Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval

Abstract

This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest ${\mathbf{x}}^{♮}\in {\mathbb{R}}^n$ from $m$ quadratic equations/samples $y_i=({\mathbf{a}}_i^{\top }{\mathbf{x}}^{♮}{)}^2$, $1\le i\le m$. This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficiency of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient descent --- when randomly initialized --- yields an $\epsilon$-accurate solution in $O(\log n+\log (1/\epsilon ))$ iterations given nearly minimal samples, thus achieving near-optimal computational and sample complexities at once. This provides the first global convergence guarantee concerning vanilla gradient descent for phase retrieval, without the need of (i) carefully-designed initialization, (ii) sample splitting, or (iii) sophisticated saddle-point escaping schemes. All of these are achieved by exploiting the statistical models in analyzing optimization algorithms, via a leave-one-out approach that enables the decoupling of certain statistical dependency between the gradient descent iterates and the data.

arXiv commentAccepted to Mathematical Programming

References in corpus (3)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Guaranteed Matrix Completion via Non-convex Factorization
• ROP: Matrix recovery via rank-one projections

Cited by in corpus (23)

• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• The Numerics of Phase Retrieval
• Consensus-Based Optimization on Hypersurfaces: Well-Posedness and Mean-Field Limit
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Sparse Signal Recovery from Phaseless Measurements via Hard Thresholding Pursuit
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• Sample-Efficient Sparse Phase Retrieval via Stochastic Alternating Minimization
• Tensor train completion: local recovery guarantees via Riemannian optimization
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• NoncovANM: Gridless DOA Estimation for LPDF System
• Extended Successive Convex Approximation for Phase Retrieval with Dictionary Learning
• Homomorphic Sensing of Subspace Arrangements
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• The landscape of deterministic and stochastic optimal control problems: One-shot Optimization versus Dynamic Programming
• SPRING: an effective and reliable framework for image reconstruction in single-particle Coherent Diffraction Imaging
• Provable Phase Retrieval with Mirror Descent
• Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima