近端梯度法

总目录

一、凸优化基础（Convex Optimization basics）

凸优化基础（Convex Optimization basics）

二、一阶梯度方法（First-order methods）

梯度下降（Gradient Descent）

次梯度（Subgradients）

近端梯度法（Proximal Gradient Descent）

随机梯度下降（Stochastic gradient descent）

三、对偶

线性规划中的对偶（Duality in linear programs）

凸优化中的对偶（Duality in General Programs）

KKT条件（Karush-Kuhn-Tucker Conditions）

对偶的应用及拓展（Duality Uses and Correspondences）

对偶方法（Dual Methods）

交替方向乘子法（Alternating Direction Method of Multipliers）

近端梯度法（Proximal Gradient Descent）

在凸优化问题中，对于可微分的目标函数，我们可以通过梯度下降法（gradient descent）迭代求解最优解，而对于不可微分的目标函数，通过引入次梯度（subgradient）也可以迭代求解最优解，然而比起梯度下降法，次梯度法的速度比较缓慢。为此，针对于一些整体不可微分但却可以分解的目标函数来说，我们可以使用一种更快的算法——近端梯度法。

1. 可分解的目标函数

考虑一个目标函数可以分解为如下形式的两个函数：

f ( x ) = g ( x ) + h ( x ) (1) f(x)=g(x)+h(x) \tag{1}

f(x)=g(x)+h(x)(1)

其中，g ( x ) g(x)g(x)是凸函数且是可微分的，h ( x ) h(x)h(x)也是凸函数但可能不可微分。使用近端梯度下降，可以实现O ( 1 / ϵ ) O(1/\epsilon)O(1/ϵ)的收敛率（ϵ = f ( x ( k ) ) − f ( x ∗ ) \epsilon=f(x^{(k)})-f(x^*)ϵ=f(x

(k)

)−f(x

∗

)，即当前迭代结果与最优解之间的偏差）。通过对近端梯度法加速，可以达到O ( 1 / ϵ ) O(1/\sqrt\epsilon)O(1/

)收敛速率。

2. 梯度下降法回顾

对于一个可微分的凸函数f ( z ) f(z)f(z)，假设起始点在x xx，则可以做二阶泰勒展开：

f ( z ) ≈ f ( x ) + ∇ f ( x ) T ( z − x ) + 1 2 ∇ 2 f ( x ) ∥ z − x ∥ 2 2 (2) f(z)\approx f(x)+\nabla f(x)^T(z-x)+\frac{1}{2}\nabla^2f(x)\|z-x\|^2_2 \tag{2}

f(z)≈f(x)+∇f(x)

(z−x)+

∇

f(x)∥z−x∥

(2)

通过替换∇ 2 f ( x ) = 1 t I \nabla^2f(x)=\frac{1}{t}I∇

f(x)=

I，可以得到

f ( z ) ≈ f ( x ) + ∇ f ( x ) T ( z − x ) + 1 2 t ∥ z − x ∥ 2 2 (3) f(z)\approx f(x)+\nabla f(x)^T(z-x)+\frac{1}{2t}\|z-x\|^2_2 \tag{3}

f(z)≈f(x)+∇f(x)

(z−x)+

∥z−x∥

(3)

最小化上述二次近似

x + = arg ⁡ min ⁡ z f ( x ) + ∇ f ( x ) T ( z − x ) + 1 2 t ∥ z − x ∥ 2 2 (4) x^+=\arg\min_zf(x)+\nabla f(x)^T(z-x)+\frac{1}{2t}\|z-x\|^2_2 \tag{4}

=arg

min

f(x)+∇f(x)

(z−x)+

∥z−x∥

(4)

可以得到下一个点的位置

z = x + = x − t ∇ f ( x ) (5) z=x^+=x-t\nabla f(x) \tag{5}

z=x

=x−t∇f(x)(5)

这就是我们常见的梯度下降的迭代更新策略。

3. 近端投影

如果f ff不可微，但可以分解为上述的两个函数g gg和h hh，则我们仍然可以使用平滑部分g gg的二次近似来定义向最小值走的一步：

x + = arg ⁡ min ⁡ a g ( z ) + h ( z ) ≈ arg ⁡ min ⁡ z g ( x ) + ∇ g ( x ) T ( z − x ) + 1 2 t ∥ z − x ∥ 2 2 + h ( z ) (6)

