强化学习的数学原理（六）：随机近似与随机梯度下降

2025-09-20 3358 words 7 minutes

Contents

在现代机器学习和深度学习领域，随机梯度下降（Stochastic Gradient Descent, SGD）算法几乎无处不在。从训练庞大的神经网络到处理海量数据集，SGD 及其变体是优化模型参数的核心引擎。然而，要真正理解 SGD 为何如此有效以及其收敛性的理论保障，我们不能仅仅将其视为一个简单的算法，而应追溯其深刻的数学根源——随机近似（Stochastic Approximation）理论。本文将从一个最基础的问题“增量式均值计算”出发，逐步揭示 Robbins-Monro 算法的精髓，并最终证明 SGD 正是该理论框架下的一个经典应用。

1. 问题的起点：均值估计 (Mean Estimation)

让我们从一个统计学中最常见的问题开始：如何估计一个随机变量 $X$ 的期望（均值）$E[X]$？

传统方法

最直观的方法是采集 $N$ 个样本点 $x_1, x_2, \dots, x_N$，然后计算它们的算术平均值 $\bar{x}$ 来近似 $E[X]$。 $$E[X] \approx \bar{x} := \frac{1}{N} \sum_{i=1}^{N} x_i$$ 这种方法简单有效，但有一个明显的缺点：它需要存储所有 $N$ 个样本点。当数据集非常大，甚至是流式数据（数据点持续不断地到来）时，这种方法的内存开销和计算需求会变得难以承受。

增量式方法及其优势

为了解决上述问题，我们可以采用一种增量式的计算方法。假设我们已经有了前 $k-1$ 个样本的均值估计 $W_k$，当第 $k$ 个样本 $x_k$ 到来时，我们如何更新估计值得到 $W_{k+1}$ 呢？

推导过程如下： $$W_{k+1} = \frac{1}{k} \sum_{i=1}^{k} x_i = \frac{1}{k} \left( \sum_{i=1}^{k-1} x_i + x_k \right)$$ 因为 $W_k = \frac{1}{k-1} \sum_{i=1}^{k-1} x_i$，所以 $\sum_{i=1}^{k-1} x_i = (k-1)W_k$。代入上式： $$W_{k+1} = \frac{(k-1)W_k + x_k}{k} = \frac{kW_k - W_k + x_k}{k} = W_k - \frac{1}{k} (W_k - x_k)$$ 我们得到了一个优雅的增量更新公式： $$W_{k+1} = W_k - \frac{1}{k} (W_k - x_k)$$ 这个公式的核心优势在于，我们不再需要存储所有历史数据。在每一步更新中，我们只需要保留当前的均值估计 $W_k$ 和新到来的数据点 $x_k$ 即可。这种在线学习（Online Learning）的能力使其在处理大规模数据时极为高效。

更一般地，我们可以将步长 $\frac{1}{k}$ 替换为一个系数 $\alpha_k$，得到通用形式： $$W_{k+1} = W_k - \alpha_k (W_k - x_k)$$ 当系数 $\alpha_k$ 满足特定条件时，随着 $k \to \infty$，估计值 $W_{k+1}$ 依然会收敛到真实的期望 $E[X]$。这个看似简单的迭代公式，实际上已经蕴含了随机近似的核心思想。

2. 通用框架：Robbins-Monro 算法

增量式均值估计展示了一种通过迭代和噪声数据逼近真实值的方法。上世纪50年代，Herbert Robbins 和 Sutton Monro 将这一思想提炼并泛化，提出了强大的 Robbins-Monro (RM) 算法。

随机近似 (Stochastic Approximation, SA)

首先，需要理解 RM 算法所属的领域：随机近似（SA）。

随机近似 (SA) 指的是一大类随机迭代算法，用于解决求根问题或优化问题。其显著特点是，相较于传统方法，它不需要知道目标函数的具体解析表达式，也不需要其梯度信息，仅依赖于对函数值的带噪观测。

Robbins-Monro 算法：在噪声中寻找真理

RM 算法的核心目标是解决求根问题：对于一个函数 $g(w)$，寻找其根 $w^*$，使得 $g(w^*) = 0$。关键的挑战在于，我们无法直接计算 $g(w)$ 的精确值，只能在任意点 $W_k$ 得到一个带噪声的观测值 $\tilde{g}(W_k, y_k)$。

RM 算法的迭代更新公式为： $$W_{k+1} = W_k - \alpha_k \tilde{g}(W_k, \eta_k), \quad k=1, 2, 3, \dots$$ 其中：

