基于1/t-Polyak步长的随机控制的随机梯度算法

1/t-Polyak Stepsize for the Stochastically Controlled Stochastic Gradient Algorithm

摘要: 随机梯度下降算法已成为求解大规模有限和优化问题的流行算法，然而，由于其在迭代过程中会产生方差，导致了振荡现象。随机控制的随机梯度(SCSG)算法缩减了该方差，但SCSG算法对于步长有较强的限制。为了扩大SCSG算法的步长选择范围，基于1/t-带步长与Polyak步长，提出1/t-Polyak步长，并将其与SCSG算法结合，提出SCSGP算法。建立了SCSGP算法在强凸条件下的线性收敛性，数值实验表明SCSGP算法与其他随机梯度类算法相比有明显优势。

Abstract: The stochastic gradient descent algorithm has become popular algorithm for solving large-scale finite-sum optimization problems. However, this algorithm leads to oscillations due to the variance in the iterative process. The stochastically controlled stochastic gradient (SCSG) algorithm reduces this variance, but the SCSG algorithm has strong limit on stepsize. To expand the range of stepsize selection of the SCSG algorithm, we propose 1/t-Polyak stepsize by combining the 1/t-band stepsize and the Polyak stepsize. Using this new stepsize for the stochastically controlled stochastic gradient (SCSG) algorithm, the SCSGP algorithm is proposed. We establish the linear convergence rate of SCSGP for strongly convex problems. Numerical experiments demonstrate a clear advantage of SCSGP over other stochastic gradient algorithms.

1. 引言

考虑有限和优化问题：

$\underset{x\in {\Re }^d}{\min }f\left(x\right)=\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{f}_i}\left(x\right)$ ， (1)

其中分量函数 $f_i\left(x\right)$ 连续可微，假设 $f\left(x\right)$ 是强凸的。机器学习中满足条件的优化问题有很多，例如带 ${\mathcal{l}}_2$ 正则项的逻辑回归问题和带 ${\mathcal{l}}_2$ 正则项的最小平方回归问题等 [1] [2] [3] 。

当数据规模过大时，随机梯度下降(SGD)算法 [4] 是求解问题(1)的主流算法，即用随机梯度估计全梯度，其迭代格式为

$x_{t+1}=x_t-{\eta }_t\nabla f_{i_t}\left(x_t\right)$ ，

其中 ${\eta }_t>0$ 是步长， $\nabla f_{i_t}\left(x_t\right)$ 是分量函数 $f_{i_t}\left(x\right)$ 在 $x_t$ 处的梯度。随机梯度 $\nabla f_{i_t}\left(x_t\right)$ 与全梯度 $\nabla f\left(x_t\right)$ 之间的方差导致SGD即使在强凸条件下，也只能达到次线性收敛速度 [5] 。方差缩减梯度(SVRG)算法 [6] 通过内外两层循环达到缩减方差的目的，但由于其在外循环中需要计算全梯度且内循环次数较大，导致数据规模过大时计算量大。为了改善这个问题，SCSG [7] 令内循环次数服从几何分布且在外循环中计算批量梯度

$\tilde{g}=\frac{1}{\left|I_t\right|}{\displaystyle \underset{i\in I_t}{\sum }\nabla f_i}\left(\tilde{x}\right)$ ，

其中 $I_t\subset \left[n\right]$ ， $\left|I_t\right|$ 为 $I_t$ 的批量大小， $\tilde{x}$ 为在外循环中设置的快照点。在内循环中，SCSG用与SVRG相同的格式更新梯度估计量：

$g_t=\nabla f_{i_t}\left(x_t\right)-\nabla f_{i_t}\left(\tilde{x}\right)+\tilde{g}$ 。

在强凸条件下，其使用固定批量可线性收敛到解的邻域。SCSG适用于求解大规模 $n\in \left[{10}^4,{10}^9\right]$ 、低精度 $\epsilon \in \left[{10}^{-4},{10}^{-2}\right]$ 的优化问题 [7] [8] [9] ，可以经过很少的有效循环次数收敛到上述目标精度。

步长是保证随机梯度类算法收敛的关键因素，很小的常数步长和衰减步长都会使算法收敛缓慢，并且手动调整常数步长的过程相当耗时 [10] [11] [12] 。Polyak步长 [13] 利用迭代过程中产生的函数值和梯度自动地计算步长，避免了手动调整的过程，其计算公式为

${\eta }_t=2\frac{f\left(x_t\right)-f^{*}}{{\Vert \nabla f\left(x_t\right)\Vert }^2}$ ，

其中 $f^{*}$ 是 $f\left(x\right)$ 的极小值。为了将Polyak步长与随机梯度类算法结合，Loizou等人 [14] 提出Polyak步长的随机版本(SPS)：

${\eta }_t=2\frac{f_{i_t}\left(x_t\right)-f_{i_t}^{*}}{{\Vert \nabla f_{i_t}\left(x_t\right)\Vert }^2}$ ，

其中 $f_{i_t}^{*}$ 是 $f_{i_t}\left(x\right)$ 的极小值。SGD结合SPS步长比结合固定步长数值表现好。当SPS步长中 $f_{i_t}^{*}$ 不易求解时，可用一个下界 ${\mathcal{l}}_{i_t}^{*}\le f_{i_t}^{*}$ 来替换 [15] 。最近，Wang等人 [16] 介绍了1/t-带步长，其允许步长在一定范围内扰动，具体格式为

$\frac{m}{t}\le {\eta }_t\le \frac{M}{t}$ ， $\forall t\ge 1$ ，

其中 $m\le M$ 是正常数。显然，衰减步长 ${\eta }_t={\eta }_0/t$ 是1/t-带步长的特殊情况。

受1/t-带步长和Polyak步长启发提出1/t-Polyak步长，并将其与SCSG结合提出新的算法——SCSGP。在强凸光滑的条件下，SCSGP结合变化的批量可达到线性收敛速度。数值实验结果表明SCSGP比SCSG及其他随机梯度类算法表现好。

论文其余部分概括如下：在第2部分中提出1/t-Polyak步长并描述SCSGP算法。收敛性分析在第3部分。在第4部分中设置了数值实验。最后在第5部分进行总结。

2. 1/t-Polyak步长与SCSGP算法

首先，利用Polyak步长的随机版本并将其与1/t-带步长结合，提出1/t-Polyak步长：

${\eta }_t=\{\begin{array}{l}m/t,{\bar{\eta }}_t^P\le m/t;\\ {\bar{\eta }}_t^P,m/t<{\bar{\eta }}_t^P<M/t;\\ M/t,{\bar{\eta }}_t^P\ge M/t,\end{array}$ (2)

其中 ${\bar{\eta }}_t^P$ 形式如下：

${\bar{\eta }}_t^P=c_B\frac{f_{I_t}\left({\tilde{x}}_{t-1}\right)-{\mathcal{l}}_{I_t}^{*}}{{\Vert \nabla f_{I_t}\left({\tilde{x}}_{t-1}\right)\Vert }^2}$ ，

其中 ${\mathcal{l}}_{I_t}^{*}$ 为批量函数 $f_{I_t}\left(x\right)$ 的极小值， $c_B$ 用于调整步长的范围，由用户给定。对于一些非负的损失函数，根据批量函数的定义可取 ${\mathcal{l}}_{I_t}^{*}=0$ 。结合1/t-Polyak步长和SCSG算法提出SCSGP算法，见算法1。

在SCSGP算法的第t次外循环中，内循环次数 $N_t~Geom\left({\gamma }_t\right)$ 是非负的几何随机变量，其概率分布为 $P\left(N_t=k\right)={\gamma }_t^k\left(1-{\gamma }_t^k\right)$ ， $\forall k=0,1,\cdots$ 。值得注意的是，SCSG中 ${\gamma }_t$ 取固定值，但在SCSGP中 ${\gamma }_t$ 随迭代次数变化。若 ${\gamma }_t=B_t/\left(B_t+b_t\right)$ ，则有

${{\rm E}}_{N_t~Geom\left({\gamma }_t\right)}=\frac{{\gamma }_t}{1-{\gamma }_t}=\frac{B_t}{b_t}$ ，

其中 ${{\rm E}}_{N_t}$ 记为对 $N_t$ 取期望。该性质在后续分析中起到重要作用。另外不难发现 $v_k^{\left(t\right)}$ 是梯度估计量 $\nabla f\left(x_k\right)$ 的有偏估计：

${{\rm E}}_{{\tilde{I}}_k}{v}_k^{\left(t\right)}=\nabla f\left(x_k^{\left(t\right)}\right)-\nabla f\left({\tilde{x}}_{t-1}\right)+\nabla f_{I_t}\left({\tilde{x}}_{t-1}\right)=\nabla f\left(x_k^{\left(t\right)}\right)+e_t$ ， (3)

其中 $e_t=\nabla f_{I_t}\left({\tilde{x}}_{t-1}\right)-\nabla f\left({\tilde{x}}_{t-1}\right)$ 。

3. 收敛性分析

由于几何随机变量 $N_t$ 在收敛分析中占据重要地位，需要给出下面关键的引理。

引理1 [8] 由于 $N_t~Geom\left({\gamma }_t\right)$ ，其中 ${\gamma }_t>0$ ，则对任意满足 ${\rm E}\left|D_{N_t}\right|<\infty$ 的序列 $\left\{D_n\right\}$ 有

${\rm E}\left(D_{N_t}-D_{N_t+1}\right)=\left(\frac{1}{{\gamma }_t}-1\right)\left(D_0-{\rm E}{D}_{N_t}\right)$ ，

其中E记为对所有随机变量取期望。

记 $\gamma =\underset{t}{\min }{\gamma }_t$ ，则对任意 $t\in \left[T\right]$ 有

$\text{E}\left(D_{N_t}-D_{N_t-1}\right)\le \left(\frac{1}{\gamma }-1\right)\left(D_0-{\rm E}{D}_{N_t}\right)$ 。 (4)

为了应用(3)，需要证明用到的相关序列 $\left\{D_n\right\}$ 满足 ${\rm E}\left|D_{N_t}\right|<\infty$ 。下面引理保证了该性质。

引理2 假设 $f_i\left(x\right)$ 是L-光滑的，令 $\frac{ML}{t}\le \frac{1}{3}{\left(\frac{b_t}{B_t}\right)}^{2/3}$ 且 $B_t\ge 8b_t$ ，则对任意 $t\ge 1$ ， ${\rm E}{\Vert {\tilde{x}}_t-{\tilde{x}}_{t-1}\Vert }^2<\infty$ ，

${\rm E}\left[f\left({\tilde{x}}_t\right)-f^{*}\right]<\infty$ ， ${\rm E}{\Vert \nabla f\left({\tilde{x}}_t\right)\Vert }^2<\infty$ ， ${\rm E}\left|\langle e_t,{\tilde{x}}_t-{\tilde{x}}_{t-1}\rangle \right|<\infty$ ， ${\rm E}\left|\langle e_t,\nabla f\left({\tilde{x}}_t\right)\rangle \right|<\infty$ 。

证明：因为 $f_i\left(x\right)$ 是L-光滑的和(3)，可得

$\begin{array}{c}{{\rm E}}_{{\tilde{I}}_k}f\left(x_{k+1}^{\left(t\right)}\right)\le f\left(x_k^{\left(t\right)}\right)-{\eta }_t\langle {{\rm E}}_{{\tilde{I}}_k}{v}_k^{\left(t\right)},\nabla f\left(x_k^{\left(t\right)}\right)\rangle +\frac{L{\eta }_t^2}{2}{{\rm E}}_{{\tilde{I}}_k}{\Vert v_k^{\left(t\right)}\Vert }^2\\ =f\left(x_k^{\left(t\right)}\right)-{\eta }_t{\Vert \nabla f\left(x_k^{\left(t\right)}\right)\Vert }^2-{\eta }_t\langle e_t,\nabla f\left(x_k^{\left(t\right)}\right)\rangle +\frac{L{\eta }_t^2}{2}{{\rm E}}_{{\tilde{I}}_k}{\Vert v_k^{\left(t\right)}\Vert }^2\\ \le f\left(x_k^{\left(t\right)}\right)-{\eta }_t\left(1-L{\eta }_t\right){\Vert \nabla f\left(x_k^{\left(t\right)}\right)\Vert }^2-{\eta }_t\langle e_t,\nabla f\left(x_k^{\left(t\right)}\right)\rangle +\frac{L^3{\eta }_t^2}{2b_t}{\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2+L{\eta }_t^2{\Vert e_t\Vert }^2,\end{array}$ (5)

其中最后一个不等式利用了 [8] 中引理B.2。由于对任意 $c>0$ 有 $2\langle a,b\rangle \le \frac{{\Vert a\Vert }^2}{c}+c{\Vert b\Vert }^2$ ，令 $c=2$ ，则有

${\eta }_t\langle e_t,-\nabla f\left(x_k^t\right)\rangle \le \frac{1}{4}{\eta }_t{\Vert \nabla f\left(x_k^{\left(t\right)}\right)\Vert }^2+{\eta }_t{\Vert e_t\Vert }^2$ 。 (6)

因为 ${\eta }_t\le \frac{M}{t}$ ， $\frac{ML}{t}\le \frac{1}{3}{\left(\frac{b_t}{B_t}\right)}^{2/3}$ 且 $B_t\ge 8b_t$ ，可知 $\frac{3}{4}-L{\eta }_t>0$ 。由(5)和(6)得到

$\begin{array}{c}{\Vert \nabla f\left(x_k^{\left(t\right)}\right)\Vert }^2\le \frac{1}{{\eta }_t\left(\frac{3}{4}-L{\eta }_t\right)}\left(f\left(x_k^{\left(t\right)}\right)-{{\rm E}}_{{\tilde{I}}_k}f\left(x_{k+1}^{\left(t\right)}\right)\right)+\frac{1+L{\eta }_t}{\frac{3}{4}-L{\eta }_t}{\Vert e_t\Vert }^2\\ +\frac{L^3{\eta }_t}{2b_t\left(\frac{3}{4}-L{\eta }_t\right)}{\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2.\end{array}$ (7)

注意到 $x_{k+1}^{\left(t\right)}=x_k^{\left(t\right)}-{\eta }_t{v}_k^{\left(t\right)}$ ，用类似(5)的推导过程可得

$\begin{array}{c}{{\rm E}}_{{\tilde{I}}_k}{\Vert x_{k+1}^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2={\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2-2{\eta }_t\langle {{\rm E}}_{{\tilde{I}}_k}{v}_k^{\left(t\right)},x_k^{\left(t\right)}-x_0^{\left(t\right)}\rangle +{\eta }_t^2{{\rm E}}_{{\tilde{I}}_k}{\Vert v_k^{\left(t\right)}\Vert }^2\\ ={\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2-2{\eta }_t\langle \nabla f\left(x_k^{\left(t\right)}\right),x_k^{\left(t\right)}-x_0^{\left(t\right)}\rangle -2{\eta }_t\langle e_t,x_k^{\left(t\right)}-x_0^{\left(t\right)}\rangle +{\eta }_t^2{{\rm E}}_{{\tilde{I}}_k}{\Vert v_k^{\left(t\right)}\Vert }^2\\ \le \left(1+\frac{{\eta }_t^2{L}^2}{b_t}\right){\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2-2{\eta }_t\langle \nabla f\left(x_k^{\left(t\right)}\right),x_k^{\left(t\right)}-x_0^{\left(t\right)}\rangle -2{\eta }_t\langle e_t,x_k^{\left(t\right)}-x_0^{\left(t\right)}\rangle \\ +2{\eta }_t^2{\Vert \nabla f\left(x_k^{\left(t\right)}\right)\Vert }^2+2{\eta }_t^2{\Vert e_t\Vert }^2.\end{array}$ (8)

再次使用 $2\langle a,b\rangle \le \frac{{\Vert a\Vert }^2}{c}+c{\Vert b\Vert }^2$ 并取 $c=\frac{b_t}{8{\eta }_t^2{B}_t}$ ，则有

$\langle -2{\eta }_t\nabla f\left(x_k^{\left(t\right)}\right),x_k^{\left(t\right)}-x_0^{\left(t\right)}\rangle \le \frac{8{\eta }_t^2{B}_t}{b_t}{\Vert \nabla f\left(x_k^{\left(t\right)}\right)\Vert }^2+\frac{b_t}{8B_t}{\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2$ ，

$\langle -2{\eta }_t{e}_t,x_k^{\left(t\right)}-x_0^{\left(t\right)}\rangle \le \frac{8{\eta }_t^2{B}_t}{b_t}{\Vert e_t\Vert }^2+\frac{b_t}{8B_t}{\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2$ 。

将上述不等式和(7)代入(8)得到

$\begin{array}{l}{{\rm E}}_{{\tilde{I}}_k}{\Vert x_{k+1}^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2\le \left(1+\frac{b_t}{4B_t}+\frac{3{\eta }_t^2{L}^2/2+8{\eta }_t^3{L}^3{B}_t/b_t}{2b_t\left(3/4-{\eta }_{t}L\right)}\right){\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2+\left(2{\eta }_t^2+\frac{8{\eta }_t^2{B}_t}{b_t}\right)\left(1+\frac{1+{\eta }_{t}L}{3/4-{\eta }_{t}L}\right){\Vert e_t\Vert }^2\\ +\frac{2{\eta }_t+8{\eta }_t{B}_t/b_t}{3/4-{\eta }_{t}L}\left(f\left(x_k^{\left(t\right)}\right)-{{\rm E}}_{{\tilde{I}}_k}f\left(x_{k+1}^{\left(t\right)}\right)\right).\end{array}$ (9)

由 ${\eta }_{t}L\le \frac{1}{3}{\left(\frac{b_t}{B_t}\right)}^{2/3}$ 和 $B_t\ge 8b_t$ 可得

$\begin{array}{c}\frac{3{\eta }_t^2{L}^2/2+8{\eta }_t^3{L}^3{B}_t/b_t}{2b_t\left(3/4-{\eta }_{t}L\right)}\le \frac{\left(1/6\right)\times {\left(b_t/B_t\right)}^{4/3}+\left(8/27\right)\times \left(b_t/B_t\right)}{2b_t\left(3/4-\left(1/3\right)\times {\left(b_t/B_t\right)}^{2/3}\right)}\\ \le \frac{1/12B_t+8/27B_t}{2\left(3/4-1/12\right)}=\frac{41}{144B_t}\le \frac{7b_t}{24B_t}.\end{array}$

结合上式和(9)有

$\begin{array}{c}{{\rm E}}_{{\tilde{I}}_k}{\Vert x_{k+1}^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2\le \left(1+\frac{b_t}{4B_t}+\frac{7b_t}{24B_t}\right){\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2+\left(2+\frac{8B_t}{b_t}\right)\left(1+\frac{1+\left(1/3\right)\times {\left(b_t/B_t\right)}^{2/3}}{3/4-\left(1/3\right)\times {\left(b_t/B_t\right)}^{2/3}}\right){\eta }_t^2{\Vert e_t\Vert }^2\\ +\frac{2{\eta }_t+8{\eta }_t{B}_t/b_t}{3/4-\left(1/3\right)\times {\left(b_t/B_t\right)}^{2/3}}\left(f\left(x_k^{\left(t\right)}\right)-{{\rm E}}_{{\tilde{I}}_k}f\left(x_{k+1}^{\left(t\right)}\right)\right)\\ \le \left(1+\frac{13b_t}{24B_t}\right){\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2+\left(\frac{21}{4}+\frac{21B_t}{b_t}\right){\eta }_t^2{\Vert e_t\Vert }^2+\left(3+\frac{12B_t}{b_t}\right){\eta }_t\left(f\left(x_k^{\left(t\right)}\right)-{{\rm E}}_{{\tilde{I}}_k}f\left(x_{k+1}^{\left(t\right)}\right)\right).\end{array}$ (10)

为了证明 ${\rm E}\left[f\left(x_k^{\left(t\right)}\right)-f^{*}\right]$ 和 ${\rm E}{\Vert x_{k+1}^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2$ 的上界，记

$G_k^{\left(t\right)}=\left(3+\frac{12B_t}{b_t}\right){\eta }_t{\rm E}\left[f\left(x_k^{\left(t\right)}\right)-f^{*}\right]+{\rm E}{\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2.$

对(10)取全期望得到

$\begin{array}{c}{G}_{k+1}^{\left(t\right)}\le G_k^{\left(t\right)}+\frac{13b_t}{24B_t}{\rm E}{\Vert x_k^{\left(t\right)}-x_0^{\left(t\right)}\Vert }^2+\left(\frac{21}{4}+\frac{21B_t}{b_t}\right){\eta }_t^2{\rm E}{\Vert e_t\Vert }^2\\ \le \left(1+\frac{13b_t}{24B_t}\right)\left(G_k^{\left(t\right)}+\left(\frac{21}{4}+\frac{21B_t}{b_t}\right){\eta }_t^2{\rm E}{\Vert e_t\Vert }^2\right)\\ \le {\left(1+\frac{13b_t}{24B_t}\right)}^k\left(G_0^{\left(t\right)}+\left(\frac{21}{4}+\frac{21B_t}{b_t}\right){\eta }_t^2{\rm E}{\Vert e_t\Vert }^2\right).\end{array}$

由 $N_t~Geom\left(\frac{B_t}{B_t+b_t}\right)$ 可得

$P\left(N_t=k\right)=\frac{b_t}{B_t+b_t}{\left(\frac{B_t}{B_t+b_t}\right)}^k\le {\left(\frac{B_t}{B_t+b_t}\right)}^k,$

${\rm E}{\left(1+\frac{13b_t}{24B_t}\right)}^{N_t}\le {{\displaystyle \underset{k\ge 0}{\sum }\left(\frac{24B_t+13b_t}{24B_t}\right)}}^k{\left(\frac{B_t}{B_t+b_t}\right)}^k={{\displaystyle \underset{k\ge 0}{\sum }\left(\frac{24B_t+13b_t}{24B_t+24b_t}\right)}}^k=\frac{24B_t+24b_t}{11b_t}.$

于是有

${\rm E}{G}_{N_t}^{\left(t\right)}\le \frac{24B_t+24b_t}{11b_t}\left(G_0^{\left(t\right)}+\left(\frac{21}{4}+\frac{21B_t}{b_t}\right){\eta }_t^2{\rm E}{\Vert e_t\Vert }^2\right),$

即

$\begin{array}{l}\left(3+\frac{12B_t}{b_t}\right){\eta }_t{\rm E}\left[f\left(x_{N_t}^{\left(t\right)}\right)-f^{*}\right]+{\rm E}\Vert x_{N_t}^{\left(t\right)}-x_0^{\left(t\right)}\Vert \\ \le \frac{24B_t+24b_t}{11b_t}\left(\left(3+\frac{12B_t}{b_t}\right){\eta }_t{\rm E}\left[f\left(x_0^{\left(t\right)}\right)-f^{*}\right]+\left(\frac{21}{4}+\frac{21B_t}{b_t}\right){\eta }_t^2{\rm E}{\Vert e_t\Vert }^2\right).\end{array}$

分别用 ${\tilde{x}}_t$ 替换 $x_{N_t}^{\left(t\right)}$ ，用 ${\tilde{x}}_{t-1}$ 替换 $x_0^{\left(t\right)}$ ，由 [8] 中引理B.3得到 ${\rm E}{\Vert e_t\Vert }^2<\infty$ ，这表明 ${\rm E}{\Vert {\tilde{x}}_t-{\tilde{x}}_{t-1}\Vert }^2<\infty$ 和 ${\rm E}\left[f\left({\tilde{x}}_t\right)-f^{*}\right]<\infty$ 。由(7)可知 ${\rm E}{\Vert \nabla f\left({\tilde{x}}_t\right)\Vert }^2<\infty$ 。利用 $2\langle a,b\rangle \le \frac{{\Vert a\Vert }^2}{c}+c{\Vert b\Vert }^2$ 可得 ${\rm E}\left|\langle e_t,{\tilde{x}}_t-{\tilde{x}}_{t-1}\rangle \right|<\infty$ 和

${\rm E}\left|\langle e_t,\nabla f\left({\tilde{x}}_t\right)\rangle \right|<\infty$ 。结论得证。

现在分析强凸条件下SCSGP的线性收敛速度。

定理1 假设 $f_i\left(x\right)$ 是L-光滑的且 $f\left(x\right)$ 是 $\mu$ -强凸的，令 $b_t=t^{1/2}$ ， $B_t=B_0{t}^{3/2}$ ，则

${\rm E}\left[f\left({\tilde{x}}_T\right)-f^{*}\right]\le c_0^T{\Delta }_f+\frac{15M{{\rm H}}^{*}}{8\mu m{B}_0}J\left(B_t<n\right),$

其中 $c_0=\frac{3}{3+2\mu m{B}_0}$ ， ${\Delta }_f=f\left({\tilde{x}}_0\right)-f^{*}$ ， ${{\rm H}}^{*}=\underset{x}{\sup }\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}\Vert \nabla f_i\left(x\right)-\nabla f\left(x\right)\Vert }$ 和 $J\left(B_t<n\right)=\{\begin{array}{cc}1,& B_t<n;\\ 0,& 其他.\end{array}$

证明：由 [8] 中引理B.3和等式(20)得到

$\begin{array}{l}\frac{{\eta }_t{B}_t}{b_t}\left(2-\frac{2b_t}{B_t}-2{\eta }_{t}L-\frac{b_t^3}{b_t^3-{\eta }_t^2{L}^2{b}_t{B}_t-{\eta }_t^3{L}^3{B}_t^2}\right){\rm E}{\Vert \nabla f\left({\tilde{x}}_t\right)\Vert }^2\\ \le 2{\rm E}\left[f\left({\tilde{x}}_{t-1}\right)-f\left({\tilde{x}}_t\right)\right]+\frac{2{\eta }_t}{b_t}\left(1+{\eta }_{t}L+\frac{b_t}{B_t}\right){{\rm H}}^{*}J\left(B_t<n\right).\end{array}$ (11)

由 $\frac{m}{t}\le {\eta }_t\le \frac{M}{t}$ ， $\frac{ML}{t}\le \frac{1}{3}{\left(\frac{b_t}{B_t}\right)}^{2/3}$ 和 $B_t\ge 8b_t$ 可得

$\begin{array}{c}2-\frac{2b_t}{B_t}-2{\eta }_{t}L-\frac{b_t^3}{b_t^3-{\eta }_t^2{L}^2{b}_t{B}_t-{\eta }_t^3{L}^3{B}_t^2}\ge 2-\frac{2b_t}{B_t}-\frac{2ML}{t}-\frac{t^3{b}_t^3}{t^3{b}_t^3-M^{2}t{L}^2{b}_t{B}_t-M^3{L}^3{B}_t^2}\\ \ge 2-2\times \frac{1}{8}-2\times \frac{1}{3}\times \frac{1}{4}-\frac{1}{1-1/\left(18b_t\right)-1/\left(27b_t\right)}\ge \frac{73}{108}\ge \frac{2}{3},\end{array}$

其中第三个不等式用了 $b_t\ge 1$ 。另外，

$1+{\eta }_{t}L+\frac{b_t}{B_t}\le 1+\frac{ML}{t}+\frac{b_t}{B_t}\le 1+\frac{1}{12}+\frac{1}{8}=\frac{29}{24}\le \frac{5}{4}$ 。

将上述两个系数代入(11)，并再次使用 $\frac{m}{t}\le {\eta }_t\le \frac{M}{t}$ 得到

$\frac{B_t}{t{b}_t}{\rm E}{\Vert \nabla f\left({\tilde{x}}_t\right)\Vert }^2\le \frac{3}{m}{\rm E}\left[f\left({\tilde{x}}_{t-1}\right)-f\left({\tilde{x}}_t\right)\right]+\frac{15M}{4mt{b}_t}{{\rm H}}^{*}J\left(B_t<n\right).$ (12)

因为f是 $\mu$ -强凸的，可得

$\frac{\mu }{2}\Vert {\tilde{x}}_t-x^{*}\Vert \le \langle \nabla f\left({\tilde{x}}_t\right),{\tilde{x}}_t-x^{*}\rangle +f^{*}-f\left({\tilde{x}}_t\right)\le \frac{{\Vert \nabla f\left({\tilde{x}}_t\right)\Vert }^2}{2\mu }+\frac{\mu {\Vert {\tilde{x}}_t-x^{*}\Vert }^2}{2}+f^{*}-f\left({\tilde{x}}_t\right),$

其中第二个不等式利用了 $2\langle a,b\rangle \le \frac{{\Vert a\Vert }^2}{c}+c{\Vert b\Vert }^2$ 。重新整理上式得

${\Vert \nabla f\left({\tilde{x}}_t\right)\Vert }^2\ge 2\mu \left(f\left({\tilde{x}}_t\right)-f^{*}\right).$

将上式代入(12)得到

$\left(3t{b}_t+2\mu m{B}_t\right){\rm E}\left[f\left({\tilde{x}}_t\right)-f^{*}\right]\le 3t{b}_t{\rm E}\left[f\left({\tilde{x}}_{t-1}\right)-f^{*}\right]+\frac{15}{4}M{{\rm H}}^{*}J\left(B_t<n\right).$

替换 $b_t=t^{1/2}$ 和 $B_t=B_0{t}^{3/2}$ ，然后两边同除 $3t^{3/2}+2\mu m{B}_0{t}^{3/2}$ 可得

$\begin{array}{c}{\rm E}\left[f\left({\tilde{x}}_t\right)-f^{*}\right]\le \left(\frac{3}{3+2\mu m{B}_0}\right){\rm E}\left[f\left({\tilde{x}}_{t-1}\right)-f^{*}\right]+\frac{15M{{\rm H}}^{*}J\left(B_t<n\right)}{4\left(3+2\mu m{B}_0\right)t^{3/2}}\\ \le \left(\frac{3}{3+2\mu m{B}_0}\right){\rm E}\left[f\left({\tilde{x}}_{t-1}\right)-f^{*}\right]+\frac{15M{{\rm H}}^{*}J\left(B_t<n\right)}{4\left(3+2\mu m{B}_0\right)}.\end{array}$

其中最后一个不等式成立是因为 $t\ge 1$ 。上式可以写为

${\rm E}\left[f\left({\tilde{x}}_t\right)-f^{*}\right]-\frac{15M{{\rm H}}^{*}J\left(B_t<n\right)}{8\mu m{B}_0}\le \left(\frac{3}{3+2\mu m{B}_0}\right)\left({\rm E}\left[f\left({\tilde{x}}_{t-1}\right)-f^{*}\right]-\frac{15M{{\rm H}}^{*}J\left(B_t<n\right)}{8\mu m{B}_0}\right).$ (13)

将 $t=T,\cdots ,1$ 时的(13)累加求和得到

${\rm E}\left[f\left({\tilde{x}}_t\right)-f^{*}\right]-\frac{15M{{\rm H}}^{*}J\left(B_t<n\right)}{8\mu m{B}_0}\le {\left(\frac{3}{3+2\mu m{B}_0}\right)}^T\left({\rm E}\left[f\left({\tilde{x}}_0\right)-f^{*}\right]-\frac{15M{{\rm H}}^{*}J\left(B_t<n\right)}{8\mu m{B}_0}\right)\le c_0^T{\Delta }_f.$ (14)

重新整理(14)，证毕。

4. 数值实验

Figure 1. Comparison of different stochastic gradient algorithms

图1. 不同随机梯度类算法的对比

考虑正则化的逻辑回归问题

$f\left(x\right)=\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}\log \left(1+\exp \left(-b_i{a}_i^{T}x\right)\right)}+\frac{1}{2n}{\Vert x\Vert }^2,$

其中 ${\left\{\left(a_i,b_i\right)\right\}}_{i=1}^n\subset {\Re }^d\times \left\{-1,1\right\}$ 是给定的训练集。 [7] 中指出内循环次数 $N_t$ 取期望值有助于增加SCSG算法的稳定性，且从 $I_t$ 中选取 ${\tilde{I}}_k$ 可以减小计算代价，所以在实验中设置 $N_t=\lfloor B_t/b_t\rfloor$ (几何随机变量 $N_t$ 的期望)且从 $I_t$ 中选取 ${\tilde{I}}_k$ ，其中 $\lfloor \cdot \rfloor$ 记为向下取整。为了验证SCSGP的有效性，比较SCSGP、SCSG、SVRG、SVRGBB和SGD。具体地，SVRG中设置小批量 $b_t\equiv 1$ ；SCSG设置 $B_t\equiv 0.05n$ ， $b_t\equiv 1$ ， $N_t=\lfloor B_t/b_t\rfloor$ ；SCSGP设置 $B_t=\lfloor B_0{t}^{3/2}\wedge n\rfloor$ ， $b_t=\lfloor t^{1/2}\wedge n\rfloor$ ， $N_t=\lfloor B_t/b_t\rfloor$ 。表1给出LIBSVM (网址： https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/)中四个标准数据集的信息。用表2的参数值进行对比实验，最优间隙随有效循环次数变化情况见图1。SCSGP明显比SCSG表现好，并且在前几个有效循环次数中，SCSGP与其它随机梯度类算法相比具有更好的数值结果。

Table 1. The information of data sets

表1. 数据集信息

Table 2. Parameters used for experiments

表2. 实验中的参数设置

5. 总结

基于Polyak步长和1/t-带步长提出1/t-Polyak步长，并将该步长与SCSG结合提出SCSGP算法。当目标函数强凸光滑时，SCSGP线性收敛。数值实验考虑正则化的逻辑回归问题，实验结果表明在前几个有效循环次数中SCSGP比其他随机梯度类算法表现好。