随机变量的变换的随机逼近方法的Robbins-Monro算法与Kiefer-Wolfowitz算法
字数 3617 2025-12-10 23:10:58

随机变量的变换的随机逼近方法的Robbins-Monro算法与Kiefer-Wolfowitz算法

我们来深入探讨随机逼近方法中的两个核心算法。随机逼近是一类用于寻找无法直接观测的函数的根或极值点的迭代随机算法，其特点是仅通过该函数带有噪声的观测值进行更新。

第一步：基本问题设定与核心思想
设想我们有一个函数 \(M(\theta)\)，但我们无法直接计算它。我们只能通过实验或模拟，在任意点 \(\theta\) 处获得一个带有随机噪声的观测值 \(Y(\theta) = M(\theta) + \epsilon\)，其中 \(\mathbb{E}[\epsilon | \theta] = 0\)，即观测是无偏的。我们的目标是：

  1. 求根问题：找到 \(\theta^*\) 使得 \(M(\theta^*) = \alpha\)（通常 \(\alpha = 0\)）。这由Robbins-Monro (RM) 算法解决。
  2. 优化问题：找到函数 \(M(\theta)\) 的极值点（最大值或最小值点），此时 \(M'(\theta^*) = 0\)。这由Kiefer-Wolfowitz (KW) 算法解决。

核心思想是：构造一个迭代序列 \(\{ \theta_n \}\)，形式为 \(\theta_{n+1} = \theta_n - a_n \times (\text{带噪声的更新项})\)。通过精心设计步长 \(\{a_n\}\) 和更新项，使得序列 \(\theta_n\) 几乎必然或依概率收敛到目标点 \(\theta^*\)。

第二步：Robbins-Monro 算法（随机逼近求根）
假设我们要解方程 \(M(\theta) = 0\)。算法迭代格式如下：

\[\theta_{n+1} = \theta_n - a_n Y_n \]

其中，\(Y_n\) 是在 \(\theta_n\) 处对 \(M(\theta_n)\) 的无偏观测，即 \(Y_n = M(\theta_n) + \epsilon_n\)，且 \(\mathbb{E}[\epsilon_n | \theta_n] = 0\)。

  • 直观解释：在点 \(\theta_n\)，我们观测到 \(Y_n\)。如果 \(Y_n > 0\)，表明 \(M(\theta_n)\) 可能为正（期望意义上），我们需要减小 \(\theta\) 以趋向于零点；反之则增加 \(\theta\)。更新量 \(a_n Y_n\) 正是基于此思想。
  • 收敛的关键条件：
  1. 步长条件：步长序列 \(\{a_n\}\) 需满足 \(a_n > 0\)， \(\sum_{n=1}^{\infty} a_n = \infty\) （保证能到达任意远处），以及 \(\sum_{n=1}^{\infty} a_n^2 < \infty\) （抑制噪声累积，使步长最终趋于零以稳定）。
  2. 函数条件：通常要求 \(M(\theta)\) 是单调增函数，且 \(M(\theta^*) = 0\)，并满足一定的增长条件（如 \((\theta - \theta^*)M(\theta) > 0\) 对 \(\theta \neq \theta^*\)），这保证了更新方向总是“拉向” \(\theta^*\)。
  3. 噪声条件：观测噪声的方差需有界，通常 \(\mathbb{E}[\epsilon_n^2 | \theta_n] \leq \sigma^2 (1 + \theta_n^2)\)。

在这些条件下，可以证明 \(\theta_n \overset{a.s.}{\to} \theta^*\)（几乎必然收敛）。

第三步：Kiefer-Wolfowitz 算法（随机逼近优化）
假设我们要最小化一个函数 \(L(\theta)\)，但无法直接计算其导数。我们只能获得在点 \(\theta\) 处带有噪声的函数值观测 \(Y(\theta) = L(\theta) + \epsilon\)。KW算法通过有限差分来近似梯度。

算法迭代格式为：

\[\theta_{n+1} = \theta_n - a_n \hat{g}_n \]

其中，梯度估计 \(\hat{g}_n\) 通过对称差分得到：

\[\hat{g}_n = \frac{Y(\theta_n + c_n) - Y(\theta_n - c_n)}{2c_n} \]

这里，\(Y(\theta_n + c_n)\) 和 \(Y(\theta_n - c_n)\) 是两个独立的、带有噪声的函数值观测。

  • 直观解释：\(\hat{g}_n\) 是梯度 \(L'(\theta_n)\) 的一个有偏但一致（当 \(c_n \to 0\)）的估计。算法本质是带噪声的梯度下降。
  • 收敛的关键条件：
  1. 步长与差分参数条件：步长 \(\{a_n\}\) 需满足与RM算法相同的条件（\(\sum a_n = \infty, \sum a_n^2 < \infty\)）。差分序列 \(\{c_n\}\) 需满足 \(c_n > 0\)， \(c_n \to 0\)，并且通常要求 \(\sum_{n=1}^{\infty} (a_n / c_n)^2 < \infty\) 以控制差分估计的方差爆炸。
  2. 函数条件：目标函数 \(L(\theta)\) 需具有唯一的最小值点 \(\theta^*\)，且在其周围具有足够好的性质（如强凸性或满足某些增长条件）。
    3. 噪声条件：观测噪声需零均值、有限方差，且在不同点的观测噪声相互独立（或至少是不相关的）。

在这些条件下，可以证明 \(\theta_n \overset{p}{\to} \theta^*\)（依概率收敛）。几乎必然收敛需要更强的条件。

第四步：算法比较、变体与应用场景

  • 比较：
    • RM 直接使用函数值观测（求根），KW 使用两个函数值观测的差分来估计梯度（优化）。
  • KW 的收敛理论通常比RM更复杂，因为其梯度估计是有偏的（偏差阶为 \(O(c_n^2)\)），且需要调整两个序列 \(\{a_n\}, \{c_n\}\)。
  • 变体：
  • 随机梯度下降 (SGD)：可视为KW算法在目标函数是有限和形式（如经验风险）时，使用单个样本或小批量样本计算真实梯度（无偏估计）的特例，此时不需要差分序列 \(c_n\)。
    • 自适应步长：后续发展出如AdaGrad、Adam等算法，它们修改了步长规则以适应不同参数的特征，但核心的随机逼近思想不变。
  • 应用场景：这两种算法是随机优化和在线学习的基石。应用领域包括：
    • 系统辨识与自适应控制（如调整控制器参数）。
    • 神经元网络训练（SGD及其变体）。
    • 强化学习中的策略评估与优化。
    • 蒙特卡洛优化中寻找似然函数的极值点。

第五步：一个简单的数值示例（Robbins-Monro）
假设真实函数 \(M(\theta) = \theta - 2\)，我们要找 \(M(\theta^*) = 0\) 的根，即 \(\theta^* = 2\)。观测模型为 \(Y_n = M(\theta_n) + \epsilon_n = (\theta_n - 2) + \epsilon_n\)，其中 \(\epsilon_n \sim N(0, 1)\)。
取步长 \(a_n = 1/n\)，初始值 \(\theta_1 = 0\)。
迭代过程：

\[\theta_2 = 0 - (1/1) \times [ (0-2) + \epsilon_1 ] = 2 - \epsilon_1 \]

\[ \theta_3 = \theta_2 - (1/2) \times [ (\theta_2 - 2) + \epsilon_2 ] \]

尽管每一步都受到噪声 \(\epsilon_n\) 干扰，但随着迭代进行（步长 \(1/n\) 减小），序列 \(\{\theta_n\}\) 将围绕真实解 \(\theta^*=2\) 波动并最终收敛于它。这直观地展示了随机逼近如何“以噪声平均噪声”并达成目标。

随机变量的变换的随机逼近方法的Robbins-Monro算法与Kiefer-Wolfowitz算法 我们来深入探讨随机逼近方法中的两个核心算法。随机逼近是一类用于寻找无法直接观测的函数的根或极值点的迭代随机算法，其特点是仅通过该函数带有噪声的观测值进行更新。 第一步：基本问题设定与核心思想 设想我们有一个函数 \( M(\theta) \)，但我们无法直接计算它。我们只能通过实验或模拟，在任意点 \( \theta \) 处获得一个带有随机噪声的观测值 \( Y(\theta) = M(\theta) + \epsilon \)，其中 \( \mathbb{E}[ \epsilon | \theta ] = 0 \)，即观测是无偏的。我们的目标是： 求根问题 ：找到 \( \theta^* \) 使得 \( M(\theta^* ) = \alpha \)（通常 \( \alpha = 0 \)）。这由Robbins-Monro (RM) 算法解决。 优化问题 ：找到函数 \( M(\theta) \) 的极值点（最大值或最小值点），此时 \( M'(\theta^* ) = 0 \)。这由Kiefer-Wolfowitz (KW) 算法解决。 核心思想是：构造一个迭代序列 \( \{ \theta_ n \} \)，形式为 \( \theta_ {n+1} = \theta_ n - a_ n \times (\text{带噪声的更新项}) \)。通过精心设计步长 \( \{a_ n\} \) 和更新项，使得序列 \( \theta_ n \) 几乎必然或依概率收敛到目标点 \( \theta^* \)。 第二步：Robbins-Monro 算法（随机逼近求根） 假设我们要解方程 \( M(\theta) = 0 \)。算法迭代格式如下： \[ \theta_ {n+1} = \theta_ n - a_ n Y_ n \] 其中，\( Y_ n \) 是在 \( \theta_ n \) 处对 \( M(\theta_ n) \) 的无偏观测，即 \( Y_ n = M(\theta_ n) + \epsilon_ n \)，且 \( \mathbb{E}[ \epsilon_ n | \theta_ n ] = 0 \)。 直观解释 ：在点 \( \theta_ n \)，我们观测到 \( Y_ n \)。如果 \( Y_ n > 0 \)，表明 \( M(\theta_ n) \) 可能为正（期望意义上），我们需要减小 \( \theta \) 以趋向于零点；反之则增加 \( \theta \)。更新量 \( a_ n Y_ n \) 正是基于此思想。 收敛的关键条件 ： 步长条件 ：步长序列 \( \{a_ n\} \) 需满足 \( a_ n > 0 \)， \( \sum_ {n=1}^{\infty} a_ n = \infty \) （保证能到达任意远处），以及 \( \sum_ {n=1}^{\infty} a_ n^2 < \infty \) （抑制噪声累积，使步长最终趋于零以稳定）。 函数条件 ：通常要求 \( M(\theta) \) 是单调增函数，且 \( M(\theta^ ) = 0 \)，并满足一定的增长条件（如 \( (\theta - \theta^ )M(\theta) > 0 \) 对 \( \theta \neq \theta^* \)），这保证了更新方向总是“拉向” \( \theta^* \)。 噪声条件 ：观测噪声的方差需有界，通常 \( \mathbb{E}[ \epsilon_ n^2 | \theta_ n] \leq \sigma^2 (1 + \theta_ n^2) \)。 在这些条件下，可以证明 \( \theta_ n \overset{a.s.}{\to} \theta^* \)（几乎必然收敛）。 第三步：Kiefer-Wolfowitz 算法（随机逼近优化） 假设我们要最小化一个函数 \( L(\theta) \)，但无法直接计算其导数。我们只能获得在点 \( \theta \) 处带有噪声的函数值观测 \( Y(\theta) = L(\theta) + \epsilon \)。KW算法通过有限差分来近似梯度。 算法迭代格式为： \[ \theta_ {n+1} = \theta_ n - a_ n \hat{g}_ n \] 其中，梯度估计 \( \hat{g}_ n \) 通过对称差分得到： \[ \hat{g}_ n = \frac{Y(\theta_ n + c_ n) - Y(\theta_ n - c_ n)}{2c_ n} \] 这里，\( Y(\theta_ n + c_ n) \) 和 \( Y(\theta_ n - c_ n) \) 是两个独立的、带有噪声的函数值观测。 直观解释 ：\( \hat{g}_ n \) 是梯度 \( L'(\theta_ n) \) 的一个有偏但一致（当 \( c_ n \to 0 \)）的估计。算法本质是带噪声的梯度下降。 收敛的关键条件 ： 步长与差分参数条件 ：步长 \( \{a_ n\} \) 需满足与RM算法相同的条件（\( \sum a_ n = \infty, \sum a_ n^2 < \infty \)）。差分序列 \( \{c_ n\} \) 需满足 \( c_ n > 0 \)， \( c_ n \to 0 \)，并且通常要求 \( \sum_ {n=1}^{\infty} (a_ n / c_ n)^2 < \infty \) 以控制差分估计的方差爆炸。 函数条件 ：目标函数 \( L(\theta) \) 需具有唯一的最小值点 \( \theta^* \)，且在其周围具有足够好的性质（如强凸性或满足某些增长条件）。 噪声条件 ：观测噪声需零均值、有限方差，且在不同点的观测噪声相互独立（或至少是不相关的）。 在这些条件下，可以证明 \( \theta_ n \overset{p}{\to} \theta^* \)（依概率收敛）。几乎必然收敛需要更强的条件。 第四步：算法比较、变体与应用场景 比较 ： RM 直接使用函数值观测（求根）， KW 使用两个函数值观测的差分来估计梯度（优化）。 KW 的收敛理论通常比RM更复杂，因为其梯度估计是有偏的（偏差阶为 \( O(c_ n^2) \)），且需要调整两个序列 \( \{a_ n\}, \{c_ n\} \)。 变体 ： 随机梯度下降 (SGD) ：可视为KW算法在目标函数是有限和形式（如经验风险）时，使用单个样本或小批量样本计算真实梯度（无偏估计）的特例，此时不需要差分序列 \( c_ n \)。 自适应步长 ：后续发展出如AdaGrad、Adam等算法，它们修改了步长规则以适应不同参数的特征，但核心的随机逼近思想不变。 应用场景 ：这两种算法是随机优化和在线学习的基石。应用领域包括： 系统辨识与自适应控制（如调整控制器参数）。 神经元网络训练（SGD及其变体）。 强化学习中的策略评估与优化。 蒙特卡洛优化中寻找似然函数的极值点。 第五步：一个简单的数值示例（Robbins-Monro） 假设真实函数 \( M(\theta) = \theta - 2 \)，我们要找 \( M(\theta^ ) = 0 \) 的根，即 \( \theta^ = 2 \)。观测模型为 \( Y_ n = M(\theta_ n) + \epsilon_ n = (\theta_ n - 2) + \epsilon_ n \)，其中 \( \epsilon_ n \sim N(0, 1) \)。 取步长 \( a_ n = 1/n \)，初始值 \( \theta_ 1 = 0 \)。 迭代过程： \[ \theta_ 2 = 0 - (1/1) \times [ (0-2) + \epsilon_ 1 ] = 2 - \epsilon_ 1 \] \[ \theta_ 3 = \theta_ 2 - (1/2) \times [ (\theta_ 2 - 2) + \epsilon_ 2 ] \] 尽管每一步都受到噪声 \( \epsilon_ n \) 干扰，但随着迭代进行（步长 \( 1/n \) 减小），序列 \( \{\theta_ n\} \) 将围绕真实解 \( \theta^* =2 \) 波动并最终收敛于它。这直观地展示了随机逼近如何“以噪声平均噪声”并达成目标。