Clustering and Sum of Squares Proofs, Part 3
This is part 3 of a continuing series on clustering, Gaussian mixtures, and Sum of Squares (SoS) proofs. If you have not read them yet, I recommend starting with Part 1 and Part 2. Also, if you find errors please mention them in the comments (or otherwise get in touch with me) and I will fix them ASAP.
The Story So Far
Let’s have a brief recap. We are designing an algorithm to cluster samples from Gaussian mixture models on . Our plan is to do this by turning a simple identifiability proof into an algorithm. For us, “simple” means that the proof is captured by the low degree Sum of Squares (SoS) proof system.
We have so far addressed only the case (which will remain true in this post). In part 1 we designed our identifiability proof, not yet trying to formally capture it in SoS. The proof was simple in the sense that it used only the triangle inequality and Holder’s inequality. In part 2 we defined SoS proofs formally, and stated and proved an SoS version of one of the key facts in the identifiability proof (Fact 2).
In this post we are going to finish up our SoS identifiability proof. In the next post, we will see how to transform the identifiability proof into an algorithm.
Setting
We recall our setting formally. Although our eventual goal is to cluster samples sampled from a mixture of Gaussians, we decided to remember only a few properties of such a collection of samples, which will hold with high probability.
The properties are:
(1) They break up into clusters of equal size, , such that for some , each cluster obeys the empirical moment bound,
where is the empirical mean of the cluster , and
(2) Those means are separated: .
The main statement of cluster identifiability was Lemma 1, which we restate for convenience here.
Lemma 1. Let . Let be a partition of into pieces of size such that for each , the collection of numbers obeys the following moment bound:
where is the average and is some number in . Let be such that for every . Suppose is large enough that .
Let have size and be such that obey the same momentboundedness property:
for the same , where is the mean . Then there exists an such that
for some universal constant .
Our main goal in this post is to state and prove an SoS version of Lemma 1. We have already proved the following Fact 2, an SoS analogue of Fact 1 which we used to prove Lemma 1.
Fact 2. Let . Let have ; let be its mean. Let be a power of . Suppose satisfies
Let be indeterminates. Let be the following set of equations and inequalities.
Then
Remaining obstacles to an SoS version of Lemma 1
We are going to face a couple of problems.
(1) The statement and proof of Lemma 1 are not sufficiently symmetric for our purposes — it is hard to phrase things like “there exists a cluster such that…” as statements directly about polynomials. We will handle this by giving more symmetric version of Lemma 1, with a more symmetric proof.
(2) Our proof of Lemma 1 uses the conclusion of Fact 1 in the form
whereas Fact 2 concludes something slightly different:
The difference in question is that the polynomials in Fact 2 are degree , and appears on both sides of the inequality. If we were not worried about SoS proofs, we could just cancel terms in the second inequality and take th roots to obtain the first, but these operations are not necessarily allowed by the SoS proof system.
One route to handling this would be to state and prove a version of Lemma 1 which concerns only degree . This is probably possible but definitely inconvenient. Instead we will exhibit a common approach to situations where it would be useful to cancel terms and take roots but the SoS proof system doesn’t quite allow it: we will work simultaneously with SoS proofs and with their dual objects, pseudodistributions.
We will tackle issues (1) and (2) in turn, starting with the (a)symmetry issue.
Lemma 1 reformulated: maintaining symmetry
We pause here to record an alternative version of Lemma 1, with an alternative proof. This second version is conceptually the same as the one we gave in part 1, but it avoids breaking the symmetry among the clusters , whereas this was done at the very beginning of the first proof, by choosing the ordering of the clusters by . Maintaining this symmetry requires a slight reformulation of the proof, but will eventually make it easier to phrase the proof in the Sum of Squares proof system. In this proof we will also avoid the assumption , however, we will pay a factor of rather than in the final bound.
Alternative version of Lemma 1.
Let .
Let be a partition of into pieces of size such that for each , the collection of numbers obeys the following moment bound:where is the average and is some number in . Let be such that for every .
Let have size and be such that obey the same momentboundedness property:
.
for the same , where . Then
We remark on the conclusion of this alternative version of Lemma 1. Notice that are nonnegative numbers which sum to . The conclusion of the lemma is that for . Since the sum of their squares is at least , one obtains
matching the conclusion of our first version of Lemma 1 up to an extra factor of .
Proof of alternative version of Lemma 1.
Let again have size with mean and th moment bound . Since partition ,
We will endeavor to bound for every pair . Since ,
Certainly and similarly for , so this is at most
Using Fact 1, this in turn is at most . So, we obtained
for every .
Putting this together with our first bound on , we get
QED.
Now that we have resolved the asymmetry issue in our earlier version of Lemma 1, it is time to move on to pseudodistributions, the dual objects of SoS proofs, so that we can tackle the last remaining hurdles to proving an SoS version of Lemma 1.
Pseudodistributions and duality
Pseudodistributions are the convex duals of SoS proofs. As with SoS proofs, there are several expositions covering elementary definitions and results in detail (e.g. the lecture notes of Barak and Steurer, here and here). We will define what we need to keep the tutorial selfcontained but refer the reader elsewhere for further discussion. Here we follow the exposition in those lecture notes.
As usual, let be some indeterminates. For a finitelysupported function and a function , define
If defines a probability distribution, then is the operator sending a function to its expectation under .
A finitelysupported is a degree pseudodistribution if
(1)
(2) for every polynomial of degree at most .
When is clear from context, we usually suppress it and write . Furthermore, if is an operator and for some pseudodistribution , we often abuse terminology and call a pseudoexpectation.
If is a family of polynomial inequalities and is a degree pseudodistribution, we say satisfies if for every and such that one has
We are not going to rehash the basic duality theory of SoS proofs and pseudodistributions here, but we will need the following basic fact, which is easy to prove from the definitions.
Fact: weak soundness of SoS proofs.
Suppose and that is a degree pseudodistribution which satisfies . Then for every SoS polynomial , if $\deg h + \ell \leq d$ then .
We call this “weak soundness” because somewhat stronger statements are available, which more readily allow several SoS proofs to be composed. See Barak and Steurer’s notes for more.
The following fact exemplifies what we mean in the claim that pseudodistributions help make up for the inflexibility of SoS proofs to cancel terms in inequalities.
Fact: pseudoexpectation CauchySchwarz.
Let be a degree pseudoexpectation on indeterminates . Let and be polynomials of degree at most . ThenAs a consequence, if has degree and is a power of , by induction
Proof of pseudoexpectation CauchySchwarz.
For variety, we will do this proof in the language of matrices rather than linear operators. Let be the matrix indexed by monomials among of degree at most , with entries . If is a polynomial of degree at most , we can think of as a vector indexed by monomials (whose entries are the coefficients of ) such that . Hence,
QED.
We will want a second, similar fact.
Fact: pseudoexpectation Holder’s.
Let be a degree sum of squares polynomial, , and a degree pseudoexpectation. Then
The proof of pseudoexpectation Holder’s is similar to several we have already seen; it can be found as Lemma A.4 in this paper by Barak, Kelner, and Steurer.
Lemma 2: an SoS version of Lemma 1
We are ready to state and prove our SoS version of Lemma 1. The reader is encouraged to compare the statement of Lemma 2 to the alternative version of Lemma 1. The proof will be almost identical to the proof of the alternative version of Lemma 1.
Lemma 2.
Let . Let be a partition of into pieces of size such that for each , the collection of numbers obeys the following moment bound:where is the average and is a power of in . Let be such that for every .
Let be indeterminates. Let be the following set of equations and inequalities.
As before is the polynomial . Thinking of the variables as defining a set via its indicator, let be the formal expression
Let be a degree pseudoexpectation which satisfies . Then
Proof of Lemma 2.
We will endeavor to bound from above for every . Since we want to use the degree polynomials in Fact 2, we get started with
by (repeated) pseudoexpectation CauchySchwarz.
Since and are separated, i.e. , we also have
where the indeterminate is and we have only used the SoS triangle inequality. Hence,
Applying Fact 2 and soundness to the righthand side, we get
Now using that and hence and similarly for , we get
By pseudoexpectation CauchySchwarz
which, combined with the preceding, rearranges to
By pseudoexpectation Holder’s,
All together, we got
Now we no longer have to worry about SoS proofs; we can just cancel the terms on either side of the inequality to get
Putting this together with
finishes the proof. QED.
Clustering and Sum of Squares Proofs, Part 2
This is part 2 of a series on clustering, Gaussian mixtures, and Sum of Squares (SoS) proofs. If you have not read it yet, I recommend starting with Part 1. Also, if you find errors please mention them in the comments (or otherwise get in touch with me) and I will fix them ASAP.
Welcome back.
In the last post, we introduced Gaussian mixture models and the clustering problem for Gaussian mixtures. We described identifiability proofs for unsupervised learning problems. Then we set ourselves some goals:
 Design a simple identifiability proof for clustering in Gaussian mixtures, saying that if are (enough) samples from a dimensional mixture of Gaussians, the groundtruth clustering of the ‘s by which Gaussian they were drawn from is identifiable from the samples.
 Formalize the simplicity of that identifiability proof by showing that it is captured by a formal proof system of restricted power: the Sum of Squares (SoS) proof system.
 Guided by our SoS identifiability proof, design an algorithm for clustering in Gaussian mixtures. (And hence prove Theorem 1 from last time.)
