Asymptotic Analysis of Empirical Risk Minimization on Entry-wise i.i.d. Heavy-Tailed Data

Kaito Takanami; Takashi Takahashi; Yoshiyuki Kabashima

cond-mat.dis-nnOct 6, 2026

Asymptotic Analysis of Empirical Risk Minimization on Entry-wise i.i.d. Heavy-Tailed Data

Authors: Kaito Takanami, Takashi Takahashi, Yoshiyuki Kabashima

Organizations: Graduate School of Science, The University of Tokyo · Institute for Physics of Intelligence, The University of Tokyo · Trans-Scale Quantum Science Institute, The University of Tokyo

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.

Figures & tables

Figure 1: Empirical validation of the theoretical coefficient-error predictions. (A, B) Solid colored lines show the theoretical predictions of

q_{\alpha}

(Equation 15 ), while markers represent numerical results obtained via finite-dimensional ERM. The solid black line shows the theoretical prediction of

q_{\alpha}

under the Bayes–optimal setting in Section 5.3 . (C) Comparison between the theoretical distribution (Equation 14 ) and the empirical coefficient-error distribution obtained by finite-dimensional ERM. The dashed black curve shows the theoretical coefficient-error distribution at

\alpha=2

, which is Gaussian. (A-C) Huber loss with

\delta=1

p_{w}=\mathcal{N}(0,1)

, and

p_{\epsilon}=\mathcal{N}(0,0.5^{2})

; (A,B)

D=256

; (C)

D=4096

\lambda=1

, and the empirical distribution is averaged over 8 independent trials. (A,B) Error bars indicate the standard error over 8 independent trials for each point.

Figure 2: Empirical validation of universality across heavy-tailed feature distributions. The solid line shows the theoretical prediction of

q_{\alpha}

for

S\alpha S(1)

features, while markers represent numerical results obtained via Huber–ridge ERM with symmetric

\alpha

-stable, Pareto, and Student-

t

coordinates. The Pareto and Student-

t

distributions are rescaled to satisfy

\Pr(|X|>x)\sim C_{\alpha}^{\mathrm{S}}x^{-\alpha}

. Parameters: (A, B)

D=256

\delta=1

\lambda=1

p_{w}=\mathcal{N}(0,1)

, and

p_{\epsilon}=\mathcal{N}(0,0.5^{2})

. Error bars indicate the standard error over 6 independent trials for each point.

Figure 3: Empirical validation of prediction-error scaling and reliability. (A) The solid colored and black lines show the theoretical predictions for

\operatorname{median}(|\Delta^{(\alpha)}(\kappa)|)

and

\operatorname{median}(|\Delta^{(2)}(\kappa)|)

under heavy-tailed and Gaussian features, respectively, while markers represent the finite-dimensional ERM results. (B) The solid colored and black lines show the theoretical predictions for

\Pr(|\Delta^{(\alpha)}(\kappa)|>t)

and

\Pr(|\Delta^{(2)}(\kappa)|>t)

under heavy-tailed and Gaussian features, respectively, while markers represent the finite-dimensional ERM results. Parameters: (A, B) Huber loss with

\delta=1

\lambda=1

p_{w}=\mathcal{N}(0,1)

p_{\epsilon}=\mathcal{N}(0,0.5^{2})

, and

D=128

. Error bars indicate the standard error over 8 independent trials for each point.

Explore similar work

Universality of empirical risk minimization
Feb 17, 2022Andrea Montanari, Basil SaeedEmpirical Risk Minimization Neural Tangent Kernel
Department of Statistics and Department of Mathematics, Stanford University · Department of Electrical Engineering, Stanford University
Weighted Empirical Risk Minimization for Machine Learning under Long-Range Dependence: Exact Pathwise Rates and Learning-Error Geometry
Sep 9, 2026Elina MoldavskayaEmpirical Risk Minimization Weight Decay
Technion–Israel Institute of Technology, Israel
Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments
Jun 5, 2026Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1Generalization Bounds Lipschitz Continuity
Department of Statistics, The University of Chicago, Chicago, IL 60637, USA. · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, IN 46556, USA.

Feb 17, 2022, math.STJ/K move · Enter open · S save

Universality of empirical risk minimization

Andrea Montanari, Basil Saeed

Department of Statistics and Department of Mathematics, Stanford University · Department of Electrical Engineering, Stanford University

Empirical Risk Minimization Neural Tangent Kernel Loss Function Risk

Open paper AskPDF arXiv

We study a general class of optimization problems with decision variable

\boldsymbolΘ \in \mathbb{R}^{p \times k}

and cost function which is the sum of

n

terms, each dependent on

\boldsymbolΘ

through the

k

-dimensional projection

\boldsymbolΘ^\top \boldsymbol{x}_i

, where

\boldsymbol{x}_i

i \leq n

are i.i.d. random vectors. This setting is general enough to include examples of current interest in statistical physics, high-dimensional statistics, and statistical learning theory. We consider the proportional asymptotics

n, p \to \infty

, with

n/p = Θ(1)

, and prove that, whenever there exists a minimizer satisfying a suitable generalization of a "delocalization" condition, the minimum value is universal. Namely, (for subgaussian

\boldsymbol{x}_i

) it depends on the distribution of

\boldsymbol{x}_i

only through its asymptotic mean and covariance. This delocalization condition is essentially necessary. Earlier universality results for such problems were limited to strongly convex loss functions. We derive applications of our theory to statistical learning and prove general universality results both for train and (under additional conditions) test error. In particular, we establish universality for vectors

\boldsymbol{x}_i

generated by random 1-layer neural networks (random features models) and first-order Taylor approximations of 2-layer networks (neural tangent models). Finally, we establish that the delocalization property holds for a class of statistical learning problems under a condition that is easy to verify.

Abstract

Explore similar work

Universality of empirical risk minimization

Weighted Empirical Risk Minimization for Machine Learning under Long-Range Dependence: Exact Pathwise Rates and Learning-Error Geometry

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite LpL_pLp​ Moments

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments