stat.MLApr 3, 2026

Characterization of Gaussian Universality Breakdown in High-Dimensional Empirical Risk Minimization

Authors: Chiheb Yaakoubi, Cosme Louart, Malik Tiomoko, Zhenyu Liao

Organizations: School of Data Science, The Chinese University of Hong Kong, Shenzhen, China · Huawei Noah’s Ark Lab, Huawei Technologies, Paris, France · School of Electronic Information and Communications, Huazhong University of Science & Technology, China

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study high-dimensional convex empirical risk minimization (ERM) under general non-Gaussian data designs. By heuristically extending the Convex Gaussian Min-Max Theorem (CGMT) to non-Gaussian settings, we derive an asymptotic min-max characterization of key statistics, enabling approximation of the mean μθ^μ_{\hatθ} and covariance Cθ^C_{\hatθ} of the ERM estimator θ^\hatθ. Specifically, under a concentration assumption on the data matrix and standard regularity conditions on the loss and regularizer, we show that for a test covariate xx independent of the training data, the projection θ^⊤x\hatθ^\top x approximately follows the convolution of the generally non-Gaussian distribution of μθ^⊤xμ_{\hatθ}^\top x with an independent centered Gaussian variable of variance tr(Cθ^E[xx⊤])\mathrm{tr}(C_{\hatθ} \mathbb{E}[xx^\top]). This result clarifies the scope and limits of Gaussian universality for ERMs. Numerical simulations across diverse losses and models are provided to validate our theoretical predictions and qualitative insights.

Figures & tables

Figure 1: Breakdown of performance and score universality through an elastic loss. Top: Empirical generalization error and theoretical prediction for the teacher–student model y=θ∗⊤x+εy=\theta^{*\top}x+\varepsilon as η∈[0,1]\eta\in[0,1] varies, with Ly(t)=(1−η)(t−y)2+η∣t−y∣\mathcal{L}_{y}(t)=(1-\eta)(t-y)^{2}+\eta|t-y| . The entries of xx are independent and bimodal, ρ(θ)=∥θ∥22\rho(\theta)=\|\theta\|_{2}^{2} , p=30p=30 , and n=50n=50 . Performance universality is tested against Gaussian surrogate data with matching mean and covariance. Bottom: Score histograms at η=0\eta=0 , together with the theoretical prediction and a moment-matched Gaussian fit. Performance universality holds at the squared-loss endpoint η=0\eta=0 although the score is non-Gaussian; for η>0\eta>0 , the moment-matched Gaussian surrogate no longer predicts the empirical performance.
  ( 20 )( 18 ) ( 4 )( 38 ) ( 39 )( 12 )( 32 ) ( 16 )( 11 )( 19 )( 8 ) ( 27 )( 25 ) ( 26 )( 30 ) ( 10 )( 17 )( 33 )( 1 )( 28 )( 2 ) ( 5 )( 29 )Our Method
AssumptionsStatistics of xx
μx≠0\mu_{x}\neq 0 (non-zero mean)     ✓ ✓✓✓ ✓✓✓✓ ✓
Cx≠σ2IpC_{x}\neq\sigma^{2}I_{p} (correlated features)     ✓ ✓✓✓ ✓ ✓✓✓✓
Multiple statistics       ✓✓✓ ✓ ✓✓ ✓
Law type, default: x∼N(μx,Cx)x\sim\mathcal{N}(\mu_{x},C_{x})
iid non-Gaussian entries✓   ✓✓✓  ✓✓    ✓✓
Table 1: Comparison of related works and our method. Color code: Light Red = RMT, Light Green = CGMT, Light Blue = AMP, Light Purple = Lindeberg-type arguments (and variants). Notation: ✓ indicates that the corresponding work covers the feature/setting; R denotes a proved statement; A denotes an assumption. Parenthesized (R) indicates that the statement holds only under a subset of the assumptions listed in that column. Note that R entries may rely on different baseline assumptions across columns and are therefore not always directly comparable. Papers are grouped within a single column when they share a closely related framework and essentially the same conclusions, although some modeling assumptions may differ.
Figure 2: Universality breakdown on MNIST data. Setting described in Appendix G Left: Empirical histograms of decision scores for Class 0 ( light blue ) and Class 1 ( light red ) of θ^⊤x\hat{\theta}^{\top}x , compared with a Gaussian approximation of matching mean and variance ( green dashed) and with the corrected theoretical density (dashed blue ). Right: Generalization performance. As expected, predictions based on Gaussian score universality ( green dashed) fail to match empirical results.
Figure 3: Evolution of the description variables through elastic loss. In the setting of Figure 1 , we show the fixed-point solution variables α∗\alpha_{*} , ν∗\nu_{*} and 11+κ∗\frac{1}{1+\kappa_{*}} . For the ℓ2\ell_{2} loss ( η=0\eta=0 ), we have ν∗=11+κ∗\nu_{*}=\frac{1}{1+\kappa_{*}} .

Explore similar work

CardsList

  1. Universality of empirical risk minimization

    Feb 17, 2022Andrea Montanari, Basil SaeedStatistical Learning TheoryEmpirical Risk Minimization

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

  2. Non-asymptotic estimates of the minimal risk in statistical learning

    Jun 22, 2026Liming Wu, Sen YangStatistical Learning TheoryEmpirical Risk Minimization

    Laboratoire de Mathématiques Blaise Pascal, CNRS-UMR 6620, Université Clermont Auvergne · IASM, Harbin Institute of Technology

  3. A Researcher's Guide to Empirical Risk Minimization

    Feb 25, 2026Lars van der LaanEmpirical Risk MinimizationStatistical Learning Theory

    Department of Statistics, University of Washington