# Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 57 references that are in the map.
- First posted on arXiv 26 Aug 2026.

## Builds on (most cited first, 20 of 20)

- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Distributed learning with regularized least squares](https://mlsanity.com/paper/1608.03339/) (2016)
- [Early stopping for kernel boosting algorithms: A general analysis with localized complexities](https://mlsanity.com/paper/1707.01543/) (2017)
- [Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms](https://mlsanity.com/paper/1801.07226/) (2018)
- [Analyzing the discrepancy principle for kernelized spectral filter learning algorithms](https://mlsanity.com/paper/2004.08436/) (2020)
- [Distributed Kernel Ridge Regression with Communications](https://mlsanity.com/paper/2003.12210/) (2020)
- [Optimal Rates for Multi-pass Stochastic Gradient Methods](https://mlsanity.com/paper/1605.08882/) (2016)
- [Optimal Kernel Quantile Learning with Random Features](https://mlsanity.com/paper/2408.13591/) (2024)
- [Adaptive Parameter Selection for Kernel Ridge Regression](https://mlsanity.com/paper/2312.05885/) (2023)
- [Adaptive Distributed Kernel Ridge Regression: A Feasible Distributed Learning Scheme for Data Silos](https://mlsanity.com/paper/2309.04236/) (2023)
- [Lepskii Principle for Distributed Kernel Ridge Regression](https://mlsanity.com/paper/2409.05070/) (2024)
- [On the Generalization Properties of Learning the Random Feature Models with Learnable Activation Functions](https://mlsanity.com/paper/2510.15327/) (2025)
- [Beyond Cross-Validation: Adaptive Parameter Selection for Kernel-Based Gradient Descents](https://mlsanity.com/paper/2603.03401/) (2026)

## Abstract (arXiv)

Random feature methods provide a scalable approximation to kernel ridge regression (KRR), but the regularization parameter that yields the oracle learning rate depends on unknown smoothness and capacity parameters. In this work, we propose a neighboring early-stopping rule for adaptive regularization in KRR with random features (KRR-RF). The method uses a grid that is uniform in inverse regularization and compares only adjacent estimators, reducing the number of discrepancy comparisons relative to standard all-pairs Lepskii-type procedures. Both the neighboring discrepancy and its empirical complexity term can be computed directly in the random feature space, without constructing the exact kernel Gram matrix. We establish a high-probability comparison bound for neighboring KRR-RF estimators and show that, under standard source and capacity conditions together with suitable grid and random feature budget conditions, the selected estimator attains the oracle polynomial learning rate up to logarithmic factors. The result allows the regularization parameter to be selected without prior knowledge of the source and capacity exponents and covers both well-specified and partially misspecified regimes. Our analysis is based on an empirical random feature effective dimension that connects the observable stopping threshold with the population complexity of the random feature model. Simulation and real-data experiments illustrate the prediction performance and computational behavior of the proposed method in comparison with standard tuning procedures.