Title: Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval,
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.