线性回归上的梯度下降, SGD 和动量法

2026-08-07 五 12:05 2026-08-10 一 15:34

核心概览

在最简单的学习模型 – 线性回归上分析梯度下降(GD)、随机梯度下降的收敛条件以及 Momentum 为何能加速。

一维线性回归存在最优学习率

即便是 wx=y 最简单的线性方程也能写成 最小化 \( (y-wx)^2 \), 然后从一个随机初始化点用梯度下降。

但梯度下降的步长需要满足 \( 0<\eta<\frac{1}{x^2} \) 才能保证算法收敛。

在该收敛范围内,收敛系数是 \( r(\eta) = |1 - 2\eta x^2| \) ,当 \( \eta \) 从 0 逐渐增大到 \( 1/(2x^2) \) 时,r 从 1 单调递减到 0,收敛速度越来越快;最快是在 \( \eta = 1/(2x^2) \) 处取到,误差一步归零。当 \( \eta \) 继续增大到 \( 1/x^2 \) 时,r 又从 0 单调递增到 1,收敛速度越来越慢,直到触及临界点后彻底发散。

这说明,即便学习率在一个能收敛的范围内,也并不是越大越好,在有效范围内,过大或者过小可能都会导致收敛极度变慢。

通过奇异值分解可以

Momentum 为何可以加速收敛

动量是减少了损失景观中陡峭方向(大奇异值)震荡程度,从而使得可以把学习率调大(小学习率本身是减少震荡),使得收敛更快。

同时它可以平滑 SGD 中每个小 batch 里的梯度噪音。

动量消除了纯粹奇异值对收敛速率的影响,这有点类似 L2 正则对小奇异值方向的平滑

最优梯度下降学习率

以最简单的 \( w x = y \) 问题为例,w,x 都是标量,只要 x 不为 0, 方程的解就是 \( w=\frac{y}{x} \)

但它可以叙述为线性回归问题,即最小化 \( (y-wx)^2 \), 然后从一个随机初始化点用梯度下降进行更新:

\( w_{t+1} = w_t - \eta \cdot \frac{\partial}{\partial w} (y - w x)^2 \)

\(\eta\) 是学习率,用来控制每一步更新的步长。

在展开数学式前,我们可以从一般定性思考上得出学习率不能太大的结论:

因为学习率是对梯度的一个缩放,而梯度只是函数在特定点局部线性化后函数增大的方向,它的有效近似性只有局限于该点附近,如果学习率很大,梯度的作用本身就会失效了。

而从优化效率上看,学习率也不能太小,因为收敛速度就会很慢。

学习率的上限

继续计算梯度:

\[ \frac{\partial}{\partial w} (y - w x)^2 = 2 (y - w x) \cdot (-x) = -2x (y - w x) \]

代回更新公式,得到:

\[ w_{t+1} = w_t - \eta \cdot [ -2x (y - w_t x) ] = w_t + 2\eta x (y - w_t x) \]

把 \( w_t \) 的系数整理在一起: \[ w_{t+1} = (1 - \eta x^2)w_t + 2\eta xy \]

这是一个形式为 \( a_{n+1} = Aa_{n}+B \) 的递推公式,A 是常数,从头展开几项会发现:

\[ a_2 = A a_1 + B, \] \[ a_3 = A(A a_1 + B) + B = A^2 a_1 + AB + B, \] \[ a_4 = A(A^2 a_1 + AB + B) + B = A^3 a_1 + A^2 B + AB + B. \]

对于第 n 项:

\[ a_n = A^{n-1} a_1 + B \left( A^{n-2} + A^{n-3} + \cdots + A + 1 \right) \]

括号里是一个等比数列求和(从 A 的 0 次幂加到 n-2 次幂),利用求和公式得到:

\[ a_n = A^{n-1} a_1 + B \cdot \frac{1 - A^{n-1}}{1 - A} \quad (A \neq 1) \]

\( a_n \) 要能收敛,那么 \( |A|<1 \) ,而 \( A = 1 - 2\eta x^2 \),

于是有 \( |1-2\eta x^2|<1 \) ,写成 \( -1<1-2\eta x^2<1 \)

左边: \[ -1<1-2\eta x^2 \Rightarrow \eta x^2<1 \]

右边: \[ 1-2\eta x^2<1 \Rightarrow \eta x^2>0 \]

\[ 0<\eta<\frac{1}{x^2} \]

因此这里 \( \eta \) 有明确的范围,即小于 \( \frac{1}{x^2} \) 才能保证梯度下降算法是收敛的。

收敛速度

在学习率的上限下训练,至少能保证收敛,但如果把学习率设置地非常小,那么收敛速度极慢

