The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures

Authors: Xiaoyi MAI, Zhenyu Liao
Primary area: learning theory
Keywords: High-dimensional statistics, random matrix theory, Gaussian universality, empirical risk minimization, mixture models, linear factor models

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.

Decision: accept (poster)
Reviewer scores: 3, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1729461392031

thread_type:
official_review

<thread_object>
creator: reviewer_66dx

<content>
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.

strengths:
- Regarding the breakdown of Gaussian universality:
Many 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. 

- Evaluation of the optimality of the squared loss
It 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.

- Numerical experiments:
In 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.

- 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.

- 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.

- 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.

questions:
See Strengths and Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729886644497

thread_type:
official_review

<thread_object>
creator: reviewer_8nd6

<content>
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.

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).

One 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.

questions:
I list below a series of observations and questions.

- 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}$.
- 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])$.
- 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).
- From what I understand, the noise terms in Eq. (5) are supposed to be independent: is this correct?
- 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.
- 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'.
- 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.
- In line 535, ```anlaysis``` to be changed in ```analysis```.
- 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730457634952

thread_type:
official_review

<thread_object>
creator: reviewer_hvpl

<content>
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.

strengths:
S1. The paper presents theoretical results related to the Gaussian Universality of classification mixtures for high dimensional data. 

S2. It identifies a case namely, LFMMs with non-Gaussian  informative factors trained using squared loss ridge regression, where Gaussian universality breaks.  

S3. Rigorous proofs are provided.

weaknesses:
W1. Although the paper is well-structured, it is rather difficult to follow due to its theoretical character. 
Nevertheless, I think that the main theoretical conclusions could be explained in a more comprehensive way.

W2. The authors should also comment on the importance of the presented results from a practical point of view.

questions:
Q1. See comment W2 above.

Q2. The paper proves a negative theoretical result regarding the squared loss, however a suggestion on the type of loss that could
be considered would add value to the paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730745264330

thread_type:
official_review

<thread_object>
creator: reviewer_ld77

<content>
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.

strengths:
Focus: There focus on mixtures of linear factor models is quite reasonable and practical and theoretically satisfying in that they generalize GMMs.

Correctness: I didn't see any problems in the math and it all smelled clean, but I didn't fine tooth comb. 

This 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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732087552439

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General reply to Reviewers

comment:
We thank all Reviewers for their time and effort. 
After reading your feedback, we would like to address here a common concern on the  **significance** of this work. 
In our view, the present contribution constitutes a meaningful addition to the long list of high-dimensional asymptotic analyses of ML methods in the literature, in that  
- it characterizes the **exact classification performance** on mixture data drawn from **linear factor models**, which, despite being a basic probabilistic framework in statistical inference and generative models, have **not** yet been studied before under the high-dimensional asymptotic regime;
- it reveals a system of equations controlling the classification performance that is **different** from those obtained under Gaussian mixture models (GMMs), therefore **unattainable** through arguments of Gaussian universality (that have been exploited in many previous efforts on high-dimensional asymptotic analyses of ML methods);
- by deriving conditions under which the system of equations is reduced to the one that holds for GMMs, it allows deeper insights into when Gaussian universality can be expected to hold in classification of mixture data beyond the conditional one-directional CLT recently discovered by Dandi et al. (2024).
  
Other questions and concerns are addressed in individual responses to the reviewers.

The modifications made in the revised version are marked in red.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733100041324

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Message to Reviewers

comment:
Dear Reviewers,

Thanks again to you all for your replies and the unanimous acknowledgment of the quality and interest of our results. The only remaining concern appears to be the significance level of the present work, which, in our understanding, should be largely based on its positioning w.r.t. the literature. 
On that point, we would like to thank Reviewer 8nd6 for the insightful questions that help us to better position our work, and Reviewer 66dx for the suggestion to illustrate the practical interest of our theoretical results on real data. With the discussion period approaching the end (on **December 2nd**), we would like to make a summary of the main points that we believe to be important to the assessment of the significance of this work.

**Significance of precise analyses under non-Gaussian data models**

