论文部分内容阅读
摘 要：方差缩减算法的主要问题之一是如何选取一個合适的步长。在实践中，手动调整一个最佳的固定步长是很耗时的，所以该文提出将Polyak步长用于随机方差缩减梯度算法（SVRG），得到了一种新的SVRG-Polyak算法。对于光滑强凸的目标函数我们证明了SVRG-Polyak算法的线性收敛性。数值实验对比了SVRG-Polyak、SVRG和带有BB步长的SVRG（SVRG-BB）3种算法，结果表明SVRG-Polyak算法的有效性。
关键词：Polyak步长 方差缩减 强凸 线性收敛
中图分类号：O1 文献标识码：A文章编号：1672-3791（2021）06（a）-0174-04
Polyak Step Size for Variance Reduction Algorithm
LI Die
（college of science， Hebei University of Technology， Tianjin， 300401 China）
Abstract：One of the main problems of the variance reduction algorithm is how to choose an appropriate step size. In practice， it is time-consuming to manually adjust an optimal fixed step size， so this paper proposes to use Polyak step size for the random variance reduction gradient algorithm （SVRG）， and a new SVRG-Polyak algorithm is obtained. For the smooth and strongly convex objective function， we prove the linear convergence of the SVRG-Polyak algorithm. Numerical experiments compared SVRG-Polyak， SVRG and SVRG with BB step size （SVRG-BB） three algorithms， and the results show the effectiveness of SVRG-Polyak algorithm.
Key Words：Polyak step size; variance reduction; strong convexity; linear convergence
机器学习具有十分广泛的作用和研究价值，优化是机器学习研究的关键一步。几乎所有机器学习问题的模型求解都依赖于优化算法。因此，设计快速有效的优化算法在机器学习研究中至关重要。在机器学习中，我们经常遇到以下优化问题，设为从到的向量函数序列。
（1）
例如，给定一个由n个独立且分布均匀的样本组成的训练集，其中是第i个样本的输入特征向量，并且是第i个样本的标签（或目标），此时问题也称为监督学习。如果设置，则可以获得最小二乘回归;如果设置则将获得正则逻辑回归。
为了解决优化问题（1），一种流行的方法是梯度下降算法（GD），它可以通过以下更新规则来描述，对于…时，有
（2）
式中，是第t次迭代的学习率，用于调整参数更新的幅度。
GD在一阶算法中占据重要地位，但是在实际应用中还存在很多问题，需要对其进行改进。GD的一个主要问题是当问题规模较大时，由于需要计算全部梯度，导致计算量很大。随机梯度下降算法（SGD）[1]在一定程度上解决了这个问题。SGD使用随机梯度代替全梯度，减少了计算量：由于随机梯度的不确定性，可能导致在迭代过程中目标函数值不断反升，使得算法具备一定的跳出极小点的能力，从而增大算法找到全局最小点的概率。
SGD可以通过以下更新规则来描述，对于…，我们从{1，2…，n}中随机抽取it。
通常假设，是对的无偏估计，即。
SGD由于算法的随机性，产生了方差，导致算法的收敛速度不如梯度下降算法快，因此涌现了大量的方差缩减算法[2-4]。对于光滑和强凸的函数，Johnson等人提出的随机方差缩减梯度法（SVRG）[2]可以达到与SDCA和SAG[4]算法相同快的收敛率，都可以达到线性收敛，并且SVRG的线性收敛结果证明更简单、具有直观解释，而且与SDCA和SAG不同，SVRG无需存储中间梯度，因此对于一些复杂问题如结构预测问题和神经网络学习，此方法更易实现。
SVRG可以通过以下更新规则来描述，对于…时，有
（4）
其中，是每m次内循环迭代后得到的快照点，是函数在处的全梯度，且
对于随机算法（SGD及其变体）来说，一个重要的问题是如何选取一个合适的步长。对于SGD来说，使用一个固定步长可以确保收敛到解的一个邻域内。确保解收敛到精确最优值的一个普遍技术是使用下降步长。另外，还有一些动态调整步长的自适应方法[5-6]也很流行。步长的自适应选择使优化算法可以根据优化曲线的局部曲率和光滑性快速加速。但是从理论上讲，没有参数的算法很少。除了对SGD进行方差缩减和步长上的改进，还有结合动量的改进，例如：结合Nesterov动量的加速梯度算法（NAG），结合Katyusha动量的Katyusha算法[7]等。 1 Polyak步长
Polyak在文献[8]中提出Polyak步长，Polyak步长普遍用于次梯度法。假设我们要求解以下的无约束优化问题：
（5）
式中，f是凸但可能非光滑函数。假定在xt处的次梯度是可以计算的。次梯度法有如下形式：
式中，r趋于0，r的和是无穷的。满足上式的例子为：
对于凸函数，在第t步极小化迭代点与最优解的距离的上界：
其中
所以， 。
值f *使得构造不包含任何参数的次梯度法的如下變体成为可能：
因此，Polyak步长为：
（6）
在这种情况下，步长依赖于的估计。在一些应用中，f *的值是已知的（或者为0），该方法可以不用估计直接使用。现有的随机算法中Polyak步长使用的是随机梯度或是部分梯度，而该文使用的是全梯度。在随机方差缩减梯度算法外层迭代中，已计算出全梯度，所以计算量并没有增加，相比于其他算法增加了准确率。
2 带有Polyak步长的SVRG
定义1：函数是强凸的，如果满足：
（7）
定义2：函数是光滑的，或者是Lipschitz连续的，如果满足以下条件：
（8）
从上述定义可以得到函数是光滑的，或者是Lipschitz连续的。
（9）
等价于
（10）
定义3：如果函数F是光滑且强凸的，则函数 F的Lipschitz常数L与强凸常数μ的比为条件数k，即。
2.1 SVRG-Polyak算法
算法：
输入：内循环迭代次数m，初始点;
步0：对…执行;
步1：计算一个全梯度;
步2：计算步长;
步3：;
步4：对执行;
步5：随机选取;
步6：;
步7：结束内层循环;
步8：;
步9：结束外层循环。
2.2 收敛性分析
引理1（co-coercivity）[9]：如果是凸函数并且它的梯度是Lipschitz连续的，那么就有：
引理2：假定F是强凸且光滑的函数，那么算法SVRG-Polyak中的步长就满足下面的不等式：
证明：令（10）中，就有，便得到了ηk的下界。根据强凸性，
令，就有，便得到了的上界。
定理1：假定是强凸的，是光滑的，令。假定m充分大时得：
那么对于SVRG-Polyak，我们就可以得到期望上的线性收敛：
证明：对SVRG-Polyak的第k个时期，令，那么
第一个不等式是利用两次得到，第二个不等式是对函数使用引理1以及利用和的Lipschitz连续性得到，最后一个等式是利用和得到。下面我们在和的条件下界定与的距离。
其中第三个不等式用的是的强凸性。通过对t递归应用上面不等式，并结合和，可以得到：
当选取充分大的m时，，算法～SVRG-Polyak～在期望上线性收敛：
推论1[SVRG-BB中推论3.6][10]：在SVRG-I中，如果m和η的选取使得下面的不等式成立：
那么SVRG-I（SVRG算法Option I）在期望上线性收敛：
可以看出，SVRG-Polyak算法也满足这样的收敛性。
推论2：定义，可以看出。在SVRG-Polyak中，如果选取m满足
那么SVRG-Polyak可以实现期望上的线性收敛：
证明：结合推论1和η以及m的范围有：
3 数值实验
下面我们给出了该文要用到的问题模型l2-正则的逻辑回归。
逻辑回归：
其中，和分别是第i个样本的特征向量和类标签，是一个权重参数。该文中的数值实验使用的是w8a数据集，它可以从LIBSVM网站上得到。该数据集的大小n为49 749，特征维数d为300。
在该节，我们针对求解逻辑回归问题在w8a数据集上比较了SVRG-Polyak和SVRG以及SVRG-BB，如图1所示。对于SVRG，使用的是3种不同的步长，分别为0.02、0.1、0.5;对于SVRG-BB，选择手调的最优步长（0.1）为初始步长。对于SVRG-Polyak、SVRG、SVRG-BB，选取m=2n，正如文献[2]建议的那样。在图1中，x轴代表的是时期数k，从左到右y轴代表的分别是函数值与最优值的距离、函数梯度和步长。其中一长一短分布不均的虚线代表SVRG算法，从图中可以看出，步长为0.1的那条虚线收敛性最好。分布均匀的那条虚线对应于初始步长为最佳的固定步长的SVRG-BB 算法，带有十字的实线对应于该文提出的SVRG-Polyak 算法。SVRG-Polyak始终可以实现与SVRG相同的次优水平，并且优于SVRG-BB，且不需要给定初始步长。尽管与调整了最佳步长的SVRG相比，SVRG-Polyak需要更多的时间，但SVRG-Polyak明显比选择另两种步长的SVRG和SVRG-BB好。 4 結语
综上所述，提出了使用带有Polyak步长的随机方差缩减梯度法（SVRG-Polyak）。对于强凸函数，从理论上证明了SVRG-Polyak的线性收敛性，并且还证明了SVRG-Polyak需要更少的内循环迭代步便可以达到这样一个收敛。相比于SVRG-BB而言，SVRG-Polyak相比于SVRG-BB无需存储上一步的变量和梯度，并且不需要给定初始步长。而且我们还做了数值实验，比较了SVRG-Polyak、SVRG-BB和SVRG。数值实验表明我们的算法和SVRG-BB、SVRG具有可比性，甚至要优于这两种算法。
参考文献
[1] ROBBINS H， MONRO S.A Stochastic Approximation Method[J].Annals of Mathematical Stats， 1951，22（3）：400-407.
[2] JOHNSON R，ZHANG T.Accelerating stochastic gradient descent using predictive variance reduction[J].News in physiological ences，2013，1（3）：315-323.
[3] SHANG F，ZHOU K，LIU H，et al.VR-SGD：A Simple Stochastic Variance Reduction Method for Machine Learning[J]. IEEE Transactions on Knowledge and Data Engineering，2020，32（1）：188-202.
[4] SCHMIDT M，ROUX NL，BACH F.Minimizing Finite Sums with the Stochastic Average Gradient[J]. Mathematical Programming，2017，162（1-2）：1-30.
[5] 史加荣，王丹，尚凡华，等.随机梯度下降算法研究进展[J/OL].自动化学报：1-17[2021-07-26].https：//www.doi.org/10.16383/j.aas.c190260.
[6] 刘彦，郭田德，韩丛英.一类随机方差缩减算法的分析与改进[J/OL].中国科学：数学（英文版）：1-18[2021-07-26].https：//www.kns.cnki.net/kcms/detail/11.5837.O1.20200922.1600.002.html.
[7] Allen-Zhu Z. Katyusha： The first direct acceleration of stochastic gradient methods[J].The Journal of Machine Learning Research，2017，18（1）：8194-8244.
[8] POLYAK B T. Introduction to optimization[M].New York：Chapman & Hall，1987：138-144.
[9] NESTEROV Y.Introductory Lectures on Convex Optimization：A Basic Course[M].Boston：Springer US，2004.
[10] TAN CH， MA SQ， DAI YH， et al.Barzilai-Borwein Step Size for Stochastic Gradient Descent[C]//Advances in Neural Information Processing Systems. New York：Curran Associates Inc，2016：685-693.
关键词：Polyak步长 方差缩减 强凸 线性收敛
中图分类号：O1 文献标识码：A文章编号：1672-3791（2021）06（a）-0174-04
Polyak Step Size for Variance Reduction Algorithm
LI Die
（college of science， Hebei University of Technology， Tianjin， 300401 China）
Abstract：One of the main problems of the variance reduction algorithm is how to choose an appropriate step size. In practice， it is time-consuming to manually adjust an optimal fixed step size， so this paper proposes to use Polyak step size for the random variance reduction gradient algorithm （SVRG）， and a new SVRG-Polyak algorithm is obtained. For the smooth and strongly convex objective function， we prove the linear convergence of the SVRG-Polyak algorithm. Numerical experiments compared SVRG-Polyak， SVRG and SVRG with BB step size （SVRG-BB） three algorithms， and the results show the effectiveness of SVRG-Polyak algorithm.
Key Words：Polyak step size; variance reduction; strong convexity; linear convergence
机器学习具有十分广泛的作用和研究价值，优化是机器学习研究的关键一步。几乎所有机器学习问题的模型求解都依赖于优化算法。因此，设计快速有效的优化算法在机器学习研究中至关重要。在机器学习中，我们经常遇到以下优化问题，设为从到的向量函数序列。
（1）
例如，给定一个由n个独立且分布均匀的样本组成的训练集，其中是第i个样本的输入特征向量，并且是第i个样本的标签（或目标），此时问题也称为监督学习。如果设置，则可以获得最小二乘回归;如果设置则将获得正则逻辑回归。
为了解决优化问题（1），一种流行的方法是梯度下降算法（GD），它可以通过以下更新规则来描述，对于…时，有
（2）
式中，是第t次迭代的学习率，用于调整参数更新的幅度。
GD在一阶算法中占据重要地位，但是在实际应用中还存在很多问题，需要对其进行改进。GD的一个主要问题是当问题规模较大时，由于需要计算全部梯度，导致计算量很大。随机梯度下降算法（SGD）[1]在一定程度上解决了这个问题。SGD使用随机梯度代替全梯度，减少了计算量：由于随机梯度的不确定性，可能导致在迭代过程中目标函数值不断反升，使得算法具备一定的跳出极小点的能力，从而增大算法找到全局最小点的概率。
SGD可以通过以下更新规则来描述，对于…，我们从{1，2…，n}中随机抽取it。
通常假设，是对的无偏估计，即。
SGD由于算法的随机性，产生了方差，导致算法的收敛速度不如梯度下降算法快，因此涌现了大量的方差缩减算法[2-4]。对于光滑和强凸的函数，Johnson等人提出的随机方差缩减梯度法（SVRG）[2]可以达到与SDCA和SAG[4]算法相同快的收敛率，都可以达到线性收敛，并且SVRG的线性收敛结果证明更简单、具有直观解释，而且与SDCA和SAG不同，SVRG无需存储中间梯度，因此对于一些复杂问题如结构预测问题和神经网络学习，此方法更易实现。
SVRG可以通过以下更新规则来描述，对于…时，有
（4）
其中，是每m次内循环迭代后得到的快照点，是函数在处的全梯度，且
对于随机算法（SGD及其变体）来说，一个重要的问题是如何选取一个合适的步长。对于SGD来说，使用一个固定步长可以确保收敛到解的一个邻域内。确保解收敛到精确最优值的一个普遍技术是使用下降步长。另外，还有一些动态调整步长的自适应方法[5-6]也很流行。步长的自适应选择使优化算法可以根据优化曲线的局部曲率和光滑性快速加速。但是从理论上讲，没有参数的算法很少。除了对SGD进行方差缩减和步长上的改进，还有结合动量的改进，例如：结合Nesterov动量的加速梯度算法（NAG），结合Katyusha动量的Katyusha算法[7]等。 1 Polyak步长
Polyak在文献[8]中提出Polyak步长，Polyak步长普遍用于次梯度法。假设我们要求解以下的无约束优化问题：
（5）
式中，f是凸但可能非光滑函数。假定在xt处的次梯度是可以计算的。次梯度法有如下形式：
式中，r趋于0，r的和是无穷的。满足上式的例子为：
对于凸函数，在第t步极小化迭代点与最优解的距离的上界：
其中
所以， 。
值f *使得构造不包含任何参数的次梯度法的如下變体成为可能：
因此，Polyak步长为：
（6）
在这种情况下，步长依赖于的估计。在一些应用中，f *的值是已知的（或者为0），该方法可以不用估计直接使用。现有的随机算法中Polyak步长使用的是随机梯度或是部分梯度，而该文使用的是全梯度。在随机方差缩减梯度算法外层迭代中，已计算出全梯度，所以计算量并没有增加，相比于其他算法增加了准确率。
2 带有Polyak步长的SVRG
定义1：函数是强凸的，如果满足：
（7）
定义2：函数是光滑的，或者是Lipschitz连续的，如果满足以下条件：
（8）
从上述定义可以得到函数是光滑的，或者是Lipschitz连续的。
（9）
等价于
（10）
定义3：如果函数F是光滑且强凸的，则函数 F的Lipschitz常数L与强凸常数μ的比为条件数k，即。
2.1 SVRG-Polyak算法
算法：
输入：内循环迭代次数m，初始点;
步0：对…执行;
步1：计算一个全梯度;
步2：计算步长;
步3：;
步4：对执行;
步5：随机选取;
步6：;
步7：结束内层循环;
步8：;
步9：结束外层循环。
2.2 收敛性分析
引理1（co-coercivity）[9]：如果是凸函数并且它的梯度是Lipschitz连续的，那么就有：
引理2：假定F是强凸且光滑的函数，那么算法SVRG-Polyak中的步长就满足下面的不等式：
证明：令（10）中，就有，便得到了ηk的下界。根据强凸性，
令，就有，便得到了的上界。
定理1：假定是强凸的，是光滑的，令。假定m充分大时得：
那么对于SVRG-Polyak，我们就可以得到期望上的线性收敛：
证明：对SVRG-Polyak的第k个时期，令，那么
第一个不等式是利用两次得到，第二个不等式是对函数使用引理1以及利用和的Lipschitz连续性得到，最后一个等式是利用和得到。下面我们在和的条件下界定与的距离。
其中第三个不等式用的是的强凸性。通过对t递归应用上面不等式，并结合和，可以得到：
当选取充分大的m时，，算法～SVRG-Polyak～在期望上线性收敛：
推论1[SVRG-BB中推论3.6][10]：在SVRG-I中，如果m和η的选取使得下面的不等式成立：
那么SVRG-I（SVRG算法Option I）在期望上线性收敛：
可以看出，SVRG-Polyak算法也满足这样的收敛性。
推论2：定义，可以看出。在SVRG-Polyak中，如果选取m满足
那么SVRG-Polyak可以实现期望上的线性收敛：
证明：结合推论1和η以及m的范围有：
3 数值实验
下面我们给出了该文要用到的问题模型l2-正则的逻辑回归。
逻辑回归：
其中，和分别是第i个样本的特征向量和类标签，是一个权重参数。该文中的数值实验使用的是w8a数据集，它可以从LIBSVM网站上得到。该数据集的大小n为49 749，特征维数d为300。
在该节，我们针对求解逻辑回归问题在w8a数据集上比较了SVRG-Polyak和SVRG以及SVRG-BB，如图1所示。对于SVRG，使用的是3种不同的步长，分别为0.02、0.1、0.5;对于SVRG-BB，选择手调的最优步长（0.1）为初始步长。对于SVRG-Polyak、SVRG、SVRG-BB，选取m=2n，正如文献[2]建议的那样。在图1中，x轴代表的是时期数k，从左到右y轴代表的分别是函数值与最优值的距离、函数梯度和步长。其中一长一短分布不均的虚线代表SVRG算法，从图中可以看出，步长为0.1的那条虚线收敛性最好。分布均匀的那条虚线对应于初始步长为最佳的固定步长的SVRG-BB 算法，带有十字的实线对应于该文提出的SVRG-Polyak 算法。SVRG-Polyak始终可以实现与SVRG相同的次优水平，并且优于SVRG-BB，且不需要给定初始步长。尽管与调整了最佳步长的SVRG相比，SVRG-Polyak需要更多的时间，但SVRG-Polyak明显比选择另两种步长的SVRG和SVRG-BB好。 4 結语
综上所述，提出了使用带有Polyak步长的随机方差缩减梯度法（SVRG-Polyak）。对于强凸函数，从理论上证明了SVRG-Polyak的线性收敛性，并且还证明了SVRG-Polyak需要更少的内循环迭代步便可以达到这样一个收敛。相比于SVRG-BB而言，SVRG-Polyak相比于SVRG-BB无需存储上一步的变量和梯度，并且不需要给定初始步长。而且我们还做了数值实验，比较了SVRG-Polyak、SVRG-BB和SVRG。数值实验表明我们的算法和SVRG-BB、SVRG具有可比性，甚至要优于这两种算法。
参考文献
[1] ROBBINS H， MONRO S.A Stochastic Approximation Method[J].Annals of Mathematical Stats， 1951，22（3）：400-407.
[2] JOHNSON R，ZHANG T.Accelerating stochastic gradient descent using predictive variance reduction[J].News in physiological ences，2013，1（3）：315-323.
[3] SHANG F，ZHOU K，LIU H，et al.VR-SGD：A Simple Stochastic Variance Reduction Method for Machine Learning[J]. IEEE Transactions on Knowledge and Data Engineering，2020，32（1）：188-202.
[4] SCHMIDT M，ROUX NL，BACH F.Minimizing Finite Sums with the Stochastic Average Gradient[J]. Mathematical Programming，2017，162（1-2）：1-30.
[5] 史加荣，王丹，尚凡华，等.随机梯度下降算法研究进展[J/OL].自动化学报：1-17[2021-07-26].https：//www.doi.org/10.16383/j.aas.c190260.
[6] 刘彦，郭田德，韩丛英.一类随机方差缩减算法的分析与改进[J/OL].中国科学：数学（英文版）：1-18[2021-07-26].https：//www.kns.cnki.net/kcms/detail/11.5837.O1.20200922.1600.002.html.
[7] Allen-Zhu Z. Katyusha： The first direct acceleration of stochastic gradient methods[J].The Journal of Machine Learning Research，2017，18（1）：8194-8244.
[8] POLYAK B T. Introduction to optimization[M].New York：Chapman & Hall，1987：138-144.
[9] NESTEROV Y.Introductory Lectures on Convex Optimization：A Basic Course[M].Boston：Springer US，2004.
[10] TAN CH， MA SQ， DAI YH， et al.Barzilai-Borwein Step Size for Stochastic Gradient Descent[C]//Advances in Neural Information Processing Systems. New York：Curran Associates Inc，2016：685-693.