优化算法：从梯度下降到牛顿法

上一篇我们建立了微积分工具箱——梯度告诉我们坡度方向，Hessian 告诉我们曲面形状，Taylor 展开让我们在任意点建立局部近似。但有了地图不等于会走路——如何用这些信息实际找到损失函数的最小值？

这就是优化算法要回答的问题。在 分解概述 的六类矩阵操作框架中，上一篇建立了”微分”工具（参数变了，输出怎么变），本篇用这些工具设计具体的迭代求解策略。如果说微积分是地图，优化算法就是行进路线。

本文从一个统一的元算法框架出发，推导出梯度下降（Gradient Descent）和牛顿法（Newton’s Method）——它们分别对应一阶和二阶 Taylor 近似的自然选择。然后引入随机梯度下降（SGD）和实用改进方法（Momentum、Adam），最后连接到矩阵分解的优化视角，为后续 PCA 和随机化 SVD 文章做铺垫。

统一框架：近似、求解、迈步

所有迭代优化算法，无论名字如何花哨，都遵循同一个三步循环：

这个元算法（meta-algorithm）的三步是：

1. 近似：在当前点 $\mathbf{x}_t$ 处，建立损失函数 $f$ 的一个局部模型 $m_t(\Delta\mathbf{x})$，近似 $f(\mathbf{x}_t + \Delta\mathbf{x})$
2. 求解：最小化这个局部模型，得到最优步长 $\Delta\mathbf{x}^* = \arg\min_{\Delta\mathbf{x}} m_t(\Delta\mathbf{x})$
3. 迈步：更新参数 $\mathbf{x}_{t+1} = \mathbf{x}_t + \Delta\mathbf{x}^*$，回到第 1 步

模型的选择定义了算法：

局部模型	来源	算法
一阶 Taylor：$m_t = f(\mathbf{x}_t) + \nabla f^T \Delta\mathbf{x}$	只用梯度	梯度下降 (GD)
二阶 Taylor：$m_t = f(\mathbf{x}_t) + \nabla f^T \Delta\mathbf{x} + \frac{1}{2}\Delta\mathbf{x}^T H \Delta\mathbf{x}$	梯度 + Hessian	牛顿法 (Newton)
一阶 Taylor + 随机采样	部分数据的梯度	随机梯度下降 (SGD)

这是本文最核心的洞察：不同的优化算法不是各自独立发明的技巧，而是同一个框架下不同精度的局部近似的自然结果。理解了这个统一视角，后面每个算法的推导都是水到渠成。

梯度下降——一阶方法

从一阶 Taylor 推导

上一篇的 Taylor 展开告诉我们，在当前点 $\mathbf{x}_t$ 附近：

$f(\mathbf{x}_t + \Delta\mathbf{x}) \approx f(\mathbf{x}_t) + \nabla f(\mathbf{x}_t)^T \Delta\mathbf{x}$

这就是一阶局部模型。我们想最小化它来决定往哪走。但这里有个问题：这个线性模型没有最小值。不管 $\nabla f$ 指向哪里，我们总可以让 $\Delta\mathbf{x}$ 在 $-\nabla f$ 方向无限延伸，使 $\nabla f^T \Delta\mathbf{x} \to -\infty$。

如上图所示，一阶模型（左）是一个无界的平面，没有极小点；而二阶模型（右）是一个抛物线，自然有极小点。这就是梯度下降需要学习率（learning rate）而牛顿法不需要的根本原因。

信赖域与学习率

解决”线性模型无界”问题的经典方法是加一个信赖域（trust region）约束：我们只相信这个线性近似在当前点附近的一个小球内是准确的。形式上：

$\min_{\Delta\mathbf{x}} \nabla f^T \Delta\mathbf{x} \quad \text{s.t.} \quad \|\Delta\mathbf{x}\| \leq \eta$

其中 $\eta > 0$ 是信赖域半径。这个约束优化问题的解很直观：在长度为 $\eta$ 的所有向量中，使 $\nabla f^T \Delta\mathbf{x}$ 最小（最负）的方向就是 $-\nabla f$ 的方向。因此：

$\Delta\mathbf{x}^* = -\eta \frac{\nabla f}{\|\nabla f\|}$

