Gradient Descent & SGD

Every deep network is trained by the same move from the training loop: compute the gradient of the loss with respect to the parameters, then step the parameters in the opposite direction. With $\theta \in {\mathbb{R}}^d$ the full parameter vector and $\mathcal{L}(\theta )$ the loss, gradient descent is the iteration

where $\eta >0$ is the learning rate. The gradient ${\nabla }_{\theta }\mathcal{L}$ points in the direction of steepest ascent, so its negation is the locally steepest descent; $\eta$ sets how far we trust that local direction before recomputing it.¹

One step is a small dataflow: read the current parameters, evaluate the gradient there, scale it by the rate, and subtract to produce the next parameters. That loop repeats until the gradient is (near) zero.

What we actually minimize

The object we want to minimize is the risk, the expected loss over the true data distribution $p_{\text{data}}$; what we can compute is the empirical risk, its average over the finite training set $\{(x_i,y_i){\}}_{i=1}^n$:

The exact gradient ${\nabla }_{\theta }\mathcal{L}=\frac{1}{n}{\sum }_i{\nabla }_{\theta }{\ell }_i$ is a sum over all $n$ examples, so one true gradient step costs a full pass over the data. For $n$ in the millions that is too expensive per update, and it is also wasteful, because the examples are redundant and an estimate of the gradient from a small sample already points the right way.²

Three granularities of the gradient

The gradient is a sample mean, so we may estimate it from all $n$ examples, from one, or from a minibatch of $B$ drawn at random. These are the three canonical variants; they trade computation per step against the noise in the direction they produce.

Pure SGD ($B=1$) and full-batch GD ($B=n$) are the endpoints of one dial; the practical regime is the middle, $B$ on the order of $32$ to $512$, large enough to use vectorized hardware and damp the noise, small enough that each step is cheap and the steps are frequent.³

The minibatch gradient is unbiased

Why is it legitimate to step against a gradient computed from a handful of examples? Because that estimate is unbiased: in expectation it equals the true gradient. Let $g=\frac{1}{B}{\sum }_{i\in \mathcal{B}}{g}_i$ with $g_i={\nabla }_{\theta }{\ell }_i$, where the indices in $\mathcal{B}$ are drawn uniformly. Each draw has $\mathbb{E}[g_i]=\frac{1}{n}{\sum }_{j=1}^n{g}_j={\nabla }_{\theta }\mathcal{L}$, so by linearity of expectation,

The estimate is centered on the truth at every batch size; what $B$ controls is not the center but the spread.

Variance falls as $1/B$

Model the per-example gradients as i.i.d. draws with common covariance $\Sigma =\mathrm{Cov}(g_i)$. The minibatch gradient is their average, so its covariance shrinks linearly in $B$. Writing $\bar{g}=g-{\nabla }_{\theta }\mathcal{L}$ for the deviation, with independence across the $B$ draws,

Taking the trace gives the total variance of the estimate, and the typical magnitude of the gradient noise is its square root:

This is the speed–noise tradeoff in one line. The catch is the square root: halving the noise costs a $4\times$ larger batch (and $4\times$ the compute per step). Past a point the variance reduction is not worth the cost — large batches give precise but expensive steps, and the noise they remove was partly useful, helping the iterate escape sharp minima and saddle regions.⁴

For example, suppose $\mathrm{tr}\Sigma =100$ in some unit, so the mean-squared error of the estimate is $100/B$ and the noise scale (its square root) is $10/\sqrt{B}$. Then:

Each row costs $4\times$ the compute of the one above for exactly a $2\times$ cut in noise. Going from $B=16$ to $B=1024$ is $64\times$ the work for an $8\times$ tighter estimate. The practical batch size is the one that just saturates the vectorized hardware; beyond that the marginal precision is not worth the compute, and the residual noise aids exploration anyway.

The same tradeoff shows in the descent path. Full-batch GD takes the exact gradient and traces a smooth curve to the minimum; SGD steps along a noisy estimate and drifts toward it, the trajectory jittering but still trending downhill because the noise has zero mean.

Convergence and the learning rate

The learning rate is the single most important hyperparameter, and its safe range is governed by the curvature of the loss. Assume $\mathcal{L}$ is $L$-smooth: its gradient is $L$-Lipschitz, $\Vert \nabla \mathcal{L}(\theta )-\nabla \mathcal{L}({\theta }^{\prime })\Vert \le L\Vert \theta -{\theta }^{\prime }\Vert$, which bounds how fast the gradient can change. Smoothness gives the descent lemma, a quadratic upper bound on the loss after a step:

Substitute the GD update ${\theta }_{t+1}-{\theta }_t=-\eta \nabla \mathcal{L}({\theta }_t)$ and abbreviate $g_t=\nabla \mathcal{L}({\theta }_t)$:

The loss is guaranteed to decrease whenever the bracket is positive, i.e. $1-\frac{L\eta }{2}>0$. This is the stability bound on the step size.

The optimal step within this bound is $\eta =1/L$. The guaranteed decrease is $\eta (1-\frac{L\eta }{2})\Vert g_t{\Vert }^2$; treating the coefficient $\varphi (\eta )=\eta -\frac{L}{2}{\eta }^2$ as a function of $\eta$ and setting ${\varphi }^{\prime }(\eta )=1-L\eta =0$ gives ${\eta }^{\star }=1/L$, at which $\varphi (1/L)=\frac{1}{L}-\frac{L}{2}\frac{1}{L^2}=\frac{1}{2L}$. Substituting back, $\mathcal{L}({\theta }_{t+1})\le \mathcal{L}({\theta }_t)-\frac{1}{2L}\Vert g_t{\Vert }^2$, the largest per-step drop the bound allows. For a $\mu$-strongly-convex, $L$-smooth loss, the iterates converge linearly at a rate set by the condition number $\kappa =L/\mu$:

A well-conditioned loss ($\kappa \approx 1$) converges in a few steps; an ill-conditioned one ($\kappa \gg 1$) converges slowly, because the largest stable $\eta$ is capped by the steepest direction ($1/L$) while progress along the shallow direction is limited by $\mu$.

The factor $(1-1/\kappa )$ per step is what makes this quantitative. To cut the distance to the optimum by a factor of $10$ takes $t$ steps with $(1-1/\kappa {)}^t\le 1/10$, i.e. $t\gtrsim \kappa \ln 10\approx 2.3\kappa$. So the iteration count scales linearly in the condition number:

A quadratic bowl with axes in a $100:1$ ratio ($\kappa =100$) needs on the order of $230$ full-batch steps for each decimal digit of accuracy, and deep-network losses routinely have curvature ratios far larger than that. This linear-in-$\kappa$ cost is the concrete reason ill-conditioning hurts, and it motivates every preconditioning trick in the next lesson. The three regimes of $\eta$ are visible directly in the loss curve.

Learning-rate schedules

A single fixed $\eta$ is a compromise: large early progress wants a big rate, fine late-stage convergence wants a small one. For SGD specifically, a constant rate cannot converge to the exact minimum. Near ${\theta }^{\star }$ the true gradient is small, but the stochastic gradient still carries noise of scale $\sqrt{\mathrm{tr}\Sigma /B}$; the update $-\eta g$ then injects a random kick of size $\propto \eta$ every step, and the iterate settles into a stationary cloud of radius $\propto \eta$ around ${\theta }^{\star }$ rather than the point itself. Shrink $\eta$ and the cloud shrinks with it, but only a rate that decays to zero drives the residual error to zero. So $\eta$ must decay. A schedule ${\eta }_t$ does this: start large, shrink over training. The Robbins–Monro conditions ${\sum }_t{\eta }_t=\infty$ (steps sum to infinity, so any starting point is reachable) and ${\sum }_t{\eta }_t^2<\infty$ (the injected noise is summable, so the cloud collapses) are the classical guarantee that decaying SGD reaches the minimum. A schedule like ${\eta }_t={\eta }_0/t$ satisfies both; a constant ${\eta }_t={\eta }_0$ satisfies the first but violates the second, and so it stalls in the noise ball.

Warmup ramps $\eta$ up from near zero over the first $T_w$ steps before any decay begins — the early iterates are far from a good region and the gradient estimates are noisiest there, so a small initial rate prevents the first few steps from blowing up; it is near-standard for large-batch and transformer training. In practice warmup is composed with cosine: ramp up, then anneal down.⁵

The algorithm

Assembling the pieces (sample a minibatch, average its gradient, look up the scheduled rate, step) gives the standard training algorithm of deep learning.

One pass over the whole dataset is an epoch ($n/B$ steps); training runs for many epochs, reshuffling the data each time so successive minibatches are fresh draws. Every line here is the target of a later refinement.⁶

A worked SGD step, end to end

For a worked example, run one minibatch step of the algorithm on the smallest model that has a gradient: linear regression, $f_{\theta }(x)=wx+b$ with the squared loss $\ell =\frac{1}{2}(f_{\theta }(x)-y{)}^2$. The parameters are $\theta =(w,b)$, and the per-example gradients are $\partial \ell /\partial w=(f_{\theta }(x)-y)x$ and $\partial \ell /\partial b=f_{\theta }(x)-y$.

