大规模机器学习问题在科学、工程、政府等几乎所有领域都变得无处不在. 对于海量数据, 研究人员通常更喜欢只处理一次或几次观察结果的算法. 随机逼近算法, 如随机梯度下降法(SGD), 虽然在60多年前被提出^[1], 但在某些情况下仍然被广泛使用和研究^[2-11].

从前人研究的情况所知, Robbins和Monro^[1]提出了梯度下降法的随机逼近. 此后, SA算法在随机优化和机器学习中得到了广泛的应用. Polyak^[2]及Polyak和Juditsky^[3]提出了SA方法的一个重要改进, 使用了更长的步长, 并对得到的迭代进行了相应的平均. Nemirovski等^[6]证明了镜像下降SA在解决非强凸规划问题时表现出了不可低估的预期速度. Shalev-Shwartz等^[5]和Nemirovski等^[6]研究了强凸情形下的平均SGD, 得到了$ O(1/\mu n) $的速率, 而非强凸情形下仅得到$ O(1/\sqrt{n}) $. Bach和Moulines^[10]考虑并分析了在非强凸情形下, 最小二乘回归和logistic回归学习问题的速率为$ O(1/n) $的随机逼近算法. 最小二乘回归和logistic回归的随机逼近算法的收敛速度几乎都是最优的. 然而, 他们需要一些假设(A1)–(A6). 在较少的假设条件下, 要求最小二乘回归的收敛速度为$ O(1/n) $是很自然的. 本文考虑了一种求解最小二乘回归和logistic回归问题的加速随机逼近型学习算法, 在文献[10]中假设(A1)–(A4) 下, 最小二乘回归学习问题的学习率达到$ O(1/n) $.

为了解决一类凸规划(CP)问题, Nesterov在文献[12]中提出了加速梯度法. 现在, 加速梯度法也被Beck和Teboulle^[13]、Tseng^[14]和Nesterov^[15-16]所推广. 解决一类新出现的复合CP问题. 2012年, Lan^[17]进一步证明了AG方法不仅对于光滑CP问题是最优的, 而且对于一般的非光滑和随机CP问题也是最优的. Ghadimi和Lan^[18-19]提出了加速随机逼近(AC-SA)算法, 并对Nesterov的光滑凸规划优化方法进行了适当的改进. 随后, 他们^[20]开发了一个通用的加速随机逼近(AC-SA)算法框架, 该框架可以专门用于产生求解强凸随机组合优化问题的最优或近似最优方法. 基于上述工作, 我们分别研究和分析了经典最小二乘回归和logistic回归问题的加速SA算法, 该算法的收敛速度为$ O(1/n) $.

本文考虑在欧氏空间中闭凸集上的一个凸函数$ f $的最小化, 由$ f(\theta) = \frac{1}{2}{\Bbb E}\left[\ell\left(y, \langle\theta, x\rangle\right)\right] $给出, 其中$ (x, y)\in X\times {\Bbb R} $表示样本数据, 并且$ \ell $表示相对于第二变量是凸的损失函数. 这种损失函数包括最小二乘回归和logistic回归. 在随机逼近框架中, $ {\bf z} = \{z_{i}\}_{i = 1}^{n} = \{(x_{i}, y_{i})\}_{i = 1}^{n}\in Z^{n} $表示一组随机样本, 这些样本是根据未知概率测度$ \rho $独立抽取的, $ \theta $定义的预测值在每对样本出现后更新.

论文的其余部分组织如下: 第2节简要介绍了最小二乘回归的加速梯度算法; 第3节研究了logistic回归的加速梯度算法; 在第4节中, 将得到的结果与已知的相关工作进行了比较; 最后用所得结果对本文进行了总结.

令$ f(\theta) = \frac{1}{2}{\Bbb E}\left[\ell\left(y_i, \langle\theta, x_i\rangle\right)\right] $, 其中$ (x_i, y_i)\in {\cal X} \times {\cal Y} $表示数据样本, $ \ell $表示损失函数, 样本出现按照未知的概率测量$ \rho $. 令$ (X, d) $是一个紧凑的度量空间, 以及$ Y = {\Bbb R} $. 其中$ \rho $是未知概率分布在$ Z = {\cal X}\times{\cal Y} $上, $ (X, Y) $是相应的随机变量. 给出结果前作如下假设:

(1) 训练数据$ (x_{k}, y_{k}), k\geq1 $, 这些数据在$ \rho $上独立同分布(i.i.d.);

(2) $ {\Bbb E}\|x_k\|^2 $是有界的, 即$ {\Bbb E}\|x_k\|^2\leq M_{1} $对任意的$ k\geq1 $;

(3) $ f(\theta) = \frac{1}{2}{\Bbb E}[\langle\theta, x_{k}\rangle^2-2y_{k}\langle\theta, x_{k}\rangle] $的全局最小值在$ \theta^{*}\in {\Bbb R}^d $这一点上可以获的;

(4) 接下来, 将$ \xi_{k} = \left(y_{k}-\langle\theta_{k}, x_{k}\rangle\right)x_{k} $表示为残差. 假设$ {\Bbb E}||\xi_{i}^2||\leq M^{2} $对于每个$ k $定义$ \overline{\xi}_{k} = \frac{1}{k}\sum\limits_{i = 1}^{k}\xi_{i} $.

这些假定在随机逼近中是基本的, 如文献[8-9].然而, 与工作^[9]相比本文不对协方差算子($ {\Bbb E}[\xi_k\bigotimes\xi_k] $)进行假设.

基于上述(1)–(4)的假设, 提出如下算法:

算法2.1   最小二乘回归的随机加速梯度算法.

Require  $ \theta_0 $ and $ \alpha_1 = 1, \alpha_k >0 $ for $ k = 2, \cdots $, $ \{\beta_k > 0 \} $ and $ \{\lambda_k > 0\} $:

1: Set $ \theta_{0}^{ag}\leftarrow\theta_{0} $, $ \overline{\xi}_0 \leftarrow 0 $ and $ k\leftarrow 1 $;

2: Set $ \theta_{k}^{md}\leftarrow(1-\alpha_{k})\theta_{k-1}^{ag}+\alpha_{k}\theta_{k-1} $;

3: Set $ z_{k}\leftarrow (\nabla f(\theta_{k}^{md})+\eta_{k}\theta_{k}^{md})/\alpha_{k} = \frac{\left(\langle \theta_{k}^{md}, x_{k}\rangle x_{k}-y_{k}x_{k}\right)+\eta_{k}\theta_{k}^{md}}{\alpha_{k}} $;

4: Set $ \theta_{k}\leftarrow\theta_{k-1}-\lambda_{k}z_{k}; $

5: Compute $ \xi_{k}\leftarrow\left(y_{k}-\langle\theta_k, x_{k}\rangle\right)x_{k} $ and $ \overline{\xi}_k \leftarrow \overline{\xi}_{k-1} + \frac{1}{k}(\xi_k - \overline{\xi}_{k-1}) $;

6: Set $ \theta_{k}^{ag}\leftarrow\theta_{k}^{md}-\beta_{k}\left(z_{k}+{\overline{\xi}_{k}}\right); $

7: Set $ k \leftarrow k + 1 $, and goto step 2.

该算法将数据样本$ (x_{k}, y_{k}) $作为输入, 并给出初始的参数$ \theta_{0} $. 其他要求包括: $ {\alpha_{k}} $中$ \alpha_{1} = 1 $和$ \alpha_{k}>0 $, 以及$ \beta_{k}>0 $和$ \lambda_{k}>0 $. 该算法涉及两个中间量$ \theta^{ag} $ (它的初始值也是$ \theta_{0} $)和$ \theta^{md} $. 当数据到达(算法第2行), $ \theta^{md} $被更新为$ \theta^{ag} $和$ \theta $的当前估计的线性组合. 参数$ \theta $估计在算法的第4行. 第$ k+1 $个数据残差和以前$ k $个数据的平均残差计算在算法第5行. 然后, 在算法第6行中以$ \beta_{k} $作为参数更新$ \theta^{ag} $. 每当进来一对新数据时, 该过程将继续进行.

梯度的无偏估计, 即$ \left(\langle \theta_{k}^{md}, x_{k}\rangle x_{k}-y_{k}x_{k}\right) $对于每个数据点$ (x_k, y_k) $计算利用算法的第3行. 从这个角度看, $ \theta_{k} $ (算法第4行)的更新实际上与随机梯度下降(也称为最小均方LMS)算法一样, 如果我们设置$ \alpha_{k} = 1 $.

在训练过程中, 计算出相对残差$ \xi_k $ (算法第5行). 并且所有的残差都是平均的, 平均相对残数对$ \theta^{ag} $更新(算法第6行)起作用. 它不同于随机加速梯度算法在文献[9]中, 在它的训练中没有剩余残差的计算和使用.接下来建立了随机逼近算法的收敛速度.

定理2.1  在假设(1)–(4)满足的情况下, $ \Gamma_{k} $按照定义(2.1)所示, 如果参数$ \{\alpha_{k}\}, \{\beta_{k}\}, $和$ \{\lambda_{k}\} $, 且$ \alpha_{1} = \Gamma_{1} = 1 $, 满足

$ \begin{eqnarray*} 1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M \geq0, \quad \frac{\alpha_{1}^{2}}{\lambda_{1}\Gamma_{1}}\geq\frac{\alpha_{2}^{2}}{\lambda_{2}\Gamma_{2}}\geq\cdots, & 2\beta_{k}^2M-\beta_{k}\alpha_{k} = 0, & \end{eqnarray*} $

则有

$ {\Bbb E}\left[f\left(\theta_{n}^{ag}\right)-f(\theta^{*})\right]\leq \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta^{*}\|^2 +M M_{2}\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2}{k^{2}\Gamma_{k}} +\frac{\eta_{k}}{2}||\theta^{*}||^{2}. $

为了证明定理2.1, 我们需要如下引理2.1 (参见文献[9]).

引理2.1  让$ \alpha_{k} $是算法1中的步长的数组, 同时$ \{\eta_{k}\} $数组满足$ \eta_{k} = (1-\alpha_{k})\eta_{k-1}+\tau_{k}, \ \ k = 1, 2, 7\cdots , $这里

