Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation

Introduction

Gaussian mixture models provide a simple framework for several machine learning problems including clustering, density estimation and classification. Mixtures are especially appealing in high dimensional problems. Perhaps the most common use of Gaussian mixtures is for clustering. Of course, the statistical (and computational) behavior of these methods can degrade in high dimensions. Inspired by the success of variable selection methods in regression, several authors have considered variable selection for clustering. However, there appears to be no theoretical results justifying the advantage of variable selection in high dimensional setting.

To see why some sort of variable selection might be useful, consider clustering $n$ subjects using a vector of $d$ genes for each subject. Typically $d$ is much larger than $n$ which suggests that statistical clustering methods will perform poorly. However, it may be the case that there are only a small number of relevant genes in which case we might expect better behavior by focusing on this small set of relevant genes.

The purpose of this paper is to provide precise bounds on clustering error with mixtures of Gaussians. We consider both the general case where all features are relevant, and the special case where only a subset of features are relevant. Mathematically, we model an irrelevant feature by requiring the mean of that feature to be the same across clusters, so that the feature does not serve to differentiate the groups. Throughout this paper, we use the probability of misclustering an observation, relative to the optimal clustering if we had known the true distribution, as our loss function. This is akin to using excess risk in classification.

This paper makes the following contributions:

We provide information theoretic bounds on the sample complexity of learning a mixture of two isotropic Gaussians in the small mean separation setting that precisely captures the dimension dependence, and matches known sample complexity requirements for some existing algorithms. This also debunks the myth that there is a gap between statistical and computational complexity of learning mixture of two isotropic Gaussians for small mean separation. Our bounds require non-standard arguments since our loss function does not satisfy the triangle inequality.

We consider the high-dimensional setting where only a subset of relevant dimensions determine the mean separation between mixture components and demonstrate that learning is substantially easier as the sample complexity only depends on the sparse set of relevant dimensions. This provides some theoretical basis for feature selection approaches to clustering.

We show that a simple computationally feasible procedure nearly achieves the information theoretic sample complexity even in high-dimensional sparse mean separation settings.

Related Work. There is a long and continuing history of research on mixtures of Gaussians. A complete review is not feasible but we mention some highlights of the work most related to ours.

Perhaps the most popular method for estimating a mixture distribution is maximum likelihood. Unfortunately, maximizing the likelihood is NP-Hard. This has led to a stream of work on alternative methods for estimating mixtures. These new algorithms use pairwise distances, spectral methods or the method of moments.

Pairwise methods are developed in Dasgupta (1999), Schulman and Dasgupta (2000) and Arora and Kannan (2001). These methods require the mean separation to increase with dimension. The first one requires the separation to be $\sqrt{d}$ while the latter two improve it to $d^{1/4}$. To avoid this problem, Vempala and Wang (2004) introduced the idea of using spectral methods for estimating mixtures of spherical Gaussians which makes mean separation independent of dimension. The assumption that the components are spherical was removed in Brubaker and Vempala (2008). Their method only requires the components to be separated by a hyperplane and runs in polynomial time, but requires $n=\Omega(d^{4}\log d)$ samples. Other spectral methods include Kannan et al. (2005), Achlioptas and McSherry (2005) and Hsu and Kakade (2013). The latter uses clever spectral decompositions together with the method of moments to derive an effective algorithm.

Most of these papers are concerned with computational efficiency and do not give precise, statistical minimax upper and lower bounds. None of them deal with the case we are interested in, namely, a high dimensional mixture with sparse mean separation.

We should also point out that the results in different papers are not necessarily comparable since different authors use different loss functions. In this paper we use the probability of misclassifying a future observation, relative to how the correct distribution clusters the observation, as our loss function. This should not be confused with the probability of attributing a new observation to the wrong component of the mixture. The latter loss does not to tend to zero as the sample size increases. Our loss is similar to the excess risk used in classification where we compare the misclassification rate of a classifier to the misclassification rate of the Bayes optimal classifier.

