引言与背景

随机逼近（Stochastic Approximation）是一类用于求解寻根或优化问题的随机迭代算法，其特点是不需要知道目标函数或其导数的表达式。

随机逼近的核心优势在于：

能够处理带有随机噪声的观测数据
不需要目标函数的解析表达式
可以在线学习，每获得一个新样本就更新估计值

均值估计问题

考虑一个随机变量\(X\)，其取值来自有限集合\(\mathcal{X}\)。我们的目标是估计\(E[X]\)。假设我们有一个独立同分布的样本序列\(\{x_i\}_{i=1}^n\)，那么\(X\)的期望值可以近似为：

\[ E[X] \approx \bar{x} = \frac{1}{n}\sum_{i=1}^n x_i \]

非增量方法与增量方法

非增量方法：先收集所有样本，然后计算平均值。缺点是如果样本数量很大，可能需要等待很长时间。

增量方法：定义

\[ w_{k+1} = \frac{1}{k}\sum_{i=1}^k x_i, k = 1, 2, ... \]

可以推导出递归公式：

\[ {w}_{k + 1} = \frac{1}{k}\mathop{\sum }\limits_{{i = 1}}^{k}{x}_{i} = \frac{1}{k}\left( {\mathop{\sum }\limits_{{i = 1}}^{{k - 1}}{x}_{i} + {x}_{k}}\right) = \frac{1}{k}\left( {\left( {k - 1}\right) {w}_{k} + {x}_{k}}\right) = {w}_{k} - \frac{1}{k}(w_k-x_k) \]

这个算法可以增量式地计算平均值，每次收到新样本就立即更新估计值。可以验证：

\[ \begin{aligned}{w}_{1} &= {x}_{1},\\ {w}_{2} &= {w}_{1} - \frac{1}{1}\left( {{w}_{1} - {x}_{1}}\right) = {x}_{1},\\ {w}_{3} &= {w}_{2} - \frac{1}{2}\left( {{w}_{2} - {x}_{2}}\right) = {x}_{1} - \frac{1}{2}\left( {{x}_{1} - {x}_{2}}\right) = \frac{1}{2}\left( {{x}_{1} + {x}_{2}}\right) ,\\ {w}_{4} &= {w}_{3} - \frac{1}{3}\left( {{w}_{3} - {x}_{3}}\right) = \frac{1}{3}\left( {{x}_{1} + {x}_{2} + {x}_{3}}\right) ,\\ ...\\ {w}_{k + 1} &= \frac{1}{k}\mathop{\sum }\limits_{{i = 1}}^{k}{x}_{i}\end{aligned} \]

更一般的形式是：

\[ w_{k+1} = w_k - \alpha_k(w_k - x_k) \]

其中\(\alpha_k > 0\) 是步长参数。 \(\{\alpha_k\}\) 满足一定条件（后面会说），当 \(k \to \infty\) 时，\(w_k \to E[X]\)。

Robbins-Monro算法

假设我们想要找到方程\(g(w) = 0\) 的根，其中\(w \in \mathbb{R}\) 是未知变量，\(g: \mathbb{R} \to \mathbb{R}\) 是一个函数。但是我们面临的问题是：

函数 \(g\) 的表达式未知
我们只能获得 \(g(w)\) 的带噪声观测值：\(\tilde{g}(w, \eta) = g(w) + \eta\)
如下图所示，这是一个黑盒系统，只有输入\(w\) 和带噪声的输出 \(\tilde{g}\) 是已知的。

算法描述

Robbins-Monro算法的形式为：

\[ \begin{equation}w_{k+1} = w_k - a_k\tilde{g}(w_k, \eta_k), k = 1, 2, 3, ...\end{equation} \]

其中 \(w_k\) 是第 \(k\) 次对根的估计，\(\tilde{g}(w_k, \eta_k)\) 是第 \(k\) 次带噪声的观测值，\(a_k\) 是正系数。

💡 Robbins-Monro算法示例：求解 \(g(w) = w^3 - 5\) 的根

收敛性质

Robbins-Monro定理: 在Robbins-Monro算法中，如果满足以下条件：

第一个条件：
第二个条件：
第三个条件：

应用于均值估计

将均值估计问题表述为寻根问题：

定义函数 \(g(w) = w - E[X]\)
原问题变为求解 \(g(w) = 0\)
给定 \(w\) 值，我们能获得的带噪声观测是 \(\tilde{g} = w - x\)
可以写成 \(\tilde{g}(w, \eta) = g(w) + \eta\)，其中 \(\eta = E[X] - x\)
应用Robbins-Monro算法：

\[ w_{k+1} = w_k - \alpha_k\tilde{g}(w_k, \eta_k) = w_k - \alpha_k(w_k - x_k) \]

这正是之前的均值估计算法。根据Robbins-Monro定理，如果\(\sum_{k=1}^{\infty} \alpha_k = \infty\)，\(\sum_{k=1}^{\infty} \alpha_k^2 < \infty\)，且\(\{x_k\}\) 是独立同分布的，则 \(w_k\) 几乎必然收敛到 \(E[X]\)。

