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

Caixing Wang; Zhibo Chen; Yue Wang

stat.MLAug 26, 2026

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

Authors: Caixing Wang, Zhibo Chen, Yue Wang

Organizations: 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

Abstract

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.

Figures & tables

Figure 1: Left: The results for KRR-RF over 16 candidate values of

\lambda

. The blue curve is the test RMSE on an independent test set after training on the full sample and its minimizer is the oracle choice. The red dashed curve is the 5-fold cross-validation score, obtained by refitting the model on training folds and evaluating it on validation folds. Cross-validation selects a smaller

\lambda

and incurs a larger test error than the oracle choice. Right: averaged over 12 trials, the oracle path benchmark requires 16 solves, while 5-fold cross-validation requires 80 solves. Despite this 5× higher cost, cross-validation still gives a worse average test RMSE (0.694 ± 0.013 vs. 0.677 ± 0.005).

K_{\max}=\left\lfloor\frac{|D|}{4\kappa^{2}h}\right\rfloor,\qquad\delta_{D}=\frac{\delta}{5K_{\max}},\qquad\lambda_{k}=\frac{1}{hk}.

Algorithm 1 Neighboring Early-Stopping Rule for KRR-RF (NESR-KRR-RF)

Method	Main computational cost	Memory cost
LP	$\mathcal{O}(K\|D\|^{3}+K^{2}\|D\|^{2})$	$\mathcal{O}(\|D\|^{2})$
ASUS	$\mathcal{O}(K\|D\|^{3}+K\|D\|^{2})$	$\mathcal{O}(\|D\|^{2})$
LP-RF	$\mathcal{O}(\|D\|M^{2}+KM^{3}+K^{2}M^{2})$	$\mathcal{O}(\|D\|M+M^{2})$
NESR-KRR-RF	$\mathcal{O}(\|D\|M^{2}+KM^{3}+KM^{2})$	$\mathcal{O}(\|D\|M+M^{2})$

Table 1: Computational complexity of different adaptive regularization methods.

	$q$	$\delta$	$C_{LP}$	$C_{ES}$	$h$	$K_{ES}$	$M$	$\|D\|$	$\|D^{\prime}\|$
Fig. 2 :(a)	0.5	0.01	0.1	0.005	50	20	100	5000	1000
Fig. 2 :(b)	0.5	0.01	0.05	0.003	50	20	100	5000	1000
Fig. 2 :(c)	0.5	0.01	0.0007	0.01	50	20	100	5000	1000
Fig. 2 :(d)	0.5	0.01	0.002	0.002	200	100	100	5000	1000
Fig. 3 :(a)	0.5	0.01	0.1	0.005	50	20	100	-	1000
Fig. 3 :(b)	0.5	0.01	0.05	0.003	50	20	100	-	1000

Table 2: Parameter settings for NESR and LP.

Panel of Figure 2 — Figure 2: Curve fitting performance with different $r$ and $\gamma$ . In each panel, the solid black line represents the true function $f(x)$ , and the blue scatter points show the noisy observations $f(x)+\varepsilon$ . Among the four compared estimators, the purple dotted line indicates the Oracle benchmark, and the orange two-dash line corresponds to Cross-Validation (CV). Additionally, the red dot-dash line denotes Lepskii Principle (LP), while the green dashed line illustrates our proposed NESR.

Panel of Figure 3 — Figure 3: RMSE vs number of training data $|D|$ for four approaches with different $r$ and $\gamma$ .

Panel of Figure 4 — Figure 4: Run time vs number of training data $|D|$ for NESR and LP with different $r$ and $\gamma$ .

Panel of Figure 5 — Figure 5: RMSE vs number of random features $M$ for four approaches with different $r$ and $\gamma$ .

Panel of Figure 6 — Figure 6: Run time vs number of random features $M$ for NESR and LP with different $r$ and $\gamma$ .

Panel of Figure 7 — Figure 7: RMSE vs subdivision factor $h$ for NESR with different $r$ and $\gamma$ .

Panel of Figure 8 — Figure 8: log MSE vs log number of training data $|D|$ for NESR with different $r$ and $\gamma$ .

	datasets	$d$	$\|D^{\prime}\|$	$\|D\|$	$\tau$	$M$	$C_{ES}$	$C_{LP}$
