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

Caixing Wang

stat.MLOct 13, 2026

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

Authors: Caixing Wang

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

Abstract

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.

Figures & tables

Figure 1: Illustration of the well-specified cases and misspecified case.

Figure 2: Exponent of $n$ in the random-feature budget $M$ in the benign RKHSs $\alpha_{0}=\gamma$ .

Figure 3: Minimum sample size required for the polynomial term to be dominated by the exponential term at a given confidence level $1-\delta$ , for different values of $p$ .

Figure 4: Learning rates under Gaussian (top row), standardized Student-

t_{4}

(middle row), and centered standardized Pareto

(5)

noise (bottom row). Columns correspond to

r\in\{0.1,0.2,0.4,0.75\}

. Each panel shows log errors against log sample sizes for full KRR and Compatible RF. The dashed line marks the theoretical slope

-2r/(2r+\gamma)

$r$	Theory	Gaussian	Student- $t_{4}$	Pareto $(5)$
$0.10$	$-0.4444$	$-0.4408$	$-0.4748$	$-0.4815$
$0.20$	$-0.6154$	$-0.5750$	$-0.6509$	$-0.6131$
$0.40$	$-0.7619$	$-0.7238$	$-0.7869$	$-0.7530$
$0.75$	$-0.8571$	$-0.8078$	$-0.8188$	$-0.9028$

Table 1: Learning-rate slopes for compatible RF, fitted by least squares to the

\log_{10}

mean errors at the final five sample sizes.

Figure 5: Effect of the number of random features

M

under Gaussian (top row), standardized Student-

t_{4}

(middle row), and centered standardized Pareto

(5)

noise (bottom row). Columns correspond to

r\in\{0.1,0.2,0.75\}

. Each panel shows errors against

M

for full KRR, uniform RF, and compatible RF.

Figure 6: Comparison of KRR-RF with robust kernel methods under Gaussian (left column), standardized Student-

t_{4}

(middle column), and centered standardized Pareto

(5)

noise (right column). The top row shows log errors against the noise level

\sigma

, while the bottom row shows training times.

Figure 7: Histogram of the target variable

usr

before (left) and after (right) transformation.

Variables	Name	Description
$x_{1}$	Iread	Reads (transfers per second) between system memory and user memory.
$x_{2}$	lwrite	Writes (transfers per second) between system memory and user memory.
$x_{3}$	scall	Number of system calls of all types per second.
$x_{4}$	sread	Number of system read calls per second.
$x_{5}$	swrite	Number of system write calls per second.
$x_{6}$	fork	Number of system fork calls per second.

Table 2: Details of variables in the cpusmall dataset.

Figure 8: Sensitivity of KRR and KRR-RF to the regularization parameter

\lambda

and the number of random features

M

Figure 9: Predictive performance and time comparison of KRR, KRR-RF, and other robust methods on the CPU dataset.

Figure 10: Normal Q-Q plot, Hill’s tail-index estimator, and tail exceedance probabilities of the standardized out-of-fold residuals for the cpusmall dataset.

Explore similar work

Aug 26, 2026

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

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.

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

Ask PDF

May 25, 2026

Conditional KRR: Injecting Unpenalized Features into Kernel Methods with Applications to Kernel Thresholding

Conditionally positive definite (CPD) kernels are defined with respect to a function class

\mathcal{F}

. It is well known that such a kernel

K

is associated with its native space (defined analogously to an RKHS), which in turn gives rise to a learning method -- called conditional kernel ridge regression (conditional KRR) due to its analogy with KRR -- where the estimated regression function is penalized by the square of its native space norm. This method is of interest because it can be viewed as classical linear regression, with features specified by

\mathcal{F}

, followed by the application of standard KRR to the residual (unexplained) component of the target variable. Methods of this type have recently attracted increasing attention. We study the statistical properties of this method by reducing its behavior to that of KRR with another fixed kernel, called the residual kernel. Our main theoretical result shows that such a reduction is indeed possible, at the cost of an additional term in the expected test risk, bounded by

\mathcal{O}(1/\sqrt{N})

, where

N

is the sample size and the hidden constant depends on the class

\mathcal{F}

and the input distribution. This reduction enables us to analyze conditional KRR in the case where

K

is positive definite and

\mathcal{F}

is given by the first

k

principal eigenfunctions in the Mercer decomposition of

K

. We also consider the setting where

\mathcal{F}

consists of

k

random features from a random feature representation of

K

. It turns out that these two settings are closely related. Both our theoretical analysis and experiments confirm that conditional KRR outperforms standard KRR in these cases whenever the

\mathcal{F}

-component of the regression function is more pronounced than the residual part.

Rustem Takhanov, Zhenisbek Assylbekov

Department of Mathematics, Nazarbayev University, Astana, Kazakhstan · Nazarbayev University Research Administration, Astana, Kazakhstan · Purdue University Fort Wayne, Indiana, USA.

Kernel Ridge Regression Kernel Regression Random Feature Methods Kernel Methods Statistical Learning Theory Ridge Regression

Ask PDF

Apr 14, 2026

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

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.

Taeyoung Kim

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

Random Feature Methods Kernel Ridge Regression Neural Network Generalization

Ask PDF