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

Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma

Abstract

This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest $\mathbf{x}^{\natural}\in\mathbb{R}^{n}$ from $m$ quadratic equations/samples $y_{i}=(\mathbf{a}_{i}^{\top}\mathbf{x}^{\natural})^{2}$, $1\leq i\leq 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\big(\log n+\log(1/\epsilon)\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.

Introduction

Phase retrieval is a fundamental problem in physical sciences, such as X-ray crystallography, and machine learning. The goal is to recover a hidden signal $\mathbf{x}^{\natural}$ from the intensity of its linear measurements, represented by the system of quadratic equations $y_i = (\mathbf{a}_i^\top \mathbf{x}^{\natural})^2$. Because the loss surface for this problem is non-convex, it is traditionally plagued by saddle points and local minima.

Previous approaches often relied on "spectral initialization"—a computationally expensive pre-processing step to find a starting point close to the global optimum. This research investigates whether such complexity is necessary, proving that vanilla gradient descent (GD), starting from a completely random initialization, can reliably and efficiently find the global solution.

Methodology: Vanilla Gradient Descent and Leave-One-Out Analysis

The study focuses on the efficiency of Wirtinger Flow, which is essentially vanilla gradient descent applied to the non-convex least squares objective. The primary challenge in analyzing GD for non-convex problems is the statistical dependency that develops between the iterates and the data.

To overcome this, the authors employ a "leave-one-out" analysis. By constructing auxiliary sequences that omit a single measurement, they demonstrate that the true GD iterates remain "incoherent" with the measurement vectors. This decoupling allows for a rigorous proof that the algorithm avoids bad regions of the landscape and converges to the global minimizer without requiring sample splitting or specialized initialization.

Analysis of Convergence

The convergence of randomly initialized GD occurs in two distinct stages. In Stage 1, the error relative to the ground truth may appear stagnant, but the correlation (inner product) between the iterate and the signal grows exponentially. Once this "signal strength" reaches a critical threshold, the algorithm enters Stage 2, where the error decays geometrically to zero.

Figure 2: The two-stage convergence process. Initially, the inner product grows while the distance remains high (Stage 1), followed by rapid geometric convergence (Stage 2).

A critical finding is that saddle points do not hinder progress. The optimization landscape for phase retrieval is such that GD naturally follows a path that distances itself from these unstable points almost immediately.

Figure 5: Optimization trajectories showing how gradient descent iterates move away from saddle points toward the global minimizer.

Key Results

The theoretical analysis yields several near-optimal guarantees:

  • Computational Complexity: The algorithm achieves an $\epsilon$-accurate solution in $O(\log n + \log(1/\epsilon))$ iterations, matching the efficiency of convex optimization.
  • Sample Efficiency: Global convergence is guaranteed with nearly minimal samples, $m \gtrsim n \text{ poly log } m$.
  • Implicit Regularization: GD stays within a "benign" region of the search space automatically, removing the need for artificial truncation or regularization tricks.

Numerical experiments confirm these findings. For instance, with $n=1000$ unknowns, randomly initialized GD consistently achieves high precision within 200 iterations, performing as well as methods using sophisticated initializations.

Limitations and Future Work

While this work provides a breakthrough for vanilla GD, some open questions remain. The current proof requires a sample size $m$ scaled by a high power of $\log m$, which is likely a technical artifact rather than a fundamental limit. Additionally, while the core theory focuses on the noiseless Gaussian case, future work aims to extend these rigorous global convergence guarantees to more structured measurement matrices and noisy real-world data.

Summary updated

Abstract

This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest $\mathbf{x}^{\natural}\in\mathbb{R}^{n}$ from $m$ quadratic equations/samples $y_{i}=(\mathbf{a}_{i}^{\top}\mathbf{x}^{\natural})^{2}$, $1\leq i\leq 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\big(\log n+\log(1/\epsilon)\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.
BibTeX
@inproceedings{chen2019gradient,
  author = {Yuxin Chen and Yuejie Chi and Jianqing Fan and Cong Ma},
  title = {{Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval}},
  booktitle = {Math. Program},
  year = {2019},
  url = {https://openreview.net/forum?id=oAwpeQxpEk2},
}
Figure