In the last post, we accomplished task (1) in dimensional case. In this post we will get started on task (2), again in the dimensional case.
Recalling from last time, in our identifiability proof we remembered only two things things about our samples :
(1) They break up into clusters of equal size, , such that for some , each cluster obeys the empirical moment bound,
where is the empirical mean of the cluster , and
(2) Those means are separated: .^{1}
The key tool we used in our identifiability proof was Fact 1, which we restate here for convenience.
Fact 1. Let have . Let denote a uniform sample from and similarly for . Let and . Suppose satisfy the th moment bound
Then
We are going to give a Sum of Squares proof of this fact. Or rather: we are going to state a very similar fact, which concerns inequalities among lowdegree polynomials, and give a Sum of Squares proof of that.
We are going to do things in a slightly unusual order, delaying definition of the SoS proof system till we have something concrete in mind to prove in it.
First, because SoS is a proof system to reason about inequalities among lowdegree polynomials, we are going to formulate Fact 2, which is like Fact 1 except it will be explicitly about lowdegree polynomials. Proving Fact 2 will be our goal.
Second, we will define the SoS proof system.
Finally, we will prove this Fact 2 in the lowdegree SoS proof system.
Fact 2: an SoS version of Fact 1
Fact 1 concerns two subsets of . When we used Fact 1 to prove Lemma 1 in part 1, one of those sets was one of the groundtruth clusters among , and one of them was a “candidate” cluster — Lemma 1 showed that the candidate cluster must in fact have been close to one of the true clusters .
We will design a system of polynomial equations whose solutions are in correspondence with candidate clusters . This is probably unavoidably foreign at first. We will offer some attempts at demystifying remarks later on, but for now we will forge ahead.
Let . Let be some indeterminates; they will be the variables in our polynomials. We are going to think of them as indicators of a subset which is a candidate cluster.
First, let’s enforce that is the indicator vector of a set of size . Consider the equations
.
Any solution to these equations over is a indicator of a subset of of size .
The second hypothesis Fact 1 places on a candidate cluster is the th moment bound. Let’s enforce that with a polynomial inequality. First, we need some notation for the empirical mean of . Denote by the polynomial
.
Often we drop the and just write . And now consider the inequality:
.
Belaboring the point somewhat: any solution over to the equations and inequalities we have described would correspond to a subset of of which obeys the th empirical moment bound. (Here we assume that is even, so that .)
Although we don’t have all the definitions we need in place yet, we will go ahead and state Fact 2. We introduce some suggestive notation. If , we define the polynomial
.
Often we just write .
Fact 2. Let . Let have ; let be its mean. Let be a power of . Suppose satisfies
Let be indeterminates. Let be the following set of equations and inequalities.
Then
We have not yet defined the notation . This notation means that that there is a degree SoS proof of the inequality on the righthand side using the axioms — we will define this momentarily.
The purpose of stating Fact 2 now was just to convince the reader that there is a plausible version of Fact 1 which may be stated entirely as inequalities among polynomials. The reader is encouraged to compare the hypotheses and conclusions of Facts 1 and 2 (ignoring this for now).^{2} There are two main differences:
(a) The inequality in the conclusion of Fact 2 is raised to the th power, as compared to the conclusion of Fact 1.
(b) The inequality in the conclusion of Fact 2 seems to have extra factors of on both sides.
Point (a) is needed just to make both sides of the inequality into polynomials in ; otherwise there would be fractional powers. The need for (b) is more subtle, and we will not be able to fully understand it for a while. For now, what we can say is: the inequality
would be true for any which solves , but that might not have an SoS proof.
One last difference is the factor on the righthand side of the conclusion. This is probably not inherent; it arises because we will use an easytoprove but lossy version of the triangle inequality in our SoS proof. In any case, it is dwarfed by the term , so we are not too worried about it.
Enough dancing around these SoS proofs — in order to stop with the handwaiving, we need to set up our proof system.
Sum of Squares Proofs
We cannot go any further without defining the formal proof system we will work in. Since for now we are sticking with a onedimensional setting, things can be little simpler than for the proof system we will need when become highdimensional, but developing the proof system still incurs a little notational burden. That is life.
The Sum of Squares proof system, henceforth “SoS”, is a formal proof system for reasoning about systems of polynomial equations and inequalities over the real numbers. At its heart is the simple fact that if is a polynomial in indeterminates with real coefficients, then for all .
Plenty of elementary expositions on SoS proofs are available (see e.g. SoS on the hypercube, SoS on general domains, and the first several sections of this paper by Ryan O’Donnell and Yuan Zhou.) We will define as much as we need to keep this tutorial selfcontained but for expanded discussion we refer the reader to those resources and references therein.
Let be some indeterminates. Let be some polynomial inequalities in those indeterminates. If is some other polynomial with real coefficients, it may be the case that for any satisfying , also ; we would say that implies .
The key concept for us will be that implies with a sum of squares proof. We say that SoSproves if there exist polynomials for such that
and the polynomials are sums of squares—i.e. each of them has the form for some polynomials . Notice that if this equation holds, for any which satisfies the inequalities the righthand side must be nonnegative, so is also nonnegative.
The polynomials form an SoS proof that implies . If are all at most , we say that the proof has degree , and we write
.
When we often just write .
We commonly use a few shorthand notations.
 We write , by which we mean .
 We include polynomial equations such as in , by which we mean that contains both and .
 We write , by which we mean that both and .
