Sum-of-squares proofs and the quest toward optimal algorithms

Introduction

A central mission of theoretical computer science is to understand which computational problems can be solved efficiently, which ones cannot, and what it is about a problem that makes it easy or hard. To illustrate these kind of questions, let us consider the following parameters of an undirected $d$-regular graph An undirected $d$-regular graph $G=(V,E)$ consists of a set of vertices $V$, which we sometimes identify with the set $[n]=\{1,\ldots,n\}$ for some integer $n$, and a set of edges $E$, which are $2$-element subsets of $V$, such that every vertex is part of exactly $d$ edges. The assumption that $G$ is regular is not important and made chiefly for notational simplicity. For vertex sets $S,T\subseteq V$, we let $E(S,T)$ denote the set of edges $\{s,t\}\in E$ with $s\in S$ and $t\in T$. $G=(V,E)$:

The smallest connected component of $G$ is the size of the smallest non-empty set $S\subseteq V$ such that $E(S,V\setminus S)=\emptyset$.

The independent-set number of $G$ is the size of the largest set $S\subseteq V$ such that $E(S,S)=\emptyset$.

The (edge) expansion The expansion of a graph is closely related to other quantities, known as isoperimetric constant, conductance or sparsest cut. These quantities are not identical but are the same up to scaling and a multiplicative factor of at most $2$. Hence, they are computationally equivalent for our purposes. We also remark that expansion is often not normalized by the degree. However for our purposes this normalization is useful. of $G$, denoted $\phi_{G}$, is the minimum expansion $\phi_{G}(S)$ of a vertex set $S\subseteq V$ with size $1\leq\lvert S\rvert\leq\lvert V\rvert/2$, where

The expansion $\phi_{G}(S)$ measures the probability that a step of the random walk on $G$ leaves $S$ conditioned on starting in $S$.

All these parameters capture different notions of well-connectedness of the graph $G$. Computing these can be very useful in many of the settings in which we use graphs to model data, whether it is communication links between servers, social connections between people, genes that are co-expressed together, or transitions between states of a system.

The computational complexity of the first two parameters is fairly well understood. The smallest connected component is easy to compute in time linear in the number $n=|V|$ of vertices by using, for example, breadth-first search from every vertex in the graph. The independent-set number is $\mathbf{NP}$-hard to compute, which means that, assuming the widely believed conjecture that $\mathbf{P}\neq\mathbf{NP}$, it cannot be computed in time polynomial in $n$. In fact, under stronger (but still widely believed) quantitative versions of the $\mathbf{P}\neq\mathbf{NP}$ conjecture, for every $k$ it is infeasible to decide whether or not the maximum independent set is larger than $k$ in time $n^{o(k)}$ [DF95, CHKX06] and hence we cannot significantly beat the trivial $O(n^{k})$-time algorithm for this problem. Similarly, while we can approximate the independent-set number trivially within a factor of $n$, assuming such conjectures, there is no polynomial-time algorithm to approximate it within a factor of $n^{1-\varepsilon(n)}$ where $\varepsilon(n)$ is some function tending to zero as $n$ grows [Hås96, Kho01].

So, connectivity is an easy problem and independent set a hard one, but what about expansion? Here the situation is more complicated. We know that we can’t efficiently compute $\phi_{G}$ exactly, and we can’t even get an arbitrarily good approximation [AMS11], but we actually do have efficient algorithms with non-trivial approximation guarantees for $\phi_{G}$. Discrete versions of Cheeger’s inequality [Che70, Dod84, AM85, Alo86] yield such an estimate, namely

where $\lambda_{2}(G)$ denotes the (efficiently computable) second largest eigenvalue of the $G$’s adjacency matrix.The adjacency matrix of a graph $G$ is the $|V|\times|V|$ matrix $A$ with $0/1$ entries such that $A_{u,v}=1$ iff $\{u,v\}\in E$. In particular, we can use (1) to efficiently distinguish between graphs with $\phi_{G}$ close to and graphs with $\phi_{G}$ bounded away from . But can we do better? For example, could we efficiently compute a quantity $c_{G}$ such that $c_{G}\leq\phi_{G}\leq O(c_{G}^{0.51})$? We simply don’t know.As we will mention later, there are algorithms to approximate $\phi_{G}$ up to factors depending on the number $n$ of vertices, which give better guarantees than (1) for graphs where $\phi_{G}$ is sufficiently small as a function of $n$.

This is not an isolated example, but a pattern that keeps repeating. Over the years, computer scientists have developed sophisticated tools to come up with algorithms on one hand, and hardness proofs showing the limits of efficient algorithms on the other hand. But those two rarely match up. Moreover, the cases where we do have tight hardness results are typically in settings, such as the independent set problem, where there is no way to significantly beat the trivial algorithm. In contrast, for problems such as computing expansion, where we already know of an algorithm giving non-trivial guarantees, we typically have no proof that this algorithm is optimal. In other words, the following is a common theme:

If you already know an algorithm with non-trivial approximation guarantees for a problem, it’s very hard to rule out that cleverer algorithms couldn’t get even better guarantees.

In 2002, Subhash Khot formulated a conjecture, known as the Unique Games Conjecture (UGC) [Kho02]. A large body of follow up works has shown that this conjecture (whose description is deferred to Section 1.1 below) implies many hardness results that overcome the above challenge and match the best-known algorithms even in cases when they achieve non-trivial guarantees. In fact, beyond just resolving particular questions, this line of works obtained far-reaching complementary meta algorithmic and meta hardness results. By this we mean results that give an efficient meta algorithm $\mathcal{A}$ (i.e., an algorithm that can be applied to a family of problems, and not just a single one) that is optimal within a broad domain $\mathcal{C}$, in the sense that (assuming the UGC) there is no polynomial-time algorithm that performs better than $\mathcal{A}$ on any problem in $\mathcal{C}$. It is this aspect of the Unique Games Conjecture result that we find most exciting, and that shows promise of going beyond the current state where the individual algorithmic and hardness results form “isolated islands of knowledge surrounded by a sea of ignorance”Paraphrasing John Wheeler. into a more unified theory of complexity.

