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

用全量梯度下降去求解 \( \min (Xw-y)^2 \) 线性回归问题，得益于这种 Xw 的线性形式以及损失是平方函数，能够写出更新公式：

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

又得益于 SVD 分解以及这个问题本身就有封闭解 \( w^* = V\Sigma^{+} U^T y \)

于是可以得到把参数切换到 V 坐标系下之后距离最优解的差的动态迭代方程：

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

其中 \( (I - 2\eta \Sigma^T \Sigma) \) 是对角矩阵，因此成功把问题解耦成各个奇异值对应方向独立进行更新的方程

\[ \Delta v_{k+1} = (1-2\eta \sigma_i^2) \Delta v_k \]

对于奇异值非 0 的方向，要能稳定收敛， \( \Delta v_{k+1} \) 需要趋于 0 ，因此步长需要满足 \( 0<\eta<\frac{1}{\sigma_i^2} \) 才行，所有方向都收敛则要满足 \( 0 < \eta < \frac{1}{\sigma_{\max}} \) 。

而对于奇异值为 0 的方向， \( \Delta v_{k+1} = 1 \Delta v_k \) ，即压根不会更新，因此只要假定 w0=0, 那么这些方向始终就是 0 ，而如果其他方向收敛，那么就会得到最小范数解。

在各个方向收敛因子（系数）是 \( r_i(\eta) = |1 - 2\eta \sigma_i^2| \) ，这不是一个单调函数，当 \( \eta \) 从 0 逐渐增大到 \( 1/(2\sigma_i^2) \) 时，r 从 1 单调递减到 0，收敛速度越来越快；最快是在 \( \eta = 1/(2\sigma_i^2) \) 处取到，更新一步就到最优值，\( \eta \) 继续增大则是“走过头”，开始震荡，收敛速度越来越慢，直到 \( 1/\sigma_i^2 \) 则发散。

全局最优的学习率是由于最小和最大奇异值对应的两个方向决定的：

在 \( \eta^* = \frac{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} \) ，最佳收敛率完全由条件数决定。

实践中，当学习率 \( \eta \) 设置得足够小时，奇异值 \( \sigma_i \) 越大 \( r_i \) 越小，收敛越快。

因此大的奇异值的方向会先收敛，如果当某些大奇异值方向（对应更重要的特征，或者称主特征）收敛后及时停止训练， 那么就相当于只学习训练数据中的主要特征而忽视可能的噪声，这和正则化效果类似，因此在梯度下降中应用 early stopping 能有隐式正则的效果。

作为对比， L2 正则下岭回归的解是，小奇异值方向的共享会被 \( \lambda \) “滤波”。

\[ \hat{w} = V \cdot \text{diag}\left( \frac{\sigma_i}{\sigma_i^2 + \lambda} \right) \cdot U^T y \]

假设每次只抽取一个样本进行梯度下降，那么更新方程为： \( w_{k+1} = (I - 2\eta x_i x_i^T) w_k + 2\eta y_i x_i \)

同样通过对总体样本 X 矩阵的 SVD 分解把 w 切换到 V 的基下，单个样本 \( x_i \) 在 V 下则是 \( z_i \)，得到

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

取全期望后得到： \[ \mathbb{E}[v_{k+1} - v^*] = \left(I - \frac{2\eta}{n} \Sigma^T \Sigma \right) \mathbb{E}[v_k - v^*] . \]

和全量梯度下降类似，因为 \( I - \frac{2\eta}{n} \Sigma^T \Sigma \) 是解耦的对角矩阵，于是每一个方向衰减因子是 \( 1-2 \eta \frac{\sigma_i^2}{n} \), 因此最终收敛条件是 \( \eta < \frac{n}{\sigma^2_{\max}} \)

如果对全量梯度下降的损失函数 \( (Xw-y)^2 \) 归一化到 \( \frac{1}{n}(Xw-y)^2 \), 那么其收敛条件也是 \( 0<\eta< \frac{n}{\sigma^2_{\max}} \) ，二者尺度是一样的。

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

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