信赖域方法给出归一化步 $-\eta\nabla f / \|\nabla f\|$，步长恒为 $\eta$。但在实践中，更常见的做法是直接让步长正比于梯度大小——梯度大时走得远，梯度小时走得近（接近极值点时自然减速）。这就是经典的梯度下降更新规则：

逐项理解：

• $\mathbf{x}_t$：当前参数位置
• $\nabla f(\mathbf{x}_t)$：当前位置的梯度——指向 $f$ 增长最快的方向
• $-\nabla f$：$f$ 下降最快的方向
• $\eta$：学习率——缩放因子，控制每步走多远。太大会冲过头，太小则收敛慢

学习率的困境

学习率 $\eta$ 的选择是梯度下降最关键的超参数：

• $\eta$ 太大：步长超出线性近似的有效范围，可能跳过最小值甚至发散
• $\eta$ 太小：每步进展微小，需要大量迭代才能收敛
• 最优 $\eta$ 取决于损失曲面的曲率——而曲率在不同方向上可能差异巨大

对于二次函数 $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T H \mathbf{x}$（$H$ 正定），最优学习率有精确公式：

$\eta^* = \frac{2}{\lambda_{\max} + \lambda_{\min}}$

其中 $\lambda_{\max}, \lambda_{\min}$ 是 Hessian $H$ 的最大和最小特征值。这个最优学习率是两个极端的折中——既不能大到在大曲率方向（$\lambda_{\max}$）上发散，也要足够大以在小曲率方向（$\lambda_{\min}$）上有效前进。

收敛速率与条件数

梯度下降的收敛速率直接取决于 Hessian 的条件数 $\kappa(H) = \lambda_{\max}/\lambda_{\min}$（范数与条件数详细讨论了条件数）。对于正定二次函数 $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T H \mathbf{x}$，使用最优学习率时，每步的损失衰减满足（见 Nocedal & Wright, 2006, Chapter 3）：

这个公式的含义非常直观：

• $\kappa = 1$（完美条件）：$\left(\frac{0}{2}\right)^2 = 0$。一步就收敛到最小值！此时等高线是正圆，梯度直指圆心
• $\kappa = 2$：$\left(\frac{1}{3}\right)^2 = 1/9 \approx 0.11$。每步损失降到前一步的 11%，约 20 步收敛到 $10^{-20}$
• $\kappa = 10$：$\left(\frac{9}{11}\right)^2 \approx 0.67$。每步只降 33%，需要约 60 步收敛到 $10^{-10}$
• $\kappa = 100$：$\left(\frac{99}{101}\right)^2 \approx 0.96$。每步只降 4%，需要约 500 步

条件数越大，梯度下降越慢——这是一个定量的、精确的结论，而非模糊的直觉。

为什么 GD 在高条件数时会震荡？

几何上看，当 $\kappa \gg 1$ 时，等高线是非常扁的椭圆。梯度垂直于等高线，所以它几乎垂直于椭圆的长轴方向（真正需要走的方向），而几乎平行于短轴方向（已经很接近最优的方向）。

结果是梯度下降在窄谷的两壁之间来回弹跳（短轴方向上过度修正），而在谷底方向（长轴方向）上进展缓慢。这就是经典的锯齿形（zig-zag）轨迹。

下面的交互组件让你直观感受这个现象——调大条件数 $\kappa$，观察 GD 轨迹如何变成锯齿：

优化算法可视化

对比 GD、Newton、Momentum 在不同条件数下的表现

梯度下降 (GD)牛顿法 (Newton)GD + Momentum

条件数 κ: 5.0学习率 η: 0.120

单步播放重置

迭代: 0损失: 8.8419

3D 曲面

等高线 + 轨迹

试试以下实验：

1. 选择 GD，设 $\kappa = 1$，观察轨迹几乎直线到达原点
2. 逐渐增大 $\kappa$ 到 10、15、20，观察锯齿越来越明显
3. 切换到 Newton，无论 $\kappa$ 多大，一步到位
4. 切换到 Momentum，观察它如何减轻锯齿现象

牛顿法——二阶方法

从二阶 Taylor 推导

牛顿法使用完整的二阶 Taylor 展开作为局部模型：

$f(\mathbf{x}_t + \Delta\mathbf{x}) \approx f(\mathbf{x}_t) + \nabla f^T \Delta\mathbf{x} + \frac{1}{2}\Delta\mathbf{x}^T H \Delta\mathbf{x}$

