监督学习中的许多问题都可以归结为如下的有限和问题

$ \min f({\boldsymbol{x}})=\frac{1}{n} \sum\limits_{i=1}^n f_i({\boldsymbol{x}}). $

(1)

其中: n是样本个数, 每个f_i: $ \mathbb{R}^d \rightarrow \mathbb{R} $是对应于样本i的损失函数。本文总假定各个f_i是L-光滑且凸的, f是μ-强凸的。以上形式还包含典型的带L₂正则项的目标函数$ f({\boldsymbol{x}})=\frac{1}{n} \sum\limits_{i=1}^n \tilde{f}_i({\boldsymbol{x}})+ \frac{\lambda}{2}\|{\boldsymbol{x}}\|^2$, λ>0。为了之后分析的简洁性, 将正则项归入各个$\tilde{f}_i $之中。

如果忽视问题(1)的有限和结构, 可以对其直接运用传统的优化方法, 比如梯度下降法

$ {\boldsymbol{x}}_{k+1}={\boldsymbol{x}}_k-\eta \nabla f\left({\boldsymbol{x}}_k\right). $

(2)

其中: η是步长, ▽f(x_k)是f在x_k处的梯度。但在机器学习背景下, 样本数量n常常是上万甚至十万或百万级的, 而计算全梯度▽f(x_k)要求计算n个f_i的梯度, 由此带来的计算量是巨大的, 其他基于全梯度的传统优化方法也面临同样的问题。

为解决上述问题, 基于Robbins与Monro^[1]对随机近似的开创性工作, 研究者们^[2-4]提出并发展了随机梯度下降(stochastic gradient descent, SGD)。SGD利用问题(1)的有限和结构, 在其最简单的形式下, 算法等可能地随机抽取单个样本i并进行如下的更新

$ {\boldsymbol{x}}_{k+1}={\boldsymbol{x}}_k-\eta \nabla f_i\left({\boldsymbol{x}}_k\right). $

(3)

其中▽f_i(x_k)是f_i在x_k处的梯度。该策略极大降低了每次更新所需要的计算量, 因而在许多具有低精度要求的机器学习问题中成为主流方法, 在无约束有限和问题之外的其他问题(比如带大量凸约束的随机优化问题^[5])中也有广泛的应用。但是当精度要求较高时, SGD的方向方差不能随迭代递减的缺点使其即使在光滑强凸的问题里也只能具有次线性的收敛速度^[6]。

为减小SGD的方向方差从而提高其收敛速度, 近年来随机方差缩减类方法被提出并得到一定的关注与发展。方差缩减方法通过利用之前迭代中的历史梯度信息, 以相比于SGD更多的内存或者计算开销为主要代价, 得到对当前梯度的更好估计, 该类估计的均方误差能够随着迭代进行而逐渐减小。

最早的方差缩减方法是随机平均梯度算法^[7-8], 它利用存储的历史梯度信息构造随机平均梯度估计子, 开创了随机方差缩减方法的研究。与之类似，以较大内存开销为主要代价的算法还包括SAGA^[9]、k-SVRG^[10]、SARGE^[11]等。另一类方差缩减方法以更大的计算开销为提高收敛速度的主要代价, 比如SVRG^[12]、S2GD^[13]、L-SVRG^[14]、SCSG^[15]、VR-SGD^[16]、SARAH^[17]等, 以上算法均实现了在强凸时的线性收敛。

在这些方差缩减方法的基础上, 人们从不同的改进角度出发做了多方面的工作。一些工作应用重要性采样技术或者随机洗牌技术, 如Prox-SVRG^[18]、PVRSG^[19]、SAGA with random reshuffling^[20]等; 一些工作尝试进一步加快收敛, 如Katyusha^[21]、MiG^[22]、RPDG^[23]等; 一些工作结合自适应步长以减少调参负担, 如SVRG-BB^[24]、Ada-SVRG^[25]、AI-SARAH^[26]、SARAH-AS^[27]等。关于结合了BB(Barzilai-Borwein, BB)步长的方法, 将在下一节做更详细的介绍。

1 相关工作

1988年Barzilai和Borwein^[28]提出BB方法, 用于为梯度类方法计算步长。其核心思想类似于拟牛顿法, 将梯度下降法迭代式(2)中的步长η等价地看作一个数量矩阵ηI(其中I是单位矩阵), 令ηI使割线方程的残差的模长最小化而解出合适的η值, 相应的ηI因此是目标函数在当前迭代点处Hessian矩阵之逆的一个较好近似。具体地, η应满足下列2个方程之一:

$ \min \left\|\eta^{-1} {\boldsymbol{s}}_{k-1}-{\boldsymbol{G}}_{k-1}\right\|, $

(4)

$ \min \left\|{\boldsymbol{s}}_{k-1}-\eta {\boldsymbol{G}}_{k-1}\right\|. $

(5)

其中: s_k-1= x_k- x_k-1, G_k-1= ▽f(x_k)- ▽f(x_k-1)。由此解得的η值分别是

$ {\boldsymbol{\eta}}_k^{{\mathrm{BB}} 1} =\frac{{\boldsymbol{s}}_{k-1}^{{\mathrm{T}}} {\boldsymbol{s}}_{k-1}}{{\boldsymbol{s}}_{k-1}^{{\mathrm{T}}} {\boldsymbol{G}}_{k-1}} , $

(6)

$ {\boldsymbol{\eta}}_k^{{\mathrm{BB}} 2} =\frac{{\boldsymbol{s}}_{k-1}^{{\mathrm{T}}} {\boldsymbol{G}}_{k-1}}{{\boldsymbol{G}}_{k-1}^{{\mathrm{T}}} {\boldsymbol{G}}_{k-1}}. $

(7)

其中前一种BB步长得到了更广泛的使用。

观察上述式子, 注意G_k-1用到2个相邻迭代点处的全梯度▽f(x_k)和▽f(x_k-1)，由引言中的讨论可知这在大规模机器学习问题中通常将带来极大的计算负担。在著名的SVRG算法^[12]中, 研究者设计了双循环结构, 全梯度仅在外循环的“快照”点(也称为全梯度点, 下文通常记为$ \tilde{\boldsymbol{x}} $或$ \tilde{\boldsymbol{x}}_k $，其中$ k \in \mathbb{N}$是外循环数)处计算, 并将结果运用到内循环中随机方向的计算上以缩减方差, 其中快照点每隔一个外循环更新一次, 因此全梯度信息的求取在迭代点序列里是“稀疏”的。针对此特点, Tan等^[24]利用上一个快照与当前快照计算BB步长, 并将该步长用作当前外循环里的所有内循环迭代的步长, 得到SVRG-BB算法(见算法0), 从而解决了将BB方法从确定性方法引入大规模问题时遇到的一个本质困难。

算法0   SVRG-BB算法[24]
参数: 内循环长度m, 初始点$ \tilde{{\boldsymbol{x}}}_0 $, 初始步长η0(仅在最初的一个外循环里使用)
for k=0, 1, … do
$ \tilde{{\boldsymbol{\nabla}}}_k=\frac{1}{n} \sum_{i=1}^n \nabla f_i\left(\tilde{{\boldsymbol{x}}}_k\right) $
if k>0 then
$ \eta_k=\frac{1}{m} \frac{\left\|\tilde{{\boldsymbol{x}}}_k-\tilde{{\boldsymbol{x}}}_{k-1}\right\|_2^2}{\left(\tilde{{\boldsymbol{x}}}_k-\tilde{{\boldsymbol{x}}}_{k-1}\right)^{\mathrm{T}}\left(\tilde{{\boldsymbol{\nabla}}}_k-\tilde{{\boldsymbol{\nabla}}}_{k-1}\right)} $
end if
选取x0= $ \tilde{\boldsymbol{x}}_k$
for t=0, 1, …, m-1 do
随机选取it∈{1, …, n}
gt=▽fit(xt)-▽fit($ \tilde{\boldsymbol{x}}_k $)+$ \tilde{\boldsymbol{\nabla}}_k $
xt+1=xt-ηkgt
end for
选取$ \tilde{\boldsymbol{x}}_{k+1}$=xm
end for

在SVRG-BB提出之后, 也有一些工作将BB方法或者其改进运用到方差缩减方法里。例如, Yang等^[29]与Yu等^[30]将基于非精确梯度的随机BB方法与方差缩减方法相结合, 分别得到MB-SARAH-RBB算法和mS2GD-RBB算法; Yu等^[31]将对角BB方法与方差缩减方法相结合, 得到VM-mSRGBB算法; Xie等^[32]针对方差缩减算法SAGA^[9]的特点, 对BB方法发展了新的变体并将其与SAGA结合, 得到一个支持非欧范数的新算法, 等等。

2 直观动机

对于采用了一定自适应步长的算法, 人们总希望通过其他方面的改进提升算法的表现。注意到SVRG-BB虽然具有良好的数值效果, 但是与最优固定步长^①下的SVRG算法相比, 仍有进步的空间。针对SVRG-BB的数值效果劣于SVRG这一现象, 提出如下的直观解释: 由于SVRG-BB所使用的BB步长本质上基于对当前外循环快照点的局部二阶信息的逼近, 所以其效果在当前快照处应是最优的, 而随着内循环迭代的进行, 迭代点离快照越来越远, 使得仍用作迭代步长的BB步长逐渐“过时”与失效, 最终(部分地)导致SVRG-BB的效果与SVRG相比较差。

① 指在采用固定步长的SVRG的数值实验中, 在一定的外循环数下使得其最终优化间隙最小的固定步长。

图 1说明了SVRG-BB可能存在的问题。图中绿色圆点表示当前外循环所使用的快照$ \tilde{\boldsymbol{x}}_{\text {current }} $，绿色线条所包围的区域表示当前外循环计算得到并使用的BB步长η_BB较为有效的区域(该区域内的点的Hessian矩阵在某种意义或度量下与$ \tilde{\boldsymbol{x}}_{\text {current }} $的Hessian矩阵较为接近, 从而η_BB也能一定程度地反映相应点处的局部二阶信息)。其他颜色的圆点表示当前外循环下所产生的各个迭代点, 其中在绿线围成区域内的点使用黑色表示, 而在绿线围成区域外的点使用红色表示, 用以表明在这些红色点处使用η_BB作为迭代步长在某种程度上不再合适了。

总之, 我们认为SVRG-BB算法里存在一个“进展-自适应步长有效性”的权衡, 其本质上是“进展幅度-进展质量”的权衡, 即: 当算法取得较大的进展, 内循环迭代点距离当前快照越来越远, 此时自适应步长越来越“过时”, 导致接下来进展的质量变差; 当算法进展较小时, 自适应步长更有效, 算法的进展质量更高。所以希望能在进展幅度与进展质量之间寻求一个更好的平衡。具体地, 我们提出将Katyusha动量加入SVRG-BB以寻求该平衡。

Katyusha动量由Allen-Zhu^[21]于2016年提出, 成功解决了SVRG在结合Nesterov动量时效果不佳的问题。相应的Katyusha算法是针对带凸正则项的问题(1)的达到最优加速收敛速率且在并行化中具有最优线性加速的方法，对其后的加速方差缩减方法的研究产生了相当的影响。在其最简单的形式下, Katyusha算法内循环中的关键迭代步骤如下:

$ \begin{aligned} & {\boldsymbol{y}}_{t+1} \leftarrow \tau_1 z_t+\tau_2 \tilde{{\boldsymbol{x}}}+\left(1-\tau_1-\tau_2\right) {\boldsymbol{x}}_t , \\ & {\boldsymbol{g}}_{t+1} \leftarrow \nabla f(\tilde{{\boldsymbol{x}}})+\nabla f_{i_{t+1}}\left({\boldsymbol{y}}_{t+1}\right)-\nabla f_{i_{t+1}}(\tilde{{\boldsymbol{x}}}), \\ & {\boldsymbol{x}}_{t+1} \leftarrow {\boldsymbol{y}}_{t+1}-\frac{1}{3 L} {\boldsymbol{g}}_{t+1} , \\ & {\boldsymbol{z}}_{t+1} \leftarrow {\boldsymbol{z}}_t-\frac{1}{3 \tau_1 L} {\boldsymbol{g}}_{t+1}. \end{aligned} $

其中：τ₁, τ₂∈(0, 1)是动量系数, i_t+1是取值于{1, 2, …, n}的一个随机变量；$\tilde{{\boldsymbol{x}}} $是每隔一个外循环更新一次的快照点；点x_t+1, y_t+1, z_t+1等均是$ \tilde{{\boldsymbol{x}}} $对应的外循环中产生的迭代点, 其中x_t, x_t+1等所在的x序列是“主序列”(类比于梯度下降法中做梯度下降的唯一序列), 而y_t, y_t+1及z_t, z_t+1等分别所在的y序列和z序列是“辅助序列”。辅助序列是加速方法中常见的设计, 用以达到理论和数值表现上的加速。辅助序列z扮演了传统加速方法中“动量”的角色, 其本质是历史方向的累积, 通过辅助序列y不断向主序列x施加历史方向的影响: 由序列y的更新方式可见其中包含了序列z的影响, 又由于x_t+1是由y_t+1=(1-τ₁-τ₂) x_t+ τ₁ z_t+τ₂ $ \tilde{{\boldsymbol{x}}} $而非x_t出发更新(即出发点是x_t受动量作用后的点), 且g_t+1也是在y_t+1而非x_t处计算, 可见动量对主序列x的更新迭代的影响。

如果动量系数τ₁=τ₂=0，则相应的迭代实质上退化成SVRG算法的仅有一个序列(即x序列)的迭代形式; 如果仅τ₂=0，则可理解为对SVRG算法直接使用一定形式的Nesterov加速技巧, 但这么做得到的理论结果和实际效果都是欠佳的。对此Allen-Zhu提出, 由于随机方差缩减方法中所使用的方向仅是相应真实梯度方向的一个估计, 故一旦产生了一个不良的估计, 其影响将在后续通过辅助序列z与y持续存在, 破坏算法的效果。因此Allen-Zhu向y序列进一步加入了“快照” $ \tilde{{\boldsymbol{x}}}$，将迭代点拉回“安全锚点” $ \tilde{{\boldsymbol{x}}} $，以此抵消部分动量的影响。所添加的$ \tilde{{\boldsymbol{x}}} $因其“拉回”的作用也被称作“消极动量”。

易见, 若将Katyusha动量加入SVRG-BB, 则当Katyusha动量前的系数较大时, 所得算法将更倾向于停留在当前快照$ \tilde{{\boldsymbol{x}}} $的附近, 更注重自适应步长有效性带来的进展质量; 而当Katyusha动量前的系数较小时, 所得算法将更倾向于离开当前快照$ \tilde{{\boldsymbol{x}}} $进行探索, 更注重进展幅度。总之, Katyusha动量的加入使得在“进展-自适应步长有效性”的权衡里进行选择成为可能。

就迭代形式而言, 基于上述直观动机, 在将前述迭代机制结合进SVRG-BB之前, 对Katyusha算法内循环的关键步骤大致做出如下改变: 由于不考虑加入传统加速方法中的动量, 所以迭代中不使用和更新前述步骤里的辅助序列z且设定系数τ₁=0。保留辅助序列y(此时它仅是主序列x和快照$ \tilde{{\boldsymbol{x}}} $的凸组合), 并通过它在x的迭代步骤里的作用将主序列x不断以合适的“力度”拉回当前外循环对应的快照$ \tilde{{\boldsymbol{x}}}$，以此达到前述直观动机。需要注意, 以上对迭代形式的讨论是为了直观地说明我们的设计, 它与最终具体的算法设计(见算法1)仍有一定不同。

算法1   SVRG-BB-Katyusha算法
参数: 内循环长度m, 初始点$ \tilde{\boldsymbol{x}}_0 $, 初始步长η0, 动量控制系数θ, 参数α, 参数$\sigma=\frac{\mu}{\alpha L} $ (注: σ由α唯一决定, 为算法与证明的表述方便而引入)
for k=0, 1, … do
$ \tilde{\boldsymbol{\nabla}}_k=\frac{1}{n} \sum_{i=1}^n \nabla f_i\left(\tilde{\boldsymbol{x}}_k\right) $
if k>0 then
$\eta_k=\frac{1}{m} \frac{\left\|\tilde{{\boldsymbol{x}}}_k-\tilde{{\boldsymbol{x}}}_{k-1}\right\|_2^2}{\left(\tilde{{\boldsymbol{x}}}_k-\tilde{{\boldsymbol{x}}}_{k-1}\right)^{\mathrm{T}}\left(\tilde{{\boldsymbol{\nabla}}}_k-\tilde{{\boldsymbol{\nabla}}}_{k-1}\right)} $
end if
选取x0= $\tilde{\boldsymbol{x}}_k $
for t=0, 1, …, m-1 do
yt=θxt+(1-θ)$\tilde{\boldsymbol{x}}_k $
随机选取it∈{1, …, n}
gt=▽fit(yt)-▽fit($\tilde{\boldsymbol{x}}_k $)+ $ \tilde{\boldsymbol{\nabla}}_k $
$ {\boldsymbol{x}}_{t+1}=\frac{1}{1+\eta_k \sigma}\left(\eta_k \sigma {\boldsymbol{y}}_t+{\boldsymbol{x}}_t-\frac{\eta_k}{\alpha L} {\boldsymbol{g}}_t\right) $
end for
选取$ \tilde{\boldsymbol{x}}_{k+1} $=xm
end for

将动量加入自适应步长方法以提高后者的表现并不是一个新鲜的做法。比如Kingma与Ba^[33]将动量与RMSprop算法结合而得到ADAM算法等。这类已有的工作虽然取得了很好的效果, 却往往缺乏如下意义上的直观解释, 即难以理解为什么是这一特别的动量与这一特别的自适应步长相结合, 能够获得比其他可能的结合更好的效果。而在SVRG-BB这一基于快照点局部信息的自适应步长算法与Katyusha动量之间进行的结合, 更充分地体现和利用了两者各自的特点, 具有较明确的直观解释和一定的启发性, 指出了将Katyusha动量与其他基于快照局部信息的自适应步长方法结合可能获得额外好处(即增加自适应步长的有效性), 拓展了对Katyusha动量作用的认识。

本文工作主要有以下几方面:

1) 指出SVRG-BB的算法设计带来了“进展-自适应步长有效性”的权衡问题, 为该算法的改进提供了一个直观的视角和思路。

2) 结合已有的2种Katyusha动量的作用形式, 提出一种新的Katyusha动量作用形式, 并根据之前对SVRG-BB算法的直观分析与Katyusha动量的特点, 将其结合到SVRG-BB中得到SVRG-BB-Katyusha, 在强凸条件下给出其线性收敛性质的证明。随后基于“贪婪”思想, 提出SVRG-BB-Katyusha-SPARSE以尽可能减少带Katyusha动量的内循环迭代带来的额外计算。

3) 对所提出的SVRG-BB-Katyusha和SVRG-BB-Katyusha-SPARSE进行求解逻辑回归问题的数值实验。实验结果表明, 所提出算法的实际表现在如下意义上领先于SVRG-BB, 即在达到一定外循环数时优化间隙有若干个数量级的减小。

3 SVRG-BB-Katyusha算法

下面正式引入基于上述直观思想改进后的算法, 并称之为SVRG-BB-Katyusha(算法1)。

做如下几点说明：其一, 为突出所引入Katyusha动量的作用, 算法1保持了SVRG-BB的其他设计(如快照的选择方式, 下一个外循环初始点的选择方式等)不变; 其二, Katyusha动量在不同的算法中可以有不同的形式, 我们主要参考并结合了L-Katyusha^[14]以及MiG^[22]的设计, 得到新的形式并将其结合到SVRG-BB之中；其三, 在数值实验中总设定动量控制系数θ=0.9，以此免去对该参数进行精调的负担并取得良好效果；其四, 在$ \sigma = \frac{\mu }{{\alpha L}} $中出现的参数α在实际中并不是一个需要精调的参数。它的引入背景是: 以公式计算出的一个李普希兹常数在最初的实验里并不能使SVRG-BB-Katyusha的效果大幅领先于原本的SVRG-BB, 体现出公式得到的李普希兹常数过松。于是将它缩小一定比例, 由此得到了很好的实验效果。所以引入α以体现这一处理, 并在之后的收敛性证明里给该处理提供理论支持。在之后的数值实验中, 对于维度较小(小于100)的数据集, 总设定α=0.5; 对于维度较大(大于等于100)的数据集, 总设定α=0.7。这样的设定在实际实验中取得了优良的效果, 并免去对α进行精调的负担。

回顾引入Katyusha动量的直观思想, 即利用Katyusha动量的“拉回”作用, 将迭代点不断拉回快照从而使得BB步长免于“过时”。据此提出, 在每一次内循环中都执行带Katyusha动量的迭代或许是不必要的, 只要足够频繁地执行带Katyusha动量的迭代而保持其余的内循环迭代与SVRG-BB相同, 使得内循环迭代点与快照足够近, 就可能保持由更有效的BB步长带来的效果增益, 并规避一部分由更复杂的内循环迭代方式带来的额外计算。基于此, 提出以下的SVRG-BB-Katyusha-SPARSE(算法2)。

算法2  SVRG-BB-Katyusha-SPARSE算法
参数: 内循环长度m, 初始点$ \tilde{\boldsymbol{x}}_0 $, 初始步长η0, 动量控制系数θ, 参数α, 参数$ \sigma=\frac{\mu}{\alpha L} $，参数m0 (注: σ由α唯一决定, 为算法与证明的表述方便而引入)
for k=0, 1, … do
$ \tilde{\boldsymbol{\nabla}}_k=\frac{1}{n} \sum_{i=1}^n \nabla f_i\left(\tilde{\boldsymbol{x}}_k\right) $
if k>0 then
$\eta_k=\frac{1}{m} \frac{\left\|\tilde{{\boldsymbol{x}}}_k-\tilde{{\boldsymbol{x}}}_{k-1}\right\|_2^2}{\left(\tilde{{\boldsymbol{x}}}_k-\tilde{{\boldsymbol{x}}}_{k-1}\right)^{\mathrm{T}}\left(\tilde{{\boldsymbol{\nabla}}}_k-\tilde{{\boldsymbol{\nabla}}}_{k-1}\right)} $
end if
选取x0= $ \tilde{\boldsymbol{x}}_k $
for t=0, …, m-1 do
if t mod m0≠0 then
随机选取it∈{1, 2，…, n}
xt+1=xt-ηk(▽fit(xt)-▽fit($ \tilde{\boldsymbol{x}}_k $)+ $ \tilde{\boldsymbol{\nabla}}_k $)
else
yt=θxt+(1-θ) $\tilde{\boldsymbol{x}}_k $
随机选取it∈{1, 2，…, n}
gt=▽fit(yt)-▽fit($ \tilde{\boldsymbol{x}}_k $)+ $ \tilde{\boldsymbol{\nabla}}_k $
${\boldsymbol{x}}_{t+1}=\frac{1}{1+\eta_k \sigma}\left(\eta_k \sigma {\boldsymbol{y}}_t+{\boldsymbol{x}}_t-\frac{\eta_k}{\alpha L} {\boldsymbol{g}}_t\right) $
end if
end for
选取$ \tilde{\boldsymbol{x}}_{k+1} $=xm
end for

基于“贪婪”思想, 在能够保证算法效果的情况下, 希望将参数m₀取得尽可能大, 以尽可能减少带Katyusha动量的内循环迭代带来的额外计算负担。在数值实验中总选取m₀=4，以此免去对该参数进行精调的负担并取得了良好效果。数值实验效果显示了这个算法的有效性, 但是理论性质还没有得到更多的刻画。

4 符号说明与假设

在进行SVRG-BB-Katyusha的收敛性证明之前, 对证明中使用的符号说明如下: ‖x‖表示向量x的欧氏范数, 〈 a, b 〉表示向量a与向量b的内积, [n]={1, 2, …, n}表示如前的n个正整数构成的集合, $ \mathbb{N} $表示所有非负整数构成的集合, $ \mathbb{R}_+ $表示所有非负实数构成的集合, 目标函数f的最小值点记为$ {\boldsymbol{x}}_* \triangleq \operatorname{argmin} f({\boldsymbol{x}}) $，相应的最小值记为$ f^* \triangleq f\left({\boldsymbol{x}}_*\right) $。

下面明确地列出对问题(1)所做的假设。

假设4.1   函数$ f: \mathbb{R}^d \rightarrow \mathbb{R}$是可微且μ-强凸的, 即

$ \begin{aligned} & f({\boldsymbol{y}}) \geqslant f({\boldsymbol{x}})+\langle\nabla f({\boldsymbol{x}}), {\boldsymbol{y}}-{\boldsymbol{x}}\rangle+\frac{\mu}{2}\|{\boldsymbol{y}}-{\boldsymbol{x}}\|^2, \\ & \forall {\boldsymbol{x}}, {\boldsymbol{y}} \in \mathbb{R}^d. \end{aligned} $

假设4.2   对所有i∈[n], 函数$f_i: \mathbb{R}^d \rightarrow \mathbb{R} $是可微且凸的, 即

$ \begin{aligned} & f_i({\boldsymbol{y}}) \geqslant f_i({\boldsymbol{x}})+\left\langle\nabla f_i({\boldsymbol{x}}), {\boldsymbol{y}}-{\boldsymbol{x}}\right\rangle, \\ & \forall {\boldsymbol{x}}, {\boldsymbol{y}} \in \mathbb{R}^d. \end{aligned} $

假设4.3   对所有i∈[n], 函数$ f_i: \mathbb{R}^d \rightarrow \mathbb{R} $是L-光滑的, 即

$ \begin{aligned} f_i(\boldsymbol{y}) & \leqslant f_i(\boldsymbol{x})+\left\langle\nabla f_i(\boldsymbol{x}), \boldsymbol{y}-\boldsymbol{x}\right\rangle+\frac{L}{2}\|\boldsymbol{y}-\boldsymbol{x}\|^2, \\ \forall \boldsymbol{x}, \boldsymbol{y} & \in \mathbb{R}^d. \end{aligned} $

将假设4.3中的不等式对所有的i∈[n]求和并除以n，可知函数$ f: \mathbb{R}^d \rightarrow \mathbb{R} $也是L-光滑的。

5 收敛性证明

下面给出SVRG-BB-Katyusha的收敛性证明, 首先介绍如下几个引理。

引理5.1及其证明基本复刻Kovalev等^[14]的工作中的Lemma 4.2。由于定理5.1(收敛性定理)的证明主体是针对同一个外循环的, 其中步长保持不变, 于是在引理5.1中以η而非η_k代表步长, 这避免了诸如把χ_t(将在引理5.1中给出定义)记作χ_{k, t}的麻烦。在引理5.3中也类似地使用符号η。在之后的定理5.1中沿用η和χ_t的记法而不特别标记其所在的外循环, 对各迭代点列(除快照外)和收缩因子β(将在定理5.1中给出定义)也不特别标记其所在的外循环, 这对证明不产生影响。

引理5.1   定义$ \chi_t \triangleq \frac{\alpha L}{2} \frac{1+\eta \sigma}{\eta}\left\|{\boldsymbol{x}}_t-{\boldsymbol{x}}_*\right\|^2$, 则

$ \begin{aligned} & \left\langle {\boldsymbol{g}}_t, {\boldsymbol{x}}_*-{\boldsymbol{x}}_{t+1}\right\rangle+\frac{\mu}{2}\left\|{\boldsymbol{y}}_t-{\boldsymbol{x}}_*\right\|^2 \geqslant \\ & \frac{\alpha L}{2 \eta}\left\|{\boldsymbol{x}}_t-{\boldsymbol{x}}_{t+1}\right\|^2+\chi_{t+1}-\frac{1}{1+\eta \sigma} \chi_t. \end{aligned} $

(8)

证明   由${\boldsymbol{x}}_{t+1}=\frac{1}{1+\eta \sigma}\left(\eta \sigma {\boldsymbol{y}}_t+{\boldsymbol{x}}_t-\frac{\eta}{\alpha L} {\boldsymbol{g}}_t\right) $, 有${\boldsymbol{g}}_t=\mu\left({\boldsymbol{y}}_t-{\boldsymbol{x}}_{t+1}\right)+\frac{\alpha L}{\eta}\left({\boldsymbol{x}}_t-{\boldsymbol{x}}_{t+1}\right) $。从而

$ \begin{aligned} \left\langle {\boldsymbol{g}}_t, {\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_*\right\rangle= & \mu\left\langle{\boldsymbol{y}}_t-{\boldsymbol{x}}_{t+1}, {\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_*\right\rangle+ \\ & \frac{\alpha L}{\eta}\left\langle{\boldsymbol{x}}_t-{\boldsymbol{x}}_{t+1}, {\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_*\right\rangle \\ = & \frac{\mu}{2}\left(\left\|{\boldsymbol{y}}_t-{\boldsymbol{x}}_*\right\|^2-\left\|{\boldsymbol{y}}_t-{\boldsymbol{x}}_{t+1}\right\|^2-\right. \\ & \left.\left\|{\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_*\right\|^2\right)+\frac{\alpha L}{2 \eta}\left(\left\|{\boldsymbol{x}}_t-{\boldsymbol{x}}_*\right\|^2-\right. \\ & \left.\left\|{\boldsymbol{x}}_t-{\boldsymbol{x}}_{t+1}\right\|^2-\left\|{\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_*\right\|^2\right) \\ \leqslant & \frac{\mu}{2}\left\|{\boldsymbol{y}}_t-{\boldsymbol{x}}_*\right\|^2+\frac{\alpha L}{2 \eta}\left(\left\|{\boldsymbol{x}}_t-{\boldsymbol{x}}_*\right\|^2-\right. \\ & \left.(1+\eta \sigma)\left\|{\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_*\right\|^2\right)- \\ & \frac{\alpha L}{2 \eta}\left\|{\boldsymbol{x}}_t-{\boldsymbol{x}}_{t+1}\right\|^2，\end{aligned} $

其中第2个等式利用了恒等式〈 a - b, b - c 〉= $ \frac{1}{2} $ (‖ a - c ‖²-‖ a - b ‖²-‖ b - c ‖²)。对上式移项整理即证。□

引理5.2来自Johnson与Zhang^[12]的工作, 对SVRG算法所使用的搜索方向的方差给出一个上界。

引理5.2   如下的不等式成立:

$ \mathbb{E}\left\|{\boldsymbol{g}}_t\right\|^2 \leqslant 4 L\left(f\left({\boldsymbol{y}}_t\right)-f^*+f(\tilde{{\boldsymbol{x}}})-f^*\right)，$

(9)

其中：g_t=▽f_it(y_t)-▽f_it($\tilde{\boldsymbol{x}} $)+▽f($\tilde{\boldsymbol{x}} $), i_t是在g_t计算时决定的等可能取[n]中某值的随机变量, $ \tilde{\boldsymbol{x}} $是y_t所在外循环开始时计算全梯度的快照点, $ \mathbb{E} $在此处是直至g_t计算之前所有随机信息都已知时针对i_t所做的条件期望。

下面是一个技术性引理, 在证明中起到重要作用。

引理5.3   如下的不等式成立:

$ \begin{aligned} & \left\langle{\boldsymbol{g}}_t, {\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_t\right\rangle+\frac{\alpha L}{2 \eta}\left\|{\boldsymbol{x}}_t-{\boldsymbol{x}}_{t+1}\right\|^2 \geqslant \\ & \frac{1}{\theta}\left(f\left({\boldsymbol{y}}_{t+1}\right)-f\left({\boldsymbol{y}}_t\right)-\right. \\ & \left.\frac{\eta \theta}{2 L(\alpha-\eta \theta)}\left\|{\boldsymbol{g}}_t-\nabla f\left({\boldsymbol{y}}_t\right)\right\|^2\right) . \end{aligned} $

(10)

证明

$ \begin{aligned} \left\langle{\boldsymbol{g}}_t, {\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_t\right\rangle+\frac{\alpha L}{2 \eta}\left\|{\boldsymbol{x}}_t-{\boldsymbol{x}}_{t+1}\right\|^2\\ = \frac{1}{\theta}\left(\frac{\alpha L}{2 \eta \theta}\left\|\theta\left({\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_t\right)\right\|^2+\left\langle{\boldsymbol{g}}_t, \theta\left({\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_t\right)\right\rangle\right) \\ = \frac{1}{\theta}\left(\frac{\alpha L}{2 \eta \theta}\left\|{\boldsymbol{y}}_{t+1}-{\boldsymbol{y}}_t\right\|^2+\left\langle\nabla f\left({\boldsymbol{y}}_t\right), {\boldsymbol{y}}_{t+1}-{\boldsymbol{y}}_t\right\rangle+\right. \\ \left.\left\langle{\boldsymbol{g}}_t-\nabla f\left({\boldsymbol{y}}_t\right), {\boldsymbol{y}}_{t+1}-{\boldsymbol{y}}_t\right\rangle\right) \\ = \frac{1}{\theta}\left(\frac{L}{2}\left\|{\boldsymbol{y}}_{t+1}-{\boldsymbol{y}}_t\right\|^2+\left\langle\nabla f\left({\boldsymbol{y}}_t\right), {\boldsymbol{y}}_{t+1}-{\boldsymbol{y}}_t\right\rangle+\right. \\ \frac{L}{2}\left(\frac{\alpha}{\eta \theta}-1\right)\left\|{\boldsymbol{y}}_{t+1}-{\boldsymbol{y}}_t\right\|^2+\left\langle{\boldsymbol{g}}_t-\nabla f\left({\boldsymbol{y}}_t\right), {\boldsymbol{y}}_{t+1}-\right. \\ \left.\left.{\boldsymbol{y}}_t\right\rangle\right) \geqslant \frac{1}{\theta}\left(f\left({\boldsymbol{y}}_{t+1}\right)-f\left({\boldsymbol{y}}_t\right)-\right.\\ \left.\frac{\eta \theta}{2 L(\alpha-\eta \theta)}\left\|{\boldsymbol{g}}_t-\nabla f\left({\boldsymbol{y}}_t\right)\right\|^2\right). \end{aligned} $

其中第2个等式利用了由算法1可推出的关系式y_t+1- y_t=θ(x_t+1- x_t)，最后一个不等式利用了函数f的L-光滑性和Young不等式。

以下的引理给出对BB步长的上下界估计, 其证明可参考Tan等^[24]的工作。

引理5.4   对于BB步长$\eta_k=\frac{1}{m}\frac{\left\|\tilde{{\boldsymbol{x}}}_k-\tilde{{\boldsymbol{x}}}_{k-1}\right\|^2}{\left\langle\tilde{{\boldsymbol{x}}}_k-\tilde{{\boldsymbol{x}}}_{k-1}, \tilde{{\boldsymbol{\nabla}}}_k-\tilde{{\boldsymbol{\nabla}}}_{k-1}\right\rangle} $, 有

$ \frac{1}{m L} \leqslant \eta_k \leqslant \frac{1}{m \mu}, $

(11)

其中$ k \in \mathbb{N} $是任何一个取定的外循环数。

证明   由f的L-光滑性得到下界, 由f的μ-强凸性得到上界。注意得到的上下界不依赖于k。

以下引理是Young不等式的一种变形。

引理5.5   对任意的a, b ∈ ${\mathbb{R}}^d $与γ>0，有

$ \langle{\boldsymbol{a}}, {\boldsymbol{b}}\rangle \geqslant-\frac{\|{\boldsymbol{a}}\|^2}{2 \gamma}-\frac{\gamma\|{\boldsymbol{b}}\|^2}{2} . $

(12)

最终给出SVRG-BB-Katyusha的收敛性定理如下。

定理5.1   定义$ \delta \triangleq \frac{1-\exp \left(-\frac{\sigma}{L}\right)}{2} $, $ \theta_0 \triangleq \frac{4}{4+\delta^2 \alpha \sigma}$, 以及

$ \begin{aligned} \beta \triangleq & \left(\frac{1}{1+\eta \sigma}\right)^m\left(1+\frac{\eta}{\alpha \theta(1+\eta \sigma)}\right)+ \\ & \frac{1}{\alpha \sigma}\left(\frac{1-\theta}{\theta}+\frac{2 \eta \theta}{\alpha-\eta \theta}\right). \end{aligned} $

则对任意α∈(0, 1], θ∈[θ₀, 1), 当内循环长度m≥M时(M=M(α, θ)将在定理证明中给出), 有$ \beta \in\left(0, 1-\frac{\delta^2}{6}\right] \subset(0, 1) $，且

$ \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_l-{\boldsymbol{x}}_*\right\|^2 \leqslant\left(1-\frac{\delta^2}{6}\right)^l\left\|\tilde{{\boldsymbol{x}}}_0-{\boldsymbol{x}}_*\right\|^2, $

(13)

其中$ l \in \mathbb{N} $是任何一个外循环数。

证明   自此直至推导出后文的式(15)之前的部分称为证明的主体部分, 在该部分事先取定一个k∈{1, 2, …, l}并对第(k-1)个外循环进行分析。直至后文取全期望之前, 符号$ \mathbb{E} $都表示直至第(k-1)个外循环的第t个内循环的i_t产生之前的随机信息都已知时的条件期望, 点x_t, x_t+1, y_t, y_t+1等都是取定的第(k-1)个外循环中产生的迭代点, 为简洁略去表示其所在外循环的角标。首先做如下的放缩:

$ \begin{array}{l} f^* \geqslant f\left({\boldsymbol{y}}_t\right)+\left\langle\nabla f\left({\boldsymbol{y}}_t\right), {\boldsymbol{x}}_*-{\boldsymbol{y}}_t\right\rangle+\frac{\mu}{2}\left\|{\boldsymbol{y}}_t-{\boldsymbol{x}}_*\right\|^2 \\ = f\left({\boldsymbol{y}}_t\right)+\frac{\mu}{2}\left\|{\boldsymbol{y}}_t-{\boldsymbol{x}}_*\right\|^2+\left\langle\nabla f\left({\boldsymbol{y}}_t\right), {\boldsymbol{x}}_*-{\boldsymbol{x}}_t+\right. \\ \left.{\boldsymbol{x}}_t-{\boldsymbol{y}}_t\right\rangle \\ = f\left({\boldsymbol{y}}_t\right)+\frac{1-\theta}{\theta}\left\langle\nabla f\left({\boldsymbol{y}}_t\right), {\boldsymbol{y}}_t-\tilde{{\boldsymbol{x}}}_{k-1}\right\rangle+ \\ \frac{\mu}{2}\left\|{\boldsymbol{y}}_t-{\boldsymbol{x}}_*\right\|^2+\left\langle\nabla f\left({\boldsymbol{y}}_t\right), {\boldsymbol{x}}_*-{\boldsymbol{x}}_t\right\rangle \\ \geqslant f\left({\boldsymbol{y}}_t\right)+\frac{1-\theta}{\theta}\left(f\left({\boldsymbol{y}}_t\right)-f\left(\tilde{{\boldsymbol{x}}}_{k-1}\right)+\right. \\ \frac{\mu}{2}\left\|{\boldsymbol{y}}_t-\tilde{{\boldsymbol{x}}}_{k-1}\right\|^2+\mathbb{E}\left(\frac{\mu}{2}\left\|{\boldsymbol{y}}_t-{\boldsymbol{x}}_*\right\|^2+\right. \left.\left\langle{\boldsymbol{g}}_t, {\boldsymbol{x}}_*-{\boldsymbol{x}}_{t+1}\right\rangle+\left\langle{\boldsymbol{g}}_t, {\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_t\right\rangle\right) \\ \geqslant f\left({\boldsymbol{y}}_t\right)+\frac{1-\theta}{\theta}\left(f\left({\boldsymbol{y}}_t\right)-f\left(\tilde{{\boldsymbol{x}}}_{k-1}\right)\right)+\mathbb{E}\left(\chi_{t+1}-\right. \\ \left.\frac{1}{1+\eta \sigma} \chi_t\right)+\mathbb{E}\left(\left\langle{\boldsymbol{g}}_t, {\boldsymbol{x}}_{t+1}-{\boldsymbol{x}}_t\right\rangle+\frac{\alpha L}{2 \eta} \| {\boldsymbol{x}}_t-\right. \\ {\boldsymbol{x}}_{t+1} \|^2 \\ \geqslant f\left({\boldsymbol{y}}_t\right)+\frac{1-\theta}{\theta}\left(f\left({\boldsymbol{y}}_t\right)-f\left(\tilde{{\boldsymbol{x}}}_{k-1}\right)\right)+\mathbb{E}\left(\chi_{t+1}-\right. \\ \left.\frac{1}{1+\eta \sigma} \chi_t\right)+\frac{1}{\theta} \mathbb{E}\left(f\left({\boldsymbol{y}}_{t+1}\right)-f\left({\boldsymbol{y}}_t\right)-\right. \\ \left.\left.\frac{2 \eta \theta}{\alpha-\eta \theta}\left(f\left({\boldsymbol{y}}_t\right)-f^*+f\left(\tilde{{\boldsymbol{x}}}_{k-1}\right)-f^*\right)\right)\right) = \mathbb{E}\left(\chi_{t+1}-\frac{1}{1+\eta \sigma} \chi_t\right)+ \\ \frac{1}{\theta} \mathbb{E}\left(f\left({\boldsymbol{y}}_{t+1}\right)-f^*\right)+\left(1+\frac{1-\theta}{\theta}-\frac{1}{\theta}\right)\left(f\left({\boldsymbol{y}}_t\right)-\right. \\ \left.f^*\right)-\frac{1-\theta}{\theta}\left(f\left(\tilde{{\boldsymbol{x}}}_{k-1}\right)-f^*\right)-\frac{2 \eta}{\alpha-\eta \theta}\left(f\left({\boldsymbol{y}}_t\right)-f^*\right)- \\ \frac{2 \eta}{\alpha-\eta \theta}\left(f\left(\tilde{{\boldsymbol{x}}}_{k-1}\right)-f^*\right)+f^*. \end{array} $

其中：第1个不等式利用了f的μ-强凸性, 第2个等式利用算法1中的设定y_t=θx_t+(1-θ) $ \tilde{\boldsymbol{x}}_{k-1} $而推得$ \boldsymbol{x}_t-\boldsymbol{y}_t=\frac{1-\theta}{\theta}\left(\boldsymbol{y}_t-\tilde{\boldsymbol{x}}_{k-1}\right) $，第2个不等式利用了f的μ-强凸性和方向g_t的无偏性, 第3个不等式利用了引理5.1, 第4个不等式先利用了引理5.3而后利用了引理5.2。

由此, 整理可得

$ \begin{aligned} & \mathbb{E} \chi_{t+1}+\frac{1}{\theta} \mathbb{E}\left(f\left({\boldsymbol{y}}_{t+1}\right)-f^*\right) \\ \leqslant & \frac{1}{1+\eta \sigma} \chi_t+\frac{2 \eta}{\alpha-\eta \theta}\left(f\left({\boldsymbol{y}}_t\right)-f^*\right)+ \\ & \left(\frac{1-\theta}{\theta}+\frac{2 \eta}{\alpha-\eta \theta}\right)\left(f\left(\tilde{{\boldsymbol{x}}}_{k-1}\right)-f^*\right). \end{aligned} $

注意到由引理5.4, 为使得

$ \frac{2 \eta}{\alpha-\eta \theta} \leqslant \frac{1}{1+\eta \sigma} \frac{1}{\theta}, $

(A)

只需要$ \frac{2 \frac{1}{m \mu}}{\alpha-\frac{1}{m \mu} \theta} \leqslant \frac{1}{1+\frac{1}{m \mu} \sigma} \frac{1}{\theta} $成立即可。记使得式(A)成立的最小正整数是M₁，则当m≥M₁时, 有

$ \mathbb{E} \chi_{t+1}+\frac{1}{\theta} \mathbb{E}\left(f\left(\boldsymbol{y}_{t+1}\right)-f^*\right)\\ \leqslant \frac{1}{1+\eta \sigma} \chi_t+\frac{1}{1+\eta \sigma} \frac{1}{\theta}\left(f\left(\boldsymbol{y}_t\right)-f^*\right)+ \\ \left(\frac{1-\theta}{\theta}+\frac{2 \eta}{\alpha-\eta \theta}\right)\left(f\left(\tilde{\boldsymbol{x}}_{k-1}\right)-f^*\right). $

对上式取全期望, 定义$ \mathfrak{L}_t \triangleq \mathbb{E} \chi_t+\frac{1}{\theta} \mathbb{E}\left(f\left(\boldsymbol{y}_t\right)-f^*\right) $并利用f的L-光滑性, 则有

$ \begin{aligned} & \mathfrak{L}_{t+1} \leqslant \frac{1}{1+\eta \sigma} \mathfrak{L}_t+\left(\frac{1-\theta}{\theta}+\right. \\ & \left.\frac{2 \eta}{\alpha-\eta \theta}\right) \frac{L}{2} \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_{k-1}-{\boldsymbol{x}}_*\right\|^2 . \end{aligned} $

反复利用上式, 可得

$ \begin{gathered} \mathfrak{L}_m \leqslant\left(\frac{1}{1+\eta \sigma}\right)^m\left(\mathbb{E} \chi_0+\frac{1}{\theta} \frac{L}{2} \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_{k-1}-{\boldsymbol{x}}_*\right\|^2\right)+ \\ \left(\frac{1-\theta}{\theta}+\frac{2 \eta}{\alpha-\eta \theta}\right) \frac{L}{2} \frac{1+\eta \sigma}{\eta \sigma} \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_{k-1}-{\boldsymbol{x}}_*\right\|^2. \end{gathered} $

其中利用了x₀ = y₀ = $ \tilde{\boldsymbol{x}}_{k-1}$与f的L-光滑性, 且对等比数列求和的结果进行了放缩。进一步有

$ \begin{aligned} & \mathbb{E} \chi_m \leqslant\left(\frac{1}{1+\eta \sigma}\right)^m\left(\mathbb{E} \chi_0+\frac{1}{\theta} \frac{L}{2} \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_{k-1}-{\boldsymbol{x}}_*\right\|^2\right)+ \\ & \left(\frac{1-\theta}{\theta}+\frac{2 \eta}{\alpha-\eta \theta}\right) \frac{L}{2} \frac{1+\eta \sigma}{\eta \sigma} \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_{k-1}-{\boldsymbol{x}}_*\right\|^2. \end{aligned} $

回忆定义$ \chi_t=\frac{\alpha L}{2} \frac{1+\eta \sigma}{\eta}\left\|\boldsymbol{x}_t-\boldsymbol{x}_*\right\|^2$, 对上式两边同乘$ \frac{2}{\alpha L} \frac{\eta}{1+\eta \sigma}$, 得到

$ \begin{gathered} \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_k-{\boldsymbol{x}}_*\right\|^2 \leqslant\left(\left(\frac{1}{1+\eta \sigma}\right)^m\left(1+\frac{\eta}{\alpha \theta(1+\eta \sigma)}\right)+\right. \\ \left.\frac{1}{\alpha \sigma}\left(\frac{1-\theta}{\theta}+\frac{2 \eta}{\alpha-\eta \theta}\right)\right) \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_{k-1}-{\boldsymbol{x}}_*\right\|^2，\end{gathered} $

其中利用了算法1对快照的选择方式$ \tilde{\boldsymbol{x}}_k$= x_m。

由β的定义, 上式即

$ \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_k-{\boldsymbol{x}}_*\right\|^2 \leqslant \beta \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_{k-1}-{\boldsymbol{x}}_*\right\|^2. $

(14)

注意β定义式里含有η=η_k-1(其中(k-1)是目前被取定和分析的外循环数), 因而此处的β是依赖于k的。下面将分析β定义式里的各个项并推导出β的一个不依赖于k的上界, 从而可以反复利用式(14)形式的递推式而得到收敛性结果。利用引理5.4, 有

$ \begin{array}{l} \left(\frac{1}{1+\eta \sigma}\right)^m =\left(1-\frac{\eta \sigma}{1+\eta \sigma}\right)^m \leqslant \exp \left(\frac{-\eta \sigma}{1+\eta \sigma} m\right) \\ \leqslant \exp \left(\frac{-\frac{\sigma}{m L}}{1+\frac{\sigma}{m \mu}} m\right) \\=\exp \left(\frac{-\frac{\sigma}{L}}{1+\frac{\sigma}{m \mu}}\right) \xrightarrow{{\text { as }} m \rightarrow \infty} \exp \left(-\frac{\sigma}{L}\right) . \end{array} $

由以上的极限式, 记M₂为使得

$ \left(\frac{1}{1+\eta \sigma}\right)^m \leqslant \exp \left(-\frac{\sigma}{L}\right)+\delta. $

(B)

成立的最小正整数, 则当m≥M₂时, 有$ \left(\frac{1}{1+\eta \sigma}\right)^m \leqslant 1-\delta $。类似地, 为使得

$ 1+\frac{\eta}{\alpha \theta(1+\eta \sigma)} \leqslant 1+\delta , $

(C)

只需要$ 1+\frac{\frac{1}{m \mu}}{\alpha \theta\left(1+\frac{1}{m L} \sigma\right)} \leqslant 1+\delta $即可。记使得式(C)成立的最小正整数为M₃。为使得

$ \frac{1}{\alpha \sigma} \frac{2 \eta}{\alpha-\eta \theta} \leqslant \frac{\delta^2}{3}, $

(D)

只需$ \frac{1}{\alpha \sigma} \frac{2 \frac{1}{m \mu}}{\alpha-\frac{1}{m \mu} \theta} \leqslant \frac{\delta^2}{3} $。记使得式(D)成立的最小正整数为M₄。回忆θ∈[θ₀, 1), 这推出

$ \frac{1}{\alpha \sigma} \frac{1-\theta}{\theta} \leqslant \frac{\delta^2}{2} . $

综上, 定义M$\triangleq $max(M₁, M₂, M₃, M₄)。当m≥M时, 有$ \beta \leqslant 1-\frac{\delta^2}{6}<1 $, 且根据式(14)有

$ \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_k-{\boldsymbol{x}}_*\right\|^2 \leqslant\left(1-\frac{\delta^2}{6}\right) \mathbb{E}\left\|\tilde{{\boldsymbol{x}}}_{k-1}-{\boldsymbol{x}}_*\right\|^2. $

(15)

此时注意各个M_i的获得基于引理5.4, 而引理5.4给出了对任何可能的BB步长的不依赖于外循环数的上下界。所以对不同的k，为保证式(15)成立而要求的内循环长度下界M的值是同一的, 故式(15)在m≥M的前提下对所有k∈{1, 2, …, l}都成立。反复利用此式, 则定理得证。

6 数值实验

本节将SVRG-BB-Katyusha与SVRG-BB-Katyusha-SPARSE应用于求解二分类问题的L₂正则逻辑回归模型给出实验结果, 模型的分量函数如下

$ f_i({\boldsymbol{x}})=\log \left(1+\exp \left(-a_i {\boldsymbol{b}}_i^{\mathrm{T}} {\boldsymbol{x}}\right)\right)+\frac{\lambda}{2}\|{\boldsymbol{x}}\|^2. $

其中：a_i∈{-1, 1}, $ {\boldsymbol{b}}_i \in \mathbb{R}^d $分别是样本i的标签和样本i的特征向量, $ \lambda \in \mathbb{R}_{+} $是正则化系数。所有实验环境均为Python 3.10.11, i5-12500H CPU。本文选择公开数据集Libsvmdata^①中的数据集ijcnn1、w8a和rcv1, 如表 1所示。

① 数据集网址: https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/

图 2~图 4中, x轴代表外循环数, y轴代表优化间隙, 即一定外循环数k对应的快照处目标函数值与目标函数最小值之差$ f\left(\tilde{\boldsymbol{x}}_k\right)-f\left(\boldsymbol{x}_*^{\prime}\right) $, 其中x′_*由运行相应数据集下使用最优固定步长且内循环次数设定为样本数2倍的SVRG达100个外循环后, 取使得目标函数值最小的快照点得到。在所有的数据集上设定λ=10^-4, m=2n。对于维数小于100的数据集(这里对应ijcnn1), 取α=0.5; 对于维数大于等于100的数据集(这里对应w8a与rcv1), 取α=0.7。将算法1与算法2要求输入的参数$ \sigma=\frac{\mu}{\alpha L} $中的强凸系数μ取为正则化参数λ，而对其中的李普希兹常数L使用公式(可以容易地证明如下公式确实得到了带正则项的逻辑回归目标函数的一个李普希兹常数)

$ L=\lambda+\frac{L^*}{n} \sum\limits_{i=1}^n\left\|{\boldsymbol{b}}_i\right\|^2, L^*=\frac{\sqrt{3}}{18} . $

总设定动量控制系数为θ=0.9。对于算法2, 总设定m₀=4。考虑到所测试算法的随机性, 对所有算法在相应设定下均运行了10次, 取数值平均后绘制图线。

图 2~图 4分别给出ijcnn1、w8a和rcv1数据集上的实验结果。

根据结果图, 可以得到如下2点观察: 其一, SVRG-BB-Katyusha与SVRG-BB-Katyusha-SPARSE在外循环数相同时, 最后输出点(即最后一个外循环末所得到的新快照)总拥有相较于SVRG-BB更小的优化间隙。具体地, 它们在ijcnn1与rcv1数据集上的表现较好, 优化间隙有若干数量级的领先, 而在w8a数据集上的表现较差, 优化间隙在选取较小或较大的初始步长时只有较微小的领先；其二, 使用m₀=4的设定, 算法2所执行的带Katyusha动量的内循环迭代次数约为算法1的25 %，而在表现上仍能保持相近, 甚至在一些情况下具有更优的表现。总之, 所提出的算法1与算法2在实际数值实验中效果优良, 以优化间隙为评价标准时相较于SVRG-BB有较为稳定且可观的优势。

7 结论

本文指出SVRG-BB的算法设计带来了“进展-自适应步长有效性”的权衡问题, 且该问题是制约SVRG-BB实际表现的一个因素。据此提出并引入新的Katyusha动量作用形式以处理该权衡问题, 通过在上述权衡中取得更好平衡来获得在优化间隙意义下更好的实际表现, 并给出所得到的SVRG-BB-Katyusha算法的线性收敛性质的证明。基于“贪婪”思想, 进一步提出SVRG-BB-Katyusha-SPARSE算法以减少带Katyusha动量的内循环迭代带来的额外计算量。在公开数据集上的数值实验表明所提出的2个方法相较于SVRG-BB具有较明显的优势, 即在达到一定外循环数时优化间隙有若干个数量级的减小。