Md. Asif Uddin
    I.7.X10

    Why a minibatch gradient is the right one on average

    proof▲▲△

    Prove that the minibatch gradient is an unbiased estimator of the full-batch gradient, and derive its variance. State precisely which property of the sampling each half of the result requires, so it is clear what breaks when the sampling is wrong.

    Hint

    Linearity of expectation gives the first half and needs almost nothing. Independence is what the second half needs, and it is a strictly stronger assumption.

    Solution

    Setup. The full objective is the mean over NN examples, L(θ)=1N∑i=1Nℓi(θ)\mathcal{L}(\theta) = \frac{1}{N}\sum_{i=1}^{N}\ell_i(\theta), so ∇L=1N∑i∇ℓi\nabla\mathcal{L} = \frac{1}{N}\sum_i \nabla\ell_i. A batch is BB indices i1,…,iBi_1, \dots, i_B drawn uniformly at random with replacement, and

    g^B=1B∑j=1B∇ℓij\hat{g}_B = \frac{1}{B}\sum_{j=1}^{B}\nabla\ell_{i_j}

    Unbiasedness. For a single uniformly drawn index,

    E[∇ℓi]=∑k=1N1N∇ℓk=∇L\mathbb{E}[\nabla\ell_{i}] = \sum_{k=1}^{N}\frac{1}{N}\nabla\ell_k = \nabla\mathcal{L}

    By linearity of expectation — which requires no independence at all —

    E[g^B]=1B∑j=1BE[∇ℓij]=∇L\mathbb{E}[\hat{g}_B] = \frac{1}{B}\sum_{j=1}^{B}\mathbb{E}[\nabla\ell_{i_j}] = \nabla\mathcal{L}

    The only property used is that each index is marginally uniform. This is why unbiasedness survives sampling without replacement, and why it fails under the sorted batches of I.7.X05 — there the marginal distribution of an index within batch 1 is uniform over class 0 only.

    Variance. Write Σ=Var⁡[∇ℓi]\Sigma = \operatorname{Var}[\nabla\ell_i] for the per-example covariance. Now independence is needed: for independent draws the variance of a sum is the sum of the variances, so

    Var⁡[g^B]=1B2∑j=1BΣ=ΣB\operatorname{Var}[\hat{g}_B] = \frac{1}{B^2}\sum_{j=1}^{B}\Sigma = \frac{\Sigma}{B}

    which is (I.7.2). The standard error is σ/B\sigma/\sqrt{B}.

    What each half needs. Unbiasedness needs marginal uniformity. Variance needs independence between the draws. The gap between them is the whole reason correlated batches are dangerous: a batch of near-duplicate examples can still be unbiased while having a variance far above Σ/B\Sigma/B, so the 1/B1/B accounting overstates how much noise the batch removed. Deduplication is a variance intervention, not only a data-hygiene one.

    Sampling without replacement. Real training shuffles and takes disjoint batches, which is sampling without replacement. Unbiasedness is unaffected. The variance gains a finite-population correction N−BN−1\frac{N-B}{N-1}, which is negligible while B≪NB \ll N and becomes decisive as B→NB \to N — at B=NB = N the variance is zero, because the batch is the dataset. The 1/B1/B law is the large-NN limit, and full-batch descent is its other end.

    The consequence for practice. Halving the noise costs four times the arithmetic, so the returns are square-root. That single fact is why batch size is a trade rather than a setting to maximise, and why the critical batch size of McCandlish and colleagues exists: past the point where the gradient is already accurate, additional examples buy accuracy nobody needed.

    Draws on