优化基础

学习目标

理解优化的基本概念，理解目标函数、梯度等核心概念
掌握梯度下降法的原理、实现和收敛性分析
了解随机梯度下降法及其在大规模机器学习中的应用
熟悉 Momentum、Adam、RMSprop 等高级优化算法
理解约束优化问题，掌握 Lagrange 乘数法和 KKT 条件

引言

优化（Optimization）是数学的一个核心分支，也是机器学习和人工智能最重要的技术基础之一。在机器学习中，"学习"本质上就是一个优化过程：我们定义一个目标函数（通常称为损失函数或代价函数），然后寻找使这个目标函数最小化（或最大化）的模型参数。

例如，在线性回归中，我们希望找到一条直线，使得预测值与真实值之间的均方误差最小；在逻辑回归中，我们最大化似然函数来学习分类边界；在神经网络中，我们通过反向传播算法计算梯度，然后使用梯度下降法来更新权重，从而最小化交叉熵损失或其他损失函数。

可以说，没有优化算法，就没有现代机器学习和深度学习。本章将系统介绍优化理论的基础知识，从最简单的梯度下降法开始，逐步深入到随机梯度下降、动量法、Adam 等高级优化算法，最后介绍约束优化问题及其解决方法。

理解优化的数学原理对于设计新算法、诊断训练问题（如梯度消失、梯度爆炸）、选择合适的优化策略等都至关重要。

1 优化基础

1.1 优化问题的定义

优化问题（Optimization Problem） 的一般形式是：

\[\min_{x \in \mathbb{R}^n} f(x)\]

或者更一般地：

\[\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad g_i(x) \leq 0, \quad i = 1, \ldots, m\]

其中：

$f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是目标函数（Objective Function） 或损失函数（Loss Function）
$g_i(x) \leq 0$ 是不等式约束（Inequality Constraint）
如果还有等式约束 $h_j(x) = 0$，则构成更一般的约束优化问题

在机器学习中，优化问题通常没有约束（或约束非常简单），因此无约束优化是最常见的形式。我们将在本章最后一节专门讨论约束优化。

最小化与最大化：由于 $\max f(x) = -\min(-f(x))$，最小化和最大化问题是等价的。在机器学习中，我们通常习惯于最小化损失函数，因此本书主要讨论最小化问题。

1.2 优化问题的分类

优化问题可以从多个角度进行分类：

根据目标函数的性质：

线性规划（Linear Programming）：目标函数和约束都是线性的
二次规划（Quadratic Programming）：目标函数是二次的，约束是线性的
非线性规划（Nonlinear Programming）：目标函数或约束是非线性的

根据约束情况：

无约束优化（Unconstrained Optimization）：没有约束条件
约束优化（Constrained Optimization）：有约束条件

根据目标函数的凸性：

凸优化（Convex Optimization）：目标函数是凸函数
非凸优化（Non-convex Optimization）：目标函数是非凸函数

这种分类非常重要。凸优化问题具有很好的性质：任何局部最优解都是全局最优解。而非凸优化问题可能存在多个局部最优解，找到全局最优解通常很困难。深度学习中的优化问题大多是非凸的，这是一个具有挑战性但又必须面对的问题。

1.3 梯度与海森矩阵

梯度（Gradient） 是多元函数导数的推广。设函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$，则梯度定义为：

\[\nabla f(x) = \begin{bmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \vdots \\ \frac{\partial f}{\partial x_n} \end{bmatrix}\]

梯度是一个向量，指向函数值增长最快的方向。在优化中，我们通常使用梯度的反方向（负梯度）来下降。

海森矩阵（Hessian Matrix） 是梯度的雅可比矩阵，定义为：

\[H(x) = \nabla^2 f(x) = \begin{bmatrix} \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} \\ \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} \\ \vdots & \vdots & \ddots & \vdots \\ \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{bmatrix}\]

海森矩阵是目标函数的二阶导数，描述了函数的曲率信息。在牛頓法等二阶优化算法中，海森矩阵起着核心作用。

泰勒展开：函数在某点附近的局部行为可以用泰勒级数来近似：

\[f(x + \Delta x) \approx f(x) + \nabla f(x)^\top \Delta x + \frac{1}{2} \Delta x^\top H(x) \Delta x + O(\|\Delta x\|^3)\]

这个展开式是许多优化算法推导的基础。

1.4 局部最优与全局最优

局部最优（Local Optimum）：如果存在 ε > 0，使得对于所有满足 $\|x - x^*\| < \epsilon$ 的 x，都有 $f(x) \geq f(x^*)$，则称 $x^*$ 是 f 的一个局部最小值点。

全局最优（Global Optimum）：如果对于所有 $x \in \mathbb{R}^n$，都有 $f(x) \geq f(x^*)$，则称 $x^*$ 是 f 的全局最小值点。

对于凸函数，局部最优就是全局最优。但对于非凸函数（如深度神经网络的目标函数），可能存在多个局部最优解，这些局部最优解的性质可能差异很大。

在深度学习中，损失函数 landscape（损失 landscape，即损失函数在参数空间中的形状）非常复杂，充满了鞍点（saddle points）和局部最优。理解这些性质对于理解为什么深度学习能够成功至关重要——研究表明，在高维空间中，局部最优可能并不像我们想象的那么可怕，很多局部最优的函数值接近全局最优，而真正的问题可能是鞍点。

1.5 优化算法概述

优化算法可以大致分为以下几类：

