Low-Rank Sum of Squares Has No Spurious Local Minima

We study the problem of decomposing a polynomial into a sum of r squares by optimizing the objective fₚ(u) = ‖∑ᵢ uᵢ² - p‖². 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 fₚ(u) has no spurious second-order critical points (SOCPs), 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 for there to be no spurious SOCPs. Our proof uses tools from computational algebraic geometry and can be interpreted as constructing a certificate of no spurious SOCPs using the first and second-order necessary conditions. In addition, choosing a norm based on sampling equally-spaced points on the circle, the gradient ∇fₚ can be computed in nearly linear time using fast Fourier transforms. Experimentally we show that this method has very good convergence properties using first-order optimization algorithms such as L-BFGS, easily scaling to million-degree polynomials.

This will be a whiteboard talk in which I will outline the proof of the main theorem and elaborate on the certificate interpretation. This talk is based on joint work with Benoît Legat and Pablo Parrilo.