Asymptotic Analysis of Empirical Risk Minimization on Entry-wise i.i.d. Heavy-Tailed Data
Abstract
Many real-world datasets exhibit unusually large values far more frequently than predicted by Gaussian models. Heavy-tailed distributions capture this behavior, yet evaluating learning performance under them remains challenging because rare, large feature entries retain non-vanishing effects even in high dimensions. Even in the canonical setting of empirical risk minimization for linear regression with entry-wise i.i.d. symmetric α-stable data, a precise asymptotic characterization of prediction has been lacking. In this work, we introduce a functional order parameter that describes the random effective problem associated with each coefficient. Using the replica method, we fully characterize the generalization error in the proportional high-dimensional limit where the sample size and feature dimension diverge at a fixed ratio. Additionally, this analysis establishes a heavy-tail universality law, scaling laws relating typical errors to prediction reliability, and the Bayes-optimal prediction error. In addition to characterizing the effects of extreme entries on the learning process, our method applies broadly to other systems with persistent local heterogeneity.
Related
- A Flexible Heavy-Tailed Probability Model for Skewed Positive Data: Theory, Estimation, and Empirical Assessment
- Limit theory for a class of non-stationary linear processes with weakly dependent heavy-tailed innovations
- Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
- DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes
- Weighted Empirical Risk Minimization for Machine Learning under Long-Range Dependence: Exact Pathwise Rates and Learning-Error Geometry
BibTeX
@misc{takanami2026asymptotic,
title = {{Asymptotic Analysis of Empirical Risk Minimization on Entry-wise i.i.d. Heavy-Tailed Data}},
author = {Kaito Takanami and Takashi Takahashi and Yoshiyuki Kabashima},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07637},
eprint = {2610.07637},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07637},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Asymptotic Analysis of Empirical Risk Minimization on Entry-wise i.i.d. Heavy-Tailed Data
AU - Kaito Takanami
AU - Takashi Takahashi
AU - Yoshiyuki Kabashima
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07637
UR - https://arxiv.org/abs/2610.07637
AB - Many real-world datasets exhibit unusually large values far more frequently than predicted by Gaussian models. Heavy-tailed distributions capture this behavior, yet evaluating learning performance under them remains challenging because rare, large feature entries retain non-vanishing effects even in high dimensions. Even in the canonical setting of empirical risk minimization for linear regression with entry-wise i.i.d. symmetric α-stable data, a precise asymptotic characterization of prediction has been lacking. In this work, we introduce a functional order parameter that describes the random effective problem associated with each coefficient. Using the replica method, we fully characterize the generalization error in the proportional high-dimensional limit where the sample size and feature dimension diverge at a fixed ratio. Additionally, this analysis establishes a heavy-tail universality law, scaling laws relating typical errors to prediction reliability, and the Bayes-optimal prediction error. In addition to characterizing the effects of extreme entries on the learning process, our method applies broadly to other systems with persistent local heterogeneity.
ER -