Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
arXiv:1910.12837
Abstract
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.
References in corpus (11)
- A Convergence Theory for Deep Learning via Over-Parameterization
- A Mean Field View of the Landscape of Two-Layers Neural Networks
- Time-uniform Chernoff bounds via nonnegative supermartingales
- Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
- On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
- Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
- An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
- Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
- Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
- Convergence of the randomized Kaczmarz method for phase retrieval
- Online ICA: Understanding Global Dynamics of Nonconvex Optimization via Diffusion Processes
Cited by in corpus (7)
- An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
- Learning a Single Neuron with Gradient Methods
- SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
- Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
- Phase retrieval of complex-valued objects via a randomized Kaczmarz method
- Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
- Stochastic Approximation for Online Tensorial Independent Component Analysis