当目标函数中有不可微部分时,可使用近端梯度下降来优化(Proximal Gradient Descent)

假设目标函数如下: f(w)=g(w)+h(w) 其中g(w)是可微凸函数,h(w)是不可微(或局部不可微)凸函数。 以线性回归为例,

给定XRm×n, yRm, Ridge Regression的目标函数为

f(w)=12||yXw||22g(w)+λ||w||2h(w) 因为2 norm处处可导,所以Ridge可以用SGD或GD来直接优化。但是若目标函数为Lasso,即正则化项定义为1 norm: f(w)=12||yXw||22g(w)+λ||w||1h(w) 这里h(w)=λ||w||1w=0处不可导,那么可用PGD来优化。

Proximity Operator

近端算子: 对于不可微函数h(w), h(w)的proximity operator定义为:

u=proxh(w)=argminu(h(u)+12||uw||22) 近端算子proxh(w)只和不可微凸函数h()有关。 上式含义,给定一个不可微凸函数h(), 给定向量wRn, 找到向量u=u, 使得公式h(u)+12||uw||22最小。 这个u=proxh(w)就是h()在给定w条件下的近端算子(Proximity Operator)。u=proxh(w)要求最佳的u可以使得函数值h(u)尽可能小,同时u要尽可能接近给定的w

基于后面的公式推导,我们给proxh(w)添加一个参数γ: u=proxhγ(w)=argminu(h(u)+12γ||uw||22) 上式表示,给定一个不可微凸函数h(), 一个给定的点w, 一个参数γ, 要找到一个u=u, 使得u带入公式h(u)+12γ||uw||22的到的结果最小。 proxhγ(w)是使得h(u)+12γ||uw||22最小的输入u

因为h(u)||uw||22都为凸函数,所以一定存在u使得函数值最小, 这个u=proxhγ(w)要求使得h(u)尽可能小(第一项),同时u要尽可能接近给定的w(第二项)。

例子:

  • h(w)=0, proxhγ(w)=u=w

  • h(w)=||w||1时,proxhγ(w)=prox||||1γ(w)是软阈值操作

u=(proxhγ(w))i={wiγwiγ0|wi|γwi+γwiγ

如果在1 norm前加上参数λ, 即h(w)=λ||w||1, 那么近端算子为: u=(proxhγ(w))i={wiλγwiλγ0|wi|λγwi+λγwiλγ

近端梯度算法

回到Lasso 回归,要求解: minw(g(w)+h(w)) w可以通过递推式求出: wk=proxhγ(wk1γg(wk1)) 为什么可以通过不断迭代迭代上式来求解最佳的wK, 使得g(w)+h(w)收敛到最小?下面先给出证明 wk=proxhγ(wk1γg(wk1))=argminu(h(u)h(u)+12γ||u(wk1γg(wk1))uwk1γg(wk1)||22)=argminu(h(u)+12γ||(uwk1)+γg(wk1)||22)=argminu(h(u)+γ2||g(wk1)||22γwk1u+(uwk1)Tg(wk1)+12γ||uwk1||22)=argminu(h(u)+g(wk1)u+(uwk1)Tg(wk1)+12γ||uwk1||22)(5)argminu(g(u)+h(u)) 整个过程不涉及对h(u)求梯度

最后两步怎么来的?

泰勒展开式:

f(x)=f(a)0!+f(a)1!(xa)+f(a)2!(xa)2++f(n)(a)n!(xa)n

g(u)做泰勒展开, 令a=wk1: g(u)=g(wk1)+(uwk1)Tg(wk1)+uwk1,uwk12g(wk1)(5) 综上: wk=proxhγ(wk1γg(wk1))argminu(g(u)+h(u)) 所以通过迭代的方式求wk=proxhγ(wk1γg(wk1)) 就是minw(g(w)+h(w))的迭代递推求解过程。

求解1 范数

将求解问题转为递推式

现在我们有问题,形式为: minw(g(w)+λ||w||1h(w)) 找到最佳w使得上式最小的过程可以迭代递推为: wk+1=proxλ||||1γ(wkγg(wk))=argminu(λ||u||1+12γ||u(wkγg(wk))||22)

求解Lasso回归

待求解问题形如: minw(12||Xwy||22+r||w||1) 可见第一项可微,第二项为1 norm 在w=0处不可微。

根据递推式: wk+1=proxλ||||1γ(wkγg(wk)zk)zk=wkγg(wk), 上式可改写为

因为learning step size γw无关,所以上式可以改写为: wk+1=proxλ||||1γ(zk)=argminw(λ||w||1+12γ||wzk||22)=argminw(λγ||w||1+12||wzk||22)

g(wk)=12||Xwy||22

g(wk)=XT(Xwky)=XTXwkXTy

zk=wkγ(XTXwkXTy)

zk带入wk+1中: wk+1=proxλ||||1γ(zk)=proxλ||||1γ(wkγXTXwk+γXTy) 因为(proxλ||||1γ(w))i={wiλγwiλγ0|wi|λγwi+λγwiλγ,

所以wkwk+1的迭代优化方式如下: wik+1=(proxλ||||1γ(zk))i={zikλγzikλγ0|zik|λγzik+λγzikλγ 其中 zikzk的第i行。

Reference

https://blog.csdn.net/Chaolei3/article/details/81320940

https://zhuanlan.zhihu.com/p/82622940

http://roachsinai.github.io/2016/08/03/1Proximal_Method/