随机变量的变换的Robbins-Monro算法与Kiefer-Wolfowitz算法
这两个算法是随机逼近领域的经典方法，用于在无法直接计算目标函数或其导数、但能获得其带噪声观测的情况下，寻找函数的零点或极值点。我会从基本问题出发，循序渐进地讲解。
第一步：核心问题与基本思想
想象你需要找到一个函数 \(M( heta)\) 的零点（即解方程 \(M( heta) = 0\)），或者一个函数 \(f( heta)\) 的极小值点。在经典优化中，你可能需要 \(M( heta)\) 的解析式或能精确计算其值。但在许多实际问题（如仿真优化、自适应控制、机器学习训练）中，你无法直接计算 \(M( heta)\) 或 \(f'( heta)\)，每次在某个参数点 \(heta_n\) 进行试验，只能得到一个带有随机噪声的观测值 \(Y_n\)。例如，\(Y_n = M( heta_n) + \epsilon_n\) 或 \(Y_n\) 是 \(f( heta_n)\) 附近梯度的有偏估计。
随机逼近 的核心思想是：设计一个迭代算法 \(heta_{n+1} = heta_n + a_n \cdot ( ext{基于} Y_n ext{的更新量})\)，使得尽管每一步都使用噪声数据，但序列 \(\{ heta_n\}\) 能收敛到我们想要的零点或最优点。这里的 \(a_n\) 是一个递减的增益序列（或步长序列），它对确保收敛至关重要。
第二步：Robbins-Monro 算法（寻根）
该算法旨在寻找回归函数 \(M( heta) = E[Y | heta]\) 的零点。
- 问题设定：假设我们想找到 \(heta^*\) 使得 \(M( heta^*) = 0\)。我们无法直接计算 \(M( heta)\)，但在任意点 \(heta\)，我们可以进行实验，观测到 \(Y( heta) = M( heta) + \epsilon( heta)\)，其中 \(\epsilon( heta)\) 是零均值的随机噪声。
- 算法迭代式：
\[ heta_{n+1} = heta_n - a_n Y_n \]
其中，\(Y_n = Y( heta_n) = M( heta_n) + \epsilon_n\) 是在当前迭代点 \(heta_n\) 获得的带噪声观测。
3. 直观理解：这个更新规则非常像确定性的梯度下降寻找零点（如果 \(M( heta)\) 是某个函数 \(f( heta)\) 的导数，这就是随机梯度下降）。它用当前观测到的函数值（带噪声）来调整参数。如果 \(Y_n\) 为正，意味着 \(M( heta_n)\) 可能为正，根据 \(heta_{n+1} = heta_n - a_n ( ext{正数})\)，\(heta\) 会减小；反之亦然。步长 \(a_n\) 必须满足两个关键条件以保证收敛：
\[ \sum_{n=1}^{\infty} a_n = \infty \quad ext{和} \quad \sum_{n=1}^{\infty} a_n^2 < \infty \]
第一个条件 \((\sum a_n = \infty)\) 确保算法有足够的“动力”到达 \(heta^*\)，即使初始值很远。第二个条件 \((\sum a_n^2 < \infty)\) 确保噪声的累积方差有限，从而使算法最终稳定下来。常用的选择是 \(a_n = c / n\)，其中 \(c > 0\)。
4. 收敛性：在 \(M( heta)\) 满足一定的单调性、光滑性条件，且噪声 \(\epsilon_n\) 满足某些矩条件和独立性/鞅差性质下，可以证明 \(heta_n \overset{ ext{a.s.}}{\ o} heta^*\)（几乎必然收敛）。这是随机逼近领域第一个里程碑式的成果。
第三步：Kiefer-Wolfowitz 算法（寻优）
该算法旨在找到使目标函数 \(f( heta) = E[F( heta, \xi)]\) 最小化的点 \(heta^*\)，其中 \(F\) 的期望无法直接计算，但能获得在 \(heta\) 处 \(f\) 的函数值（带噪声）观测。
- 问题设定：最小化 \(f( heta)\)。在点 \(heta\) 处，我们无法计算梯度 \(f'( heta)\)，但能获得两个对称点的带噪声函数值观测，用以估计梯度。
- 算法迭代式（有限差分法）：
\[ heta_{n+1} = heta_n - a_n \left( \frac{\widehat{f}( heta_n + c_n) - \widehat{f}( heta_n - c_n)}{2c_n} ight) \]
其中：
- \(\widehat{f}( heta_n \pm c_n)\) 是在点 \(heta_n \pm c_n\) 处对 \(f( heta_n \pm c_n)\) 的带噪声观测。
- 分式项是对梯度 \(f'( heta_n)\) 的中心有限差分估计。
- \(a_n\) 是增益序列（步长），与Robbins-Monro算法中类似。
- \(c_n\) 是一个趋于0的差分间隔序列，常用 \(c_n \propto n^{-\gamma}\)（\(0 < \gamma < 1/2\)）。
- 直观理解：算法用对称两点的函数值差除以两点距离来近似梯度，然后沿近似梯度的反方向（因为是 minimization）更新参数。步长 \(a_n\) 仍需满足 \(\sum a_n = \infty, \sum a_n^2 < \infty\)。差分间隔 \(c_n\) 趋于0是为了使梯度估计渐近无偏，但其趋于0的速度需要与 \(a_n\) 协调，以平衡估计的偏差和方差。
- 与Robbins-Monro的关系：可以将KW算法视为RM算法的一个应用。定义 \(M( heta) = f'( heta)\)，我们想找 \(M( heta) = 0\) 的点。KW算法中，差分商 \(\frac{\widehat{f}( heta_n + c_n) - \widehat{f}( heta_n - c_n)}{2c_n}\) 就是 \(M( heta_n)\) 的一个有偏、但渐近无偏的噪声观测值 \(Y_n\)。因此，KW算法的更新式 \(heta_{n+1} = heta_n - a_n Y_n\) 在形式上与RM算法一致，只是这里的 \(Y_n\) 是对梯度的估计而非对函数值的直接观测。
第四步：关键要点对比与拓展
- 目标不同：
- RM算法：寻找回归函数的零点（\(M( heta)=0\)）。
- KW算法：寻找目标函数的极值点（\(f'( heta)=0\)），通过有限差分估计梯度。
- 观测信息不同：
- RM算法：直接获得 \(M( heta)\) 的带噪声观测。
- KW算法：需要获得 \(f( heta)\) 在对称两点的带噪声观测，以构造梯度估计。
- 共同核心：两者都是随机迭代逼近算法，都依赖衰减的增益序列 \(a_n\) 来控制噪声的影响并保证收敛。收敛性证明通常依赖于构造一个相关的常微分方程（ODE），并证明算法轨迹逼近该ODE的解轨迹（ODE稳定性方法）。
- 现代拓展：这两个基础算法启发了大量随机优化方法。例如，在机器学习中广泛使用的随机梯度下降（SGD） 可以看作是RM算法的直接推广：目标是最小化 \(f( heta) = E[F( heta, \xi)]\)，在每步使用单个或小批量样本计算损失函数 \(F\) 对 \(heta\) 的梯度估计（有噪声），然后更新 \(heta_{n+1} = heta_n - a_n ( ext{噪声梯度估计})\)。这比KW算法更高效，因为它不需要额外的函数评估来估计梯度，前提是我们可以直接计算 \(F\) 对 \(heta\) 的梯度（即使其期望无法直接计算）。
总之，Robbins-Monro和Kiefer-Wolfowitz算法为解决噪声环境下的寻根和优化问题提供了根本性的框架，是连接经典优化理论与现代随机计算（如随机梯度下降）的关键桥梁。它们的核心在于巧妙设计迭代格式和增益序列，以噪声数据驱动迭代，并借助概率极限理论保证收敛性。