Exercises — Stochastic gradient descent (SGD)

Compare each batch size $m$ to $N=1000$.

• (a) averages over all $1000$ → $m=N$ → Full-batch GD.
• (b) uses a single example → $m=1$ → pure (online) SGD.
• (c) uses $32$ of $1000$, so $1<m<N$ → mini-batch SGD. What it looks like: (a) is one smooth expensive step, (b) is a wildly jittery cheap step, (c) is the practical middle.

One epoch = one full sweep = $N/m$ updates. $\frac{N}{m}=\frac{50000}{250}=200\text{ updates per epoch}.$ Over $8$ epochs: $200\times 8=1600$ updates. Why: each update consumes one mini-batch of $m$ examples, and $N/m$ batches tile the whole dataset exactly once.

(a) False. With uniform random sampling $\mathbb{E}[g_{\mathcal{B}}]=\nabla L$ — it is unbiased. (b) True. Variance $={\sigma }^2/m$ (with ${\sigma }^2$ = per-example gradient variance from the definition above), so $m\to 2m$ makes it ${\sigma }^2/(2m)$ = half. (c) False. Noise never vanishes with fixed $\eta$; $\theta$ bounces in a ball of radius $\propto \eta$.

Each step: $\theta \leftarrow \theta -\eta (\theta -x)$.

• Draw $x_1=1$: $\nabla =0-1=-1$; ${\theta }_1=0-0.4(-1)=0.4$.
• Draw $x_2=5$: $\nabla =0.4-5=-4.6$; ${\theta }_2=0.4-0.4(-4.6)=0.4+1.84=2.24$.
• Draw $x_1=1$: $\nabla =2.24-1=1.24$; ${\theta }_3=2.24-0.4(1.24)=2.24-0.496=1.744$. What the figure below shows: read it left-to-right along the number line. The two orange dots are the data points $x_1=1$ and $x_2=5$; the violet star at $3$ is the true minimum. The magenta dots rising up the page are ${\theta }_0,{\theta }_1,{\theta }_2,{\theta }_3$ in order, and the magenta arrows are the actual jumps. Notice arrow 1 nudges right toward $x_1=1$, arrow 2 leaps far right toward $x_2=5$ (overshooting past $3$), and arrow 3 pulls back left toward $x_1=1$. The dotted vertical lines drop each $\theta$ onto the number line so you can read its value. Despite the zig-zag, every $\theta$ after the first sits inside the $[1,5]$ range and the values hover around the true mean $3$ — that is SGD's noisy-but-centered behaviour made visible.

Full gradient: $\nabla L=\frac{1}{2}[(\theta -1)+(\theta -5)]=\theta -3$. At ${\theta }_0=0$: $\nabla L=-3$. ${\theta }_1=0-0.4(-3)=\mathrm{1.2.}$ Why this contrasts: full-batch aims straight at $3$ in one clean move; SGD wobbles because each step only sees one point. Both are heading to $3$.

Variance $={\sigma }^2/m$, std-dev $=\sqrt{{\sigma }^2/m}$.

• $m=1$: var $=12$, std $=\sqrt{12}\approx 3.464$.
• $m=3$: var $=12/3=4$, std $=2$.
• $m=12$: var $=12/12=1$, std $=1$. Why: multiplying $m$ by $12$ cut the std-dev only from $3.464$ to $1$ (about $3.46\times$, i.e. $\sqrt{12}$) — diminishing returns.

Bounce distance $\propto$ std-dev $\propto \sigma /\sqrt{m}$. $\frac{\text{std}(m=32)}{\text{std}(m=8)}=\frac{\sigma /\sqrt{32}}{\sigma /\sqrt{8}}=\sqrt{\frac{8}{32}}=\sqrt{\frac{1}{4}}=\frac{1}{2}.$ So the bounce shrinks by a factor of 2 — while costing 4× the compute per step. Why it matters: $4\times$ cost buys only $2\times$ less jitter; this is the diminishing-returns story quantified.

