On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning
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 ∈ (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.
Related
- A Method for Exact Enforcement of Boundary Conditions on General Curved Triangular Domains: Algorithm and Application to Scientific Machine Learning
- Optimality Conditions and Solution Set Characterisations of Convex Minimal Time Optimisation Problems
- On quantitative sufficient second-order optimality conditions for elliptic optimal control problems
- Necessary Optimality Conditions for Bilevel Programming using Tangential Subdifferentials
- Unified Optimality Conditions for Stochastic Optimal Control in the Rough Path and Itô Frameworks
BibTeX
@misc{wang2026optimality,
title = {{On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning}},
author = {Caixing Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18333},
eprint = {2610.18333},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18333},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning
AU - Caixing Wang
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18333
UR - https://arxiv.org/abs/2610.18333
AB - 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 ∈ (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.
ER -