Polynomial Learning of Distribution Families

Introduction

Estimating parameters of a model from sampled data is one of the oldest and most general problems of statistical inference. Given a number of samples, one needs to choose a distribution that best fits the observed data. While traditionally theoretical analysis in the statistical literature has concentrated on rates (e.g., minimax rates), in recent years other computational aspects of this problem, especially as dependence on dimension of the space, have attracted attention. In particular, a recent line of work in the theoretical computer science and learning communities has been concerned with learning the distribution in time and using the number of samples, polynomial in parameters and the dimension of the space. This effort has been particularly directed at the family of Gaussian Mixture models due to their simple formulation and widespread use in applications spanning areas such as computer vision, speech recognition, and many others (see, e.g.,). This line of research started with the work of Dasgupta , who was the first to show that learning the parameters of a Gaussian mixture distribution in time polynomial in the dimension of the space $n$ was possible at all. This work has been refined and extended in a number of consequent papers. The results in required separation between mixture components on the order of $\sqrt{n}$. That was later improved to of $\Omega(n^{\frac{1}{4}})$ in for mixtures of spherical Gaussians and in for general Gaussians. The separation requirement was further reduced and made independent of $n$ to the order of $\Omega(k^{\frac{1}{4}})$ in for a mixture of $k$ spherical Gaussians and to the order of $\Omega(\frac{k^{\frac{3}{2}}}{\epsilon^{2}})$ in for logconcave distributions. In the separation requirement was further reduced to $\Omega(k+\sqrt{k\log n})$. An extension of PCA called isotropic PCA was introduced in to learn mixtures of Gaussians when any pair of Gaussian components is separated by a hyperplane having very small overlap along the hyperplane direction (so-called ”pancake layering problem”). A number of recent papers addressed related problems, such as learning mixture of product distributions and heavy tailed distributions.

However all of these papers assumed a minimum separation between the components, which is an increasing function of the dimension $n$ and/or the number of components $k$. The general question of learning parameters of a distribution without any separation conditions, remained open. The first result in that direction was obtained in Feldman, et al., , which showed that the density (but not the parameters) of mixtures of axis aligned Gaussians can be learned in polynomial time using the method of moments.

Very recently two papers independently addressed two special cases of Gaussian mixture learning without separation assumption. In Kalai, et al., the authors showed that a mixture of two Gaussians with arbitrary covariance matrices can be learned in polynomial time. The technique relies on a randomized algorithm to reduce the problem to one dimension. The key argument of the paper is based on deconvolving the one-dimensional mixture to increase the separation between the components and carefully analyzing the moments of the deconvolved mixture in order to apply the method of moments. In it is shown that a mixture of $k$ identical spherical Gaussians can be learned in time polynomial in dimension. The key result is based on analyzing the Fourier transform of the distribution in one dimension to give a lower bound on the norm. However, it is not clear whether the techniques of either or could be applied to the general case with an arbitrary number of components and covariance matrices.

In this paper we resolve the polynomial learnability problem by proving that there exists a polynomial algorithm to estimate parameters of a general high-dimensional mixture with arbitrary fixed number of Gaussians components without any additional assumptions. Table 1 briefly summarizes the progress in the area and our result.

Our main result for Gaussian mixtures relies on a quite general result of independent interest on learning what we call polynomial families. These families are characterized by their moments being polynomial in the parameters of a distribution. It turns out that almost all common distribution families, e.g., Gaussian, exponential, uniform, Laplace, binomial, Poisson and a number of others. (see Table 2 in Appendix A for a longer list and a description of their moments), as well as their mixtures and (tensor) products have this property. Our technique uses methods of real algebraic geometry and combines them with the classical method of moments (originally introduced by Pearson in to analyze Gaussian mixtures).

We note that there have been applications of algebraic geometry in the field of statistics, particularly in conditional independence testing and likelihood estimation for discrete distributions and exponential families (see, e.g., ). We note that a mixture of more than one Gaussian distributions is a family of continuous distributions, which is not an exponential family.

Below we give a brief summary of the main results and the structure of the paper.

Brief outline of the paper. Section 2. We start Section 2 by introducing the problem of parameter learning and defining the notion of a polynomial family. We proceed to prove the main result showing that parameters of a distribution from a polynomial family can be learned with confidence $1-\delta$ up to precision $\epsilon$ using the number of samples $poly(\frac{1}{\delta},\max(\frac{1}{\epsilon},\frac{1}{{\mathscr{R}}}))$, where ${\mathscr{R}}$ is the radius of identifiability, a measure of intrinsic hardness of unique parameter identification for a distributionFor example, it is impossible to identify mixing coefficients of a mixture of two Gaussians with identical means and variances, thus in that case ${\mathscr{R}}=0$. See Section 3 for the detailed analysis of Gaussian mixtures.. In fact, the result is more general, even if the radius of identifiability is zero, parameters can still be learned up to a certain equivalence relation defined in the paper.

The proof consists of the two main steps. The first step uses the Hilbert basis theorem for an appropriately defined ideal in the ring of polynomials to show that a fixed set of (possibly high-dimensional) moments uniquely identifies the distribution.

In the second step, we pose parameter estimation problem as a system of quantified algebraic equations and inequalities using the finite set of moments obtained in the first step. We use quantifier elimination for semi-algebraic sets (Tarski-Seidenberg theorem) to prove that there exists a polynomial algorithm for parameter learning.

Section 3. In Section 3 we prove our main results on learning Gaussian mixture distributions in high dimensions. The main difficulty is that the general results of Section 2 cannot be applied directly since the number of parameters increases with the dimension of the space. To overcome this issue, we prove that the Gaussian family has the property that we call polynomial reducibility. That is the parameters of a distribution in $n$ dimensions can be recovered from a $poly(n)$ number of low-dimensional projections. Specifically, we show that a mixture of Gaussians with $k$ components can be recovered using a polynomial number of projections to $(2k^{2}+2)$-dimensional space. This leads us to Theorem 3.1, our main result for parameter learning on Gaussian mixtures. We show that parameters of a Gaussian mixture can be learned with precision $\epsilon$ and confidence $1-\delta$, using the number of samples polynomial in dimension $n$, $\frac{1}{\delta}$ and $\max(\frac{1}{\epsilon},\frac{1}{{\mathscr{R}}})$. Moreover, we also provide explicit formula for the radius of identifiability of Gaussian mixtures. If we are given an a priori bounds on the minimum mixing weight and the minimum separation between the mean/covariance pairs, that leads to an upper bound on $\frac{1}{{\mathscr{R}}}$. For example, our results holds even in the extreme case where all components have the same mean, as long as the covariance matrices are different. In Theorem 3.2 we also show that in the absence of such a lower bound, ${\mathscr{R}}$ can be estimated directly from the data.

We discuss other polynomially reducible families, where a similar approach would yield results on polynomial learnability.