一阶方法（First-order Methods）：只使用梯度（一阶导数）信息。代表算法：梯度下降法、随机梯度下降法。

二阶方法（Second-order Methods）：使用梯度信息和海森矩阵（或其近似）。代表算法：牛頓法、拟牛頓法（如 L-BFGS）。

自适应方法（Adaptive Methods）：自动调整学习率等超参数。代表算法：AdaGrad、RMSprop、Adam。

零阶方法（Zero-order Methods）：不使用梯度信息，只使用函数值。代表算法：网格搜索、贝叶斯优化、进化算法。

在实际应用中，梯度下降法及其变体是机器学习中使用最广泛的优化算法，原因在于：

计算效率高：每次迭代只需要计算梯度
易于实现：算法逻辑清晰
可扩展性强：可以处理大规模数据和高维参数
收敛性有理论保证（在适当条件下）

2 梯度下降法

2.1 梯度下降法的原理

梯度下降法（Gradient Descent） 是最基本、最广泛使用的优化算法之一。其核心思想来自一个直观的观察：沿函数梯度的反方向移动，函数值会下降。

给定当前点 $x^{(t)}$，梯度下降法的更新规则为：

\[x^{(t+1)} = x^{(t)} - \alpha \nabla f(x^{(t)})\]

其中 $\alpha > 0$ 是学习率（Learning Rate） 或步长（Step Size），控制每一步移动的距离。

几何解释：梯度 $\nabla f(x)$ 指向函数增长最快的方向，因此负梯度 $-\nabla f(x)$ 指向函数下降最快的方向。梯度下降法就是沿着这个方向迈一小步，然后重新计算梯度，重复这个过程。

一维示例：考虑函数 $f(x) = x^2$。梯度为 $\nabla f(x) = 2x$。如果当前点在 $x^{(t)} = 2$，梯度为 4，负梯度方向是 -4。更新后 $x^{(t+1)} = 2 - \alpha \cdot 4 = 2 - 4\alpha$。如果选择 $\alpha = 0.1$，则 $x^{(t+1)} = 2 - 0.4 = 1.6$，函数值从 $f(2) = 4$ 下降到 $f(1.6) = 2.56$，确实下降了。

泰勒展开解释：由泰勒展开：

\[f(x^{(t+1)}) \approx f(x^{(t)}) + \nabla f(x^{(t)})^\top (x^{(t+1)} - x^{(t)}) = f(x^{(t)}) - \alpha \|\nabla f(x^{(t)})\|^2\]

只要 $\alpha > 0$，函数值必然下降（近似意义上）。

2.2 收敛性分析

梯度下降法的收敛性取决于多个因素，包括目标函数的性质和学习率的选择。

凸函数的情况：对于凸函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$，如果梯度是 Lipschitz 连续的（ Lipschitz 常数为 L），即：

\[\|\nabla f(x) - \nabla f(y)\| \leq L \|x - y\|, \quad \forall x, y\]

并且学习率满足 $\alpha \leq 1/L$，则梯度下降法具有线性收敛速度：

\[\|x^{(t)} - x^*\|^2 \leq \left(1 - \frac{\mu}{L}\right)^t \|x^{(0)} - x^*\|^2\]

其中 $\mu$ 是函数的强凸参数（strongly convex parameter），$x^*$ 是全局最优解。

Lipschitz 连续梯度是一个常见且合理的假设。它保证函数变化不会太快，梯度不会剧烈波动。

收敛速度分类：

线性收敛（Linear Convergence）：误差以几何级数减少，收敛速度用收敛率衡量
次线性收敛（Sublinear Convergence）：收敛越来越慢，如 $O(1/t)$
超线性收敛（Superlinear Convergence）：收敛越来越快，如 $O(1/t^2)$（牛頓法）

对于一般非凸函数，梯度下降法只能保证收敛到驻点（stationary point，即梯度为零的点），但不能保证收敛到全局甚至局部最优。在深度学习中，实际发现梯度下降法通常能够找到不错的局部最优解（如果存在的话）。

2.3 学习率的影响

学习率是梯度下降法最重要的超参数，它直接影响算法的收敛性和稳定性。

学习率过大的问题：

震荡：参数在极小值附近来回跳动，无法收敛
发散：函数值不降反升，完全无法收敛
越过极小值：可能越过局部最优或鞍点

学习率过小的问题：

收敛缓慢：需要大量迭代才能接近最优解
容易陷入局部最优：探索能力不足
效率低下：计算资源和时间浪费

学习率选择的艺术：在实际应用中，学习率通常需要通过实验来调整。常见策略包括：

固定学习率：简单但可能不是最优的
学习率衰减（Learning Rate Decay）：随着训练进行逐渐减小学习率
学习率调度（Learning Rate Scheduling）：根据预设策略动态调整学习率

2.4 学习率衰减策略

学习率衰减（Learning Rate Decay） 是一种经验上有效且广泛使用的策略，它允许算法在训练初期快速探索，在后期精细调整。

常见的衰减策略包括：

步衰减（Step Decay）：每隔固定 epoch 数将学习率乘以一个因子（如 0.5）：

\[\alpha_t = \alpha_0 \cdot \gamma^{\lfloor t / T \rfloor}\]

其中 $\gamma$ 是衰减率（通常为 0.5 或 0.9），T 是衰减周期。

指数衰减（Exponential Decay）：

\[\alpha_t = \alpha_0 \cdot e^{-\gamma t}\]