(2.1) $ \begin{eqnarray} \Gamma_{k} = \left\{ \begin{array}{ll} 1, & \ k = 1, \\ (1-\alpha_{k})\Gamma_{k-1}, & \ k\geq 2. \end{array} \right. \end{eqnarray} $

然后有$ \eta_{k}\leq \Gamma_{k}\sum\limits_{i = 1}^{k}\frac{\tau_{i}}{\Gamma_{i}} $, 对任意$ k\geq 1 $.

接下来, 我们证明定理2.1.

证   首先, 令$ \theta_k^{d} = \theta_{k}^{ag}-\theta_{k}^{md} $, $ F(\theta) = f(\theta)+\eta_{k}/2||\theta||^{2} $, $ M = M_{1}+1 $, 其中这里$ 0<\eta_{k}<1 $. 利用函数$ f $的Taylor展开, 算法2.1第3行和第4行, 得到

(2.2) $ \begin{eqnarray} f\left(\theta_{k}^{ag}\right)& = &f(\theta_{k}^{md})+\langle\nabla f(\theta_{k}^{md}), \theta_k^{d}\rangle +\left(\theta_k^{d}\right)^\intercal \nabla^{2}f(\theta_{k}^{md})\theta_k^{d} {}\\ & = &f(\theta_{k}^{md})-\beta_{k}\alpha_{k}\|z_{k}\|^2-\beta_{k}\alpha_{k}\langle z_{k}, \overline{\xi}_{k}\rangle+\beta_{k}^2({\Bbb E}\|x_{k}\|^2)\left\|z_{k}+\overline{\xi}_{k}\right\|^2{}\\ &\leq&f(\theta_{k}^{md})-\beta_{k}\alpha_{k}\|z_{k}\|^2-\beta_{k}\alpha_{k}\langle z_{k}, \overline{\xi}_{k}\rangle+\beta_{k}^2(M_{1}+1)\left \|z_{k}+\overline{\xi}_{k}\right\|^2 {}\\ &\leq&f(\theta_{k}^{md})-\beta_{k}\alpha_{k}\|z_{k}\|^2-\beta_{k}\alpha_{k}\langle z_{k}, \overline{\xi}_{k}\rangle+\beta_{k}^2M\left \|z_{k}+\overline{\xi}_{k}\right\|^2, \end{eqnarray} $

其中第二个不等式利用了假设条件(2). 由于

$ F(\mu)-F(\nu) = \langle \nabla F(\nu), \mu-\nu\rangle+(\mu-\nu)^{T}({\Bbb E}(x_{k}x_{k}^{T})+\eta_{k})(\mu-\nu), $

则

(2.3) $ \begin{eqnarray} \label{5} F(\nu)-F(\mu)& = &\langle \nabla F(\nu), \nu-\mu\rangle-(\mu-\nu)^{T}({\Bbb E}(x_{k}x_{k}^{T})+\eta_{k})(\mu-\nu)\\ &\leq&\langle \nabla F(\nu), \nu-\mu\rangle, \end{eqnarray} $

上述不等式是根据矩阵$ {\Bbb E}(x_{k}x_{k}^\intercal) $的半正定性. 通过算法2.1第2行和不等式(2.2), 有

(2.4) $ \begin{eqnarray} & &F(\theta_{k}^{md})-[(1-\alpha_{k})F(\theta_{k-1}^{ag})+\alpha_{k}F(\theta)] \\ & = &\alpha_{k}[F(\theta_{k}^{md})-F(\theta)]+(1-\alpha_{k})[F(\theta_{k}^{md})-F(\theta_{k-1}^{ag})] \\ &\leq& \alpha_{k}\langle \nabla F(\theta_{k}^{md}), \theta_{k}^{md}-\theta\rangle+(1-\alpha_{k})\langle \nabla F(\theta_{k}^{md}), \theta_{k}^{md}-\theta_{k-1}^{ag}\rangle \\ & = &\langle \nabla F(\theta_{k}^{md}), \alpha_{k}(\theta_{k}^{md}-\theta)+(1-\alpha_{k})(\theta_{k}^{md}-\theta_{k-1}^{ag})\rangle \\ & = &\alpha_{k}\langle \nabla F(\theta_{k}^{md}), \theta_{k-1}-\theta\rangle = \alpha^{2}_{k}\langle z_{k}, \theta_{k-1}-\theta\rangle, \end{eqnarray} $

故有

$ \begin{eqnarray*} F\left(\theta_{k}^{ag}\right)&\leq &(1-\alpha_{k})F(\theta_{k-1}^{ag})+\alpha_{k}F(\theta)+\alpha_{k}^{2}\langle z_{k}, \theta_{k-1}-\theta\rangle \\ &&-\beta_{k}\alpha_{k}\|z_{k}\|^2-\beta_{k}\alpha_{k}\langle z_{k}, \overline{\xi}_{k}\rangle+\beta_{k}^2M\left\|z_{k}+\overline{\xi}_{k}\right\|^2. \end{eqnarray*} $

由算法2.1的第4行, 知

$ \|\theta_{k}-\theta\|^2 = \left\|\theta_{k-1}-\lambda_{k}z_{k}-\theta\right\|^2 = \|\theta_{k-1}-\theta\|^2-2\lambda_{k}\langle z_{k}, \theta_{k-1}-\theta \rangle+\lambda_{k}^2\left\|z_{k}\right\|^2, $

得

$ \langle z_{k}, \theta_{k-1}-\theta \rangle = \frac{1}{2\lambda_{k}}\left[\|\theta_{k-1}-\theta\|^2-\|\theta_{k}-\theta\|^2\right]+\frac{\lambda_{k}}{2}\left\|z_{k}\right\|^2, $

同时

$ \left\|z_{k}+\overline{\xi}_{k} \right\|^2 = \left\|z_{k}\right\|^2+\left\|\overline{\xi}_{k}\right\|^2+2\langle z_{k}, \overline{\xi}_{k}\rangle. $

结合不等式(2.2)和(2.4), 得到

$ \begin{eqnarray*} F\left(\theta_{k}^{ag}\right)&\leq& (1-\alpha_{k})F(\theta_{k-1}^{ag})+\alpha_{k}F(\theta)+\frac{\alpha_{k}^{2}}{2\lambda_{k}} \left[\|\theta_{k-1}-\theta\|^2-\|\theta_{k}-\theta\|^2\right]\\ &&-\beta_{k}\alpha_{k}\left(1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M\right)\|z_{k}\|^2 +M\beta_{k}^2\left\|\overline{\xi}_{k}\right\|^2+\langle\overline{\xi}_{k}, (2\beta_{k}^2M-\beta_{k}\alpha_{k})z_{k}\rangle. \end{eqnarray*} $

由上述不等式, 得

$ \begin{eqnarray*} F\left(\theta_{k}^{ag}\right)-F(\theta)&\leq & (1-\alpha_{k})[F(\theta_{k-1}^{ag})-F(\theta)]+\frac{\alpha_{k}^{2}}{2\lambda_{k}}\left[\|\theta_{k-1}-\theta\|^2-\|\theta_{k}-\theta\|^2\right]\\ &&-\beta_{k}\alpha_{k}\left(1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M\right)\|z_{k}\|^2 +M\beta_{k}^2\left\|\overline{\xi}_{k}\right\|^2+\langle\overline{\xi}_{k}, (2\beta_{k}^2M-\beta_{k}\alpha_{k})z_{k}\rangle. \end{eqnarray*} $

由引理2.1, 知

$ \begin{eqnarray*} F\left(\theta_{n}^{ag}\right)-F(\theta)&\leq& \Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\alpha_{k}^{2}}{2\lambda_{k}\Gamma_{k}} \left[\|\theta_{k-1}-\theta\|^2-\|\theta_{k}-\theta\|^2\right] +\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2M}{\Gamma_{k}}\left\|\overline{\xi}_{k}\right\|^2\\ &&-\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}\alpha_{k}}{\Gamma_{k}}\left(1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M\right)\|z_{k}\|^2 \\ &&+\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{1}{\Gamma_{k}}\langle\overline{\xi}_{k}, (2\beta_{k}^2M-\beta_{k}\alpha_{k})z_{k}\rangle. \end{eqnarray*} $