In Section 4 we conclude and discuss some limitations of our results, directions of future work and conjectures.

Learning Polynomial Families

In this section we prove some general learnability results for a large class of probability distributions that we call polynomial families, which are characterized by the moments being polynomial functions of parameters. This class turns out to contain nearly all commonly used probability distributions, as well as their mixtures and (tensor) products. See Appendix A (Table 2) for a partial list together with the description of their moments either explicitly or through a recurrence relation, as well as some examples of families, which are not polynomial (Table 3).

The main result in this section is Theorem 2.8, which shows that there exists an algorithm to learn the parameters of a polynomial distribution using a polynomial number of samples.

However, for many families identifying the values of parameters uniquely is impossible, due to the fact that several different values of parameters may correspond to the same probability distribution. Moreover, if two values of parameters, say, ${\theta}$ and $\omega$ are close to two values of parameters, $\theta^{\prime}$ and $\omega^{\prime}$ respectively, which have identical probability distributions, then it may be hard to distinguish between them. This situation is illustrated in Fig. 1. These observations suggests that a more general formulation of learning distribution parameters needs to take these into account. A mathematical formalization of the more general of learnability will be given in Eq.1, which defines a notion of a neighborhood taking parameters with identical probability distribution into account. An $\epsilon$-”neighborhood” of ${\theta}$, ${\cal N}({\theta},\epsilon)$, is shown in gray in Fig. 1. We will also introduce the notion of the radius of identifiability ${\mathscr{R}}(\theta)$ (definition 2.9) to give a quantification of how hard it may be to identify the parameters. For example, parameters $\theta$ for which ${\mathscr{R}}(\theta)=0$ cannot be identified given any amount of data. In Fig. 1, the radius of identifiability ${\mathscr{R}}({\theta})$ is equal to $\epsilon^{\prime}$.

For mixtures of Gaussians any permutation of the mixture components has the same distribution, while a component with zero mixing weight may have arbitrary mean/covariance. If two components have the same mean/covariance pair, then the mixing coefficients are not defined uniquely. However, assuming that the mean/variance pairs for any two components are different and that the mixing coefficients are non-zero, the parameters are defined uniquely up to a permutation of components (see Section 2).

Our main Theorem 2.8 applies even when parameters of a probability distributions are not defined uniquly, including the standard definition of parameter learning as a special case (see Corollary 2.10 and Corollary 2.11).

In Subsection 2.1 we prove the basic properties of polynomial families, including the key result, Theorem 2.3, which shows that a finite set of moments uniquely determines the distribution.

In Subsection 2.2 we define the extended notion of a neighborhood ${\cal N}({\theta},\epsilon)$ and discuss its basic properties. We proceed to obtain the main technical result, a lower bound in Theorem 2.5. This, together with the upper bound in Proposition 2.7 allows us to set up a grid search to prove the main Theorem 2.8. We also define the radius of identifiability, and derive Corollary 2.10 and Corollary 2.11.

The family of semi-algebraic sets is closed under finite union, intersection and taking complements. Importantly, the Tarski-Seidenberg theorem states that a linear projection of a semi-algebraic set is also semi-algebraic. This is equivalent to the elimination of quantifiers for semi-algebrac sets, which we will need shortly. See for a review of results on real algebraic geometry.

We call the family $p_{\theta}$ a polynomial family, if each (raw $l$-dimensional) moment $M_{i_{1},\ldots,i_{l}}(\theta)=\int x_{1}^{i_{1}}\ldots x_{l}^{i_{l}}\,dp_{\theta}$ of the distribution exists and can be represented as a polynomial of the parameters $(\theta^{1},\ldots,\theta^{m})$. We also require that each $p_{\theta}$ should be defined uniquely by its momentsThis is true under some mild conditions, e.g., if the moment generating function converges in a neighborhood of zero ..

We will order the moments $M_{i_{1},\ldots,i_{l}}$ lexicographically and denote them by $M_{1}({\theta}),\ldots,M_{n}({\theta}),\ldots$ In the one-dimensional case this corresponds to the standard ordering of the moments.

As it turns out, most of the common families of probability distributions are, in fact, polynomial (see Appendix A). Moreover, a mixture, a product or a linear transformation of polynomial families is also a polynomial family, as stated in the following

The proof follows directly from the linearity of the integral, the Fubini’s theorem and the fact that polynomial functions stay polynomial under a linear change.

Let us now recall that a family $p_{\theta}$, is called identifiable if $p_{{{\theta_{1}}}}\neq p_{{{\theta_{2}}}}$ for any ${{\theta_{1}}}\neq{{\theta_{2}}}$. We will now prove the following

Let $p_{\theta}$ be a polynomial family of distributions. Then there exists a positive integer $N$, such that $p_{{\theta_{2}}}=p_{{\theta_{1}}}$ if and only if $M_{i}({{\theta_{1}}})=M_{i}({{\theta_{2}}})$ for all $i=1,\ldots,N$. In the case when the family $p_{\theta}$ is identifiable, the first $N$ moments are sufficient to uniquely identify the parameter $\theta$.

Proof: Since Let $p_{\theta}$ is a polynomial family, each $M_{i}({\theta})$ is a polynomial of ${\theta}$. Let ${{\theta_{1}}}=({\theta}_{1}^{1},\ldots,{\theta}_{1}^{m})$ and ${{\theta_{2}}}=({\theta}_{2}^{1},\ldots,{\theta}_{2}^{m})$. Let

be a polynomial of $2m$ variables. Now let ${\cal I}_{j}$ be the ideal in the ring of polynomials of $2m$ variables generated by the polynomials $P_{1},\ldots,P_{j}$. Thus we have an increasing sequence of ideals ${\cal I}_{1}\subset{\cal I}_{2}\subset{\cal I}_{3}\ldots$ Let ${\cal I}=\cup_{j=1}^{\infty}~{}{\cal I}_{j}$. By the Hilbert basis theorem, the ideal $\cal I$ is finitely generated, which implies that for some $N$ large enough, ${\cal I}_{N}$ contains all of the generators. Therefore for any $M\geq N$ we can write

for some polynomials $a_{i}$. Thus if $P_{i}({{\theta_{1}}},{{\theta_{2}}})=0$ for $i=1,\ldots,N$ then $P_{i}({{\theta_{1}}},{{\theta_{2}}})=0$ for any $i$. Recalling the definition of $P_{M}$, we conclude that all moments of $p_{{\theta_{1}}}$ and $p_{{\theta_{2}}}$ coincide if and only if the first $N$ moments of these distributions are the same. Since the sequence of moments defines the distribution uniquely, the statement of the theorem follows. $\Box$

2 Learning Polynomial Families

We will now introduce a notion of an $\epsilon$-”neighbourhood” of a point, which takes into account that different parameters may have identical probability distribution. We proceed to prove the main Theorem 2.8 and a few corollaries, showing that the standard parameter learning problem becomes a special case of the result.

