959 lines
28 KiB
Markdown
959 lines
28 KiB
Markdown
---
|
||
title: 2-优化理论
|
||
tags:
|
||
- 优化理论
|
||
- 数学基础
|
||
- 深度学习
|
||
---
|
||
|
||
# 优化理论
|
||
|
||
> 本笔记面向深度学习科研人员，系统讲解优化理论的数学基础，涵盖经典方法、自适应学习率、自然梯度、K-FAC 以及信任域方法。每部分包含严格的数学推导与直觉解释。
|
||
|
||
---
|
||
|
||
## 1. 经典优化方法
|
||
|
||
### 1.1 梯度下降法 (Gradient Descent)
|
||
|
||
#### 基本更新规则
|
||
|
||
给定目标函数 $f: \mathbb{R}^n \to \mathbb{R}$，梯度下降法沿负梯度方向进行迭代更新：
|
||
|
||
$$
|
||
\theta_{t+1} = \theta_t - lpha \nabla f(\theta_t)
|
||
$$
|
||
|
||
其中 $\alpha > 0$ 为学习率（步长）。
|
||
|
||
#### 一阶收敛速度分析
|
||
|
||
**定理 1.1 (梯度下降的收敛速率)**
|
||
|
||
假设 $f$ 为 $\beta$-平滑（$\beta$-Lipschitz 梯度）且 $\mu$-强凸，则梯度下降法以线性速率收敛：
|
||
|
||
$$
|
||
f(\theta_t) - f(\theta^*) \leq \left(1 - \frac{\mu}{\beta}\right)^t (f(\theta_0) - f(\theta^*))
|
||
$$
|
||
|
||
**证明：**
|
||
|
||
由于 $f$ 为 $\beta$-平滑，利用二次上界（Quadratic Upper Bound）：
|
||
|
||
$$
|
||
f(\theta_{t+1}) \leq f(\theta_t) + \langle \nabla f(\theta_t), \theta_{t+1} - \theta_t \rangle + \frac{\beta}{2} \|\theta_{t+1} - \theta_t\|^2
|
||
$$
|
||
|
||
代入更新规则 $\theta_{t+1} - \theta_t = -\alpha \nabla f(\theta_t)$：
|
||
|
||
$$
|
||
f(\theta_{t+1}) \leq f(\theta_t) - \alpha \|\nabla f(\theta_t)\|^2 + \frac{\beta \alpha^2}{2} \|\nabla f(\theta_t)\|^2 = f(\theta_t) - \alpha\left(1 - \frac{\beta \alpha}{2}\right) \|\nabla f(\theta_t)\|^2
|
||
$$
|
||
|
||
取最优步长 $\alpha^* = \frac{1}{\beta}$：
|
||
|
||
$$
|
||
f(\theta_{t+1}) \leq f(\theta_t) - \frac{1}{2\beta} \|\nabla f(\theta_t)\|^2
|
||
$$
|
||
|
||
由强凸性，$f(\theta_t) - f(\theta^*) \leq \frac{1}{2\mu} \|\nabla f(\theta_t)\|^2$，代入得：
|
||
|
||
$$
|
||
f(\theta_{t+1}) - f(\theta^*) \leq \left(1 - \frac{\mu}{\beta}\right)(f(\theta_t) - f(\theta^*))
|
||
$$
|
||
|
||
迭代 $t$ 次即得所证。$\square$
|
||
|
||
**直觉解释：**
|
||
- 条件数 $\kappa = \beta / \mu$ 决定了收敛速率。病态（ill-conditioned）问题收敛慢。
|
||
- 步长选择 $\alpha = 1/\beta$ 是最优的，过大会发散，过小会收敛缓慢。
|
||
- 梯度下降仅利用一阶信息，在强凸二次函数上收敛时间为 $O(\log(1/\epsilon))$。
|
||
|
||
---
|
||
|
||
### 1.2 牛顿法 (Newton's Method)
|
||
|
||
#### 二阶收敛性
|
||
|
||
牛顿法利用二阶导数信息加速收敛：
|
||
|
||
$$
|
||
\theta_{t+1} = \theta_t - H_t^{-1} \nabla f(\theta_t)
|
||
$$
|
||
|
||
其中 $H_t = \nabla^2 f(\theta_t)$ 为 Hessian 矩阵。
|
||
|
||
**定理 1.2 (牛顿法局部二阶收敛)**
|
||
|
||
设 $f$ 二阶连续可微，Hessian 在最优解 $\theta^*$ 处非奇异，且 $\nabla f(\theta^*) = 0$。则牛顿法局部二阶收敛：
|
||
|
||
$$
|
||
\|\theta_{t+1} - \theta^*\| = O(\|\theta_t - \theta^*\|^2)
|
||
$$
|
||
|
||
**证明：**
|
||
|
||
将 $\nabla f(\theta_t)$ 在 $\theta^*$ 处 Taylor 展开：
|
||
|
||
$$
|
||
\nabla f(\theta_t) = \underbrace{\nabla f(\theta^*)}_{=0} + H^* (\theta_t - \theta^*) + o(\|\theta_t - \theta^*\|)
|
||
$$
|
||
|
||
因此：
|
||
|
||
$$
|
||
\theta_{t+1} - \theta^* = \theta_t - \theta^* - H_t^{-1} \nabla f(\theta_t) = -H_t^{-1} \nabla f(\theta_t) + (\theta_t - \theta^*)
|
||
$$
|
||
|
||
代入展开式：
|
||
|
||
$$
|
||
\theta_{t+1} - \theta^* = -H_t^{-1} [H^* (\theta_t - \theta^*) + o(\|\theta_t - \theta^*\|)] + (\theta_t - \theta^*) = (I - H_t^{-1} H^*)(\theta_t - \theta^*) + o(\|\theta_t - \theta^*\|^2)
|
||
$$
|
||
|
||
当 $\theta_t \to \theta^*$ 时，$H_t \to H^*$，故 $\|I - H_t^{-1} H^*\| = O(\|\theta_t - \theta^*\|)$，于是：
|
||
|
||
$$
|
||
\|\theta_{t+1} - \theta^*\| = O(\|\theta_t - \theta^*\|^2)
|
||
$$
|
||
|
||
$\square$
|
||
|
||
#### 牛顿法的优势与局限
|
||
|
||
| 方面 | 说明 |
|
||
|------|------|
|
||
| **优势** | 二阶收敛（比梯度下降的线性收敛快得多） |
|
||
| **局限** | 需要计算 $O(n^2)$ 的 Hessian 矩阵并求逆 |
|
||
| **适用场景** | 小规模问题（如逻辑回归、神经网络精调） |
|
||
| **深度学习问题** | $n$ 可达百万至十亿，Hessian 计算不现实 |
|
||
|
||
**信赖域解释：** 牛顿法可视为在每一步求解如下信赖域子问题：
|
||
|
||
$$
|
||
\min_{d} \quad f(\theta_t) + \langle \nabla f(\theta_t), d \rangle + \frac{1}{2} d^T H_t d \quad \text{s.t.} \quad \|d\| \leq \Delta
|
||
$$
|
||
|
||
当 $H_t$ 正定时，解为 $d = -(H_t + \lambda I)^{-1} \nabla f(\theta_t)$，即牛顿步骤。
|
||
|
||
---
|
||
|
||
### 1.3 共轭梯度法 (Conjugate Gradient Method)
|
||
|
||
#### 基本思想
|
||
|
||
共轭梯度法旨在无需显式存储 Hessian 矩阵的情况下，求解线性系统 $A x = b$（其中 $A$ 对称正定），进而用于求解二次优化问题：
|
||
|
||
$$
|
||
\min_x \quad \frac{1}{2} x^T A x - b^T x
|
||
$$
|
||
|
||
#### 共轭方向定义
|
||
|
||
一组方向 $\{p_0, p_1, \ldots, p_{n-1}\}$ 称为 **$A$-共轭**，若：
|
||
|
||
$$
|
||
p_i^T A p_j = 0, \quad \forall i \neq j
|
||
$$
|
||
|
||
**引理 1.1** $A$-共轭方向组线性无关。
|
||
|
||
#### 算法流程
|
||
|
||
```
|
||
初始化: x_0, r_0 = b - A x_0, p_0 = r_0
|
||
for k = 0, 1, 2, ...:
|
||
α_k = (r_k^T r_k) / (p_k^T A p_k)
|
||
x_{k+1} = x_k + α_k p_k
|
||
r_{k+1} = r_k - α_k A p_k
|
||
if ||r_{k+1}|| < ε: break
|
||
β_k = (r_{k+1}^T r_{k+1}) / (r_k^T r_k)
|
||
p_{k+1} = r_{k+1} + β_k p_k
|
||
```
|
||
|
||
**定理 1.3 (共轭梯度收敛性)**
|
||
|
||
对于对称正定矩阵 $A$，共轭梯度法在最多 $n$ 步内精确收敛到解，且有误差界：
|
||
|
||
$$
|
||
\|x_k - x^*\|_A \leq 2 \left(\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}\right)^k \|x_0 - x^*\|_A
|
||
$$
|
||
|
||
其中 $\kappa = \lambda_{\max}(A) / \lambda_{\min}(A)$ 为条件数。
|
||
|
||
**与优化联系：** 求解二次优化 $\min_x \frac{1}{2} x^T A x - b^T x$ 等价于求解 $A x = b$。在非二次问题上，共轭梯度法可通过重启处理。
|
||
|
||
**直觉：** 共轭梯度法结合了正交搜索方向（像梯度下降）与共轭性（避免方向重复），在二次函数上具有最优收敛性。
|
||
|
||
---
|
||
|
||
## 2. 自适应学习率方法
|
||
|
||
> 深度学习的核心挑战：高维非凸优化、梯度稀疏、特征尺度不一。经典 SGD 对所有参数使用统一学习率，难以适应。
|
||
|
||
### 2.1 AdaGrad
|
||
|
||
#### 算法推导
|
||
|
||
AdaGrad 源自「对不同参数自适应调整学习率」的思想，核心是对历史梯度平方累积：
|
||
|
||
**更新规则：**
|
||
|
||
$$
|
||
\theta_{t+1,i} = \theta_{t,i} - \frac{\alpha}{\sqrt{G_{t,ii} + \epsilon}} \cdot g_{t,i}
|
||
$$
|
||
|
||
其中：
|
||
- $g_{t,i} = \nabla_{\theta_i} \mathcal{L}(\theta_t)$ 为第 $i$ 个参数在时间 $t$ 的梯度
|
||
- $G_t = \sum_{\tau=1}^t g_\tau g_\tau^T$ 为累积梯度平方矩阵（对角元素为 $G_{t,ii}$）
|
||
- $\epsilon$ 为数值稳定项（通常 $10^{-8}$）
|
||
|
||
**对角形式的推导：**
|
||
|
||
假设参数独立，近似目标函数为：
|
||
|
||
$$
|
||
\mathcal{L}(\theta) \approx \mathcal{L}(\theta_0) + \sum_i \frac{\partial \mathcal{L}}{\partial \theta_i} \delta_{\theta_i} + \frac{1}{2} \sum_i H_{ii} \delta_{\theta_i}^2
|
||
$$
|
||
|
||
其中 $H_{ii}$ 为 Hessian 对角元素。
|
||
|
||
对每个参数做二阶展开并求解最优步长：
|
||
|
||
$$
|
||
\frac{\partial}{\partial \delta_{\theta_i}} \left[ g_i \delta_{\theta_i} + \frac{1}{2} H_{ii} \delta_{\theta_i}^2 \right] = 0 \Rightarrow \delta_{\theta_i}^* = -\frac{g_i}{H_{ii}}
|
||
$$
|
||
|
||
若用累积梯度平方 $G_{t,ii}$ 估计 $H_{ii}$（假设 $H_{ii} \approx G_{t,ii}$），则：
|
||
|
||
$$
|
||
\theta_{t+1,i} = \theta_{t,i} - \frac{\alpha}{\sqrt{G_{t,ii} + \epsilon}} g_i
|
||
$$
|
||
|
||
#### 学习率衰减分析
|
||
|
||
**引理 2.1 (AdaGrad 学习率衰减)**
|
||
|
||
对于稀疏梯度特征（梯度只在少数时间出现），AdaGrad 对应的有效学习率为：
|
||
|
||
$$
|
||
\alpha_{t,i} = \frac{\alpha}{\sqrt{t_i + 1}}
|
||
$$
|
||
|
||
其中 $t_i$ 为参数 $i$ 累积非零梯度的次数。
|
||
|
||
**直觉：** AdaGrad 实际上对频繁出现的特征施加更小的学习率，对稀疏特征保留更大的学习率。这对于 NLP 中的词嵌入等稀疏特征特别有效。
|
||
|
||
**缺陷：** $G_t$ 单调增长，导致学习率持续衰减至过小，在凸函数上表现良好但深度学习中过早停止。
|
||
|
||
---
|
||
|
||
### 2.2 RMSProp
|
||
|
||
#### 指数加权移动平均的引入
|
||
|
||
RMSProp 通过指数加权移动平均（EWMA）替代简单累积，解决 AdaGrad 学习率过度衰减的问题：
|
||
|
||
$$
|
||
G_t = \gamma G_{t-1} + (1-\gamma) g_t g_t^T
|
||
$$
|
||
|
||
**对角形式更新：**
|
||
|
||
$$
|
||
\theta_{t+1,i} = \theta_{t,i} - \frac{\alpha}{\sqrt{G_{t,ii} + \epsilon}} g_{t,i}
|
||
$$
|
||
|
||
**参数含义：**
|
||
- $\gamma \in [0, 1)$ 控制历史梯度平方的衰减率（通常取 $0.9$）
|
||
- 近期梯度对 $G_t$ 影响更大，学习率适应更快
|
||
|
||
**与 AdaGrad 的关系：**
|
||
|
||
| 方法 | 累积方式 | 学习率 |
|
||
|------|----------|--------|
|
||
| AdaGrad | $G_t = \sum_{\tau=1}^t g_\tau^2$ | 持续衰减 |
|
||
| RMSProp | $G_t = \gamma G_{t-1} + (1-\gamma) g_t^2$ | 稳定衰减 |
|
||
|
||
**直觉：** RMSProp 通过 EWMA 使 $G_t$ 成为「滑动窗口」内的梯度平方均值，避免了单调累积导致的过度衰减。
|
||
|
||
**收敛性：** RMSProp 并非保证凸收敛，但实践中对非凸问题（如深度网络训练）效果显著。
|
||
|
||
---
|
||
|
||
### 2.3 Adam (Adaptive Moment Estimation)
|
||
|
||
#### 融合动量与 RMSProp
|
||
|
||
Adam 结合了两大思想：
|
||
1. **动量 (Momentum)**：加速收敛、抑制震荡
|
||
2. **RMSProp**：对梯度二阶矩自适应
|
||
|
||
**算法流程：**
|
||
|
||
```
|
||
初始化: θ_0, m_0 = 0, v_0 = 0, t = 0
|
||
for each iteration do:
|
||
t += 1
|
||
g_t = ∇_θ L(θ_{t-1}) # 梯度
|
||
m_t = β_1 * m_{t-1} + (1-β_1) * g_t # 一阶矩（动量）
|
||
v_t = β_2 * v_{t-1} + (1-β_2) * g_t^2 # 二阶矩（梯度平方的 EWMA）
|
||
m_hat = m_t / (1 - β_1^t) # 偏差校正（bias correction）
|
||
v_hat = v_t / (1 - β_2^t)
|
||
θ_t = θ_{t-1} - α * m_hat / (√v_hat + ε)
|
||
```
|
||
|
||
#### 偏差校正的完整推导
|
||
|
||
**问题：** 初始化时 $m_0 = 0, v_0 = 0$，导致早期估计有偏。
|
||
|
||
**一阶矩偏差分析：**
|
||
|
||
展开 $m_t$：
|
||
|
||
$$
|
||
m_t = (1-\beta_1) \sum_{i=1}^t \beta_1^{t-i} g_i
|
||
$$
|
||
|
||
真实期望为 $\mathbb{E}[g_t]$，但：
|
||
|
||
$$
|
||
\mathbb{E}[m_t] = (1-\beta_1) \sum_{i=1}^t \beta_1^{t-i} \mathbb{E}[g_i] \neq \mathbb{E}[g_t]
|
||
$$
|
||
|
||
特别地，当 $\mathbb{E}[g_i] = g^*$ 恒定时：
|
||
|
||
$$
|
||
\mathbb{E}[m_t] = g^* (1 - \beta_1^t)
|
||
$$
|
||
|
||
因此无偏估计为：
|
||
|
||
$$
|
||
\hat{m}_t = \frac{m_t}{1 - \beta_1^t}
|
||
$$
|
||
|
||
类似地，对二阶矩：
|
||
|
||
$$
|
||
\mathbb{E}[v_t] = (1-\beta_2) \sum_{i=1}^t \beta_2^{t-i} \mathbb{E}[g_i^2] = \mathbb{E}[g_t^2] (1 - \beta_2^t)
|
||
$$
|
||
|
||
无偏估计为：
|
||
|
||
$$
|
||
\hat{v}_t = \frac{v_t}{1 - \beta_2^t}
|
||
$$
|
||
|
||
**偏差校正的作用：**
|
||
- 初期（$t$ 小）：$1-\beta_1^t$ 和 $1-\beta_2^t$ 接近 0，放大估计值
|
||
- 后期（$t$ 大）：$1-\beta_1^t \to 1$，校正项趋于 1，影响可忽略
|
||
|
||
#### Adam 更新公式的直观理解
|
||
|
||
更新方向为 $\hat{m}_t$（偏差校正后的动量），步长由 $\hat{v}_t$ 控制：
|
||
|
||
$$
|
||
\theta_{t+1} = \theta_t - \alpha \frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \epsilon}
|
||
$$
|
||
|
||
- 动量项 $\hat{m}_t$ 提供方向加速
|
||
- 归一化因子 $\sqrt{\hat{v}_t}$ 提供自适应学习率
|
||
|
||
**收敛性保证：** 在适当假设下，Adam 可证明 $O(\sqrt{1/t})$ 的后悔上界。
|
||
|
||
**直觉：** Adam 如同「带阻尼的物理球」在损失曲面滚动，动量提供惯性，RMSProp 提供摩擦系数（随梯度变化调整）。
|
||
|
||
---
|
||
|
||
### 2.4 AdamW (Adam with Weight Decay)
|
||
|
||
#### 问题背景
|
||
|
||
标准 Adam+L2 正则化等价于在损失函数上添加 $\frac{\lambda}{2} \|\theta\|^2$，梯度为 $\nabla_\theta \mathcal{L} + \lambda \theta$。
|
||
|
||
更新为：
|
||
|
||
$$
|
||
\theta_{t+1} = \theta_t - \alpha \frac{m_t}{\sqrt{v_t}} - \alpha \lambda \theta_t = (1 - \alpha \lambda) \theta_t - \alpha \frac{m_t}{\sqrt{v_t}}
|
||
$$
|
||
|
||
**问题：** Adam 的自适应学习率会与 L2 正则化项耦合，导致正则化强度随参数规模变化，实际有效权重衰减不等于 $\lambda$。
|
||
|
||
#### 权重衰减的正确形式
|
||
|
||
AdamW 将权重衰减独立于自适应学习率：
|
||
|
||
$$
|
||
\theta_{t+1} = (1 - \lambda \alpha) \theta_t - \alpha \frac{m_t}{\sqrt{v_t}}
|
||
$$
|
||
|
||
而非标准 Adam 的 $(1 - \alpha \lambda) \theta_t$。
|
||
|
||
#### AdamW 与 Adam+L2 的本质区别
|
||
|
||
**核心观点：AdamW 与 Adam+L2 绝对不等价。** AdamW 提出的初衷就是解决 Adam 中 L2 正则与自适应学习率耦合畸变问题。
|
||
|
||
1. **标准 Adam + L2 正则（错误耦合）**
|
||
损失加 $\frac{\lambda}{2}\|\theta\|^2$，梯度混入 $\lambda\theta$：
|
||
$$
|
||
\theta_{t+1} = \theta_t - \alpha \frac{\hat{m}_t}{\sqrt{\hat{v}_t}+\epsilon} - \alpha\lambda \theta_t
|
||
$$
|
||
权重衰减强度**被自适应学习率缩放**，超参 $\lambda$ 失去物理意义。
|
||
|
||
2. **AdamW 正确分离式更新（行业标准）**
|
||
**先独立做权重衰减，再执行 Adam 梯度更新**，二者完全解耦：
|
||
$$
|
||
\begin{align*}
|
||
\theta_t &\leftarrow (1-\lambda) \cdot \theta_t \\
|
||
\theta_{t+1} &\leftarrow \theta_t - \alpha \cdot \frac{\hat{m}_t}{\sqrt{\hat{v}_t}+\epsilon}
|
||
\end{align*}
|
||
$$
|
||
|
||
**实践意义：**
|
||
|
||
| 特性 | Adam+L2 | AdamW |
|
||
|------|---------|-------|
|
||
| 正则化强度 | 依赖参数尺度 | 显式控制 |
|
||
| 权重衰减 | 与自适应学习率耦合 | 独立于学习率 |
|
||
| 超参解释性 | 差 | 好 |
|
||
|
||
**直觉：** AdamW 把权重衰减从梯度项中剥离，不再被一阶梯度、二阶矩自适应学习率影响，让 $\lambda$ 成为纯粹、可解释的权重衰减系数，解决了 Adam+L2 正则效果不稳定的问题。
|
||
|
||
---
|
||
|
||
## 3. 自然梯度 (Natural Gradient)
|
||
|
||
### 3.1 从欧氏度量到黎曼度量
|
||
|
||
#### 经典梯度的局限
|
||
|
||
经典梯度下降 $\theta_{t+1} = \theta_t - \alpha \nabla_\theta \mathcal{L}$ 基于欧氏度量 $\|\cdot\|_2$，即假设参数空间是均匀的。但在概率分布空间，KL 散度比欧氏距离更自然地度量「变化」。
|
||
|
||
#### KL 散度作为局部度量
|
||
|
||
两个概率分布 $p(\cdot|\theta)$ 和 $p(\cdot|\theta + \delta\theta)$ 之间的 KL 散度在一阶近似下：
|
||
|
||
$$
|
||
D_{\text{KL}}(p(\cdot|\theta) \| p(\cdot|\theta + \delta\theta)) \approx \frac{1}{2} \delta\theta^T F(\theta) \delta\theta
|
||
$$
|
||
|
||
其中 $F(\theta)$ 为 **Fisher 信息矩阵**。
|
||
|
||
**定义 3.1 (黎曼度量张量)**
|
||
|
||
令 $g_{ij}(\theta) = F_{ij}(\theta) = \mathbb{E}_{x \sim p(\cdot|\theta)} \left[ \frac{\partial \log p(x|\theta)}{\partial \theta_i} \frac{\partial \log p(x|\theta)}{\partial \theta_j} \right]$，则参数空间配备黎曼度量：
|
||
|
||
$$
|
||
\langle \delta\theta, \delta\theta \rangle_g = \delta\theta^T F(\theta) \delta\theta
|
||
$$
|
||
|
||
---
|
||
|
||
### 3.2 Fisher 信息矩阵的推导
|
||
|
||
**定理 3.1 (Fisher 信息矩阵)**
|
||
|
||
对参数化概率分布 $p(x|\theta)$，Fisher 信息矩阵定义为：
|
||
|
||
$$
|
||
F(\theta) = \mathbb{E}_{x \sim p(\cdot|\theta)} \left[ \nabla_\theta \log p(x|\theta) \nabla_\theta \log p(x|\theta)^T \right]
|
||
$$
|
||
|
||
**推导：**
|
||
|
||
对数似然梯度 $\nabla_\theta \log p(x|\theta)$ 的协方差：
|
||
|
||
$$
|
||
\text{Cov}_{x \sim p} [\nabla_\theta \log p(x|\theta)] = \mathbb{E}[(\nabla \log p)(\nabla \log p)^T] - \underbrace{\mathbb{E}[\nabla \log p]}_{=0} \mathbb{E}[\nabla \log p]^T
|
||
$$
|
||
|
||
第二项为零，因为：
|
||
|
||
$$
|
||
\mathbb{E}_{x \sim p} [\nabla_\theta \log p(x|\theta)] = \int p \frac{\nabla_\theta p}{p} dx = \nabla_\theta \int p \, dx = \nabla_\theta 1 = 0
|
||
$$
|
||
|
||
因此：
|
||
|
||
$$
|
||
F(\theta) = \text{Cov}(\nabla \log p) = \mathbb{E}[(\nabla \log p)(\nabla \log p)^T]
|
||
$$
|
||
|
||
**性质：**
|
||
1. $F(\theta)$ 半正定
|
||
2. $F(\theta) = \mathbb{E}[H_{\log p}]$，其中 $H_{\log p}$ 为对数似然的 Hessian
|
||
3. 对指数族分布，$F(\theta)$ 与 Hessian 一致
|
||
|
||
**与 Hessian 的联系：**
|
||
|
||
对损失函数 $\mathcal{L}(\theta) = -\mathbb{E}_{x \sim q}[\log p(x|\theta)]$（$q$ 为数据分布），有：
|
||
|
||
$$
|
||
-\nabla^2 \log p(x|\theta) = \nabla \log p(x|\theta) \nabla \log p(x|\theta)^T - H_{\log p}(x|\theta)
|
||
$$
|
||
|
||
取期望：
|
||
|
||
$$
|
||
F(\theta) = \mathbb{E}[-\nabla^2 \log p(x|\theta)] + \mathbb{E}[H_{\log p}(x|\theta)]
|
||
$$
|
||
|
||
若模型正确（$q = p$），第二项为零，故 $F(\theta) = \mathbb{E}[-H_{\log p}]$。
|
||
|
||
---
|
||
|
||
### 3.3 自然梯度更新
|
||
|
||
#### 定义
|
||
|
||
自然梯度定义为损失函数梯度在黎曼度量下的最速上升方向：
|
||
|
||
$$
|
||
\nabla_{\text{natural}} \mathcal{L} = F(\theta)^{-1} \nabla_\theta \mathcal{L}
|
||
$$
|
||
|
||
**定理 3.2 (自然梯度更新)**
|
||
|
||
在 KL 散度约束下，自然梯度更新为：
|
||
|
||
$$
|
||
\theta_{\text{new}} = \theta_{\text{old}} + \alpha \cdot F(\theta)^{-1} \nabla_\theta \mathcal{L}
|
||
$$
|
||
|
||
**推导：**
|
||
|
||
考虑约束优化问题：
|
||
|
||
$$
|
||
\min_{\delta\theta} \quad \mathcal{L}(\theta + \delta\theta) \quad \text{s.t.} \quad D_{\text{KL}}(p(\cdot|\theta) \| p(\cdot|\theta + \delta\theta)) \leq \frac{\epsilon}{2}
|
||
$$
|
||
|
||
一阶近似约束：
|
||
|
||
$$
|
||
\frac{1}{2} \delta\theta^T F(\theta) \delta\theta \leq \frac{\epsilon}{2} \Rightarrow \delta\theta^T F(\theta) \delta\theta \leq \epsilon
|
||
$$
|
||
|
||
使用拉格朗日乘子法：
|
||
|
||
$$
|
||
\mathcal{L}(\theta + \delta\theta) \approx \mathcal{L}(\theta) + \nabla \mathcal{L}^T \delta\theta + \frac{\lambda}{2} \delta\theta^T F \delta\theta
|
||
$$
|
||
|
||
对 $\delta\theta$ 求导并令为零：
|
||
|
||
$$
|
||
\nabla \mathcal{L} + \lambda F \delta\theta = 0 \Rightarrow \delta\theta = -\frac{1}{\lambda} F^{-1} \nabla \mathcal{L}
|
||
$$
|
||
|
||
令步长 $\alpha = -1/\lambda$，即得自然梯度更新。$\square$
|
||
|
||
---
|
||
|
||
### 3.4 与置信域方法的关系
|
||
|
||
**置信域 (Trust Region) 方法** 同样在约束区域内近似目标函数：
|
||
|
||
$$
|
||
\min_d \quad \nabla \mathcal{L}^T d + \frac{1}{2} d^T B d \quad \text{s.t.} \quad \|d\| \leq \Delta
|
||
$$
|
||
|
||
其中 $B$ 为正定矩阵。
|
||
|
||
**类比：**
|
||
- 经典 TRR：用 $B = I$（欧氏度量）
|
||
- 自然梯度 TR：用 $B = F(\theta)$（黎曼度量）
|
||
|
||
**差异：**
|
||
- 欧氏度量假设参数空间各向同性
|
||
- 黎曼度量基于 Fisher 信息，考虑了参数变化对分布的影响
|
||
|
||
**直觉：** 自然梯度告诉你「在概率分布空间中最有效的下降方向」，而非「在参数空间中欧氏意义下最陡的方向」。这对于涉及概率输出的模型（如分类器、生成模型）尤为重要。
|
||
|
||
---
|
||
|
||
## 4. K-FAC (Kronecker-Factored Approximate Curvature)
|
||
|
||
### 4.1 动机：解决 Fisher 矩阵的计算瓶颈
|
||
|
||
自然梯度更新 $F^{-1} \nabla \mathcal{L}$ 需要：
|
||
1. 计算 $F$（$n \times n$，$n$ 为参数数量，可达百万）
|
||
2. 求逆 $F^{-1}$（$O(n^3)$）
|
||
|
||
**K-FAC 的核心思想：** 用低秩 Kronecker 积近似 Fisher 矩阵，实现 $O(n)$ 存储与 $O(n)$ 更新。
|
||
|
||
---
|
||
|
||
### 4.2 Kronecker 分解的数学基础
|
||
|
||
**定义 4.1 (Kronecker 积)**
|
||
|
||
对 $A \in \mathbb{R}^{m \times n}$ 和 $B \in \mathbb{R}^{p \times q}$，Kronecker 积为：
|
||
|
||
$$
|
||
A \otimes B = \begin{bmatrix} a_{11} B & a_{12} B & \cdots & a_{1n} B \\ a_{21} B & a_{22} B & \cdots & a_{2n} B \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} B & a_{m2} B & \cdots & a_{mn} B \end{bmatrix} \in \mathbb{R}^{(mp) \times (nq)}
|
||
$$
|
||
|
||
**关键性质：**
|
||
|
||
1. **矩阵-向量乘积的分解计算：**
|
||
若 $F \approx A \otimes B$，则对向量 $v$：
|
||
|
||
$$
|
||
(A \otimes B) \text{vec}(X) = \text{vec}(A X B^T)
|
||
$$
|
||
|
||
这允许高效计算而不需要显式构造 $F$。
|
||
|
||
2. **求逆公式：**
|
||
$(A \otimes B)^{-1} = A^{-1} \otimes B^{-1}$
|
||
|
||
---
|
||
|
||
### 4.3 对角近似 vs Kronecker 近似的权衡
|
||
|
||
#### 对角近似
|
||
|
||
假设 $F$ 为对角矩阵 $\text{diag}(f_1, f_2, \ldots, f_n)$，则：
|
||
|
||
- 存储：$O(n)$
|
||
- 求逆：$O(n)$
|
||
- 更新：$O(n)$
|
||
|
||
**优点：** 极其简单高效
|
||
|
||
**缺点：** 忽略参数间相关性，对于高度相关的参数（如深度网络跨层参数）精度差
|
||
|
||
#### Kronecker 近似
|
||
|
||
假设 $F \approx A \otimes B$，其中 $A \in \mathbb{R}^{d_1 \times d_1}$，$B \in \mathbb{R}^{d_2 \times d_2}$，总参数 $n = d_1 d_2$。
|
||
|
||
**优点：** 捕获局部结构相关性
|
||
|
||
**缺点：** 需要选择合适的分解维度（通常对应网络层或权重矩阵结构）
|
||
|
||
#### 权衡对比
|
||
|
||
| 近似方式 | 存储复杂度 | 计算复杂度 | 精度 |
|
||
|----------|-----------|-----------|------|
|
||
| 完整 Fisher | $O(n^2)$ | $O(n^3)$ | 最高 |
|
||
| 对角近似 | $O(n)$ | $O(n)$ | 最低 |
|
||
| Kronecker | $O(d_1^2 + d_2^2)$ | $O(n)$ | 中等 |
|
||
|
||
---
|
||
|
||
### 4.4 Fisher 矩阵的块对角 Kronecker 分解
|
||
|
||
#### 分块结构
|
||
|
||
对于全连接层参数 $W \in \mathbb{R}^{d_{\text{in}} \times d_{\text{out}}}$，其 Fisher 信息矩阵为：
|
||
|
||
$$
|
||
F_W = \mathbb{E}[(\nabla_W \log p)(\nabla_W \log p)^T]
|
||
$$
|
||
|
||
K-FAC 将 $F_W$ 分解为：
|
||
|
||
$$
|
||
F_W \approx A \otimes B
|
||
$$
|
||
|
||
其中：
|
||
- $A \in \mathbb{R}^{d_{\text{in}} \times d_{\text{in}}}$，捕获输入激活间的相关性
|
||
- $B \in \mathbb{R}^{d_{\text{out}} \times d_{\text{out}}}$，捕获输出梯度间的相关性
|
||
|
||
**近似推导：**
|
||
|
||
利用方差拆分：
|
||
|
||
$$
|
||
F_W = \mathbb{E}[\nabla_W \log p \cdot \nabla_W \log p^T] = \mathbb{E}[a a^T \otimes g g^T] = \mathbb{E}[a a^T] \otimes \mathbb{E}[g g^T]
|
||
$$
|
||
|
||
其中 $a$ 为输入激活，$g$ 为输出梯度。在 K-FAC 中，我们用样本估计：
|
||
|
||
$$
|
||
\hat{A} = \frac{1}{S} \sum_{s=1}^S a_s a_s^T, \quad \hat{B} = \frac{1}{S} \sum_{s=1}^S g_s g_s^T
|
||
$$
|
||
|
||
则：
|
||
|
||
$$
|
||
F_W \approx \hat{A} \otimes \hat{B}
|
||
$$
|
||
|
||
#### 自然梯度计算的高效实现
|
||
|
||
给定梯度 $\nabla_W \mathcal{L}$，自然梯度更新为：
|
||
|
||
$$
|
||
\text{vec}(d) = (\hat{A}^{-1} \otimes \hat{B}^{-1}) \text{vec}(\nabla_W \mathcal{L})
|
||
$$
|
||
|
||
利用 Kronecker 性质：
|
||
|
||
$$
|
||
D = \hat{A}^{-1} \nabla_W \mathcal{L} \hat{B}^{-1}
|
||
$$
|
||
|
||
其中 $D$ 为 $d$ 的矩阵形式。
|
||
|
||
**算法复杂度：**
|
||
|
||
| 操作 | 复杂度 |
|
||
|------|--------|
|
||
| 存储 $\hat{A}, \hat{B}$ | $O(d_{\text{in}}^2 + d_{\text{out}}^2)$ |
|
||
| 计算 $D$ | $O(d_{\text{in}} \cdot d_{\text{out}})$ |
|
||
| 梯度计算 | $O(d_{\text{in}} \cdot d_{\text{out}})$ |
|
||
|
||
相比完整 Fisher 的 $O(n^3)$，K-FAC 实现了线性复杂度。
|
||
|
||
---
|
||
|
||
### 4.5 K-FAC 的实践要点
|
||
|
||
**超参选择：**
|
||
- 块大小：通常按层划分（每层独立 Kronecker 分解）
|
||
- 移动平均衰减：$\gamma \in [0.9, 0.99]$
|
||
- 小批量大小：影响估计方差
|
||
|
||
**训练稳定性：**
|
||
- 添加 damping $\lambda I$ 以保证数值稳定
|
||
- $\lambda$ 通常取 $10^{-3}$ 到 $10^{-1}$
|
||
|
||
**效果：**
|
||
- 在大规模 CNN、RNN 中效果显著
|
||
- 可达 SGD with momentum 的 2-10 倍加速
|
||
|
||
---
|
||
|
||
## 5. 信任域方法 (Trust Region Methods)
|
||
|
||
### 5.1 从信赖域到 TRPO
|
||
|
||
#### 信赖域方法概述
|
||
|
||
信赖域方法在每一步于当前位置 $\theta_t$ 附近构建局部模型 $m_k(d)$：
|
||
|
||
$$
|
||
\min_d \quad m_k(d) \quad \text{s.t.} \quad \|d\| \leq \Delta_k
|
||
$$
|
||
|
||
其中 $m_k(d)$ 通常为二阶近似：
|
||
|
||
$$
|
||
m_k(d) = f(\theta_k) + \nabla f(\theta_k)^T d + \frac{1}{2} d^T B_k d
|
||
$$
|
||
|
||
$B_k$ 为曲率估计（可以是 Hessian、Hessian-free、或仅对角）。
|
||
|
||
#### TRPO 的优化目标
|
||
|
||
**Trust Region Policy Optimization (TRPO)** 将策略优化问题建模为最大化期望回报，同时约束策略更新的幅度：
|
||
|
||
$$
|
||
\max_{\theta} \quad \mathbb{E}_t \left[ \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{\text{old}}}(a_t|s_t)} \hat{A}_t \right]
|
||
$$
|
||
|
||
$$
|
||
\text{s.t.} \quad \mathbb{E}_t \left[ D_{\text{KL}}(\pi_{\theta_{\text{old}}}(\cdot|s_t) \| \pi_\theta(\cdot|s_t)) \right] \leq \bar{D}_{\text{KL}}
|
||
$$
|
||
|
||
**推导为单步优化问题：**
|
||
|
||
对每个状态 $s$，令 $\rho(s)$ 为状态访问分布，则目标可写为：
|
||
|
||
$$
|
||
\max_\theta \quad \mathbb{E}_{s \sim \rho, a \sim \pi_{\theta_{\text{old}}}} \left[ \frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)} A(s,a) \right]
|
||
$$
|
||
|
||
定义 $\bar{D}_{\text{KL}}$ 为平均 KL 散度约束。
|
||
|
||
---
|
||
|
||
### 5.2 KL 散度约束下的拉格朗日乘子法
|
||
|
||
将 KL 散度约束加入目标：
|
||
|
||
$$
|
||
\mathcal{L}(\theta, \lambda) = \mathbb{E}_{s \sim \rho} \left[ \sum_a \pi_\theta(a|s) A(s,a) \right] - \lambda \left( \mathbb{E}_{s \sim \rho} \left[ D_{\text{KL}}(\pi_{\theta_{\text{old}}} \| \pi_\theta) \right] - \bar{D}_{\text{KL}} \right)
|
||
$$
|
||
|
||
**最优性条件（一阶）：**
|
||
|
||
$$
|
||
\frac{\partial \mathcal{L}}{\partial \theta} = 0 \Rightarrow \mathbb{E}_{s \sim \rho} \left[ \nabla_\theta \pi_\theta(a|s) A(s,a) \right] - \lambda \mathbb{E}_{s \sim \rho} \left[ \nabla_\theta D_{\text{KL}}(\pi_{\theta_{\text{old}}} \| \pi_\theta) \right] = 0
|
||
$$
|
||
|
||
**近似求解：**
|
||
|
||
使用一阶近似 $\pi_\theta(a|s) \approx \pi_{\theta_{\text{old}}}(a|s) + \nabla_\theta \pi_{\theta_{\text{old}}}(a|s)^T (\theta - \theta_{\text{old}})$，并假设 $A(s,a) \approx \hat{A}_t$，则：
|
||
|
||
$$
|
||
\mathbb{E}_{s,a} \left[ \nabla \log \pi_{\theta_{\text{old}}}(a|s) \hat{A}_t \right] - \lambda \mathbb{E}_{s,a} \left[ \nabla_\theta \log \pi_\theta(a|s) - \nabla_\theta \log \pi_{\theta_{\text{old}}}(a|s) \right] = 0
|
||
$$
|
||
|
||
令 $\delta\theta = \theta - \theta_{\text{old}}$，在 $\theta_{\text{old}}$ 处展开二阶项，得到关于 $\delta\theta$ 的线性方程组。
|
||
|
||
---
|
||
|
||
### 5.3 共轭梯度法求解子问题
|
||
|
||
#### 子问题的建立
|
||
|
||
将 TRPO 的约束优化问题近似为二次规划：
|
||
|
||
$$
|
||
\min_d \quad \nabla \mathcal{L}^T d + \frac{1}{2} d^T H d \quad \text{s.t.} \quad d^T M d \leq \bar{D}_{\text{KL}}
|
||
$$
|
||
|
||
其中：
|
||
- $H \approx \nabla^2 (\text{KL 散度项})$（Fisher 信息矩阵）
|
||
- $M = I$（或根据度量变化）
|
||
|
||
**等价的无约束形式：**
|
||
|
||
引入拉格朗日乘子 $\lambda$：
|
||
|
||
$$
|
||
\min_d \quad \nabla \mathcal{L}^T d + \frac{1}{2} d^T H d + \lambda (d^T M d - \bar{D}_{\text{KL}})
|
||
$$
|
||
|
||
最优性条件：
|
||
|
||
$$
|
||
H d + \lambda M d = -\nabla \mathcal{L}
|
||
$$
|
||
|
||
即 $(H + \lambda M) d = -\nabla \mathcal{L}$。
|
||
|
||
#### 共轭梯度求解步骤
|
||
|
||
**输入：** $g = -\nabla \mathcal{L}$，$H$（可用 Hessian-vector product 近似），约束半径 $\Delta$
|
||
|
||
**输出：** 步长 $d$
|
||
|
||
```
|
||
d_0 = 0, r_0 = g, z_0 = M r_0
|
||
for k = 0, 1, 2, ...:
|
||
if ||r_k|| < ε: break
|
||
α = (r_k^T z_k) / (p_k^T H p_k) # 计算步长
|
||
d_{k+1} = d_k + α p_k
|
||
r_{k+1} = r_k - α H p_k
|
||
z_{k+1} = M r_{k+1}
|
||
β = (r_{k+1}^T z_{k+1}) / (r_k^T z_k)
|
||
p_{k+1} = z_{k+1} + β p_k
|
||
```
|
||
|
||
**终止判据：** 当步长 $\|d_k\|$ 达到约束边界 $\Delta$ 时停止（自然梯度计算中，$\Delta$ 控制更新幅度）。
|
||
|
||
#### Hessian-vector product 的高效计算
|
||
|
||
深度网络中，完整的 $H$ 无法存储。K-FAC 提供近似：
|
||
|
||
$$
|
||
H v \approx (A^{-1} \otimes B^{-1}) v
|
||
$$
|
||
|
||
利用 Kronecker 性质：
|
||
|
||
$$
|
||
H v = \text{vec}(A^{-1} \cdot \text{mat}(v) \cdot B)
|
||
$$
|
||
|
||
只需存储 $A^{-1}, B^{-1}$，复杂度 $O(d_{\text{in}} \cdot d_{\text{out}})$。
|
||
|
||
---
|
||
|
||
### 5.4 TRPO 的完整流程
|
||
|
||
```
|
||
输入: 策略参数 θ_old, 约束 Δ
|
||
1. 计算梯度: g = ∇_θ J(θ_old)
|
||
2. 构建 Fisher 信息矩阵估计: F ≈ K-FAC(A, B)
|
||
3. 用共轭梯度法解 (F + λI)d = -g，约束 ||d|| ≤ Δ
|
||
4. 线搜索确保满足 KL 约束:
|
||
θ_new = θ_old + α d, α ∈ {0.1, 0.3, 0.5, 0.8, 1.0}
|
||
直到 D_KL(π_old || π_new) ≤ Δ
|
||
5. 更新: θ_old = θ_new
|
||
```
|
||
|
||
**关键特性：**
|
||
- 约束显式控制策略变化幅度（相比 Adam/AdamW 的隐式控制）
|
||
- 共轭梯度保证 $O(n)$ 步求解（$n$ 为参数维度）
|
||
- 线搜索确保收敛稳定性
|
||
|
||
---
|
||
|
||
## 6. 总结与对比
|
||
|
||
### 6.1 方法对比
|
||
|
||
| 方法 | 复杂度 | 收敛速度 | 自适应学习率 | 收敛保证 |
|
||
|------|--------|----------|--------------|----------|
|
||
| 梯度下降 | $O(n)$ | 线性 | 否 | 凸/强凸 |
|
||
| 牛顿法 | $O(n^3)$ | 二阶 | 否 | 局部 |
|
||
| 共轭梯度 | $O(n^2)$ | 线性（条件数依赖） | 否 | 二次 |
|
||
| AdaGrad | $O(n)$ | 次线性 | 是 | 凸 |
|
||
| RMSProp | $O(n)$ | 实践有效 | 是 | 无 |
|
||
| Adam | $O(n)$ | 实践有效 | 是 | 次线性 |
|
||
| 自然梯度 | $O(n^3)$（未近似） | 快速 | 天然 | 局部 |
|
||
| K-FAC | $O(n)$ | 实践有效 | 是 | 近似 |
|
||
| TRPO | $O(n)$ | 稳定 | 否 | 有约束 |
|
||
|
||
### 6.2 选择建议
|
||
|
||
**小规模问题（$n < 10^4$）：**
|
||
- 牛顿法、共轭梯度法优先
|
||
|
||
**大规模深度学习（$n > 10^6$）：**
|
||
- Adam/AdamW 作为默认选择
|
||
- 若需二阶信息，用 K-FAC 近似自然梯度
|
||
|
||
**策略优化（Reinforcement Learning）：**
|
||
- TRPO 提供稳定收敛
|
||
|
||
**直觉总结：**
|
||
- 一阶方法（梯度下降、SGD）简单但慢
|
||
- 自适应方法（Adam/RMSProp）在深度学习中平衡效率与效果
|
||
- 二阶方法（Newton、K-FAC）在计算允许时能提供更快的收敛
|
||
- 约束方法（TRPO）在策略更新中提供安全性保证
|
||
|
||
---
|
||
|
||
## 附录 A：关键数学结论
|
||
|
||
### A.1 强凸与平滑的定义
|
||
|
||
**定义 A.1 ($\mu$-强凸)**
|
||
|
||
函数 $f$ 为 $\mu$-强凸，若：
|
||
|
||
$$
|
||
f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle + \frac{\mu}{2} \|y-x\|_2^2, \quad \forall x,y
|
||
$$
|
||
|
||
**定义 A.2 ($\beta$-平滑)**
|
||
|
||
函数 $f$ 为 $\beta$-平滑，若：
|
||
|
||
$$
|
||
f(y) \leq f(x) + \langle \nabla f(x), y-x \rangle + \frac{\beta}{2} \|y-x\|_2^2, \quad \forall x,y
|
||
$$
|
||
|
||
### A.2 矩阵微积分常用公式
|
||
|
||
**向量梯度：**
|
||
$$
|
||
\nabla_x (b^T x) = b, \quad \nabla_x (x^T A x) = (A + A^T)x
|
||
$$
|
||
|
||
**Kronecker 性质：**
|
||
$$
|
||
(A \otimes B) \text{vec}(X) = \text{vec}(A X B^T)
|
||
$$
|
||
|
||
---
|
||
|
||
*本笔记基于优化理论与深度学习交叉领域的经典工作编写，重点在于建立从理论到实践的桥梁。* |