Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Chong You;Zhihui Zhu;Qing Qu;Yi Ma
中科院分区：
文献类型：
--
作者：
Chong You;Zhihui Zhu;Qing Qu;Yi Ma
最近的进展表明，隐式偏置梯度下降过参数化模型，使低秩矩阵的线性测量恢复，即使没有先验知识的内在秩。相比之下，对于从严重损坏的测量中恢复的鲁棒低秩矩阵，过度参数化导致过度拟合，而无需关于损坏的固有秩和稀疏性的先验知识。本文表明，与双过参数化的低秩矩阵和稀疏腐败，梯度下降有差异的学习率可证明恢复的基础矩阵，即使没有先验知识的秩矩阵也稀疏腐败。我们进一步扩展了我们的方法，通过使用深度卷积网络对图像进行过度参数化来实现自然图像的鲁棒恢复。实验表明，我们的方法处理不同的测试图像和不同的腐败水平与一个单一的学习管道，网络宽度和终止条件不需要根据具体情况进行调整。成功的基础再次是隐式偏差，不同的过度参数化的参数，这可能会影响更广泛的应用上的学习率不一致。
Recent advances have shown that implicit bias of gradient descent on over-parameterized models enables the recovery of low-rank matrices from linear measurements, even with no prior knowledge on the intrinsic rank. In contrast, for robust low-rank matrix recovery from grossly corrupted measurements, over-parameterization leads to overfitting without prior knowledge on both the intrinsic rank and sparsity of corruption. This paper shows that with a double over-parameterization for both the low-rank matrix and sparse corruption, gradient descent with discrepant learning rates provably recovers the underlying matrix even without prior knowledge on neither rank of the matrix nor sparsity of the corruption. We further extend our approach for the robust recovery of natural images by over-parameterizing images with deep convolutional networks. Experiments show that our method handles different test images and varying corruption levels with a single learning pipeline where the network width and termination conditions do not need to be adjusted on a case-by-case basis. Underlying the success is again the implicit bias with discrepant learning rates on different over-parameterized parameters, which may bear on broader applications.