First, the role of $k$: it must satisfy $k>0$ so the denominator $1+kt$ actually grows with the step count $t$ (if $k=0$ the rate never decays — that is just constant $\eta$; if $k<0$ the denominator eventually hits zero or flips sign and the rate blows up). Larger $k$ = faster decay = the rate cools down sooner. Crucially, $k$ only scales the sums by a constant — it changes how fast you converge, not whether the Robbins–Monro conditions hold. Write ${\eta }_t\sim \frac{{\eta }_0}{k}\cdot \frac{1}{t}$ for large $t$ (the constant offset $1$ doesn't change large-$t$ behaviour).

• ${\sum }_t{\eta }_t\sim \frac{{\eta }_0}{k}{\sum }_t\frac{1}{t}$ — the harmonic series diverges $\Rightarrow \sum {\eta }_t=\infty$. ✓ This buys: total travel distance is unbounded, so you can reach the minimum no matter how far.
• ${\sum }_t{\eta }_t^2\sim \frac{{\eta }_0^2}{k^2}{\sum }_t\frac{1}{t^2}$ — this is the p-series with $p=2$, which converges (to ${\eta }_0^2{\pi }^2/6k^2$-ish) $\Rightarrow \sum {\eta }_t^2<\infty$. ✓ This buys: steps shrink fast enough that accumulated noise is finite and averages out, so you actually stop bouncing. Why these two, not one? Diverging $\sum {\eta }_t$ alone could bounce forever; converging $\sum {\eta }_t^2$ alone could stall before reaching the min. Together: reach it and settle. The $1/t$ decay of this schedule is the slowest decay that still makes $\sum {\eta }_t^2$ converge — a knife-edge sweet spot; $k$ tunes the constant in front but cannot break either property. See Learning Rate Schedules.

Near the minimum the true gradient $\nabla L\approx 0$, so the update is dominated by the noise part of $g_{\mathcal{B}}$, whose typical size is $\propto \eta \cdot (\sigma /\sqrt{m})$. With fixed $\eta$ this size never shrinks, so $\theta$ keeps taking noise-driven steps of constant scale — a permanent wiggle in a ball of radius $\propto \eta$. With a decaying ${\eta }_t\to 0$, each noise kick gets smaller, and because $\sum {\eta }_t^2<\infty$ the total remaining wiggle is finite and vanishing — $\theta$ converges.

Scale factor $c=512/64=8$. New learning rate: ${\eta }_{\text{new}}=c\cdot \eta =8\times 0.1=\mathrm{0.8.}$ Intuition: a larger batch gives a less noisy gradient, so each step is more trustworthy — you can afford a bigger step. The linear rule targets keeping the total parameter movement per epoch roughly constant: with $c\times$ larger batches you take $c\times$ fewer updates per epoch, so each update must move $c\times$ farther to cover the same ground.

Updates per epoch $=N/m$; total over $10$ epochs $=10N/m$.

• $m=100$: $10\cdot 10^6/100=100000$ updates.
• $m=1000$: $10\cdot 10^6/1000=10000$ updates. So the big-batch run takes $10\times$ fewer steps in the same epoch budget. Linear scaling from base $(100,0.05)$ with $c=1000/100=10$: $\eta =10\times 0.05=\mathrm{0.5.}$ Why together: fewer, bigger, more-confident steps at a proportionally larger learning rate cover comparable distance — the synthesis of update-count, batch size and learning rate.

Flat minima are favoured by more gradient noise, which the network cannot "sit still" inside a narrow sharp basin.

1. Decrease batch size $m$. Noise variance $={\sigma }^2/m$ grows as $m$ shrinks → more exploration → escapes sharp basins. (See Batch Size and Generalization.)
2. Increase the learning rate $\eta$ (within stability). The effective noise injected per step scales with $\eta$, so a larger $\eta$ widens the bouncing ball and pushes SGD out of narrow minima. (See Learning Rate Schedules.) Both raise the temperature of SGD's random walk, biasing it toward wide, flat, generalizing basins — the implicit-regularization story linked to the Bias-Variance Tradeoff.

Exact gradient of the averaged loss is $\nabla L=\theta -\bar{x}=\theta -3$. Update: ${\theta }_{t+1}={\theta }_t-\eta ({\theta }_t-3).$ Subtract $3$ from both sides — this reveals the error $e_t={\theta }_t-3$: ${\theta }_{t+1}-3=({\theta }_t-3)-\eta ({\theta }_t-3)=(1-\eta )({\theta }_t-3).$ So $e_{t+1}=(1-\eta )e_t$: the error shrinks (or grows) by a constant factor $r=(1-\eta )$ each step — a geometric sequence, $e_t=r^t{e}_0$. With $\eta =0.4$, $r=0.6$:

• ${\theta }_0=0\Rightarrow e_0=-3$.
• ${\theta }_1=3+0.6(-3)=3-1.8=1.2$.
• ${\theta }_2=3+0.6(-1.8)=3-1.08=1.92$.
• ${\theta }_3=3+0.6(-1.08)=3-0.648=2.352$. Since $|r|=0.6<1$, $e_t\to 0$, so ${\theta }_t\to 3={\theta }^{\ast }$. What it looks like: smooth exponential glide to the minimum — no wobble, because full-batch has zero gradient noise here. All three regimes (governed by $|1-\eta |$):
• $|1-\eta |<1$ (i.e. $0<\eta <2$): error shrinks each step → converges to $3$. Within this, $0<\eta <1$ gives $r\in (0,1)$ = a monotone glide from one side; $1<\eta <2$ gives $r\in (-1,0)$ = convergence that alternates sides (overshoots then corrects), spiraling in. At exactly $\eta =1$, $r=0$ → one-step jump straight to $3$.
• $|1-\eta |=1$ (i.e. $\eta =0$ or $\eta =2$): error magnitude is constant. $\eta =0$ = no movement at all; $\eta =2$ = $r=-1$ = $\theta$ oscillates forever between $0$ and $6$, never settling.
• $|1-\eta |>1$ (i.e. $\eta <0$ or $\eta >2$): error grows each step → diverges, flying away from the minimum. This is the too-large-learning-rate blow-up. Why this matters: the exact same contraction factor governs stability of the learning rate on any quadratic — $\eta$ too large ($>2$ here) doesn't just slow you down, it explodes.

In 5.1 the gradient is the exact averaged gradient $\theta -3$, so the noise term is identically $0$; the update is a pure contraction $e_{t+1}=(1-\eta )e_t\to 0$ and $\theta$ glides in. In SGD the estimate is $g_{\mathcal{B}}=\theta -x_j$, which equals the true gradient plus a mean-zero noise term whose typical size is $\sigma /\sqrt{m}$ (here caused by which point $x_j$ we happened to draw). That noise never disappears at fixed $\eta$: near $\theta =3$ the true part $\approx 0$ but the noise part $\approx \eta \cdot (\sigma /\sqrt{m})$ keeps kicking $\theta$ around a ball of radius $\propto \eta$. The responsible quantity is the gradient-estimate variance ${\sigma }^2/m$ (equivalently its square root, the noise std-dev $\sigma /\sqrt{m}$); to kill the wobble you must send ${\eta }_t\to 0$ under Robbins–Monro, exactly as in Exercise 3.2. Full-batch has ${\sigma }^2/m$ effectively zero here, so no schedule is needed — it just contracts to the point.

Need $|e_t|=3\cdot (0.6{)}^t<0.1\Rightarrow (0.6{)}^t<1/30$. Take logs: $t>\frac{\ln (1/30)}{\ln 0.6}=\frac{-3.4012}{-0.5108}\approx 6.66$. Smallest integer: $t=7$. Check: $3\cdot 0.6^7=3\cdot 0.0279936=0.0839808<0.1$. ✓ And $t=6$: $3\cdot 0.6^6=0.139968>0.1$. So $t=7$.

Updates in one epoch ::: $N/m$. Meaning of ${\sigma }^2$ ::: per-example gradient variance = spread of individual gradients around the true gradient. Effect of $m\to 2m$ on noise variance ::: halves it (${\sigma }^2/m$). Robbins–Monro pair ::: $\sum {\eta }_t=\infty$ and $\sum {\eta }_t^2<\infty$. Role of $k$ in ${\eta }_t={\eta }_0/(1+kt)$ ::: decay constant, must be $k>0$; tunes speed, not whether R–M holds. Linear scaling rule ::: multiply $m$ by $c\Rightarrow$ multiply $\eta$ by $c$. Fixed-$\eta$ SGD endpoint ::: a bouncing ball of radius $\propto \eta$, not a point. Error law of exact-gradient step on quadratic ::: $e_{t+1}=(1-\eta )e_t$; converges iff $|1-\eta |<1$.