随机逼近

Stochastic Approximation

SA 指的是解决寻根（方程求解）或优化问题的一大类随机迭代算法。与许多其他寻根（方程求解）算法（如基于梯度的方法）相比，SA 的强大之处在于它不需要知道目标函数的表达式或其导数或者梯度的表达式。

均值估计（Mean Estimation）

在蒙特卡洛采样中：

$$\mathbb{E}[X]\approx \overline{x}:=\frac{1}{N}\sum _{i=1}^N{x}_i$$

如何计算平均值 $\overline{x}$ ?

• 收集所有样本，然后计算平均值。但这种方法必须等待样本收集完毕。
• 迭代计算平均值。

$$w_{k+1}=w_k-\frac{1}{k}(w_k-x_k)$$

有：

$$\begin{array}{l}{w}_1=0\\ w_2=w_1-(w_1-x_1)=x_1\\ w_3=\frac{1}{2}(x_1+x_2)\\ w_4=\frac{1}{3}(x_1+x_2+x_3)\\ \cdots \\ w_{k+1}=\frac{1}{k}\sum _{i=1}^k{x}_i=\frac{1}{k}\overline{x}\end{array}$$

进一步推广：

$$w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$$

Robbins-Monro 算法

Robbins-Monro 算法是 随机逼近领域的开创性方法，由 Herbert Robbins 和 Sutton Monro 于 1951 年提出，用于解决无法直接观测目标函数的方程求根问题。该算法在统计学、机器学习和控制理论中有广泛应用。

对于方程 $g(w)=0$，假设最优解为 $w^{\ast }$

在噪声存在的情况下，通过迭代逐步逼近方程 $g(w)=0$ 的解 $w^{\ast }$：

$$w_{k+1}=w_k-{\alpha }_k\cdot (g\left(w_k\right)+{\xi }_k)$$

其中，$w_k$ 是对根的第 $k$ 次估计，${\alpha }_k$ 是个正系数， 噪声 ${\xi }_k$ 表示对真实函数 $g(w)$ 观测时的随机误差。

算法收敛性依赖于以下条件：

• 步长要求：

$$\sum _{k=1}^{\mathrm{\infty }}{\alpha }_k=\mathrm{\infty }\text{(允许充分探索)}$$$$\sum _{k=1}^{\mathrm{\infty }}{\alpha }_k^2<\mathrm{\infty }\text{(抑制噪声累积)}$$

 常见选择：${\alpha }_k=c/k(c>0)$

• 函数性质：

 $g(w)$ 需满足：

$$0<c_1\le {\mathrm{\nabla }}_{w}g(w)\le c_2$$

 即函数单调且梯度有上下界。

• 噪声条件：

$$\mathbb{E}[{\xi }_k\mid w_k]=0$$$$\mathbb{E}[{\xi }_k^2\mid w_k]<\mathrm{\infty }$$

容易证明，均值分析方法得到的：

$$w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$$

是一个特殊的 RM 算法。