于是我们关注收敛的速度,要知道收敛速度,我们需要知道目标,幸运的是,我们知道收敛的目标就是 \( w^*=\frac{y}{ x} \) , 于是我们构造出参数距离最优点距离在梯度下降中的迭代公式:

\[ w_{t+1}-w^* = (1-2\eta x^2)w_t+2\eta x y - \frac{y}{x} \]

整理等式右侧: \( w_{t+1}-w^* = (1-2\eta x^2)w_t -(\frac{y}{ x}-2\eta x y) \) 继续提取: \( w_{t+1}-w^* = (1-2\eta x^2)w_t -\frac{y}{ x}(1-2\eta x^2 ) \) 继续提取: \( w_{t+1}-w^* = (1-2\eta x^2)(w_t-w^*) \) 继续提取: \( |w_{t+1}-w^*| = |(1-2\eta x^2)| |w_t-w^*| \)

得到了一个权重和最优权重的差的递推公式,这是一个等比数列,比值为 \( r = |1-2\eta x^2| \) 这个值决定了收敛的速度,如果 r 接近 0,误差收缩快;如果 r 接近 1,误差缩减慢。

把 r 看作 \( \eta \) 的函数,\( r(\eta) = |1 - 2\eta x^2| \) ,而上一节我们知道学习率上限是 \( \frac{1}{x^2} \),

当 \( \eta \) 从 0 逐渐增大到 \( 1/(2x^2) \) 时,r 从 1 单调递减到 0,收敛速度越来越快;

最快是在 \( \eta = 1/(2x^2) \) 处取到,误差一步归零。

当 \( \eta \) 继续增大到 \( 1/x^2 \) 时,r 又从 0 单调递增到 1,收敛速度越来越慢,直到触及临界点后彻底发散。

这里说明,即便学习率在一个能收敛的范围内,也并不是越大越好,在有效范围内,过大或者过小可能都会导致收敛极度变慢。

二维理想场景和最优学习率

现在我们把这个标量结论推广到二维情形。假设样本特征数扩展到两个,样本数也扩展到两个,为了保持数据尽可能简单,我们令数据矩阵 X 直接取为对角矩阵,即

\[ \begin{bmatrix}\sigma_l & 0 \\ 0 & \sigma_s\end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} \]

这里 X 是对角的,意味着两个维度完全解耦——第一个方程只涉及 \(w_1\),第二个只涉及 \(w_2\),彼此互不影响。

既然解耦了,我们就可以把上一节得到的标量结论分别套用到两个维度上,注意这种情况可以分别用两次独立梯度下降,先计算 w1 再计算 w2 。

对于单个标量方程 \( \sigma w = y\),梯度下降收敛的学习率必须满足 \(0 < \eta < 1/\sigma^2\)。

于是对于第一个维度,约束是 \(0 < \eta < 1/\sigma_l^2\);对于第二个维度,约束是 \(0 < \eta < 1/\sigma_s^2\)。

现在假设 \(\sigma_l \gg \sigma_s\),也就是第一个维度的数据尺度远大于第二个维度。那么 \(1/\sigma_l^2\) 就会远小于 \(1/\sigma_s^2\)。为了让两个维度都能收敛,学习率必须同时满足两个约束,因此只能取它们的交集,即 \(0 < \eta < 1/\sigma_l^2\)。

因此真正限制全局学习率上限的是最大的那个 \(\sigma\)。

即便我们把学习率控制在各维度共同收敛的区间内,不同方向上的收敛速率仍然会不同。

根据上节标量情形的误差递推式 \(|w_{t+1} - w^*| = |1 - 2\eta\sigma^2| \cdot |w_t - w^*|\) ,收敛因子是 \(r(\eta\sigma^2) = |1 - 2\eta\sigma^2|\) ,它随 \(\eta\sigma^2\) 的变化不是单调的:

  • 当 \(\eta\sigma^2\) 从 0 增大到 0.5 时,r 从 1 单调递减到 0,此时 sigma 越大,r 越小,收敛越快;
  • 当 \(\eta\sigma^2\) 超过 0.5 后,r 又开始从 0 单调递增到 1,此时 sigma 越大,r 反而越大,收敛变慢,并且会出现正负交替的震荡衰减。

二维场景里,因为 \(\sigma_l\) 远大于 \(\sigma_s\),这两个方向对应的 \(\eta\sigma^2\) 值会落在收敛区间的不同位置。如果 \(\eta\) 取得较大,比如接近 \(1/\sigma_l^2\) 的上界,那么 \(\eta\sigma_l^2\) 可能已经落入 \((0.5, 1)\) 中接近 1 的区间,此时特征大的方向(w1)的收敛因子 r 偏大,可能会经历各种震荡。

