PaperlayerView exact revision on arXiv

Source-linked AI summary

Rounding Sum-of-Squares Relaxations

Boaz Barak, Jonathan Kelner, David Steurer

arXiv:1312.6652v1cs.DScs.LGquant-ph

TL;DR

Higher levels of the SOS hierarchy have been difficult to round into useful algorithms. This paper lifts combining algorithms through the SOS proof-system connection and obtains new algorithms for polynomial optimization, sparse-vector problems, and Small Set Expansion.

  • Problem

    General tools for rounding SOS solutions—especially tools that use higher-level constraints—are scarce, despite strong hierarchy lower bounds and few positive algorithmic results.

    Source: §1 · pp. 3–4

  • Method

    The authors lift a combining algorithm’s analysis through the SOS proof-system connection, turning a distribution-to-solution map into a rounding algorithm for sufficiently high-level SOS solutions.

    Source: §1 · p. 4, §1.1 · p. 5

  • Results

    The paper reports algorithms for nonnegative-polynomial maximization, planted sparse-vector recovery, and Small Set Expansion.

    Source: §3 · p. 16, §5 · p. 27, §6 · p. 30

  • Takeaways & Limitations

    Analytical sparsity yields Small Set Expansion guarantees parameterized by the dimension of the graph’s top eigenspace.

    Source: §6 · p. 30

    The L4/L2 choice restricts the results to low-dimensional subspaces, although some applications involve nearly full-dimensional kernels.

    Source: §1.3 · p. 8

Abstract

