On Learning Mixtures of Well-Separated Gaussians

Introduction

The goal is to estimate the parameters $\{(w_{j},\mu_{j},\sigma_{j}):j\in[k]\}$ up to required accuracy $\delta>0$ in time and number of samples that is polynomial in $k,d,1/\delta$.

Our next result shows that the separation of $\Omega(\sqrt{\log k})$ is tight – this separation suffices to learn the parameters of the mixture with polynomial samples. We state the theorem for the special case of uniform mixtures of spherical Gaussians. (See Theorem 5.1 for the formal statement.)

Our next result shows that in constant dimensions, one can obtain a computationally efficient algorithm. In fact, in such low dimensions a separation of order $\Omega(1)$ suffices.

The core technical portion of Theorem 1.3 and Theorem 1.4 is a new iterative algorithm, which is the main algorithmic contribution of the paper. This algorithm takes coarse estimates of the means, and iteratively refines them to get arbitrarily good accuracy $\delta$. We now present an informal statement of the guarantees of the iterative algorithm.

The above theorem also holds when the weights and variances are unequal. See Theorem 4.1 for a formal statement. Note that in the above result, the desired accuracy $\delta$ can be arbitrarily small compared to $k$, and the separation required does not depend on $\delta$. To prove the polynomial identifiability results (Theorems 1.3 and 1.4), we first find coarse estimates of the means that serve as initializers to this iterative algorithm, which then recovers the means up to arbitrarily fine accuracy independent of the separation.

The algorithm works by solving a system of non-linear equations that is obtained by estimating simple statistics (e.g., means) of the distribution restricted to certain carefully chosen regions. We prove that the system of non-linear equations satisfies a notion of “diagonal dominance” that allows us to leverage iterative algorithms like Newton’s method and achieve rapid (quadratic) convergence.

Given a mixture of spherical Gaussians with equal weights and variances, and with separation

Our iterative algorithm shows that to resolve this open question affirmatively, it is enough to find initializers that are reasonably close to the true parameters. In fact, a simple amplification argument shows that initializers that are $c\sqrt{\log k}/8$ close to the true means will suffice for this approach.

Our iterative algorithm is reminiscent of some commonly used iterative heuristics, such as Lloyd’s Algorithm and especially Expectation Maximization (EM). While these iterative methods are the practitioners’ method-of-choice for learning probabilistic models, they have been notoriously hard to analyze. We believe that the techniques developed here may also be useful to prove guarantees for these heuristics.

2 Prior Work and Comparison of Results

Gaussian mixture models are among the most widely used probabilistic models in statistical inference . Algorithmic results fall into two broad classes — separation-based results, and moment-based methods that do not assume explicit geometric separation.

The body of work that is most relevant to this paper assumes that there is some minimum separation between the means of the components in the mixture. The first polynomial time algorithmic guarantees for mixtures of Gaussians were given by Dasgupta , who showed how to learn mixtures of spherical Gaussians when the separation is of the order of $d^{1/2}$. This was later improved by a series of works for both spherical Gaussians and general Gaussians. The algorithm of Vempala and Wang gives the best known result, and uses PCA along with distance-based clustering to learn mixtures of spherical Gaussians with separation

We note that all these clustering-based algorithms require a separation that either implicitly or explicitly depend on the estimation accuracy $\delta$.Such a dependency on $\delta$ seems necessary for clustering-based algorithms that cluster every point accurately with high probability. Finally, although not directly related to our work, we note that a similar separation condition was shown to suffice also for non-spherical Gaussians , where separation is measured based on the variance along the direction of the line joining the respective means (as opposed, e.g., to the sum of maximum variances $\lVert\Sigma_{i}\rVert+\lVert\Sigma_{j}\rVert$ which could be much larger).

Iterative methods like Expectation Maximization (EM) and Lloyd’s algorithm (sometimes called the $k$-means heuristic) are commonly used in practice to learn mixtures of spherical Gaussians but, as mentioned above, are notoriously hard to analyze. Dasgupta and Schulman proved that a variant of the EM algorithm learns mixtures of spherical Gaussians with separation of the order of $d^{1/4}\text{polylog}(dk)$. Kumar and Kannan and subsequent work showed that the spectral clustering heuristic (i.e., PCA followed by Lloyd’s algorithm) provably recovers the clusters in a rather wide family of distributions which includes non-spherical Gaussians; in the special case of spherical Gaussians, their analysis requires separation of order $\sqrt{k}$.

Very recently, the EM algorithm was shown to succeed for mixtures of $k=2$ spherical Gaussians with $\Omega(\sigma)$ separation (we note that in this setting with $k=O(1)$, polynomial time guarantees are also known using other algorithms like the method-of-moments , as we will see in the next paragraph). SDP-based algorithms have also been studied in the context of learning mixtures of spherical Gaussians with a similar separation requirement of $\Omega(k\max_{i}\sigma_{i})$ . The question of how much separation between the components is necessary was also studied empirically by Srebro et al. , who observed that iterative heuristics successfully learn the parameters under much smaller separation compared to known theoretical bounds.

A related problem in the context of clustering graphs and detecting communities is the problem of learning a stochastic block model or planted partitioning model . Here, a sharp threshold phenomenon involving an analogous separation condition (between intra-cluster probability of edges and inter-cluster edge probability) is known under various settings (see the recent survey by Abbe for details). In fact, the algorithm of Kumar and Kannan give a general separation condition that specializes to separation between the means for mixtures of Gaussians, and separation between the intra-cluster and inter-cluster edge probabilities for the stochastic block model.

3 Overview of Techniques

The sample complexity lower bound proceeds by showing a more general statement: in any large enough collection of uniform mixtures, for all but a small fraction of the mixtures, there is at least one other mixture in the collection that is close in statistical distance (see Theorem 3.2). For our lower bounds, we will just produce a large collection of uniform mixtures of well-separated spherical Gaussians in $d=c\log k$ dimensions, whose pairwise parameter distances are reasonably large. In fact, we can even pick the means of these mixtures randomly in a ball of radius $\sqrt{d}$ in $d=c\log k$ dimensions; w.h.p. most of these mixtures will need at least $k^{\omega(1)}$ samples to identify.

To show the above pigeonhole style statement about large collections of mixtures, we will associate with a uniform mixture having means $\mu_{1},\dots,\mu_{k}$, the following quantities that we call “mean moments,” and we will use them as a proxy for the actual moments of the distribution:

The mean moments just correspond to the usual moments of a mixture of delta functions centered at $\mu_{1},\dots,\mu_{k}$. Closeness in the first $R=O(1/\varepsilon)$ mean moments (measured in injective tensor norm) implies that the two corresponding distributions are $\varepsilon$ close in statistical distance (see Lemma 3.7 and Lemma 3.8). The key step in the proof uses a careful packing argument to show that for most mixtures in a large enough collection, there is a different mixture in the collection that approximately matches in the first $R$ mean moments (see Lemma 3.6).

