Robust Model Selection and Nearly-Proper Learning for GMMs
Authors: Allen Liu
Jerry Li
Ankur Moitra
Venue: NeurIPS 2022 Accept (2022)
Keywords: Mixtures of Gaussians
model selection
proper learning
density estimation

Abstract: In learning theory, a standard assumption is that the data is generated from a finite mixture model. But what happens when the number of components is not known in advance? The problem of estimating the number of components, also called model selection, is important in its own right but there are essentially no known efficient algorithms with provable guarantees.  In this work, we study the problem of model selection for univariate Gaussian mixture models (GMMs). Given $\textsf{poly}(k/\epsilon)$ samples from a distribution that is $\epsilon$-close in TV distance to a GMM with $k$ components, we can construct a GMM with $\widetilde{O}(k)$ components that approximates the distribution to within $\widetilde{O}(\epsilon)$ in $\textsf{poly}(k/\epsilon)$ time.  Thus we are able to approximately determine the minimum number of components needed to fit the distribution within a logarithmic factor.  Moreover, by adapting the techniques we obtain similar results for reconstructing Fourier-sparse signals.  Prior to our work, the only known algorithms for learning arbitrary univariate GMMs either output significantly more than $k$ components (e.g. $k/\epsilon^2$ components for kernel density estimates) or run in time exponential in $k$. 

Robust Model Selection and Nearly-Proper Learning for GMMs
Allen Liu MIT
Jerry Li Microsoft Research Redmond, WA 98052 jerrl @mmccrooffe com
Ankur Moitra MIT Cambridge, MA 02139 moi rarmmmmmi edu
Cambridge, MA 02139 cliu568emi t. edu
Abstract
In learning theory, a standard assumption is that the data is generated from finite mixture model. But what happens when the number of components is not known in advance? The problem of estimating the number of components, also called model selection, is important in its own right but there are essentially no known efficient algorithms with provable guarantees let alone ones that can tolerate adversarial corruptions. In this work, we study the problem of robust model selection for univariate Gaussian mixture models (GMMs). Given poly(k/cc samples from a distribution that is c-close in TV distance to GMM with & components, we can construct GMM with Ö(k) components that approximates the distribution within (c)) in poly (k/c) time. Thus we are able approximately determine the minimum number of components needed to fit the distribution within logarithmic factor. Prior to our work, the only known algorithms for learning arbitrary univariate GMMs either output significantly more than & components (e.g. k/e² components for kernel density estimates) or run in time exponential in k. Moreover, by adapting our techniques we obtain similar results for reconstructing Fourier-sparse signals.
Introduction
Many works in learning theory operate under the assumption that the data is generated from a finite mixture model, and furthermore that the number of components is known in advance. But what happens when the number of components is not known in advance? The problem of estimating the number of components called model selection and has been intensively studied in statisties for over fifty years [Neyman and Scott 1966). Indeed, in many scientific applications, it is the central issue. Consider the motivation given by Chen et al. (2004): genetics, we might have continuous -aauued valued trait, like height, that can be measured across a population and we want to understand its genetic basis. But is the underlying genetic mechanism simple or complex? genes or are there many more genes waiting to be discovered that each have small effect on it?
controlled by just a few
From a statistical perspective, what makes model selection challenging is that the standard analysis of the likelihood ratio test breaks down because of lack of regularity and non-identifiaility [Hartigan
1985]. Despite many attempts [Ghosh and Sen 1984 Lo al.) 2200] Huang al. 2017] and rejoinders [Jelfries] 2003), even understanding the asymptotic distribution of the likelihood ratio statistics has remained a long-standing challenge the field [Kasahara and Shimotsu
2015 From
an algorithmic standpoint, the problem is even more difficult.
In this work, study the problem of robust model selection for one-dimensional Gaussian mixture models with 1: components (k-GMMs for short). A natural approach for this problem is via agnostic proper learning, where the task is to, given samples from unknown distribution, output the best k-GMM approximation to this distribution in TV distance. An efficient agnostic proper learning
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

algorithm, combined with standard tools from hypothesis testing, would immediately yield an algorithm for model selection.
Unfortunately, while there are many efficient algorithms for learning one-dimensional GMMs, they all fall into of several categories: (1) They assume some strong separation conditions on the components so that the samples can be clustered based on which component they were generated
from. (2) They solve the harder problem of learning the parameters of the components. which information-theorticcal
requires the number of samples to be exponential in k [Moitra and Valiant 2010). (3) They employ brute-force search [Daskalakis and Kamath, 2014, Acharya et al.) 2014 or solve system of polynomial inequalities [Li and Schmidt,, 2017]. and run in time exponential
in k. (4) They leam an approximation that either not GMM, e.g. piece-wise polynomial
approximation [Chan et al., 2013 Acharya et al.) [017] or output GMM where the number of
components is much larger than & Wu and X 2018] Devvooe and Lugosi 2012] Bhaskara et al.
2015). (5) They assume that the components in the GMM have the same or similar variances and means not too far apart so that there is a good approximation to the density with just a logarithmic number of components [Wu and Yang 2018 Polyanskiy and Wu 2020J. In all cases, these guarantees are insufficient for efficient model selection, and/or yield a trivial approximation to the number of components in GMM except in restricted settings. In this work, we ask: Are there efficient algorithms for learning arbitrary one-dimensional GMMs that output an approximation with ((k) components? Relatedly: Are there efficient algorithms for approximating the number of components in GMM? We give efficient algorithms whose running time and sample complexity are polynomial in & for both of these problems, and also the related problem of reconstructing Fourier-sparse signals with an unknown number of frequencies.
1.1 Learning and model selection for GMMs
Our main result is a new robust learning algorithm for one-dimensional GMMs. We show:
Theorem 1.1. Let k. e > 0 be parameters and let f be a distribution such that drv(M, f) S for some unknown mixture of Gaussians M = ====(Ga wnG +...... + wyGr,, Assume that we are given (kk/E²) samples from f. Then there is an algorithm that runs poly(k/c) time and with probability 0.9 (over the random samples), outputs mixture of ((k) Gaussians, M, such that
In contrast to other known learning algorithms (discussed earlier), our learning algorithm works for arbitrary GMMs, runs in polynomial time and uses a polynomial number of samples, and while does not output a GMM with exactly i components, it does the next best thing: it outputs a GMM with at most a polylogarithmic factor more components.
As a corollary, we also give an algorithm for robust approximate model selection for GMMs. The connection to model selection is that when our algorithm fails to find a GMM with Ō(k) components that fits the data we can be assured that there must more than & components to begin with. Notice in particular that improper approximations by themselves do not suffice for the model selection problem, as a good improper approximation could exist even if the distribution is far from any GMM with Ō(k) components.
Theorem 1.2. Let k > 0 be parameters are given. Let F1 be the family of distributions that are c-close to a ks- k-GMM with i components (in TV distance). Let F2 be the family of distributions that are not (ce)-lose to any GMM with Ö(k) components. There is an algorithm that given poly (k/E) samples from a known distribution D, runs in poly(k/e) time, and outputs 1 if E Fr and outputs 2 D E F2 both faiture probability at most 0.2.
Remark. Even if the distribution DD completely unknown and we are only given samples from
the above result still holds as long as D is somewhat well behaved (note that such an assumption is
necessary as hypothesis testing with respect to total variation distance without any assumptions on D is impossible). In particular we can use piecewise polynomial approximation (Chun et al. 2013) or kernel density estimates ( Terrell and Scott 1992) to learn a distribution DD' that close to D that we have an explicit form for and then run the hypothesis test using D'.
2

---

1.2 Fourier sparse interpolation
Our techniques also immediately apply to the problem of Fourier sparse interpolation, where the goal is to interpolate signal based on noisy measurements of it at a few points [Chen et 2016]. We say that a function M is (k, C*) simple it can be written in the form
M(t) Σ age 2 j=1
where additionally Σ, layl I C. In other words, function is (kc, C)) simple if it is k-sparse in the Fourier domain, and its Fourier coefficients are bounded in & by C.
We consider the following problem. We get query access to function f(t) = M(() (t) at any point in the interval 1], where M is (k, C*) simple and has all frequencies in the interval [-F, F). and r()) is noise that will assume is bounded in L2 norm. The goal is compute Fourier-sparse approximation MMt)) that close to f(),, in the sense that its error is comparable to that of M(t). Recently Chen et al. [0166] showed how to construct an approximation M(()) that satisfies
[I((() - M(OIl S 1lx(0)l22 + (|IM()))2
where the L2 norm is taken over the interval [-., Their algorithm works for any 0 and uses poly(k, 1/e) log F measurements. Moreover the M(t) that they output is poly(k: log 1/c)- Fourier sparse. Similarly to the GMM setting, natural goal is to perform robust interpolation but with tighter bounds on the number of frequencies. We show:
Theorem 1.3. Let J.M be above where M is (k, 1)-simlle. Then for any desired accuracy e and constant с >> in poly(k, log 1/e) log F' queries and poly(k/c, log 1/e) log time, we can output a function M such that with probability
2 -2(())
1. .M is Ö(k) ((k))Foourer sparse with [| S Ö(k)
2. - IM f|2 O + M
Remark. Note the constraints [| and [M translate into bounds on the sizes of the coefficients of the exponentials in MM and M respectively.
The natural open question left by our work is to improve the sparsity bounds, both for interpola- tion/learning and model selection. In principle could be possible that there are efficient algorithms for these problems, however it now seems somewhat unlikely. Even without noise, learning a Gaus- sian mixture model with & components without separation condition in time poly(k: (k: 1/c) is open. From our work (see Section 2 we see that even in the well-conditioned case this is equivalent to finding a non-trivially sparse solution to a system polynomial equations where there seems to be no structure that makes algorithmic search better than brute-force possible. Moreover, this question has already been open for many years, but there hasn't 't been any progress on proper learning. Thus, we conjecture that both the learning and model selection problems are computationally hard if we not allowed to relax the number components.
1.3 Related work
There is a vast literature on the three problems we consider. Here we will give more detailed review of related work.
Learning Mixtures of Gaussians and Model Selection Since the pioneering work of Pearson [894], mixtures of Gaussians have become one of the most ubiquitous and well-studied generative models in both theory and practice. Numerous problems have been studied on the context of
learning mixtures of Gaussians, including clustering (Dasguptal 1999 Vempala and Wang 2004 Achlioptas and McSherry] 2005 Dasgupta and Schulman, [007] Arora and Kale, [007]] Kumar and
Kannan] Awasth Awasthi and Sheffet 2012, Mixon al.. [017 (Hopinn and Lij 2018 Kothari et al.
2018 Diakonikolas et al. 2018 learning in the presence of ad adversarial noise in high dimensional
3

---

settings DDiakonikolas et al. 2018 Hopkins and Li| 22018. Kothari et al. 2018 Bakshi et al. 2020
Diakonikolas et al. [0200] Kane 2021 Liu and Moitra [020 [202]], parameter estimation
Kalai
et al. 2010 Belkin and Sinha 2015 Moitra and Valiant [010 Hardt and Price 2015]
learning in
smoothed settings [Hsu and Kakade 2013] Anderson et al. 2014 Bhaskara et al. 2014 Ge et al.
2015]. and density estimation [Devroye and Lugosi 2012 Chan et al., 2014 Acharya et al. 2017].
Of particular interest us the line of work on proper learning [Feldman et al. 2006 Acharya ct al. 2014, Li and Schmidr, 2017 Ashtiani et al.) 2018]. where the goal is to output a mixture of k-Gaussians which close in total variation to the underlying ground truth. Unfortunately, while the sample complexity of these algorithms is usually polynomial, the runtime for all known approaches is exponential in k.. In contrast, our runtimes are polynomial, albeit for a relaxed version of the problem. where the output is allowed to be mixture of k' Gaussians, for k' >> k.
For this "semi-proper" regime, efficient algorithms are known, albeit either only for restricted settings, or with significantly worse quantitative results than we achieve. In the "well-conditioeed" case, where the means are close together, and the variances of all the components are comparable, the aforementioned work of [Wu and Yang, 2018 Polyanskiy and Wu 2020) demonstrates that the nonparametric MLE can efficiently obtain an estimate using only logarithmically many pieces. However, the nonparametric MLE is not suited for the general setting, where the means could be far apart, and variances could be very different, and will not converge in general. Moreover, while nonparametric MLE is robust to perturbations in KL, it is not robust to perturbations in total variation distance, as we consider here.
For the general case, by using kernel density estimates, one can achieve approximation using k' Okk/cC) for some constant C DDerroye and Lugosi 2012). Similarly Bhaskara et al. [2015 achieves error using K' = O(k/E") pieces. That is, for both of these approaches, they require a number of pieces which scales polynomially with 1/e. In comparison, our dependence on in terms of the number of pieces is logarithmic.
As discussed previously, there are strong connections between proper learning and model selection [Neyman and Scott [966]
|Hrrtgan] 1985| Ghosh and Sen 1984 Lo et al. [001 Jeffries] [2003 Kasa
hara and Shimotsu 2015 Huang et 20.7]. Related notions have been considered in distribution
testing [Parnas et al. 2006 Valiant and Valiant 2010a b 201 I Jiao et al.
2016 2017 Han et al.
2016) and testing properties of boolean functions Diakonikolas al. 2007 Iyer al. 2021
Continuous Time Sparse Fourier Transforms Sparse Fourier transforms in the continuous
setting, also known sparse Fourier transforms off the grid, has been the subject of intensive study. Indeed, the first algorithm for this problem dates back to (Pronyy [1955. Modern algorithms include
MUSIC [Schmidt 1982. ESPRIT [Roy al. 1986]. maximum likelihood estimators (Bresler and
Macovski 1986). convex programming based methods [Candès and Fernandez-Grrana 2014 and
the matrix pencil method Mooira 2015).
Most of these works, especially those that work in a noisy setting, require a frequency gap. Moreover they require more than k samples (their bound usually depends on the frequency gap), even if the underlying signal is k-sparse in the Fourier domain. recent line of work has focused on the problem of improving the sample complexity in particular getting bounds which only depend & with
runtimes that are polynomial in le [Fannjiang and Liao 2012 Duarte and Baraniuk 2013 Tang
et al. 2013 2014 Boufounos al. 2015 Huang and Kakade 2015 Price and Song 2015 The setting where there is no gap and there is noise is particularly challenging. One approach is to relax the definition of a frequency gap, and require it only between "clusters" of frequencies (Batenkov ett al. 2020). Another line of work [Avron et al., 2019 Chen and Price 2019) shows how to output hypothesis which is k-sparse without any gap assumptions and with sample complexity which is polynomial in k. However these methods run in exponential time, As we previously discussed, the most relevant works us are Chen et al. (2016) and Chen and Price [2019), which give an algorithm whose running time and sample complexity are polynomial in A that works without any gap assumptions, but for a relaxation where we are allowed to output ((.2)-Fourrier sparse signal.
2 Technical overview
We now give an overview of our approach. We will focus on just the GMM case this overview. Our approach for sparse Fourier interpolation follows a very similar outline. We first present our

---

techniques assuming that we have explicit access to f. In Section 2.3 we show how to reduce to this case when we are only given samples. In other words, the problem as follows: we are given function f. and we want to find sparse approximation to f as nonnegative sum of Gaussians, i.e. we want to write
f ~ a + + G.
with n. small, where each G2 is Gaussian.
2.1 Well-conditioned case
We first solve the "well-conditioned" case. Roughly, we say that a GMM is well-conditioned if the variances of the components are all constant scale and the means are all not too far from zero. Formally, we have the following definition:
Definition 2.1. We say a Gaussian G N o²) ) 8- d-well-conditionel if lul S and lo² 1| S Furthermore say a mixture of Gaussians M = wiG1 + ...... w&Ga is E-well-conditioned if all of the components GI...., G2 are Awell-conditionel
Naturally, our techniques also apply to a shared scaling and/or translation of the components, but will ignore this for now. Earlier work of [Wu and Yang 2018 Polyanskiy and Wu 2020] proved
an important structural result that well-conditioned GMM can be e-approximated by mixture with Olog 1/c) components. However we will want robust and algorithmic version: particular, instead of requiring the distribution to be exactly a coleicondi GMM, we will only require that be close in total variation distance. Even in this setting, with some level of model misspecification. we want an efficient algorithm for constructing an approximating GMM with few components. To this end, a key result, proved Section A is:
Lemma 2.2. Lete 0 be parameter. Assume drv(f, M) S e where M = W1G1+ +....... ..... + wyGr is condiioocod mixture of Gaussians. Then we can compute, in poly(1/c) time, a mixture M of at most O(log 1/c) Gaussians such that drv(M, < Ö(e).
given access distribution such that
Our approach departs from the moment matching framework of Wu and Yang 2018 Polyanskiy and Wu (2020). Instead we take the probability density function of any well-conditioned Gaussian Gj. We can expand as a Taylor series around 0 of the form
(2)
Gz(z) = cG
11
2!
for some coefficients cG We can then associate it with the vector CG; (cG, (6-1)) of length e = Olog 1/e). Then, for any well-conditioned mixture M = a1 G1 + ... + 0g Gn, we can associate it with the corresponding convex combination of the vectors of its components, i.e., define cM = aicG, + ...... +... GgCG, E R.
The point of this is the following implication: if two well-conditioned mixtures get mapped vectors which are close, then these two mixtures must be close total variation distance. The intuition is that when write down the L2 distance between the two mixtures, because the Taylor coefficients of Gaussians decay exponentially fast, the contribution of terms with degree / Ó(log 1/c) to the integral becomes negligible.
Now, we can associate the set of well-conditioned mixtures with a convex body in O 1/e)- dimensions, where the vertices of the convex body are given by single Gaussians. Consequently we can use Carathcodory's 's thcorem to argue that any point within this body can be approximated as an Olog 1/ 1 convex combination of the vertices, equivalently, any well-conditioned mixture can we approximated by a mixture of Ollog 1/e) well-conditioned Gaussians.
It remains to demonstrate how to actually find this sparse mixture of Gaussians. Naively, the number of vertices infinite, there are infinitely many well-conditioned Gaussians. However, it not too hard to show that if we consider slight coarsening of this body by only taking the vertices to be the vectors associated to the well-conditioned Gaussians which belong in some poly poly(1/e)-sized net, then the quality of our solution only degrades by constant multiplicative factors. At this point we can appeal to standard results in convex optimization to find the desired sparse approximation. We defer the details of this argument to Section
5

---

2.2 Localization
After solving the well-conditioned case, the next step is to reduce the general case the well- conditioned case via localization. We begin with an important definition.
Definition 2.3 (Gaussian Multiplier), For parameters μ, G, we define
(==
M1,0²(x)
(2)
20
L.e. it is Gaussian scaled that its maximum value is 1.
Gaussian multipliers will be crucial in the localization step. Now assume that f can be written as some unknown k-sparse combination, say
f G1 + agGr
We can then modify f. e.g. by multiplying by Gaussian multiplier M, Heuristically, this operation changes the coefficients a1,- a1...., dg in a predictable way. Namely, the coefficients dz of Gaussians G, that are far from N(u, o²) are exponentially attenuated based on the distance to (u, o²). This effectively "localizes" the mixture. More formally, Claim 2.4. We have the identity
fe--n 2oof N N HHO + m10² ofo²
M (1)1,
e
of of +
VI+ of
Proof. We prove the above through direct computation.
(z)) =
(0-
20
(x-R)) 20
1
( (
+
x
01
2x
21V2T
2
0
(M1 n1)
01 2m
exp
2
1/
02 +
o
1 +
2 of + 0²
of
[u) x²²
H + 110²
Fon
+112
0i0²
2io +0
N
of+02 of
72
+
G2
The hope is that this will leave with only components that not too far from each other exactly the well-conditioned case which we already know how to solve. If the variances of all of comparable, then this is indeed the case. However, additional complications arise when one of the components G = Nu,, of)) has variance o; < a because this component will still have much smaller variance than the others after localizing. Nevertheless, carefully localize at different scales, using smaller variance Gaussian multipliers to localize around smaller variance components so that all of the localized mixtures are well-conditioned.
the components
show that can
The main remaining question is to select a good family of localizations so that we can then fully reconstruct the original mixture from the localized mixtures. Each localized mixture will cost us O(log 1/e) components, and therefore we must use most Ō(k) different localizations. When all of the variances of the Gaussians are not too dissimilar, we can do so by leveraging the following structural result, which states that one can e-approximate the constant function using a sum of evenly spaced Gaussians with variance 1 and spacing (log 1 - (or smaller). The intuition behind this observation is that the Fourier transform of a Gaussian is also a Gaussian, which has exponential tail decay.
Lemma 2.5. Let < < 0.1 be a parameter. Let e be real number such that 0 < c S (log 1/e) -1/2 Define
f(x) = Σ
Mz)o,o2(z).
2xx
=0
Then 1 -- s 1+ for all z.

---

Proof. WLOG = 1. Now the function f is e-periodic and even, so we may consider its Fourier expansion
2TT
4TT
f(x) dg + 2a, cos
+ 22g cos
and we will now compute the Fourier coefficients. First note that
ao [ f(z)d=
Mo, (z)dz= 1.
00
v 2m
c(++1)
Next, for any j21 1,
aj {- f(z) cos
2xjj dr
cj
(2zjz
Mo.1(1) cos
dr
2T
c(f+1)
1
2
2x2,2
+
dr
2
2
where in the above we use the notation clear that
1-
Using the assumption that c S (log 1/e)
-1/2,
Σ
20
2x2,2
2
S
so we deduce that for any æ,
2x
lf(x) - 1| 2| |02| + ....
In other words, the function f is between 1 and 1 + everywhere and we are done.
In light of the above lemma, we can use a set of evenly spaced Gaussian multipliers and simply sum the different localized mixtures. Note that suffices to use ((k) different localizations because we only need to sum over the Gaussian multipliers that have some nontrivial overlap with one of the k true components (since for Gaussian multipliers that are far from all of the components, the localized mixture will be approximately 0).
To handle the fully general case, when the variances of the Gaussians are unbounded, we need generalization of the previous lemma that allows us to c-approximate the indicator function of an interval with sum of Ollog" 1/c) Gaussians. The proof of this generalization is in Section B
Definition 2.6 (Significant Interval). For a Gaussian multiplier M,,02, we say the C-significant interval of M is [u- Co, n + Co). We will use the same terminology for Gaussian N N(,,
Theorem 2.7. Let be a positive real number and O < < 0.1 be a parameter. There is a function f with the following properties
1. f can be written a linear combination of Gaussian multipliers
f(x) = w/ M je1 o² (x) + ... + Wyy M Pn (I)
where Ollog* 1/e) and 0 < w1 w..... Wn <
2. The 10g/lo I/essiniifcan intervals of all of the Mpn.o are contained in the interval
e-),+e) +]
3. (.05(()) < for all x
4. 1-c5 f() for all x in the interval [-1,
5. 0 f()) for 2 (1 + e)l and x < -(1 +1 +el
We combine this structural result with a dynamic program which allows us to efficiently choose the scales at which to localize. Putting all of these pieces together yields our full algorithm, assuming we have access to the pdf of the unknown function. We show how eliminate the need for pdf access below and present our full algorithm in complete detail in Section C
7

---

2.3 Abstracting away the samples
In the previous sections, we have assumed that we have access the underlying pdf function Typically, however, we only have sample access to the unknown distribution. To rectify this, we will use the improper learner [Chan al. 2013) (see Theorem 37) whose output a piecewise polynomial. We can then only work with this piecewise polynomial, which is an explicit function that we can then perform explicit computations with.
Definition 2.8. function f is t-piecewise degree d if there is partition of the real line into intervals ..(()) of degree at most d such that for all E [t). f(x) = (x) I1,...,4, .I and polynomials (.)......)............... (0(2) on the interval 4.
The work in Chan et al. 2013 guarantees to learn piecewise polynomial f' that is close to M in T, distance when given O samples (and they also show that this sample complexity is essentially optimal).
Theorem 2.9 (Chan et al. 2013)). Let M - w GiGi + WGGr be an unknown mixture of Gaussians and f a distribution such that d & There is an algorithm that, given (kke²²) samples from f. runs in poly(k/c) time and returns pieeceiie degree Ollog 1/c) function f' such that with 0.9 probability (over the random samples),
I1 - S O(e).
For technical reasons, will need few simple post-procees poos-prccsssing steps after using Theorem 2.9 We can ensure that the output hypothesis f' always nonnegative by splitting each polynomial into positive and negative parts and zeroing out the negative parts (since this will not increase the L' error). Finally, we can re-normalize so that the output f" is actually a distribution. This renormalization at most doubles the L error. Thus have:
Corollary 2.10. Let M W1G1 +... w&Gr be unknown mixture of Gaussians and f distribution such that dTv(J,M) S c. There is an algorithm that, given (k/{2) samples from 'D, runs in poly(kfc) time and returns an O(k log 1 1/c)-piecewiss degree Olog 1c) function f' such that f' is distribution and with 0.9 probability (over the random samples),
dTv(f, 5(())
2.4 Hypothesis testing for model selection
We now show how our result for model order selection, Theorem 1.2 follows immediately from com- bining Theorem I.I with standard procedure for testing the TV-distance between two distributions from samples (see Yatracos (1985)).
Claim 2.11. Let D1, D2 be two distributions for which we have explicitly computable density functions. Let T > 0 be parameters. Assume that we are given O(1/e² log 1/7) samples from D and can efficiently sample from Dz. Then poly (1/e log 1/7) time, we can compute d such that with probability 1 T-T,
dd- (d cc
1.2 can run the algorithm in Theorem with parameters k, to obtaín an output distribution M that mixture of (k) Gaussians. We can then use Claim 2.11 with parameters e, 0.01 to measure the TV-distance between M and D (note that have explicit access to the pdf of D) and output 1 or 2 depending on if our estimate of the TV distance is less than (c)). Combining the guarantees of Theorem [.I and Claim 2.11 ensures that our output satisfies the desired properties.
Proof of Theorem
2.5 Sparse Fourier
We now briefly describe how our techniques can be used for sparse Fourier reconstruction. Recall that the problem is to, given query access a function f on [-1, which approximately k-Fourier sparse, approximate with an (kk)-Fourir sparse function. As before, we first abstract away the query access, by leveraging the following result from Chen al. 20166)

---

Theorem 2.12 (Theorem 1 in Chen et al. 2016)). ). Let f be a function defined on [-1, 1] and assume we are given query access to J. Let M be a function that is (k. 1)-simpll and has frequencies in the interval [- -F; F. Then for any desired accuracy 6, in poly(k, log 1/c) )) log F samples and poly(k, log 1/c) log" F time, we can output function f' such that with probability 1 - 2- 2-9())
1. f' is (poly(k, log 1/6), exp(poly(k (k; log 1/)))- simple
2.
S -1
(
2
Remark. While the bound the coefficients of f' is not explicitly stated in Theorem 1.1 in Chen et al. (0166) it immediately follows from the proof.
Our algorithm for postprocessing this into ((k))Fourita sparse signal follows roughly the same steps as in the Gaussian case. First, we show that in certain "well-conditioned" regime, namely, when the frequencies are not too dissimilar, there is a signal using Olog 1/e) frequencies which approximates the function. To handle the general case, we use localizations based on carefully chosen kernels to reduce every signal to a sum of well-conditioned signals (at least, approximately).
One important distinction between the GMM and sparse Fourier reconstruction setting we highlight that in the latter, the goal usually to have runtimes which scale logarithmically with 1/c, whereas in the GMM setting, poly(1/e) sample complexity and thus runtime is unavoidable. However. our naive method of solving the well-conditioned case required constructing a net of poly(1/e) many Gaussians, and thus required poly(1/ /c) runtime. To circumvent this difficulty, we demonstrate that in fact this can be improved, and that by being more careful, and choosing the (much smaller) set of vertices based on the Chebyshev points, we can in fact improve this runtime significantly. See Sections D and
E for a full treatment of our algorithm.
2.6 Paper organization
The remainder of the paper will be devoted to proving Theorem 1.1 our main result for GMMs and Theorem 1.3 our main result for sparse Fourier reconstruction. Due to space constraints, the remaining parts are deferred to the appendix. We first present the proof of our result for GMMs. In Section localization which we will then use in Section prove our full result for GMMs. We then present the proof of our main result for sparse Fourier reconstruction which follows a very similar outline. We deal with the well cell-conditioned case in Section then the general case in Section Appendix contains several basic tools that will be used throughout the paper.
A] we deal with the well-conditioned case. In Section we present some tools for
Acknowledgments and Disclosure of Funding
AL was supported in part by an NSF Graduate Research Fellowship and a Fannie and John Hertz Foundation Fellowship. AM was supported in part by Microsoft Trustworthy AI Grant, NSF CAREER Award CCF-1453261, NSF Large CCF1565235, a David and Lucile Packard Fellowship and ONR Young Investigator Award.
3 Ethics and broader impact
Our work is purely theoretical and we do not think there are any ethical issues or potential negative societal impacts.
References
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Near-optimal- sample estimators for spherical gaussian mixtures. arXiv preprint 402 2014.
Jayadev Acharya, Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt. Sample-optimal density estima- tion in nearly-linear time. Proceedings of the Twenty-Fighte Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1278-1288 SIAM, 2017.

---

Dimitris Achlioptas and Frank McSherry. On spectral learning of mixtures of distributions. In International Conference on Computational Learning Theory, pages 458 -69.. Springer, 2005.
Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, and James Voss. The more, the merrier: the blessing of dimensionality for learning large gaussian mixtures. In Conference on Learning Theory, pages 1135-1164 PMLR, 2014.
Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach semidefinite programs. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California. USA. June 11-13, 2007, pages 227-236- 2007.
Hassan Ashtiani, Shai Ben-Davic Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pages 1415-3425, 2018.
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. A universal sampling method for reconstructing signals with simple fourier transforms. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Compuling, pages 1051-1063, 2019.
Pranjal Awasthi and Or Sheffet. Improved spectral-norm bounds for clustering. In Approxima- tion, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 37-49. Springer, 2012.
Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M Kane, Pravesh K Kothari, and Santosh Vempala. Robustly learning mixtures of k arbitrary gaussians. arXiv preprint arXiv:2012.02119, 2020.
Dmitry Batenkov, Laurent Demanet, Gil Goldman, and Yosef Yomdin. Conditioning of partial nonuni- form fourier matrices with clustered nodes. SIAM Journal on Matrix Analysis and Applications, 41 (1):199-220, 2020.
Mikhail Belkin and Kaushik Sinha. Polynomial learning of distribution families. SIAM Journal on Computing, 44(4):889 -911 2015.
Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan. Smoothed analysis of tensor decompositions. In Proceedings of the forty-sixth sixth annual ACM symposium on Theory of computing, pages
2014.
Aditya Bhaskara, Ananda Suresh, and Morteza Zadimoghaddam. Sparse solutions nonnegative linear systems and applications. In Artificial Intelligence and Statistics, pages 93-92. PMLR, 2015.
Petros Boufounos, Volkan Cevher, Anna C Gilbert, Yi Li, and Martin J Strauss. What's the frequency, kenneth?: Sublinear fourier sampling off the grid. Algorithmica, 73(2):261-28) 2015.
Yoram Bresler and Albert Macovski. Exact maximum likelihood parameter estimation of superim- posed exponential signals noise, IEEE Transactions on Acoustics, Speech, and Signal Processing, 34(5):1081-1089 1986.
Emmanuel Candès and Carlos Fernandez-Grands Towards mathematical theory of super- resolution. Communications on pure and applied Mathematics, 67(6))906-955 2014.
Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun. Efficient density estimation via piecewise polynomial approximation. 2013.
Siu-On Chan, Ilias Diakonikolas, Rocco Servedio, and Xiaorui Sun. Efficient density estimation via piecewise polynomial approximation. In Proceedings the forty-sixth annual ACM symposium on Theory of computing, pages 604-613, 2014.
Hanfeng Chen, Jiahua Chen, and John D Kalbfleisch. Testing for finite mixture model with two components. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 66(1): 95-115, 2004.
10

---

Xue Chen and Eric Price. Active regression via linear-sample sparsification. In Conference on Learning Theory, pages 663 695. PMLR, 2019.
Xue Chen, Daniel M Kane, Eric Price, and Zhao Song. Fourier-sparse interpolation without a frequency gap. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 741-750. IEEE, 2016.
Sanjoy Dasgupta. Learning mixtures of gaussians. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 634-644. IEEE, 1999.
Sanjoy Dasgupta and Leonard Schulman. A probabilistic analysis em for mixtures of separated, spherical gaussians. Journal of Machine Learning Research, 8(Fcb):203-226, 2007.
Constantinos Daskalakis and Gautam Kamath. Faster and sample near-optimal algorithms for proper learning mixtures of gaussians. In Conference on Learning Theory, pages 1183-1213. PMLR,
2014.
Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer Science & Business Media, 2012.
Ilias Diakonikolas, Homin K Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A Servedio, and Andrew Wan. Testing for concise representations. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 549-558. IEEE, 2007.
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1047-1060, 2018
Ilias Diakonikolas, Samuel B Hopkins, Daniel Kane, and Sushrut Karmalkar. Robustly learning any clusterable mixture of gaussians. arXiv preprint
2020.
Marco F Duarte and Richard G Baraniuk. Spectral compressive sensing. Applied and Computational Harmonic Analysis, (5(1):111-129 2013.
Albert Fannjiang and Wenjing Liao. Coherence pattern -gided compressive sensing with unresolved grids. SIAM Journal on Imaging Sciences, (1):1199-003 2012.
Jon Feldman, Rocco Servedio, and Ryan O'Donnell. Pac learning axis-aligned mixtures of gaussians with no separation assumption. In International Conference Computational Learning Theory, pages 20-34. Springer, 2006.
Rong Ge, Qingqing Huang, and Sham M Kakade. Learning mixtures of gaussians in high dimensions. In Proceedings of the sorty-sevetth annual ACM symposium on Theory of computing, pages 761-770, 2015.
Jayanta K Ghosh and Pranab Kumar Sen. On the asymptotic performance of the log likelihood ratio statistic for the mixture model and related results. Technical report, North Carolina State University. Dept. of Statistics, 1984.
Venkatesan Guruswami and David Zuckerman. Robust fourier and polynomial curve fitting. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 751-759. IEEE, 2016.
Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Minimax rate-optimal estimation of divergences between discrete distributions. In Proceedings of the 2016 International Symposium on Information Theory and its Applications, ISITA '16, pages 256 260, Washington, DC, USA, 2016. IEEE Computer Society.
Moritz Hardt and Eric Price. Tight bounds for learning a mixture of two gaussians. In Proceedings of the
annual ACM symposium on Theory of computing, pages 753-760, 2015.
JA Hartigan. A failure of likelihood asymptotics for normal mixtures. In Proc. Barkeley Conference in Honor of J. Neyman and J. Kiefer, volume 2, pages 807-810, 1985.

---

Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1021- 1034, 2018.
Daniel Hsu and Sham M Kakade. Learning mixtures of spherical gaussians: moment methods and spectral decompositions. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 11-20, 2013.
Qingqing Huang and Sham M Kakade. Super-resolution off the grid. arXiv preprint arXiv:1509.0794 2015.
Tao Huang, Heng Peng, and Kun Zhang. Model selection for gaussian mixture models. Statistica Sinica, pages 147-169, 2017.
Vishmu lyer, Avishay Tal, and Michael Whitmeyer. Junta distance approximation with sub-exponential queries. In Electron. Colloquium Comput. Complex., volume 28, page 4, 2021.
Neal Jeffries. A note on 'testing the number of components in a normal mixture'. Biometrika, 90 (4):991-999) 9944, 2003.
Jiantao Jiao, Yanjun Han, and Tsachy Weissman. Minimax estimation of the L distance. In Proceedings of the 2016 IEEE International Symposium on Information Theory, ISIT '16, pages 750-754, Washington, DC, USA, 2016. IEEE Computer Society.
Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions. IEEE Transactions Information Theory, 61(5):2835-288) 2885, 2017.
Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Efficiently learning mixtures of two gaussians. In Proceedings of the forty-second ACM symposium Theory of computing, pages 553-562, 2010.
Daniel M Kane. Robust learning of mixtures of gaussians. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1246-1258. SIAM, 2021.
Hiroyuki Kasahara and Katsumi Shimotsu. Testing the number of components in normal mixture regression models. Journal of the American Statistical Association, 110(512):1632-16)) 2015.
Pravesh K Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1035-1046, 2018.
Amit Kumar and Ravindran Kannan. Clustering with spectral norm and the k-means algorithm. In 2010 IEEE 51 Annual Symposium on Foundations of Computer Science, pages 299-308. IEEE, 2010.
Jerry Li and Ludwig Schmidt. Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities. In Conference Learning Theory, pages 1302-1382. PMLR, 2017.
Allen Liu and Ankur Moitra. Setting the robust learnability of mixtures of gaussians. arXiv preprint wrXiv:2011.03622 2020.
Allen Liu and Ankur Moitra. Learning gmms with nearly optimal robustness guarantees. arXiv preprint arXiv:2104.096 2021.
Yungtai Lo, Nancy R Mendell, and Donald B Rubin. Testing the number of components in normal mixture. Biometrika, 88(3):667-778, 2001.
Dustin G Mixon, Soledad Villar, and Rachel Ward. Clustering subgaussian mixtures by semidefinite
programming. Information and Inference: A Journal of the IMA, 6(4):389-411 2017.
Ankur Moitra. Super-resolution, extremal functions and the condition number of vandermonde matrices. In Proceedings of the sereth annual ACM symposiun on Theory of computing, pages 821-830, 2015.
12

---

Ankur Moitra and Gregory Valiant. Settling the polynomial learnability of mixtures of gaussians. In 2010 IEEE 51 Annual Symposium on Foundations of Computer Science, pages 33-102. IEEE, 2010.
J Neyman and Scott. On the use of e (a) tests of composite hypotheses. Bulletin de L'Institut International de Statistique, 41:477-497, 1966.
Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 1216):1012-1042, 2006.
Karl Pearson. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, 185:71-110, 1894.
Yury Polyanskiy and Yihong Wu, Self-regularizing property of nonparametric maximum likelihood estimator in mixture models, 2020. URL.
08244
Eric Price and Zhao Song. A robust sparse fourier transform in the continuous setting. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 583-600. IEEE, 2015.
Prony. Essai experimental et analytique sur les lois de dilabilite des fluides elastiques et sur celles de la force expansive de la vapeur de l'eau et de la vapeur de palcool a differentes temperatures. Journal de I'Ecole Poly technique, pages 24-76, 1795.
Theodore J Rivlin. Chebyshev polynomials. Courier Dover Publications, 2020.
Robert Roy, Arogyaswami Paulraj, and Thomas Kailath. Esprit-a subspace rotation approach to estimation of parameters of cisoids in noise. IEEE transactions acoustics, speech, and signal 1986.
processing. 34(5))
Ralph Otto Schmidt. A signal subspace approach to multiple emitter location and spectral estimation. Stanford University, 1982.
Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht. Compressed sensing off the grid. IEEE transactions on information theory, 59(11):7465-7490, 2013.
Gongguo Tang, Badri Narayan Bhaskar, and Benjamin Recht. Near minimax line spectral estimation. IEEE Transactions on Information Theory, 61(1):499-513 5124999-5111101 2014.
George R Terrell and David W Scott. Variable kernel density estimation. The Annals of Statistics, pages 1236-1265, 1992.
Gregory Valiant and Paul Valiant. A CLT and tight lower bounds for estimating entropy. Electronic Colloquium on Computational Complexity (ECCC), 17(179), 2010a.
Gregory Valiant and Paul Valiant. Estimating the unseen: A poolinear-samplee canonical estimator of distributions. Electronic Colloquium on Computational Complexity (ECCC), 17(180), 2010b.
Gregory Valiant and Paul Valiant. Estimating the unseen: An log n-sample estimator for entropy and support size, shown optimal via new CLTss. In Proceedings of the 43rd Annual ACM Symposium on the Theory of Computing, STOC '11, pages 685-694, New York, NY, USA, 2011. ACM.
Santosh Vempala and Grant Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841-860, 2004.
Xuan Wu and Changzhi Xie. Improved algorithms for properly learning mixture of gaussians. In National Conference of Theoretical Computer Science, pages 8-26. Springer, 2018.
Yihong Wu and Pengkun Yang. Optimal estimation of gaussian mixtures via denoised method of 07237
moments, 2018. URL WwK.nttps..//axx.ooor///db
Yannis G Yatracos. Rates of convergence of minimum distance estimators and kolmogorov's entropy. The Annaly of Statistics, pages 768-774, 1985.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In the appendix
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "vL4VRtkGiH", "reviewer": "Reviewer_bUkB", "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.", "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.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \nThe paper is technically interesting and employs an interesting suite of techniques. The solution deviates from prior work ideas and requires substantial technical work. \nThe 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.\n\nI recommend that the paper be accepted.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JNd4Fb5spHd", "reviewer": "Reviewer_27w8", "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.\n\nProof 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.", "questions": "no questions at this stage", "limitations": "I don't foresee direct negative impact of this theoretical work", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ The paper addresses an important and basic problem in the area of density estimation: proper learning of 1-d GMMs\n+ There have been multiple previous attempts on this problem; but this paper significantly improves over them\n+ The algorithmic techniques as well as the structural results are novel and interesting\n+ The presentation is nice\n\nWeaknesses (minor issues):\n+ 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.\n+ Missing discussion of a seemingly very relevant paper by X. Wu and C. Xie, “Improved algorithms for properly learning mixture of gaussians”.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8rhM4CBe28J", "reviewer": "Reviewer_r5gD", "summary": "In learning theory, we often assume that samples are drawn from a finite mixture model.\nAlso, the number of components in the finite mixture model is known.\nHowever, in many applications, this number may not be known in advance.\nThe problem of finding the number of components is called model selection.\nThe authors study the problem of robust model selection for one dimensional Gaussian mixture models with $k$ components ($k$-GMM).\nFormally, it is formulated as follows.\nGiven 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$.\n\nThere is a long line of existing works for learning GMM.\nHowever, 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.\nIn this paper, the authors give an algorithm for learning arbitrary one dimensional $k$-GMMs that outputs an approximation with $\\tilde O(k)$ components.\n\nThe algorithm works as follows.\nRecall 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.\nThe authors first consider the following case.\nWhen 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.\nIt is what the authors call well-conditioned.\nSince the Gaussians are well-conditioned, achieving this is rather easy by examining the Taylor expansion.\nThen, the authors reduce the general case to the well conditioned case via localization.\nThe 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.\nFor each interval $I$, the mixture of Gaussians in $\\mathcal{M}$ whose significant interval intersects $I$ forms a mixture of well conditioned Gaussians.\nOn 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.\nHence, 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.\n\nFurthermore, the authors apply the result to solve hypothesis testing for model selection problem and the techniques to solve sparse Fourier problem.\n\n", "questions": "\nQuestions:\n- 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?\n\nMinor note:\n- In line 219, what is $G_0$?", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n- The paper is well-written.\nThe ideas and the proofs are easy to follow.\n- The results is interesting.\nThe 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.\nThis improvement for the dependence on $\\frac{1}{\\epsilon}$ from a polynomial bound to a logarithmic bound is interesting.\n\n\nWeaknesses:\n- It may just be a minor weakness.\nIn terms of proof techniques, it seems that the techniques used in this paper are rather standard.\nIt seems the tools used in the proof are not very surprising. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8ZXCgyp95o_", "reviewer": "Reviewer_8UxQ", "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.  \n\nIn 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.", "questions": "1. About title: I feel that the word 'robust' in title is slightly misleading, because this paper is not really about handling corruptions. \n\n2. 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?\n\n3. 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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strength*\n\n- 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.\n\n- The paper also provides a nice application (sparse Fourier reconstruction) of their theoretical findings. \n\n\n*Weakness*\n\n- Techniques used in this paper are very specific to the 1-D GMM case, and thus significance of the results is limited. \n\n- 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).\n\n- 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. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept