It is well-known that simple short-sighted algorithms, such as gradient descent, generalize well in the over-parameterized learning tasks, due to their implicit regularization. However, it is unknown whether the implicit regularization of these algorithms can be extended to robust learning tasks, where a subset of samples may be grossly corrupted with noise. In this work, we provide a positive answer to this question in the context of robust matrix recovery problem. In particular, we consider the problem of recovering a low-rank matrix from a number of linear measurements, where a subset of measurements are corrupted with large noise. We show that a simple sub-gradient method converges to the true low-rank solution efficiently, when it is applied to the over-parameterized l1-loss function without any explicit regularization or rank constraint. Moreover, by building upon a new notion of restricted isometry property, called sign-RIP, we prove the robustness of the sub-gradient method against outliers in the over-parameterized regime. In particular, we show that, with Gaussian measurements, the sub-gradient method is guaranteed to converge to the true low-rank solution, even if an arbitrary fraction of the measurements are grossly corrupted with noise.


翻译:众所周知,简单的短视算法,例如梯度下降,由于隐含的正规化,在过度参数化的学习任务中非常普遍,因为其隐含的正规化,但尚不清楚这些算法的隐含正规化能否扩大到稳健的学习任务,因为其中一部分样本可能因噪音而严重腐蚀。在这项工作中,我们从强力矩阵恢复问题的角度为这一问题提供了积极的答案。特别是,我们考虑从一系列线性测量中恢复一个低级矩阵的问题,因为在这一测量中,一组测量数据被大量噪声腐蚀。我们表明,当这些算法被应用到过度参数化的l1损失函数而没有任何明确的正规化或等级限制时,简单次等级化方法能否有效地与真正的低等级解决方案接轨。此外,我们借助一种新的限制异度测量属性属性概念,称为标志-RIP,我们证明了次等级方法对过度量化制度中的外部对象的稳健性。我们尤其表明,如果高斯测量数据,如果保证一个绝对的低度度测量方法与真实的低度度度测量方法相趋一致,那么,那么分级方法就必然会与完全的低度的低度的精确。

0
下载
关闭预览

相关内容

专知会员服务
155+阅读 · 2021年3月6日
专知会员服务
50+阅读 · 2020年12月14日
迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
3+阅读 · 2018年10月18日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
3+阅读 · 2017年12月14日
VIP会员
相关资讯
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员