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

Abstract

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

References in corpus (28)

• Message Passing Algorithms for Compressed Sensing
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Universality in polytope phase transitions and message passing algorithms
• A framework to characterize performance of LASSO algorithms
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Alternating Minimization for Mixed Linear Regression
• Phaseless Rcovery using Gauss-Newton Method
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning
• Symbol Error Rate Performance of Box-relaxation Decoders in Massive MIMO
• The Lasso with general Gaussian designs with applications to hypothesis testing
• Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization
• From Symmetry to Geometry: Tractable Nonconvex Problems
• The Impact of Regularization on High-dimensional Logistic Regression
• Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms
• A Precise Performance Analysis of Learning with Random Features
• Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• Instability, Computational Efficiency and Statistical Accuracy
• Regularly random duality
• Provable Benefits of Overparameterization in Model Compression: From Double Descent to Pruning Neural Networks
• Asymptotic Behavior of Adversarial Training in Binary Classification