$W_k$ 是对根 $w^*$ 的第 $k$ 次估计。
$\tilde{g}(W_k, \eta_k) = g(W_k) + \eta_k$ 是第 $k$ 次带噪声的观测，其中 $\eta_k$ 是均值为零的噪声。
$\alpha_k$ 是一个正系数，通常称为步长或学习率。

这个算法的强大之处在于，函数 $g(w)$ 对我们来说可以是一个“黑箱”，我们只需要一个能提供带噪观测的“预言机”（Oracle）即可。

收敛条件及其意义

RM 算法的收敛性不是无条件的，它需要满足以下三个关键条件（Robbins-Monro 定理）：

函数有界性: $0 < C_1 < \nabla_w g(w) \leq C_2$ 对所有 $w$ 成立。
- 意义: **g单调递增且是凸函数。**这个条件要求函数 $g(w)$ 的行为是“良好”的。它不能太平坦（梯度不为零），也不能增长过快（梯度有界）。这保证了函数在根附近是单调的，迭代过程能够稳定地朝根的方向前进。
步长系数条件: $\sum_{k=1}^{\infty} \alpha_k = \infty$ 且 $\sum_{k=1}^{\infty} \alpha_k^2 < \infty$。
- 意义: 这是 RM 算法最核心的条件，它精妙地平衡了收敛速度和稳定性。
  - $\sum \alpha_k^2 < \infty$ 要求步长最终必须趋向于零（$\alpha_k \to 0$）。这保证了迭代的步子越来越小，使得估计值最终能在一个点附近稳定下来，而不是在根的周围永远震荡。
  - $\sum \alpha_k = \infty$ 要求步长衰减的速度不能“太快”。这保证了迭代步长的累加和是无限的，从而有能力跨越任意有限的距离，避免因步长过早衰减而停在离根很远的地方。
- 一个经典的满足该条件的序列是 $\alpha_k = \frac{1}{k}$。
对条件 2 的解释:
1. $\sum_{k=1}^{\infty} \alpha_k^2 < \infty$ indicates that $\alpha_k \to 0$ as $k \to \infty$.
  - $W_{k+1} - W_k = - \alpha_k \tilde{g}(W_k, \eta_k)$
  - If $\alpha_k \to 0$, then $W_{k+1} - W_k \to 0$.
2. $\sum_{k=1}^{\infty} \alpha_k = \infty$ （$\alpha_k$ 不能收敛的太快）
  - $W_2 - W_1 = - \alpha_1 \tilde{g}(W_1, \eta_1)$, $W_3 - W_2 = - \alpha_2 \tilde{g}(W_2, \eta_2)$
  - $W_{\infty} - W_1 = \sum_{k=1}^{\infty} \alpha_k \tilde{g}(W_k, \eta_k)$
  - 如果 $W_k \to w^*$，且 $\sum_{k=1}^{\infty} \alpha_k < \infty$ ，则 $\sum_{k=1}^{\infty} \alpha_k \tilde{g}(W_k, y_k)$ may be bounded。
  - 这意味着 $W_{\infty} - W_1$ 要求有界，初始值 $W_1$ 不能任选。
噪声条件: $E[\eta_k | H_k] = 0$ 且 $E[\eta_k^2 | H_k] < \infty$ (其中 $H_k = \{W_k, W_{k-1}, \cdots, \}$ 是历史信息)。
- 意义: 这个条件要求噪声必须是零均值的（无系统性偏差），并且方差有限（不会出现极端离谱的干扰）。它保证了噪声在长期来看会相互抵消，不会将迭代过程引向错误的方向。

当这三个条件满足时，RM 算法保证 $W_k$ 依概率 1 收敛到根 $w^*$。

与均值估计的深刻联系

现在，我们可以清晰地看到增量式均值估计与 RM 算法的关系。均值估计的目标是找到一个值 $w$，使得 $w = E[X]$，这等价于求解 $g(w) = w - E[X] = 0$ 的根。

目标函数: $g(w) = w - E[X]$。
带噪观测: 对于当前的估计 $W_k$ 和一个新的样本 $x_k$，我们可以构造一个 $g(W_k)$ 的无偏估计：$\tilde{g}(W_k, x_k) = W_k - x_k$。这里的噪声项 $\eta_k = E[X] - x_k$，其期望为零。

将这个 $\tilde{g}$ 代入 RM 算法的更新公式： $$W_{k+1} = W_k - \alpha_k (W_k - x_k)$$ 这与我们之前推导出的增量式均值估计算法完全一致！因此，增量式均值估计是 Robbins-Monro 算法在特定求根问题上的一个特例。

3. 随机梯度下降 (Stochastic Gradient Descent)