Instead we will use these statistics to set up a system of non-linear equations where the unknowns are the true parameters and solve for them using the Newton method. We will use the initializers $z_{j}=\mu^{(0)}_{j}$, to define the statistics that give our equations. Hence the unknown parameters $\{\mu_{i}:i\in[k]\}$ satisfy the following equation for each $j\in[k]$:

Note that in the above equation, the only unknowns or variables are the true means $\{\mu_{i}:i\in[k]\}$. After scaling the equations, and a suitable change of variables ${\bf x}_{j}=\mu_{j}/\sigma_{j}$ to make the system “dimensionless” we get a non-linear system of equations denoted by $F({\bf x})=b$. For the above system, ${\bf x}^{*}_{i}=\mu_{i}/\sigma_{i}$ represents a solution to the system given by the parameters of $\mathcal{G}$. The Newton algorithm uses the iterative update

For the Newton method we need access to the estimates for $b$, and the derivative matrix $F^{\prime}$ (the Jacobian) evaluated at ${\bf x}^{(t)}$. The derivative of the $j$ equation w.r.t. ${\bf x}_{i}$ corresponds to

where $g_{\sigma_{i}{\bf x}_{i},\sigma_{i}}(y)$ represents the p.d.f. at a point $y$ due to a spherical Gaussian with mean at $\sigma_{i}{\bf x}_{i}$ and covariance $\sigma_{i}^{2}/(2\pi)$ in each direction. Unlike usual applications of the Newton method, we do not have closed form expressions for $F^{\prime}$ (the Jacobian), due to our definition of the set $S_{j}$. However, we will instead be able to estimate the Jacobian at ${\bf x}^{(t)}$ by calculating the above expression (RHS) by considering a Gaussian with mean $\sigma_{i}{\bf x}^{(t)}_{i}$ and variance $\sigma_{i}^{2}/(2\pi)$. The Newton method can be shown to be robust to errors in $b,F,F^{\prime}$ (see Theorem B.2).

The main technical effort for proving convergence is in showing that the inverse $(F^{\prime})^{-1}$ evaluated at any point in the neighborhood around ${\bf x}^{*}$ is well-conditioned. We will show the convergence of the Newton method by showing “diagonal dominance” properties of the $dk\times dk$ matrix $F^{\prime}$. This uses the separation between the means of the components, and the properties of the region $S_{j}$ that we have defined. For $\Omega(\sqrt{\log k})$ separation, this uses standard facts about Gaussian concentration to argue that each of the $(k-1)$ off-diagonal blocks (in the $j$th row of $F^{\prime}$) is at most $1/(2k)$ factor of the corresponding diagonal term. With $\Omega(1)$ separation in $d=O(1)$ dimensions, we can not hope to get such a uniform bound on all the off-diagonal blocks (a single off-diagonal block can itself be $\Omega_{d}(1)$ times the corresponding diagonal entry). We will instead use careful packing arguments to show that the required diagonal dominance condition (see Lemma 4.13 for a statement).

Hence, the initializers are used to both define the regions $S_{j}$, and as initialization for the Newton method. Using this diagonal dominance in conjunction with initializers (Theorem 5.2) and the (robust) guarantees of the Newton method (Theorem B.2) gives rapid convergence to the true parameters.

Preliminaries

A standard mixture is just a uniform mixture of spherical Gaussians with all covariances $\sigma^{2}=1/(2\pi)$. Before we proceed, we define the following notion of parameter “distance” between mixtures of Gaussians:

For standard mixtures, the definition simplifies to

Note that this definition is invariant to scaling the variances (for convenience). We note that parameter distance is not a metric, but it is just a convenient way of measure closeness of parameters between two distributions.

The distance between two individual Gaussian components can also be measured in terms of the total variation distance between the components . For instance, in the case of standard spherical Gaussians, a parameter distance of $c\sqrt{\log k}$ corresponds to a total variation distance of $k^{-O(c^{2})}$.

Also, for a given mixture of $k$ spherical gaussians $\mathcal{G}=\{(w_{j},\mu_{j},\sigma_{j}):j\in[k]\}$, we will denote $w_{\text{min}}=\min_{j\in[k]}w_{j}$, $\sigma_{\max}=\max_{j\in[k]}\sigma_{j}$ and $\sigma_{\min}=\min_{j\in[k]}\sigma_{j}$.

In the above notation the bound $\rho$ can be thought of as a sufficiently large polynomial in $k$, since we are aiming for bounds that are polynomial in $k$. Since we can always scale the points by an arbitrary factor without affecting the performance of the algorithm, we can think of $\rho$ as the (multiplicative) range of values taken by the parameters $\{\mu_{i},\sigma_{i}:i\in[k]\}$. Since we want separation bounds independent of $k$, we will denote individual aspect ratios for variances and weights given by $\rho_{\sigma}=\max_{i\in[k]}\sigma_{i}/\min_{i\in[k]}\sigma_{i}$, and $\rho_{w}=\max_{i\in[k]}w_{i}/\min_{i\in[k]}w_{i}$.

1 Notation and Preliminaries about Newton’s method

Consider a system of $m$ non-linear equations in variables $u_{1},u_{2},\dots,u_{m}$:

In particular, for Newton’s method to work, $\lVert u^{0}-u^{*}\rVert\leq(L\max_{u\in\mathcal{N}}\lVert J(u)^{-1}\rVert)^{-1}$ will guarantee convergence. A statement of the robust convergence of Newton’s method in the presence of estimates is given in Theorem B.2 and Corollary B.4.

Consider any square matrix $A$ of size $n\times n$ satisfying

Then, $\lVert A^{-1}\rVert_{\infty\to\infty}\leq 1/\alpha.$

Lower Bounds with O​(log⁡k)𝑂𝑘O(\sqrt{\log k}) Separation

Here we show a sample complexity lower bound for learning standard mixtures of $k$ spherical Gaussians even when the separation is of the order of $\sqrt{\log k}$. In fact, this lower bound will also hold for a random mixture of Gaussians in $d\leq c\cdot\log k$ dimensions (for sufficiently small constant $c$) with high probability.In particular, this rules out polynomial-time smoothed analysis guarantees of the kind shown for $d=k^{\Omega(1)}$ in .

even though their parameter distance is at least $c_{2}\sqrt{\log k}$. Moreover, we can take $c=1/(4\log C)$ and $c_{2}=C^{-24}$.

