Skip to main content

Stochastic Approximation

Mean Estimation​

wk+1=1k∑i=1kxi=1k(∑i=1k−1xi+xk)=1k((k−1)wk+xk)=wk−1k(wk−xk)\begin{aligned} w_{k+1} &= \frac{1}{k} \sum\limits_{i=1}^{k} x_{i} \\ &= \frac{1}{k} \left( \sum\limits_{i=1}^{k-1} x_{i} + x_{k} \right) \\ &= \frac{1}{k} ((k-1)w_{k} + x_{k}) \\ &= w_{k} - \frac{1}{k}(w_{k} - x_{k}) \end{aligned}

Robbins-Monro​

Model-free solution to g(w)=0g(w) = 0:

wk+1=wk−αkg~(wk,ηk),k=1,2,3,…=wk−αk(g(wk)+ηk)\begin{aligned} w_{k+1} &= w_k - \alpha_k \tilde{g}(w_k, \eta_k), \quad k = 1, 2, 3, \dots \\ &= w_k - \alpha_k(g(w_k) + \eta_k) \end{aligned}

收敛条件:

  1. 0<c1≤∇wg(w)≤c2,∀w0 < c_1 \leq \nabla_w g(w) \leq c_2, \quad \forall w
  2. ∑k=1∞αk=∞\sum\limits_{k=1}^{\infty} \alpha_k = \infty and ∑k=1∞αk2<∞\sum\limits_{k=1}^{\infty} \alpha_k^2 < \infty
  3. E[ηk∣Hk]=0\mathbb{E}[\eta_k | \mathcal{H}_k] = 0 and E[ηk2∣Hk]<∞,Hk={wk,wk−1,… }\mathbb{E}[\eta_k^2 | \mathcal{H}_k] < \infty, \quad \mathcal{H}_k = \{w_k, w_{k-1}, \dots\}

Stochastic Gradient Descent​

wk+1=wk−αk∇wJ(wk)=wk−αkE[∇wf(wk,X)]=wk−αk∇wf(wk,xk)\begin{aligned} w_{k+1} &= w_k - \alpha_k \nabla_w J(w_k) \\ &= w_k - \alpha_k\mathbb{E}[\nabla_w f(w_k, X)] \\ &= w_k - \alpha_k \nabla_w f(w_k, x_k) \end{aligned}

收敛条件:

  1. 0<c1≤∇w2f(w,X)≤c20 < c_1 \leq \nabla_w^2 f(w, X) \leq c_2
  2. ∑k=1∞αk=∞\sum\limits_{k=1}^{\infty} \alpha_k = \infty and ∑k=1∞αk2<∞\sum\limits_{k=1}^{\infty} \alpha_k^2 < \infty
  3. {xk}k=1∞ is i.i.d.\{x_k\}_{k = 1}^{\infty} \text{ is i.i.d.}