Notes/机器学习/深度学习模型/0-基础知识/2-优化理论.md

title, tags

title	tags
2-优化理论	优化理论 数学基础 深度学习

优化理论

本笔记面向深度学习科研人员，系统讲解优化理论的数学基础，涵盖经典方法、自适应学习率、自然梯度、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)

---

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