The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures
Authors: Xiaoyi MAI
Zhenyu Liao
Venue: ICLR 2025 Poster (2025)
Keywords: High-dimensional statistics
random matrix theory
Gaussian universality
empirical risk minimization
mixture models
linear factor models
Primary area: learning theory
TL;DR: Establish asymptotic performance of ERM classifiers under linear factor mixture model, and derive conditions for Gaussian universality.

Abstract: The assumption of Gaussian or Gaussian mixture data has been extensively exploited in a long series of precise performance analyses of machine learning (ML) methods, on large datasets having comparably numerous samples and features. 
To relax this restrictive assumption, subsequent efforts have been devoted to establish "Gaussian equivalent principles" by studying scenarios of Gaussian universality where the asymptotic performance of ML methods on non-Gaussian data remains unchanged when replaced with Gaussian data having the *same mean and covariance*.
Beyond the realm of Gaussian universality, there are few exact results on how the data distribution affects the learning performance. 

In this article, we provide a precise high-dimensional characterization of empirical risk minimization, for classification under a general mixture data setting of *linear factor models* that extends Gaussian mixtures. 
The Gaussian universality is shown to break down under this setting, in the sense that the asymptotic learning performance depends on the data distribution *beyond* the class means and covariances.
To clarify the limitations of Gaussian universality in the classification of mixture data and to understand the impact of its breakdown, we specify conditions for Gaussian universality and discuss their implications for the choice of loss function.

Published as a conference paper at ICLR 2025
THE BREAKDOWN OF GAUSSIAN UNIVERSALITY IN CLASSIFICATION OF HIGH-DIMENSIONAL LINEAR FAC- TOR MIXTURES
Xiaoyi Mai
Zhenyu Liao"
Institut de Mathématiques de Toulouse (IMT) University of Toulouse-Jean Jaurès Toulouse, France
EIC
Huazhong University of Science & Technology Wuhan, China
x xiaoyi. i ma @math. univ-toulouse. fr
chenyu_liao@huse .nd.cc
ABSTRACT
The assumption of Gaussian or Gaussian mixture data has been extensively ex- ploited in long series of precise performance analyses of machine learning (ML) methods, on large datasets having comparably numerous samples and features. To relax this restrictive assumption, subsequent efforts have been devoted establish "Gaussian equivalent principles" by studying scenarios of Gaussian universality where the asymptotic performance ML methods on non-Gaussian data remains unchanged when replaced with Gaussian data having the same mean and covari- ance. Beyond the realm of Gaussian universality, there are few exact results on how the data distribution affects the learning performance.
In this article, we provide a precise nigh-dimensional characterization of empirical risk minimization, for classification under general mixture data setting of linear factor models that extends Gaussian mixtures. The Gaussian universality is shown to break down under this setting, in the sense that the asymptotic learning perfor- mance depends on the data distribution beyond class means and covariances. To clarify the limitations of Gaussian universality in the classification of mixture data and to understand the impact of its breakdown, we specify conditions for Gaussian universality and discuss their implications for the choice of loss function.
INTRODUCTION
Modern machine learning (ML) is dealing with increasingly larger datasets having high- high-dimensional features, using large-scale models of increasing complexity. Understanding the generalization ability of these surge-scale ML models has become major focus of research efforts (Bartlett et al., 2020
Loog al. 2020 Nakkiran al., (02T). One analysis approach of growing popularity the high- dimensional asymptotic analysis (Liao & Couillet 2019 Taheri et al. 2021a Celentano & Montanari 2022, Hastie et al., 2022 Loureiro et al. 2022] Celentano et al. 2023), by considering regime where the number n of samples and the dimension of feature vectors are commensurately large. Despite its asymptotic nature, this approach turns out to be surprisingly effective in explaining and predicting modern ML practice: the asymptotic performance curves repetitively observed to closely match the average empirical performance curves on realistic datasets of moderate size and dimension (Couillet & Liao 2022), and partieularly different from those offered by, e.g., classical maximum likelihood theory (Bean et al. 20033 Sur & Candès 2019 Taheri et al.] 2021b).
To analytically characterize the generalization performance of large-scale ML models in the afore- mentioned high-dimensional regime, advanced statistical tools such as the approximate message pass- ing (Donoho & Montanari, 2016 Barbier et al. 2019), convex Gaussian min-max theorem (Thram- poulidis et al. [0188] [aalhii et al. | 2019 Deng et al. 2022; Javanmard & Soltanolkotabi 2022). replica method (Huang] 22017; Gerace al. 22200; Maillard al. 20200), and random matrix the- ory (RMT) (Couillet & Liao| 2022] Mai et al.) 2019 Mai & Couileet, (021)) have been carefully adapted to take into account of the nonlinearity of ML models. As these tools apply directly on
"Corresponding author: Zhenyu Liao.

---

