当目标函数中有不可微部分时,可使用近端梯度下降来优化(Proximal Gradient Descent)
假设目标函数如下:
其中是可微凸函数,是不可微(或局部不可微)凸函数。 以线性回归为例,
给定, , Ridge Regression的目标函数为
因为 norm处处可导,所以Ridge可以用SGD或GD来直接优化。但是若目标函数为Lasso,即正则化项定义为 norm:
这里在处不可导,那么可用PGD来优化。
Proximity Operator#
近端算子: 对于不可微函数, 的proximity operator定义为:
近端算子只和不可微凸函数有关。 上式含义,给定一个不可微凸函数, 给定向量, 找到向量, 使得公式最小。 这个就是在给定条件下的近端算子(Proximity Operator)。要求最佳的可以使得函数值尽可能小,同时要尽可能接近给定的。
基于后面的公式推导,我们给添加一个参数:
上式表示,给定一个不可微凸函数, 一个给定的点, 一个参数, 要找到一个, 使得带入公式的到的结果最小。 是使得最小的输入。
因为和都为凸函数,所以一定存在使得函数值最小, 这个要求使得尽可能小(第一项),同时要尽可能接近给定的(第二项)。
例子:
如果在 norm前加上参数, 即, 那么近端算子为:
近端梯度算法#
回到Lasso 回归,要求解:
可以通过递推式求出:
为什么可以通过不断迭代迭代上式来求解最佳的, 使得收敛到最小?下面先给出证明
整个过程不涉及对求梯度
最后两步怎么来的?
泰勒展开式:
对做泰勒展开, 令:
综上:
所以通过迭代的方式求 就是的迭代递推求解过程。
求解 范数#
将求解问题转为递推式。
现在我们有问题,形式为:
找到最佳使得上式最小的过程可以迭代递推为:
求解Lasso回归#
待求解问题形如:
可见第一项可微,第二项为 norm 在处不可微。
根据递推式:
令, 上式可改写为
因为learning step size 与无关,所以上式可以改写为:
把带入中:
因为,
所以到的迭代优化方式如下:
其中 是的第行。
Reference#
https://blog.csdn.net/Chaolei3/article/details/81320940
https://zhuanlan.zhihu.com/p/82622940
http://roachsinai.github.io/2016/08/03/1Proximal_Method/