邻近梯度下降法

　　对于无约束凸优化问题，当目标函数可微时，可以采用梯度下降法求解；当目标函数不可微时，可以采用次梯度下降法求解；当目标函数中同时包含可微项与不可微项时，常采用邻近梯度下降法求解。上述三种梯度算法均属于离线批处理类型算法，在大规模的数据问题中，每次迭代都需要计算整个数据集梯度，因而需要较大的计算代价和存储空间。在线邻近梯度法（Online Proximal Gradient，OPG）是随即优化算法与临近梯度算法的结合，是一种典型的随机优化方法，以单个或小批量采样数据而实现数据实时处理。

　　考虑如下目标函数可分解为两部分的凸优化问题：

\begin{equation}\label{E1}
\min _{x} f(x)+g(x),
\end{equation}

其中$x$为优化变量，$f(x)$为光滑可微凸损失函数，$g(x)$是不可微的凸函数，一般为正则项。邻近梯度算法对其中的不可微项$g(x)$保持不变，可微项$f(x)$在$k$步迭代值$x_k$处做一阶Taylor展开，并加入二阶邻近项，对\eqref{E1}式的邻近梯度下降为：

\begin{aligned}
x_{k+1} &=\underset{u}{\arg \min } g(u)+f\left(x_{k}\right)+\nabla f\left(x_{k}\right)^{T}\left(u-x_{k}\right)+(1 / 2 \tau)\left\|u-x_{k}\right\|_{2}^{2} \\
&=\underset{u}{\operatorname{argmin}} g(u)+\frac{1}{2 \tau} \| u-\left.\left(x_{k}-t \nabla f\left(x_{k}\right)\right)\right|_{2} ^{2} \\
&=\operatorname{prox}_{\tau g}\left(x_{k}-\tau \nabla f\left(x_{k}\right)\right)
\end{aligned}

其中$\tau$为梯度步长，$\operatorname{prox}_{\tau g}(\cdot)$为邻近算子，根据$g(x)$形式有不同的定义，当$g(x)$为0时，邻近梯度算法退化为梯度下降算法；当$g(x)$为示性函数时，邻近算子为投影算符；当$g(x)$为$l_1$范数时，邻近算子为软阈值收缩算子。

在线邻近梯度下降法中，$f(x)$可以为不可微凸函数，将其利用次梯度线性化处理，同时也加入邻近项，可得：

\begin{equation}\label{E3}
x_{k+1}=\arg \min \left\{f_{k}^{T} x+g(x)+\left(1 / 2 \eta_{k}\right)\left\|x-x_{k}\right\|_{2}^{2}\right\}
\end{equation}

其中，次梯度$f_k$为$f(x)$的在$k$步迭代值$x_k$处近似，线性化处理目的是简化计算；$\left(1 / 2 \eta_{k}\right)\left\|x-x_{k}\right\|_{2}^{2}$为在$x_k$处的二次正则项，也称邻近项，目的是使得$x_{k+1}$和$x_{k}$相距较近，同时随着迭代收敛，$x_{k+1}$逐渐接近$x_{k}$，邻近项逐渐接近于0，所以可认为邻近项的目的是加快收敛，同时不会影响最终结果；$\eta_{k}>0$为邻近步长参数。

关于次梯度（Subgradient）