An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

This paper addresses the challenge of analyzing the convergence of Sum-of-Squares (SoS) hierarchies for optimization problems over the unit sphere. While SoS is a powerful tool, different problems—such as quantum separability, matrix norm approximation, and general polynomial optimization—have historically required disparate analytical techniques. The authors propose a unified framework based on an 'argmax principle': given a feasible pseudo-expectation, they construct a high-moment auxiliary polynomial (e.g., the expected value of the inner product to the power of 2k) and use its maximizers to extract structural information about the pseudo-distribution. This approach transforms the problem of proving SoS convergence into an analysis of the local and global optimality conditions of this auxiliary polynomial.

The paper demonstrates the versatility of the argmax principle through three primary applications:

1. Best Separable State (BSS): The authors provide a degree-O(sqrt(n/epsilon)) SoS analysis for the perfect-completeness BSS gap problem. This improves upon previous results and is shown to be essentially tight under the Exponential-Time Hypothesis (ETH), matching the hardness results derived from QMA(2) protocols.

2. Matrix p-to-q Norms: For the matrix 2-to-4 norm (and more generally p-to-q norms with even q), the authors show that degree-O(sqrt(n/epsilon)) SoS yields a multiplicative (1+epsilon) approximation. This improves upon prior work that only provided decision algorithms for constant-gap instances.

3. General Polynomial Optimization: The authors recover the convergence theorem for degree-d polynomials over the sphere with a significantly shorter and more direct proof than previous methods, achieving an approximation ratio of O_d((n/k)^(d/2-1)) for degree-k SoS.

By providing a common analytical object—the high-moment argmax—the authors unify several previously disconnected areas of theoretical computer science and quantum complexity. This framework not only simplifies complex proofs but also yields sharper bounds and, in some cases, suggests efficient rounding procedures. The results demonstrate that the argmax principle is a robust tool for understanding SoS convergence, potentially applicable to a wider range of problems in robust statistics and high-dimensional optimization.