Stability of Early-Stopped Gradient Methods

Why the Stopping Time Matters

Gradient descent can produce a useful predictor before it has reached an empirical risk minimizer. That can matter statistically: each update uses the observed sample, so additional updates can increase the influence of any one observation on the final predictor. A stability bound makes this connection precise. Under smoothness and convexity assumptions, it gives an explicit way to track how the iteration count and step sizes control sensitivity to replacing one training example.

We study full-batch gradient descent on the empirical risk. The stopping time is fixed in advance, and the same initialization and step-size sequence are used for every sample. These details matter: a stopping rule chosen using the sample is part of the learning algorithm and is not covered automatically by the fixed-horizon bound.

Setup and Stability

Let $S=(z_1,\ldots,z_n)$ be a sample of size $n$, and let $\ell(w;z)$ be the loss at parameter $w\in\mathbb{R}^d$ on observation $z$. The empirical risk is

F_S(w)=\frac{1}{n}\sum_{i=1}^n \ell(w;z_i).

Starting from a fixed $w_0$, full-batch gradient descent with step sizes $\eta_t>0$ generates

w_{t+1}(S)=w_t(S)-\eta_t\nabla F_S(w_t(S)),\qquad t=0,\ldots,T-1.

The output at iteration $T$ is the early-stopped predictor $A_T(S)=w_T(S)$. Two samples are replace-one neighbors if they have the same size and differ in at most one observation.

Definition: The algorithm $A_T$ has replace-one uniform stability $\epsilon_T$ with respect to loss $\ell$ if, for every pair of replace-one neighboring samples $S,S'$ and every test observation $z$, $$ \left|\ell(A_T(S);z)-\ell(A_T(S');z)\right|\leq \epsilon_T. $$ The bound is uniform because it applies to every neighboring pair and every test point.

We use the following assumptions for the main bound. For every observation $z$, the function $w\mapsto\ell(w;z)$ is convex and differentiable on the whole space $\mathbb{R}^d$, and its gradient is $\beta$-Lipschitz: $\|\nabla\ell(u;z)-\nabla\ell(v;z)\|\leq\beta\|u-v\|$. Also assume $\|\nabla\ell(w;z)\|\leq G$ and that the loss is $L$-Lipschitz in $w$, for all $w,z$. The gradient bound and loss Lipschitz bound are stated separately so their roles in the proof are explicit. Take a fixed step size $0<\eta_t\leq 2/\beta$ at each iteration.

A Smooth Convex Gradient Step Does Not Expand Distances

The key property is that a gradient step on a convex, smooth objective cannot increase the distance between two starting points when the step size is at most $2/\beta$. The domain condition is important: the objective below is defined and smooth on all of $\mathbb{R}^d$, so each point used in the proof is in its domain.

Lemma: Suppose $f:\mathbb{R}^d\to\mathbb{R}$ is convex and differentiable, with $\beta$-Lipschitz gradient for $\beta>0$. For $0\leq\eta\leq 2/\beta$, the gradient map $G_\eta(x)=x-\eta\nabla f(x)$ is nonexpansive: $$ \|G_\eta(x)-G_\eta(y)\|\leq\|x-y\|\qquad\text{for all }x,y\in\mathbb{R}^d. $$

Proof. First, gradient Lipschitzness gives the smoothness inequality $f(v)\leq f(u)+\langle\nabla f(u),v-u\rangle+\frac{\beta}{2}\|v-u\|^2$. To see this directly, integrate the gradient along the line segment from $u$ to $v$. The difference between the resulting integral and the linear term is bounded by $\int_0^1\beta s\|v-u\|^2\,ds=\frac{\beta}{2}\|v-u\|^2$.

We next derive the gradient inequality needed for nonexpansiveness. Fix $x,y$, and define $h(u)=f(u)-\langle\nabla f(y),u\rangle$. This function is convex and $\nabla h(y)=0$, so convexity implies that $y$ is a global minimizer of $h$. Apply the smoothness inequality for $h$ at $x$ with $v=x-\nabla h(x)/\beta$. This point lies in $\mathbb{R}^d$, where $h$ is defined and smooth. It follows that

h(y)\leq h(v)\leq h(x)-\frac{\|\nabla h(x)\|^2}{2\beta}.

Since $\nabla h(x)=\nabla f(x)-\nabla f(y)$, this gives $f(x)-f(y)-\langle\nabla f(y),x-y\rangle\geq \|\nabla f(x)-\nabla f(y)\|^2/(2\beta)$. Interchanging $x$ and $y$ and adding the two inequalities yields

\langle\nabla f(x)-\nabla f(y),x-y\rangle \geq\frac{1}{\beta}\|\nabla f(x)-\nabla f(y)\|^2.

Write $d=x-y$ and $g=\nabla f(x)-\nabla f(y)$. Expanding the squared distance after the gradient step and applying the last inequality gives

\|d-\eta g\|^2 =\|d\|^2-2\eta\langle d,g\rangle+\eta^2\|g\|^2 \leq \|d\|^2+\left(\eta^2-\frac{2\eta}{\beta}\right)\|g\|^2 \leq\|d\|^2.

