====== 第四章 优化算法 ======

===== 4.1 优化理论基础 =====

==== 4.1.1 凸优化与非凸优化 ====

**凸集与凸函数**

集合$C$是凸集，如果对于任意$\mathbf{x}, \mathbf{y} \in C$和$\theta \in [0, 1]$，有：

$$\theta \mathbf{x} + (1-\theta) \mathbf{y} \in C$$

函数$f$是凸函数，如果对于任意$\mathbf{x}, \mathbf{y}$和$\theta \in [0, 1]$，有：

$$f(\theta \mathbf{x} + (1-\theta) \mathbf{y}) \leq \theta f(\mathbf{x}) + (1-\theta) f(\mathbf{y})$$

凸优化问题具有良好的性质：
  - 任何局部最优都是全局最优
  - 可以使用高效的优化算法
  - 收敛性有理论保证

**神经网络的非凸性**

深度神经网络的损失函数通常是高度非凸的，原因包括：
  - 网络结构的非线性
  - 多个隐藏层导致的函数复合
  - 大量参数形成的复杂损失曲面

非凸优化的挑战：
  - 存在大量局部最优和鞍点 
  - 收敛性难以理论分析
  - 初始化对最终结果影响大

==== 4.1.2 收敛性分析 ====

**收敛速率**

优化算法的收敛速率描述接近最优解的速度：

  - $O(\frac{1}{t})$：次线性收敛（SGD）
  - $O(\rho^t)$：线性收敛（$\rho < 1$，Gradient Descent for strongly convex）
  - $O(\frac{1}{t^2})$：加速梯度方法

**停止准则**

实际训练中常用的停止条件：
  - 达到最大迭代次数
  - 损失变化小于阈值
  - 验证集性能不再提升（早停）
  - 梯度范数小于阈值

===== 4.2 随机梯度下降变体 =====

==== 4.2.1 SGD with Momentum ====

动量方法通过累积历史梯度信息来加速收敛：

$$\mathbf{v}_t = \gamma \mathbf{v}_{t-1} + \eta \nabla_{\theta} \mathcal{L}(\theta_t)$$
$$\theta_{t+1} = \theta_t - \mathbf{v}_t$$

Nesterov加速梯度（NAG）是动量的改进版本：

$$\mathbf{v}_t = \gamma \mathbf{v}_{t-1} + \eta \nabla_{\theta} \mathcal{L}(\theta_t - \gamma \mathbf{v}_{t-1})$$
$$\theta_{t+1} = \theta_t - \mathbf{v}_t$$

NAG先在动量方向上"预判"一步，然后计算梯度，有助于更稳定地收敛。

==== 4.2.2 AdaGrad详解 ====

AdaGrad为每个参数维护独立的学习率：

$$\mathbf{g}_t = \nabla_{\theta} \mathcal{L}(\theta_t)$$
$$\mathbf{G}_t = \mathbf{G}_{t-1} + \mathbf{g}_t \odot \mathbf{g}_t$$
$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\mathbf{G}_t + \epsilon}} \odot \mathbf{g}_t$$

AdaGrad的优势：
  - 适合稀疏梯度（如自然语言处理）
  - 自动调整学习率，无需手动调节
  - 对凸问题有好的理论保证

AdaGrad的局限：
  - 学习率单调递减，可能过早衰减
  - 非凸问题上表现不佳

==== 4.2.3 RMSProp与Adadelta ====

**RMSProp**

RMSProp使用指数移动平均代替累积：

$$\mathbf{E}[\mathbf{g}^2]_t = \beta \mathbf{E}[\mathbf{g}^2]_{t-1} + (1-\beta) \mathbf{g}_t^2$$
$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\mathbf{E}[\mathbf{g}^2]_t + \epsilon}} \odot \mathbf{g}_t$$

**Adadelta**

Adadelta是AdaGrad的扩展，消除了对学习率的全局设置：

$$\mathbf{E}[\mathbf{g}^2]_t = \rho \mathbf{E}[\mathbf{g}^2]_{t-1} + (1-\rho) \mathbf{g}_t^2$$
$$\text{RMS}[\mathbf{g}]_t = \sqrt{\mathbf{E}[\mathbf{g}^2]_t + \epsilon}$$
$$\Delta \theta_t = -\frac{\text{RMS}[\Delta \theta]_{t-1}}{\text{RMS}[\mathbf{g}]_t} \mathbf{g}_t$$