As mentioned by Reviewer 8nd6, some previous publications in prestigious venues such as [Adomaityte et al. (2024)]( https://proceedings.neurips.cc/paper_files/paper/2023/hash/88be023075a5a3ff3dc3b5d26623fa22-Abstract-Conference.html), [El Karoui et al. (2013)](https://www.pnas.org/doi/pdf/10.1073/pnas.1307842110) focused on precise performance analyses under elliptical data models without specially mentioning Gaussian universality. 
Indeed, the main contribution of the very recent publication [Adomaityte et al. (2024)]( https://proceedings.neurips.cc/paper_files/paper/2023/hash/88be023075a5a3ff3dc3b5d26623fa22-Abstract-Conference.html) is a precise understanding of classification on high-dimensional mixtures of elliptical data. It goes without saying that other important data models in statistical learning besides elliptical models deserve the same attention from the research community. The significance of our contribution is justified from that angle alone: it is the fist to characterize the exact classification performance on high-dimensional mixture data drawn from **linear factor models** -- a fundamental probabilistic framework **not less important than elliptical models**, see [(Goodfellow et al., 2016, Chapter 13))](https://www.deeplearningbook.org).

**Significance of understanding the impact of non-Gaussian data beyond the data vector norms**

As pointed out by Reviewer 8nd6, the previous works [Adomaityte et al. (2024)](https://proceedings.neurips.cc/paper_files/paper/2023/hash/88be023075a5a3ff3dc3b5d26623fa22-Abstract-Conference.html), [Adomaityte et al. (2024)](https://arxiv.org/pdf/2309.16476), and [El Karoui et al. (2013)](https://www.pnas.org/doi/pdf/10.1073/pnas.1307842110) also shed light on the impact of non-Gaussian data. However, as the elliptical data vector $\mathbf{x}=a\mathbf{u}$ considered in these works is a Gaussian vector $\mathbf{u}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_p/p)$ rescaled by a random factor $a$, these analyses *do not* provide further information besides the impact of the data vector norms controlled by the scaling factor $a$. For instance, they do not apply to the classical case of i.i.d. non-Gaussian features, which in fact corresponds to a linear factor model with identity covariance.

**Significance of verifiable conditions of Gaussian universality**

Many newest results on Gaussian universality (GU) focused on the pointwise normality conditions (see a list of major contributions in Section 2). While revealing a key element of GU, these conditions are difficult to check, as they require knowledge on the statistical behavior of the ERM solution, which is in general *inaccessible* without precise analysis. In other words, given a data distribution and a loss function, the pointwise normality conditions cannot be used to predict GU, except in some special cases like the manufactured counterexample of [Montanari & Saeed (2022)](https://arxiv.org/pdf/2202.08832) mentioned by Reviewer 8nd6. 
While this counterexample showed the breakdown of GU on Rademacher data for a **particularly designed** loss function, there was *no* theoretical conclusion on whether GU can hold for other losses. In fact, for several popular losses, empirical observations of universal performances on Rademacher data were reported in Figure 1&2 of [Taheri et al. (2021)](https://www.mdpi.com/1099-4300/23/2/178). 

In contrast, our conditions of GU *are easy to verify* by simply answering whether the informative factors are exclusively Gaussian and whether the square loss is used. As evidenced by our experiments on real data in Appendix B of the revised manuscript, we can predict, from the yes-or-no answers to these questions, the universal or non-universal behavior on Fashion-MNIST image data w.r.t. the in-distribution performance and the classifier without running the ERM algorithm or conducting the precise analysis.

We hope that this summary is concise and informative. If you find these points on significance satisfying, we kindly ask that you increase your score. If you have any further question or\and comment, we will be more than happy to address them.

Best,

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
(a) The paper, "The Breakdown of Gaussian Universality in Classification of High-dimensional Mixtures," investigates the limitations of Gaussian universality (GU) in high-dimensional classification tasks. The authors provide a precise asymptotic characterization of empirical risk minimization (ERM) under linear factor mixture models (LFMM), a generalization of Gaussian mixture models (GMMs). They show that the Gaussian universality principle breaks down in this setting, with learning performance depending on higher-order moments of the data distribution. Additionally, the paper derives conditions under which GU holds and discusses implications for choosing loss functions.

(b) **Strengths:**
   - Rigorous mathematical analysis using leave-one-out techniques.
   - Precise characterization of performance in a high-dimensional regime, advancing the understanding of GU limitations.
   - Novel insights into when GU can be expected to hold or break under LFMM.
   - Contributions to the understanding of the interplay between data distribution and loss function design.

(c) **Weaknesses:**
   - The paper's scope may seem incremental compared to existing studies, such as those analyzing elliptical data models.
   - The practical implications of the theoretical results could be more clearly emphasized, particularly in real-world scenarios.
   - Some results, such as the non-optimality of the squared loss under certain conditions, are not unexpected and could benefit from further elaboration.

(d) **Reasons for acceptance:**
   The paper offers significant theoretical contributions to the understanding of GU in high-dimensional settings, a critical area in modern machine learning. Its rigorous methodology and clear exposition provide a valuable resource for further research. The authors' identification of GU conditions and their implications enrich the literature. While some reviewers expressed concerns about the work's significance, the combination of novelty, soundness, and relevance to the ICLR audience justifies acceptance.

---