Early stopping and non-parametric regression: An optimal data-dependent stopping rule

Garvesh Raskutti; Martin J. Wainwright; Bin Yu

Source-linked AI summary

Early stopping and non-parametric regression: An optimal data-dependent stopping rule

Garvesh Raskutti, Martin J. Wainwright, Bin Yu

arXiv:1306.3574v1Jun 15, 2013stat.ML

TL;DR

The paper asks whether nonparametric RKHS regression can use an easily computable, data-dependent stopping rule instead of hold-out or cross-validation selection. It analyzes gradient descent, proves error bounds, and shows minimax-optimal rates for several kernel classes, while relating the stopping path to kernel ridge regression.

Problem
The paper addresses the open question of whether a data-dependent and easily computable stopping rule can produce a minimax-optimal estimator for nonparametric RKHS regression.
Method
It analyzes gradient descent on the unregularized least-squares loss in a transformed coordinate system and selects stopping using data-derived step-size sums and empirical kernel eigenvalues.
Results
The stopping rule achieves minimax-optimal rates for low-rank kernel classes and Sobolev spaces, with bounds for empirical and population errors.
Takeaways & Limitations
Early stopping provides a computationally simpler regularization route with theoretically optimal rates and a regularization path closely related to kernel ridge regression.
Takeaways & Limitations
The method relies on computing empirical kernel-matrix eigenvalues and has not yet been adapted to mis-specified models.

Abstract

from arXiv · show

The strategy of early stopping is a regularization technique based on choosing a stopping time for an iterative algorithm. Focusing on non-parametric regression in a reproducing kernel Hilbert space, we analyze the early stopping strategy for a form of gradient-descent applied to the least-squares loss function. We propose a data-dependent stopping rule that does not involve hold-out or cross-validation data, and we prove upper bounds on the squared error of the resulting function estimate, measured in either the $L^2(P)$ and $L^2(P_n)$ norm. These upper bounds lead to minimax-optimal rates for various kernel classes, including Sobolev smoothness classes and other forms of reproducing kernel Hilbert spaces. We show through simulation that our stopping rule compares favorably to two other stopping rules, one based on hold-out data and the other based on Stein's unbiased risk estimate. We also establish a tight connection between our early stopping strategy and the solution path of a kernel ridge regression estimator.

1 Introduction

The paper addresses whether early stopping can provide a data-dependent, easily computable, minimax-optimal estimator for nonparametric RKHS regression. It analyzes gradient descent and derives theoretical guarantees for empirical and population error.

Motivation: Early stopping regularizes unregularized gradient descent and can reduce computational complexity relative to penalized regularization.The paper contrasts early stopping with Tikhonov regularization for nonparametric regression.
Open question: Prior work left open whether a data-dependent and easily computable stopping rule could produce a minimax-optimal estimator.
Contribution: The paper answers this question for nonparametric regression when the regression function belongs to an RKHS.
Contribution: The proposed rule stops when the running sum of step sizes exceeds the critical bias–variance trade-off determined from the data.
Results: For low-rank kernels and Sobolev spaces, the resulting estimator achieves minimax-optimal rates, with bounds for empirical and population errors.
Results: The analysis combines analytic and empirical-process techniques and compares the rule with hold-out-based stopping in simulations.

2 Background and problem formulation

The paper formulates nonparametric regression in an RKHS, represents functions through kernel eigenfunctions, and studies a transformed-coordinate gradient update. Simulations illustrate decreasing then increasing prediction error as iterations continue.

2.1 Non-parametric regression and kernel classes: Nonparametric regression estimates f*(x) = E[Y | x] from covariate–response samples under random or fixed design.
2.1 Non-parametric regression and kernel classes: The model assumes zero-mean sub-Gaussian noise, including Gaussian noise as a special case.
2.1 Non-parametric regression and kernel classes: An RKHS is a complete function space with a reproducing kernel, and its eigenfunctions form an L2(P)-orthonormal basis.
2.1 Non-parametric regression and kernel classes: RKHS classes include polynomial, Sobolev, Gaussian, Laplacian, spline, and other kernels, subject to a uniform boundedness condition in the analysis.
2.2 Gradient update equation: The estimator restricts functions to the span of empirical kernel functions and uses the empirical kernel matrix, its square root, and a transformed coordinate system for gradient descent.
2.2 Gradient update equation: The procedure starts from θ0 = 0 with user-chosen positive step sizes and measures both empirical L2(P_n) and population L2(P) error.
2.3 Overfitting and early stopping: In simulations with n = 100 and Gaussian noise, gradient descent used constant step size α = 0.25 on Sobolev and Gaussian kernels.
2.3 Overfitting and early stopping: Prediction error decreased rapidly, reached a minimum before or around T ≈ 20 iterations, and then increased as later iterations fitted noise.

3 Main results and their consequences

