Rounding Sum-of-Squares Relaxations

Introduction

One of the reasons for this paucity of positive results is that we have relatively few tools to round such convex hierarchies. A rounding algorithm maps a solution to the relaxation to a solution to the original program. While the name derives from the prototypical case of relaxing an integer program to a linear program by allowing the variables to take non-integer values, we use “rounding algorithm” for any mapping from relaxation solutions to actual solutions, even in cases where the actual solutions are themselves non-integer. In the case of a hierarchy, the relaxation solution satisfies more constraints, but we do not always know how to take advantage of this when rounding. For example, [ARV04] used a very sophisticated analysis to get better rounding when the solution to a Sparsest Cut relaxation satisfies a constraint known as triangle inequalities, but we have no general tools to use the additional constraints that come from higher levels of the hierarchies, nor do we know if these can help in rounding or not. This lack of rounding techniques is particularly true for the Sum of Squares (SOS, also known as Lasserre) hierarchy [Par00, Las01]. While it is common in the TCS community to use Lasserre to describe the primal version of this SDP, and Sum of Squares (SOS) to describe the dual, in this paper we use the more descriptive SOS name for both programs. We note that in all the applications we consider, strong duality holds, and so these programs are equivalent. This is the strongest variant of the canonical semidefinite programming hierarchies, and has recently shown promise to achieve tasks beyond the reach of weaker hierarchies [BBH+12]. But there are essentially no general rounding tools that take full advantage of its power. The closest general tool we are aware of is the repeated conditioning methods of [BRS11, GS11], though these can be implemented in weaker hierarchies too and so do not seem to use the full power of the SOS hierarchy. However, this technique does play a role in this work as well.

In this work we propose a general approach to rounding SOS hierarchies, and instantiate this approach in two cases, giving new algorithms making progress on natural variants of two longstanding problems. Our approach is based on the intimate connection between the SOS hierarchy and the “Positivstellensatz”/“Sum of Squares” proof system. This connection was used in previous work for either negative results [Gri01b, Gri01a, Sch08], or positive results for specific instances [BBH+12, OZ13, KOTZ14], translating proofs of a bound on the actual value of these instances into proofs of bounds on the relaxation value. In contrast, we use this connection to give explicit rounding algorithms for general instances of certain computational problems.

Our work uses the Sum of Squares (SOS) semidefinite programming hierarchy and in particular its relationship with the Sum of Squares (or Positivstellensatz) proof system. We now briefly review both the hierarchy and proof system. See the introduction of [OZ13] and the monograph [Lau09] for a more in depth discussion of these concepts and their history. Underlying both the SDP and proof system is the natural approach to prove that a real polynomial $P$ is nonnegative via showing that it equals a sum of squares: $P=\sum_{i=1}^{k}Q_{i}^{2}$ for some polynomials $Q_{1},\ldots,Q_{k}$. The question of when a nonnegative polynomial has such a “certificate of non-negativity” was studied by Hilbert who realized this doesn’t always hold and asked (as his $17{th}$ problem) whether a nonnegative polynomial is always a sum of squares of rational functions. This was proven to be the case by Artin, and also follows from the more general Positivstellensatz (or “Positive Locus Theorem”) [Kri64, Ste74].

The Positivstellensatz/SOS proof system of Grigoriev and Vorobjov [GV01] is based on the Positivstellensatz as a way to refute the assertion that a certain set of polynomial equations

can be satisfied by showing that there exists some polynomials $Q_{1},\ldots,Q_{k}$ and a sum of squares polynomial $S$ such that

([GV01] considered inequalities as well, although in our context one can always restrict to equalities without loss of generality.) One natural measure for the complexity of such proof is the degree of the polynomials $P_{1}Q_{1},\ldots,P_{k}Q_{k}$ and $S$.

The sum of squares semidefinite program was proposed independently by several authors [Sho87, Par00, Nes00, Las01] One way to describe it is as follows. If the set of equalities (1.1) is satisfiable then in particular there exists some random variable $X$ over $\varmathbb R^{n}$ such that

That is, $X$ is some distribution over the non-empty set of solutions to (1.1).

If $P$ is the constant polynomial $1$ then $\mathcal{L}P=1$

Until recently, this relation was mostly used for negative results, translating proof complexity lower bounds into integrality gap results for the SOS hierarchy [BBH+12, OZ13, KOTZ14]. However, in 2012 Barak, Brandão, Harrow, Kelner, Steurer and Zhou [BBH+12] used this relation for positive results, showing that the SOS hierarchy can in fact solve some interesting instances of the Unique Games maximization problem that fool weaker hierarchies. Their idea was to use the analysis of the previous works that proved these integrality gaps for weaker hierarchies. Such proofs work by showing that (a) the weaker hierarchy outputs a large value on this particular instance but (b) the true value is actually small. [BBH+12]’s insight was that oftentimes the proof of (b) only uses arguments that can be captured by the SOS/Positivstellensatz proof system, and hence inadvertently shows that the SOS SDP value is actually small as well. Some follow up works [OZ13, KOTZ14] extended this to other instances, but all these results held for very specific instances which have been proven before to have small objective value.

While the SOS hierarchy is relevant to many algorithmic applications, some recent work focused on its relation to Khot’s Unique Games Conjecture (UGC) [Kho02]. On a high level, the UGC implies that the basic semidefinite program is an optimal efficient algorithm for many problems, and hence in particular using additional constant or polylogarithmic levels of the SOS hierarchy will not help. More concretely, as discussed in Section 1.3 below, the UGC is closely related to the question of how hard it is to find sparse (or “analytically sparse”) vectors in a given subspace. Our work shows how the SOS hierarchy can be useful in general, and in particular gives strong average-case results and nontrivial worst-case results for finding sparse vectors in subspaces. Therefore, it can be considered as giving some (far from conclusive) evidence that the UGC might be false.

2 Optimizing polynomials with nonnegative coefficients bounded spectral norm

Our first result yields an additive approximation to this optimization problem for polynomials with nonnegative coefficients, when the value is scaled by the spectral norm of an associated matrix. If $P$ is an $n$-variate degree-$t$ homogeneous polynomial with nonnegative coefficient, then it can be represented by a tensor $M\in\varmathbb R^{n^{t}}$ such that $P(x)=M\cdot x^{\otimes t}$ for every $x\in\varmathbb R^{n}$. It is convenient to state our result in terms of this tensor representation:

There is an algorithm $A$, based on $O(t\log n/\varepsilon^{2})$ levels of the SOS hierarchy, such that for every even The algorithm easily generalizes to polynomials of odd degree $t$ and to non-homogenous polynomials, see Remark 3.5. $t$ and nonnegative $M\in\varmathbb R^{n^{t}}$,

where $\cdot$ denotes the standard dot product, and $\lVert M\rVert_{spectral}$ denotes the spectral norm of $M$, when considered as an $n^{t/2}\times n^{t/2}$ matrix.

Note that the algorithm of Theorem 1.2 only uses a logarithmic number of levels, and thus it shows that this fairly natural polynomial optimization problem can be solved in quasipolynomial time, as opposed to the exponential time needed for optimizing over general polynomials of degree $>2$. Indeed, previous work on the convergence of the Lasserre hierarchy for general polynomials [DW12] can be described in our language here as trying to isolate a solution in the support of the distribution, and this generally requires a linear number of levels. Obtaining the logarithmic bound here relies crucially on constructing a “combined” solution that is not necessarily in the support. The algorithm is also relatively simple, and so serves as a good demonstration of our general approach.