The meta-algorithm that the UGC predicts to be optimal is based on semidefinite programming and it uses this technique in a very particular and quite restricted way. (In many settings, this meta-algorithm can be implemented in near-linear time [Ste10].) We will refer to this algorithm as the UGC meta-algorithm. It can be viewed as a common generalization of several well known algorithms, including those that underlie Cheeger’s Inequality, Grothendieck’s Inequality [Gro53], the Goemans–Williamson Max Cut algorithm [GW95], and the Lovász $\vartheta$ function [Lov79]. As we’ve seen for the example of Cheeger’s Inequality, in many of those settings this meta-algorithm gives non-trivial approximation guarantees which are the best known, but there are no hardness results ruling out the existence of better algorithms. The works on the UGC has shown that this conjecture (and related ones) imply that this meta-algorithm is optimal for a vast number of problems, including all those examples above. For example, a beautiful result of Raghavendra [Rag08] showed that for every constraint-satisfaction problem (a large class of problems that includes many problems of interest such as Max $k$-SAT, $k$-Coloring, and Max-Cut), the UGC meta-algorithm gives the best estimate on the maximum possible fraction of constraints one can satisfy. Similarly, the UGC (or closely related variants) imply there are no efficient algorithms that give a better estimate for the sparsest cut of a graph than the one implied by Cheeger’s Inequality [RST12] and no better efficient estimate for the maximum correlation of a matrix with $\pm 1$-valued vectors than the one given by Grothendieck’s Inequality.See [RS09b] for the precise statement of Grothendieck’s Inequality and this result. Curiously, the UGC implies that Grothendieck’s Inequality yields the best efficient approximation factor for the correlation of a matrix with $\pm 1$-valued vectors even though we don’t actually know the numerical value of this factor (known as Grothendieck’s constant). To summarize:

If true, the Unique Games Conjecture tells us not only which problems in a large class are easy and which are hard, but also why this is the case. There is a single unifying reason, captured by a concrete meta-algorithm, that explains all the easy problem in this class. Moreover, in many cases where this meta-algorithm already gives non-trivial guarantees, the UGC implies that no further efficient improvements are possible.

All this means that the Unique Games Conjecture is certainly a very attractive proposition, but the big question still remains unanswered—is this conjecture actually true? While some initial results supported the UGC, more recent works, although still falling short of disproving the conjecture, have called it into question. In this survey we discuss the most promising current approach to refute the UGC, which is based on the Sum of Squares (SOS) method [Sho87, Nes00, Par00, Las01]. The SOS method could potentially refute the Unique Games Conjecture by beating the guarantees of the UGC meta-algorithm on problems on which the conjecture implies the latter’s optimality. This of course is interesting beyond the UGC, as it means we would be able to improve the known guarantees for many problems of interest. Alas, analyzing the guarantees of the SOS method is a very challenging problem, and we still have relatively few tools to do so. However, as we will see, we already know that at least in some contexts, the SOS method can yield better results than what was known before. The SOS method is itself a meta algorithm, so even if it turns out to refute the UGC, this does not mean we need to give up on the notion of explaining the complexity of wide swaths of problems via a single algorithm; we may just need to consider a different algorithm. To summarize, regardless of whether it refutes the UGC or not, understanding the power of the SOS method is an exciting research direction that could advance us further towards the goal of a unified understanding of computational complexity.

Instead of the Unique Games Conjecture, in this survey we focus on a related conjecture known as the Small-Set Expansion Hypothesis (SSEH) [RS10]. The SSEH implies the UGC [RS10], and while there is no known implication in the other direction, there are several results suggesting that these two conjectures are probably equivalent [RS10, RST10, RS09a, ABS10, BBH+12]. At any rate, most (though not all) of what we say in this survey applies equally well to both conjectures, but the SSEH is, at least in our minds, a somewhat more natural and simpler-to-state conjecture.

Recall that for a $d$-regular graph $G=(V,E)$ and a vertex set $S\subseteq V$, we defined its expansion as $\phi_{G}(S)=|E(S,V\setminus S)|/(d|S|)$. By Cheeger’s inequality (1), the second largest eigenvalue yields a non-trivial approximation for the minimum expansion $\phi_{G}=\min_{1\leq|S|\leq|V|/2}\phi_{G}(S)$, but it turns out that eigenvalues and similar methods do not work well for the problem of approximating the minimum expansion of smaller sets. The Small-Set Expansion Hypothesis conjectures that this problem is inherently difficult.

For every $\varepsilon>0$ there exists $\delta>0$ such that given any graph $G=(V,E)$, it is $\mathbf{NP}$-hard to distinguish between the case (i) that there exists a subset $S\subseteq V$ with $|S|=\delta|V|$ such that $\phi_{G}(S)\leq\varepsilon$ and the case (ii) that $\phi_{G}(S)\geq 1-\varepsilon$ for every $S$ with $|S|\leq\delta|V|$.

As mentioned above, the SSEH implies that (1) yields an optimal approximation for $\phi_{G}$. More formally, assuming the SSEH, there is some absolute constant $c>0$ such that for every $\phi\geq 0$, it is $\mathbf{NP}$-hard to distinguish between the case that a given graph $G$ satisfies $\phi_{G}\leq\phi$ and the case that $\phi_{G}\geq c\sqrt{\phi}$ [RST12]. Given that the SSEH conjectures the difficulty of approximating expansion, the reader might not be so impressed that it also implies the optimality of Cheeger’s Inequality. However, we should note that the SSEH merely conjectures that the problem becomes harder as $\delta$ becomes smaller, without postulating any quantitative relation between $\delta$ and $\varepsilon$, and so it is actually surprising (and requires a highly non-trivial proof) that it implies such quantitatively tight bounds. Even more surprising is that (through its connection with the UGC) the SSEH implies tight hardness result for a host of other problems, including every constraint satisfaction problem, Grothendieck’s problem, and many others, which a priori seem to have nothing to do with graph expansion.

While we will stick to the SSEH in this survey, for completeness we present here the definition of the Unique Games Conjecture. We will not use this definition in the proceeding and so the reader can feel free to skip this remark. The UGC can be thought of as a more structured variant of the SSEH where we restrict to graphs and sets that satisfy some particular properties. Because we restrict both the graphs and the sets, a priori it is not clear which of these conjectures should be stronger. However it turns out that the SSEH implies the UGC [RS10]. It is an open problem whether the two conjectures are equivalent, though the authors personally suspect that this is the case.

We say that an $n$-vertex graph $G=(V,E)$ is $\delta$-structured if there is a partition of $V$ into $\delta n$ sets $V_{1},\ldots,V_{\delta n}$ each of size $1/\delta$, such that for every $i\neq j$, either $E(V_{i},V_{j})=\emptyset$ or $E(V_{i},V_{j})$ is a matching (namely for every $u\in V_{i}$ there is exactly one $v\in V_{j}$ such that $\{u,v\}\in E$). We say a set $S\subseteq V$ is $\delta$-structured if $|S\cap V_{i}|=1$ for all $i$ (and so in particular, $|S|=\delta n$). The Unique Games Conjecture states that for every $\varepsilon>0$ there exists a $\delta>0$ such that it is $\mathbf{NP}$ hard, given a $\delta$-structured $G$, to distinguish between the case (i) that there exists a $\delta$-structured $S$ such that $\phi_{G}(S)\leq\varepsilon$ and the case (ii) that every $\delta$-structured $S$ satisfies $\phi_{G}(S)\geq 1-\varepsilon$. The conjecture can also be described in the form of so-called “two prover one round games” (hence its name); see Khot’s surveys [Kho10a, Kho10b].