Adadelta使用更新量的指数移动平均作为学习率的单位。

==== 4.2.4 Adam家族 ====

**Adam**

Adam结合了动量和自适应学习率：

$$\mathbf{m}_t = \beta_1 \mathbf{m}_{t-1} + (1-\beta_1) \mathbf{g}_t$$
$$\mathbf{v}_t = \beta_2 \mathbf{v}_{t-1} + (1-\beta_2) \mathbf{g}_t^2$$
$$\hat{\mathbf{m}}_t = \frac{\mathbf{m}_t}{1-\beta_1^t}, \quad \hat{\mathbf{v}}_t = \frac{\mathbf{v}_t}{1-\beta_2^t}$$
$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{\mathbf{v}}_t} + \epsilon} \hat{\mathbf{m}}_t$$

**Adamax**

Adamax使用无穷范数代替L2范数：

$$\mathbf{u}_t = \max(\beta_2 \cdot \mathbf{u}_{t-1}, |\mathbf{g}_t|)$$
$$\theta_{t+1} = \theta_t - \frac{\eta}{\mathbf{u}_t} \hat{\mathbf{m}}_t$$

**Nadam**

Nadam结合Nesterov动量和Adam：

$$\hat{\mathbf{m}}_t = \frac{\beta_1 \mathbf{m}_t}{1-\beta_1^{t+1}} + \frac{(1-\beta_1)\mathbf{g}_t}{1-\beta_1^t}$$

===== 4.3 学习率调度策略 =====

==== 4.3.1 分段常数衰减 ====

每隔一定epoch将学习率乘以衰减因子：

$$\eta_t = \eta_0 \cdot \gamma^{\lfloor t / s \rfloor}$$

其中$s$是衰减周期，$\gamma$是衰减因子（如0.1）。

==== 4.3.2 指数与多步衰减 ====

**指数衰减**：
$$\eta_t = \eta_0 \cdot e^{-kt}$$

**多步衰减**：
在特定epoch进行衰减：
  - epoch 30: $\eta = 0.1 \eta_0$
  - epoch 60: $\eta = 0.01 \eta_0$
  - epoch 90: $\eta = 0.001 \eta_0$

==== 4.3.3 余弦退火 ====

余弦退火模拟余弦函数的形状调整学习率：

$$\eta_t = \eta_{min} + \frac{1}{2}(\eta_{max} - \eta_{min})(1 + \cos(\frac{t}{T}\pi))$$

**带重启的余弦退火（SGDR）**：

周期性重启学习率，帮助跳出局部最优：

$$\eta_t = \eta_{min} + \frac{1}{2}(\eta_{max} - \eta_{min})(1 + \cos(\frac{t \mod T_i}{T_i}\pi))$$

==== 4.3.4 预热策略 ====

**线性预热**：

前几个epoch线性增加学习率：
$$\eta_t = \eta_{target} \cdot \frac{t}{T_{warmup}}, \quad t \leq T_{warmup}$$

预热的作用：
  - 避免早期训练不稳定
  - 特别是在大批量训练时
  - 帮助Adam等自适应优化器更好地估计二阶矩

===== 4.4 大批量训练 =====

==== 4.4.1 大批量训练的挑战 ====

增大批量大小可以提高计算效率（利用硬件并行性），但会带来挑战：

  - **泛化性能下降**：大批量训练的测试误差通常更高
  - **优化困难**：损失曲面更尖锐，容易陷入尖锐极小值
  - **需要调整学习率**：大批量需要更大的学习率

==== 4.4.2 线性学习率缩放 ====

大批量训练的经验法则：当批量大小乘以$k$时，学习率也乘以$k$：

$$\eta_{new} = \eta_{base} \cdot \frac{\text{batch\_size}_{new}}{\text{batch\_size}_{base}}$$

==== 4.4.3 LARS和LAMB ====

**LARS（Layer-wise Adaptive Rate Scaling）**

为每层设置独立的学习率：

$$\eta_l = \eta \cdot \frac{||\mathbf{w}_l||}{||\nabla_{\mathbf{w}_l} \mathcal{L}||}$$

LAMB是LARS的Adam版本，结合了分层自适应和Adam的优点。

===== 4.5 二阶优化方法 =====

==== 4.5.1 牛顿法 ====

牛顿法利用二阶信息进行优化：