其中 $\nabla f = \nabla f(\mathbf{x}_t)$ 是当前梯度，$H = \nabla^2 f(\mathbf{x}_t)$ 是当前 Hessian。

这个二次模型（当 $H$ 正定时）有最小值。对 $\Delta\mathbf{x}$ 求梯度并令其为零：

$\nabla_{\Delta\mathbf{x}} m_t = \nabla f + H\Delta\mathbf{x} = \mathbf{0}$

解出最优步长：

$\Delta\mathbf{x}^* = -H^{-1}\nabla f$

这就是牛顿步（Newton step）。代入更新规则：

逐项理解：

• $\nabla f(\mathbf{x}_t)$：当前梯度，告诉我们”方向”
• $H^{-1}$：Hessian 的逆，起到自适应缩放的作用——在曲率大的方向上缩小步长，在曲率小的方向上放大步长
• $-H^{-1}\nabla f$：兼顾了方向和步长的最优选择

关键性质

性质 1：对二次函数一步收敛。如果 $f$ 本身就是二次函数，那么二阶 Taylor 展开就是精确的（没有高阶项）。这意味着牛顿步直接跳到二次函数的最小值——一步到位。

性质 2：不需要学习率。Hessian 矩阵编码了曲面在各方向的曲率信息，$H^{-1}$ 自动将梯度方向按曲率进行适当缩放。曲率大的方向步长自动变小（高曲率意味着函数弯曲剧烈，大步会冲过头），曲率小的方向步长自动变大（低曲率意味着函数近乎平坦，需要大步才能有效推进）。

性质 3：局部二次收敛。在足够接近最小值 $\mathbf{x}^*$ 时，牛顿法的收敛速率是二次的（quadratic convergence）：

$\|\mathbf{x}_{t+1} - \mathbf{x}^*\| \leq C\|\mathbf{x}_t - \mathbf{x}^*\|^2$

其中 $C$ 是一个常数。“二次收敛”意味着：如果当前误差是 $10^{-3}$，下一步误差约为 $10^{-6}$，再下一步约为 $10^{-12}$——有效数字每步翻倍。这比 GD 的线性收敛快得多。

注意：这是一个局部结果——需要起点足够接近 $\mathbf{x}^*$ 才成立。远离最小值时，牛顿法可能表现不佳（如果 $H$ 不正定，步可能朝错误方向走）。

几何直觉：球形步 vs 椭球形步

这是理解 GD 和牛顿法区别最深刻的直觉。

GD 在特征基下的行为：GD 取步 $-\eta\nabla f$。在 Hessian 的特征基下，对于二次函数，梯度在特征方向 $\mathbf{q}_i$ 上的分量是 $g_i = \lambda_i x_i$。GD 的步长正比于 $\eta\lambda_i x_i$——大特征值方向走得多，小特征值方向走得少。但大 $\lambda_i$ 意味着曲率高，等高线在该方向上很”窄”，应该走得少才不会冲过头；小 $\lambda_i$ 意味着曲率低，等高线在该方向上很”宽”，应该走得多才能有效推进。GD 完全搞反了。

Newton 在特征基下的行为：Newton 取步 $-H^{-1}\nabla f$。在特征基下，$H^{-1}$ 将每个方向的梯度分量除以对应的特征值。具体地，如果梯度在特征方向 $\mathbf{q}_i$ 上的分量是 $g_i = \lambda_i x_i$（对于从原点出发的二次函数），那么 Newton 步在该方向上的分量是 $g_i / \lambda_i = x_i$——恰好是到最优点的距离。

换言之：

• GD 取球形步（step size ∝ gradient magnitude，不考虑曲率）
• Newton 取椭球形步（step size 自适应曲率，在每个方向上恰好走到最优）

这就是为什么 GD 锯齿而 Newton 直达的根本原因。

上图清晰地展示了这个对比：在条件数 $\kappa = 10$ 的椭圆形等高线上，GD 需要大量步才能沿着窄谷前进（因为它总在谷壁间弹跳），而 Newton 一步就到达最小值。

代价问题

牛顿法效果虽好，但代价昂贵。对于 $n$ 个参数：

• 存储 Hessian：$H \in \mathbb{R}^{n \times n}$，需要 $O(n^2)$ 内存
• 求解线性系统 $H\Delta\mathbf{x} = -\nabla f$：$O(n^3)$ 计算量
• 计算 Hessian 各元素：每个二阶偏导需要额外的反向传播

对于深度学习模型（$n$ 可达 $10^9$），$O(n^2)$ 的存储和 $O(n^3)$ 的计算都完全不可行——一个 $10^9 \times 10^9$ 的矩阵需要约 $10^{18}$ 字节 = 1 EB（exabyte）的存储，这远超任何计算机的能力。

这就是为什么深度学习主要使用一阶方法（GD、SGD、Adam），而将牛顿法的思想作为启发来设计更高效的近似方案。

数值例子

用上一篇完全相同的二次损失函数，把两种算法的效果看清楚：

$\mathcal{L}(w_1, w_2) = 3w_1^2 + 2w_1w_2 + 2w_2^2$

回忆上一篇的结果：

• 梯度：$\nabla \mathcal{L} = (6w_1 + 2w_2, \; 2w_1 + 4w_2)^T$
• Hessian：$H = \begin{bmatrix}6 & 2 \\ 2 & 4\end{bmatrix}$（常数矩阵，因为 $\mathcal{L}$ 是二次的）
• 特征值：$\lambda_1 = 5 + \sqrt{5} \approx 7.24$，$\lambda_2 = 5 - \sqrt{5} \approx 2.76$
• 条件数：$\kappa \approx 2.62$
• 唯一最小值在原点 $(0, 0)$

梯度下降

起点 $\mathbf{w}_0 = (1, 1)^T$：

第 0 步：$\mathcal{L}(1, 1) = 3 + 2 + 2 = 7$，$\nabla\mathcal{L} = (8, 6)^T$

第 1 步（$\eta = 0.1$）： $\mathbf{w}_1 = (1, 1)^T - 0.1 \cdot (8, 6)^T = (0.2, 0.4)^T$ $\mathcal{L}(0.2, 0.4) = 3(0.04) + 2(0.08) + 2(0.16) = 0.12 + 0.16 + 0.32 = 0.60$

损失从 7 降到 0.60——一步降了 91%。

第 2 步：$\nabla\mathcal{L}(0.2, 0.4) = (2.0, 2.0)^T$ $\mathbf{w}_2 = (0.2, 0.4)^T - 0.1 \cdot (2.0, 2.0)^T = (0.0, 0.2)^T$ $\mathcal{L}(0, 0.2) = 0 + 0 + 2(0.04) = 0.08$

第 3 步：$\nabla\mathcal{L}(0, 0.2) = (0.4, 0.8)^T$ $\mathbf{w}_3 = (0, 0.2)^T - 0.1 \cdot (0.4, 0.8)^T = (-0.04, 0.12)^T$ $\mathcal{L}(-0.04, 0.12) = 3(0.0016) + 2(-0.0048) + 2(0.0144) = 0.0048 - 0.0096 + 0.0288 = 0.024$

三步后损失从 7 降到 0.024。收敛中，但离零还有距离。

步	$w_1$	$w_2$	$\mathcal{L}$
0	1.000	1.000	7.000
1	0.200	0.400	0.600
2	0.000	0.200	0.080
3	−0.040	0.120	0.024

牛顿法

起点同样是 $\mathbf{w}_0 = (1, 1)^T$。

$H^{-1}$ 的计算：对 $H = \begin{bmatrix}6 & 2 \\ 2 & 4\end{bmatrix}$，$\det(H) = 24 - 4 = 20$，所以：

$H^{-1} = \frac{1}{20}\begin{bmatrix}4 & -2 \\ -2 & 6\end{bmatrix} = \begin{bmatrix}0.2 & -0.1 \\ -0.1 & 0.3\end{bmatrix}$

牛顿步：

$\Delta\mathbf{w} = -H^{-1}\nabla\mathcal{L}(1,1) = -\begin{bmatrix}0.2 & -0.1 \\ -0.1 & 0.3\end{bmatrix}\begin{bmatrix}8 \\ 6\end{bmatrix} = -\begin{bmatrix}1.6 - 0.6 \\ -0.8 + 1.8\end{bmatrix} = -\begin{bmatrix}1.0 \\ 1.0\end{bmatrix} = \begin{bmatrix}-1.0 \\ -1.0\end{bmatrix}$

$\mathbf{w}_1 = (1, 1)^T + (-1, -1)^T = (0, 0)^T$

