# Low-Rank Univariate Sum of Squares Has No Spurious Local Minima

arXiv: https://arxiv.org/abs/2205.11466 · HTML: https://mlsanity.com/paper/2205.11466/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2022.

## Built on by (most cited first, 2 of 2)

- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)
- [A practical, fast method for solving sum-of-squares problems for very large polynomials](https://mlsanity.com/paper/2410.19844/) (2024)

## Abstract (arXiv)

We study the problem of decomposing a polynomial p into a sum of r squares by minimizing a quadratically penalized objective fp(u) = leftlVert sumi=1r ui2 - prightlVert2. This objective is nonconvex and is equivalent to the rank-r Burer-Monteiro factorization of a semidefinite program (SDP) encoding the sum of squares decomposition. We show that for all univariate polynomials p, if r ≥ 2 then fp(u) has no spurious second-order critical points, showing that all local optima are also global optima. This is in contrast to previous work showing that for general SDPs, in addition to genericity conditions, r has to be roughly the square root of the number of constraints (the degree of p) for there to be no spurious second-order critical points. Our proof uses tools from computational algebraic geometry and can be interpreted as constructing a certificate using the first- and second-order necessary conditions. We also show that by choosing a norm based on sampling equally-spaced points on the circle, the gradient nabla fp can be computed in nearly linear time using fast Fourier transforms. Experimentally we demonstrate that this method has very fast convergence using first-order optimization algorithms such as L-BFGS, with near-linear scaling to million-degree polynomials.