Speaker: 袁晨阳

Title: Low-rank Univariate Sum of Squares has no Spurious Local Minima

Language: Chinese

Time & Venue: 2024.06.04 10:00-11:00 Zoom会议号: 835 6580 1088 密码: 821461

Abstract: We study the problem of decomposing a polynomial p into a sum of r squares by minimizing 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 (the degree of p) 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. We also show that by 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 demonstrate that this method has very fast convergence using first-order optimization algorithms such as L-BFGS, with near-linear scaling (in terms of problem input size) to million-degree polynomials.