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

We thank the reviewer for his/her detailed read of the paper and insightful comments that help us improve this paper.

Convergence speed:

As pointed out by the reviewer, it can be derived from our proof in Appendix that the differences in expectation provided in Theorem 1 (and thus the generalization and training performances per Corollary 1) converge at a speed of at least $O(p^{-1/4})$. Nonetheless, we believe that this rate is largely sub-optimal. As many high-dimensional asymptotic analyses of ML methods (cited in the introduction of the manuscript), the primary focus of this paper is to derive the system of equations that determines the asymptotic performance under LFMM as $n,p \to \infty$ together, we did not make the effort to obtain the optimal convergence speed. That is why we chose not to explicitly state our convergence speed in the main text, as it is likely to be overly pessimistic. Instead, we provided empirical validation of our asymptotic results by showing a close match in practice for $n,p$ only in a few hundreds.

Real data experiments:

We agree that it would be interesting to test to what extent our conclusions on the Gaussian universality breakdown apply in real data learning scenarios. We are running additional experiments on real-world datasets, particularly to highlight:

• the impact of non-Gaussian informative factors on the Gaussian universality breakdown, as suggested in our Corollary 2; and
• the robustness of square loss to the Gaussian universality breakdown, as discussed in our Remark 2. We will post these numerical results as soon as they are ready.

As for the inquiry of the reviewer about the empirical results mentioned in Line 53 of the submission, Sur & Candès, (2019); Taheri et al. (2021b) only tested the Gaussian universality on synthetic data in a regression setting, which is not directly related to the classification problem of mixture data under study in our paper. Loureiro et al. (2021) used a random feature mapping on MNIST and fashion-MNIST data to induce the conditional one-directional CLT in (3), so as to observe Gaussian universality on these image data. We believe that the random feature mapping kind of destroyed the structure of non-Gaussian informative factors which might be present in the original data vectors. It is indeed interesting to discuss these empirical results with respect to ours (we will add this discussion along with the experiments on real data).

Deviation from Gaussian universality:

A benefit of our exact performance characterization under LFMM provided in Theorem 1 and Corollary 1 is that it can be used to assess quantitatively the deviation from Gaussian universality. In particular, it can be shown from our Theorem 1 that under GMM, the "high-dimensional equivalent $\tilde{\boldsymbol{\beta}}$" of the ERM solution $\hat{\boldsymbol{\beta}}$ is aligned in expectation with $(\lambda\mathbf{I}+\theta\boldsymbol{\Sigma})^{-1}\boldsymbol{\mu}$. In contrast, under LFMM, $\mathbb{E}[\tilde{\boldsymbol{\beta}}]$ lies in the direction of $(\lambda\mathbf{I}+\theta\boldsymbol{\Sigma})^{-1} (\boldsymbol{\mu}+ \sum_{k=1}^q \omega_{k} \mathbf{v}_k)$, where $\omega_1,\ldots,\omega_q\neq 0$ for non-Gaussian informative factors $z_1,\ldots, z_q$, causing $\mathbb{E}[\tilde{\boldsymbol{\beta}}]$ to be more or less aligned with the directions $\mathbf{v}_1,\ldots, \mathbf{v}_q$ controlled by the non-Gaussian informative factors.

However the value of $\omega_k$ can not be assessed without knowing the distributions of the non-Gaussian informative factor $z_k$. Therefore before applying our results to assess the deviation from Gaussian universality, it requires a pre-processing step to estimate the LFMM from the data set.

We would not call the deviation from Gaussian universality as statistical bias, as it reflects the adaptation of the ERM classifier to non-Gaussian informative factors, which is most likely to be beneficial to the classification performance.

We thank the reviewer for the careful reading of our paper and the helpful suggestions.

With respect to other non-universality results

We are aware of the existence of other forms of Gaussian universality breakdown, such as the one induced by elliptically distributed data characterized in the work of Adomaityte et al. (2024). In our opinion, the non-universality result in Adomaityte et al. (2024) is fundamentally different from ours for several reasons stated below.

