---
title: Gradient Descent & SGD
module: Optimization
moduleNumber: 3
lessonNumber: 1
order: 301
summary: >
  Training is descent on the empirical risk: step the parameters against
  the gradient. We derive the minibatch
  gradient as an unbiased estimator whose variance falls as $1/B$, derive the
  learning-rate ceiling from the smoothness-stability bound $\eta < 2/L$, and lay out
  the schedules (step, exponential, cosine, warmup) that anneal it over training.
topics: [Optimization]
sources:
  - book: Goodfellow
    ref: "Ch. 8 — Optimization for Training Deep Models, §8.1 How Learning Differs from Pure Optimization"
  - book: Goodfellow
    ref: "§8.2 Challenges in Neural Network Optimization; §8.3 Basic Algorithms (SGD)"
  - book: Chollet
    ref: "§2.4 — The Engine of Neural Networks: Gradient-Based Optimization"
  - book: Stevens
    ref: "Ch. 5 — The Mechanics of Learning (gradient descent, learning rate)"
---

Every deep network is trained by the same move from the
[training loop](/deep-learning/foundations/what-is-deep-learning): 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

$$
\theta_{t+1} = \theta_t - \eta\,\nabla_\theta \mathcal{L}(\theta_t),
$$

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.[^gf-gd]

> **Definition (Gradient descent).** The iteration $\theta_{t+1} = \theta_t -
> \eta\,\nabla_\theta\mathcal{L}(\theta_t)$, which moves the parameters along the
> negative gradient (the direction of locally steepest decrease of the loss) by
> a step of size $\eta$.

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.

$$
% caption: One gradient-descent update as a dataflow. The current parameters
% $\theta_t$ feed the gradient $g_t = \nabla\mathcal{L}(\theta_t)$, which is scaled
% by $\eta$ and subtracted to give $\theta_{t+1} = \theta_t - \eta g_t$; the output
% feeds back as the next input.
\begin{tikzpicture}[>=stealth, font=\footnotesize, node distance=6mm]
  \definecolor{acc}{HTML}{2348F2}
  \tikzstyle{box}=[draw=black, thick, minimum height=8mm, inner sep=4pt]
  \node[box] (theta) {params};
  \node[box, right=16mm of theta] (grad) {gradient};
  \node[box, right=14mm of grad] (scale) {scale by rate};
  \node[box, right=14mm of scale, draw=acc, text=acc] (sub) {subtract};
  \node[box, right=16mm of sub] (next) {new params};
  \draw[->, thick] (theta) -- (grad);
  \draw[->, thick] (grad) -- node[above, font=\scriptsize] {$g_t$} (scale);
  \draw[->, thick] (scale) -- (sub);
  \draw[->, thick, acc] (sub) -- (next);
  % current params also feed the subtract node
  \draw[->, thick] (theta) to[out=-40, in=-140] (sub.south);
  % feedback loop
  \draw[->, thick, black] (next.north) to[out=140, in=40] node[above, font=\scriptsize, black] {next step} (theta.north);
\end{tikzpicture}
$$

## 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$:

$$
R(\theta) = \mathbb{E}_{(x,y)\sim p_{\text{data}}}\brackets{\ell(f_\theta(x), y)},
\qquad
\mathcal{L}(\theta) = \frac{1}{n}\sum_{i=1}^{n} \ell(f_\theta(x_i), y_i).
$$

The exact gradient $\nabla_\theta\mathcal{L} = \tfrac1n\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.[^gf-erm]

> **Definition (Empirical risk minimization).** Replacing the inaccessible risk
> $R(\theta) = \mathbb{E}_{p_{\text{data}}}[\ell]$ with the trainable empirical
> risk $\mathcal{L}(\theta) = \tfrac1n\sum_i \ell(f_\theta(x_i), y_i)$, the average
> loss over the finite training set, and minimizing that by gradient descent.

## 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.

