An Argmax Principle for Sum-of-Squares Relaxations on the Sphere
2026-08-03 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors develop a new principle called the argmax principle to better understand sum-of-squares (SoS) methods for optimization problems on the unit sphere. They show that examining certain high-degree polynomial expressions helps identify good approximate solutions, simplifying and unifying previous analyses. Using this idea, they improve approximation results for problems like the Best Separable State, matrix 2-to-4 norm estimation, and polynomial optimization, sometimes matching known hardness limits. Their approach does not create new relaxations but offers a clearer way to interpret SoS solutions with simpler or stronger results.
sum-of-squares (SoS) relaxationpseudo-expectationhigh-order pseudo-momentsBest Separable Statematrix 2-to-4 normpolynomial optimizationargmax principleapproximation algorithmsQMA(2) complexityExponential-Time Hypothesis
Authors
Fernando Jeronimo Granha, Pei Wu, Haochen Xu
Abstract
We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of high-order pseudo-moments, such as $Φ_k(u)=\widetilde{\mathbb E}\langle x,u\rangle^{2k}$. Our guiding principle is that its maximizers are rounding candidates: their local and global optimality conditions reveal the reweighed pseudo-expectation inequalities governing SoS convergence. This viewpoint unifies several problems previously analyzed by rather different techniques. We obtain three results. First, for Best Separable State, we give a degree-$O(\sqrt{n/ε})$ SoS analysis for approximating $h_{\mathrm{sep}}(P)$ in the perfect-completeness regime, improving and simplifying Barak, Kothari and Steurer (STOC'17). The dependence is essentially tight for inverse-linear gap under the Exponential-Time Hypothesis, matching hardness from $\mathrm{QMA}(2)$ protocols. Second, for the matrix $2\to4$ norm, degree-$O(\sqrt n/ε)$ SoS gives a multiplicative $(1+ε)$ approximation. Barak et al. (STOC'12) previously gave a comparable-time constant-gap decision algorithm; our result gives a multiplicative guarantee and extends to a family of $p\to q$ norms with even $q$. Finally, for degree-$d$ polynomial optimization, we recover the convergence theorem of Bhattiprolu et al. (FOCS'17) with a shorter, more direct proof: degree-$k$ SoS gives approximation ratio $O_d((n/k)^{d/2-1})$. The paper introduces no new relaxation. Instead, the high-moment argmax gives a common way to read an SoS solution, unifying previously separate convergence analyses and yielding sharper bounds or simpler proofs.