有了 RM 算法的理论基础，我们终于可以来分析机器学习的核心——随机梯度下降。

待求解的优化问题

在监督学习中，我们的目标通常是最小化一个损失函数 $J(w)$，这个损失函数定义为在整个数据分布上某个函数 $f(w, X)$ 的期望值： $$\min_{w} J(w) = E[f(w, X)]$$

$w$: 模型的待优化参数。
$X$: 代表数据样本的随机变量。
$f(w, X)$: 在单个样本 $X$ 上关于参数 $w$ 的损失。
$w$和$X$可以是标量或向量；$f(*)$是标量

求解优化问题的三种梯度方法

对于这个优化问题，一个经典思路是沿着梯度的反方向更新参数。

Method 1: 梯度下降 (GD) $$ W_{k+1} = W_k - \alpha_k \nabla_w E[f(W_k, X)] = W_k - \alpha_k E[\nabla_w f(W_k, X)] $$ 这个方法使用真实的期望梯度，理论上最精确。但计算 $E[\nabla_w f(W_k, X)]$ 需要对所有可能的数据进行积分，在实践中几乎是不可能实现的。
Method 2: 批量梯度下降 (BGD) $$ W_{k+1} = W_k - \alpha_k \left( \frac{1}{n} \sum_{i=1}^{n} \nabla_w f(W_k, x_i) \right) $$ BGD 用一个批次（通常是整个训练集）的平均梯度来近似真实梯度。当数据集很大时，每一步迭代的计算成本都非常高昂。
Method 3: 随机梯度下降 (SGD) $$ W_{k+1} = W_k - \alpha_k \nabla_w f(W_k, x_k) $$ SGD 在每一步只随机抽取一个样本 $x_k$，并用该样本的梯度 $\nabla_w f(W_k, x_k)$ 来作为整个期望梯度的近似。这种方法计算成本极低，且非常适合在线学习。

SGD 与 Robbins-Monro 的关系与收敛性证明

SGD 看似是一个非常粗糙的近似，但它的有效性可以由 RM 算法严格保证。

将优化问题转化为求根问题: 函数 $J(w)$ 的最小值点（或局部最小值点）必然满足其梯度为零的条件。因此，最小化 $J(w)$ 的问题等价于寻找梯度函数的根： $$ \nabla_w J(w) = \nabla_w E[f(w, X)] = E[\nabla_w f(w, X)] = 0 $$
构建 RM 框架:
- 令目标函数为 $g(w) = E[\nabla_w f(w, X)]$。我们的目标就是寻找 $g(w)$ 的根。
- 在 SGD 的每一步，我们使用单个样本 $x_k$ 计算的梯度 $\nabla_w f(W_k, x_k)$ 作为对真实梯度 $g(W_k)$ 的一次带噪观测。即： $$ \tilde{g}(W_k, x_k) = \nabla_w f(W_k, x_k) $$
- 这里的噪声项是 $\eta_k = \nabla_w f(W_k, x_k) - E[\nabla_w f(W_k, X)]$。只要样本 $x_k$ 是从数据分布中独立同分布地（i.i.d.）抽取的，那么这个噪声的期望就是零，满足 RM 算法的噪声条件。
推导 SGD 更新: 将上述定义代入 RM 算法的通用更新公式 $W_{k+1} = W_k - \alpha_k \tilde{g}(W_k, y_k)$，我们得到： $$ W_{k+1} = W_k - \alpha_k \nabla_w f(W_k, x_k) $$ 这正是 SGD 的更新法则！这个推导雄辩地证明了：SGD 是 Robbins-Monro 算法在求解“期望梯度等于零”这一特定求根问题上的直接应用。

SGD 的收敛条件

基于上述关系，SGD 的收敛性可以直接继承自 RM 算法的收敛定理。具体来说，如果满足以下条件：

$0 < C_1 < \nabla_w g(w) \leq C_2$。
步长 $\alpha_k$ 满足 $\sum \alpha_k = \infty$ 和 $\sum \alpha_k^2 < \infty$。
数据样本 ${x_k}$ 是独立同分布（i.i.d.）抽样的。

那么，SGD 算法将以概率 1 收敛到损失函数 $J(w)$ 的一个驻点（梯度为零的点）。

总而言之，从最简单的增量式均值估计，到通用的 Robbins-Monro 随机近似框架，再到现代机器学习的基石 SGD，我们看到了一条清晰而深刻的理论脉络。SGD 的强大威力并非偶然，它深深植根于坚实的数学理论之中，这正是它能够在充满噪声和不确定性的数据世界中稳健地寻找最优解的根本原因。