0x00 Preface#
本文着眼于深度学习中的收敛性分析，作为第二部分，主要介绍了深度学习中梯度下降在（强凸光滑/光滑凸/非光滑凸/光滑非凸/非凸情况下）的收敛性证明。对于先前的定义，本文将不再赘述，读者可以先阅读 深度学习中的收敛性分析 (Part 1)。很多内容参考了,,和，少量参考 。
0x01 Definition of Convergence#
通常，深度学习的优化问题可以表示为
$$
\min_{w} f(w)
$$
其中，$w$ 是待优化的参数，$f(w)$ 是待优化的目标函数。在深度学习中，我们通常使用梯度下降法来求解优化问题，即
$$
w_{t+1} = w_t - \eta \nabla f(w_t)
$$
而一个梯度方法是收敛的可以从三个方面来定义：
-
目标函数值收敛到最优值：$\mathbb{E} f(w_T) - f^* \leq \epsilon(T)$，其中 $f^*$ 是目标函数的最优值
-
迭代序列收敛到最优解：$\mathbb{E} ||w_T - w^*||^2 \leq \epsilon(T)$，其中 $w^*$ 是参数的最优解
如果，$\epsilon(T) \to 0$，那么我们称这个梯度方法是收敛的。对于收敛优化算法，它们的收敛速率可能并不相同，通常，用 $\log \epsilon(T)$ 的衰减速率来定义优化算法的收敛速率。
- 1） 如果 $\log \epsilon(T)$ 与 $-T$ 同阶，那么我们称这个算法具有线性收敛速率。
- 2） 如果 $\log \epsilon(T)$ 比 $-T$ 衰减速度慢，那么我们称这个算法具有次线性收敛速率。
- 3） 如果 $\log \epsilon(T)$ 比 $-T$ 衰减速度快，那么我们称这个算法具有超线性收敛速率，进一步地，如果 $\log \log \epsilon(T)$ 与 $-T$ 同阶，那么我们称这个算法具有二阶收敛速率。
而在非凸优化中，由于可能存在多个局部极小点，不容易找到全局最优，因此考虑算法能否收敛到梯度为 0 的临界点。
- 利用梯度的遍历距离作为度量：$\min_{t=1,\cdots,T} \mathbb{E} ||\nabla f(w_T)||^2 \leq \epsilon(T)$ 或者 $\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}||\nabla f(w_{t})||^2$ 趋于 0
info
下面将从最强的假设 强凸+光滑 开始，逐步放松条件进行分析。
0x02 Smooth Strongly Convex with GD#
defination
假设目标函数 $f$ 是 $R^{d}$ 上的$\mu$-强凸函数，并且 $L$-光滑，当步长 $\eta \leq \frac{1}{L}$ 且起始点为 $w_0$ 时，经过 $t$ 步迭代，$f(w_T)$ 被 bounded 如下：
$$
f\left(w_{t}\right)-f^{*} \leq (1-\eta \mu)^{t}\left(f\left(w_{0}\right)-f^{*}\right)
$$
Proof:
tip
先说一个整体的证明思路，大致下面的内容也是这样的，先证明单步迭代的 bounded，然后再利用数学归纳法证明多步迭代的 bounded。其间会通过对 $\eta$ 的取值进行限制（往往通过二次函数的顶点来确定，或者双曲函数来确定）。同时注意，光滑性给了函数的一个上界，强凸性给了函数的一个下界，有时候为了统一不等式符号方向，会对函数取负号。
同时，哪怕是对函数同样的假设，在不同的 $\eta$ 设置中和不同的 bounded 中，也会有不同的收敛速率。
先看单步迭代：
$$
\begin{aligned}
f\left(w_{t+1}\right)-f\left(w_{t}\right) &=f\left(w_{t}-\eta \nabla f\left(w_{t}\right)\right)-f\left(w_{t}\right) \\
& \leq \nabla f\left(w_{t}\right)^{\top}\left(w_{t}-\eta \nabla f\left(w_{t}\right)-w_{t}\right)+\frac{L}{2}\left\|w_{t}-\eta \nabla f\left(w_{t}\right)-w_{t}\right\|^{2} \\
&=-\eta \left\|\nabla f\left(w_{t}\right)\right\|^{2}+\frac{L}{2} \eta ^{2}\left\|\nabla f\left(w_{t}\right)\right\|^{2} \\
&=\left(\frac{L}{2} \eta ^{2}-\eta \right)\left\|\nabla f\left(w_{t}\right)\right\|^{2}
\end{aligned}
$$
这时候我们通过对两项都添加负号，然后利用二次函数的顶点来确定 $\eta$ 的取值，同时希望用上强凸函数导出的性质，即
$$
2\mu (f(x)-f^{*}) \leq \|\nabla f(x)\|^2
$$
于是有
$$
\begin{aligned}
f\left(w_{t+1}\right)-f\left(w_{t}\right) &\leq \eta \left(1-\frac{L}{2} \eta \right)\left(-\left\|\nabla f\left(w_{t}\right)\right\|^{2}\right) \\
& \leq \eta \left(1-\frac{L}{2} \eta \right)\left(2\mu \left(f\left(w_{t}\right)-f^{*}\right)\right)
\end{aligned}
$$
这时，我们令 $\eta \leq \frac{1}{L}$，则有 $(1-\frac{L}{2} \eta ) \geq \frac{1}{2}$，于是有
$$
f\left(w_{t+1}\right)-f\left(w_{t}\right) \leq -\eta \mu (f\left(w_{t}\right)-f^{*})
$$
注意到，左右都是关于 $f(x)$ 的式子，在左边 $+-f^*$，得到
$$
f\left(w_{t+1}\right)-f^{*}+f^{*}-f\left(w_{t}\right) \leq -\eta \mu (f\left(w_{t}\right)-f^{*}) \\
\Rightarrow f\left(w_{t+1}\right)-f^{*} \leq (1-\eta \mu) (f\left(w_{t}\right)-f^{*})
$$
后面就归纳一下：
$$
\begin{aligned}
f\left(w_{t+1}\right)-f^{*} & \leq(1-\eta \mu)\left(f\left(w_{t}\right)-f^{*}\right) \\
& \leq(1-\eta \mu)\left(1-\eta \mu\right)\left(f\left(w_{t-1}\right)-f^{*}\right) \\
& \leq \cdots \\
& \leq(1-\eta \mu) \cdots(1-\eta \mu)\left(f\left(w_{1}\right)-f^{*}\right) \\
& \leq(1-\eta \mu)^{t+1}\left(f\left(w_{0}\right)-f^{*}\right)
\end{aligned}
$$
现在，我们得到了 boundary，来计算一下复杂度。
根据复杂度的定义，令 $f(w_t)-f^* \leq \epsilon$，则有
$$
(1-\eta \mu)^{t}(f(w_0)-f^*) \leq \epsilon \\
\Rightarrow t\log (1-\eta \mu) + \log (f(w_0)-f^*) \leq \log \epsilon \\
\Rightarrow t\log \frac{1}{1-\eta \mu} - \log (f(w_0)-f^*) \geq \log \frac{1}{\epsilon} \\
\Rightarrow t=O(\log \frac{1}{\epsilon})
$$
tip
其中，$Q=\frac{L}{\mu}$，一般被称为条件数。
从 0x02 和 0x03，我们对梯度下降法的收敛性质有以下讨论：
-
当目标函数是强凸函数时，梯度下降法的收敛速率是线性的；当目标函数是凸函数时，其收敛速率是次线性的。也就是说，强凸性质会大大提高梯度下降法的收敛速率。进一步地，强凸性之越好（即$\mu$ 越大），条件数 $Q$ 越小，收敛越快。
-
光滑性质在凸和强凸两种情形下都会加快梯度下降法的收敛速率，即 $L$ 越小（强凸情况下，条件数 $Q$ 越小），收敛越快。
0x03 Smooth Convex with GD#
defination
假设目标函数 $f$ 是 $R^{d}$ 上的凸函数，并且 $L$-光滑，当步长 $\eta =\frac{1}{L}$ 且起始点为 $w_0$ 时，经过 $t$ 步迭代，$f(w_t)$ 被 bounded 如下：
$$
f\left(w_{t}\right)-f^{*} \leq \frac{L}{2T} || w_{0} - w^{*} ||^{2}
$$
Proof:
由上面的证明，我们已经知道在 $L$-光滑的情况下，有
$$
f(w_{t+1})-f(w_{t}) \leq \eta \left(1-\frac{L}{2} \eta \right)\left(-\left\|\nabla f\left(w_{t}\right)\right\|^{2}\right)
$$
根据凸性质，有
$$
f(w_{t})-f^{*} \leq \nabla f(w_{t})^{\top}(w_{t}-w^{*})
$$
根据梯度下降有等式
$$
\left \| w_{t+1} - w^{*} \right \|^{2} = \left \| w_{t} - w^{*} \right \|^{2} - 2 \eta \nabla f(w_{t})^{\top}(w_{t}-w^{*}) + \eta^{2} \left \| \nabla f(w_{t}) \right \|^{2}
$$
我们用 GD 得到的等式中的 $\nabla f(w_{t})^{\top}(w_{t}-w^{*})$ 替换掉凸性质中的，有
$$
\begin{aligned}
f(w_{t+1})-f^{*} &= f(w_{t+1})-f(w_{t})+f(w_{t})-f^{*} \\
& \leq \eta \left(1-\frac{L}{2} \eta \right)\left(-\left\|\nabla f\left(w_{t}\right)\right\|^{2}\right) + \nabla f(w_{t})^{\top}(w_{t}-w^{*}) \\
&= \eta \left(1-\frac{L}{2} \eta \right)\left(-\left\|\nabla f\left(w_{t}\right)\right\|^{2}\right) + \frac{1}{2\eta} \left \| w_{t} - w^{*} \right \|^{2} - \frac{1}{2\eta} \left \| w_{t+1} - w^{*} \right \|^{2} + \frac{\eta}{2} \left \| \nabla f(w_{t}) \right \|^{2} \\
& = (\frac{L}{2}\eta ^2-\eta + \frac{\eta}{2}) \left \| \nabla f(w_{t}) \right \|^{2} + \frac{1}{2\eta} \left \| w_{t} - w^{*} \right \|^{2} - \frac{1}{2\eta} \left \| w_{t+1} - w^{*} \right \|^{2} \\
& = \frac{\eta}{2}(L\eta - 1) \left \| \nabla f(w_{t}) \right \|^{2} + \frac{1}{2\eta} \left \| w_{t} - w^{*} \right \|^{2} - \frac{1}{2\eta} \left \| w_{t+1} - w^{*} \right \|^{2}
\end{aligned}
$$
注意这里，我们令 $\eta = \frac{1}{L}$，于是就能够将 $||\nabla f(w_{t})||^2$ 的项消去，这个取值其实是从 $f(w_{t+1})-f(w_{t})$ 的不等式中取值得到的，因为要小于最小值，后面其实是一个等式替换，不涉及 $\eta$ 的取值。
$$
f(w_{t+1})-f^{*} \leq \frac{L}{2} \left \| w_{t} - w^{*} \right \|^{2} - \frac{L}{2} \left \| w_{t+1} - w^{*} \right \|^{2}
$$
看到这个相比就知道后面怎么做了，就是一个求和了
$$
\begin{aligned}
\sum_{t=0}^{T} f(w_{t+1})-f^{*} &\leq \frac{L}{2} \sum_{t=0}^{T} \left \| w_{t} - w^{*} \right \|^{2} - \frac{L}{2} \sum_{t=0}^{T-1} \left \| w_{t+1} - w^{*} \right \|^{2} \\
&= \frac{L}{2} \left \| w_{0} - w^{*} \right \|^{2} - \frac{L}{2} \left \| w_{T+1} - w^{*} \right \|^{2} \\
&\leq \frac{L}{2} \left \| w_{0} - w^{*} \right \|^{2}
\end{aligned}
$$
注意等式左边也可以继续进行放缩，即
$$
\min_{t=1,\cdots,T} f(w_{t})-f^{*} \leq \frac{L}{2T} \left \| w_{0} - w^{*} \right \|^{2}
$$
证毕。
这时候，我们得到了 boundary，来计算一下复杂度。
根据复杂度的定义，令 $f(w_t)-f^* \leq \epsilon$，则有
$$
f(w_{t}-f^{*}) \leq \frac{L}{2T} \left \| w_{0} - w^{*} \right \|^{2} \leq \epsilon \\
T \geq \frac{L}{2\epsilon} \left \| w_{0} - w^{*} \right \|^{2} \\
\Rightarrow T=O(\frac{1}{\epsilon})
$$
是次线性的收敛速率。
0x04 Non-smooth Convex with GD#
如果我们仅剩凸性质，那么必须加上梯度有界的假设才能 bound 住，从而保证收敛，因而我们可以得到如下的结论：
defination
假设目标函数 $f$ 是 $R^{d}$ 上的凸函数，当步长
$\eta =\frac{f(w_{0})-f^*}{\sqrt{T+1}G}$
且起始点为 $w_{0}$ 时，经过 $t$ 步迭代，$f(w_{t})$ 被 bounded 如下：
$$
\min_{t=0,\cdots,T} f\left(w_{t}\right)-f^{*} \leq \frac{G||w_{0}-w^{*}||^{2}}{\sqrt{T+1}}
$$
Proof:
其实和上面是大概相同的思路，有
$$
\begin{aligned}
f(w_{t})-f^{*} &\leq \nabla f(w_{t})^{\top}(w_{t}-w^{*}) \\
&= \frac{1}{2\eta} \left \| w_{t} - w^{*} \right \|^{2} - \frac{1}{2\eta} \left \| w_{t+1} - w^{*} \right \|^{2} + \frac{\eta}{2} \left \| \nabla f(w_{t}) \right \|^{2} \\
&\leq \frac{1}{2\eta} \left \| w_{t} - w^{*} \right \|^{2} - \frac{1}{2\eta} \left \| w_{t+1} - w^{*} \right \|^{2} + \frac{\eta}{2} G^{2}
\end{aligned}
$$
同样对左右进行求和
$$
\begin{aligned}
\sum_{t=0}^{T} f(w_{t})-f^{*} &\leq \sum_{t=0}^{T} \frac{1}{2\eta} (\left \| w_{t} - w^{*} \right \|^{2} - \left \| w_{t+1} - w^{*} \right \|^{2}) + (T+1) \frac{\eta}{2} G^{2} \\
&= \frac{1}{2\eta} \left \| w_{0} - w^{*} \right \|^{2} - \frac{1}{2\eta} \left \| w_{T+1} - w^{*} \right \|^{2} + \frac{\eta (T+1)}{2} G^{2} \\
&\leq \frac{1}{2\eta} \left \| w_{0} - w^{*} \right \|^{2} + \frac{\eta (T+1)}{2} G^{2} \\
\end{aligned}
$$
即
$$
\min_{t=0,\cdots,T} f\left(w_{t}\right)-f^{*} \leq \frac{1}{2\eta (T+1)} \left \| w_{0} - w^{*} \right \|^{2} + \frac{\eta}{2}G^{2}
$$
根据小学二年级的对勾函数，我们有当 $\eta = \sqrt{\frac{||w_{0}-w^{*}||^{2}}{G^{2}(T+1)}}=\frac{||w_{0}-w^{*}||}{G\sqrt{T+1}}$ 时，有
$$
\min_{t=0,\cdots,T} f\left(w_{t}\right)-f^{*} \leq \frac{G||w_{0}-w^{*}||^{2}}{\sqrt{T+1}}
$$
证毕。
复杂度很容易就看出来
$$
\frac{G||w_{0}-w^{*}||^{2}}{\sqrt{T+1}} \leq \epsilon \\
T \geq \frac{G^{2}||w_{0}-w^{*}||^{2}}{\epsilon^{2}} \\
\Rightarrow T=O(\frac{1}{\epsilon^{2}})
$$
是次线性的收敛速率。
这里有一个 Alternative 的方法，反着推比较容易，我个人觉得不太容易从正面想到。
defination
假设目标函数 $f$ 是 $R^{d}$ 上的凸函数，当步长
$\eta = \frac{f(w_{t})-f^{*}}{||\nabla f(w_{t})||^2}$
且起始点为 $w_{0}$ 时，经过 $t$ 步迭代，$f(w_{t})$ 被 bounded 如下：
$$
\min_{t=0}^{T} f(w_{t})-f^{*}\leq \frac{G\left || w_{0}-w_{*}\right ||}{\sqrt{T+1}}
$$
Proof:
从梯度下降出发：
$$
\begin{aligned}
\left \|w_{t+1}-w^{*}\right \|^{2} &= \left \|w_{t}-\eta \nabla f(w_{t})-w^{*}\right \|^{2} \\
&= \left \|w_{t}-w^{*}\right \|^{2} - 2\eta \nabla f(w_{t})^{\top}(w_{t}-w^{*}) + \eta^{2} \left \| \nabla f(w_{t}) \right \|^{2} \\
&= \left \|w_{t}-w^{*}\right \|^{2} - 2\eta (f(w_{t})-f^{*}) + \eta^{2} \left \| \nabla f(w_{t}) \right \|^{2}
\end{aligned}
$$
这时，是一个关于 $\eta$ 的二次函数，直接令 $\eta = \frac{f(w_{t})-f^{*}}{||\nabla f(w_{t})||^2}$，这个也称为 Polyak 步长，于是有
$$
\left \|w_{t+1}-w^{*}\right \|^{2} \leq \left \|w_{t}-w^{*}\right \|^{2} - \frac{(f(w_{t})-f^{*})^{2}}{||\nabla f(w_{t})||^{2}}
$$
移项得到
$$
(f(w_{t})-f^{*})^{2} \leq ||\nabla f(w_{t})||^{2} (\left \|w_{t}-w^{*}\right \|^{2} - \left \|w_{t+1}-w^{*}\right \|^{2}) \\
\sum_{t=0}^{T} (f(w_{t})-f^{*})^{2} \leq \sum_{t=0}^{T} G^{2} (\left \|w_{t}-w^{*}\right \|^{2} - \left \|w_{t+1}-w^{*}\right \|^{2}) \\
\Rightarrow \min_{t=0}^{T} (f(w_{t})-f^{*})^{2} \leq \frac{G^2\left \| w_{0}-w_{*}\right \|^2}{T+1} \\
\Rightarrow \min_{t=0}^{T} (f(w_{t})-f^{*}) \leq \frac{G\left \| w_{0}-w_{*}\right \|}{\sqrt{T+1}}
$$
与上面方法选择的 $\eta$ 不同，但是有相同的收敛速率。
0x05 Smooth non-convex with GD#
defination
假设目标函数 $f$ 是 $R^{d}$ 上的 $L$-光滑函数，当步长 $\eta =\frac{1}{L}$ 且起始点为 $w_0$ 时，经过 $t$ 步迭代，$f(w_t)$ 被 bounded 如下：
$$
\min_{t=0,\cdots,T} \left||\nabla f(w_{t})\right||^{2} \leq \frac{2L (f(w_{0})-f(w^{*}))}{(T+1)}
$$
Proof:
我们直接从上面的结论出发，有
$$
\begin{align}
f(w_{t+1})-f(w_{t}) &\leq \eta \left(1-\frac{L}{2} \eta \right)\left(-\left\|\nabla f\left(w_{t}\right)\right\|^{2}\right) \\
\eta (1-\frac{L}{2}\eta) \left\|\nabla f\left(w_{t}\right)\right\|^{2} &\leq f(w_{t})-f(w_{t+1})
\end{align}
$$
左边取最大值，即 $\eta = \frac{1}{L}$，有
$$
\frac{1}{2L} \left\|\nabla f\left(w_{t}\right)\right\|^{2} \leq f(w_{t})-f(w_{t+1})
$$
简单求和，再放缩一下：
$$
\begin{aligned}
\sum_{t=0}^{T} \frac{1}{2L} \left\|\nabla f\left(w_{t}\right)\right\|^{2} &\leq \sum_{t=0}^{T} f(w_{t})-f(w_{t+1}) \\
&= f(w_{0})-f(w_{T+1}) \\
&\leq f(w_{0})-f(w^{*})
\end{aligned}
$$
证毕。
0x06 Strongly Convex and Non-smooth with GD#
好了到这里只剩最后一个了，但注意这里除了强凸性，还需要 $L$-Lipschitz 连续性，相当于各点梯度一致有界，至少梯度不能直接飞了…
defination
假设目标函数 $f$ 是 $R^{d}$ 上的 $\mu$-强凸函数，且 $L$-Lipschitz 连续，当步长 $\eta_{t} =\frac{2}{\eta (t+1)}$ 且起始点为 $w_0$ 时，经过 $t$ 步迭代，$f(w_t)$ 被 bounded 如下：
$$
\min_{t=0,\cdots,T} f(w_{t})-f^{*} \leq \frac{2L^{2}}{\mu (T+1)}
$$
Proof:
由 GD 和 强凸性
$$
\left \| w_{t+1} - w^{*} \right \|^{2} = \left \| w_{t} - w^{*} \right \|^{2} - 2 \eta \nabla f(w_{t})^{\top}(w_{t}-w^{*}) + \eta^{2} \left \| \nabla f(w_{t}) \right \|^{2} \\
\leq (1-\eta \mu ) \left \| w_{t} - w^{*} \right \|^{2} - 2 \eta (f(w_{t})-f^{*}) + \eta^{2} \left \| \nabla f(w_{t}) \right \|^{2}
$$
有 $L$-Lipschitz 连续性
$$
|f(w_{t}) - f^{*}| \leq L \left \| w_{t} - w^{*} \right \| \\
\frac{f(w_{t}) - f^{*}}{\left \| w_{t} - w^{*} \right \|} = \left \| \nabla f(w_{t}) \right \| \leq L
$$
于是有
$$
\begin{aligned}
f(w_{t})-f^{*} &\leq \frac{1}{2 \eta} (1-\eta \mu ) \left \| w_{t} - w^{*} \right \|^{2} - \frac{1}{2 \eta} \left \| w_{t+1} - w^{*} \right \|^{2} + \frac{\eta}{2} L^{2} \\
&= \frac{1}{2 \eta} (1-\eta \mu ) \left \| w_{t} - w^{*} \right \|^{2} - \frac{1}{2 \eta} \left \| w_{t} - w^{*} \right \|^{2} + \frac{1}{2 \eta} \left \| w_{t} - w^{*} \right \|^{2} - \frac{1}{2 \eta} \left \| w_{t+1} - w^{*} \right \|^{2} + \frac{\eta}{2} L^{2} \\
&= - \frac{\mu}{2} \left \| w_{t} - w^{*} \right \|^{2} + \frac{\eta}{2}L^2 + \frac{1}{2 \eta} \left \| w_{t} - w^{*} \right \|^{2} - \frac{1}{2 \eta} \left \| w_{t+1} - w^{*} \right \|^{2}
\end{aligned}
$$
正常求和放缩可能只能得到次线性的收敛速率，如果配方裂项，可以得到一个更紧的 bound。通过解方程的方法设 $t$ 项的系数为 $c\cdot (t-1)$ （注意到最后有一个常数项需要乘 $t$ 之后才方便放缩，则有
$$
\left\{\begin{matrix}
c\cdot (t-1) = x - \mu \\
c\cdot (t+1) = x
\end{matrix}\right.
$$
解得
$$
\left\{\begin{matrix}
c = \frac{\mu}{2} \\
x = \frac{\mu(t+1)}{2}
\end{matrix}\right.
$$
也就是，$\frac{1}{\eta} = \frac{\mu(t+1)}{2}$，即 $\eta = \frac{2}{\mu (t+1)}$，于是有
$$
\begin{aligned}
f(w_{t})-f^{*} &\leq \frac{1}{8} [\mu (t-1) \left \| w_{t} - w^{*} \right \|^{2} - \mu (t+1) \left \| w_{t+1} - w^{*} \right \|^{2}] + \frac{1}{\mu (t+1)}L^2 \\
t(f(w_{t})-f^{*}) &\leq \frac{1}{8} [\mu t(t-1) \left \| w_{t} - w^{*} \right \|^{2} - \mu t(t+1) \left \| w_{t+1} - w^{*} \right \|^{2}] + \frac{t}{\mu (t+1)}L^2 \\
\sum_{t=0}^{T} t(f(w_{t})-f^{*}) &\leq \frac{1}{8} [0 - \mu T(T+1) \left \| w_{T+1} - w^{*} \right \|^{2}] + \frac{T}{\mu}L^2 \\
\sum_{t=0}^{T} t(\min_{t={0,\cdots,T}} f(w_{t})-f^{*}) &\leq \frac{T}{\mu}L^2
\end{aligned}
$$
注意左边是个等差数列了，于是有
$$
\min_{t={0,\cdots,T}} f(w_{t})-f^{*} \leq \frac{2L^{2}}{\mu (T+1)}
$$
证毕。
0x07 Conclusion#
其实还有一个非凸非光滑，但是这个情况下，梯度下降法不一定能收敛…
我们用到梯度有界的假设，在 非光滑凸 和 非光滑强凸，我们不难看出，非光滑对收敛性是一个很不友好的 setting，而强凸往往能保证有着很好的收敛速率，光滑强凸和非光滑强凸都能够带来线性的收敛速率。
Reference#