有了一个额外的动量参数 \( \beta \) 之后，只要满足 \( \sqrt{1-\beta} \geq \frac{\kappa - 1}{\kappa + 1} \) ，就能选择到一个学习率使得所有奇异值方向都进入到重根和复根区，从而所有方向都以 \( \sqrt{1-\beta} \) 的收敛因子收敛。

而这比无动量的梯度下降的 \( \frac{\kappa^2-1}{\kappa^2+1} \) 收敛因子更小，要到达同样的 loss 水平，一般梯度下降受制于对崎岖地形的平衡，迭代次数是 \( O(\kappa^2) \), 而动量法次数是 \( O(\kappa) \) ，从平方级别的了线性级别。

计算出梯度：

\[ \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 \) 的递推公式（得益于二次函数的梯度是 w 的线性函数），

\( 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 \) 再继续增大就属于“走过头了”，直观上会产生震荡。

具体来说，当 \( \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} \]

既然解耦了，就可以把上一节得到的标量结论分别独立地套用到两个维度上，比如先计算 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 反而越大，收敛变慢，并且会出现正负交替的震荡衰减。

那么 \( \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 \) 绘制出来：

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

如果输入 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} \), 那么有：

此时最优的学习率取在 \( 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^*)\)

注意 \( \Lambda = I-2\eta \Sigma^T \Sigma \) 已经是一个对角化之后的矩阵了（多亏我们切换到 V 正交基下），矩阵里对角线上每一项是 \( 1-2\eta \sigma_i^2 \), 即我们完全回到了解耦和或者一维的情况，在独立地求解 n 个 \(|w_{t+1} - w^*| = |1 - 2\eta x^2| \, |w_t - w^*|\) 形式的方程。

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

对于奇异值为 0 的方向， \(v_{k+1} - v^* = (v_k - v^*)\) ，即压根不会更新，因此只要假定 w0=0, 那么这些方向始终就是 0 ，而如果其他方向收敛，那么就会得到最小范数解。

有了前文理解，当学习率被设置得充分小，例如满足 \(\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)\)，那么各个不同奇异值方向收敛情况变得复杂，比如有震荡或者过小都可能发生。

本节只关注随机选择单个样本的 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 的递归关系，在前文的全量梯度下降中，它是： \(v_{k+1} - v^* = (I - 2\eta \Sigma^T \Sigma)(v_k - v^*)\)

随机梯度下降中，每次只使用 \( x_i x_i^T \) 进行更新，它是个 rank1 的矩阵，每次都在变化，不能被 SVD 分解成一个固定的 \( \Sigma^T \Sigma \) 的形式，而且即便对每个矩阵进行分解，也没法把期望应用在 \( \Sigma \) 上，因为采样发生在每一行的表象层面，而 SVD 是一种非线性分解，期望操作不能穿透非线性运算，即 \( E[g(x)] \) 在 g 是非线性函数时不等于 \( g(E[x]) \)

于是把 \( 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^*] . \]

和全量梯度下降类似，因为 \( I - \frac{2\eta}{n} \Sigma^T \Sigma \) 是解耦的对角矩阵，于是每一个方向衰减因子是 \( 1-2 \eta \frac{\sigma_i^2}{n} \), 因此最终收敛条件是 \( \eta < \frac{n}{\sigma^2_{\max}} \)

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

如果每次采样 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\)。

前文推理得到了一个有点反直觉的结论，即在随机梯度下降里 batch 越小收敛的学习率范围更大了，学习率上界和 n/k 成正比 。

但现实中往往是 batch 越大学习率可以越大。

这是因为是前文中我们使用的损失函数的尺度是不同的，我们始终是用 \( (Xw-y)^2 \) 作为损失函数，不论 X 有多少行。

因此它们的损失函数本身就不在一个尺度，实践中更多使用的是 \( \frac{1}{n}(Xw-y)^2 \)