\begin{aligned} x^+&=\arg\min_a g(z)+h(z) \\ &\approx \arg\min_z g(x)+\nabla g(x)^T(z-x)+\frac{1}{2t}\|z-x\|^2_2+h(z) \tag{6} \end{aligned}

=arg

min

g(z)+h(z)

≈arg

min

g(x)+∇g(x)

(z−x)+

∥z−x∥

+h(z)

(6)

式（6）可以写成：

x + = arg ⁡ min ⁡ z 1 2 t ∥ z − ( x − t ∇ g ( x ) ) ∥ 2 2 + h ( z ) : = p r o x h , t ( x − t ∇ g ( x ) ) (7) x^+=\arg\min_z\frac{1}{2t}\|z-(x-t\nabla g(x))\|^2_2+h(z):=prox_{h,t}(x-t\nabla g(x)) \tag{7}

=arg

min

∥z−(x−t∇g(x))∥

+h(z):=prox

h,t

(x−t∇g(x))(7)

其中，近端函数p r o x proxprox定义为

p r o x h , t ( x ) = arg ⁡ min ⁡ z 1 2 t ∥ z − x ∥ 2 2 + h ( z ) (8) prox_{h,t}(x)=\arg\min_z\frac{1}{2t}\|z-x\|^2_2+h(z) \tag{8}

prox

h,t

(x)=arg

min

∥z−x∥

+h(z)(8)

4. 近端梯度下降

使用近端函数，我们可以定义一个迭代过程，叫做迭代梯度下降。其过程如下：

首先，选择一个初始点x ( 0 ) x^{(0)}x

(0)

，然后重复：

x ( i ) = p r o x h , t i ( x ( i − 1 ) − t i ∇ g ( x ( i − 1 ) ) ) , i = 1 , 2 , 3 , . . . (9) x^{(i)}=prox_{h,t_i}(x^{(i-1)}-t_i\nabla g(x^{(i-1)})), i=1,2,3,... \tag{9}

(i)

=prox

h,t

(i−1)

−t

∇g(x

(i−1)

)),i=1,2,3,...(9)

使用该方法有几个优点：

对于许多h hh函数，其近端投影p r o x h , t prox_{h,t}prox

h,t

有解析解；

p r o x t prox_{t}prox

仅仅依赖于h hh，因此可以被用于不同的g gg函数；

g gg可以是任意复杂的函数，只要我们能计算其梯度；

4.1 例子：迭代软阈值算法（ISTA）

考虑下面lasso问题：

min ⁡ β ∈ R p 1 2 ∥ y − X β ∥ 2 2 + λ ∥ β ∥ 1 (10) \min_{\beta \in \mathcal{R}^p}\frac{1}{2}\|y-X\beta\|^2_2+\lambda\|\beta\|_1 \tag{10}

β∈R

min

∥y−Xβ∥

+λ∥β∥

(10)

令g ( β ) = 1 2 ∥ y − X β ∥ 2 2 g(\beta)=\frac{1}{2}\|y-X\beta\|^2_2g(β)=

∥y−Xβ∥

，h ( β ) = ∥ β ∥ 1 h(\beta)=\|\beta\|_1h(β)=∥β∥

。对于目标函数的近端映射可以用软阈值法来计算：

p r o x h , t ( β ) = arg ⁡ min ⁡ z 1 2 t ∥ β − z ∥ 2 2 + λ ∥ z ∥ 1 = S λ t ( β ) (11) prox_{h,t}(\beta)=\arg\min_z \frac{1}{2t}\|\beta-z\|^2_2+\lambda\|z\|_1=S_{\lambda t}(\beta) \tag{11}

prox

h,t

(β)=arg

min

∥β−z∥

+λ∥z∥

λt

(β)(11)

其中，S λ t ( β ) S_{\lambda t}(\beta)S

λt

(β)有解析解，相当于软阈值算子：