Let ${\cal E}(\theta)=\{\omega|p_{\omega}=p_{\theta}\}$ be the set of parameters $\omega$ which have distributions same as $p_{\theta}$. We note that the distributions corresponding to different values of parameters in the set ${\cal E}(\theta)$ are identical and hence cannot be distinguished from each other given any amount of sampled data. We now define

In other words, $\omega$ belongs to ${\cal N}(\theta,\epsilon)$ if it is within $\epsilon^{\prime}<\epsilon$ distance of a parameter value which has the same probability distribution as a parameter value within $\epsilon-\epsilon^{\prime}$ of $\theta$. This definition is illustrated graphically in Fig. 1. We observe the following properties of ${\cal N}(\theta,\epsilon)$:

(Symmetry) If ${{\theta_{1}}}\in{\cal N}({{\theta_{2}}},\epsilon)$ then ${{\theta_{2}}}\in{\cal N}({{\theta_{1}}},\epsilon)$.

($\epsilon$-ball) An $\epsilon$-ball $B(\theta,\epsilon)$ around $\theta$ is contained in ${\cal N}(\theta,\epsilon)$. If $B(\theta,\epsilon)$ is an identifiable family, then $B(\theta,\epsilon)={\cal N}(\theta,\epsilon)$.

(Equivalence) If $p_{{\theta_{1}}}=p_{{\theta_{2}}}$, then ${{\theta_{1}}}\in{\cal N}({{\theta_{2}}},\epsilon)$ for any $\epsilon>0$.

Thus ${\cal N}(\theta,\epsilon)$ can be viewed as an “$\epsilon$-ball” around $\theta$ taking probability distribution into account. For example, values of parameters with identical probability distributions cannot be distinguished by this metric, which is consistent with statistical identifiability.

${\cal N}(\theta,\epsilon)$ is an open semi-algebraic set.

Proof:${\cal N}(\theta,\epsilon)$ is open since, a sufficiently small open ball around any point $\omega\in{\cal N}(\theta,\epsilon)$ is also contained in ${\cal N}(\theta,\epsilon)$. To see that it is algebraic we recall that by Theorem 2.3 there exists an $N$, such that ${{\theta_{1}}}\in{\cal E}({{\theta_{2}}})$ if and only if

which is an algebraic condition. Hence, by applying the Tarski-Seidenberg theorem to eliminate the existential quantifiers in Eq. 1, we see that ${\cal N}(\theta,\epsilon)$ is semi-algebraic. $\Box$

Proof: Choose $N$ as in Theorem 2.3. We start by observing we can replace the condition

$|M_{i}({{\theta_{1}}})-M_{i}({{\theta_{2}}})|>\epsilon$ by

in the statement of the theorem. Since the existence of $t$ is not affected by the substitution of $N{\epsilon^{2}}$, instead of $\epsilon$, to simplify the matters we will assume that $Q({{\theta_{1}}},{{\theta_{2}}})>\epsilon$.

From Theorem 2.3 we recall that if for some $i\leq N$ $|Q({{\theta_{1}}},{{\theta_{2}}})|\neq 0$ then $p_{{\theta_{1}}}\neq p_{{\theta_{2}}}$. Let $\delta$ be a positive real number. Consider the set $X=\{{{\theta_{1}}},{{\theta_{2}}}|{{\theta_{1}}}\in{\cal N}({{\theta_{2}}},\delta)\}$. From Lemma 2.4 and the fact that the relationship ${{\theta_{1}}}\in{\cal N}({{\theta_{2}}},\delta)$ is symmetric, it follows that $X$ is an open subset of $\Theta\times\Theta$. Hence the set $\Theta\times\Theta-X=\{{{\theta_{1}}},{{\theta_{2}}}\in\Theta,{{\theta_{1}}}\notin{\cal N}({{\theta_{2}}},\delta))\}$ is compact and since $Q({{\theta_{1}}},{{\theta_{2}}})>0$ for any $({{\theta_{1}}},{{\theta_{2}}})\in\Theta\times\Theta-X$ we have

By an argument following that in Lemma 2.4 we see that $X$ and hence its complement are semi-algebraic sets.

Consider now the set $S_{\delta}$, $\delta>0$ given by the following expression

We write this polynomial as $q(x)=q_{M}(\delta)x^{M}+\ldots+q_{0}(\delta)$, such that $q(\epsilon(\delta))=0$. We can assume that $q_{0}(\delta)$ is not identically zero (dividing by an appropriate power of $x$ if necessary). From Lemma 2.6 we see that if $q(\epsilon(\delta))=0$ then

The last quantity is a ratio of two polynomials in $\delta$ and can thus be lower bounded by $C(\delta^{t^{\prime}})$, so that $\epsilon(\delta)>C\delta^{t^{\prime}}$ for some $t^{\prime}>0$, when $\delta$ is sufficiently small.

Putting $t=\frac{1}{t^{\prime}}$ and recalling the definition of $S_{\delta}$, we see that $Q(\theta_{1},\theta_{2})<\epsilon$, implies ${{\theta_{1}}}\in{\cal N}({{\theta_{2}}},O(\epsilon^{t}))$, which completes the proof of the theorem. $\Box$

Let $\delta$ be a positive root of the polynomial $q(x)=a_{M}x^{M}+\ldots+a_{0}$, $a_{0}\neq 0$. Then $\delta>\min(\frac{\sum_{i=1}^{M}|a_{i}|}{|a_{0}|},1)$.

Proof:We have $\delta(\sum_{i=1}^{M}a_{i}\delta^{i-1})=-a_{0}$. For $0<\delta<1$ we have $\sum_{i=1}^{M}a_{i}\delta^{i-1}<\sum_{i=1}^{M}|a_{i}|$, and the statement follows. $\Box$

If $\Theta$ is contained in a ball of diameter $B$, then $C$ is bounded from above by a polynomial of $B$.

Proof:To prove the claim it is sufficient to show that each summand $|M_{i}({{\theta_{1}}})-M_{i}({{\theta_{2}}})|^{2}$ is bounded from above by $C^{\prime}\|{{\theta_{1}}}-{{\theta_{2}}}\|^{2}$, which is equivalent to proving that $\frac{|M_{i}({{\theta_{1}}})-M_{i}({{\theta_{2}}})|}{\|{{\theta_{1}}}-{{\theta_{2}}}\|}<\sqrt{C^{\prime}}$. We now observe that by the mean value theorem

where ${\mathop{\rm grad}}$ is the gradient of the function $M_{i}$. Since $M_{i}$ is a polynomial, all elements of the vector ${\mathop{\rm grad}}(M_{i})$ are polynomial in $\theta$. Therefore

where $t$ is the maximum degree of these polynomials and $C^{\prime\prime}$ is an appropriate constant. This implies the statement of the Proposition. $\Box$

