《分布式机器学习：算法、理论与实践》—

《分布式机器学习：算法、理论与实践》——【RE2a】

近端梯度下降法是众多梯度下降 (gradient descent) 方法中的一种，其英文名称为proximal gradident descent，其中，术语中的proximal一词比较耐人寻味，将proximal翻译成“近端”主要想表达"（物理上的）接近"。与经典的梯度下降法和随机梯度下降法相比，近端梯度下降法的适用范围相对狭窄。对于凸优化问题，当其目标函数存在不可微部分（例如目标函数中有 $l_1$ -范数或迹范数）时，近端梯度下降法才会派上用场。

1. 特定的凸优化问题

一般而言，近端梯度下降法常用于解决以下这类优化问题：

假设目标函数 ${color{blue}{f(x)=g(x)+h(x)}}$ 是由 $g(x)$ 和 $h(x)$ 叠加而成，其中，限定 ${color{blue}{g(x)}}$ 是可微的凸函数、 ${color{blue}{h(x)}}$ 是不可微 (或局部不可微) 的凸函数。

2. 以线性回归问题为例

给定 ${color{blue}{oldsymbol{X}inmathbb{R}^{m imes n},oldsymbol{y}inmathbb{R}^{m}}}$ ，若线性回归表达式为 ${color{blue}{oldsymbol{y}=oldsymbol{X}oldsymbol{w}}}$ ，其中，变量 ${color{blue}{oldsymbol{w}inmathbb{R}^{n}}}$ 表示系数向量。优化的目标函数可以写成如下形式：

${color{blue}{f(oldsymbol{w})=underbrace{frac{1}{2}left|oldsymbol{y}-oldsymbol{X}oldsymbol{w} ight|_{2}^{2}}_{gleft(oldsymbol{w} ight)}+underbrace{lambdaleft|oldsymbol{w} ight|_{1}}_{hleft(oldsymbol{w} ight)}}}~~~~~~(1)$

其中， ${color{blue}{left|cdot ight|_{1}}}$ 表示 $l_1$ -范数； ${color{blue}{left|cdot ight|_{2}}}$ 表示 $l_2$ -范数；正则项中的 $l_1$ -范数是为了保证变量 $oldsymbol{w}$ 是稀疏的。在这个目标函数中，正则项中的 $l_1$ -范数便是一个不可微的凸函数。由此便引申出采用近端梯度下降法对这类优化问题进行求解。

2.1 近端算子 (proximal operator)

一般来说，对于任意向量 ${color{blue}{oldsymbol{w}}}$ ，如果不可微函数为 ${color{blue}{h(oldsymbol{w})=lambda|oldsymbol{w}|_1}}$ ，则近端算子 (proximal operator) 为

${color{blue}{egin{aligned} operatorname{prox}_{th(cdot)}(oldsymbol{w}) &=operatorname{arg}underset{oldsymbol{z}}{operatorname{min}} frac{1}{2 t}|oldsymbol{w}-oldsymbol{z}|_{2}^{2}+lambda|oldsymbol{z}|_{1} \ &=operatorname{arg}underset{oldsymbol{z}}{operatorname{min}} frac{1}{2}|oldsymbol{w}-oldsymbol{z}|_{2}^{2}+lambda t|oldsymbol{z}|_{1} \ &=mathcal{S}_{lambda t}(oldsymbol{w}) end{aligned}}}~~~~(2)$

其中， ${color{blue}{ operatorname{prox}_{th(cdot)}(oldsymbol{w}) }}$ 表示关于变量 ${color{blue}{oldsymbol{w}}}$ 和函数 ${color{blue}{ h(cdot)}}$ 的近端算子； ${color{blue}{mathcal{S}_{lambda t}left(oldsymbol{w} ight)inmathbb{R}^{n}}}$ 表示关于变量 ${color{blue}{oldsymbol{w}}}$ 软阈值函数（下面将着重介绍），选用符号 $mathcal{S}$ 是因为软阈值soft-thresholding的英文首字母为s。

这条公式想表达的意思是：对于任意给定的 ${color{blue}{oldsymbol{w}inmathbb{R}^{n}}}$ ，我们希望找到使得 ${color{blue}{frac{1}{2}|oldsymbol{w}-oldsymbol{z}|_{2}^{2}+lambda t|oldsymbol{z}|_{1}}}$ 最小化的解 ${color{blue}{oldsymbol{u}=operatorname{prox}_{th(cdot)}(oldsymbol{w}) }}$ ，其中， ${color{blue}{t}}$ 是一个新增参数，表示近端梯度下降的步长 (step size)。实际上，近端算子只和不可微的凸函数 ${color{blue}{h(oldsymbol{w})}}$ 有关 (如公式(2)中的 ${color{blue}{left|cdot ight|_{1}}}$ )。

