1、小批量梯度与期望#

定义：对任意索引集 $S = \{j_1, ..., j_p\}$，可定义小批量目标和梯度：

若 $j_\ell$ 独立均匀采样自 $\{1, ..., m\}$，则

即小批量梯度是全梯度的无偏估计。

2、SGD算法流程#

1. 给定初始点 $X_0$（可随机）。
2. 对 $k=0,1,2,\ldots$ 重复：
   • 随机采样 $S_k=\{j_1, ..., j_{p_k}\}$，每个 $j_\ell$ 独立采自 $\{1,...,m\}$
   • $G_k = \nabla f_{S_k}(X_k)$
   • $X_{k+1} = X_k - \alpha_k G_k$
3. 步长 $\alpha_k$ 可固定或动态调整，$p_k$ 常常取1（单样本），也可取小批量。

由于 $\nabla f(X_k)^T (-G_k)$ 不一定 $<0$，每步不保证严格下降，因此分析期望下降。

1、二分类问题（MNIST 4 vs 9）#

目标函数：

其中 $y_i=1$（数字9），$y_i=-1$（数字4）。

SGD设置：$\alpha_k=0.001$，$|S_k|=1$。数值结果显示目标减少但后期有波动（噪声地板，noise floor）。

2、一般化SGD#

更一般形式为：

每步采样 $\xi_k$，取 $G_k = \nabla_x F(X_k, \xi_k)$。同理，

1、假设#

1. 每个 $f_j$ 都是 $L$-光滑函数 $\Rightarrow f$ 也是 $L$-光滑。

2. 存在 $M>0$，使得

   $$\operatorname{VAR}(G_k|X_k) := \mathbb{E}[(G_k - \nabla f(X_k))^T (G_k - \nabla f(X_k)) | X_k] \leq M$$

   即条件方差有界。

   证明：

   由于 $G_k = \nabla f_{S_k}(X_k)$ 是对样本集 $S_k$ 的梯度均值，且每个 $j_\ell$ 独立均匀采样自 $\{1, ..., m\}$，我们有

   $$\mathbb{E}[G_k | X_k] = \nabla f(X_k)$$

   计算条件方差：

   $$\operatorname{VAR}(G_k|X_k) = \mathbb{E}[\|G_k - \nabla f(X_k)\|^2 | X_k]$$

   对于单样本（$|S_k|=1$），

   $$\operatorname{VAR}(G_k|X_k) = \frac{1}{m} \sum_{j=1}^m \|\nabla f_j(X_k) - \nabla f(X_k)\|^2$$

   若每个 $\|\nabla f_j(x)\|$ 在所有 $x$ 上有界，即存在 $C>0$ 使得 $\|\nabla f_j(x)\| \leq C$，则

   $$\operatorname{VAR}(G_k|X_k) \leq 4C^2$$

   因此，若每个分量梯度有界，则条件方差有界，满足假设2。

2、关键引理：期望过估计（Overestimation in expectation）#

引理：

在上述假设下，

若进一步有条件方差界 $M$，则

• 当 $\alpha_k$ 足够小，右侧为严格下降。

证明：

由 $L$-光滑性，

对 $G_k$ 条件期望，利用 $\mathbb{E}[G_k|X_k] = \nabla f(X_k)$，由 $L$-光滑性，有

对 $S_k$ 条件期望（即对 $G_k$ 关于 $X_k$ 的条件期望）：

由于 $\mathbb{E}[G_k|X_k] = \nabla f(X_k)$，代入得

3、收敛性定理（L-光滑情况下）#

定理：

设 $f$ 有下界 $f$，满足上述假设。SGD 用定步长 $\alpha_k \equiv \eta/L$，$\eta \in (0,1]$，则

即噪声存在，$\|\nabla f(X_k)\|^2$ 只收敛到 $\eta M$，无法无限趋近于零（称为noise floor）。

证明：

由关键引理，

取 $\alpha_k \equiv \eta/L$，其中 $\eta \in (0,1]$，则

因此，

对 $X_k$ 取全期望，记 $f_k = \mathbb{E}[f(X_k)]$，有

移项并累加 $k=0$ 到 $k-1$，得

由于 $f_k \geq f$（$f$ 为下界），

两边同时除以 $k$，并取最小值有

证毕。

1、假设#

1. $f_j$ $L$-光滑，$f$ $L$-光滑。
2. $f$ 是 $\gamma$-强凸函数，即 $$2\gamma (f(x) - f(x^*)) \leq \|\nabla f(x)\|^2$$ 极小点 $x^*$ 唯一。
3. 步长 $\alpha_k \equiv \eta/L, \; \eta \in (0,1]$
4. 有界方差：$\operatorname{VAR}(G_k|X_k)\leq M$

2、收敛性定理#

定理（SGD 强凸情形）：

SGD 以 Q-线性速率收敛到残差： 设条件数 $\kappa = L/\gamma$，则

• $k \to \infty$ 时，极限误差为 $\frac{\eta M}{2\gamma}$，依赖噪声和步长。

证明：

由基础引理（L-光滑且 $\gamma$-强凸）：

取 $\alpha_k = \eta/L$，代入得

记 $\kappa = L/\gamma$，则 $1 - \frac{\gamma \eta}{L} = 1 - \frac{\eta}{\kappa}$，上式变为

递归展开（不等式迭代 $k$ 次）：

等比数列求和，$\sum_{i=0}^{k-1} r^i = \frac{1 - r^k}{1 - r}$，其中 $r = 1 - \frac{\eta}{\kappa}$，所以

代入得

化简右侧第二项：

最终得

证毕。