1 minute read

Stochastic Approximation & Stochastic Gradient Descent

Mean estimation

  • 考虑随机变量 $X$

  • 目标是估计 $\mathbb{E}[X]$

  • 假设已经收集了一系列 iid（independent and identical distributed）的样本${x_i}_{i=1}^N$

  • $X$ 的期望可以由下式近似得到 \(\mathbb{E}[X] \approx \bar{x} := \frac{1}{N}\sum_{i=1}^N x_i\)

如何计算 $\bar x$：

  1. 收集完所有的$x_i$相加取平均值，需要等待

  2. 增量式的方法，对已有的$k$个数据 \(w_{k+1} = \frac{1}{k} \sum_{i=1}^k x_i\) 因此 \(w_k = \frac{1}{k-1} \sum_{i=1}^{k-1} x_i\) 可以得到$w_{k+1}$与$w_k$之间的关系 \(\begin{aligned} w_{k+1} &= w_k - \frac{1}{k}(w_k - x_k) \\ &= w_k + \frac{1}{k}(x_k - w_k) \end{aligned}\)

    推广 \(\begin{aligned} w_{k+1} = w_k - {\color{red}\alpha_k}(w_k - x_k) \\ = w_k + {\color{red}\alpha_k}(x_k - w_k) \end{aligned}\) 是特殊的随机近似算法、随机梯度下降算法

Robbins-Monro 算法

随机梯度下降是RM算法的一种特殊情况

RM算法解决的问题是： \(w_{k+1} = w_k - a_k \tilde{g}(w_k,\eta_k), \quad k = 1,2,3,\dots\)

  • $\tilde{g}(w_k,\eta_k) = g(w_k)+\eta_k$
  • $\eta_k$表示“噪音”

$g(w)$是一个黑盒，不知道具体函数，

  • 输入序列${ w_k}$，输出序列${ \tilde{g}(w_k,\eta_k)}$

Robbins-Monro Theorem

在Robbins-Monro算法中，如果有

  • $0 < c_1 \leq \nabla_wg(w) \leq c_2, \forall w$
    • 要求梯度一定是要大于零且有上界的
  • $\sum_{k=1}^\infty a_k = \infty$ and $\sum_{k=1}^\infty a_k^2 < \infty$
    • 要求 $a_k$ 是要收敛于零的，但是收敛速度不能太快，保证后加入的采样的权重不会太低
  • $\mathbb{E}[\eta_k \mathcal{H}] = 0$ and $\mathbb{E}[\eta_k^2 \mathcal{H}] < \infty$
    • $\eta_k$ 的mean等于零，且不要求 $\eta_k$ 是高斯噪音

其中 $\mathcal{H}k = { w_k, w{k-1},\dots }$，则 $w_k$ 依照 probability 1（w.p.1）收敛到根 $w^$，且有 $g(w^) = 0$

为什么Mean estimation是特殊的RM算法

  1. 考虑函数 \(g(w) = w - \mathbb{E}[X]\) 目标是求解 $g(w)=0$ 的根，就可以得到 $\mathbb{E}[X]$

  2. 由$X$的采样，可以得到 \(\tilde{g}(w,x) = w - x\) 注意到 \(\begin{aligned} \tilde{g} (w,\eta) = w - x &= w - x + \mathbb{E}[X] - \mathbb{E}[X] \\ &= (w - \mathbb{E}[X]) + (\mathbb{E}[X] - x) = g(w) + \eta \end{aligned}\)

  3. 求解 $g(x)=0$ 的RM算法就为 \(w_{k+1} = w_k - \alpha_k \tilde{g}(w_j,\eta_k) = w_k - \alpha (w_k - x_k)\) 即Mean estimation

Dvoretzky‘s Theorem 暂时跳过

Stochastic gradient descent（SGD）

SGD也是RM算法的一个特殊情况，而Mean estimation又是SGD的一个特殊情况

SGD算法要解决的是下面的优化问题 \(\min_w J(w) = \mathbb{E} [f(w,X)]\)

  • $w$ 是要优化的参数
  • $X$ 是随机变量
  • $w$ 和 $X$ 可以是向量

解法一：gradient descent（GD）

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

解法二：batch gradient descent（BGD）

没有模型，就使用数据，对随机变量采样，取平均值 \(\mathbb{E}[\nabla_w f(w_k,X)] \approx \frac{1}{n} \sum_{i=1}^n \nabla_w f(w_k,x_i)\) 因此，得到 \(w_{k+1} = w_k - \alpha_k \frac{1}{n} \sum_{i=1}^n \nabla_w f(w_k, x_i)\)

解法三：stochastic gradient descent（SGD）

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

  • 与GD算法相比，GD中使用的是真实的梯度 $\mathbb{E}[\nabla_wf(w_k,X)]$，而SGD中，采用的是随机梯度 $\nabla_w f(w_k,x_k)$

  • 在BGD中，令$n=1$，即得到SGD

You May Also Enjoy