Exercises — Mini-batch gradient descent

• $N$ ::: total number of training examples.
• $m$ ::: the batch size — how many examples we average over per step.
• $\theta$ ::: the network's parameters (the numbers we tune).
• ${\ell }_i$ ::: the loss on one example $i$; ${\nabla }_{\theta }{\ell }_i$ is its per-example gradient.
• $J(\theta )=\frac{1}{N}{\sum }_i{\ell }_i$ ::: the average loss over the whole dataset.
• $g_{\mathcal{B}}=\frac{1}{m}{\sum }_{i\in \mathcal{B}}{\nabla }_{\theta }{\ell }_i$ ::: the mini-batch gradient estimate.
• $\eta$ ::: the learning rate (step size).
• $\sigma$ ::: per-example gradient standard deviation (how "spread out" the $g_i$ are).
• epoch ::: one full pass over the whole dataset.

WHAT we do: match each $m$ to its position on the batch-size spectrum.

• (a) $m=1$ → Stochastic Gradient Descent (SGD) — one example per step, noisiest. See Stochastic Gradient Descent.
• (b) $m=N$ → Batch (full) gradient descent — exact gradient, one step per epoch. See Gradient Descent.
• (c) $1<m\ll N$ → Mini-batch gradient descent — the practical sweet spot. WHY: the only thing that distinguishes these three named methods is the value of $m$ relative to $N$.

Steps per epoch $=\lceil N/m\rceil =\lceil 1000/100\rceil =10$. WHY the ceiling $\lceil \cdot \rceil$: if the last batch is a leftover of fewer than $m$ examples, we still take a step on it, so we round up. Here $1000/100=10$ exactly, so no leftover — the answer is simply $10$.

Full batches: $\lfloor 50000/128\rfloor =390$ full batches of 128. Those cover $390\times 128=49920$ examples. Leftover: $50000-49920=80$ examples form one final (short) batch. Total updates: $390+1=\lceil 50000/128\rceil =391$. WHY it matters: with drop_last=True you'd throw away those 80 examples and get $390$ updates; otherwise you keep them and get $391$. Either way, it's 391 (or 390) updates vs 1 for full-batch — that's the whole point of mini-batching.

WHAT tool and WHY: the parent derived $\mathrm{std}(g_{\mathcal{B}})=\sigma /\sqrt{m}$. We use it because it directly tells us how spread shrinks with batch size.

• $m=9$: $6/\sqrt{9}=6/3=2.0$
• $m=36$: $6/\sqrt{36}=6/6=1.0$ Noise dropped by factor $2.0/1.0=2\times$. Compute rose by factor $36/9=4\times$ (we processed 4× more examples). WHY this is the lesson: $4\times$ the cost bought only $2\times$ less noise. That's the diminishing-returns face of $1/\sqrt{m}$.

(a) True gradient $=\frac{3+(-1)+5+(-3)}{4}=\frac{4}{4}=1$. (b) $\{x_1,x_4\}:\frac{3+(-3)}{2}=0$. $\{x_2,x_3\}:\frac{-1+5}{2}=2$. (c) Average of the two batches $=\frac{0+2}{2}=1$ — the true gradient exactly. WHY: each batch alone is "wrong" (0, then 2), yet these two batches together tile all four examples once each, so their average must equal the full mean. This is unbiasedness in miniature: individual steps mislead, the ensemble is honest.

WHAT/WHY: Team A's noise is $\sigma /\sqrt{m}=10/\sqrt{25}=2$. Team B wants $2/2=1$. Solve $10/\sqrt{m_B}=1\Rightarrow \sqrt{m_B}=10\Rightarrow m_B=100$. Cross-check with the law: to halve noise you must quadruple the batch, and indeed $100=4\times 25$. ✓ The takeaway: halving noise always costs a $4\times$ larger batch, because noise $\propto 1/\sqrt{m}$ and $(2{)}^2=4$.

No. Look at the figure: the thin blue line (per-step mini-batch loss) genuinely rises at several steps, but the thick orange line (running/epoch average) falls steadily. WHY steps can go up: each step uses $g_{\mathcal{B}}$, not the true gradient $\nabla J$. Sometimes a batch's gradient points slightly wrong, and ${\theta }_{t+1}={\theta }_t-\eta g_{\mathcal{B}}$ momentarily increases the true loss. Over many steps the noise cancels (unbiasedness) and the average descends. The correct diagnosis rule: judge progress by the running / epoch average, never a single noisy step.

Noise ratio $=\frac{\sigma /\sqrt{64}}{\sigma /\sqrt{1024}}=\sqrt{\frac{1024}{64}}=\sqrt{16}=4$. So $16\times$ compute buys only a $4\times$ noise reduction. WHY not worth it (on noise alone): $1/\sqrt{m}$ means gains grow only as the square root of cost — a classic diminishing return. Worse, the parent warns that losing the helpful mini-batch noise can hurt generalisation by steering you toward sharp minima — see Generalization and Flat Minima. Big batches usually pay off only when combined with LR scaling and warmup.

The rule: if you multiply $m$ by $k$, multiply $\eta$ by $\approx k$. Here $k=256/32=8$, so ${\eta }_{\text{new}}\approx 8\times 0.1=0.8$. WHY it works: a bigger batch gives a lower-variance gradient ($\sigma /\sqrt{m}$ smaller), so a bigger step is safe — you're more sure of the direction. See Learning Rate Scheduling. WHY warmup: at the very start $\theta$ is random and the loss surface is wild; a sudden $\eta =0.8$ can diverge. So we ramp $\eta$ up gradually over the first few epochs, then hold. Optimisers like Adam in Momentum and Adam further tame the transition.

WHAT breaks: with sorted data and no shuffle, early batches are all cats, later batches all dogs. Each batch's gradient $g_{\mathcal{B}}$ is then systematically pulled toward one class — it is not a random sample of the whole dataset. WHY the theory collapses: the parent's unbiasedness proof required each index in $\mathcal{B}$ to be drawn uniformly at random, giving $\mathbb{E}[g_{\mathcal{B}}]=\nabla J$. A "cats-only" batch violates that; its expectation is the cat gradient, not the full-data gradient. The estimator becomes biased, and the model oscillates (learn cats, forget them while learning dogs). The fix: shuffle every epoch so batches are approximately i.i.d. and the unbiasedness argument holds again.

(a) Updates: $m=100\Rightarrow \lceil 60000/100\rceil =600$ per epoch $\times 5=3000$ updates. $m=500\Rightarrow \lceil 60000/500\rceil =120$ per epoch $\times 5=600$ updates. (b) Examples processed: both do 5 full epochs, so both see $5\times 60000=300000$ examples. (c) Same data seen, but $m=100$ took $3000$ steps vs $600$ — 5× more parameter updates for the same data, so the small-batch run typically makes more progress per example (more, noisier nudges), while the big-batch run makes fewer, cleaner nudges.

(a) Updates per epoch $=\lceil 1200000/256\rceil$. Since $256\times 4687=1199872$, leftover $=128$, so $4687+1=4688$ updates per epoch. (b) Scaling factor $k=256/32=8\Rightarrow \eta \approx 8\times 0.05=0.4$ (with a short warmup ramp — see Learning Rate Scheduling). (c) Total updates $=4688\times 90=421,920$. (d) Why not $m=4096$: noise only falls as $1/\sqrt{m}$, so past a point extra batch buys almost no direction quality, updates-per-epoch collapse (fewer chances to adjust), and the vanishing gradient-noise can steer you into sharp minima that generalise worse (Generalization and Flat Minima). Moderate $m$ with scaled $\eta$ is the sweet spot.

(a) Derivation (WHAT/WHY each step): $\mathrm{Var}(g_{\mathcal{B}})=\mathrm{Var}\left(\frac{1}{m}{\sum }_{i=1}^m{g}_i\right)=\frac{1}{m^2}\mathrm{Var}\left({\sum }_{i=1}^m{g}_i\right)$ Why the $1/m^2$: scaling a random quantity by a constant $c$ scales its variance by $c^2$; here $c=1/m$. $=\frac{1}{m^2}{\sum }_{i=1}^m\mathrm{Var}(g_i)=\frac{1}{m^2}\cdot m{\sigma }^2=\frac{{\sigma }^2}{m}.$ Why the sum splits: independence makes the variance of a sum equal the sum of variances (cross-terms vanish). Taking $\sqrt{\cdot }$: $\mathrm{std}=\sigma /\sqrt{m}$. (b) Prediction: want $\sigma /\sqrt{m}=\sigma /10\Rightarrow \sqrt{m}=10\Rightarrow m=100$. Sanity: to shrink noise $10\times$ you pay $10^2=100$ examples — the square-law bites hard, which is exactly why nobody chases tiny gradient noise.

Diagnosis: the batch grew $1024/32=32\times$ but $\eta$ stayed the same. The gradient is now $\sqrt{32}\approx 5.7\times$ less noisy yet each step is the same tiny size — so you're taking small, confident steps far too cautiously, wasting the extra information. Fewer updates per epoch compounds the crawl. Fix (two parts):

1. Scale the learning rate: $\eta \approx 32\times 0.05=1.6$ per the linear scaling rule (use warmup so it doesn't blow up early).
2. Add warmup + possibly momentum/Adam (Momentum and Adam) to keep the large-$\eta$ start stable. WHY it works: low-variance gradients justify larger steps; matching $\eta$ to $m$ restores per-epoch progress. Ignoring the scaling rule is the classic "big-batch training is slow" pitfall.

• Steps per epoch, $N=60000,m=500$? ::: $120$.
• Batch to make noise $=\sigma /10$? ::: $m=100$.
• Multiply $m$ by 8 — what to $\eta$? ::: multiply by $\approx 8$ (with warmup).
• Loss rose one step — broken? ::: No; batch noise. Judge the running average.
• Cost to halve gradient noise? ::: $4\times$ the batch size.