Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper shows the exact asymptotic behavior of the GLM/1-layer-NN solution for features following a mixture of K Gaussian distribution.  
main_review: My comments on the paper are mixed. 
1) 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.
2) 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. 
3) 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.

In summary, the paper has some incremental contributions.  
limitations_and_societal_impact: This is a theoretical paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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.  

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

Overall, I think this paper will be interesting to the theory community especially for those who are interested in high-dimensional asymptotic solutions. 
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_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
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. 

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

Clarity: 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? 

Significance: 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. 
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_title: null

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)