Start from $w=0.5$, $b=0.0$, take a minibatch of $B=2$ examples $(x,y)=(2,3)$ and $(4,5)$, and use $\eta =0.05$. First the forward pass and residuals:

Each example contributes a gradient $(rx,r)$; the minibatch gradient is their average:

The residuals are negative (the model underpredicts), so the gradient is negative, and the descent step $-\eta g$ moves both parameters up:

One step lifted $w$ from $0.5$ toward the least-squares slope. Re-running the forward pass with the new parameters shows the loss fell: the residual on the first example shrinks from $-2.0$ to $0.9\cdot 2+0.125-3=-1.075$, and on the second from $-3.0$ to $0.9\cdot 4+0.125-5=-1.275$. The batch mean-squared residual dropped from $\frac{1}{2}(4+9)=6.5$ to $\frac{1}{2}(1.156+1.626)\approx 1.39$ in a single update. Iterating this loop is training; the only thing a deep network changes is that ${\nabla }_{\theta }\ell$ now flows through backpropagation rather than a one-line derivative.

The ravine: why plain SGD struggles

The stability bound exposes plain GD's weakness. When the loss is ill-conditioned (curvature far steeper in one direction than another, $\kappa \gg 1$), the largest stable $\eta$ is fixed by the steep direction, but that same $\eta$ makes almost no progress along the shallow one. The result is a ravine: the iterate bounces back and forth across the steep walls while creeping slowly down the gentle floor toward the minimum.

Halving $\eta$ to stop the zig-zag also halves progress along the floor: the ratio of progress to oscillation is fixed at $\kappa$, and no scalar $\eta$ changes it. To address this, change the direction of the step rather than its length: damp the oscillating component and accumulate the consistent one. This is the move momentum and adaptive methods make, in the next lesson.

Learning-rate methods

The standard references treat the learning rate as a hyperparameter to tune by hand; the research literature has since turned each of this lesson's knobs into a method.

• Finding $\eta$ without a grid search. Smith's LR range test sweeps the learning rate up exponentially over a few hundred iterations and plots loss against rate; the largest rate before the loss turns up is a near-optimal choice, read straight off the curve. It replaces the smoothness constant $L$ (which we never know) with a direct measurement.⁷
• Batch size as a substitute for decay. The $1/\sqrt{B}$ noise law says a larger batch is a quieter gradient, and Smith et al. showed the two levers are interchangeable: increasing the batch size over training reaches the same accuracy as decaying the learning rate, while keeping the step count low enough to parallelize. The noise-ball argument of the schedules section is exactly why.⁸
• Large-batch training at scale. Goyal et al. trained ImageNet in one hour by pushing the batch to $8192$ with the linear scaling rule (scale $\eta$ in proportion to $B$) plus a warmup ramp — the same warmup this lesson motivated from noisy early gradients, now standard for the largest models.⁹
• One-cycle and super-convergence. Smith's one-cycle policy ramps the rate up to a large peak and back down within a single run, and can train some networks an order of magnitude faster (super-convergence), a schedule that goes well past the standard monotone-decay picture.¹⁰

Each of these is a public, named result that builds directly on the two facts this lesson derived: the $1/\sqrt{B}$ noise law and the $\eta <2/L$ stability bound.

Takeaways

• Training is the iteration ${\theta }_{t+1}={\theta }_t-\eta {\nabla }_{\theta }\mathcal{L}$: step the parameters against the gradient of the empirical risk.
• The gradient is a sample mean, so it can be estimated from a minibatch of $B$ examples, an unbiased estimator ($\mathbb{E}[g]=\nabla \mathcal{L}$) whose variance is $\Sigma /B$, noise magnitude $\propto 1/\sqrt{B}$. Bigger batches give precise, expensive steps; the useful regime is the middle.
• For an $L$-smooth loss, GD decreases the loss iff $\eta <2/L$; the optimal step is $\eta =1/L$, and convergence rate is set by the condition number$\kappa =L/\mu$. Too small $\to$ slow; too large $\to$ diverge.
• A fixed rate cannot converge under SGD noise; schedules (step, exponential, cosine annealing, linear warmup) decay $\eta$ over training to trade fast early progress for fine late convergence.
• Plain SGD zig-zags in ill-conditioned ravines because one $\eta$ must serve both the steep and shallow directions — the motivation for momentum.¹¹