Although the definition suggests something static — there is a fixed collection of polynomials forming an SoS proof — in practice we treat SoS proofs as dynamic objects, building them line by line much as we would any other proof. We are going to see an example of this very soon when we prove Fact 2.
It is time to begin to make good on the promise from the last section that we would get substantial mileage out of proving identifiability of mixtures of Gaussians using only simple inequalities. While it will take us several sections to completely make good on our promise, we can begin by giving SoS versions of the triangle and Holder’s inequalities we used in our identifiability proof. We will prove one of these now to give the reader a sense of how such arguments go; since there is usually not much novelty in SoS proofs of such basic inequalities we will defer others till later.
We would like to emphasize that the following SoS proofs themselves have nothing to do with mixtures of Gaussians; instead they are part of a growing problemindependent toolkit of basic inequalities useful in designing SoS proofs of more interesting mathematical statements. The fact that one can have such a problemindependent toolkit is in part what makes the proofstoalgorithms method so broadly useful.
SoS triangle inequality
We will start with a fairly weak SoS triangle inequality, that will suffice for our needs.
Much more sophisticated versions of this inequality are possible which allow various norms and do not lose the factor we do here.
Fact: SoS triangle inequality.
Let be indeterminates. Let be a power of . Then
To prove the SoS triangle inequality we will want the following basic observation about composability of SoS proofs. (This is really a special case of a more general composibility result.)
Proposition: squaring SoS proofs.
Suppose and are sums of squares. Then .
Proof of proposition.
By hypothesis, is a sum of squares polynomial. Now,
so it is a product of sum of squares polynomials, and hence itself a sum of squares.
QED.
Proof of SoS triangle inequality.
We start with the case . In this case, we have . We claim that , since the polynomial is a square. Hence, we find
Now to prove the general case, we proceed by induction. We may suppose
By the proposition, this implies . Now we can apply the base case again to for and to complete the argument.
QED.
SoS Holder’s inequality
Holder’s inequality poses a quandary for SoS proofs, because of the nonintegral exponents in most norms (hence such norms do not naturally correspond to polynomials). Consequently, there are many SoS versions of Holder’s inequality in the literature, choosing various ways to handle this nonintegrality. The version we present here will be most useful for our mixtures of Gaussians proof. We will address the nonintegral powers issue by imposing polynomial inequalities requiring that some of the underlying variables be Boolean.
Since the proof of this SoS Holder’s inequality proceeds via a similar induction to the one we used for the SoS triangle inequality we just proved, we defer it to the end of this post.
SoS Holder’s inequality.
Let be indeterminates and let be the collection of equationsNote that the only solutions to are .
Let be polynomials of degree at most . Let be a power of . Then
and
SoS Boolean Inequalities
We will also want one more SoS inequality for our proof of Fact 1. In linear programming relaxations of Boolean problems, it is common to replace an integrality constraint with the linear inequalities . SoS can derive the latter inequalities.
Fact: SoS Boolean Inequalities
.
Proof of Fact.
For the inequality , just use the axiom . For the inequality , write
.
QED.
Proof of Fact 2
Without further ado, we will prove Fact 2 by lifting the proof of Fact 1 into the SoS proof system. Though slightly notationally cumbersome, the proof follows that of Fact 1 nearly line by line—the reader is encouraged to compare the two proofs.
Proof of Fact 2.
We write out what we want to bound in terms of , then apply Holder’s inequality and the triangle inequality.
We deploy our SoS Holder’s inequality to obtain
Next we can use our equations to conclude that in fact
The polynomial is a sum of squares, as is via our SoS triangle inequality; applying this with and we obtain
We can add the sum of squares to obtain
Using the equations , which, as in the SoS Boolean inequalities fact can be used to prove , we obtain
Finally using and , we get
Last of all, using to simplify the term ,
The fact follows by rearranging. QED.
SoS proof of Holder’s inequality
The last thing we haven’t proved is our SoS Holder’s inequality. We will need an SoS CauchySchwarz inequality to prove it.
SoS CauchySchwarz.
Let be indeterminates. Then
Proof of SoS CauchySchwarz.
It is not hard to check that
which is a sum of squares. QED.
Proof of SoS Holder’s inequality.
We start with the case . Using SoS CauchySchwarz, we obtain
This follows from our SoS CauchySchwarz inequality by substituting for and for ; we proved a fact about a sum of squares polynomial in which implies a corresponding fact about a sum of squares in variables and . The latter in turn is a sum of squares in .
To finish the first half of the case, we just need to replace with on the righthand side. By adding the polynomials via the equations , we obtain
To establish the second inequality for the base case, we start by again adding multiples of to get
Then the inequality follows from CauchySchwarz and again adding some multiples of .
Now it’s time for the induction step. We can assume
By again adding multiples of , we obtain
Now both sides are sums of squares. So, by squaring, we find
The proof is finished by applying CauchySchwarz to the last term and cleaning up by adding multiples of as necessary. QED.
Looking Ahead
In the next post, we will use Fact 2 to deduce an SoS version of Lemma 1 (from part 1). Subsequently, we will finish designing an algorithm for onedimensional clustering, proving Theorem 1 (from part 1) in the onedimensional case. Then we will get high dimensional.
Footnotes