or to simply distinguish between the case that this quantity is at least $\varepsilon$ and the case that $\rho$ is separable. The best result known in this area is the paper [BCY11] mentioned above, which solved the distinguishing variant of quantum separability problem in the case that measurements are restricted to so-called Local Operations and one-way classical communication (one-way LOCC) operators. However, they did not have an rounding algorithm, and in particular did not solve the problem of actually finding a separable state that maximizes the probability of acceptance of a given one-way LOCC measurement. The techniques of this work were used by Brandão and Harrow [BH13] to solve the latter problem, and also greatly simplify the proof of [BCY11]’s result, which originally involved relations between several measures of entanglement proved in several papers.The paper [BH13] was based on a previous version of this work [BKS12] that contained only the results for nonnegative tensors.

Relation to small set expansion. Nonnegative tensors also arise naturally in some applications, and in particular in the setting of small set expansion for Cayley graphs over the cube, which was our original motivation to study them. In particular, one corollary of our result is:

We discuss the derivation and the meaning of this corollary in Section 6 but note that the condition of having small value $K(G)$ seems reasonable. Having $K(G)=O(1)$ implies that the graph is a small set expander, and in particular the known natural examples of Cayley graphs that are small set expanders, such as the noisy Boolean hypercube and the “short code” graph of [BGH+12] have $K(G)=O(1)$. Thus a priori one might have thought that a graph that is hard to distinguish from small set expanders would have a small value of $K(G)$.

3 Optimizing hypercontractive norms and finding analytically sparse vectors

Finding a sparse nonzero vector inside a $d$ dimensional linear subspace $V\subseteq\varmathbb R^{n}$ is a natural task arising in many applications in machine learning and optimization (e.g., see [DH13] and the references therein). Related problems are known under many names including the “sparse null space”, “dictionary learning”, “blind source separation”, “min unsatisfy”, and “certifying restricted isometry property” problems. (These problems all have the same general flavor but differ on various details such as worst-case vs. average case, affine vs. linear subspaces, finding a single vector vs. a basis, and more.) Problems of this type are often NP-hard, with some hardness of approximation results known, and conjectured average-case hardness (e.g., see [ABSS97, KZ12, GN10] and the references therein).

We consider a natural relaxation of this problem, which we call the analytically sparse vector problem (ASVP), which assumes the input subspace (almost) contains an actually sparse $0/1$ vector, but allows the algorithm to find a vector $v\in V$ that is only “analytically sparse” in the sense that $\lVert v\rVert_{4}/\lVert v\rVert_{2}$ is large. More formally, for $q>p$ and $\mu>0$, we say that a vector $v$ is $\mu$ $L_{q}/L_{p}$-sparse if $(\operatorname*{\varmathbb{E}}_{i}v_{i}^{q})^{1/q}/(E_{i}v_{i}^{p})^{1/p}\geqslant\mu^{1/q-1/p}$. That is, a vector is $\mu$ $L_{q}/L_{p}$-sparse if it has the same $q$-norm vs $p$-norm ratio as a $0/1$ vector of measure at most $\mu$.

This is a natural relaxation, and similar conditions have been considered in the past. For example, Spielman, Wang, and Wright [SWW12] used in their work on dictionary learning a subroutine finds a vector $v$ in a subspace that maximizes the ratio $\lVert v\rVert_{\infty}/\lVert v\rVert_{1}$ (which can be done efficiently via $n$ linear programs). However, because any subspace of dimension $d$ contains an $O(1/\sqrt{d})$ $L_{\infty}/L_{1}$-sparse vector, this relaxation can only detect the existence of vectors that are supported on less than $O(n/\sqrt{d})$ coordinates. Some works have observed that the $L_{2}/L_{1}$ ratio is a much better proxy for sparsity [ZP01, DH13], but computing it is a non-convex optimization problem for which no efficient algorithm is known. Similarly, the $L_{4}/L_{2}$ ratio is a good proxy for sparsity for subspaces of small dimension (say $d=O(\sqrt{n})$) but it is non-convex, and it is not known how to efficiently optimize it. It seems that what makes our relaxation different from the original problem is not so much the qualitative issue of considering analytically sparse vectors as opposed to actually sparse vectors, but the particular choice of the $L_{4}/L_{2}$ ratio, which on one hand seems easier (even if not truly easy) to optimize over than the $L_{2}/L_{1}$ ratio, but provides better guarantees than the $L_{\infty}/L_{1}$ ratio. However, this choice does force us to restrict our attention to subspaces of low dimension, while in some applications such as certifying the restricted isometry property, the subspace in question is often the kernel of a “short and fat” matrix, and hence is almost full dimensional. Nonetheless, we believe it should be possible to extend our results to handle subspaces of higher dimension, perhaps at the some mild cost in the number of rounds.

Nevertheless, because $\lVert v\rVert_{4}^{4}$ is a degree $4$ polynomial, the problem of maximizing it for $v\in V$ of unit norm amounts to a polynomial maximization problem over the sphere, that has a natural SOS program. Indeed, [BBH+12] showed that this program does in fact yield a good approximation of this ratio for random subspaces. As we show in Section 5, we can use this to improve upon the results of [DH13] and find planted sparse vectors in random subspaces that are of not too large a dimension:

In particular, we note that this recovers a planted vector with up to $\Omega(n)$ nonzero coordinates when $d\leqslant\sqrt{n}$, and it can recover vectors with more than the $O(n/\sqrt{d})$ nonzero coordinates that are necessary for existing techniques whenever $d\ll n^{2/3}$.

Perhaps more significantly, we prove the following nontrivial worst-case bound for this problem:

There is a polynomial-time algorithm $A$, based on $O(1)$ levels of the SOS hierarchy, that on input a $d$-dimensional subspace $V\subseteq\varmathbb R^{n}$ such that there is a $0/1$-vector $v\in V$ with at most $\mu n$ nonzero coordinates, $A(V)$ outputs an $O(\mu d^{1/3})$ $L_{4}/L_{2}$-sparse vector in $V$.

Moreover, this holds even if $v$ is not completely inside $V$ but only satisfies $\lVert\Pi_{V}v\rVert_{2}^{2}\geqslant(1-\varepsilon)\lVert v\rVert_{2}^{2}$, for some absolute constant $\varepsilon>0$, where $\Pi_{V}$ is the projector to $V$.

The condition that the vector is $0/1$ can be significantly relaxed, see Remark 4.12. Theorem 4.1 is also motivated by the Small Set Expansion problem. The current best known algorithms for Small Set Expansion and Unique Games [ABS10] reduce these problems into the task of finding a sparse vector in a subspace, and then find this vector using brute force enumeration. This enumeration is the main bottleneck in improving the algorithms’ performance. This is the only step that takes super-polynomial time in [ABS10]’s algorithm for Small Set Expansion. Their algorithm for Unique Games has an additional divide and conquer step that takes subexponential time, but, in our opinion, seems less inherently necessary. Thus we conjecture that if the sparse-vector finding step could be sped up then it would be possible to speed up the algorithm for both problems. [BBH+12] showed that, at least for the Small Set Expansion question, finding an $L_{4}/L_{2}$ analytically sparse vector would be good enough. Using their work we obtain the following corollary of Theorem 1.5:

There is an algorithm that given an $n$-vertex graph $G$ that contains a set $S$ of size $o(n/d^{1/3})$ with expansion at most $\varepsilon$, outputs a set $S^{\prime}$ of measure $\delta=o(1)$ with expansion bounded away from $1$, i.e., $\Phi(S)\leqslant 1-\Omega(1)$, where $d$ is the dimension of the eigenspace of $G$’s random walk matrix corresponding to eigenvalues larger than $1-O(\varepsilon)$.

The derivation and meaning of this result is discussed in Section 6. We note that this is the first result that gives an approximation of this type to the small set expansion in terms of the dimension of the top eigenspace, as opposed to an approximation that is polynomial in the number of vertices.