Finally, we remind the reader that our motivation for studying sparsely separated mixtures is that this provides a model for variable selection in clustering problems. There are some relevant recent papers on this problem in the high-dimensional setting. Pan and Shen (2007) use penalized mixture models to do variable selection and clustering simultaneously. Witten and Tibshirani (2010) develop a penalized version of $k$-means clustering. Related methods include Raftery and Dean (2006); Sun et al. (2012) and Guo et al. (2010). The applied bioinformatics literature also contains a huge number of heuristic methods for this problem. None of these papers provide minimax bounds for the clustering error or provide theoretical evidence of the benefit of using variable selection in unsupervised problems such as clustering.

Problem Setup

where $f(\cdot;\mu,\Sigma)$ is the density of $\mathcal{N}(\mu,\Sigma)$, $\sigma>0$ is a fixed constant, and $\theta:=(\mu_{1},\mu_{2})\in\Theta$. We consider two classes $\Theta$ of parameters:

The first class defines mixtures where the components have a mean separation of at least $\lambda>0$. The second class defines mixtures with mean separation $\lambda>0$ along a sparse set of $s\in\{1,\dots,d\}$ dimensions. Also, let $P_{\theta}$ denote the probability measure corresponding to $p_{\theta}$. Throughout the paper, we will use $\phi$ and $\Phi$ to denote the standard normal density and distribution functions.

where the minimum is over all permutations $\pi:\{1,2\}\rightarrow\{1,2\}$. This is the probability of misclustering relative to an oracle that uses the true distribution to do optimal clustering.

We denote by $\widehat{F}_{n}$ any assignment function learned from the data $X_{1},\dots,X_{n}$, also referred to as estimator. The goal of this paper is to quantify how the minimax expected loss (worst case expected loss for the best estimator)

scales with number of samples $n$, the dimension of the feature space $d$, the number of relevant dimensions $s$, and the signal-to-noise ratio defined as the ratio of mean separation to standard deviation $\lambda/\sigma$. We will also demonstrate a specific estimator that achieves the minimax scaling.

For the purposes of this paper, we say that feature $j$ is irrelevant if $\mu_{1}(j)=\mu_{2}(j)$. Otherwise we say that feature $j$ is relevant.

Minimax Bounds

We begin without assuming any sparsity, that is, all features are relevant. In this case, comparing the projections of the data to the projection of the sample mean onto the first principal component suffices to achieve both minimax optimal sample complexity and clustering loss.

where $\widehat{\mu}_{n}=n^{-1}\sum^{n}_{i=1}X_{i}$ is the sample mean, $\widehat{\Sigma}_{n}=n^{-1}\sum^{n}_{i=1}(X_{i}-\widehat{\mu}_{n})(X_{i}-\widehat{\mu}_{n})^{T}$ is the sample covariance and $v_{1}(\widehat{\Sigma}_{n})$ denotes the eigenvector corresponding to the largest eigenvalue of $\widehat{\Sigma}_{n}$. If $n\geq\max(68,4d)$, then

Furthermore, if $\frac{\lambda}{\sigma}\geq 2\max(80,14\sqrt{5d})$, then

Assume that $d\geq 9$ and $\frac{\lambda}{\sigma}\leq 0.2$. Then

We believe that some of the constants (including lower bound on $d$ and exact upper bound on $\lambda/\sigma$) can be tightened, but the results demonstrate matching scaling behavior of clustering error with $d$, $n$ and $\lambda/\sigma$. Thus, we see (ignoring constants and log terms) that

The result is quite intuitive: the dependence on dimension $d$ is as expected. Also we see that the rate depends in a precise way on the signal-to-noise ratio $\lambda/\sigma$. In particular, the results imply that we need $d\leq n$.

In modern high-dimensional datasets, we often have $d>n$ i.e. large number of features and not enough samples. However, inference is usually tractable since not all features are relevant to the learning task at hand. This sparsity of relevant feature set has been successfully exploited in supervised learning problems such as regression and classification. We show next that the same is true for clustering under the Gaussian mixture model.

2 Sparse and small mean separation setting

Now we consider the case where there are $s<d$ relevant features. Let $S$ denote the set of relevant features. We begin by constructing an estimator $\widehat{S}_{n}$ of $S$ as follows. Define

Now we use the same method as before, but using only the features in $\widehat{S}_{n}$ identified as relevant.

