Source-linked AI summary
Sum-of-squares proofs and the quest toward optimal algorithms
Boaz Barak, David Steurer
TL;DR
The paper addresses the difficulty of establishing when nontrivial algorithmic guarantees are optimal. It surveys connections between UGC and SOS, including results in which UGC predicts the optimality of a common meta-algorithm. It discusses how SOS could potentially improve guarantees and challenge UGC, while noting that equivalence between SSEH and UGC remains open.
Problem
For problems with nontrivial approximation guarantees, it is difficult to rule out more effective algorithms and establish that existing guarantees are optimal.
Source: §1 · p. 3Method
The survey examines SOS, its applications, and its connections to UGC and SSEH, including how SOS guarantees might be analyzed.
Source: §1 · p. 4, §1.2 · p. 6Results
Assuming UGC, the UGC meta-algorithm is optimal across a broad class, including constraint-satisfaction problems, sparsest cut, and matrix correlation.
Source: §1 · p. 4Takeaways & Limitations
SOS could potentially beat UGC-predicted guarantees, improving known results and possibly refuting UGC.
Source: §1 · p. 4Whether SSEH and UGC are equivalent remains an open problem.
Source: §1.1 · p. 5
Abstract
from arXiv · showhide
In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible guarantees for a wide range of different problems. The Unique Games Conjecture (UGC) is a tantalizing conjecture in computational complexity, which, if true, will shed light on the complexity of a great many problems. In particular this conjecture predicts that a single concrete algorithm provides optimal guarantees among all efficient algorithms for a large class of computational problems. The Sum-of-Squares (SOS) method is a general approach for solving systems of polynomial constraints. This approach is studied in several scientific disciplines, including real algebraic geometry, proof complexity, control theory, and mathematical programming, and has found applications in fields as diverse as quantum information theory, formal verification, game theory and many others. We survey some connections that were recently uncovered between the Unique Games Conjecture and the Sum-of-Squares method. In particular, we discuss new tools to rigorously bound the running time of the SOS method for obtaining approximate solutions to hard optimization problems, and how these tools give the potential for the sum-of-squares method to provide new guarantees for many problems of interest, and possibly to even refute the UGC.
1. Introduction
The introduction presents the UGC as a route to matching nontrivial algorithms with hardness results, then surveys how SOS may test those guarantees and potentially challenge the conjecture. It focuses on the Small-Set Expansion Hypothesis (SSEH) and outlines the survey’s SOS applications and scope.
1. Introduction
- The UGC offers a unified account in which a concrete meta-algorithm is optimal across a broad problem class, addressing the recurring gap between algorithms and hardness proofs.The conjecture implies that no polynomial-time algorithm performs better on any problem in the class.Source: §1 · pp. 3–4
- UGC-based results match the UGC meta-algorithm’s guarantees across constraint-satisfaction problems, sparsest cut, and matrix correlation.For constraint-satisfaction problems, Raghavendra showed that the meta-algorithm gives the best estimate of the maximum satisfiable fraction of constraints.Source: §1 · p. 4
- The survey examines whether SOS can beat UGC-predicted guarantees, potentially improving known results and challenging the conjecture.The authors note that analyzing SOS guarantees remains difficult and that available tools are limited.Source: §1 · p. 4
1.1. The UGC and SSEH conjectures.
- SSEH conjectures that approximating the minimum expansion of small vertex sets is inherently difficult, where eigenvalue methods do not work well.It formalizes this as an NP-hard distinction between graphs with a small low-expansion set and graphs where every sufficiently small set has high expansion.Source: §1.1 · p. 5
- Assuming SSEH, Cheeger’s inequality gives an optimal approximation for minimum expansion, and the hypothesis also implies tight hardness for constraint-satisfaction and Grothendieck problems.The text says deriving quantitatively tight bounds from SSEH requires a highly non-trivial proof.Source: §1.1 · p. 5
- SSEH implies UGC, but whether the two conjectures are equivalent remains open; the authors suspect they are equivalent.Most, but not all, of the survey’s discussion applies to both conjectures.Source: §1.1 · pp. 5–6
1.2. Organization of this survey and further reading.
- The survey presents SOS, its relation to UGC and SSEH, and applications including planted sparse-vector recovery and sparse coding.It also discusses evidence for the conjectures and the relation to finding sparse vectors in arbitrary subspaces.Source: §1.2 · p. 6
- Unlike earlier UGC surveys, this one centers on whether UGC is true and on SOS beyond basic LP and SDP relaxations.Its SOS discussion emphasizes approximate solutions using very low degree, preferably constant or polylogarithmic, rather than exact convergence.Source: §1.2 · pp. 6–7
2. Sums of Squares Proofs and Algorithms
The section presents SOS refutations as certificates of unsatisfiability and turns bounded-degree certificates into an algorithm for polynomial optimization. It then uses the duality between SOS proofs and pseudodistributions to explain how approximation guarantees can be analyzed.
2. Sums of Squares Proofs and Algorithms
- An SOS refutation certifies that a polynomial system has no solution through an identity expressing −1 as a sum of squares plus a combination of its constraints.The Positivstellensatz gives this characterization of infeasibility.Source: §2 · p. 7
2.1. From proofs to algorithms.
- On the hypercube, a system is either satisfiable or has a degree-2n SOS refutation, although this degree bound is not computationally useful.Degree-2n refutations can be comparable in size to enumerating the hypercube.Source: §2 · p. 8
2. Sums of Squares Proofs and Algorithms
- A degree-ℓ SOS refutation can be found in mn^O(ℓ) time by solving a semidefinite program.The sum-of-squares condition is represented by a positive-semidefinite matrix constraint.Source: §2.1 · pp. 8–9
2.1. From proofs to algorithms.
- The degree-ℓ SOS estimate is computable in n^O(ℓ) time and lower-bounds the true minimum, with estimates nondecreasing as degree rises.For systems whose feasible set is {±1}^n, the sequence reaches the exact minimum by degree 2n.Source: §2.1 · pp. 9–10
2.2. Pseudodistributions and pseudoexpectations.
- A degree-ℓ pseudodistribution satisfies constraints through low-degree pseudoexpectations, enabling analysis that treats it like a distribution when the steps have low-degree SOS proofs.The method uses only low-degree moments, not sampling access to an actual distribution.Source: §2.2 · pp. 11, 13
- For explicitly bounded systems, exactly one of a degree-ℓ SOS refutation or a satisfying degree-ℓ pseudodistribution exists.The dual SOS algorithm searches for such a pseudodistribution; both forms run in n^O(ℓ) time.Source: §2.2 · pp. 12–13
3. Approximating expansion via sums of squares
The section frames graph expansion as an SOS optimization problem, relates degree-2 SOS to Cheeger’s inequality, and describes higher-degree guarantees for small-set expansion. Its proof of the degree-2 guarantee rounds a pseudodistribution by sampling a Gaussian with matching moments.
3. Approximating expansion via sums of squares
- Degree-2 SOS recovers Cheeger’s inequality for expansion, and examples show its estimate is tight; if SSEH holds, improving it requires degree at least n^Ω(1).The section identifies degree-2 SOS with the UGC meta-algorithm and the second-largest-eigenvalue approach.Source: §3 · pp. 13–14
- Degree-ℓ SOS with ℓ=n^τ beats the degree-2 bound for small-set expansion and yields a sub-exponential algorithm that extends to Unique Games, but still falls short of refuting SSEH and UGC.Here τ tends to zero with the SSEH parameter ε.Source: §3 · p. 14
3.1. Proof of Theorem 3.1.
- The proof rounds a pseudodistribution by sampling a Gaussian with matching first and second moments, then thresholds coordinates at 1/2 to produce a set.If the resulting set exceeds n/2 in size, the algorithm takes its complement.Source: §3.1 · p. 15
- The rounding analysis targets an expected cut size O(√(ϕdn)) while producing a set of size between n/3 and 2n/3 with constant probability.The proof analyzes small-variance and large-variance cases for the rounded coordinates.Source: §3.1 · pp. 15–16
4. Machine learning with Sum of Squares
This section applies SOS to two unsupervised-learning problems, sparse vector recovery and sparse dictionary learning. It develops recovery guarantees by analyzing deterministic polynomial constraints.
4.2. Sparse dictionary learning.
- Sparse dictionary learning seeks the unknown dictionary from samples y = Ax, where A has isotropic unit columns and x is drawn from a sparse-vector distribution.Earlier rigorous recovery guarantees required x to have fewer than √n nonzeros, whereas SOS applies when x has o(n) nonzero or significant entries.Source: §4 · pp. 16–17, §4.2 · p. 19
4.1. Sparse vector recovery.
- For sparse vector recovery, SOS recovers a sparse target from a subspace with d ≪ √n Gaussian directions, even when the target has fewer than εn coordinates.With probability close to 1, the algorithm outputs a unit vector whose squared correlation with the target is at least 1 − O(ε).Source: §4 · p. 16, §4.1 · p. 17
- The recovery approach encodes the target as a solution to polynomial equations, computes a degree-4 pseudodistribution, then samples a Gaussian vector matching its quadratic moments.The encoding uses unit norm and a projected ℓ4 constraint; the analysis combines a random-subspace projector property with a pseudodistribution argument.Source: §4.1 · pp. 17–18
4.2. Sparse dictionary learning.
- With n^O(1) independent samples and a (d, τ)-nice code distribution, a quasipolynomial-time algorithm recovers a set within Hausdorff distance ε of the dictionary columns.The theorem assumes a κ-overcomplete dictionary and succeeds with high probability.Source: §4.2 · p. 20
- The dictionary-learning analysis encodes columns as near-maximizers of a sample-based polynomial; degree-O(log n) SOS pseudodistributions can identify all such vectors.Reweighting by products of squared random linear forms isolates one column at a time, and the argument extends this isolation to pseudodistributions.Source: §4.2 · pp. 20–21
5. Hypercontractive norms and small-set expansion
Small-set expansion can be recast as finding sparse vectors in low-eigenvalue subspaces, linking a graph problem to polynomial optimization. The survey uses this connection to examine what SOS degree can certify and how stronger certificates could bear on SSEH and UGC.
5. Hypercontractive norms and small-set expansion
- Non-expanding small sets yield sparse vectors in low-eigenvalue subspaces, and sparse vectors in those subspaces yield small sets with expansion bounded by a constant below 1.The theorem gives both directions, with the resulting expansion bound depending on the subspace threshold.Source: §5 · p. 22
- The theorem reduces small-set expansion to bounding a polynomial over unit vectors in a subspace, the kind of optimization problem SOS is designed to address.The resulting question is what SOS degree is needed to certify a 2p-norm bound for every unit vector in the subspace.Source: §5 · p. 22
- For a random subspace of dimension much smaller than √n, the survey reports a degree-4 SOS certificate for the 4-norm bound, and says this is optimal for that setting.The 4-norm is not bounded when the dimension exceeds √n.Source: §5 · p. 22
- Any subspace of dimension d ≫ n^(1/p) contains an (o(1), p)-sparse vector.This existence result is stated as a consequence of Lemma 5.2.Source: §5 · pp. 22–23
- An O(n^(1/p))-degree SOS proof certifies the stated moment bound when the subspace satisfies the corollary's condition.The proof uses the dimension bound and the degree needed to approximately bound a constant-degree polynomial on the d-dimensional sphere [DW12].Source: §5 · p. 23
- Degree n^τ SOS proofs distinguish the stated small-set expansion cases in exp(O(n^τ)) time; improving τ to tend to zero with n for fixed ε would essentially refute SSEH and UGC.The current running time is described as much better than enumerating all possible sets.Source: §5 · p. 23
- Earlier hard instances used to support UGC and SSEH can be solved by constant-degree SOS, though this does not rule out other instances that are hard for that algorithm.The survey notes that no such reasonably conjectured hard instance was then known for the problems underlying the two conjectures.Source: §5 · p. 24