Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective

We consider a general class of regression models with normally distributed\ncovariates, and the associated nonconvex problem of fitting these models from\ndata. We develop a general recipe for analyzing the convergence of iterative\nalgorithms for this task from a random initialization. In particular, provided\neach iteration can be written as the solution to a convex optimization problem\nsatisfying some natural conditions, we leverage Gaussian comparison theorems to\nderive a deterministic sequence that provides sharp upper and lower bounds on\nthe error of the algorithm with sample-splitting. Crucially, this deterministic\nsequence accurately captures both the convergence rate of the algorithm and the\neventual error floor in the finite-sample regime, and is distinct from the\ncommonly used "population" sequence that results from taking the\ninfinite-sample limit. We apply our general framework to derive several\nconcrete consequences for parameter estimation in popular statistical models\nincluding phase retrieval and mixtures of regressions. Provided the sample size\nscales near-linearly in the dimension, we show sharp global convergence rates\nfor both higher-order algorithms based on alternating updates and first-order\nalgorithms based on subgradient descent. These corollaries, in turn, yield\nmultiple consequences, including: (a) Proof that higher-order algorithms can\nconverge significantly faster than their first-order counterparts (and\nsometimes super-linearly), even if the two share the same population update and\n(b) Intricacies in super-linear convergence behavior for higher-order\nalgorithms, which can be nonstandard (e.g., with exponent 3/2) and sensitive to\nthe noise level in the problem. We complement these results with extensive\nnumerical experiments, which show excellent agreement with our theoretical\npredictions.\n