# 牛顿法与梯度下降的完整比较

[[MCS/day6/00 学习指南|day6 学习指南]] · [[MCS/00 MCS学习总览|十一天总览]] · [[MCS/day6/阅读核验与疑问|阅读核验与疑问]] · 上一篇：[[MCS/day6/06 libm 的函数逼近与工程实现|libm 的函数逼近与工程实现]] · 下一篇：[[MCS/day6/08 牛顿法、拟牛顿法与 Adam 问答|牛顿法、拟牛顿法与 Adam 问答]]

> 来源：[[MCS/day6补充3|day6补充3]]。用途：补充。原有推导、追问与解答保留；阅读时请结合本日核验说明。

## 牛顿法 vs 梯度下降：完整整理

### 一、核心结论

- **牛顿法比梯度下降"快"**：指的是**迭代次数少**（收敛快），不是每步算得快。
- **牛顿法每步更贵**：要算海森矩阵、存海森矩阵、求逆/解方程，代价远高于梯度。
- 两者不矛盾，衡量的是不同维度。

| | 每步成本 | 迭代次数 | 用的信息 |
|---|---|---|---|
| 梯度下降 | 便宜，$O(n)$ | 多 | 一阶梯度 |
| 牛顿法 | 贵，$O(n^3)$ | 少 | 一阶梯度 + 二阶海森 |

---

### 二、泰勒展开视角

在点 $x_k$ 处展开：

$$
f(x) = f(x_k) + f'(x_k)(x-x_k) + \frac{1}{2}f''(x_k)(x-x_k)^2 + \cdots
$$

- **一阶泰勒**：保留到一次项 → 直线（切线）→ 梯度下降用
- **二阶泰勒**：保留到二次项 → 抛物线 → 牛顿法用

#### 梯度下降

$$
f(x) \approx f(x_k) + f'(x_k)(x-x_k)
$$

$$
x_{k+1} = x_k - \alpha f'(x_k)
$$

只知道斜率，步长靠调。

#### 牛顿法

$$
f(x) \approx f(x_k) + f'(x_k)(x-x_k) + \frac{1}{2}f''(x_k)(x-x_k)^2
$$

令导数为零，跳到抛物线顶点：

$$
x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)}
$$

多维形式：

$$
x_{k+1} = x_k - H^{-1}\nabla f
$$

---

### 三、求根牛顿法 vs 优化牛顿法

容易混淆的地方，必须分开。

#### 求根牛顿法：解 $g(x)=0$

对 $g(x)$ 做**一阶泰勒**：

$$
g(x) \approx g(x_k) + g'(x_k)(x-x_k)
$$

令其为零：

$$
x_{k+1} = x_k - \frac{g(x_k)}{g'(x_k)}
$$

几何图像：**切线逼近零点**。

#### 优化牛顿法：求 $f(x)$ 极小

对 $f(x)$ 做**二阶泰勒**：

$$
f(x) \approx f(x_k) + f'(x_k)(x-x_k) + \frac{1}{2}f''(x_k)(x-x_k)^2
$$

令导数为零：

$$
x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)}
$$

几何图像：**抛物线逼近极小点**。

#### 两者的关系

优化牛顿法 = 对 $f'$ 做求根牛顿法：

$$
x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)}
$$

所以：

- 对 $f$ 看：二阶泰勒，抛物线。
- 对 $f'$ 看：一阶泰勒，切线。
- 对 $g$ 看：求根牛顿法，一阶泰勒，切线。

三种说法描述同一件事，视角不同。

#### 对照表

| | 求根牛顿法 | 优化牛顿法 |
|---|---|---|
| 目标 | 解 $g(x)=0$ | 求 $f(x)$ 极小 |
| 泰勒对象 | 对 $g$ 一阶泰勒 | 对 $f$ 二阶泰勒 |
| 几何图像 | 切线逼近零点 | 抛物线逼近极小点 |
| 更新式 | $x - g/g'$ | $x - f'/f''$ |
| 等价说法 | — | 对 $f'$ 做一阶泰勒求根 |

---

### 四、海森矩阵的代价

海森矩阵 $H$ 的元素：

$$
H_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}
$$

是 $n \times n$ 矩阵，约 $n^2/2$ 个独立元素。

#### 1. 计算代价

- 解析求导：很多函数没有简单解析式。
- 自动微分：算完整海森通常要 $O(n)$ 次反向传播。
- 有限差分：每个元素扰动一次，要 $O(n)$ 次梯度计算。

梯度只需一次反向传播。

#### 2. 存储代价

存 $n^2$ 个数：

- $n = 10^3$：约 8 MB，还好。
- $n = 10^5$：约 80 GB，单机放不下。
- $n = 10^6$：TB 级，不现实。

梯度只需存 $n$ 个数。

#### 3. 求逆/解方程代价

解 $Hd = -\nabla f$，Cholesky/LU 分解约 $O(n^3)$：

- $n = 10^3$：约 $10^9$ 次运算。
- $n = 10^4$：约 $10^{12}$ 次，很慢。
- $n = 10^5$：约 $10^{15}$ 次，不可行。

#### 4. 数值与条件代价

- **非正定**：非凸区域海森可能有负特征值，方向可能上升，牛顿法发散。
- **奇异**：不可逆，方程无解或无穷多解。
- **病态**：条件数大，求逆放大误差，方向抖动。