2 Organization of this survey and further reading

In the rest of this survey we describe the Sum of squares algorithm, some of its applications, and its relation to the Unique Games and Small-Set Expansion Conjectures. We start by defining the Sum of Squares algorithm, and how it relates to classical questions such as Hilbert $17^{th}$ problem. We will demonstrate how the SOS algorithm is used, and its connection to the UGC/SSEH, by presenting Cheeger’s Inequality (1) as an instance of this algorithm. The SSEH implies that the SOS algorithm cannot yield better estimates to $\phi_{G}$ than those obtained by (1). While we do not know yet whether this is true or false, we present two different applications where the SOS does beat prior works— finding a planted sparse vector in a random subspace, and sparse coding— learning a set of vectors $A$ given samples of random sparse linear combinations of vectors in $A$. We then discuss some of the evidence for the UGC/SSEH, how this evidence is challenged by the SOS algorithm and the relation between the UGC/SSEH and the problem of (approximately) finding sparse vectors in arbitrary (not necessarily random) subspaces. Much of our discussion is based on the papers [ABS10, BGH+12, BBH+12, BKS14b, BKS14a]. See also [Bar12, Bar14b, Bar14a] for informal overviews of some of these issues.

For the reader interested in learning more about the Unique Games Conjecture, there are three excellent surveys on this topic. Khot’s CCC survey [Kho10b] gives a fairly comprehensive overview of the state of knowledge on the UGC circa 2010, while his ICM survey [Kho10a] focuses on some of the techniques and connections that arose in the works around the UGC. Trevisan [Tre12] gives a wonderfully accessible introduction to the UGC, using the Max-Cut problem as a running example to explain in detail the UGC’s connection to semidefinite programming. As a sign of how rapidly research in this area is progressing, this survey is almost entirely disjoint from [Kho10a, Kho10b, Tre12]. While the former surveys mostly described the implications of the UGC for obtaining very strong hardness and “meta hardness” results, the current manuscript is focused on the question of whether the UGC is actually true, and more generally understanding the power of the SOS algorithm to go beyond the basic LP and SDP relaxations.

Our description of the SOS algorithm barely scratches the surface of this fascinating topic, which has a great many applications that have nothing to do with the UGC or even approximation algorithms at large. The volume [BPT13] and the monograph [Lau09] are good sources for some of these topics. The SOS algorithm was developed in slightly different forms by several researchers, including Shor [Sho87], Nesterov [Nes00], Parrilo [Par00], and Lasserre [Las01]. It can be viewed as a strengthening of other “meta-algorithms” proposed by [SA90, LS91] (also known as linear and semi-definite programming hierarchies).See [Lau03] for a comparison. Our description of the SOS meta algorithm follows Parrilo’s, while the description of the dual algorithm follows Lasserre, although we use the pseudoexpectation notation introduced in [BBH+12] instead of Lasserre’s notion of “moment matrices”. The Positivstellensatz/SOS proof system was first studied by Grigoriev and Vorobjov [GV01] and Grigoriev [Gri01] proved some degree lower bounds for it, that were later rediscovered and expanded upon by [Sch08, Tul09]. All these are motivated by the works in real geometry related to Hilbert’s $17^{\text{th}}$ problem; see Reznick’s survey [Rez00] for more on this research area. One difference between our focus here and much of the other literature on the SOS algorithm is that we are content with proving that the algorithm supplies an approximation to the true quantity, rather than exact convergence, but on the other hand are much more stringent about using only very low degree (preferably constant or polylogarithmic in the number of variables).

Sums of Squares Proofs and Algorithms

One of the most common ways of proving that a quantity is non-negative is by expressing it as a Sum of Squares (SOS). For example, we can prove the Arithmetic-Mean Geometric-Mean inequality $ab\leq a^{2}/2+b^{2}/2$ by the identity $a^{2}+b^{2}-2ab=(a-b)^{2}$. Thus a natural question, raised in the late $19^{\text{th}}$ century, was whether any non-negative (possibly multivariate) polynomial can be written as a sum of squares of polynomials. This was answered negatively by Hilbert in 1888, who went on to ask as his $17^{\text{th}}$ problem whether any such polynomial can be written as a sum of squares of rational functions. A positive answer was given by Artin [Art27], and considerably strengthened by Krivine and Stengle. In particular, the following theorem is a corollary of their results, which captures much of the general case.

Let $P_{1},\ldots,P_{m}\in\mathds{R}[x]=\mathds{R}[x_{1},\ldots,x_{n}]$ be multivariate polynomials. Then, the system of polynomials equations $\mathcal{E}=\{P_{1}=0,\ldots,P_{m}=0\}$ has no solution over $\mathds{R}^{n}$ if and only if, there exists polynomials $Q_{1},\ldots,Q_{m}\in\mathds{R}[x]$ such that $S\in\mathds{R}[x]$ is a sum of squares of polynomials and

In the following lemma, we will prove a special case of Theorem 2.1, where the solution set of $\mathcal{E}$ is a subset of the hypercube $\{\pm 1\}^{n}$. Here, the degree of SOS refutations is bounded by $2n$. (This bound is not meaningful computationally because the size of degree-$\Omega(n)$ refutations is comparable to the number of points in $\{\pm 1\}^{n}$.)

Let $\mathcal{E}=\{P_{0}=0,x_{1}^{2}-1=0,\ldots,x_{n}^{2}-1=0\}$ for some $P_{0}\in\mathds{R}[x]$. Then, either the system $\mathcal{E}$ is satisfiable or it has a degree-$2n$ SOS refutation.

Suppose the system is not satisfiable, which means that $P_{0}(x)\neq 0$ for all $x\in\{\pm 1\}^{n}$. Since $\{\pm 1\}^{n}$ is a finite set, we may assume $P_{0}^{2}\geq 1$ over $\{\pm 1\}^{n}$. Now interpolate the real-valued function $\sqrt{P_{0}^{2}-1}$ on $\{\pm 1\}^{{}n}$ as a multilinear (and hence degree at most $n$) polynomial in $R\in\mathds{R}[x]$. Then, $P_{0}^{2}-1-R^{2}$ is a polynomial of degree at most $2n$ that vanishes over $\{\pm 1\}^{n}$. (Since we can replace $x_{i}^{2}$ by $1$ in any monomial, we can assume without loss of generality that $P_{0}$ is multilinear and hence has degree at most $n$.) This means that we can write $P_{0}^{2}-1-R^{2}$ in the form $\sum_{i=1}^{n}Q_{i}\cdot(x_{i}^{2}-1)$ for polynomials $Q_{i}$ with $Q_{i}\leq\deg 2n-2$. (This fact can be verified either directly or by using that $x_{1}^{2}-1,\ldots,x_{n}^{2}-1$ is a Gröbner basis for $\{\pm 1\}^{n}$.) Putting things together, we see that $-1=R^{2}+(-P_{0})\cdot P_{0}+\sum_{i=1}^{n}Q_{i}\cdot(x_{i}^{2}-1)$, which is a SOS refutation for $\mathcal{E}$ of the form in Theorem 2.1. ∎