Suspicious readers may note that our original Gaussian mixture model assumed that the population means are separated. Because we will draw enough samples that the empirical mean of each cluster is very close to the true (population) mean, this difference can be ignored for now and is easy to handle when we put everything together to analyze our final algorithm.

To make them look even more alike of course we could have introduced notations like , but for concreteness we are keeping the variables at least a little explicit.
Clustering and Sum of Squares Proofs, Part 1
Update (1/5/18): a pdf containing all six posts in this series is now available on my website.
I am excited to (temporarily) join the Windows on Theory family as a guest blogger!
This is the first post in a series which will appear on Windows on Theory in the coming weeks. The aim is to give a selfcontained tutorial on using the Sum of Squares algorithm for unsupervised learning problems, and in particular in Gaussian mixture models. This will take several posts: let’s get started.
In an unsupervised learning problem, the goal is generally to recover some parameters given some data , where is a probability distribution on, say, which is parameterized by . The goal is to estimate by some estimator which (a) does not require too many samples and (b) can be computed from those samples in polynomial time. This basic setup can be instantiated (sometimes with minor adaptations) to capture numerous important problems in statistics and machine learning: a few examples are
 component analysis and its many variants (PCA, ICA, Sparse PCA, etc.)
 Netflix problem / matrix completion / tensor completion
 dictionary learning / blind source separation
 community detection and recovery / stochastic block models
 many clustering problems
