Learning Gaussian Mixtures with Generalized Linear Models: Precise Asymptotics in High-dimensions
Authors: Bruno Loureiro
Gabriele Sicuro
Cedric Gerbelot
Alessandro Pacco
Florent Krzakala
Lenka Zdeborova
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Statistical Physics
Replica method
High-dimensional statistics
Approximate Message Passing
Gaussian Mixture Models

Abstract: Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. In this manuscript, we characterise the learning of a mixture of $K$ Gaussians with generic means and covariances via empirical risk minimisation (ERM) with any convex loss and regularisation. In particular, we prove exact asymptotics characterising the ERM estimator in high-dimensions, extending several previous results about Gaussian mixture classification in the literature. We exemplify our result in two tasks of interest in statistical learning: a) classification for a mixture with sparse means, where we study the efficiency of $\ell_1$ penalty with respect to $\ell_2$; b) max-margin multi-class classification, where we characterise the phase transition on the existence of the multi-class logistic maximum likelihood estimator for $K>2$. Finally, we discuss how our theory can be applied beyond the scope of synthetic data, showing that in different cases Gaussian mixtures capture closely the learning curve of classification tasks in real data sets.

Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions
Bruno Loureiro
Gabriele Sicuro Department of Mathematics King's College London
IdePHICS, EPFL, Lausanne
Cédric Gerbelot
Alessandro Pacco
Laboratoire de Physique de l'École Normale Supéricure
IdePHICS, EPFL, Lausanne
Florent Krzakala IdePHICS, EPFL, Lausanne
Lenka Zdeborová SPOC, EPFL, Lausanne
Abstract
Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. In this manuscript, characterise the learning of mixture of K Gaussians with generic means and covariances via empirical risk minimisation (ERM) with any convex loss and regularisation. In particular, we prove exact asymptotics characterising the ERM estimator in high-dimensions, extending several previous results about Gaussian mixture classification in the literature. We exemplify interest in statistical learning: a) classification for a mixture with sparse means, where we study the efficiency of penalty with respect to &g; max-margin multi- class classification, where we characterise the phase transition on the existence of the multi-class logistic maximum likelihood estimator for K 2. Finally, we discuss how our theory can be applied beyond the scope of synthetic data, showing that in different cases Gaussian mixtures capture closely the learning curve classification tasks in real data sets.
result in two tasks of
Introduction
recurring observation in modern deep learning practice is that neural networks often defy the standard wisdom classical statistical theory. For instance, deep neural networks typically achieve good generalisation performances a regime in which it interpolates the data, fact odds with the intuitive bias-variance trade-off picture stemming from classical theory [1-3]. Surprisingly, many of the "exotic" behaviours encountered in deep neural networks have recently been shown to be shared by models as simple as overparametrised linear classifiers [4, 5], e.g., the aforementioned benign over-fitting [6]. Therefore, understanding the generalisation properties of simple models in nigh-dimensions has proven to be fertile ground for elucidating some of the challenging statistical questions posed by modern machine learning practice [7-16].
In this manuscript, we pursue this enterprise in the context of a commonly used model for high- dimensional classification problems: the Gaussian mixture. Indeed, it has been recently argued that the features learned by deep neural networks trained on the cross-entropy loss "collapse" in a mixture of well-separated clusters, with the last layer acting simple linear classifier [17]. Another observation put forward in [18] is that data obtained using generative adversarial networks behave Gaussian mixtures. Here, derive exact asymptotic formula characterising the performance
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of generalised linear classifiers trained on K Gaussian clusters with generic covariances and means. Our formula is valid for any convex loss and penalty, encompassing popular tasks in the machine learning literature such ridge regression, basis pursuit, cross-entropy minimisation and max- max-margin estimation. This allow us to answer relevant questions for statistical learning, such as: what the separability threshold for K-clustered data? How does regularisation affects estimation? Can different penalties help when the means are sparse? We also extend the observation of [18] showing that the learning curves of binary classification tasks on real data are indeed well captured by our asymptotic analysis.
Model definition We consider learning from d' d-dimensional mixture of K Gaussian clusters CLE(K]. The data set is obtained by sampling n pairs (x", )'Eeein) R K identically and indepen- dently. We adopt the one-hot encoded representation of the labels, i.e., if x" E Cz. then y" ex. kth basis vector of R We will denote the matrix of concatenated samples X E Rddx. The mixture density then reads:
K
P y)
Σ yePWN (æ |eA, Ex),
(1)
where Mi pr, Σ) the multivariate normal distribution with mean μ and covariance matrix Σ.
The matrix of concatenated means is denoted M E Ra In Eq. (1), Vk: Pk P(y = ex) 2 Mg E Id and Σn Rdxd is positive-defintte We will consider the estimator obtained by minimising the following empirical risk:
Wa y" vd
R(W, b) = Σ l
+b) + +rr(W),
v=1
(W*, b*) = argmin R(W,b)
(3)
WERKxd BERK
where W E gx and E RK are the weights and bias to be learned, is a convex loss function,
and is a regularisation function whose strength is tuned by the parameter À > 0. For example the loss function can represent the composition of a cross-entropy loss with a softmax thresholding on the linear part of Eq. (2). We will characterise the distribution of the estimator (W*, [W",""), and we will evaluate the average training loss defined as
W*x
b))
El
l
3
+
(4)
Vd
as well as the average training error et and generalisation error Eg. defined as the misclassification rates:
= - DI 3" + v W' + by) ).
[1
[ new +
W nnw
Eg =g==Banww (nnew gyuw
Vd + bbb)
where (x:uew neww) ) is a new unseen data point sampled from the distribution in Eq. (I). In the previous equations, we have used the function ÿ: R + RK that ()((=) == I[maxx 3x 2x).
The main contributions in this manuscript are the following:
(C1) In Sec. and Appendix A we prove closed-form equations characterizing the asymptotic distribution of the matrix of weights W E kxd enabling the exact computation of key quantities such as the training and generalisation error. Our proof method solves shortconings of previous approaches by introducing a novel approximate message-passing sequence, building on recent advances in this framework, that is of independent interest.
(C2) In Sec. 3.1 we study the problem of classifying an anisotropic mixture with sparse means, where the strong or weak directions in the data are correlated with the non-zero components of the mean as in [19]. We study how learning the sparsity with an l penalty improves the classification performance.
(C3) In Sec. 3.2 we study the performance of the cross-entropy estimator in the limit of vanishing regularisation À + 0* for K Gaussian clusters as function of the sample complexity a n/d; we show that a phase transition takes place at a certain value a between a regime of complete separability of the data and a regime in which the correct classification of almost all points in the data set is not possible. We also investigate the effect of À > O regularisation on the generalisation error, comparing the K > 2 case with the results given in the literature for K = 2 [14, 20].

---

(C4) In Sec. 3.3 we investigate the applicabilitty of our formula beyond the Gaussian assumption by applying to classification tasks on real data. We show that for different tasks and losses, it closely captures the real learning curves, even when data is mapped through a non-linear feature map. This further shows that Gaussian mixtures are a good surrogate model for investigating real classification tasks, as put forward in [18].
Relation to previous work The analysis of Gaussian mixture models in the high- sigh-dimensional regime has been the subject of many recent works. Exact asymptotics has been derived for the binary classification case with diagonal covariances in [21-23] for the logistic loss and in [24, 25] for the square loss, both with l2 penalty. A similar analysis has been performed in [26] for the hard-margin SVM. These works were generalised to generic convex losses and &2 penalty in [14], where it has been also shown that the regularisation term can play an important role in reaching Bayes-optimal performances. Hinge regression with & penalty and diagonal covariance was treated in [13]. Recently, these asymptotic results were generalised to the case in which both clusters share the same covariance in [27]. and finite rate bounds were given in [28, 29] in the case of sub-Gaussian mixtures. Asymptotic results for the multiclass problem with diagonal covariance were derived in [20] for the restricted case of the square loss with E2 penalty. Our result unifies all the aforementioned asymptotic formulas, and extends them to the general case of a multiclass problem with generic covariances and arbitrary convex losses and penalties.
From a technical standpoint, in [13, 14, 20, 21, 25, 27, 30] the authors use convex Gaussian compari- son inequalities, see e.g. [31, 32], to prove their result. In particular, the proof given [20] for the multiclass problem harnesses the geometry of least-squares, and it is then stressed that this method breaks down for multiclass problems in which the risk does not factorise over the K clusters (as for the cross-entropy, for example). We solve this problem using an innovative proof technique which has an interest in its own. Our approach is to capture the effect of non-linearity and generic covariances via the rigorous study of an approximate message-passing (AMP) sequence, a family of iterations that admit closed- form asymptoties at each step called state evolution equations [33]. Our proof relies on several refinements of AMP methods to handle the full complexity of the problem, notably spatial coupling with matrix valued variables [34-36] and non-separeble update functions [37], via a multi-layer approach to AMP [38].
The sparse Gaussian mixture model analysed in Section 3.1 is closely related to the rare/weak features model introduced in [19] and widely studied in the context of sparse linear discriminant analysis [39-42]. It was recently revisited in [28, 29] in the context of ERM with max-margin classifiers. Here, we consider correlated variation of the model and study the benefit of using sparsity inducing L penalty.
The separability transition is a classical topic [43, 44] that has recently witnessed a renewal of interest thanks to its connection to overparametrization. It was studied in [16] in the context of uncorrelated Gaussian data, in [8] in the random features model and in [14, 21] for binary Gaussian mixtures.
Recently, [12, 45, 46] showed that the performance of different regression tasks on real data are well-captured by teacher-student Gaussian model in high-dimensions for ridge regression, but this turned not to be true for non-linear problems such as logistic classification [12]. Authors of [18) showed instead that data from generative adversarial networks behave like Gaussian mixtures, motivating the modeling of such mixture for real-data in the present paper.
2 Technical results
Our main technical result is an exact asymptotic characterization of the distribution of the esti- mator W'. Informally, the estimator W and the quantity W W /vd behave asymptotically as non-linear transforms of multivariate Gaussian distributions. These transforms are directly linked to the proximal operators [47, 48] associated to the loss and regularisation functions, summarizing the effect of the cost function landscape on the estimator. The parameters of these Gaussian distributions and proximals can then be computed from the fixed point of a self-contained set of equations. We start by presenting the most generic form of our result in a concentration of measure- like statement in Theorem 1, and discuss an intuitive interpretation of the different quantities involved. Theorem 2 then states how the training and generalisation errors can be computed. All results presented in the experiments section can be obtained from Theorem 1. In Corollary 3 we discuss particular case where explicit simplifications can be obtained. But first, let's summarise the required assumptions for our result to hold.
3

---

(A1) The functions & (as a function of its second argument) and are proper. closed, lower semi- continuous convex functions. We assume additionally that either the cost function E(y, .X) + r()) is strictly convex, that Ä(y- +) is strictly convex in its second argument and r is the & norm, and that the optimization problem 2 is feasible.
(A2) The covariance matrices are positive definite and their spectral norms are bounded.
(A3) The mean vectors μą are distributed according to some density Pu(M such that the following quantity is finite
Vd
E
[
M1 < +00,
(5)
where ||r denotes the Frobenius norm.
(A4) The number of samples n. and dimension both go to infinity with fixed ratio a = n/4, called hereafter the sample complexity. The number of clusters K is finite.
(A5) The fixed point of the set of self-consistent equations (8) exists and is unique.
As specified by assumption (A1), our proof does not apply any convex problem. We discuss this assumption further in Appendix A.5. We also comment on the existence and uniqueness of the solution the set of self consistent equations Eq.(8) in Appendix A.6. Before proceeding further, let us specify useful notation. Suppose that the matrix G = (Gki)& R kxdd is given, alongside the four-index tensor A (ARsk')) RR k'R' E kxdd
8 R Kx We will use the notation G & A = Eks GEiAKI E R xd_ Similarly, given four-index tensor A, we will define VA as the tensor such that A A O A. We now in position state main result.
Theorem (Concentration properties of the estimator). Let ÊKE(K] (N Ix) be collection of K di-immssiioall standard normal vectors independent of other quantities. Let also be {Ex} a set of K matrices, 3₁ E RRK xd, with ii.dd standard normal entries, independent of other quantities. Under the set assumptions (Al-A5), for any R. Ø2 kx + R, the estimator W* and the matrix Z = -- W+ X verify:
functions of finite order o1 Rkxd
Ta
(I(W*)
P Es (o)(
22
Be (
(6)
n,d++000
n.d++0
where we have introduced the proximal for the loss:
hg V/ 1/2 Prox Prox
v. g(..
(V,
1/2 wx) ERK
W/ = my + b
Q Ex
1/2
(7)
and H E kxn is obtained by concatenating each h2s p&n times. We have also introduced the matrix proximal E xxd
G = ==A A r OAO)) A A-' -'=I V.LLE B= Σ (uumm +3x V
The collection of parameters (Qk, my, Vn, Q ma, VE)REjKI given by the fixed point of the following self-consisteri equations:
Qx GE
Q = axpllE [fuf
m. EE Guul
V = - "Eg [
(8)
V1 -== GO (Q Ex)
7
2 Σnh E O
[K
my = Lpp [fk]
where fx V "hx wr). and the vector b* is such that En P& (ie 0 holds.
The purpose of this statement is to have an asymptotically exact description of the distribution of the estimator, where the dimensions going to infinity are effectively summarized averages over simple, independent distributions. Those distributions are parametrised by the set of finite-size parameters
(Qx, m VE, Qu, my, VR) VR)KEjK] that can be exactly evaluated and have clear interpretation. Indeed, the parameters (my, my) and Q Qx) respectively represent means and covariances of multivariate Gaussians (combined with the original pa, Σx), and the (V,, V%) parametrise the deformations that should be applied to these Gaussians to obtain the distribution of W = The distribution is characterized weak sense with concentration of pseudo-Lipschitz (i.e., sufficiently regular) functions, whose definition is reminded in the Appendix A. From this result one can work out

---

number of properties of the weights W e.g., training and generalisation error, but also hypothesis tests as done in [49] for the LASSO. Due the generality of the statement, no direct simplification is possible. However, we will see that in certain specific cases all quantities can be greatly simplified. This is notably the case for diagonal covariance matrices and separable estimators and observables $1, $2, where the sums over high-dimensional Gaussians concentrate explicitly to one-dimensional expectations. For instance the results of [14, 20] can be recovered as special cases of the present work. Theorem then allows to obtain the asymptotic values of the generalisation error, of the training loss and of the training error. Their explicit expression is given in the following Theorem.
Theorem (generalisation error and training loss). In the hypotheses of Theorem 1, the training loss, the training error and the generalisation error are given by
K "g 1 Σ
6g Σ Pk Rel(ek, h
6, 6= 1==1-
1- Σ Pe (hx));
P (6 (w]]] (9)
The case of ridge regularisation and diagonal Σ₁- The general formulas given above can be remarkably simplified under some assumptions about the choice of the regularisation and about the structure of the covariance matrices Σg. This is the case for instance for the ridge regularisation r(W)= = || / 2 and jointly diagonalizable covariances. In this case, Theorem simplifies as follows.
Corollary 3. Under the hypotheses of Theorem 1, let further assume that ridge regularisation is adopted, r r(W) = | /2, and that the covariance matrices Σ₁ have a common set of orthonormal eigenvectors {v.) i- that, for each Σn = o D.u. Let us also introduce, in the d - +00 limit, the joint distribution for the K K-dimensional vectors = (o) o.....ok) and f (μ ..... , kk)
I 8(a -0))0(p² vduk v.) + p(or,
7
(10)
==
Then, the first three saddle point equations in eqs. (8) take the form
Qx Eo
ot (AIx + EK IK=10'Vs)
-2 (Enn 1 mmm +E o ==
mk Eo,r
4 Al + E VnVi)
Ex 1 untminn
(1I)
Vx = Fo a
x (MIx + Ex=1 onV))
Narrative of the proof The proof detailed in Appendix A. It overcomes problems that existing methods, notably convex Gaussian comparison inequalities [20], have yet to be adapted to. The first main technical difficulty resides in the estimator of interest being a matrix learned with non-linee non-lincar functions. This makes it impossible decompose the problem on each row of the estimator, which must be characterized in a probabilistic sense directly as a matrix. The second main difficulty is brought by the mixture of arbitrary covariances. Intuitively, the covariances correlate the estimator with the individual clusters, and therefore the correlation function cannot be represented by a single quantity. In our proof, these points are handled using the AMP and related state-evolution techniques [33, 50-52j. The main idea of the proof is to express the estimator W as the limit of a convergent sequence whose structure enables the decomposition of all correlations and distributions in closed form. AMP iterations can handle matrix valued variables [36, 53], correlations in block-structure [36], non-separable functions [37, 38] and compositions of the previous three, leaving large choice of possibilities in their design. We thus reformulate the problem in way that makes the interaction between the estimator and each cluster explicit, effecttivlyy introducing a block structure to the problem, and isolate the overlaps with the means (14x), }. We then design matrix-valuce sequence that obeys the update rule of an AMP sequence, in order to benefit from its exact asymptotics, and whose fixed point condition matches the optimality condition of the ERM problem, Eq. (2). Our proof builds on the spatial coupling framework in the AMP literature [36, 54], which shows that the effect of random matrices defined with non-identically distributed blocks can be embedded in an AMP iteration while explicitly keeping the effect of each block. The non-linearities are then obtained by block decomposition of the proximal operators defined on sets of matrices, acting on
5

---

different variables of the AMP sequence and representing the effect of each cluster. The convergence analysis is made possible by the convexity the problem: the sequence is defined with proximal operators of convex functions which are roughly contractions, and results in converging sequences when combined with the high-dimensional properties of the iteration. also interesting note that the replica method, although heuristic, yet again gives the correct prediction without any hindering from the aforementioned main difficulties, as detailed Appendix
Universality AMP-type proofs are amenable to both finite sample size analysis and universality proofs. For instance, in [55] it is shown that simpler instances of AMP for the LASSO exhibit exponential concentration in the system size, and the i.i.d. Gaussian assumption can be relaxed to independently sampled Gaussian distributions, as shown in [56, 57]. Although these results do not formally encompass our case, their proof method contains most of the required technicalities, and it should be possible to prove similar results the present setting. Indeed, recent results in [18] suggest that the formula of Theorem and should be universal for all mixtures of concentrated distribution in high-dimension, not only Gaussian ones. As we discuss Sec. 3.3, even real data learning curves are empirically found to follow the behavior of the mixture of Gaussians.
3 Results on synthetic and real datasets
In this section we exemplify how Theorem can be employed to compute quantities of interest in different empirical risk minimisation tasks in high-dimensions. In all cases discussed below, eqs. (8) have been solved numerically, A repository with a polished version of the code we used to solve the equations is available GitHub [58] (see also Appendix B.5).
3.1 Correlated sparse mixtures
0.4
0.3
fractoon
6.2
0.1
frib
=05
025
optimal
2.0
0.5
0.0
0.3
2.2
23
sample complexity
Figure 1: (Left) Two-dimensional projection of the Gaussian mixture introduced via Eq. (12) in which the sparse directions of the means are correlated with the weak/strong directions in the data. (Right) Fraction of non-zero elements of the lasso estimator (lop) and optimal regularisation strength (bottom) a function of the sample complexity a n/a for different anisotropy ratios and fixed sparsity p = 0.1. Note that for A1 A Z 1 and for low a the optimal error is achieved for vanishing regularisation, which corresponds to the basis pursuit algorithm [59].
As first example, consider a binary classification problem in which the most relevant features live in subspace of IRd, and can be either weaker stronger with respect to the irrelevant features. This problem can be modelled with a Gaussian mixture model with sparse means, and where the correlated with the non-zero components of the
strong/weak directions of the covariance matrix means. Mathematically, we consider a data set with n independent samples (x". xe"."") E Rd x 1-1 drawn from Gaussian mixture x" ~ (y μ, E) with diagonal covariance Σij o. which is correlated with the sparse means:
P( σ) = II (nN 10,00,,1)66..0 1)6,, E=1
(12)
where p > 0 the fraction of non-zero entries in μ.. This model is closely related to the rare/weak features model introduced by Donoho and Jin in [19]. Indeed, in the case A A₂ = A the

---

4g/02 0.1
4,/02 0.5
4,/0, -
Train. error Gen.
0.2
ridge
lasso
6.4
0.2
0.0
sample complexity
Figure 2: Learning curves for the sparse mixture model defined via Eq. (12) at fixed sparsity p 0.1, comparing the performance of the ridge (blue) and the lasso (orange) estimators optimal regularisation strength X" and for different anisotropy ratio A (here A = 0.1 and we vary A2). Full lines denote the theoretical prediction, and dots denote finite instance simulations with package [60]. Above a certain regime in which the &
1000 using the ClasticNet module in the Scikit-leat
sample complexity a, we can identify two regimes: a) a A / penalty improves significantly over f; b) a A A ž regime in which the performance is similar. Interestingly, even though the generalisation error of lasso is considerably better in a), the training loss (i.e. the mse on the labels) is higher, & vice-versa in b).
signal-to-noise ratio of the model is proportional p/ p/VA, with p and A -1/2 playing the roles of the parameters and pm setting the "rareness" and "strength" of the features in [19].
The formulas given in Theorem simplify considerably for this model (see Appendix C for details), and therefore can be readily used to characterise the learning performance of different losses and penalties. For instance, one fundamental question with the & regularization is advantageous over the usual fz. Figure 2 compares the learning curves computed from Theorem for the lasso and ridge estimators, with optimal regularisation strength (a) = argmin Cg (a, X) at fixed sparsity = 0.1. We can see that lasso performs considerably 1, while achieves a similar performance when A//22 2 Z 1. This is quite intuitive: the sparse directions are uninformative, and therefore learning the relevant features is better when they stronger. Figure (right) shows how the sparsity of the learned estimator W and the optimal regularisation X depends on the sample complexity Interestingly, for A 0.1 or lower there is region of small a in which basis pursuit (A 0+) [59] is optimal, and the sparsity of the estimator has a curious non- non-monotonic behaviour with a.
address is when learning sparse solution
better than ridge in the regime where A
n//.
3.2 Separability transition for the cross-entropy loss
We now consider the problem of classifying points of K Gaussian clusters using cross cross-entropy loss
(
I1 In
(13)
Using the results of Theorem 2, we estimate the dependence of the generalisation error 6g on the sample complexity a and on the regularisation A. We assume Gaussian means μ4 ~ (0, La/d) and diagonal covariances Σn = Σ ALg Finally, adopt ridge penalty, r r(W)= = [ /2, and we focus on the case of balanced clusters, i.e., Ps = 1/K for the sake of simplicity.
In Fig. 3 (left top) we plot the generalisation error fg as function of a for 2 < K < 5 and À = 10-4 The smooth curve is obtained solving the fixed point equations in The- orem and plugging the results in the formulas in Theorem The results of numerical experiments are obtained averaging over 102 instances of the problem solved using the Logisti iergrssiReeressii module in the Scikit-learn package [60]. An excellent agreement observed. For each pair (K, A) and for vanishing regularisation À + 0+ we observe generalisation error. Indeed, the cusp a (A) in the generalisation error corresponds to the point in which the cross-entropy estimator ceases to perfectly interpolate the data, revealing the existence of separability transition of the type discussed in [16] for Gaussian i.i.d. data. As stressed therein, a phase of perfect separability of the data points corresponds to regime in which the maximum -ikimuum-ikelihood likelihood
Separability transition-
demubleedecent--eee behaviour in the
7

---

0.8
10
K=2
K-
1-10-
training error generalisation error
K=3
5
==10-2
0.6
A- 1-10-1
Reparasinng transition
gentrallsstion error
A=
0.55
Bayes optimal
0.4
0.50
0.2
0.45
0.40
0.2
0.35
0.0.5
A-1
0.30
A= 0.4
1=10
0.0
0
6
8
5
10
sample complexity
sample complexity
Figure 3: Classification of K Gaussian clusters in d dimensions, having Gaussian means and
Σg = Σ AL, with A = 1/2. In all presented cases, a quadratic regularisation has been adopted. Numerical experiments have been performed using d = 10 (I.eft) Generalisation error ég (lop) and training еπтог (bottom) as function of a at À 10- Theoretical predictions (full lines) are compared with the results of numerical experiments (dots). Dash-dotted lines of the corresponding color represent, for comparison, the Bayes-optima error. The results of numerical experiments are in agreement with the theoretical predictions in all cases. (Center) Separability transition dj as function of K in the same setting for different values of A. (Right) Dependence of the generalisation error on the regularization À for K 3 and 1/2 in the balanced case, Pk = 1/K.
estimate does not exist with probability one. This is visible, in the same figure (left bottom), from the training еπтоr e, that is identically zero for < ag and strictly positive otherwise. Our result extends the observations in [14, 21], where an analytic expression for az has been given the case of for K 2, 141 ーA4 Gaussian vector, generalising the classical result of Cover [43]. The separability transition point 0'K decreases with A and increases with K, showing that for larger K it is easier to separate the different clusters: this intuitively follows from the fact that, fixed and A, each cluster is given by ad/ K points, i.e., fewer for increasing K and therefore easier to classify, see Fig. 3 (center).
The role of regularisation - In Fig. 3 (right)
generalisation error
0.42
0.17
we compare the performances of the cross-entropy loss with respect to the Bayes-optimal error (de- tailed in Appendix D) for different strength À of the regularisation, assuming all identical diagonal covariances Σg Σ AL.- In the case of bal- anced clusters (i.e., Pk = 1/K k for all k) it is ob- served that the generalisation error approaches the Bayes-optime error for À + +oo. The same phe- nomenology has been observed in [14, 24] in the K case with opposite means and generic loss, and in [20] for K > 2 for the square loss. Using the concentration results of Section 2, we investigated the robustness of this result in the case of balanced clusters but with different covariances and vari- ous losses. First, we considered two opposite bal- anced clusters with Σ, I,I, and Σg A,I, A1 # A2, and we estimated the generalisation error at fixed sample complexity as function of E [10-4, 102] using ridge regression. As shown in Fig. 4 (left), the regularisation strength optimis- ing the error finite, and in particular depends on the sample complexity. This situation closer to what is observed in real problems with balanced data analysed using logistic regression. Indeed, using
0.16
0
0.15
a= 1.2 Fa MNIST
MNIST
0 5
0.38
0.14
a= 1.1
0.36
10-1
10a
10-3
10-2
10-1
regularisation
regularisation
Figure 4: (Leff..) Generalisation error obtained using ridge regression in the case two bal- anced Gaussian clusters having Σ; 1/ Lu and Σn Too La function of À for different val- ues of the sample complexity a. (Right) Gen- eralisation error eg function of X fixed in the binary classification of MNIST and in the FaShionMNIST via logistic regression (see Sec. 3.3 for details).

---

0.20
Theory
0.10
Theory
Synthetic
Synthetic
0.15
MNIST
0.05
Fashion-MNiST
training loss
0.4
0.00
0.4
0.3
0.2
2
3
7
0
2
5
6
sample complexity
sample complexity
Figure 5: Generalisation error and training loss for the binary classification using the logistic loss on MNIST with À = 0.05 (left) and on Fashion-MNIST with À = 1 (right). The results are compared with synthetic data produced from the corresponding Gaussian mixture, and the theoretical prediction.
the covariances from real data sets such MNIST Fashion-MNIST yields similar behaviour, Fig. 4 (right), with an optimal that is found to be finite.
3.3 Binary classification with real data
A recent line of works has reported that the asymptotic learning curves of simple regression tasks on real data sets can be well approximated by a surrogate Gaussian model matching the first two moments of the data [12, 45, 46]. However, this analysis fundamentally restricted to least-squares regression, and considerable deviation from the Gaussian model was observed for classification tasks [12]. Authors of [18] have shown that realistic-looking data from trained generative adversarial networks behave like Gaussian mixtures. Here, we pursue these observations and investigate whether Theorem 2 can be used capture the learning curves of classification tasks two popular data sets: MNIST [61] and Fashion-MNIST MNIST [62]. Our goal is to compare the performances of some classification tasks on them with the predictions provided by the theory for the Gaussian mixture model.
Both data sets consist of noot 7 10th images 3" Rd d= 784. Each image at is associated to a label / = f0, 1, ......9,, 9} specifying the type of represented digit (in the case of MNIST) or item (in the case of Fashion-MNiSTI In both cases, we divided the database into two balanced classes (even vs odd digits for MNIST, clothes vs accessories for Fashion-MNISTT), relabelling the elements 4 with yd E 1 depending on their class, and selected the training, leaving the others for the test of the performances. We adopted a logistic loss with & regularisation. First, we performed logistic regression on the training real data set, then we tested the learned estimators on the remaining Teot - n images. At the same time, for each class & of the training set, we empirically estimated the corresponding mean μ E I2 and covariance matrix Eg E IR dxd We then assumed that the classification problem on the real database corresponds to a Gaussian mixture model of K clusters with means { ) k<(2] and covariances {Ex ke Under this assumption, we computed the generalisation error and the training loss predicted by the theory inserting the empirical means and covariances in our general formulas. The results are given in Fig. showing good agreement between the theoretical prediction and the results obtained on MNIST and Mushion-MNISS In Fig. 5 we also plot, as reference, the results classification task performed on synthetic data, obtained generating genuine Gaussian mixture with the means and covariances of the real data set.
Thot elements perform
Interestingly, this construction can also be used to analyse the learning curves of classification problems with non-linear feature maps [12], e.g. random features [63]. In this case, we first apply to our data set feature map x" orf( FF"), where F E Rxxd has i.i.d. Gaussian entries and the erf function is applied component wise. The classification task is then performed on the new data set {(#", y [ee[n]. the new data points x" living in p-dimensional space. We denote = p/d. We repeat the analysis described above in this new setting. Our results are in Fig. for different values of y. Once again, the generalisation error and the training loss are shown to be in good agreement with both the theoretical prediction and the synthetic data sets obtained plugging in our formulas the
real data means and the real data covariance matrices.

---

0.25
0.15
0.5
Theory
Theory
generalitation
0.20
y-
Synthetic MNIST
0.10
Y-
Synthetic
y=
y=
Fashion-MNIST
0.15
0.05
0.00
0.6
0.4
training
0.3
0.2
sample complexity
sample complexity
Figure 6: Generalisation emror and training loss for the binary classification using the logistic MNIST at À = 0.05 (left) and on Fashion-MNIST at = (right) in the random feature setting, for different values of y, ratio between the number of parameters and the dimensionality of the data. The results are compared with synthetic data produced with the same y, and the theoretical prediction.
Acknowledgements
We thank Raphaël Berthier and Francesca Mignacco for discussions. We acknowledge funding from the ERC under the European Union's Horizon 2020 Research and Innovation Program Grant Agreement 714608- SMiLe, and from the French National Research Agency grants ANR-17-CE23- 0023-01 PAIL. GS is grateful to EPFL for its generous hospitality during the finalization of the project.
References
[1] Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma. Neural Computation, 4(1):1-58, 1992.
[2] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer Series in Statisties. Springer New York Inc., New York, NY, USA, 2001.
[3] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical biri-variance trade-off. Proceedings of the National Academy of Sciences, 116632)15844--15854 2019.
[4] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Preprint arXiv:1903.0m 08560, 2020.
[5] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to understand kernel learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 541 1419549. PMLR, 10-15 Jul 2018.
[6] Peter I.. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, -17648) 2020.
[7] Song Mei and Andrea Montanari. The generalization error of random features regression: Pre- cise asymptotics and double descent curve. Communications on Pure and Applied Mathematics, 2019. To appear, preprint arXiv: 19Xiv:190.... 901999088555...
[8] Federica Gerace, Bruno Loureiro, Flornet Krzakala, Mare Mézard, and Lenka Zdeborová. Generalisation error in learning with random features and the hidden manifold model. 37th International Conference Machine Learning, 2020.
10

---

[9] Behrooz Ghorbani. Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural network. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 9111-9121, 2019.
[10] Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure on learning neural networks: The hidden manifold model. Physical Review X, 10(4):041044, 2020.
[11] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. The Gaussian equivalence of generative models for learning with shallow neural networks. Preprint arXiv:2006. /4709, 2020.
[12] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model. Preprint arXiv:2102.08127, 2021.
[13] Tengyuan Liang and Pragya Sur. A precise high-dimensional asymptotic theory for Boosting and minimum-l, -norm interpolated classifiers. Preprint arXiv:2002.01 01000 586, 2020.
[14] Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova. The role of regularization in classification of high-dimensional noisy Gaussian mixture. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6874-6883, PMLR, 13-18 Jul 2020.
[15] Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. Classifying high- dimensional gaussian mixtures: Where kernel methods fail and neural networks succeed. Preprint arXiv:2 2021.
[16] Emmanuel J Candès, Pragya Sur, et al. The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression. The Annals of Statistics, 48(1):27- 42, 2020.
[17] Vardan Papyan, X. Y. Han, and David L. Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40):24652-2466 2020.
[18] Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet. Ran- dom matrix theory proves that deep learning representations of GAN-data behave as Gaussian mixtures. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8573-8582, PMLR, 13-18 Jul 2020.
[19] David Donoho and Jiashun Jin. Higher criticism thresholding: Optimal feature selection when useful features are rare and weak. Proceedings of the National Academy of Sciences, 105(39):14990-1479)) 2008
[20] Christos Thrampoulidis. Samet Oymak, and Mahdi Soltanolkotabi. Theoretical insights into multiclass classification: A high-dimensiionl asymptotic view. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8907-8920. Curran Associates, Inc., 2020.
[21] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high-dimensional binary linear classification. Preprint arXiv:1911.0582. 2020.
[22] Xiaoyi Mai, Zhenyu Liao, and Romain Couillet. A large scale analysis of logistic regres- sion: Asymptotic performance and new insights. In ICASSP 2019 2019 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 3357-3361, 2019.
[23] Xiaoyi Mai and Zhenyu Liao. High dimensional classification via regularized and unregularized empirical risk minimization: Precise error and optimal loss. Preprint 3744, 2020.
11