The key to the proof of Theorem 3.1 is the following pigeonhole statement, which can be viewed as a bound on the covering number (or equivalently, the metric entropy) of the set of Gaussian mixtures.

Suppose we are given a collection $\mathcal{F}$ of standard mixtures of spherical Gaussians in $d$ dimensions that are $\rho=\sqrt{d}$ bounded, i.e., $\lVert\mu_{j}\rVert\leq\sqrt{d}$ for all $j\in[k]$. There are universal constants $c_{0},c_{1}\geq 1$, such that for any $\eta>0,\varepsilon\leq\exp(-c_{1}d)$, if

Notice that $k$ plays no role in the statement above. In fact, the proof also holds for mixtures with arbitrary number of components and arbitrary weights.

For any fixed $i\neq j$, the probability that $\|x_{i}-x_{j}\|\geq\gamma r$ is at most $\gamma^{d}$, because the volume of a ball of radius $\gamma r$ is $\gamma^{d}$ times that of a ball of radius $r$. The claim now follows by a union bound. ∎

Set $\gamma:=2^{-6/c}$, and consider the following probabilistic procedure. We first let $\mathcal{X}$ be a set of $(1/\gamma)^{d/3}$ points chosen independently and uniformly from the ball of radius $\sqrt{d}$. We then output a mixture chosen uniformly from the collection $\mathcal{F}$, defined as the collection of all standard mixtures of spherical Gaussians obtained by selecting $k$ distinct means from $\mathcal{X}$. Observe that the output of this procedure is distributed according to $\mathcal{D}$. Our goal is therefore to prove that with probability at least $1-2/k$, the output of the procedure satisfies the property in the theorem.

First, by Claim 3.4, with probability at least $1-\gamma^{d/3}\geq 1-1/k$, any two points in $\mathcal{X}$ are at distance at least $\gamma\sqrt{d}$. It follows that in this case, the means in any mixture in $\mathcal{F}$ are at least $\gamma\sqrt{d}$ apart, and also that any two distinct mixtures in $\mathcal{F}$ have a parameter distance of at least $\gamma\sqrt{d}$ since they must differ in at least one of the means. Note that $\gamma=C^{-24}$ for our choice of $c,\gamma$.

To complete the proof, we notice that by our choice of parameters, and denoting $\varepsilon=k^{-C}$,

The last inequality follows since for our choice of $\varepsilon=k^{-C}$, $c=\frac{1}{4\log C}$ and $C$ is large enough with $C\geq c_{0}$, so that

Hence applying Theorem 3.2 to $\mathcal{F}$, for at least $1-1/k$ fraction of the mixtures in $\mathcal{F}$, there is another mixture in $\mathcal{F}$ that is $\varepsilon$ close in total variation distance. We conclude that with probability at least $1-2/k$, a random mixture in $\mathcal{F}$ satisfies all the required properties, as desired. ∎

2 Proof of Theorem 3.2

It will be convenient to represent the p.d.f. $f(x)$ of the standard mixture of spherical Gaussians with means $\mu_{1},\mu_{2},\dots,\mu_{k}$ as a convolution of a standard mean zero Gaussian with a sum of delta functions centered at $\mu_{1},\mu_{2},\dots,\mu_{k}$,

Instead of considering the moments of the mixture of Gaussians, we will consider moments of just the corresponding mixture of delta functions at the means. We will call them “mean moments,” and we will use them as a proxy for the actual moments of the distribution.

Next, Lemma 3.7 shows that the two distributions that are close in the first $R$ mean moments are also close in the $L_{2}$ distance. This translates to small statistical distance between the two distributions using Lemma 3.8.

We will use the following standard packing claim.

Let $K$ be the unit ball of the norm $\|\cdot\|$. Then by assumption, the sets $x_{i}+\delta K/2$ for $i\in[N]$ are disjoint. But since they are all contained in $(\Delta+\delta/2)K$,

The “in particular” part follows by taking a maximal set of $\delta$-separated points. ∎

Notice that the image of $\psi$ lies in a direct sum of symmetric subspaces whose dimension is $D=\binom{d+R}{R}$ (i.e., the number of ways of distributing $R$ identical balls into $(d+1)$ different bins). Since $R\geq d$,

We define a norm on these vectors $\psi(\mu_{1},\dots,\mu_{k})$ in terms of the maximum injective norm of the mean moments,

Since each of our means has length at most $\sqrt{d}$, we have that

Using Claim 3.5, if $\lvert\mathcal{F}\rvert>N/\eta$ where

we have that for at least $1-\eta$ fraction of the Gaussian mixtures in $\mathcal{F}$, there is another mixture from $\mathcal{F}$ which is $(d+1)^{-R/4}$ close, as required. ∎

We first show that if the moments are very close, the Fourier transform of the two distributions is very close. This translates to a bound on the $L_{2}$ distance by Parseval’s identity.

Since the Fourier transform of a convolution is the product of the Fourier transforms, we have

Now we upper bound $\lvert\widehat{h}(\zeta)\rvert$ for $\lVert\zeta\rVert<\tau$.

We claim that the injective norm above is at most $k\varepsilon_{r}$ for all $r\geq 1$. For $r\leq R$, this follows immediately from the assumption in (11). For $r\geq R$, we use the fact that the means are $\rho=\sqrt{d}$ bounded,

where the last line follows since $R\geq 16\pi e\log(1/\varepsilon)$ and $2d\leq\log(1/\varepsilon)$. Hence, for $\lVert\zeta\rVert\leq\tau$, we have

since $\lVert\zeta\rVert\leq\tau$. Finally, using this bound along with (15) we have

Hence, by Parseval’s identity, the lemma follows.

The means are all length at most $\sqrt{d}$, and $\varepsilon<2^{-d}$. Let us define as before

Since $S$ is a Euclidean ball of radius $\gamma$, by Stirling’s approximation (Fact A.6), the volume is

where the third inequality follows by raising both sides to the power $2/d$ and using the fact that for $\alpha\geq 6$, $32\pi e(\alpha+1)\leq 2^{2\alpha}$. This concludes the proof.

The proof follows by a straightforward combination of Lemmas 3.6, 3.7, and 3.8. As stated earlier, we will choose $R=c_{0}\log(1/\varepsilon)$, and constants $c_{0}=8\pi e$, $c_{1}=36$. First, by Lemma 3.6 we have that for at least $(1-\eta)$ fraction of the Gaussian mixtures in $\mathcal{F}$, there is another mixture in the collection whose first $R=c_{0}\log(1/\varepsilon)$ mean moments differ by at most $d^{-R/4}$ in symmetric injective tensor norm. To use Lemma 3.7 with $\varepsilon^{\prime}=\varepsilon^{2}/4$, we see that