The Sum of Squares algorithm is based on the following theorem, which was discovered in different forms by several researchers:

Theorem 2.3 yields the following meta algorithm that can be applied on any problem of the form

(We can assume degrees of SOS proofs to be even.) As we’ve seen in Lemma 2.2, for the typical domains we are interested in Computer Science, such as when the set of solutions of $\{P_{1}=0,\ldots,P_{m}=0\}$ is equal to $\{\pm 1\}^{n}$, this sequence is finite in the sense that $\varphi^{(2n)}=\min_{x\in\{\pm 1\}^{n}}P_{0}(x)$.

Another approach to optimize over non-linear problems such as (3) is to use local-search algorithms such as gradient descent that make local improvement steps, e.g., in the direction of the gradient, until a local optimum is reached. One difference between such local search algorithms and the SOS algorithm is that the latter sometimes succeeds in optimizing highly non-convex problems that have exponential number of local optima. As an illustration, consider the polynomial $P(x)=n^{4}\sum_{i=1}^{n}(x_{i}^{2}-x_{i})^{2}+(\sum_{i=1}^{n}x_{i})^{2}$.

Its unique global minimum is the point $x=0$, but it is not hard to see that it has an exponential number of local minima (for every $x\in\{0,1\}^{n}$, $P(x)<P(y)$ for every $y$ with $\|y-x\|\in[1/n,2/n]$, and so there must be a local minima in the ball of radius $1/n$ around $x$). Hence, gradient descent or other such algorithms are extremely likely to get stuck in one of these suboptimal local minima. However, since $P$ is in fact a sum of squares with constant term , the degree-$4$ SOS algorithm will output $P$’s correct global minimum value.

2 Pseudodistributions and pseudoexpectations

for some particular function $f$ (satisfying $f(\varphi)\geq\varphi$) which captures our approximation guarantee. (E.g., a factor $c$ approximation corresponds to the function $f(\varphi)=c\varphi$.)

Pseudodistributions are the dual object to SOS refutations, and hence the non-existence of a refutation implies the existence of a pseudodistribution.

We now elaborate on this, and explain both the definition and intuition behind pseudodistributions. In Section 3 we will give a concrete example, by showing how one can prove that degree-$2$ SOS proofs capture Cheeger’s Inequality using such an argument. Results such as the analysis of the Goemans-Williamson Max Cut algorithm [GW95], and the proof of Grothendieck’s Inequality [Gro53] can be derived using similar methods.

The term pseudoexpectation stems from the fact that for every distribution $\mathcal{D}$ over $\mathds{R}^{n}$, we can obtain such an operator by choosing $\mathcal{L}(P)=\operatorname{\mathds{E}}_{\mathcal{D}}P$ for all $P\in\mathds{R}[x]$. Moreover, the properties $\mathcal{L}(1)=1$ and $\mathcal{L}(P^{2})\geq 0$ turn out to capture to a surprising extent the properties of distributions and their expectations that we tend to use in proofs. Therefore, we will use a notation and terminology for such pseudoexpectation operators that parallels the notation we use for distributions. In fact, all of our notation can be understood by making the thought experiment that there exists a distribution as above and expressing all quantities in terms of low-degree moments of that distribution (so that they also make sense if we only have a pseudoexpectation operator that doesn’t necessarily correspond to a distribution).

The duality between SOS proofs and pseudoexpectations is expressed in the following theorem. We say that a system $\mathcal{E}$ of polynomial equations is explicitly bounded if there exists a linear combination of the constraints in $\mathcal{E}$ that has the form $\{\sum_{i}x_{i}^{2}+S=M\}$ for $M\in\mathds{R}$ and $S\in\mathds{R}[x]$ a sum-of-squares polynomial. (Note that in this case, every solution $x\in\mathds{R}^{n}$ of the system $\mathcal{E}$ satisfies $\sum_{i}x_{i}^{2}\leq M$.)

In many applications we will use the following dual form of the SOS algorithm:

Solve the problem pretending that $\{x\}$ is an actual distribution over solutions, and if all the steps you used have low-degree SOS proofs, the solution still works even when $\{x\}$ is a low-degree pseudodistribution.

It may seem that coming up with an algorithm for the actual distribution case is trivial, as any element in the support of the distribution would be a good solution. However note that even in the case of a real distribution, the algorithm does not get sampling access to the distribution, but only access to its low-degree moments. Depending on the reader’s temperament, the above description of the algorithm, which “pretends” pseudodistributions are real ones, may sound tautological or just wrong. Hopefully it will be clearer after the next two sections, where we use this approach to show how the SOS algorithm can match the guarantee of Cheeger’s Inequality for computing the expansion, to find planted sparse vectors in random subspaces, and to approximately recover sparsely used dictionaries.

Approximating expansion via sums of squares

There exists an absolute constant $c$ such that for every graph $G$

Before we prove Theorem 3.1, let us discuss its significance. Theorem 3.1 is essentially a restatement of Cheeger’s Inequality in the SOS language—the degree $2$-SOS algorithm is the UGC meta algorithm which is essentially the same as the algorithm based on the second-largest eigenvalue. The second-largest eigenvalue is directly related to the minimum value of $\varphi$ such that there exists a degree-$2$ pseudodistribution satisfying the more relaxed system $\{\sum_{\{ij\}\in E}(x_{i}-x_{j})^{2}=\varphi\cdot dn/2,\sum_{i}x_{i}=n/2,\sum_{i}x_{i}^{2}=n/2\}$. There are examples showing that (5) is tight, and so we cannot get better approximation using degree $2$ proofs. But can we get a better estimate using degree $4$ proofs? Or degree $\log n$ proofs? We don’t know the answer, but if the Small-Set Expansion Hypothesis is true, then beating the estimate (5) is $\mathbf{NP}$ -hard, which means (under standard assumptions) that to do so we will need to use proofs of degree at least $n^{\Omega(1)}$.

One such example comes from the beautiful work of Arora, Rao and Vazirani [ARV09] who showed that

which is better than the guarantee of Theorem 3.1 for $\phi_{G}\ll 1/\log n$. However, this is not known to contradict the SSEH or UGC, which apply to the case when $\phi_{G}$ is a small constant.

