ML1-6 梯度下降法与牛顿法

· 更新于 2026/8/20· Tech

机器学习CS229

0. 理想问题设定

最小化一个凸的、连续且可微的损失函数 ℓ(w)ℓ(w)（或者最大化似然函数）。
最终求出相应的 w^\hat{w} 。

算法框架：

  1. 初始化 w0\text{初始化 } \mathbf{w}_0
  2. 重复直到收敛:\text{重复直到收敛:} wt+1=wt+s\mathbf{w}^{t+1} = \mathbf{w}^t + \mathbf{s} （与\text{（与} ℓ(w)ℓ(w) 相关)\text{相关)}
  3. 若 ∥wt+1−wt∥2<ϵ，则已收敛（参数几乎不动）\text{若 } \|\mathbf{w}^{t+1} - \mathbf{w}^t\|_2 < \epsilon \text{，则已收敛（参数几乎不动）}

问题：如何选择这样的步长 s\mathbf{s} ?

1. 梯度下降法

梯度下降法是我们最常用的最优化方法。

其几个典型特性如下：

  • 当目标函数是凸函数时，梯度下降法的解是全局解
  • 一般情况下，其解不一定是全局最优解
  • 方法简单直观，但是可能需要大量迭代才会收敛

下面引用一段维基百科对梯度下降法的定义：

定义

梯度下降法（Gradient descent）是一种求解无约束最优化问题的一阶迭代最优化算法，它被用来求得可微函数的局部极小值，通常也称为最陡下降法。

  • 要使用梯度下降法找到一个函数的局部极小值，必须向函数上当前点对应梯度（或者是近似梯度）的反方向的规定步长距离点进行迭代搜索，因为这是最陡下降的方向。
  • 如果相反地向梯度正方向迭代进行搜索，则会接近函数的局部极大值点，这个过程则被称为梯度上升法。

上图展示了梯度下降的过程，其中

  • 蓝色的曲线是等高线
  • 红色箭头指向该点梯度的反方向
  • 从某个随机点出发，走向谷底，到达函数局部的极小值

1.1 公式参考

x(k+1)=x(k)−α∇xkf(x)x^{(k+1)} = x^{(k)} - \alpha \nabla_{x_k} f(x)

  • x(k+1)x^{(k+1)}：更新后的位置
  • x(k)x^{(k)}：更新前的位置
  • α\alpha：学习率
  • ∇xkf(x)\nabla_{x_k} f(x)：在 x(k)x^{(k)} 处对 ff 求梯度

即选取步长

s=−α∇xkf(x)\mathbf{s} = -\alpha \nabla_{x_k} f(x)

1.2 局限

  1. 学习率 α\alpha 的选取，对整个学习过程会产生很大的影响
    • 当 α\alpha 足够小时，梯度下降才会收敛，相应的速度会很慢
    • 当 α\alpha 太大时，算法很容易震荡发散，“之字型”抖动
  2. 靠近最优解的区域收敛速度将明显变慢

例如下式的二维函数，其参数为 x1,x2x_1, x_2：

f(x)=0.5(x12−x22)+0.5(x1−1)2f(x) = 0.5(x_1^2 - x_2^2) + 0.5(x_1 - 1)^2

下图展示了在固定学习率的情况下，两种不同的学习率分别迭代 20 次的结果，起始点 (x1,x2)=(0,0)(x1,x2)=(0,0) ，最小值点 (x1,x2)=(1,1)(x1,x2)=(1,1) 。

对于这些缺点，可以通过使用可变学习率的方法优化，如：

  • α=t0/tα = t_0 / t：随时间衰减的学习率
  • Adagrad 自适应学习率：梯度大的特征步长小，梯度小的特征步长大
  • 线性搜索：每次迭代前寻找最优的学习率，再进行迭代

1.3 常见用法

  1. 批量梯度下降法（Batch Gradient Descent，BGD）
    更新每一参数时都使用所有的样本来进行更新
  2. 随机梯度下降法（Stochastic Gradient Descent，SGD）
    在每次迭代时，只使用一个样本
  3. 批量梯度下降法（Mini-batch Gradient Descent，MBGD）
    更新每一参数时都使用一部分样本（batch）来进行更新，兼顾上述两方法

2. 牛顿法

前述梯度上升是一种非常有效的算法，但它在每次迭代时都需要小步，因此需要大量迭代才能收敛。

牛顿法（Newton's method）是一种在实数域和复数域上近似求解方程的方法。它是一种二阶优化算法。

牛顿法通常比梯度下降法收敛更早，并且迭代次数通常要少一个数量级。然而，在这种情况下，每次迭代的成本往往更高。

首先，考虑用于寻找函数零点的牛顿法。具体地，假设我们有一个函数 f:R↦Rf : \mathbb{R} \mapsto \mathbb{R} ，我们希望找到一个 θ\theta 使得 f(θ)=0f(\theta) = 0 。其中，θ∈R\theta \in \mathbb{R}。牛顿法执行以下更新：

