Regularized Least Squares Learning with Heavy-Tailed Noise Is Minimax Optimal
Abstract
This paper examines the performance of ridge regression in reproducing kernel Hilbert spaces in the presence of noise that exhibits a finite number of higher moments. We establish excess risk bounds consisting of subgaussian and polynomial terms based on the well known integral operator framework. The dominant subgaussian component allows to achieve convergence rates that have previously only been derived under subexponential noise—a prevalent assumption in related work from the last two decades. These rates are optimal under standard eigenvalue decay conditions, demonstrating the asymptotic robustness of regularized least squares against heavy- tailed noise. Our derivations are based on a Fuk–Nagaev inequality for Hilbert-space valued random variables.
Cite
Text
Mollenhauer et al. "Regularized Least Squares Learning with Heavy-Tailed Noise Is Minimax Optimal." Advances in Neural Information Processing Systems, 2025.Markdown
[Mollenhauer et al. "Regularized Least Squares Learning with Heavy-Tailed Noise Is Minimax Optimal." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/mollenhauer2025neurips-regularized/)BibTeX
@inproceedings{mollenhauer2025neurips-regularized,
title = {{Regularized Least Squares Learning with Heavy-Tailed Noise Is Minimax Optimal}},
author = {Mollenhauer, Mattes and Mücke, Nicole and Meunier, Dimitri and Gretton, Arthur},
booktitle = {Advances in Neural Information Processing Systems},
year = {2025},
url = {https://mlanthology.org/neurips/2025/mollenhauer2025neurips-regularized/}
}