There exists an algorithm, which, given $\epsilon>0$ and $1>\delta>0$, and $P(\frac{1}{\epsilon},\frac{1}{\delta},B)$ samples from $p_{\theta},\theta\in\Theta$, where $\Theta$ is the set of parameters within a ball of radius $B$ and $P$ is a polynomial depending only on the distribution family, outputs $\hat{\theta}$, s.t. $\hat{\theta}\in{\cal N}(\theta,\epsilon)$ with probability at least $1-\delta$. The algorithm also requires a polynomial number of operations.

To simplify further discussion we will now define the radius of identifiability:

As before let $p_{\theta}$, $\theta\in\Theta$ be a family of probability distributions. For each $\theta$ we define the radius of identifiability as follows

In other words, ${\mathscr{R}}(\theta)$ is the largest number, such that the open ball of radius ${\mathscr{R}}(\theta)$ around $\theta$ intersected with $\Theta$ is an identifiable (sub)family of probability distributions. If no such ball exists, ${\mathscr{R}}(\theta)=0$.

From Theorem 2.8 and the definition of the radius of identifiability we have the following

There exists an algorithm, such that, given $\epsilon>0$, for any identifiable $\theta\in\Theta$, where $\Theta$ is the set of parameters within a ball of radius $B$, it outputs ${{\hat{\theta}}}$ within $\min(\epsilon,{\mathscr{R}}(\theta))$ of ${\theta}$ with probability $1-\delta$, using a number of sample points from $p_{\theta}$ polynomial in $\max\left(\frac{1}{\epsilon},\frac{1}{{\mathscr{R}}(\theta)}\right)$, $\frac{1}{\delta}$ and $B$.

More generally, if $\theta\in\Theta$, where $\Theta$ is the set of parameters within a ball of radius $B$, is not identifiable but, ${\cal E}(\theta)=\{{\theta}_{1},\ldots,{\theta}_{k}\}$ is a finite set, there exists an algorithm, such that, given $\epsilon>0$, it outputs ${{\hat{\theta}}}$ within $\min(\epsilon,\min_{j}{\mathscr{R}}(\theta_{j}))$ of ${\theta}_{i}$ for some $i\in\{1,\ldots,k\}$ with probability $1-\delta$, using a number of sample points from $p_{\theta}$ polynomial in $\max\left(\frac{1}{\epsilon},\frac{1}{\min_{j}{\mathscr{R}}(\theta_{j})}\right)$ and $\frac{1}{\delta}$.

This last result is what we need to analyze Gaussian mixture model in the next Section.

Remark: It is important to note that the radius of identifiability depends on the choice of family $\Theta$. Specifically, the radius is a decreasing function on the family of the sets $\Theta$ ordered by inclusion.

Gaussian Distributions and Polynomially Reducible High Dimensional Families

The main result of this section is to show that there exists an algorithm for estimating parameters of high-dimensional Gaussian mixture distributions in time polynomial in the dimension $n$ and other parameters. We note that the techniques from the previous section cannot be applied directly to high-dimensional distributions since the number of parameters generally increases with dimension. Instead our approach will be to show that parameters of high-dimensional Gaussians can be estimated using $\operatorname*{poly}(n)$ linear projections to linear subspaces, whose dimension is independent of $n$. We will call this property polynomial reducibility and will also briefly discuss some other families satisfying this condition later in the section.

We will assume that the number of components $k$ is fixed. We note that any permutation of the mixture components leads to the same density function and hence cannot be identified from data. On the other hand, it is well known () that the density of the distribution determines the parameters uniquely up to a permutation, if and only if any two components with the same means have different covariance matrices and no mixing coefficient is equal to zero.

The main result of the section is given by the following

We note that the radius of identifiability ${\mathscr{R}}(\theta)$ can be calculated explicitly from the Proposition 3.3:

Thus if the mean/variance pairs for any two components are different with difference bounded from below and the minimum mixing weight is is also bounded from below, then we have explicit lower bound for ${\mathscr{R}}(\theta)$.

In fact even when ${\mathscr{R}}(\theta)$ is not known in advance, it can be estimated from data as:

The rest of the section is structured as follows:

In subsection 3.1 we discuss various properties of Gaussian mixture distributions. In particular we derive the formula for the radius of identifiability (Proposition 3.3) and show that there exists a low-dimensional projection such that the radius of identifiability changes by at most a linear factor (Theorem 3.7).

In subsection 3.2 we give a sketch for the proof of the main theorem, showing how the parameters of a high-dimensional distribution can be estimated from a polynomial number of projections. The details of the proof as well as the proof of Theorem 3.2 are given in the appendix C.

Finally, we note that our results apply to high-dimensional distributions which are not mixtures of Gaussians with a fixed number of components. For example, a product of $n$ $1$-dimensional Gaussian mixture distributions, which is a Gaussian mixture distribution in $n$ dimensions with $k^{n}$ components, can be easily learned using our methods. The same applies to other product distributions whose components are polynomial families.

Moreover, suppose $\Theta$ is a convex setNote that requiring convexity is natural, since the set of positive definite matrices is a convex cone. such that it contains all possible mixing coefficients $(w_{1},\ldots,w_{k})$ for any fixed set of means and variancesThis requirement is unnecessarily strong, however the precise condition, evident from the proof, is awkward to state.

In this case the inequality becomes an equality:

In particular, the radius of identifiability is invariant under the permutation of components.

Proof:We will start by proving the inequality 5. Suppose that the distributions $p_{\theta^{\prime}}$ and $p_{\theta^{\prime\prime}}$ have the same density. To prove the inequality, we need to show that at least one of ${\theta}^{\prime}$, ${\theta}^{\prime\prime}$ is no closer to ${\theta}$ then the right hand side of the inequality 5.

Let us first consider the case when there is no pair $i\neq j$, s.t. $\mu^{\prime}_{i}=\mu^{{}^{\prime\prime}}_{j}$ and $\Sigma_{i}^{\prime}=\Sigma^{{}^{\prime\prime}}_{j}$. In that case that case at least one of the mixing coefficients for one of the mixtures must be equal to zero. That implies that either $\|{\theta}-{\theta}^{\prime}\|\geq\min_{i}w_{i}$ or $\|{\theta}-{\theta}^{\prime\prime}\|\geq\min_{i}w_{i}$, which is consistent with the 5.

Alternatively, suppose that for some $i\neq j$ we have $(\mu_{i}^{\prime},\Sigma_{i}^{\prime})=(\mu_{j}^{\prime\prime},\Sigma_{j}^{\prime\prime})$. Put $v^{\prime}=(\mu_{i}^{\prime},\Sigma_{i}^{\prime})=(\mu_{j}^{\prime\prime},\Sigma_{j}^{\prime\prime})$, $v_{1}=(\mu_{i},\Sigma_{i})$, $v_{2}=(\mu_{j},\Sigma_{j})$. We see that