#### 5. 适用性代价

深度学习中用随机梯度，海森在随机设定下噪声大，不同 batch 差异大，算精确海森得不偿失。

---

### 五、海森非奇异时

非奇异只解决**可解性**，不解决其他问题。

| 问题 | 非奇异后 |
|---|---|
| 方程可解 | 解决 |
| 方向是下降方向 | 不一定，需正定 |
| 每步 $O(n^3)$ | 没变 |
| 存储 $O(n^2)$ | 没变 |
| 算 $H$ 贵 | 没变 |
| 病态数值不稳 | 没变 |

**非奇异 ≠ 正定**。有负特征值时，牛顿方向可能指向上升方向。

即使既非奇异又正定，单步 $O(n^3)$ 成本依然存在，大规模问题仍不可承受。

---

### 六、海森奇异时：如何修正

奇异时不能直接求逆，需要修正成非奇异（最好正定）。

#### 1. 加正则项：$H + \lambda I$

$$
(H + \lambda I) d = -\nabla f
$$

- $\lambda > 0$ 时，特征值变为 $\mu_i + \lambda$，足够大就全正。
- 同时解决奇异和非正定。
- 这是**阻尼牛顿法 / Levenberg-Marquardt** 的核心。

$$\lambda$$ 的作用：

- $\lambda \to 0$：接近纯牛顿法，快但不稳。
- $\lambda \to \infty$：退化成小步梯度下降。

$$\lambda$$ 是牛顿法与梯度下降之间的调节旋钮。

#### 2. 伪逆：Moore-Penrose

$$
d = -H^+ \nabla f
$$

在零空间给最小范数解。但不保证下降方向，计算也不便宜。

#### 3. 信赖域方法

解带约束子问题：

$$
\min_d \quad \nabla f^T d + \frac{1}{2} d^T H d
$$

$$
\text{s.t.} \quad \|d\| \le \Delta
$$

约束自然限制步长，避免方向爆炸。与加正则项数学上等价于某个 $\lambda$。

#### 4. 特征值修正

对 $H = Q\Lambda Q^T$，替换非正特征值：

$$
\Lambda' = \text{diag}(\max(\mu_i, \epsilon))
$$

用 $H' = Q\Lambda' Q^T$。能保证正定，但特征分解是 $O(n^3)$。

#### 5. 拟牛顿法：根本不碰 $H$

- **BFGS**：维护正定近似 $B_k \approx H$，更新公式天然保持正定。
- **L-BFGS**：只存少量向量，存储 $O(n)$，每步 $O(n)$。

大规模优化主流，绕开算 $H$、存 $H$、求逆 $H$ 的全部代价。

#### 修正后还是牛顿法吗

- 纯牛顿法：真实 $H$，解 $Hd = -\nabla f$。
- 阻尼牛顿法：用 $H + \lambda I$，仍二阶。
- 拟牛顿法：用近似 $B_k$，二阶近似。
- 信赖域：约束下用 $H$，本质二阶。

都保留利用曲率信息，比梯度下降收敛快；同时修正避免奇异性。

#### 修正的代价

加正则、伪逆、特征值修正，都仍在 $O(n^3)$ 量级，没降低单步成本。解决的是**能不能算、稳不稳**，不是**贵不贵**。

真正降成本的是拟牛顿法和 L-BFGS。

---

### 七、为什么牛顿法迭代次数少

因为用了**曲率信息**。

梯度下降只知道斜率，在狭长山谷里梯度方向几乎垂直于谷底，来回震荡，走很多冤枉路。

牛顿法用 $H^{-1}$ 把空间"拉平"：

$$
x_{k+1} = x_k - H^{-1}\nabla f
$$

把狭长山谷变成近似圆形，直接指向极小点。

- 对二次函数：一步到位。
- 对一般光滑函数：极小点附近二次收敛（误差平方级减小）。

---

### 八、总成本比较

设 $n$ 为参数维度：

- 梯度下降：每步 $O(n)$，迭代 $K_1$ 次，总成本 $O(K_1 n)$。
- 牛顿法：每步 $O(n^3)$，迭代 $K_2$ 次，总成本 $O(K_2 n^3)$。

虽然 $K_2 \ll K_1$，但 $n^3$ 在大 $n$ 时爆炸：

- 小规模、高精度：牛顿法总时间可能更短。
- 大规模（深度学习）：牛顿法每步成本无法承受，梯度下降或拟牛顿法总时间更短。

---

### 九、一句话总结

- 牛顿法快在**迭代次数**，贵在**单步成本**。
- 用二阶泰勒（抛物线）逼近，梯度下降用一阶泰勒（切线）逼近。
- 求根牛顿法对 $g$ 一阶泰勒（切线）；优化牛顿法对 $f$ 二阶泰勒（抛物线）；两者更新式相同。
- 海森矩阵代价：算 $O(n)$ 次梯度级计算，存 $O(n^2)$，求逆 $O(n^3)$，还可能奇异、非正定、病态。
- 非奇异只解决可解性，不解决成本和正定性。
- 奇异时用 $H + \lambda I$、伪逆、信赖域、特征值修正，或直接用 BFGS/L-BFGS。
- 修正解决可解性和稳定性，不解决单步成本高。
- 大规模问题主流：拟牛顿法（L-BFGS）和一阶自适应方法（Adam 等）。