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

向右看齐 2022-10-16 00:46 274阅读 0赞

### 目录 ###

*  介绍
 *  梯度下降法回顾
 *  近端梯度下降法
 *  加速的近端梯度法

# 介绍 #

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

# 梯度下降法回顾 #

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

# 近端梯度下降法 #

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

# 加速的近端梯度法 #

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70]: /images/20221014/5a803ae6e8c64a1694172cfc48fb0d4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 1]: /images/20221014/aea2045d80a14f49920eaf220ed629d8.png
[2021052609421388.png]: /images/20221014/d14f8947a8094ac4b49cff7400195b4f.png
[2021052609042332.png]: /images/20221014/233503a47e174a1e80f3ccccadc54e98.png
[20210526090457517.png]: /images/20221014/053079880ab94e80958e70a91f576336.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 2]: /images/20221014/75521dd153004acb83e6d8adb13b895f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 3]: /images/20221014/5cbb5b551ac74e3daed268f5fae39fbc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 4]: /images/20221014/c93250b6727f405db083fe0ee2972cd4.png
[20210526095907183.png]: /images/20221014/6177a19a6a144427b0b893c59ded6185.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 5]: /images/20221014/2b8bec334dfe43169af25e58484b4d1f.png
[20210526102825773.png]: https://img-blog.csdnimg.cn/20210526102825773.png