Therefore, $\max\{\|\theta^{\prime}-\theta\|^{2},\|\theta^{\prime\prime}-\theta\|^{2}\}\geq\frac{1}{4}(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2})$ which is again consistent with Inequality 5 and together with the first case implies the inequality.

To show Eq. 6 we need to observe that the bound is tight. Again we consider two possible cases. If the minimum in the right hand side of Eq. 6 is equal to the square of one of the mixing weights, say, $w_{i}$, construct ${\theta}^{\prime}$ by putting $w_{i}^{\prime}=0$ and keeping the rest of the parameters of $\theta$. We see that $\|{\theta}^{\prime}-{\theta}\|=w_{i}$. By slightly perturbing $\mu^{\prime}$, we see that there exists a ${\theta}^{\prime\prime}$ arbitrarily close (but not equal)to ${\theta}^{\prime}$ with the same probability density. Thus the radius of identifiability cannot exceed $w_{i}$.

Alternatively the minimum in the right hand side of Eq. 6 could be equal to $\frac{1}{4}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)$ for some $i\neq j$. Construct ${\theta}^{\prime}$ by putting $\mu^{\prime}_{i}=\mu^{\prime}_{j}=\frac{1}{2}(\mu_{i}-\mu_{j})$ and $\Sigma^{\prime}_{i}=\Sigma^{\prime}_{j}=\frac{1}{2}(\Sigma_{i}-\Sigma_{j})$ and keeping the rest of the parameters of ${\theta}$. It is easy to see that $\|{\theta}^{\prime}-{\theta}\|^{2}=\frac{1}{4}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)$. Note that $\theta^{\prime}\in\Theta$ by the convexity condition. By perturbing $w_{i}$ and $w_{j}$ slightly, and keeping the rest of parameters fixed, we can obtain ${\theta}^{\prime\prime}$ arbitrarily close to ${\theta}^{\prime}$ with the same probability density. Hence the radius of identifiability does not exceed $\frac{1}{4}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)$, which completes the proof. $\Box$

From the discussion above we have the following

Let $\Theta$ be a convex set, such that for any $\theta\in\Theta$ all mixing coefficients $w_{i}$ are nonzero. Then

It is also easy to see that the radius of identifiability satisfies a type of triangle inequality and that under any permutation of (mean, covariance matrix, mixing weight) triples the radius of identifiability does not change. This is expressed in the following two lemmas (the straightforward proofs are omitted):

From now on, we will assume that $\Theta$ is a sufficiently large ball or cube (with the necessary conditions to make $p_{\theta}$ a valid probability distribution), so that we do not have to worry about convexity and other technical properties.

We will now state the following Theorem whose proof can be found in appendix C.

2 Sketch of the Proof of Theorem 3.1

We present a brief overview of the proof. The technical details can be found in Appendix C. The main idea is to show that parameters of high-dimensional Gaussian mixture can be estimated arbitrarily well using $\operatorname*{poly}(n)$ projections to coordinate subspaces, whose dimension only depends on $k$. Since the dimension of these lower dimensional subspaces is independent of $n$, results from Section 2 can be used to estimate the parameters.

Let $\theta=(\theta_{1},\theta_{2},\ldots,\theta_{k})$, where $\theta_{i}=(\mu_{i},\Sigma_{i},w_{i})$, be the parameter vector after flattening the covariance matrices. Recall that projection of $p_{\theta}$ onto a $2k^{2}$-coordinate plane $T$, will result in a mixture $\pi_{T}(p_{\theta})$, parameterized (with a slight abuse of notation) by $P_{T}(\theta)=(P_{T}(\theta_{1}),P_{T}(\theta_{2}),\ldots,P_{T}(\theta_{k}))$.

Step 1: Let ${\mathscr{R}}(\theta)$ be the radius of identifiability. Theorem 3.7 guarantees the existence of a $2k^{2}$-dimensional coordinate subspace $S$, such that radius of identifiability decreases by at most $\frac{1}{n}$, ${\mathscr{R}}(P_{S}(\theta))\geq\frac{1}{n}{\mathscr{R}}(\theta)$.

To identify such a subspace, we take all $n\choose 2k^{2}$ coordinate projections. For each projection to a subspace $T$ we estimate the parameters using the Theorem 2.8. It is important to note that given $\epsilon^{\prime}$ as input, Theorem 2.8 is guaranteed to produce a value of parameter $\widehat{P_{T}(\theta)}$, such that $|{\mathscr{R}}(\widehat{P_{T}(\theta)})-{\mathscr{R}}(P_{T}({\theta}))|<\epsilon^{\prime}$ (Lemma 3.5) using a number of samples polynomial in $k$ and $\frac{1}{\epsilon^{\prime}}$. Applying the union bound for all $n\choose 2k^{2}$ projections provides an estimate for the radius of identifiability for each projection within $\epsilon^{\prime}$. Choosing $\epsilon^{\prime}$ appropriately (say, $\frac{{\mathscr{R}}({\theta})}{2n}$), and choosing the projection with the largest estimated radius of identifiability, yields a coordinate subspace $S$ with a lower bounded ${\mathscr{R}}(P_{S}({\theta}))$.

The coordinates within $S$ are represented by the horizontally shaded region in Figure 2. We use this space as a starting point for Step 2.

Step 2: By applying Corollary 2.11 to the projection $P_{S}({\theta})$, we can estimate the mixing weights, projections of the original means and $2k^{2}\times 2k^{2}$ minors of the covariance matrices corresponding to the coordinates within $S$. We now need to estimate the rest of the parameters using a sample size polynomial on $n$. We do this by estimating each additional coordinate separately. That is for each coordinate $i$ not in $S$ we take $S_{i}=span(S,e_{i})$, where $e_{i}$ is the corresponding coordinate vector. It can be seen that the radius of identifiability does not decrease going from $S$ to $S_{i}$. We show that the $i$’th coordinate of each component mean can be estimated by applying Corollary 2.11 to the projection to $S_{i}$. We repeat this procedure for each of the $n-2k^{2}$ coordinates not in $S$.

To estimate the covariance matrices we proceed similarly, except that we need to estimate entries corresponding to pairs of coordinates $(i,j)$. Now we have two possibilities, since either one of $i,j$ or both of them may not be in $S$. If exactly one of them, say $i$, is not in $S$, projection to $S_{i}$ defined above can be used to estimate the corresponding entry of each covariance matrix. If both $i,j$ are not in $S$, we take the projection onto $S_{ij}=span(S,e_{i},e_{j})$. By applying Corollary 2.11, we show that the $ij$’th entry of covariance matrices can also be estimated.

Thus, after obtaining the initial space $S$, the complete set of parameters can be estimated using at most $n-2k^{2}+{{n-2k^{2}}\choose 2}$ parameter estimations for $2k^{2}+1$ or $2k^{2}+2$-dimensional subspaces.

This procedure is graphically shown in in Figure 2.

