在做马毅老师新书 High-Dimensional Data Analysis with Low-Dimensional Models 第七章书后习题的时候看到一道关于implicit bias of gradient descent的有趣题目,花了一下午才做出来,后来上网查了一下发现是去年一篇NeurIPS的Spotlight,在这里做个笔记。
码字不易,点个赞呗再走呗,欢迎关注我们的专栏非凸优化学习之路,里面会更新一些优化的最新进展~
本文分为以下几个部分:
Part I: 文章介绍
Part II: 梯度下降的Implicit bias介绍
Part III: 文章证明的简化版本
Part I: 文章简介
这篇文章考虑了一个经典的反问题,从有噪音的测量 中恢复 X , 是要恢复的信号, 是一个线性变换, 是一个稀疏噪音。这个问题呢,在图像去噪当中有着重要的作用。这个问题是一个非凸问题
一般呢,我们就relax一下变成凸问题然后解
坏处是啥呢,首先他要在内存里面存一个很大很大的X,然后每步迭代的时候也要对X做一个SVD,又耗内存又慢。所以呢,这篇文章提出了一个非凸的formulation
通过一些不复杂的计算,我们可以证明凸问题和非凸问题解的等价性,这里留到part III再说。
跟其它算法比呢,这个方法不需要调参也内存时间代价也小
在实验效果上也当然是比神经网络的方法还好并且取得SOTA的
Part II: 梯度下降的Implicit bias
为啥凸和非凸的formulation是等价的呢,这就要归功于梯度下降的Implicit bias了。我们先来看一下在underdetermined linear equations当中梯度下降的表现。考虑一个least square问题
我们用梯度下降去优化它,迭代方程为
我们记A的null space为 ,row space为 ,那幺我们投影 到这两个space上则有
所以如果初始点 的话就会收敛到minimum norm solution,也就是下面这个优化问题的解
这也就是我们通常所说的梯度下降的implicit bias,对于带动量的梯度下降呢,也会收敛到这个点。对于带precondition的算法比如adam
我们则会收敛到下面这个问题的解
所以precondition其实是破坏了minimum norm的性质。 弱弱地求问一下这个和adam泛化性能比sgd差有关系吗?
Part III: 证明
我们在这里证明一下sparse部分,low rank部分也是同理(其实是我懒),我们要证明下面两个问题的解是等价的
我们先写出(2)的拉格朗日对偶
另 有
这也就是着名的l1的dual certificate,(2)推到这里可能也就差不多了,我们来看看对(1)进行梯度下降迭代,假设初始点 ,我们有
其中 。(4)是一个线性方程,所以我们可以轻松地得到它的解
其中 。令
下面我们要证明 满足(3)的 dual certificate 也就是
其中 以及 。
这里就像推导soft thresholding一样分类讨论
- 如果element i最后是大于0的即
- ,我们有
- 。因为
- ,所以有
- 和
- ,两边取对数之后有
- ,两边同时除以
- 并考虑
- 可以得到
- 。
- 的情况和1是一样的此时
- 的情况我们有
- ,两边取log之后
- ,两边同时除以
- 并考虑
- 可以得到
- ,另外一边也是同理可得
- ,所以此时
- 。
综合123三点,此时 满足(5)当中条件,因为存在这幺一个dual certificate,所以noncvx的(1)和cvx的(2)的解是等价的,到这里就证完啦~
Part IV: 一些吐槽
- 标题党没办法啊,不标题党没人点进来啊啊啊。。。
- 为啥把最近nips的paper来做书后习题啊,没hint估计这辈子都做不出来啊啊啊。。。
- 好久没更优化的文章了,原因是人菜做不动优化呜呜呜~~~来个大哥带带我优化吧啊啊啊。。。
- 话说怎幺发现这篇paper的故事也有点意思,我看风格以为是vidal老师的paper,但是找了一下没找到放弃了,后来在一周之后也就是今天在马毅老师的个人主页发现了这篇paper~
Be First to Comment