对于Robbins-Monro算法的证明可以用Dvoretzky收敛定理，具体证明过程可以参阅 Mathematical Foundations of Reinforcement Learning

随机梯度下降(SGD)

考虑以下优化问题：

\[ \min_w J(w) = E[f(w, X)] \]

其中\(w\) 是待优化参数，\(X\) 是随机变量，期望是关于\(X\) 计算的。

梯度下降算法为：

\[ \begin{equation}w_{k+1} = w_k - \alpha_k\nabla_w J(w_k) = w_k - \alpha_k E[\nabla_w f(w_k, X)]\end{equation} \]

但这需要计算期望\(E[\nabla_w f(w_k, X)]\)，而这通常是未知的。

随机梯度下降算法

要解决这个问题，首先可以考虑用样本均值代替期望，即

\[ \mathbb{E}\left\lbrack {{\nabla }_{w}f\left( {{w}_{k},X}\right) }\right\rbrack \approx \frac{1}{n}\mathop{\sum }\limits_{{i = 1}}^{n}{\nabla }_{w}f(w_k, x_i) \]

将其带入到 (2)式，可得，

\[ {w}_{k + 1} = {w}_{k} - \frac{{\alpha }_{k}}{n}\mathop{\sum }\limits_{{i = 1}}^{n}{\nabla }_{w}f\left( {{w}_{k},{x}_{i}}\right). \]

上面的算法的一个问题是它需要每次迭代中的所有样本。在实践中，如果样本是逐个采集的，那么每次采集样本时更新 \(w\) 是比较好处理的。为此，我们可以使用以下算法：

\[ \begin{equation}w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k)\end{equation} \]

其中 \(x_k\) 是在时间步 \(k\) 收集的样本。该算法即为随机梯度下降法，因为它依赖于随机样本。随机梯度下降算法用随机梯度 \(\nabla_w f(w_k, x_k)\) 替代真实梯度 \(E[\nabla_w f(w_k, X)]\)。

收敛性分析

SGD有一个有趣的收敛模式：当估计值远离最优解时，收敛过程快速；当估计值接近最优解时，随机梯度的随机性变得显著，收敛速度减慢。

相对误差分析：

\[ \delta_k = \frac{|\nabla_w f(w_k, x_k) - E[\nabla_w f(w_k, X)]|}{|E[\nabla_w f(w_k, X)]|} \leq \frac{|\nabla_w f(w_k, x_k) - E[\nabla_w f(w_k, X)]|}{c|w_k - w^*|} \]

这表明相对误差 \(\delta_k\) 与 \(|w_k - w^*|\) 成反比。

SGD的收敛性定理: 对于SGD算法\(w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k)\)，如果满足以下条件，则 \(w_k\)几乎必然收敛到\(\nabla_w E[f(w, X)] = 0\) 的根：

🧾 SGD算法可以看作是特殊的Robbins-Monro算法：

SGD与均值估计

均值估计问题可以表述为优化问题：

\[ \min_w J(w) = E\left[\frac{1}{2}\|w - X\|^2\right] = E[f(w, X)] \]

其中\(f(w, X) = \|w - X\|^2/2\)，梯度为\(\nabla_w f(w, X) = w - X\)。可以验证最优解为\(w^* = E[X]\)（通过求解\(\nabla_w J(w) = 0\)）。

应用SGD算法：

\[ w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k) = w_k - \alpha_k(w_k - x_k) \]

这正是之前的均值估计算法，表明均值估计算法是一个专门为解决均值估计问题设计的SGD算法。

BGD, SGD, and mini-batch GD

假设我们要最小化\(J(w) = E[f(w, X)]\)，给定随机样本集\(\{x_i\}_{i=1}^n\)：

批量梯度下降(BGD)：
小批量梯度下降(MBGD)：
随机梯度下降(SGD)：
MBGD可以看作是SGD和BGD之间的中间版本：
相比SGD，MBGD随机性更小，因为它使用更多样本
相比BGD，MBGD不需要在每次迭代中使用所有样本，更加灵活
如果\(m = 1\)，MBGD变为SGD
MBGD的收敛速度通常比SGD更快
对于均值估计问题，三种算法分别为：

BGD：\(w_{k+1} = w_k - \alpha_k(w_k - \bar{x})\)
MBGD：\(w_{k+1} = w_k - \alpha_k(w_k - \bar{x}_k^{(m)})\)，其中\(\bar{x}_k^{(m)} = \frac{1}{m}\sum_{j \in I_k} x_j\)
SGD：\(w_{k+1} = w_k - \alpha_k(w_k - x_k)\)
当\(\alpha_k = 1/k\)时，这些方程可以解为：
BGD：\(w_{k+1} = \bar{x}\)
MBGD：\(w_{k+1} = \frac{1}{k}\sum_{j=1}^k \bar{x}_j^{(m)}\)
SGD：\(w_{k+1} = \frac{1}{k}\sum_{j=1}^k x_j\)

Reference

🔖 https://github.com/MathFoundationRL/Book-Mathematical-Foundation-of-Reinforcement-Learning/blob/main/3%20-%20Chapter%206%20Stochastic%20Approximation.pdf