Excellent resources on any of these topics are just a Google search away, and our purpose here is not to survey the vast literature on unsupervised learning, or even on provable “TCSstyle” algorithms for these problems. Instead, we will try to give a simple exposition of one technique which has now been applied successfully to many unsupervised learning problems: the Sum of Squares method for turning identifiability proofs into algorithms.
Identifiability is a concept from statistics. If one hopes for an algorithm which recovers parameters , it must at least be true that uniquely (or almost uniquely) determine , with high probability: when this occurs we say is identifiable from the samples .
Classically, identifiability is often proved by analysis of a (typically) inefficient bruteforce algorithm. First, one invents some property of . For example, in a maximumlikelihood argument, one shows that for some . Then, often via a concentrationofmeasure argument, one shows that no far from satisfies property . In the maximumlikelihood example, this would entail showing that if is far from then .
An identifiability argument like this typically has no implications for computationallyefficient algorithms, since finding which satisfies often appears to require bruteforce search. Thus, often when the investigation turns to efficient algorithms, the identifiability argument is abandoned and more explicitly algorithmic techniques are brought to bear: convex relaxations, spectral methods, and even heuristic methods.
The method we present here for designing computationallyefficient algorithms begins with a return to identifiability proofs. The main insight is that if both
 the property and, more importantly,
 the proof that any satisfying must be close to
are sufficiently simple, then identifiability of from does imply the existence of an efficient algorithm to (approximately) recover from !
For us, simple has a formal meaning: the proof should be captured in the lowdegree Sum of Squares proof system.
The algorithms which result in the end follow a familiar recipe: solve some convex relaxation whose constraints depend on and round it to obtain . But the design and analysis of this relaxation are heavily informed by the simple identifiability proof described above. In particular, the convex programs which result will not be familiar relaxations of maximum likelihood problems!
In this series of blog posts, we are going to carry out this strategy from start to finish for a classic unsupervised learning problem: clustering mixtures of Gaussians. So that we can get down to business as quickly as possible, we defer a short survey of the literature on this “proofstoalgorithms” method to a later post.
Mixtures of Gaussians
Gaussian mixtures are classic objects in statistics, dating at least to Pearson in 1894. The basic idea is: suppose you have a data set which was generated in a heterogeneous fashion: some points were sampled from probability distribution , some from , and so on up to , but you do not know which points came from which distributions. Under what settings can you cluster the points by which distribution they came from, and perhaps also recover some properties of those distributions, such as their means ?
Pearson, in 1894, was faced with a collection of body measurements of crabs. The distribution of one such attribute in the data — the ratio of forehead length to body width — curiously deviated from a Gaussian distribution. Pearson concluded that in fact two distinct species of crabs were present in his data set, and that the data should therefore be modeled as a mixture of two Gaussians. He invented the method of moments to discover the means of both the Gaussians in question.^{1} In the years since, Gaussian mixtures have become a fundamental statistical modeling tool: algorithms to fit Gaussian mixtures to data sets are included in basic machine learning packages like sklearn.
Here is our mixture of Gaussians model, formally.
Mixtures of separated spherical Gaussians:
Let
 .
 be such that for every .
 be dimensional spherical Gaussians, centered at the means .
 be iid samples, each drawn by selecting uniformly, then drawing .
 be the induced partition of into parts, where if samples was drawn from
