Newton 法与拟 Newton 法

层级：B｜按需

1. 一阶方法看坡度，二阶方法还看曲率

梯度下降对所有方向用同一个学习率；若损失谷地各方向曲率差异大，速度慢。Newton 法用 Hessian 调整每个方向的步长，在局部二次模型准确时可极快收敛。

2. 从求根推导一元 Newton 法

要解 $g(x)=0$ ，用切线近似：

g(x+\Delta)\approx g(x)+g'(x)\Delta=0.

所以

x_{t+1}=x_t-\frac{g(x_t)}{g'(x_t)}.

最小化 $f$ 时令 $g=f'$ ：

x_{t+1}=x_t-\frac{f'(x_t)}{f''(x_t)}.

3. 多元 Newton 步

二阶 Taylor 模型：

m(\Delta)=f(x)+g^T\Delta+\frac12\Delta^TH\Delta.

令模型梯度为零：

H\Delta=-g.

解线性系统得 Newton 方向，再更新

x_{t+1}=x_t+\alpha_t\Delta.

纯 Newton 用 $\alpha_t=1$ ；全局化版本用线搜索或信赖域。

4. 为何能纠正尺度

在 Hessian 特征方向 $q_i$ ：

\Delta_i=-\frac{g_i}{\lambda_i}.

曲率大的方向缩小步长，曲率小的方向放大。对严格凸二次函数，Newton 一步到达最优点，与条件数无关（忽略求解误差）。

5. 局部二次收敛

在最优点附近、Hessian 正定且足够光滑等条件下：

\|x_{t+1}-x^*\| \le C\|x_t-x^*\|^2.

误差大致平方，正确位数快速翻倍。但这是局部性质，初始点太远时可能失败。

6. 非凸与奇异问题

Hessian 不定：Newton 方向可能是上升方向；
Hessian 奇异/近奇异：线性系统无唯一稳定解；
远离最优：二次近似不准确；
高维：存储 $O(p^2)$ 、直接求解 $O(p^3)$ 不可承受。

常用修正：

(H+\lambda I)\Delta=-g,

选择足够大 $\lambda$ 使矩阵正定；或使用信赖域限制 $\|\Delta\|$ 。

7. 阻尼 Newton 与线搜索

先求 Newton 方向，若 $g^T\Delta<0$ 是下降方向，再用回溯选择 $\alpha\in(0,1]$ 满足充分下降。靠近最优点时通常接受全步 $\alpha=1$ ，恢复快速收敛。

若方向非下降，可修改 Hessian、使用负梯度或信赖域。

8. 拟 Newton 思想

不直接算 Hessian，而从相邻迭代的参数与梯度变化近似逆 Hessian或 Hessian。记

s_t=x_{t+1}-x_t, \qquad y_t=g_{t+1}-g_t.

希望近似矩阵满足割线条件

B_{t+1}s_t=y_t

（若 $B$ 近似 Hessian），模拟 $H\Delta g$ 的关系。

9. BFGS

BFGS 通过秩二更新维护正定 Hessian 近似或逆近似。若

y_t^Ts_t>0,

并从正定矩阵开始，更新保持正定，产生下降方向。它在中等维度光滑确定性优化中非常有效。

不必死记完整更新式，重点是：利用梯度差估曲率、满足割线条件、避免显式二阶导。

10. L-BFGS

BFGS 存储 $p\times p$ 矩阵，参数大时昂贵。L-BFGS 只保留最近 $m$ 对 $(s_t,y_t)$ ，通过两层循环递推计算方向，内存约 $O(mp)$ 。

它适合：

全量或低噪声梯度；
光滑目标；
中大规模参数但可承受多次函数/梯度评估。

小批量噪声会让曲率差分不可靠，需随机拟 Newton 变体或更大 batch。

11. 共轭梯度与 Hessian–vector product

Newton 系统

H\Delta=-g

可用共轭梯度迭代求近似解，只需计算 $Hv$ ，不存 Hessian。若 $H$ 正定，这形成 truncated Newton/Newton-CG。自动微分可高效计算 HVP。

12. Logistic 回归中的 Hessian

负对数似然梯度与 Hessian：

g=X^T(p-y),

H=X^TWX,

$W$ 对角元素 $p_i(1-p_i)\ge0$ ，所以 Hessian PSD。Newton/IRLS 可高效训练中等规模逻辑回归；正则化提高正定性。

易错点

实现 Newton 步应解 $H\Delta=-g$ ，不显式求 $H^{-1}$ 。
非凸 Hessian 不定时 Newton 方向未必下降。
二次收敛是局部且有条件的。
L-BFGS 对高噪声 mini-batch 未必合适。
二阶方法每步贵，评价应看总时间而非步数。

常见问答

Q1：Newton 法没有学习率吗？

纯局部形式用全步，但稳健实现通常有阻尼、线搜索或信赖域半径，相当于控制步长。

Q2：拟 Newton 是二阶方法吗？

它使用梯度差隐式估计曲率，通常归入准二阶方法，不需要显式 Hessian。

Q3：深度学习能用 Newton 法吗？

完整 Newton 很少，但 Hessian-free、K-FAC、自然梯度、Shampoo 等利用曲率结构或近似。大规模一阶方法仍更普遍。

练习

对 $f(x)=\frac12a(x-b)^2$ 做一次 Newton 更新。
多元 Newton 步为何是解线性系统？
Hessian 有负特征值时 Newton 方向可能怎样？
L-BFGS 相比 BFGS 节省了什么？
Logistic Hessian 为什么 PSD？

答案与提示

$f'=a(x-b),f''=a$ ，一步到 $b$ 。
二次模型一阶条件为 $H\Delta=-g$ 。
可能沿负曲率方向上升或趋向最大点。
不存完整 $p\times p$ 矩阵，只存少量向量对。
$v^TX^TWXv=(Xv)^TW(Xv)\ge0$ 。