Near-optimal-sample estimators for spherical Gaussian mixtures

Introduction

Meaningful information often resides in high-dimensional spaces: voice signals are expressed in many frequency bands, credit ratings are influenced by multiple parameters, and document topics are manifested in the prevalence of numerous words. Some applications, such as topic modeling and genomic analysis consider data in over 1000 dimensions, .

Typically, information can be generated by different types of sources: voice is spoken by men or women, credit parameters correspond to wealthy or poor individuals, and documents address topics such as sports or politics. In such cases the overall data follow a mixture distribution .

Mixtures of high-dimensional distributions are therefore central to the understanding and processing of many natural phenomena. Methods for recovering the mixture components from the data have consequently been extensively studied by statisticians, engineers, and computer scientists.

An important and extensively studied special case of mixture distributions are spherical-Gaussians , where different coordinates have the same variance, though potentially different means. Due to their simple structure, they are easier to analyze and under a minimum-separation assumption have provably-practical algorithms for clustering and parameter estimation .

2 Sample complexity

Reducing the number of samples is of great practical significance. For example, in topic modeling every sample is a whole document, in credit analysis every sample is a person’s credit history, and in genetics, every sample is a human DNA. Hence samples can be very scarce and obtaining them can be very costly. By contrast, current CPUs run at several Giga Hertz, hence samples are typically much more scarce of a resource than time.

Note that for one-dimensional statistical problems, the need for sample-efficient algorithms has been broadly recognized. The sample complexity of many problems is known quite accurately, often to within a constant factor. For example, for discrete distributions over $\{1{,}\ldots{,}s\}$, an approach proposed in and its modifications were used in to estimate the probability multiset using $\Theta(s/\log s)$ samples. Learning one-dimensional $m$-modal distributions over $\{1{,}\ldots{,}s\}$ requires $\Theta(m\log(s/m)/\epsilon^{3})$ samples . Similarly, one-dimensional mixtures of $k$ structured distributions (log-concave, monotone hazard rate, and unimodal) over $\{1{,}\ldots{,}s\}$ can be learned with ${\cal O}(k/\epsilon^{4})$, ${\cal O}(k\log(s/\epsilon)/\epsilon^{4})$, and ${\cal O}(k\log(s)/\epsilon^{4})$ samples, respectively, and these bounds are tight up to a factor of $\epsilon$ .

Compared to one dimensional problems, in high dimensions there is a polynomial gap in the sample complexity. For example, for learning spherical Gaussian mixtures, the number of samples required by previous algorithms is ${\cal O}(d^{12})$ for $k=2$ components, and increased exponentially with $k$ . In this paper we bridge this gap, by constructing near-linear sample complexity estimators.

3 Previous and new results

Our main contribution is PAC learning $d$ dimensional Gaussian mixtures with near-linear samples. We show few auxiliary results for one-dimensional Gaussians.

time. Observe that recent algorithms typically construct the covariance matrix , hence require $\geq nd^{2}$ time. In that sense, for small values of $k$, the time complexity we derive is comparable to the best such algorithms can hope for. Observe also that the exponential dependence on $k$ is of the form d^{2}\Big{(}\frac{k^{7}}{\epsilon^{3}}\log\frac{d}{\delta}\Big{)}^{k^{2}}, which is significantly lower than the $d^{{\cal O}(k^{3})}$ dependence in previous results.

By contrast, Theorem 2 shows that PAC learning $k$-component spherical Gaussian mixtures require $\Omega(dk/\epsilon^{2})$ samples for any algorithm, hence our distribution learning algorithms are nearly sample optimal. In addition, their time complexity significantly improves on previously known ones.

3.2 One-dimensional Gaussian mixtures

Independently and around the same time as this work showed that mixtures of two one-dimensional Gaussians can be learnt with $\widetilde{{\cal O}}(\epsilon^{-2})$ samples and in time ${\cal O}(\epsilon^{-7.01})$. We provide a natural estimator for learning mixtures of $k$ one dimensional Gaussians using some basic properties of Gaussian distributions and show that mixture of any $k$-one dimensional Gaussians can be learnt with $\widetilde{{\cal O}}(k\epsilon^{-2})$ samples and in time \widetilde{{\cal O}}\left(\bigl{(}\frac{k}{\epsilon}\bigr{)}^{3k+1}\right).

4 The approach and technical contributions

The popular Scheffe estimator takes a collection ${\cal F}$ of distributions and uses ${\cal O}(\log|{\cal F}|)$ independent samples from an underlying distribution $\mathbf{f}$ to find a distribution in ${\cal F}$ whose distance from $\mathbf{f}$ is at most a constant factor larger than that of the distribution in ${\cal F}$ that is closet to $f$ . In Lemma 1, we lower the time complexity of the Scheffe algorithm from ${\cal O}(|{\cal F}|^{2})$ time to $\widetilde{{\cal O}}(|{\cal F}|)$, helping us reduce the time complexity of our algorithms.

Our goal is therefore to construct a small class of distributions that is $\epsilon$-close to any possible underlying distribution. For simplicity, consider spherical Gaussians with the same variance and means bounded by $B$. Take the collection of all distributions derived by quantizing the means of all components in all coordinates to $\epsilon_{m}$ accuracy, and quantizing the weights to $\epsilon_{w}$ accuracy. It can be shown that to get distance $\epsilon$ from the underlying distribution, it suffices to take $\epsilon_{m},\epsilon_{w}\leq 1/{\rm{poly}}_{\epsilon}(dk)$. There are at most \bigl{(}\frac{B}{\epsilon_{m}}\bigr{)}^{dk}\cdot\bigl{(}\frac{1}{\epsilon_{w}}\bigr{)}^{k}=2^{\widetilde{{\cal O}}_{\epsilon}(dk)} possible combinations of the $k$ mean vectors and weights. Hence Scheffe implies an exponential-time algorithm with sample complexity $\widetilde{{\cal O}}(dk)$.

To reduce the dependence on $d$, one can approximate the span of the $k$ mean vectors. This reduces the problem from $d$ to $k$ dimensions, allowing us to consider a distribution collection of size $2^{{\cal O}(k^{2})}$, with Scheffe sample complexity of just ${\cal O}(k^{2})$. constructs the sample correlation matrix and uses $k$ of its columns to approximate the span of mean vectors. This approach requires the $k$ columns of the sample correlation matrix to be very close to the actual correlation matrix, and thus requires a lot more samples.

We derive a spectral algorithm that uses the top $k$ eigenvectors of the sample covariance matrix to approximate the span of the $k$ mean vectors. Since we use the entire covariance matrix instead of just $k$ columns, a weaker concentration is sufficient and we gain on the sample complexity.

