# Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval

arXiv: https://arxiv.org/abs/1910.12837 · HTML: https://mlsanity.com/paper/1910.12837/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2019.

## Built on by (most cited first, 30 of 34)

- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks](https://mlsanity.com/paper/2202.00293/) (2022)
- [Grokking as a First Order Phase Transition in Two Layer Networks](https://mlsanity.com/paper/2310.03789/) (2023)
- [From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks](https://mlsanity.com/paper/2302.05882/) (2023)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem](https://mlsanity.com/paper/2103.04902/) (2021)
- [Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs](https://mlsanity.com/paper/2306.16921/) (2023)
- [Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time](https://mlsanity.com/paper/2306.16361/) (2023)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGD](https://mlsanity.com/paper/2305.18502/) (2023)
- [Masks, Signs, And Learning Rate Rewinding](https://mlsanity.com/paper/2402.19262/) (2024)
- [Learning a Single Neuron for Non-monotonic Activation Functions](https://mlsanity.com/paper/2202.08064/) (2022)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance](https://mlsanity.com/paper/2304.00707/) (2023)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrieval](https://mlsanity.com/paper/2601.22652/) (2026)
- [From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent](https://mlsanity.com/paper/2210.06705/) (2022)
- [Max-affine regression via first-order methods](https://mlsanity.com/paper/2308.08070/) (2023)
- [Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffs](https://mlsanity.com/paper/2406.02157/) (2024)
- [Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data](https://mlsanity.com/paper/2511.18661/) (2025)
- [Universality of high-dimensional scaling limits of stochastic gradient descent](https://mlsanity.com/paper/2512.13634/) (2025)
- [On Uniform Boundedness Properties of SGD and its Momentum Variants](https://mlsanity.com/paper/2201.10245/) (2022)
- [Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression](https://mlsanity.com/paper/2302.09727/) (2023)
- [A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval](https://mlsanity.com/paper/2409.04733/) (2024)
- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [Limit Theorems for Stochastic Gradient Descent in High-Dimensional Single-Layer Networks](https://mlsanity.com/paper/2511.02258/) (2025)
- [OLR-WA: Online Weighted Average Linear Regression in Multivariate Data Streams](https://mlsanity.com/paper/2512.14892/) (2025)
- [Interactive Learning of Single-Index Models via Stochastic Gradient Descent](https://mlsanity.com/paper/2602.17876/) (2026)
- [Escape dynamics and implicit bias of one-pass SGD in overparameterized quadratic networks](https://mlsanity.com/paper/2604.03068/) (2026)

## Abstract (arXiv)

In recent literature, a general two step procedure has been formulated for solving the problem of phase retrieval. First, a spectral technique is used to obtain a constant-error initial estimate, following which, the estimate is refined to arbitrary precision by first-order optimization of a non-convex loss function. Numerical experiments, however, seem to suggest that simply running the iterative schemes from a random initialization may also lead to convergence, albeit at the cost of slightly higher sample complexity. In this paper, we prove that, in fact, constant step size online stochastic gradient descent (SGD) converges from arbitrary initializations for the non-smooth, non-convex amplitude squared loss objective. In this setting, online SGD is also equivalent to the randomized Kaczmarz algorithm from numerical analysis. Our analysis can easily be generalized to other single index models. It also makes use of new ideas from stochastic process theory, including the notion of a summary state space, which we believe will be of use for the broader field of non-convex optimization.