Validation of Early-Stopped Iterative Algorithms

Why the Iteration Count Is a Tuning Choice

An iterative learning algorithm produces a sequence of predictors: one after the first update, another after the second, and so on. Continuing the algorithm may improve its fit to the training data while eventually worsening prediction on new observations. Early stopping addresses this by choosing an iteration count using validation data. The count is therefore a tuning parameter, just like a choice among other candidate procedures.

There are two related sources of optimism to keep distinct. First, selecting the lowest point on a validation curve makes the reported minimum tend to be lower than the selected predictor’s true risk. Second, if the analyst uses validation results to change the algorithm or invent additional candidates, the candidates may no longer form a fixed path independent of validation data. The first effect occurs even when the path is fixed; the second is a further form of adaptive reuse.

Definition: Let $D_{\mathrm{tr}}$ be training data and let an iterative algorithm, run using only $D_{\mathrm{tr}}$, produce predictors $f_t(D_{\mathrm{tr}})$ at iterations $t\in\mathcal T=\{0,1,\ldots,T\}$. For a new observation $Z$ from the target population and a loss function $L$, define the conditional risk $$ R_t(D_{\mathrm{tr}})=E[L(f_t(D_{\mathrm{tr}}),Z)\mid D_{\mathrm{tr}}]. $$ For an independent validation sample $V=(Z_1,\ldots,Z_m)$, define $$ \widehat R_t=\frac{1}{m}\sum_{i=1}^m L(f_t(D_{\mathrm{tr}}),Z_i),\qquad \hat t\in\arg\min_{t\in\mathcal T}\widehat R_t. $$ The stopping iteration $\hat t$ is selected by validation. A fixed tie-breaking rule may be used when the minimum is attained more than once.

The risk here is conditional on the training data: once that data are fixed, the entire candidate path is fixed as well. The validation sample must be independent of the training data and, conditional on the training data, consist of independent observations from the target population. This setup lets us analyze selection from one finite, prespecified path. It does not assume the validation losses for different iterations are independent; in practice they are often strongly correlated.

Reading a Validation Curve

A training-loss curve and a validation-risk curve answer different questions. Training loss measures fit to the data used to construct the path. Validation risk estimates how each fixed predictor on that path performs on fresh observations. A decrease in training loss alone does not establish that later iterations predict better.

Worked Example: Training Fit Improves After Validation Risk Turns Up

Suppose a one-parameter predictor is the constant $a_t$. On the training data, the response is $2$, and the algorithm starts at $a_0=0$ and updates by $$ a_{t+1}=a_t+\frac{1}{4}(2-a_t). $$ The training squared-error loss is $(a_t-2)^2$. Calculate the first five iterates and compare this loss with validation risk on four responses $0,0,2,2$.

Applying the update gives $a_0=0$, $a_1=0.5$, $a_2=0.875$, $a_3=1.15625$, and $a_4=1.3671875$. The corresponding training losses are $$ 4,\quad 2.25,\quad 1.265625,\quad 0.7119140625,\quad 0.40045166015625. $$ Thus the training loss decreases at every displayed step.

For a constant $a$, the validation squared-error risk on the four responses is $$ \frac{2a^2+2(a-2)^2}{4}=(a-1)^2+1. $$ Substituting the iterates gives validation risks $2$ at $t=0$, $1.25$ at $t=1$, $1.015625$ at $t=2$, $1.0244140625$ at $t=3$, and $1.13482666015625$ at $t=4$. For instance, at $t=4$, the risk is $\{2(1.86920166015625)+2(0.40045166015625)\}/4=1.13482666015625$.

Among these five candidates, validation selects $t=2$, even though training loss continues to decrease through $t=4$. The curve indicates a best stopping point among the iterations examined; it does not establish that this point is optimal among all possible predictors.

In this example, the four validation responses can be regarded as a sample from a population that assigns probability $1/2$ to each of $0$ and $2$. Their average squared loss for a constant $a$ equals the population risk $(a-1)^2+1$. In general, the validation curve is random, and inspecting several candidate iterations makes the selected minimum subject to selection optimism.

A Risk Guarantee for a Fixed Path