where $\widehat{S}_{n}$ is the estimated set of relevant dimensions, $x_{\widehat{S}_{n}}$ are the coordinates of $x$ restricted to the dimensions in $\widehat{S}_{n}$, and $\widehat{\mu}_{\widehat{S}_{n}}$ and $\widehat{\Sigma}_{\widehat{S}_{n}}$ are the sample mean and covariance of the data restricted to the dimensions in $\widehat{S}_{n}$. If $n\geq\max(68,4s)$, $d\geq 2$ and $\alpha\leq\frac{1}{4}$, then

Assume that $\frac{\lambda}{\sigma}\leq 0.2$, $d\geq 17$, and that $5\leq s\leq\frac{d-1}{4}+1$. Then

We remark again that the constants in our bounds can be tightened, but the results suggest that

In this case, we have a gap between the upper and lower bounds for the clustering loss. Also, the sample complexity can possibly be improved to scale as $s$ (instead of $s^{2}$) using a different method. However, notice that the dimension only enters logarithmically. If the number of relevant dimensions is small then we can expect good rates. This provides some justification for feature selection. We conjecture that the lower bound is tight and that the gap could be closed by using a sparse principal component method as in Vu and Lei (2012) to find the relevant features. However, that method is combinatorial and so far there is no known computationally efficient method for implementing it with similar guarantees.

We note that the upper bound is achieved by a two-stage method that first finds the relevant dimensions and then estimates the clusters. This is in contrast to the methods described in the introduction which do clustering and variable selection simultaneously. This raises an interesting question: is it always possible to achieve the minimax rate with a two-stage procedure or are there cases where a simultaneous method outperforms a two-stage procedure? Indeed, it is possible that in the case of general covariance matrices (non-spherical) two-stage methods might fail. We hope to address this question in future work.

Proofs of the Lower Bounds

The lower bounds for estimation problems rely on a standard reduction from expected error to hypothesis testing that assumes the loss function is a semi-distance, which the clustering loss isn’t. However, a local triangle inequality-type bound can be shown (Proposition 2). This weaker condition can then be used to lower-bound the expected loss, as stated in Proposition 1 (which follows easily from Fano’s inequality).

The proof techniques of the sparse and non-sparse lower bounds are almost identical. The main difference is that in the non-sparse case, we use the Varshamov–Gilbert bound (Lemma 1) to construct a set of sufficiently dissimilar hypotheses, whereas in the sparse case we use an analogous result for sparse hypercubes (Lemma 2). See the appendix for complete proofs of all results.

Let $\Omega=\{0,1\}^{m}$ for $m\geq 8$. There exists a subset $\{\omega_{0},...,\omega_{M}\}\subseteq\Omega$ such that $\omega_{0}=(0,...,0)$, $\rho(\omega_{i},\omega_{j})\geq\frac{m}{8}$ for all $0\leq i<j\leq M$, and $M\geq 2^{m/8}$, where $\rho$ denotes the Hamming distance between two vectors (Tsybakov (2009)).

Let $\Omega=\{\omega\in\{0,1\}^{m}:\|\omega\|_{0}=s\}$ for integers $m>s\geq 1$ such that $s\leq m/4$. There exist $\omega_{0},...,\omega_{M}\in\Omega$ such that $\rho(\omega_{i},\omega_{j})>s/2$ for all $0\leq i<j\leq M$, and $\log(M+1)\geq\frac{s}{5}\log\left(\frac{m}{s}\right)$ (Massart (2007), Lemma 4.10).

Let $g(x)=\phi(x)(\phi(x)-x\Phi(-x))$. Then $2g\left(\frac{\|\mu\|}{2\sigma}\right)\sin\beta\cos\beta\leq L_{\theta}(F_{\theta^{\prime}})\leq\frac{\tan\beta}{\pi}.$

where $g(x)=\phi(x)(\phi(x)-x\Phi(-x))$. By Lemma 1, there exist $\omega_{0},...,\omega_{M}\in\Omega$ such that $M\geq 2^{(d-1)/8}$ and $\rho(\omega_{i},\omega_{j})\geq\frac{d-1}{8}$ for all $0\leq i<j\leq M$. For simplicity of notation, let $\theta_{i}=\theta_{\omega_{i}}$ for all $i\in[0..M]$. Then, for $i\neq j\in[0..M]$,

