mlsanityData to 7 Oct 2026

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

arXiv 1803.07726 ↗First posted 21 Mar 2018stat.ML cs.IT cs.LGcited by 71

Not on the map. Why?

Abstract (arXiv)

This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest xnatural∈ℝn from m quadratic equations/samples yi=(aitopxnatural)2, 1≤ i≤ 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 ε-accurate solution in Obig(log n+log(1/ε)big) 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.

Key facts. Cited by 71 papers in the map (data through 7 Oct 2026). First posted on arXiv 21 Mar 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 16; 2023: 13; 2024: 13; 2025: 6; 2026: 6.

71 papers.

Sort:

By area:

  1. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  2. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  3. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  4. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  5. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  6. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  7. 2021Sample Efficient Linear Meta-Learning by Alternating Minimizationcited by 25
  8. 2021Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problemcited by 23
  9. 2024Bayes-optimal learning of an extensive-width neural network from quadratically many samplescited by 23
  10. 2021Inference for Heteroskedastic PCA with Missing Datacited by 21
  11. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  12. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
38 more
  1. 2021Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priorscited by 14
  2. 2023Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGDcited by 14
  3. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  4. 2021Submodular + Concavecited by 13
  5. 2022Learning a Single Neuron for Non-monotonic Activation Functionscited by 13
  6. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  7. 2021Bandit Phase Retrievalcited by 12
  8. 2023Convergence of Alternating Gradient Descent for Matrix Factorizationcited by 12
  9. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  10. 2022Model-Based Reinforcement Learning for Offline Zero-Sum Markov Gamescited by 11
  11. 2022Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energycited by 9
  12. 2023Approximate message passing from random initialization with applications to mathbbZ2 synchronizationcited by 9
  13. 2024Tilting the Odds at the Lottery: the Interplay of Overparameterisation and Curricula in Neural Networkscited by 9
  14. 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
  15. 2022Misspecified Phase Retrieval with Generative Priorscited by 7
  16. 2021Tensor train completion: local recovery guarantees via Riemannian optimizationcited by 6
  17. 2021Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descentcited by 5
  18. 2022Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decompositioncited by 5
  19. 2022From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descentcited by 5
  20. 2021Nonparametric Modeling of Higher-Order Interactions via Hypergraphonscited by 4
  21. 2022Robust Matrix Completion with Heavy-tailed Noisecited by 4
  22. 2022Rank-1 Matrix Completion with Gradient Descent and Small Random Initializationcited by 4
  23. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  24. 2022An Algebraically Converging Stochastic Gradient Descent Algorithm for Global Optimizationcited by 3
  25. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
  26. 2023Near Optimal Heteroscedastic Regression with Symbiotic Learningcited by 3
  27. 2024Gradient-based Learning in State-based Potential Games for Self-Learning Production Systemscited by 3
  28. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  29. 2021Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensingcited by 2
  30. 2021Efficient Sparse Coding using Hierarchical Riemannian Pursuitcited by 2
  31. 2022Provable Phase Retrieval with Mirror Descentcited by 2
  32. 2023Gradient descent in matrix factorization: Understanding large initializationcited by 2
  33. 2023Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minimacited by 2
  34. 2024Top-K ranking with a monotone adversarycited by 2
  35. 2024In-depth Analysis of Low-rank Matrix Factorisation in a Federated Settingcited by 2
  36. 2026NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronizationcited by 2
  37. 2026Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networkscited by 2
  38. 2022Variational Bayesian inference for CP tensor completion with side informationcited by 1

50 most cited of 71 All 71 (JSON)