前言: 本文的主角是近端梯度方法(Proximal Gradient Method), 这是一个在数学优化领域广为人知，在机器学习领域却很少看到的数学优化方法，它在非光滑优化领域发挥着巨大的作用，下面我们从一个机器学习问题开始了解它能够解决什么问题。
正则化损失最小化
正则化损失最小化(Regularized Loss Minimization, RLM)是机 器学习领域中一种联合最小化经验⻛险和正则化函数的学习范式，其形式如下: \[ \min_{\omega}L_S(\omega)+\alpha\mathcal{R}(\omega) \]
这里假定\(L_S(\omega)\)表示关于训练样本集\(S\)和模型系数\(\omega\)的经验⻛险项，代表模型对训练 样本集\(S\)拟合的好坏程度;\(\mathcal{R}(\omega)\)表示关于模型系数\(\omega\)的正则项，代表我们 对模型的额外偏好;正则项系数\(\alpha\)用于控制正则ß程度。以回归为例，当经验⻛险项为最小二乘损 失\(L_S(\omega)=(X\omega-Y)^T(X\omega-Y)\)时，若正则项为\(\ell_2\)正则\(\mathcal{R} (\omega)=\Vert\omega\Vert_2^2\)，此时RLM问题为 \[ \min_{\omega}(X\omega-Y)^T(X\omega-Y)+\alpha\Vert\omega\Vert_2^2 \]
其有闭式解\(\omega_*=(X^TX+\alpha I)^{-1}X^TY\); 若正则项为\(\ell_1\)正则\(\mathcal{R}(\omega)=\Vert\omega\Vert_1\)，此时RLM问题为
\[\min_{\omega}(X\omega-Y)^T(X\omega-Y)+\alpha\Vert\omega\Vert_1\] 上述问题又名Lasso问题，可以采用坐标下降方法、近端梯度方法(Proximal Gradient Method, PGM)去解决，且相比\(\ell_2\)正则，\(\ell_1\)正则得到的解更为稀疏。
近端梯度方法解决\(\ell_1\)正则化问题
一般的，考虑如下问题带正则项的机器学习问题
\[\min_{\omega}L_S(\omega)+\alpha\mathcal{R}(\omega)\] 其中\(L_S(\omega)\)具有L-smooth性质，即\(\Vert\nabla_\omega L_S(x)-\nabla_\omega L_S(y)\Vert_2\le L\Vert x-y\Vert_2\)。近端梯度方法处理的方式为迭代地进行如下计算
- 计算
\[ z_k=\omega_k-\frac{1}{L}\nabla L_S(\omega_k) \]
- 求解
\[ \begin{aligned} \omega_{k+1} &= \arg\min_\omega\ \frac{L}{2}\Vert \omega-z_k\Vert_2^2+\alpha \mathcal{R}(\omega) \\ &=\arg\min_\omega\ \frac{1}{2}\Vert \omega-z_k\Vert_2^2+\frac{\alpha}{L} \mathcal{R}(\omega)\\ \end{aligned} \]
第一步中的 \(\nabla L_S(\omega_k)\) 表示\(L_S(\omega)\)在\(\omega=\omega_k\)处的梯度；第二步的计算复杂度则依赖于\(\mathcal{R}(\omega)\)的选取。接下来我们从第二步的计算中抽象出近端算子\(\operatorname{prox}_{h}(x)\)的概念
\[ \operatorname{prox}_{h}(z)=\underset{\omega \in \mathbb{R}^{n}}{\arg \min }\ \frac{1}{2}\|\omega-z\|_{2}^{2}+h(\omega) \]
当\(h(\omega)=\lambda\|\omega\|_{1}\)，\(\lambda>0\)，\(\operatorname{prox}_{h}(x)\)恰为软阈值算子(Soft Thresholding)[1]
\[ \left[\operatorname{prox}_{h}(z)\right]_{i}=\left\{\begin{array}{ll} 0 & \text { if }\left|z_{i}\right| \leq \lambda \\ z_{i}-\lambda & \text { if } z_{i}>\lambda \\ z_{i}+\lambda & \text { if } z_{i}<-\lambda \end{array} \quad i=1, \ldots, n\right.; \]
上述闭式解意味着对于正则项为\(\ell_1\)的RLM问题，近端梯度方法能够高效的解决。
近端梯度方法解决其它正则问题
当\(h(\omega)=\sum_{i=1}^{n}\left(\lambda^{2}-\left(\left|\omega_{i}\right|-\lambda\right)^{2} \mathbb{I}\left(\left|\omega_{i}\right|<\lambda\right)\right)\), \(\operatorname{prox}_{h}(x)\)恰为硬阈值算子(Hard Thresholding)[2]; 当\(h(\omega)=\|\omega\|_{1}-\lambda\|\omega\|_{2}\), [3]给出了闭式解。因此，对于上述两种正则的RLM问题而言，近端梯度方法也能够高效的解决。
近端梯度方法的一种直观理解
回到近端梯度方法处理的问题上来
\[ \min_{\omega}L_S(\omega)+\alpha\mathcal{R}(\omega) \]
近端梯度方法做的事可以理解为分步最优化原目标函数的一个上界 \[ \begin{aligned} L_S(\omega)+\alpha\mathcal{R}(\omega) & \leq L_S(\omega_k)+\left\langle\nabla L_S(\omega_k), \omega-\omega_k\right\rangle+\frac{L}{2}\left\|\omega-\omega_k\right\|_{2}^{2}+\alpha\mathcal{R}(\omega) \\ &=\frac{L}{2}\left\|\omega-\left(\omega_k-\frac{1}{L} \nabla L_S(\omega_k)\right)\right\|_{2}^{2}+\alpha\mathcal{R}(\omega) \\ \end{aligned} \] 第一个不等式可由L-smooth性质得到，而近端梯度方法等价于最小化上式。
[1] Boyd, Stephen, Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[2] Antoniadis, Anestis. "Wavelets in statistics: a review." Journal of the Italian Statistical Society 6.2 (1997): 97.
[3] Lou, Yifei, and Ming Yan. "Fast L1–L2 minimization via a proximal operator." Journal of Scientific Computing 74.2 (2018): 767-785.