Skip to main content

6. Stochastic Gradient Descent

当期望或完整梯度难以直接计算时，可以用随机样本构造一个带噪声的估计，再通过小步迭代逐渐接近目标。Robbins–Monro 随机逼近描述了这种方法能够收敛所需的基本条件，SGD 则是它在优化中的典型应用。

1. 从增量平均开始​

给定样本 X1,X2,…X_1,X_2,\ldots，前 kk 个样本的平均值为：

wk=1k∑i=1kXi.w_k=\frac1k\sum_{i=1}^{k}X_i.

当新样本 Xk+1X_{k+1} 到来时，可以增量更新：

wk+1=wk+1k+1(Xk+1−wk)=kwk+Xk+1k+1.\begin{aligned} w_{k+1} &=w_k+\frac{1}{k+1}(X_{k+1}-w_k)\\ &=\frac{k w_k+X_{k+1}}{k+1}. \end{aligned}

它的结构是：

新估计=旧估计+步长×(新样本−旧估计).\boxed{ \text{新估计} =\text{旧估计} +\text{步长}\times (\text{新样本}-\text{旧估计}) }.

2. Robbins–Monro 随机逼近​

假设我们想找到方程的根 w∗w^*：

g(w∗)=0.g(w^*)=0.

g(w)g(w) 可以称为平均场函数（mean field）或期望更新方向。实际中无法直接观测 g(wk)g(w_k)，只能得到带噪声的估计：

g^k=g(wk)+ηk.\widehat g_k=g(w_k)+\eta_k.

Robbins–Monro 更新为：

wk+1=wk−αkg^k.\boxed{ w_{k+1}=w_k-\alpha_k\widehat g_k }.

要让 wkw_k 逐渐接近 w∗w^*，需要同时约束 gg、随机噪声和步长。

2.1 函数 gg 的条件​

讲义采用的一维定理假设 g(w∗)=0g(w^*)=0 的解存在，并且：