This proof is largely a reformulation of the standard proof of a discrete variant of Cheeger’s Inequality, phrased in the SOS language of pseudodistributions, and hence is included here mainly to help clarify these notions, and to introduce a tool— sampling from a distribution matching first two moments of a pseudodistribution— that will be useful for us later on. By the dual formulation, to prove Theorem 3.1 we need to show that given a pseudodistribution $\{x\}$ over characteristic vectors of size-$k$ sets $S$ of size $k\leq n/2$ with $|E(S,V\setminus S)|=\varphi dk$, we can find a particular set $S^{*}$ of size at most $n/2$ such that $E(S^{*},V\setminus S^{*})\leq O(\sqrt{\varphi})d|S^{*}|$. For simplicity, we consider the case $k=n/2$ (the other cases can be proven in a very similar way). The distribution $\{x\}$ satisfies the constraints $\{\sum x_{i}=n/2\}$, $\{x_{i}^{2}=x_{i}\}$ for all $i$, and $\{\sum_{\{i,j\}\in E}(x_{i}-x_{j})^{2}=\varphi d\sum_{i}x_{i}\}$. The algorithm to find $S^{*}$ is quite simple:

Output the set $S^{*}=\{i\mid y_{i}\geq 1/2\}$ (which corresponds to the 0/1 vector closest to $y$).

We remark that the set produces by the algorithm might have cardinality larger than $n/2$, in which case we will take the complement of $S^{*}$.

We will first give a constructive proof the well-known fact that for every distribution over $\mathds{R}^{n}$, there exists an $n$-dimensional Gaussian distribution with the same quadratic moments. Given the moments of a distribution $\{x\}$ over $\mathds{R}^{n}$, we can sample a Gaussian distribution $\{y\}$ matching the first two moments of $\{x\}$ as follows. First, we can assume $\operatorname{\mathds{E}}x_{i}=0$ for all $i$ by shifting variables if necessary. Next, let $v^{1},\ldots,v^{n}$ and $\lambda_{1},\ldots,\lambda_{n}$ be the eigenvectors and eigenvalues of the matrix $M_{i,j}=\operatorname{\mathds{E}}x_{i}x_{j}$. (Note that $M$ is positive semidefinite and so $\lambda_{1},\ldots,\lambda_{n}\geq 0$.) Choose i.i.d random standard Gaussian variables $w_{1},\ldots,w_{n}$ and define $y=\sum_{k}\sqrt{\lambda_{k}}w_{k}v^{k}$. Since $\operatorname{\mathds{E}}w_{k}w_{k^{\prime}}$ equals $1$ if $k=k^{\prime}$ and equals otherwise,

Analyzing the algorithm.

The analysis is based on the following two claims: (i) the set $S^{*}$ satisfies $n/3\leq\lvert S^{*}\rvert\leq 2n/3$ with constant probability and (ii) in expectation $|E(S^{*},V\setminus S^{*})|\leq O(\sqrt{\varphi}dn)$.

We will focus on two extreme cases that capture the heart of the arguments for the claims. In the first case, all variables $y_{i}$ have very small variance so that $\operatorname{\mathds{E}}y_{i}^{2}\approx(\operatorname{\mathds{E}}y_{i})^{2}$. In this case, because our constraints imply that $\operatorname{\mathds{E}}y_{i}^{2}=\operatorname{\mathds{E}}y_{i}$, every variable satisfies either $\operatorname{\mathds{E}}y_{i}^{2}\approx 0$ or $\operatorname{\mathds{E}}y_{i}^{2}\approx 1$, which means that the distribution of the set $S^{*}$ produced by the algorithm is concentrated around a particular set, and it is easy to verify that this set satisfies the two claims. In the second, more interesting case, all variables $y_{i}$ have large variance, which means $\operatorname{\mathds{E}}y_{i}^{2}=1/2$ in our setting.

Machine learning with Sum of Squares

In this section, we illustrate the computational power of the sum-of-squares method with applications to two basic problems in unsupervised learning. In these problems, we are given samples of an unknown distribution from a fixed, parametrized family of distributions and the goal is to recover the unknown parameters from these samples. Despite the average-case nature of these problems, most of the analysis in these applications will be for deterministic problems about polynomials that are interesting in their own right.

The first problem is sparse vector recovery. Here, we are given a random basis of a $d$-dimensional linear subspace $U\subseteq\mathds{R}^{n}$ of the form

where $\cramped{x^{\scriptscriptstyle(0)}}$ is a sparse vector and $\cramped{x^{\scriptscriptstyle(1)}},\ldots,\cramped{x^{\scriptscriptstyle(d)}}$ are independent standard Gaussian vectors. The goal is to reconstruct the vector $\cramped{x^{\scriptscriptstyle(0)}}$. This is a natural problem in its own right, and is also a useful subroutine in various settings; see [DH13]. Demanet and Hand [DH13] gave an algorithm (based on [SWW12]) that recovers $\cramped{x^{\scriptscriptstyle(0)}}$ by searching for the vector $x$ in $U$ that maximizes $\|x\|_{\infty}/\|x\|_{1}$ (which can be done efficiently by $n$ linear programs). It is not hard to show that $\cramped{x^{\scriptscriptstyle(0)}}$ has to have less than $|n|/\sqrt{d}$ coordinates for it to be maximize this ratio,See Lemma 5.2 below for a related statement. and hence this was a limitation of prior techniques. In contrast, as long as $d$ is not too large (namely, $d=O(\sqrt{n})$), the SOS method can recover $\cramped{x^{\scriptscriptstyle(0)}}$ as long as it has less than $\varepsilon n$ coordinates for some constant $\varepsilon>0$ [BKS14b].

The second problem we consider is sparse dictionary learning, also known as sparse coding. Here, we are given independent samples $\cramped{y^{\scriptscriptstyle(1)}},\ldots,\cramped{y^{\scriptscriptstyle(R)}}\in\mathds{R}^{n}$ from an unknown distribution of the form $\{y=Ax\}$, where $A\in\mathds{R}^{n\times m}$ is a matrix and $x$ is a random $m$-dimensional vector from a distribution over sparse vectors. This problem, initiated by the work Olshausen and Field [OF96] in computational neuroscience, has found a variety of uses in machine learning, computer vision, and image processing (see, e.g. [AAJ+13] and the references therein). The appeal of this problem is that intuitively data should be sparse in the “right” representation (where every coordinate corresponds to a meaningful feature), and finding this representation can be a useful first step for further processing, just as representing sound or image data in the Fourier or Wavelet bases is often a very useful primitive. While there are many heuristics use to solve this problem, prior works giving rigorous recovery guarantees such as [SWW12, AAJ+13, AGM13] all required the vector $x$ to be very sparse, namely less than $\sqrt{n}$ nonzero entries.If the distribution $x$ consists of $m$ independent random variables then better guarantees can be achieved using Independent Component Analysis (ICA) [Com94]. See [GVX14] for the current state of art in this setting. However we are interested here in the more general case. In contrast, the SOS method can be used to approximately recover the dictionary matrix $A$ as long as $x$ has $o(n)$ nonzero (or more generally, significant) entries [BKS14a].

Our algorithm will follow the general recipe we described in Section 2.2:

Find a system of polynomial equations $\mathcal{E}$ that captures the intended solution $\cramped{x^{\scriptscriptstyle(0)}}$, then pretend you are given a distribution $\{u\}$ over solutions of $\mathcal{E}$ and show how you could recover a single solution $u^{*}$ from the low order moments of $\{u\}$.

Specifically, we come up with a system $\mathcal{E}$ so that desired vector $\cramped{x^{\scriptscriptstyle(0)}}$ satisfies all equations, and it is essentially the only solution to $\mathcal{E}$. Then, using the SOS algorithm, we compute a degree-$4$ pseudodistribution $\{u\}$ that satisfies $\mathcal{E}$. Finally, as in Section 3.1, we sample a vector $u^{*}$ from a Gaussian distribution that has the same quadratic moments as the pseudodistribution $\{u\}$.

Why does the sum-of-squares method work?

The analysis of algorithm has two ingredients. The first ingredient is a structural property about projectors of random subspaces.

Let $U^{\prime}\subseteq\mathds{R}^{n}$ be a random $d$-dimensional subspace with $d\ll\sqrt{n}$ and let $P^{\prime}$ be the projector into $U^{\prime}$. Then, with high probability, the following sum-of-squares relation over $\mathds{R}[u]$ holds for $\mu^{\prime}\geq\Omega(1)\cdot\lVert\mathds{1}\rVert_{2}^{2}$,

We can write $P^{\prime}=B^{\top}B$ where $B$ is a $d\times n$ matrix whose rows are an orthogonal basis for the subspace $U^{\prime}$. Therefore, $P^{\prime}u=B^{\top}x$ where $x=Bu$, and so to prove Lemma 4.2 it suffices to show that under these conditions, $\|B^{\top}x\|_{4}^{4}\preccurlyeq O(\|x\|_{2}^{4}/\|\mathds{1}\|_{2}^{4})$. The matrix $B^{\top}$ will be very close to having random independent Gaussian entries, and hence, up to scaling, $\|B^{\top}x\|_{4}^{4}$ will be (up to scaling), close to $Q(x)=\tfrac{1}{n}\sum\langle w_{i},x\rangle^{4}$ where $w_{1},\ldots,w_{d}\in\mathds{R}^{d}$ are chosen independently at random from the standard Gaussian distribution. The expectation of $\langle w,x\rangle^{4}$ is equal $3\sum_{i,j}x_{i}^{2}x_{j}^{2}=3\|x\|_{2}^{4}$. Therefore, to prove the lemma, we need to show that for $n\gg d^{2}$, the polynomial $Q(x)$ is with high probability close to its expectation, in the sense that the $d^{2}\times d^{2}$ matrix corresponding to $Q$’s coefficients is close to its expectation in the spectral norm. This follows from standard matrix concentration inequalities, see [BBH+12, Theorem 7.1The reference is for the arxiv version arXiv:1205.4484v2 of the paper.]). ∎

The following lemma is the second ingredient of the analysis of the algorithm.

Note that the conclusion of Lemma 4.3 implies that a vector $u^{*}$ sampled from a Gaussian distribution with the same quadratic moments as the computed pseudodistribution also satisfies $\operatorname{\mathds{E}}_{u^{*}}\lVert P^{\prime}u^{*}\rVert_{2}^{2}\leq 4(\mu/\mu^{\prime})^{1/4}$ and $\operatorname{\mathds{E}}\lVert u^{\ast}\rVert_{2}^{2}=1$. By Markov inequality, $\lVert u^{*}-\cramped{x^{\scriptscriptstyle(0)}}\rVert_{2}^{2}\leq 16(\mu/\mu^{\prime})^{1/4}$ holds with probability at least $3/4$. Since $u^{\ast}$ is Gaussian, it satisfies $\lVert u^{\ast}\rVert_{2}^{2}\geq 1/4$ with probability at least $1/2$. If both events occur, which happens with probability at least $1/4$, then $\langle u^{\ast},\cramped{x^{\scriptscriptstyle(0)}}\rangle^{2}\geq(1-O(\mu/\mu^{\prime}))\lVert u^{\ast}\rVert_{2}^{2}$, thus establishing Theorem 4.1.

Proof of Lemma 4.3

There are many ways in which pseudodistributions behave like actual distributions, as far as low degree polynomials are concerned. To prove Lemma 4.3, we need to establish the following two such results:

Suppose $a$ and $b$ are nonnegative integers that sum to a power of $2$. Then, every degree-$(a+b)$ pseudodistribution $\{u,v\}$ satisfies

Let $\{u,v\}$ be a degree-$4$ pseudodistribution. Then,

2 Sparse dictionary learning

A $\kappa$-overcomplete dictionary is a matrix $A\in\mathds{R}^{n\times m}$ with $\kappa=m/n\geq 1$ and isotropic unit vectors as columns (so that $\lVert A^{\top}u\rVert_{2}^{2}=\kappa\lVert u\rVert_{2}^{2}$). We say a distribution $\{x\}$ over $\mathds{R}^{m}$ is $(d,\tau)$-nice if it satisfies $\operatorname{\mathds{E}}_{i}x_{i}^{d}=1$ and $\operatorname{\mathds{E}}_{i}x_{i}^{d/2}x_{j}^{d/2}\leq\tau$ for all $i\neq j\in[m]$, and it satisfies that non-square monomial degree-$d$ moments vanish so that $\operatorname{\mathds{E}}x^{\alpha}=0$ for all non-square degree-$d$ monomials $x^{\alpha}$, where $x^{\alpha}=\prod x_{i}^{\alpha_{i}}$ for $\alpha\in\mathds{Z}^{n}$. For $d=O(1)$ and $\tau=o(1)$, a nice distribution satisfies that $\operatorname{\mathds{E}}\tfrac{1}{m}\sum_{i}x_{i}^{4}\gg\left(\tfrac{1}{m}\sum_{i}x_{i}^{2}\right)^{2}$ which means that it is approximately sparse in the sense that the square of the entries of $x$ has large variance (which means that few of the entries have very big magnitude compared to the rest).

For every $\varepsilon>0$ and $\kappa\geq 1$, there exists $d$ and $\tau$ and a quasipolynomial-time algorithm algorithm for sparse dictionary learning with the following guarantees: Suppose the input consists of $n^{O(1)}$ independent samplesHere, we also make the mild assumption that the degree-$2d$ moments of $x$ are bounded by $n^{O(1)}$. from a distribution $\{y=Ax\}$ over $\mathds{R}^{n}$, where $A\in\mathds{R}^{n\times m}$ is a $\kappa$-overcomplete dictionary and the distribution $\{x\}$ over $\mathds{R}^{m}$ is $(d,\tau)$-nice. Then, with high probability, the algorithm outputs a set of vectors with Hausdorff distance The Hausdorff distance between two sets of vectors upper bounds the maximum distance of a point in one of the sets to its closest point in the other set. Due to the innate symmetry of the sparse dictionary problem (replacing a column $\cramped{a^{\scriptscriptstyle(i)}}$ of $A$ by $-\cramped{a^{\scriptscriptstyle(i)}}$ might not affect the input distribution), we measure the Hausdorff distance after symmetrizing the sets, i.e., replacing the set $S$ by $S\cup-S$. at most $\varepsilon$ from the set of columns of $A$.