A finite-path guarantee makes the role of validation selection precise. Suppose all validation losses lie in an interval of length $B$, such as $[0,B]$. Conditional on the training data, Hoeffding’s inequality gives, for any fixed iteration $t$ and any $u>0$, $$ P\left(\left|\widehat R_t-R_t\right|>u\mid D_{\mathrm{tr}}\right) \le 2\exp\left(-\frac{2mu^2}{B^2}\right). $$ This applies to each iteration because its predictor is fixed conditional on training data. A union bound then controls the deviations for the whole path at once.

Theorem: Suppose the path $\{f_t(D_{\mathrm{tr}}):t\in\mathcal T\}$ is constructed without using validation data, $|\mathcal T|=K<\infty$, the validation observations are independent draws from the target population conditional on $D_{\mathrm{tr}}$, and $0\le L(f_t(D_{\mathrm{tr}}),Z)\le B$ for every candidate and observation. Then, for any $0<\delta<1$, with conditional probability at least $1-\delta$, $$ R_{\hat t}\le \min_{t\in\mathcal T}R_t+ 2B\sqrt{\frac{\log(2K/\delta)}{2m}}. $$

Proof. Set $\varepsilon=B\sqrt{\log(2K/\delta)/(2m)}$. For each fixed $t$, Hoeffding’s inequality bounds the conditional probability that $|\widehat R_t-R_t|>\varepsilon$ by $2\exp(-2m\varepsilon^2/B^2)=\delta/K$. By the union bound, the conditional probability that this deviation exceeds $\varepsilon$ for at least one of the $K$ iterations is at most $\delta$. Thus, with probability at least $1-\delta$, every iteration satisfies $|\widehat R_t-R_t|\le\varepsilon$.

On this event, choose $t^\star$ with $R_{t^\star}=\min_{t\in\mathcal T}R_t$. The selected iteration satisfies $$ R_{\hat t}\le\widehat R_{\hat t}+\varepsilon \le\widehat R_{t^\star}+\varepsilon \le R_{t^\star}+2\varepsilon. $$ The middle inequality holds because $\hat t$ minimizes validation risk over the path. Substitution of $\varepsilon$ proves the result. $\square$

The guarantee compares the selected iterate with the best true-risk iterate on this same path. It does not say the selected iterate beats every predictor outside the path, and it does not remove the gap between the path’s best risk and the best risk achievable by some other procedure. Its bound becomes less informative as $K$ grows or $m$ shrinks.

Worked Example: Interpreting a Finite-Path Bound

Suppose an algorithm has five prespecified stopping iterations, validation losses lie in $[0,1]$, and the validation sample has $m=100$ observations. For $\delta=0.05$, the theorem uses $$ \varepsilon=\sqrt{\frac{\log(2\cdot5/0.05)}{2\cdot100}} =\sqrt{\frac{\log(200)}{200}} \approx 0.1628. $$

With probability at least $0.95$, the true risk at the validation-selected iteration is no more than $2\varepsilon\approx0.3255$ above the smallest true risk among those five iterations. This is a valid but potentially loose guarantee; it is not a claim that validation risk is within $0.3255$ of every candidate’s risk, or that the chosen iteration is optimal beyond the five examined.

Why the Minimum Validation Risk Can Be Optimistic

Even when the path is fixed in advance, selection favors iterations whose validation errors happen to be low. A bound for the expected size of this effect makes the point directly. Write the optimism gap as $R_{\hat t}-\widehat R_{\hat t}$. Because $\widehat R_{\hat t}$ is the minimum validation risk, this gap is bounded above by the largest risk-minus-validation deviation among the candidates.

Result: Under the theorem’s bounded-loss and fixed-path assumptions, conditional on the training data, $$ E[R_{\hat t}-\widehat R_{\hat t}\mid D_{\mathrm{tr}}] \le B\sqrt{\frac{\log K}{2m}}. $$ For $K=1$, the right side is zero and the validation estimate is unbiased for the single fixed candidate’s risk.