The problem is: given , output a partition of into parts, each of size , such that (up to renaming the clusters ),
for each and some small number .
To avoid some minor but notationally annoying matters, we are going to work with a small variant of the model, where we assume that exactly samples came from each Gaussian . We call a mixture like this “equidistributed”.
We will work up to a proof of this theorem, which was proved recently (as of Fall 2017) in 3 independent works.
Main Theorem (HopkinsLi, KothariSteinhardt, DiakonikolasKaneStewart):
For arbitrarilylarge there is an algorithm requiring samples from the equidistributed mixtures of Gaussians model and running in time which outputs a partition of into parts of size such that with high probability,for some universal constant .^{3}
In particular:
 If for some , then by choosing the algorithm recovers the correct clustering up to errors in time with many samples.
 If for a largeenough universal constant , then choosing gives a quasipolynomialtime algorithm (using quasipolynomiallymany samples) to recover clusters up to error.^{4}
One (rather weak) consequence of the main theorem is that, for samples, there is enough information in the samples to determine the underlying clustering, up to error . Our strategy to prove the main theorem will start with proving the latter statement independently — as we have discussed, such an argument is often called a proof of identifiability because we say that the clusters are identifiable from the samples (up to errors).
While identifiability itself does not carry immediate algorithmic consequences, our proof of identifiability will be somewhat special: it will be simple in a formal sense, namely, that it will be captured by a formal proof system of restricted power. This simplicity of the proof of identifiability will almost immediately imply the main theorem: the construction of a computationallyefficient algorithm from a simple proof of identifiability is the heart of the proofstoalgorithms method.
Identifiability proof: 1 dimension
Our eventual goal is to work up to a proof in the lowdegree Sum of Squares proof system that clusters are identifiable from samples from a mixture of Gaussians. Since we have not yet defined lowdegree Sum of Squares proofs, for now we will focus on constructing an identifiability proof which avoids mathematical facts which we deem “too complicated”. In particular, we will avoid any Chernoff/union bound style arguments.
To get to the heart of the matter it helps to simplify the setting. Our first simplification is to restrict attention to the case, so that distributions are univariate Gaussians with unit variance.
Before stating our first lemma, let’s discuss the key property of a collection of samples from a Gaussian which we will use. Recall that if is a standard Gaussian, then for every ,
If are samples from , then for large enough, the empirical distribution of inherits this property, up to some small fluctuations. Namely, with high probability we would have
(We could have replaced by any small constant greater than .) Here, the notation means that an index is chosen uniformly among .
If for some , then the same discussion applies immediately to and . But even more is true: if is the empirical mean of (that is, ), then with high probability the th centered empirical moment also inherits the same bound:
In the Gaussian mixture setting, so long as enough samples are drawn from each Gaussian , each cluster will have th empirical moments satisfying the above bound (with high probability).
In our identifiability proof, we choose to forget that the samples were drawn from Gaussians, and we remember only that they break up into underlying clusters, each of which satisfies that empirical moment bound. We do not even remember the “true” means of each Gaussian; instead we talk only about the empirical means. We will show that no clustering far from that underlying groundtruth clustering results in clusters which satisfy the empirical moment bound.
Lemma 1. Let . Let be a partition of into pieces of size such that for each , the collection of numbers obeys the following moment bound:
where is the average and is some number in . Let be such that for every . Suppose is large enough that .
Let have size and be such that obey the same momentboundedness property:
for the same , where is the mean . Then there exists an such that
for some universal constant .
How do we interpret Lemma 1 as a statement of cluster identifiability? The lemma implies that the clusters are, up to errors, the only subsets of of size which satisfy the th moment bound. This is our property , like we discussed earlier in this post. The true clustering satisfies (i.e. if you group by this groundtruth clustering, the resulting clusters will have bounded empirical th moments), and every clustering which satisfies this bounded th moment property must be close to the true clustering. Thus, the correct clusters could be identified by searching for subsets of which satisfy the th moment bound (never mind that such a search would naively require about time).
We said that to use the sum of squares method to turn our identifiability proof into an algorithm, both the property and the proof of identifiability need to be simple.
This th moment boundedness property will turn out to be simple enough. What about the proof of Lemma 1? By the end of this post we will prove Lemma 1 in a way which uses only Holder’s inequality for the vs norms and the triangle inequality for the norm. Later, we will show that these inequalities are simple in the correct formal sense: they are captured by a proof system of restricted power.
Our proof of Lemma 1 relies on the following key fact.
Fact 1. Let have . Let denote a uniform sample from and similarly for . Let and . Suppose satisfy the th moment bound
Then
A slightly more general interpretation of this fact is that a pair of random variables on which have bounded th moments and whose total variation distance cannot have means which are too far apart: .
Proof of Fact 1.
Let . Observe that there is a coupling of the random variables so that . The coupling chooses with probability to select a uniform sample , then lets . With probability , the random variable is a uniform sample from and similarly for .
Let be a coupled pair of samples. We expand a quantity related to the one we want to bound, and then apply Holder’s inequality with the and norms. (The underlying inner product space assigns functions the inner product .)
Now we can apply the triangle inequality for the norm to the last term, followed by our th moment assumptions.
Putting everything together, we get . QED.
Keeping in mind our eventual goal of constructing a lowdegree Sum of Squares proof, we record the observation that the only inequalities we required to prove Fact 1 were the vs. Holder’s inequality and the triangle inequality for the norm.
Armed with Fact 1, we can prove Lemma 1.The main idea in the proof is that if and are the two clusters with greatest intersection with , then can only be close to one of .
Proof of Lemma 1.
Let have size , with mean and th moment bound . Without loss of generality, order the clusters so that has largest intersection with , then , and so on: that is . If , then , just by counting.
Since , either or . We claim it must be the second. Using Fact 1,
since certainly , and we assumed . We conclude that .
We have obtained and . Putting these together with Fact 1, we find
Rearranging, this reads QED.
Looking ahead
This concludes our onedimensional identifiability proof, which will form the core of our proof of Theorem 1. In our next post we will lift this proof to a Sum of Squares proof (for which we will need to define Sum of Squares proofs). After that, with a Sum of Squares proof in hand, we will finish designing our mixture of Gaussians algorithm for the onedimensional case. Then we will show that the same ideas, nearly unchanged, imply that the algorithm works in higher dimensions.
Thanks
Many thanks to Boaz Barak, David Steurer, and especially Daniel Freund for their helpful remarks on early drafts of this post.
Footnotes
 Moritz Hardt on Gaussian mixtures and Pearson’s approach