而 \(\eta\sigma_s^2\) 由于 \( \sigma_s \) 小,可能还落在 \((0, 0.5)\) 靠近 0 的区间,r 也很大,于是两个方向都在震荡。

而在学习率取得足够小到满足 \(\eta \le 1/(2\sigma_l^2)\) 时,所有方向对应的 \(\eta\sigma^2\) 都不超过 0.5,函数 \(f(x)=1-2x\) 才是单调递减的,这时候可以说特征( \( \sigma \))更大的方向有最快的收敛速度。

现在我们考虑全局学习 \( \eta \) 取多少的时候能使得总体收敛速度最快?

由于更慢的收敛会拖累整个优化算法,因此最好是各个方向优化齐头并进,也就是 \( |1-2\eta \sigma_l^2| = |1-2\eta \sigma_s^2| \) 情况,而由于 \( \sigma_l \neq \sigma_s \), 因此绝对值里内容是异号的,这样解得最优学习率为: \[ \eta^* = \frac{1}{\sigma_l^2 + \sigma_s^2} \]

而最优学习率下两个方向的收敛因子都是: \[ R_{\text{eq}} = \frac{\sigma_l^2 - \sigma_s^2}{\sigma_l^2 + \sigma_s^2} \]

此时没有一个最慢的方向,或者说所有都是最慢(或最快)。

但会不会它比某个其他导致收敛不平衡学习率的最慢收敛速度还慢呢?

可以用图像直观上证明,比如给定 \( \sigma_l = 1 \) , \( \sigma_s = \frac{\sqrt{2}}{2} \)

那么收敛因子分别为 \( r_l = |1-2\eta|, r_s = |1-\eta| \), 将 \( \eta-r \) 绘制出来:

best_lr_2.svg

只有将 \( \eta \) 取图中黑色折线( \( r_l \) )和红色折线( \( r_s \) )的交点,二者的最大值(收敛最慢速率)才能取最小,如果取交点走侧那么 \( r_s \) 变成瓶颈,如果取右侧则 \( r_l \) 变成瓶颈。

代数上证明

要证明的结论是:给定任意一个偏离 \( \eta^* \) 的学习率,整体速率都会变慢。

取任意一个“不平等”的学习率 \(\eta \neq \eta^*\), 由于 \( 1-2\eta^* \sigma_s^2 \) 为正而 \( 1-2\eta^* \sigma_l^2 \) 为负这个事实出发:

当 \(\eta < \eta^*\) 时,小特征方向的量 \(1-2\eta \sigma_s^2\) 仍为正,且随着 \(\eta\) 减小而增大,因此 \( r_s \) 变大;大特征方向的量 \(1-2\eta \sigma_l^2\) 为负,但其绝对值在减小,所以 \(r_l\) 变小。此时 \(r_s > r_l\),整体速率由 \( r_s \) 决定,并且 \(R(\eta) = 1 - 2\eta\sigma_s^2 > R_{\text{eq}}\)。

当 \(\eta > \eta^*\)(且仍处于使迭代不发散的范围,比如 \(\eta < 1/\sigma_l^2\))时,大特征方向的量变得更负,其绝对值反弹增大,使得 \(r_l > r_s\),整体速率由 \(r_l\) 决定,同样得到 \(R(\eta) = 2\eta\sigma_l^2 - 1 > R_{\text{eq}}\)。

可以用简单图像来解释,每个收敛因子都是 V 字形的,两个不同的 sigma 塑造的 V 组合起来变成了 W, 而只有

可见,只要学习率偏离这个平衡点,无论偏小还是偏大,总有一个方向的收敛会变得更慢,拖累整体速率,使其严格大于相等时的值。

如果输入 X 是一个 nxn 的对角矩阵,对应值从大到小是 \( \sigma_1 \) 到 \( \sigma_n \), 那么同样可以解 n 个独立方程得到学习率必须小于 \( \frac{1}{\sigma_1^2} \) 算法才能收敛。

但什么时候是最优学习率呢?

如果有更多在 \( \sigma_s \) 和 \( \sigma_l \) 之间的 \( \sigma_i \), 由于收敛率是一个内部线性的绝对值函数,因此收敛速度还是由最大和最小的 \( \sigma \) 决定,因此最快收敛学习率选择还是满足 \( \eta^* = \frac{1}{\sigma_l^2 + \sigma_s^2} \)

同样可以用绘图的方式,假设在两个方向基础上增加了一个新方向 \( \sigma = \frac{1}{2} \), 那么有:

best_lr_3.svg