Define $\gamma=\frac{1}{4}(g(\xi)-2\xi^{2})\frac{\sqrt{d-1}\epsilon}{\lambda}.$ Then for any $i\neq j\in[0..M]$, and any $\widehat{F}$ such that $L_{\theta_{i}}(\widehat{F})<\gamma$,

because, for $\xi\leq 0.1$, by definition of $\epsilon$,

Proofs of the Upper Bounds

Propositions 5 and 6 below bound the error in estimating the mean and principal direction, and can be obtained using standard concentration bounds and a variant of the Davis–Kahan theorem. Proposition 7 relates these errors to the clustering loss. For the sparse case, Propositions 8 and 9 bound the added error induced by the support estimation procedure. See appendix for proof details.

Let $r=\left|\frac{(x_{0}-\mu_{0})^{T}v}{\cos\beta}\right|$. Since the clustering loss is invariant to rotation and translation,

Since $\tan\beta\leq\frac{1}{2}$ and $\epsilon_{2}\leq\frac{1}{4}$, we have $r\leq 2\sigma\epsilon_{1}+2\|\mu\|\epsilon_{2}$, and $\Phi\left(\frac{\|\mu\|}{\sigma}\right)-\Phi\left(\frac{\|\mu\|-r}{\sigma}\right)\leq 2\left(\epsilon_{1}+\epsilon_{2}\frac{\|\mu\|}{\sigma}\right)\phi\left(\max\left(0,\frac{\|\mu\|}{2\sigma}-2\epsilon_{1}\right)\right).$ Defining $A=\left|\frac{\|\mu\|-r}{\sigma}\right|$,

where we used $u=x\cos\beta-y\sin\beta$ and $v=x\sin\beta+y\cos\beta$ in the second step. The bound now follows easily. ∎

Proof of Theorem 1. Using Propositions 5 and 6 with $\delta=\frac{1}{\sqrt{n}}$, Proposition 7, and the fact that $(C+x)\exp(-\max(0,x-4)^{2}/8)\leq(C+6)\exp(-\max(0,x-4)^{2}/10)$ for all $C,x>0$,

(it is easy to verify that the bounds are decreasing with $\|\mu\|$, so we use $\|\mu\|=\frac{\lambda}{2}$ to bound the supremum). In the $d=1$ case Proposition 6 need not be applied, since the principal directions agree trivially. The bound for $\frac{\lambda}{\sigma}\geq 2\max(80,14\sqrt{5d})$ can be shown similarly, using $\delta=\exp\left(-\frac{n}{32}\right)$. $\square$

Assume that $n\geq 1$, $d\geq 2$, and $\alpha\leq\frac{1}{4}$. Then $\widetilde{S}(\theta)\subseteq\widehat{S}_{n}\subseteq S(\theta)$ with probability at least $1-\frac{6}{n}$.

By Proposition 8, with probability at least $1-\frac{6}{n}$,

for all $i\in[d]$. Assume the above event holds. If $S(\theta)=[d]$, then of course $\widehat{S}_{n}\subseteq S(\theta)$. Otherwise, for $i\notin S(\theta)$, we have $(1-\alpha)\sigma^{2}\leq\widehat{\Sigma}_{n}(i,i)\leq(1+\alpha)\sigma^{2}$, so it is clear that $\widehat{S}_{n}\subseteq S(\theta)$. The remainder of the proof is trivial if $\widetilde{S}(\theta)=\emptyset$ or $S(\theta)=\emptyset$. Assume otherwise. For any $i\in S(\theta)$,

By definition, $|\mu(i)|\geq 4\sigma\sqrt{\alpha}$ for all $i\in\widetilde{S}(\theta)$, so $\frac{(1+\alpha)^{2}}{1-\alpha}\sigma^{2}\leq\widehat{\Sigma}_{n}(i,i)$ and $i\in\widehat{S}_{n}$ (we ignore strict equality above as a measure event), i.e. $\widetilde{S}(\theta)\subseteq\widehat{S}_{n}$, which concludes the proof. ∎