这种情况下全量梯度下降在 V 坐标系参数迭代公式为

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

稳定条件变成 \( 0 < \eta < \frac{n}{\sigma^2_{\max}} \)

这个尺度和单个样本随机梯度下降的结论一样了，而对于 batch 大小为 k 的 SGD, 得到的学习率收敛范围也是这个值。

而 batch size 越大能得到更精准的梯度（虽然期望都是一样的，但方差更小），所以实践中更大的 batch 可以用更大的学习率。

在全量梯度下降中，选择最优的学习率 \(\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 上起到了平滑梯度噪声的作用。

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

\[ 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 坐标系下，令 \(\Delta v_t = V^T(w_t - w^*)\)，\(a_t = V^T z_t\)。

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

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

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

• \( a_{t+1}^{(i)} = (1-\beta)a_t^{(i)} + 2\beta \sigma_i^2 \Delta v_t^{(i)} \)
• \( \Delta v_{t+1}^{(i)} = -\eta (1- \beta) a_{t}^{(i)} + (1-2\eta\beta \sigma_i^2)\Delta v_t^{(i)} \)

对于后 \(d-n\) 个零奇异值方向（\(\sigma_i = 0\)），更新公式变为 \( \Delta v_{t+1} = \Delta v_t - \eta(1-\beta) a_{t+1} \) 且 \(a_{t+1} = (1-\beta)a_t\)。只要初始动量和初始误差在该方向为 0（从 0 开始梯度下降满足这一点），它们就会永远保持为 0, 因此得到的还是某种最小范数解。

对于核心关注的奇异值非 0 的方向，写成矩阵形式为

\[ \begin{bmatrix} a_{t+1}[i] \\ \Delta v_{t+1}[i] \end{bmatrix} = \begin{bmatrix}1-\beta & 2\beta \sigma_i^2 \\ -\eta(1-\beta) & 1-2\eta\beta\sigma_i^2 \end{bmatrix} \begin{bmatrix} a_{t}[i] \\ \Delta v_{t}[i] \end{bmatrix} \]

在无动量的梯度下降中，各奇异值对应方向的参数的更新的动态描述是 \( \Delta v_{k+1} = (1 - 2\eta \sigma_i^2 )\Delta v_k\) ，收敛行为完全由 \( |1-2\eta \sigma_i^2| \) 和 1 的关系所决定。

而引入动量后，收敛性由以上 \(2\times 2\) 矩阵的性质决定，这是一个 x=Ax 的迭代方程，我们期望 x 收敛到 0, 因此要 \( A^k \) 趋近于 0 矩阵，这个性质是由 A 的特征值决定的。

由于该矩阵的 trace 是 \( T_i = 2-\beta-2\eta \beta \sigma_i^2 \) , det 是 \( D_i = 1-\beta \) ，那么特征方程为

\[ \lambda^2 - (2- \beta-2\eta \beta \sigma_i^2) \lambda + (1-\beta) = 0 \]

两个特征根就是：

\[ \lambda_{1,2} = \frac{T_i \pm \sqrt{T_i^2 - 4D_i}}{2} \]

记 \( \Delta = T_i^2 - 4D_i = (2- \beta - 2\eta\beta\sigma_i^2)^2 - 4(1-\beta) \)

根据 \( \Delta \) 和 0 的关系会得到不同情况：

• \(\Delta = 0\)： 特征根为重根
• \(\Delta > 0\)： 特征根为两个不同的实根。
• \(\Delta < 0\)： 特征根为一对共轭复根

我们最终关心的是特征根 \( \lambda_{1,2} \) 的绝对值（如果是复数就是模长）和 1 的关系，为了收敛，必须所有的特征根的模长都小于 1 。

可以用 \( \lambda_1 + \lambda_2 = T_i \) 且 \( \lambda_1 \lambda_2 = D_i \) 来简化对 \( \lambda \) 模长的计算