Skip to main content

Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval

Author(s): Chen, Yuxin; Chi, Y; Fan, Jianqing; Ma, C

To refer to this page use:
Abstract: © 2019, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society. This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest x♮∈ Rn from m quadratic equations/samples yi=(ai⊤x♮)2,1≤i≤m. This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficacy 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 O(log n+ log (1 / ϵ)) 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.
Publication Date: 1-Jul-2019
Citation: Chen, Y, Chi, Y, Fan, J, Ma, C. (2019). Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval. Mathematical Programming, 176 (1-2), 5 - 37. doi:10.1007/s10107-019-01363-6
DOI: doi:10.1007/s10107-019-01363-6
ISSN: 0025-5610
EISSN: 1436-4646
Pages: 5 - 37
Type of Material: Journal Article
Journal/Proceeding Title: Mathematical Programming
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.