as required, where for the first inequality we used that $2^{-\alpha}<1/\alpha$ for $\alpha>0$, and the second inequality uses $\log(1/\varepsilon)\geq c_{1}=36$. We complete the proof by applying Lemma 3.7 (with $\varepsilon$ in Lemma 3.7 taking the value $\varepsilon^{2}/4$) and Lemma 3.8. ∎

Iterative Algorithms for min⁡{Ω​(log⁡k),d}Ω𝑘𝑑\min\{\Omega(\sqrt{\log k}),\sqrt{d}\} Separation

We will assume that we are given initializers that are inverse polynomially close in parameter distance. These initializers $\mu^{(0)}_{1},\mu^{(0)}_{2},\dots,\mu^{(0)}_{k}$ will be used to set up an “approximate” system of non-linear equations that has sufficient “diagonal dominance” properties, and then use the Newton method with the same initializers to solve it. In what follows, $\rho_{w}$ and $\rho_{\sigma}$ denote the aspect ratio for the weights and variances respectively as defined in Section 2.

There exist universal constants $c,c_{0}>0$ such that the following holds. Suppose we are given samples from a mixture of $k$ spherical Gaussians $\mathcal{G}$ having parameters $\{(w_{j},\mu_{j},\sigma_{j}):j\in[k]\}$, where the weights and variances are known, satisfying

and suppose we are given initializers $\mu^{(0)}_{1},\mu^{(0)}_{2},\dots,\mu^{(0)}_{k}$ satisfying

For standard mixtures, (16) corresponds to a separation of order $\min\{\sqrt{\log k},\sqrt{d}\}$.

Firstly, we will assume without loss of generality that $d\leq k$, since otherwise we can use a PCA-based dimension-reduction result due to Vempala and Wang .

The above theorem is essentially Corollary 3 in . In , however, they take the subspace spanned by the top $\max\{k,\log d\}$ singular vectors, most likely due to an artifact of their analysis. We give a different self-contained proof in Appendix C. We will abuse notation, and use $\{\mu_{i}:i\in[k]\}$ to refer to the means in the dimension reduced space. Note that after dimension reduction, the means are still well-separated for $c^{\prime}>(c-1)$ i.e.,

For each component $j\in[k]$ in $\mathcal{G}$, we first define a region $S_{j}$ around $z_{j}$ as follows. We will show in Lemmas 4.8 and 4.9 that the total probability mass in $S_{j}$ from other components is smaller than the probability mass from the component $j$.

where $b=F({\bf x}^{*})$. This is a system of $kd$ equations in $kd$ unknowns. Obviously ${\bf x}^{*}$ is a solution of the system, and if we could find it we would be able to recover all the means, as desired.

Our algorithm basically just applies Newton’s method to solve (21) with initializers given by ${\bf x}^{(0)}_{i}=\mu^{(0)}_{i}/\sigma_{i}$ for $i\in[k]$. To recall, Newton’s method uses the iterative update

where $F^{\prime}({\bf x}^{(t)})$ is the first derivative matrix (Jacobian) of $F$ evaluated at ${\bf x}^{(t)}$. One issue, however, is that we are not given $b=F({\bf x}^{*})$. Nevertheless, as we will show in Lemma 4.4, we can easily estimate it to within any desired accuracy using a Monte Carlo approach based on the given samples (from the Gaussian mixture corresponding to ${\bf x}^{*}$). A related issue is that we do not have a closed-form expression for $F$ and $F^{\prime}$, but again, we can easily approximate their evaluation at any point ${\bf x}$ and to within any desired accuracy using a Monte Carlo approach (by generating samples from the Gaussian mixture corresponding to ${\bf x}$). The algorithm is given below in detail.

Iterative Algorithm for Amplifying Accuracy of Parameter Estimation

Parameters: Set $T=C\log\log(d/\delta)$, for some sufficiently large constant $C>0$, $\varepsilon_{0}=c_{0}d^{-5/2}$ where $c_{0}>0$ is a sufficiently small constant, and $\eta_{1},\eta_{2},\eta_{3}=\delta w_{\text{min}}/(c^{\prime}\sqrt{d}\rho_{\sigma})$ where $c^{\prime}>0$ is a sufficiently small constant.

Output: Estimates $(\mu^{(T)}_{i}:i\in[k])$ for each component $i\in[k]$ such that $\lVert\mu^{(T)}_{i}-\mu_{i}\rVert_{\infty}\leq\delta\sigma_{i}$.

If $\delta\geq\varepsilon_{0}$, then we just output $\mu^{(T)}_{i}=\mu^{(0)}_{i}$ for each $i\in[k]$.

Set ${\bf x}^{(0)}_{i}=\tfrac{1}{\sigma_{i}}\mu^{(0)}_{i}$ for each $i\in[k]$.

(This is the only place the given samples are used)

For $t=1$ to $T=O(\log\log(dk/\delta))$ steps do the following:

Obtain using Lemma 4.5 an estimate $\widetilde{F^{\prime}}({\bf x}^{(t)})$ of $F^{\prime}({\bf x}^{(t)})=\nabla_{{\bf x}}F({\bf x}^{(t)})$ up to accuracy $\eta_{3}$ (in $\infty\to\infty$ operator norm).

Output $\mu^{(T)}_{i}=\sigma_{i}{\bf x}^{(T)}_{i}$ for each $i\in[k]$.

The proof of the two approximation lemmas below is based on a rather standard Chernoff argument; see Section 4.5.

Suppose samples $y^{(1)},y^{(2)},\dots,y^{(N)}$ are generated from a mixture of $k$ spherical Gaussians with parameters $\{(w_{i},\sigma_{i}{\bf x}_{i},\sigma_{i})\}_{i\in[k]}$ in $d$ dimensions, and $\max\{\lVert{\bf x}_{i}\rVert_{\infty},1\}\leq\rho/\sigma_{i}~{}\forall i\in[k]$. There exists a constant $C>0$ such that for any $\eta>0$ the following holds for $N\geq C\rho^{3}\log(\tfrac{dk}{\gamma})/(\eta^{2}w_{\text{min}})$ samples: with probability at least $1-\gamma$, for each $j\in[k]$ the empirical estimate for $F_{j}({\bf x})$ has error at most $\eta$ i.e.,

where $S_{j}$ is defined in Definition 4.3.