$$\theta_{t+1} = \theta_t - \mathbf{H}^{-1} \nabla_{\theta} \mathcal{L}$$

其中$\mathbf{H}$是Hessian矩阵。

优点：
- 二次收敛速率
- 收敛速度快

缺点：
- 计算Hessian和求逆开销巨大（$O(n^3)$）
- 存储Hessian需要$O(n^2)$空间

==== 4.5.2 拟牛顿法 ====

拟牛顿法用近似矩阵代替Hessian：

**BFGS算法**：
通过低秩更新维护Hessian逆的近似：
$$\mathbf{H}_{k+1}^{-1} = (\mathbf{I} - \frac{\mathbf{s}_k \mathbf{y}_k^T}{\mathbf{y}_k^T \mathbf{s}_k}) \mathbf{H}_k^{-1} (\mathbf{I} - \frac{\mathbf{y}_k \mathbf{s}_k^T}{\mathbf{y}_k^T \mathbf{s}_k}) + \frac{\mathbf{s}_k \mathbf{s}_k^T}{\mathbf{y}_k^T \mathbf{s}_k}$$

**L-BFGS**：
有限内存BFGS，只保存最近的$m$个向量对，大幅降低存储需求。

==== 4.5.3 自然梯度 ====

自然梯度考虑参数空间的黎曼几何结构：

$$\theta_{t+1} = \theta_t - \eta \mathbf{F}^{-1} \nabla_{\theta} \mathcal{L}$$

其中$\mathbf{F}$是Fisher信息矩阵。

自然梯度在参数空间中进行最速下降，但计算Fisher矩阵的逆仍然昂贵。

===== 4.6 例题分析 =====

==== 例题4.1 优化器比较 ====

**题目**：比较SGD with Momentum、RMSProp和Adam三种优化器的特点和适用场景。

**解答**：

**SGD with Momentum**：
  - 优点：泛化性能通常更好，收敛到更平坦的极小值
  - 缺点：需要仔细调参（学习率、动量系数），对初始学习率敏感
  - 适用：追求最优泛化性能的场景，如图像分类的最终训练

**RMSProp**：
  - 优点：自适应学习率，适合非平稳目标
  - 缺点：没有动量，可能在峡谷区域震荡
  - 适用：RNN训练，在线学习

**Adam**：
  - 优点：自适应学习率+动量，对超参数不敏感，训练速度快
  - 缺点：可能收敛到次优解，泛化性能可能不如SGD
  - 适用：大多数情况，特别是稀疏梯度、大规模数据集

==== 例题4.2 学习率调度计算 ====

**题目**：初始学习率$\eta_0 = 0.1$，使用余弦退火，$\eta_{min} = 0.001$，$T = 100$ epoch。计算第25、50、75 epoch的学习率。

**解答**：

$$\eta_t = 0.001 + \frac{1}{2}(0.1 - 0.001)(1 + \cos(\frac{t}{100}\pi))$$
$$= 0.001 + 0.0495(1 + \cos(0.01t\pi))$$

**t=25**：
$$\eta_{25} = 0.001 + 0.0495(1 + \cos(0.25\pi))$$
$$= 0.001 + 0.0495(1 + 0.707) = 0.001 + 0.0845 = 0.0855$$

**t=50**：
$$\eta_{50} = 0.001 + 0.0495(1 + \cos(0.5\pi))$$
$$= 0.001 + 0.0495(1 + 0) = 0.0505$$

**t=75**：
$$\eta_{75} = 0.001 + 0.0495(1 + \cos(0.75\pi))$$
$$= 0.001 + 0.0495(1 - 0.707) = 0.001 + 0.0145 = 0.0155$$

==== 例题4.3 大批量训练学习率调整 ====

**题目**：基准设置：批量大小时32，学习率0.01。现在要使用批量大小256，如何调整学习率？使用线性缩放原则。

**解答**：

线性缩放原则：
$$\eta_{new} = \eta_{base} \cdot \frac{\text{batch\_size}_{new}}{\text{batch\_size}_{base}}$$

$$\eta_{new} = 0.01 \cdot \frac{256}{32} = 0.01 \cdot 8 = 0.08$$

因此，学习率应调整为0.08。

===== 4.7 训练题 =====

==== 选择题 ====