4 Related work

Our paper follows the work of [BBH+12], that used the language of pseudoexpectation to argue that the SOS hierarchy can solve specific interesting instances of Unique Games, and perhaps more importantly, how it is often possible to almost mechanically “lift” arguments about actual distributions to the more general setting of pseudodistribution. In this work we show how the same general approach be used to obtain positive results for general instances.

The fact that LP/SDP solutions can be viewed as expectations of distributions is well known, and several rounding algorithms can be considered as trying to “reverse engineer” a relaxation solution to get a good distribution over actual solutions.

Techniques such as randomized rounding, the hyperplane rounding of [GW95], and the rounding for TSP [GSS11, AKS12] can all be viewed in this way. One way to summarize the conceptual difference between our techniques and those approaches is that these previous algorithms often considered the relaxation solution as giving moments of an actual distribution on “fake” solutions. For example, in [GW95]’s Max Cut algorithm, where actual solutions are modeled as vectors in $\{\pm 1\}^{n}$, the SDP solution is treated as the moment matrix of a Gaussian distribution over real vectors that are not necessarily $\pm 1$-valued. Similarly in the TSP setting one often considers the LP solution to yield moments of a distribution over spanning trees that are not necessarily TSP tours. In contrast, in our setting we view the solution as providing moments of a “fake” distribution on actual solutions.

Treating solutions explicitly as “fake distributions” is prevalent in the literature on negative results (i.e., integrality gaps) for LP/SDP hierarchies. For hierarchies weaker than SOS, the notion of “fake” is different, and means that there is a collection of local distributions, one for every small subset of the variables, that are consistent with one another but do not necessarily correspond to any global distribution. Fake distributions are also used in some positive results for hierarchies, such as [BRS11, GS11], but we make this more explicit, and, crucially, make much heavier use of the tools afforded by the Sum of Squares relaxation.

The notion of a “combining algorithm” is related to the notion of polymorphisms [BJK05] in the study of constraint satisfaction problems. A polymorphism is a way to combine a number of satisfying assignments of a CSP into a different satisfying assignments, and some relations between polymorphism, their generalization to approximation problems, rounding SDP’s are known (e.g., see the talk [Rag10]). The main difference is polymorphisms operate on each bit of the assignment independently, while we consider here combining algorithms that can be very global.

In a follow up (yet unpublished) work, we used the techniques of this paper to obtain improved results for the sparse dictionary learning problem, recovering a set of vectors $x_{1},\ldots,x_{m}\in\varmathbb R^{n}$ from random samples of $\mu$-sparse linear combinations of them for any $\mu=o(1)$, improving upon previous results that required $\mu\ll 1/\sqrt{n}$ [SWW12, AGM13, AAJ+13].

5 Organization of this paper

In Section 2 we give a high level overview of our general approach, as well as proof sketches for (special cases of) our main results. Section 3 contains the proof of Theorem 1.2— a quasipolynomial time algorithm to optimize polynomials with nonnegative coefficients over the sphere. Section 4 contains the proof of Theorem 1.5— a polynomial time algorithm for an $O(d^{1/3})$-approximation of the “analytical sparsest vector in a subspace” problem. In Section 5 we show how to use the notion of analytical sparsity to solve the question of finding a “planted” sparse vector in a random subspace. Section 6 contains the proofs of Corollaries 1.3 and 1.6 of our results to the small set expansion problem. Appendix A contains certain technical lemmas showing that pseudoexpectation operators obey certain inequalities that are true for actual expectations. Appendix C contains a short proof (written in classical notation, and specialized to the real symmetric setting) of [BCY11, BH13]’s result that the SOS hierarchy yields a good approximation to the acceptance probability of QMA(2) verifiers / measurement operators that have bounded one-way LOCC norm. Appendix B shows a simpler algorithm for the case that the verifier satisfies the stronger condition of a bounded $L2$ (Frobenius) norm. For the sake of completeness, Appendix D reproduces the proof from [BBH+12] of the relation between hypercontractive norms and small set expansion. Our papers raises many more questions than it answers, and some discussion of those appears in Section 7.

6 Notation

We will use linear subspaces of the form $V=R^{\mathcal{U}}$ where $\mathcal{U}$ is a finite set with an associated measure $\mu:\mathcal{U}\rightarrow[0,\infty]$. The $p$-norm of a vector $v\in V$ is defined as $\lVert v\rVert_{p}=\left(\sum_{\omega\in\mathcal{U}}\mu(\omega)|v_{\omega}|^{p}\right)^{1/p}$. Similarly, the inner product of $v,w\in V$ is defined as $\langle u,v\rangle=\sum_{\omega\in\mathcal{U}}\mu(\omega)u_{\omega}v_{\omega}$. We will only use two measures in this work: the counting measure, where $\mu(\omega)=1$ for every $\omega\in\mathcal{U}$, and the uniform measure, where $\mu(\omega)=1/|\mathcal{U}|$ for all $\omega\in\mathcal{U}$. (The norms corresponding to this measure are often known as the expectation norms.)

We will use vector notation (i.e., letters such as $u,v$, and indexing of the form $u_{i}$) for elements of subspaces with the counting measure, and function notation (i.e., letters such as $f,g$ and indexing of the form $f(x)$) for elements of subspaces with the uniform measure. The dot product notation $u\cdot v$ will be used exclusively for the inner product with the counting measure.

Pseudoexpectations

(In the context of optimization, to enforce the inequality constraint $Q(x)\geqslant 0$, it is always possible to add an auxiliary variable $y$ and then enforce the equality constraint $Q(x)-y^{2}\equiv 0$.) Appendix A contains several useful facts about pseudoexpectations.

Overview of our techniques

Traditionally to design a mathematical-programming based approximation algorithm for some optimization problem $O$, one first decides what the relaxation is— i.e., whether it is a linear program, semidefinite program, or some other convex program, and what constraints to put in. Then, to demonstrate that the value of the program is not too far from the actual value, one designs a rounding algorithm that maps a solution of the convex program into a solution of the original problem of approximately the same value. Our approach is conceptually different— we design the rounding algorithm first, analyze it, and only then come up with the relaxation.

Initially, this does not seem to make much sense— how can you design an algorithm to round solutions of a relaxation when you don’t know what the relaxation is? We do this by considering an idealized version of a rounding algorithm which we call a combining algorithm. Below we discuss this in more detail but roughly speaking, a combining algorithm maps a distribution over actual solutions of $O$ into a single solution (that may or may not be part of the support of this distribution). This is a potentially much easier task than rounding relaxation solutions, and every rounding algorithm yields a combining algorithm. In the other direction, every combining algorithm yields a rounding algorithm for some convex programming relaxation, but in general that relaxation could be of exponential size. Nevertheless, we show that in several interesting cases, it is possible to transform a combining algorithm into a rounding algorithm for a not too large relaxation that we can efficiently optimize over, thus obtaining a feasible approximation algorithm. The main tool we use for that is the Sum of Squares proof system, which allows to lift certain arguments from the realm of combining algorithms to the realm of rounding algorithms.

We now explain more precisely the general approach, and then give an overview of how we use this approach for our two applications— finding “analytically sparse” vectors in subspaces, and optimizing polynomials with nonnegative coefficients over the sphere.

Consider a general optimization problem of minimizing some objective function in some set $S$, such as the $n$ dimensional Boolean hypercube or the unit sphere. A convex relaxation for this problem consists of an embedding that maps elements in $S$ into elements in some convex domain, and a suitable way to generalize the objective function to a convex function on this domain. For example, in linear programming relaxations we typically embed $\{0,1\}^{n}$ into the set $^{n}$, while in semidefinite programming relaxations we might embed $\{0,1\}^{n}$ into the set of $n\times n$ positive semidefinite matrices using the map $x\mapsto X$ where $X_{i,j}=x_{i}x_{k}$. Given this embedding, we can use convex programming to find the element in the convex domain that maximizes the objective, and then use a rounding algorithm to map this element back into the domain $S$ in a way that approximately preserves the objective value.

A combining algorithm $C$ takes as input a distribution $\mathcal{X}$ over solutions in $S$ and maps it into a single element $C(\mathcal{X})$ of $S$, such that the objective value of $C(\mathcal{X})$ is approximately close to the expected objective value of a random element in $\mathcal{X}$. Every rounding algorithm $R$ yields a combining algorithm $C$. The reason is that if there is some embedding $f$ mapping elements in $S$ into some convex domain $T$, then for every distribution $\mathcal{X}$ over $S$, we can define $y_{\mathcal{X}}$ to be $\operatorname*{\varmathbb{E}}_{x\in\mathcal{X}}f(x)$. By convexity, $y_{\mathcal{X}}$ will be in $T$ and its objective value will be at most the average objective value of an element in $\mathcal{X}$. Thus if we define $C(\mathcal{X})$ to output $R(y_{\mathcal{X}})$ then $C$ will be a combining algorithm with approximation guarantees at least as good as $R$’s.

We now turn to giving a high level overview of our results. For the sake of presentations, we focus on certain special cases of these two applications, and even for these cases omit many of the proof details and only provide rough sketches of the proofs. The full details can be found in Sections 5, 4 and 3.

We consider the following natural problem, which was also studied by Demanet and Hand [DH13]. Let $f_{0}\in\varmathbb R^{\mathcal{U}}$ be a sparse function over some universe $\mathcal{U}$ of size $n$. That is, $f_{0}$ is supported on at most $\mu n$ coordinates for some $\mu=o(1)$. Let $V$ be the subspace spanned by $f_{0}$ and $d$ random (say Gaussian) functions $f_{1},\ldots,f_{d}\in\varmathbb R^{\mathcal{U}}$. Can we recover $f_{0}$ from any basis for $V$?

Demanet and Hand showed that if $\mu$ is very small, specifically $\mu\ll 1/\sqrt{d}$, then $f_{0}$ would be the most $L_{\infty}/L_{1}$-sparse function in $V$, and hence (as mentioned above) can be recovered efficiently by running $n$ linear programs. The SOS framework yields a natural and easy to describe algorithm for recovering $f_{0}$ as long as $\mu$ is a sufficiently small constant and the dimension $d$ is at most $O(\sqrt{n})$. The algorithm uses the SOS program for finding the most $L_{4}/L_{2}$-sparse function in $V$, which, as mentioned above, is simply the polynomial optimization problem of maximizing $\lVert f\rVert_{4}^{4}$ over $f$ in the intersection of $V$ and the unit Euclidean sphere.

for some constant $C$. Therefore using triangle inequality, and using the fact that $\lVert f^{\prime}\rVert_{2}\leqslant\lVert f\rVert_{2}=1$, it must hold that

In particular this implies that if we apply a singular value decomposition (SVD) to the second moment matrix $D$ of $\mathcal{D}$ (i.e., $D=\operatorname*{\varmathbb{E}}_{f\in\mathcal{D}}f^{\otimes 2}$) then the top eigenvector will have $1-o(1)$ correlation with $f_{0}$, and hence we can simply output it as our solution.

To make this combining algorithm into a rounding algorithm we use the result of [BBH+12] that showed that (2.1) can actually be proven via a sum of squares argument. Namely they showed that there is a degree $4$ sum of squares polynomial $S$ such that

(2.4) implies that even if $\mathcal{D}$ is merely a pseudodistribution then it must satisfy (2.1). (When the latter is raised to the fourth power to make it a polynomial inequality.) We can then essentially follow the argument, proving a version of (2.2) raised to the $4^{\text{th}}$ power by appealing to the fact that pseudodistributions satisfy Hölder’s inequality, (Corollary A.11) and hence deriving that $\mathcal{D}$ will satisfy (2.3), with possibly slightly worse constants, even when it is only a pseudodistribution.

In Section 5, we make this precise and extend the argument to obtain nontrivial (but weaker) guarantees when $d\geqslant\sqrt{n}$. We then show how to use an additional correction step to recover the original function $f_{0}$ up to arbitrary accuracy, thus boosting our approximation of $f_{0}$ into an essentially exact one.

2 Finding “analytically sparse” vectors in general subspaces

We now outline the ideas behind the proof of Theorem 4.1— finding analytically sparse vectors in general (as opposed to random) subspaces. This is a much more challenging setting than random subspaces, and indeed our algorithm and its analysis is more complicated (though still only uses a constant number of SOS levels), and at the moment, the approximation guarantee we can prove is quantitatively weaker. This is the most technically involved result in this paper, and so the reader may want to skip ahead to Section 2.3 where we give an overview of the simpler result of optimizing over polynomials with nonnegative coefficients.

We consider the special case of Theorem 4.1 where we try to distinguish between a YES case where there is a $0/1$ valued $o(d^{-1/3})$-sparse function that is completely contained in the input subspace, and a NO case where every function in the subspace has its four norm bounded by a constant times its two norm. That is, we suppose that we are given some subspace $V\subseteq\varmathbb R^{\mathcal{U}}$ of dimension $d$ and a distribution $\mathcal{D}$ over functions $f:\mathcal{U}\rightarrow\{0,1\}$ in $V$ such that $\operatorname*{\varmathbb{P}}_{\omega\in\mathcal{U}}[f(\omega)=1]=\mu$ for every $f$ in the support of $\mathcal{D}$, and $\mu=o(d^{-1/3})$. The goal of our combining algorithm to output some function $g\in V$ such that $\lVert g\rVert_{4}^{4}=\operatorname*{\varmathbb{E}}_{\omega}g(\omega)^{4}\gg(\operatorname*{\varmathbb{E}}_{\omega}g(\omega)^{2})^{2}=\lVert g\rVert_{2}^{4}$. (Once again, we use the expectation inner product and norms, with uniform measure over $\mathcal{U}$.)

Since the $f$’s correspond to sets of measure $\mu$, we would expect the inner product $\langle f,f^{\prime}\rangle$ of a typical pair $f,f^{\prime}$ (which equals the measure of the intersection of the corresponding sets) to be roughly $\mu^{2}$. Indeed, one can show that if the average inner product $\langle f,f^{\prime}\rangle$ is $\omega(\mu^{2})$ then it’s easy to find such a desired function $g$. Intuitively, this is because in this case the distribution $\mathcal{D}$ of sets does not have an equal chance to contain all the elements in $\mathcal{U}$, but rather there is some set $I$ of $o(|\mathcal{U}|)$ coordinates which is favored by $\mathcal{D}$. Roughly speaking, that would mean that a random linear combination $g$ of these functions would have most of its mass concentrated inside this small set $I$, and hence satisfy $\lVert g\rVert_{4}\gg\lVert g\rVert_{2}$. But it turns out that letting $g$ be a random gaussian function matching the first two moments of $\mathcal{D}$ is equivalent to taking such a random linear combination, and so our combining algorithm can obtain this $g$ using moment information alone.