余弦衰减（Cosine Decay）：学习率按余弦函数曲线衰减：

\[\alpha_t = \alpha_0 \cdot \frac{1 + \cos(\pi t / T)}{2}\]

余弦衰减在深度学习中有广泛应用，PyTorch 的 CosineAnnealingLR 等调度器实现了这种策略。

线性热身（Linear Warmup）：在训练初期逐渐增大学习率，然后再衰减：

\[\alpha_t = \begin{cases} \alpha_0 \cdot t / T_w & \text{if } t < T_w \\ \text{按策略衰减} & \text{if } t \geq T_w \end{cases}\]

热身策略有助于训练初期参数的稳定性，防止因参数初始化不当导致的大梯度。

2.5 批量梯度下降、随机梯度下降与小批量梯度下降

根据每次迭代使用的样本数量，梯度下降法可以分为三种形式：

批量梯度下降（Batch Gradient Descent，BGD）：每次迭代使用全部训练样本计算梯度：

\[x^{(t+1)} = x^{(t)} - \alpha \frac{1}{n} \sum_{i=1}^{n} \nabla f_i(x^{(t)})\]

其中 n 是训练样本总数。

优点：梯度估计准确，收敛稳定
缺点：每次迭代计算量大，不适合大规模数据；容易陷入局部最优（泛化能力可能受限）

随机梯度下降（Stochastic Gradient Descent，SGD）：每次迭代只使用一个样本计算梯度：

\[x^{(t+1)} = x^{(t)} - \alpha \nabla f_i(x^{(t)})\]

其中 i 是随机选择的一个样本。

优点：每次迭代计算量小，可以逃离局部最优
缺点：梯度估计噪声大，收敛不稳定，可能在极小值附近震荡

小批量梯度下降（Mini-batch Gradient Descent）：每次迭代使用一小批（batch）样本计算梯度：

\[x^{(t+1)} = x^{(t)} - \alpha \frac{1}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \nabla f_i(x^{(t)})\]

其中 $\mathcal{B}$ 是大小为 b 的小批量。

这是深度学习中最常用的形式，它结合了批量梯度下降的稳定性和随机梯度下降的效率。小批量大小（batch size）是一个重要超参数，通常在 32 到 256 之间选择。

小批量梯度下降的理论解释：使用小批量而非单个样本，可以获得更准确的梯度估计，减少噪声；而与全量数据相比，小批量计算更快，允许更多参数更新。适当大小的批量可以利用并行计算（如 GPU）的效率，同时保持足够的随机性来逃离局部最优。

3 随机梯度下降

3.1 随机梯度下降的原理

随机梯度下降（SGD） 是机器学习最重要的优化算法之一，尤其在大规模机器学习中扮演核心角色。其基本思想是用单个样本（或小批量样本）的梯度来近似整体梯度，从而大大降低每次迭代的计算量。

在机器学习中，目标函数通常可以写成经验风险的形式：