Suppose we are given the parameters of a mixture of $k$ spherical Gaussians $\{(w_{i},\sigma_{i}{\bf x}_{i},\sigma_{i})\}_{i\in[k]}$ in $d$ dimensions, with $\max\{\lVert{\bf x}_{i}\rVert_{\infty},1\}\leq\rho/\sigma_{i}$ for each $i\in[k]$, and region $S_{j}$ is defined as in Definition 4.3. There exists a constant $C>0$ such that for any $\eta>0$ the following holds for $N\geq C\rho^{4}d^{2}k^{2}\log(\tfrac{dk}{\gamma})/(\eta^{2}w_{\text{min}})$. Given $N$ samples $y^{(1)},y^{(2)},\dots,y^{(N)}$ generated from spherical Gaussian with mean $\sigma_{i}{\bf x}_{i}$ and variance $\sigma_{i}^{2}/(2\pi)$, we have with probability at least $1-\gamma$, for each $j\in[k]$ the following empirical estimate for $\nabla_{{\bf x}_{i}}F_{j}$ has error at most $\eta$ i.e.,

Furthermore, we have that the estimated second derivative $\widetilde{F^{\prime}}({\bf x})=(\widetilde{\nabla_{{\bf x}_{i}}F_{j}}({\bf x}):i,j\in[k])$ satisfies \big{\lVert}F^{\prime}({\bf x})-\widetilde{F^{\prime}}({\bf x})\big{\rVert}_{\infty\to\infty}\leq\eta.

2 Convergence Analysis using the Newton method

is the set of values of the variables that are close to the true values of the variables given by ${\bf x}^{*}_{i}=\tfrac{\mu_{i}}{\sigma_{i}}~{}\forall i\in[k]$, and $c_{0}>0$ is an appropriately large universal constant given in Theorem 4.1.

The following lemma lower bounds the contribution to region $S_{j}$ from the $j$th component.

In the notation of Theorem 4.1, for all $j\in[k]$, we have

The proof of the above lemma follows from concentration bounds for multivariate Gaussians. The following lemma upper bounds the contribution in $S_{j}$ from the other components.

In the notation of Theorem 4.1, and for a component $j\in[k]$ in $\mathcal{G}$, the contribution in $S_{j}$ from the other components is small, namely, for all $j\in[k]$

The above lemma is the more technical of the two, and it is crucial in showing diagonal dominance of the Jacobian. The proof of the above lemma is very different for separation of order $\sqrt{\log k}$ and $\sqrt{d}$ – hence we will handle this separately in Sections 4.4.1 and 4.4.2 respectively.

We now show the convergence of Newton algorithm assuming the above two lemmas. Theorem 4.1 follows in a straightforward manner from the guarantees of the Newton algorithm. We mainly need to show that $\lVert F^{\prime}\rVert\lVert F^{\prime\prime}\rVert\varepsilon_{0}<1/2$.

We now prove that the function $(F^{\prime}({\bf x}))^{-1}$ has bounded operator norm using the diagonal dominance properties of $F$.

We will divide the matrix $F^{\prime}$ into $k\times k=k^{2}$ blocks of size $d\times d$ each, and show that the matrix satisfies the required diagonal dominance property. Let us first consider the diagonal blocks i.e., we have from (23) for each $j\in[k]$

Consider a mixture of Gaussians where the $j$th component has mean $\sigma_{j}{\bf x}_{j}$ and standard deviation $\sigma_{j}/\sqrt{2\pi}$. It satisfies the required separation conditions since $\lVert\sigma_{i}{\bf x}_{i}-\mu_{i}\rVert_{2}\leq\varepsilon_{0}\sigma_{i}$. Applying Lemma 4.8,

Using a similar calculation, we see that for the off-diagonal blocks $M_{ji}=\nabla_{{\bf x}_{i}}F_{j}({\bf x})$,

Also, $\lVert\sigma_{i}{\bf x}_{i}-z_{j}\rVert_{\infty}\leq\lVert\mu_{i}-\mu_{j}\rVert_{\infty}+\sigma_{i}+\sigma_{j}\leq 2\lVert\mu_{i}-\mu_{j}\rVert_{2}$. For each $r_{1},r_{2}\in[d]$

Summing over all $i\neq j$, and using the bounds in Lemma 4.9,

Hence using Lemma 2.5 for diagonally dominant matrices, we get from (31) and (32)

We now prove that the function $F^{\prime}({\bf x})$ is locally Lipschitz by upper bounding the second derivative operator.

There exists a universal constant $c^{\prime}>0$ such that the derivative $F^{\prime}$ is locally $L$-Lipschitz in the neighborhood $\mathcal{N}$ for $L\leq c^{\prime}d^{5/2}$.

Hence the second derivatives are non-zero only for diagonal blocks $i_{1}=i_{2}$. For each $j,i\in[k]$ the second derivatives for $\forall r_{0},r_{1},r_{2}\in[d]$ are given by

Hence, applying Lemma B.1 with $F^{\prime}$ in the open set $K=\mathcal{N}$, the lemma follows. ∎

We first note that we have from (17), for each $i\in[k]$ that $\lVert{\bf x}^{*}_{i}-{\bf x}^{(0)}_{i}\rVert_{\infty}\leq\lVert{\bf x}^{*}_{i}-{\bf x}^{(0)}_{i}\rVert_{2}\leq\lVert\mu_{i}-\mu^{(0)}_{i}\rVert_{2}/\sigma_{i}\leq\varepsilon_{0}$. We will use the algorithm to find $\lVert{\bf x}^{(T)}-{\bf x}^{*}\rVert_{\infty}<\delta/\sqrt{d}$ (use the algorithm with $\delta^{\prime}:=\delta/\sqrt{d}$). The proof follows in a straightforward manner from Corollary B.4. Lemma 4.11 shows that $F^{\prime}$ is locally $L$-Lipschitz for $L=c^{\prime}d^{5/2}$. Together with Lemma 4.10 we have $\varepsilon_{0}L\lVert(F^{\prime})^{-1}\rVert_{\infty\rightarrow\infty}\leq 1/2$ for our choice of $\varepsilon_{0}$. Also from Lemma 4.4, by using $N=O(\delta^{-2}\rho^{6}k^{6}w_{\text{min}}^{-3})$ samples (and $d\leq k$), $\eta_{1}+\eta_{2}\leq\frac{\delta}{4\sqrt{d}\lVert(F^{\prime})^{-1}\rVert_{\infty\rightarrow\infty}}$. It is easy to check that $B=\max_{y}\lVert F^{\prime}(y)\rVert\leq\frac{\max_{i}\sigma_{i}}{w_{\text{min}}\min_{i}\sigma_{j}}\leq 4\rho_{\sigma}/w_{\text{min}}$. Hence, similarly from Lemma 4.5 $\eta_{3}\leq\frac{\delta}{4\sqrt{d}B\lVert(F^{\prime})^{-1}\rVert_{\infty\rightarrow\infty}^{2}}$ as required. Hence, from Corollary B.4, $T=O(\log\log(d/\delta))$ iterations of the Newton’s method suffices. Further, each iteration mainly involves inverting a $dk\times dk$ matrix which is polynomial time in $d,k$. ∎