此时最优的学习率取在 \( r_s \) 和 \( r_l \) 的交点上,如果在左侧,最慢的方向仍然由最小奇异值方向统治,如果取右侧最慢方向仍然是最大奇异值方向

推广到一般的最小二乘问题

对于一般的 \(Xw = y\) 最小二乘问题,梯度下降的迭代可以写作

\[ w_{k+1} = (I - 2\eta X^T X) w_k + 2\eta X^Ty \]

对 X 做 SVD 分解 \( X = U\Sigma V^T \), 那么优化目标是 \( w^* = V\Sigma^{+} U^T y \)

可以写出: \[ w_{k+1}-w^* = (I - 2\eta V\Sigma^T\Sigma V^T)w_k + 2\eta V\Sigma^TU^T y - V\Sigma^{+} U^T y \]

利用 \(I = VV^T\),第一项可写为 \(V(I - 2\eta\Sigma^T\Sigma)V^T w_k\),后两项合并为 \(V(2\eta\Sigma^TU^Ty - \Sigma^{+}U^Ty)\).

\[ w_{k+1} - w^* = V\bigl[ (I - 2\eta\Sigma^T\Sigma) V^Tw_k + 2\eta\Sigma^TU^Ty - \Sigma^{+}U^Ty \bigr]. \]

仿造化简单变量情况,我们希望构造出误差的纯递推式子

因此关注尾项: \( 2\eta\Sigma^TU^Ty - \Sigma^{+}U^Ty \)

利用 \(\Sigma^T = \Sigma^T \Sigma \Sigma^{+ } \)(在非零奇异值位置上 \(\Sigma\Sigma^{+ }=I\),在零奇异值位置上两边都是零),把 \(\Sigma^{+ } \) 提取出来,尾项可以改写成

\[ 2\eta\Sigma^T U^T y - \Sigma^{+} U^T y = (2\eta\Sigma^T\Sigma - I) \Sigma^{+} U^T y = -(I - 2\eta\Sigma^T\Sigma) \Sigma^{+} U^T y. \]

代入前面的表达式,得到 \[ w_{k+1} - w^* = V\bigl[ (I - 2\eta\Sigma^T\Sigma) V^T w_k - (I - 2\eta\Sigma^T\Sigma) \Sigma^{+} U^T y \bigr] \]

\[ = V (I - 2\eta\Sigma^T\Sigma) (V^T w_k - \Sigma^{+} U^T y). \]

我们把所有的 w 切换到 V 的正交基下,即令 \( v_{k+1} =V^Tw_{k+1} \) , \( v_{k} =V^Tw_{k} \) , \( v^* =V^Tw^* = \Sigma^{+ } U^Ty \)

在以上式子两边乘以 \( V^T \) 就得到:

\(v_{k+1} - v^* = (I - 2\eta \Sigma^T \Sigma)(v_k - v^*)\)

注意它和单变量情况的对比:单变量时,误差递推关系是 \(|w_{t+1} - w^*| = |1 - 2\eta x^2| \, |w_t - w^*|\)。到了这里,问题变成了一个形如 \(y_{t+1} = \Lambda y_t\) 的线性迭代,目标是 \(y_t\) 收敛到零向量。

注意 \( \Lambda = I-2\eta \Sigma^T \Sigma \) 本身就已经是一个对角化之后的矩阵了(多亏我们切换到 V 正交基下)

将递推展开得到: \(y_{t+1} = \Lambda^t y_1\),

这里矩阵里对角线上每一项是 \( 1-2\eta \sigma_i^2 \), 即我们完全回到了解耦和或者一维的情况。

因此得到 \( 0<\eta< \frac{1}{\sigma^2_{\max}} \) 且在 \( \eta^* = \frac{1}{\sigma_{\max}^2 + \sigma_{\min}^2} \) 情况下收敛最快。

Early stopping 和隐式正则

有了前文理解,当学习率被设置得充分小,例如满足 \(\eta < 1/(2\sigma_{\max}^2)\) 时,每个方向上的衰减因子 \(1-2\eta\sigma_i^2\) 不仅小于 1,而且都保持为正。

奇异值 \(\sigma_i\) 越大,衰减因子就越小,该方向收敛得越快;奇异值越小的方向,衰减因子越接近 1,收敛也越缓慢。

也就是说,梯度下降在早期会优先学习大奇异值方向对应的显著模式,之后才逐渐花更多力气去拟合小奇异值方向上的细节分量。

这使得早停(early stopping)具有了隐式正则化的效果:

如果在迭代收敛到小奇异值方向之前就停止训练,模型将主要保留大奇异值方向的信息,而对数据中微小的波动或噪声不敏感。这种机制与 L2 正则颇为相似,后者通过惩罚权重大小,同样会压制小奇异值方向上的分量,限制模型对细微扰动的拟合。

不过这种等价性依赖于学习率足够小这一条件。如果学习率虽然仍在收敛区间内(\(\eta < 1/\sigma_{\max}^2\)),但大于 \(1/(2\sigma_{\max}^2)\),那么各个不同奇异值方向收敛情况变得复杂,比如有震荡或者过小都可能发生。

推广到随机梯度下降

求解 Xw=y 时可能并不是直接把整个 X 作为输入进行梯度下降,而是每次只随机采样一个样本进行梯度下降。

如何在线性回归视角下定义这种带有随机性的问题?

先用一个类比,假设 Xw=y 的 X 行远大于列数,即约束方程多于列,那么方程是无解的。

如果一般的 f(x)=y 方程无解,人们还能期望什么呢?

一种想法是,既然无法满足所有约束,那么删掉一些,问题可能就有解了。

这是一种对原问题的修改或者“放松”。

于是我们随机删除行使得约束越来越少最终有解,比如每次只随机选择 3 个方程(假设小于特征数,必定有解),然后求出最小范数解,最后把这些解加权平均。

但这种方式往往是错误的,用前文简单的例子:

\[ \begin{bmatrix}\sigma_l & 0 \\ 0 & \sigma_s\end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} \]

选择第一行 \( \sigma_1 w_1 = y_1 \) 得到最小范数解是 \( w_1=\frac{y_1}{\sigma_1}, w_2=0 \), 选择第二行则得到 \( w_1=0, w_2 = y_2/\sigma_s \)。如果求平均得到 \( y_1/2\sigma_l \) 和 \( y_2/2\sigma_s \) ,但实际是 \( y_1/\sigma_l \) 和 \( y_2/\sigma_s \) 。

小批量随机梯度下降在做某种类似的事情,但它不是取一小批量直接求解出结果,而是只对解进行一小部分梯度方向的贡献。

这使得它可以在概率上保证结果的正确性。

本节只关注随机选择单个样本 SGD, 它变成了这样的问题:

每次从 Xw=y 形式的方程里随机选择一行 \( x_i^T \) 和 \( y_i \),然后对它做一次梯度下降,误差更新迭代公式为:

\[ w_{k+1} = (I - 2\eta x_i x_i^T) w_k + 2\eta y_i x_i \]

然后我们要证明的是, \( E[w_{k+1}] \) 会等于 Xw=y 总体的最优解 \( w^* \)

和前文推广到一般的方程中推理思路类似,我们关注 \( w_{k} \) 和 \( w^* \) 的差,并且为了进行某种解耦,我们更关注的是把权重转换到 V 正交基下的权重形式: \( v_{k+1} =V^Tw_{k+1} \) , \( v_{k} =V^Tw_{k} \) , \( v^* =V^Tw^* = \Sigma^{+ } U^Ty \)

我们希望把迭代式写成关于 v 的递归关系,在前文一般 GD 下它是: \(v_{k+1} - v^* = (I - 2\eta \Sigma^T \Sigma)(v_k - v^*)\)

然而由于我们每次只使用 \( x_i x_i^T \) 进行更新,它不能被 SVD 分解出 \( \Sigma^T \Sigma \) 的形式,而且即便分解了,我们也没法把期望应用在 \( \Sigma \) 上,因为采样发生在每一行的表象层面,而 SVD 是一种非线性分解。

但我们还是希望进行基变换,同时保持“行采样”这种行为在变换后仍然成立。

我们把 \( V^Tx_i \) 看作一个整体,它是从 X 中随机采样一行,然后切换坐标系的结果,将它记为 \( z_i \), 由于 V 是单位正交矩阵,有 \( x_i = Vz_i \) ;

而且还有 \(y_i = x_i^T w^* = (V z_i)^T w^* = z_i^T v^*\),

于是可以开始对更新方程 \( w_{k+1} = (I - 2\eta x_i x_i^T) w_k + 2\eta y_i x_i \) 进行改造:

两边减去 \( w^* \) 再左乘 \( V^T \) 得到:

\[ v_{k+1} - v^* = V^T(I - 2\eta x_i x_i^T) w_k + 2\eta y_i V^T x_i - v^* . \]

就整理为 \[ v_{k+1} - v^* = v_k - 2\eta z_i (z_i^T v_k) + 2\eta z_i (z_i^T v^*) - v^* = (I - 2\eta z_i z_i^T)(v_k - v^*) . \]

也就是:

\[ v_{k+1} - v^* = (I - 2\eta z_i z_i^T)(v_k - v^*) \]

与全批量 GD 的对角结构相比,这里用秩一矩阵 \(z_i z_i^T\) 取代了确定的 \( \Sigma^T \Sigma \),表面上看不到解耦性质(即整个系数不是对角矩阵),但它没有破坏采样的结构。

可以对抽样指标 \(i\) 取期望,由于 \(i\) 是从全部 n 行中均匀随机选取的,便有

\[ \mathbb{E}[z_i z_i^T] = \frac{1}{n} \sum_{i=1}^n z_i z_i^T = \frac{1}{n} V^T X^T X V = \frac{1}{n} \Sigma^T \Sigma . \]

这里,在期望下,对角矩阵重新回来了:给定当前误差 \(v_k - v^*\) 时的条件期望满足

\[ \mathbb{E}[v_{k+1} - v^* \mid v_k] = \left(I - \frac{2\eta}{n} \Sigma^T \Sigma \right)(v_k - v^*) . \]

两边再取全期望,便得到关于期望误差的线性迭代 \[ \mathbb{E}[v_{k+1} - v^*] = \left(I - \frac{2\eta}{n} \Sigma^T \Sigma \right) \mathbb{E}[v_k - v^*] . \]

这里和 GD 情况类似了,因为 \( I - \frac{2\eta}{n} \Sigma^T \Sigma \) 是解耦的对角矩阵,于是每一个方向衰减因子是 \( 1-2 \eta \frac{\sigma_i^2}{n} \), 因此最终收敛条件是 \( \eta < \frac{n}{\sigma^2_{\max}} \)

这意味着,在满足学习率的情况下,SGD 的权重至少从期望上会收敛到全局最优解。

而且这里我们仍然能计算出期望收敛层面的最优学习率,对吗? 但已经有最优了,为什么要 momentum 呢?

推广到批量随机梯度下降

如果每次采样 batch size 为 k,那么与单行情形唯一的区别,是把原来的行向量 \(x_i\) 替换为一个子矩阵 \(X_i \in \mathbb{R}^{k \times d}\),其中下标 i 不指代单个样本,而是标识一个随机抽取的 batch。对应的更新方程变为 \[ w_{t+1} = (I - 2\eta X_i^T X_i) w_t + 2\eta X_i^T y_i, \]

这里 \(y_i\) 是该 batch 对应的目标值向量,梯度计算依然基于这批样本上的平方损失之和,没有除以 k,以保持与前面单样本讨论的记号一致。

沿用全局右奇异基 V 进行坐标变换,令 \(Z_i = X_i V\),则 \(X_i = Z_i V^T\),且 \(y_i = X_i w^* = Z_i V^T w^* = Z_i v^*\)。将误差 \(v_t = V^T w_t\) 代入,并减去 \(v^*\),即可得到与单样本完全平行形式

\[ v_{t+1} - v^* = (I - 2\eta Z_i^T Z_i)(v_t - v^*)。 \]

单个子矩阵的期望 Gram 矩阵满足 \[ \mathbb{E}[Z_i^T Z_i] = \frac{k}{n} \Sigma^T \Sigma。 \]

因此,在给定当前误差的条件下, \[ \mathbb{E}[v_{t+1} - v^* \mid v_t] = \left(I - \frac{2\eta k}{n} \Sigma^T \Sigma \right)(v_t - v^*)。 \] 这意味各特征方向上的期望衰减因子变为 \(1 - 2\eta k \sigma_j^2 / n\)。为保证所有方向收缩,需要

\[ 0 < \eta < \frac{n}{k \sigma_{\max}^2}。 \]

当 k=1 时,得到单样本的 \(\eta < n/\sigma_{\max}^2\);当 k=n 时,回到全批量的 \(\eta < 1/\sigma_{\max}^2\)。

通过 Momentum 加速

引入动量的动机

即便在全量 GD 下,选择了最优的学习率 \(\eta^* = 1/(\sigma_{\max}^2 + \sigma_{\min}^2)\) 下,最快方向的衰减因子是

\[ 1 - 2\eta^*\sigma_{\max}^2 = 1 - \frac{2\sigma_{\max}^2}{\sigma_{\max}^2 + \sigma_{\min}^2} = \frac{\sigma_{\max}^2 - \sigma_{\min}^2}{\sigma_{\max}^2 + \sigma_{\min}^2}. \]

定义 \(\kappa = \sigma_{\max}/\sigma_{\min}\) ,它被称为矩阵 X 的条件数,用 \( \kappa \) 代入得到最佳衰减因子 \( r = \frac{\kappa^2 - 1}{\kappa^2 + 1} = 1-\frac{2}{\kappa^2 + 1} \)

