# Early stopping for kernel boosting algorithms: A general analysis with localized complexities

arXiv: https://arxiv.org/abs/1707.01543 · HTML: https://mlsanity.com/paper/1707.01543/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2017.

## Built on by (most cited first, 27 of 27)

- [Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalization](https://mlsanity.com/paper/2401.15604/) (2024)
- [Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension](https://mlsanity.com/paper/2305.14077/) (2023)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [Off-Policy Evaluation for Episodic Partially Observable Markov Decision Processes under Non-Parametric Models](https://mlsanity.com/paper/2209.10064/) (2022)
- [Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent](https://mlsanity.com/paper/2205.07331/) (2022)
- [Strong inductive biases provably prevent harmless interpolation](https://mlsanity.com/paper/2301.07605/) (2023)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime](https://mlsanity.com/paper/2203.03159/) (2022)
- [Random Smoothing Regularization in Kernel Gradient Descent Learning](https://mlsanity.com/paper/2305.03531/) (2023)
- [From inexact optimization to learning via gradient concentration](https://mlsanity.com/paper/2106.05397/) (2021)
- [Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent](https://mlsanity.com/paper/2402.16793/) (2024)
- [Reliable and scalable variable importance estimation via warm-start and early stopping](https://mlsanity.com/paper/2412.01120/) (2024)
- [Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis](https://mlsanity.com/paper/2512.24999/) (2025)
- [Iterative regularization for low complexity regularizers](https://mlsanity.com/paper/2202.00420/) (2022)
- [A Theoretical Framework for LLM Fine-tuning Using Early Stopping for Non-random Initialization](https://mlsanity.com/paper/2602.13942/) (2026)
- [Beyond Cross-Validation: Adaptive Parameter Selection for Kernel-Based Gradient Descents](https://mlsanity.com/paper/2603.03401/) (2026)
- [Residual-as-Teacher: Mitigating Bias Propagation in Student--Teacher Estimation](https://mlsanity.com/paper/2603.25466/) (2026)
- [Early stopping by correlating online indicators in neural networks](https://mlsanity.com/paper/2402.02513/) (2024)
- [Absolute convergence and error thresholds in non-active adaptive sampling](https://mlsanity.com/paper/2402.02522/) (2024)
- [Uniform convergence of the smooth calibration error and its relationship with functional gradient](https://mlsanity.com/paper/2505.19396/) (2025)
- [A Ridge Too Far: Correcting Over-Shrinkage via Negative Regularization](https://mlsanity.com/paper/2508.17412/) (2025)
- [GRADSTOP: Early Stopping of Gradient Descent via Posterior Sampling](https://mlsanity.com/paper/2508.19028/) (2025)
- [Don't stop me now: How Validation Criteria Affect Checkpoint Selection and Early Stopping](https://mlsanity.com/paper/2602.22107/) (2026)
- [ScoreStop: Gradient-based early stopping using functional score tests](https://mlsanity.com/paper/2606.02740/) (2026)
- [The Geometry of Saturation: Effective Rank Predicts When Labels Stop Helping in Few-Shot Classification](https://mlsanity.com/paper/2606.24903/) (2026)
- [Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees](https://mlsanity.com/paper/2608.25513/) (2026)
- [A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networks](https://mlsanity.com/paper/2609.21017/) (2026)

## Abstract (arXiv)

Early stopping of iterative algorithms is a widely-used form of regularization in statistics, commonly used in conjunction with boosting and related gradient-type algorithms. Although consistency results have been established in some settings, such estimators are less well-understood than their analogues based on penalized regularization. In this paper, for a relatively broad class of loss functions and boosting algorithms (including L2-boost, LogitBoost and AdaBoost, among others), we exhibit a direct connection between the performance of a stopped iterate and the localized Gaussian complexity of the associated function class. This connection allows us to show that local fixed point analysis of Gaussian or Rademacher complexities, now standard in the analysis of penalized estimators, can be used to derive optimal stopping rules. We derive such stopping rules in detail for various kernel classes, and illustrate the correspondence of our theory with practice for Sobolev kernel classes.