Our combining algorithm will also try all $n$ coordinate projection functions. That is, let $\delta_{\omega}$ be the function such that $\delta_{\omega}(\omega^{\prime})$ equals $n=|\mathcal{U}|$ if $\omega=\omega^{\prime}$ and equals otherwise, (and hence under our expectation inner product $f(\omega)=\langle f,\delta_{\omega}\rangle$). The algorithms will try all functions of the form $\Pi\delta_{u}$ where $\Pi$ is the projector to the subspace $V$. Fairly straightforward calculations show that $2$-norm squared of such a function is expected to be $(d/n)\lVert\delta_{\omega}\rVert_{2}^{2}=d$, and it turns out in our setting we can assume that the norm is well concentrated around this expectation (or else we’d be able to find a good solution in some other way). Thus, if coordinate projection fails then it must hold that

It turns out that (2.5) implies some nontrivial constraints on the distribution $\mathcal{D}$. Specifically we know that

But since $f=\Pi f$ and $\Pi$ is symmetric, the RHS is equal to

where the last inequality uses Cauchy–Schwarz. If we square this inequality we get that

But since is a projector satisfying $\Pi=\Pi^{2}$, we can use (2.5) and obtain that

Equation (2.6), contrasted with the fact that $\operatorname*{\varmathbb{E}}_{f,f^{\prime}\sim\mathcal{D}}\langle f,f^{\prime}\rangle=O(\mu^{2})$, means that the inner product of two random functions in $\mathcal{D}$ is somewhat “surprisingly unconcentrated”, which seems to be a nontrivial piece of information about $\mathcal{D}$. Interestingly, this part of the argument does not require $\mu$ to be $o(d^{-1/3})$, and some analogous “non-concentration” property of $\mathcal{D}$ can be shown to hold for a hard to round $\mathcal{D}$ for any $\mu=o(1)$. However, we currently know how to take advantage of this property to obtain a combining algorithm only in the case that $\mu\ll d^{-1/3}$. Indeed, because the $f$’s are nonnegative functions, if we pick a random $u$ and consider the distribution $\mathcal{D}_{u}$ where the probability of every function is reweighed proportionally to $f(u)$, then intuitively that should increase the probability of pairs with large inner products. Indeed, as we show in Lemma A.4, one can use Hölder’s inequality to prove that there exist $\omega_{1},\ldots,\omega_{4}$ such that under the distribution $\mathcal{D}^{\prime}$ where every element $f$ is reweighed proportionally to $f(\omega_{1})\cdots f(\omega_{4})$, it holds that

(2.7) and (2.6) together imply that $\mathcal{E}_{f,f^{\prime}\sim\mathcal{D}^{\prime}}\langle f,f^{\prime}\rangle\gg\mu^{2}$, which, as mentioned above, means that we can find a function $g$ satisfying $\lVert g\rVert_{4}\gg\lVert g\rVert_{2}$ by taking a gaussian function matching the first two moments of $\mathcal{D}^{\prime}$.

Once again, this combining algorithm can be turned into an algorithm that uses $O(1)$ levels of the SOS hierarchy. The main technical obstacle (which is still not very hard) is to prove another appropriate generalization of Hölder’s inequality for pseudoexpectations (see Lemma A.4). Generalizing to the setting that in the YES case the function is only approximately in the vector space is a bit more cumbersome. We need to consider apart from $f$ the function $\overline{f}$ that is obtained by first projecting $f$ to the subspace and then “truncating” it by rounding each coordinate where $f$ is too small to zero. Because this truncation operation is not a low degree polynomial, we include the variables corresponding to $\overline{f}$ as part of the relaxation, and so our pseudoexpectation operator also contains the moments of these functions as well.

3 Optimizing polynomials with nonnegative coefficients

We now consider the task of maximizing a polynomial with nonnegative coefficients over the sphere, namely proving Theorem 3.1. We consider the special case of Theorem 3.1 where the polynomial is of degree $4$. That is, we are given a parameter $\varepsilon>0$ and an $n^{2}\times n^{2}$ nonnegative matrix $M$ with spectral norm at most $1$ and want to find an $\varepsilon$ additive approximation to the maximum of

over all $x\in R^{n}$ with $\lVert x\rVert=1$, where in this section we let $\lVert x\rVert$ be the standard (counting) Euclidean norm $\lVert x\rVert=\sqrt{\sum_{i}x_{i}^{2}}$.

One can get some intuition for this problem by considering the case where $M$ is $0/1$ valued and $x$ is $0/k^{-1/2}$ valued for some $k$. In this case one can think of $M$ is a $4$-uniform hypergraph on $n$ vertices and $x$ as a subset $S\subseteq[n]$ that maximizes the number of edges inside $S$ divided by $|S|^{2}$, and so this problem is related to some type of a densest subgraph problem on a hypergraph. The condition of maximizing $|E(S)|/|S|^{2}$ is related to the log density condition used by [BCC+10] in their work on the densest subgraph problem, since, assuming that the set $[n]$ of all vertices is not the best solution, the set $S$ satisfies that $\log_{|S|}|E(S)|>\log_{n}|E|$. However, we do not know how to use their algorithm to solve this problem. Beyond the fact that we consider the hypergraph setting, their algorithm manages to find a set of nontrivial density under the assumption that there is a “log dense” subset, but it is not guaranteed to find the “log dense” subset itself.

Let’s assume that we are given a distribution $\mathcal{X}$ over unit vectors that achieve some value $\nu$ in (2.8). This is a non convex problem, and so generally the average of these vectors would not be a good solution. However, it turns out that the vector $x^{*}$ defined such that $x^{*}_{i}=\sqrt{\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{i}^{2}}$ can sometimes be a good solution for this problem. Specifically, we will show that if it fails to give a solution of value at least $c-\varepsilon$, then we can find a new distribution $\mathcal{X}^{\prime}$ obtained by reweighing elements $\mathcal{X}$ that is in some sense “simpler” than $\mathcal{X}$. More precisely, we will define some nonnegative potential function $\Psi$ such that $\Psi(\mathcal{X})\leqslant\log n$ for all $\mathcal{X}$ and $\Psi(\mathcal{X}^{\prime})\leqslant\Psi(\mathcal{X})-\Omega(\varepsilon^{2})$ under the above conditions. This will show that we will need to use this reweighing step at most logarithmically many times.

where $y$ is the $n^{2}$-dimensional vector defined by $y_{i,j}=\sqrt{\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{i}^{2}x_{j}^{2}}$. Indeed, (2.10) follows from the non-negativity of $M$ and the Cauchy–Schwarz inequality since

Note that since $\mathcal{X}$ is a distribution over unit vectors, both $x^{*}$ and $y$ are unit vectors, and hence (2.9) and (2.10) together with the fact that $M$ has bounded spectral norm imply that

However, it turns out that $\lVert y-{x^{*}}^{\otimes 2}\rVert$ equals $\sqrt{2}$ times the Hellinger distance of the two distributions $D,D^{*}$ over $[n]\times[n]$ defined as follows: $\operatorname*{\varmathbb{P}}[D=(i,j)]=\operatorname*{\varmathbb{E}}x_{i}^{2}x_{j}^{2}$ while $\operatorname*{\varmathbb{P}}[D^{*}=(i,j)]=(\operatorname*{\varmathbb{E}}x_{i}^{2})(\operatorname*{\varmathbb{E}}x_{j}^{2})$ (see Section 3). At this point we can use standard information theoretic inequalities to derive from (2.11) that there is $\Omega(\varepsilon^{2})$ mutual information between the two parts of $D$. Another way to say this is that the entropy of the second part of $\mathcal{D}$ drops on average by $\Omega(\varepsilon^{2})$ if we condition on the value of the first part. To say the same thing mathematically, if we define $D(\mathcal{X})$ to be the distribution $(\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{1}^{2},\ldots,\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{n}^{2})$ over $[n]$ and $D(\mathcal{X}|i)$ to be the distribution $\tfrac{1}{\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{i}^{2}}(\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{i}^{2}x_{1}^{2},\ldots,\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{i}^{2}x_{n}^{2})$ then