Using recent tools from non-asymptotic random matrix theory , we show that the approximation of the span of the means converges in $\widetilde{{\cal O}}(d)$ samples. This result allows us to address most “reasonable” distributions, but still there are some “corner cases” that need to be analyzed separately. To address them, we modify some known clustering algorithms such as single-linkage, and spectral projections. While the basic algorithms were known before, our contribution here, which takes a fair bit of effort and space, is to show that judicious modifications of the algorithms and rigorous statistical analysis yield polynomial time algorithms with near optimal sample complexity.

Our approach applies most directly to mixtures of spherical Gaussians. We provide a simple and practical recursive clustering and spectral algorithm that estimates all such distributions in ${\cal O}_{k}(d\log^{2}d)$ samples.

The paper is organized as follows. In Section 2, we introduce notations, describe results on the Scheffe estimator, and state a lower bound. In Section 3, we present the algorithm for $k$-spherical Gaussians. In Section 4 we show a simple learning algorithm for one-dimensional Gaussian mixtures. To preserve readability, most of the technical details and proofs are given in the appendix.

Preliminaries

2 Selection from a pool of distributions

Let $\epsilon>0$. For some constant $c$, given \frac{c}{\epsilon^{2}}{\log\bigl{(}\frac{|{\cal F}|}{\delta}\bigr{)}} independent samples from a distribution $\mathbf{f}$, with probability $\geq 1-\delta$, the output $\hat{\mathbf{f}}$ of modified scheffe $D({\hat{\mathbf{f}}},{\mathbf{f}})\leq 1000\max(\epsilon,D({\mathbf{f}},{{\cal F}})).$ Furthermore, the algorithm runs in time {\cal O}\bigl{(}\frac{|{\cal F}|T\log(|{\cal F}|/\delta)}{\epsilon^{2}}\bigr{)}.

We therefore find a small class ${\cal F}$ with at least one distribution close to the underlying mixture. For our problem of estimating $k$ component mixtures in $d$-dimensions, $T={\cal O}(dk)$ and $|{\cal F}|=\widetilde{{\cal O}}_{k,\epsilon}(d^{2})$. Note that we have not optimized the constant $1000$ in the above lemma.

3 Lower bound

Using Fano’s inequality, we show an information theoretic lower bound of $\Omega(dk/\epsilon^{2})$ samples to learn $k$-component $d$-dimensional mixtures of spherical Gaussians for any algorithm. More precisely,

Mixtures in d𝑑d dimensions

We now concentrate on estimating the means. As stated in the introduction, given the span of the mean vectors ${\boldsymbol{\mu}_{i}}$, we can grid the $k$ dimensional span to the required accuracy $\epsilon_{g}$ and use Scheffe, to obtain a polynomial time algorithm. One of the natural and well-used methods to estimate the span of mean vectors is using the correlation matrix . Consider the correlation-type matrix,

In expectation, the fraction of terms from $\mathbf{p}_{i}$ is $w_{i}$. Furthermore for a sample $X$ from a particular component $j$,

Therefore, as $n\to\infty$, the matrix $S$ converges to $\sum^{k}_{j=1}w_{j}{\boldsymbol{\mu}_{j}}{\boldsymbol{\mu}_{j}}^{t}$, and its top $k$ eigenvectors span of means.

While the above intuition is well understood, the number of samples necessary for convergence is not well studied. Ideally, irrespective of the values of the means, we wish $\widetilde{{\cal O}}(d)$ samples to be sufficient for the convergence. However this is not true, as we demonstrate by a simple example.

Consider the special case, $d=1$, $k=2$, $\sigma^{2}=1$, $w_{1}=w_{2}=1/2$, and the difference of means $|\mu_{1}-\mu_{2}|=L$ for a large $L\gg 1$. Given this prior information, one can estimate the the average of the mixture, that yields $\frac{\mu_{1}+\mu_{2}}{2}$. Solving equations obtained by $\mu_{1}+\mu_{2}$ and $\mu_{1}-\mu_{2}=L$, yields $\mu_{1}$ and $\mu_{2}$. The variance of the mixture is $1+\frac{L^{2}}{4}>\frac{L^{2}}{4}$. With additional Chernoff type bounds, one can show that given $n$ samples the error in estimating the average is

Therefore to estimate the means to a small accuracy we need $n\geq L^{2}$, i.e., more the separation, more samples are necessary.

A similar phenomenon happens in the convergence of the correlation matrices, where the variances of quantities of interest increases with separation. In other words, for the span to be accurate the number of samples necessary increases with the separation. To overcome this phenomenon, a natural idea is to cluster the Gaussians such that the means of components in the same cluster are close and then apply scheffe on the span within each cluster.

Even though spectral clustering algorithms are studied in , they assume that the weights are strictly bounded away from , which does not hold here. We use a simple recursive clustering algorithm that takes a cluster $C$ with average ${\overline{\boldsymbol{\mu}}}(C)$. If there is a component in the cluster such that $\sqrt{w_{i}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}$ is $\Omega(\log(n/\delta))$, then the algorithm divides the cluster into two nonempty clusters without any mis-clustering.

For technical reasons similar to the above example, we also use a coarse clustering algorithm that ensures that the mean separation is $\widetilde{{\cal O}}(d^{1/4})$ within each cluster. The algorithm can be summarized as:

Variance estimation: Use first $k+1$ samples and estimate the minimum distance among sample-pairs to estimate $\sigma^{2}$.

Coarse clustering: Using a single-linkage algorithm, group the samples such that within each cluster formed, the mean separation is smaller than $\widetilde{{\cal O}}(d^{1/4})$.

Recursive clustering: As long as there is a cluster that has samples from more than one component with means far apart, (described by a condition on the norm of its covariance matrix in the algorithm) estimate its largest eigenvector and project samples of this cluster onto this eigenvector and cluster them. This hierarchical method is continued until there are clusters that contain close-by-components.

Search in the span: The resulting clusters contain components that are close-by, i.e., $\left|\left|{\boldsymbol{\mu}_{i}}-{\boldsymbol{\mu}_{j}}\right|\right|_{2}<{\cal O}(k^{3/2}{\hat{\sigma}}^{2}\log\frac{n}{\delta})$. We approximate the span of means by the top $k-1$ eigenvectors and the mean vector, and perform an exhaustive search using Modified scheffe.

We now describe these steps stating the performance of each step.

2 Sketch of correctness

To simplify the bounds and expressions, we assume that $d>1000$ and $\delta\geq\min(2n^{2}e^{-d/10},1/3)$. For smaller values of $\delta$, we run the algorithm with error $1/3$ and repeat it ${\cal O}(\log\frac{1}{\delta})$ times to choose a set of candidate mixtures ${\cal F}_{\delta}$. By Chernoff-bound with error $\leq\delta$, ${\cal F}_{\delta}$ contains a mixture $\epsilon$-close to $\mathbf{f}$. Finally, we run modified scheffe on ${\cal F}_{\delta}$ to obtain a mixture that is close to $\mathbf{f}$. By the union bound and Lemma 1, the error is $\leq 2\delta$.