因为

$ \frac{\alpha_{1}^{2}}{\lambda_{1}\Gamma_{1}}\geq\frac{\alpha_{2}^{2}}{\lambda_{2}\Gamma_{2}}\geq\cdots, \ \alpha_{1} = \Gamma_{1} = 1, $

所以

$ \begin{eqnarray*} \sum\limits_{k = 1}^{n}\frac{\alpha_{k}^{2}}{2\lambda_{k}\Gamma_{k}}\left[\|\theta_{k-1}-\theta\|^2-\|\theta_{k}-\theta\|^2\right] \leq\frac{\alpha_{1}^{2}}{2\lambda_{1}\Gamma_{1}}\left[\|\theta_{0}-\theta\|^2\right] = \frac{1}{2\lambda_{1}}\|\theta_{0}-\theta\|^2. \end{eqnarray*} $

故有

$ F\left(\theta_{n}^{ag}\right)-F(\theta) \leq \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta\|^2 +\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2M}{\Gamma_{k}}\left\|\overline{\xi}_{k}\right\|^2 +\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{1}{\Gamma_{k}}\langle\overline{\xi}_{k}, (2\beta_{k}^2M-\beta_{k}\alpha_{k})z_{k} \rangle, $

所以

(2.5) $ \begin{eqnarray} f\left(\theta_{n}^{ag}\right)-f(\theta) & = & F\left(\theta_{n}^{ag}\right)-F(\theta)-\left[\frac{\eta_{n}}{2}||\theta_{n}^{ag}||^{2}-\frac{\eta_{n}}{2}||\theta||^{2}\right]{}\\ &\leq&F\left(\theta_{n}^{ag}\right)-F(\theta)+\frac{\eta_{n}}{2}||\theta||^{2}{}\\ &\leq& \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta\|^2 +\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2M} {\Gamma_{k}}\left\|\overline{\xi}_{k}\right\|^2+ \frac{\eta_{n}}{2}||\theta||^{2} {}\\ & &+\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{1}{\Gamma_{k}}\langle\overline{\xi}_{k}, (2\beta_{k}^2M-\beta_{k}\alpha_{k})z_{k})\rangle, \end{eqnarray} $

最后一个不等式, 来自下面的假设

$ 1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M \geq0, \ \ 2\beta_{k}^2M-\beta_{k}\alpha_{k} = 0. $

由假设(4), 有

$ \begin{eqnarray*} {\Bbb E}\left\|\bar{\xi_{k}}\right\|^2 = {\Bbb E}\left\{\frac{1}{k^{2}}\|\sum\limits_{i = 1}^{k}\xi_{i}\|^2\right\}\leq {\Bbb E}\left\{\frac{1}{k^{2}}k\sum\limits_{i = 1}^{k}\|\xi_{i}\|^2\right\}\leq M_{2}. \end{eqnarray*} $

对不等式(2.5)两边对$ (x_{i}, y_{i}) $取期望, 有

$ \begin{eqnarray*} {\Bbb E}\left[f\left(\theta_{n}^{ag}\right)-f(\theta)\right]&\leq& \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta\|^2 +M M_{2}\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2}{\Gamma_{k}}+\frac{\eta_{n}}{2}||\theta||^{2}. \end{eqnarray*} $

取$ \theta = \theta^{*} $, 有

$ \begin{eqnarray*} {\Bbb E}\left[f\left(\theta_{n}^{ag}\right)-f(\theta^{*})\right]&\leq& \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta^{*}\|^2 +M M_{2}\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2}{\Gamma_{k}}+\frac{\eta_{n}}{2}||\theta^{*}||^{2}. \end{eqnarray*} $