The paper defines a computable stopping rule from empirical kernel complexity and step-size accumulation, then establishes high-probability error bounds for fixed and random designs. These results yield minimax-optimal rates for several kernel classes and clarify computational and statistical links with kernel ridge regression.

Stopping rule: The stopping rule uses empirical kernel eigenvalues, local empirical Rademacher complexity, and the running step-size sum η_t to choose a data-dependent iteration.The eigenvalues are computable from the data, while η_t acts as a tuning parameter controlling the bias–variance tradeoff.
General error bounds: Theorem 1 gives high-probability squared-error bounds before, at, and after the selected stopping time for fixed-design regression.Before the threshold, updates reduce prediction error; after it, the theorem supplies a lower bound indicating over-iteration.
General error bounds: Theorem 2 extends analogous squared L2(P)-error bounds to randomly sampled covariates, while the general theory applies to any RKHS.The proofs combine direct analysis of the gradient update with empirical-process and concentration techniques.
Specific kernel classes: For polynomial eigenvalue decay and finite-rank kernels, the stopping rule achieves minimax-optimal rates, including the Sobolev and first-order spline settings.The cited corollaries establish optimality through known non-parametric regression lower-bound results.
Kernel ridge connection: Gradient-descent and kernel-ridge solution paths are theoretically connected and qualitatively similar, while gradient updates require O(n^2) operations versus O(n^3) for repeatedly solving kernel ridge regression.The comparison varies the ridge inverse penalty and follows 100 gradient iterations.

4 Proofs

The proofs analyze gradient descent through the empirical kernel matrix's eigendecomposition and diagonal shrinkage matrices, yielding bias–variance bounds that support stopping-time guarantees in empirical and population norms. Auxiliary lemmas control shrinkage, bias, variance, norm comparisons, and critical radii, while a parallel decomposition supports kernel ridge regression comparisons.

Proof strategy: The gradient recursion is rewritten using the empirical kernel matrix's eigendecomposition, enabling analysis through diagonal shrinkage matrices.The shrinkage matrices quantify movement toward the origin and are bounded using the step sizes and kernel eigenvalues.
Theorem 1: A bias/variance decomposition bounds the squared empirical error at every iteration, after which separate lemmas control the two components with high probability.The proof combines these componentwise bounds to establish the upper bound before the stopping time and the lower bound after it.
Corollaries: For Sobolev-type eigenvalue decay, the proof bounds the critical radius and obtains the rate ε_n ≍ (σ^2/n)^(ν/(2ν+1)).The rate follows by verifying the critical inequality for the kernel complexity function.
Kernel ridge regression: The kernel ridge regression proof uses an analogous ridge shrinkage matrix and bias/variance decomposition for the estimator indexed by penalty parameter ν.This establishes the comparison framework between early-stopping iterates and kernel ridge regression.

5 Discussion

The discussion concludes that the data-dependent stopping rule achieves the paper's theoretical guarantees and connects early stopping to kernel ridge regression. It also identifies model misspecification and exact eigenvalue computation as directions for improvement.

5 Discussion: The stopping rule yields upper bounds for empirical and population L2 error and minimax-optimal rates for low-rank kernel classes and Sobolev spaces.Simulations also report theoretically optimal convergence rates for Lipschitz kernels.
5 Discussion: Simulations find favorable performance compared with stopping rules based on hold-out data and Stein's Unbiased Risk Estimate.This comparison is reported alongside the theoretical-rate result for Lipschitz kernels.
5 Discussion: Early stopping with cumulative step sizes η_t = Σ_{k=0}^{t−1} α_k has nearly identical mean-squared error bounds to kernel ridge regression indexed by ν.The result establishes a close connection between the early-stopping regularization path and the ridge solution path.
5 Discussion: The analysis assumes a correctly specified model and requires computation of the kernel-matrix eigenvalues, leaving approximate-eigenvalue stopping rules for future work.The paper specifically suggests subsampling as one possible route to approximate eigenvalue computation.

A Derivation of gradient descent updates

The appendix derives the gradient-descent update by differentiating a transformed least-squares loss and substituting the resulting gradient into the iterative recursion.

A Derivation of gradient descent updates: Gradient descent operates through θ_{t+1} = θ_t − α_t∇eL(θ_t), starting from t = 0.The transformed parameterization is used to express the algorithmic update underlying equation (9).
A Derivation of gradient descent updates: Taking the gradient of the transformed loss and substituting it into the recursion yields the stated gradient-descent update.The appendix records this substitution as the derivation of claim (9).

B Auxiliary lemmas for Theorem 1

The appendix collects the proofs of the auxiliary lemmas used to establish Theorem 1.

B Auxiliary lemmas for Theorem 1: The auxiliary-lemma proofs for Theorem 1 are gathered together in the appendix.The main text presents the proof steps while deferring more technical results to the appendices.

B.1 Proof of Lemma 1