Published as a conference paper at ICLR 2025
Gaussian data, majority of dighedimensional asymptotic analyses are performed under Gaussian data models in the context of regression (El Karoui et al., Donoho & Montanari 2016) Taheri
et al. 202 Celentamo & Montanari 2022) or Gaussian mixture models (GMMs) in the context of
classification (Mignacco et al., 2020; I'rampoulidii et al. 2020 Refinetti et al. 2021).
Despite this seemingly restrictive assumption of data Gaussianity, the derived high-dimensional asymptotic results have been empirically observed to remain valid on non-Gaussian data, including both synthetic non-Gaussian data and samples drawn from realistic (say image) datasets (Loureiro et al. [ Taheri et al., 20211). hinting at a phenomenon of Gaussian universality. This motivated series of recent works establishing, through, e.g., an one-directional central limit theorem (CLT) argument, a Gaussian equivalent principal (GEP) for nigh-dimensional ML models ranging from
generalized linear models to shallow neural networks (Gerace et al., 2020 Goldt et al., 2022 Hu
Lu 2022; Montanari & Saeed 20222 (Schröder et al. 2023; Han & Shen 2023). According to the
GEP, the performance of MI. methods on non-Gaussian data is asymptotically the same under an equivalent Gaussian model with matching first- and second-order moments. Assuming conditional one-directional CLT, Dandi et al. (2024) put forward a conditional Gaussian equivalent principle (CGEP) stating that the asymptotic classification error for non- non-Gaussian mixtures remains unchanged when replaced by Gaussian mixture model with identical class-cou conditional means and covariances. This contribution, however, did not specify the conditions required on the mixture data model for this conditional one-directional CLT to hold.
This work is driven by the need to investigate the applicability of CGEP under mixture models and to characterize the impact of non-Gaussian data variations when the CGEP does not apply. By considering more general mixture model (see Definition D where classes are described by linear factor models-a fundamental probabilistic framework in statistical inference and generative models (Goodfellow et al.] [2016] Chapter 13), our analysis extends long line of high- sigh-dimensional
asymptotic performance analyses in classification of Gaussian mixtures (Dobriban & Wager] 20188)
Huang 2017 [iao & Couillet 2019. Mai & Liao 2019 Huang & Yang 2021 Kammoun & Alouini
2021 Wang & &Thrampouiddis, 2021 Pesce et al. 2023 We discuss the validity of CGEP under this
linear factor mixture model and specify its conditions. On a technical level, we develop a flexible
"Ieave-one-out" analysis approach, in a similar spirit to the analysis of robust linear regression by
El Karoui et al.] 2013).. The elementary nature of this leave-one-out procedure allows us to extend the approach of high- high-dimensional asymptotic analysis beyond the realm of Gaussian universality.
Our Contributions.
The main findings of this paper are summarized below.
1. We provide Theorem an asymptotic characterization of fidgerrgullarized empirical risk minimization (ERM) for classification of data drawn from linear factor mixture model (LFMM, see Definition heloow, that generalizes the GMM). This precise characterization gives access to the asymptotic performance on mixture data beyond Gaussian universality,
2. Based on the proposed analysis, we study Gaussian universality in the sense of CGEP and provide conditions on LFMM under which the data distribution affects the asymptotic learning behavior only via its first two class-conditional moments.
We first discuss in Section 5. the Gaussian universality on in-distribution performance and conclude in Corollary 2 that the training and generalization performances of ERM under a given LFMM remain unchanged under its equivalent GMM (with identical class means and covariances, see Definition 2). if all informative factors of the LFMM that significantly correlated with the class label are class- conditiona normal variables.
We then investigate in Section 5.2 Gaussian universality of classifier (see Defini- given test set (of arbitrary distribution), the ERM classifier trained on data drawn from an LFMM gives the same asymptotic classification error as the one trained on its equivalent GMM, whenever the square loss is used and/or in the case of class-conditional Gaussian informative factors for LFMM.
tion 3 and conclude in Corollary 3 that
3. While it has been known that for -igh-dimensional GMM, the square loss is optimal in both unregularized (Taheri et al. 2021b) and ridge-regularized (Mai & Liao| 2019) classifications. it is no longer the case under the general LFMM due to the breakdown of Gaussian universality. We discuss in Section 5.2 how the suboptimality of square loss under LFMM relates to its effect on the Gaussian universality of the ERM classifier. Our analysis thus opens the door to future investigation the optimal loss design for non-Gaussian data.
2

---

Published as a conference paper at ICLR 2025
2 BACKGROUND ON GAUSSIAN UNIVERSALITY IN HIGH DIMENSIONS
The Gaussian universality phenomenon was observed in many high-dimensional inference or MI. problems, where some key statistics such as estimation error classification accuracy exhibit universal behaviors independent of the data distribution. This phenomenon was extensively exploited to relax the data Gaussianity assumption that underlined many results in high-dimensional statistics, through a universality argument often established with two key ingredients the law of large numbers (LLN) and the CLT.
Here we briefly review previous findings on Gaussian universality in the high-dimensional regime.
Universality of large sample covariance matrices. It has been long known in RMT that the eigenspectra of large random matrices enjoy universal properties for Gaussian and non-Gaussian entries TTo et al., 2010: Pastur & Shcherbina 20.1). Fundamentally, Marchenko & Pastur (9677) put forward that for sample covariance matrices of the type 1 -i= x E RPP obtained from n i. data vectors x; of dimension p, the universality on the limiting eigenvalue distribution hinges on the concentration of quadratic forms of x; around their expectations, that is
lim (x: Mx; E[x! (xx]))EExx Mx,] = 0,
for deterministic M E TRPXP. This LLN-ttpe result holds for a wide family of high-dimension
random vectors x;, An important example studied by Bai & Silverstein 2008 is x; = Σ with z; of i.i.d. standardized entries with bounded fourth moments and non-negative definite symmetric Σ.
Universality of empirical risk minimization. In line with the universal behavior of large sample covariance matrices, it has been recently demonstrated in a series of works (Gerace et al. 2020) Goldi jet al. 2022; Hu & Lu 2022, Montanari & Saeed [022]] Schröder et al. 2023) that random (and deterministic under certain conditions) feature maps can produce feature matrices that, when replaced by "equivalent" Gaussian features with the same first- and second-ordes moments, yield the same training and/or generalization performance for many ML methods. This GEP has also been proven for data vectors of independent entries in the context of regularized regression (Montanari & Nguyen 2017 Panahi & Hassibi 2017 Han & Shen 2023).
In the context of ERM, the GEP traced back to a CLT on the inner product x xT3 for feature vector x E IP independent of classifier 33 living in a subspace B C IP containing the ERM solution B, i... lim suPpEs (B[f [)] B(f(gT))
0,
with g ~ (IEx,, Cov(x)) being the "equivalent" Gaussian vector, for any bounded Lipschitz function f: R + R. The one-directional CLT in (2) requires the ERM solution 3 to not particularly
aligned with any non-Gaussian variation in the feature vector x, in order to ensure the asymptotic
normality of x B per CLT-type argument.
Universality of empirical risk minimization on mixture data. Inspired by the one-directional CLT condition 2 for GEP in ERM. Dandi et al. (2024) demonstrated the Gaussian universality for mixture models under a key assumption that is a conditional version of (2):
pi suP EE [[(x [x[(x)))>>> l = c] E ( 3) 0,
where y/ is the class label of x, C' a class modality, and gicr ~ N (L x| C), Cov[xly> C)). Under this conditional -ie-directional CLT in B Dandi et al. (2024) showed that the asymptotic training and generalization errors only depend on the classicon means and covariances of the mixture model, obeying thus a conditional Gaussian equivalent principle (CGEP).
However, the condition in (3) is not verifiable from the data distribution, making it essentially different from the ones given in Section 5
Other related works established equivalences between Gaussian data and Gaussian mixtures. For classification with random labels y/x ~ Unif({ (-1, generated independently of x, Gerace et al.] (2024) proved that the training loss on GMM is asymptotically equal to that on a single Gaussian. Pesce et al. (2023) considered a reacher-student model and showed that when the target label is generated by teacher model uncorrelated with cluster means, the same asymptotic performance can be obtained by replacing a homoscedastic (i.c., having identical covariance) Gaussian mixture with a single Gaussian.
3

---

Published as a conference paper at ICLR 2025
Universality under elliptical distributions. For "elliptic-like" data vectors of form aMu with a E IR a random scaling variable, M E Rexd a deterministic matrix and u E R a vector of standardized variables satisfying the concentration of quadratic forms in (I) (e.g., ~ (O Ia)), El Karoui (209) revealed a universal limiting spectrum for the sample covariance matrix that is insensitive to the distribution of u but depends the scaling variable a.
Due to the existence of the scaling variable a, the one-directional CLT in 2 can not hold unless when conditioned on a. This remark was confirmed by the findings of El Karoui (2018); Adomaityte et al. 2024). For M Ip and u of i..dd entries, [EI Karoui (2018) characterized the asymptotic error of ndge-regularized regression, which universal with respect the distribution of but not a. In other words, the GEP collapses while the CGEP with respect to the scaling factor can still apply in this setting. Adomaityte et al. (2024) considered a mixture model x A (yps, aIp) with label y 1 and random scaling factor a, under which the asymptotic classification error is non-universal with respect to the distribution of a. Here with our analysis under LFMM, we show that Gaussian universality may breakdown even for data vectors of concentrated quadratic forms as described in [[. a condition not satisfied by elliptical data vectors due to the presence of a random scaling factor a.
PROBLEM SETUP
For a set of n training samples {(x;; v:)) with feature vectors x; E R and binary labels y: E {+1), classifier is trained by minimizing the following ridge-regularized empirical risk:
s arg BER" a E.=1 [(.TB. ys) 2 111
for some non- non-negative loss function L: R x {=1} - R. that evaluates the difference between the classification score i = B3 x; and the corresponding ground-truth label y;- Data instances x with negative scores 3x x will be assigned the class of label y = 1, and those with positive scores to the class annotated by = 1. The addition of the 22 regularization term with X > 0 can improve the generalization through better bias-variance trade-off, and also ensures the uniqueness of the solution Be,, in the over- ver-parametrized regime where the feature dimension p greater than the sample size n.
In this paper, we consider convex and continuously differentiable loss functions.
Assumption 1 (Loss function). The function ((-,y): R + R, in 4 is convex and continuously differentiable with its (first) derivative different from 0 at the origin. Its second and third derivatives exist and are bounded, except on a finite set of points.
used in logistic regression, the square loss {(. y) = (y - 2) for least-squares classifier, and the square hinge loss { y) max 1 (0.1- wn] -moosh losses such as the hinge loss E(j. y) = max (0. yu) used in SVMs Schölkopf & Smola 2018). and the absolute loss E(ū y) = 1 yl. fail to meet Assumption
Assumption I holds for the logistic loss f(g. y) --n1))11(((1++++ e e-v0))
In(1/(1
In the following, we focus on the ERM in 4). and use the shorthand notation P for Br, in 4 unless there is a risk of confusion. We consider the following linear factor mixture model.
Definition (Linear factor mixture model, LFMM). We say that a data instance (x, D(x..) with class label y {+1} and class priors Pr(y -1) p. Pr(y = 1) 1 p. follows linear factor mixture model if the corresponding feature vector x E R2 can be expressed as linear mapping of independent factors 21, ....... Zz as
x x= EP ZEVE- = ER + Ve)
(5)
for linearly independent deterministic vectors Vi,..., Vp E IRP and standardized independen noises R. of symmetric distribution. Among the p factors 21,..., Zp. we have
2
Ep el.....
:......2p
q informative factors 21, 2y with deterministic signals Sy > 0, Vk E fl.....gh g); and
p noise factors 2g+1s...,, Zp with sy 0, Vk E (q 1 L.....pp. p}.
'To study these non-smooth losses, workaround would be to evaluate instead series of smooth functions that gradually approach the non-smooth functions, so as to retrieve their performance in some carefully taken limit. Such considcration is however beyond the focus of this paper.
In other words, E[ex] Varles) yk [1.....p).
4

---

Published as a conference paper at ICLR 2025
Note that (5 can be compactly written Vz, with V -Vv...... Vpl R and
[zi...., ppl [ys E1....: 1S4 Eq. Eq+l....... epl" E RP. The class-conditional means and
covariances of x are therefore given by
μ = E y = 11 E S&VA IP, Eixly = -4,
(6)
Σ = Cov x =1] vV Ei- vAV Rexp.
(7)
Notice that GMM of form x ~ (yp,, Σ) is a special case of LFMM in Definition with exclusively Gaussian noises 61, Ep. See also Definition D beloo for the associated equivalent GMM.
Linear factor models are among the most fundamental probabilistic models with latent variables, which underlie many ML methods such as PCA and ICA, and serve building blocks of deep generative models (Goodfellow et al. 2016 Chapter 13). They are often expressed as:
Wh b noise,
where h is vector of latent variables, b a constant bias, and noise stands for an uninformative term of independent Gaussian noises. The LFMM in Definition [ can be related to this form minus the bias b. Our framework requires the clusters to have opposite means (therefore b = Op), which can be satisfied through a centering operation on the original data space.
Our analysis applies under the following assumption on the distribution of LFMM. Assumption 2 (Distribution of LFMM). We consider, for the LFMM in Definition 7 that (i) the factors žı, .1..... Zp have bounded fourth moments and (ii) the signal subspace Spant Vi...., Va is orthogonal to the noise subspace Span (oan(vv+1y..... Vp).
The condition of bounded fourth moment for 21...., 2p in Item (i) of Assumption 2 is required for some concentration results in our diteesmmnnii asymptotic analysis and Item (i) separates the informative signal subspace from the noise subspace (in which no classifier can achieve better performance than random guesses).
We position ourselves under the following high-dimensional asymptotic setting, where the feature dimension and sample size n are both large and comparable.
with fixed n/p p E (0, oo), we have, for the LFMM in Definition| 7 that (i) || |E Σ Σー11 = ((1) and (ii) 81
Assumption 3 (High-dimenssonna regime). As
(1)) with fixed q.
In plain words, Assumption 3 says that the ratio n/p. p. or the number of samples per dimension, remains finite in high dimensions. Item (i) of Assumption 3 ensures, by bounding || and ||||| that the distance between the LFMM class centers comparable ||Σ|| and ||, that the variation of feature vector x on any direction in IP" is also comparable to 1. This implies that the feature vector x does not live subspace of dimension smaller than The fixed number of informative factors in Item (ii) of Assumption 3 is a consequence of |||||| = Ek= s = O(1)
1. also guarantees, by controlling
ASYMPTOTIC PERFORMANCE UNDER LFMM
In this section, we present self-consistent system of equations that gives access to the high- dimensional training and generalization performances of the ERM classifier in 4 under the LFMM in Definition [ The characterization of high-dimensional asymptotic performance via system of equations reminiscent of previous analyses under GMM (Mai & Liao 2019 Mignacco et al. 2020; Pesce et al. 2023), but our equations are different due to the collapse of the conditional one-dimensional CLT
required for applying the CGEP.
Before presenting our system of equations, let us introduce first some mathematical objects involved in these equations. With the proximal operator prax,,, arg min [f(a) + //4 (a t)² for t > 0 and convex f: + TR, we define the mapping
(, y) (prox,,((-w)) (t) t)/k,
(8)
for some constant A > 0. Let E IR be a random variable of form
ym + oe + Ei=1 VhEER
5

---

Published as a conference paper at ICLR 2025
for constants m, o, (/ ..,.... Vy with label y and c1...., Cg the corresponding noise variables in the informative factors 21..... 2q of the LFMM in Definition as well as é ~ NV 1) independent of y, :1,-..,, Zy- Remark that the distribution of r is parameterized by m, o², 1/1,..., Vg.
Self-consistent system of equations. Our system of equations is on the g-3 deterministic constants 8, 77 7, Wi,..... wy that fully characterize the asymptotic performance of ERM classifier trained on high-dimensional LFMM
(hx(r, v)
0 E
11 - Elyba w)), 7-
E v)
Ör
W/ = TE he (r. ye
+ 0 QE.
Ak E (1,....9)
(10)
where
c = uill + Σx WR
Q = (AIp + -1))
(11)
the mapping (r, y) is as defined in ( for
k tr EQ,
(12)
and the random variable as defined in with
= QE, o² QE)? 4 = VIQE. Ak fI......9..
(13)
We are now ready to present our Theorem on the asymptotic distributions of in-sample and -ut-ol-sample predicted scores. The proof of Theorem is provided in Appendix AA.
Theorem (Asymptotic distribution of predicted scores). Let Assumptions solution to the ERM problem in (4) on a training set {(xi, } of size drawn i.idd. (xi, vs)
and 3 hold, for e
D(x.g) from the LFMM in Definition we have that, for any bounded Lipschitz,unccioo R I.
IE| [[T(TT)) - E[S(3T +0
(14)
for any deterministic feature vector v E IR,, and
[Tf((xx))) x,)] - LB (prox ((--v:)))))))))))))))))))))))))) xx))] + 0, Vi fI,
(15)
where
B (AI, + +Σ)
(n++E WAVK + +
(16)
for Gaussian vector u -N Ip/n) independent of {(x,, y:) and constants 0, 0, 71.1, Wg determined by the self-consistent system of equations in (10). with k given in (12).
According to 14h in Theorem for a fresh test sample (x', ,y) (which might be drawn from a distri- bution different from D (x..) of training samples, as in the case of transfer learning). the out-of-sample
predicted scores 3 x', 3T x' produced by the ERM classifier and its nigh-dimensional "equivalent" B given in [16] have asymptotically the same distribution in the sense of (I4). Furthermore, [5] tells
us that the in-sample predicted score ,3T x, of 9 on a training sample (x,, y:) follows asymptotically the same distribution as prox,.((txx)) (,8Tx x)). Since the distribution of / is given in
(6).. we obtain
directly from Theorem the asymptotic training and generalization errors of the ERM classifier B.
Furthermore, follows from LLN and CLT that (B3T x, y) with (x, y) ~ D(x.g) independent of / converges in distribution to (r, y) with r as defined in (9) with m, ,,,,/,,,,.........../......... ..,,..., Big given in [3). We thus obtain the following corollary on the asymptotic classification accuracy of f on any training sample (x, 1/)) and test sample xx,"") drawn from the same distribution D(x,y)- The proof of Corollary is deferred to Appendix A.2.T
Corollary 1 (Asymptotic generalization and training performances). Under the conditions and notations of Theorem]] we have that, for any bounded Lipschitz, f: R. IR
E [
[b] [[[(rrlu]] -0, 0,
(17)
AAcordding to Assumption 1 derivative of h(r, y) with respect r, l.e., lime-or_ (h(t. v) h(r; v)) / (tr-).
Bhir.y) @r exists except finite set of points. On those points, we use the left

---

Published as a conference paper at ICLR 2025
for (x. ((x.g) independent of B. where is defined in 9 with 0², , Vg given in
13
Consequently, we have
Pr(y'3'* > 0) - Pr(yr > 0) + O,
(18)
for some test sample (x',y') D (xx,)) independent of [xx,, y4 )) and
Pr(y, 3T x; > 0) Pr(y proxx, (r) > 0) 0 Vi E (I.....
(19)
Remark 1 (On classifier bias under GMM and LFMM). Taking expectation on both sides of (T6),
get E (3] (AI, + AΣ) (du + Ei=1 w))&). follows from (T)) and Stein's 's lemma (Ingersoll 1987) that W1, wi,..., We 0 in the case of Gaussian informative factors 2 Eq.. As GMM is special case of LFMM with exclusively Gaussian (informative and noise) factors, have that B aligns, in expectation, with (AIp 0Σ) I under GMM. For non- non-Gaussian informative factors, we generally have non-zero wi,.... We that account for the non- Gaussian variation in data, making 3 more less aligned with the directions Vi....: Vy of the informative factors.
5 CONDITIONS AND IMPLICATIONS OF GAUSSIAN UNIVERSALITY
In this section, we exploit our high-dimensional asymptotic analysis in Section to derive the condi- tions of Gaussian universality under LFMM. To discuss the Gaussian universality in classification of mixture data, we introduce the notion of equivalent Gaussian mixture model (to given LFMM), in a similar spirit to Dandi et al. (0024).
we define its equivalent Gaussian mixture model (GMM) (gg.a) as the GMM with the same means and covariances as the LFMM ((x.g)) Namely,
Definition (Equivalent Gaussian mixture model). For an LFMM D (xx.g) as in Definition 7
g
Ny,,,
(20)
for μ. given in (6) and of Definition
1 respectively. We denote by 3 the ERM solution to 4 obtained n i..dd equivalent GMM samples (gi y1)...... (gn, Bn) ~ D D(g.a). and similarty its high- high-dimensional "equivalent" 3 as in (16) of Theorem
Notice importantly from Definition that the equivalent GMM D (g.y) to an LFMM D(x.y) can be obtained by taking el,...,
: Ep of the LFMM P(x.y) to be standard Gaussian variables.
We define two types of Gaussian universality considered in this paper as follows.
Definition 3 (Gaussian universality under LFMM). For an ERM solution 3 obtained on a gen- eral LFMM D(x.)) in Definition and an ERM solution f obtained on the equivalent GMM in Definition 2 we say that the Gaussian universality holds
classifier if ( has asymptotically the same predictive ability 335 on given test set, consequence of their high-dimensional equivalents 3r,x, Br, provided in Theorem 1 following the same distribution;
on in-distribution performance if the respective training and generalization performances under D(x.s)) are asymptotically the same as under P(R.s)- that is
Pr(vxx] B > 0) - Pr(ug... 3 > 0) - 00
(21)
and
Pr(g/x B - Pr(y'g g 0 > 0) + 0. for (x',3/) ~ D(x.)) a test sample independent of [(x,, y:)} and (g',v') ~ D(g.v) independent of {(g,, v.)
(22)
In the following, study first in Section the the Gaussian universality in the sense of in-distribution performance, and discuss our results with respect to the conditional one-directional CLT and the CGEP in Dandi et al. (2024). We then reveal in Section 5.2 the key role of square loss in inducing the Gaussian universality of classifier, and discuss its implication for the choice of loss function.
Throughout this section, discussions illustrated through numerical experiments datasets of moderately large size, with n. only in hundreds. A close match consistently observed between the proposed asymptotic analysis and the empirical results.
7

---

Published as a conference paper at ICLR 2025
Universality
GMM
Breakdown
-10
-10-2
-10
Distribution of , x
1.5
Emp
1
0.5
Figure 1: Theoretical and empirical distribution of predicted scores 3xx for some fresh (x', v/) P(x.g) independent of B. The thcoretical probability densities (red) are obtained from Theorem] and the empirical histograms (blue) are the values of 3 x over 10 independent copies of x', for three different LFMMs as in Definition with n 600, = 200, p 0.5, = [v2; 0 0p-1 (so that 9 = 1), and Haar distributed V. Left: normal e and uniformly distributed c2, Cp. Middle: normal cI,..., Cp; Right: uniformly distributed 61, and normal Cp.
5.1 GAUSSIAN UNIVERSALITY OF IN-DISTRIBUTION PERFORMANCE
Notice from (8) in Corollary that the in-iistribution generalization performance of 3 under an LFMM D (x.y) is determined by the random variable r in ( the distribution of which depends solely on (i) the distributions of y, et...., Ey in the LFMM and (ii) the values of m, o², 111, ..... by given in 13 Remark also that the values of m, o², ./..... by in (13) are determined by the system of equations (1O). which concerns only the distributions of r, c1...., Cg. as well as the deterministic parameters ,a, E, Vi,..., Va of the LFMM.
We thus conclude that the distribution of r insensitive to the distributions of noise factors Eqt l......... Zp. In other words, an LFMM with Gaussian noises e1,...,fe Cy in its informative factors 21...., 2q has the same asymptotic generalization performance as its equivalent GMM in Definition] 2 regardless of the distributions of the noise factors 2q+ly... 2p.
similar conclusion can be drawn from (19 of Corollary on the asymptotic in in-distribution training performance, by studying also the distribution of r but through a proximal mapping prax,, We formalize these conclusions on the universality of in-distribution performance in Corollary 2 the proof of which is given in Appendix A.2.2
Corollary 2 (Condition of Gaussian universality in-distribution performance). Under the settings and notations of Theorem [and Definition the Gaussian universality of ti-distribution performance in Definition 3 holds if and only if noises ei....,Cy Cg of LFMM informative factors in (5) Gaussian.
Figure D provides numerical illustrations of Corollary 2 where we compare the empirical histograms and the asymptotic distributions of the out-of-sample predicted scores 3 x' for data drawn from three different LFMMs: an LFMM satisfying the in-distribution performance universality condition in Corollary 2 (left), LFMM sharing the same parameters (μ, E, with the first but violating the condition in Corollary (right), and their equivalent GMM in the sense of Definition 2 (middle).
Remark (Connection to conditional one-directional CLT in-distribution performance in Corollary 2 are related to the CGEP proven by Dandi et al. (2024) under the presumed validity conditional onc-directional CLT in 3 Under our notations, the conditional one-directional CLT in 3 translates to the convergence of y v/ x' and 3/ //xx' x to the same normal distribution, i.e.,
Our universality results on the
x 3 m
5'g 38 m
NO,1))
S0
(23)
Va² E1 1
as it can be shown from (14) 17) that T x' has asymptotically the same distribution as yr, which is of mean m and variance o²
It is easy to see from (9) that yr is normally distributed if and only if 61,---- Gy Gaussian, which exactly the condition of universality stated in Corollary 2
8

---

Published as a conference paper at ICLR 2025
Universality
Breakdown
0.3
Fr (r; 1)]
0.5
r. (r, -1)]
0-
dbi DC
O DED
-0.5
-0.3
1
4
0.8
0.2
(x
(x<))T.m
0.4
0.1
0
-2
0
1 2
10 -5
5
10
Figure 2: Empirical and theoretical results under an LFMM with p 200, p 0.5, 8 22 0
Rademacher e1. normal c Ep, and Haar distributed V. Top: scatter plot of 200 independent
(r.h.(( (r, =-]] Bottom: histograms of predicted scores on 10 fresh samples (x', 1/) ~ D(x.g) given
by G and g versus theoretical densities obtained from Theorem |
Left: n 100, square loss E(D.8) = (0- - /2. Right: n = 600, square hinge loss ((j.g) = ma (1 }y)
5.2 GAUSSIAN UNIVERSALITY OF CLASSIFIER AND IMPLICATION FOR CHOICE OF LOss
As discussed in Section 5.T the system of equations in (10) does not depend on the distributions
of noise factors 2y+1..... Zp. As the distribution of the high-dimensional equivalent 3 to / given in (66) is controlled by the constants 0, 17, 7/ 7,:41--- Wg that are determined by (IO). it is therefore also universal over the distributions of Eg+l...... 2p. Then, by a similar reasoning to Corollary 2 we conclude that the Gaussian universality of classifier in Definition 3 holds in the case of normally distributed , Eqq.
This is however the only case of Gaussian universality on classifier. Note from 9 and (T) that,
even though the system of equations in (10) does depend on the distributions of e Egg it only involves their means and variances if hx (r, y) is linear in r. Remark also from (8) that hy (r, y) varies linearly with r if and only if the square loss ((U, y) = (Ø- - / (or its rescaled version) is used.
These two conditions for the Gaussian universality of classifier as understood in Definition are made precise in the following result, proven in Appendix A.2.3
Corollary 3 (Condition of Gaussian universality on classifier). Under the settings and notations of Theorem
7 and Definition [ the Gaussian universality of classifier in Definition 3 holds if and only if one of the the following two conditions is met: (i) , Eg in (5) are normally distributed; (ii) ol(g. y) /8 is a linear function o. e.g., E(g.y) = (ÿ //2
Remark 3 (Limitation of square loss). As an important consequence of Corollary 3 any classifier & trained using the square loss generic LFMM samples ((x,, y/ ) D(x..) and 9 trained on equivalent GMM samples [g: } ~ D(g.)) have asymptotically the same probability of correctly classifying fresh LFMM test sample (x' ~ D(x.g). That is, ERM classifiers trained with square loss are unable adapt to non-Gaussian informative factors of LFMM, contrarily to other (non-square) losses.
The particular effect of square loss discussed in Remark 3 numerically demonstrated in Figure 2 On the left hand side, the square loss Esqr (ū. v) (ū 2 /2 is used, and h, y) varies linearly with r as in the top left plot (the two elongated scatter plots are associated respectively with y = =1),
so that the distribution of X Bem.r.A and x"T 3 Lngr. are indistinguishable in the bottom left plot of
Figure 2 On the right hand, the square hinge loss Cang((1))) (Ū.y) max (0, 1 0y)² is used, and observe drastically different behaviors for x"T Br A and x"T 3 Aalieg in the right column of Figure 2 when the points [r., hy =1] are highly nonlinear.
Remark 3 supported by the numerically results in Figure points to the insensitivity of least-square classifiers to the distributions of non-Gaussian informative factors, despite their non-universal impact

---

Published as a conference paper at ICLR 2025
GMM
LFMM
Accuracy (%)
0.9
Th
Square loss. Emp
Log loss. Emp
0.8
Square Joes. Theo
Log loss, Thoo
9
2
26
2-9
2
2
2
Figure 3: Empirical classification accuracy of Br,, computed over 10 independent copies of (x',y") P(x.y) and averaged over 100 trials with width of +1 standard deviation, versus theoretical performance given in Theorem I given by the square loss ( y) (y 8) /2 and the logistic loss {(). y) = - (1(1/(1 + e e-vy) and on n = 800 training samples. Left: GMM under Definition 1 with p 200, p 0.5, [1, 5; 0.5; 0p-2] (so that 2), and V diag(2, 1p-1) H with Haar distributed H. Right: LFMM identical to the GMM in the left, but with Rademacher é!.
on the in-distribution performance discussed in Section 5.1 The incapacity of square loss to account for non- non-Gaussian variations in the informative factors sheds light on the suboptimality of square loss observed in the right display of Figure 3 where the logistic loss yields better performance than the square loss with optimally chosen regularization À on LFMM having non- non-Gaussian informative factors, while the logistic loss fails do better than the square loss under the equivalent GMM in the left-hand figure. Further experiments on real-world datasets are given in Appendix B
This finding on the suboptimality of square loss under LFMM provide new insights on the impact of loss function beyond previous optimality results of square loss under GMM. For high-dimension
GMM data, the square loss has been proven optimal, see (Taheri et al. 2021b) for the case of unregularized ERM, and MMai & Liao 2019) for ridge-regularized ERM, in the n, + limit. That is, the square loss not only gives the best unbiased classifier, but also allows for an optimal bias- variance trade-off with well calibrated rndeeregularrizttoo. As a result of the Gaussian universality breakdown discussed above, the optimality of square loss is no longer valid under the more general LFMM. This motivates a few open questions the optimal loss:
Is the square loss optimal only under GMM, or when the Gaussian universality of in- distribution performance in Definition holds?
In the case of Gaussian universality breakdown, does the optimal loss depend the sample ratio n/p as in the setting of linear regression (Bean et al. 2013)?
Is it possible, in the large n. p regime, to propose an optimal design of classification loss adapted to the data distribution and sample size?
6 CONCLUDING REMARKS
Our analysis considered a basic framework of linear factor mixture models (LFMM) and showed that the Gaussian universality can already break down under this natural extension of GMM. Based on the precise performance characterization, we derived conditions of Gaussian universality to shed light on the limit the widely observed and extensively studied Gaussian universality phenomenon.
Breaking the Gaussian universality in classification of mixture models allows also deeper insight into the choice of classification loss beyond the optimality of square loss under GMM (Taheri et al. 2021b Mai & Liao 2019). The suboptimality of square loss under LFMM can be further investigated in future works, to propose, for instance, an optimal design loss function that takes into account the data distribution and the sample size, as done by Bean et al. (013) for linear regression.
Several simplifications made in our analysis can be removed more or less easily. For instance, while the extension to multi-clas classfficassiiinnnnnnnc is fairly straightforward, the generalization to non-smooth losses less direct: even though our system of equations in (10) does not require access to the derivatives of the loss function, they are involved in the establishment of these equations.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Z. Liao would like to acknowledge the National Natural Science Foundation of China (via fund NSFC- 62206101 and ASFCC-1244100 and the Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2033B121201000) for providing partial support. This work also supported by the Cluster ANITI --NR-19--13A- 19-P13A-0004).
REFERENCES
Urte Adomaityte, Gabriele Sicuro, and Pierpuolo Vivo. Classification of heavy-tailed features in high dimensions: a superstatistical approach. Advances in Neural Information Processing Systems, 36, 2024.
Zhidong Bai and Jack W Silverstein. Clt linear spectral statistics of large-dimensional sample covariance matrices. In Advances In Statistics, pp. 281-333. World Scientific, 2008
Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdehorová. Optimal emoos and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 16( 12):545115466) 2019.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30033-30070 2020.
Derek Bean, Peter Bickel, Noureddine El Karoui, and Bin Yu. Optimal m-estimation in high- dimensional regression. Proceedings of the National Academy of Sciences, 146636))4553--4456, 2013.
Michael Celentano and Andrea Montanari. Fundamental barriers to high-dimensional regression with convex penalties. The Annals of Statistics, 50(1):170-19))) 2022.
Michael Celentano, Andrea Montanari, and Yuting Wei. The lasso with general gaussian designs with applications to hypothesis testing. The Annals of Statistics, 51(5):2194-22) 2220, 2023.
Romain Couillet and Zhenyu Liao. Random matrix methods for machine learning. Cambridge
University Press, 2022.
Yatin Dandi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro, and Lenka Zdeborová. Univer- sality laws for gaussian mixtures in generalized linear models, Advances in Neural Information Processing Systems, 36, 2024.
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification. Information and Inference: A Journal of the IMA, 11(2): 435 495, 2022.
Edgar Dobriban and Stefan Wager. High-dimensional asymptoties of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-27) 229, 2018. ISSN 0090-5364. doi: 10. 77-a0s1549
David Donoho and Andrea Montanari. High dimensional robust m-estimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166:935-969, 2016.
Noureddine El Karoui.
Concentration of measure and spectra of random matrices: Applications to correlation matrices, elliptical distributions and beyond. 2009.
Noureddine Karoui. On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators. Probability Theory and Related Fields, 170:95-175, 2018.
Noureddine El Karoui, Derek Bean, Peter J Bickel, Chinghway Lim, and Bin Yu. On robust regression with high-dimennt dingh--imesiooall predictors. Proceedings of the National Academy of Sciences, 110(36): 14557-14562, 2013.
11

