# Regularized least squares learning with heavy-tailed noise is minimax optimal

arXiv: https://arxiv.org/abs/2505.14214 · HTML: https://mlsanity.com/paper/2505.14214/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 73 references that are in the map.
- First posted on arXiv 20 May 2025.

## Builds on (most cited first, 23 of 23)

- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Kernel Instrumental Variable Regression](https://mlsanity.com/paper/1906.00232/) (2019)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Optimal Rates for Regularized Conditional Mean Embedding Learning](https://mlsanity.com/paper/2208.01711/) (2022)
- [Learning Theory for Distribution Regression](https://mlsanity.com/paper/1411.2066/) (2014)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Learning linear operators: Infinite-dimensional regression as a well-behaved non-compact inverse problem](https://mlsanity.com/paper/2211.08875/) (2022)
- [On the Optimality of Misspecified Spectral Algorithms](https://mlsanity.com/paper/2303.14942/) (2023)
- [Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm](https://mlsanity.com/paper/2312.07186/) (2023)
- [Beating SGD Saturation with Tail-Averaging and Minibatching](https://mlsanity.com/paper/1902.08668/) (2019)
- [On the Optimality of Misspecified Kernel Ridge Regression](https://mlsanity.com/paper/2305.07241/) (2023)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [On the Saturation Effect of Kernel Ridge Regression](https://mlsanity.com/paper/2405.09362/) (2024)
- [Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms](https://mlsanity.com/paper/2405.14778/) (2024)
- [Optimal rates for the regularized learning algorithms under general source condition](https://mlsanity.com/paper/1611.01900/) (2016)
- [Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimal](https://mlsanity.com/paper/2411.19653/) (2024)
- [On Least Squares Estimation under Heteroscedastic and Heavy-Tailed Errors](https://mlsanity.com/paper/1909.02088/) (2019)
- [On the Robustness of Kernel Ridge Regression Using the Cauchy Loss Function](https://mlsanity.com/paper/2503.20120/) (2025)

## Built on by (most cited first, 3 of 3)

- [Cubit: Token Mixer with Kernel Ridge Regression](https://mlsanity.com/paper/2605.06501/) (2026)
- [On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise](https://mlsanity.com/paper/2605.09757/) (2026)
- [A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networks](https://mlsanity.com/paper/2609.21017/) (2026)

## Abstract (arXiv)

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.