Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers the fundamental problem of model selection for univariate Gaussian Mixture Models (GMMs), which asks for the minimum number of components needed to fit the given data. The approach to do this is via robust proper learning of GMMs, where given access to a distribution that is $\epsilon$-close to a $k$-GMM we want to find a $k’$-GMM (having ideally $k’=k$) being $\tilde{O}(\epsilon)$-close to that distribution. The paper presents the first algorithm for this task with $k’=\tilde{O}(k)$ that works for arbitrary GMMs and has polynomial sample complexity and runtime. Using that result, it obtains an algorithm for the model selection problem. Finally, the paper utilizes the techniques to obtain a result for Fourier sparse interpolation that enjoys better bounds on the sparsity of the outputted signal than prior work. At the core of the GMM algorithm is a procedure that works for GMMs with well-conditioned components and a localization technique allowing to reduce the general case to the well-conditioned one. The former is based on considering the Taylor expansions of the Gaussian components and associating the well-conditioned mixtures to points in a convex body. The latter uses Gaussian multipliers to reweight the mixtures so that they become more localized and constructs $\tilde{O}(k)$ such multipliers that allow reconstruction of the original mixture.
strengths_and_weaknesses: Questions regarding learning of Gaussians and mixture models are arguably one of the most fundamental problems in statistics. The paper presents an algorithm that enjoys polynomial runtime while working under no additional assumptions on the input. 
The paper is technically interesting and employs an interesting suite of techniques. The solution deviates from prior work ideas and requires substantial technical work. 
The paper is also well-written and despite the fact that the arguments used are involved, the authors managed to present their ideas in a clean way. I have not carefully checked the details in the supplementary material, but the outline of the main submission seemed reasonable.

I recommend that the paper be accepted.

questions: One question for the authors is if the localization technique or something similar has also been employed in prior work for GMMs or other problems.
limitations: Sufficiently addressed.
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: In learning theory, we often assume that samples are drawn from a finite mixture model.
Also, the number of components in the finite mixture model is known.
However, in many applications, this number may not be known in advance.
The problem of finding the number of components is called model selection.
The authors study the problem of robust model selection for one dimensional Gaussian mixture models with $k$ components ($k$-GMM).
Formally, it is formulated as follows.
Given samples drawn from a distribution that is $\epsilon$-close to a $k$-GMM in total variation, we want to output a $k'$-GMM where $k'$ is not much larger than $k$.

There is a long line of existing works for learning GMM.
However, they have different shortcomings in this setting such as requiring exponentially (in $k$) many samples, running in time in exponential in $k$, the number of Gaussians in the output $k'$ much larger than $k$, etc.
In this paper, the authors give an algorithm for learning arbitrary one dimensional $k$-GMMs that outputs an approximation with $\tilde O(k)$ components.

The algorithm works as follows.
Recall that we are given samples drawn from a distribution $f$ and there is a $k$-GMM $\mathcal{M}$ $\epsilon$-close to $f$ in total variation.
The authors first consider the following case.
When the underlying GMM $\mathcal{M}$ satisfies the property that the means of the Gaussians are all not too far away and the variances of the Gaussians are all constant scale, then we can find a $O(\log \frac{1}{\epsilon})$-GMM $\widetilde{\mathcal{M}}$ that is also close to $f$ in total variation.
It is what the authors call well-conditioned.
Since the Gaussians are well-conditioned, achieving this is rather easy by examining the Taylor expansion.
Then, the authors reduce the general case to the well conditioned case via localization.
The high level idea is to look for the intervals such that the union of these intervals covers the union of the significant intervals of the Gaussians in $\mathcal{M}$ where the significant interval of a Gaussian is a long interval covering most probability mass of this Gaussian.
For each interval $I$, the mixture of Gaussians in $\mathcal{M}$ whose significant interval intersects $I$ forms a mixture of well conditioned Gaussians.
On the other hand, the Gaussians in $\mathcal{M}$ whose significant interval does not intersect this interval $I$ are negligible with respect to this mixture of well conditioned Gaussians.
Hence, the authors use dynamic programming to find out these intervals from the samples and use the algorithm for the well conditioned case to output a mixture of $\widetilde O(k)$ Gaussians since the number of these intervals is $\widetilde O(k)$ and there are $\log \frac{1}{\epsilon}$ Gaussians in the mixture for the well conditioned case.

Furthermore, the authors apply the result to solve hypothesis testing for model selection problem and the techniques to solve sparse Fourier problem.


strengths_and_weaknesses: 
Strengths:
- The paper is well-written.
The ideas and the proofs are easy to follow.
- The results is interesting.
The number of Gaussians in the output is $k(\log \frac{1}{\epsilon})^{O(1)}$ while this number is $k(\frac{1}{\epsilon})^{O(1)}$ in the previous works.
This improvement for the dependence on $\frac{1}{\epsilon}$ from a polynomial bound to a logarithmic bound is interesting.


Weaknesses:
- It may just be a minor weakness.
In terms of proof techniques, it seems that the techniques used in this paper are rather standard.
It seems the tools used in the proof are not very surprising. 