Fig. 9 :(a)	KIN8NM	8	1192	-	2	1000	0.0250	0.0001
Fig. 9 :(b)	SPCD	81	3263	-	8	1000	0.0400	0.0003
Fig. 9 :(c)	PPOPTS	9	5730	-	1	1000	0.0800	0.0010
Fig. 9 :(d)	SUSY	18	2000	-	$2^{2.5}$	1000	0.0750	0.0001
Fig. 9 :(e)	HTRU2	8	3808	-	2	1000	0.0200	0.0010
Fig. 9 :(f)	MGT	10	3020	-	$2^{1.5}$	1000	0.0500	0.0030

Table 3: Parameter settings and dataset characteristics.

Panel of Figure 9 — Figure 9: Prediction accuracy and runtime vs the training sample size $|D|$ on real datasets. Top panel: Regression tasks, where the line plots represent the MSE and the bar plots represent the average runtime over 10 independent trials. Bottom panel: Classification tasks, where the line plots represent the classification error rate and the bar plots represent the average runtime over 10 independent trials.

Panel of Figure 10 — Figure 10: Prediction accuracy and runtime vs the number of random features $M$ on real datasets. Top panel: Regression tasks, where the line plots represent the MSE and the bar plots represent the average runtime over 10 independent trials. Bottom panel: Classification tasks, where the line plots represent the classification error rate and the bar plots represent the average runtime over 10 independent trials.

Explore similar work

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning
Oct 13, 2026Caixing WangRandom Feature Methods Kernel Ridge Regression
School of Statistics and Data Science, Southeast University, Nanjing, China
A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networks
Sep 17, 2026Mike Nguyen, Nicole MückeEarly Stopping Nonparametric Regression
Technical University of Braunschweig
Loop Corrections in Random Feature Models: Training Error and Generalization Gap
Apr 14, 2026Taeyoung KimRandom Feature Methods Kernel Ridge Regression
Center for AI and Natural Sciences, Korea Institute for Advanced Study, Seoul 02455, South Korea

Oct 13, 2026J/K move · Enter open · S save

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning

Caixing Wang

School of Statistics and Data Science, Southeast University, Nanjing, China

Random Feature Methods Kernel Ridge Regression Statistical Learning Theory Model Misspecification

Open paper AskPDF arXiv

Random features provide a standard approach to scaling kernel methods to large datasets by approximating the kernel with a finite-dimensional feature map. Existing works of random feature methods primarily focus on well-specified models and light-tailed noise conditions, leaving a gap in understanding their performance under more general conditions, such as misspecified models and heavy-tailed noise. In this paper, we provide a comprehensive and improved analysis of kernel ridge regression with random features (KRR-RF) under general conditions. In the light-tailed noise setting, we improve upon the worst-case uniform bounds of the feature map used in the previous works and lead to the minimax optimal learning rates with

2r+γ>α_0

, where

(r,γ,α_0)

denote the regularity of the target function, the effective dimension of the kernel, and the embedding index of the RKHS, respectively. In the heavy-tailed noise setting, we leverage a recently developed Hilbert-valued Fuk-Nagaev inequality and extend the same optimal results under finite weak moment conditions. The additional cost to achieve robustness is a mildly stronger explicit sample-size requirement than in the light-tailed case. For both settings, our results recover the conditions random features budgets (up to log factors) required in the previous works. In the most benign case when

α_0=γ

, KRR-RF are minimax optimal for all

r \in (0,1]

. To the best of our knowledge, this is the first work to establish optimal learning rates for KRR-RF under weak moment conditions in the misspecified setting. Numerical experiments and a real data analysis validate the derived learning rates and demonstrate their practical relevance in the presence of mis-specification and heavy-tailed noise.

Method	Main computational cost	Memory cost
LP	$\mathcal{O}(K\|D\|^{3}+K^{2}\|D\|^{2})$	$\mathcal{O}(\|D\|^{2})$
ASUS	$\mathcal{O}(K\|D\|^{3}+K\|D\|^{2})$	$\mathcal{O}(\|D\|^{2})$
LP-RF	$\mathcal{O}(\|D\|M^{2}+KM^{3}+K^{2}M^{2})$	$\mathcal{O}(\|D\|M+M^{2})$
NESR-KRR-RF	$\mathcal{O}(\|D\|M^{2}+KM^{3}+KM^{2})$	$\mathcal{O}(\|D\|M+M^{2})$

Abstract

Explore similar work

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning

A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networks

Loop Corrections in Random Feature Models: Training Error and Generalization Gap