随机梯度下降初步
本文主要初步介绍随机梯度下降（Stochastic Gradient Descent, SGD）算法及其 mini-batch 变种的基本原理、假设与数学性质。
1 引言
一般而言，机器学习模型的训练过程可以建模为以下随机优化问题（Stochastic Optimization Problem），其目标是最小化在数据分布上的期望风险（Expected Risk）：
\[ \min_{\theta \in \mathbb{R}^d} F(\theta) = \mathbb{E}_{z \sim \mathcal{D}} [\ell(z; \theta)] \]
其中：
- \(\theta \in \mathbb{R}^d\) 为模型参数
- \(z\) 为服从分布 \(\mathcal{D}\) 的随机样本，在监督学习中通常表示为 \((x, y)\) 格式的样本-标签对。
- \(\ell(\cdot; \theta)\) 为单样本损失函数。
由于数据分布 \(\mathcal{D}\) 通常未知或数据量极其庞大，直接计算上述期望往往不可行。而传统的确定性梯度下降算法（Gradient Descent Method）需要遍历所有数据来计算精确梯度 \(\nabla F(\theta)\)，在大数据场景下不再适用。
那么有什么好的办法求解这一类优化问题吗？我们换一个角度来看待这个问题。我们知道，“极小化目标函数”往往与“求解目标函数梯度零点”有关。即寻找方程 \[ M(\theta) \triangleq \nabla F(\theta) = 0 \] 的根 \(\theta^*\)。正如上文所说，由于数据分布 \(\mathcal{D}\) 通常未知或数据量极其庞大，我们一般无法直接获得它的解析式或精确值，一般的非线性方程方程求解数值方法也无法直接应用。
1951 年 Robbins 和 Monro 提出一种随机逼近（Stochastic Approximation）方法求解这类问题(Robbins 和 Monro 1951)。这就是随机梯度下降（Stochastic Gradient Descent, SGD）算法的理论基础。
为了加深理解，我们可以先看看论文中原始问题的形式，再对应回我们的随机优化问题。具体地，任意给定参数 \(\theta\in \mathbb{R}\)， 如果它都对应一个随机变量 \(Y= Y(\theta)\)，且其分布函数为 \(H(y \mid \theta)\)，我们可以定义 \[ M(\theta) = \mathbb{E}[Y(\theta)] = \int_{-\infty}^{\infty} y \, dH(y \mid \theta) \] 进而可以定义一个非线性方程 \[ M(\theta) = \alpha \] 当我们对\(H(y \mid \theta)\)以及\(M(\theta)\)都不甚了解时，传统的数值方法很难求解该方程的根。但是Robbins 和 Monro 提出了一种迭代算法，并证明了在一定假设条件下，这一算法产生的参数序列会以2阶矩收敛到方程 \(M(\theta) = \alpha\) 的根，进而以概率收敛。 这种算法首先初始化一个参数值 \(\theta_0\)，以及一个步长序列 \(\{\eta_t\}\)，然后通过以下迭代公式更新参数： \[ \theta_{t+1} = \theta_t + \eta_t(\alpha - y_t) \] 其中 \(y_t\) 满足 \(\Pr\{y_t \leq y \mid \theta_t\} = H(y \mid \theta_t)\)。在实际使用时，\(y_t\)可以通过对随机变量 \(Y(\theta_t)\)进行抽样获得。
将这一理论框架应用到机器学习中的随机优化问题时，我们可以做如下对应：
我们要解的是 \(M(\theta) \triangleq \nabla F(\theta) =0\)，其中\(F(\theta) = \mathbb{E}_{z \sim \mathcal{D}} [\ell(z; \theta)]\)。
由于 \(\nabla F(\theta) = \nabla_\theta \mathbb{E}_{z \sim \mathcal{D}} [\ell(z; \theta)] = \mathbb{E}_{z \sim \mathcal{D}} [\nabla_\theta \ell(z; \theta)]\)，因此 \(Y(\theta)\) 可以对应随机样本损失函数的梯度 \(\nabla \ell(z; \theta)\)， \(y_t\) 对应梯度的随机估计量，即 \(y_t =\nabla \ell(z_t; \theta)\)，其中 \(z_t\) 是从数据分布 \(\mathcal{D}\) 中抽取的随机样本。
在这种对应关系下，迭代公式变为： \[ \theta_{t+1} = \theta_t - \eta_t \nabla \ell(z_t; \theta_t) \]
这正是随机梯度下降（SGD）算法的基本形式。
实际情况中，数据通常是以有限数据集 \(\mathcal{D} = \{z_i\}_{i=1}^N\) 的形式给出（但是规模很大），此时期望风险可以近似为经验风险： \[ F(\theta) \approx \hat{F}(\theta) = \frac{1}{N} \sum_{i=1}^N \ell(z_i; \theta) \]
2 随机梯度下降算法
需要指出的是，在论文(Robbins 和 Monro 1951) 中，为了证明迭代序列收敛到方程 \(M(\theta)=\alpha\) 的唯一根，作者采用了一系列有些“苛刻”的条件：例如问题是一维的、\(M(\theta)\) 在某种意义上单调且根唯一、\(Y(\theta)\) 在所有 \(\theta\) 上几乎处处一致有界，以及步长序列 \(\{\eta_t\}\) 满足 \[ \sum_{t=0}^\infty \eta_t = \infty,\qquad \sum_{t=0}^\infty \eta_t^2 < \infty. \] 等。在这些条件下，经典随机逼近理论可以证明 \(\{\theta_t\}\) 以二阶矩收敛。
如今随机梯度下降算法应用的问题维度已经不局限于一维，数据统计性质也远比“一致有界”要复杂得多。第 \(t\) 个迭代点 \(\theta_t\) 上使用的随机梯度也不仅仅局限于单个抽样样本的梯度，而是被推广到一种叫做梯度估计器（Oracle）的概念上，它代表一种机制（mechanism），这种机制在输入第 \(t\) 步迭代点 \(\theta_t\) 及其对应的随机性 \(z_t\) 后会返回一个估计量。它可以是单样本的梯度、或者是mini-batch 梯度（见下文）以及其它变种。我们将这种机制记作 \(g(\theta_t;z_t)\)，为了符号的简便性，在不至引起混淆的情况下，后文有时会使用符号 \(g(\theta_t)\)。
为了分析SGD算法的收敛性，现阶段人们常常使用以下假设：
目标函数的光滑性与（强）凸性假设：\(F\) 在整个参数空间上可微，且梯度满足 Lipschitz 连续。有时候会要求\(F\)是（强）凸函数。在强凸情形下，极小点若存在则唯一。值得注意的是，凸函数的梯度满足单调性条件，即对于任意 \(\theta_1, \theta_2 \in \mathbb{R}^d\)，都有 \[ (\nabla F(\theta_1) - \nabla F(\theta_2))^\top (\theta_1 - \theta_2) \geq 0. \]
随机梯度的无偏性假设：给定当前参数 \(\theta_t\)，梯度估计器 \(g(\theta_t)\) 满足 \[ \mathbb{E}[g(\theta_t)] = \nabla F(\theta_t), \] 即在条件期望意义下，随机梯度与真实梯度一致。
噪声方差（或二阶矩）有界假设：随机梯度与真实梯度之间的偏差具有有界的二阶矩，即存在常数 \(\sigma^2\)，使得 \[ \mathbb{E}\bigl[\|g(\theta_t) - \nabla F(\theta_t)\|^2 \mid \theta_t\bigr] \leq \sigma^2, \] 或者更一般地，存在常数 \(A, B \geq 0\)，使得 \[ \mathbb{E}\bigl[\|g(\theta_t) - \nabla F(\theta_t)\|^2 \mid \theta_t\bigr] \leq A + B \|\nabla F(\theta_t)\|^2. \]
这些假设可以看作是对 Robbins–Monro 框架核心结构的保留，同时对收敛条件进行了系统的推广和弱化。
随机梯度下降算法的迭代格式可以写作： \[ \theta_{t+1} = \theta_t - \eta_t \, g(\theta_t), \]
例如经典的单样本 SGD 中，梯度估计量 \(g(\theta_t)\) 取为单个随机样本的梯度： \[ g(\theta_t) = \nabla_\theta \ell(z_t; \theta_t), \] 其中 \(z_t\) 是从数据分布 \(\mathcal{D}\) 中抽取的随机样本。
2.1 Mini-batch SGD：有放回抽样情形
经典的单样本 SGD 每次仅使用一个样本计算梯度，虽然计算成本低，但引入的噪声可能较大（方差 \(\sigma^2\) 较大），容易导致迭代轨迹剧烈震荡，且难以利用现代硬件的并行计算能力。小批量随机梯度下降（Mini-batch SGD）通过每次迭代使用 \(M\) 个样本来计算梯度，是单样本 SGD 的自然推广。
设第 \(t\) 次迭代中，有放回地独立采样得到 \(M\) 个样本 \[ \mathcal{B}_t = \{z_{t,1}, \ldots, z_{t,M}\}, \] 其中 \(z_{t,1},\dots,z_{t,M} \overset{\text{i.i.d.}}{\sim} \mathcal{D}\)。 将梯度估计量定义为这批样本梯度的均值： \[ g^{(M)}(\theta_t) = \frac{1}{M} \sum_{i=1}^M \nabla_\theta \ell(z_{t,i}; \theta_t). \]
我们可以证明：若单样本梯度满足前述的无偏性与方差有界性假设，那么 Mini-batch 梯度估计量 \(g^{(M)}(\theta_t)\) 必然满足同样的无偏性假设，且其方差上界更小。 为简化记号，在下面的推导中，不失一般性，我们固定某个迭代步 \(t\) 和参数 \(\theta_t\)，记单样本梯度以及全量梯度为： \[ g(z) \triangleq \nabla_\theta \ell(z;\theta_t),\qquad \nabla F \triangleq \nabla F(\theta_t). \] 这样 \[ g^{(M)}(\theta_t) = \frac{1}{M}\sum_{i=1}^M g(z_{t,i}). \]
2.1.1 无偏性的保持
设单样本梯度是无偏的，即 \[ \mathbb{E}_{z\sim\mathcal{D}}[g(z)] = \nabla F. \] 由于期望是线性的，且样本 \(z_{t,1},\dots,z_{t,M}\) 相互独立、服从分布 \(\mathcal{D}\)，我们有： \[ \begin{aligned} \mathbb{E}[g^{(M)}(\theta_t)] &= \mathbb{E}\left[ \frac{1}{M} \sum_{i=1}^M g(z_{t,i}) \right] \\ &= \frac{1}{M} \sum_{i=1}^M \mathbb{E}[g(z_{t,i})] \\ &= \frac{1}{M} \cdot M \cdot \nabla F \\ &= \nabla F. \end{aligned} \]
这表明 Mini-batch 梯度继承了无偏性，依然是真实梯度的正确估计： \[ \boxed{\mathbb{E}[g_t^{(M)}(\theta_t)] = \nabla F(\theta_t).} \]
2.1.2 方差的有界性
假设单样本梯度的噪声方差有界，即存在常数 \(\sigma^2\) 使得 \[ \mathbb{E}\bigl[\|g(z) - \nabla F(\theta_t)\|^2\bigr] \leq \sigma^2. \]
定义第 \(i\) 个样本的梯度噪声为 \[ X_i \triangleq g(z_{t,i}) - \nabla F(\theta_t). \] 则有 \(\mathbb{E}[X_i]=0\)，且 \(X_1,\dots,X_M\) 相互独立、同分布。此时 \[ g_t^{(M)}(\theta_t) - \nabla F(\theta_t) = \frac1M \sum_{i=1}^M X_i. \]
我们关心的是
\[
\mathbb{E}\bigl[\|g_t^{(M)} - \nabla F\|^2\bigr]
= \mathbb{E}\left\|\frac1M \sum_{i=1}^M X_i\right\|^2.
\]
注意到有恒等式 \[ \left\|\sum_{i=1}^M X_i\right\|^2 = \sum_{i=1}^M \|X_i\|^2 + 2\sum_{i<j} \langle X_i,X_j\rangle. \]
两边取期望： \[ \mathbb{E}\left\|\sum_{i=1}^M X_i\right\|^2 = \sum_{i=1}^M \mathbb{E}\|X_i\|^2 + 2\sum_{i<j} \mathbb{E}\langle X_i,X_j\rangle. \]
由于 \(X_i\) 与 \(X_j\) 独立，且 \(\mathbb{E}[X_i]=0\)，有 \[ \mathbb{E}\langle X_i,X_j\rangle = \mathbb{E}\bigl[X_i^\top X_j\bigr] = \mathbb{E}\bigl[X_i^\top \mathbb{E}(X_j\mid X_i)\bigr] = \mathbb{E}\bigl[X_i^\top \mathbb{E}(X_j)\bigr] = \mathbb{E}\bigl[X_i^\top 0\bigr] = 0. \] 因此所有交叉项的期望为 \(0\)，于是 \[ \mathbb{E}\left\|\sum_{i=1}^M X_i\right\|^2 = \sum_{i=1}^M \mathbb{E}\|X_i\|^2. \]
由于各 \(X_i\) 同分布， \[ \mathbb{E}\|X_i\|^2 = \mathbb{E}\|X_1\|^2 = \mathbb{E}\|g(z)-\nabla F(\theta_t)\|^2 \le \sigma^2. \] 于是 \[ \mathbb{E}\left\|\sum_{i=1}^M X_i\right\|^2 \le M \sigma^2. \]
回到我们要算的量： \[ \begin{aligned} \mathbb{E}\bigl[\|g_t^{(M)}(\theta_t) - \nabla F(\theta_t)\|^2\bigr] &= \mathbb{E}\left\|\frac1M \sum_{i=1}^M X_i\right\|^2 \\ &= \frac{1}{M^2} \mathbb{E}\left\|\sum_{i=1}^M X_i\right\|^2 \\ &\le \frac{1}{M^2}\cdot M \sigma^2 \\ &= \frac{\sigma^2}{M}. \end{aligned} \]
因此，在有放回抽样下，若单样本梯度噪声满足 \[ \mathbb{E}\bigl[\|g(z)- \nabla F(\theta_t)\|^2\bigr] \le \sigma^2, \] 则对应的 mini-batch 梯度估计量满足 \[ \boxed{ \mathbb{E}\bigl[\|g_t^{(M)}(\theta_t) - \nabla F(\theta_t)\|^2 \mid \theta_t\bigr] \le \frac{\sigma^2}{M}. } \]
由于 \(M \ge 1\)，显然 \(\frac{\sigma^2}{M} \le \sigma^2\)。这说明 Mini-batch SGD 不仅满足方差有界假设，而且将梯度估计的方差显著降低了 \(M\) 倍。这意味着在相同的迭代步数下，Mini-batch 算法能提供更稳定的梯度方向，从而支持使用更大的步长 \(\eta_t\) 并加速收敛。
2.2 无放回抽样与有限总体校正 (Finite Population Correction)
上面的 \(\frac{\sigma^2}{M}\) 方差界在理论分析中被广泛使用，但它隐式地依赖于有放回抽样（sampling with replacement）假设，即每次抽取的样本之间是相互独立的。
我们提到过在实际情况中，数据通常是以有限数据集 \(\mathcal{D} = \{z_i\}_{i=1}^N\) 的形式给出（但是规模很大），此时我们通常考虑经验风险： \[ F(\theta) \approx \hat{F}(\theta) = \frac{1}{N} \sum_{i=1}^N \ell(z_i; \theta) \] 在主流深度学习框架（如 PyTorch, TensorFlow）的工程实现中，通常采用无放回抽样（sampling without replacement）策略：即在每个 epoch 开始时打乱数据集（shuffle），然后将数据切分为若干个不重叠的小批量。
这就引出了一个这么一件事情：
如果严格套用 \(\frac{\sigma^2}{M}\) 的公式，当批次大小 \(M\) 等于数据集大小 \(N\) 时，梯度估计的方差为 \(\frac{\sigma^2}{N}\)。由于 \(\sigma^2 > 0\)，这意味着全量梯度（full batch gradient）的方差上界仍然大于零。 但事实上，全量梯度 \[ \nabla \hat F(\theta) = \frac{1}{N}\sum_{i=1}^N \nabla \ell(z_i;\theta) \] 是一个确定性的向量，其方差应为 0。
这实际上是因为无放回抽样下，抽样得到的样本并不独立。为了更准确地描述 Mini-batch SGD 在实际工程中的行为，我们需要引入统计学中的有限总体校正（Finite Population Correction, FPC）。
2.2.1 数学设定
考虑一个有限数据集 \[ \mathcal{D} = \{z_1,\dots,z_N\}. \] 对于固定的参数 \(\theta\)，所有样本的梯度构成了一个有限总体： \[ \mathcal{G} = \{g_1,\dots,g_N\}, \qquad g_i \triangleq \nabla \ell(z_i;\theta). \]
定义样本平均（即经验风险的全量梯度）为 \[ \nabla \hat F(\theta) = \frac{1}{N}\sum_{i=1}^N g_i, \] 并定义样本方差为（这里使用的是无偏方差）： \[ \sigma^2(\theta) \triangleq \frac{1}{N-1}\sum_{i=1}^N \|g_i - \nabla \hat F(\theta)\|^2. \]
下面我们关心的是：从 \(\{1,\dots,N\}\) 中无放回抽取一个大小为 \(M\) 的子集 \(S\)，定义 mini-batch 梯度 \[ g_t^{(M)} = \frac{1}{M}\sum_{i\in S} g_i, \] 那么 \[ \mathbb{E}\bigl[\|g_t^{(M)} - \nabla \hat F(\theta)\|^2\bigr] \] 的精确形式是什么。
2.2.2 标量情形的有限总体校正
由于样本梯度往往是以向量形式存在的（\(d>1\))。为了把思路讲清楚，我们先看一维标量情况。设有固定的样本（标量）： \[ x_1,\dots,x_N, \] 定义样本均值 \[ \bar{x} = \frac{1}{N}\sum_{i=1}^N x_i, \] 以及样本（无偏）方差 \[ S^2 = \frac{1}{N-1}\sum_{i=1}^N (x_i - \bar{x})^2. \]
从中无放回抽取 \(M\) 个索引构成子集 \(S\)，样本均值为 \[ \bar X = \frac{1}{M}\sum_{i\in S} x_i. \]
引入指示变量 \[ \xi_i \triangleq \begin{cases} 1, & i\in S,\\ 0, & i\notin S, \end{cases} \qquad i=1,\dots,N. \] 则 \[ \bar X = \frac{1}{M}\sum_{i=1}^N \xi_i x_i. \]
注意 \[ \mathbb{E}[\xi_i] = \Pr(i\in S) = \frac{M}{N}. \] 一个简单的计算可以验证无偏性： \[ \mathbb{E}[\bar X] = \frac{1}{M}\sum_{i=1}^N x_i\,\mathbb{E}[\xi_i] = \frac{1}{M}\cdot\frac{M}{N}\sum_{i=1}^N x_i = \bar{x}. \]
现在我们计算 \(\mathbb{E}[(\bar X - \bar{x})^2]\)。令 \[ y_i \triangleq x_i - \bar{x},\qquad \sum_{i=1}^N y_i = 0, \] 则 \[ \bar X - \bar{x} = \frac{1}{M}\sum_{i=1}^N \xi_i y_i. \]
于是 \[ (\bar X - \bar{x})^2 = \frac{1}{M^2}\left(\sum_{i=1}^N \xi_i y_i\right)^2 = \frac{1}{M^2}\left( \sum_{i=1}^N \xi_i y_i^2 + 2\sum_{1\le i<j\le N} \xi_i\xi_j y_i y_j \right). \]
对上式取期望： \[ \mathbb{E}[(\bar X - \bar{x})^2] = \frac{1}{M^2}\left( \sum_{i=1}^N \mathbb{E}[\xi_i] y_i^2 + 2\sum_{i<j} \mathbb{E}[\xi_i\xi_j] y_i y_j \right). \]
我们已经知道 \(\mathbb{E}[\xi_i]=\frac{M}{N}\)。对于 \(i\neq j\)，\(\xi_i\xi_j=1\) 当且仅当 \(i\) 和 \(j\) 都被选中。注意到无放回等概率抽样下，任意指定两个元素同时被选中的概率为 \[ \Pr(i\in S,\;j\in S) = \frac{\binom{N-2}{M-2}}{\binom{N}{M}} = \frac{M(M-1)}{N(N-1)}, \] 因此 \[ \mathbb{E}[\xi_i\xi_j]= \mathbb{E}[\mathbb{1}_{\{i\in S,j\in S\}}] = \Pr(i\in S,\;j\in S) = \frac{M(M-1)}{N(N-1)},\qquad i\neq j. \]
代入得到 \[ \begin{aligned} \mathbb{E}[(\bar X - \bar{x})^2] &= \frac{1}{M^2}\left( \frac{M}{N}\sum_{i=1}^N y_i^2 + 2\cdot\frac{M(M-1)}{N(N-1)}\sum_{i<j} y_i y_j \right). \end{aligned} \]
利用恒等式 \[ \left(\sum_{i=1}^N y_i\right)^2 = \sum_{i=1}^N y_i^2 + 2\sum_{i<j} y_i y_j = 0, \] 可得 \[ \sum_{i<j} y_i y_j = -\frac12\sum_{i=1}^N y_i^2. \]
代回： \[ \begin{aligned} \mathbb{E}[(\bar X - \bar{x})^2] &= \frac{1}{M^2}\left( \frac{M}{N}\sum_i y_i^2 + 2\cdot\frac{M(M-1)}{N(N-1)}\cdot\left(-\frac12\sum_i y_i^2\right) \right) \\ &= \frac{1}{M^2}\left[ \frac{M}{N} - \frac{M(M-1)}{N(N-1)} \right]\sum_i y_i^2 \\ &= \frac{1}{M^2}\cdot\frac{M}{N}\cdot\frac{N-M}{N-1}\sum_i y_i^2 \\ &= \frac{1}{M}\cdot\frac{N-M}{N}\cdot\frac{1}{N-1}\sum_i y_i^2. \end{aligned} \]
注意到 \[ S^2 = \frac{1}{N-1}\sum_{i=1}^N (x_i - \bar{x})^2 = \frac{1}{N-1}\sum_i y_i^2, \] 于是得到著名的有限总体校正公式： \[ \boxed{ \mathbb{E}[(\bar X - \bar{x})^2] = \frac{1}{M}\left(1 - \frac{M}{N}\right)\,S^2. } \]
与有放回抽样的 \(\frac{S^2}{M}\) 相比，这里多了一个 \[ 1 - \frac{M}{N} \in (0,1] \] 的校正因子。当 \(M\ll N\) 时，该因子接近 \(1\)，无放回与有放回几乎没有区别；当 \(M\to N\) 时，该因子趋近 \(0\)，方差也趋于 \(0\)，与“全批次梯度是确定性的”这一事实完全吻合。
2.2.3 向量梯度情形的有限总体校正
回到向量梯度的情形。注意到我们定义了 \[ g_i \triangleq \nabla \ell(z_i;\theta),\qquad \nabla \hat F(\theta) = \frac{1}{N}\sum_{i=1}^N g_i. \] 设无放回抽取样本量大小为 \(M\) 的样本集合 \(S\)，则mini-batch 梯度为 \[ g_t^{(M)} = \frac{1}{M}\sum_{i\in S} g_i. \]
我们关心的是 \[ \mathbb{E}\bigl[\|g_t^{(M)} - \nabla \hat F(\theta)\|^2\bigr] \] 是什么样的形式。
注意到 \[ \|g_t^{(M)} - \nabla \hat F\|^2 = \sum_{k=1}^d \bigl((g_t^{(M)})_k - \nabla \hat F_k\bigr)^2, \] 其中下标 \(k\) 表示向量的第 \(k\) 个坐标。因此 \[ \mathbb{E}\bigl[\|g_t^{(M)} - \nabla \hat F\|^2\bigr] = \sum_{k=1}^d \mathbb{E}\bigl[((g_t^{(M)})_k - \nabla \hat F_k)^2\bigr]. \]
不失一般性，考虑第 \(k\) 个坐标分量，我们令 \[ x_i = (g_i)_{k},\qquad \bar{x}_k = \frac{1}{N}\sum_{i=1}^N x_i = \nabla \hat F_k, \] 应用上一节的一维结果，得到 \[ \mathbb{E}\bigl[((g_t^{(M)})_k - \nabla \hat F_k)^2\bigr] = \frac{1}{M}\left(1 - \frac{M}{N}\right) S_k^2, \] 其中 \[ S_k^2 = \frac{1}{N-1}\sum_{i=1}^N (g_i^{(k)} - \nabla \hat F_k)^2. \]
因此 \[ \begin{aligned} \mathbb{E}\bigl[\|g_t^{(M)} - \nabla \hat F\|^2\bigr] &= \sum_{k=1}^d \frac{1}{M}\left(1 - \frac{M}{N}\right) S_k^2 \\ &= \frac{1}{M}\left(1 - \frac{M}{N}\right)\sum_{k=1}^d S_k^2. \end{aligned} \]
而 \[ \sum_{k=1}^d S_k^2 = \sum_{k=1}^d \frac{1}{N-1}\sum_{i=1}^N (g_i^{(k)} - \nabla \hat F_k)^2 = \frac{1}{N-1}\sum_{i=1}^N \sum_{k=1}^d (g_i^{(k)} - \nabla \hat F_k)^2 = \frac{1}{N-1}\sum_{i=1}^N \|g_i - \nabla \hat F\|^2. \]
因此我们得到向量版的有限总体校正公式： \[ \boxed{ \mathbb{E}\bigl[\|g_t^{(M)} - \nabla \hat F(\theta)\|^2\bigr] = \frac{1}{M}\left(1 - \frac{M}{N}\right) \cdot \frac{1}{N-1}\sum_{i=1}^N \|g_i - \nabla \hat F(\theta)\|^2. } \]
如果我们假设样本总体梯度的方差有统一上界，即存在常数 \(\sigma^2\) 使得对所有 \(\theta\) 都有 \[ \frac{1}{N-1}\sum_{i=1}^N \|\nabla \ell(z_i;\theta) - \nabla \hat F(\theta)\|^2 \le \sigma^2, \] 那么无放回 mini-batch 梯度满足 \[ \boxed{ \mathbb{E}\bigl[\|g_t^{(M)} - \nabla \hat F(\theta)\|^2\bigr] \le \frac{1}{M}\left(1 - \frac{M}{N}\right)\sigma^2. } \]
与有放回采样的 \(\frac{\sigma^2}{M}\) 相比，无放回多了一个 \[ \left(1 - \frac{M}{N}\right) \] 的有限总体校正因子。它有三个直接的含义：
- 当 \(M=1\) 时，校正因子为 \(1\)，退化为单样本 SGD 的方差 \(\sigma^2\)；
- 当 \(M\ll N\) 时，\(\frac{M}{N}\) 很小，校正因子接近 \(1\)，无放回与有放回几乎没有区别，这也是大数据场景下常见的近似；
- 当 \(M=N\) 时，校正因子为 \(0\)，从而 \(\mathbb{E}\|g_t^{(N)} - \nabla \hat F(\theta)\|^2 = 0\)，即 full-batch 梯度是确定的，没有随机性，更准确地描述了 Mini-batch SGD 在实际工程中的行为。
综上所述，我们可以把 mini-batch SGD 在有限样本情形下的无偏性与方差假设统一写成：
- 有放回抽样时： \[ \mathbb{E}[g_t^{(M)}(\theta_t)] = \nabla \hat F(\theta_t), \qquad \mathbb{E}\bigl[\|g_t^{(M)}(\theta_t) - \nabla \hat F(\theta_t)\|^2\bigr] \le \frac{\sigma^2}{M}; \]
- 无放回抽样时： \[ \mathbb{E}[g_t^{(M)}(\theta_t)] = \nabla \hat F(\theta_t), \qquad \mathbb{E}\bigl[\|g_t^{(M)}(\theta_t) - \nabla \hat F(\theta_t)\|^2\bigr] \le \frac{1}{M}\left(1 - \frac{M}{N}\right)\sigma^2. \]