关于近端梯度下降法你不知道的事_加速近端梯度法

介绍

• 近端梯度下降法是众多梯度下降 (gradient descent) 方法中的一种，其英文名称为proximal gradident descent，其中，术语中的proximal一词比较耐人寻味，将proximal翻译成“近端”主要想表达"（物理上的）接近"。与经典的梯度下降法和随机梯度下降法相比，近端梯度下降法的适用范围相对狭窄。对于凸优化问题，当其目标函数存在不可微部分（例如目标函数中有 [公式] -范数或迹范数）时，近端梯度下降法才会派上用场。
• 一般来说，PGD适用于特定的凸优化问题：假设目标函数 $f(x)=g(x)+h(x)$ 是由 $g(x)$ 和 $h(x)$ 叠加而成，其中，限定 $g(x)$ 是可微的凸函数、 $h(x)$ 是不可微 (或局部不可微) 的凸函数。
• 使用近端梯度下降，可以实现$O(1/ϵ)$的收敛率$(ϵ=f(x^k)-f(x^{\ast }))$，即当前迭代结果与最优解之间的偏差）。通过对近端梯度法加速，可以达到$O(1/\sqrt{ϵ})$收敛速率。

梯度下降法回顾

• 如下：
  
  这里我有个疑问，几乎所有的教程都将这里写作了$||z-x|{|}_2^2$而不是$(z-x{)}^2$考虑到z和x可能是向量，那么根据多元泰勒公式：
  
  貌似不能使用$||z-x|{|}_2^2$，当然$(z-x{)}^2$也是不恰当的，而应该使用海森矩阵：（下图以二阶泰勒为例）
  
  如果写作$||z-x|{|}_2^2$，相当于只考虑海森矩阵的对角线了。没有想出太好的解释，只能归咎于上面公式（2）和公式（3）的约等于符号了。
• 下面介绍一下为什么可以这么替换，其实原因还是Lipschitz条件（这好像是向量情况下的Lipschitz条件），即
  
  这里给出了一个L的下界，且下界的形式与二阶导函数形式类似，从而泰勒展开式的二阶导便通过L替代，从而严格不等也变成了近似：
  
  此处的L就是上面公式（3）中的$1/t$。
  然后
  
  这里是使用了求导来寻找极小值的方法，即让（4）式对z求导。

近端梯度下降法

• 如果$f$不可微，但可以分解为上述的两个函数$g$和$h$，则我们仍然可以使用平滑部分$g$的二次近似来定义向最小值走的一步：
  
  其中（6）到（7）的化简过程如下：
  
  （$L=1/t$）
  既然是常数，那我们就在优化问题中舍弃$\phi$。所以就得到了（7）式。
  现在的优化问题已经变成了下面的问题：
  
  即$x$已知，要求得到一个$z$使得上式最小化。这种问题，都可以适用软阈值函数解决。
  关于软阈值函数的证明可见：https://blog.csdn.net/BIT_666/article/details/80051737

加速的近端梯度法

• 如下：
  
  其实就是初始点作为$x^{(-1)}$，然后第二个点使用正常的近端梯度下降法求得，作为$x^{(0)}$，然后从第三个点开始，满足（19）式。即$k$从1开始。
  然后软阈值函数也不使用上一次的$x$来计算了，而是使用$v$，即：
  $x^{(i)}=prox(v-t{g}^{\prime }(v))$然后计算$v$再进行下一次计算，而不是$x^{(i)}=prox(x^{(i-1)}-t{g}^{\prime }(x^{(i-1)}))$
• 至于近端梯度下降法为什么有效，这里不讲专业的证明，只从$v$的计算公式上看，$v$在原来的基础上加了一个动量：
  
  以此来提高迭代速度。