Variance estimation: Let $\hat{\sigma}$ be the variance estimate from step 1. In high dimensions, the difference between two random samples from a Gaussian concentrates. This is made precise in the next lemma which states $\hat{\sigma}$ is a good estimate of the variance. Then the following is a simple application of Gaussian tail bounds.

Given $n$ samples from the $k$-component mixture, with probability $1-2\delta$,

Coarse single-linkage clustering: The second step is a single-linkage routine that clusters mixture components with far means. Single-linkage is a simple clustering scheme that starts out with each data point as a cluster, and at each step merges the two that are closest to form larger clusters. The algorithm stops when the distance between clusters is larger than a pre-specified threshold.

Suppose the samples are generated by an one-dimensional mixture of $k$ components that are far, then with high probability, when the algorithm generates $k$ clusters and all the samples within a cluster are generated by a single component. More precisely, if $\forall i,j\in[k]$, $|\mu_{i}-\mu_{j}|=\Omega(\sigma\log n)$, then all the $n$ samples concentrate around their respective means and the separation between any two samples from different components would be larger than the largest separation between any two samples from the same component. Hence for a suitable value of threshold, single-linkage correctly identifies the clusters. For $d$-dimensional Gaussian mixtures a similar notion holds true, with minimum separation $\Omega(d^{1/4}\log\frac{n}{\delta})$. More precisely,

After Step 2 of Learn k-sphere, with probability $\geq 1-2\delta$, all samples from each component will be in the same cluster and the maximum distance between two components within each cluster is \leq 10k\sigma\bigl{(}d\log\frac{n^{2}}{\delta}\bigr{)}^{1/4}.

Recursive spectral-clustering: The clusters formed at this step consists of components with mean separation ${\cal O}(d^{1/4}\log\frac{n}{\delta})$. We now recursively zoom into the clusters formed and show that it is possible to cluster the components with much smaller mean separation. Note that since the matrix is symmetric, the largest magnitude of the eigenvalue is same as the spectral norm. We first find the largest eigenvector of

which is the sample covariance matrix with its diagonal term reduced by $\hat{\sigma}^{2}.$ If there are two components with means far apart, then using single-linkage we divide the cluster into two. The following lemma shows that this step performs accurate clustering of components with means well separated.

Let $n\geq c\cdot\frac{dk^{4}}{\epsilon}\log\frac{n^{3}}{\delta}$. After recursive clustering, with probability $\geq 1-4\delta$. the samples are divided into clusters such that for each component $i$ within any cluster $C$, $\sqrt{w_{i}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}\leq 25\sigma\sqrt{k^{3}\log\frac{n^{3}}{\delta}}$ . Furthermore, all the samples from one component remain in a single cluster.

Exhaustive search and Scheffe: After step 3, all clusters have a small weighted radius $\sqrt{w_{i}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}\leq 25\sigma\sqrt{k^{3}\log\frac{n^{3}}{\delta}}$, the the eigenvectors give an accurate estimate of the span of ${\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)$ within each cluster. More precisely,