一步就到达了最小值 $(0, 0)$，$\mathcal{L}(0, 0) = 0$。

这不是巧合——$\mathcal{L}$ 是二次函数，所以二阶 Taylor 展开是精确的，牛顿步必然一步到位。而 GD 三步后仍然是 0.024，还需要继续迭代。

对比总结

算法	步数到 $\mathcal{L} < 0.001$	每步需要	总代价
GD ($\eta = 0.1$)	~8 步	梯度 $O(n)$	$O(8n)$
Newton	1 步	梯度 $O(n)$ + $H^{-1}$ $O(n^3)$	$O(n^3)$

对于 $n = 2$ 这样的小问题，Newton 显然更好。但当 $n = 10^9$ 时，$O(n^3)$ 是不可承受的，$O(8n)$ 反而实际可行——这就是深度学习用 GD 变体而非 Newton 的原因。

随机梯度下降 (SGD)

全批量 GD 在大数据上的困难

在 ML 中，损失函数通常是所有训练样本的平均损失：

$\mathcal{L}(\boldsymbol{\theta}) = \frac{1}{N}\sum_{i=1}^{N} \ell(\boldsymbol{\theta}; \mathbf{x}_i, y_i)$

其中 $\boldsymbol{\theta}$ 是模型参数，$(\mathbf{x}_i, y_i)$ 是第 $i$ 个训练样本，$N$ 是训练集大小。

计算完整梯度 $\nabla\mathcal{L}$ 需要遍历所有 $N$ 个样本：

$\nabla\mathcal{L}(\boldsymbol{\theta}) = \frac{1}{N}\sum_{i=1}^{N} \nabla_{\boldsymbol{\theta}}\ell(\boldsymbol{\theta}; \mathbf{x}_i, y_i)$

当 $N = 10^6$（如 ImageNet）甚至 $N = 10^{12}$（如大语言模型的训练语料），每一步 GD 都需要处理全部数据——代价极高。而且在到达最小值之前，我们需要很多步。能否做得更快？

SGD 的核心思想

SGD（Stochastic Gradient Descent，随机梯度下降）的思路很简单：不用全部数据计算梯度，随机抽一小批。

每步随机采样一个 mini-batch（小批量）$\mathcal{B} \subset \{1, 2, \ldots, N\}$，用它估计梯度：

$\hat{g} = \frac{1}{|\mathcal{B}|}\sum_{i \in \mathcal{B}} \nabla_{\boldsymbol{\theta}}\ell(\boldsymbol{\theta}; \mathbf{x}_i, y_i)$

然后像 GD 一样更新：$\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta\hat{g}$。

关键性质：无偏估计。由于 mini-batch 是均匀随机采样的：

$\mathbb{E}[\hat{g}] = \frac{1}{N}\sum_{i=1}^{N} \nabla_{\boldsymbol{\theta}}\ell(\boldsymbol{\theta}; \mathbf{x}_i, y_i) = \nabla\mathcal{L}(\boldsymbol{\theta})$

即随机梯度的期望等于真实梯度。每一步的方向可能有偏差，但平均来看方向是对的。

代价优势：如果 mini-batch 大小 $|\mathcal{B}| = 64$，每步只需处理 64 个样本而非全部 $10^6$ 个。虽然每步不那么精确，但可以用同样的时间跑大约 $10^6 / 64 \approx 15000$ 步——在实践中这通常更高效。

噪声是 bug 还是 feature？

直觉上，SGD 的噪声是一个”缺点”——每步方向不精确。但近年来的研究发现，这个噪声实际上有正面作用：

1. 逃离尖锐极小值：SGD 的随机扰动使得优化轨迹不会被困在尖锐（sharp）的局部最小值中——噪声会把参数弹出来
2. 隐式正则化：SGD 倾向于收敛到平坦（flat）的极小值，而平坦极小值通常泛化性能更好。直觉上，平坦极小值附近的 Hessian 特征值较小，对参数扰动不敏感——这正是泛化所需要的
3. 实验证据：大 batch 训练（噪声小）往往比小 batch 训练（噪声大）泛化更差，尽管它们找到的训练损失相当

收敛速率

SGD 在凸问题上的收敛速率为 $O(1/\sqrt{T})$（其中 $T$ 是迭代次数），慢于全批量 GD 的线性收敛。但由于每步代价低得多（$O(|\mathcal{B}|)$ vs $O(N)$），按墙钟时间计算，SGD 通常更快达到可接受的精度（详见 Bottou, Curtis, Nocedal, 2018）。