3 Bounding Leakage from Own Component: Proof of Lemma 4.8

The first equation (33) follows easily from the rotational invariance of a spherical Gaussian. Suppose $g_{0}=\langle y,\widehat{v}_{0}\rangle$, then $g_{0}\sim N(0,\sigma^{2}/(2\pi))$. Hence

We will now prove (35); the proof of (34) follows the same argument. We first observe that using the rotational invariance, it suffices to consider the span of $\widehat{v}_{0},\widehat{e}_{r_{1}},\widehat{e}_{r_{2}}$.

where the last line follows from truncated moments of a normal variable with variance $\sigma^{2}/(2\pi)$ (Lemma A.2). Using the fact that $\exp(t^{2})>9\cdot 16\pi$ for $t\geq 3$, the lemma follows. The proof for $r_{1}=r_{2}$, and for (34) follows from an identical argument. ∎

To prove (26), $\forall r_{1}\in[d]$ we have

Let $Z_{ji}=\{y:\langle y-\mu_{j},\widehat{e}_{ji}\rangle>3\sigma_{j}\sqrt{\log(\rho_{\sigma}/w_{\text{min}})}\}$ be the set $y$ that do not satisfy the constraint along $\widehat{e}_{ji}$. Since $\lVert z_{j}-\mu_{j}\rVert_{2}\leq\sigma_{j}$, we have that the total loss from those $y\in Z_{ji}$ is

by applying Lemma 4.12 with the Gaussian $(y-\mu_{j})$, and $t=3\sqrt{\log(\rho_{\sigma}/w_{\text{min}})}$. Hence, we have

since $w_{\text{min}}\leq 1/k$. The proof of the last equation follows in an identical fashion. From (35) of Lemma 4.12, we have

4 Bounding Leakage from Other Components: Proof of Lemma 4.9

Since our algorithm works when we either have separation of order $\sqrt{\log k}$ or separation of order $\sqrt{d}$, we have two different proofs for Lemma 4.9 depending on whether $\sqrt{\log(1/w_{\text{min}})}\leq\sqrt{d}$ or notMore accurately whether $\sqrt{\log(\rho_{\sigma}/w_{\text{min}})}\leq\sqrt{d}+\sqrt{\log(\rho_{w}\rho_{\sigma})}$, where $\rho_{w}\geq 1/w_{\text{min}}$..

Let $\widehat{e}_{ji}$ be the unit vector along $z_{i}-z_{j}$. We will now show that every point $y\in S_{j}$, is far from $z_{i}$ along the direction $\widehat{e}_{ji}$.

Since $y\in S_{j}$, $\lvert\langle y-z_{j},\widehat{e}_{ji}\rangle\rvert\leq 4\sigma_{j}\sqrt{\log(\rho_{\sigma}/w_{\text{min}})}$, and

We will now use Lemma 4.12 for each component $i\in[k]$ with mean zero Gaussian $y-\mu_{i}$ and $t^{2}=16\log(\rho_{\sigma}/w_{\text{min}})+\tfrac{1}{8\pi\sigma_{i}^{2}}\lVert\mu_{j}-\mu_{i}\rVert^{2}_{2}$. We first prove (28); using equation (33) with Gaussian $(y-\mu_{i})$ of variance $\sigma_{i}^{2}/(2\pi)$,

For (29), we use (34) similarly with $(y-\mu_{i})$ and variance $\sigma_{i}^{2}/(2\pi)$ and $t$ as above:

The proof of (30) follows in an identical fashion from (35) for $r_{1},r_{2}\in[d]$

4.2 Separation of Order d𝑑\sqrt{d}

The proof of Lemma 4.9 uses the following useful lemma that shows that for any point within $\sigma_{j}\sqrt{d}$ distance of $\mu_{j}$, the total probability mass from the other Gaussian components is negligible. Note that in the following lemma, $k$ can be arbitrary large in terms of $d$.

then for every component $j\in[k]$ and $\forall x^{*}:\lVert x^{*}-\mu_{j}\rVert\leq 4\sigma_{j}\sqrt{d}$ and $\forall 0\leq m\leq 2$,

where $\rho_{\sigma}=\max_{i}\sigma_{i}/(\min_{i}\sigma_{i})$ and $\rho_{w}=\max_{i}w_{i}/(\min_{i}w_{i})$.

We now prove Lemma 4.9 under separation $\lVert\mu_{i}-\mu_{j}\rVert_{2}\geq c(\sigma_{i}+\sigma_{j})(\sqrt{d}+\sqrt{\log(\rho_{\sigma}\rho_{w})})$ assuming the above lemma.

Our proof will follow by applying Lemma 4.13, and integrating over all $y\in S_{j}$. For any point $y\in S_{j}$, $\lVert y-\mu_{j}\rVert_{2}\leq 3\sigma_{j}(\sqrt{d}+\sqrt{\log(\rho_{w}\rho_{\sigma})})$, and the separation of the means satisfies (37). To prove (25) we get from (38),

To prove (27), we get from (39) that for each $y\in S_{j}$ and $r_{1},r_{2}\in[d]$,

To prove (26), we first note that for each $y\in S_{j}$, $\lVert\mu_{i}-\mu_{j}\rVert_{2}\leq\lVert\mu_{i}-y\rVert+(\sqrt{d}+\sqrt{\log\rho_{w}})\sigma_{j}\leq 2\lVert\mu_{i}-y\rVert$. Hence, by applying (39) in Lemma 4.13, the following inequality holds:

Hence (26) follows from a similar argument as before. ∎

The proof of Lemma 4.13 proceeds by using a packing-style argument. Roughly speaking, in the uniform case when all the variances are roughly equal, the separation condition can be used to establish an upper bound on the number of other Gaussian means that are at a distance of $r$ from a certain mean. We now present the proof for the case when the variances are roughly equal, and this will also be important for the general case.

In the notation of Lemma 4.13, let us denote for convenience, the $j$th component by $(w_{0},\mu_{0},\sigma_{0})$. Then, the total probability mass at any point $x^{*}$ s.t. $\lVert x^{*}-\mu_{0}\rVert\leq 4\sqrt{d}\sigma_{0}$, from components $(w_{1},\mu_{1},\sigma_{1}),\dots,(w_{i},\mu_{i},\sigma_{i}),\dots,(w_{k^{\prime}},\mu_{k^{\prime}},\sigma_{k^{\prime}})$ satisfying $\forall i\in[k^{\prime}],~{}\sigma_{0}\leq\sigma_{i}\leq 2\sigma_{0}$, and $\lVert\mu_{i}-\mu_{0}\rVert_{2}\geq C\left(\sqrt{d}+\sqrt{\log\rho_{w}}\right)$ is given by