| variant | gradient estimate | cost / step | noise | use |
| --- | --- | --- | --- | --- |
| batch GD | $\dfrac1n\sum_{i=1}^{n}\nabla_\theta\ell_i$ | $O(n)$ | none (exact) | small data, convex problems |
| minibatch SGD | $\dfrac1B\sum_{i\in\mathcal{B}}\nabla_\theta\ell_i$ | $O(B)$ | $\propto 1/B$ | the default for deep nets |
| (pure) SGD | $\nabla_\theta\ell_i$, one example | $O(1)$ | high | online / streaming data |

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.[^gf-minibatch]

> **Definition (Minibatch).** A subset $\mathcal{B}\subset\{1,\dots,n\}$ of size
> $B$, sampled (usually without replacement) each step, over which the gradient
> is averaged to form the stochastic estimate $g = \tfrac1B\sum_{i\in\mathcal{B}}
> \nabla_\theta\ell_i$ used in place of the full gradient.

## 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 = \tfrac1B\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] = \tfrac1n\sum_{j=1}^{n} g_j = \nabla_\theta\mathcal{L}$,
so by linearity of expectation,

$$
\mathbb{E}[g]
= \frac1B\sum_{i\in\mathcal{B}} \mathbb{E}[g_i]
= \frac1B \cdot B \cdot \nabla_\theta\mathcal{L}
= \nabla_\theta\mathcal{L}.
$$

> **Theorem (Unbiased gradient estimate).** If the minibatch indices are sampled
> uniformly, the minibatch gradient is an unbiased estimator of the full-batch
> gradient: $\mathbb{E}[g] = \nabla_\theta\mathcal{L}$, independent of the batch
> size $B$.

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 =
\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,

$$
\Cov(g)
= \Cov\!\parens{\frac1B\sum_{i=1}^{B} g_i}
= \frac1{B^2}\sum_{i=1}^{B} \Cov(g_i)
= \frac1{B^2}\cdot B\,\Sigma
= \frac{\Sigma}{B}.
$$

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

$$
\mathbb{E}\brackets{\lVert g - \nabla_\theta\mathcal{L}\rVert^2}
= \frac{\tr\Sigma}{B},
\qquad
\text{noise scale} \;\propto\; \frac{1}{\sqrt{B}}.
$$

> **Theorem (Gradient-noise variance).** For i.i.d. per-example gradients with
> covariance $\Sigma$, the minibatch estimate has $\Cov(g) =
> \Sigma/B$, so its mean-squared error decays as $1/B$ and the noise magnitude as
> $1/\sqrt{B}$.

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.[^gf-batchsize]

For example, suppose $\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:

| batch $B$ | MSE $=\tr\Sigma/B$ | noise scale $\propto 1/\sqrt B$ | compute / step |
| --- | --- | --- | --- |
| $16$ | $6.25$ | $2.50$ | $1\times$ |
| $64$ | $1.5625$ | $1.25$ | $4\times$ |
| $256$ | $0.3906$ | $0.625$ | $16\times$ |
| $1024$ | $0.0977$ | $0.3125$ | $64\times$ |

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.

$$
% caption: Gradient noise vs. batch size. Small-$B$ estimates (black) scatter
% around the true gradient (blue); the spread shrinks as $1/\sqrt{B}$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % --- small B: wide scatter ---
  \coordinate (oA) at (0,0);
  \fill[black] (oA) circle (1.6pt);
  \node[anchor=north] at (0,-0.25) {small $B$};
  \foreach \dx/\dy in {1.7/1.5, 2.1/0.2, 1.3/1.7, 2.2/1.6, 1.5/-0.4, 2.0/1.9, 1.9/0.7, 1.2/0.4} {
    \draw[->, black, thick] (oA) -- (\dx,\dy);
  }
  \draw[->, acc, very thick] (oA) -- (2.0,1.0)
    node[anchor=west, text=acc] {true grad};
  % --- mid B: tighter ---
  \begin{scope}[xshift=5.6cm]
    \coordinate (oB) at (0,0);
    \fill[black] (oB) circle (1.6pt);
    \node[anchor=north] at (0,-0.25) {medium $B$};
    \foreach \dx/\dy in {1.8/1.2, 2.05/0.85, 1.75/1.15, 2.1/1.05, 1.95/0.75} {
      \draw[->, black, thick] (oB) -- (\dx,\dy);
    }
    \draw[->, acc, very thick] (oB) -- (2.0,1.0)
      node[anchor=west, text=acc] {true grad};
  \end{scope}
  % --- large B: concentrated ---
  \begin{scope}[xshift=11.2cm]
    \coordinate (oC) at (0,0);
    \fill[black] (oC) circle (1.6pt);
    \node[anchor=north] at (0,-0.25) {large $B$};
    \foreach \dx/\dy in {1.97/0.98, 2.0/1.04, 2.03/0.97} {
      \draw[->, black, thick] (oC) -- (\dx,\dy);
    }
    \draw[->, acc, very thick] (oC) -- (2.0,1.0)
      node[anchor=west, text=acc] {true grad};
  \end{scope}
