Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
复制标题
DOI：
10.1007/s10208-019-09429-9
复制
发表时间：
2017-11
影响因子：
3
通讯作者：
Cong Ma;Kaizheng Wang;Yuejie Chi;Yuxin Chen
中科院分区：
文献类型：
--
作者：
Cong Ma;Kaizheng Wang;Yuejie Chi;Yuxin Chen
近年来，在设计可证明有效的非凸优化程序以解决统计估计问题方面，出现了一系列的活动。对于像相位恢复或低阶矩阵补全这样的各种问题，最先进的非凸算法需要适当的正则化(如裁剪、正则化代价、投影)以保证快速收敛。然而，当涉及到诸如梯度下降之类的普通程序时，先前的理论要么建议高度保守的学习速度以避免超调，要么完全缺乏性能保证。本文揭示了几个非凸问题中的一个显著现象：即使在没有显式正则化的情况下，梯度下降也遵循一个停留在具有良好几何形状的盆地内的轨迹，该轨迹由与采样机制不一致的点组成。这种“隐式正则化”特性允许梯度下降以一种更具侵略性的方式进行，而不会超调，这反过来又会带来大量的计算节省。集中于两个统计估计问题，即求解随机二次方程组和低阶矩阵补全，我们证明了在没有显式正则化的情况下，梯度下降获得了近最优的统计和计算保证。作为副产品，对于有噪声的矩阵补全，我们证明了梯度下降能够实现入口型和谱型范数误差的最优控制。
Recent years have seen a flurry of activities in designing provably efficient nonconvex optimization procedures for solving statistical estimation problems. For various problems like phase retrieval or low-rank matrix completion, state-of-the-art nonconvex procedures require proper regularization (eg trimming, regularized cost, projection) in order to guarantee fast convergence. When it comes to vanilla procedures such as gradient descent, however, prior theory either recommends highly conservative learning rates to avoid overshooting, or completely lacks performance guarantees. This paper uncovers a striking phenomenon in several nonconvex problems: even in the absence of explicit regularization, gradient descent follows a trajectory staying within a basin that enjoys nice geometry, consisting of points incoherent with the sampling mechanism. This “implicit regularization” feature allows gradient descent to proceed in a far more aggressive fashion without overshooting, which in turn results in substantial computational savings. Focusing on two statistical estimation problems, ie solving random quadratic systems of equations and low-rank matrix completion, we establish that gradient descent achieves near-optimal statistical and computational guarantees without explicit regularization. As a byproduct, for noisy matrix completion, we demonstrate that gradient descent enables optimal control of both entrywise and spectral-norm errors.