前言
本文我们简要分析SGD的收敛性能。
SGD回顾
在优化器三：SGD基础一文中我们介绍了SGD与MSGD：
$$ \boldsymbol{\theta}^{(\tau+1)}=\boldsymbol{\theta}^{(\tau)}-\eta^{(\tau)} \cdot g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{i_\tau}) \tag{1} $$
其中：
$$ g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]})= \begin{cases} \nabla L_i(\boldsymbol{\theta}^{(\tau)})=\nabla L(\boldsymbol{\theta}^{(\tau)};\boldsymbol{\xi}_{[i_\tau]})，&(SGD)\\ \frac{1}{N_{i_\tau}}\sum\limits_{j=1}^{N_{i_\tau}} \nabla L(\boldsymbol{\theta}^{(\tau)};\xi_{[i_\tau],j}),&(MSGD) \end{cases}\tag{2} $$
此外还需要注意到的是，$\boldsymbol{\theta}^{(\tau)}$只与SGD的历史信息也即$\boldsymbol{\theta}^{(0)},\boldsymbol{\xi}_{i_1}\cdots,\boldsymbol{\theta}^{(\tau-1)},\boldsymbol{\xi}_{i_{\tau-1}}$有关，与$\boldsymbol{\xi}_{i_\tau}$是无关的。故而$\boldsymbol{\theta}^{(\tau)}$在算子$\mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[\cdot]$与$\mathbb{D}_{\boldsymbol{\xi}_{i_\tau}}[\cdot]$下是个常量。为了后文的表述方便，我们引入算子：
$$ \mathbb{E}[\cdot]=\mathbb{E}_{\boldsymbol{\xi}_{i_0}}\mathbb{E}_{\boldsymbol{\xi}_{i_1}}\cdots \mathbb{E}_{\boldsymbol{\xi}_{i_{\tau-1}}}\mathbb{E}_{\boldsymbol{\xi}_{i_\tau}} [\cdot]\tag{3} $$
此外由（1）可知，$\boldsymbol{\theta}^{(\tau)}$只与历史信息$\boldsymbol{\theta}^{(0)},\boldsymbol{\xi}_{i_1}\cdots,\boldsymbol{\theta}^{(\tau-1)},\boldsymbol{\xi}_{i_{\tau-1}}$有关，与$\boldsymbol{\xi}_{i_\tau}$是无关的，具体来说：
$$ \mathbb{E}_{\boldsymbol{\xi}_{i_k}}[\mathcal L(\boldsymbol{\theta}^{(\tau)})]=\mathcal L(\boldsymbol{\theta}^{(\tau)}),\forall k\geq \tau \tag{4} $$
我们在分析Vanilla Gradient Descent时介绍道，刻画收敛无非是分析三个序列之一：$\{\epsilon(\tau)\}$，$\{\mathbb{E}[\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \|]\}$与$\{\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|\}$。而为了刻画收敛性能则定义了$\epsilon(\tau),\tau(\epsilon)$以及$\tau_S(\epsilon)$。假设我们下文中研究的$\mathcal L$均为$L$-光滑的，我们先来研究一下$\{\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|\}$与$\tau_S(\epsilon)$，显然这在强凸、凸与非凸时都是能研究的。
序列$\{\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|\}$的分析
现在，我们期望仅从$L$-光滑这一个条件分析一下$\{\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|\}$的情况。由$L$-光滑：
$$ \mathcal L(\boldsymbol{\theta}^{(\tau+1)})\leq\mathcal L(\boldsymbol{\theta}^{(\tau)})+\left\langle g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]}),\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^{(\tau)} \right\rangle+\frac L2 \|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^{(\tau)} \|^2\tag{5} $$
代入（1）式并在两边对$\boldsymbol{\xi}_{i_\tau}$取期望，我们有：
$$ \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}} [\mathcal L(\boldsymbol{\theta}^{(\tau+1)})]-\mathcal L(\boldsymbol{\theta}^{(\tau)}) \leq -\eta^{(\tau)} \left\langle\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)}), \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}} [g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{i_\tau})]\right\rangle+\frac{1}{2}\left(\eta^{(\tau)}\right)^2 L\cdot \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[\|g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{i_\tau})\|^2]\tag{6} $$
同时我们在前一篇文章中说明了SGD的更新方向是全梯度的无偏估计！也即：
$$ \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]})]=\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\tag{7} $$
从而我们有：
$$ \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}} [\mathcal L(\boldsymbol{\theta}^{(\tau+1)})]-\mathcal L(\boldsymbol{\theta}^{(\tau)}) \leq -\eta^{(\tau)}\|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)}) \|^2 +\frac{1}{2}\left(\eta^{(\tau)}\right)^2 L\cdot \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[\|g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{i_\tau})\|^2]\tag{8} $$
移项并考虑$\boldsymbol{\xi}_{i_0},\cdots,\boldsymbol{\xi}_{i_\tau}$的全期望，则：
$$ \eta^{(\tau)}\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|^2\leq \mathbb{E}[\epsilon(\tau)-\epsilon(\tau+1)]+\frac L2 \left(\eta^{(\tau)} \right)^2\mathbb{E}[\|g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]}) \|^2]\tag{9} $$
所以一个自然的想法是，我能不能拿掉（9）式右边的随机性，将不等号右边变为一个常数，进而通过累加得出$\tau_S(\epsilon)$的上界？！！我们引入约束：
$$ \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[\|g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]})\|^2]\leq G^2\tag{10} $$
代入（9），并累加：
$$ \min_{k=0,\cdots,\tau}\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(k)})\|^2\leq \frac{\mathbb{E}[\epsilon(0)-\epsilon(\tau+1)]}{\sum\limits_{k=0}^\tau \eta^{(k)}}+\frac{LG^2}{2}\frac{\sum\limits_{k=0}^\tau \left(\eta^{(k)}\right)^2}{\sum\limits_{k=0}^\tau \eta^{(k)}}\tag{11} $$
如果$G^2=0$，此时SGD便失去了随机性也即退化为了Vanilla Gradient Descent，此时$\tau_S(\epsilon)\geq\Omega(\frac 1{\epsilon^2})$，这与我们在优化器二：Vanilla Gradient Descent中得到的结论是一致的。
如果考虑随机性也即$G^2>0$时，针对不同的步长选择，我们可以得到不同的结论。若步长固定$\eta^{(\tau)}\equiv \eta>0$，我们可以说$\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|$以$O(\frac{1}{\eta\tau})$的速度收敛至一个局部极小值点附近，因为方差与噪音阻止了其进一步下降：
$$ \lim_{\tau\to \infty}\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|^2=\frac{LG^2\eta}{2} $$
选择相对较小的固定步长会使得优化误差收敛至更接近最优值，但是收敛速率会变得更低。因此，方差越小，固定步长的策略对SGD的收敛速度更有效！
我们再来考虑步长衰减，也即$\eta^{(\tau)}\geq \eta^{(\tau+1)},\lim_{\tau\to\infty}\eta^{(\tau)}=0$时的情况。容易知道：
$$ \sum_{k=0}^\infty \eta^{(k)}=\infty,\ \sum_{k=0}^\infty \left(\eta^{(k)} \right)^2<\infty $$
是$\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|$收敛的一个充分条件。如果要半定量地刻画收敛速度，则一般采用特别易于分析的多项式衰减：
$$ \eta^{(\tau)}=\frac c {(\tau+1)^p},\ p>0 $$
注意到：
$$ \int_{0}^{\tau+1}\frac c{(x+1)^p}\text dx\leq \sum_{k=0}^\tau \eta^{(\tau)}\leq 1+\int_{1}^{\tau+1} \frac 1 {x^p}\text dx\tag{12} $$
两个经典的$p$取值为$1$与$\frac 12$。在$p=1$时，$\tau_S(\epsilon)\geq \Omega(e^{\epsilon^{-2}})$，在$p=\frac 12$时，$\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|$的收敛速度为$O(\frac{\log \tau}{\sqrt{\tau}})$，求解$\tau_S(\epsilon)$需要解超越方程：$\epsilon^2=\log \tau/\sqrt{\tau}$，但是大致来看，$\tau_S(\epsilon)\geq \Omega(\frac 1{\epsilon^2})$。
我们可以将$\{\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|\}$收敛性的结论小结如下：
| 步长 | $\ | \nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\ | $ | $\tau_S(\epsilon)$ |
|---|---|---|---|---|
| 固定，$\eta^{(\tau)}\equiv\eta>0$ | $O(\frac 1{\eta\tau})+\frac{LG^2\eta}{2}$ | - | ||
| 衰减，$\eta^{(\tau)}=\frac{c}{\tau+1}$ | $O(\frac 1 {\log{\tau}})$ | $\Omega(e^{\epsilon^{-2}})$ | ||
| 衰减，$\eta^{(\tau)}=\frac c{\sqrt{\tau+1}}$ | $O(\frac{\log \tau}{\sqrt{\tau}})$ | $\tilde\Omega(\frac 1{\epsilon^4})$ |
其中$\tilde\Omega$代表不精确的估计值，我们这里是略去了$\log\frac 1\epsilon$有关的项。
序列$\{\epsilon(\tau)\}$
接下来我们研究$\{\epsilon(\tau) \}$的收敛性，其中：$\epsilon(\tau)=\mathbb{E}[\mathcal L(\boldsymbol{\theta}^{(\tau)})-\mathcal L(\boldsymbol{\theta}^*)]$。首先假设$\mathcal L$是$\mu$-强凸的，也即：
$$ \|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|^2\geq 2\mu\epsilon(\tau)\tag{13} $$
结合（8）与（10），则有：
$$ \mathbb{E}[\epsilon(\tau+1)]\leq (1-2\mu\eta^{(\tau)})\mathbb{E}[\epsilon(\tau)]+\frac{LG^2}{2}\left(\eta^{(\tau)} \right)^2\tag{14} $$
若步长固定$\eta^{(\tau)}\equiv \eta>0$，则：
$$ \begin{align} \mathbb{E}[\epsilon(\tau)]&=\mathbb{E}[\mathcal L(\boldsymbol{\theta}^{(\tau)})-\mathcal L(\boldsymbol{\theta}^*)]\\ &\leq\frac{LG^2\eta}{4\mu}+(1-2\mu\eta)^\tau\cdot\left(\epsilon(0)-\frac{LG^2\eta}{4\mu}\right) \end{align}\tag{15} $$
如果$G^2=0$，那么SGD可以线性收敛到最优值。如果梯度计算存在噪声，则会失去该特性，但仍然可以使用固定的步长，使得$\mathcal L(\boldsymbol{\theta}^{(\tau)})$以线性收敛速度收敛到最优值附近。而且类似于我们刚刚分析的$\{\|\nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)})\|\}$，我们也可以得到结论：方差越小，固定步长的策略对SGD的收敛速度更有效！
如果步长衰减，则：
$$ \mathbb{E}[\epsilon(\tau+1)]\leq \frac{LG^2 \eta^{(\tau)}}{4\mu}+\prod_{k=0}^\tau (1-2\mu\eta^{(k)})\cdot \left[\epsilon(0)-\frac{LG^2\eta^{(0)}}{4\mu} \right]\tag{16} $$
容易知道，在$\eta^{(k)}<\frac 1{2\mu}$且$\sum_{k=0}^\infty \eta^{(k)}=\infty$时，由$\log(1-x)<-x,x\in(0,1)$，则：
$$ \lim_{\tau\to\infty}\prod_{k=0}^\tau (1-2\mu\eta^{(k)})=0\tag{17} $$
加之$\eta^{(\tau)}\geq \eta^{(\tau+1)},\lim_{\tau\to\infty}\eta^{(\tau)}=0$，故而$\mathbb{E}[\epsilon(\tau)]$必然收敛至0。为了半定量刻画收敛速度，我们同样考虑多项式衰减的情况。若仍有：$\eta^{(k)}<\frac 1{2\mu}$，且$\eta^{(k)}=\frac c{\tau+1}$，则有：
$$ \begin{align} &\mathbb{E}[\epsilon(\tau)]\leq \frac{\nu}{\tau+1}\\ where:\ &\nu=\max\left\{\frac{LG^2c^2}{2(2c\mu-1)},\epsilon(0) \right\} \end{align}\tag{18} $$
为了证明上式，我们对$\tau$使用数学归纳法。显然$\tau=0$时（18）式成立。现设$\tau(\geq0)$时（18）成立，结合（14），我们有：
$$ \begin{align} \mathbb{E}[\epsilon(\tau+1)]&\leq (1-2\mu\eta^{(\tau)})\frac{\nu}{ \tau+1}+\frac 12 \left(\eta^{(\tau)}\right)^2LG^2 &归纳假设\\ &\leq \frac{\tau+1-2c\mu}{(\tau+1)^2}\nu+ \frac{LG^2c^2}{2(\tau+1)^2}&\eta^{(\tau)}=\frac{c}{\tau+1}\\ &\leq \frac{\tau}{(\tau+1)^2}\nu-\frac{2c\mu-1}{(\tau+1)^2}\nu+\frac{LG^2c^2}{2(\tau+1)^2}&\\ &\leq \frac{\tau}{(\tau+1)^2}\nu+\frac{LG^2c^2-2(2c\mu-1)\nu}{2(\tau+1)^2}&\nu\geq \frac{LG^2c^2}{2(2c\mu-1)}\\ &\leq \frac{\nu}{\tau + 2}&\tau(\tau+2)\leq (\tau+1)^2 \end{align} $$
我们可以总结一下$L$-光滑+$\mu$-强凸时$\{\epsilon(\tau)\}$的收敛情况：
| 步长 | $\mathbb{E}[\epsilon(\tau)]$ | $\tau(\epsilon)$ |
|---|---|---|
| 固定，$\eta^{(\tau)}\equiv\eta\in(0,\frac 1{2\mu})$ | $\frac{LG^2\eta}{4\mu}+O\left((1-2\mu\eta)^\tau\right)$ | - |
| 衰减，$\eta^{(\tau)}=\frac{c}{\tau+1}\in(0,\frac 1{2\mu})$ | $O(\frac 1{\tau})$ | $\Omega(\frac1\epsilon)$ |
容易看到，固定步长时初期以线性速度快速收敛，但最终只能收敛至最优解附近；而衰减步长虽能收敛至最优解，可收敛速度是次线性的。那么有没有可能将二者联系起来取长补短，构成一种阶段性的SGD，从而取得更好的效果呢？留待读者思考。
我们再来看一般凸函数的情况。对于（1）两边同时减去$\boldsymbol{\theta}^*$再平方有：
$$ \|\boldsymbol{\theta}^{(\tau+1)} -\boldsymbol{\theta}^*\|^2=\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \|^2-2\eta^{(\tau)}\left\langle g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]}),\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \right\rangle+\left(\eta^{(\tau)} \right)^2\|g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]}) \|^2\tag{19} $$
两边对$\boldsymbol{\xi}_{i_\tau}$取期望，有：
$$ \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[\|\boldsymbol{\theta}^{(\tau+1)} -\boldsymbol{\theta}^*\|^2]=\|\boldsymbol{\theta}^{(\tau)} -\boldsymbol{\theta}^*\|^2-2\eta^{(\tau)}\left\langle \nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)}), \boldsymbol{\theta}^{(\tau)} -\boldsymbol{\theta}^*\right\rangle+\left(\eta^{(\tau)} \right)^2\mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[ \|g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]}) \|^2]\tag{20} $$
由凸性得：
$$ \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[\|\boldsymbol{\theta}^{(\tau+1)} -\boldsymbol{\theta}^*\|^2\leq\|\boldsymbol{\theta}^{(\tau)} -\boldsymbol{\theta}^*\|^2-2\eta^{(\tau)}\epsilon(\tau)+\left(\eta^{(\tau)} \right)^2\mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[ \|g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]}) \|^2]\tag{21} $$
我们延续（10）的假设，结合（21）我们有：
$$ \begin{align} 2\sum_{k=0}^\tau \mathbb{E}[\epsilon(k)]&\leq\frac{1}{\eta^{(0)}}\mathbb{E}_{\boldsymbol{\xi}_{i_0}}[\|\boldsymbol{\theta}^{(0)}-\boldsymbol{\theta}^* \|^2]\\ &+\sum_{k=0}^{\tau-1}\left(\frac{1}{\eta^{(k+1)}}-\frac{1}{\eta^{(k)}} \right)\mathbb{E}_{\boldsymbol{\xi}_{i_0}}\cdots\mathbb E_{\boldsymbol{\xi}_{i_{k+1}}}[\|\boldsymbol{\theta}^{(k+1)}-\boldsymbol{\theta}^* \|]\\ &-\frac{1}{\eta^{(\tau)}}\mathbb{E}[\|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^* \|^2]+G^2\sum_{k=0}^\tau \eta^{(k)} \end{align} $$
如果我们进一步假设：$\mathbb{E}[\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \|^2]\leq D^2$，那么我们有：
$$ \sum_{k=0}^\tau \mathbb{E}[\epsilon(k)]\leq \frac {D^2}{2\eta^{(\tau)}} + \frac{G^2}{2}\sum_{k=0}^\tau \eta^{(k)}\tag{22} $$
同时我们注意到：$\sum_{k=0}^\tau \mathbb{E}_{\boldsymbol{\xi}_{i_0}}\cdots\mathbb{E}_{\boldsymbol{\xi}_{i_k}}[\epsilon(k)]\geq (\tau+1)\mathbb{E}[\epsilon(\tau)]$，所以：
$$ \mathbb{E}[\epsilon(\tau)]\leq \frac{D^2}{2\eta^{(\tau)}(\tau+1)}+\frac{G^2}{2(\tau+1)}\sum_{k=0}^\tau \eta^{(k)}\tag{23} $$
若步长采用多项式衰减：
$$ \eta^{(\tau)} = \frac{c}{(\tau + 1)^p},\ c,p>0,\ \tau\geq 0 $$
则有：
$$ \mathbb{E}[{\epsilon(\tau)}]\leq \frac{D^2}{2c}(\tau+1)^{p-1}+\frac{G^2c}{2(1-p)(\tau+1)^p}\tag{24} $$
此时$\mathbb{E}[\epsilon(\tau)]\leq O(\tau^{\max\{p-1,-p\}})$，显然地当$p=\frac 12$时$\mathbb{E}[\epsilon(\tau)]$有最优上界$O(\frac 1{\sqrt{\tau}})$，具体地：
$$ \mathbb{E}[\epsilon(\tau)]\leq \frac{D^2+2G^2c^2}{2c\sqrt{\tau+1}},\ \tau(\epsilon)\geq \left(\frac{D^2+2G^2c^2}{2c\epsilon}\right)^2-1=\Omega(\frac{1}{\epsilon^2})\tag{25} $$
注意到我们在一般凸函数的分析中没有用到$L$-光滑，但是添加了一个$\mathbb{E}[\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \|^2]\leq D^2$的假设。
序列$\{\mathbb{E}[\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \|]\}$
最后我们试着来分析一下$\{\mathbb{E}[\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \|]\}$，一般而言这是最不好分析的..为了表述方便，我们记：
$$ \boldsymbol{d}^{(\tau)}=\mathbb{E}[\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \|^2]\tag{26} $$
我们假设$\mathcal L$是$L$-光滑且$\mu$-强凸的。我们重新考虑（20）式：
$$ \mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[\|\boldsymbol{\theta}^{(\tau+1)} -\boldsymbol{\theta}^*\|^2]=\|\boldsymbol{\theta}^{(\tau)} -\boldsymbol{\theta}^*\|^2-2\eta^{(\tau)}\left\langle \nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)}), \boldsymbol{\theta}^{(\tau)} -\boldsymbol{\theta}^*\right\rangle+\left(\eta^{(\tau)} \right)^2\mathbb{E}_{\boldsymbol{\xi}_{i_\tau}}[ \|g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]}) \|^2]\tag{20} $$
结合强凸性：
$$ \left\langle \nabla \mathcal{L}(\boldsymbol{\theta}^{(\tau)}), \boldsymbol{\theta}^{(\tau)} -\boldsymbol{\theta}^*\right\rangle\geq \mu \|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \|^2\tag{27} $$
所以如果同样满足约束（10），我们有：
$$ \boldsymbol{d}^{(\tau+1)}-\frac{G^2\eta^{(\tau)}}{2\mu}\leq (1-2\mu\eta^{(\tau)})\left(\boldsymbol{d}^{(\tau)}-\frac{G^2\eta^{(\tau)}}{2\mu} \right)\tag{28} $$
此时，我们得到了一个类似于（14）的式子，所以沿用我们在分析强凸情况下的序列$\{\epsilon(\tau) \}$的方法，我们可以分析出$\boldsymbol{d}^{(\tau)}$的收敛性能。具体地：
| 步长 | $\boldsymbol{d}^{(\tau)}$ |
|---|---|
| 固定，$\eta^{(\tau)}\equiv\eta\in(0,\frac 1{2\mu})$ | $\frac{G^2\eta}{2\mu}+O\left((1-2\mu\eta)^\tau\right)$ |
| 衰减，$\eta^{(\tau)}=\frac{c}{\tau+1}\in(0,\frac 1{2\mu})$ | $O(\frac{1}{\tau})$ |
小结
本文我们研究了SGD在$L$-光滑+$\mu$-强凸、一般凸函数以及非凸情况下的表现，事实上这个结果是很粗糙的，很多研究成果在更松条件下取得了更紧的边界，这里就不展开了，有时间再介绍相关工作。
总结一下本文的结果：
如果我们讨论的是必然收敛至最优解的情况，则我们可以说SGD在强凸、凸的情况下的收敛速度分别为：$O(\frac{1}{\tau})$、$O(\frac 1{\sqrt{\tau}})$。而且在非凸时必然收敛至一个局部最优点。
最后对SGD做一个总的分析吧。我们可以这样说：SGD是一个好算法，但它并不完美。说他是一个好算法，是说它仅用一个样本就达到了还不错的收敛速度，相比于GD，在计算效率上是有显著提升的。此外，随机性还可以视为一种隐式的正则化方法，可能可以跳出不太好的局部最优点与鞍点，参见参考资料5、6、7（图来源于7）：
说它并不完美，主要是其有四大缺点：（1） 对于非凸问题容易陷入局部最优；（2）SGD选择合适学习率很困难。 学习率太小可能会导致收敛速度非常缓慢，而学习率太大会阻碍收敛， 容易引起权重在最优解附近震荡，甚至可能引起发散；（3）SGD 采用随机的数据计算梯度近似整个数据集数据的真实梯度而引起的梯度噪音和方差 。（4）SGD的收敛速度还是比较慢。第一点事实上在现代机器学习特别是深度学习中已经不太提起了，对于甚高维的高度非凸函数，能找到一个局部最优就不错了！对于（2），引申出了一类自适应学习率与梯度的算法；对于（3），引申出了包括方差缩减等方法在内的一系列算法；对于（4），引申出了随机动量加速算法。就SGD在现代机器学习优化算法中的地位，它怎么能不被称为一个好算法呢？
Mini-Batch SGD
我们知道当$N_{i_\tau}$总是大于1时的SGD称为MSGD，为了简化问题，我们假设batch size恒等于$b$，也即$N_{i\tau}\equiv b$。对于MSGD，有：
$$ g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]})=\frac{1}{b}\sum\limits_{j=1}^{b} \nabla L(\boldsymbol{\theta}^{(\tau)};\xi_{[i_\tau],j}) $$
注意到这样的一个事实（$X,X_1,\cdots,X_m$独立同分布）：
$$ \mathbb{E}\left[\left(\frac{\sum_{i=1}^m X_i}{m} -\mathbb{E}[X]\right)^2\right]=\frac{\mathbb{E}[X^2]-\mathbb{E}^2[X]}{m}\tag{29} $$
我们用数学归纳法证明。显然$m=1$时成立，下设（29）在$m-1(\geq1)$时成立，考察$m$时的情况。
$$ \begin{align} \mathbb{E}\left[\left(\frac{\sum_{i=1}^m X_i}{m} -\mathbb{E}[X]\right)^2\right]&=\mathbb{E}\left[\left(\frac{\sum_{i=1}^{m-1} X_i-(m-1)\mathbb{E}[X]}{m} +\frac{X_m-\mathbb{E}[X]}{m}\right)^2\right]\\ &=\frac{1}{m^2}\mathbb E\left[\left(\sum_{i=1}^{m-1} X_i-(m-1)\mathbb{E}[X]\right)^2\right]\\ &\quad\ + \frac{1}{m^2} \mathbb{E}[(X_m-\mathbb{E}[X])^2]\\ &\quad\ +\frac{2}{m^2}\mathbb{E}\left[\left(\sum_{i=1}^{m-1} X_i-(m-1)\mathbb{E}[X]\right)(X_m-\mathbb{E}[X]) \right]\\ &=\frac{(m-1)^2}{m^2}\cdot\frac 1{m-1}(\mathbb{E}[X^2]-\mathbb{E}^2[X])\\ &\quad\ +\frac{1}{m^2}(\mathbb{E}[X^2]-\mathbb{E}^2[X])+0\\ &=\frac{\mathbb{E}[X^2]-\mathbb{E}^2[X]}{m} \end{align} $$
所以套入SGD与MSGD，我们可以知道，MSGD的$g(\boldsymbol{\theta}^{(\tau)},\boldsymbol{\xi}_{[i_\tau]})$的方差是SGD的$1/b$倍，说明引入mini-batch会使得训练更加稳定。当然我们从直观上而言，MSGD应该是GD与SGD的综合，收敛速度、计算效率、方差都应该介于二者之间。现在我们已经说明了方差，接下来看另外两者。
根据参考文献3,4我们知道，对于一般的凸函数：
$$ \mathbb{E}[\epsilon(\tau)]\leq O(\frac{1}{\sqrt{b\tau}})\tag{30} $$
看上去好像我们以$b$倍计算量的代价只带来了$\sqrt{b}$倍的精度提升，但是我们可以引入分布式的思想，在$b$个处理单元上计算一个batch上的梯度，这样每个处理单元上的计算量与SGD相同。应用于深度学习中即是用GPU训练。
所以，mini-batch的思想既能使训练更加稳定，在精度上也有提升，因此在深度学习中普遍采用。
References
- Optimization Methods for Large-Scale Machine Learning，Léon Bottou et al，SIAM Review，2018
- https://www.cs.ubc.ca/~schmidtm/Courses/540-W19/L11.pdf
- Optimal Distributed Online Prediction Using Mini-Batches，Ofer Dekel et al，Journal of Machine Learning Research 2013 (JMLR 2013)，2012
- A Convergence Analysis of Distributed SGD with Communication-Efficient Gradient Sparsification，Shaohuai Shi et al，Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI)，2019
- Stochastic Training is Not Necessary for Generalization，Jonas Geiping et al，The Tenth International Conference on Learning Representations (ICLR 2022)，2021
- Escaping From Saddle Points – Online Stochastic Gradient for Tensor Decomposition，Rong Ge，JMLR 2016，2015
- The Modern Mathematics of Deep Learning，Julius Berner，arXiv，2021