\end{tikzpicture}
$$

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.

$$
% caption: Smooth batch-GD (blue) vs. noisy SGD (red) on the same contours.
% Both reach the minimum; SGD jitters but its expected direction is correct.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % elliptical contours
  \foreach \r in {0.55,1.1,1.65,2.2,2.75}
    \draw[black] (0,0) ellipse ({\r*1.6} and \r);
  \fill[green] (0,0) circle (2.6pt);
  \node[green, anchor=north] at (0,-2.95) {\texttt{minimum}};
  % smooth batch path
  \draw[acc, very thick, ->] (-4.0,2.3) .. controls (-2.6,1.3) and (-1.4,0.7) .. (-0.15,0.1);
  \node[acc, anchor=south east] at (-4.0,2.35) {batch GD};
  % noisy SGD path
  \draw[red, thick]
    (-3.6,2.6) -- (-3.1,1.6) -- (-2.9,2.0) -- (-2.2,1.0)
    -- (-2.4,1.3) -- (-1.5,0.55) -- (-1.7,0.85)
    -- (-0.9,0.2) -- (-1.05,0.45) -- (-0.3,-0.05) -- (-0.15,0.18);
  \fill[red] (-0.15,0.18) circle (1.4pt);
  \node[red, anchor=south west] at (-3.6,2.6) {SGD};
\end{tikzpicture}
$$