Assume $\widetilde{S}(\theta)\neq\emptyset$. Let $\cos\widehat{\beta}=|v_{1}(\widehat{\Sigma}_{\widehat{S}_{n}})^{T}v_{1}(\Sigma)|,$ $\cos\widetilde{\beta}=|v_{1}(\Sigma_{\widehat{S}_{n}})^{T}v_{1}(\Sigma)|$, and $\cos\beta=|v_{1}(\widehat{\Sigma}_{\widehat{S}_{n}})^{T}v_{1}(\Sigma_{\widehat{S}_{n}})|$ where $\Sigma=\sigma^{2}I+\mu\mu^{T}$, and for simplicity we define $\widehat{\Sigma}_{\widehat{S}_{n}}$ and $\Sigma_{\widehat{S}_{n}}$ to be the same as $\widehat{\Sigma}_{n}$ and $\Sigma$ in $\widehat{S}_{n}$, respectively, and elsewhere. Then $\sin\widehat{\beta}\leq\sin\widetilde{\beta}+\sin\beta$, and

Using the same argument as the proof of Theorem 1, as long as the above bound is smaller than $\frac{1}{2\sqrt{5}}$,

Using the fact $L_{\theta}(\widehat{F})\leq\frac{1}{2}$ always, and that $\alpha\leq\frac{1}{4}$ implies $\frac{\log(nd)}{n}\leq 1$, the bound follows. $\square$

Conclusion

We have provided minimax lower and upper bounds for estimating high dimensional mixtures. The bounds show explicitly how the statistical difficulty of the problem depends on dimension $d$, sample size $n$, separation $\lambda$ and sparsity level $s$.

For clarity, we have focused on the special case where there are two spherical components and the mixture weights are equal. In future work, we plan to extend the results to general mixtures of $k$ Gaussians.

One of our motivations for this work is the recent interest in variable selection methods to facilitate clustering in high dimensional problems. Existing methods such as Pan and Shen (2007); Witten and Tibshirani (2010); Raftery and Dean (2006); Sun et al. (2012) and Guo et al. (2010) provide promising numerical evidence that variable selection does improve high dimensional clustering. Our results provide some theoretical basis for this idea.

However, there is a gap between the results in this paper and the methodology papers mentioned above. Indeed, as of now, there is no rigorous proof that the methods in those papers outperform a two stage approach where the first stage screens for relevant features and the second stage applies standard clustering methods on the features extracted from the first stage. We conjecture that there are conditions under which simultaneous feature selection and clustering outperforms the two stage approach. Settling this questions will require the aforementioned extension of our results to the general mixture case.

References

Notation

where $f(\cdot;\mu,\Sigma)$ is the density of $\mathcal{N}(\mu,\Sigma)$, $\sigma>0$ is a fixed constant. Let $P_{\theta}$ denote the probability measure corresponding to $p_{\theta}$. We consider two classes $\Theta$ of parameters:

Throughout this document, $\phi$ and $\Phi$ denote the standard normal density and distribution functions.

where the minimum is over all permutations $\pi:\{1,2\}\rightarrow\{1,2\}$.

Also, for a matrix $B$, $v_{i}(B)$ and $\lambda_{i}(B)$ are the $i$’th eigenvector and eigenvalue of $B$ (assuming $B$ is symmetric), arranged so that $\lambda_{i}(B)\geq\lambda_{i+1}(B)$, and $\|B\|_{2}$ is the spectral norm.

Upper bounds

Let $X\sim\chi_{d}^{2}$. Then for any $\epsilon>0$,

To minimize the right hand side, we differentiate the exponent with respect to $t$ to obtain the equation

which can be satisfied by setting $t=\frac{1}{2}\left(1-\frac{1}{1+\epsilon}\right)<\frac{1}{2}$ (it is easy to verify that this is a global minimum). Using this value for $t$, the first bound follows.

and setting $t=\frac{1}{2}\left(\frac{1}{1-\epsilon}-1\right)$,

1.2 Concentration bounds for estimating principal direction

where $\widehat{\Sigma}_{n}$ is the empirical covariance of $Z_{i}$.

Let $\overline{Z}_{n}=\frac{1}{n}\sum_{i=1}^{n}Z_{i}$. Then

