本文的主要研究对象是机器学习特别是深度学习里最为流行的优化器：随机梯度下降(SGD)以及Adam。
Contents
随机梯度下降SGD
算法
在最速下降法里，迭代步骤是
\boldsymbol x_{k+1}=\boldsymbol x_k-\alpha_k \boldsymbol g_k,其中\boldsymbol g_k=\nabla f(\boldsymbol x_k)，\alpha_k选择是或能最小化f(\boldsymbol x_k-\alpha \boldsymbol g_k)的非负实数（如果可能），实际中为了实用通常选择一个小的常数。在优化基础、下降方法里已经对最速下降有过叙述。
在机器学习特别是深度学习里，梯度的计算将会变得困难，因为样本量n往往极为巨大——要优化的对象是经验损失\widehat L=\frac1n\sum_{i=1}^n\ell(f(\boldsymbol x_i),y_i)，是一个n项平均，作为真正的损失L=\mathbb E_{\mathbf x,\mathrm y}[\ell(f(\mathbf x),\mathrm y)]的一个近似。计算梯度\nabla\widehat L时对其中的每一项都要计算梯度，然后再求n项的平均。这个计算代价通常都是不可接受的。一种“化n为1”的方案是每次只取其中随机的一个梯度\nabla\ell_{\mathrm i}以替代n项平均，这样，因为n个都等可能地取到，起码在期望上，是和\nabla\widehat L是一样的：\mathbb E_{\mathrm i}[\nabla\ell_{\mathrm i}]=\nabla\widehat L。当然用一项来近似n项平均是过于“激进”的，一个折中的方案是在1到n之间，计算少量样本的平均。这就是一般所说的“小批量(minibatch)”的梯度下降，是最常见的。可以简单地称之“随机梯度下降”(stochastic gradient descent, SGD)。
随机梯度下降SGD的算法：从某初始参数\boldsymbol \theta出发，取定一列学习率\{\eta_k\}，每次迭代过程为：从训练集的n个样本中采样m个小批量(\boldsymbol x_{(1)},y_{(1)}),\dots,(\boldsymbol x_{(m)},y_{(m)})，计算更新
\begin{aligned}
\boldsymbol g&\leftarrow \frac1m\nabla_{\boldsymbol \theta}\Big(\sum_{i=1}^m\ell(f(\boldsymbol x_{(i)}),y_{(i)})\Big),\\
\boldsymbol \theta&\leftarrow\boldsymbol \theta-\eta\boldsymbol g.
\end{aligned}
实际应用中，采样这一步骤一般不会在训练过程中进行，通常的做法是提前将样本打乱一遍，然后训练时再按顺序每次取m个。在遍历过一遍训练集后（一般称这为一个epoch），再从头开始重复使用前m个样本，后面也一样按顺序重复使用。虽然在这里，这种“重复使用”似乎不够“随机”了，但一般来说问题似乎不大。另一方面，在实际中还会出现n大到遍历过一次完整的训练集都很困难的情况（大数据时代），这时欠拟合才是最大的问题，而非过拟合。此时，在每次迭代，训练器看到的都是“全新的”样本了。
动量
动量(momentum)是物理学中的一个概念，定义为m\boldsymbol v。纯SGD一般是比较慢的，而引入动量则可以有加速效果。将优化的过程考虑成一个物理过程：一个物体（单位质量）在力的作用下从初始点运动到极小值点。举例来说，考虑一个物体从碗状曲面的碗边开始运动，物体会从零初速度开始，不断加速运动，直到前进的力和阻力平衡，然后在碗底周围晃荡，最后在碗底逐渐减速到零。
这个过程涉及的两个力，一个是让物体前进的，在优化场景里对应的是负梯度，另一个是阻力，简单起见一般选取的是viscous drag，是一种正比于速度的阻力。（如果正比于速度平方，那么速度较小时阻力会很弱物体停不下来；如果正比于速度的零次方，那么就是滑动摩擦，这就会强到物体在中途就过早停下来了）
利用牛顿定律建模，就是-\eta\nabla_{\boldsymbol \theta}\widehat L-\alpha'\boldsymbol v=\frac{\mathrm d\boldsymbol v}{\mathrm dt}，然后我们将时间“离散化”，就是-\eta\nabla_{\boldsymbol \theta}\widehat L-\alpha'\boldsymbol v_k=\boldsymbol v_{k+1}-\boldsymbol v_k，于是\boldsymbol v_{k+1}=(1-\alpha')\boldsymbol v_k-\eta\nabla_{\boldsymbol \theta}\widehat L=:\alpha\boldsymbol v_k-\eta\nabla_{\boldsymbol \theta}\widehat L。于是我们得到了带动量的SGD算法：
带动量的SGD算法：从某初始参数\boldsymbol \theta出发，取定学习率\eta和动量参数\alpha（和初速度\boldsymbol v，我们取零速度），每次迭代过程为：从训练集的n个样本中采样m个小批量(\boldsymbol x_{(1)},y_{(1)}),\dots,(\boldsymbol x_{(m)},y_{(m)})，计算更新
\begin{aligned}\boldsymbol g&\leftarrow \frac1m\nabla_{\boldsymbol \theta}\Big(\sum_{i=1}^m\ell(f(\boldsymbol x_{(i)}),y_{(i)})\Big),\\
\boldsymbol v&\leftarrow \alpha \boldsymbol v-\eta\boldsymbol g,\\
\boldsymbol \theta&\leftarrow\boldsymbol \theta+\boldsymbol v.\end{aligned}动量参数\alpha一般取0.9,0.99等。
SGD+Momentum还有另一种等价形式，Pytorch的实现就用的是这一版本。更新为
\begin{aligned}
\boldsymbol v&\leftarrow \alpha \boldsymbol v+\boldsymbol g,\\
\boldsymbol \theta&\leftarrow\boldsymbol \theta-\eta\boldsymbol v.\end{aligned}\boldsymbol v前是负号，因为和前一版本的\boldsymbol v是反向的。
Adam
另一大类算法是自适应学习率的算法（adaptive learning rate）。对于学习率，一个自然的想法是对梯度向量较大的分量适当缩小学习率、对较小的分量适当增加学习率。这种想法的一种实现就是RMSProp算法(Root Mean Square Propagation)，每一步“自适应”考虑了梯度的所有历史。
RMSProp
RMSProp算法：从某初始参数\boldsymbol \theta出发，取定学习率\eta和衰减速率\rho，以及一个小常数\delta（用于被小数除时的数值稳定，例如可取1\mathtt e{-}6,1\mathtt e{-}7），初始化一个向量\boldsymbol r=\boldsymbol 0，每次迭代过程为：从训练集的n个样本中采样m个小批量(\boldsymbol x_{(1)},y_{(1)}),\dots,(\boldsymbol x_{(m)},y_{(m)})，计算更新
\begin{aligned}\boldsymbol g&\leftarrow \frac1m\nabla_{\boldsymbol \theta}\Big(\sum_{i=1}^m\ell(f(\boldsymbol x_{(i)}),y_{(i)})\Big),\\
\boldsymbol r&\leftarrow\rho \boldsymbol r+(1-\rho)\, \boldsymbol g\odot\boldsymbol g,\\
\Delta\boldsymbol \theta&\leftarrow\frac{\eta}{\sqrt{\delta+\boldsymbol r}}\odot(-\boldsymbol g),\\
\boldsymbol \theta&\leftarrow\boldsymbol \theta+\Delta\boldsymbol \theta.\end{aligned}
这里迭代的第三行中的运算是逐元素的，可以参考其代码的形式：
dx = compute_gradient(x)
grad_squared = decay_rate * grad_squared + (1 - decay_rate) * dx * dx
x -= learning_rate / (np.sqrt(grad_squared) + 1e-7) * dx
Adam
Adam则是另一个自适应学习率的算法，远比上一个更为流行。形式上很像是RMSProp+Momentum的组合（但似乎没有必要这么看）。粗略地说，Adam的更新为
\begin{aligned}
t&\leftarrow t+1,\\
\boldsymbol s&\leftarrow\beta_1\boldsymbol s+(1-\beta_1)\boldsymbol g,\\
\boldsymbol r&\leftarrow\beta_2\boldsymbol r+(1-\beta_2)\, \boldsymbol g\odot\boldsymbol g,\\
\boldsymbol \theta&\leftarrow\boldsymbol \theta-\eta\frac{\boldsymbol s}{\sqrt{\boldsymbol r}+\delta}.
\end{aligned}
当\beta_1=0时，就变为了RMSProp。Adam还对\boldsymbol s,\boldsymbol r两项进行了矫正。以\boldsymbol s为例，\boldsymbol s_{t}可以写成
\begin{aligned}
\boldsymbol s_{t}&=(1-\beta_1)\boldsymbol g_{t}+(1-\beta_1)\beta_1\boldsymbol g_{t-1}+\beta_1^2\boldsymbol s_{t-1}=\cdots\\
&=(1-\beta_1)\boldsymbol g_{t}+(1-\beta_1)\beta_1\boldsymbol g_{t-1}+\dots+(1-\beta_1)\beta_1^{t-1}\boldsymbol g_1\\
&=(1-\beta_1)\boldsymbol g_{t}+(1-\beta_1)\beta_1\boldsymbol g_t+\dots+(1-\beta_1)\beta_1^{t-1}\boldsymbol g_t+\Delta_t\\
&=(1-\beta_1^t)\boldsymbol g_t+\Delta_t.
\end{aligned}特殊情况是，如果\boldsymbol g全相等，那么\Delta=\boldsymbol 0，于是可考虑矫正：\widehat{\boldsymbol s}=\boldsymbol s\mathbin/(1-\beta_1^t)，类似地\widehat{\boldsymbol r}=\boldsymbol r\mathbin/(1-\beta_2^t)。
Adam算法：取定\eta,\beta_1,\beta_2,\delta（\delta用于被小数除时的数值稳定，例如可取1\mathtt e{-}7,1\mathtt e{-}8），初始化\boldsymbol \theta,\boldsymbol r,\boldsymbol s,t，每次迭代过程为：从训练集的n个样本中采样m个小批量(\boldsymbol x_{(1)},y_{(1)}),\dots,(\boldsymbol x_{(m)},y_{(m)})，计算更新
\begin{aligned}
t&\leftarrow t+1,\\
\boldsymbol g&\leftarrow \frac1m\nabla_{\boldsymbol \theta}\Big(\sum_{i=1}^m\ell(f(\boldsymbol x_{(i)}),y_{(i)})\Big),\\
\boldsymbol s&\leftarrow\beta_1\boldsymbol s+(1-\beta_1)\boldsymbol g,\\
\boldsymbol r&\leftarrow\beta_2\boldsymbol r+(1-\beta_2)\, \boldsymbol g\odot\boldsymbol g,\\
\widehat{\boldsymbol s}&\leftarrow\frac{1}{1-\beta_1^t}\boldsymbol s,
\\
\widehat{\boldsymbol r}&\leftarrow\frac1{1-\beta_2^t}\boldsymbol r ,\\
\boldsymbol \theta&\leftarrow\boldsymbol \theta-\eta\frac{\widehat{\boldsymbol s}}{\sqrt{\widehat{\boldsymbol r}}+\delta}.
\end{aligned}
超参数尝试有一些建议值：\beta_1=0.9, \beta_2=0.999, \eta=1\mathtt e{-}3或5\mathtt e{-}4。这也是Pytorch里这些超参的默认值。
可以参考Adam的代码形式：
dx = compute_gradient(x)
s = beta1 * s + (1 - beta1) * dx
st = s / (1 - beta1 ** t)
r = beta2 * r + (1 - beta2) * dx * dx
vt = v / (1 - beta2 ** t)
x -= learning_rate * st / (np.sqrt(rt) + 1e-7)
AdamW
AdamW也是同样极为流行的优化算法。是Adam的带权重衰减(weight decay)的变体。
机器学习中，正则化是非常经典的技术。例如在目标函数之后加上一项正则项：L+\lambda\|\boldsymbol \theta\|，我们考虑常用的2范数正则化，因为这在数学上更易于处理。在线性回归里，这也等价于岭回归。正则化后的目标函数变为L+\frac\lambda2\boldsymbol \theta^\mathsf T\boldsymbol \theta，求梯度后为\nabla_{\boldsymbol \theta} L+\lambda\boldsymbol \theta，使用梯度下降，参数更新即为\boldsymbol \theta\leftarrow\boldsymbol \theta-\eta(\nabla_{\boldsymbol \theta}L+\lambda\boldsymbol \theta)。这可以改写为\boldsymbol \theta\leftarrow(1-\eta\lambda)\boldsymbol\theta-\eta\nabla_{\boldsymbol \theta}L，可以看到这相当于权重先进性了一次“衰减”然后再按标准梯度下降进行更新。
换成更通常的说法，就是：对GD，L2正则等价于权重衰减。
对于Adam，就没有这种等价性了。在Pytorch里，Adam的weight_decay实际上是L2正则，AdamW则实现了实质上的权重衰减：
AdamW算法：取定\eta,\beta_1,\beta_2,\delta（\delta用于被小数除时的数值稳定，例如可取1\mathtt e{-}7,1\mathtt e{-}8），初始化\boldsymbol \theta,\boldsymbol r,\boldsymbol s,t，每次迭代过程为：从训练集的n个样本中采样m个小批量(\boldsymbol x_{(1)},y_{(1)}),\dots,(\boldsymbol x_{(m)},y_{(m)})，计算更新
\begin{aligned}
t&\leftarrow t+1,\\
\boldsymbol g&\leftarrow \frac1m\nabla_{\boldsymbol \theta}\Big(\sum_{i=1}^m\ell(f(\boldsymbol x_{(i)}),y_{(i)})\Big),\\
\boldsymbol \theta&\leftarrow(1-\eta\lambda)\boldsymbol \theta,\\
\boldsymbol s&\leftarrow\beta_1\boldsymbol s+(1-\beta_1)\boldsymbol g,\\
\boldsymbol r&\leftarrow\beta_2\boldsymbol r+(1-\beta_2)\, \boldsymbol g\odot\boldsymbol g,\\
\widehat{\boldsymbol s}&\leftarrow\frac{1}{1-\beta_1^t}\boldsymbol s,
\\
\widehat{\boldsymbol r}&\leftarrow\frac1{1-\beta_2^t}\boldsymbol r ,\\
\boldsymbol \theta&\leftarrow\boldsymbol \theta-\eta\frac{\widehat{\boldsymbol s}}{\sqrt{\widehat{\boldsymbol r}}+\delta}.
\end{aligned}
使用AdamW的理由在于Adam的L2正则效果不如SGD的好，而用权重衰减的话正则化效果更好。
下面是一些比较各算法的图示，不过其中一些算法没有叙述，里面也没有将Adam(W)列入比较。源：https://www.denizyuret.com/2015/03/alec-radfords-animations-for.html
附录：GD,SGD分析
这一节主要分析一下GD和SGD。Adam则暂时留空，因为其分析尚不如(S)GD成熟，当下也是热门研究；此外，Adam自身的收敛性也有一些问题，这就限制了对它的分析。
梯度平滑假设
首先，目标函数L\in C^2，即二次连续可微；梯度假设是比较“平滑”的，一般会叙述为：梯度\nabla L:\mathbb R^d\to\mathbb R^d是L-Lipschitz连续的（字母L复用了，但应该问题不大），即总有
\|\nabla L(\boldsymbol \theta_1)-\nabla L(\boldsymbol \theta_2)\|\leqslant L\|\boldsymbol \theta_1-\boldsymbol \theta_2\|.
利用梯度信息做优化，当然不能让梯度“为所欲为”。这种平滑假设是大多数梯度方法都会有的。当然，L-平滑假设只是一个习惯做的通常假定，现在的深度学习实践中并非总成立（因而不少研究会考虑更宽松的假设）。L-平滑假设也相当于说，Hesse矩阵\nabla^2 L的谱范数（算子范数，也等于最大奇异值）\|\nabla^2L\| _ 2，是有界的：记绝对值最大特征值为\lambda_{\max}，总有不等式
\|\nabla^2L(\boldsymbol \theta)\|_2=|\lambda_{\max}(\nabla^2L(\boldsymbol \theta))|\leqslant L.
在一元函数的情况下，Lipschitz连续和导数有界互推是简单的，梯度Lipschitz连续和Hessian范数有界的等价性则复杂一点。如果Hessian范数有界，对任何\boldsymbol \theta_1,\boldsymbol \theta_2，由拟微分平均值定理，存在它们中间的一点\boldsymbol \xi，使\|\nabla L(\boldsymbol \theta_1)-\nabla L(\boldsymbol \theta_2)\|\leqslant\|\nabla^2 L(\boldsymbol \xi)\|_2\|\boldsymbol \theta_1-\boldsymbol \theta_2\|\leqslant L\|\boldsymbol \theta_1-\boldsymbol \theta_2\|。反之，对任意\boldsymbol \theta_1，取\boldsymbol \theta_2使\|(\nabla^2 L(\boldsymbol \theta_1))(\boldsymbol \theta_2-\boldsymbol \theta_1)\|=\|\nabla^2L(\boldsymbol \theta_1)\|_2\|\boldsymbol \theta_2-\boldsymbol \theta_1\|，于是
\begin{aligned}
\nabla L(\boldsymbol \theta_2)&=\nabla L(\boldsymbol \theta_1)+(\nabla^2 L(\boldsymbol \theta_1))(\boldsymbol \theta_2-\boldsymbol \theta_1)+\boldsymbol r(\|\boldsymbol \theta_2-\boldsymbol \theta_1\|),\\
\|\nabla^2 L(\boldsymbol \theta_1)\|_2\|\boldsymbol \theta_2-\boldsymbol \theta_1\|&\leqslant \|\nabla L(\boldsymbol \theta_2)-\nabla L(\boldsymbol \theta_1)\|+\|\boldsymbol r\|,\\
&\leqslant L\|\boldsymbol \theta_2-\boldsymbol \theta_1\|+\|\boldsymbol r\|,\\
\|\nabla^2 L(\boldsymbol \theta_1)\|_2&\leqslant L+\|\boldsymbol r(1)\|.
\end{aligned}进一步取\boldsymbol \theta_2使得\|\boldsymbol \theta_2-\boldsymbol \theta_1\|\to0，就是\|\nabla^2 L(\boldsymbol \theta_1)\|_2\leqslant L了。由\boldsymbol \theta_1的任意性，所需结论成立。
GD
在平滑假设下，由Taylor定理，立知恒有
L(\boldsymbol \theta_2)\leqslant L(\boldsymbol \theta_1)+\nabla L(\boldsymbol \theta_1)^\mathsf T(\boldsymbol \theta_2-\boldsymbol \theta_1)+\frac L2\|\boldsymbol \theta_2-\boldsymbol \theta_1\|^2.
在GD下，\boldsymbol \theta_2=\boldsymbol \theta_1-\eta\nabla L(\boldsymbol \theta_1)，上式变为L(\boldsymbol \theta_2)\leqslant L(\boldsymbol \theta_1)-\eta\|\nabla L(\boldsymbol \theta_1)\|^2+\frac L2\eta^2\|\nabla L(\boldsymbol \theta_1)\|^2，可见只需要\frac L2\eta^2\leqslant\eta，即\eta\leqslant 2/L，损失函数就会一直下降。
注意，在下文中，\boldsymbol\theta_t的下标指示的是迭代次数，而迭代初始是\boldsymbol\theta_0或是\boldsymbol\theta_1则不作区分，按方便取用。
取\eta=1/L，在GD下，梯度的收敛速率大致是O(1/t)，每一步迭代，有L(\boldsymbol \theta_t)\leqslant L(\boldsymbol \theta_{t-1})-\frac1{2L}\|\nabla L(\boldsymbol \theta_{t-1})\|^2，于是L(\boldsymbol \theta_t)\leqslant L(\boldsymbol \theta_1)-\frac1{2L}\sum_{i=1}^t\|\nabla L(\boldsymbol \theta_i)\|^2，于是平均梯度\frac1t\sum_{i=1}^t\|\nabla L(\boldsymbol \theta_i)\|^2\leqslant\frac1t(2L(L(\boldsymbol \theta_1)-L(\boldsymbol \theta_t)))，这表明梯度的范数平均以O(1/t)速率收敛。
在L是凸的假设下，L的收敛速率也是O(1/t)。我们有
\begin{aligned}
&L(\boldsymbol \theta_t)-L(\boldsymbol \theta^\ast)\leqslant L(\boldsymbol \theta_{t-1})-L(\boldsymbol \theta^\ast)-\frac\eta2\|\nabla L(\boldsymbol \theta_{t-1})\|^2\\
&\phantom{L(\boldsymbol \theta_t)-L(\boldsymbol \theta^\ast)}\leqslant \nabla L(\boldsymbol \theta_{t-1})^\mathsf T(\boldsymbol \theta_{t-1}-\boldsymbol \theta^\ast)-\frac\eta2\|\nabla L(\boldsymbol \theta_{t-1})\|^2,\\
&\|\boldsymbol \theta_t-\boldsymbol \theta^\ast\|^2=\|\boldsymbol \theta_{t-1}-\boldsymbol \theta^\ast\|^2-2\eta\nabla L(\boldsymbol \theta_{t-1})^\mathsf T(\boldsymbol \theta_{t-1}-\boldsymbol \theta^\ast)+\eta^2\|\nabla L(\boldsymbol \theta_{t-1})\|^2,\\
\implies{}&L(\boldsymbol \theta_t)-L(\boldsymbol \theta^\ast)\leqslant-\frac1{2\eta}(\|\boldsymbol \theta_{t}-\boldsymbol \theta^\ast\|^2-\|\boldsymbol \theta_{t-1}-\boldsymbol \theta^\ast\|^2),\\
\implies{}&\sum_{i=1}^tL(\boldsymbol \theta_i)-tL(\boldsymbol \theta^\ast)\leqslant-\frac1{2\eta}(\|\boldsymbol \theta_{t}-\boldsymbol \theta^\ast\|^2-\|\boldsymbol \theta_{0}-\boldsymbol \theta^\ast\|^2)\leqslant \frac L2\|\boldsymbol \theta_0-\boldsymbol \theta^\ast\|^2,
\end{aligned}而L(\boldsymbol \theta_t)是递减的，故L(\boldsymbol \theta_t)-L(\boldsymbol \theta^\ast)\leqslant\frac L{2t}\|\boldsymbol \theta_0-\boldsymbol \theta^\ast\|^2，这就得到了欲证结论。
在L是强凸的假设下，收敛速率进一步改进。关于强凸，有几种等价定义：函数f是\mu-强凸的，如果存在正数\mu使对任意\boldsymbol x,\boldsymbol y有
- f(\boldsymbol y)\geqslant f(\boldsymbol x)+\nabla f(\boldsymbol x)^\mathsf T(\boldsymbol y-\boldsymbol x)+\frac\mu2\|\boldsymbol y-\boldsymbol x\|^2;
- \nabla^2 f(\boldsymbol x)\succcurlyeq \mu I;
- (\nabla f(\boldsymbol x)-\nabla f(\boldsymbol y))^\mathsf T(\boldsymbol x-\boldsymbol y)\geqslant \mu\|\boldsymbol x-\boldsymbol y\|^2.
若L是L-平滑、\mu-强凸的，那么收敛速率是指数级的——令\eta=1/L，\kappa=L/\mu，那么\boldsymbol \theta_t以O(\mathrm e^{-t/\kappa})的速率收敛到\boldsymbol \theta^\ast，L(\boldsymbol \theta_t)和\nabla L(\boldsymbol \theta_t)的收敛也是这样的指数级。先看\boldsymbol \theta_t，应用强凸假设和平滑假设，有
\begin{aligned}
&\left\{\begin{gathered}
\|\boldsymbol \theta_t- \boldsymbol \theta^\ast\|^2=\| \boldsymbol \theta_{t-1}- \boldsymbol \theta^\ast\|^2-2\eta\nabla L( \boldsymbol \theta_{t-1})^\mathsf T( \boldsymbol \theta_{t-1}- \boldsymbol \theta^\ast)+\eta^2\|\nabla L( \boldsymbol \theta_{t-1})\|^2,\\
\nabla L( \boldsymbol \theta_{t-1})^\mathsf T( \boldsymbol \theta_{t-1}- \boldsymbol \theta^\ast)\geqslant L(\boldsymbol \theta_{t-1})-L(\boldsymbol \theta^\ast)+\tfrac\mu2\|\boldsymbol \theta_{t-1}-\boldsymbol \theta^\ast\|^2,\\
\begin{aligned}
&L(\boldsymbol \theta^\ast)\leqslant L(\boldsymbol \theta_t)\leqslant L(\boldsymbol \theta_{t-1})-\tfrac1{2L}\|\nabla L(\boldsymbol \theta_{t-1})\|^2\\
\implies{}&\|\nabla L(\boldsymbol \theta_{t-1})\|^2\leqslant 2L\cdot[L(\boldsymbol \theta_{t-1})-L(\boldsymbol \theta^\ast)],
\end{aligned}
\end{gathered}\right.\\
\implies{}&\|\boldsymbol \theta_t- \boldsymbol \theta^\ast\|^2\leqslant(1-\eta\mu)\| \boldsymbol \theta_{t-1}- \boldsymbol \theta^\ast\|^2,\\
\implies{}&\|\boldsymbol \theta_t-\boldsymbol \theta^\ast\|^2\leqslant(1-\tfrac1\kappa)^t\|\boldsymbol \theta_0-\boldsymbol \theta^\ast\|^2\leqslant \mathrm e^{-t/\kappa}\|\boldsymbol \theta_0-\boldsymbol \theta^\ast\|^2.
\end{aligned}中间的化简消去了一些项，是因为选取的是\eta=1/L。这就得到了\boldsymbol \theta_t的指数级衰减。注意到梯度是Lipschitz连续的，梯度也是指数衰减；同时由平滑假设L(\boldsymbol \theta^\ast)\leqslant L(\boldsymbol \theta_t)\leqslant L(\boldsymbol \theta^\ast)+\frac L2\|\boldsymbol \theta_t-\boldsymbol \theta^\ast\|^2可知目标函数也是指数衰减。
SGD
最后，给出一些SGD的经典分析。前面的SGD算法中，每一次的m个小批量我们记为(\boldsymbol x_{(1)},y_{(1)}),\dots,(\boldsymbol x_{(m)},y_{(m)})，下面为了体现抽取的随机性我们更换记号，记为(\boldsymbol x_{\mathrm i_1},y_{\mathrm i_1}),\dots,(\boldsymbol x_{\mathrm i_m},y_{\mathrm i_m})，这样随机性通过随机变量\mathbf i=(\mathrm i_1,\dots,\mathrm i_m)体现出来了。
引理：梯度平滑假设下，
\mathbb E_{\mathbf i_t}[L(\boldsymbol \theta_{t+1})]-L(\boldsymbol \theta_t)\leqslant -\eta_t\|\nabla L(\boldsymbol \theta_t)\|^2+\frac12\eta_t^2L\, \mathbb E_{\mathbf i_t}\big[\|\boldsymbol g_t\|^2\big].该式可直接通过平滑假设代入迭代式，然后取期望得到。
引理：再假设\mathbb E_{\mathbf i_t}\big[\|\boldsymbol g_t-\nabla L(\boldsymbol \theta_t)\|^2\big]\leqslant M，对任意t\in\mathbb N；学习率\eta_t\leqslant 1/L，那么
\mathbb E_{\mathbf i_t}[L(\boldsymbol \theta_{t+1})]-L(\boldsymbol \theta_t)\leqslant -\frac{\eta_t}{2}\|\nabla L(\boldsymbol \theta_t)\|^2+\frac12\eta_t^2LM.推导也是不难的：由假设，\mathbb E_{\mathbf i_t}\big[\|\boldsymbol g_t\|^2\big]\leqslant M+\|\nabla L(\boldsymbol \theta_t)\|^2，而\eta_t L\leqslant 1，代入就得到该引理。
移项、求和、取期望，得到\sum_{t=1}^T\frac{\eta_t}{2}\mathbb E_{\mathrm I}\big[\|\nabla L(\boldsymbol \theta_t)\|^2\big]\leqslant \mathbb E_{\mathrm I}[L(\boldsymbol \theta_1)]-\mathbb E_{\mathrm I}[L(\boldsymbol \theta_{T+1})]+\frac12LM\sum_{t=1}^T\eta_t^2，又L(\boldsymbol \theta^\ast)\leqslant L(\boldsymbol \theta_{T+1})，因此
\frac{\sum_{t=1}^T{\eta_t}\mathbb E_{\mathrm I}\big[\|\nabla L(\boldsymbol \theta_t)\|^2\big]}{\sum_{t=1}^T\eta_t}\leqslant \frac{2(\mathbb E_{\mathrm I}[L(\boldsymbol \theta_1)]-L(\boldsymbol \theta^\ast))+LM\sum_{t=1}^T\eta_t^2}{\sum_{t=1}^T\eta_t}.
这个式子能得出以下三个命题。由此可粗略看出一个非常经典的让SGD收敛的学习率充分条件：
\sum_{t=1}^\infty\eta_t=\infty,\quad \sum_{t=1}^\infty\eta_t^2<\infty.第一个条件表明学习率并不会降低太快，第二个表明也不会下降太慢。而使用常数学习率时，下面的命题表明我们可以推导一个收敛于\eta LM的界（注意到常数学习率下，由于小批量的随机性的缘故，我们不能做到收敛到\boldsymbol\theta^\ast，因而不能找到收敛于0的界）。
命题：在前面引理的假设下，设学习率\eta_t\equiv \eta，那么
\frac1T\sum_{t=1}^T\mathbb E_\mathrm I\big[\|\nabla L(\boldsymbol \theta_t)\|^2\big]\leqslant\frac2{\eta T}(\mathbb E_\mathrm I[L(\boldsymbol \theta_1)]-L(\boldsymbol \theta^\ast))+\eta LM.命题可从前面的结论立刻得到。
当m=n时，M=0，我们又得到了前面GD的平均梯度范数O(1/t)的收敛结论。
定理：在前面引理的假设下，设学习率\eta_t递减，且满足\sum{\eta _ t}=\infty，\sum\eta _ t^2<\infty，那么
\liminf_{t\to\infty} \mathbb E _ {\mathrm I}\big[\|\nabla L(\boldsymbol \theta_t)\|^2\big]=0.
这个定理通过如下命题（通过反证法轻易）得到：
命题：与前一命题条件相同，有
\lim_{T\to\infty}\frac{\sum_{t=1}^T{\eta_t}\mathbb E_{\mathrm I}\big[\|\nabla L(\boldsymbol \theta_t)\|^2\big]}{\sum_{t=1}^T\eta_t}=0.
所以，对这样递减的学习率，SGD生成的\{\boldsymbol \theta_t\}_ {t=1}^\infty，可以从中找一子列\{\boldsymbol \theta_{i_t}\}_ {t=1}^\infty使得对应的梯度是趋于零的：\mathbb E\big[\|\nabla L(\boldsymbol \theta_{i_t})\|^2\big]\to0。命题则表明范数的加权平均趋于零。顺带一提，在更强的假设下，我们可以做到\mathbb E_{\mathrm I}\big[\|\nabla L(\boldsymbol \theta_{t})\|^2\big]\to0，例如函数\boldsymbol\theta\to\|\nabla L(\boldsymbol\theta)\|^2的导数是Lipschitz连续的，就是说\boldsymbol\theta\to2\nabla^2 L(\boldsymbol\theta)\nabla L(\boldsymbol\theta)是Lipschitz连续的，可以推出\mathbb E_{\mathrm I}\big[\|\nabla L(\boldsymbol \theta_{t})\|^2\big]\to0，证明就略过了。
下面给出SGD在强凸目标函数下的经典分析，凸的就略过了。设目标函数是\mu-强凸的，有不等式L(\boldsymbol \theta)\geqslant L(\boldsymbol \theta_t)+\nabla L(\boldsymbol \theta_t)^\mathsf T(\boldsymbol \theta-\boldsymbol \theta_t)+\frac\mu2\|\boldsymbol \theta-\boldsymbol \theta_t\|^2，考察右边的最小值，求导得\nabla L(\boldsymbol \theta_t)+\mu(\boldsymbol \theta-\boldsymbol \theta_t)=\boldsymbol 0，故\boldsymbol \theta=\boldsymbol \theta_t-\frac1\mu\nabla L(\boldsymbol \theta_t)，从而L(\boldsymbol \theta_t)-\frac1\mu\|\nabla L(\boldsymbol \theta_t)\|^2+\frac\mu2\cdot\frac1{\mu^2}\|\nabla L(\boldsymbol \theta_t)\|^2\leqslant\dots\leqslant L(\boldsymbol \theta^\ast)，中间省略号表示前面不等式右边令\boldsymbol \theta=\boldsymbol \theta^\ast的情形。于是我们可知
2\mu(L(\boldsymbol \theta_t)-L(\boldsymbol \theta^\ast))\leqslant\|\nabla L(\boldsymbol \theta_t)\|^2.这就是Polyak-Lojasiewicz不等式。
命题：前面引理的假设下，设目标函数是\mu-强凸的。设学习率\eta_t\equiv\eta，那么：
\mathbb E_{\mathrm I}[L(\boldsymbol \theta_{t+1})]-L(\boldsymbol \theta^\ast)\leqslant\frac{\eta LM}{2\mu}+(1-\eta\mu)^{t}\Big(L(\boldsymbol \theta_1)-F(\boldsymbol \theta^\ast)-\frac{\eta LM}{2\mu}\Big).证明需要用到前面的引理和PL不等式。引理代入PL不等式：
\begin{aligned}
&\mathbb E_{\mathbf i_t}[L(\boldsymbol \theta_{t+1})]-L(\boldsymbol \theta_t)\leqslant -\frac{\eta_t}{2}\|\nabla L(\boldsymbol \theta_t)\|^2+\frac12\eta_t^2LM\\
&\phantom{\mathbb E_{\mathbf i_t}[L(\boldsymbol \theta_{t+1})]-L(\boldsymbol \theta_t)}\leqslant-{\eta_t}\mu[L(\boldsymbol \theta_t)-L(\boldsymbol \theta^\ast)]+\frac12\eta_t^2LM\\
\implies{}&\mathbb E_{\mathbf i_t}[L(\boldsymbol \theta_{t+1})]\leqslant L(\boldsymbol \theta_t)-{\eta_t}\mu[L(\boldsymbol \theta_t)-L(\boldsymbol \theta^\ast)]+\frac12\eta_t^2LM\\
\implies{}&\mathbb E_{\mathrm I}[L(\boldsymbol \theta_{t+1})]-L(\boldsymbol \theta^\ast)\leqslant (1-{\eta_t}\mu)(\mathbb E_{\mathrm I}[L(\boldsymbol \theta_t)]-L(\boldsymbol \theta^\ast))+\frac12\eta_t^2LM.
\end{aligned}现在1\geqslant1-\eta_t\mu\geqslant1-\frac1\kappa\geqslant0，再在上面不等式两边配凑，得\mathbb E_{\mathrm I}[L(\boldsymbol \theta_{t+1})]-L(\boldsymbol \theta^\ast)-\frac{\eta LM}{2\mu}\leqslant (1-{\eta_t}\mu)(\mathbb E_{\mathrm I}[L(\boldsymbol \theta_t)]-L(\boldsymbol \theta^\ast)-\frac{\eta LM}{2\mu})，利用这一递推式就可以得到原命题了。
命题：在前面引理的假设下，设目标函数是\mu-强凸的。设常数\beta>1/\mu，学习率取\eta_t=\frac{\beta}{t}，（是满足\sum_{t=1}^T\eta_t=\infty及\sum_{t=1}^T\eta^2<\infty的，）那么有某常数A，使
\mathbb E_\mathrm I[L(\boldsymbol \theta_t)]-L(\boldsymbol\theta^\ast)\leqslant\frac{A}{t}.来证这个不等式。取A大到当t=1时成立，再进一步取A\geqslant (\beta^2LM)/(2(\beta\mu-1))。现在t=1已自动成立；若已对t成立，那么利用前面已经证明的\mathbb E_{\mathrm I}[L(\boldsymbol \theta_{t+1})]-L(\boldsymbol \theta^\ast)\leqslant (1-{\eta_t}\mu)(\mathbb E_{\mathrm I}[L(\boldsymbol \theta_t)]-L(\boldsymbol \theta^\ast))+\frac12\eta_t^2LM，得\mathbb E_{\mathrm I}[L(\boldsymbol \theta_{t+1})]-L(\boldsymbol \theta^\ast)\leqslant (1-\beta\mu/t)\cdot A/t+\frac12\beta^2LM/t^2=\frac{t-\beta\mu}{t^2}A+\frac{\beta^2LM}{2t^2}，右边变形得\frac{t-1}{t^2}A+\frac{1}{t^2}[-(\beta\mu-1)A+\frac12\beta^2LM]，而A的选取已经使得第二项为负，所以原式小于等于\frac{t-1}{t^2}A\leqslant \frac A{t+1}，这就证明了命题对t+1也成立，所以命题恒成立。
该命题表明这个设置下excess risk的收敛速度是O(1/t)。
发表回复