[ S λ t ] i = { β i − λ t , β i > λ t 0 , − λ t ≤ β i ≤ λ t β i + λ t , β i < − λ t (12) [S_{\lambda t}]_i=\left\{

βi−λt,0,βi+λt,βi>λt−λt≤βi≤λtβi<−λt

βi−λt,βi>λt0,−λt≤βi≤λtβi+λt,βi<−λt

\right. \tag{12}

λt

]

⎩

⎪

⎨

⎪

⎧

−λt,

+λt,

>λt

−λt≤β

≤λt

<−λt

(12)

而g ( β ) g(\beta)g(β)的梯度为X T ( X β − y ) X^T(X\beta-y)X

(Xβ−y)，因此，我们可以得到近端梯度下降更新策略：

β + = S λ t ( β − t X T ( X β − y ) ) (13) \beta^+=S_{\lambda t}(\beta-tX^T(X\beta-y)) \tag{13}

λt

(β−tX

(Xβ−y))(13)

5. 特殊情况

近端梯度下降相当于梯度下降法的一种推广，因此也被称为复合梯度下降（composite gradient descent）或者广义梯度下降（generalized gradient descent）。下面几个特殊的情况可以看出为什么称之为广义梯度下降。

5.1 梯度下降

当h ( x ) = 0 h(x)=0h(x)=0时，近端映射函数变为：

p r o x t ( x ) = arg ⁡ min ⁡ z 1 2 t ∥ x − z ∥ 2 2 = x (14) prox_t(x)=\arg\min_z\frac{1}{2t}\|x-z\|^2_2=x \tag{14}

prox

(x)=arg

min

∥x−z∥

=x(14)

因此，更新策略变为

x ( k ) = x ( k − 1 ) − t k ∇ g ( x ( k − 1 ) ) , k = 1 , 2 , 3 , . . . (15) x^{(k)}=x^{(k-1)}-t_k\nabla g(x^{(k-1)}), k=1,2,3,... \tag{15}

(k)

(k−1)

−t

∇g(x

(k−1)

),k=1,2,3,...(15)

即正常的梯度下降法。

5.2 投影梯度下降

当h ( x ) = I c h(x)=I_ch(x)=I

，I c I_cI

为集合C CC的指示函数时，近端映射函数变为：

p r o x t ( x ) = arg ⁡ min ⁡ z 1 2 t ∥ x − z ∥ 2 2 + I c = arg ⁡ min ⁡ z ∈ C 1 2 t ∥ x − z ∥ 2 2 = P C ( x ) (16)

proxt(x)=argminz12t∥x−z∥22+Ic=argminz∈C12t∥x−z∥22=PC(x)

proxt(x)=arg⁡minz12t‖x−z‖22+Ic=arg⁡minz∈C12t‖x−z‖22=PC(x)

\tag{16}

prox

(x)

=arg

min

∥x−z∥

=arg

z∈C

min

∥x−z∥

(x)

(16)

其中，P C ( x ) P_C(x)P

(x)表示集合C CC上的投影算子。

因此，更新策略变为

x ( k ) = P c ( x ( k − 1 ) − t k ∇ g ( x ( k − 1 ) ) ) , k = 1 , 2 , 3 , . . . (17) x^{(k)}=P_c(x^{(k-1)}-t_k\nabla g(x^{(k-1)})), k=1,2,3,... \tag{17}

(k)

(k−1)

−t

∇g(x

(k−1)

)),k=1,2,3,...(17)

即为投影梯度下降法。其先使用正常的梯度更新策略，然后将得到的x xx投影回集合C CC中。

5.3 近端最小化算法

当g ( x ) = 0 g(x)=0g(x)=0时，更新策略变为：

x ( k ) = arg ⁡ min ⁡ z 1 2 t ∥ x ( k − 1 ) − z ∥ 2 2 + h ( z ) , k = 1 , 2 , 3 , . . . (18) x^{(k)} = \arg\min_z\frac{1}{2t}\|x^{(k-1)}-z\|^2_2+h(z), k=1,2,3,... \tag{18}

(k)

=arg

min

∥x

(k−1)

−z∥

+h(z),k=1,2,3,...(18)

其叫做近端最小化算法（proximal minimization algorithm）。其比次梯度方法快，但仅仅适用于近端算子是闭合形式的情况。

————————————————

原文链接：https://blog.csdn.net/zbwgycm/article/details/83060251

近端梯度法

推荐阅读更多精彩内容