from arXiv · show

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly weaker) solution -- into a *rounding algorithm* that maps a solution of the relaxation to a solution of the original problem. Using this approach, we obtain algorithms that yield improved results for natural variants of three well-known problems: 1) We give a quasipolynomial-time algorithm that approximates the maximum of a low degree multivariate polynomial with non-negative coefficients over the Euclidean unit sphere. Beyond being of interest in its own right, this is related to an open question in quantum information theory, and our techniques have already led to improved results in this area (Brand\~{a}o and Harrow, STOC '13). 2) We give a polynomial-time algorithm that, given a d dimensional subspace of R^n that (almost) contains the characteristic function of a set of size n/k, finds a vector $v$ in the subspace satisfying $|v|_4^4 > c(k/d^{1/3}) |v|_2^2$, where $|v|_p = (E_i v_i^p)^{1/p}$. Aside from being a natural relaxation, this is also motivated by a connection to the Small Set Expansion problem shown by Barak et al. (STOC 2012) and our results yield a certain improvement for that problem. 3) We use this notion of L_4 vs. L_2 sparsity to obtain a polynomial-time algorithm with substantially improved guarantees for recovering a planted $\mu$-sparse vector v in a random d-dimensional subspace of R^n. If v has mu n nonzero coordinates, we can recover it with high probability whenever $\mu < O(\min(1,n/d^2))$, improving for $d < n^{2/3}$ prior methods which intrinsically required $\mu < O(1/\sqrt(d))$.

1 Introduction

The introduction presents a general SOS-based framework for turning combining algorithms into rounding algorithms, with applications to polynomial optimization and finding analytically sparse vectors in subspaces. It also connects sparse-vector recovery to Small Set Expansion and situates the paper’s fake-distribution approach among prior work.

1 Introduction

  • The SOS hierarchy tightens convex relaxations by adding constraints at each level, with level ℓ optimizable in n^O(ℓ) time; prior work established many strong integrality gaps.The introduction identifies the scarcity of positive algorithmic results that use these hierarchies to go beyond known guarantees as motivation for new rounding tools.Source: §1 · p. 3
  • The paper addresses the shortage of general tools for rounding SOS solutions by using the SOS proof-system connection to lift combining algorithms into rounding algorithms.A combining algorithm maps a distribution over feasible solutions to a possibly weaker solution; the lifted argument lets it work from a sufficiently high-level pseudoexpectation.Source: §1 · pp. 3–4, §1.1 · p. 5

1.2 Optimizing polynomials with nonnegative coefficients bounded spectral norm

  • With O(t log n/ε^2) SOS levels, the algorithm additively approximates the polynomial objective scaled by the tensor’s spectral norm, giving quasipolynomial-time optimization.The result applies to homogeneous polynomials of even degree t with nonnegative coefficients over the unit sphere.Source: §1.2 · p. 6

1.3 Optimizing hypercontractive norms and finding analytically sparse vectors

  • For a planted vector supported on at most c n min(1, n/d^2) coordinates, O(1) SOS rounds recover an ε-approximation in polynomial time with high probability under the stated random-subspace model.The other d spanning vectors are sampled independently from a Gaussian distribution.Source: §1.3 · p. 8
  • For a d-dimensional subspace containing a 0/1 vector with at most µn nonzero coordinates, O(1) SOS levels find an O(µd^1/3) L4/L2-sparse vector in polynomial time.L4/L2 sparsity is an analytic relaxation of support sparsity based on a vector’s q-norm-to-p-norm ratio.Source: §1.3 · p. 8
  • The L4/L2 ratio is presented as easier to optimize than L2/L1 and more useful for guarantees than L∞/L1, but the approach is restricted to low-dimensional subspaces.The passage suggests extending the results to higher-dimensional subspaces, perhaps at a mild cost in the number of rounds; sparse-vector enumeration is described as a bottleneck in Small Set Expansion algorithms [ABS10].Source: §1.3 · p. 8
  • Using, the authors derive a Small Set Expansion corollary: a set of size o(n/d^1/3) yields an output set of measure o(1) with expansion bounded away from 1.The result is stated for a graph whose random-walk matrix has a d-dimensional eigenspace corresponding to eigenvalues larger than 1−O(ε), and is described as the first approximation of this type parameterized by that dimension rather than polynomially in the vertex count.Source: §1.3 · p. 9

1.4 Related work

  • The approach treats SOS solutions as moments of “fake” distributions on actual solutions, unlike prior rounding methods that use distributions over fake solutions.The paper makes fake distributions more explicit and uses SOS tools more heavily than related positive hierarchy results [BRS11]; its combining algorithms are related to CSP polymorphisms but may combine assignments globally rather than bitwise.Source: §1.4 · p. 9

1.5 Organization of this paper

  • The paper organization maps its general approach and proof sketches, polynomial optimization, analytical sparsity, planted sparse-vector recovery, and Small Set Expansion results to Sections 2–6.The appendices cover pseudoexpectation inequalities, SOS results for QMA(2) verifiers, a bounded-Frobenius-norm algorithm, and the hypercontractivity–Small Set Expansion relation.Source: §1.5 · p. 10

1.6 Notation

  • The notation defines a level ℓ pseudoexpectation as a linear operator on polynomials of degree at most ℓ, with pseudodistributions referring to objects with an associated operator.The passage also defines consistency with equality constraints through vanishing expected squares and with inequality constraints through a sum-of-squares representation.Source: §1.6 · p. 10

2 Overview of our techniques

The paper’s general strategy is to design a combining algorithm first, then use the Sum-of-Squares proof system to turn it into a rounding algorithm for an efficiently optimizable relaxation. The overview applies this strategy to planted sparse-vector recovery, finding analytically sparse vectors in general subspaces, and maximizing nonnegative polynomials over the sphere.

2 Overview of our techniques

  • Sum-of-Squares reasoning lifts suitable combining algorithms from distributions over solutions to rounding algorithms for efficiently optimizable relaxations.The approach designs and analyzes the rounding algorithm before constructing the relaxation.Source: §2 · p. 11

2.1 Finding a planted sparse vector in a random low-dimensional subspace

  • In a random subspace containing a sparse vector and random functions, the top eigenvector of the functions’ second-moment matrix has 1-o(1) correlation with the planted vector.An additional correction step recovers the original function up to arbitrary accuracy.Source: §2.1 · pp. 12–13

2.2 Finding “analytically sparse” vectors in general subspaces

  • For general subspaces, large average pairwise inner products among sparse functions can yield a vector with higher L_4 than L_2 norm via Gaussian moment matching.The overview’s combining approach applies when µ is much smaller than d^-1/3; it notes that exploiting the related non-concentration property is currently known only in this regime.Source: §2.2 · pp. 13–14

2.3 Optimizing polynomials with nonnegative coefficients

  • For degree-4 polynomials with nonnegative coefficients, repeated reweighting after a failed direct candidate search leads to rounding using O(log n/ε^2) moment levels.The overview notes that the moment-based algorithm also works with SOS pseudoexpectations, yielding a rounding algorithm.Source: §2.3 · pp. 15–16

3 Approximation for nonnegative tensor maximization

For nonnegative homogeneous polynomials, the paper uses SOS pseudoexpectations to round a distribution of high-value unit vectors. A direct rounding test either produces a near-optimal vector or conditioning reduces an entropy potential until the test succeeds.

3 Approximation for nonnegative tensor maximization

  • O(t^2 log n/ε^2) SOS levels suffice to find a unit vector within ε∥M∥_spectral of the maximum for a degree-2t homogeneous polynomial with nonnegative coefficients.The guarantee is additive: M(x*) ≥ max_{∥x∥=1} M(x) − ε∥M∥_spectral.Source: §3 · p. 16

3.1 Direct Rounding

  • If the correlated coordinates’ joint distribution is within Hellinger distance ε of the product of its marginals, direct rounding gives a unit vector losing at most 4ε∥M∥_spectral.This guarantee also holds for a level-ℓ pseudodistribution when ℓ ≥ 2t.Source: §3.1 · p. 17

3.2 Making Progress

  • When direct rounding fails, conditioning on coordinates reduces the entropy potential by at least 2ε^2/t^2, providing progress toward a successful rounding step.The paper’s progress argument applies whether the input is a distribution or a pseudodistribution.Source: §3.2 · pp. 18–19

4 Finding an “analytically sparse” vector in a subspace

The paper turns a combining algorithm for finding analytically sparse vectors into a polynomial-time SOS rounding algorithm using O(1) levels. Its procedure tests several projected candidates, conditions the input distribution, and adds auxiliary variables to handle truncation in the pseudodistribution setting.

4 Finding an “analytically sparse” vector in a subspace

  • A polynomial-time algorithm based on O(1) SOS levels is obtained by first establishing a combining algorithm and then extending its analysis to pseudodistributions.The theorem’s input includes a projector and a nearly contained sparse Boolean function.Source: §4 · p. 19, §4.6 · p. 23

4.2 Coordinate projection rounding

  • Coordinate-projection rounding tests every projected coordinate function Πδ_ω and outputs one that meets the target condition.This candidate search is independent of the input distribution.Source: §4 · p. 19

4.1 Random function rounding

  • Random-function rounding projects a random Gaussian function through the subspace projector and tests the result against the target condition.The paper analyzes what follows if this projected Gaussian fails to have sufficiently large L_4 relative to L_2.Source: §4 · p. 19, §4.1 · p. 20

4.4 Conditioning

  • Conditioning reweights the distribution by function values squared at selected coordinates; the procedure searches over four coordinates.For selected points, the reweighting is proportional to f(ω1)^2 through f(ω4)^2.Source: §4 · p. 20, §4.4 · p. 22

4.3 Gaussian Rounding

  • Gaussian rounding matches the first two moments of the input distribution, projects the resulting Gaussian function, and tests it against the target condition.Source: §4 · p. 20, §4.3 · p. 21

4.5 Truncating functions

  • For a nearly contained sparse indicator, the truncation step projects the function into the subspace and zeros projected coordinates in a small positive interval.Source: §4.5 · p. 23

4.6 Putting things together

  • Because truncation is not a low-degree polynomial, the SOS relaxation adds the truncated functions as auxiliary variables and enforces the relevant conclusions as constraints.Source: §4.6 · p. 24

5 Finding planted sparse vectors

The section combines SOS-based approximate recovery with a linear program for exact recovery of a planted sparse vector. Its guarantees also apply beyond uniformly random subspaces when the relevant norm conditions hold.

5 Finding planted sparse vectors

  • Theorem 5.1 gives a polynomial-time algorithm for planted recovery when μ < Kμ0(d), with running time polynomial in |U| and log(1/ε).The theorem’s guarantees also extend to subspaces satisfying the section’s norm requirements, not only uniformly random subspaces.Source: §5 · pp. 25, 27
  • A constant-degree SOS relaxation first finds an approximate vector, then an auxiliary linear program converts a sufficiently correlated vector into exact recovery.The approximate stage uses an SOS-certifiable L4/L2 separation between the planted vector and the other subspace vectors.Source: §5 · pp. 25–26

5.2 Recovering f0 exactly (Proof of Theorem 5.3)

  • Under Theorem 5.3’s conditions, the linear program uniquely recovers the planted vector after normalization.The proof’s exact-recovery step uses a vector sharing many coordinates with the planted vector, extending the range beyond the basis-vector approach described in the text.Source: §5 · p. 26, §5.2 · p. 28

5.1 Recovering f0 approximately (Proof of Theorem 5.2)

  • Maximizing the L4 norm over unit vectors in the subspace yields a vector correlated with the planted vector, using a degree-8 SOS program and a Gaussian sample consistent with its first two moments.The guarantee relies on a degree-4 SOS proof certifying the norm bound on the other subspace.Source: §5.1 · p. 27

6 Results for Small Set Expansion

The section gives SOS algorithms for Small Set Expansion on Cayley graphs and general regular graphs. Their guarantees depend on graph structure or the dimension of a relevant eigenspace.

6 Results for Small Set Expansion

  • The paper gives a quasipolynomial-time algorithm for an interesting family of Cayley graphs and a polynomial-time approximation algorithm for general graphs whose guarantee depends on the top eigenspace dimension.Small Set Expansion is connected in the section to the Unique Games problem.Source: §6 · p. 30

6.1 Small-set expansion of Cayley graphs

  • Degree ε^-O(1)Kλ(G)^O(1) log n SOS relaxations approximate the maximum L4/L2 ratio over V⩾λ to additive ε.The section states that the running time is quasipolynomial when Kλ(G) is polylogarithmic.Source: §6.1 · p. 30
  • For long-code and short-code based graphs with constant eigenvalue gap, Kλ(G) = O(1) for all λ = Ω(1), supporting quasipolynomial-time algorithms on these families.The SOS relaxation distinguishes a small set of measure at most μ and expansion at most ε from the stated no-case.Source: §6.1 · pp. 30–31

6.2 Approximating small-set expansion using ASVP

  • The section notes that an algorithm replacing the (dim V⩾λ)^(1/3) factor with a constant would refute the Small-Set Expansion Hypothesis.A smaller o(1)-exponent improvement is only conjectured to imply a refutation under standard complexity assumptions; the authors state they have no proof.Source: §6.2 · p. 31
  • Constant-degree SOS relaxations solve the regular-graph promise problem when the yes-case set has measure at most μ/(dim V⩾λ)^(1/3) and expansion at most ε.The no-case requires sets of measure μ to have expansion at least 1 − 1/C.Source: §6.2 · p. 31

7 Discussion and open questions

The discussion identifies open directions for SOS rounding, including more general rounding principles and applications to sparsity, while suggesting that some current results may admit further improvement. It also proposes combining gaps as a way to study failures of particular combining algorithms.

7 Discussion and open questions

  • Potential applications include improving the Sparsest Cut result of with more SOS levels and using SOS for unsupervised learning, especially nonlinear models.The discussion suggests SOS for problems where random instances may not be the hardest, while noting that planted sparse-vector results also show average-case usefulness.Source: §7 · p. 32
  • A universal rounding algorithm and a general theorem translating combining algorithms into rounding algorithms remain open questions.The paper notes progress toward such a translation elsewhere.Source: §7 · p. 32
  • Analytically sparse vectors may support further applications; the authors propose exploring Lq/Lp sparsity tradeoffs and conjecture detection in random subspaces of dimension n^(1−1/ℓ).For planted sparse vectors, they conjecture an analytical relaxation could be optimized in n^O(ℓ) time.Source: §7 · p. 32
  • The authors conjecture that their Section 4 algorithm or analysis can improve because they know no candidate hard instances in the relevant parameter range.Further improvement is identified as the key question for the Small-Set-Expansion Hypothesis / Unique Games Conjecture context.Source: §7 · p. 32
  • A combining gap is a distribution of good solutions that defeats a particular combining algorithm, and thus can expose failure independent of the relaxation used.The discussion cites hard instances for the Goemans–Williamson hyperplane-cut rounding algorithm as an example.Source: §7 · p. 32

A Pseudoexpectation toolkit

The appendix defines pseudo-expectations and records properties that let them support SOS reasoning much like true expectations. It also describes their representation and the resulting computational cost of solving the SOS relaxation.

A Pseudoexpectation toolkit

  • A level-r pseudo-expectation functional is a linear map on polynomials of degree at most r that is normalized and nonnegative on squares of degree at most r/2.The functional can be represented by its pseudo-expectations of monomials up to degree r.Source: A Pseudoexpectation toolkit · p. 37
  • A level-r SOS relaxation has an n^O(r)-time separation oracle and can be solved to accuracy ε in time (mn · log(1/ε))^O(r).The representation uses a table of pseudo-expectations for monomials of degree at most r, and positivity is a positive-semidefinite condition.Source: A Pseudoexpectation toolkit · p. 37
  • True random-variable expectations induce pseudo-expectations at every level, and the hierarchy converges to true expectations as the level tends to infinity, though not necessarily in finitely many steps.The passage notes that for most problems of interest in TCS, n levels suffice for exact convergence or a sufficiently close approximation.Source: A Pseudoexpectation toolkit · p. 37
  • An SOS ordering between polynomials implies the same ordering under any matching-degree pseudo-expectation; this also applies on a linear subspace when the pseudoexpectation is supported on the kernel constraints.The appendix gives a kernel-based lemma for transferring an SOS comparison to a pseudo-expectation satisfying the corresponding constraint.Source: A Pseudoexpectation toolkit · pp. 37–39
  • Pseudo-expectations satisfy a Cauchy–Schwarz inequality, including the consequence that a polynomial with zero squared pseudo-expectation has zero product pseudo-expectation with every eligible polynomial.The appendix also records a pseudo-expectation version of Hölder’s inequality.Source: A Pseudoexpectation toolkit · pp. 37–38
  • Two pseudodistributions can be combined into a joint pseudoexpectation for which products of eligible polynomials from the separate variables factor into their pseudo-expectations.The construction preserves positivity by using the positive semidefinite moment matrices of the two pseudodistributions.Source: A Pseudoexpectation toolkit · p. 38

A.1 Spectral norm and SOS proofs

For a degree-4 homogeneous polynomial, the spectral norm bound has an equivalent sum-of-squares certificate.

A.1 Spectral norm and SOS proofs

  • For degree-4 homogeneous P, ∥P∥_spectral ≤ c holds if and only if a degree-4 sum-of-squares certificate exists.The appendix establishes this characterization by relating the polynomial to a positive semidefinite matrix representation.Source: §A.1 · p. 40

B Low-Rank Tensor Optimization

The appendix studies optimization of low-rank quartic polynomials and gives algorithms for approximating their norm and a related tensor objective. Its guarantees depend on the rank parameter and approximation accuracy.

B Low-Rank Tensor Optimization

  • A polynomial P(x) = Σ_i=1^r Q_i(x)^2 has its norm computable within multiplicative error ε in exp(poly(r, ε)) time.The method reduces the norm computation to maximizing the norm of a linear combination of the quadratic polynomials over a unit coefficient vector.Source: B Low-Rank Tensor Optimization · p. 40
  • For a symmetric n^2 × n^2 PSD matrix with Frobenius norm at most 1, the associated maximum has an ε-additive approximation in poly(n) exp(poly(1/ε)) time.The proof approximates the matrix by a low-rank sum and bounds the difference in the objective by ε.Source: B Low-Rank Tensor Optimization · pp. 40–41

C LOCC Polynomial Optimization

For a class of degree-4 polynomial optimization problems, the section bounds the sum-of-squares relaxation and gives a Gaussian-rounding argument for obtaining an actual vector. When the A and B polynomial variables are disjoint, the approximation guarantee improves from a factor-three bound to an additive-error bound.

C LOCC Polynomial Optimization

  • For disjoint A and B variables, the section relates its proof to Brandão, Christandl, and Yard, and says the proof before Gaussian rounding is essentially that of Brandão and Harrow.The cited prior result covers the disjoint-variable case.Source: C LOCC Polynomial Optimization · pp. 41, 43
  • For degree-4 homogeneous polynomials P of the stated decomposed form, the sum-of-squares relaxation has value at most 3||P|| + ε at degree d ≥ O(1/ε²) log n.Source: C LOCC Polynomial Optimization · p. 41
  • A Gaussian with the same first two moments as the distribution achieves at least the value obtained by independently sampling the A and B parts when global correlation is low.The cited result also applies when the input is a degree-4 pseudo-distribution.Source: C LOCC Polynomial Optimization · pp. 41–42
  • Reweighting by a polynomial of degree O((1/ε^2) log n) yields a distribution with low global correlation, enabling Gaussian rounding while preserving the objective up to ε.The reweighting polynomial is a product of the B_i polynomials; the construction also applies to the stated higher-degree pseudo-distributions.Source: C LOCC Polynomial Optimization · pp. 41–43
  • Given a degree-d + 4 pseudo-distribution with ∥X∥2 = 1 and P(X) ≥ c, the proof yields a vector x with ∥P∥ ≥ c/3 − ε.Here d = O(1/ε^2) log n; such a vector can also be found efficiently by sampling from {X′}.Source: C LOCC Polynomial Optimization · p. 43

D The 2-to-q norm and small-set expansion

This section relates the 2-to-q norm of a graph’s top-eigenspace projector to small-set expansion. It gives bounds in both directions and an algorithm that turns a sufficiently large-norm function into a small set with poor expansion.

D The 2-to-q norm and small-set expansion

  • A sufficiently small 2-to-q norm of the top-eigenspace projector implies that every set of measure at most δ has expansion at least 1 − λ − ε^2.The norm condition is ||P_{≥λ}(G)||_{2→q} ≤ ε/δ^((q−2)/2q).Source: D The 2-to-q norm and small-set… · p. 44
  • Conversely, the section bounds the projector norm under a small-set expansion assumption and gives an efficient algorithm that finds a set of measure less than δ with low expansion from a qualifying high-norm function.The theorem states the expansion threshold as 1 − λ^2 − cq, and the algorithmic guarantee as Φ_G(S) ≤ 1 − λ^2 − cq.Source: D The 2-to-q norm and small-set… · p. 44
  • A polynomial-time computable relaxation with good approximation for the 2-to-q norm would refute the Small-Set Expansion Hypothesis.The section also notes that the projector-norm characterization and a vector-to-set algorithm were established in prior work.Source: D The 2-to-q norm and small-set… · pp. 43–44

D.1 Norm bound implies small-set expansion

This subsection proves one direction of the connection: an upper bound on the 2-to-q norm of the projector to a graph’s top eigenspace implies small-set expansion.

D.1 Norm bound implies small-set expansion

  • An upper bound on the top-eigenspace projector’s 2-to-q norm implies that the graph is a small-set expander.The theorem’s norm condition is stated for every δ > 0 and ε > 0.Source: §D.1 · p. 47
  • The proof uses duality of norms and the fact that the eigenspace projector is self-adjoint to express the relevant operator norm in a form suitable for bounding.The passage gives the dual-norm identity and notes A = A^T for a projection operator.Source: §D.1 · p. 47
  • For a set S, the proof applies the norm bound to its characteristic function after splitting that function into top-eigenspace and remaining components.The decomposition is f = f′ + f′′, where f′ is in the λ-eigenspace subspace and f′′ is the remainder.Source: §D.1 · p. 47
Loading 1312.6652v1…