The proof analyzes the gradient-descent iteration in SVD-based coordinates, unwraps the resulting recursion, and bounds the distance to the target using shrinkage matrices and orthogonality.

B.1 Proof of Lemma 1: The gradient-descent iteration is rewritten in an alternative coordinate system based on the empirical kernel matrix SVD.The transformed sequence is analyzed through the corresponding gradient recursion.
B.1 Proof of Lemma 1: Unwrapping the recursion expresses the estimation error through the shrinkage matrices and a rotated noise vector.The initialization γ0 = 0 is used in obtaining the unrolled expression.
B.1 Proof of Lemma 1: The squared error is bounded by separating the relevant terms with an elementary norm inequality and exploiting vanishing coefficients beyond the effective rank.The proof then uses orthogonality of U to translate the transformed-coordinate bound back to the original function values.

B.2 Proof of Lemma 3

The proof derives bounds from the shrinkage-matrix definition using exponential inequalities, including 1 − u ≤ exp(−u) and exp(−u) ≤ (1 + u)^−1.

B.2 Proof of Lemma 3: The shrinkage-matrix definition is combined with 1 − u ≤ exp(−u) to obtain an upper bound.This inequality controls the relevant shrinkage factors.
B.2 Proof of Lemma 3: A remaining bound is established by applying 1 − u ≤ exp(−u) and exp(−u) ≤ (1 + u)^−1 for u > 0.The proof explicitly identifies these two inequalities as the bases for its successive steps.

C Auxiliary results for Proposition 1

This section supplies auxiliary results for kernel ridge regression and establishes existence and uniqueness properties for the critical radius and the associated stopping point.

C Auxiliary results for Proposition 1: The appendix introduces auxiliary lemmas used in the proof of Proposition 1 on kernel ridge regression.The KRR estimate is manipulated algebraically using its defining expression and a shrinkage matrix.
C Auxiliary results for Proposition 1: The critical radius bεn exists and is unique because bRK(ε) is non-increasing, nε^2 is increasing, and bRK(ε) is continuous.It satisfies the stated fixed point equation.
C Auxiliary results for Proposition 1: The stopping point bT is unique and lies in [0, ∞) for any valid sequence of step-sizes.The argument uses η0 = 0, ηt → ∞, and bεn ∈ (0, ∞).
C Auxiliary results for Proposition 1: A separate appendix is devoted to auxiliary lemmas used in proving Theorem 2.

E.1 Proof of Lemma 4

The proof bounds the gradient-descent error by decomposing it into deterministic and noise-related quadratic forms, then controls their means, operator norms, and Frobenius norms up to the stopping time.

E.1 Proof of Lemma 4: The proof uses the kernel eigendecomposition and gradient-update relation to express the relevant quantities through diagonal eigenvalue operators.The empirical kernel complexity and shrinkage factors enter the subsequent bounds.
E.1 Proof of Lemma 4: The deterministic component is bounded using the observation equation and a previously established inequality involving the target function.The remaining random terms are then bounded through the At and Bt analyses.
E.1 Proof of Lemma 4: The error analysis separates the terms At and Bt, with Bt treated as a quadratic form in independent zero-mean sub-Gaussian noise variables.A sub-Gaussian tail bound is then used to control Bt.
E.1 Proof of Lemma 4: The proof separately bounds the operator norm and Frobenius norm of UQU^T and combines these estimates with the stopping-rule inequality.The resulting claim holds for any t ≤ bT.
E.1 Proof of Lemma 4: E[Bt] ≤ 1 for every t ≤ bT.This follows from the stopping-rule definition together with the assumed noise covariance bound.

E.2 Proof of Lemma 6

The proof establishes the target bound by combining Gaussian concentration, deterministic comparisons from Mendelson’s results, and a conditioning argument on two high-probability events.

Conclusion: Because both conditioning events hold with the stated probability, the chained inequalities establish the claim bεn ≤ εn.The final step uses the prescribed parameter substitutions and the definition of εn.
Proof setup: The proof introduces random variables driven by i.i.d. standard normal weights and their associated deterministic functions.These quantities form the objects used in the subsequent concentration and comparison arguments.
Deterministic comparisons: Mendelson’s results provide universal-constant comparisons between Qn(t) and RK(t), and between bQn(t) and bRK(t), for t2 ≥ 1/n.Specifically, each empirical quantity is bounded above and below by constant multiples of its corresponding RK quantity.
Concentration: Gaussian concentration is applied after showing that the relevant maps of the weight vector are Lipschitz with respect to the ℓ2 norm.The proof establishes this property for both bZn(w, t) and Zn(w, t), then invokes standard concentration results.
Event-based argument: Conditioning on the events A(t, t0) and A′(t, t0) controls deviations of the random quantities from their respective means.The proof then applies bounds from equation (59), Lemma 5, and the definition of εn at specified parameter choices.