引理2.1证毕.

通过对$ \{\alpha_{k}\}, \{\beta_{k}\} $和$ \{\lambda_{k}\} $等参数的选择, 获得如下推论.

推论2.1  假设回归学习的加速梯度算法中的$ \alpha_{k} $, $ \beta_{k} $和$ \eta_{k} $满足

$ \begin{eqnarray*} \label{7} \alpha_{k} = \frac{2}{k+1}, \quad \beta_{k} = \frac{1}{M(k+1)}, \; \; \eta_{k} = \frac{1}{k(k+1)}, \; \; \lambda_{k} = \frac{k}{2M(k+1)}, \qquad \forall k\geq 1, \end{eqnarray*} $

则对任意的$ n\geq 1 $, 有

$ {\Bbb E}\left[f\left(\theta_{n}^{ag}\right)-f(\theta^{*})\right]\leq \frac{4M}{n(n+1)}\|\theta_{0}-\theta^{*}\|^2 +\frac{M_{1}}{M n(n+1)} +\frac{1}{2n(n+1)}||\theta^{*}||^{2}. \label{cor1} $

证   利用引理2.1中(2.1)式和推论2.1的结果, 当$ k\geq 2 $, 有

$ \begin{eqnarray*} \Gamma_{k} = (1-\alpha_{k})\Gamma_{k-1} = \frac{k-1}{k+1}\times \cdots\times\frac{1}{3}\times\Gamma_{1} = \frac{2}{k(k+1)}. \end{eqnarray*} $

显然有

$ 1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M \geq0, \quad 2\beta_{k}^2M-\beta_{k}\alpha_{k} = 0, \; \; \frac{\alpha_{1}^{2}}{\lambda_{1}\Gamma_{1}} = \frac{\alpha_{2}^{2}}{\lambda_{2}\Gamma_{2}} = \cdots = 4M, $

从而有

$ M\Gamma_{n}M_{2}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2}{\Gamma_{k}} = \frac{2M_{2}}{n(n+1)}\sum\limits_{k = 1}^{n}\frac{\frac{M}{M^2(k+1)^2}}{\frac{2}{k(k+1)}} = \frac{M_{2}}{M n(n+1)}\sum\limits_{k = 1}^{n}\frac{k(k+1)}{(k+1)^{2}}\leq\frac{M_{2}}{M (n+1)}. $

从定理2.1的结果, 可得到

$ \begin{eqnarray*} {\Bbb E}\left[f\left(\theta_{n}^{ag}\right)-f(\theta^{*})\right]&\leq& \frac{4M}{n(n+1)}\|\theta_{0}-\theta^{*}\|^2 +\frac{M_{2}}{M(n+1)}+\frac{1}{2n(n+1)}||\theta^{*}||^{2}. \end{eqnarray*} $

推论2.1证毕.

推论2.1表明, 在没有强凸性和Lipschitz连续梯度假设的情况下, 所提出的随机加速算法能够达到$ O(1/n) $的收敛速度.

本章考虑逻辑损失函数: $ l(\theta) = {\Bbb E}[\log(1+\exp(-y\langle x, \theta\rangle))] $.在这一部分, 假设观察数据$ (x_{i}, y_{i})\in {\cal F}\times\{0, 1\} $是未知分布$ \rho $上的独立同分布, 这里的$ {\cal F} $是$ d $维欧式空间, 同时$ d\geq1 $. 接着, 我们定义$ \theta^{*}\in {\Bbb R}^d $是$ l $的全局极小值, $ \xi_{i} = \left(y_{i}-\langle\theta_{k}, x_{i}\rangle\right)x_{i} $是残差, $ \bar{\xi}_{k} = \frac{1}{k}\sum\limits_{i = 1}^{k}\xi_{i} $是$ k $个数据进入的平均残差.为了分析算法, 给出下面假设:

(B1) $ {\Bbb E}\|x_{i}\|^2 $是有界的, 即$ {\Bbb E}\|x_i\|^2\leq M_{1} $对任意的$ i\geq1 $;

(B2) $ {\Bbb E}\|\xi_{i}\|^2\leq M_{2} $对于每一个$ i $.

同样, 与Bach等人文献[11]的算法不同, 对Hessian算子不作全局最优的假设.

在算法3.1展示了Logistic回归的加速随机梯度算法.在该算法中, $ \theta_0 \in {\cal F} $是一个初始值, 并

$ \nabla l(\theta_{k}) = \frac{-y_{k}\exp\{-y_{k}\langle x_{k}, \theta_{k}\rangle\}x_{k}}{1+\exp\{-y_{k}\langle x_{k}, \theta_{k}\rangle\}} $

算法3.1  逻辑回归的加速随机梯度近似算法.

Require   $ \theta_0 $ and $ \alpha_1 = 1, \alpha_k >0 $ for $ k = 2, \cdots $, $ \{\beta_k > 0 \} $ and $ \{\lambda_k > 0\} $.

1: Set $ \theta_{0}^{ag}\leftarrow\theta_{0} $, $ \overline{\xi}_0 \leftarrow 0 $ and $ k\leftarrow 1 $,

2: Set $ \theta_{k}^{md}\leftarrow (1-\alpha_{k})\theta_{k-1}^{ag}+\alpha_{k}\theta_{k-1} $,

3: Compute $ z_{k}\leftarrow \frac{1}{\alpha_{k}}(\nabla l(\theta_{k}^{md})+\eta_{k}\theta_{k}^{md}), $

