引言与背景

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

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

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

均值估计问题

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

非增量方法与增量方法

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

增量方法：定义

可以推导出递归公式：

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

更一般的形式是：

其中${\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算法的形式为：

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

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

收敛性质

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

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

应用于均值估计

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

• 定义函数 $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算法：

这正是之前的均值估计算法。根据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)

考虑以下优化问题：

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

梯度下降算法为：

但这需要计算期望$E[{\nabla }_{w}f(w_k,X)]$，而这通常是未知的。

随机梯度下降算法

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

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

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

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

收敛性分析

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

相对误差分析：

这表明相对误差 ${\delta }_k$ 与 $|w_k-w^{\ast }|$ 成反比。

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与均值估计

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

其中$f(w,X)=\Vert w-X{\Vert }^2/2$，梯度为${\nabla }_{w}f(w,X)=w-X$。可以验证最优解为$w^{\ast }=E[X]$（通过求解${\nabla }_{w}J(w)=0$）。

应用SGD算法：

这正是之前的均值估计算法，表明均值估计算法是一个专门为解决均值估计问题设计的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更快
  对于均值估计问题，三种算法分别为：

1. BGD：$w_{k+1}=w_k-{\alpha }_k(w_k-\bar{x})$
1. 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$
1. SGD：$w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$
   当${\alpha }_k=1/k$时，这些方程可以解为：

1. BGD：$w_{k+1}=\bar{x}$
1. MBGD：$w_{k+1}=\frac{1}{k}{\sum }_{j=1}^k{\bar{x}}_j^{(m)}$
1. 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