Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
From MaRDI portal
Publication:2425162
Abstract: This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest from quadratic equations/samples , . 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 -accurate solution in 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.
Recommendations
- On global convergence of gradient descent algorithms for generalized phase retrieval problem
- Phase Retrieval by Alternating Minimization With Random Initialization
- Convolutional Phase Retrieval via Gradient Descent
- Scalable incremental nonconvex optimization approach for phase retrieval
- Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Variational phase retrieval with globally convergent preconditioned proximal algorithm
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Phase retrieval via randomized Kaczmarz: theoretical guarantees
- PhaseEqual: Convex Phase Retrieval via Alternating Direction Method of Multipliers
Cites work
- scientific article; zbMATH DE number 204193 (Why is no real title available?)
- A nonconvex approach for phase retrieval: reshaped Wirtinger flow and incremental algorithms
- Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
- Blind deconvolution by a steepest descent algorithm on a quotient manifold
- Compressive Phase Retrieval via Reweighted Amplitude Flow
- Concentration and moment inequalities for polynomials of independent random variables
- Convolutional Phase Retrieval via Gradient Descent
- Cubic regularization of Newton method and its global performance
- Entrywise eigenvector analysis of random matrices with low expected rank
- Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
- Fast rank-one alternating minimization algorithm for phase retrieval
- Fundamental limits of weak recovery with applications to phase retrieval
- 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
- Low rank matrix recovery from rank one measurements
- Matrix Completion From a Few Entries
- Misspecified nonconvex statistical optimization for sparse phase retrieval
- Near-optimal bounds for phase synchronization
- Non-Convex Phase Retrieval From STFT Measurements
- Nonconvex Matrix Factorization From Rank-One Measurements
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- On robust regression with high-dimensional predictors
- On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators
- Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow
- Optimization-Based AMP for Phase Retrieval: The Impact of Initialization and $\ell_{2}$ Regularization
- Phase Retrieval Using Alternating Minimization
- Phase retrieval via Wirtinger flow: theory and algorithms
- Phase retrieval via matrix completion
- Phase retrieval via randomized Kaczmarz: theoretical guarantees
- Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- ROP: matrix recovery via rank-one projections
- Rapid, robust, and reliable blind deconvolution via nonconvex optimization
- Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points
- Saving phase: injectivity and stability for phase retrieval
- Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
- Solving quadratic equations via phaselift when there are about as many equations as unknowns
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- Sparse and Low-Rank Tensor Estimation via Cubic Sketchings
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Stable optimizationless recovery from phaseless linear measurements
- Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization
- The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square
- The projected power method: an efficient algorithm for joint alignment from pairwise differences
- Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks
Cited in
(50)- Wasserstein F-tests for Fréchet regression on Bures-Wasserstein manifolds
- The numerics of phase retrieval
- Nearly optimal bounds for the global geometric landscape of phase retrieval
- scientific article; zbMATH DE number 7626752 (Why is no real title available?)
- An oracle gradient regularized Newton method for quadratic measurements regression
- Complex phase retrieval from subgaussian measurements
- Phase retrieval via randomized Kaczmarz: theoretical guarantees
- Solving systems of quadratic equations via exponential-type gradient descent algorithm
- Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Asymptotic Properties of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Fast gradient method for low-rank matrix estimation
- scientific article; zbMATH DE number 7415089 (Why is no real title available?)
- Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
- Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
- Tensor factorization recommender systems with dependency
- Scalable incremental nonconvex optimization approach for phase retrieval
- Sharp global convergence guarantees for iterative nonconvex optimization with random data
- Provable Phase Retrieval with Mirror Descent
- Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
- A new complexity metric for nonconvex rank-one generalized matrix completion
- scientific article; zbMATH DE number 7370623 (Why is no real title available?)
- A selective overview of deep learning
- Anisotropic diffusion in consensus-based optimization on the sphere
- Tilting the odds at the lottery: the interplay of overparameterisation and curricula in neural networks
- Multicategory Angle-Based Learning for Estimating Optimal Dynamic Treatment Regimes With Censored Data
- The power of preconditioning in overparameterized low-rank matrix sensing
- The global landscape of phase retrieval. II: Quotient intensity models
- On the convergence of mirror descent beyond stochastic convex programming
- The global landscape of phase retrieval. I: Perturbed amplitude models
- A nonconvex approach for phase retrieval: reshaped Wirtinger flow and incremental algorithms
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Sparse signal recovery from phaseless measurements via hard thresholding pursuit
- On global convergence of gradient descent algorithms for generalized phase retrieval problem
- Convolutional Phase Retrieval via Gradient Descent
- Consensus-based optimization on hypersurfaces: Well-posedness and mean-field limit
- Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
- Nonconvex Low-Rank Tensor Completion from Noisy Data
- Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
- The local convexity of solving systems of quadratic equations
- Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
- Recent Theoretical Advances in Non-Convex Optimization
- On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
- Improved global guarantees for the nonconvex Burer-Monteiro factorization via rank overparameterization
- Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
- Homomorphic sensing of subspace arrangements
- Inference for heteroskedastic PCA with missing data
- Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in \(O(\sqrt{n})\) iterations
This page was built for publication: Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425162)