---

Published as a conference paper at ICLR 2025
Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. General- isation error in learning with random features and the hidden manifold model. In Internationaa Conference Machine Learning, pp. 3452-3462, PMLR, 2020.
Federica Gerace, Florent Krzakala, Bruno Loureiro, Ludovic Stephan, and Lenka Zdeborová. Gaus- sian universality of perceptrons with random labels. Physical Review E. 109(3):034305, 2024.
Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mézard, and Lenka Zde- borová. The gaussian equivalence of generative models for learning with shallow neural networks. In Mathematical and Scientific Machine Learning, pp. 426-471. PMLR, 2022.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http: 7 w/www www.deeeplearringgooooooo org
Qiyang Han and Yandi Shen. Universality of regularized regression estimators in high dimensions. The Annals of Statistics, 51(4):1799-1823 2023.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Annals of statistics, 50(2):949, 2022.
Hong Hu and Yue M Lu. Universality laws for high-dimensional learning with random features. 2022.
IEEE Transactions on Information Theory,
Hanwen Huang. Asymptotic behavior of support vector machine for spiked population model. Journal of Machine Learning Research, 18(45):1-21, 2017.
Hanwen Huang and Qinglong Yang. Large dimensional analysis of general margin based classification
methods. Journal of Statistical Mechanics: Theory and Experiment, 2021(11):113000 2021.
Jonathan E Ingersoll. Theory of financial decision making, volume 3. Rowman & Littlefield, 1987.
Adel Javanmard and Mahdi Soltanolkotabi. Precise statistical analysis of classification accuracies for adversarial training. The Annals of Statistics, 50(4):2127-2156, 2022.
Abla Kammoun and Mohamed-Sling Alouini. On the precise error analysis of support vector machines. IEEE Open Journal of Signal Processing, 2:99-1 1199-118..1 18, 2021.
Zhenyu Liao and Romain Couillet. A large dimensional analysis of least squares support vector machines. IEEE Transactions on Signal Processing, 67(4): -074, 2019.
Marco Loog, Tom Viering, Alexander Mey, Jesse H Krijthe, and David MJ Tax. A brief prehistory of double descent. Proceedings of the National Academy of Sciences, 1 10255-11662 2020.
Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions. Advances Neural Information Processing Systems, 34:10144-10157, 2021. 2021.
Bruno Loureiro, Cédric Gerbelot, Maria Refinetti, Gabriele Sicuro, and Florent Krzakala. Fluctuations, bias, variance & ensemble of learners: Exact asymptotics for convex losses in high-dimension, In International Conference on Machine Learning, pp. 1 14314. PMLR, 2022.
Xiaoyi Mai and Romain Couillet. Consistent semi-supervised graph regularization for high dimen- sional data. Journal of Machine Learning Research, 22(94):1-48 2021.
Xiaoyi Mai and Zhenyu Liao. High dimensional classification via regularized and unregularized empirical risk minimization: Precise error and optimal loss. arXiv preprint arXiv: 1905. 13742, 2019.
Xiaoyi Mai, Zhenyu Liao, and Romain Couillet. A large scale analysis of logistic regression: Asymptotic performance and new insights. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3357-3361. IEEE, 2019.
Antoine Maillard, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Phase retrieval in high dimensions: Statistical and computational phase transitions. Advances in Neural Information Processing Systems, 1 2020.
12