But one can verify that $D(\mathcal{X}|i)=D(\mathcal{X}_{i})$ where $\mathcal{X}_{i}$ is the distribution over $x$’s such that $\operatorname*{\varmathbb{P}}[\mathcal{X}_{i}=x]=x_{i}^{2}\operatorname*{\varmathbb{P}}[\mathcal{X}=x]/\operatorname*{\varmathbb{E}}_{\mathcal{X}}x_{i}^{2}$, which means that if we define $\Psi(\mathcal{X})=H(D(\mathcal{X}))$ then we get that

and hence $\Psi$ is exactly the potential function we were looking for.

Approximation for nonnegative tensor maximization

Let $M$ be a degree-$2t$ homogeneous polynomial in $x=(x_{1},\ldots,x_{n})$ with nonnegative coefficients. Then, there is an algorithm, based on $O(t^{2}\log n/\varepsilon^{2})$ levels of the SOS hierarchy, that finds a unit vector $x^{*}\in\varmathbb R^{n}$ such that

To prove Theorem 3.1 we first come up with a combining algorithm, namely an algorithm that takes (the moment matrix of) a distribution $\mathcal{X}$ over unit vectors $x\in R^{n}$ such that $M(x)\geqslant\nu$ and find a unit vector $x^{*}$ such that $M(x^{*})\geqslant\nu-\varepsilon$. We then show that the algorithm will succeed even if $\mathcal{X}$ is merely a level $O(t\log n/\varepsilon^{2})$ pseudo distribution; that is, the moment matrix is a pseudoexpectation operator. The combining algorithm is very simple:

Combining algorithm for polynomials with nonnegative coefficients:

Input: distribution $\mathcal{X}$ over unit $x\in\varmathbb R^{n}$ such that $M(x)=\nu$.

Operation: Do the following for $t^{2}\log n/\varepsilon^{2}$ steps:

For $i\in[n]$, let $x^{*}_{i}=\sqrt{\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{i}^{2}}$. If $M(x^{*})\geqslant\nu-4\varepsilon$ then output $x^{*}$ and quit.

Try to find $i_{1},\ldots,i_{t-1}\in[n]$ such that the distribution $\mathcal{X}_{i_{1},\ldots,i_{t-1}}$ satisfies $\Psi(\mathcal{X}_{i_{1},\ldots,i_{t-1}})\leqslant\Psi(\mathcal{X})-\varepsilon^{2}/t^{2}$, and set $\mathcal{X}=\mathcal{X}_{i_{1},\ldots,i_{t-1}}$, where:

$\mathcal{X}_{i_{1},\ldots,i_{t-1}}$ is defined by letting $\operatorname*{\varmathbb{P}}[\mathcal{X}_{i_{1},\ldots,i_{t-1}}=x]$ be proportional to $\operatorname*{\varmathbb{P}}[\mathcal{X}=x]\cdot\prod_{j=1}^{t-1}x_{i_{j}}^{2}$ for every $x\in\varmathbb R^{n}$.

$\Psi(\mathcal{X})$ is defined to be $H(A(\mathcal{X}))$ where $H(\cdot)$ is the Shannon entropy function and $A(\mathcal{X})$ is the distribution over $[n]$ obtained by letting $\operatorname*{\varmathbb{P}}[A(\mathcal{X})=i]=\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{i}^{2}$ for every $i\in[n]$.

Clearly $\Psi(\mathcal{X})$ is always in $[0,\log n]$, and hence if we can show that we always succeed in at least one of the steps, then eventually the algorithm will output a good $x^{*}$. We now show that if the direct rounding step fails, then the conditioning step must succeed. We do the proof under the assumption that $\mathcal{X}$ is an actual distribution. Almost of all of this analysis holds verbatim when $\mathcal{X}$ is a pseudodistribution of level at least $2t^{2}\log n/\varepsilon^{2}$, and we note the one step where the extension requires using a nontrivial (though easy to prove) property of pseudoexpectations, namely that they satisfy the Cauchy–Schwarz inequality.

For any two jointly-distributed random variables $X$ and $Y$,

1 Direct Rounding

Given $\mathcal{X}$, we define the following correlated random variables $A_{1},\ldots,A_{t}$ over $[n]$: the probability that $(A_{1},\ldots,A_{t})=(i_{1},\ldots,i_{t})$ is equal to $\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{i_{1}}^{2}\cdots x_{i_{t}}^{2}$. Note that for every $i$, the random variable $A_{i}$ is distributed according to $A(\mathcal{X})$. (Note that even if $\mathcal{X}$ is only a pseudodistribution, $A_{1},\ldots,A_{t}$ are actual random variables.) The following lemma gives a sufficient condition for our direct rounding step to succeed:

Next, we bound the difference between $Q(y)$ and $M(x^{*})$

Since both ${x^{*}}^{\otimes t}$ and $y$ are unit vectors, $\lVert y+{x^{*}}^{\otimes t}\rVert\leqslant 2$. By construction, the vector $y$ corresponds to the distribution $\{A_{1}\cdots A_{t}\}$ and ${x^{*}}^{\otimes t}$ corresponds to the distribution $\{A_{1}\}\cdots\{A_{t}\}$. In particular, $d_{H}(\{A_{1}\cdots A_{t}\},\{A_{1}\}\cdots\{A_{t}\})=\tfrac{1}{\sqrt{2}}\lVert y-{x^{*}}^{\otimes t}\rVert$. Together with the bounds (3.1) and (3.2),

To verify this carries over when $\mathcal{X}$ is a pseudodistribution, we just need to use the fact that Cauchy–Schwarz holds for pseudoexpectations (Lemma A.2).

2 Making Progress

The following lemma shows that if the sufficient condition above is violated, then on expectation we can always make progress. (Because $A_{1},\ldots,A_{t}$ are actual random variables, it automatically holds regardless of whether $\mathcal{X}$ is an actual distribution or a pseudodistribution.)

If $d_{H}(\{A_{1}\cdots A_{t}\},\{A_{1}\}\cdots\{A_{t}\})\geqslant\varepsilon$, then $H(A_{t}\mid A_{1}\cdots A_{t-1})\leqslant H(A)-2\varepsilon^{2}/t^{2}$

The bound follows by combining a hybrid argument with Lemma 3.2.

Let $A^{\prime}_{1},\ldots,A^{\prime}_{t}$ be independent copies of $A_{1},\ldots,A_{t}$ so that

We consider the sequence of distributions $D_{0},\ldots,D_{t}$ with

By assumption, $d_{H}(D_{0},D_{t})\geqslant\varepsilon$. Therefore, there exists an index $i$ such that $d_{H}(D_{i-1},D_{i})\geqslant\varepsilon/t$. Let $X=A_{1}\cdots A_{i-1}$ and $Y=A_{i}A^{\prime}_{i+1}\cdots A^{\prime}_{t}$. Then, $D_{i}=\{XY\}$ and $D_{i-1}=\{X\}\{Y\}$. By Lemma 3.2,

Since $A^{\prime}_{i+1},\ldots,A^{\prime}_{t}$ are independent of $A_{1},\ldots,A_{i}$,

By symmetry and the monotonicity of entropy under conditioning, we conclude