Let $\cramped{y^{\scriptscriptstyle(1)}},\ldots,\cramped{y^{\scriptscriptstyle(R)}}$ be independent samples from the distribution $\{y=Ax\}$. Then, we consider the polynomial $P=\tfrac{1}{R}\sum_{i}\langle\cramped{y^{\scriptscriptstyle(i)}},u\rangle^{d}\in\mathds{R}[u]_{d}$. Using the properties of nice distributions, a direct computation shows that with high probability $P$ satisfies the relation

(Here, we are omitting some constant factors, depending on $d$, that are not important for the following discussion.) It follows that $P(\cramped{a^{\scriptscriptstyle(i)}})=1\pm\tau$ for every column $\cramped{a^{\scriptscriptstyle(i)}}$ of $A$. It’s also not hard to show that every unit vector $a^{\ast}$ with $P(a^{\ast})\approx 1$ is close to one of the columns of $A$. (Indeed, every unit vector satisfies $P(a^{\ast})\leq\max_{i}\langle\cramped{a^{\scriptscriptstyle(i)}},a^{\ast}\rangle^{d-2}\kappa+\tau$. Therefore, $P(a^{\ast})\approx 1$ implies that $\langle\cramped{a^{\scriptscriptstyle(i)}},a^{\ast}\rangle^{2}\geq\kappa^{-\Omega(1/d)}$, which is close to $1$ for $d\gg\log\kappa$.) What we will show is that pseudodistributions of degree $O(\log n)$ allow us to find all such vectors.

Why does the sum-of-squares method work?

In the following, $\varepsilon>0$ and $\kappa\geq 1$ are arbitrary constants that determine constants $d=d(\varepsilon,\kappa)\geq 1$ and $\tau=\tau(\varepsilon,\kappa)>0$ (as in the theorem).

Let $P\in\mathds{R}[u]$ be a degree-$d$ polynomial with $\pm(P-\lVert A^{\top}u\rVert_{d}^{d})\preccurlyeq\tau\lVert u\rVert_{2}^{d}$ for some $\kappa$-overcomplete dictionary $A$. Let $\mathcal{D}$ be a degree-$O(\log n)$ pseudodistribution that satisfies the constraints $\{\lVert u\rVert_{2}^{2}=1\}$ and $\{P(u)=1-\tau\}$. Let $W\in\mathds{R}[u]$ be a product of $O(\log n)$ random linear formsHere, a random linear form means a polynomial $\langle u,v\rangle\in\mathds{R}[u]$ where $v$ is a random unit vector in $\mathds{R}^{n}$.. Then, with probability at least $n^{-O(1)}$ over the choice of $W$, there exists a column $\cramped{a^{\scriptscriptstyle(i)}}$ of $A$ such that

Lemma 4.7 allows us to reconstruct one of the columns of $A$. Using similar ideas, we can iterate this argument and recover one-by-one all columns of $A$. We omit the proof of Lemma 4.7, but the idea behind it is to first give an SOS proof version of our argument above that maximizers of $P$ must be close to one of the $a^{(i)}$’s. We then note that if a distribution $\mathcal{D}$ is supported (up to noise) on at most $m$ different vectors, then we can essentially isolate one of these vectors by re-weighing $\mathcal{D}$ using the product of the squares of $O(\log m)$ random linear forms.

It turns out, this latter argument has a low degree SOS proof as well, which means that in our case that given $\mathcal{D}$ satisfying the constraint $\{P(u)=1-\tau\}$, we can isolate one of the $\cramped{a^{\scriptscriptstyle(i)}}$’s even when $\mathcal{D}$ is not an actual distribution but merely a pseudodistribution.

Hypercontractive norms and small-set expansion

So far we have discussed the Small-Set Expansion Hypothesis and the Sum of Squares algorithm. We now discuss how these two notions are related. One connection, mentioned before, is that the SSEH predicts that in many settings the guarantees of the degree-$2$ SOS algorithm are best possible, and so in particular it means that going from degree $2$ to say degree $100$ should not give any substantial improvement in terms of guarantees. Another, perhaps more meaningful connection is that there is a candidate approach for refuting the SSEH using the SOS algorithm. At the heart of this approach is the following observation:

The small-set expansion problem is a special case of the problem of finding “sparse” vectors in a linear subspace.

This may seem strange, as a priori, the following two problem seem completely unrelated: (i) Given a graph $G=(V,E)$, find a “small” subset $S\subseteq V$ with low expansion $\phi_{G}(S)$, and (ii) Given a subspace $W\subseteq\mathds{R}^{n}$, find a “sparse” vector in $W$. The former is a combinatorial problem on graphs, and the latter a geometric problem on subspaces. However, for the right notions of “small” and “sparse”, these turn out to be essentially the same problem. Intuitively, the reason is the following: the expansion of a set $S$ is proportional to the quantity $x^{\top}Lx$ where $x$ is the characteristic vector of $S$ (i.e. $x_{i}$ equals $1$ if $i\in S$ and equals otherwise), and $L$ is the Laplacian matrix of $G$ (defined as $L=I-d^{-1}A$ where $I$ is the identity, $d$ is the degree, and $A$ is $G$’s adjacency matrix). Let $v_{1},\ldots,v_{n}$ be the eigenvectors of $L$ and $\lambda_{1},\ldots,\lambda_{n}$ the corresponding eigenvalues. Then $x^{\top}Lx=\sum_{i=1}^{n}\lambda_{i}\langle v_{i},x\rangle^{2}.$

Concretely, for $p>1$ and $\delta\in(0,1)$, we say that a vector $x\in\mathds{R}^{n}$ is $(\delta,p)$-sparse if $\operatorname{\mathds{E}}_{i}x_{i}^{2p}\geq\delta^{1-p}(\operatorname{\mathds{E}}_{i}x_{i}^{2})^{p}$. Note that a characteristic vector of a set of measure $\delta$ is $(\delta,p)$-sparse for any $p$. The relation between small-set-expansion and finding sparse vectors in a subspace is captured by the following theorem:

Let $G=(V,E)$ be a $d$-regular graph with Laplacian $L$. Then for every $p\geq 2$ and $\varphi\in(0,1)$,

(Non-expanding small sets imply sparse vectors.) If there exists $S\subseteq V$ with $|S|=o(|V|)$ and $\phi_{G}(S)\leq\varphi$ then there exists an $(o(1),p)$-sparse vector $x\in W_{\leq\varphi+o(1)}$ where for every $\lambda$, $W_{\leq\lambda}$ denotes the span of the eigenvectors of $L$ with eigenvalue smaller than $\lambda$.