---

[24] Edgar Dobriban and Stefan Wager. sion and classification. The Annals of Statistics, 46(1):247 279. 2018.
asymptotics of prediction: Ridge regres-
[25] Ganesh Kini and Christos Thrampoulidis. Analytic study of double descent in binary classifica- tion: The impact of loss. Preprint arX1v:2001.11552,, 2020.
[26] Houssem Sifaou, Abla Kammoun, and Mohamed-Sling Alouini. Phase transition in the hard- margin support vector machines. In 2019 IEEE 8th International Workshop on Computational Advances in Mulii-Sensor Adaptive Processing (Cainngg(AAA (CAMSAP), pages 415-419, 2019.
[27] Ke Wang and Christos Thrampoulidis. Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting and regularization. 2021.
(28) Niladri S. Chatterji and Philip M. Long. Finite-sample analysis of interpolating linear classifiers in the overparameterizeed regime. Preprint arXiv:2004. /2019, 2021.
[29] Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for weer-parameterized maximum
margin classification on sub- sab-gaussian mixtures. Preprint arXiv:2104.13628, 2021.
[30] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high- dimensional logistic regression. Preprint S.fV::1906.03661, 2019.
[31] 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-5628, 2018.
[32] Mihailo Stojnic. framework characterize performance of lasso algorithms. Preprint arXiv:1303.729) 72911, 2013.
[33] Mohsen Bayati and Andrea Montanari. The dynamics of message passing dense graphs, with applications to compressed sensing. JEEE Transactions on Information Theory, 57(2):764-785. 2011.
[34] Florent Krzakala, Mare Mézard, Francois Sausset, Yifan Sun, and Lenka Zdeborová. Probabilis- tic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices. Journal of Statistical Mechanics: Theory and Experiment, 2012(09)P000009 2012.
[35] David L Donoho, Adel Javammard, and Andrea Montanari. Information-theereea theoretically optimal compressed sensing via spatial coupling and approximate message passing. IEEE transactions on information theory, 59(11).7434-746) 2013.
[36] Adel Javanmard and Andrea Montanari. State evolution for general approximate message passing algorithms, with applications spatial coupling. Information and Inference: Journal of the IMA, 2(2):115-144, 2013.
[37] Raphael Berthier, Andrea Montanari, and Phan-Minh Nguyen. State evolution for approximate message passing with non-separable functions. Information and Inference: A Journal of the IMA, 9(1::33-77, 2020.
[38] Andre Manoel, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Multi-layer generalized linear estimation. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 22022 IEEE, 2017.
[39] Jiashun Jin. Impossibility of successful classification when useful features are rare and weak. Proceedings of the National Academy of Sciences, (06(22):8859-888))) 2009.
[40] Jun Shao, Yazhen Wang, Xinwei Deng, and Sijian Wang. Sparse linear discriminant analysis by thresholding for high dimensional data. The Annals of Statistics, 39(2):1241 - 1265, 201
[41] Qing Mai, Hui Zou, and Ming Yuan. A direct approach to sparse discriminant analysis in ultra-high dimensions. Biometrika, 99(1):99-4,, 12 2012.
[42] Yanfang Li and Jinzhu Jia. I.1 least squares for sparse high-dimensional LDA. Electronic Journal of Statistics, 11(1):2499 2518, 2017.
12