Lemma 3.4 implies that if our direct rounding fails then the expectation of $H(A_{1})$ conditioned on $A_{2},\ldots,A_{t}$ is at most $H(A)-2\varepsilon^{2}/t^{2}$, but in particular this means there exist $i_{1},\ldots,i_{t-1}$ so that $H(A_{t}|A_{1}=i_{1},\ldots,A_{t-1}=i_{t-1})\leqslant H(A)-2\varepsilon^{2}/t^{2}$. The probability of $i$ under this distribution $A_{t}|A_{1}=i_{1},\ldots,A_{t-1}=i_{t-1}$ is proportional to $\operatorname*{\varmathbb{E}}_{x\sim\mathcal{X}}x_{i}^{2}\cdot\prod_{j=1}^{t-1}x_{i_{j}}^{2}$, which means that it exactly equals the distribution $A(\mathcal{X}_{i_{1},\ldots,i_{t-1}})$. Thus we see that $\Psi(\mathcal{X}_{i_{1},\ldots,i_{t-1}})\leqslant\Psi(\mathcal{X})-2\varepsilon^{2}/t^{2}$. This concludes the proof of Theorem 3.1. ∎

If the polynomial is not homogenous but only has monomials of even degree, we can homogenize it by multiplying every monomial with an appropriate power of $(\sum x_{i}^{2})$ which is identically equal to $1$ on the sphere. To handle odd degree monomials we can introduce a new variable $x_{0}$ and set a constraint that it must be identically equal to $1/2$. This way we can represent all odd degree monomials by even degree monomials with a blowup of $2$ in the coefficients. Note that if the pseudoexpectation operator is consistent with this constraint then our rounding algorithm will in fact output a vector that satisfies it.

Finding an “analytically sparse” vector in a subspace

In this section we prove Theorem 1.5. We let $\mathcal{U}$ be a universe of size $n$ and $L_{2}(\mathcal{U})$ be the vector space of real-valued functions $f\colon\mathcal{U}\to\varmathbb R$. The measure on the set $\mathcal{U}$ is the uniform probability distribution and hence we will use the inner product $\langle f,g\rangle=\operatorname*{\varmathbb{E}}_{\omega}f(\omega)g(\omega)$ and norm $\lVert f\rVert_{p}=\left(\operatorname*{\varmathbb{E}}_{\omega}f(\omega)^{p}\right)^{1/p}$ for $f,g\colon\mathcal{U}\to\varmathbb R$ and $p\geqslant 1$.

There is a constant $\varepsilon>0$ and a polynomial-time algorithm $A$, based on $O(1)$ levels of the SOS hierarchy, that on input a projector operator $\Pi$ such that there exists a $\mu$-sparse Boolean function $f$ satisfying $\lVert\Pi f\rVert_{2}^{2}\geqslant(1-\varepsilon)\lVert f\rVert_{2}^{2}$, outputs a function $g\in\textrm{Image}(\Pi)$ such that

We will prove Theorem 4.1 by first showing a combining algorithm and then transforming it into a rounding algorithm. Note that the description of the combining algorithm is independent of the actual relaxation used, since it assumes a true distribution on the solutions, and so we first describe the algorithm before specifying the relaxation. In our actual relaxation we will use some auxiliary variables that will make the analysis of the algorithm simpler.

Combining algorithm for finding an analytically sparse vector:

Input: Distribution $\mathcal{D}$ over Boolean (i.e., $0/1$ valued) functions $f\in L_{2}(\mathcal{U})$ that satisfy:

$\mu(f)=\operatorname*{\varmathbb{P}}[f(\omega)=1]=1/\lambda$.

$\lVert\Pi f\rVert_{2}^{2}\geqslant(1-\varepsilon)\lVert f\rVert_{2}^{2}$.

For $\omega\in\mathcal{U}$, let $\delta_{\omega}\colon\mathcal{U}\to\varmathbb R$ be the function that satisfies $\langle f,\delta_{\omega}\rangle=f(\omega)$ for all $f\in L_{2}(\mathcal{U})$. Go over all vectors of the form $g_{\omega}=\Pi\delta_{\omega}$ for $\omega\in\mathcal{U}$ and if there is one that satisfies (4.1) then output it. Note that the output of this procedure is independent of the distribution $\mathcal{D}$.

Choose a random gaussian vector $t\in L_{2}(\mathcal{U})$ and output $g=\Pi t$ if it satisfies (4.1). (Note that this is also independent of the distribution $\mathcal{D}$.)

Go over all choices for $\omega_{1},\ldots,\omega_{4}\in\mathcal{U}$ and modify the distribution $\mathcal{D}$ to the distribution $\mathcal{D}_{\omega_{1},\ldots,\omega_{4}}$ defined such that $\operatorname*{\varmathbb{P}}_{\mathcal{D}_{\omega_{1},\ldots,\omega_{4}}}[f]$ is proportional to $\operatorname*{\varmathbb{P}}_{\mathcal{D}}[f]\prod_{j=1}^{4}f(\omega_{j})^{2}$ for every $f$.

For every one of these choices, let $t$ to be a random Gaussian that matches the first two moments of the distribution $\mathcal{D}$, and output $g=\Pi t$ if it satisfies (4.1).

Because we will make use of this fact later, we will note when certain properties hold not just for expectations of actual probability distributions but for pseudoexpectations as well. The extension to pseudoexpectations is typically not deep, but can be cumbersome, and so the reader might want to initially restrict attention to the case of a combining algorithm, where we only deal with actual expectations. We show the consequences for each of the steps failing, and then combine them together to get a contradiction.

We start by analyzing the random function rounding step. Let $e_{1},\ldots,e_{n}$ be an orthonormal basis for the space of functions $L_{2}(\mathcal{U})$. Let $t$ be a standard Gaussian function in $L_{2}(\mathcal{U})$, i.e., $t=\xi_{1}e_{1}+\ldots+\xi_{n}e_{n}$ for independent standard normal variable $\xi_{1},\ldots,\xi_{n}$ (each with mean and variance $1$). The following lemmas combined show what are the consequences if $\lVert\Pi t\rVert_{4}$ is not much bigger than $\lVert\Pi t\rVert_{2}$.

For any $f,g\colon\mathcal{U}\to\varmathbb R$,

In the $\{e_{1},\ldots,e_{n}\}$ basis, $f=\sum_{i}a_{i}e_{i}$ and $g=\sum_{j}b_{j}e_{j}$. Then, $\langle f,g\rangle=\sum_{i}a_{i}b_{i}$ and $\langle f,t\rangle\langle g,t\rangle=\sum_{ij}a_{i}b_{j}\xi_{i}\xi_{j}$, which has expectation $\sum_{i}a_{i}b_{i}$. Hence, the left-hand side is the same as the right-hand side. ∎

The $4^{th}$ moment of $\lVert\Pi t\rVert_{4}$ satisfies

By the previous lemma, the Gaussian variable $\Pi t(\omega)=\langle\Pi\delta_{\omega},t\rangle$ has variance $\lVert\Pi\delta_{\omega}\rVert_{2}^{2}$. Therefore,

since $3=\operatorname*{\varmathbb{E}}_{X\sim N(0,1)}X^{4}$. ∎

The $4^{th}$ moment of $\lVert\Pi t\rVert_{2}$ satisfies

The random variable $\lVert\Pi t\rVert_{2}$ has a $\chi^{2}$-distribution with $k=\operatorname{rank}\Pi$ degrees of freedom. The mean of this distribution is $k$ and the variance is $2k$. It follows that $\operatorname*{\varmathbb{E}}_{t}\lVert\Pi t\rVert_{2}^{4}\leqslant 10(\operatorname{rank}\Pi)^{4}$. ∎

2 Coordinate projection rounding

We now turn to showing the implications of the failure of projection rounding. We start by noting the following technical lemma, that holds for both the expectation and counting inner products:

Let $x$ and $y$ be two independent, vector-valued random variables. Then,

where the last equality holds by independence. But this is simply equal to

The following lemma shows a nontrivial consequence for $\lVert\Pi\delta_{\omega}\rVert_{4}^{4}$ being small:

For any distribution $\mathcal{D}$ over $L_{2}(\mathcal{U})$,