Let $n\geq c\cdot\frac{dk^{9}}{\epsilon^{4}}\log^{2}\frac{d}{\delta}$ for some constant $c$. After step 3, with probability $\geq 1-7\delta$ the following holds: if $|C|\geq n\epsilon/5k$, then the projection of $[{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)]/\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}$ on the space orthogonal to the span of top $k-1$ eigenvectors has magnitude $\leq\frac{\epsilon\sigma}{8\sqrt{2}k\sqrt{w_{i}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|}_{2}$.

We now have accurate estimates of the spans of the clusters and each cluster has components with close means. It is now possible to grid the set of possibilities in each cluster to obtain a set of distributions such that one of them is close to the underlying. There is a trade-off between a dense grid to obtain a good estimation and the computation time required. The final step takes the sparsest grid possible to ensure an error $\leq\epsilon$. This is quantized below.

Let $n\geq c\cdot\frac{dk^{9}}{\epsilon^{4}}\log^{2}\frac{d}{\delta}$ for some constant $c$. Then Algorithm Learn k-sphere with probability $\geq 1-9\delta$, outputs a distribution $\hat{\mathbf{f}}$ such that $D({\hat{\mathbf{f}}},{\mathbf{f}})\leq 1000\epsilon$. Furthermore, the algorithm runs in time {\cal O}\Big{(}n^{2}d\log n+d^{2}\Big{(}\frac{k^{7}}{\epsilon^{3}}\log\frac{d}{\delta}\Big{)}^{k^{2}}\Big{)}.

Note that the run time is calculated based on the efficient implementation of single-linkage and the exponential term is not optimized. We now study mixtures in one-dimension and provide an estimator using Modified Scheffe.

Mixtures in one dimension

Given $n$ independent samples $x_{1},\ldots,x_{n}$ from $N(\mu,\sigma^{2})$, there are two samples $x_{j},x_{k}$ such that $|x_{j}-\mu|\leq\sigma\frac{7\log 2/\delta}{2n}$ and $|x_{j}-x_{k}-\sigma|\leq 2\sigma\frac{7\log 2/\delta}{2n}$ with probability $\geq 1-\delta$.

Proof The density of $N(\mu,\sigma^{2})$ is $\geq(7\sigma)^{-1}$ in the interval $[\mu-\sqrt{2}\sigma,\mu+\sqrt{2}\sigma]$. Therefore, the probability that a sample occurs in the interval $\mu-\epsilon\sigma,\mu+\epsilon\sigma$ is $\geq 2\epsilon/7$. Hence, the probability that none of the $n$ samples occurs in $[\mu-\epsilon\sigma,\mu+\epsilon\sigma]$ is $\leq(1-2\epsilon/7)^{n}\leq e^{-2n\epsilon/7}$. If $\epsilon\geq\frac{7\log 2/\delta}{2n}$, then the probability that none of the samples occur in the interval is $\leq\delta/2$. A similar argument shows that there is a sample within interval, $[\mu+\sigma-\epsilon\sigma,\mu+\sigma+\epsilon\sigma]$, proving the lemma.

The above observation can be translated into selecting a pool of candidate distributions such that one of the distributions is close to the underlying distribution.

Given $n\geq\frac{120k\log\frac{4k}{\delta}}{\epsilon}$ samples from a mixture $f$ of $k$ Gaussians. Let $S=\{N(x_{j},(x_{j}-x_{k})^{2})\,:\,1\leq j,k\leq n\}$ be a set of Gaussians and $W=\{0,\frac{\epsilon}{2k},\frac{2\epsilon}{2k}\ldots,1\}$ be the set of weights. Let

be a set of n^{2k}\bigl{(}\frac{2k}{\epsilon}\bigr{)}^{k-1}\leq n^{3k-1} candidate mixture distributions. There exists a $\hat{f}\in{\cal F}$ such that $D({f},{\hat{f}})\leq\epsilon$.

Let $f=(w_{1},w_{2},\ldots w_{k},p_{1},p_{2},\ldots p_{k})$. For $\hat{f}=(\hat{w}_{1},\hat{w}_{2},\ldots,\hat{w}_{k-1},1-\sum^{k-1}_{i=1}\hat{w}_{i},\hat{p}_{1},\hat{p}_{2},\ldots\hat{p}_{k})$, by the triangle inequality,

We show that there is a distribution in $\hat{f}\in{\cal F}$ such that the sum above is bounded by $\epsilon$. Since we quantize the grids as multiples of $\epsilon/2k$, we consider distributions in ${\cal F}$ such that each $|\hat{w}_{i}-w_{i}|\leq\epsilon/4k$, and therefore $\sum_{i}|\hat{w}_{i}-w_{i}|\leq\frac{\epsilon}{2}$.

We now show that for each $p_{i}$ there is a $\hat{p}_{i}$ such that $w_{i}D({p_{i}},{\hat{p}_{i}})\leq\frac{\epsilon}{2k}$, thus proving that $D({f},{\hat{f}})\leq\epsilon$. If $w_{i}\leq\frac{\epsilon}{4k}$, then $w_{i}D({p_{i}},{\hat{p}_{i}})\leq\frac{\epsilon}{2k}$. Otherwise, let $w^{\prime}_{i}>\frac{\epsilon}{4k}$ be the fraction of samples from $p_{i}$. By Lemma 9 and 14, with probability $\geq 1-\delta/2k$,

Since $w_{i}>\epsilon/4k$, with probability $\geq 1-\delta/2k$, $w_{i}\leq 2w^{\prime}_{i}$. By the union bound with probability $\geq 1-\delta/k$, $w_{i}D({p_{i}},{\hat{p}_{i}})\leq\frac{60\log\frac{4k}{\delta}}{n}$. Hence if $n\geq\frac{120k\log\frac{4k}{\delta}}{\epsilon}$, the above quantity is less than $\epsilon/2k$. The total error probability is $\leq\delta$ by the union bound. ∎

Running Modified Scheffe algorithm on the above set of candidates ${\cal F}$ yields a mixture that is close to the underlying one. By Lemma 1 and the above lemma we get

Let $n\geq c\cdot\frac{k\log\frac{k}{\epsilon\delta}}{\epsilon^{2}}$ for some constant $c$. There is an algorithm that runs in time

and returns a mixture $\hat{f}$ such that $D({f},{\hat{f}})\leq 1000\epsilon$ with error probability $\leq 2\delta$.

The above bound matches the independent and contemporary result by for $k=2$. While the process of identifying the candidate means is same for both the papers, the process of identifying the variances and proof techniques are different.

Acknowledgements

We thank Sanjoy Dasgupta, Todd Kemp, and Krishnamurthy Vishwanathan for helpful discussions.

References

Appendix A Useful tools

The Bhattacharyya parameter for two one dimensional Gaussian distributions $p_{1}=N(\mu_{1},\sigma_{1}^{2})$ and $p_{2}=N(\mu_{2},\sigma_{2}^{2})$ is

For Gaussian distributions the Bhattacharyya parameter is (see ), $B(p_{1},p_{2})=ye^{-x}$, where $x=\frac{(\mu_{1}-\mu_{2})^{2})}{4(\sigma_{1}^{2}+\sigma_{2}^{2})}$ and $y=\sqrt{\frac{2\sigma_{1}\sigma_{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}}$ . Observe that

Substituting the value of $x$ results in the lemma. ∎

For any two Gaussian product distributions $\mathbf{p}_{1}$ and $\mathbf{p}_{2}$,

A.2 Concentration inequalities

We use the following concentration inequalities for Gaussian, Chi-Square, and sum of Bernoulli random variables in the rest of the paper.

For a Gaussian random variable $X$ with mean $\mu$ and variance $\sigma^{2}$,

If $Y_{1},Y_{2},\ldots Y_{n}$ be $n$ i.i.d.Gaussian variables with mean and variance $\sigma^{2}$, then

Furthermore for a fixed vector $\mathbf{a}$,

If $X_{1},X_{2}\ldots X_{n}$ are distributed according to Bernoulli $p$, then with probability $1-\delta$,

We now state a non-asymptotic concentration inequality for random matrices that helps us bound errors in spectral algorithms.

Let $\mathbf{y}(1),\mathbf{y}(2),\ldots,\mathbf{y}(n)$ be generated according to $N(0,\Sigma)$. For every $\epsilon\in(0,1)$ and $t\geq 1$, if n\geq c^{\prime}d\bigl{(}\frac{t}{\epsilon}\bigr{)}^{2} for some constant $c^{\prime}$, then with probability $\geq 1-2e^{-t^{2}n}$,

A.3 Matrix eigenvalues

We now state few simple lemmas on the eigenvalues of perturbed matrices.

Let $\lambda^{A}_{1}\geq\lambda^{A}\geq\ldots\lambda^{A}_{d}\geq 0$ and $\lambda^{B}_{1}\geq\lambda^{B}\geq\ldots\lambda^{B}_{d}\geq 0$ be the eigenvalues of two symmetric matrices $A$ and $B$ respectively. If $\left|\left|A-B\right|\right|\leq\epsilon$, then $\forall\,i$, $|\lambda^{A}_{i}-\lambda^{B}_{i}|\leq\epsilon$.

Let $\mathbf{u}_{1},\mathbf{u}_{2},\ldots\mathbf{u}_{d}$ be a set of eigenvectors of $A$ that corresponds to $\lambda^{A}_{1},\lambda^{A}_{2},\ldots\lambda^{A}_{d}$. Similarly let $\mathbf{v}_{1},\mathbf{v}_{2},\ldots\mathbf{v}_{d}$ be eigenvectors of $B$ Consider the first eigenvalue of $B$,

Now consider an $i>1$. If $\lambda^{B}_{i}<\lambda^{A}_{i}-\epsilon$, then by definition of eigenvalues

Now consider a unit vector $\sum^{i}_{j=1}\alpha_{j}\mathbf{u}_{j}$ in the span of $\mathbf{u}_{1},\ldots\mathbf{u}_{i}$, that is orthogonal to $\mathbf{v}_{1},\ldots\mathbf{v}_{i-1}$. For this vector,

a contradiction. Hence, $\forall i\leq d$, $\lambda^{B}_{i}\geq\lambda^{A}_{i}-\epsilon$. The proof in the other direction is similar and omitted. ∎

Let $A=\sum^{k}_{i=1}\eta^{2}_{i}\mathbf{u}_{i}\mathbf{u}^{t}_{i}$ be a positive semidefinite symmetric matrix for $k\leq d$. Let $\mathbf{u}_{1},\mathbf{u}_{2},\ldots\mathbf{u}_{k}$ span a $k-1$ dimensional space. Let $B=A+R$, where $\left|\left|R\right|\right|\leq\epsilon$. Let $\mathbf{v}_{1},\mathbf{v}_{2},\ldots\mathbf{v}_{k-1}$ be the top $k-1$ eigenvectors of $B$. Then the projection of $\mathbf{u}_{i}$ in space orthogonal to $\mathbf{v}_{1},\mathbf{v}_{2},\ldots\mathbf{v}_{k-1}$ is $\leq\frac{2\sqrt{\epsilon}}{\eta_{i}}$.

Let $\mathbf{u}_{i}=\sum^{k-1}_{j=1}\alpha_{i,j}\mathbf{v}_{j}+\sqrt{1-\sum^{k-1}_{j=1}\alpha^{2}_{i,j}}\mathbf{u}^{\prime}$, for a vector $\mathbf{u}^{\prime}$ orthogonal to $\mathbf{v}_{1},\mathbf{v}_{2},\ldots\mathbf{v}_{k-1}$. We compute $\mathbf{u}^{\prime t}A\mathbf{u}^{\prime}$ in two ways. Since $A=B-R$,

Since $\mathbf{u}^{\prime}$ is orthogonal to first $k$ eigenvectors, we have $\left|\left|B\mathbf{u}^{\prime}\right|\right|_{2}\leq 3\epsilon$ and hence $|\mathbf{u}^{\prime(}B-R)\mathbf{u}^{\prime}|\leq 4\epsilon$.

We have shown that the above quantity is $\leq 4\epsilon$. Therefore \bigl{(}1-\sum^{k-1}_{j=1}\alpha^{2}_{i,j}\bigr{)}^{1/2}\leq 2\sqrt{\epsilon}/\eta_{i}. ∎

Appendix B Selection from a set of candidate distributions

We first present the algorithm Scheffe* with running time $\widetilde{{\cal O}}(|{\cal F}|^{2}Tn)$.

We make the following modification to the algorithm where we reduce the size of potential distributions by half in every iteration.

Algorithm modified Scheffe Input: set ${\cal F}$ of candidate distributions, $\epsilon:$ upper bound on $\min_{f_{i}\in{\cal F}}D({f},{f_{i}})$, $n$ independent samples $x_{1},\ldots,x_{n}$ from $f$. 1. Let ${\cal G}={\cal F}$, ${\cal C}\leftarrow\emptyset$ 2. Repeat until $|{\cal G}|>1$: (a) Randomly form $|{\cal G}|/2$ pairs of distributions in ${\cal G}$ and run Scheffe* on each pair using the $n$ samples. (b) Replace ${\cal G}$ with the $|{\cal G}|/2$ winners. (c) Randomly select a set ${\cal A}$ of $\min\{|{\cal G}|,|{\cal F}|^{1/3}\}$ elements from ${\cal G}$. (d) Run Scheffe* on each pair in ${\cal A}$ and add the distributions with most wins to ${\cal C}$. 3. Run Scheffe* on ${\cal C}$ and output the winner

For the ease of proof, we assume that $\delta\geq\frac{10\log|{\cal F}|}{|{\cal F}|^{1/3}}$. If $\delta<\frac{10\log|{\cal F}|}{|{\cal F}|^{1/3}}$, we run the algorithm with error probability $1/3$ and repeat it ${\cal O}(\log\frac{1}{\delta})$ times to choose a set of candidate mixtures ${\cal F}_{\delta}$. By Chernoff-bound with error probability $\leq\delta$, ${\cal F}_{\delta}$ contains a mixture close to $f$. Finally, we run Scheffe* on ${\cal F}_{\delta}$ to obtain a mixture that is close to $f$.

For any set ${\cal A}$ and a distribution $p$, given $n$ independent samples from $p$ the empirical probability $\mu_{n}({\cal A})$ has a distribution around $p({\cal A})$ with standard deviation $\sim\frac{1}{\sqrt{n}}$. Together with an observation in Scheffe estimation in one can show that if the number of samples $n={\cal O}\left(\frac{\log\frac{|{\cal F}|}{\delta}}{\epsilon^{2}}\right)$, then Scheffe* has a guarantee $10\max(\epsilon,D({f},{{\cal F}}))$ with probability $\geq 1-\delta$.

Since we run Scheffe* at most $|{\cal F}|(2\log|{\cal F}|+1)$ times, choosing $\delta=\delta/(4|{\cal F}|\log|{\cal F}|+2|{\cal F}|)$ results in the sample complexity of

and the total error probability of $\delta/2$ for all runs of Scheffe* during the algorithm. The above value of $n$ dictates our sample complexity. We now consider the following two cases:

Appendix C Lower bound

We first show a lower bound for a single Gaussian distribution and generalize it to mixtures.

The proof is an application of the following version of Fano’s inequality . It states that we cannot simultaneously estimate all distributions in a class using $n$ samples if they satisfy certain conditions.

(Fano’s Inequality) Let $f_{1},\ldots,f_{r+1}$ be a collection of distributions such that for any $i\neq j$, $D({f_{i}},{f_{j}})\geq\alpha$, and $KL(f_{i},f_{j})\leq\beta$. Let $f$ be an estimate of the underlying distribution using $n$ i.i.d. samples from one of the $f_{i}$’s. Then,

We consider $d-$dimensional spherical Gaussians with identity covariance matrix, with means along any coordinate restricted to $\pm\frac{c\epsilon}{\sqrt{d}}$. The KL divergence between two spherical Gaussians with identity covariance matrix is the squared distance between their means. Therefore, any two distributions we consider have KL distance at most

We now consider a subset of these $2^{d}$ distributions to obtain a lower bound on $\alpha$. By the Gilbert-Varshamov bound, there exists a binary code with $\geq 2^{d/8}$ codewords of length $d$ and minimum distance $d/8$. Consider one such code. Now for each codeword, map $1\to\frac{c\epsilon}{\sqrt{d}}$ and $0\to-\frac{c\epsilon}{\sqrt{d}}$ to obtain a distribution in our class. We consider this subset of $\geq 2^{d/8}$ distributions as our $f_{i}$’s.

C.2 Mixtures of k𝑘k Gaussians

We now provide a lower bound on the sample complexity of learning mixtures of $k$ Gaussians in $d$ dimensions. We extend the construction for learning a single spherical Gaussian to mixtures of $k$ Gaussians and show a lower bound of $\Omega(kd/\epsilon^{2})$ samples. We will again use Fano’s inequality over a class of $2^{kd/64}$ distributions as described next.

We now choose $\boldsymbol{\mu}_{1},\ldots,\boldsymbol{\mu}_{k}$’s extremely well-separated. The class of distributions we consider will be a mixture of $k$ components, where the $j$th component is a distribution from ${\cal P}$ shifted by $\boldsymbol{\mu}_{j}$. Since the $\boldsymbol{\mu}$’s will be well separated, we will use the results from last section over each component.

of $k$ spherical Gaussians. We consider this class of $T^{k}=2^{kd/8}$ distributions. By the Gilbert-Varshamov bound, for any $T\geq 2$, there is a $T$-ary codes of length $k$, with minimum distance $\geq k/8$ and number of codewords $\geq 2^{k/8}$. This implies that among the $T^{k}=2^{dk/8}$ distributions, there are $2^{kd/64}$ distributions such that any two tuples $(i_{1},\ldots,i_{k})$ and $(i_{1}^{\prime},\ldots,i_{k}^{\prime})$ corresponding to different distributions differ in at least $k/8$ locations.

If we choose the $\boldsymbol{\mu}$’s well separated, the components of any mixture distribution have very little overlap. For simplicity, we choose $\boldsymbol{\mu}_{j}$’s satisfying

This implies that for $j\neq l$, $\left|\left|P_{ij}-P_{i^{\prime}l}\right|\right|_{1}<(\epsilon/2dk)^{10}$. Therefore, for two different mixture distributions,

where $(a)$ follows form the fact that two mixtures have overlap only in the corresponding components, $(b)$ uses the fact that at least in $k/8$ components $i_{j}\neq i_{j}^{\prime}$, and then uses the lower bound from the previous section.

Now, to upper bound the KL divergence, we simply use the convexity, namely for any distributions $P_{1}\ldots P_{k}$ and $Q_{1}\ldots Q_{k}$, let $\bar{P}$ and $\bar{Q}$ be the mean distributions. Then,

By the construction and from the previous section, for any $j$,

Therefore, we can take $\beta=4c^{2}\epsilon^{2}$.

which for $c_{1}=128,c=128.1$ and $n<\frac{dk}{8^{8}\epsilon^{2}}$ is at least $\epsilon$.

Appendix D Proofs for k𝑘k spherical Gaussians

We first state a simple concentration result that helps us in other proofs.

We prove the lower bound, the proof for the upper bound is similar and omitted. Since $\mathbf{X}$ and $\mathbf{Y}$ are Gaussians, $\mathbf{X}-\mathbf{Y}$ is distributed as $N(\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2},2\sigma^{2})$. Rewriting $\left|\left|\mathbf{X}-\mathbf{Y}\right|\right|_{2}$