Derivation. For each $t$, let $Z_t=R_t-\widehat R_t$. Since $\hat t$ minimizes validation risk, $$ R_{\hat t}-\widehat R_{\hat t} \le \max_{t\in\mathcal T}(R_t-\widehat R_t)=\max_{t\in\mathcal T}Z_t. $$ Conditional on training data, Hoeffding’s lemma for a random variable in an interval of length $B$ implies $$ E[\exp(\lambda Z_t)\mid D_{\mathrm{tr}}] \le \exp\left(\frac{\lambda^2B^2}{8m}\right),\qquad \lambda>0. $$ No independence across the $Z_t$'s is required. Using $\exp(\lambda\max_t Z_t)\le\sum_t\exp(\lambda Z_t)$, followed by Jensen’s inequality for the concave logarithm, gives $$ E[\max_t Z_t\mid D_{\mathrm{tr}}] \le \frac{\log K}{\lambda}+\frac{\lambda B^2}{8m}. $$ For $K>1$, choose $\lambda=\sqrt{8m\log K}/B$. Both terms then equal $B\sqrt{\log K/(8m)}$, so their sum is $B\sqrt{\log K/(2m)}$. When $K=1$, $Z_1$ has conditional mean zero, giving the stated bound directly. Combining this with the first inequality proves the result. $\square$

Worked Example: Two Stopping Iterations and a Visible Optimism Gap

Let the response $Y$ be Bernoulli with $P(Y=1)=P(Y=0)=1/2$, and use zero-one loss. Consider a two-step candidate path whose predictors at iterations $0$ and $1$ always predict $0$ and $1$, respectively. Each has true risk $1/2$. Use an independent validation sample of size $2$, and let $K_V$ be the number of validation responses equal to $1$.

The empirical risks are $\widehat R_0=K_V/2$ and $\widehat R_1=(2-K_V)/2$. If $K_V=0,1,2$, the selected minimum is respectively $0, 1/2, 0$. These cases have probabilities $1/4,1/2,1/4$, so the expected selected validation risk is $$ \frac14(0)+\frac12\left(\frac12\right)+\frac14(0)=\frac14. $$ The selected predictor still has true risk $1/2$, whichever candidate is selected. Thus the expected optimism gap is $1/2-1/4=1/4$. The candidate validation risks are dependent, since their sum is always $1$; independence between candidates was not needed for selection to create optimism.

Using the Curve Without Expanding Its Scope

A validation curve is most straightforward to interpret when the algorithm, its updates, and the set of iterations to examine are specified without looking at validation results. In that case, selecting the minimum is a finite-candidate selection problem, and the bounds above account for the number of stopping choices. Correlation between adjacent iterates may make their observed losses move together, but it does not invalidate the union-bound guarantee.

A different situation arises if the analyst sees the curve, changes the learning rate or model, and then keeps using the same validation sample to compare the revised candidates. The final path now depends on the validation data. The fixed-path argument above no longer applies as stated: conditional on training data alone, the candidate predictors are not all fixed. Repeatedly querying or adapting to a holdout is the broader problem of adaptive validation reuse. A fresh independent assessment set or a design that accounts for the full adaptive procedure is needed to assess performance honestly.

Common mistake: “The training loss keeps falling, so I should run more iterations,” or, conversely, “The minimum point on the validation curve is an unbiased estimate of the chosen model’s risk.” The first statement confuses fit to training data with prediction risk. The second ignores that the minimum was selected from noisy estimates. Training loss can keep falling while validation risk rises, and the selected validation minimum can be optimistic even on a fixed path. Report the selection rule and its candidate path, and do not treat the same minimum used for tuning as an independent final performance assessment.

Key takeaway: Early stopping selects an iteration from an algorithmic path. Independent validation data can compare a prespecified finite path and provide a risk guarantee, but the minimum validation value is subject to selection optimism. Letting validation results reshape the path requires additional protection against adaptive reuse.

Check Your Understanding

Use the definitions and results above to answer these questions.

Why is the number of iterations a tuning parameter even when the update rule is fixed?
What independence condition makes the finite-path validation bound applicable?
In the squared-error example, why does decreasing training loss not imply that the later iterate has lower validation risk?
For a fixed path, why does selecting the minimum validation risk create a possible optimism gap even when candidate validation risks are dependent?
What changes if the analyst modifies the learning algorithm after inspecting the validation curve and reuses that same validation sample?