4: Set $ \theta_{k}\leftarrow \theta_{k-1}-\lambda_{k}z_{k}, $

5: Compute $ \xi_{k}\leftarrow \left(y_{k}-\langle\theta_k, x_{k}\rangle\right)x_{k} $ and $ \overline{\xi}_k \leftarrow\overline{\xi}_{k-1} + \frac{1}{k}(\xi_k - \overline{\xi}_{k-1}) $;

6: Set $ \theta_{k}^{ag}\leftarrow\theta_{k}^{md}-\beta_{k}\left(z_{k}+\bar{\xi}_{k}\right). $

7: Set $ k \leftarrow k + 1 $, and goto step 2.

算法3.1的基本框架与算法2.1相同, 除了梯度的无偏估计是由不同的损失函数求导的.接下来, 对算法的收敛速度进行了非渐近分析, 得到加速随机梯度算法的收敛速度.

定理3.1   让$ \{\theta_{k}^{md}, \theta_{k}^{ag}\} $按照上述加速算法计算, 在假设(B1)–(B2)满足的情况下, 按照$ \Gamma_{k} $定义(2.1)所示, 如果选择满足下面条件的$ \{\alpha_{k}\}, \{\beta_{k}\} $和$ \{\lambda_{k}\} $, $ \alpha_{1} = \Gamma_{1} = 1 $,

$ 1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M \geq0, \ \ 2\beta_{k}^2M-\beta_{k}\alpha_{k} = 0, \; \; \frac{\alpha_{1}^{2}}{\lambda_{1}\Gamma_{1}}\geq\frac{\alpha_{2}^{2}}{\lambda_{2}\Gamma_{2}}\geq\cdots, $

然后, 对于任意$ n\geq 1 $, 有

$ {\Bbb E}\left[l\left(\theta_{n}^{ag}\right)-l(\theta^{*})\right]\leq \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta^{*}\|^2 +M\sigma^2\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2}{k^{2}\Gamma_{k}} +\frac{\eta_{k}}{2}||\theta^{*}||^{2}. $

证   让$ L(\theta) = l(\theta)+(\eta_{k}/2)||\theta||^{2} $.利用函数$ L $的Taylor展开, 存在$ \vartheta $使得

(3.1) $ \begin{eqnarray} L\left(\theta_{k}^{ag}\right)& = &L(\theta_{k}^{md})+\langle\nabla L(\theta_{k}^{md}), \theta_{k}^{d}\rangle +\left(\theta_{k}^{d}\right)^{T}\nabla^{2}L(\vartheta)\theta_{k}^d{}\\ & = &L(\theta_{k}^{md})-\beta_{k}\alpha_{k}\|z_{k}\|^2-\beta_{k}\alpha_{k}\langle z_{k}, \frac{1}{k}\bar{\xi}_{k}\rangle{}\\ &&+\left(\theta_{k}^d\right)^{T}({\Bbb E}\left[\frac{\exp\{-y_{k}\langle x_{k}, \vartheta\rangle\}x_{k}x_{k}^{T}}{1+\exp\{-y_{k}\langle x_{k}, \vartheta\rangle\}}\right]+\eta_{k})\theta_{k}^d, \end{eqnarray} $

在上式中, 由于

$ \begin{eqnarray*} \frac{\exp\{-y_{k}\langle x_{k}, \vartheta\rangle\}}{1+\exp\{-y_{k}\langle x_{k}, \vartheta\rangle\}}\leq1, \ \ \lambda_{max}(x_{k}x_{k}^{T})\leq\|x_{k}\|^{2}. \end{eqnarray*} $

很容易验证下面这个矩阵是半正定的

$ \begin{eqnarray*} {\Bbb E}\left[\frac{\exp\{-y_{k}\langle x_{k}, \vartheta\rangle\}x_{k}x_{k}^{T}}{1+\exp\{-y_{k}\langle x_{k}, \vartheta\rangle\}}\right], \end{eqnarray*} $

其最大特征值满足

$ \begin{eqnarray*} \lambda_{\max}\left({\Bbb E}\left[\frac{\exp\{-y_{k}\langle x_{k}, \vartheta\rangle\}x_{k}x_{k}^{T}}{1+\exp\{-y_{k}\langle x_{k}, \vartheta\rangle\}}\right]\right)\leq {\Bbb E}\|x_{k}\|^2\leq M_{1}. \end{eqnarray*} $

结合算法3.1第4行和式(3.1), 令$ M = M_{1}+1 $, 有

$ L\left(\theta_{k}^{ag}\right)\leq L(\theta_{k}^{md})-\beta_{k}\alpha_{k}\|z_{k}\|^2-\beta_{k}\alpha_{k}\langle z_{k}, \bar{\xi}_{k}\rangle+\beta_{k}^2M \|z_{k}+\bar{\xi}_{k}\|^2. $

对比式(3.1), 存在$ \zeta\in {\Bbb R}^d $满足

$ \begin{eqnarray*} L(\mu)-L(\nu)& = &\langle \nabla L(\nu), \mu-\nu\rangle \\ &&+(\mu-\nu)^\intercal ({\Bbb E}\left[\frac{\exp\{-y_{k}\langle x_{k}, \zeta\rangle\}x_{k}x_{k}^\intercal}{1+\exp\{-y_{k}\langle x_{k}, \zeta\rangle\}}\right]+\eta_{k})(\mu-\nu), \mu, \nu\in {\Bbb R}^d, \end{eqnarray*} $

有