θ:=θ−f(θ)f′(θ)\theta := \theta - \frac{f(\theta)}{f'(\theta)}

我们可以将其视为通过一个与 ff 在当前 θ\theta 处相切的线性函数来近似 ff，求解该线性函数的零点，并将下一个 θ\theta 值设为此线性函数的零点位置。

牛顿法给出了求解 f(θ)=0f(\theta) = 0 的方法，如何用它最大化似然函数呢？ℓ\ell 的最大值对应于其一阶导数 ℓ′(θ)\ell'(\theta) 为零的点(最小化函数也是同理)。因此，令 f(θ)=ℓ′(θ)f(\theta) = \ell'(\theta) ，我们可以使用相同的算法来最大化 ℓ\ell，即

θ:=θ−ℓ′(θ)ℓ′′(θ)\theta := \theta - \frac{\ell'(\theta)}{\ell''(\theta)}

2.1 公式参考

x(k+1)=x(k)−f′(x(k))f′′(x(k))x^{(k+1)} = x^{(k)} - \frac{f'(x^{(k)})}{f''(x^{(k)})}

  • x(k)x^{(k)}：第 kk 次迭代的位置
  • f′(x(k))f'(x^{(k)})：一阶导数（梯度）
  • f′′(x(k))f''(x^{(k)})：二阶导数（曲率）
  • x(k+1)x^{(k+1)}：更新后的新位置

即选取步长

s=−f′(x(k))f′′(x(k))\mathbf{s} = -\frac{f'(x^{(k)})}{f''(x^{(k)})}

2.2 二次收敛性

牛顿法具有称为二次收敛性的性质（quadratic convergence）。一般地，迭代算法产生序列 x(k)→x∗x^{(k)} → x^*，误差 ek=∣x(k)−x∗∣e_k = |x^{(k)} − x^*|。收敛速度描述误差怎么缩小，梯度下降法一般是线性收敛的，而牛顿法一般是二次收敛的。

给出一个二次收敛的非正式定义如下：

存在常数 M > 0，使得：

∣∣xk+1−x∗∣∣≤M⋅∣∣xk−x∗∣∣2||x_{k+1} − x^*|| ≤ M \cdot ||x_{k} − x^*||^2
可以见到，每次迭代，误差都被"平方压缩"。

  • 有效数字位数每步翻倍
  • 达到 ε 精度只需 log log(1/ε) 次迭代

设牛顿法在一次迭代中具有 0.01 误差。迭代之后，误差可以二次跳跃到 0.0001，并且在两次迭代之后，它可以进一步跳跃到 0.00000001。这就是牛顿法需要相对较少迭代的原因。

关于上述相关性质的证明，可以参见 UTSA Math — Newton's Method。

2.3 向量写法

在我们的逻辑回归设置中，θ\theta 是向量值，因此我们需要将牛顿法从单维情况推广到多维情况。牛顿法到多维设置的推广（也称为Newton-Raphson法）由下式给出：

θ:=θ−H−1∇θℓ(θ)\theta := \theta - H^{-1} \nabla_\theta \ell(\theta)

上式中

  • ∇θℓ(θ)\nabla_\theta \ell(\theta) 是 ℓ(θ)\ell(\theta) 对 θi\theta_i 的偏导数向量
  • HH 是一个 d×dd \times d 矩阵（如包含截距项则为 d+1d + 1），称为 Hessian 矩阵

此时，步长 s\mathbf{s} 即

s=−H−1∇θℓ(θ)\mathbf{s} = - H^{-1} \nabla_\theta \ell(\theta)

Hessian 矩阵定义为多变量函数中二阶偏导数的矩阵，其元素由下式给出

Hij=∂2ℓ(θ)∂θi∂θjH_{ij} = \frac{\partial^2 \ell(\theta)}{\partial \theta_i \partial \theta_j}

因此，Hessian 矩阵形如

H=(∂2f∂x12∂2f∂x1∂x2⋯∂2f∂x1∂xn∂2f∂x2∂x1∂2f∂x22⋯∂2f∂x2∂xn⋮⋮⋱⋮∂2f∂xn∂x1∂2f∂xn∂x2⋯∂2f∂xn2)H = \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\[6pt] \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\[6pt] \vdots & \vdots & \ddots & \vdots \\[6pt] \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{pmatrix}

牛顿法通常比批量梯度下降收敛更快，并且需要更少的迭代次数就能非常接近最小值。
然而，牛顿法的一次迭代可能比梯度下降的一次迭代更昂贵，因为它需要找到并求逆一个 Hessian 矩阵；但只要 dd 不是太大，总体上通常要快得多。

当牛顿法应用于最大化逻辑回归的对数似然函数 ℓ(θ)\ell(\theta) 时，得到的方法也称为 Fisher 得分。

3. 泰勒展开视角

通过假设损失函数 ℓ(θ)\ell(\theta) 比我们料想的要简单的多（在某点附近），可以预估函数的走势以优化。这可以通过泰勒近似实现：只要步长范数 ∣∣s∣∣2||\mathbf{s}||_2 很小（即 w+s\mathbf{w} + \mathbf{s} 非常接近 w\mathbf{w} ），我们就可以用一阶和二阶导数近似函数 ℓ(w+s)\ell(\mathbf{w} + \mathbf{s})：

一阶展开：ℓ(w+s)≈ℓ(w)+g(w)⊤s\ell(\mathbf{w} + \mathbf{s}) \approx \ell(\mathbf{w}) + g(\mathbf{w})^\top \mathbf{s}

二阶展开：ℓ(w+s)≈ℓ(w)+g(w)⊤s+12s⊤H(w)s\ell(\mathbf{w} + \mathbf{s}) \approx \ell(\mathbf{w}) + g(\mathbf{w})^\top \mathbf{s} + \frac{1}{2} \mathbf{s}^\top H(\mathbf{w}) \mathbf{s}

其中，

  • g(w)=∇ℓ(w)g(\mathbf{w}) = ∇ℓ(\mathbf{w}) 是梯度（一阶导数）
  • H(w)=∇2ℓ(w)H(\mathbf{w}) = ∇^2\ell(\mathbf{w}) 是 Hessian 矩阵（二阶导数）

上述两种近似在 ∣∣s∣∣2||\mathbf{s}||_2 很小均成立。

3.1 梯度下降与一阶近似

在梯度下降中我们只用梯度（一阶），即：我们假设 ℓ\ell 在 w\mathbf{w} 附近是线性的，其行为类似于 ℓ(w)+g(w)⊤s\ell(\mathbf{w}) + g(\mathbf{w})^\top \mathbf{s} 。

在最速下降（steepest descent）中，我们直接设：

s=−αg(w),α>0 很小\mathbf{s} = -\alpha g(\mathbf{w}), \quad \alpha > 0 \text{ 很小}

可以很简单地证明此时 ℓ(w+s)<ℓ(w)\ell(\mathbf{w} + \mathbf{s}) \lt \ell(\mathbf{w}) ：

ℓ(w+(−αg(w)))≈ℓ(w)−αg(w)Tg(w)⏟>0<ℓ(w)\ell(\mathbf{w} + (-\alpha g(\mathbf{w}))) \approx \ell(\mathbf{w}) - \alpha \underbrace{g(\mathbf{w})^T g(\mathbf{w})}_{>0} < \ell(\mathbf{w})

3.2 牛顿法与二阶近似

在牛顿法中我们使用的是二阶近似：

ℓ(w+s)≈ℓ(w)+g(w)⊤s+12s⊤H(w)s\ell(\mathbf{w} + \mathbf{s}) \approx \ell(\mathbf{w}) + g(\mathbf{w})^\top \mathbf{s} + \frac{1}{2} \mathbf{s}^\top H(\mathbf{w}) \mathbf{s}

上式在 w\mathbf{w} 附近将 ℓ\ell 近似为一个凸抛物线，我们可以通过求解以下优化问题找到它的最小值：

arg⁡min⁡sℓ(w)+g(w)⊤s+12s⊤H(w)s\arg\min_{\mathbf{s}} \ell(\mathbf{w}) + g(\mathbf{w})^\top \mathbf{s} + \frac{1}{2} \mathbf{s}^\top H(\mathbf{w}) \mathbf{s}
为了找到目标的最小值，我们对 s\mathbf{s} 求一阶导数、令其为零并解出 s\mathbf{s}：

g(w)+H(w)s=0⇒s=−[H(w)]−1g(w)g(\mathbf{w}) + H(\mathbf{w})\mathbf{s} = 0 \quad \Rightarrow \quad \mathbf{s} = -[H(\mathbf{w})]^{-1}g(\mathbf{w})

注意

如果近似足够精确且所得步长足够小，牛顿法的收敛速度一般是非常快的。但是，当函数在某个维度上（几乎）平坦时，其二阶导数接近于零，则其倒数将变得非常大，进而导致巨大的步长。与梯度下降不同，这里不能够保证步长受控。由于泰勒近似仅在局部区域精确，大步长可能使当前估计值远离泰勒近似有效的区域，最终导致发散。

上图展示了同一函数上的梯度下降步（左）和牛顿步（右）。损失函数以黑色表示，近似用红色虚线表示。

  • 梯度步沿函数的线性近似将点向下移动
  • 牛顿步将点移动到用于近似函数的抛物线的极小值处

参考

  1. https://cs229.stanford.edu/main_notes.pdf
  2. https://aman.ai/cs229/newton-method/
  3. 梯度下降法-维基百科
  4. 牛顿法-维基百科

  5. Gradient Descent (and Beyond)

    https://www.cs.cornell.edu/courses/cs4780/2018fa/lectures/lecturenote07.html

  6. 常见的几种最优化方法（梯度下降法、牛顿法、拟牛顿法、共轭梯度法等）

  7. 最优化算法 — Machine Learning From Scratch 0.1 文档

    https://machine-learning-from-scratch.readthedocs.io/zh-cn/latest/%E6%9C%80%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95.html#id3

  8. UTSA Math — Newton's Method
cicada@blog:~
$ cat series/prev→ML1-5 感知机$ cat series/next→ML1-7 指数族

本作品采用 CC BY-NC-SA 4.0 许可协议

转载或引用请注明出处