Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the problem of learning Gaussian mixture models; specifically estimating the means of a uniform spherical mixture of $k$ Gaussians with identity covariance matrix in $d$ dimensions. A common parametrization is the minimum separation ($\Delta$) between any mean-pair. Previous works have shown that for polynomial sample complexity a) if $\delta$ is $o(\sqrt{logk})$ then $d$ cannot be $\Omega(\log k)$, b) $\delta = \Omega(\sqrt{log k })$ is possible, and c) $\delta = o(1/\sqrt{log k })$ is not possible. This paper nails down the $\delta$, $d$ tradeoff in the intermediate $\delta$ region. Specifically it shows that $\delta = d/\sqrt{log k}$ is optimal. 

The crux of the algorithm is two fold. First sample ln k/p samples from the mixture where p is the probability that a sample from the mixture is \eps close to some cluster's mean. Then the key part of the algorithm is to test if a given guess of the mean is close to one of the mean vectors or far away from it. This is done by estimating the expectation of the Fourier transform under truncated Gaussian as a statistic.  
strengths_and_weaknesses: This paper settles a gap in existing literature about a fundamental problem that the machine learning community has studied for a while. The analysis is based on a novel technique that possibly might generalize to other mixture models. 

I don't have any major complaints. Nevertheless, I think the presentation of the paper could be vastly improved to make it stronger. For example, section 1.2 appears out of nowhere - it is not apiori clear why one might want to consider a testing problem. Even in the later sections, the flow of the algorithm is not clear which is particularly not ideal because only background forms the first 7 out of 9 pages of the submission. It would be much better if main ideas of the algorithm were in the submission instead of the appendix. For instance, it would be cleaner for the main submission to have more details about why drawing samples from the mixture is sufficient to give good mean guesses.  
questions: Apart from the presentation comment, I don't have other questions. 
limitations: The limitations section in the paper is adequate.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper provides a Fourier approach to the problem learning mean parameters of spherical Gaussians and its computation complexity. In the low-dimensional regime, the computation complexity of the algorithm is shown to be polynomial in the number of clusters. The computation complexity bound is examined carefully with respect to the magnitude of the the number of dimensions, the number of clusters, and the separateness of the mean parameters. The algorithm can also be extended to learn mixtures of other well-known local families of distributions.
strengths_and_weaknesses: **Strength**: The writing style of the paper helps the reader to quickly understand its main contributions without going too deeply into details with several technical terms when bounding the computation complexity. The proofs in Appendix are clear and carefully written. 

**Weakness**: The paper lacks experiment components. Without some simulation studies, it is hard to understand the advantages of this approach to other algorithms in the literature. 
questions: 1. Can you provide some simulation studies with the proposed algorithms and demonstrate the complexity with some figures? It would be very helpful to understand the theory better (especially to differentiate the regimes in Figure 1) and to show that the algorithm works. With the considered setting, simulation studies should not be very difficult.

2. How can we compare the complexity of this Fourier-based algorithm to well-known algorithm solving mixture models such as Expectation-Maximization? It is worth mentioning this in the Related Work section. 
limitations: The considered problem is of interest to the Mixtures Learning community. A limitation of this paper is the lack of experimental studies.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors consider the problem of estimating means $(\mu_i)_{i=1}^k$  from $m$ sample of the mixture

$\sum_{i = 1}^k \mathcal{N}(\mu_i, I_d)$, up to a small error. The ability to estimate the means primarily depend on the minimum separation between all pairs of means, the number of samples $m$, dimension of samples $d$, and number of clusters $k$. It also desirable to estimate the means, up to an error, with runtime that is polynomial in the parameters. The authors answer this problem in the low dimension regime where $d =o(\log k)$, which has been an open problem. Their main result provides an algorithm that provided samples from the mixture, efficiently learns the parameters in dimension $O(\log k/\log \log k)$ if the minimum separation between the means is at least $\frac{d}{\sqrt{\log k}}$. The runtime is shown to be polynomial in $k$. Their algorithm considers the Fourier transform of the mixture and estimates the corresponding characteristic function by carefully designing a sampling strategy for the frequency in this Fourier domain. I think the paper is well-written and clear.
strengths_and_weaknesses: Strengths:

- The paper is well-written and clear. The authors clearly explain the problem, outlining their contributions. Their proof for $d=1$ provides a good initiation for the general proof.
- The problem being considered is a well-studied problem and, to my knowledge, the contribution seem significant.


Weakness:
- While the paper is primarily of a theoretical nature, the authors provide an algorithm to estimate the means of the spherical Gaussian. If possible, it would be very interesting to see numerical performance of this algorithm, or a discussion on why this is not feasible.

questions: - Is there a quantifiable (in parameter like $d$, $\Delta$, $k$, $\dots$) number of sample lower bound required for estimating the means to a fixed error?
- Echoing the points above, what are the practical limitations of the algorithm?


limitations: The paper very briefly mentions its limitations.
review_title: null

Meta-review: metareview: Overall the reviewers felt that this paper should be accepted because it provides a nice theoretical result that pins down the sample vs. gap tradeoff for learning mixtures of Gaussians in low-dimension -- a well studied and interesting problem.
confidence: Less certain
Decision: Accept