• Due to the existence of the scaling variable $a$ in elliptically distributed data $\mathbf{x}_i$, it is easy to see that the conditional one-directional CLT in (3) cannot hold (unless one considers the expectation conditioned on both the label $y$ and the scaling variable $a$), consequently the Gaussian universality is bound to break down. In contrast, it is not clear whether the conditional one-directional CLT in (3) holds for the linear factor mixture model (LFMM) under study unless a precise performance analysis is performed.
• Contrarily to the constant breakdown of Gaussian universality under the elliptically distributed data setting in Adomaityte et al. (2024), our analysis revealed that the Gaussian universality can sometimes hold under LFMM. By identifying conditions of Gaussian universality under LFMM, our analysis allows a deeper understanding on the applicability of Gaussian universality and the causes of its breakdown.
• Another major difference between LFMM and the elliptical data setting considered in Adomaityte et al. (2024) lies in the fact that the concentration of quadratic forms of $\mathbf{x}_i$ in (1) does not hold for elliptical data, as opposed to LFMM. This is also the cause behind their different behaviors regarding the robustness of square loss with respect to Gaussian universality pointed out by the reviewer. As we know, the ERM solution given by the square loss is a weighted mean of the training data vectors $\mathbf{x}_i$ multiplied by the inverse of the sample covariance matrix (SCM) of $\mathbf{x}_i$. As the scaling variable $a$ breaks the concentration of quadratic forms of $\mathbf{x}_i$ in (1), the universality of the SCM collapses (which was briefly discussed in Lines 161-164 of the submission; in fact, the covariance considered in Adomaityte et al. (2024) can be unbounded), and so does the universality of ERM with square loss.

To avoid ambiguity regarding the positioning of the present work with respect to other non-universality results, we have removed the expression in question "the first to characterize the learning performance when the Gaussian universality breaks down" in the concluding remarks of the manuscript and modified the section accordingly.
We have also added a phrase in Line 172 of the revision to comment on the non-universal behavior of elliptically distributed data induced by the scaling variable $a$.

Further comparison to the work of Adomaityte et al. (2024)

• This is no overlap between our LFMM and the elliptically distributed data setting considered in Adomaityte et al. (2024) for classification and in Adomaityte et al. (2024) for regression. As explained earlier, the scaling variable $a$ breaks the concentration of the norm of elliptically distributed $x_i$. On the other hand, it is easy to check that under our LFMM, the norm of $x_i$ always concentrates as a consequence of the statistical independence of noises $e_1,\ldots,e_p$ by the law of large numbers.
• From a technical perspective, our analysis also differs from Adomaityte et al. (2024). Precisely, Adomaityte et al. (2024) used the replica heuristic to find the asymptotic equations on the learning performance, whereas our results are proven through a series of concentration results derived with the help of leave-one-out manipulation.

Thanks to the reviewer for the feedback.

While we cannot argue with the reviewer on the "general relevance" of this work as it is reserved to personal judgement, we would like to point out that precise and general characterizing results are particularly hard to obtain in the high-dimensional asymptotic regime, to our knowledge such results are scarce (if not absent) in the literature. We would appreciate it if the reviewer could provide some references that contain characterizing results deemed to be precise and general by the reviewer.

The reviewer seems to concur that this paper provides a novel analysis in the high-dimensional asymptotic regime. In our opinion, this fact alone (combined with the popularity of linear factor models) already qualifies this work as a significant contribution in the field of high-dimensional asymptotic analysis (which we argue to be an important field but still unfamiliar to many of the audience and reviewers of ICLR). We kindly refer the reviewer to General Reply to all Reviewers for further comments on the significance of this work.

We respectfully do not agree that this work provides little further insight into the breakdown of Gaussian universality beyond existing results. At the risk of repeating ourselves, we would like to point out the point-wise normality condition is not directly verifiable from the data distribution. Therefore, it provides limited insight into whether the Gaussian universality holds under a given data model. As the reviewer might also notice, the counterexample provided in Montanari & Saeed (2022) is 'manufactured' with a particular loss function to induce the breakdown of Gaussian universality on Radermacher data $\mathbf{x}={\rm Unif}\\{-1,1\\}$. This counterexample clearly does not mean that the Gaussian universality cannot hold on $\mathbf{x}={\rm Unif} \\{-1,1\\}$ for a different loss function (see for instance Figure 2 in Taheri et al. (2021) for universality results on Radermacher data). In our view, the existence of such designed counterexamples in the literature attest to the interest in the research community to understand better when the Gaussian universality holds and when it fails, which supports the value of the present work, rather than undermines it.

We thank the reviewer for acknowledging that the present work is "a nice contribution" of adequate "novelty", and for providing concrete comments that help us better understand the standpoint of the reviewer.

Thanks also for the confirmation that "general and precise" results are out of reach in the current literature. We would like to emphasize that it is not our intention to claim that our analysis provides a major breakthrough that puts it on a different level from other important contributions in the field (such as the ones mentioned by the reviewer). The point that we are trying to make is simply that it contains sufficiently novel and interesting results to be a worthy publication with respect to previous related works.

As mentioned by the reviewer, high-dimensional asymptotic analyses for elliptical data, such as Adomaityte et al. (2023), Adomaityte et al. (2024), and El Karoui et al. (2013), are important contributions in the field even without considering their implication on Gaussian universality. In our opinion, this is also the case for our work: the novelty of the analysis and the importance of linear factors models under study already provide strong arguments on the significance of this paper.