可以看到,最佳收敛率完全由条件数决定。

当条件数很大时,衰减因子接近 1 – 即便学习率达到最优,总体收敛速度也极为缓慢。

条件数刻画的是损失函数地貌(loss landscape)中“最陡方向”和“最缓方向”之间差异的程度。

想象一个狭长的山谷:谷壁方向极陡,谷底方向极平。条件数很大,意味着这个差异很极端。

梯度下降在这样的地形上会发生剧烈震荡:因为任何一点点沿着谷底方向的移动,都会把你稍稍带上谷壁,而下一步谷壁陡峭的坡度又把你弹回谷底,如此往复。

这形成了一种优化轨迹里的高频震荡部分,而在谷的长轴方向,它则是缓慢地接近谷底(如果很快,那么短轴方向震荡就更加剧烈)

所以条件数越大,山谷越窄,轨道中来回弹射的幅度和频率就越大。可以说,条件数某种程度上决定了优化历程中“可能震荡的程度”。

而引入动量是通过记住“过去在这个方向震荡过几次了,那么就不需要再来回震荡了”这件事把高频震荡给 "滤波" 的。

所以它的底层思路和信号里高通滤波是类似的,只要能记住某个维度有过一些重复运动,那么就可以把无用的来回削弱,而如果某个维度没有重复,那么它就会继续保持这个方向。

具体来说,动量通过维护着一个历史梯度的指数滑动平均,当参数在谷壁之间来回弹射时,这次的更新方向和上次几乎相反,动量把它们累加起来,结果就相互抵消了,垂直于谷底方向的震荡被大大削弱,而沿着谷底长轴方向,每一步的推进虽然微小,但方向高度一致,动量会持续累积平滑,那些接近谷底的梯度很小的平坦区也能获得更早的大梯度积累下的补偿,起到加速效果。

这种情况下,平坦方向(奇异值小的方向,后文会解释)就不需要为了缓和陡峭方向的震荡而把学习率调小(使得得自己的收敛因子和最小奇异值一样),而是可以在动量已经压制了陡峭方向的震荡的情况下,调大学习率,这是为什么加入动量之后学习率可以更大的原因。

注意这里的分析完全基于全量梯度下降,而引入随机性后,本身梯度是有噪声的,把过去的梯度加权累计本身是一种近似获取全局梯度的手段,因此它又在 sgd 上起到了平滑梯度噪声的作用。

为什么奇异值大的反向更陡峭。

可以通过收敛因子 \( |1 - 2\eta\sigma^2| \) 来判断,假设学习率固定,假设两个奇异值分别是 2 和 1, 那么收敛因子是 \( r_l = |1-8\eta| \) 和 \( r_s = |1-2\eta| \) :

  • 当学习率小的时候,比如 0.02, 那么 \( r_l = |1-0.16| \) 且 \( r_s = |1-0.04| \) ,绝对值内部都是比大于 0 且最终结果接近 1, 结果是收敛速度很慢,因为步长很小,两个方向都在慢慢稳步接近极小值点,而且可以看出奇异值大的会更快收敛。(这有呼应了隐式正则)
  • 当学习率变大到 0.2, 那么 \( r_l = |1-1.6| \) 且 \( r_s = |1-0.4| \) ,小奇异值的方向是更接近于 0,, 因此收敛更快了,这是一般步长变大后所外推的结果,奇异值大的方向虽然总体值也更小意味着收敛更快,但绝对值内部是负的,这意味着这个步长过大已经跨过最小值点震荡了。

所以奇异值大的方向对应的是损失函数的景观(loss landscape)里陡峭的方向(二维情况是椭圆短轴),而奇异值小对应的是平坦方向(椭圆长轴)。

和 SVD 分解中数据分布方差的长轴短轴的区别

这要和 线性回归的几何解释 文章中 L2 正则对线性回归解影响时奇异值的特点进行区分,在那里岭回归的封闭解的 SVD 分解形式为: \[ \hat{w} = V (\Sigma^2 + \lambda I)^{-1} \Sigma^T U^T y \] 拆解为按奇异值逐分量处理: \[ \boxed{\hat{w} = V \cdot \text{diag}\left( \frac{\sigma_i}{\sigma_i^2 + \lambda} \right) \cdot U^T y} \] 这里奇异值大的方向表示的是数据里方差大信息最丰富的方向,对应长轴,而奇异值小的是方差小信息量小(可能是噪声)的维度,对应短轴。PCA 里数据降维也对应这种解释。

动量引入后的收敛条件

这里我们只分析全量梯度下降的情况:

线性回归里,动量更新是在原始参数空间中把过去的梯度进行指数加权平均,写作:

