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

Taeyoung Kim

cs.LGApr 14, 2026

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

Authors: Taeyoung Kim

Organizations: Center for AI and Natural Sciences, Korea Institute for Advanced Study, Seoul 02455, South Korea

Abstract

We study fixed-design random feature ridge regression beyond the mean-kernel approximation. The expectation is taken over the frozen-feature ensemble, conditional on the training sample. Because the predictor is a nonlinear function of the empirical kernel, its mean training error, test error, and conditional generalization gap depend on centered kernel covariances as well as on mean kernel objects. We derive the covariance-level, or one-loop, corrections from a finite resolvent identity. This avoids an almost-sure Neumann-series assumption and yields an explicit remainder bound for the training error. The test correction additionally requires mixed train--test covariance tensors and therefore cannot, in general, be recovered from the train-restricted kernel law alone. Numerical experiments show that the covariance term removes the leading inverse-width discrepancy in a controlled regularization regime, while an ablation that discards the mixed train--test covariance fails for the test error even though the training correction is unchanged. They also identify a width--regularization boundary, measured by a resolvent-fluctuation diagnostic, beyond which the second-order truncation loses accuracy. All inverse-width statements are for fixed sample size, depth, design, and positive kernel-level regularization. The analysis concerns frozen features and does not model feature learning or neural-tangent-kernel evolution.

Figures & tables

Figure 1: Width and depth dependence of the covariance corrections for the

\sin(2x)

target with

\tanh

features at the controlled value

\gamma=0.1

. Bands are pointwise paired-bootstrap intervals. The near-

-1

width slopes are interpreted together with the direct vertex measurement in Figure 2 .

Figure 2: Bias ablation and direct vertex diagnostics at

\gamma=0.1

. Left:

n\mathbb{E}[\|\Delta_{K}\|_{F}^{2}]

is approximately width-independent. Middle: bounds on the contraction-map norm as depth varies. Right: the training correction reflects both resolvent and vertex effects, so depth dependence cannot be assigned to either factor alone.

Figure 3: Representative width sweep for

y(x)=\sin(2x)

L=2

\tanh

, and

\gamma=0.1

. Top: empirical ensemble means, mean-object predictions, and mean-plus-covariance predictions. Bottom: the residuals

R_{0}

and

R_{1}

from ( 169 ). The gap panels display the magnitude of the signed ensemble-mean gap.

Figure 4: Residual scaling for

\gamma=0.05,0.1,0.2

. The mean-object residual

R_{0}

follows

n^{-1}

. The post-correction residual

R_{1}

is much smaller and approaches the Monte Carlo floor; the printed bootstrap intervals do not support distinguishing

n^{-3/2}

from

n^{-2}

uniformly across observables.

Figure 5: Mixed-covariance ablation for test error at

\gamma=0.2

. Columns correspond to three test populations with an identical training design. Retaining only train–train covariance leaves a residual

2.6

–

4.1

times the mean-object baseline residual; including the mixed train–test tensors removes that discrepancy.

Figure 6: Validity map for $y(x)=\sin(2x)$ , $L=2$ , and $\tanh$ features. The upper row reports the mean, exceedance probability, and $90$ th percentile of $q_{\Theta}$ ; the lower row reports the relative post-correction errors. The solid and dashed white contours mark $\mathbb{E}[q_{\Theta}]=1$ and $\mathbb{E}[q_{\Theta}]=0.3$ ; hatching marks the region above $\mathbb{E}[q_{\Theta}]=1$ .

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Median point-estimate ratios

R_{0}/R_{1}

across the target and architecture settings. These bars are descriptive; the main text reports ratios formed from the absolute confidence bounds.

Figure 8: Left: fitted exponents for

R_{0}

and

R_{1}

, with bootstrap intervals. Right: paired and split estimates of the post-correction training residual at

\gamma=0.05

, together with the Monte Carlo floor.

Figure 9: Mixed-covariance ablation for the absolute conditional generalization gap at

\gamma=0.2

Figure 10: Relative post-correction error versus $q_{\Theta}=\|(G+\gamma I)^{-1}\Delta_{K}\|_{2}$ across widths, regularization values, targets, and activations.

Figure 11: Diagnostics for the ReLU–

\lvert x\rvert

stress test: cancellation, bootstrap uncertainty, and the joint effect of regularization on

q_{\Theta}

and truncation error.

Figure 12: Term-by-term decomposition of the ReLU–

\lvert x\rvert

test covariance correction over the regularization ladder. Bands are paired-bootstrap intervals.

Figure 13: Fitted exponents in the descriptive model

\log|\mathcal{E}|=c+a\log N+b\log n

\gamma=10^{-2}

and

0.2

Figure 14: Training mean-object and covariance terms across $N$ and $n$ at $\gamma=10^{-2}$ , with effective-dimension diagnostics.

Figure 15: Training mean-object and covariance terms across $N$ and $n$ at $\gamma=0.2$ , with effective-dimension diagnostics.

Figure 16: Ensemble distributions of training error, test error, and the absolute conditional gap for three widths at

\gamma=0.1

. Vertical lines mark the empirical mean, mean-object prediction, and mean-plus-covariance prediction.

Figure 17: Mode-resolved mean-object and covariance contributions to the training error in the eigenbasis of

G

. The dashed line marks

\rho=\gamma

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
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
Characterizing the Generalization Error of Random Feature Regression with Arbitrary Data-Augmentation
May 11, 2026Lucas Morisset, Alain Durmus, Adrien HardyNeural Network Generalization Data Augmentation
Qube Research & Technologies · École Polytechnique

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.

Abstract

Explore similar work

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

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

Characterizing the Generalization Error of Random Feature Regression with Arbitrary Data-Augmentation