牛顿法 vs 梯度下降

牛顿法利用二阶信息,在当前点 $w$ 做二阶泰勒展开 $f(w + \Delta w) \approx f(w) + \nabla f^T\Delta w + \frac{1}{2}\Delta w^T H\Delta w$(H 为 Hessian),对 $\Delta w$ 求导并置零: $\nabla f + H\Delta w = 0$,得到牛顿步 $\Delta w = -H^{-1}\nabla f$。几何本质是“拟合一个二次曲面并一步走到其顶点”: 对二次函数恰一步到位;对一般光滑函数局部二次收敛——误差按平方衰减 $\Vert w_{k+1} - w^*\Vert \le C\Vert w_k - w^*\Vert^2$,有效数字每步翻倍(从 $10^{-3}$ 到 $10^{-6}$ 再到 $10^{-12}$),而梯度下降只是线性收敛 $(1 - 1/\kappa)^t$。

面试必考与梯度下降的对比,经典病态例题: $f(x,y) = x^2 + 100y^2$。Hessian $H = \mathrm{diag}(2, 200)$,条件数 $\kappa = 200/2 = 100$。GD 沿陡峭的 $y$ 方向来回震荡,约需 $O(\kappa)$ 次迭代才收敛;牛顿法 $H^{-1}\nabla f = (x, y)^T$ 直接做“坐标变换”消除尺度差,一步到达原点 $(0,0)$。

一阶方法的收敛率被条件数支配($\kappa$ 越大越慢),牛顿法用 $H^{-1}$ 对空间各向同性化,对病态问题一步收敛;代价是每步求解线性方程组 $O(D^3)$、存储 Hessian 需 $O(D^2)$ 内存,高维深度网络不可行 → 实际用近似: L-BFGS($O(D)$ 内存、历史梯度近似逆 Hessian)、Gauss-Newton(最小二乘中 $H \approx J^TJ$,用 $J^TJ + \lambda I$ 保证可逆)。非凸函数 Hessian 可能非正定,牛顿方向不再是下降方向,需阻尼牛顿或加正则 $H + \lambda I$(Levenberg-Marquardt)。

从二阶泰勒展开推导牛顿步 $\Delta w = -H^{-1}\nabla f$(写出对 $\Delta w$ 求导置零的完整步骤)。

为什么牛顿法对二次函数一步收敛、对一般函数二次收敛?给出收敛阶定义 $\Vert w_{k+1}-w^*\Vert \le C\Vert w_k-w^*\Vert^2$ 的含义。

病态例题 $f = x^2 + 100y^2$:分别估计 GD($\kappa=100$)与牛顿法各需多少步收敛,并解释牛顿法一步到位的机理。

牛顿法的计算代价($O(D^3)$/步、$O(D^2)$ 内存)是多少?L-BFGS 与 Gauss-Newton 分别如何近似 Hessian?

非凸函数 Hessian 可能非正定,牛顿方向为何不再可靠?阻尼牛顿 / $H + \lambda I$(Levenberg-Marquardt)如何修复?