Furthermore $(\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2})\cdot\mathbf{Z}$ is sum of Gaussians and hence a Gaussian distribution. It has mean and variance $2\sigma^{2}\left|\left|\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2}\right|\right|^{2}_{2}$. Therefore, by Lemma 15 with probability $1-\delta/n^{2}$,

By the union bound with probability $1-2\delta/n^{2}$,

There are ${n\choose 2}$ pairs and the lemma follows by the union bound. ∎

We show that if Equations (1) and (2) are satisfied, then the lemma holds. The error probability is that of Lemma 23 and is $\leq 2\delta$. Since the minimum is over $k+1$ indices, at least two samples are from the same component. Applying Equations (1) and (2) for these two samples

Similarly by Equations (1) and (2) for any two samples $\mathbf{X}(a),\mathbf{X}(b)$ in $[k+1]$,

where the last inequality follows from the fact that $\alpha^{2}-4\alpha\beta\geq-4\beta^{2}$. The result follows from the assumption that $d>20\log n^{2}/\delta$.

D.2 Proof of Lemma 5

We show that if Equations (1) and (2) are satisfied, then the lemma holds. The error probability is that of Lemma 23 and is $\leq 2\delta$. Since Equations (1) and (2) are satisfied, by the proof of Lemma 4, $|{\hat{\sigma}}^{2}-\sigma^{2}|\leq 2.5\sigma^{2}\sqrt{\frac{\log(n^{2}/\delta)}{d}}$. If two samples $X(a)$ and $X(b)$ are from the same component, by Lemma 23,