$ \begin{eqnarray*} L(\nu)-L(\mu) & = &\langle \nabla L(\nu), \nu-\mu\rangle -(\mu-\nu)^{T}({\Bbb E}\left[\frac{\exp\{-y_{k}\langle x_{k}, \zeta\rangle\}x_{k}x_{k}^{T}}{1+\exp\{-y_{k}\langle x_{k}, \zeta\rangle\}}\right]+\eta_{k})(\mu-\nu)\\ &\leq&\langle \nabla l(\nu), \nu-\mu\rangle, \end{eqnarray*} $

这里的不等式是因为半正定矩阵, 类似式(2.4), 有

$ \begin{eqnarray*} L(\theta_{k}^{md})-[(1-\alpha_{k})L(\theta_{k-1}^{ag})+\alpha_{k}L(\theta)]\leq \alpha_{k}^{2}\langle z_{k}, \theta_{k-1}-\theta\rangle. \end{eqnarray*} $

所以得到

$ \begin{eqnarray*} L\left(\theta_{k}^{ag}\right)&\leq& (1-\alpha_{k})L(\theta_{k-1}^{ag})+\alpha_{k}L(\theta)+\alpha_{k}^{2}\langle z_{k}, \theta_{k-1}-\theta\rangle\\ &&-\beta_{k}\alpha_{k}\|z_{k}\|^2-\beta_{k}\alpha_{k}\langle z_{k}, \frac{1}{k}\bar{\xi}_{k}\rangle +\beta_{k}^2M\|z_{k}+\bar{\xi}_{k}\|^2. \end{eqnarray*} $

从算法3.1第4行有

$ \|\theta_{k}-\theta\|^2 = \left\|\theta_{k-1}-\lambda_{k}z_{k}-\theta\right\|^2 = \|\theta_{k-1}-\theta\|^2-2\lambda_{k}\langle z_{k}, \theta_{k-1}-\theta \rangle +\left\|z_{k}\right\|^2. $

结合式(3.1), 有

$ \begin{eqnarray*} L\left(\theta_{k}^{ag}\right)&\leq& (1-\alpha_{k})L(\theta_{k-1}^{ag})+\frac{\alpha_{k}^{2}}{2\lambda_{k}} \left[\|\theta_{k-1}-\theta\|^2-\|\theta_{k}-\theta\|^2\right]\\ &&+\alpha_{k}L(\theta)-\beta_{k}\alpha_{k}\left(1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M\right)\|z_{k}\|^2\\ &&+M\beta_{k}^2\left\|\overline{\xi}_{k}\right\|^2+\langle\overline{\xi}_{k}, (2\beta_{k}^2M-\beta_{k}\alpha_{k})z_{k})\rangle. \end{eqnarray*} $

由上述不等式, 得到

$ \begin{eqnarray*} L\left(\theta_{k}^{ag}\right)-L(\theta) &\leq& (1-\alpha_{k})[L(\theta_{k-1}^{ag})-L(\theta)] +\frac{\alpha_{k}^{2}}{2\lambda_{k}}[\|\theta_{k-1}-\theta\|^2\\ && -\|\theta_{k}-\theta\|^2]-\beta_{k}\alpha_{k}\left(1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M\right)\|z_{k}\|^2\\ && +M\beta_{k}^2\left\|\overline{\xi}_{k}\right\|^2+\langle\overline{\xi}_{k}, (2\beta_{k}^2M-\beta_{k}\alpha_{k})z_{k}\rangle. \end{eqnarray*} $

利用引理2.1, 有

$ \begin{eqnarray*} L\left(\theta_{n}^{ag}\right)-L(\theta)&\leq& \Gamma_{n}\sum\limits_{k = 1}^{n} \frac{\alpha_{k}^{2}}{2\lambda_{k}\Gamma_{k}}\left[\|\theta_{k-1}-\theta\|^2-\|\theta_{k}-\theta\|^2\right] +\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2M}{\Gamma_{k}}\left\|\overline{\xi}_{k}\right\|^2\\ &&-\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}\alpha_{k}}{\Gamma_{k}}\left(1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M\right)\|z_{k}\|^2\\ &&+\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{1}{\Gamma_{k}}\langle\overline{\xi}_{k}, (2\beta_{k}^2M-\beta_{k}\alpha_{k})z_{k})\rangle. \end{eqnarray*} $

因为

$ \frac{\alpha_{1}^{2}}{\lambda_{1}\Gamma_{1}}\geq\frac{\alpha_{2}^{2}}{\lambda_{2}\Gamma_{2}}\geq\cdots, \ \alpha_{1} = \Gamma_{1} = 1, $

然后

$ \sum\limits_{k = 1}^{n}\frac{\alpha_{k}^{2}}{2\lambda_{k}\Gamma_{k}}\left[\|\theta_{k-1}-\theta\|^2-\|\theta_{k}-\theta\|^2\right] \leq\frac{\alpha_{1}^{2}}{2\lambda_{1}\Gamma_{1}}\left[\|\theta_{0}-\theta\|^2\right] = \frac{1}{2\lambda_{1}}\|\theta_{0}-\theta\|^2, $

得到

$ \begin{eqnarray*} \label{12} L\left(\theta_{n}^{ag}\right)-L(\theta)\leq \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta\|^2+\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2M}{\Gamma_{k}}\left\|\overline{\xi}_{k}\right\|^2, \end{eqnarray*} $

这里的不等式用了定理的条件

$ 1-\frac{\lambda_{k}\alpha_{k}}{2\beta_{k}}-\frac{\beta_{k}}{\alpha_{k}}M \geq0, \ \ 2\beta_{k}^2M-\beta_{k}\alpha_{k} = 0. $