\[L(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(x_i, y_i, \theta)\]

其中 $\ell$ 是单个样本的损失，n 是样本数量。

计算 $\nabla L(\theta)$ 需要遍历所有 n 个样本，当 n 非常大时（如 ImageNet 有上百万张图片），这变得不可接受。随机梯度下降用单个样本 $i_t$ 的梯度 $\nabla \ell(x_{i_t}, y_{i_t}, \theta)$ 来近似整体梯度：

\[\theta^{(t+1)} = \theta^{(t)} - \alpha \nabla \ell(x_{i_t}, y_{i_t}, \theta^{(t)})\]

3.2 随机梯度的统计性质

随机梯度是真实梯度的无偏估计：

\[E[\nabla \ell(x_{i_t}, y_{i_t}, \theta)] = \nabla L(\theta)\]

这是因为每个样本被选中的概率相等，期望等于整体平均。

然而，随机梯度有方差（variance）：

\[\text{Var}(\nabla \ell(x_i, y_i, \theta)) = \sigma^2\]

这个方差导致随机梯度下降的收敛路径是曲折的，而不是平滑地直奔极小值。

方差与收敛的关系：在优化后期，当参数接近最优解时，梯度的模长趋近于零，但随机梯度的方差可能仍然较大，导致参数在最优解附近震荡。这就是为什么在训练后期需要降低学习率或使用方差缩减技术。

3.3 收敛性分析

随机梯度下降的收敛性分析比批量梯度下降更复杂，主要使用随机优化的分析工具。

基本假设：

目标函数 $L(\theta)$ 是凸的（或满足其他正则条件）
随机梯度是真实梯度的无偏估计
梯度的二阶矩（variance）有界：$E[\|\nabla \ell(x_i, y_i, \theta)\|^2] \leq G^2$

收敛率：在适当的学习率调度下（如学习率递减），随机梯度下降可以收敛到全局最优，收敛率为 $O(1/\sqrt{T})$，其中 T 是迭代次数。

与批量梯度下降的比较：批量梯度下降的收敛率是 $O(1/T)$（线性收敛），比随机梯度下降快。但批量梯度下降每次迭代的成本是 $O(n)$，而随机梯度下降是 $O(1)$。综合考虑计算成本，对于大规模问题，随机梯度下降往往更有效。

非凸情况：在深度学习中，目标函数是非凸的。理论研究表明，在适当的条件下（如学习率满足 $\sum \alpha_t = \infty$ 和 $\sum \alpha_t^2 < \infty$），随机梯度下降可以收敛到驻点（梯度为零的点）。实践中，随机梯度下降通常能够找到不错的局部最优或鞍点。

3.4 随机梯度下降在深度学习中的应用

随机梯度下降及其变体是深度学习训练的基础。几乎所有深度学习框架（如 PyTorch、TensorFlow）都内置了 SGD 优化器。

批量大小的影响：在深度学习中，批量大小是一个重要超参数，它影响训练动态和最终性能：

大批量（≥ 512）：梯度估计更准确，训练更稳定，但泛化性能可能下降（sharp minima 问题）；需要更大的学习率
小批量（32-128）：梯度有噪声，有助于逃离局部最优和鞍点，泛化性能通常更好；需要较小的学习率

学习率与批量大小的关系：研究表明，学习率应该与批量大小成比例，即大批量使用更大的学习率。Linear Scaling Rule 指出，当批量大小增加 k 倍时，学习率也应该增加 k 倍（需要足够的 warm-up）。

3.5 梯度裁剪

梯度裁剪（Gradient Clipping） 是一种防止梯度爆炸的技术，特别适用于训练循环神经网络（RNN）等容易出现梯度爆炸的模型。

梯度裁剪的公式：

\[g \leftarrow g \cdot \min\left(1, \frac{c}{\|g\|}\right)\]

或者按范数裁剪：

\[\text{if } \|g\| > c: \quad g \leftarrow \frac{c}{\|g\|} \cdot g\]

其中 c 是阈值（通常为 1-5），g 是梯度。

何时使用：当梯度范数超过阈值时进行裁剪。这可以防止参数更新过大，避免数值不稳定。梯度裁剪在训练 RNN、Transformer 等模型时几乎是必不可少的。

4 高级优化算法

4.1 Momentum

4.1.1 动量法的原理

动量法（Momentum） 是最古老且最有效的优化算法加速技术之一，由 Polyak 在 1964 年提出。其核心思想是模拟物理中动量的概念，让参数更新具有一定的惯性。

标准 SGD 的更新规则是：

\[v^{(t+1)} = \alpha \nabla f(x^{(t)})$$ $$x^{(t+1)} = x^{(t)} - v^{(t+1)}\]

动量法的更新规则是：

\[v^{(t+1)} = \beta v^{(t)} + \alpha \nabla f(x^{(t)})$$ $$x^{(t+1)} = x^{(t)} - v^{(t+1)}\]

其中 $v^{(t)}$ 是速度（velocity），$\beta \in [0, 1)$ 是动量系数（通常取 0.9 或 0.99）。

物理直观：动量法可以理解为一个小球在损失函数曲面上滚动。由于具有动量，小球不会在第一个平坦点就停下来，而是会继续滚动，积累更大的动量，从而能够翻过小丘，逃离浅的局部最优。同时，当曲面下凹时，动量帮助小球加速前进。

等效形式：动量法还有另一种等效的表达形式：

\[x^{(t+1)} = x^{(t)} - \alpha \nabla f(x^{(t)}) + \beta (x^{(t)} - x^{(t-1)})\]

这表明当前更新方向是当前梯度和上一步更新的组合。

4.1.2 动量法的收敛性

动量法的收敛性分析比标准 SGD 更复杂。在凸函数情况下，动量法可以加速收敛。

收敛速度：对于凸函数，动量法可以达到 $O(1/t)$ 的收敛率（与批量梯度下降相同），但实际收敛速度更快，尤其是对于 ill-conditioned（条件数较大）的函数。

Condition Number 的影响：函数的 condition number（条件数）定义为最大曲率与最小曲率之比。当 condition number 很大时（即函数在不同方向上曲率差异很大），标准梯度下降会走"之"字形路线，收敛缓慢。动量法通过累积历史更新方向，帮助平滑这些振荡，加速收敛。

4.1.3 动量法在深度学习中的应用

在深度学习中，动量法几乎是训练神经网络的标配。它被内置于所有主流深度学习框架的优化器中（如 PyTorch 的 SGD with momentum）。

学习率与动量的关系：

较大的动量系数（β → 1）允许更大的有效学习率
当 β = 0.99 时，有效学习率可以高达单步学习率的 100 倍
但过大的动量可能导致不稳定

Nesterov 动量：Nesterov 动量是动量法的一个变体，它使用"前瞻"梯度来计算更新：

\[v^{(t+1)} = \beta v^{(t)} + \alpha \nabla f(x^{(t)} - \beta v^{(t)})$$ $$x^{(t+1)} = x^{(t)} - v^{(t+1)}\]

这相当于先按照之前的速度方向走一步，然后再计算梯度校正。Nesterov 动量在某些情况下比标准动量收敛更快。

4.2 AdaGrad

4.2.1 AdaGrad 的原理

AdaGrad（Adaptive Gradient） 是第一个自适应学习率算法，由 Duchi 等人在 2011 年提出。它的核心思想是对每个参数使用不同的学习率，频繁更新的参数学习率较小，稀疏更新的参数学习率较大。

AdaGrad 的更新规则为：

\[g^{(t)} = \nabla f(x^{(t)})$$ $$r^{(t)} = r^{(t-1)} + g^{(t)} \odot g^{(t)}$$ $$x^{(t+1)} = x^{(t)} - \frac{\alpha}{\sqrt{r^{(t)}} + \epsilon} \odot g^{(t)}\]

其中：

$r^{(t)}$ 是梯度平方的累积和（按元素）
$\odot$ 是逐元素乘法
$\epsilon$ 是防止除零的小常数（如 $10^{-8}$）

直观理解：AdaGrad 对每个维度维护了一个累积的梯度平方和。如果某个维度在过去经常有大的梯度（即更新频繁），$r^{(t)}$ 会较大，该维度的学习率会被自动调低。反之，如果某个维度稀疏更新（即很少被更新），$r^{(t)}$ 较小，学习率相对较高。

这对于处理稀疏数据（如自然语言处理中的词嵌入）特别有效，因为词频差异很大，频繁出现的词不需要大学习率，而罕见词需要更大的学习率来赶上。

4.2.2 AdaGrad 的问题

AdaGrad 的一个主要问题是学习率会单调递减，可能导致训练过早停止。随着 $r^{(t)}$ 不断累积，学习率会越来越小，最终趋近于零，参数停止更新。

这在处理凸函数时是可以接受的（学习率递减有助于收敛到最优解），但在非凸的深度学习场景中可能有问题——我们可能还没有找到好的解，学习率就已经太小了。

4.3 RMSprop

4.3.1 RMSprop 的原理

RMSprop（Root Mean Square Propagation） 是 AdaGrad 的改进版本，由 Hinton 在其 Coursera 课程中提出，它使用指数移动平均来替代累积和，从而避免学习率持续下降的问题。

RMSprop 的更新规则：

\[g^{(t)} = \nabla f(x^{(t)})$$ $$r^{(t)} = \rho r^{(t-1)} + (1 - \rho) g^{(t)} \odot g^{(t)}$$ $$x^{(t+1)} = x^{(t)} - \frac{\alpha}{\sqrt{r^{(t)}} + \epsilon} \odot g^{(t)}\]

其中 $\rho$ 是衰减率（通常取 0.9），控制指数移动平均的窗口大小。

与 AdaGrad 的区别：AdaGrad 使用所有历史梯度平方的累积和，而 RMSprop 只使用最近一段时间的梯度（通过指数移动平均实现）。这使得学习率可以自适应调整，而不会无限递减。

等效形式：RMSprop 可以与动量结合使用：

\[g^{(t)} = \nabla f(x^{(t)})$$ $$r^{(t)} = \rho r^{(t-1)} + (1 - \rho) g^{(t)} \odot g^{(t)}$$ $$v^{(t+1)} = \beta v^{(t)} + \frac{\alpha}{\sqrt{r^{(t)}} + \epsilon} \odot g^{(t)}$$ $$x^{(t+1)} = x^{(t)} - v^{(t+1)}\]

这称为 RMSprop with Momentum，是深度学习中的常用优化器之一。

4.4 Adam

4.4.1 Adam 的原理

Adam（Adaptive Moment Estimation） 是目前深度学习中使用最广泛的优化器之一，由 Kingma 和 Ba 在 2015 年提出。Adam 结合了动量法和 RMSprop 的优点，同时使用了一阶矩估计（动量）和二阶矩估计（梯度平方的移动平均）。

Adam 的更新规则：

参数初始化： $$m^{(0)} = 0, \quad v^{(0)} = 0, \quad t = 0$$

每次迭代： $$t = t + 1$$ $$g^{(t)} = \nabla f(x^{(t-1)})$$ $$m^{(t)} = \beta_1 m^{(t-1)} + (1 - \beta_1) g^{(t)} \quad \text{（一阶矩，动量）}$$ $$v^{(t)} = \beta_2 v^{(t-1)} + (1 - \beta_2) g^{(t)} \odot g^{(t)} \quad \text{（二阶矩）}$$

偏差校正： $$\hat{m}^{(t)} = \frac{m^{(t)}}{1 - \beta_1^t} \quad \text{（校正一阶矩偏差）}$$ $$\hat{v}^{(t)} = \frac{v^{(t)}}{1 - \beta_2^t} \quad \text{（校正二阶矩偏差）}$$

参数更新： $$x^{(t)} = x^{(t-1)} - \frac{\alpha}{\sqrt{\hat{v}^{(t)}} + \epsilon} \odot \hat{m}^{(t)}$$

参数说明：

$\beta_1$：一阶矩（动量）的衰减率，通常取 0.9
$\beta_2$：二阶矩（梯度平方）的衰减率，通常取 0.999
$\alpha$：学习率，通常取 0.001（与上述默认值配合使用）
$\epsilon$：防止除零的小常数，通常取 $10^{-8}$

偏差校正的必要性：在训练初期，由于 $m^{(0)} = 0$ 和 $v^{(0)} = 0$，一阶矩和二阶矩的估计值会有偏差。例如，$m^{(1)} = \beta_1 \cdot 0 + (1-\beta_1) g^{(1)} = (1-\beta_1) g^{(1)}$，而真实值应该是 $g^{(1)}$。通过除以 $(1 - \beta^t)$ 可以校正这个偏差。随着 t 增大，$\beta^t$ 趋近于零，校正项趋近于 1，偏差逐渐消失。

4.4.2 Adam 的优点

Adam 有以下主要优点：

自适应学习率：结合了一阶矩和二阶矩估计，可以自动调整每个参数的学习率
稀疏梯度友好：对稀疏梯度有较好的处理
内存效率高：只存储一阶和二阶矩的估计，不需要存储历史梯度
鲁棒性强：对超参数的选择相对不敏感，默认参数在很多场景下都能工作
收敛速度快：通常比 SGD 收敛更快，适合大规模数据和参数

4.4.3 Adam 的问题与改进

Adam 的问题：

泛化性能：在一些任务上，Adam 的泛化性能不如 SGD（带有动量的随机梯度下降）。这可能是因为自适应学习率导致过早收敛到 sharp minima。
理论收敛性：在某些情况下，Adam 不能收敛到最优解（虽然实践中通常工作良好）。
方差问题：在后期，Adam 的方差可能较大，导致泛化性能下降。

AdamW：Adam 的一个改进是权重衰减（Weight Decay）方式的改进。在标准 Adam 中，权重衰减是通过 L2 正则化实现的，但 Adam 的自适应学习率会与 L2 正则化产生干扰。AdamW 将权重衰减与优化步骤分离，取得了更好的效果。PyTorch 的 AdamW 优化器实现了这一改进。

Adamax：Adam 的一个变体，使用无穷范数来代替二阶矩估计，在某些场景下更稳定。

RAdam（Rectified Adam）：在 Adam 中引入学习率预热（warm-up）来改进收敛性。

4.5 学习率总结对比

算法	学习率特点	动量	适用场景
SGD	固定或衰减	可选	收敛稳定的任务，泛化性能好
SGD + Momentum	固定或衰减	有	通用场景
AdaGrad	自适应递减	无	稀疏数据
RMSprop	自适应调整	可选	非稳态问题
Adam	自适应调整	有	默认选择，大规模问题

实践建议：对于大多数深度学习任务，Adam 是一个不错的默认选择，它可以快速收敛。对于追求最优泛化性能的任务，可以先用 Adam 快速收敛，然后再用 SGD 精调。对于稀疏数据或自然语言处理任务，Adam 特别适合。

5 约束优化

5.1 约束优化问题的定义

约束优化（Constrained Optimization） 问题是指在满足一定约束条件的情况下，寻找使目标函数最小化的解。约束优化问题的一般形式为：

\[\min_x f(x)\]

\[\text{s.t.} \quad g_i(x) \leq 0, \quad i = 1, \ldots, m\]

\[\quad h_j(x) = 0, \quad j = 1, \ldots, p\]

其中 $g_i(x) \leq 0$ 是不等式约束，$h_j(x) = 0$ 是等式约束。

可行域（Feasible Region）：满足所有约束条件的点 x 的集合称为可行域，记作：

\[\mathcal{F} = \{x \in \mathbb{R}^n \mid g_i(x) \leq 0, i = 1, \ldots, m; h_j(x) = 0, j = 1, \ldots, p\}\]

约束优化的目标是找到 $x^* \in \mathcal{F}$ 使得 $f(x^*) = \min_{x \in \mathcal{F}} f(x)$。

5.2 约束优化的分类

根据约束的类型，约束优化问题可以分为：

仅含不等式约束：$g_i(x) \leq 0$，这是最一般的情况

仅含等式约束：$h_j(x) = 0$，等式约束定义了一个流形（manifold）

混合约束：同时含有不等式约束和等式约束

约束的性质：

线性/非线性约束：约束函数是线性还是非线性
凸/非凸约束：约束定义的可行域是凸集还是非凸集
稀疏/稠密约束：约束是稀疏分布还是稠密分布

凸优化问题：如果目标函数是凸函数，不等式约束函数是凸函数，等式约束函数是仿射函数（即线性的），则该问题称为凸优化问题。凸优化问题的任何局部最优都是全局最优。

5.3 可视化理解约束

二维例子：考虑以下约束优化问题：

\[\min_{x_1, x_2} f(x_1, x_2) = x_1^2 + x_2^2\]

\[\text{s.t.} \quad x_1 + x_2 = 1\]

这是一个在直线 $x_1 + x_2 = 1$ 上寻找离原点最近点的问题。几何直观告诉我们，最优解应该是 $(0.5, 0.5)$，距离原点 $\sqrt{0.5}$。

不等式约束的例子：

\[\min_{x_1, x_2} f(x_1, x_2) = x_1^2 + x_2^2\]

\[\text{s.t.} \quad x_1 + x_2 \leq 1, \quad x_1 \geq 0, \quad x_2 \geq 0\]

这个问题的可行域是第一象限中位于直线 $x_1 + x_2 = 1$ 下方的三角形区域。最小值点仍然是 $(0.5, 0.5)$，但这次它是一个内部可行点（不是边界约束的交点）。

5.4 拉格朗日乘数法

拉格朗日乘数法（Lagrange Multiplier Method） 是求解等式约束优化问题的基本方法。

基本思想：对于等式约束问题 $\min_x f(x) \quad \text{s.t.} \quad h(x) = 0$，我们引入拉格朗日乘子 $\lambda$ 构造拉格朗日函数：

\[\mathcal{L}(x, \lambda) = f(x) + \lambda^\top h(x)\]

其中 $\lambda \in \mathbb{R}^p$ 是拉格朗日乘子向量。

最优性条件：在约束下极小化 f 等价于在无约束下极小化拉格朗日函数。一阶必要条件为：

\[\frac{\partial \mathcal{L}}{\partial x} = \nabla f(x) + J_h(x)^\top \lambda = 0$$ $$\frac{\partial \mathcal{L}}{\partial \lambda} = h(x) = 0\]

其中 $J_h(x)$ 是等式约束函数 $h$ 的雅可比矩阵（梯度按行排列）。

几何解释：在最优解处，目标函数的梯度 $\nabla f(x^*)$ 一定位于约束曲面法向量张成的空间中，即 $\nabla f(x^*)$ 是约束梯度 $h'(x^*)$ 的线性组合。这意味着在最优解处，目标函数的梯度与约束曲面正交，约束曲面是目标函数梯度方向的等值线。

二维例子回顾：对于问题 $\min x_1^2 + x_2^2 \quad \text{s.t.} \quad x_1 + x_2 = 1$：

构造拉格朗日函数：$\mathcal{L} = x_1^2 + x_2^2 + \lambda(x_1 + x_2 - 1)$

求偏导并设为零： - $\frac{\partial \mathcal{L}}{\partial x_1} = 2x_1 + \lambda = 0 \Rightarrow x_1 = -\lambda/2$ - $\frac{\partial \mathcal{L}}{\partial x_2} = 2x_2 + \lambda = 0 \Rightarrow x_2 = -\lambda/2$ - $\frac{\partial \mathcal{L}}{\partial \lambda} = x_1 + x_2 - 1 = 0 \Rightarrow x_1 + x_2 = 1$

由前两式得 $x_1 = x_2$，代入第三式得 $2x_1 = 1$，即 $x_1 = x_2 = 0.5$，$\lambda = -1$。

5.5 KKT 条件

KKT 条件（Karush-Kuhn-Tucker Conditions） 是拉格朗日乘数法在不等式约束问题上的推广，是约束优化问题最优解的一阶必要条件。

考虑一般约束优化问题：

\[\min_x f(x)\]

\[\text{s.t.} \quad g_i(x) \leq 0, \quad i = 1, \ldots, m\]

\[\quad h_j(x) = 0, \quad j = 1, \ldots, p\]

KKT 条件：

Stationarity（平稳性）： $$\nabla f(x^*) + \sum_{i=1}^{m} \mu_i \nabla g_i(x^*) + \sum_{j=1}^{p} \lambda_j \nabla h_j(x^*) = 0$$
Primal Feasibility（原始可行性）： $$g_i(x^*) \leq 0, \quad i = 1, \ldots, m$$ $$h_j(x^*) = 0, \quad j = 1, \ldots, p$$
Dual Feasibility（对偶可行性）： $$\mu_i \geq 0, \quad i = 1, \ldots, m$$
Complementary Slackness（互补松弛）： $$\mu_i g_i(x^*) = 0, \quad i = 1, \ldots, m$$

互补松弛条件的直观理解：对于每个不等式约束 $g_i(x) \leq 0$：

如果 $g_i(x^*) < 0$（约束未绑紧），则 $\mu_i = 0$（对应的乘子为零）
如果 $g_i(x^*) = 0$（约束绑紧，在可行域边界上），则 $\mu_i \geq 0$ 可以非零

这意味着只有"活跃的"（active）不等式约束才会对对偶变量有贡献。

例子：考虑约束优化问题：

\[\min_{x_1, x_2} (x_1 - 2)^2 + (x_2 - 1)^2\]

\[\text{s.t.} \quad x_1^2 - x_2 \leq 0\]

这是一个抛物线约束——可行域是抛物线 $x_2 = x_1^2$ 下方的区域（包括边界）。目标函数是一个二次函数，在 $(2, 1)$ 处取得最小值（无约束情况下）。

检查 $(2, 1)$ 是否在可行域内：$2^2 - 1 = 3 > 0$，不满足约束。所以约束是绑紧的（active），最优解在边界 $x_2 = x_1^2$ 上。

设 $x_1 = t, x_2 = t^2$，代入目标函数：$f(t) = (t-2)^2 + (t^2-1)^2$。求导：$f'(t) = 2(t-2) + 4t(t^2-1) = 2t - 4 + 4t^3 - 4t = 4t^3 - 2t - 4$。解 $f'(t) = 0$ 可以得到最优解。

5.6 约束优化在机器学习中的应用

5.6.1 支持向量机（SVM）

支持向量机是一个经典的约束优化问题：

\[\min_{w, b} \frac{1}{2}\|w\|^2\]

\[\text{s.t.} \quad y_i(w^\top x_i + b) \geq 1, \quad i = 1, \ldots, n\]

这是一个凸二次规划问题，目标是最大化间隔（等价于最小化权重范数），约束是保证所有样本被正确分类且有间隔。

通过引入拉格朗日乘子和求解对偶问题，我们可以得到支持向量的稀疏解——只有少数样本（支持向量）的乘子非零。

5.6.2 神经网络的不确定性量化

在贝叶斯深度学习中，我们经常需要对网络权重施加约束（如非负性、正则化等），这可以通过约束优化来实现。

5.6.3 权重归一化

某些模型架构要求权重满足特定约束（如正交性、归一性等）。权重归一化（Weight Normalization）将权重向量分解为模长和方向两部分：

\[w = \frac{g}{\|v\|} v\]

其中 v 是方向参数，g 是模长参数。通过参数化，我们可以将模长约束转化为无约束参数优化。

5.7 约束优化算法概述

实际求解约束优化问题的算法包括：

惩罚函数法（Penalty Method）：将约束加入目标函数，形成惩罚项：

\[\min_x f(x) + \sigma \sum_{i=1}^{m} \max(0, g_i(x))^2 + \sigma \sum_{j=1}^{p} h_j(x)^2\]

当 x 违反约束时，惩罚项增加。增大惩罚系数 σ 可以迫使解进入可行域。

障碍函数法（Barrier Method）：只在可行域内部进行优化，通过障碍函数防止接近边界：

\[\min_x f(x) - \frac{1}{t} \sum_{i=1}^{m} \log(-g_i(x))\]

当 x 接近边界（$g_i(x) \to 0$）时，障碍函数值趋近无穷，阻止 x 离开可行域。

增广拉格朗日法（Augmented Lagrangian Method）：结合了惩罚函数和拉格朗日乘数的优点：

\[\mathcal{L}_\rho(x, \lambda) = f(x) + \lambda^\top h(x) + \frac{\rho}{2} \|h(x)\|^2 + \sum_{i=1}^{m} \mu_i g_i(x) + \frac{\rho}{2} \sum_{i=1}^{m} \max(0, g_i(x))^2\]

序列最小二乘规划（SQP）：将约束优化问题转化为一系列二次规划子问题来求解，是求解非线性约束优化问题最有效的方法之一。

本章小结

本章系统介绍了优化的基础知识及其在机器学习中的应用。

我们首先定义了优化问题，理解了优化问题的分类、梯度与海森矩阵等基本概念。梯度下降法是最基本的优化算法，我们详细讨论了其原理、收敛性分析和学习率的影响。

随机梯度下降法是处理大规模机器学习问题的关键算法，它用单个样本或小批量样本的梯度来近似整体梯度，大大提高了计算效率。我们分析了随机梯度的统计性质和收敛性，讨论了梯度裁剪等实用技术。

高级优化算法部分介绍了动量法、AdaGrad、RMSprop 和 Adam 等算法。动量法通过引入"惯性"来加速收敛并减少震荡；AdaGrad 和 RMSprop 通过自适应调整学习率来适应不同参数的需求；Adam 结合了动量法和 RMSprop 的优点，是目前最广泛使用的优化器。

最后，我们介绍了约束优化问题及其解决方法，包括拉格朗日乘数法和 KKT 条件。这些理论工具在支持向量机、条件随机场等机器学习模型中有重要应用。

优化算法是机器学习的核心，掌握这些基础知识对于理解模型训练过程、诊断训练问题、设计新算法都至关重要。

思考与练习

梯度下降法验证：设目标函数 $f(x) = x^4 - 3x^3 + 2$，使用梯度下降法求解最小值：
计算梯度 $\nabla f(x)$
编写程序实现梯度下降法，初始点 $x_0 = 3$，学习率 $\alpha = 0.01$
观察迭代过程，理解为什么学习率过大会导致不收敛
尝试不同的学习率（如 0.1, 0.05, 0.01），观察收敛行为的差异
学习率调度：在深度学习中，为什么训练后期通常需要降低学习率？
设计一个学习率调度策略：初始学习率 0.1，每 10 个 epoch 降低 10%
思考余弦衰减和线性 warmup 的适用场景
如果学习率一直保持较高，会发生什么？
随机梯度下降 vs 批量梯度下降：
对于一个有 100 万样本的训练集，比较批量梯度下降和随机梯度下降每次迭代的计算复杂度
假设批量梯度下降每 epoch 需要 1000 秒，使用随机梯度下降大约需要多少时间？
为什么说随机梯度下降的"噪声"有时候是有益的？
动量法分析：考虑函数 $f(x, y) = x^2 + 10y^2$（椭圆函数，condition number = 10）。
使用标准梯度下降（学习率适当）迭代 100 步，观察收敛路径
使用动量法（β = 0.9）迭代 100 步，观察收敛路径有何不同
解释为什么动量法在椭圆函数上表现更好
Adam 算法实现：手动实现 Adam 优化器，包括偏差校正步骤。
初始化 $m_0 = 0, v_0 = 0, t = 0$
给定梯度 $g_t$，更新规则是什么？
解释为什么需要偏差校正
使用 Adam 训练一个简单模型（如线性回归），观察收敛过程
AdaGrad 与 RMSprop 比较：AdaGrad 的学习率会随时间单调递减，这可能导致什么问题？
RMSprop 如何解决这个问题？
在什么情况下 AdaGrad 仍然可能是更好的选择？
约束优化 - 拉格朗日乘数法：求解以下约束优化问题： $$\min_{x, y} x^2 + y^2$$ $$\text{s.t.} \quad x + y = 1$$
构造拉格朗日函数
求偏导并设方程组
解出 x, y 的最优值
验证该点满足约束且是全局最小值
KKT 条件应用：考虑 SVM 的优化问题（简化为二维情况）： $$\min_{w, b} \frac{1}{2}\|w\|^2$$ $$\text{s.t.} \quad y_i(w^\top x_i + b) \geq 1$$
写出 KKT 条件中的 complementary slackness 条件
解释为什么只有支持向量（落在间隔边界上的样本）的拉格朗日乘子可能非零
为什么 SVM 的解是稀疏的？
优化算法选择：假设你正在训练一个深度神经网络：
如果训练 loss 一直在震荡但没有明显下降，可能是什么原因？应该怎么调整？
如果训练 loss 下降正常但验证 loss 很高（过拟合），优化算法能解决这个问题吗？
如果模型出现梯度消失/梯度爆炸，应该使用什么技术？
Batch Size 的影响：在深度学习中，批量大小会影响训练动态：
- 大批量（1024+）和小批量（32-128）的收敛性有何不同？
- 大批量为什么需要更大的学习率（Linear Scaling Rule）？
- 为什么小批量通常有更好的泛化性能？
- 如果 GPU 内存有限，如何在保持小批量优势的同时增大批量？