By Lemma 4, the above quantity is less than $2d{\hat{\sigma}}^{2}+23{\hat{\sigma}}^{2}\sqrt{d\log\frac{n^{2}}{\delta}}$. Hence all the samples from the same component are in a single cluster.

Suppose there are two samples from different components in a cluster, then by Equations (1) and (2),

Relating ${\hat{\sigma}}^{2}$ and $\sigma^{2}$ using Lemma 4,

Hence \left|\left|{\boldsymbol{\mu}_{i}}-{\boldsymbol{\mu}_{j}}\right|\right|_{2}\leq 10\sigma\bigl{(}d\log\frac{n^{2}}{\delta}\bigr{)}^{1/4}. There are at most $k$ components; therefore, any two components within the same cluster are at a distance \leq 10k\sigma\bigl{(}d\log\frac{n^{2}}{\delta}\bigr{)}^{1/4}.

D.3 Proof of Lemma 6

The proof is involved and we show it in steps. We first show few concentration bounds which we use later to argue that the samples are clusterable when the sample covariance matrix has a large eigenvalue. Let $\hat{w}_{i}$ be the fraction of samples from component $i$. Let $\hat{\boldsymbol{\mu}}_{i}$ be the empirical average of samples from $\mathbf{p}_{i}$. Let ${\hat{\overline{\boldsymbol{\mu}}}}(C)$ be the empirical average of samples in cluster $C$. If $C$ is the entire set of samples we use ${\hat{\overline{\boldsymbol{\mu}}}}$ instead of ${\hat{\overline{\boldsymbol{\mu}}}}(C)$. We first show a concentration inequality that we use in rest of the calculations.

Given $n$ samples from a $k$-component Gaussian mixture with probability $\geq 1-2\delta$, for every component $i$

The second inequality uses the fact that $d\geq 20\log n^{2}/\delta$. For bounding the weights, observe that by Lemma 17 with probability $\geq 1-\delta/k$,

By the union bound the error probability is $\leq 2k\delta/2k=\delta$. ∎

A simple application of triangle inequality yields the following lemma.

Given $n$ samples from a $k$-component Gaussian mixture if Equation (3) holds, then