1. 关于凸优化问题，以下说法正确的是：
   A. 存在多个全局最优
   B. 任何局部最优都是全局最优
   C. 必须使用随机梯度下降
   D. 神经网络损失函数通常是凸的

2. Adam优化器中，$\beta_1$和$\beta_2$的典型取值是：
   A. 0.5和0.9
   B. 0.9和0.999
   C. 0.999和0.9
   D. 0.1和0.01

3. 余弦退火学习率调度的主要优点是：
   A. 计算简单
   B. 学习率单调递减
   C. 周期性重启帮助跳出局部最优
   D. 不需要设置初始学习率

4. 大批量训练时，泛化性能下降的主要原因是：
   A. 计算量太大
   B. 容易收敛到尖锐的极小值
   C. 内存不足
   D. 梯度估计不准

5. 以下哪种方法使用二阶信息进行优化？
   A. SGD
   B. Adam
   C. 牛顿法
   D. RMSProp

==== 填空题 ====

6. Nesterov加速梯度与普通Momentum的主要区别是$\_\_\_\_$。

7. AdaGrad的主要局限是$\_\_\_\_$。

8. 线性学习率缩放原则指出，批量大小增加k倍，学习率应$\_\_\_\_$。

9. 预热策略的主要作用是$\_\_\_\_$。

10. L-BFGS相比于标准BFGS的主要改进是$\_\_\_\_$。

==== 计算题 ====

11. 使用Adam优化器，给定参数$\beta_1=0.9$，$\beta_2=0.999$，$\eta=0.001$，$\epsilon=10^{-8}$。前5个时间步的梯度为：$g_1=0.5$，$g_2=-0.3$，$g_3=0.2$，$g_4=0.1$，$g_5=-0.4$。初始$m_0=0$，$v_0=0$。计算第5步偏差校正后的$\hat{m}_5$和参数更新量$\Delta\theta$。

12. 使用步进衰减策略，初始学习率$\eta_0=0.1$，每30个epoch衰减为原来的0.1倍。计算第10、35、70 epoch的学习率。

===== 4.8 答案与解析 =====

==== 选择题答案 ====

1. **答案：B**
   解析：凸优化的重要性质是任何局部最优都是全局最优。

2. **答案：B**
   解析：Adam默认$\beta_1=0.9$，$\beta_2=0.999$。

3. **答案：C**
   解析：余弦退火周期性重启学习率，帮助跳出局部最优。

4. **答案：B**
   解析：大批量训练容易收敛到损失曲面的尖锐极小值，泛化性能差。

5. **答案：C**
   解析：牛顿法使用Hessian矩阵（二阶信息）。

==== 填空题答案 ====

6. **答案：先沿动量方向预判一步再计算梯度**

7. **答案：学习率单调递减，可能过早衰减**

8. **答案：也增加k倍**

9. **答案：避免早期训练不稳定（或帮助自适应优化器更好地估计矩）**

10. **答案：只保存最近的m个向量对，降低存储需求**

==== 计算题答案 ====

11. **解答**：
    
逐步计算：

| t | $g_t$ | $m_t$ | $v_t$ |
| 1 | 0.5 | 0.05 | 0.0005 |
| 2 | -0.3 | 0.015 | 0.00035 |
| 3 | 0.2 | 0.0335 | 0.00028 |
| 4 | 0.1 | 0.0402 | 0.00022 |
| 5 | -0.4 | -0.0038 | 0.00018 |
    
偏差校正（$t=5$）：

$$\hat{m}_5 = \frac{-0.0038}{1-0.9^5} = \frac{-0.0038}{0.4095} \approx -0.0093$$

$$\hat{v}_5 = \frac{0.00018}{1-0.999^5} = \frac{0.00018}{0.005} \approx 0.036$$
    
参数更新量：

$$\Delta\theta = -\frac{0.001}{\sqrt{0.036} + 10^{-8}} \times (-0.0093) \approx 0.00049$$

12. **解答**：
    
衰减函数：$\eta_t = 0.1 \times 0.1^{\lfloor t/30 \rfloor}$
    
$t=10$：$\lfloor 10/30 \rfloor = 0$，$\eta = 0.1 \times 1 = 0.1$

$t=35$：$\lfloor 35/30 \rfloor = 1$，$\eta = 0.1 \times 0.1 = 0.01$

$t=70$：$\lfloor 70/30 \rfloor = 2$，$\eta = 0.1 \times 0.01 = 0.001$