It is well known that for any $\epsilon_{1}>0$,

Using this along with Proposition 11, we have for any $\epsilon_{2}>0$,

Setting $\epsilon_{1}=\sqrt{\frac{2\log\frac{1}{\delta}}{d}}$,

and, setting $\epsilon_{2}=\sqrt{\frac{8\log\frac{1}{\delta}}{d}\max\left(1,\frac{8\log\frac{1}{\delta}}{d}\right)}$, with probability at least $1-3\delta$,

The bound is minimized by $t=\frac{1}{2\epsilon}\left(\sqrt{1+4\epsilon^{2}}-1\right)<1$, so

and the proof is complete by noting that the distribution of $X_{i}Y_{i}$ is symmetric. ∎

2 Davis–Kahan

(Corollary 8.1.11 of Golub and Van Loan (1996)).

3 Bounding error in estimating the mean

where the last step is using Hoeffding’s inequality and Proposition 11. Setting $\epsilon_{2}=\sqrt{\frac{2\log\frac{1}{\delta}}{n}}$,

Since $\epsilon_{1}-\log(1+\epsilon_{1})\geq\frac{\epsilon_{1}}{4}\min(1,\epsilon_{1})$,

4 Bounding error in estimating principal direction

where $\widehat{\Sigma}_{n}$ is the empirical covariance of $X_{i}$.

where $\widehat{\Sigma}_{n}^{Z}$ is the empirical covariance of $Z_{i}$ and $\overline{Y}$ and $\overline{Z}$ are the empirical means of $Y_{i}$ and $Z_{i}$. So

Since $|\overline{Y}|\leq 1$ and since $Y_{i}Z_{i}$ has the same distribution as $Z_{i}$, by Proposition 11, for any $\epsilon>0$,

Finally, by Proposition 12, with probability at least $1-3\delta$,

and we complete the proof by combining the three bounds. ∎

where $\overline{Z},\overline{W},\overline{Y}$ are the respective empirical means. Moreover,

and using the Gaussian tail bound, for $\delta\leq\frac{1}{\sqrt{e}}$,

then with probability at least $1-12\delta-2\exp\left(-\frac{n}{20}\right)$,

By Proposition 15 (with $\delta_{1}=\exp\left(-\frac{n}{20}\right)$), Proposition 16 (with $\delta_{2}=\frac{\delta}{d-1}$), and Lemma 3, with probability at least $1-12\delta-2\exp\left(-\frac{n}{20}\right)$,

and the result follows after some simplifications.

5 General result relating error in estimating mean and principal direction to clustering loss

Let $\theta=(\mu_{0}-\mu,\mu_{0}+\mu)$ and let

WLOG assume $v^{T}\mu\geq 0$ (otherwise we can simply replace $v$ with $-v$, which does not affect the bound). Then

Since $\breve{x}$ and $\breve{y}$ are projections of $x-\mu_{0}$ onto orthogonal unit vectors, and since $\breve{x}$ is exactly the component of $x-\mu_{0}$ that lies in the direction of $\mu$, we can integrate out all other directions and obtain

where $\phi_{\sigma}$ is the density of $\mathcal{N}(0,\sigma^{2})$. But,

Since the above quantity is increasing in $|B(\breve{y})|$, and since $|B(\breve{y})|\leq|\breve{y}|\tan\beta+r$ where

we have that, replacing $\breve{y}$ by $x$,

Since $\tan\beta\leq\frac{1}{2}$, we have that $r\leq 2|(x_{0}-\mu_{0})^{T}v|\leq 2\sigma\epsilon_{1}+2\|\mu\|\epsilon_{2}$ and

Defining $A=\left|\frac{\|\mu\|-r}{\sigma}\right|$,

6 Non-sparse upper bound

Furthermore, if $\frac{\lambda}{\sigma}\geq 2\max(80,14\sqrt{5d})$, then

Using Propositions 14 and 17 with $\delta=\frac{1}{\sqrt{n}}$, Proposition 18, and the fact that $(C+x)\exp(-\max(0,x-4)^{2}/8)\leq(C+6)\exp(-\max(0,x-4)^{2}/10)$ for all $C,x>0$,

