Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval.
Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval.
复制标题
DOI：
10.1007/s10107-019-01363-6
复制
发表时间：
2019-07
影响因子：
2.7
通讯作者：
Ma C
中科院分区：
文献类型：
--
作者：
Chen Y;Chi Y;Fan J;Ma C
本文研究了二次方程组的求解问题，即从m个二次方程/样本中恢复一个感兴趣的对象。这个问题，也被称为相位检索，跨越多个领域，包括物理科学和机器学习。我们调查的效率梯度下降（或Wirtinger流）设计的非凸最小二乘问题。我们证明了高斯设计下，梯度下降-随机初始化时-产生一个精确的解决方案，在O（log n + log（1/n））迭代几乎最小的样本，从而实现接近最佳的计算和样本的复杂性一次。这提供了关于相位恢复的香草梯度下降的第一个全局收敛保证，而不需要（i）精心设计的初始化，（ii）样本分裂，或（iii）复杂的鞍点逃逸方案。所有这些都是通过在分析优化算法时利用统计模型来实现的，通过一种留一法，使梯度下降迭代和数据之间的某些统计依赖性解耦。
This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest from m quadratic equations/samples . 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.