Given $n$ samples from a $k$-component Gaussian mixture, if Equation (3) holds and the maximum distance between two components is \leq 10k\sigma\bigl{(}d\log\frac{n^{2}}{\delta}\bigr{)}^{1/4}, then $\left|\left|{\hat{\overline{\boldsymbol{\mu}}}}-{\overline{\boldsymbol{\mu}}})\right|\right|_{2}\leq c\sigma\sqrt{\frac{dk\log\frac{n^{2}}{\delta}}{n}},$ for a constant $c$.

Hence by Equation (3) and the fact that the maximum distance between two components is \leq 10k\sigma\bigl{(}d\log\frac{n^{2}}{\delta}\bigr{)}^{1/4},

For $n\geq d\geq\max(k^{4},20\log n^{2}/\delta,1000)$, we get the above term is $\leq c\sqrt{\frac{kd\log n^{2}/\delta}{n}}\sigma$, for some constant $c$. ∎

We now make a simple observation on covariance matrices.

Given $n$ samples from a $k$-component mixture,

Observe that for any two vectors $\mathbf{u}$ and $\mathbf{v}$,

Applying the above observation to $\mathbf{u}=\hat{\boldsymbol{\mu}}_{i}-{\hat{\overline{\boldsymbol{\mu}}}}$ and $\mathbf{v}={\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}$, we get

The lemma follows from triangle inequality. ∎

The following lemma immediately follows from Lemmas 26 and 27.

Given $n$ samples from a $k$-component Gaussian mixture, if Equation (3) and the maximum distance between two components is \leq 10k\sigma\bigl{(}d\log\frac{n^{2}}{\delta}\bigr{)}^{1/4}, then

For a set of samples $\mathbf{X}(1),\ldots\mathbf{X}(n)$ from a $k$-component mixture,

where $\hat{w}_{i}$ and $\hat{\boldsymbol{\mu}}_{i}$ are the empirical weights and averages of components $i$ and ${\hat{\overline{\boldsymbol{\mu}}}}=\frac{1}{n}\sum^{n}_{i=1}\mathbf{X}_{i}$.

First observe that for any set of points $x_{i}$ and their average $\hat{x}$ and any value $a$,

Summing over all components results in the lemma. ∎

We now bound the error in estimating the eigenvalue of the covariance matrix.

Given $\mathbf{X}(1),\ldots\mathbf{X}(n)$, $n$ samples from a $k$-component Gaussian mixture, if Equations (1), (2), and (3) hold, then with probability $\geq 1-2\delta$,

Since Equations (1), (2), and (3) hold, conditions in Lemmas 26 and 28 are satisfied. By Lemma 28,

By Lemma 29, the covariance matrix can be rewritten as

The second term in Equation (6) is bounded by Lemma 25. Hence together with the fact that $d\geq 20\log n^{2}/\delta$ we get that with probability $\geq 1-2\delta$, the second and third terms are bounded by ${\cal O}\left(\sigma^{2}\sqrt{\frac{dk}{n}\log\frac{n^{2}}{\delta}}\right).$ ∎

Let $\mathbf{u}$ be the largest eigenvector of the sample covariance matrix and $n\geq c\cdot dk^{2}\log\frac{n^{2}}{\delta}$. If $\max_{i}\sqrt{\hat{w}_{i}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}\right|\right|_{2}=\alpha\sigma$ and Equation (LABEL:eq:covconc) holds, then there exists $i$ such that $|\mathbf{u}\cdot({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}})|\geq\sigma(\alpha-1-1/\alpha)/\sqrt{k}$.

Observe that $\left|\left|\sum_{j}w_{j}\mathbf{v}_{j}\mathbf{v}^{t}_{j}\right|\right|\geq\left|\left|\sum_{j}w_{j}\mathbf{v}_{j}\mathbf{v}^{t}_{j}\frac{\mathbf{v}_{i}}{\left|\left|\mathbf{v}_{i}\right|\right|}\right|\right|_{2}\geq w_{i}\left|\left|\mathbf{v}_{i}\right|\right|^{2}_{2}$. Therefore

Hence by Lemma 30 and the triangle inequality, the largest eigenvalue of the sample-covariance matrix is $\geq\alpha^{2}\sigma^{2}-c(n)$. Similarly by applying Lemma 30 again we get,$\left|\left|\sum^{k}_{i=1}\hat{w}_{i}({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}})({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}})^{t}\mathbf{u}\right|\right|_{2}\geq\alpha^{2}\sigma^{2}-2c(n).$ By triangle inequality and Cauchy-Schwartz inequality,

Hence $\sqrt{k}\alpha\sigma\max_{i}|({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}})\cdot\mathbf{u}|\geq\alpha^{2}\sigma^{2}-2c(n)$. The lemma follows by substituting the bound on $n$ in $c(n)$. ∎

We now make a simple observation on Gaussian mixtures.

The samples from a subset of components $A$ of the Gaussian mixture are distributed according to a Gaussian mixture of components $A$ with weights being $w_{i}^{\prime}=w_{i}/(\sum_{j\in A}w_{j})$.

Observe that we run the recursive clustering at most $n$ times. At every step, the underlying distribution within a cluster is a Gaussian mixture. Let Equations (1), (2) hold with probability $1-2\delta$. Let Equations (3) (LABEL:eq:covconc) all hold with probability $\geq 1-\delta^{\prime}$, where $\delta^{\prime}=\delta/2n$ at each of $n$ steps. By the union bound the total error is $\leq 2\delta+\delta^{\prime}\cdot 2n\leq 3\delta$. Since Equations (1), (2) holds, the conditions of Lemmas 4 and 5 hold. Furthermore it can be shown that discarding at most $n\epsilon/4k$ samples at each step does not affect the calculations.

We first show that if $\sqrt{w_{i}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}\geq 25\sqrt{k^{3}\log(n^{3}/\delta)}\sigma$, then the algorithm gets into the loop. Let $w_{i}^{\prime}$ be the weight of the component within the cluster and $n^{\prime}\geq n\epsilon/5k$ be the number of samples in the cluster. Let $\alpha=25\sqrt{k^{3}\log(n^{3}/\delta)}$. By Fact 32, the components in cluster $C$ have weight $w_{i}^{\prime}\geq w_{i}$. Hence $\sqrt{w_{i}^{\prime}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}\geq\alpha\sigma$. Since $\sqrt{w_{i}^{\prime}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}\geq\alpha\sigma$, and by Lemma 5 $\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|\leq 10k\sigma(d\log n^{2}/\delta)^{1/4}$, we have $w_{i}^{\prime}\geq\alpha^{2}/(100k^{2}\sqrt{d\log n^{2}/\delta})$. Hence by lemma 24, $w_{i}^{\prime}\geq w_{i}/2$ and $\sqrt{\hat{w}_{i}^{\prime}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}\geq\alpha\sigma/\sqrt{2}$. Hence by Lemma 30 and triangle inequality the largest eigenvalue of $S(C)$ is