(Sparse vectors imply non-expanding small sets.) If there exists a $(o(1),p)$-sparse vector $x\in W_{\leq\varphi}$, then there exists $S\subseteq V$ with $|S|=o(|V|)$ and $\phi_{G}(S)\leq\rho$ for some constant $\rho<1$ depending on $\varphi$.

The first direction of Theorem 5.1 follows from the above reasoning, and was known before the work of [BBH+12]. The second direction is harder, and we omit the proof here. The theorem reduces the question of determining whether there for small sets $S$, the minimum of $\phi_{G}(S)$ is close to one or close to zero, into the question of bounding the maximum of $\operatorname{\mathds{E}}_{i}x_{i}^{2p}$ over all unit vectors in some subspace. The latter question is a polynomial optimization problem of the type the SOS algorithm is designed for! Thus, we see that we could potentially resolve the SSEH if we could answer the following question:

What is the degree of SOS proofs needed to certify that the $2p$-norm is bounded for all (Euclidean norm) unit vectors in some subspace $W$?

We still don’t know the answer to this question in full generality, but we do have some interesting special cases. Lemma 4.2 of Section 4.1 implies that if $W$ is a random subspace of dimension $\ll\sqrt{n}$ then we can certify that $\operatorname{\mathds{E}}_{i}x_{i}^{4}\leq O(\operatorname{\mathds{E}}_{i}x_{i}^{2})^{2}$ for all $x\in W$ via a degree-$4$ SOS proof. This is optimal, as the $4$-norm simply won’t be bounded for dimensions larger than $\sqrt{n}$:

Let $W\subseteq\mathds{R}^{n}$ have dimension $d$ and $p\geq 2$, then there exists a unit vector $x\in W$ such that

Hence in particular any subspace of dimension $d\gg n^{1/p}$ contains a $(o(1),p)$-sparse vector.

Therefore, by the inequality $(\sum a_{i})/(\sum b_{i})\leq\max a_{i}/b_{i}$, there exists an $i$ such that if we let $x=x^{i}$ then $x_{i}^{2}\geq\tfrac{d}{n}\sum_{j}x_{j}^{2}=d\operatorname{\mathds{E}}x_{j}^{2}.$ Hence, just the contribution of the $i^{th}$ coordinate to the expectation achieves $\operatorname{\mathds{E}}_{j}x_{j}^{2p}\geq\tfrac{d^{p}}{n}\left(\operatorname{\mathds{E}}_{j}x_{j}^{2}\right)^{p}.$ ∎

Lemma 5.2 implies the following corollary:

Let $p,n\in\mathds{N}$, and $W$ be subspace of $\mathds{R}^{n}$. If $\operatorname{\mathds{E}}_{i}x_{i}^{2p}\leq O(\operatorname{\mathds{E}}_{i}x_{i}^{2})^{p})$, then there is an $O(n^{1/p})$-degree SOS proof for this fact. (The constants in the $O(\cdot)$ notation can depend on $p$ but not on $n$.)

By Lemma 5.2, the condition implies that $d=\dim W\leq O(n^{1/p})$, and it is known that approximately bounding a degree-$O(1)$ polynomial on the $d$-dimensional sphere requires an SOS proof of at most $O(d)$ degree (e.g., see [DW12] and the references therein). ∎

Combining Corollary 5.3 with Theorem 5.1 implies that for every $\varepsilon,\delta$ there exists some $\tau$ (tending to zero with $\varepsilon$), such that if we want to distinguish between the case that an $n$-vertex graph $G$ satisfies $\phi_{G}(S)\leq\varepsilon$ for every $|S|\leq\delta n$, and the case that there exists some $S$ of size at most $\delta n$ with $\phi_{G}(S)\geq 1-\varepsilon$, then we can do so using a degree $n^{\tau}$ SOS proofs, and hence in $\exp(O(n^{\tau}))$ time. This is much better than the trivial $\binom{n}{\delta n}$ time algorithm that enumerates all possible sets. Similar ideas can be used to achieve an algorithm with a similar running time for the problem underlying the Unique Games Conjecture [ABS10]. If these algorithms could be improved so the exponent $\tau$ tends to zero with $n$ for a fixed $\varepsilon$, this would essentially refute the SSEH and UGC.

Thus, the question is whether Corollary 5.3 is the best we could do. As we’ve seen, Lemma 4.2 shows that for random subspaces we can do much better, namely certify the bound with a constant degree proof. Two other results are known of that flavor. Barak, Kelner and Steurer [BKS14b] showed that if a $d$-dimensional subspace $W$ does not contain a $(\delta,2)$-sparse vector, then there is an $O(1)$-degree SOS proof that it does not contain (or even almost contains) a vector with $O(\tfrac{\delta n}{d^{1/3}})$ nonzero coordinates. If the dependence on $d$ could be eliminated (even at a significant cost to the degree), then this would also refute the SSEH. Barak, Brandão, Harrow, Kelner, Steurer and Zhou [BBH+12] gave an $O(1)$-degree SOS proof for the so-called “Bonami-Beckner-Gross $(2,4)$ hypercontractivity theorem“ (see [O’D14, Chap. 9]). This is the statement that for every constant $k$, the subspace $W_{k}\subseteq\mathds{R}^{2^{t}}$ containing the evaluations of all degree $\leq k$ polynomials on the points $\{\pm 1\}^{t}$ does not contain an $(o(1),2)$-sparse vector, and specifically satisfies for all $x\in W_{k}$,

On its own this might not seem so impressive, as this is just one particular subspace. However, this particular subspace underlies much of the evidence that has been offered so far in support of both the UGC and SSEH conjectures. The main evidence for the UGC/SSEH consists of several papers such as [KV05, KS09, RS09a, BGH+12] that verified the predictions of these conjectures by proving that various natural algorithms indeed fail to solve some of the computational problems that are hard if the conjectures are true. These results all have the form of coming up with a “hard instance” $G$ on which some algorithm $\mathcal{A}$ fails, and so to prove such a result one needs to do two things: (i) compute (or bound) the true value of the parameter on $G$, and (ii) show that the value that $\mathcal{A}$ outputs on $G$ is (sufficiently) different than this true value. It turns out that all of these papers, the proof of (i) can be formulated as low degree SOS proof, and in fact the heart of these proofs is the bound (6). Therefore, the results of [BBH+12] showed that all these “hard instances” can in fact be solved by the SOS algorithm using a constant degree. This means that at the moment, we don’t even have any example of an instance for the problems underlying the SSEH and UGC that can be reasonably conjectured (let alone proved) hard for the constant degree SOS algorithm. This does not mean that such instances do not exist, but is suggestive that we have not yet seen the last algorithmic word on this question.

We thank Amir Ali Ahmadi for providing us with references on the diverse applications of the SOS method.

References