Conclusion and Discussion

The results of this paper resolve the general problem of polynomial learning of Gaussian mixture distributions. Our results do not require any separation assumptions and apply as long as the mixture is identifiable. For example, they apply even if all components of the mixture have the same mean distribution, as long as the covariance matrices are different and the mixing coefficients are non-zero.

The proof brings the techniques of algebraic geometry to the classical method of moments, an approach that, as far as we know, is new to this domain. We also provide quite general results applicable to learning various low-dimensional families and some observations on high-dimensional families going beyond Gaussian mixture distributions with a fixed number of components. For example, one can also learn products of arbitrary probability distributions in a fixed low-dimensional polynomial family, e.g., a product of $n$ number of $d$-dimensional Gaussians mixtures with $k$ components each (which is a $nd$-dimensional Gaussian mixture distribution with $k^{n}$ components).

We are planning to investigate other applications in learning of the framework presented in this paper. We also note that the methods proposed in the paper can be turned into implementable (and potentially practical) algorithms through the use of tools from computational algebraic geometry. This is also a direction of future investigation.

References

Appendix

Appendix A Some Polynomial Families of Distributions

In this appendix we provide a partial list comprising the expressions of moments of various univariate probability distributions which form polynomial families. It turns out that most of the commonly used distributions form polynomial families as shown Table 2. In the fifth column of Table 2, we provide either expression for the $i^{th}$ moment or a recurrence relation, which shows that the moments are polynomial in the distribution parameters, along with explicit expressions for the first three moments. These moment expressions and recurrence relations are well known and can be found in, e.g., . In a couple of cases we need a slightly different parameterization, instead of the standard one, to ensure that the moments are polynomial in these new parameters. For example, in standard parametrization, Negative Binomial distribution $NB(r,p)$ is expressed by probability mass function ${x+r-1\choose r-1}(1-p)^{r}p^{x}$. However, if we replace $p$ by a new parameter $m=\frac{p}{1-p}$, then the moments are polynomial in $r$ and $m$. Recurrence relation for this new parameterization can be obtained following the same steps as in . Table 3 we list two families which are not polynomial.

Appendix B Separation Preserving Coordinate Planes

Existence of a Coordinate Plane where Projected Means Remain Separated :

Similarly, in addition, to ensure that that after projecting onto $S_{\mathcal{M}}$, $P_{S_{\mathcal{M}}}(\mu_{2})$ is guaranteed to remain separated from any $P_{S_{\mathcal{M}}}(\mu_{j})$, $j\in\mathcal{A}_{2}$, by at least $\|\mu_{2}-\mu_{j}\|\frac{1}{\sqrt{l}}$, we may need to add indices of $(k-2)$ additional coordinate directions to $\mathcal{M}$ and so on. So in total $\mathcal{M}$ can have indices of at most $(k-1)+(k-2)+\cdots+1=\frac{k(k-1)}{2}<k^{2}$ coordinate directions to ensure that as long as we project $\{\mu_{i}\}_{i=1}^{k}$ onto $l\choose k^{2}$ different $k^{2}$-coordinate planes, there exists at least one $k^{2}$-coordinate plane $S$ such that $\forall_{i,j},~{}\|P_{S}(\mu_{i})-P_{S}(\mu_{j})\|\geq\|\mu_{i}-\mu_{j}\|\frac{1}{\sqrt{l}}$. $\Box$

Existence of a Coordinate Plane where Projected Covariance Matrices Remain Separated :

Similarly, in addition, to ensure that that after projecting onto $S_{\mathcal{M}}$, $P_{S_{\mathcal{M}}}(\Sigma_{2})$ is guaranteed to remain separated from any $P_{S_{\mathcal{M}}}(\Sigma_{j})$, $j\in\mathcal{A}_{2}$, by at least $\|\Sigma_{2}-\Sigma_{j}\|\frac{1}{l}$, we may need to add indices of $2(k-2)$ additional coordinate directions to $S_{\mathcal{M}}$ and so on. So in total $\mathcal{M}$ can have indices of at most $2(k-1)+2(k-2)+\cdots+1=k(k-1)<k^{2}$ coordinate directions to ensure that as long as we project $\{\Sigma_{i}\}_{i=1}^{k}$ onto $l\choose k^{2}$ different $k^{2}$-coordinate planes, there exists at least one $k^{2}$-coordinate plane $S$ such that $\forall_{i,j},~{}\|P_{S}(\Sigma_{i})-P_{S}(\Sigma_{j})\|\geq\|\Sigma_{i}-\Sigma_{j}\|\frac{1}{l}$. $\Box$

Appendix C Proof of Theorem 3.1, Theorem 3.2 and Theorem 3.7

In this appendix we give the detailed proof of Theorem 3.1 as well as proof of Theorem 3.2 and Theorem 3.7. We start with some preliminary Lemmas.

Proof:Explicit expression for ${\mathscr{R}}(\theta)$ is given in Equation 6. If $\frac{1}{4}\min_{i\neq j}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)<\min_{i}w_{i}^{2}$ then for any $i\neq j,({\mathscr{R}}(\theta))^{2}=\frac{1}{4}\min_{i\neq j}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)\leq\frac{1}{4}\|\theta_{i}-\theta_{j}\|^{2}$. On the other hand if $\frac{1}{4}\min_{i\neq j}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)\geq\min_{i}w_{i}^{2}$ then for any $i\neq j$, $({\mathscr{R}}(\theta))^{2}=\min_{i}w_{i}^{2}\leq\frac{1}{4}\min_{i\neq j}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)\leq\frac{1}{4}\|\theta_{i}-\theta_{j}\|^{2}$. $\Box$

Let $\theta=(\theta_{1},\theta_{2},\ldots,\theta_{k})$, where $\theta_{i}=(\mu_{i},\Sigma_{i},w_{i})$, be parameter vector after flattening the covariance matrices. Recall that projection of $p_{\theta}$ onto any $2k^{2}$-coordinate plane $T$, will result in a mixture $\pi_{T}(p_{\theta})$, which is parameterized (with a little abuse of notation) by $P_{T}(\theta)=(P_{T}(\theta_{1}),P_{T}(\theta_{2}),\ldots,P_{T}(\theta_{k}))$.