Therefore the algorithm gets into the loop.

If $n^{\prime}\geq n\epsilon/8k^{2}\geq c\cdot dk^{2}\log\frac{n^{3}}{\delta}$, then by Lemma 31, there exists a component $i$ such that $|\mathbf{u}\cdot({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C))|\geq\sigma(\alpha/\sqrt{2}-1-\sqrt{2}/\alpha)/\sqrt{k}$, where $\mathbf{u}$ is the top eigenvector of the first $n\epsilon/4k^{2}$ samples.

Observe that $\sum_{i\in C}w_{i}\mathbf{u}\cdot({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C))=0$ and $\max_{i}|\mathbf{u}\cdot({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C))|\geq\sigma(\alpha/\sqrt{2}-1-\sqrt{2}/\alpha)/\sqrt{k}$. Let ${\boldsymbol{\mu}_{i}}$ be sorted according to their values of $\mathbf{u}\cdot({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C))$, then

where the last inequality follows from Lemma 4 and the fact that $d\geq 20\log n^{2}/\delta$. For a sample from component $\mathbf{p}_{i}$, similar to the proof of Lemma 5, by Lemma 15, with probability $\geq 1-\delta/n^{2}k$,

where the second inequality follows from Lemma 4. Since there are two components that are far apart by $\geq 9\hat{\sigma}\sqrt{\log\frac{n^{2}}{\delta}}\hat{\sigma}$ and the maximum distance between a sample and its mean is $\leq 2{\hat{\sigma}}\sqrt{\log(n^{2}k/\delta)}$ and the algorithm divides into at-least two non-empty clusters such that no two samples from the same distribution are clustered into two clusters.

For the second part observe that by the above concentration on $\mathbf{u}$, no two samples from the same component are clustered differently irrespective of the mean separation. Note that we are using the fact that each sample is clustered at most $2k$ times to get the bound on the error probability. The total error probability by the union bound is $\leq 4\delta$. ∎

D.4 Proof of Lemma 7

We show that if the conclusions in Lemmas 6 and 24 holds, then the lemma is satisfied. We also assume that the conclusions in Lemma 30 holds for all the clusters with error probability $\delta^{\prime}=\delta/k$. By the union bound the total error probability is $\leq 7\delta$.

Let $\mathbf{v}_{1},\mathbf{v}_{2},\ldots\mathbf{v}_{k-1}$ be the top eigenvectors of $\frac{1}{|C|}\sum_{i\in C}w_{i}({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C))({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C))^{t}$. Let $\eta_{i}=\sqrt{\hat{w}_{i}^{\prime}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}=\sqrt{\hat{w}_{i}}\sqrt{\frac{n}{|C|}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}$. Let $\boldsymbol{\Delta}_{i}=\frac{{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C))}{\left|\left|({\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C))\right|\right|_{2}}$. Therefore,

Hence by Lemma 20, the projection of $\boldsymbol{\Delta}_{i}$ on the space orthogonal to top $k-1$ eigenvectors of $S(C)$ is

The last inequality follows from the bound on $\hat{w}_{i}$ in Lemma 24.

D.5 Proof of Theorem 8

We show that the theorem holds if the conclusions in Lemmas 7 and 26 holds with error probability $\delta^{\prime}=\delta/k$. Since in the proof of Lemma 7, the probability that Lemma 6 holds is included, Lemma 6 also holds with the same probability. Since there are at most $k$ clusters, by the union bound the total error probability is $\leq 9\delta$.

For every component $i$, we show that there is a choice of mean vector and weight in the search step such that $w_{i}D({\mathbf{p}_{i}},{\hat{\mathbf{p}}_{i}})\leq\epsilon/2k$ and $|w_{i}-\hat{w}_{i}|\leq\epsilon/4k$. That would imply that there is a $\hat{\mathbf{f}}$ during the search such that

Since the weights are gridded by $\epsilon/4k$, there exists a $\hat{w}_{i}$ such that $|w_{i}-\hat{w}_{i}|\leq\epsilon/4k$. We now show that there exists a choice of mean vector such that $w_{i}D({\mathbf{p}_{i}},{\hat{\mathbf{p}}_{i}})\leq\epsilon/2k$. Note that if a component has weight $\leq\epsilon/4k$, the above inequality follows immediately. Therefore we only look at those components with $w_{i}\geq\epsilon/4k$, by Lemma 24, for such components $\hat{w}_{i}\geq\epsilon/5k$ and therefore we only look at clusters such that $|C|\geq n\epsilon/5k$. By Lemmas 14 and for any $i$,

Note that since we are discarding at most $n\epsilon/8k^{2}$ random samples at each step. A total number of $\leq n\epsilon/8k$ random samples are discarded. It can be shown that this does not affect our calculations and we ignore it in this proof. By Lemma 4, the first estimate of $\sigma^{2}$ satisfies $|{\hat{\sigma}}^{2}-\sigma^{2}|\leq 2.5\sigma^{2}\sqrt{\log n^{2}/\delta}$. Hence while searching over values of $\hat{\sigma}^{2}$, there exist one such that $|\sigma^{\prime 2}-\sigma^{2}|\leq\epsilon\sigma^{2}/\sqrt{64dk^{2}}$. Hence,

Therefore if we show that there is a mean vector $\hat{\boldsymbol{\mu}}_{i}$ during the search such that $\left|\left|{\boldsymbol{\mu}_{i}}-\hat{\boldsymbol{\mu}}_{i}\right|\right|_{2}\leq\epsilon\sigma/\sqrt{16k^{2}\hat{w}_{i}}$, that would prove the Lemma. By triangle inequality,

The second inequality follows from the bound on $n$ and the fact that $|C|\geq n\hat{w}_{i}$. Since $w_{i}\geq\epsilon/4k$, by Lemma 24, $\hat{w}_{i}\geq w_{i}/2$, we have

Let $\mathbf{u}_{1}\ldots\mathbf{u}_{k-1}$ are the top eigenvectors the sample covariance matrix of cluster $C$. We now prove that during the search, there is a vector of the form $\sum^{k-1}_{j=1}g_{j}\epsilon_{g}\hat{\sigma}\mathbf{u}_{j}$ such that $\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)-\sum^{k-1}_{j=1}g_{j}\epsilon_{g}\hat{\sigma}\mathbf{u}_{j}\right|\right|_{2}\leq\frac{\epsilon\sigma}{8k\sqrt{w_{i}}}$, during the search, thus proving the lemma. Let $\eta_{i}=\sqrt{w_{i}}\left|\left|{\boldsymbol{\mu}_{i}}-{\overline{\boldsymbol{\mu}}}(C)\right|\right|_{2}$. By Lemma 7, there are set of coefficients $\alpha_{i}$ such that