---

Published as a conference paper at ICLR 2025
Vladimir Alexandrovich Marchenko and Leonid Andreevich Pastur. Distribution of eigenvalues for some sets of random matrices. Matematicheski Sbornik, 114(4):507-533 1967.
Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova. The role of regularization in classification of high-dimensional noisy gaussian mixture. In International conference on machine learning, pp. 6874-6883. PMLR, 2020.
Andrea Montanari and Phan-Minh Nguyen. Universality of the elastic net error. In 2017 IEEE International Symposium on Information Theory (ISFT), pp. 2338 2342, June 2017. doi: 10. 109/ 1SIT.2017.800694.
Andrea Montanari and Basil N Saeed. Universality empirical risk minimization. In Conference on Learning Theory, pp. 4310-4312, PMLR, 2022.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021 2021(12):12400) 2021.
Ashkan Panahi and Babak Hassibi. A Universal Analysis of Large-Scale Regularized Least Squares Solutions. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Leonid Andreevich Pastur and Mariya Shcherbina. Eigenvalue distribution of large random malrices. Number 171. American Mathematical Soc., 2011.
Luca Pesce, Florent Krzakala, Bruno Loureiro, and Ludovic Stephan. Are gaussian data all you need? the extents and limits of universality in high-dimensional generalized linear estimation. In International Conference Machine Learning, pp. 27680-27708. PMLR, 2023.
Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. Classifying high- dimensional gaussian mixtures: Where kernel methods fail and neural networks succeed. In International Conference Machine Learning, pp. 8936-8947 PMLR, 2021.
Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high-dimensional logistic regression. Advances Neural Information Processing Systems, 32, 2019.
Bernhard Schölkopf and Alexander Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, 2018. ISBN 978-0-262-25693-3. doi: 10.755 11775///micces441.0000.0000
Dominik Schröder, Hugo Cui, Daniil Dmitriev, and Bruno Loureiro. Deterministic equivalent and error universality of deep random features learning. In International Conference on Machine Learning, pp. 30285-30320. PMLR, 2023.
Pragya Sur and Emmanuel Candès. A modern maximum- likelioodd theory for high high-dimensional logistic regression. Proceedings of the National Academy of Sciences, 116(29):14516111 2019.
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Fundamental limits of ridge- regularized empirical risk minimization in high dimensions. In International Conference on Artificial Intelligence and Statistics, pp. 3773-2781, PMLR, 2021a.
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Sharp guarantees and optimal
performance for inference in binary and gaussian-mixtue mixture models. Entropy, 23(2):178, lb.
Terence Tao, Van Vu, and Manjunath Krishnapur. Random matrices: Universality of esds and the circular law. 2010.
Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-567) 2018.
Christos Thrampoulidis, Samet Oymak, and Mahdi Soltanolkotabi. Theoretical insights into mul- ticlass classification: A high-dimensional asymptotic view. Advances in Neural Information Processing Systems, 33:8907-8920, 2020.
13