---

[43] Thomas M Cover.
Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions on electronic computers, (3):3263334. 1965.
[44] Elizabeth Gardner. The space of interactions in neural network models. Journal of physics A: Mathematical and general, 21(1): 1988.
[45] Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernll aligmment risk estimator: Risk prediction from training data. Preprint arXiv:2006.09796, 2020.
[46] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves kernel regression and wide neural networks. In International Conference on Machine Leurning, pages 1024-1034. PMLR, 2020.
[47] Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in optimization. 1(3):127-232 2014.
[48] Heinz H Bauschke, Patrick L Combettes, et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
[49] Michael Celentano, Andrea Montanari, and Yuting Wei. The Lasso with general Gaussian designs with applications to hypothesis testing. Preprint arXiv:2007.13716, 2020.
[50] Erwin Bolthausen. An iterative construction of solutions of the TAP equations for the SherrintoonKKirpatrrie model. Communications Mathematical Physics, 325(1):333-366 2014.
[51] Mohsen Bayati and Andrea Montanari. The LASSO risk for Gaussian matrices. IEEE Transac- tions on Information Theory, 58(4):1997-2017, 2011.
[52] Cedric Gerbelot, Alia Abbara, and Florent Krzakala. Asymptotic Errors for Teacher-Studen Convex Generalized Linear Models (or: How to Prove Kabashima's Replica Formula). Preprint arXiv:2006.06588 2020.
[53] Benjamin Aubin, Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris, and Lenka Zdeborová. The committee machine: Computational to statistical gaps in learning two-layers neural network. Journal of Statistical Mechanics: Theory and Experiment, 2019(12) 2019.
[54] Florent Krzakala, Marc Mézard, François Sausset, YF Sun, and Lenka Zdeborová. Statistical- physics-based reconstruction in compressed sensing. Physical Review X, 2(2):021005, 2012.
[55] Cynthia Rush and Ramji Venkataramanan. Finite sample analysis of approximate message passing algorithms. IEEE Transactions on Information Theory, 64(1 64(111)7244-7286, 2018.
(56) Mohsen Bayati, Mare Lelarge, Andrea Montanari, et al. Universality in polytope phase transitions and message passing algorithms. Annals of Applied Probability, 25(2):753-822 2015.
[57] Wei-Kuo Chen and Wai-Kit Lam. Universality of approximate message passing algorithms. Electronic Journal of Probability, 26:1-44, 2021.
[58) Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Pixurerixturerrojeett, October 2021. https::/ https://githul: http///tttttb.t//// wwt./oommmmc/eeeee Idmm/IIePHCCS
CausskixtureProject.
[59] Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 20(1):33 61, 1998.
[60] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. The Journal of Machine Learning Research, 12:2825-2834
2011.
13

---

[61] Yann LeCun and Corinna Cortes, ATT Labs [Online], 2010. Database released under CC BY-SA 3.0 license http://yann. lecun. com/ http///dbm/mn/...///m//
[62] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. Preprint vrXiv:1708.00744, 2017. Database
released under MIT licence at https: attpps//g/t hhtps:///gthhb.../ catm///aaaadddreeearaaaaaaaaaaa -nniss..ss..
[63] Ali Rahimi and Benjamin Recht. Random Features for Large-Scale Kernel Machines. In NIPS, pages 1177-1184, 2007.
[64] Heinz H Bauschke, Jonathan M Borwein, and Patrick Combettes. Bregman monotone optimization algorithms. SIAM Journal on control and optimization, 42(2):596-636, 2003.
[65] Heinz H Bauschke, Minh N Dao, and Scott B Lindstrom. Regularizing with bregman bregman-moreat moreau envelopes. SIAM Journal on Optimization, 28(4):3208-322 2018.
[66] Lenka Zdeborová and Florent Krzakala. Statistical physics inference: Thresholds and algorithms. Advances in Physics, 65(5):453-5522 2016.
[67] Cédric Gerbelot and Raphaël Berthier. Graph-based approximate message passing iterations. arXiv preprint arXiv: 1905, 2021.
[68] Ryan Tibshirani. The lasso problem and uniqueness. Electronic Journal of statistics, 7:1456- 1490, 2013.
[69] Mare Mézard, Giorgio Parisi, and Miguel Virasoro. Spin glass theory and beyond: An Intro- duction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987.
[70] Saharon Rosset, Ji Zhu, and Trevor Hastie. Margin maximizing loss functions. NIPS, pages 1237-1244, 2003.
14


Reviews:
[{"review_id": "q0k-ZgfBJM3", "reviewer": "Reviewer_HUKh", "summary": "This paper provides a general asymptotic characterization of the solution that comes from learning a mixture of K Gaussians under a supervised learning setting with arbitrary convex loss and regularization. The technique for proving the characterization is novel. Specifically, it constructs an approximate message passing sequence that admits state evolution equations, whose fixed point satisfies the optimality condition of the original problem. Equipped with the theoretical tools, the authors study both synthetic data (sparse Gaussian mixture and general K Gaussian mixtures) and real datasets to further understand (1) $\\ell_{1}$ and $\\ell_{2}$ regularization for sparse mixture models; (2) separability transition; and (3) quality of Gaussian mixtures as surrogate model. Interestingly, the experiments exhibit a high agreement between the theoretical and numerical values. ", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Originality: This work utilizes the technique from the field of statistical physics to understand high dimensional inference problem in statistical learning. Specifically, an approximating message passing sequence is constructed so that the fixed point of that sequence coincides with the optimal solution of the original convex optimization problem with regularization. Using the existing theory for approximate message passing, the asymptotic value of the convex loss at the optimal solution can be derived. This method generalizes the previous work that derives the asymptotic result under some special setting for covariance structure and convex loss. \n\nQuality: The paper is technically strong. Due to the space, the authors have to defer the proof to the supplementary material. The process to construct the AMP sequence such that the fixed point satisfies the optimality condition has been very carefully written. \n\nClarity: The submission is nicely written. A few questions to make sure I understand things correctly: (1) In the objective function, why does it not have $\\frac{1}{n}$ factor for the loss term? (2) what is the choice of $d$ in the experiments for synthetic data?  How would choice of $d$ affect the gap between theoretical value and the experimental value? (3) The authors have mentioned that the current asymptotic result can be adapted to the finite sample setting, does that include both finite $n$ and $d$? (4) What the result might be if $n$ grows much faster than $d$, in the sense that $\\frac{n}{d}$ is not a constant? \n\nSignificance: I think the result is very important. In particular, the technique of constructing approximate message passing algorithm can be potentially useful to other statistical learning setting. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "How easy is it to construct an AMP sequence for a learning problem? Some comments on flexibility of the technique will be helpful. Some motivations of the AMP method and high level ideas to apply AMP method will also inspire other researchers in future, who might not be familiar with the technique.  ", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "n9jIDIgvXyX", "reviewer": "Reviewer_Cx7X", "summary": "The paper shows the exact asymptotic behavior of the GLM/1-layer-NN solution for features following a mixture of K Gaussian distribution.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "My comments on the paper are mixed. \n1) If we only look at a classification problem on a mixture of Gaussian distribution, to pick a convex approach, it seems natural to consider a linear model with a convex loss function. But we can also utilize a non-convex approach to first estimate the Gaussian parameters and then classify the sample which probably gives better results.\n2) If we look at it as learning a neural network with a mixture of Gaussian as input, one layer is too simple to consider. If we think deep NN without the output layer produces a mixture of Gaussian and we just want to know the asymptotic of the final loss function, one layer seems to be fine. \n3) If we look at the contribution to the AMP literature, I think it is great that we can extend the framework to a mixture of Gaussians. On the other hand, the result can be more general if it can extend to mixtures of concentrated distributions. The authors have mentioned that they expect the result should be similar and there are already existing results that extend Gaussian distribution to sub-Gaussian distribution. It looks like with some effort, the result in this paper can be more general.\n\nIn summary, the paper has some incremental contributions.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Wgq5NZTu5u5", "reviewer": "Reviewer_DjLU", "summary": "The paper provides precise asymptotic solutions for learning Gaussian mixtures using generalized linear models. This work generalizes and extends previous works in this direction by allowing any means/covariance of each Gaussian component, any convex loss and any regularization. Beyond the theoretical analysis, the paper also studied several examples, including comparing Lasso and Ridge regression, comparing the theoretical vs practical learning curves on real data. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The main contribution of this paper is a generalization of existing literature on asymptotic solutions for Gaussian mixtures. The results are original and novel. The paper is well-written and the theorem is clearly presented. The experimental result on real data looks surprisingly good to me.  \n\nMy main concern is the complexity for solving the fixed point of Eq. (8). As far as I read, the main paper doesn't mention how to solve it. Even for the simplified setting, the solution to Eq (11) doesn't seem to be straight forward to me. The appendix seems to imply that Monte Carlo approximation and iterative algorithms will be involved in the computation. Note that these approaches may lead to some error in the asymptotic results.   \n\nOverall, I think this paper will be interesting to the theory community especially for those who are interested in high-dimensional asymptotic solutions. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper addressed the limitations of the theory, i.e., the assumptions. Since this is theoretical paper, the societal impact is minimal. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of learning a mixture of k gaussians by performing empirical risk minimization on a convex loss with a regularization penalty. The main technical contribution of this work is an asymptotic characterization of the solution, through statistical physics techniques. The conceptual novelty is that they can work with mixtures of gaussians, and it seems promising that some of these ideas might ultimately be useful in even more general settings, such as mixtures of concentrated distributions. They also give some appealing applications to (1) the case with sparse means, where they study the efficiency of $\ell_1$ vs. $\ell_2$ penalties and (2) max margin multiclass classification, where they identify a phase transition in the maximum likelihood estimator. They also give some interesting empirical applications that work beyond synthetic data.   
Decision: Accept (Spotlight)