questions: 
Questions:
- Is there a sample complexity lower bound showing that no efficient algorithm outputs a mixture of $k\cdot N$ Gaussians where $N$ is sub-poly-logarithmic of $\frac{1}{\epsilon}$ or even independent of $\frac{1}{\epsilon}$ under this setting?

Minor note:
- In line 219, what is $G_0$?
limitations: n/a
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers density estimation of 1-D Gaussian mixtures with unknown number of components $k$. Main point of this submission is to find a 1-D Gaussian mixture hypothesis with at most $\tilde{O} (k) = k \cdot {\rm poly} \log(1/\epsilon)$ components, such that the returned hypothesis is $O(\epsilon)$-close in TV distance to the ground truth. Previous work on the same problem used either larger number of components $O(1/\epsilon^2)$ or used non Gaussian-mixture hypothesis. Main tools used here are polynomial approximation of Gaussian p.d.f. up to degree $O(\log^2 (1/\epsilon))$. It is shown that the techniques shown for 1-D Gaussian mixture can also be used for sparse Fourier reconstruction.  

In my understanding, the proposed algorithm proceeds in two steps: (1) run any improper learning algorithm that outputs a GMM hypothesis with much more number of components (the authors' pick is [Chan et al., 2013] that uses $\tilde{O}(k/\epsilon^2)$ samples) and (2) reduce the number of used components using polynomial approximation of Gaussian p.d.f s. Main subtlety in processing (2) is that if variances (of individual Gaussians) across different components vary a lot, then it is trickier to find polynomial functions that can approximate all p.d.f. s of Gaussian components. Authors proposed a "localization technique" to handle this.
strengths_and_weaknesses: *Strength*

- Presentation of the paper is very clear. It would be even nicer if you have an algorithm box or enumeration block that summarizes the full algorithm.

- The paper also provides a nice application (sparse Fourier reconstruction) of their theoretical findings. 


*Weakness*

- Techniques used in this paper are very specific to the 1-D GMM case, and thus significance of the results is limited. 

- The paper is mostly about the post-processing to reduce the number of components. I wonder if there is anything improved in the density estimation step compared to benchmarks (e.g., Li and Schmidt, 2017).

- If there is any interesting challenge that did not appear in 1-D GMM but should be considered in the sparse Fourier problem, then it might be better fleshed out in the main text. 
questions: 1. About title: I feel that the word 'robust' in title is slightly misleading, because this paper is not really about handling corruptions. 

2. Also, I am not sure 'nearly-proper' is a well-defined terminology to use. We don't know whether $k \cdot {\rm poly} \log (1/\epsilon)$ is the best we can do. Do you have any thoughts on whether O(k) components without log factors possible?

3. The crux of the result is to apply Caratheodory's theorem in polynomial function space. This sounds fairly standard. Could you elaborate on how standard or novel this technique is in density estimation literature? 
limitations: I don't see any negative societal impact.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper addresses the problem of proper learning of 1-d GMMs w.r.t. total variation distance. However, k (number of components) is unknown and we are allowed to output a mixture more than k components (at most polylogarithmic factor more). For non-proper learning, it is already known how to learning 1-d GMMs using piecewise polynomials. Therefore, the main remaining challenge for proper learning is a computational one, not a statistical one. The techniques used to solve the problem are novel and interesting, and compared to the previous work, the number of components of the mixture they find is significantly smaller.

Proof overview: we can assume we have an approximation to the distribution in the form of a piecewise polynomial (based on the previous work). The authors prove that under some conditions (the components are not very thin), there are Gaussian multipliers that can make the mixture "well-conditioned" (concentrated around a mean with similar variances). They then prove that indicator function of every interval can be written as a mixture of Gaussian multipliers. Therefore, the mixture over that interval can be written as the product of the mixture and the indicator. If the interval is such that the conditions for thin Gaussians and the multipliers are met, then the product is a well-conditioned mixture. They then prove that there are intervals that satisfy the condition and most of the mass of mixture is concentrated on those intervals.
strengths_and_weaknesses: Strengths:

+ The paper addresses an important and basic problem in the area of density estimation: proper learning of 1-d GMMs
+ There have been multiple previous attempts on this problem; but this paper significantly improves over them
+ The algorithmic techniques as well as the structural results are novel and interesting
+ The presentation is nice

Weaknesses (minor issues):
+ Sometimes the authors jump in to the technical steps of the proofs without explaining the big picture. Adding a few sentences at the beginning of these subsections can help readability. For example, in the localization section, it is not clear from the beginning that the localization is going to be centered at different components (The reader may assume it is going to be a single localization for the whole mixture). I was not able to understand the techniques thoroughly until I read the instructions in the appendix.
+ Missing discussion of a seemingly very relevant paper by X. Wu and C. Xie, “Improved algorithms for properly learning mixture of gaussians”.
questions: no questions at this stage
limitations: I don't foresee direct negative impact of this theoretical work
review_title: null

Meta-review: metareview: This paper gives significantly improved guarantees for (im)proper learning of Gaussian mixtures in 1-dimension. Given samples from a distribution that is close to a mixture of Gaussians, it gives an polynomial time (and samples) algorithm that outputs a mixture with (slightly) more components that is also close. The paper's contributions are solid both in terms of the result and the techniques involved. So this is a clear accept.  
confidence: Certain
Decision: Accept