To see how to apply the ideas in this tutorial to a much broader class of clustering problems, see my joint paper with Jerry Li and the recent paper of Pravesh Kothari and Jacob Steinhardt.

Before these recent works, the best polynomialtime algorithms for the clustering mixtures of Gaussians could not tolerate any (when a simple greedy algorithm can be shown to solve the clustering problem to high accuracy). On the other hand, known lower bounds show that when , clustering is impossible (even using exponential time) with samples, so one cannot hope to improve the guarantees of this theorem too much further [RegevVijayaraghavan]. (That said, reducing the sample complexity and running time to when is a fascinating open problem.)
Variants of this theorem, which may be found in all three of the sources listed, offer algorithms which additionally output estimates of the means , work for many distributions besides Gaussians (without even knowing the underlying distribution!), and tolerate some amount of advesarial corruption among the samples . We note also that the theorems in those works handle the usual mixtures of Gaussians problem, rather than the equidistributed version, and can tolerate nonuniform mixtures; i.e. those where some clusters are much smaller than others.
On the (Im)possiblity of intelligence explosion
(In this post I am following the venerable tradition of bloggers opining about matters on which they don’t really know much about. I hope I learn something from the feedback –Boaz).
Nothing is impossible,
Child, nothing is impossible.
Every bridge is crossable.
Every tooth is flossable.
Every win is lossable.
Every worker’s bossable.
Every cookie’s tossable.
Every yak’s a lhasa bull.
Nothing is impossible,
Child, nothing is impossible.Okay, teacher, can you name something that ISN’T possible?
No, Child. Nothing is impossible.
So, there IS something that’s impossible. Naming something that’s impossible is impossible.
(From “The Teacher and The Child”by Chris Harris)
In this world where reasoned arguments and respect for facts seem increasigly rare, some people are actually worried about the opposite problem of “intelligence explosion”.
Recently, through a blog post of Scott Aaronson, I came across this essay by François Chollet. Given Scott’s less than raving review, I fully expected not to like it, but actually found myself agreeing with some parts of this essay (though not all, and in particular not with the title).
The basic fear of “intelligence explosion” is that:
 Once we develop sufficiently advanced artificial intelligence, it will go on to use this intelligence to build better and better AI, quickly leaving us behind.
 The AI will develop some form of consciousness and rather than using their intelligence to make our lives better, will be about as kind to us as we were to the Neanderthals.