Details of Step 1: Let $\gamma=\min\left(\frac{{\mathscr{R}}(\theta)}{n},\frac{\epsilon}{n}\right)$ where ${\mathscr{R}}(\theta)$ is the radius of identifiability. Theorem 3.7 guarantees the existence of a $2k^{2}$-dimensional coordinate subspace $S$, such that radius of identifiability decreases by at most $\frac{1}{n}$, ${\mathscr{R}}(P_{S}(\theta))\geq\frac{1}{n}{\mathscr{R}}(\theta)\geq\gamma$. To identify such a subspace, we take all $n\choose 2k^{2}$ coordinate projections. For any fixed projection to a $2k^{2}$-dimensional subspace $T$, invoking Theorem 2.8 using a sample of size $\operatorname*{poly}(\frac{1}{\gamma},\frac{1}{\delta},B)$, (setting the precision parameter to $\frac{\gamma}{3}$) produces a value of parameters $\widehat{P_{T}(\theta)}$ such that $|{\mathscr{R}}(\widehat{P_{T}(\theta)})-{\mathscr{R}}(P_{T}({\theta}))|<\frac{\gamma}{3}$ (Lemma 3.5). Applying the union bound for all $n\choose 2k^{2}$ projections provides an estimate for the radius of identifiability for each projection within $\frac{\gamma}{3}$. Thus invoking Theorem 2.8 $n\choose 2k^{2}$ times, each time using a sample of size $\operatorname*{poly}\left(\frac{1}{\gamma},\frac{1}{(\delta/4n^{2})},B\right)$, (setting the precision parameter to $\frac{\gamma}{3}$) and choosing the projection with the largest estimated radius of identifiability, yields a coordinate subspace $S$ such that with probability at least $1-\frac{\delta}{4},~{}{\mathscr{R}}(P_{S}(\theta))\geq\frac{\gamma}{3}$. Clearly the sample size requirement for this step is polynomial in $n$.

Details of Step 2: By applying Corollary 2.11 to the mixture $\pi_{S}(p_{\theta})$, where $S$ is obtained in Step 1, using a sample of size $\operatorname*{poly}(\frac{1}{\gamma},\frac{1}{\delta},B)$, (setting the precision parameter to $\frac{\gamma}{9}$) with probability greater than $1-\frac{\delta}{4}$ we can get an estimate of $\widehat{P_{S}(\theta)}$ satisfying $\|\widehat{P_{S}(\theta)}-P_{S}(\theta)\|\leq\frac{\gamma}{9}$. Note that these estimates encompass the mixing weights, projections of the original means and $2k^{2}\times 2k^{2}$ minors of the covariance matrices corresponding to the coordinates within $S$. If we let $\theta^{{}^{\prime}}$ to be $P_{S}(\theta)$ then the estimate $\hat{\theta}^{{}^{\prime}}=\widehat{P_{S}(\theta)}$ is, up to a permutation, within $\frac{\gamma}{9}$ of $\theta^{{}^{\prime}}$ with probability greater than $(1-\frac{\delta}{4})$. Note that the dimension of $\theta^{{}^{\prime}}$ is $(k-1)+k\left(2k^{2}+\frac{2k^{2}(2k^{2}+1)}{2}\right)$. These parameters are represented by the horizontally shaded region in Figure 2.

We now need to estimate the rest of the parameters using a sample size polynomial on $n$. This procedure explained in the following two sub-steps.

2a: Estimating means and part of covariance matrices

In this sub-step we estimate each additional coordinate separately. That is for each coordinate $i$ not in $S$ we take $S_{i}=span(S,e_{i})$, where $e_{i}$ is the corresponding coordinate vector. It can be seen that the radius of identifiability does not decrease going from $S$ to $S_{i}$. We will show that the $i$’th coordinate of each component mean, $i$’th diagonal entry for each component covariance matrix and $2k^{2}$ extra off diagonal entries for each component covariance matrix can be estimated by applying Corollary 2.11 to the projection to $S_{i}$. We repeat this procedure for each of the $n-2k^{2}$ coordinates not in $S$.

For each such $n-2k^{2}$ coordinates not in $S$, we project $p_{\theta}$ onto $S_{i}$ and invoke the algorithm of Corollary 2.11 (setting the precision parameter to be $\frac{\gamma}{9}$) using a sample of size $\operatorname*{poly}\left(\frac{1}{\gamma},\frac{1}{(\delta/4n)},B\right)$ . Clearly this sample size is polynomial in $n$. This ensures that, each time we get an estimate $\widehat{P_{S_{i}}(\theta)}$ such that with probability at least $1-\frac{\delta}{4},~{}\|\widehat{P_{S_{i}}(\theta)}-P_{S_{i}}(\theta)\|\leq\frac{\gamma}{9}$. Since $P_{S}(\theta)\subset P_{S_{i}}(\theta)$ letting $\phi_{i}=P_{S_{i}}(\theta)\setminus P_{S}(\theta)$ to be the extra parameters, we have for each $i$,

with probability greater than $(1-\frac{\delta}{4})$, where $\hat{\phi}$ is the estimate of $\phi$. Since for each $S_{i}$, $\forall_{m\neq n},\|P_{S_{i}}(\theta_{m})-P_{S_{i}}(\theta_{n})\|\geq\frac{2\gamma}{3}$, (using Lemma C.1 and Lemma C.2), estimates of the extra parameters can be uniquely associated to the parameters of the component Gaussian distributions estimated in Step 2.

Letting $\theta^{{}^{\prime\prime}}$ to be $\cup_{i=1}^{n-2k^{2}}\phi_{i}$, we have

with probability greater than $(1-\frac{\delta}{4})$, where $\hat{\theta}^{{}^{\prime\prime}}$ is the estimate of $\theta^{{}^{\prime\prime}}$.

Note that the dimension of $\theta^{{}^{\prime\prime}}$ is $k(n-2k^{2})(2+2k^{2})$, where each $P_{S_{i}}(\theta)\setminus P_{S}(\theta)$ encompasses $i$’th coordinate for each component mean, $i$’th diagonal entry for each component covariance matrix and $2k^{2}$ extra off diagonal entries for each component covariance matrix. These parameters represent the diagonally shaded region in Figure 2.

2b: Estimating the remaining entries of covariance matrices

To estimate the the remaining parameters of the covariance matrices we need to estimate entries corresponding to pairs of coordinates $(i,j)$ when both $i$ and $j$ are not in $S$. We take the projection onto $S_{ij}=span(S,e_{i},e_{j})$. It can be seen as before that radius of identifiability does not decrease going from $S$ to $S_{ij}$. By applying Corollary 2.11, we will show that the $ij$’th entry of covariance matrices can be estimated. Since there are $n-2k^{2}\choose 2$ such projections, we repeat this procedure $n-2k^{2}\choose 2$ times, each time we project $p_{\theta}$ onto appropriate $S_{ij}$ and invoke the algorithm of Corollary 2.11, (setting the precision parameter to $\frac{\gamma}{9}$) using a sample of size $\operatorname*{poly}\left(\frac{1}{\gamma},\frac{1}{(\delta/4n^{2})},B\right)$. Clearly this sample size is polynomial in $n$. This ensures that, each time we get an estimate $\widehat{P_{S_{ij}}(\theta)}$ such that with probability at least $1-\frac{\delta}{4},~{}\|\widehat{P_{S_{ij}}(\theta)}-P_{S_{ij}}(\theta)\|\leq\frac{\gamma}{9}$. Since $P_{S}(\theta)\subset P_{S_{ij}}(\theta)$ in each case and there are $n-2k^{2}\choose 2$ such cases, letting $\psi_{t},t=1,\ldots,{n-2k^{2}\choose 2}$ to be the extra parameters in each case , we have for each $t$, $\|\hat{\psi}_{t}-\psi_{t}\|\leq\frac{\gamma}{9}$ with probability greater than $(1-\frac{\delta}{4})$, where $\hat{\psi}_{t}$ is the estimate of $\psi_{t}$. As before estimates of these extra parameters can be uniquely associated to the parameters of the component Gaussian distributions estimated in Step 2. Letting $\theta^{{}^{\prime\prime\prime}}$ to be the $k{n-2k^{2}\choose 2}$ covariance parameters that have not been estimates in the previous steps, we have $\theta^{{}^{\prime\prime\prime}}\subset\cup_{t=1}^{n-2k^{2}\choose 2}\psi_{t}$, and in particular,