\[ w_{t+1} = w_t - \eta z_{t+1}, \qquad z_{t+1} = (1-\beta)z_t + \beta (2X^T X w_t - 2X^T y). \]

这里 \( z_t \) 是加权后的梯度。

与前文使用的技巧一样,切换到和最优权重的误差空间并投影到 V 坐标系下,令 \(x_t = V^T(w_t - w^*)\),\(a_t = V^T z_t\)。

代入 \(X = U\Sigma V^T\) 以及 \(w^* = V\Sigma^{+}U^T y\),经过简化,外部目标 y 被消去,系统变成了纯粹是误差 \( x_t \) 和动量 \( a_t \) 之间相互递归的公式(齐次差分方程):

\[\begin{cases} x_{t+1} = x_t - \eta \, a_{t+1} \\ a_{t+1} = (1-\beta)a_t + 2\beta \, (\Sigma^T\Sigma) \, x_t \end{cases}\]

因为 \(\Sigma^T\Sigma\) 是对角矩阵(有部分奇异值可能是 0),各特征方向彼此解耦。因此对每一个奇异值 \(\sigma_i\),独立地有

  • \(a_{t+1}^{(i)} = (1-\beta)a_t^{(i)} + 2\beta \sigma_i^2 x_t^{(i)}\)
  • \(x_{t+1}^{(i)} = x_t^{(i)} - \eta a_{t+1}^{(i)}\)

写成矩阵形式即为

\[ \begin{bmatrix} a_{t+1}^{(i)} \\ x_{t+1}^{(i)} \end{bmatrix} = \begin{bmatrix} 1-\beta & 2\beta\sigma_i^2 \\ -\eta & 1 \end{bmatrix} \begin{bmatrix} a_t^{(i)} \\ x_t^{(i)} \end{bmatrix}.\] (对于零奇异值方向,只要从零初始化,它们始终为零。)

这是一个 \( x_t = A^tx_0 \) 的矩阵的幂的形式,

前面说过,动量是一种高频的滤波机制,因此它和动力系统里差分方程(或连续微分方程)共享相同数学表示,而以上式子表明,每个方向上的收敛性完全由这个 \(2\times 2\) 矩阵的特征值决定。其特征方程为

\[ \lambda^2 - (2-\beta)\lambda + (1-\beta + 2\beta\eta\sigma_i^2) = 0, \] 解得 \[ \lambda_{1,2} = 1 - \frac{\beta}{2} \pm \frac{1}{2}\sqrt{\beta^2 - 8\beta\eta\sigma_i^2}. \]

根据判别式 \(\Delta = \beta^2 - 8\beta\eta\sigma_i^2\) 的符号,呈现三种不同的行为:

  • 当 \(\beta > 8\eta\sigma_i^2\) 时,特征值为两个相异实根,系统处于过阻尼状态,收敛缓慢且无振荡。
  • 当 \(\beta = 8\eta\sigma_i^2\) 时,特征值为重根 \(\lambda = 1 - \beta/2\),对应临界阻尼。为了保证此时参数收敛,需要 \(|\lambda|<1\),即 \(0 < \beta < 4\),进而导出 \(\eta = \beta/(8\sigma_i^2) < 1/(2\sigma_i^2)\)。
  • 当 \(\beta < 8\eta\sigma_i^2\) 时,根号内为负,出现一对共轭复根,其模长恰为 \(\sqrt{1-\beta}\),系统进入欠阻尼状态,表现出带有衰减振荡的收敛行为。
TODO 和岭回归对比

要保证任一方向收敛,两个特征根的模长必须都小于 1。这个条件给出了学习率的上界 \(\eta < (2+\beta)/(2\sigma_i^2)\),保守起见常取 \(\eta < 1/\sigma_i^2\) 作为稳定性的安全条件。现在可以看到动量提速的关键:在普通梯度下降中,小奇异值方向(\(\sigma_i\) 小)的衰减因子 \(1-2\eta\sigma_i^2\) 接近 1,收敛极慢。引入动量后,即使对于很小的 \(\sigma_i\),只要 \(\beta\) 选择适当,系统可以进入欠阻尼区,此时特征值为模长 \(\sqrt{1-\beta}\) 的复数,意味着衰减速率由 \(\beta\) 单独决定,不再直接受制于 \(1-2\eta\sigma_i^2\) 那种接近 1 的缓慢收缩。这就使得原本拖后腿的平坦方向能够以与陡峭方向可比的速度收敛,从而整体加速。

radioLinkPopups

如对本文有任何疑问,欢迎通过 github issue 邮件 metaescape at foxmail dot com 进行反馈