Consciousness is a hard concept to define. Humans used to attribute consciousness to the weather, praying to the sun and sea gods. After all it made perfect sense, the weather is unpredictable and dangerous, and seemed to vary in capricious ways. As we have grown to understand weather better, we no longer think that it is conscious. Yes, there is still an element of unpredictability and randomness to it, but we do understand the basic mechanisms at play, and can place some probabilities or bounds on its behavior. So these days the weather is stochastic rather than adversarial.
Arthur C. Clarke famously said that “Any sufficiently advanced technology is indistinguishable from magic.”. Similarly, one can say that any system that is sufficiently adversarial is indistinguishable from being conscious.
If we follow this definition, then we have already created conscious machines, since we can definitely already create technologies that we understand so poorly that we cannot model it in any way other than adversarial. In some sense this is the underlying lesson of results such as the Halting problem and NP completeness. Moreover, ever since the Atom bomb, mankind’s potential to damage the planet and ourselves has gone far beyond what nature can do (and of course, as witnessed by global warming, nuclear energy is not the only technology that can affect the whole planet). Also, as anyone getting “on the air updates” for their gadgets can attest to, we already have systems that continuously improve over time, often with a feedback loop. With more and more of the world’s economy becoming dependent on the transfer of information as opposed to goods (which of course is somewhat of an artificial distinction), the speed of progress has become much faster. So, if the question is whether we should worry about us developing and deploying technology whose behavior we can’t completely predict, and one that could result in very bad consequences, then I am with the alarmists.
What I find less appealing about the “AI risk” position is the focus on notions such as “intelligence” and “conciousness”. There is already an algorithm outperforming most humans on IQ tests and surely soon there will be an algorithm with an IQ of 300, or whatever the maximum possible value is. However, as Chollet points out, while some individual humans have had profound influence on the course of humanity, it is typically not intelligence alone that helped them (see e.g. the rather sad story of William James Sidis). That said, one can’t dispute that in the 200K years we’ve been around, Homo Sapiens have managed to make some significant progress, and so if you could simulate a population of even average humans, but do it with more people and larger speed, you’d speed up scientific discovery. Indeed (and this is where I part ways with Chollet) scientific progress has been accelerating, precisely because we use scientific progress to make more progress, whether it’s computer simulations helping in doing physics or quantum physics helping us build new computers, and so on and so forth. We are likely to continue to progress at an accelerating pace, not by trying to simulate a population of average or genius humans, but rather by continuously applying our tools and understanding to build better tools and improve our understanding.
But all of the above does not mean that modelling computation and communication systems as a new species and anthropomorphizing them is helpful. Research can and should be done on trying to verify that the behavior of computing systems does not deviate from certain parameters, whether it is Windows 10 or an AI algorithm.
With the progress of time computers are likely to continue to do more and more tasks currently associated with human intelligence, and yes, we do have a nontrivial chance of creating a technology that may eventually destroy us. But I don’t see why thinking of algorithms in anthropomorphic terms is helpful any more than thinking of the weather in terms of deities. If anything, understanding human “intelligence” and “consciousness” in more algorithmic ways seems like a better path forward.
HALG 2018 Call for Nominations
[Guest post by Robi Krauthgamer; note that there is no conflict in nominating the same work/person to be highlighted in both HALG and TheoryFest. –Boaz]
Call for Nominations
3rd Highlights of Algorithms conference (HALG 2018)
Amsterdam, June 46, 2018
http://2018.highlightsofalgorithms.org/
The HALG 2018 conference seeks highquality nominations for invited talks that will highlight recent advances in algorithmic research. Similarly to previous years, there are two categories of invited talks:
A. survey (60 minutes): a survey of an algorithmic topic that has seen exciting developments in last couple of years.
B. paper (30 minutes): a significant algorithmic result appearing in a paper in 2017 or later.
To nominate, please email halg2018.nominations@gmail.com the following information:
1. Basic details: speaker name + topic (for survey talk) or paper’s title, authors, conference/arxiv + preferable speaker (for paper talk).
2. Brief justification: Focus on the benefits to the audience, e.g., quality of results, importance/relevance of topic, clarity of talk, speaker’s presentation skills. Pay attention to potentially nonobvious information, e.g., the topic might seem out of scope, or the material seems inadequate for one talk.
All nominations will be reviewed by the Program Committee (PC) to select speakers that will be invited to the conference.
Nominations deadline: December 12, 2017 (for full consideration).
Please keep in mind that the conference does not provide financial support for the speakers.
Best regards,
Robert Krauthgamer,
HALG 2018 PC chair.
The GOP Tax plan and universities
In his State of the Union address in January 1984, president Ronald Reagan announced that he directed his treasury secretary to simplify and reform the U.S., tax code. Thus began a process of 1.5 years until in June 1985, the house Ways and Means committee began formal discussion on the bill, which it voted on November 1985, and after a yearlong process in Congress, the bill was signed into law by president Reagan on October 1986.
In contrast, the Republican party is currently “desperate for a win” and is trying to move a massive tax reform involving about 8 trillion dollars (cutting about 5 trillion dollars of taxes and partially paying for by increasing about 3.5 trillion dollars in other taxes) in a very short period of time.
When such huge decisions are done in haste, it’s likely to cause “collateral damage”. In particular, universities and academic research, which have been a major engine of growth in the U.S. economy, have been targeted by this ostensibly “pro growth” tax plan as a way to finance its cuts in other places. There are several provisions in it that are particularly harmful to universities, including taxing endowments, eliminating student loan interest deductions, and considering graduate student tuition waivers as taxable income.
As Luca says, if you are a U.S. citizen, and particularly if you have a Republican congressional representative, please contact him or her and make your voice heard.
Teaching models of computation
(This blog post is in the form of a Jupyter notebook. See here for an arguably better formatted version, and here for the version with the omitted code, this (Beta version) website allows you to see the code “live” without needing to install Jupyter on your machine.)