---
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)
$$

---

*本笔记基于优化理论与深度学习交叉领域的经典工作编写，重点在于建立从理论到实践的桥梁。*