0<c1≤g′(w)≤c2<∞,∀w.\boxed{ 0<c_1\leq g'(w)\leq c_2<\infty, \qquad \forall w }.

这个条件的含义是：

  • g′(w)>0g'(w)>0：gg 严格单调递增，根至多只有一个；
  • g′(w)≥c1g'(w)\geq c_1：函数不会过于平坦，仍能给出足够的修正方向；
  • g′(w)≤c2g'(w)\leq c_2：斜率不会任意大，更新方向不会因 gg 过于陡峭而失控。

因为 gg 单调递增且 g(w∗)=0g(w^*)=0：

{w>w∗⇒g(w)>0,w−αg(w) 向左移动,w<w∗⇒g(w)<0,w−αg(w) 向右移动.\begin{cases} w>w^* \Rightarrow g(w)>0, &w-\alpha g(w)\text{ 向左移动},\\ w<w^* \Rightarrow g(w)<0, &w-\alpha g(w)\text{ 向右移动}. \end{cases}

所以平均更新方向总是指向根 w∗w^*。

2.2 随机噪声的条件​

设 Hk\mathcal H_k 表示第 kk 次采样前已知的历史信息。通常要求：

E[ηk∣Hk]=0,E[ηk2∣Hk]≤C<∞.\boxed{ \mathbb E[\eta_k\mid\mathcal H_k]=0, \qquad \mathbb E[\eta_k^2\mid\mathcal H_k]\leq C<\infty }.

第一个条件表示噪声没有固定的偏向；第二个条件表示噪声的平均平方幅度受控。

2.3 步长 αk\alpha_k 的条件​

要求：

∑k=1∞αk=∞,∑k=1∞αk2<∞.\boxed{ \sum_{k=1}^{\infty}\alpha_k=\infty, \qquad \sum_{k=1}^{\infty}\alpha_k^2<\infty }.

可以直观地理解为：

  • ∑kαk=∞\sum_k\alpha_k=\infty：总步长不能太小，否则可能还没到达根附近就已经“走不动”；
  • ∑kαk2<∞\sum_k\alpha_k^2<\infty：步长要逐渐减小，使累积噪声受控。

典型选择是 αk=1/k\alpha_k=1/k，因为：

∑k=1∞1k=∞,∑k=1∞1k2=π26<∞.\sum_{k=1}^{\infty}\frac1k=\infty, \qquad \sum_{k=1}^{\infty}\frac1{k^2}=\frac{\pi^2}{6}<\infty.

常数步长 αk=α>0\alpha_k=\alpha>0 不满足第二个条件，因此通常用于持续跟踪变化中的目标，而不是证明精确收敛到固定点。

3. 均值估计例子​

如果要估计随机变量 XX 的期望，定义：

g(w)=w−E[X].g(w)=w-\mathbb E[X].

它的根是 w∗=E[X]w^*=\mathbb E[X]，并且 g′(w)=1g'(w)=1，所以满足前面的函数条件。

因为 E[X]\mathbb E[X] 未知，对新样本 Xk+1X_{k+1} 使用：

g^k=wk−Xk+1.\widehat g_k=w_k-X_{k+1}.

其中的噪声是：

ηk=E[X]−Xk+1.\eta_k=\mathbb E[X]-X_{k+1}.

若样本独立同分布且方差有限，则噪声条件成立。代入 Robbins–Monro 更新：

wk+1=wk−αk(wk−Xk+1).w_{k+1} =w_k-\alpha_k(w_k-X_{k+1}).

当 αk=1/(k+1)\alpha_k=1/(k+1) 时，这正好就是增量平均。

4. 从随机逼近到 SGD​

考虑：

min⁡wJ(w),J(w)=EX[f(w,X)].\min_w J(w), \qquad J(w)=\mathbb E_X[f(w,X)].

在可以交换求导与期望的条件下，真实梯度为：

g(w)=∇J(w)=EX[∇wf(w,X)].g(w)=\nabla J(w) =\mathbb E_X[\nabla_w f(w,X)].

在得到 wkw_k 后，抽取一个新的随机样本 Xk+1X_{k+1} 构造梯度估计：

g^k=∇wf(wk,Xk+1).\widehat g_k=\nabla_w f(w_k,X_{k+1}).

若它是真实梯度的无偏估计：

E[g^k∣Hk]=∇J(wk),\mathbb E[\widehat g_k\mid\mathcal H_k]=\nabla J(w_k),

那么 Robbins–Monro 更新就变成 SGD：

wk+1=wk−αk∇wf(wk,Xk+1).\boxed{ w_{k+1} =w_k-\alpha_k\nabla_w f(w_k,X_{k+1}) }.

在多维优化中，一维条件 0<c1≤g′(w)≤c20<c_1\leq g'(w)\leq c_2 会被相应的凸性、梯度光滑性和稳定性条件取代，但“平均方向正确、噪声受控、步长逐渐减小”这三个核心思想不变。

5. GD、Batch GD 与 SGD​

方法每次更新所用的数据特点
GD精确期望梯度方向稳定，但期望通常难以直接计算
Batch GD整个有限数据集单次成本高，梯度波动较小
SGD一个随机样本单次成本低，但梯度噪声较大

Mini-batch SGD 每次使用一小批样本，在计算成本和梯度方差之间折中。

6. 小结​

Robbins–Monro 随机逼近的基本结构是：

wk+1=wk−αk(g(wk)+ηk).w_{k+1}=w_k-\alpha_k\bigl(g(w_k)+\eta_k\bigr).

其收敛的三类核心条件是：

  1. gg 的根存在且平均更新方向指向该根；
  2. 噪声的条件均值为 00 且二阶矩有界；
  3. 步长满足 ∑kαk=∞\sum_k\alpha_k=\infty 与 ∑kαk2<∞\sum_k\alpha_k^2<\infty。

SGD 的本质就是用随机样本梯度作为 g(wk)g(w_k) 的带噪声估计，然后按照同样的随机逼近模板迭代。