Early stopping: Exercises — AI-ML deep dive

Definition Every symbol used on this page (recalled from the parent so you never flip back)

$L_{val}$ — the validation loss: how wrong the model is on data it was never trained on. Lower = better generalization.
$p$ — the patience: how many epochs in a row we allow with no improvement before we stop.
$ε$ — the learning rate: the size of each gradient-descent step. A knob you set.
$λ_{i}$ — the curvature of the loss bowl along eigen-direction $i$ (an eigenvalue of the Hessian). Big $λ_{i}$ = steep, narrow bowl; small $λ_{i}$ = flat, shallow bowl.
$t$ — the number of training steps (gradient updates) taken so far.
$α$ — the weight-decay strength in $L_{2}$ regularization (the size of the penalty on large weights).
min-delta — the smallest drop in $L_{val}$ that we agree to count as a real improvement. If the new loss beats the record by less than min-delta, we treat it as "no improvement" (so the patience counter still ticks up). It is a noise filter: set it just above the jitter and below the real per-epoch gains, so random wiggles don't fool us into thinking we improved.
$[Q^{⊤} w^{*}]_{i}$ — the ideal value of the weights along eigen-direction $i$ (the coordinate of the true minimizer after rotating into the bowl's natural axes).

Common mistake Stability condition — the fine print that makes the formula valid

The clean "each step shrinks the gap by $(1 - ε λ_{i})$ " story only behaves if $0 \leq 1 - ε λ_{i} \leq 1 ⟺ 0 \leq ε λ_{i} \leq 1.$ Why: if $ε λ_{i} > 1$ then $(1 - ε λ_{i})$ is negative and $∣1 - ε λ_{i} ∣$ can exceed $1$ — the weight overshoots and oscillates, and for $ε λ_{i} > 2$ it diverges (blows up). The tidy monotone "travels from $0$ toward $1$ " picture and the map to $L_{2}$ both assume $ε λ_{i} \leq 1$ . Every exercise on this page is built with $ε λ_{i} \leq 0.5$ , safely inside the stable zone, so you can trust the formula — but always sanity-check this before applying it.

The $L_{2}$ counterpart: weight decay $α$ shrinks the same direction to a fraction $\frac{λ _{i}}{λ _{i} + α}$ , so the survived portion is $\frac{α}{λ _{i} + α}$ . Setting the two survived portions equal gives the matching condition $(1 - ε λ_{i})^{t} \approx \frac{α}{λ _{i} + α}$ (valid in that same stable, quadratic regime).

Level 1 — Recognition

Exercise 1.1 (L1)

Here is an epoch-by-epoch validation loss log:

1: 0.80, 2: 0.61, 3: 0.50, 4: 0.47, 5: 0.49, 6: 0.46, 7: 0.51, 8: 0.53

Which epoch holds the best-so-far weights?

Recall Solution

"Best-so-far" means the lowest $L_{val}$ seen up to and including that epoch. Scan the values: the running minimum is $0.80 \to 0.61 \to 0.50 \to 0.47 \to 0.47 \to 0.46 \to 0.46 \to 0.46$ . The smallest value is $0.46$ , occurring at epoch 6. Answer: epoch 6. The dip at epoch 5 ( $0.49$ ) does not reset the record because it is higher than epoch 4's $0.47$ .

Exercise 1.2 (L1)

True or false: the training loss curve is the one that forms a U-shape which early stopping watches for.

Recall Solution

False. Training loss keeps sliding down — the model can always fit the data it sees a little better. It is the validation loss that goes down, bottoms out, then climbs back up (the U-shape). Early stopping watches the validation curve. (This is exactly the two-curve picture described in the "U-shaped validation curve" callout above: training slides down forever, validation makes a valley.)

Level 2 — Application

Exercise 2.1 (L2)

Same log as 1.1, with patience $p = 2$ :

1: 0.80, 2: 0.61, 3: 0.50, 4: 0.47, 5: 0.49, 6: 0.46, 7: 0.51, 8: 0.53

At which epoch does training stop, and which weights are restored?

Recall Solution

The rule: keep a counter of consecutive epochs that fail to beat the running minimum. Reset it to $0$ whenever a new record is set. Stop when the counter reaches $p = 2$ .

Epoch	$L_{val}$	New record?	Counter
1	0.80	yes (first)	0
2	0.61	yes	0
3	0.50	yes	0
4	0.47	yes	0
5	0.49	no	1
6	0.46	yes	0
7	0.51	no	1
8	0.53	no	2 → STOP

Counter hits $p = 2$ at epoch 8, so we stop after epoch 8 and restore the epoch-6 weights (the record holder $0.46$ ), not the epoch-8 weights.

Exercise 2.2 (L2)

Take one eigen-direction with $ε λ_{i} = 0.2$ . After $t = 5$ gradient-descent steps (starting from weight $0$ ), what fraction of the ideal value $[Q^{⊤} w^{*}]_{i}$ has this direction reached? (This fraction is the shrinkage factor.)

Recall Solution

First check stability: $ε λ_{i} = 0.2 \leq 1$ ✓, so the formula applies. Use the page's one formula, the shrinkage factor: $1 - (1 - ε λ_{i})^{t} .$ Why this formula? Each step multiplies the remaining gap by $(1 - ε λ_{i})$ ; after $t$ steps the gap is $(1 - ε λ_{i})^{t}$ , so the fraction covered is one minus that. Plug in: $(1 - 0.2)^{5} = 0. 8^{5} = 0.32768$ . Fraction reached $= 1 - 0.32768 = 0.67232$ . So this direction has travelled about 67% of the way to its ideal value.

Level 3 — Analysis

Exercise 3.1 (L3)

Using the matching condition $(1 - ε λ_{i})^{t} \approx \frac{α}{λ _{i} + α},$ with $ε λ_{i} = 0.1$ , $t = 20$ , and $λ_{i} = 2$ : find the equivalent weight-decay strength $α$ .

Recall Solution

Stability check: $ε λ_{i} = 0.1 \leq 1$ ✓. Step 1 — compute the left side (WHAT): $(1 - 0.1)^{20} = 0. 9^{20}$ . $0. 9^{20} = 0.12158$ (to 5 d.p.). Step 2 — set equal to the shrinkage of $L_{2}$ (WHY): this number is the fraction of the weight that survives shrinkage, and $L_{2}$ survives to the same fraction $\frac{α}{λ _{i} + α}$ . So $\frac{α}{λ _{i} + α} = 0.12158.$ Step 3 — solve for $α$ (the algebra): cross-multiply: $α = 0.12158 (λ_{i} + α) ⟹ α (1 - 0.12158) = 0.12158 λ_{i}$ $α = \frac{0.12158}{0.87842} λ_{i} = 0.13841 λ_{i} .$ With $λ_{i} = 2$ : $α = 0.13841 \times 2 = 0.27682$ . Reading it: 20 steps at this learning rate is like a weight decay of $α \approx 0.277$ in this direction.

Exercise 3.2 (L3)

Two eigen-directions share the same learning rate $ε = 0.1$ . Direction A has curvature $λ_{A} = 5$ (steep bowl), direction B has $λ_{B} = 0.05$ (nearly flat bowl). After $t = 30$ steps, compute each shrinkage factor and explain what early stopping is doing to each.

Recall Solution

Stability check: $ε λ_{A} = 0.5 \leq 1$ ✓ and $ε λ_{B} = 0.005 \leq 1$ ✓. Shrinkage factor $= 1 - (1 - ε λ)^{30}$ .

Direction A: $ε λ_{A} = 0.1 \times 5 = 0.5$ . $(1 - 0.5)^{30} = 0. 5^{30} \approx 9.3 \times 1 0^{- 10} \approx 0$ . Factor $\approx 1 - 0 = 1.0$ → fully fit.

Direction B: $ε λ_{B} = 0.1 \times 0.05 = 0.005$ . $(1 - 0.005)^{30} = 0.99 5^{30} \approx 0.86006$ . Factor $\approx 1 - 0.86006 = 0.13994$ → barely moved, ~14%.

What early stopping did: it let the high-curvature direction A converge completely (these encode strong, general signal that reduces loss fast) while suppressing the low-curvature direction B (these barely move in the time budget, so they stay near $0$ — exactly like weight decay killing small-eigenvalue directions).

The figure below makes this concrete. The horizontal axis is training steps $t$ , the vertical axis is the shrinkage factor (fraction reached). The magenta curve (steep bowl, $λ_{A} = 5$ ) shoots up to $1.0$ within a few steps and stays pinned there — this direction is kept. The violet curve (flat bowl, $λ_{B} = 0.05$ ) crawls, reaching only ~ $0.14$ by the dashed orange stop line at $t = 30$ — this direction is suppressed. Equal number of steps, wildly unequal distance travelled.

Figure: shrinkage factor $1 - (1 - ε λ)^{t}$ vs training step $t$ , for a steep eigen-direction (magenta, kept) and a flat one (violet, suppressed); orange dashed line marks where we stop, $t = 30$ steps.

Level 4 — Synthesis

Exercise 4.1 (L4)

You have $10, 000$ samples. A colleague uses a validation set of only $100$ samples and finds the validation loss jitters by $\pm 0.04$ epoch-to-epoch. Their real improvements per epoch near the minimum are about $0.01$ . With patience $p = 3$ , explain quantitatively why they keep stopping too early, then propose two independent fixes.

Recall Solution

The core problem: the noise band ( $\pm 0.04$ ) is four times larger than the signal (real improvement $\approx 0.01$ ). Near the minimum a genuine improvement of $0.01$ is easily hidden inside a random $- 0.04$ dip followed by a $+ 0.04$ bounce. So the "running minimum" can be set by a lucky noise spike, after which real improvements of $0.01$ can't beat it for many epochs → the patience counter fills up → premature stop, i.e. underfitting.

Fix 1 — bigger validation set. Validation-loss noise shrinks roughly like $1/ N_{val}$ . Going from $100$ to $1, 600$ samples cuts the jitter by $1600/100 = 16 = 4 \times$ , from $\pm 0.04$ down to $\approx \pm 0.01$ — now noise $\approx$ signal, which is workable. (For the theory of why bigger sets give steadier estimates see Validation and Cross-Validation.)

Fix 2 — larger patience and a sensible min-delta. Raise $p$ (e.g. $p = 10$ ) so a run of noise-driven misses doesn't trigger a stop. And recall min-delta is the minimum drop that counts as improvement: set it below the real signal (say $0.005 < 0.01$ ) so genuine gains still register, but above zero so pure noise wiggles of a fraction of the jitter don't keep falsely resetting the counter. Note how min-delta and patience cooperate: min-delta filters what counts as an improvement per epoch, while patience decides how many non-improvements to tolerate. Smoothing the monitored curve (moving average over a few epochs) is an equivalent third option.

Why the two fixes are independent: Fix 1 attacks the noise itself; Fix 2 attacks our tolerance for noise. Either helps; together they are robust.

Exercise 4.2 (L4)

Recall (parent note) that "more steps $t$ plays the role of $\frac{1}{α}$ ." A decaying learning rate means $ε$ shrinks over training. Argue what a decaying $ε$ does to the effective regularization near the end of training, using the shrinkage formula.

Recall Solution

Look at the surviving fraction $(1 - ε λ_{i})^{t}$ . Progress in one step multiplies the remaining gap by $(1 - ε λ_{i})$ : larger $ε$ = bigger cut, faster arrival = weaker effective regularization (as long as we stay in the stable zone $ε λ_{i} \leq 1$ ). As $ε$ decays toward the end, each late step barely changes the gap $(1 - ε λ_{i} \to 1)$ . So:

Early training (large $ε$ ): weights move fast, high-curvature directions lock in.
Late training (small $ε$ ): weights nearly freeze — the effective number of "useful" steps stops growing, so the effective $α$ stops shrinking. The model settles at a fixed regularization strength instead of drifting toward $α \to 0$ (no regularization).

Synthesis takeaway: a decaying schedule and early stopping cooperate — the decay naturally slows the march toward overfitting, giving early stopping a gentler, less noisy minimum to catch. See Gradient Descent for the underlying update rule.

Level 5 — Mastery

Exercise 5.1 (L5)

Design problem. You are told: $ε = 0.05$ , a "signal" eigen-direction has $λ_{sig} = 8$ , a "noise" eigen-direction has $λ_{noise} = 0.1$ . You want the noise direction shrunk to at most 25% of its ideal value (fraction reached $\leq 0.25$ ) while the signal direction reaches at least 99%. Find a number of steps $t$ (an integer) that satisfies both, or prove none exists.

Recall Solution

Stability check first: $ε λ_{sig} = 0.05 \times 8 = 0.4 \leq 1$ ✓ and $ε λ_{noise} = 0.05 \times 0.1 = 0.005 \leq 1$ ✓. Both directions are in the stable, monotone regime, so the shrinkage formula applies cleanly.

Set up the two inequalities using the shrinkage factor $1 - (1 - ε λ)^{t}$ .

Noise constraint (want it small): fraction $\leq 0.25$ $1 - (1 - 0.005)^{t} \leq 0.25 ⟹ (0.995)^{t} \geq 0.75.$ Take logs (log is monotone; $ln 0.995 < 0$ , so the inequality flips): $t \leq \frac{l n 0.75}{l n 0.995} = \frac{- 0.287682}{- 0.005013} \approx 57.4.$ So $t \leq 57$ .

Signal constraint (want it large): fraction $\geq 0.99$ $1 - (1 - 0.4)^{t} \geq 0.99 ⟹ (0.6)^{t} \leq 0.01.$ $t \geq \frac{l n 0.01}{l n 0.6} = \frac{- 4.60517}{- 0.510826} \approx 9.02.$ Since $t = 9$ gives $0. 6^{9} \approx 0.01008 > 0.01$ (just fails) and $t = 10$ gives $0. 6^{10} \approx 0.00605 < 0.01$ (passes), we need $t \geq 10$ .

Combine: we need $10 \leq t \leq 57$ . This range is non-empty, so a valid budget exists — for instance $t = 30$ steps.

Check $t = 30$ :

Signal fraction $= 1 - 0. 6^{30} = 1 - (\approx 2.2 \times 1 0^{- 7}) \approx 0.9999998 \geq 0.99$ ✓
Noise fraction $= 1 - 0.99 5^{30} = 1 - 0.86006 = 0.13994 \leq 0.25$ ✓

Answer: any integer $t \in [10, 57]$ steps works; $t = 30$ is a safe pick. The steep signal direction converges in ~10 steps while the flat noise direction stays well below the 25% cap for up to 57 steps — a wide window, which is exactly why early stopping is forgiving in practice.

Exercise 5.2 (L5)

Conceptual mastery. In two sentences, explain why early stopping is called an implicit regularizer while $L_{2}$ (weight decay) is explicit, even though the parent note proves they are approximately equal. Then state the one situation where the equivalence breaks.

Recall Solution

Explicit vs implicit: $L_{2}$ adds a term $\frac{α}{2} ∥ w ∥^{2}$ directly to the objective — the regularization is written into the math you optimize. Early stopping changes nothing in the objective; it regularizes only as a side effect of not finishing the optimization, so the penalty is never written down (implicit) — its "strength" is hidden inside the stopping time $t$ .

Where the equivalence breaks: the proof relies on the quadratic (bowl) approximation of the loss near a single minimizer, with a fixed learning rate $ε$ satisfying the stability condition $ε λ_{i} \leq 1$ , and plain gradient descent. That is where the clean map $t \leftrightarrow \frac{1}{α}$ holds. The moment the real loss stops looking like one clean bowl — non-quadratic landscapes, several competing minima, momentum, or adaptive/decaying learning rates — the eigen-directions no longer shrink by the tidy independent factors $(1 - ε λ_{i})^{t}$ , so early stopping and $L_{2}$ only roughly agree rather than matching exactly.

One-line takeaway: they coincide only in the local quadratic regime (the loss-bowl picture from Hessian and Curvature); outside it, treat them as related-but-distinct tools — a theme in Overfitting and Generalization.

Recall One-line self-check before you leave

The shrinkage factor $1 - (1 - ε λ_{i})^{t}$ answers: "how far did direction $i$ travel in $t$ steps?" ::: Steep ( $λ$ big) → near $1$ (kept); flat ( $λ$ small) → near $0$ (suppressed) — provided $ε λ_{i} \leq 1$ so steps stay stable. Stopping the clock ≈ weight decay.