3 Gaussian Rounding

In this subsection we analyze the gaussian rounding step. Let $t$ be a random function with the Gaussian distribution that matches the first two moments of a distribution $\mathcal{D}$ over $L_{2}(\mathcal{U})$.

The $4^{th}$ moment of $\lVert\Pi t\rVert_{4}$ satisfies

If $\{A,B,C,D\}$ have Gaussian distribution, then

The fourth moment of $\lVert\Pi t\rVert_{2}$ satisfies

4 Conditioning

We now show the sense in which conditioning can make progress. Let $\mathcal{D}$ be a distribution over $L_{2}(\mathcal{U})$. For $\omega\in\mathcal{U}$, let $\mathcal{D}_{\omega}$ be the distribution $\mathcal{D}$ reweighed by $f(\omega)^{2}$ for $f\sim\mathcal{D}$. That is, $\operatorname*{\varmathbb{P}}_{\mathcal{D}_{\omega}}\{f\}\propto f(\omega)^{2}\cdot\operatorname*{\varmathbb{P}}_{\mathcal{D}}\{f\}$, or in other words, for every function $P(\cdot)$, $\operatorname*{\varmathbb{E}}_{f\sim\mathcal{D}_{\omega}}P(f)=(\operatorname*{\varmathbb{E}}_{fsim\mathcal{D}}f(\omega)^{2}P(f))/(\operatorname*{\varmathbb{E}}_{f\sim\mathcal{D}}f(\omega)^{2})$. Similarly, we write $\mathcal{D}_{\omega_{1},\ldots,\omega_{r}}$ for the distribution $\mathcal{D}$ reweighed by $f(\omega_{1})^{2}\cdots f(\omega_{r})^{2}$.

For every even $r\in\varmathbb N$, there are points $\omega_{1},\ldots,\omega_{r}\in\mathcal{U}$ such that the reweighed distribution $\mathcal{D}^{\prime}=\mathcal{D}_{\omega_{1},\ldots,\omega_{r}}$ satisfies

but using $\operatorname*{\varmathbb{E}}(X/Y)\leqslant(\max X)/(\max Y)$ and $\operatorname*{\varmathbb{E}}_{\omega_{1},\ldots,\omega_{r}}f(\omega_{1})^{2}\cdots f(\omega_{r})^{2}g(\omega_{1})^{2}\cdots g(\omega_{r})^{2}=\left\langle g^{2},f^{2}\right\rangle^{r}$, the RHS is lower bounded by

Now, if $\mathcal{D}$ was an actual expectation, then we could use Hölder’s inequality to lower bound the numerator of the RHS by $\left(\operatorname*{\varmathbb{E}}_{f,g\sim\mathcal{D}}\left\langle f^{2},g^{2}\right\rangle^{r}\right)^{(r+1)/r}$ which would lower bound the RHS by $\left(\operatorname*{\varmathbb{E}}_{f,g\sim\mathcal{D}}\left\langle f^{2},g^{2}\right\rangle^{r}\right)^{1/r}$. For pseudoexpectations this follows by appealing to Lemma A.4. ∎

5 Truncating functions

The following observation would be useful for us for analyzing the case that the distribution is over functions that are not completely inside the subspace. Note that if the function $f$ is inside the subspace, we can just take $\overline{f}=f$ in Lemma 4.11, and so the reader may want to skip this section in a first reading and just pretend that $\overline{f}=f$ below.

Let $\varepsilon<1/400$, $\Pi$ be a projector on $\varmathbb R^{\mathcal{U}}$ and suppose that $f\colon\mathcal{U}\to\{0,1\}$ satisfies that $\operatorname*{\varmathbb{P}}[f(\omega)=1]=\mu$ and $\lVert\Pi f\rVert_{2}^{2}\geqslant(1-\varepsilon)\mu$. Then there exists a function $\overline{f}:\varmathbb R^{\mathcal{U}}\rightarrow\varmathbb R$ such that:

$\lVert\Pi\overline{f}\rVert_{4}^{4}\geqslant\Omega(\mu)$.

For every $\omega\in\mathcal{U}$, $\Pi f(\omega)^{2}\geqslant\Omega(|\overline{f}(\omega)|)$.

Fix $\tau>0$ to be some sufficiently small constant (e.g., $\tau=1/2$ will do). Let $f^{\prime}=\Pi f$. We define $\overline{f}=f^{\prime}\cdot 1_{|f^{\prime}|\geqslant\tau}$ (i.e., $\overline{f}(\omega)=f^{\prime}(\omega)$ if $|f^{\prime}(\omega)|\geqslant\tau$ and $\overline{f}(\omega)=0$ otherwise) and define $\underline{f}=f^{\prime}\cdot 1_{|f^{\prime}|<\tau}$. Clearly $f^{\prime}(\omega)^{2}\geqslant\tau|\overline{f}(\omega)|$ for every $\omega\in\mathcal{U}$.

Since $\underline{f}(x)\neq 0$ if and only if $f^{\prime}(x)\in(0,\tau)$, clearly $|\underline{f}(x)|\leqslant|f(x)-f^{\prime}(x)|$ and hence $\lVert\underline{f}\rVert_{2}^{2}\leqslant\varepsilon\mu$. Using $f^{\prime}=\overline{f}+\underline{f}$, we see that $\Pi\overline{f}=f+(f^{\prime}-f)-\underline{f}+(\Pi\overline{f}-\overline{f})$. Now since $f^{\prime}$ is in the subspace, $\lVert\Pi\overline{f}-\overline{f}\rVert_{2}\leqslant\lVert f^{\prime}-\overline{f}\rVert_{2}=\lVert\underline{f}\rVert_{2}$ and hence for $g=(f^{\prime}-f)-\underline{f}+(\Pi\overline{f}-\overline{f})$, $\lVert g\rVert_{2}\leqslant 3\sqrt{\varepsilon\mu}$. Therefore the probability that $g(\omega)\geqslant 10\sqrt{\varepsilon}$ is at most $\mu/2$. This means that with probability at least $\mu/2$ it holds that $f(\omega)=1$ and $g(\omega)\leqslant 10\sqrt{\varepsilon}$, in which case $\overline{f}(\omega)\geqslant 1-10\sqrt{\varepsilon}\geqslant 1/2$. In particular, we get that $\operatorname*{\varmathbb{E}}\overline{f}(\omega)^{4}\geqslant\Omega(\mu)$. ∎

The proof of Lemma 4.11 establishes much more than its statement. In particular note that we did not make use of the fact that $f$ is nonnegative, and a function $f$ into $\{0,\pm 1\}$ with $\operatorname*{\varmathbb{P}}[f(\omega)\neq 0]=\mu$ would work just the same. We also did not need the nonzero values to have magnitude exactly one, since the proof would easily extend to the case where they are in $[1/c,c]$ for some constant $c$. One can also allow some nonzero values of the function to be outside that range, as long as their total contribution to the 2-norm squared is much smaller than $\mu$.

6 Putting things together

We now show how the above analysis yields a combining algorithm, and we then discuss the changes needed to extend this argument to pseudodistributions, and hence obtain a rounding algorithm.

Let $\mathcal{D}$ be a distribution over Boolean functions $f\colon\mathcal{U}\to\{0,1\}$ with $\lVert f\rVert_{2}^{2}=\mu$ and $\lVert\Pi f\rVert_{2}^{2}\geqslant 0.99\lVert f\rVert_{2}^{2}$. The goal is to compute a function $t\colon\mathcal{U}\to\varmathbb R$ with $\lVert\Pi t\rVert_{4}\gg\lVert t\rVert_{2}^{2}$, given the low-degree moments of $\mathcal{D}$.