Furthermore, we have $\sum_{i\in[k^{\prime}]}w_{i}g_{i}^{1/2}(x^{*})<w_{0}\sigma_{0}^{-d}\exp(-C^{2}d/4).$

We can assume without loss of generality that $\mu_{0}=0,\sigma_{0}=1$. Suppose $r_{i}=\lVert\mu_{i}-x\rVert_{2}$. Considering $1\leq\sigma_{i}\leq 2$ and $g_{i}(x)=\sigma_{i}^{-d}\exp(-\pi\lVert x-\mu_{i}\rVert_{2}^{2}/\sigma_{i}^{2})$, the lemma will follow, if we prove the following inequality for any $C\geq C_{0}\geq 16$:

Let $B_{i}=\{y:\lVert y-\mu_{i}\rVert_{2}\leq\sqrt{d}\}$. From the separation conditions, we have that

the balls $B_{1},\ldots,B_{k^{\prime}}$ are pairwise disjoint, and

the balls are far from the origin i.e, $\forall y\in B_{i},\lVert y\rVert\geq C(\sqrt{d}+\sqrt{\log\rho_{w}})$.

We first relate the p.d.f. value $g_{i}(x)$ to the Gaussian measure of a ball of radius $\sqrt{d}$ around $\mu_{i}$. The volume of the ball $\text{Vol}(B_{i})\geq 1$ and for every $y\in B_{i}$, the separation conditions and triangle inequality imply that $\lVert y\rVert\geq\lVert\mu_{i}-x^{*}\rVert-\lVert y-\mu_{i}\rVert-\lVert x^{*}\rVert\geq r_{i}/\sqrt{2}$. Hence,

By using the disjointness of balls $B_{i}$, we get that

where the last line follows since a Gaussian random variable in $d$ dimensions with mean and unit variance in each direction has measure at most $\exp(-s^{2}/2)$ outside a ball of radius $(\sqrt{d}+s)$ (see Lemma A.4). ∎

We now proceed to the proof of Lemma 4.13.

We may again assume without loss of generality that $\mu_{j}=0$ and $\sigma_{j}=1$ (by shifting the origin and scaling). Hence $\lVert x^{*}\rVert_{2}\leq\sqrt{d}/\sqrt{\pi}$. We will divide the components $i\in[k]\setminus\{j\}$ depending on their standard deviation $\sigma_{i}$ into buckets $I_{0},I_{1},\dots,I_{s}$ where $s\leq\lceil\log(\max_{i}\sigma_{i}/\sigma_{j})\rceil$ as follows:

Let us first consider the components in the bucket $I_{0}$, and suppose we scale so that $\sigma_{j}=1$. As before let $r_{i}=\lVert x^{*}-\mu_{i}\rVert_{2}$. We first note that if $\sigma_{i}\leq\sigma_{j}$, since $\lVert x^{*}-\mu_{i}\rVert_{2}\geq C\sqrt{d}(\sigma_{i}+\sigma_{j})$, a simple calculation shows that $g_{\mu_{i},\sigma_{i}}(x^{*})\leq g_{\mu_{i},\sigma_{j}}(x^{*})$. Hence, by applying Lemma 4.14 to $I_{0}$ with a uniform variance of $\sigma_{j}^{2}=1$ for all Gaussians, we see that

Consider any bucket $I_{q}$. We will scale the points down by $2^{q-1}\sigma_{j}$ so that $y^{\prime}=y/(2^{q-1}\sigma_{j})$, and let $\forall i\in I_{q}$ $r^{\prime}_{i}=r_{i}/(2^{q-1}\sigma_{j})$. Again from Lemma 4.14 we have that

Hence, by summing up over all buckets (using (44) and (46)), the total contribution $\sum_{i\in[k]\setminus\{j\}}w_{i}g_{i}(x)\leq 4w_{j}\exp(-C^{d}/4)\leq\exp(-C^{2}d/8)\cdot w_{j}g_{j}(x)$.

The final equation (39) follows from separation conditions, since $\lVert x-\mu_{i}\rVert>C\sqrt{d}\sigma_{i}$, hence $\exp(\pi\lVert x-\mu_{i}\rVert^{2}/2\sigma_{i}^{2})>\lVert x-\mu_{i}\rVert^{m}/\sigma_{i}^{m}$ for some sufficiently large constant $C=C(m)\geq 1$. Hence, by using an identical argument with the furthermore part of Lemma 4.14, it follows.

5 Sampling Errors

Hence, to union bound over all $d$ events $N=O\left(\varepsilon^{-2}\rho^{2}\log d\log(1/\gamma)\right)$ suffices.

A similar proof also works for the second equation (48). ∎

Further, we can write $Z=Z_{1}+Z_{2}$, where

Finally, we have from upper bound of the error in the individual blocks that

Sample Complexity Upper Bounds with Ω​(log⁡k)Ω𝑘\Omega(\sqrt{\log k}) Separation

For sake of exposition, we will restrict our attention to the case when the standard deviations $\sigma_{i}$, and weights $w_{i}$ are known for all $i\in[k]$. We believe that similar techniques can also see used to handle unknown $\sigma_{i},w_{i}$ as well (see Remark 4.6). In what follows $\rho_{\sigma}$ corresponds to the aspect ratio of the covariances i.e., $\rho_{\sigma}=\max_{i\in[k]}\sigma_{i}/\min_{i\in[k]}\sigma_{i}$.

There exists a universal constant $c>0$ such that suppose we are given samples from a mixture of spherical Gaussians $\mathcal{G}=\{(w_{i},\mu_{i},\sigma_{i}):i\in[k]\}$ (with known weights and variances) that are $\rho$-bounded and the means are well-separated i.e.

Such results are commonly referred to as polynomial identifiability or robust identifiability results. We can again assume as in Section 4 that without loss of generality that $d\leq k$ due to the following dimension-reduction technique using PCA . Theorem 5.1 follows in a straightforward manner by combining the iterative algorithm, with initializers given by the following theorem.

For any constant $c\geq 10$, suppose we are given samples from a mixture of spherical Gaussians $\mathcal{G}=\{(w_{i},\mu_{i},\sigma_{i}):i\in[k]\}$ that are $\rho$-bounded and the means are well-separated i.e.

and both mixtures have minimum weight $w_{\text{min}}\geq 1/k^{c}$, then

where \rho_{s}=\max\Big{\{}\frac{\max_{j\in[k]}\sigma^{*}_{j}}{\min_{j\in[k]}\sigma_{j}},\frac{\max_{j\in[k]}\sigma_{j}}{\min_{j\in[k]}\sigma^{*}_{j}}\Big{\}}.