where $\hat{\theta}^{{}^{\prime\prime\prime}}$ is the estimate of $\theta^{{}^{\prime\prime\prime}}$, with probability greater than $(1-\frac{\delta}{4})$. The parameters represented by $\theta^{{}^{\prime\prime\prime}}$ are shown in the vertically shaded region of Figure 2.

In Step 1 we need to invoke Theorem 2.8 $n\choose 2k^{2}$ times. In step 2 we need to invoke Corollary 2.11 $1+(n-2k^{2})+{n-2k^{2}\choose 2}$ times. Thus total invocation of Theorem 2.8 and Corollary 2.11 combined is $\operatorname*{poly}(n)$. Now note that if $\epsilon<{\mathscr{R}}(\theta)$ then $\gamma=\frac{\epsilon}{n}$. On the other hand if $\epsilon\geq{\mathscr{R}}(\theta)$ then $\gamma=\frac{{\mathscr{R}}(\theta)}{n}\leq\frac{\epsilon}{n}$.

Since $\theta^{{}^{\prime}}\cup\theta^{{}^{\prime\prime}}\cup\theta^{{}^{\prime\prime\prime}}=\theta$, the corresponding estimate (with a little abuse of notation) $\hat{\theta}=\hat{\theta}^{{}^{\prime}}\cup\hat{\theta}^{{}^{\prime\prime}}\cup\hat{\theta}^{{}^{\prime\prime\prime}}$, with probability greater than $(1-\delta)$, is within $\epsilon$ of $\theta$ only up to a permutation using a sample of size $\operatorname*{poly}\left(n,\max\left(\frac{1}{\epsilon},\frac{1}{{\mathscr{R}}(\theta)}\right),\frac{1}{\delta},B\right)$. $\Box$

Theorem 3.7, guarantees the existence of a $2k^{2}$-coordinate plane $S$ such that when $p_{\theta}$ is projected onto $S$, the corresponding mixture $\pi_{S}(p_{\theta})$, parameterized by $P_{S}(\theta)$, satisfies that ${\mathscr{R}}(P_{S}(\theta))\geq{\mathscr{R}}(\theta)\frac{1}{n}$. Since $S$ is not known in advance, projecting $p_{\theta}$ on to all $n\choose 2k^{2}$, $2k^{2}$-coordinate planes, each time invoking the algorithm of Theorem 2.8 with a sample of size $\operatorname*{poly}\left(\frac{1}{(\epsilon/3n)},\frac{1}{(\delta/n^{2})},B\right)$ and using union bound ensures that for each $2k^{2}$-coordinate plane $T$, Theorem 2.8 produces a value of parameters $\widehat{P_{T}(\theta)}$ such that $\widehat{P_{T}(\theta)}\in\mathcal{N}\left(P_{T}(\theta),\frac{\epsilon}{3n}\right)$ with probability greater than $(1-\delta)$. Now for each such $2k^{2}$-coordinate plane $T$, Lemma 3.5 guarantees that $|{\mathscr{R}}{\widehat{P_{T}(\theta)}}-{\mathscr{R}}{P_{T}(\theta)}|\leq\frac{\epsilon}{3n}$. Thus there must exist at least one $2k^{2}$-coordinate plane (say $T_{*}$) such that, ${\mathscr{R}}(\widehat{P_{T_{*}}(\theta)})\geq{\mathscr{R}}(\theta)\frac{1}{n}-\frac{\epsilon}{3n}$. Thus,

The desired algorithm now works as follows. For each of the $n\choose 2k^{2}$ values of parameters $\widehat{P_{T}(\theta)}$ outputted by Theorem 2.8, we compute ${\mathscr{R}}(\widehat{P_{T}(\theta)})$ using Equation 6. Now set ${\mathscr{R}}_{*}=\max_{T}{\mathscr{R}}(\widehat{P_{T}(\theta)})$. If ${\mathscr{R}}_{*}<\frac{2\epsilon}{3n}$ then output ${\mathscr{R}}(\theta)<\epsilon$ otherwise output ${\mathscr{R}}(\theta)\geq\epsilon$. $\Box$

Lemma B.1 establishes the existence of a $k^{2}$-coordinate plane $S_{1}$, such that $\forall_{i,j},~{}\|P_{S_{1}}(\mu_{i})-P_{S_{1}}(\mu_{j})\|^{2}\geq\|\mu_{i}-\mu_{j}\|^{2}\frac{1}{n}>\|\mu_{i}-\mu_{j}\|^{2}\frac{1}{n^{2}}$. Similarly Lemma B.2 establishes the existence of a $k^{2}$-coordinate plane $S_{2}$, such that $\forall_{i,j}~{}\|P_{S_{2}}(\Sigma_{i})-P_{S_{2}}(\Sigma_{j})\|^{2}\geq\|\Sigma_{i}-\Sigma_{j}\|^{2}\frac{1}{n^{2}}$. Taking the span of these two planes produces a $2k^{2}$-coordinate plane $S=span(S_{1},S_{2})$, such that

Note that radius of identifiability of $\pi_{S}(p_{\theta})$, parameterized by $P_{S}(\theta)$, is given by,

where the inequality follows from the fact that $\forall a_{1},a_{2},b,(a_{1}\leq a_{2})\Rightarrow(\min(a_{1},b)\leq\min(a_{2},b))$.

case 1: $\frac{1}{4}\min_{i\neq j}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)\leq\min_{i}w_{i}^{2}$

Here $({\mathscr{R}}(\theta))^{2}=\frac{1}{4}\min_{i\neq j}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)$ and $({\mathscr{R}}(P_{S}(\theta)))^{2}\geq\left(\frac{1}{n^{2}}\right)\frac{1}{4}\min_{i\neq j}\left(\|\mu_{i}-\mu_{j}\|^{2}+\|\Sigma_{i}-\Sigma_{j}\|^{2}\right)=\left(\frac{1}{n^{2}}\right)({\mathscr{R}}(\theta))^{2}$.