# 牛顿法、拟牛顿法与 Adam 问答

[[MCS/day6/00 学习指南|day6 学习指南]] · [[MCS/00 MCS学习总览|十一天总览]] · [[MCS/day6/阅读核验与疑问|阅读核验与疑问]] · 上一篇：[[MCS/day6/07 牛顿法与梯度下降的完整比较|牛顿法与梯度下降的完整比较]] · 下一篇：[[MCS/day6/09 XGBoost、优化器选择与收敛邻域|XGBoost、优化器选择与收敛邻域]]

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

## 牛顿法、拟牛顿法与 Adam：从求根到深度学习的优化方法总结

### 一、核心思想：优化问题如何变成求根问题

#### 1. 从“求最小”到“求零点”

优化问题 `Min f(x)` 的必要条件是导数等于零：

$$f'(x)=0$$

这一步把**优化问题**转化成了**求根问题**。原本找最低点，现在找导数为零的点。

#### 2. 牛顿法求根

对函数 $g(x)$ 求零点，牛顿-拉佛森迭代公式为：

$$x_{n+1}=x_n-\frac{g(x_n)}{g'(x_n)}$$

令 $g(x)=f'(x)$，得到优化中的牛顿法：

$$x_{n+1}=x_n-\frac{f'(x_n)}{f''(x_n)}$$

**一维情况**：梯度除以曲率，标量除以标量。  
**多维情况**：

$$x \leftarrow x - H^{-1}\nabla f$$

其中 $H$ 是海森矩阵，$\nabla f$ 是梯度。

#### 3. 牛顿法的来源：二次近似

用二次函数局部近似原函数：

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

对 $x$ 求导并令其为零，直接跳到二次函数的极值点，得到同样的迭代公式。

---

### 二、为什么优化牛顿法要令 $g(x)=f'(x)$

核心逻辑链：

$$\min f(x)
\;\Longrightarrow\;
f'(x)=0
\;\Longrightarrow\;
\text{令 } g(x)=f'(x)
\;\Longrightarrow\;
x_{n+1}=x_n-\frac{g(x_n)}{g'(x_n)}
=x_n-\frac{f'(x_n)}{f''(x_n)}$$

牛顿法本身只认一个东西：它要求零点的那个函数，记作 $g(x)$。  
优化问题的一阶必要条件，就是把 $f'(x)$ 当作要求零点的那个函数。

多维对应：

| 一维 | 多维 |
|------|------|
| $g(x)=f'(x)$ | $g(x)=\nabla f(x)$ |
| $g'(x)=f''(x)$ | $g'(x)=H(x)$ 海森矩阵 |
| 标量除以标量 | 矩阵求逆乘以向量 |

---

### 三、二阶导数符号与极值：不用泰勒的形象解释

核心两句话：

> **一阶导数 $f'(x)$ 管“上坡还是下坡”；二阶导数 $f''(x)$ 管“上坡下坡的变化趋势”。**

在驻点 $f'(x_0)=0$ 处：

#### $f''(x_0)>0$：极小值——谷底

$$f'(x)$$ 在 $$x_0$$ 附近递增：

| 位置 | $f'(x)$ | 含义 |
|------|-------------|------|
| $x<x_0$ | $f'(x)<0$ | 下坡，往谷底走 |
| $x=x_0$ | $f'(x)=0$ | 平了，到底了 |
| $x>x_0$ | $f'(x)>0$ | 上坡，离开谷底 |

先降后升，谷底，极小值。

#### $f''(x_0)<0$：极大值——山顶

$$f'(x)$$ 在 $$x_0$$ 附近递减：

| 位置 | $f'(x)$ | 含义 |
|------|-------------|------|
| $x<x_0$ | $f'(x)>0$ | 上坡，往山顶爬 |
| $x=x_0$ | $f'(x)=0$ | 平了，到顶了 |
| $x>x_0$ | $f'(x)<0$ | 下坡，离开山顶 |

先升后降，山顶，极大值。

> 口诀：先降后升，谷底，$f''>0$；先升后降，山顶，$f''<0$。

---

### 四、牛顿法的优点与局限

#### 优点

- **局部二阶收敛**：误差以平方缩小，起步离根不太远、导数不太病态时极快。
- **看见曲率，一步看到谷底**：如果函数接近抛物面，可以直接算到极值点。
- **按曲率重新丈量空间**：对线性缩放不敏感，能缓解病态和尺度问题。

#### 一阶方法做不好的三件事

1. **学习率**：步长难选。
2. **病态**：狭长山谷中曲率差几十倍甚至几百倍，固定步长会走“之”字形。
3. **尺度**：不同变量量级不一致，梯度各分量量级不同。

#### 牛顿法为什么没有解决所有问题

核心是**海森矩阵的问题**：

- 海森矩阵是 $n\times n$。若 $n=100$ 万，双精度存储约需 **8 TB**。
- 求逆复杂度 $O(n^3)$，深度神经网络参数量动辄 billion 级别，根本算不起来。
- 离最优点很远、海森矩阵不正定、鞍点附近时，牛顿法可能比梯度下降更差，甚至发散。

---

### 五、牛顿-康托洛维奇理论：局部二阶收敛

#### 核心结论（记在笔记旁边）

> **康托洛维奇理论：牛顿法局部二阶收敛，误差大约变为上次的平方。**

用公式写：

$$e_{n+1} \approx C \cdot e_n^2$$

其中：

- $e_n = |x_n - x^*|$：第 $n$ 步的误差。
- $e_{n+1}$：下一步的误差。
- $C$：某个常数，与 $f''$ 和 $f'''$ 有关。

#### 什么叫“误差变为上次的平方”？

| 当前误差 $e_n$ | 下一步误差 $e_{n+1}\approx e_n^2$ |
|------------------|--------------------------------------|
| $10^{-3}$ | $10^{-6}$ |
| $10^{-6}$ | $10^{-12}$ |
| $10^{-12}$ | $10^{-24}$ |

**有效数字大约翻倍。**

#### 为什么叫“局部”二阶收敛？

- **局部**：只在根附近才成立。起步必须离根不太远。
- **二阶**：误差以平方速度缩小，而不是线性缩小。
- **收敛**：误差越来越小，最终趋于零。

康托洛维奇的条件大意是：

1. 起步离根不太远。
2. 导数不太病态（$f'$ 不为零，$f''$ 有界）。
3. 满足这些条件时，牛顿法局部二阶收敛。

#### 对比：一阶收敛 vs 二阶收敛

| 收敛阶 | 误差关系 | 例子 |
|--------|----------|------|
| 一阶（线性） | $e_{n+1}\approx C e_n$ | 梯度下降 |
| 二阶（平方） | $e_{n+1}\approx C e_n^2$ | 牛顿法 |

一阶收敛：误差每次缩小固定倍数。  
二阶收敛：误差每次变成上次的平方，越靠近根，快得越夸张。

---

### 六、海森矩阵与正定性

海森矩阵可想象成一张**地形曲率表**：往东多弯、往北多弯、斜着走怎样。

| Hessian 类型 | 特征值符号 | 几何形状 | 驻点类型 |
|--------------|------------|----------|----------|
| **正定** | 全正 | 碗 | 局部极小 |
| **负定** | 全负 | 倒碗 | 局部极大 |
| **不定** | 有正有负 | 马鞍面 | **鞍点** |
| 半正定 | 有零有正 | 平底槽 | 可能是极小，需更高阶判断 |
| 半负定 | 有零有负 | 平顶槽 | 可能是极大，需更高阶判断 |

鞍点 = Hessian 不定 = 特征值有正有负。  
一维没有真正的鞍点，因为只有一个方向。

---

### 七、拟牛顿法：用割线近似曲率

#### 核心思想

不真的算海森矩阵，只用最近几步梯度的变化去估算曲率。

维护一个对称矩阵 $B$ 近似海森矩阵，满足割线方程：

$$Bs=y$$

- $s$：自变量变化量（走的多点）。
- $y$：梯度变化量。

即用**差商代替 $f''$ **，这叫**割线法**。

#### 发展脉络

- **1959 年，Davidon**：提出不需要真的算海森矩阵，用最近几步梯度变化估算曲率。
- **1970 年左右，BFGS**：四个人几乎同时得到同一类公式。BFGS 是四人名字首字母。
- **上世纪 80 年代，Nocedal**：L-BFGS，不存矩阵，只记最近 $m$ 次迭代的向量。

#### 应用

- sklearn 逻辑回归 `solver='lbfgs'`
- scipy `optimize.minimize(method='BFGS')`、`L-BFGS-B`
- 视觉与 SLAM 中的 Bundle Adjustment、相机标定：高斯牛顿 / Levenberg-Marquardt
- PyTorch `torch.optim.LBFGS`：适合参数不多、loss 光滑的小问题，不适合训练大模型

---

### 八、Adam：一阶矩与二阶矩的伪曲率

#### 为什么深度学习不用牛顿法

1. **存不起海森矩阵**。
2. **mini-batch 梯度有噪声**，二阶导数噪声更大、更敏感。
3. **神经网络中鞍点很多**，牛顿法会奔着驻点去，不管是不是极小值。
4. **非凸函数**，不可导点上没有正经二阶导。

#### Adam 的做法

- 用**一阶矩**和**二阶矩**（梯度平方）。
- 这里的二阶不是海森矩阵，而是梯度平方。
- 用一阶矩和二阶矩做**对角**、随机的**伪曲率**。
- 好处：**便宜**。

#### 2014 年，Kingma 和 Welling 发表 Adam

当参数规模到千万甚至 billion 级别后，Adam 解决了百万级和十亿级参数下的优化问题。连 L-BFGS 也进行了偏重。

深度学习又改回一阶：梯度加上动量，又加上按坐标自适应步长。

---

### 九、XGBoost：二阶泰勒展开的工程典范

#### GBDT 与 XGBoost

- **GBDT**：只用一阶导数（梯度）优化损失。
- **XGBoost**：最大升级是用**二阶泰勒展开**，同时使用一阶导 $g$ 和二阶导 $h$（海森矩阵的对角线元素）。

#### 公式

$$L^{(t)}\approx\sum_i\left[g_iw_i+\frac{1}{2}h_iw_i^2\right]+\Omega(f_t)$$

- $g_i$：损失函数在当前预测值处的一阶导数。
- $h_i$：二阶导数，海森矩阵的对角线元素。
- $w_i$：样本落在的叶子节点的权重。
- $\Omega(f_t)$：正则化项，惩罚树复杂度，防止过拟合。

#### 五大核心特点

1. **二阶泰勒损失**：收敛更快，对损失函数适配性更强，鲁棒性好，抗噪声。
2. **自带正则化**：限制树不要长太复杂，强力抑制过拟合。
3. **分裂节点的预排序或分箱**：工程加速，支持近似直方图分箱，海量数据训练更快。
4. **缺失值自动处理**：不需要人工处理。
5. **支持并行计算**：但**树的迭代是串行的**，必须一颗一颗加；**并行只发生在单棵树内部特征分裂**。

#### 应用

- 适合结构化表格数据，被誉为机器学习**入门模型**。
- 因子筛选、预测涨跌、风险评估。
- 做风控时先做时间序列分析、序列回撤，然后下分（降采样/分箱）。

#### LightGBM

XGBoost 的改进版：**直方图算法 + 按叶子生长（Leaf-wise）**，速度更快，精度略接近。

---




---

### 十、关键对比与选择

| 方法 | 核心 | 优点 | 局限 |
|------|------|------|------|
| 牛顿法 | 海森矩阵 | 二阶收敛，一步看到谷底 | 存储 $O(n^2)$，求逆 $O(n^3)$，鞍点问题 |
| 拟牛顿法 | 割线方程近似海森 | 不用真算海森，BFGS/L-BFGS | 仍依赖曲率估计 |
| Adam | 一阶矩 + 二阶矩 | 便宜，适合大模型 | 伪曲率，非精确 |
| XGBoost | 二阶泰勒 + 正则 | 表格数据极好，工程加速 | 非结构化数据不如深度学习 |

---

### 十一、作业与思考

1. **牛顿法为什么常常显得快？**
2. **L-BFGS 和 Adam 怎么选择？**
3. **什么是收敛半径？**
4. **高斯消元是什么？应用？**


见 [[MCS/day6/09 XGBoost、优化器选择与收敛邻域|XGBoost、优化器选择与收敛邻域]]

---

### 十二、一句话总结

> 牛顿法并未失败，而是问题的尺度换了。  
> 从精确牛顿，到拟牛顿，再到 Adam，是问题扩大以后不得已的选择，也是工具替换的必然。  
> 一阶方法有三件事做不好：学习率、病态、尺度。  
> 二阶方法看见曲率，但海森矩阵存不起、算不动。  
> 所以有了割线近似、L-BFGS、Adam，以及 XGBoost 的二阶泰勒展开。  
> 牛顿-康托洛维奇：局部二阶收敛，误差大约变为上次的平方，记 $e_{n+1}\approx e_n^2$，记 $10^{-3}\to 10^{-6}$。





## Adam 算是二阶优化方法吗？

**结论：不算。Adam 本质上是一阶优化方法。**

---

### 一、Adam 的核心公式

$$
m_t = \beta_1 m_{t-1} + (1-\beta_1) g_t
$$

$$
v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2
$$

$$
\hat{m}_t = \frac{m_t}{1-\beta_1^t}, \quad \hat{v}_t = \frac{v_t}{1-\beta_2^t}
$$

$$
\theta_{t+1} = \theta_t - \alpha \frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \epsilon}
$$

其中：

- $g_t$：一阶梯度
- $m_t$：梯度的一阶矩（均值）
- $v_t$：梯度的二阶矩（梯度平方的均值）
- 更新方向：$\hat{m}_t / \sqrt{\hat{v}_t}$

---

### 二、为什么 Adam 是一阶方法？

- 只用了**梯度本身**和**梯度的平方**
- **没有计算 Hessian**
- **没有用相邻梯度差估计曲率**
- $v_t$ 是梯度平方的滑动平均，**不是二阶导数，也不是曲率估计**

所以 Adam 属于：

> **一阶梯度法 + 自适应步长**

---

### 三、和真正二阶方法的对比

| 方法 | 用到的信息 | 是否二阶 |
|---|---|---|
| 梯度下降 | 一阶梯度 | 否 |
| Adam | 一阶梯度 + 梯度平方（自适应） | 否 |
| 牛顿法 | Hessian + 梯度 | 是 |
| 拟牛顿法（BFGS） | 梯度差估计曲率 | 是（近似二阶） |
| LM | Hessian + $\lambda I$ + 梯度 | 是 |
| Gauss-Newton | 近似 Hessian（$J^T J$）+ 梯度 | 是 |

---

### 四、为什么有人误以为 Adam 是二阶？

1. **名字里有“矩”**：一阶矩、二阶矩，听起来像二阶信息。但这里的“二阶矩”是**梯度平方的期望**，不是二阶导数。
2. **自适应学习率**：对不同参数用不同步长，效果上有点像二阶方法的“各方向缩放”，但它是**启发式**的，不是基于曲率。

---

### 五、一句话总结

**Adam 是一阶方法，不是二阶优化方法。**

它用梯度的一阶矩和二阶矩（梯度平方）做自适应步长，但没有 Hessian，也没有曲率估计。

真正二阶的是：牛顿法、拟牛顿法（BFGS）、LM、Gauss-Newton。


## 大规模深度学习 vs 牛顿法：优化器选择逻辑整理

### 一、核心结论

> 一阶方法赢在规模，二阶方法赢在精度和迭代次数，但规模一大就退场。

- 大规模深度学习（CNN、大模型）→ 普遍使用一阶优化器（SGD、Adam 及其变体）
- 牛顿法 / 拟牛顿法 → 属于二阶方法，在大规模深度学习中基本不用

---

### 二、大规模深度学习：为什么用一阶优化器？

常用优化器：

- SGD（随机梯度下降）及其动量变体
- Adam 及其改进版本（AdamW、Lion 等）
- 其他一阶自适应方法

选择原因：

- 参数量：GPT 级别 $10^9 \sim 10^{12}$ 参数，Hessian 为 $n \times n$，根本存不下
- 计算成本：求 Hessian、求逆、解线性方程组为 $O(n^3)$ 或至少 $O(n^2)$
- 损失面：高度非凸，二阶泰勒展开假设不成立
- 随机性：mini-batch 带来随机噪声，牛顿法不鲁棒
- 性价比：一阶方法每步便宜、可扩展、对随机性鲁棒，总体更划算

---

### 三、牛顿法 / 拟牛顿法：什么场景下会用？

1. 传统机器学习 / 凸优化问题
   - 逻辑回归、SVM 对偶问题、线性回归正则化求解等
   - 参数量不大（几千到几万维），Hessian 可存可算

2. 参数量较小的平滑优化问题
   - 维度 $n \le 10^3 \sim 10^4$ 时，计算和存储 $n \times n$ Hessian 及求解线性方程组仍可行

3. 需要高精度解、收敛快的场景
   - 牛顿法靠近最优解时是二次收敛，迭代次数很少
   - 问题规模小、但对精度和收敛速度要求高时使用

4. L-BFGS 在中等规模问题中的使用
   - 经典 NLP 任务（CRF、最大熵模型）、小规模神经网络、科学计算参数反演
   - 拟牛顿法，不需显式存 Hessian，但依然依赖二阶信息
   - 规模通常到 $10^5 \sim 10^6$ 参数就吃力

5. 二阶优化在深度学习中的例外
   - K-FAC、Shampoo、Sophia 等尝试
   - 本质是近似二阶信息，工程复杂、开销大
   - 未成为大模型训练主流，主流仍是 Adam + 改进

---

### 四、对比总结

| 维度 | 一阶方法（SGD / Adam） | 二阶方法（牛顿 / 拟牛顿） |
|------|------------------------|--------------------------|
| 代表方法 | SGD、Adam、AdamW | 牛顿法、BFGS、L-BFGS |
| 适用规模 | 大规模（$10^6 \sim 10^{12}$） | 小到中等规模（$\le 10^5 \sim 10^6$） |
| 每步成本 | 低 | 高（$O(n^2)$ 或 $O(n^3)$） |
| 收敛速度 | 慢（线性） | 快（二次，靠近最优解） |
| 对随机性 | 鲁棒 | 不鲁棒 |
| 非凸问题 | 适用 | 假设不成立 |
| 典型场景 | CNN、大模型训练 | 凸优化、传统 ML、小规模高精度问题 |

---

### 五、一句话记忆

> 大规模深度学习 → 一阶优化器（SGD/Adam）→ 完全不用牛顿法。
> 牛顿法/拟牛顿法 → 小规模、凸或平滑、高精度、参数量可控的传统优化问题。



**梯度 → 方向导数 → 负梯度方向 → 梯度下降法**

1. **梯度刻画局部变化**：梯度描述函数在某一点处局部变化率的方向与幅度。
    
2. **方向导数与梯度方向**：由方向导数的余弦表达式可知，当方向与梯度方向一致时，方向导数取极大值；当方向与梯度方向相反时，方向导数取极小值。
    
3. **负梯度方向下降最快**：因此，负梯度方向就是函数值局部下降速率最大的方向，也就是“下降最快”的方向。
    
4. **构造迭代格式**：梯度下降法正是据此构造迭代格式，让参数沿着负梯度方向更新，从而逐步减小函数值。
    
5. **一句话总结**：因为负梯度方向是局部下降最快的方向，所以梯度下降法要往反方向走。