In the above proposition, $\rho_{s}\leq\rho^{2}$ is a simple upper bound since we will only search for all parameters of magnitude at most $\rho$. But it can be much smaller if we have a better knowledge of the range of $\{\sigma_{j}:j\in[k]\}$. We note that in very recent independent work, Diakonikolas et al. established a similar statement about mixtures of Gaussians where the components have small overlap (see Appendix B in ). We first see how the above proposition implies Theorem 5.2.

The following simple lemma gives a sample-efficient algorithm to find a distribution from a net of distributions $\mathcal{T}$ that is close to the given distribution. This tournament-based argument is a commonly used technique in learning distributions.

Suppose $\mathcal{T}$ is a set of probability distributions over $\mathcal{X}$, and we are given $m$ samples from a distribution $D$, which is $\delta$ close to some distribution $D^{\prime\prime}\in\mathcal{T}$ in statistical distance, i.e., $\lVert D-D^{\prime\prime}\rVert_{TV}\leq\delta$. Then there is an algorithm that uses $m=O(\delta^{-2}\log\lvert\mathcal{T}\rvert)$ samples from $D$ and with probability at least $1-1/\lvert\mathcal{T}\rvert$ finds a distribution $D^{*}$ such that $\lVert D-D^{*}\rVert_{TV}\leq 4\delta$.

Let $\mathcal{T}=\{D_{1},D_{2},\dots,D_{|\mathcal{T}|}\}$ be the set of distributions over $\mathcal{X}$. For any $i\neq j$ let $A_{ij}\subset\mathcal{X}$ be such that

Use $m=O(\delta^{-2}\log\lvert\mathcal{T}\rvert)$ samples to obtain estimates $p_{ij}$ satisfying with probability at least $1-1/\lvert\mathcal{T}\rvert$ that

Output the first distribution $D_{i}\in\mathcal{T}$ that satisfies

First, notice that by (53) and the assumption that $\lVert D-D^{\prime\prime}\rVert_{TV}\leq\delta$, $D^{\prime\prime}$ satisfies the test in (54). We next observe by the definition of $A_{ij}$ in (52) that for any $i\neq j$ such that both $D_{i}$ and $D_{j}$ pass the test, we must have $\lVert D_{i}-D_{j}\rVert_{TV}\leq 3\delta$. This implies that the output of the algorithm must be within statistical distance $4\delta$ of $D$, as desired. ∎

We now prove Proposition 5.2 assuming the above Proposition 5.3. This follows in a straightforward manner by using the algorithm from Lemma 5.4 where $\mathcal{T}$ is chosen to be a net over all possible configuration of means, variances and weights. We give the proof below for completeness.

2 Proof of Proposition 5.3

To show Proposition 5.3, we will consider any two mixtures of well-separated Gaussians, and show that the statistical distance is at least inverse polynomial in $k$. This argument becomes particularly tricky when the different components can have different values of $\sigma_{i}$ e.g., instances where one component of $\mathcal{G}$ with large $\sigma_{i}$ is covered by multiple components from $\mathcal{G}^{*}$ with small $\sigma^{*}_{j}$ values.

For each component $j\in[k]$ in $\mathcal{G}$, we define the region $S_{j}$ around $\mu_{j}$, where we hope to show a statistical distance.

The following lemma shows that most of the probability mass from $j$th component around $\mu_{j}$ is confined to $S_{j}$.

where the last step follows since $c\geq 5$ and $w_{\text{min}}\leq 1/k$. Hence, performing a union bound over the $k$ components in $\mathcal{G}^{*}$ completes the proof. ∎

The following lemma shows that there is at most one component of $\mathcal{G}^{*}$ that is close to the component $(w_{j},\mu_{j},\sigma_{j}^{2}I)$ in $\mathcal{G}$.

We now proceed to the proof of the main proposition (Proposition 5.3) of this section. We will try to match up components in $\mathcal{G},\mathcal{G}^{*}$ that are very close to each other in parameter distance and remove them from their respective mixtures. Then we will consider among unmatched components the one with the smallest variance. Suppose $(w_{j},\mu_{j},\sigma_{j})$ were this component, we will show a significant statistical distance in the region $S_{j}$ around $\mu_{j}$.

The following lemma considers two components, $G_{j}=(w_{j},\mu_{j},\sigma_{j})$ from $\mathcal{G}$ , and $G^{*}_{j}=(w^{*}_{j},\mu^{*}_{j},\sigma^{*}_{j})$ from $\mathcal{G}^{*}$ that have a non-negligible difference in parameters (we use the same index $j$ for convenience, since this is without loss of generality). This lemma shows that if $\sigma_{j}\leq\sigma^{*}_{j}$, then there is some region $S\subset S_{j}$ where the component $G_{j}$ has significantly larger probability mass than $G^{*}_{j}$. We note that it is crucial for our purposes that we obtain non-negligible statistical distance in a region around $S_{j}$. Suppose $f_{j}$ and $f^{*}_{j}$ are the p.d.f.s of the two components (with weights), it is easier to lower bound $\lVert f_{j}-f^{*}_{j}\rVert_{1}$ (e.g. Lemma 38 in ). However, this does not translate to a corresponding lower bound restricted to region $S$ i.e., $\lVert f_{j}-f^{*}_{j}\rVert_{1,S}$ since $f_{j}$ and $f^{*}_{j}$ do not represent distributions (e.g. $\lVert f_{j}\rVert_{1}=w_{j}<1$).

For some universal constant $c_{1}>0$, suppose we are given two spherical Gaussian components with parameters $(w_{j},\mu_{j},\sigma_{j})$ and $(w^{*}_{j},\mu^{*}_{j},\sigma^{*}_{j})$ that are $\rho_{\sigma}$-bounded satisfying

Then, there exists a set $S\subset S_{j}$ such that

Before we proceed, we present two lemmas which lower bound the statistical distance when the means of the components differ, or if the means are identical but the variances differ.

In the notation of Lemma 5.9, suppose $\lVert\mu_{j}-\mu^{*}_{j}\rVert_{2}\geq\gamma\sigma_{j}$. Then, there exists a set $S\subset S_{j}$ such that

Without loss of generality we can assume that $\mu_{j}=0$ (by shifting the origin to $\mu_{j}$). Let us consider two regions

Due to the symmetry of $S_{j}$ (Definition 5.5), it is easy to see that

For any point $x$, let $x_{jl}=\langle x,\widehat{e}_{jj}\rangle$. Further, $\mu^{*}_{j}=\lVert\mu^{*}_{j}\rVert\widehat{e}_{jj}$. We first note that $x\in R_{j}\Longleftrightarrow(-x)\in L_{j}$ due to the symmetric definition of $S_{j}$. Hence,