## 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, $\lVert\nabla\mathcal{L}(\theta) -
\nabla\mathcal{L}(\theta')\rVert \le L\lVert\theta-\theta'\rVert$, which bounds how
fast the gradient can change. Smoothness gives the descent lemma, a quadratic
upper bound on the loss after a step:

$$
\mathcal{L}(\theta_{t+1})
\le \mathcal{L}(\theta_t)
+ \nabla\mathcal{L}(\theta_t)^{\top}(\theta_{t+1}-\theta_t)
+ \frac{L}{2}\lVert\theta_{t+1}-\theta_t\rVert^2.
$$

Substitute the GD update $\theta_{t+1}-\theta_t = -\eta\,\nabla\mathcal{L}(\theta_t)$
and abbreviate $g_t = \nabla\mathcal{L}(\theta_t)$:

$$
\mathcal{L}(\theta_{t+1})
\le \mathcal{L}(\theta_t) - \eta\lVert g_t\rVert^2 + \frac{L\eta^2}{2}\lVert g_t\rVert^2
= \mathcal{L}(\theta_t) - \eta\parens{1 - \frac{L\eta}{2}}\lVert g_t\rVert^2.
$$

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

> **Theorem (Stability bound).** If $\mathcal{L}$ is $L$-smooth and $0 < \eta <
> 2/L$, gradient descent monotonically decreases the loss, $\mathcal{L}(\theta_{t+1})
> \le \mathcal{L}(\theta_t)$, with strict decrease whenever $g_t \ne 0$. For
> $\eta \ge 2/L$ the quadratic overshoots and the iteration can diverge.

> **Proof.** From the descent lemma, $\mathcal{L}(\theta_{t+1}) - \mathcal{L}(\theta_t)
> \le -\eta(1 - \tfrac{L\eta}{2})\lVert g_t\rVert^2$. The factor $\eta > 0$, and
> $1 - \tfrac{L\eta}{2} > 0$ exactly when $\eta < 2/L$; then the right side is
> $\le 0$, and $< 0$ unless $g_t = 0$. So each step lowers the loss until a
> stationary point. $\qed$

The optimal step within this bound is $\eta = 1/L$. The guaranteed decrease is
$\eta(1-\tfrac{L\eta}{2})\lVert g_t\rVert^2$; treating the coefficient $\phi(\eta)
= \eta - \tfrac{L}{2}\eta^2$ as a function of $\eta$ and setting $\phi'(\eta) = 1 -
L\eta = 0$ gives $\eta^\star = 1/L$, at which $\phi(1/L) = \tfrac1L - \tfrac{L}{2}
\tfrac1{L^2} = \tfrac{1}{2L}$. Substituting back,
$\mathcal{L}(\theta_{t+1}) \le \mathcal{L}(\theta_t) - \tfrac{1}{2L}\lVert g_t\rVert^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$:

$$
\lVert\theta_t - \theta^\star\rVert^2
\le \parens{1 - \frac1\kappa}^{t}\,\lVert\theta_0 - \theta^\star\rVert^2.
$$

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:

| condition number $\kappa$ | per-step factor $1-1/\kappa$ | steps for $10\times$ progress |
| --- | --- | --- |
| $1$ | $0$ | $1$ |
| $10$ | $0.90$ | $\approx 22$ |
| $100$ | $0.99$ | $\approx 230$ |
| $10^4$ | $0.9999$ | $\approx 23{,}000$ |

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.

$$
% caption: Loss vs. iteration for three learning rates: too small (black) crawls,
% well-tuned (blue) descends fast and flattens, too large (red) diverges.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (0,0) -- (6.6,0) node[right] {iteration};
  \draw[->, thick] (0,0) -- (0,4.2) node[above] {loss};
  % too small: slow, shallow decay
  \draw[black, very thick] plot[domain=0:6.2, samples=60] (\x, {3.4*exp(-0.18*\x)+0.2});
  \node[black, anchor=west] at (4.5,2.0) {\texttt{too} small};
  % good: fast decay to low floor
  \draw[acc, very thick] plot[domain=0:6.2, samples=60] (\x, {3.6*exp(-0.9*\x)+0.25});
  \node[acc, anchor=west] at (1.55,0.5) {good};
  % too large: diverges (grows)
  \draw[red, very thick] plot[domain=0:3.55, samples=60] (\x, {0.5*exp(0.62*\x)});
  \node[red, anchor=south] at (2.6,3.6) {\texttt{too} large};
\end{tikzpicture}
$$

| learning rate | behavior | cause |
| --- | --- | --- |
| too small ($\eta\ll 1/L$) | loss falls, but slowly | each step trusts the gradient too little |
| well-tuned ($\eta\approx 1/L$) | fast, monotone descent | near-maximal stable step |
| too large ($\eta \ge 2/L$) | oscillation, then divergence | quadratic overshoots; bound violated |

## 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{
\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.

$$
% caption: Constant vs. decaying rate near the minimum. A fixed $\eta$ (red) leaves
% the iterate rattling in a ball of radius $\propto\eta$; a decaying $\eta_t$ (blue)
% shrinks the ball toward the true minimum (green).
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % target minimum
  \fill[green] (0,0) circle (2.4pt);
  \node[green, anchor=north] at (0,-1.9) {\texttt{minimum}};
  % constant-rate noise ball (fixed radius)
  \draw[red, dashed, thick] (0,0) circle (1.5);
  \node[red, anchor=south] at (0,1.55) {constant rate};
  \foreach \a/\r in {20/1.2, 75/1.35, 130/1.1, 200/1.4, 265/1.25, 320/1.15} {
    \fill[red] (\a:\r) circle (1.2pt);
  }
  % decaying-rate spiral collapsing inward
  \begin{scope}[xshift=5.4cm]
    \fill[green] (0,0) circle (2.4pt);
    \node[green, anchor=north] at (0,-1.9) {\texttt{minimum}};
    \draw[acc, thick, ->]
      (1.45,0) .. controls (1.2,1.1) and (-0.2,1.3) .. (-1.0,0.55)
      .. controls (-1.3,-0.1) and (-0.7,-0.85) .. (0.0,-0.75)
      .. controls (0.55,-0.6) and (0.65,-0.1) .. (0.4,0.28)
      .. controls (0.15,0.5) and (-0.2,0.35) .. (-0.22,0.05)
      .. controls (-0.2,-0.15) and (0.02,-0.18) .. (0.05,-0.02);
    \node[acc, anchor=south] at (0,1.55) {decaying rate};
  \end{scope}
\end{tikzpicture}
$$

| schedule | formula | shape | notes |
| --- | --- | --- | --- |
| step decay | $\eta_t = \eta_0\,\gamma^{\lfloor t/s\rfloor}$ | staircase | drop by factor $\gamma$ every $s$ steps |
| exponential | $\eta_t = \eta_0\,e^{-\lambda t}$ | smooth decay | continuous analogue of step decay |
| cosine annealing | $\eta_t = \eta_{\min} + \tfrac12(\eta_0-\eta_{\min})\parens{1+\cos\tfrac{\pi t}{T}}$ | half-cosine | smooth to $\eta_{\min}$ at horizon $T$ |
| linear warmup | $\eta_t = \eta_0\,t/T_w$ for $t \le T_w$ | ramp up | then hand off to a decay schedule |

**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.[^chollet-opt]

$$
% caption: Three learning-rate schedules: step decay (gray) drops in stages, cosine
% annealing (blue) eases to a floor, and warmup-then-cosine (red) ramps up first.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (0,0) -- (7.2,0) node[right] {step};
  \draw[->, thick] (0,0) -- (0,3.4) node[above] {rate};
  % step decay (staircase): 3 -> 1.8 -> 1.08 ...
  \draw[black, very thick]
    (0,3.0) -- (2.0,3.0) -- (2.0,1.95) -- (4.0,1.95)
    -- (4.0,1.25) -- (6.0,1.25) -- (6.0,0.8) -- (6.8,0.8);
  \node[black, anchor=west] at (5.1,2.55) {step};
  % cosine annealing over T=6.8, eta0=3, etamin=0.2
  \draw[acc, very thick] plot[domain=0:6.8, samples=70]
    (\x, {0.2 + 0.5*(3.0-0.2)*(1 + cos(deg(3.14159*\x/6.8)))});
  \node[acc, anchor=west] at (2.5,1.15) {cosine};
  % warmup (linear to step 1.2) then cosine down
  \draw[red, very thick] (0,0) -- (1.2,3.0);
  \draw[red, very thick] plot[domain=1.2:6.8, samples=60]
    (\x, {0.2 + 0.5*(3.0-0.2)*(1 + cos(deg(3.14159*(\x-1.2)/5.6)))});
  \node[red, anchor=south] at (1.2,3.05) {\texttt{warmup}};
\end{tikzpicture}
$$

## 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.

```algorithm
caption: $\textsc{MinibatchSGD}(f_\theta, \mathcal{D}, \eta_0, B, T)$ — stochastic gradient descent with optional schedule
initialize $\theta$ (random init)
for $t \gets 0$ to $T-1$ do
  sample a minibatch $\mathcal{B} \subset \mathcal{D}$ of size $B$ // uniform, without replacement
  $g \gets \frac1B \sum_{i \in \mathcal{B}} \nabla_\theta\, \ell(f_\theta(x_i), y_i)$ // unbiased estimate
  $\eta_t \gets \textsc{Schedule}(\eta_0, t)$ // step / cosine / warmup
  $\theta \gets \theta - \eta_t \cdot g$ // descent step
return $\theta$
```

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.[^stevens-mech]

> **Definition (Epoch).** One full sweep through the training set, comprising
> $\lceil n/B\rceil$ minibatch steps. Schedules are usually specified in epochs;
> the data is reshuffled between epochs to decorrelate the gradient estimates.

## 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)
= w x + b$ with the squared loss $\ell = \tfrac12(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:

$$
\hat y_1 = 0.5\cdot 2 + 0 = 1.0,\quad r_1 = 1.0 - 3 = -2.0,\qquad
\hat y_2 = 0.5\cdot 4 + 0 = 2.0,\quad r_2 = 2.0 - 5 = -3.0.
$$

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

$$
g_w = \tfrac12\brackets{(-2)(2) + (-3)(4)} = \tfrac12(-4 - 12) = -8.0,
\qquad
g_b = \tfrac12\brackets{(-2) + (-3)} = -2.5.
$$

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

$$
w \gets 0.5 - 0.05\,(-8.0) = 0.9,
\qquad
b \gets 0.0 - 0.05\,(-2.5) = 0.125.
$$

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 $\tfrac12(4 + 9) = 6.5$ to $\tfrac12(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](/deep-learning/neural-networks/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.

$$
% caption: An ill-conditioned ravine. With $\eta$ capped by the steep direction,
% gradient descent (red) zig-zags across the walls while crawling toward the minimum (green).
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % highly elongated contours (steep across, shallow along)
  \foreach \r in {0.5,1.0,1.5,2.0,2.5}
    \draw[black] (0,0) ellipse ({\r*3.0} and {\r*0.7});
  \fill[green] (0,0) circle (2.6pt);
  \node[green, anchor=north] at (0,-2.05) {\texttt{minimum}};
  % zig-zag path bouncing across the steep walls while drifting along the floor
  \draw[red, very thick, ->]
    (-7.0,1.35) -- (-5.6,-1.15) -- (-4.4,1.0) -- (-3.3,-0.85)
    -- (-2.4,0.7) -- (-1.6,-0.55) -- (-1.0,0.45) -- (-0.55,-0.3)
    -- (-0.25,0.2) -- (-0.08,-0.1);
  \fill[red] (-7.0,1.35) circle (1.8pt);
  \node[red, anchor=south] at (-7.0,1.45) {start};
\end{tikzpicture}
$$

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](/deep-learning/optimization/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.[^smith-lr]
- **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.[^smith-batch]
- **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.[^goyal]
- **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.[^smith-onecycle]

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](/deep-learning/optimization/momentum-and-adaptive-methods).[^gf-illcond]

[^gf-gd]: **Goodfellow**, _Deep Learning_, §4.3 — Gradient-Based Optimization: the negative gradient as the direction of steepest descent and the role of the step size.
[^gf-erm]: **Goodfellow**, _Deep Learning_, §8.1 — How Learning Differs from Pure Optimization: minimizing empirical risk as a surrogate for the inaccessible risk over $p_{\text{data}}$.
[^gf-minibatch]: **Goodfellow**, _Deep Learning_, §8.1.3 — Batch and Minibatch Algorithms: why minibatches of $32$–$256$ trade statistical efficiency against hardware throughput.
[^gf-batchsize]: **Goodfellow**, _Deep Learning_, §8.1.3 — diminishing returns of larger batches (noise falls only as $1/\sqrt{B}$) and the regularizing value of gradient noise.
[^chollet-opt]: **Chollet**, _Deep Learning with Python_, §2.4 — The Engine of Neural Networks: gradient-based optimization, the learning-rate knob, and schedule/warmup heuristics in practice.
[^stevens-mech]: **Stevens**, _Deep Learning with PyTorch_, Ch. 5 — The Mechanics of Learning: the minibatch loop, epochs, and reshuffling as implemented in a training routine.
[^gf-illcond]: **Goodfellow**, _Deep Learning_, §8.2 — Challenges in Neural Network Optimization: ill-conditioning of the Hessian and the zig-zag of first-order descent in a ravine.
[^smith-lr]: **Smith**, _Cyclical Learning Rates for Training Neural Networks_, WACV 2017 — the learning-rate range test: sweep $\eta$ upward and read the largest stable rate off the loss curve.
[^smith-batch]: **Smith, Kindermans, Ying & Le**, _Don't Decay the Learning Rate, Increase the Batch Size_, ICLR 2018 — growing $B$ is equivalent to decaying $\eta$, since both shrink the $\sqrt{\tr\Sigma/B}$ gradient noise.
[^goyal]: **Goyal et al.**, _Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour_, 2017 — the linear scaling rule ($\eta \propto B$) plus a warmup ramp for very large batches.
[^smith-onecycle]: **Smith & Topin**, _Super-Convergence: Very Fast Training of Neural Networks Using Large Learning Rates_, 2018 — the one-cycle policy (ramp $\eta$ up to a large peak, then down) and super-convergence.