A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networks

Mike Nguyen; Nicole Mücke

stat.MLSep 17, 2026

A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networks

Authors: Mike Nguyen, Nicole Mücke

Organizations: Technical University of Braunschweig

Abstract

We study data-driven early stopping for spectral regularisation methods in the classical non-parametric regression setting. Building on the discrepancy principle, we propose a multi-scale stopping rule that applies to general kernel estimators and show that, unlike previous approaches, it achieves full adaptivity over all smoothness levels in the well-specified case. A key contribution of our work is an extension based on random feature approximations, which reduces computational cost on large datasets while preserving minimax-optimal statistical guarantees. Our procedure not only selects an optimal stopping time but also provides a fully data-driven choice of the number of random features needed to achieve optimal rates. Through the established connection between random features and neural networks in the neural tangent kernel regime, our method further yields a principled, data-driven recommendation for the network width. We prove that the resulting simultaneously chosen width and stopping time allow neural networks to attain minimax-optimal learning rates without prior knowledge of smoothness or capacity parameters.

Figures & tables

Figure 1: Mean squared error of $f_{\tau(T)}$ (MSE, red) and stopping time $\tau(T)$ (blue) as functions of the smoothing parameter $T$ . Shaded areas indicate $\pm$ one standard deviation across trials.

	$\displaystyle\mathcal{M}$	$\displaystyle:=\{\lfloor n^{\frac{j}{\log n}}\rfloor\mid j=1,\dots,\log n\},\text{ constants }\tilde{c},c>0,$
	$\displaystyle\mathcal{T}_{t}$	$\displaystyle:=\{te^{p}:p=0,\dots,\lfloor\log(n/t)\rfloor\},$
	$\displaystyle L_{T}^{m}$	$\displaystyle:=\phi_{T}^{1/2}(K_{m})K_{m}^{1/2},$
	$\displaystyle V_{T,m}$	$\displaystyle:=\sigma^{2}\max\{\widehat{\mathcal{N}}_{m}^{\phi}(T),\log\log n\},$
	$\displaystyle\,\widehat{\mathcal{N}}^{\phi}_{m}(T)$	$\displaystyle:=\operatorname{tr}(\phi_{T}(K_{m})K_{m}).$

Algorithm 1 Adaptive early stopping with random features

	$\displaystyle\mathcal{M}:=$	$\displaystyle\{\lfloor n^{j/\log n}\rfloor\mid j=1,\dots,\log n\},\text{ constants }\tilde{c},c>0,$
	$\displaystyle\mathcal{T}_{t}:=$	$\displaystyle\{te^{p}:p=0,\dots,\lfloor\log(n/t)\rfloor\},$
	$\displaystyle L_{T}^{m}:=$	$\displaystyle\phi_{T}^{1/2}(K_{m})K_{m}^{1/2},$
	$\displaystyle V_{T,m}:=$	$\displaystyle\sigma^{2}\max\{\widehat{\mathcal{N}}_{m}^{\phi}(T),\log\log n\},$
	$\displaystyle\widehat{\mathcal{N}}^{\phi}_{m}(T):=$	$\displaystyle\operatorname{tr}(\phi_{T}(K_{m})K_{m}).$

Algorithm 2 Adaptive early stopping for NNs

	$\displaystyle\mathcal{M}$	$\displaystyle:=\{\lfloor n^{\frac{j}{\log n}}\rfloor\mid j=1,\dots,\log n\},\text{ constants }\tilde{c},c>0,$
	$\displaystyle\mathcal{T}_{t}$	$\displaystyle:=\{te^{p}:p=0,\dots,\lfloor\log(n/t)\rfloor\},$
	$\displaystyle L_{T}^{m}$	$\displaystyle:=\phi_{T}^{1/2}(K_{m})K_{m}^{1/2},$
	$\displaystyle V_{T,m}$	$\displaystyle:=\sigma^{2}\max\{\widehat{\mathcal{N}}_{m}^{\phi}(T),\log\log n\},$
	$\displaystyle\,\widehat{\mathcal{N}}^{\phi}_{m}(T)$	$\displaystyle:=\operatorname{tr}(\phi_{T}(K_{m})K_{m}).$

Table 7

Explore similar work

Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees
Aug 26, 2026Caixing Wang, Zhibo Chen, Yue WangRandom Feature Methods Kernel Ridge Regression
School of Statistics and Data Science, Southeast University · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China
A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm
Aug 25, 2026Duy Hoang, Bastien Berret, Olivier Bruneau +1Early Stopping Neural Network Generalization
Universit´e Paris-Saclay, CNRS, ENS Paris-Saclay, LMF Gif-sur-Yvette, 91190, France · Universit´e Paris-Saclay, Inria, CIAMS Gif-sur-Yvette, 91190, France · Universit´e Paris-Saclay, ENS Paris-Saclay, LURPA Gif-sur-Yvette, 91190, France
Random Features for Operator-Valued Kernels: Bridging Kernel Methods and Neural Operators
Mar 1, 2026Mike Nguyen, Nicole MückeRandom Feature Methods Kernel Methods
Technical University of Braunschweig

Aug 26, 2026J/K move · Enter open · S save

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

Caixing Wang, Zhibo Chen, Yue Wang

School of Statistics and Data Science, Southeast University · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China

Random Feature Methods Kernel Ridge Regression Statistical Learning Theory Early Stopping

Open paper AskPDF 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.

Abstract

Explore similar work

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

A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

Random Features for Operator-Valued Kernels: Bridging Kernel Methods and Neural Operators