(it is easy to verify that the bounds are decreasing with $\|\mu\|$, so we use $\|\mu\|=\frac{\lambda}{2}$ to bound the supremum). Note that the $d=1$ case must be handled separately, but results in a bound that agrees with the above.

Also, when $\frac{\lambda}{\sigma}\geq 2\max(80,14\sqrt{5d})$, using $\delta=\exp\left(-\frac{n}{32}\right)$,

7 Estimating the support in the sparse case

where $\overline{Z}$ and $\overline{Y}$ are the respective empirical means, and

So, by Hoeffding’s inequality, a Gaussian tail bound, and Proposition 10, we have that for any $0<\delta<\frac{1}{\sqrt{e}}$, with probability at least $1-6\delta$,

where we have used the fact that for $\epsilon\in(0,0.5]$,

Assume that $n\geq 1$, $d\geq 2$, and $\alpha\leq\frac{1}{4}$. Then $\widetilde{S}(\theta)\subseteq\widehat{S}_{n}\subseteq S(\theta)$ with probability at least $1-\frac{6}{n}$.

By Proposition 19, with probability at least $1-\frac{6}{n}$,

for all $i\in[d]$. Assume the above event holds. If $S(\theta)=[d]$, then of course $\widehat{S}_{n}\subseteq S(\theta)$. Otherwise, for $i\notin S(\theta)$,

so it is clear that $\widehat{S}_{n}\subseteq S(\theta)$.

The remainder of the proof is trivial if $\widetilde{S}(\theta)=\emptyset$ or $S(\theta)=\emptyset$. Assume otherwise. For any $i\in S(\theta)$,

By definition, $|\mu(i)|\geq 4\sigma\sqrt{\alpha}$ for all $i\in\widetilde{S}(\theta)$, so

and $i\in\widehat{S}_{n}$ (we ignore strict equality above as a measure event), i.e. $\widetilde{S}(\theta)\subseteq\widehat{S}_{n}$, which concludes the proof. ∎

8 Sparse upper bound

Assume that $d\geq 2$, and $\alpha\leq\frac{1}{4}$. Let

where $\widehat{\mu}_{\widehat{S}_{n}}$ and $\widehat{\Sigma}_{\widehat{S}_{n}}$ are the empirical mean and covariance of $X_{i}$ for the dimensions in $\widehat{S}_{n}$, and elsewhere. Then

Assume $\widetilde{S}(\theta)\neq\emptyset$. Let

where $\Sigma=\sigma^{2}I+\mu\mu^{T}$, and $\Sigma_{\widehat{S}_{n}}$ is the same as $\Sigma$ in $\widehat{S}_{n}$, and elsewhere. Then

Using the same argument as the proof of Theorem 5, we have that as long as the above bound is smaller than $\frac{1}{2\sqrt{5}}$,

However, when $8\frac{\sigma\sqrt{s\alpha}}{\lambda}>\frac{1}{2\sqrt{5}}$, the above bound is bigger than $\frac{1}{2}$, which is a trivial upper bound on the clustering error, hence the bound can be stated without further conditions. Finally, since $\alpha\leq\frac{1}{4}$, we must have $\frac{\log(nd)}{n}\leq 1$, so $\alpha\leq(\sqrt{6}+2)\sqrt{\frac{\log(nd)}{n}}$, which completes the proof.

Lower bounds

Let $P_{0},P_{1},...,P_{M}$ be probability measures satisfying

(Varshamov–Gilbert bound) Let $\Omega=\{0,1\}^{m}$ for $m\geq 8$. Then there exists a subset $\{\omega_{0},...,\omega_{M}\}\subseteq\Omega$ such that $\omega_{0}=(0,...,0)$,

where $\rho$ denotes the Hamming distance between two vectors (Tsybakov (2009)).

Let $\Omega=\{\omega\in\{0,1\}^{m}:\|\omega\|_{0}=s\}$ for integers $m>s\geq 1$. For any $\alpha,\beta\in(0,1)$ such that $s\leq\alpha\beta m$, there exists $\omega_{0},...,\omega_{M}\in\Omega$ such that for all $0\leq i<j\leq M$,

In particular, setting $\alpha=3/4$ and $\beta=1/3$, we have that $\rho(\omega_{i},\omega_{j})>s/2$, $\log(M+1)\geq\frac{s}{5}\log\left(\frac{m}{s}\right)$, as long as $s\leq m/4$ (Massart (2007), Lemma 4.10).

2 A reduction to hypothesis testing without a general triangle inequality

Let $\theta_{0},...,\theta_{M}\in\Theta_{\lambda}$ (or $\Theta_{\lambda,s}$), $M\geq 2$, $0<\alpha<1/8$, and $\gamma>0$. If

and for all $0\leq i\neq j\leq M$ and clusterings $\widehat{F}$,

3 Properties of the clustering error

For any $\theta,\theta^{\prime}\in\Theta_{\lambda}$, and any clustering $\widehat{F}$, if

WLOG assume $F_{\theta}$, $F_{\theta^{\prime}}$, and $\widehat{F}$ are such that, using simplified notation,

where $\cos\beta=\frac{|\mu^{T}\mu^{\prime}|}{\|\mu\|^{2}}$ and $g(x)=\phi(x)(\phi(x)-x\Phi(-x))$.

Define $\xi=\frac{\|\mu\|}{2\sigma}$. With a change of variables, we have

For any $a\leq b$, $\Phi(b)-\Phi(a)\leq\frac{b-a}{\sqrt{2\pi}}$, so

4 A KL divergence bound of the necessary order

where $\xi=\frac{\|\mu\|}{2\sigma}$ and $\cos\beta=\frac{|\mu^{T}\mu^{\prime}|}{\|\mu\|\|\mu^{\prime}\|}$.

Since the KL divergence is invariant to affine transformations, it is easy to see that

since $\xi_{x}^{2}+\xi_{y}^{2}=\xi^{2}$. By the mean value theorem and the fact that $\tanh$ is monotonically increasing,

for all $z$. Since $\tanh$ is an odd function,

5 Non-sparse lower bound

Assume that $d\geq 9$ and $\frac{\lambda}{\sigma}\leq 0.2$. Then

Let $\xi=\frac{\lambda}{2\sigma}$, and define

By Proposition 23, since $\cos\beta_{\omega,\nu}\geq\frac{1}{2}$,

where $g(x)=\phi(x)(\phi(x)-x\Phi(-x))$. By Lemma 5, there exist $\omega_{0},...,\omega_{M}\in\Omega$ such that $M\geq 2^{(d-1)/8}$ and

For simplicity of notation, let $\theta_{i}=\theta_{\omega_{i}}$ for all $i\in[0..M]$. Then, for $i\neq j\in[0..M]$,

Then for any $i\neq j\in[0..M]$, and any $\widehat{F}$ such that $L_{\theta_{i}}(\widehat{F})<\gamma$,

because, for $\xi\leq 0.1$, by definition of $\epsilon$,

So by Proposition 21 and the fact that $\xi\leq 0.1$,

and to complete the proof we use the fact that

6 Sparse lower bound

Assume that $\frac{\lambda}{\sigma}\leq 0.2$, $d\geq 17$, and

For simplicity, we state this proof for $\Theta_{\lambda,s+1}$, assuming $4\leq s\leq\frac{d-1}{4}$. Let $\xi=\frac{\lambda}{2\sigma}$, and define

By Proposition 23, since $\cos\beta_{\omega,\nu}\geq\frac{1}{2}$,

where $g(x)=\phi(x)(\phi(x)-x\Phi(-x))$. By Lemma 6, there exist $\omega_{0},...,\omega_{M}\in\Omega$ such that $\log(M+1)\geq\frac{s}{5}\log\left(\frac{d-1}{s}\right)$ and

For simplicity of notation, let $\theta_{i}=\theta_{\omega_{i}}$ for all $i\in[0..M]$. Then, for $i\neq j\in[0..M]$,

Then for any $i\neq j\in[0..M]$, and any $\widehat{F}$ such that $L_{\theta_{i}}(\widehat{F})<\gamma$,

because, for $\xi\leq 0.1$, by definition of $\epsilon$,

So by Proposition 21 and the fact that $\xi\leq 0.1$,

and to complete the proof we use the fact that