当不可微的凸函数的形式为 ${color{blue}{h(oldsymbol{w})=|oldsymbol{w}|_1}}$ 时，则对应的软阈值函数为

${color{blue}{left[mathcal{S}_{t}(oldsymbol{w}) ight]_{i}=left{egin{array}{ll}{w_{i}-t,} & { ext { if } w_{i}>t}, \ {0,} & { ext { if }|w_{i}| leq t,} \ {w_{i}+t,} & { ext { if } w_{i}<-t.}end{array} ight.}}~~~~(3)$

如公式(2)，当 ${color{blue}{h(oldsymbol{w})=lambda|oldsymbol{w}|_1}}$ （ $l_1$ -范数作为正则项，其正则项参数为 ${color{blue}{lambda}}$ ）时，软阈值函数则为 ${color{blue}{mathcal{S}_{lambda t}left(cdot ight)}}$ ，其定义为

${color{blue}{left[mathcal{S}_{lambda t}(oldsymbol{w}) ight]_{i}=left{egin{array}{ll}{w_{i}-lambda t,} & { ext { if } w_{i}>lambda t}, \ {0,} & { ext { if }|w_{i}| leq lambda t,} \ {w_{i}+lambda t,} & { ext { if } w_{i}<-lambda t.}end{array} ight.}}~~~~(4)$

公式(4)给出的软阈值函数恰好与公式(2)中的目标函数相对应。至于为什么软阈值函数的形式是这样，Derivation of the soft thresholding operator中给出了简单详细的推导过程。

2.2 近端梯度下降 (proximal gradient descent)

对于优化问题 ${color{blue}{min_{oldsymbol{w}}~g(oldsymbol{w})+h(oldsymbol{w})}}$ ，变量 ${color{blue}{oldsymbol{w}}}$ 的迭代递推公式为

${color{blue}{egin{aligned}oldsymbol{w}^{k}&= ext{prox}_{th(cdot)}left(oldsymbol{w}^{k-1}-t abla g(oldsymbol{w}^{k-1}) ight) \ &=mathcal{S}_{lambda t}left(oldsymbol{w}^{k-1}-t abla g(oldsymbol{w}^{k-1}) ight) \ end{aligned} }}$

其中，变量上标的 ${color{blue}{k}}$ 表示当前迭代次数。

迭代递推公式证明过程（涉及知识：泰勒展开）:
${color{blue}{egin{aligned}oldsymbol{w}^{k}&= ext{prox}_{th(cdot)}left(oldsymbol{w}^{k-1}-t abla g(oldsymbol{w}^{k-1}) ight) \ &= ext{arg}min_{oldsymbol{z}}~h(oldsymbol{z})+frac{1}{2t}|oldsymbol{z}-left(oldsymbol{w}^{k-1}-t abla g(oldsymbol{w}^{k-1}) ight)|_2^2 \ &= ext{arg}min_{oldsymbol{z}}~h(oldsymbol{z})+frac{t}{2}| abla g(oldsymbol{w}^{k-1})|_2^2+ abla g(oldsymbol{w}^{k-1})^ op(oldsymbol{z}-oldsymbol{w}^{k-1})+frac{1}{2t}|oldsymbol{z}-oldsymbol{w}^{k-1}|_2^2 \ &= ext{arg}min_{oldsymbol{z}}~h(oldsymbol{z})+g(oldsymbol{w}^{k-1})+ abla g(oldsymbol{w}^{k-1})^ op(oldsymbol{z}-oldsymbol{w}^{k-1})+frac{1}{2t}|oldsymbol{z}-oldsymbol{w}^{k-1}|_2^2 \ &approx ext{arg}min_{oldsymbol{z}}~h(oldsymbol{z})+g(oldsymbol{z}) \ end{aligned} }}$
注意：由于公式第三行中的 $frac{t}{2}| abla g(oldsymbol{w}^{k-1})|_2^2$ 和第四行中的 $g(oldsymbol{w}^{k-1})$ 均与决策变量 $oldsymbol{z}$ 无关，因此公式第三行等于公式第四行。

2.3 线性回归问题的迭代过程

回到公式(1)，我们定义了函数 ${color{blue}{g(oldsymbol{w})}}$ 的表达式为

${color{blue}{g(oldsymbol{w})=frac{1}{2}left|oldsymbol{y}-oldsymbol{X}oldsymbol{w} ight|_{2}^{2}}}$

由于 ${color{blue}{ abla g(oldsymbol{w})=-oldsymbol{X}^{ op}(oldsymbol{y}-oldsymbol{X} oldsymbol{w})}}$ ，根据近端梯度下降法的迭代递推公式可以推导出变量 ${color{blue}{oldsymbol{w}}}$ 的近端梯度更新公式为

${color{blue}{egin{aligned}oldsymbol{w}^{k}&=mathcal{S}_{lambda t}left(oldsymbol{w}^{k-1}-t abla g(oldsymbol{w}^{k-1}) ight) \ &=mathcal{S}_{lambda t}left(oldsymbol{w}^{k-1}+toldsymbol{X}^ opoldsymbol{y}-toldsymbol{X}^ opoldsymbol{X}oldsymbol{w}^{k-1} ight) \ end{aligned} }}$

这条更新公式通常也被称为迭代软阈值算法 (iterative soft-thresholding algorithm, ISTA)。

众所周知，如果将这里的 ${color{blue}{h(oldsymbol{w})=lambda|oldsymbol{w}|_1}}$ 换成 ${color{blue}{h(oldsymbol{w})=frac{1}{2}lambda|oldsymbol{w}|_2^2}}$ ，则整个线性回归的优化问题就会变成一个最小二乘问题。获取变量 ${color{blue}{oldsymbol{w}}}$ 的最优解也会变得非常简单，只需要令 ${color{blue}{ abla left(g(oldsymbol{w})+h(oldsymbol{w}) ight)=-oldsymbol{X}^{ op}(oldsymbol{y}-oldsymbol{X} oldsymbol{w})+lambdaoldsymbol{w}=oldsymbol{0}}}$ 即可，此时的最优解为

${color{blue}{oldsymbol{w}=left(oldsymbol{X}^ opoldsymbol{X}+lambdaoldsymbol{I} ight)^{-1}oldsymbol{X}^ opoldsymbol{y}}}$

其中， ${color{blue}{lambda}}$ 表示正则项参数。

当然，这里还有一个很值得思考的问题：

对于上述线性回归问题，为何选用近端梯度下降法，而非次梯度 (subgradient descent) 下降法呢？

实际上，次梯度下降法也能求解这种线性回归问题。一般而言，对于损失函数

${color{blue}{f(oldsymbol{w})={frac{1}{2}left|oldsymbol{y}-oldsymbol{X}oldsymbol{w} ight|_{2}^{2}}+{lambdaleft|oldsymbol{w} ight|_{1}}}}$

我们可以得到正则项的梯度为 ${color{blue}{left{egin{array}{ll} &-lambda, & ext{if}~w_i<0, \ &lambda,& ext{if}~w_i>0, \ end{array} ight.}}$ 然而不幸的是，当 ${color{blue}{w_i=0}}$ 时，正则项不可微。为了消除这个影响，我们可以采用次梯度 ${color{blue}{lambdacdot ext{sgn}(oldsymbol{w})}}$ ，当再遇到 ${color{blue}{w_i=0}}$ 时，次梯度就会等于 ${color{blue}{0}}$ .

相应地，损失函数的次梯度为

${color{blue}{g(oldsymbol{w})=-2 oldsymbol{X}^{ op}(oldsymbol{y}-oldsymbol{X} oldsymbol{w})+lambda operatorname{sgn}(oldsymbol{w})}}$

与梯度下降法类似，我们可以用次梯度下降法使得损失函数最小化。但仔细看一下损失函数次梯度的表达式 ${color{blue}{g(oldsymbol{w})}}$ ，我们会发现：次梯度法可能不会像我们所期许的那样，得到真正的稀疏解 ${color{blue}{oldsymbol{w}}}$ ，次梯度法只会使解的部分数值 (即 ${color{blue}{oldsymbol{w}}}$ 的部分元素) 尽可能小 (尽可能接近 ${color{blue}{0}}$ )。因此，只有选用近端梯度下降这类方法，我们才能获得稀疏解，并同时提升迭代过程的收敛性。

3. 相关参考

[1] Proximal Gradient Descent (by Ryan Tibshirani from CMU)：http://stat.cmu.edu/~ryantibs/convexopt/lectures/prox-grad.pdf

[2] Why proximal gradient descent instead of plain subgradient methods for Lasso?

[3] Why doesn't subgradient descent give sparse solutions to the Lasso?

编辑于 2019-11-27

收敛速度稍慢，理论收敛阶1/n。对于l1极小化问题，临（邻）近梯度法（pg）即为ista。采用加速版本的ista即fista算法可以到1/n2。

https://www.google.com.hk/search?q=%E8%BF%91%E7%AB%AF%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D

临近算子是对梯度的延伸，当函数 f 为光滑函数时，该临近算子就是梯度。

https://blog.csdn.net/qq547276542/article/details/78251779

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

讲得详细

Frank-Wolfe方法将线性约束最优化问题转化为一系列线性规划问题和一维搜索问题求解。可以证明，当f具有连续一阶偏导数，且可行域S有界，Frank-Wolfe方法是收敛的。

https://www.cnblogs.com/cx2016/p/12926182.html

所以这个示意图还是不错的