The last inequality uses $0\leq\eta\leq2/\beta$. Taking square roots proves the claim. $\square$

Stability Bound for a Fixed Stopping Time

The empirical risk $F_S$ is convex and $\beta$-smooth because it is an average of convex, $\beta$-smooth losses. Thus, for a fixed sample, one gradient step on $F_S$ is nonexpansive. Replacing an observation adds a separate perturbation: at any fixed parameter, the two empirical gradients differ by at most $2G/n$.

Theorem: Under the assumptions above, suppose all runs use the same fixed initialization $w_0$, and the step sizes satisfy $0<\eta_t\leq2/\beta$. For any replace-one neighboring samples $S,S'$, $$ \|w_T(S)-w_T(S')\| \leq \frac{2G}{n}\sum_{t=0}^{T-1}\eta_t. $$ Consequently, $A_T$ has replace-one uniform stability at most $$ \epsilon_T\leq \frac{2LG}{n}\sum_{t=0}^{T-1}\eta_t. $$ For a constant step size $\eta$, this becomes $\epsilon_T\leq 2LG\eta T/n$.

Proof. Let $S,S'$ differ only at index $i$, and write $\delta_t=\|w_t(S)-w_t(S')\|$. The iterates start at the same point, so $\delta_0=0$. Add and subtract the update on $F_S$ evaluated at $w_t(S')$, and use the triangle inequality:

\begin{aligned} \delta_{t+1} &\leq \|w_t(S)-\eta_t\nabla F_S(w_t(S)) -[w_t(S')-\eta_t\nabla F_S(w_t(S'))]\|\\ &\quad+\eta_t\|\nabla F_S(w_t(S'))-\nabla F_{S'}(w_t(S'))\|. \end{aligned}

The first term is at most $\delta_t$, by the lemma applied to $F_S$. At the common parameter $w_t(S')$, all but one summand in the two empirical gradients cancel. The gradient bound therefore gives

\|\nabla F_S(w_t(S'))-\nabla F_{S'}(w_t(S'))\| =\frac{1}{n}\|\nabla\ell(w_t(S');z_i)-\nabla\ell(w_t(S');z_i')\| \leq\frac{2G}{n}.

Hence $\delta_{t+1}\leq\delta_t+2\eta_tG/n$. Iterating this inequality from $\delta_0=0$ proves the parameter-distance bound. Finally, the $L$-Lipschitz property of the test loss implies $\left|\ell(w_T(S);z)-\ell(w_T(S');z)\right|\leq L\delta_T$ for every $z$. This proves the stability bound. $\square$

Worked Example: A Logistic-Loss Horizon Bound

Consider binary logistic loss $\ell(w;(x,y))=\log(1+\exp(-yw^\top x))$, with $y\in\{-1,1\}$ and $\|x\|\leq1$. Its gradient is $-yx/(1+\exp(yw^\top x))$, so its norm is at most $1$. The scalar logistic function has second derivative at most $1/4$; consequently the loss gradient is $1/4$-Lipschitz in $w$. The loss is also $1$-Lipschitz in $w$. Thus we may take $G=L=1$ and $\beta=1/4$.

Let $n=200$, use the constant step size $\eta=2$, and stop after $T=15$ iterations. The permitted step-size range is $0<\eta\leq2/\beta=8$, so this choice satisfies the theorem's condition. The stability bound is

\epsilon_T\leq\frac{2(1)(1)}{200}(2)(15)=0.3.

This is a worst-case upper bound on the change in test loss when one training observation is replaced. It is not an assertion that every neighboring pair actually changes the loss by $0.3$.

Worked Example: Exact One-Step Change for Logistic Loss

Take a one-dimensional logistic model with $x=1$, $n=10$, initialization $w_0=0$, and step size $\eta=1$. In $S$, let all ten labels be $+1$. In $S'$, change one label to $-1$, leaving nine labels at $+1$.

At $w=0$, the gradient for a $+1$ label is $-1/2$, and for a $-1$ label it is $+1/2$. Therefore $\nabla F_S(0)=-1/2$, while $\nabla F_{S'}(0)=[9(-1/2)+1/2]/10=-4/10$. The one-step outputs are $w_1(S)=1/2$ and $w_1(S')=2/5$, so their distance is $1/10$. This matches the direct perturbation calculation: the two empirical gradients differ by $1/10$.

For a test point with $x=1,y=+1$, the loss difference is $\left|\log(1+\exp(-1/2))-\log(1+\exp(-2/5))\right|$. The derivative of $q\mapsto\log(1+\exp(-q))$ has absolute value at most $1$. The mean value theorem therefore bounds this difference by $|1/2-2/5|=1/10$. The general theorem gives the looser but valid bound $2LG\eta T/n=2/10$ for $T=1$. The factor of two is a worst-case bound on replacing one gradient by another, not an exact prediction for this particular pair.

From Stability to Expected Generalization

Stability also controls expected generalization. Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $P$, let $S=(Z_1,\ldots,Z_n)$, and define the population risk $R(w)=E_{Z\sim P}[\ell(w;Z)]$ and empirical risk $R_S(w)=n^{-1}\sum_i\ell(w;Z_i)$. Assume the expectations in the following display exist. Uniform stability bounds the expected difference between population and training risk without requiring a high-probability claim.

Result: If a learning algorithm has replace-one uniform stability $\epsilon$, then $$ \left|E\left[R(A(S))-R_S(A(S))\right]\right|\leq\epsilon. $$

Derivation. For each $i$, let $Z_i'$ be an independent draw from $P$, independent of $S$, and let $S^{(i)}$ be $S$ with $Z_i$ replaced by $Z_i'$. By independence and identical distribution, $E[\ell(A(S);Z_i')]=E[R(A(S))]$. Also, the pair $(S^{(i)},Z_i)$ has the same distribution as $(S,Z_i')$: the training sample in each pair consists of $n$ independent draws, and the displayed test observation is an independent draw. It follows that

\begin{aligned} E[R(A(S))-R_S(A(S))] &=\frac{1}{n}\sum_{i=1}^n E[\ell(A(S);Z_i')-\ell(A(S);Z_i)]\\ &=\frac{1}{n}\sum_{i=1}^n E[\ell(A(S^{(i)});Z_i)-\ell(A(S);Z_i)]. \end{aligned}

The two samples in each summand are replace-one neighbors. The absolute value of each loss difference is at most $\epsilon$, so the absolute value of the average expectation is at most $\epsilon$. $\square$

Combining this result with the gradient-descent theorem gives $\left|E[R(A_T(S))-R_S(A_T(S))]\right|\leq (2LG/n)\sum_{t=0}^{T-1}\eta_t$. For constant step size, the bound grows linearly with $T$. This expresses a controlled trade-off: a larger cumulative step size can make the output more sensitive to a single observation. It does not say that more iterations always worsen actual generalization, only that this stability guarantee becomes weaker.

Worked Example: A Decreasing Step-Size Schedule

Suppose $n=50$, $L=2$, $G=2$, $\beta=1$, and the three step sizes are $0.10,0.10,0.05$. Each is at most $2/\beta=2$. Their sum is $0.25$, so the parameter-distance bound for neighboring samples is

\frac{2G}{n}\sum_{t=0}^{2}\eta_t =\frac{4}{50}(0.25)=0.02.

Multiplying by the test-loss Lipschitz constant gives $\epsilon_3\leq L(0.02)=0.04$, and hence the absolute expected generalization gap is at most $0.04$. For comparison, three constant steps of $0.10$ would have total step size $0.30$, giving parameter-distance bound $4(0.30)/50=0.024$ and loss-stability bound $2(0.024)=0.048$. The comparison concerns these guarantees; it does not establish that the two schedules have the same optimization behavior.

Interpretation and a Common Pitfall

The iteration count enters the constant-step bound through the product $\eta T$, while a varying schedule enters through $\sum_t\eta_t$. If the step size is held fixed, stopping earlier gives a smaller stability upper bound. If the number of steps grows while step sizes shrink, the cumulative step size, rather than the count alone, is what appears in this analysis.

Pitfall: treating a fixed-horizon result as a data-dependent stopping result. The proof compares two runs at the same iteration $t$, with the same step size at that iteration. If each sample selects its own stopping time, the runs can stop at different iterations; the recurrence above does not by itself bound that additional difference. Include the stopping rule in the algorithm and analyze its effect, or use a horizon chosen independently of the data.
Pitfall: using a gradient step outside the objective's domain. The nonexpansiveness proof uses the point $x-\nabla h(x)/\beta$. The lemma therefore assumes that the objective is defined and smooth on the whole ambient space. A claim on a restricted domain needs additional conditions ensuring the descent point is in the domain, or a result proved for that domain.
Pitfall: reading an upper bound as an exact trend in test performance. Stability bounds control sensitivity and, under the stated sampling conditions, expected generalization. They do not prove that the training risk decreases at a particular rate or that the actual test risk worsens with every extra step.

Key takeaway: For full-batch gradient descent on convex, smooth losses, each fixed-sample gradient step is nonexpansive when $0<\eta_t\leq2/\beta$. Replacing one observation adds at most $2\eta_tG/n$ to the distance between runs. Thus early stopping controls the resulting stability through the cumulative step size, and uniform stability gives a corresponding expected generalization bound.

Check Your Understanding

Use the assumptions and results above to answer the following.

For a constant step size, how does the stated stability bound change when the stopping time doubles while $n,L,G,\eta$ remain fixed?
Why does the nonexpansiveness proof require attention to the domain of the objective?
In the one-step logistic example, calculate the empirical gradient for the sample with nine positive labels and one negative label.
What quantity replaces $\eta T$ in the stability bound when the step size varies by iteration?
Why does the fixed-horizon argument not automatically cover a stopping time selected separately from each training sample?