Global Optimality of Local Search for Low Rank Matrix Recovery
Global Optimality of Local Search for Low Rank Matrix Recovery
复制标题
DOI：
--
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Srinadh Bhojanapalli;Behnam Neyshabur;N. Srebro
中科院分区：
文献类型：
--
作者：
Srinadh Bhojanapalli;Behnam Neyshabur;N. Srebro
我们证明了在非相干线性测量的低秩矩阵恢复的非凸分解参数化中不存在伪局部极小值。通过噪声测量，我们发现所有的局部最小值都非常接近全局最优值。结合鞍点处的曲率界，给出了随机梯度下降{\em从随机初始化}的多项式时间全局收敛保证。
We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial time global convergence guarantee for stochastic gradient descent {\em from random initialization}.