Press "Enter" to skip to content

不用l1核范数,伯克利NeurIPS spotlight带你看过参数化的稀疏低秩

在做马毅老师新书 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一样分类讨论

 

 

    1. 如果element i最后是大于0的即

    1. ,我们有

    1. 。因为

    1. ,所以有

    1. ,两边取对数之后有

    1. ,两边同时除以

    1. 并考虑

    1. 可以得到

    1. 的情况和1是一样的此时

    1. 的情况我们有

    1. ,两边取log之后

    1. ,两边同时除以

    1. 并考虑

    1. 可以得到

    1. ,另外一边也是同理可得

    1. ,所以此时

 

 

综合123三点,此时 满足(5)当中条件,因为存在这幺一个dual certificate,所以noncvx的(1)和cvx的(2)的解是等价的,到这里就证完啦~

 

Part IV: 一些吐槽

 

 

    1. 标题党没办法啊,不标题党没人点进来啊啊啊。。。

 

    1. 为啥把最近nips的paper来做书后习题啊,没hint估计这辈子都做不出来啊啊啊。。。

 

    1. 好久没更优化的文章了,原因是人菜做不动优化呜呜呜~~~来个大哥带带我优化吧啊啊啊。。。

 

    1. 话说怎幺发现这篇paper的故事也有点意思,我看风格以为是vidal老师的paper,但是找了一下没找到放弃了,后来在一周之后也就是今天在马毅老师的个人主页发现了这篇paper~

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注