We would like to stress again that the purpose of our results is not to disprove Gaussian universality or to show to which point "Gaussian universality results can be fragile", but to better understand when this important phenomenon can be expected to hold, which is a crucial question only partially answered by existing results such as the point-wise normality condition and the manufactured counterexample in Montanari & Saeed (2022). As correctly understood by the reviewer, studying Gaussian universality under LFMM has the particular interest of revealing conditions of Gaussian universality breakdown. Note also that these conditions are easy to verify from the (Gaussian or non-Gaussian) distributions of informative factors and the type (square or non-square) of loss function used in ERM. See the numerical results in Section 5 and Appendix B on synthetic and real data, where we can predict the GU behavior before running the ERM. Another important point we would like to highlight (again) is that linear factor models are among the most basic probabilistic models (Goodfellow et al., 2016, Chapter 13)). They are, in our view, not less important than elliptical data models, and are by no means particular data models intentionally designed by the authors to induce the Gaussian universality breakdown.

As briefly explained in our first reply to the reviewer, elliptical data vectors $\mathbf{x}=a\mathbf{u}$ with random scalar $a$ and Gaussian vector $\mathbf{u}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_p/p)$ considered in Adomaityte et al. (2023), Adomaityte et al. (2024), and El Karoui et al. (2013) are not of concentrated norm. To see this, notice first that $\Vert\mathbf{u}\Vert^2=1+o(1)$ at large dimension $p$ by the law of large numbers. Consequently $\Vert\mathbf{x}\Vert^2=a^2\Vert\mathbf{u}\Vert^2=a^2+o(1)$, which obviously does not concentrate around a constant as long as $a$ is not constant. Therefore the finiteness of the moments of $a$ does not guarantee a concentrated norm of $\mathbf{x}$. Another major difference (not mentioned in the first reply) between elliptical data vectors $\mathbf{x}=a\mathbf{u}$ considered in these works and our LFMM is that even though $\mathbf{x}=a\mathbf{u}$ is clearly non-Gaussian, it follows a conditional Gaussian distribution (as the distribution of $\mathbf{x}$ conditioned on $a$ is a multivariate normal distribution), which is not the case under our LFMM.

Finally we still do not see the problem with the first point of our contributions quoted by the reviewer. To us, the fact that this analysis focuses on "classification of data drawn from a linear factor mixture model" is clearly stated. And in no part of this description did we ever attempt to exclude the existence of other non-universal results in the literature. In fact, all the references mentioned by the reviewer had been cited and discussed in our submission. We also adapted remarks on these works in the revised version after exchanging with the reviewer. We would be grateful if the reviewer could provide any further suggestion or question on our discussion of related works.

We thank the reviewer for the valuable comments.

We would like to clarify that our analysis is not limited to the square loss, but instead applies to a family of smooth convex losses (see Assumption 1 for more details).

Comment on practical relevance

The research line of high-dimensional asymptotic analyses of ML methods such as ours is gaining interest and gives rise to a rapidly growing volume of publications (see for instance the numerous references cited in the introduction of the manuscript). It is driven by the need for a better understanding of modern large-scale ML with comparably large feature dimension $p$ and sample size $n$, where the practical reality often contradicts the classical learning theory according to which overfitted large learning models like deep neural networks should generalize poorly on newly observed data instances. As high-dimensional asymptotic analyses give the exact generalization performance at any finite sample ratios $n/p$, they allow a deep understanding of the learning mechanism and provide practical guidance in the modern big data regime.

Due to the technical challenge of characterizing the exact performance at finite $n/p$, most analyses in the literature considered Gaussian features or/and used arguments of Gaussian universality. The practical insights provided in these works rely on how much the Gaussian setting is able to describe the practical reality. In comparison, our work

• sheds light into the interplay between the learning model and the data statistics beyond the first and second moments, through a precise performance analysis beyond the realm of Gaussian universality; and
• provides guidance on when real data can be expected to behave as Gaussian data, based on the identified conditions of Gaussian universality under LFMM; and
• lays foundation for future works on the optimal loss design better adapted to non-Gaussian features.

Comment on optimal loss

High-dimensional asymptotic analyses typically give an implicit characterization of the generalization performance through a system of equations, making it challenging to find the optimal loss (that potentially depends not only on the data distribution but also on the sample ratio $n/p$). For that reason, investigations on the optimal loss in the high-dimensional asymptotic regime often give rise to independent publications, for instance [1, 2]. While our precise high-dimensional analysis can be used to design optimal loss adapted to non-Gaussian features under LFMM, such results are of independent interest and beyond the focus of this paper, which, in our opinion, already contains sufficient novel results.

[1] Bean, D., Bickel, P.J., El Karoui, N. and Yu, B., 2013. Optimal M-estimation in high-dimensional regression. Proceedings of the National Academy of Sciences, 110(36), pp.14563-14568.

[2] Taheri, H., Pedarsani, R. and Thrampoulidis, C., 2021. Sharp guarantees and optimal performance for inference in binary and Gaussian-mixture models. Entropy, 23(2), p.178.

I thank the authors for their detailed reply to all reviewers. The paper contains interesting results, however I am not confident that the importance as well as the relevance of those results justify an ICLR publication.

We thank the reviewer for the valuable comments.

Significance of this work

We would like to stress that the main objective of this paper is not to provide a negative result to disprove the Gaussian universality principle, but rather to provide a precise performance analysis of classification under linear factor mixture models (LFMM, which, to quote the reviewer, is a quite reasonable and practical and theoretically satisfying data setting), and then to identify conditions of Gaussian universality breakdown under LFMM, which shed light on the limitation of the extensively exploited Gaussian universality.

Please see the general reply to all reviewers above for more detailed comments on these points.

Comment on the sub-optimality of square loss

We did not intend to point out the sub-optimality of square loss as ''an important contribution'' of this work, but as an argument on the interest of our LFMM data setting, compared to the commonly considered GMM setting, in capturing key aspects of learning behavior, such as the impact of loss function.

In the modern high-dimensional regime where the sample size $n$ and the feature dimension $p$ are both large (as considered in this paper, which we argue to be more practical for modern large-scale ML, see the first paragraph of introduction for references), it is known that the maximum likelihood estimator can be sub-optimal and the choice of optimal loss is much less clear. See for instance Figure 1 of [1], where the optimal loss is shown to be different from the $L_1$ loss in the Laplacian case at finite $n/p$, as opposed to the classical result of maximum likelihood theory mentioned by the reviewer.
In fact, the classical maximum likelihood theory often fails in the large $n,p$ regime, as evidenced by the findings of [2]. Another example is given in Section 3.2 of [3], where it was shown that in this high-dimensional regime, the optimal loss is not the square loss, even when the features are Gaussian distributed (e.g., for logistic and probit models).

Even though precise performance analyses such as ours allow access to the generalization performance as a function of the loss function and the sample ratio $n/p$, the asymptotic generalization performance is usually expressed in an implicit form involving a system of equations. Optimizing the generalization performance over the choice of loss function is hence a non-trivial task, often warranting separate investigations such as [1, 3]. One contribution of our analysis is laying the ground for future works on the search for optimal loss under LFMM.

[1] Bean, D., Bickel, P.J., El Karoui, N. and Yu, B., 2013. Optimal M-estimation in high-dimensional regression. Proceedings of the National Academy of Sciences, 110(36), pp.14563-14568.

[2] Sur, P. and Candès, E.J., 2019. A modern maximum-likelihood theory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences, 116(29), pp.14516-14525.

[3] Taheri, H., Pedarsani, R. and Thrampoulidis, C., 2021. Sharp guarantees and optimal performance for inference in binary and Gaussian-mixture models. Entropy, 23(2), p.178.

We would like to thank the reviewers for recognizing the quality of our reply (even though not yet reflected in the scores). To test the practical applicability of our results on real data (as per the suggestion of Reviewer 66dx), we added, in Appendix B of the (newest) revised manuscript, additional experiments on Fashion-MNIST image data, where we showed how our universality conditions on the (Gaussian or non-Gaussian) distributions of informative factors and the type (square or non-square) of loss stated in Corollaries 2 and 3 can be used to predict Gaussian universality phenomena (or their breakdown) with respect to the in-distribution performance and the ERM classifier (see Definition 3 for more details on these two types of Gaussian universality).

I would like to thank the authors for the summary. As a side note that came to my mind by reading it, the authors might consider stressing the originality of the contribution regarding linear factor models with respect to previous papers dealing with the breaking of GU in the classification of mixtures, by referring to LFMM in the title, e.g., "The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures" or something similar.

Dear Reviewer LD77,

It is our understanding that review ratings should be based on concrete arguments. We looked again in your replies and failed to identify one, other than the repeated generic comment about not meeting the “bar” for ICLR. Good arguments to support such criticisms could be, for instance, lack of originality or interest w.r.t. the previous works. Our message above addresses precisely these points. If you have further question or comment, please let us know before the discussion deadline.

It is also our belief that your rating should reflect faithfully your current stand on the paper. If you are just uncertain about this paper as you said in your last reply, we kindly ask you to at least increase your score to borderline and to drop your confidence level.