Why stop before the training error is smallest?
When data contain noise, decreasing the training loss can eventually fit noise as well as signal. In linear regression this tension can be calculated exactly, direction by direction. The calculation also shows what its conclusion does not say: an optimal stopping time depends on the unknown signal and noise, and risk on the training inputs need not equal risk on new inputs.
Fix and suppose , where is fixed, , and . No Gaussian or independent-coordinate assumption is needed for the expected squared-error formulas below. We condition on the design throughout. Let and use a thin singular value decomposition
Write for the columns, , and . We minimize by the update from . Use the convention , including when . Here is a nonnegative integer and , where is the largest singular value. If the objective instead has a factor , the permissible step size and the formulas must be rescaled.
Definition 19.1.1
(Fitted-value risk)
The fixed-design prediction risk is
The expectation is over the training noise. This compares fitted values with the noiseless mean at the same design points; it is neither training loss against nor prediction error at new covariates.
A spectral filter and its risk
Theorem 19.1.2
(Exact bias–variance decomposition)
Under the stated assumptions,
Consequently and . These endpoints alone do not determine which intermediate time has the smallest risk.
Proof
(Diagonalize the iteration in singular coordinates)
Put . Multiplying the update by yields
The geometric sum gives . All updates lie in the span of the , giving the first formula. Since , its error coordinate is
The cross term has expectation zero and . Orthogonality of the gives the risk formula. The step-size condition gives , proving the limit.
Proof X-ray
Where the tradeoff enters
Three hypotheses do separate jobs. The start keeps every iterate in the row space spanned by the , so the scalar recursions describe the whole iterate. The SVD decouples the update: each coordinate obeys its own one-dimensional recursion with multiplier , and the geometric sum solves it exactly. The noise assumptions enter only in the last step: removes the cross term between and , and gives each direction the same variance and makes the directions add without interaction. The key move is to measure error in fitted-value coordinates rather than parameter coordinates, so no division by a small appears; parameter error can behave quite differently. The squared bias term retains the signal that has not yet been learned, and the variance term measures the training noise admitted by the same filter . The step-size condition is used only for the limit.
When , all : the filter grows monotonically from zero to one, with larger singular values generally learned sooner. Under the wider stable range some are negative, causing oscillation; the formula remains valid, but the filter can exceed one; the signed bias can alternate and the variance can oscillate, although squared bias remains nonincreasing. Stability of the iteration does not mean every individual iterate is a shrinkage estimator.
Worked example 19.1.3
(One direction: interpolation can increase risk)
Take , , , , and . Then and
At the risks are , , and , respectively. The first update retains half the signal but admits only half the noise; the final fit reproduces all the noise. The realized training loss, however, is , which decreases to zero. Thus the training loss alone does not identify the risk-minimizing time.
Worked example 19.1.4
(Two directions learned at different speeds)
Let , , , and , so that , and . With the convention , the first direction contributes to at (all bias) and at every (all variance): it is learned completely in one step. The second contributes , with
Since with increasing in , and passes between and , the integer minimum is at , where . Both endpoints give .
Worked example 19.1.5
(An oscillating but stable step)
Take , , and , which is inside the stable range . Then and :
The squared bias decreases, but the filter alternates between values above and below one, so the variance term oscillates; at the risk exceeds both and the limit . Stability of the iteration does not make each iterate a shrinkage estimator.
The explorer below evaluates the exact risk , split into squared bias and variance, for a chosen design and stopping time, and shows which ridge penalty would match each direction's filter.
Comparison with ridge regression
For , ridge regression minimizes . Solving in singular coordinates gives fitted-value filter . Early stopping uses . Both suppress small singular directions when , but a common qualitative effect does not make the two filters identical at a single common parameter.
Counterexample mode
One stopping time need not equal one ridge penalty
Take , , and . The gradient filters are and . Matching the first with ridge requires , hence ; matching the second requires , hence . No single matches both, so the fitted vectors differ for data with nonzero components in both directions. At the zero filter is approached only as ; at the nonzero-mode filter is approached as .
The formula is an expectation under an idealized fixed design. It does not prescribe an observable stopping time because and are generally unknown. Validation data, a noise model, or other assumptions are needed for a practical rule. Selecting the time using the same observations changes the estimator and requires its own analysis. In overparameterized problems, components of in are invisible at these inputs, even though they may matter at new inputs.
Common mistake
(Stopping when the training loss stops falling)
The training loss is nonincreasing for and tends to its minimum, so it never signals that noise is being fitted. In the one-direction example it decreases to zero while the risk rises from back to . A stopping rule needs information the training loss does not contain, such as held-out data.
Common mistake
(Keeping the step-size range after rescaling the objective)
For the gradient is , so the multipliers become and the stable range is . Using with the averaged objective is needlessly small, and using with the summed objective diverges.
Practice with solutions
Quick check
(In the one-dimensional example, find the continuous filter value minimizing , and identify the best integer .)
Write the risk as a function of the filter value .
Solution · Answer
Completing the square gives . Thus is optimal; the gradient filter equals it at , so is best among the integer times.
Quick check
(Let , , and . Is the update stable? Is its filter a shrinkage factor in ?)
Compute .
Solution · Answer
Yes, because and has magnitude below one. But : the first fit overshoots. Subsequent iterates converge while alternating around the least-squares fit.
Quick check
(If , , and , compute the fitted vector at and the ridge fitted vector for .)
With diagonal, the singular directions are the coordinate axes.
Solution · Answer
Apply the filters to get . Ridge filters are , giving . Matching one direction does not match the other.
Quick check
(Suppose and . What does this section's risk measure, and what can it say about prediction at covariate ?)
Which coordinates of does see?
Solution · Answer
Here , so fixed-design risk measures error in estimating zero at the sole observed input. The second parameter is invisible to ; the training design supplies no information about its value. Prediction at depends on that component and is not controlled by the displayed fixed-design risk.