---

Published as a conference paper at ICLR 2025
Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of gaussian mixtures. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4030 4030-4034. IEEE. 2021.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprini arXiv:1708.07747, 2017.
14

---

Published as a conference paper at ICLR 2025
A PROOFS
Here, we present the detailed proofs of our theoretical results in the paper. Precisely, the proof of
Theorem is given in Appendix A. and the proofs of corollaries given in Appendix A.2 (the
proof of Corollary i Appendix A.2.I the proof of Corollary in Appendix A.2.2 and that of Corollary in Appendix [A.2.3 (A.2.3 respectively).
Notations. Before getting into the proofs, we first introduce the following asymptotic notations. The big O notation ((u,)) is understood here in probability. We specify that when multidimensional objects are concerned, (u,,) is understood entry-wise. The notation Op-1(-) is understood as follows: for a vector v. V O11-1 (u.)) means its Euclidean norm is ((,,) and for a square matrix M, = = O1-11 (u,, means that the operator norm of M is O(u,). The small o notation and Big-Thees are understood likewise. Note that under Assumption (u,,) since n, scales linearly. In the following we shall use constantly O(u,) for simplicity of exposition. The symbol ~ is used in the following sense: for a scalar & = O(),, 8 = 8 indicates that 5 o(1), and for vector with ||v|| = O(1), variable r ~ N(m,o' with potentially random m and o², the expectation [[f(r)] should be understood conditioned on o², that, E[r] is equal to instead of E[m]]. When parametrized functions (-) are involved, Ejsr (r)] is computed by taking the integral over r.
is equivalent to use either (w,,) or
v means ||v vll = (1). For random
A.1 PROOF OF THEOREM
In this section, we will provide the proof of Theorem T leave-one-out and laying out the key steps as guide of our proof.
We start by explaining the main idea of
A.1.1 MAIN IDEA AND KEY STEPS
Taking À > 0 in the optimization problem 4 ensures a unique solution 3. Cancelling the gradient
(with respect (3) of the objective function in of /
4 obtain the following stationary-point expression
1
A
(BT Xxs B:)x,
(24)
n2
where we denote (t,,, vi) ae(t.w)) ot
To characterize the behavior of 3 from (24). we need to assess the statistical behavior of gT x,, which is not directly tractable due to the intricate dependence between , on x; resulted from the implicit optimization 4 To tackle this complication, we make use of a "leave-one-out" version 3_ of B with respect to the i-th training sample (x,, y), obtained by solving (4 with all the remaining n training samples (xj, Uj) for + i. Again we have
Σ (1, jæ
(25)
This leave-one-out solution B_, has two crucial properties: (i) it is by definition independent of the left-out data sample (x,, v:); and (ii) it is asymptotically close the original solution , as removing one among n training samples has a negligible effect as n + co. These two properties imply that (_, and / behave similarly on all training or test samples, except on (x,, vt). which is training sample for / and new observation for $_..
Our proof relies on these two properties to derive a series of equations characterizing the limiting behavior of (8T x; and Tx'. Below is an overview of our key steps to guide the readers through the proof.
Key steps:
1. Establishing the high-dimensional approximation
33
3I,x - -ke (Txx;,9)))
(26)
15

---

Published as a conference paper at ICLR 2025
for some constant independent of i.
2. Obtaining from 26) that
B x; = proxx, (3 Vi):
and therefore
- Xi, 9:) = 11@3" -xi, yi) = prox .e) (B_ Us) B x
where recall h1t,, y) (prox x.( (1) f)/k with proximal operator prox,,,(1)
arg min [f(a) + 1 (a - - for T > 0 and convex f: R + R.
2r
3. Using the approximation in Step 2 to rewrite 24 as
2/ ~
M X XX,,
n
1=1
for
Vz, = Vitk + Ve with e, the noise vector e .e....., cp] R2 for x,, thereby replacing the intractable [T x; in (24) with a tractable function of [_x,..
4. Demonstrating the concentration result
x Xx, Vi)ai = n
for some deterministic 7).
5. Demonstrating the concentration results
Σ h x weel or Øb. Vk E (I,...,9)
for some deterministic o1..... 0g. and
n Σ
[ =0, Ak (q+ + 1,...,pp
M
n
6. Demonstrating with concentration arguments and CLT that
x h Xx, - V n cc
n
where é; = [e:]g+ V noise Notls..... Vpl and RP random vector such that, for any deterministic vector t = |1tt1...., 4p] E TRP- of unit norm,
Vnt E/7 - N(001)
in distribution, for some deterministic 0 and 7
7. Demonstrating
1 - tr EAI, + +E).
8. Establishing asymptotic equations 17, 0, and 6 from the results of the above steps, which characterize the limiting behavior of the solution A.
In the following, present the detailed proof of Theorem
16

---

Published as a conference paper at ICLR 2025
A.1.2 DETAILED PROOF OF THEOREM 1
We start by establishing the following bound on the difference between 3 and its leave-one-out version B-i.
Lemma 1 (Bound on B-i1- For B E
IP the unique solution to 4 and B_g E R2 the
associated leave-one-out solution as defined in (25
that is independent of x,, we have,
8 3_ = -Op
(27)
in probability as n. + co.
Proof of Lemma 7
We define first
Rj = X,,
= E' (1'xx,,11 Xj, Vi),
for all j [L......) and their leave-one-out versions
Rz(-i) = c)(-8) = e' x3. 1/).
for all j E nZ..
According to Assumption I ((.,w) is continuously differentiable and has bounded second derivative except on a finite points of set, therefore there exists universal constant K such that (4' - l' (t2) S K|t, fzl- As result, for every pair of i.j ... there exists finite positive (due to the convexity of E(-,8)) value aj(-i) such that
Cj ---( -aj(-s) -3T,,,13,xx,)
(28)
Taking 24
we obtain
1 Σ -((-)))x
2
2
-C;;;
n
n
1 Σ |
(B (8-
= =- Cx -
##L
Therefore
AIp + Σ - (8 (8-
c,
and
-1 Σ x
1
B B,
AIp + n
-x..
(29)
n
571
Since 1 Enys x),+) is non-negative definite, all eigenvalues of (ΛI,, + E. are greater than or equal to X, so that
| - B
An G; | 0pp Op--b)
where we use the fact that 3 has bounded norm as n.p - oc, which is easy to check for 0, to prove the boundedness of c;. This concludes the proof of Lemma
17

---

Published as a conference paper at ICLR 2025
As consequence of the proof of Lemma 1 have, by 28 that
a)(-1) ( x., v/ (pp
where (t, (tat)) This equation is however only valid when (.)v) exists, while in Bt Assumption [ we allow y) to not exist on a finite set of points. Actually, as the number of R3 falling this set of point is also finite, we can take (t) a_f((t.)) without any asymptotic 0
impact on our results. To see that is finite, we use (24) to establish n linearly independent equations on R1. R.: AR; - Σ () Wi n..
As x....., X, are i..dd feature vectors drawn from the high- -ibedeimiiionnll LFMM, the number of R; having the same value is finite with probability at large
With a slight abuse of notation, let us set from now on
ax(-) = (3_
Then, 29
writes
1
B-B-,
-, (1-))
(30)
n
where
1 Σ a)(-))
G_ MIp + T1
jti
Notice that G())) is independent of (x,, yr). For R₂ = 13 x; and Ti = Re(-i) = ,,,,, we have, by the law of large numbers on (recall that Exx,x;] nh + E), that
R. Pi xxx G + 0(p 1) c. V G= 0
1
1 n
n
1
tr (G + +(p
(31)
where the last equality is a classical concentration result as a consequence of the independent entries in e;, It is understandable that is significantly different from R2 as the latter is the predicted
score of 3 one of its training sample and the former the predicted score of 3_, on test sample independent of its training set.
Let us define
- tr (GI|Z),
k= -r (t I)),
where
1
G
AI + n
axx,x
with aj - xj. It follow from
30p that TTx, TT,xx =0(= therefore ag =
aj(-i) + +(p $). It then easy check that
K 0 :).
We can thus rewrite 31 as
R; - kc; + 0pp
(32)
We arrive thus at the end of Step 1. At this point, we do not have access to the statistical behavior of k. only the fact that it is independent of the data index i.
Recall
1e y) (prox 1)/R,
(33)
we obtain from 32)
G hhhlrri wi) 0p-11)
18

---