然后, 有

(3.2) $ \begin{eqnarray} l\left(\theta_{n}^{ag}\right)-l(\theta) & = & L\left(\theta_{n}^{ag}\right)-L(\theta)-\left[\frac{\eta_{n}}{2}||\theta_{n}^{ag}||^{2}-\frac{\eta_{n}}{2}||\theta||^{2}\right]\\ &\leq&F\left(\theta_{n}^{ag}\right)-F(\theta)+\frac{\eta_{n}}{2}||\theta||^{2}\\ &\leq& \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta\|^2 +\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2M}{\Gamma_{k}}\left\|\overline{\xi}_{k}\right\|^2+ \frac{\eta_{n}}{2}||\theta||^{2}, \end{eqnarray} $

根据假设(B2), 有

$ \begin{eqnarray*} {\Bbb E}\left\|\bar{\xi_{k}}\right\|^2 = {\Bbb E}\left\{\frac{1}{k^{2}}\|\sum\limits_{i = 1}^{k}\xi_{i}\|^2\right\}\leq {\Bbb E}\left\{k\sum\limits_{i = 1}^{k}\|\xi_{i}\|^2\right\}\leq M_{2}. \end{eqnarray*} $

对不等式(3.2)关于$ (x_{i}, y_{i}) $取期望, 得到

$ \begin{eqnarray*} {\Bbb E}\left[l\left(\theta_{n}^{ag}\right)-l(\theta)\right]\leq \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta\|^2 +M M_{2}\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2}{\Gamma_{k}} +\frac{\eta_{n}}{2}||\theta||^{2}. \end{eqnarray*} $

取$ \theta = \theta^{*} $, 有

$ \begin{eqnarray*} {\Bbb E}\left[l\left(\theta_{n}^{ag}\right)-l(\theta^{*})\right]\leq \frac{\Gamma_{n}}{2\lambda_{1}}\|\theta_{0}-\theta^{*}\|^2 +M M_{2}\Gamma_{n}\sum\limits_{k = 1}^{n}\frac{\beta_{k}^2}{\Gamma_{k}} +\frac{\eta_{n}}{2}||\theta^{*}||^{2}. \end{eqnarray*} $

定理3.1证毕.

类似于定理3.1, 选择特定的$ \{\alpha_{k}\}, \{\beta_{k}\} $及$ \{\lambda_{k}\} $, 得到下面的推论.

推论3.1   假设逻辑回归的加速梯度算法中的$ \alpha_{k} $, $ \beta_{k} $和$ \eta_{k} = \frac{1}{k(k+1)} $满足

$ \alpha_{k} = \frac{2}{k+1}, \; \beta_{k} = \frac{1}{M(k+1)}, \; \eta_{k} = \frac{1}{k(k+1)}, \; \lambda_{k} = \frac{k}{2M(k+1)}, \quad \forall k\geq 1, $

对于任意的$ x_{n}\geq 1 $, 有

$ \begin{eqnarray*} {\Bbb E}\left[l\left(\theta_{n}^{ag}\right)-l(\theta^{*})\right]\leq \frac{4M}{(n+1)}\|\theta_{0}-\theta^{*}\|^2 +\frac{M_{2}}{M n(n+1)} +\frac{1}{2n(n+1)}||\theta^{*}||^{2}. \end{eqnarray*} $

推论3.1表明, 在没有强凸性和Lipschitz连续梯度假设的情况下, 所提出的算法能够达到$ O(1/n) $的收敛速度.

第二节和第三节分别研究了最小二乘回归和最小二乘学习问题的加速随机逼近型算法. 利用目标函数的凸性, 得出了加速随机逼近学习算法的上界. 在本节中, 将讨论本文的研究结果与其他近期研究的关系.

本文对随机逼近学习算法的收敛性分析是基于Ghadimi和Lan在文献[17]中对随机组合优化的类似分析. 我们的工作与Ghadimi和Lan的工作有两个不同之处. 与文献[8]中的随机优化问题相比, 随机逼近算法收敛性分析中的第一个区别是针对任何迭代, 而不是迭代极限, 即文献[8]中推论3的参数$ \beta_{k}, \lambda_{k} $与迭代极限$ N $有关, 并且在假设条件上也弱一点. 第二个差别在两个误差范围. Ghadimi和Lan得到了随机组合优化的比率$ O(1/\sqrt{n}) $, 而我们得到了回归问题的比率$ O(1/n) $.

Bach和Moulines^[9]的工作可能与我们的工作密切相关, 他们研究了凸函数极小化的随机逼近问题, 需要要求其在某些点的梯度的无偏估计, 其中包括基于经验风险最小化的机器学习方法. Bach和MouLein所考虑的样本设置与我们的相似：学习者给出了样本集$ \{(x_{i}, y_{i})\}_{i = 1}^{n} $, 回归学习问题的目的是学习线性函数$ \langle\theta, x\rangle $参数. 在没有强凸性假设的情况下, 本文和Bach和Moulines得到了最小二乘回归随机逼近算法的$ O(1/n) $收敛速率.

在本文中考虑了两种随机逼近(SA)算法, 经典最小二乘回归和logistic回归问题的加速SA算法, 该算法的收敛速度为$ O(1/n) $. 与已知的结果相比, 我们只需要较少的条件就可以得到最小二乘回归和logistic回归问题的收敛速度. 对于加速SA算法, 我们给出了推广误差的非渐近分析（期望值）, 并对我们的理论分析进行了研究.