Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
Authors:
- Vijay BhattiproluVBVijay Bhattiprolu
- Mrinalkanti GhoshMGMrinalkanti Ghosh
- Venkatesan GuruswamiVGVenkatesan Guruswami
- Euiwoong LeeELEuiwoong Lee
- Madhur TulsianiMTMadhur Tulsiani
Preprint
Abstract
We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x \in \mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in diverse contexts ranging from tensor and operator norms to graph expansion to quantum information theory. The homogeneous degree $2$ case is efficiently solvable as it corresponds to computing the spectral norm of an associated matrix, but the higher degree case is NP-hard. We give approximation algorithms for this problem that offer a trade-off between the approximation ratio and running time: in $n^{O(q)}$ time, we get an approximation within factor $O_d((n/q)^{d/2-1})$ for arbitrary polynomials, $O_d((n/q)^{d/4-1/2})$ for polynomials with non-negative coefficients, and $O_d(\sqrt{m/q})$ for sparse polynomials with $m$ monomials. The approximation guarantees are with respect to the optimum of the level-$q$ sum-of-squares (SoS) SDP relaxation of the problem. Known polynomial time algorithms for this problem rely on "decoupling lemmas." Such tools are not capable of offering a trade-off like our results as they blow up the number of variables by a factor equal to the degree. We develop new decoupling tools that are more efficient in the number of variables at the expense of less structure in the output polynomials. This enables us to harness the benefits of higher level SoS relaxations. We complement our algorithmic results with some polynomially large integrality gaps, albeit for a slightly weaker (but still very natural) relaxation. Toward this, we give a method to lift a level-$4$ solution matrix $M$ to a higher level solution, under a mild technical condition on $M$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Convergence analysis for Lasserre’s measure-based hierarchy of upper bounds for polynomial optimizationMathematical Programming, 2016
- On the variational problem for upper tails in sparse random graphsRandom Structures & Algorithms, 2016
- An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplexMathematical Programming, 2014
- Tight upper tail bounds for cliquesRandom Structures & Algorithms, 2012
- Upper tails for trianglesRandom Structures & Algorithms, 2011
- The missing log in large deviations for triangle countsRandom Structures & Algorithms, 2011
- Linear Equations Modulo 2 and the $L_1$ Diameter of Convex BodiesSIAM Journal on Computing, 2008
- A PTAS for the minimization of polynomials of fixed degree over the simplexTheoretical Computer Science, 2006
- Upper tails for subgraph counts in random graphsIsrael Journal of Mathematics, 2004
- On the advantage over a random assignmentRandom Structures & Algorithms, 2004