随机梯度下降

Stochastic Gradient Descent

目标为解决以下优化问题：

$$\underset{w}{min}J(w)=\mathbb{E}[f(w,X)]$$

求解参数 $w，使目标函数（机器学习中的损失函数）最小化。

梯度下降（Gradient Descent,GD）

$$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_w\mathbb{E}[f(w,X)]=w_k-{\alpha }_k\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]$$

特点：

❌ 难以求解

批量梯度下降（Batch Gradient Descent,BGD）

$$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_w\mathbb{E}[f(w,X)]\approx w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\mathrm{\nabla }}_{w}f(w_k,x_i)$$

特点：

✅ 梯度估计准确，收敛稳定

❌ 每轮计算复杂度 O(n)，大数据场景不可行

小批量梯度下降（MBGD）

$$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_w\mathbb{E}[f(w,X)]\approx w_k-{\alpha }_k\frac{1}{m}\sum _j^n{\mathrm{\nabla }}_{w}f(w_k,x_m)$$

随机梯度下降

用单个样本梯度作为期望梯度的无偏估计：

$$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_w\mathbb{E}[f(w,X)]\approx w_k-{\alpha }_k{\mathrm{\nabla }}_{w}f(w_k,x_k)$$

SGD 是一种特殊的 RM 算法，如果 SGD 满足下面的条件就可以知道 $w_k$ 收敛到 $w^{\ast }$ 就是方程的解：

1. $0<c_1\le {\mathrm{\nabla }}_w^{2}f(w,X)\le c_2$

2. $\sum _{k=1}^{\mathrm{\infty }}{\alpha }_k=\mathrm{\infty },\sum _{k=1}^{\mathrm{\infty }}{\alpha }_k^2<\mathrm{\infty }$

3. $x_k\sim P_X$ 是独立同分布的采样。