Stochastic Approximation & Stochastic Gradient DescentPermalink

Mean estimationPermalink

• 考虑随机变量 $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 算法Permalink

随机梯度下降是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 TheoremPermalink

在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算法Permalink

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）Permalink

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

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

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

解法一：gradient descent（GD）Permalink

解法二：batch gradient descent（BGD）Permalink

没有模型，就使用数据，对随机变量采样，取平均值 $\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）Permalink

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

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