Published as a conference paper at ICLR 2025
It then follow from the above equation and
24 that
2
Σ
(ri, y)x; + +11111(p
(34)
i=1
Set from now on and rewrite (4 as
= (ri,
X
cx2; + (p-1(=
(35)
1m1
We arrive thus at the end of Step
We will now demonstrate
1 Σ ycc: Blyne - Opp
(36)
by showing the variance of n2 Σm= yeG; is order Op-
To do so, we need to introduce the definition of leave-two-out solution 3_ obtained by removing not one but two training samples (x,, 34) and (x,, W;). The subscript -ij understood similarly to the subscript -i, but associated with the statistical objects dependent of B_ij. Similarly
30p. have
B.. B n
-9-1)s G -0
(37)
where
C(-i) hx ( r(-ij) -
Multiplying 37
with x. from the left side, we get
T T(-)) - - + Opp-bppp) $).
Then for i + j. observe from the above equation that
Elyacuye = (ra
= Ely,y,h, 81) (r Uy)l + O(p :).
Note importantly that, conditioned 3- ((- and r(-i)s independent. We have thus
E(y.,,ha(r( 9: (r) = h Wun.ghahorr.........ara...-.-.-
Blyshn (|
1,
(r -r
Since he (r(r(-i))-V)) hu(rs, 91) Op 1), we get from the above equation and the one before that
Elncyyyy Ely.c Elggeyl O(p O(p- #).
It follow directly that
Var
1
V&C = -(pp $).
(38)
Therefore
yic: 17 + O(p
+)),
with
17 B[yaa.
(39)
We prove thus
39
which brings to the end of Step
4
19

---

Published as a conference paper at ICLR 2025
By the same reasoning, obtain also
clel ox +
with O = [[c/[e]
(40)
To see that
dx = 0, (u
we define first the cavv-one-variabll--uu classifier 3 as the solution to on training set generated from slightly differently distribution than D(x.g). with ex constantly equal to zero. The superscript - is understood similarly to the subscript -i in the statistical objects dependent of G- with their deave-one-variable-on version obtained by replacing f_ with 3 Similarly to the leave-one-out reasoning with respect the data samples, the applied to control the difference between 3 and G- In the same spirit (30). have
asymptotic arguments can be
- G - lil (1-11(-7) --
(41)
71
where efr E IRth is a vector with its i-th element being [ei|e. and G-k a matrix of bounded norm with high probability and independent of [e,]k-
Note first from 35 that
XV noise
3
C V Vooise x; + (1-1
1=1
C: V noise VT
noise + (1-1(1=
(42)
n
where we have V VooiseX; V noise VT noise e according the orthogonality between the signal sub-
space and the noise subspace stated in Item (ii) of Assumption 2 As the eigenvalues of V noise VT are comparable to 1 according to Item (ii) of Assumption
noise
we get
(V noise VT
uuise))
V noise
Σ Gā O1I
(43)
n
Similarly, we have, for g-k that
n
A (V noise VT ) V noise
Σ
Gē
(p-
(44)
Combining 41 and we obtain that, for {q 1.....p.
Φx - (V noise VT
V
Vooiee
+0pp +)
noise
k-q
(V noise VT
noise)
V noise
EE BB $1
1 |B [B(G-=e(w)
+0pp
n
k-q
=0(p }),
(45)
where we used the fact that
(V noise VT "
V hoiseEEB
81]
Σ
Blc, le "1e-gl = O,
k-4
n
since 10 (0 for all (1....,n) according to the definition of the leave-one-
variable-out classifier 3-k
We arrive thus at the end of Step5
20

---

Published as a conference paper at ICLR 2025
Recall from 45 that Φ = O(p )) for ls E {q + 1, ,,...,p). have thus from (40) that
aloije Opp-1), vk {a 1..
follows then from 42 that
Ak ta 1,..,.,,,p V - 0
(46)
We observe then, for & {q + I.....pp. p}.
1
Σ
h (r
hr 1 Σ
( va)(oclk.. Vi Jeile
=
==1
==1
k=
h
[eile
i=
dgtk
hi
Σ ( va)aelles Di (BTv))
(47)
1=1
dack
Σ (a"vva)lssass va)lesla.
( 0(p (48)
1=1
deck
where we denote (r v) We denote the first term by
8h., (r.w)
8r
C
1
Σ
h
[ valloas [e:]a-
i=1
dgt
Note from 41 that
Ek
hx
Σ dzt
[vT Mi [ei] O(p-1).
(49)
71
Since g-k is by definition independent of all [ei] for i [I....,n), we notice that all hee (Edp)(vJ 3/i [es]a, E (I,...,m) are independent conditioned (old) Joe(a+1....p We assess the conditional mean of e as follows
E [culf Ide (....))
Σd hx
E(vi0 -
(0(00~))oo)) ") Vs E [[cllal] O(p :)
dztk
-0 ))
(50)
Similarly we have
2
1 a
Var [cxlf d
(
>
hr
[vv
[e:]a. Di
E [[.]]]]]
n²
dzfk
27
E
hw
Σ (v -0 - 81
O(p O
11
dzfk
21

---

Published as a conference paper at ICLR 2025
where the second line is obtained by similar reasoning to (39) We remark thus that the concentra- tions of the conditional mean IE JdE(utt....p)A)) and variance Var [ex|f e! fde(ott....pp/ around the same limits:
E [E ( pe [ol =0(=-)
Var leulf Ide +-²+0 4), with ²== [cc]].
(51)
In summary, when conditioned on {eld) JuElgtI.....p the sum of independent fl....,m} is of mean asympiotically equal to 0
Vi) [eilk; i and variance asymptotically equal to y². Then, by the central limit theorem, we have VTEe/7 4 IV,,,), Ak ( 10,+1...... l...,.,,
hi
(52)
in distribution as p oo at the same pace.
Now we wish to show that
Vn
tECK/r 4 N0.
(53)
lmg+1
for any deterministic vector t = [fg+1........ tpl" E R of unit norm. To this end, we introduce the leave-two-vee -or-ttto-varibbes-oout solution g-kdd obtained similarly g-* but with both Ck Cd constantly set to 0. The superseript kkd is understood similarly to the superscript kk, but associated with the statistical objects dependent of 3_k It is easy to see that
E
LEER
Σ
[x Olp 0pp-
k=9+1
k=
To approximate the variance of vn En 2x
LNER, let us define first
k2
1
h
Σ
(vī k2 No)ld V4
[eolkr
(54)
n
for which we have
G
'ki
K2 + (p (p-2)
(55)
from
and (46)
Similarly to (49)
we have
hic
( ki [cild,
[eila, + 1(p
dzt
Therefore
Cki
hx
Σ (v kikz
k [eila. Mi
[ei]e, + (
i=1
6k2 hw Σ (vT ks (eslld. Vi
[ei] + (p-t).
where we notice that Em he (Edyhe M= 9i [cilen is independent of
En hn (Eigehei (v ky ko [esles 81s) leilez. We obtain thus
p = n Σ
P
Var Vn Σ tkck
t [e, cka ckul = n Σ E +n
Σ
EE [en, Ekyl
kmg+1
ky .ig +
2 + Opp
22

---

Published as a conference paper at ICLR 2025
To obtain 53). suffices demonstrate the asymptotic mutual independence of Cgtls...... c by showing that E is asymptotically independent of d4k=0111 for all & E {9 + 1,..,; P). Let k q + 1 without the loss of generality, observe from 49 and
52 that
c-+1
(g+ (esla,
leig++1:
2m
1
and recall from
55 that
(g+1)
c
g+t
(g+1)
9t3
(9+1)
Ep
It is easy to see from
54 that 9+2
1(++1)
..... (0+1)
is independent of Cx+l. Therefore
E hi Edeeth (v Ne:la.3.) /eilo+1 is independent of c++ ..... Cp
(9+1)
(o+1) We
obtain thus 53
Now the second term of 488) In similar manner 339h have
E va)
[e,]
Σ
h/
EvIBB~
[eilds Da
[e:lk + +
dytk
==1
<(v ) Vi
E [[]]]]]] + Opp 1).
dgtl
Consequently,
[ va)(ee)e) desck
[e:]2:8T v4 1aa=0(0--
--00+00 + O(p
Vv, with 0 -B(K (ri, wc)
(56)
To control the third term of (48) it suffices prove that its second moment is opp 5) by using the concentration arguments with the reave-one-variabl--o0 manipulation as before, and the fact that Tvv Opp- 1) for & E {q + L....,p..
arrive thus at the end 6
Rewrite now 35 as
1 Σ Ve, + (p 3).
X
caysu n
(57)
Summarizing 39
40
48).
52p. nd
56). we obtain
X/ mp VKVE OV
noise VT Moise V E,
with e = [(gtt,-..... pp Therefore
B (AI, + +02)
WAVE + V Vncisee) mp
(58)
where wy Φu +E Vk. and
Vnt e/7 $ 10,11)
23

---

Published as a conference paper at ICLR 2025
for any deterministic vector t 11 .....
I
RP-9 of unit norm according 53
Similarly,
we have, for the leave-one-out solution, that
i = (AI, + +02) -1
Wk
V nnise
(59)
where e-; = (eg+1(-1)) ................................ (p(-i)) with
()(-1) Σ
hN
Σ vallsllles [esJa-
jti
dtk
We get from (30) that
1 hn
E(ST [(@Tva)(esle va)lesld. Vi [ei]a-
Ck - (k(-1)
dsc
Hence
B-B (AI, +00)
hoiie
leading to
xT - x xT =(1i + Ve,) (AIp + AΣ)
noise C,O,
n
Lr (AI, + -Σ).
Comparing the above equation with 32 we observe
1 tr EAI + +E).
We are now at the end of Step
It is casy to see from 59) that
r = 0_ = y:m +
the (ese + tōē
where ē a random variable independent of [e.]i.....
[e:]g with
4 10.
and
QE. σ² = tr (QE)
= p
th V.Q.
Ak fl,.....
with
(AI, 0Σ) -1
WkVK
We obtain thus the system of equations in 10 from the values f 77 y, .... wy-
40
and 56) which gives access to
Set
i = (AI, + -
1/14 +
(60)
where (O p. I,/n, n/n. We obtain
14 from 600 and
58
by simple application of CLT, and
15) from (60). (59) and 32
This concludes the proof of Theorem
24

---

Published as a conference paper at ICLR 2025
A.2 PROOFS COROLLARIES
A.2.1 PROOF OF COROLLARY
Recall from Theorem 1 that
B = (AIp + 0Σ)
WeVE 7
for Gaussian vector u ~ (0p, m/) independent of ((x;, For (x, v) ~ ((x,)) indepen- dent of B3 we recall from Definition that
x= yp + Ve,
with [er....,,y ep]². Then, let V noise
(o+ll.... Vpl and ē leqtt......... epl. we have
8xx x = ym + dRCR + g noisee
noise + yu ' QV C
with m, ....... 4. as given in 13). and Q E as in
Note importantly that
E SvQ = 0, Ak {g ... due to the orthogonality of Span(vi..... v,] Span Vo+1. vp3 stated in Item(i)) of Assump- tion 2
As u, e are independent random vectors of independent entries, we have, by CLT, that
?u yu QV
noise
10,,
Var
yu y QV noise
Remark also that
22 ir (EQV noise VT n
2 (EQ)²
Var
y T Σ
QV in Corollary I
noise
noise Q)
n
We thus obtain
From
14 in Theorem
we have
Pr(y/ 3T 0|(x' v/)) Pr(y/ 0|(x'x ,((x','')) -
Taking expectation over (x', v²) D (x.)) get directly from the above equation that
Pr(y'3 0) Prly
0
It follows straightforwardly from 17 that
Pr(y'3Tx x > - Pryyr > 0) + 0,
leading to (8))
Similarly, we obtain
19 from
and (15) which concludes the proof.
A.2.2 PROOF COROLLARY
easy to see that, when eI...., E are normally distributed, the random variable r defined in g follows Gaussian distribution A o² Ei= 2 For r N(m, 0² + Ei=1 v with m, a, .1,.... th, as given in (13), we observe that the system of equations in (10) is invariant to the distributions of e1,..., Cp, thus yielding the same values of 0, 1J, w,.,,....... as well as the same K, m, 0², 11 .i........ 44g
Therefore, with Gaussian c....., Cg. follows universal distribution A(m, o² Ei v2 in-
dependent of the distributions egtl...., Ep. We have also the same universality result on the distribution of prox prox,,tt.w k.((-a)) (r) as the value of 6 is also insensitive to the distributions of eet1y Cp-
25

---

Published as a conference paper at ICLR 2025
Combining the above universal arguments the distributions of r and (r) with Corol- lary [
we prove that the Gaussian universality of in-distribution performance in Definition 3 holds e1....:: Cy are Gaussian variables.
remains to demonstrate the breakdown of Gaussian universality on in-distribution performance 61.-..: Cg -on-Gausii
Note first [ = (11) with À ((1). The boundedness of ||Br.x|| in the large n.p limit is easily justified from the regularized optimization penalty 4 with À > 0. Recall also
A - Σ 1=1
"B X1, xi, Vi)x:
from which we observe that, to ensure |1Bex11 = o(1), we need (( x,, v4) = o(1). However when || o(1), have (' x v1) (0, vt) @(1). We thus get || @(1) by contradiction. Consequently, we have also |r.ll ((1) for the high-dimension
equivalent / given in Theorem Since 33 x for x ~ (xx independent of has asymptotically the same distribution in 9 according Corollary it follows from |1 ((1) that @(1).
Therefore = h r, y)] = (1).
Let us reorganize the expression (6)
XB mp
DEVE OV noisse VT V 3 +
(61)
k=
with
Φk wk 0v y)hu(ry)eel, Ak E qI.
Recall from (8) that
(e y) (prox, (eroxx_e(-10 m.e(-.)) (1) - l)/K,
where prox,, = arg min [(a + 2- (a - t)3 for 7 > 0 and convex f: - R. Due to the
convexity of ((.,y) y) Assumption (x y) a decreasing function. As , are standardized variables of symmetric distribution according to Definition I we have
(r, v)) y)e
hx yym-oē+
Σ dE(D....a
vueat JerPe (dex),
where P.. is the probability measure of ek. As eg is a centered variable of symmetric probability distribution, have
hr
4m
oē +
Σ
Uhea - tkeks y/ en Pen (dex)
dE/L...gg
ym + oē +
Σ
Vhea + whek. ex Pau (dex)
hx ym + σē +
Σ
daca - -hee, 1/ ex (dex)
de
As hee(t,)) decreases with i, there exists a positive value a > 0 such that
hec (mmtor+
Σ
Sueat -hx tx (umttet
Σ
Vded Vded-threk thek. --2arbeer ek.
dEV
dE(L....QF.k
In the end, we have
Φ1 (r, - -0
where og 0 for all e (1.....q). :
26

---

Published as a conference paper at ICLR 2025
Plugging in the above expression of Φk, rewrite (61)
2 4Ipl
VL OV noise
VT
noise 3 7 E u.
Taking expectation at the both sides of the above equation, get
XQt = mp
V - VV noise VT noise B
k=1
Therefore
XV info Of = Xxp = v/V
Info V S
VT
Info V Vant ag)
where V Vi,.... Vgl. 3b [,,,.... Gg I and (8 ... sg)- As V Viñoo and both deterministic with no presumed relation, we consider them to independent in some probability space. We obtain thus
+ n (AI, + V info Vitodiag(au........
Vinos @(1)
info
Therefore r is non-Gaussian unless in the case of Gaussian el...., Eg. leading to the breakdown of in-distribution performance in Definition 3
A.2.3 PROOF OF COROLLARY
As discussed in Appendix of B, is universal in the case of normally distributed ei...., Eg. We obtain directly the Gaussian universality of classifier in Definition 3 Jnder the condition of Gaussian .
the system of equations in (1O). which determines the distribution
Note importantly that when de(ů. /ō is a linear function of of form
@g(g. O) aÿ + b(y)
for some constant a > 0 (due to the convexity of E(- v)) and b(y) independent of g. we have
9 -xbbyy)
prox (0)
1 + ka
which leads
w. (0) 5
- aÿ b(y)
N(. y)
1 + k0.
Recall from that
ym oē Σ
shee.
km
The equations in
10 thus become
am E[(y(yy)
E[Oh, (r: w)/rrr
1) = Elyhh (r, v)]
1 + ka
+ ka
aa (m2 + 0² + >i=1 152) E(b(y))
2amn (yb())
7 / Ehh
1 ka
-arbx + 0 v QE
Wk = E[hh(r, y)ec + 0. vIQq= = 1 ka
which are independent of the distributions of the noise variables ei..... We prove thus the Gaussian universality of classifier in Definition 3 when Øe(ū. v) v) is linear function of ÿ-
Conversely, when dc(g. /0 is a nonlinear function of ÿ. h (r, y) is also a nonlinear function of Consequently, the values of 0, n,, 7, wi,...,,4, Wl depend the higher-order moments of c Cg besides the first two, thus leading to the breakdown of Gaussian universality on classifier in the presence of non-Gaussian cg.
27

---

Published as a conference paper at ICLR 2025
B EXPERIMENTS ON REAL DATA
In this section, we report experimental results on Fashion-MNIST image data (iaao et al. (017) to show how the conditions of Gaussian universality provided in Corollaries and can be used to understand and predict Gaussian universality phenomena on real data learning problems.
We have discussed two types of universality this paper: universality on in-distribution perfor- mance and universality classifier (see Definition 3 for more details). To discuss these two types of universality, we distinguish, depending on the Gaussianity of informative factors and the use of square loss, the following three scenarios:
1. Scenario I: in the case of non Gan-Gaussi informative factors and when non-square loss is used, neither the universality on in-distribution nor the universality on classifier holds;
2. Scenario 2: in the case of non- Gaussian informative factors and when a square loss is used, the universality on in-distrbuution breaks down while the universality on classifier still holds;
3. Scenario 3: in the case of Gaussian informative factors and when an arbitrary (square or non-square) loss is used, both the universality in-distribution and the universality classifier hold.
To see if these three scenarios derived under LFMM can be "reproduced" on realistic Fashion-MNIST image data, conduct first principle component analysis (PCA) on standardized Fashion-MNIST data to extract the informative factors. To obtain the equivalent GMM in Definition for a mixture of Tashion-MNIST data, we estimate the class mean and the class covariance for each class of -ashion-MNIST, using all available samples in that class.
Here, consider the following cases to illustrate the different effects of Gaussian and non- Gaussian informative factors on ERM classification:
1. Case I: Classes 4&5 of Fashion-MNIST data, as an example of non-Gaussian informative factors; and
2. Case 2: Classes 3&7 of Fashion-MNIST data, for which approximately Gaussian informa- tive factors can be observed.
In TigureAaand Figure 5 we compare, for the aforementioned two cases, the (empirical) distributions of the first two informative factors obtained from PCA. We observe that the informative factors of Classes 4&5 have highly asymmetric distributions, corresponding to a strong deviation from the Gaussianity, while the distribution of informative factors in Classes 7&7 are much closer to the form of normal density function in comparison.
Figures 6 to 10 then provide empirical results on these two cases to demonstrate the universal or non-universal behavior with respect to the in-distribution performance and the ERM classifier, under the three scenarios on informative factors and loss function listed at the beginning of this section.
We discuss first Scenario 1 with non-Gaussian informative factors (Case 1 Classes 4&:) and non- square losses. Under this scenario, the in-distribution performance is predicted, as per Corollary [ to be different from that under the equivalent GMM, as can be observed in the middle and right plots of Figure 7 According to Corollary 3. the universality on classifier does not hold in this case either. In other words, the classifier trained on Fashion-MNIST data and the one trained on data drawn from the equivalent GMM give different performances on the same test Fashion-MNIST data. This is empirically manifested in middle and right plots of Figure ! and suggests an effective learning using non-square losses from high-order moment information beyond the class mean and covariance.
It is interesting to compare Scenario with Scenario 2, where we use square and non-square losses on non-Gaussian informative factors. In Scenario 2, while we still do not have universal in-distribution performance as evidenced in the left column of Figure 7 the classifier trained on equivalent GMM data gives practically the same performance on test Fashion-MNIST data the classifier trained on realistic Fashion-MNNI fails to learn from Fashion-MNIST data beyond the information contained in the equivalent GMM (i.c., the class mean and covariance). Consequently, the square loss yields suboptimal performance as shown in the left plot of Figure
data, as shown in the left plot of Figure D This means that the square loss
28

---

Published as a conference paper at ICLR 2025
2
1,5
1.5
Histogram
0.5
0.5
0.5
(a) First informative factor of Class 4
(b) Second informative factor of Class
3
3
Histogram
Histogram
2
2
1
0
0.5
0.5
(c) informative factor Class
(d) Second informative factor Class 5
Figure 4: Histogram of the first and second information factors of Class 4 and 5, estimated using all samples from the Mushion-MNIST dataset.
In Scenario 3 with (approximately) Gaussian informative factors (Case 2 on Classes 3&7), the two types of Gaussian universality (on in-distribution performance and on classifier) hold for any choice of loss function. The universality on in nn-distribution performance is demonstrated in Figure 8 where we observe a much closer match between the in n--distribution performance on Aishion-MNIST and the equivalent GMM, in comparison with the drastically different in-distribution performances reported in Figure for Case 1 on Classes 4&5 with non-Gaussial informative factors. The universality on classifier that holds for any loss (square or non-square) in this scenario is empirically confirmed by comparing Figure TO with Figure 9 Otherwisc speaking, in this case, Fashion-Mi MNIST data treated by the ERM classifier as if they were Gaussian mixture data. As result, we predict that there little room in trying do better than the square loss (that is identified by Taheri et al. (2021b): Mail & Liao (2019) to be the optimal loss under GMM). This consistent with the empirical performances given by different losses displayed in the right plot of Figure
As a side note, the empirical universal results provided in Figure 2 of (Dandi et al. 2024) also involved Fashion-MNIST data. However as Dandi et al. 2024 trained the classifier synthetic data generated by a conditional GAN learned from the Fashion-MNIST dataset, these experimental results not directly comparable to ours, which were obtained from direct training on Fashion-MNIST data.
29

---

Published as a conference paper at ICLR 2025
2
1.5
1.5
Histogram
1
1
0.5
0.5
0
0
0.5
0.5
(a) First informative factor of Class 3
(b) Second informative factor of Class
2
Histogram
Histogram
2
0
0.6
-0 0.4
0.2
0.5
0.5
(c) informative factor Class
(d) Second informative factor Class 7
Figure 5: Histogram of the first and second information factors of Class 3 and estimated using all samples from the Fashion-MNIST dataset.
Classification Accuracy (%)
0.99
0.99
0.98
Square loss
Square loss
Logistic
Logistic Square hinge loss
Square hinge loss
0.97
0.98
2
2
2
2
2
2
26
A
Figure 6: Classification accuracies as a function of the regularization penalty, for square, logistic, and square hinge loss, on Rashion-MNIST data of sample size 512. Left: Class versus as an example of non-Gaussian information factors showed in Figure 4 Right: Class 3 versus 7, as an example (close-to) Gaussian information factors showed in Figure
30

---

Published as a conference paper at ICLR 2025
Classification Accuracy (%)
1
0.98
0.98
0.98
0.96
Fashion MNIST
0.96
Fashion -NNSS
0.96
Fashion MNNIST Fashion-MNIST
Equivalent GMM
Equivalent GMM
Equivalent GMM
2-9
20
29
2-
2
2
2
2
A
À
Figure 7: In-distribution classification accuracies as function of the regularization penalty 7, for Fashion-MNIST data (Class 4 versus 5, illustrating example of non-Gan non-Gaussian informative factors as shown in Figure 4 and Equivalent GMM of sample size n 512, with square (left), logistic (middle), and square hinge (right) losses.
Classification Accuracy (%)
0.99
Fashion MNIST
Fashion MNIST
Fashion MNIST ENsIS
Equivalent GMM
Equivalent GMM
Equivalent GMM
2-9
2
29
2
2
2
2
2
2
À
Figure 8: In-distribution classification accuracies function of the regularization penalty for Fashion-MNIST data (Class versus 7, as an illustrating example of close-to-Gaussian informative factors shown in Figure 5) and Equivalent GMM of sample size 512, with square (left), logistic (middle), and square hinge (right) losses.
Classification Accuracy (%)
0.99
0.99
0.98
0.98
0.98
0.97
0.97
0.96
Fashion-MNIST
0.96
Fashion-MNIST Equivalent
0.96
Fashion-MNIST
Equivalent
Equivalent
0.95
0.95
2-9
20
29
2
20
2
20
À
A
Figure 9: Classification accuracies on test Fashion-MNIST data as function of the regularization penalty 7, given by classifiers trained on Fashion-MNIST data (Class 4 versus as an illustrating example of non-Gaussian informative factors as shown in Figure 4 and on Equivalent GMM data of sample size n 512, with square (left), logistic (middle), and square hinge (right) losses.
31

---

Published as a conference paper at ICLR 2025
Classification Accuracy (%))
0.99
FasHion-MNIST
Fashion-MNIST
Pashion-MNIST
Equivalent GMM
Equivalent GMM
Equivalent GMM
9
2
29
2
2
2 9
2
2
A
Figure 10: Classification accuracies on MASSST data as function of the regularization penalty 7, given by ERM classifiers trained on Fashion-MNIST data (Class 3 versus 7, as an illustrating example of closetoo-Gaussic informative factors as shown in Figure on Equivalent GMM data of sample size 512, with square (left), logistic (middle), and square hinge (right) losses.
32


Reviews:
[{"review_id": "KnQ1uk8Rn0", "reviewer": "Reviewer_LD77", "summary": "Paper shows that a mixture of linear factors model with non-Gaussian noise doesn't satisfy \"Gaussian universality\" in terms of asymptotic analysis. This is what I'd call a negative result, and the authors argue this is significant because previously researchers have shown that in various cases you can get away with swapping in Gaussians when doing asymptotic analysis using some central limit theorem arguments.", "questions": "The authors declare that they have shown squared error isn't an optimal loss *in this setting* and state that as an important contribution. Why is that surprising though, I mean it's easy to conjure up scenarios where that's true (e.g. Laplacian noise -> L1 loss).  So why should we be surprised if you assume non-Gaussian noise on your features and then tell us squared loss is not optimal?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "Focus: There focus on mixtures of linear factor models is quite reasonable and practical and theoretically satisfying in that they generalize GMMs.\n\nCorrectness: I didn't see any problems in the math and it all smelled clean, but I didn't fine tooth comb. \n\nThis seems like a perfectly nice bit of results that I'd like to see published somewhere someday, but I just can't personally argue that it meets the high bar for ICLR in terms of significance.", "weaknesses": "They have to make a non-Gaussian noise assumption, and then the number of non-Gaussian noise variables goes to infinity whereas the number of informative features $q$ stays fixed. Now CLT says that even in the presence of a lot of non-Gaussian noise one can end up with Gaussians, so some might argue it's still surprising that this failed a CLT like story, but this isn't the usual CLT set-up, so perhaps not so surprising that infinite non-Gaussian noise leads to non-Gaussian-swappable asymptotics.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EMzvjkDikH", "reviewer": "Reviewer_hVpL", "summary": "The paper studies on the issue of 'Gaussian universality' for classification of high dimensional data drawn from a Linear Factor Model (LFMM) that constitutes a GMM generalization. It focuses on LFMM classifiers trained using squared loss and ridge regression. The main theoretical result is that, if LFMMs with non-Gaussian informative factors are used, 'Gaussian universality' breaks down.", "questions": "Q1. See comment W2 above.\n\nQ2. The paper proves a negative theoretical result regarding the squared loss, however a suggestion on the type of loss that could\nbe considered would add value to the paper.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. The paper presents theoretical results related to the Gaussian Universality of classification mixtures for high dimensional data. \n\nS2. It identifies a case namely, LFMMs with non-Gaussian  informative factors trained using squared loss ridge regression, where Gaussian universality breaks.  \n\nS3. Rigorous proofs are provided.", "weaknesses": "W1. Although the paper is well-structured, it is rather difficult to follow due to its theoretical character. \nNevertheless, I think that the main theoretical conclusions could be explained in a more comprehensive way.\n\nW2. The authors should also comment on the importance of the presented results from a practical point of view.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fgWHvkR414", "reviewer": "Reviewer_8nd6", "summary": "Given the relevance of Gaussian or Gaussian mixtures for dataset modeling in theoretical machine learning, a recent line of works investigated under which conditions the Gaussian assumption can be justified in the high-dimensional regime. This line of works resulted in a series of contributions showing that a *Gaussian Universality Principle* can be indeed safely invoked in many cases. To show the limitations of such an assumption, the authors propose a classification task on a linear factor mixture model, in which two clouds in a $p$-dimensional space have to be classified. The clouds are constructed by using a linear factor model each so that the signal (i.e., the cloud mean) is determined by $q<p$ independent directions only. It is then proven that in this setting Gaussian universality might break down, and the statistical properties of the estimators obtained by convex ERM are asymptotically characterized.", "questions": "I list below a series of observations and questions.\n\n- I found a little bit misleading the sentence at lines 139-141: the one dimensional CLT in Eq. (2) is independent of any ERM solution $\\hat{\\boldsymbol\\beta}$.\n- The notation in Eq. (3) is not very transparent with respect to the average over $\\mathbf g$. It would be maybe more clear to just consider $\\mathbb E[f(\\mathbf g^\\top\\boldsymbol\\beta)]$ and then specify that $\\mathbf g\\sim\\mathcal N(\\mathbb E[\\mathbf x|y_{\\mathbf x}=C],\\mathrm{Cov}[\\mathbf x|y_{\\mathbf x}=C])$.\n- In the discussion of the elliptical distribution case, the quantity $a$ is random (this should maybe specified when introduced). It is not clear to me what the authors refer to when commenting about the application of the CGEP to this case: from what I understand *each data point in the dataset* has a different $a$ from a given distribution, so for example in the paper by [Adomaityte et al. (2024)](https://proceedings.neurips.cc/paper_files/paper/2023/hash/88be023075a5a3ff3dc3b5d26623fa22-Abstract-Conference.html) conditioning on the class does not lead to a distribution that satisfies a CGEP, so elliptic distributions can be seen as another example of a simple setup that ``breaks'' Gaussian universality (which is I think the point of the cited paper).\n- From what I understand, the noise terms in Eq. (5) are supposed to be independent: is this correct?\n- The possibility of accessing an explicit form for $\\tilde{\\boldsymbol\\beta}$ in Eq. (16) strongly depends on the fact that ridge regularization has been chosen. Unless I am mistaken, it might be worth clarifying this point.\n- Is the discrepancy appearing in Fig 1 middle due to finite-size effects? In this case, is this numerically verifiable? Also, in the label, I suppose that 'normal' has to follow 'Middle'.\n- Corollary 3 and the following Remark 2 are interesting results, although I was wondering how much they depend on the specific LFMM form of the dataset. Again, in the aforementioned paper by [Adomaityte et al. (2024)](https://proceedings.neurips.cc/paper_files/paper/2023/hash/88be023075a5a3ff3dc3b5d26623fa22-Abstract-Conference.html) a breaking of Gaussian universality is indeed observed also in the classification of two elliptic clouds *with square loss* (see Figure 1 therein). My impression therefore is that the 'robustness' of square loss with respect to GU in Corollary 3 might stem more from the specific model considered in the paper than from some intrinsic property of square loss.\n- In line 535, ```anlaysis``` to be changed in ```analysis```.\n- In the Appendix, at line 870 what does the notation $\\partial_-$ mean? Also, lines 887-888 should be checked. A square bracket is missing at the end of line 1075. At line 1131, $E$ has to be replaced with $\\mathbb E$. I think an expectation has to be added under the square root in the definition of $\\gamma$ at line 1395.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper presents an interesting model, that is completely characterizable in the asymptotic regime, to test and break down Gaussian universality (GU). Amongst the relevant features observed by the authors, the directions in which the signal is absent play no role in the statistics of the preactivations (i.e., the in-distribution performance), and square loss exhibits special robustness with respect to GU. The results in the paper are rigorously proven and the problem is attacked by adopting a leave-one-out strategy. Proofs are given in the Appendix. Finally, I found both the manuscript and the appendix very clear and well-written.", "weaknesses": "The paper claims to be ```the first to characterize the learning performance when the Gaussian universality``` (GU) ```breaks down```. However, in one of the cited papers by [Adomaityte et al. (2024)](https://proceedings.neurips.cc/paper_files/paper/2023/hash/88be023075a5a3ff3dc3b5d26623fa22-Abstract-Conference.html) a similar (in spirit) analysis has been recently performed: the classification problem of two non-Gaussian clouds has been analyzed by using the heuristic replica method, analytically showing that Gaussian universality can indeed break down quite simply: the statistical properties of the estimators are also given therein. Although the type of dataset model adopted is in general different, my impression is that the results are on the same line as the one published in this manuscript: unless I am mistaken, the LFMM includes as special case a subfamily of the setup considered therein. If for example $\\mathbf V=\\mathbf I_p$ and $e_k=a\\eta_k$ with $\\eta_k\\sim\\mathcal N(0,1)$ and $a$ positive random quantity having $\\mathbb E[a^2]<+\\infty$, one recovers the finite-variance model in [Adomaityte et al. (2024)](https://proceedings.neurips.cc/paper_files/paper/2023/hash/88be023075a5a3ff3dc3b5d26623fa22-Abstract-Conference.html) where GU breaking is observed (note however that in this model $\\mathbb E[a^4]=\\mathbb E[e_i^2e_j^2]\\neq \\mathbb E[e_i^2]\\mathbb E[e_j^2]=\\mathbb E[a^2]^2$ in general).\n\nOne might argue that, beyond classification, similar Gaussian universality-breaking results were present in the line of works of [El Karoui et al. (2013)](https://www.pnas.org/doi/10.1073/pnas.1307842110) on regression (see also a different paper by [Adomaityte et al. (2024)](https://arxiv.org/pdf/2309.16476)) although the focus in these works was more on robustness. One weakness of the paper is therefore that it might appear as a complement to the existing contributions in which a lack of GU is observed and characterized in the same asymptotic regime.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "97b5ec9JLR", "reviewer": "Reviewer_66dx", "summary": "This paper studies the Gaussian universality and its breakdown in classification problems in the setting of high-dimensional linear factor mixture models (LFMM). LFMMs is an extension of the Gaussian Mixture Model in the classification problem. The study demonstrates that the Gaussian universality does not hold for LFMM in general. Furthermore, the paper considers the relationship with the squared loss and Gaussian universality, and clarify the importance of selecting an appropriate loss function. The theoretical analysis provides a new perspective on high-dimensional data analysis. Several numerical experiments are conducted to confirm the theoretical findings based on asymptotic theory. More comprehensive numerical experiments and verification using real data are needed.", "questions": "See Strengths and Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Regarding the breakdown of Gaussian universality:\nMany previous studies have investigated data that follow a Gaussian distribution and scenarios in which the Gaussian universality holds. Since these assumptions do not necessarily hold for real data, it is necessary to analyse more general situations. In the paper, the authors reveal the conditions under which the Gaussian universality is violated for LFMMs. The results can provide new insights into high-dimensional data analysis. \n\n- Evaluation of the optimality of the squared loss\nIt is known that the squared loss is the optimal loss function under the Gaussian mixture models. In contrast to that, this paper discusses the possibility that the squared loss is sub-optimal under a more general LFMMs. It suggests that existing works do not necessarily apply in cases where the Gaussian universality breaks down, and presents a new challenge of selecting an appropriate loss function.\n\n- Numerical experiments:\nIn order to verify the theoretical results, several numerical experiments are demonstrated. These experiments examine the behaviour of the classifier when the Gaussian universality is violated. In Figure 2, the performance of the square loss and the square hinge loss is compared, and one can see that the numerical result is consistent with the theoretical results. Similarly, Figure 3 suggests that the squared loss may not be the optimal solution, and this is also consistent with the theoretical results.", "weaknesses": "This paper deals with the important problem of the breakdown of Gaussian universality in the classification problem of high-dimensional LFMMs. The following are some of the concerns that should be considered.\n\n- In some theorems and corollaries, is it possible to evaluate the convergence speed? Although the proof in the supplementary material seems to evaluate the convergence speed, it would be better for the reader to understand the paper more deeply if the speed were explicitly stated in the main text.\n\n- Theoretical claims are supported by some numerical experiments. However, these experiments are only verified using synthetic data. It is unclear how much the real-world data deviates from the Gaussian universality. Additional experiments using real data are needed to strengthen the paper's arguments. In addition, in line 53 of the introduction, the possibility of observing Gaussian universality in real data is mentioned. I think a supplementary explanation is needed to relate this statement to the results of the paper.\n\n- This paper clarifies the conditions under which the Gaussian universality breaks down, but does not discuss the extent of this breakdown in detail. Can the extent of the deviation from the Gaussian universality be evaluated as a statistical bias? If the impact of this bias on learning performance can be quantified, it would be very useful in practical applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)