实用方法概览

纯 GD 太慢（锯齿问题），纯 Newton 太贵（$O(n^3)$），SGD 有噪声。实际深度学习中使用的方法介于两者之间——用一阶信息的代价，近似二阶方法的效果。

Momentum（动量）

提出者：Polyak, 1964。

GD 的锯齿问题源于：在窄谷中，梯度在短轴方向上来回震荡。如果我们记住之前的方向，让更新”有惯性”，震荡方向的分量会互相抵消，而持续前进方向的分量会累积。

逐项理解：

• $\beta\mathbf{v}_t$：保留上一步速度的 $\beta$ 倍——“惯性”
• $-\eta\nabla f$：新的梯度贡献——“加速度”
• 效果：在持续下降的方向上速度累积加快，在震荡方向上正负抵消趋于零

物理类比：一个球在碗里滚动。没有 Momentum 的 GD 像在粘稠的液体中移动（每步独立，无惯性）。有 Momentum 的 GD 像在光滑碗里滚——会积累速度、超越底部、然后来回摆动逐渐减速停下。

Adam（Adaptive Moment Estimation）

提出者：Kingma & Ba, 2015（arXiv:1412.6980）。

Adam 是深度学习中最流行的优化器。它的核心思想是为每个参数维护独立的学习率，根据梯度历史自适应调节。

Adam 维护两个指数移动平均：

• 一阶矩 $\mathbf{m}_t = \beta_1 \mathbf{m}_{t-1} + (1-\beta_1)\nabla f$ ——梯度的平均方向（类似 Momentum）
• 二阶矩 $\mathbf{v}_t = \beta_2 \mathbf{v}_{t-1} + (1-\beta_2)(\nabla f)^2$ ——梯度平方的平均（逐元素），估计每个维度的方差

更新规则（经过偏差校正后）：

$\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta \frac{\hat{\mathbf{m}}_t}{\sqrt{\hat{\mathbf{v}}_t} + \epsilon}$

其中除法和平方根都是逐元素操作，$\epsilon \approx 10^{-8}$ 防止除零。

与 Newton 的联系：Newton 更新是 $-H^{-1}\nabla f$，需要完整的 $n \times n$ Hessian 逆。Adam 用 $\sqrt{\hat{\mathbf{v}}_t}$（梯度平方的移动平均）对每个参数维度做缩放，效果类似于用一个对角矩阵近似 $H$——在梯度波动大的维度上自动缩小步长，在梯度稳定的维度上放大步长。这不是精确的 Hessian 对角线（$\mathbb{E}[g_i^2]$ 包含了梯度方差的贡献），但直觉类似：只用 $O(n)$ 的额外存储，获得了部分自适应曲率的好处。

L-BFGS

L-BFGS（Limited-memory BFGS）（见 Nocedal & Wright, 2006）用最近 $m$ 步的梯度差来隐式近似 $H^{-1}$。它不显式存储 $n \times n$ 矩阵，只存 $m$ 对向量（$m$ 通常取 10-20），所以内存是 $O(mn)$。

L-BFGS 是中等规模优化的首选方法（如逻辑回归、SVM、矩阵分解），但对于深度学习的参数规模（$n > 10^8$），即使 $O(mn)$ 也过于昂贵，而且 L-BFGS 不天然适配 mini-batch 噪声。

谱系总结

从左到右，算法用越来越多的曲率信息，收敛越来越快，但每步代价也越来越高。深度学习的”甜蜜点”在 Adam 附近——用一阶代价 $O(n)$，获得部分二阶好处。

收敛速率可视化

下面的交互组件展示不同算法在同一个二次函数上的收敛曲线。调整条件数 $\kappa$，观察 GD 曲线如何被拖慢，而 Newton 几乎不受影响：

收敛速度对比

调整条件数 κ，观察不同算法的收敛曲线

条件数 κ: 5.0

梯度下降牛顿法MomentumGD 理论上界

注意观察：当 $\kappa$ 增大时，GD 曲线（蓝色）和理论上界（虚线）越来越接近——说明在高条件数时，GD 的实际表现接近理论最差情况。而 Momentum（橙色）通过累积速度，在高 $\kappa$ 时比纯 GD 有明显改善。

优化视角下的矩阵分解

优化算法不仅用于训练神经网络，矩阵分解本身也可以用优化的视角来理解。这一节简要预览几个重要的连接，为后续文章做铺垫。

Power iteration = 对 Rayleigh 商的梯度上升

SVD 和 随机化 SVD 中的核心算法 power iteration（幂迭代）$\mathbf{v} \leftarrow A^TA\mathbf{v} / \|A^TA\mathbf{v}\|$，可以理解为对 Rayleigh 商（Rayleigh quotient）的梯度上升：

$R(\mathbf{v}) = \frac{\mathbf{v}^T A^TA\mathbf{v}}{\mathbf{v}^T\mathbf{v}}$

$R(\mathbf{v})$ 在 $A^TA$ 的最大特征向量处取到最大值 $\sigma_1^2$（最大奇异值的平方）。Power iteration 就是在单位球面上对 $R(\mathbf{v})$ 做梯度上升——每步沿梯度方向走，然后投影回单位球面（归一化）。

低秩逼近的优化视角

矩阵补全（matrix completion）和非负矩阵分解（NMF）都可以表述为优化问题。例如，秩 $k$ 逼近：

$\min_{U \in \mathbb{R}^{m \times k}, V \in \mathbb{R}^{n \times k}} \|A - UV^T\|_F^2$

这个问题可以用交替最小化（alternating least squares, ALS）求解：固定 $U$ 优化 $V$（线性最小二乘），再固定 $V$ 优化 $U$，交替进行。每步都是一个凸问题，但联合问题是非凸的。

Oja 算法 = 在线 SGD 做 PCA

Oja (1982) 提出的算法展示了 SGD 和 PCA 的深刻联系：给定一个流式数据 $\mathbf{x}_1, \mathbf{x}_2, \ldots$，Oja 算法用 SGD 的方式在线更新主成分方向 $\mathbf{w}$：

$\mathbf{w}_{t+1} = \mathbf{w}_t + \eta_t \left(\mathbf{x}_t\mathbf{x}_t^T\mathbf{w}_t - (\mathbf{w}_t^T\mathbf{x}_t\mathbf{x}_t^T\mathbf{w}_t)\mathbf{w}_t\right)$

每步只看一个样本 $\mathbf{x}_t$，不需要存储整个数据矩阵。这在数据流式到达或数据量太大无法一次性加载时非常有用——是 SGD 思想在矩阵分解中的直接应用。

这些连接将在 PCA、随机化 SVD 和 矩阵补全 中详细展开。

总结与展望

本文从”近似、求解、迈步”的统一框架出发，推导了优化算法的核心方法。回顾关键要点：

• 统一框架：所有迭代优化 = 选择局部模型 + 求解模型最小值 + 更新参数。模型精度决定算法：一阶→GD，二阶→Newton
• 梯度下降：$\mathbf{x}_{t+1} = \mathbf{x}_t - \eta\nabla f$。简单、$O(n)$ 每步，但收敛取决于条件数 $\kappa$。收敛率 $\leq \left(\frac{\kappa-1}{\kappa+1}\right)^2$ 每步
• 牛顿法：$\mathbf{x}_{t+1} = \mathbf{x}_t - H^{-1}\nabla f$。利用曲率信息，不需要学习率，局部二次收敛。但 $O(n^3)$ 太贵
• SGD：随机采样 mini-batch 估计梯度，$O(|\mathcal{B}|)$ 每步。噪声是 feature 不是 bug——有助于找到平坦极小值
• 实用方法：Momentum 用惯性减少锯齿，Adam 用对角近似 Hessian 自适应调学习率，L-BFGS 用梯度历史近似 $H^{-1}$
• 矩阵分解的优化视角：power iteration = Rayleigh 商梯度上升，低秩逼近 = 交替最小化，Oja 算法 = 在线 SGD 做 PCA

至此，Part 1 “拆” 的核心工具已经完备：分解（特征分解 + SVD）、度量（范数 + 条件数）、微分（梯度 + Hessian）、优化（GD + Newton + SGD）。下一篇将学习 PCA（主成分分析）——它是分解工具的第一个经典应用，通过对数据协方差矩阵的特征分解，找到数据中方差最大的方向，实现降维。PCA 的优化目标（最大化方差 / 最小化重建误差）正是本文建立的优化框架的具体实例。