基于1_t-Polyak步长的随机控制的随机梯度算法.pdf

Advances in Applied Mathematics 应用数学进展应用数学进展,2024,13(3),1008-1017 Published Online March 2024 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2024.133095 文章引用文章引用:刘晨晨.基于 1/t-Polyak 步长的随机控制的随机梯度算法J.应用数学进展,2024,13(3):1008-1017.DOI:10.12677/aam.2024.133095 基于基于1/t-Polyak步长的随机控制的随机梯度算法步长的随机控制的随机梯度算法 刘晨晨刘晨晨 河北工业大学理学院，天津 收稿日期：2024年2月27日；录用日期：2024年3月21日；发布日期：2024年3月27日 摘摘 要要 随机梯度下降算法已成为求解大规模有限和优化问题的流行算法，然而，由于其在迭代过程中会产生方随机梯度下降算法已成为求解大规模有限和优化问题的流行算法，然而，由于其在迭代过程中会产生方差，导致了振荡现象。随机控制的随机梯度差，导致了振荡现象。随机控制的随机梯度(SCSG)算法缩减了该方差，但算法缩减了该方差，但SCSG算法对于步长有较强的限算法对于步长有较强的限制。为了扩大制。为了扩大SCSG算法的步长选择范围，基于算法的步长选择范围，基于1/t-带步长与带步长与Polyak步长步长，提出提出1/t-Polyak步长步长，并将其并将其与与SCSG算法结合算法结合，提出提出SCSGP算法。建立了算法。建立了SCSGP算法在强凸条件下的线性收敛性，数值实验表明算法在强凸条件下的线性收敛性，数值实验表明SCSGP算法与其算法与其他他随机梯度类算法相比有明显优势随机梯度类算法相比有明显优势。关键词关键词 有限和优化，随机算法，方差缩减，有限和优化，随机算法，方差缩减，1/t-带步长带步长 1/t-Polyak Stepsize for the Stochastically Controlled Stochastic Gradient Algorithm Chenchen Liu School of Sciences,Hebei University of Technology,Tianjin Received:Feb.27th,2024;accepted:Mar.21st,2024;published:Mar.27th,2024 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 va-riance 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 stochas-tic gradient(SCSG)algorithm,the SCSGP algorithm is proposed.We establish the linear conver-gence rate of SCSGP for strongly convex problems.Numerical experiments demonstrate a clear 刘晨晨 DOI:10.12677/aam.2024.133095 1009 应用数学进展 advantage of SCSGP over other stochastic gradient algorithms.Keywords Finite-Sum Optimization,Stochastic Algorithms,Variance Reduction,1/t-Band Stepsize Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 考虑有限和优化问题：()()11mindnixif xfxn=，(1)其中分量函数()ifx连续可微，假设()f x是强凸的。机器学习中满足条件的优化问题有很多，例如带2?正则项的逻辑回归问题和带2?正则项的最小平方回归问题等1 2 3。当数据规模过大时，随机梯度下降(SGD)算法4是求解问题(1)的主流算法，即用随机梯度估计全梯度，其迭代格式为()1ttttitxxfx+=，其中0t是步长，()titfx是分量函数()tifx在tx处的梯度。随机梯度()titfx与全梯度()tf x之间的方差导致 SGD 即使在强凸条件下，也只能达到次线性收敛速度5。方差缩减梯度(SVRG)算法6通过内外两层循环达到缩减方差的目的，但由于其在外循环中需要计算全梯度且内循环次数较大，导致数据规模过大时计算量大。为了改善这个问题，SCSG 7令内循环次数服从几何分布且在外循环中计算批量梯度()1tii ItgfxI=?，其中 tIn，tI为tI的批量大小，x?为在外循环中设置的快照点。在内循环中，SCSG 用与 SVRG 相同的格式更新梯度估计量：()()tttitigfxfxg=+?。在强凸条件下，其使用固定批量可线性收敛到解的邻域。SCSG 适用于求解大规模4910,10n、低精度4210,10的优化问题7 8 9，可以经过很少的有效循环次数收敛到上述目标精度。步长是保证随机梯度类算法收敛的关键因素，很小的常数步长和衰减步长都会使算法收敛缓慢，并且手动调整常数步长的过程相当耗时10 11 12。Polyak 步长13利用迭代过程中产生的函数值和梯度自动地计算步长，避免了手动调整的过程，其计算公式为()()*22tttf xff x=，其中*f是()f x的极小值。为了将 Polyak 步长与随机梯度类算法结合，Loizou 等人14提出 Polyak 步长的随机版本(SPS)：Open AccessOpen Access刘晨晨 DOI:10.12677/aam.2024.133095 1010 应用数学进展 ()()*22tttitititfxffx=，其中*tif是()tifx的极小值。SGD 结合 SPS 步长比结合固定步长数值表现好。当 SPS 步长中*tif不易求解时，可用一个下界*ttiif?来替换15。最近，Wang 等人16介绍了 1/t-带步长，其允许步长在一定范围内扰动，具体格式为 tmMtt，1t，其中mM是正常数。显然，衰减步长0tt=是 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 步长：,;,;,PtPPtttPtm tm tm tM tM tM t=，则对任意满足tND 的序列nD有()()1011tttNNNtDDDD+=，其中 E 记为对所有随机变量取期望。记mintt=，则对任意 tT有()()101E1tttNNNDDDD。(4)为了应用(3)，需要证明用到的相关序列nD满足tND。下面引理保证了该性质。引理引理 2 假设()ifx是 L-光滑的，令2 313ttbMLtB且8ttBb，则对任意1t，21ttxx?，()*tf xf?，()2tf x?，1,ttte xx?，(),ttef x有222,aa bc bc+，令2c=，则有()()()221,4ttttktkttefxfxe+。(6)因为tMt，2 313ttbMLtB且8ttBb，可知304tL。由(5)和(6)得到()()()()()()()()()221320113344.324kttttkkktIttttttkttLf xf xf xeLLLxxbL+?(7)注意到()()()1kktttktxxv+=，用类似(5)的推导过程可得()()()()()()()()()()()()()()()()()()()()()()()()()()()2222100022200022200022222,2,2,12,2,22.kkkkkktkktkIIIktkkttttttttktkItktkttttttttttttkttkttttttttkttxxxxvxxvxxf xxxe xxvLxxf xxxe xxbf xe+=+=+?(8)再次使用222,aa bc bc+并取28tttbcB=，则有()()()()()()()()2220082,8tttttttttkkkttktBbf xxxf xxxbB+，()()()()2220082,8ttttttttkttkttBbe xxexxbB+。将上述不等式和(7)代入(8)得到()()()()()()()()()()22332222210013288112142283 44.33 4kkttttttttttkkttItttttttttttkktttIbLL B bBLxxxxeBbLbLB bf xf xL+?(9)由2 313tttbLB和8ttBb可得()()()()()()()()()4 322332 33 43 43 4 11 68 27328221 31128 27741.21442142ttttttttttttttttttb Bb BLL B bbLbb BBBbBB+=刘晨晨 DOI:10.12677/aam.2024.133095 1013 应用数学进展 结合上式和(9)有()()()()()()()()()()()()()()()()()2 322221002 312 3222011 3781214241 3281 313211221132443 43 4kktttttttttkkttItttttttttttkkItttttttktttttb BbbBxxxxeBBbb BB bf xf xb BbBBxxeBbb+?()()()()()1.ktttkkIf xf x+?(10)为了证明()()*tkf xf和()()210ttkxx+的上界，记()()()()()2*0123.tttttktkktBGf xfxxb=+对(10)取全期望得到()()()()()()222102222013212124413212112441321211.244ttttttkkktttttttkttttktttttttbBGGxxeBbbBGeBbbBGeBb+由ttttBNGeomBb+可得(),kkttttttttttbBBP NkBbBbBb=+00132413241324241.2424242411tNkkkttttttttkktttttttbBbBBbBbBBBbBbb+=+于是有()()22024242121,114ttttttNttttBbBGGebb+即()()()()()()*02*2012324241221213.114tttttttNNttttttttttttBf xfxxbBbBBf xfebbb+分别用tx?替换()ttNx，用1tx?替换()0tx，由8中引理 B.3 得到2te，这表明21ttxx?和()*tf xf?。由(7)可知()2tf x?。利用222,aa bc bc+可得1,ttte xx?和 刘晨晨 DOI:10.12677/aam.2024.133095 1014 应用数学进展 (),ttef x?。结论得证。现在分析强凸条件下 SCSGP 的线性收敛速度。定理定理 1 假设()ifx是 L-光滑的且()f x是-强凸的，令1 2tbt=，03 2tBB t=，则()()*0015,8TTftMf xfcJ BnmB+?其中00332cmB=+，()*0ff xf=?，()()*11supnixifxf xn=和()1,;0,.ttBnJ Bn=其他 证明：证明：由8中引理 B.3 和等式(20)得到()()()()32322332*1222221.ttttttttttttttttttttttBbbLf xbBbL b BL Bbf xf xLJ BnbB +?(11)由tmMtt，2 313ttbMLtB和8ttBb可得()()33332233233223322222221111732222,8341 1 181 271083tttttttttttttttttttbbbt bMLLBBtbL b BL Bt bM tL b BM L Bbb 其中第三个不等式用了1tb。另外，11295111128244tttttbbMLLBtB+=。将上述两个系数代入(11)，并再次使用tmMtt得到()()()()2*1315.4tttttttBMf xf xf xJ Bntbmmtb+?(12)因为 f 是-强凸的，可得()()()()22*,222tttttttxxf xxxf xxxff xff x+?其中第二个不等式利用了222,aa bc bc+。重新整理上式得()()()2*2.ttf xf xf?将上式代入(12)得到()()()()*115323.4tttttttbmBfxftbfxfMJ Bn+?替换1 2tbt=和03 2tBB t=，然后两边同除303 2232tmB t+可得 刘晨晨 DOI:10.12677/aam.2024.133095 1015 应用数学进展 ()()()()()()()*100*3*1002153324 32153.324 32tttttMJ Bnf xff xfmBmBtMJ Bnf xfmBmB+?其中最后一个不等式成立是因为1t。上式可以写为()()()()*100015153.8328ttttMJ BnMJ Bnf xff xfmBmBmB+?(13)将,1tT=?时的(13)累加求和得到()()()()*0000015153.8328TttTtfMJ BnMJ Bnf xff xfcmBmBmB+?(14)重新整理(14)，证毕。4.数值实验数值实验 Figure 1.Comparison of different stochastic gradient algorithms 图图 1.不同随机梯度类算法的对比 刘晨晨 DOI:10.12677/aam.2024.133095 1016 应用数学进展 考虑正则化的逻辑回归问题()()()2111log 1exp,2nTiiif xba xxnn=+其中()1,1,1ndiiia b=是给定的训练集。7中指出内循环次数tN取期望值有助于增加 SCSG 算法的稳定性，且从tI中选取kI?可以减小计算代价，所以在实验中设置tttNB b=(几何随机变量tN的期望)且从tI中选取kI?，其中 记为向下取整。为了验证 SCSGP 的有效性，比较 SCSGP、SCSG、SVRG、SVRGBB 和 SGD。具体地，SVRG 中设置小批量1tb；SCSG 设置0.05tBn，1tb，tttNB b=；SCSGP 设置3 20tBB tn=，1 2tbtn=，tttNB b=。表 1 给出 LIBSVM(网址：https:/www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/)中四个标准数据集的信息。用表 2 的参数值进行对比实验，最优间隙随有效循环次数变化情况见图 1。SCSGP 明显比 SCSG 表现好，并且在前几个有效循环次数中，SCSGP 与其它随机梯度类算法相比具有更好的数值结果。Table 1.The information of data sets 表表 1.数据集信息 数据集 n d L a8a 22,696 123 3.5 a9a 32,561 123 3.5 w8a 49,749 300 28.5 ijcnn1 49,990 22 0.9842 Table 2.Parameters used for experiments 表表 2.实验中的参数设置 数据集 SGD SVRG SVRGBB SCSG SCSGP a8a 7 L=0.8tNn=0.1 L=0.8tNn=0.05 L=0.5mL=10s=a9a 7 L=0.8tNn=0.05 L=0.8tNn=0.05 L=0.5mL=10s=w8a 25 L=0.8tNn=2 L=0.8tNn=5 L=20mL=20s=ijcnn1 80 L=tNn=0.1 L=tNn=0.1 L=1mL=15s=5.总结总结 基于 Polyak 步长和 1/t-带步长提出 1/t-Polyak 步长，并将该步长与 SCSG 结合提出 SCSGP 算法。当目标函数强凸光滑时，SCSGP 线性收敛。数值实验考虑正则化的逻辑回归问题，实验结果表明在前几个有效循环次数中 SCSGP 比其他随机梯度类算法表现好。刘晨晨 DOI:10.12677/aam.2024.133095 1017 应用数学进展 参考文献参考文献 1 Kasiviswanathan,S.P.and Jin,H.(2016)Efficient Private Empirical Risk Minimization for High-Dimensional Learn-ing.International Conference on Machine Learning,48,488-497.2 Krizhevsky,A.,Sutskever,I.and Hinton,G.E.(2017)Imagenet Classification with Deep Convolutional Neural Net-works.Communications of the ACM,60,84-90.https:/doi.org/10.1145/3065386 3 Sutskever,I.,Martens,J.,Dahl,G.,et al.(2013)On the Importance of Initialization and Momentum in Deep Learning.International Conference on Machine Learning,28,1139-1147.4 Robbins,H.and Monro,S.(1951)A Stochastic Approximation Method.The Annals of Mathematical Statistics,22,400-407.https:/doi.org/10.1214/aoms/1177729586 5 Bottou,L.,Curtis,F.E.and Nocedal,J.(2018)Optimization Methods for Large-Scale Machine Learning.SIAM Review,60,223-311.https:/doi.org/10.1137/16M1080173 6 Johnson,R.and Zhang,T.(2013)Accelerating Stochastic Gradient Descent Using Predictive Variance Reduction.Ad-vances in Neural Information Processing Systems,1,315-323.7 Lei,L.and Jordan,M.(2017)Less than a Single Pass:Stochastically Controlled Stochastic Gradient.Artificial Intelli-gence and Statistics,54,148-156.8 Lei,L.,Ju,C.,Chen,J.,et al.(2017)Non-Convex Finite-Sum Optimization via SCSG Methods.Advances in Neural Information Processing Systems,11,2345-2355.9 Lei,L.and Jordan,M.I.(2020)On the Adaptivity of Stochastic Gradient-Based Optimization.SIAM Journal on Opti-mization,30,1473-1500.https:/doi.org/10.1137/19M1256919 10 Gower,R.M.,Loizou,N.,Qian,X.,et al.(2019)SGD:General Analysis and Improved Rates.International Confe-rence on Machine Learning,97,5200-5209.11 Ghadimi,S.and Lan,G.(2013)Stochastic First-and Zeroth-Order Methods for Nonconvex Stochastic Programming.SIAM Journal on Optimization,23,2341-2368.https:/doi.org/10.1137/120880811 12 Rakhlin,A.,Shamir,O.and Sridharan,K.(2011)Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization.arXiv:1109.5647.13 Polyak,B.T.(1987)Introduction to Optimization.Optimization Software.Publications Division,New York.14 Loizou,N.,Vaswani,S.,Laradji,I.H.,et al.(2021)Stochastic Polyak Step-Size for SGD:An Adaptive Learning Rate for Fast Convergence.International Conference on Artificial Intelligence and Statistics,130,1306-1314.15 Orvieto,A.,Lacoste-Julien,S.and Loizou,N.(2022)Dynamics of SGD with Stochastic Polyak Stepsizes:Truly Adap-tive Variants and Convergence to Exact Solution.Advances in Neural Information Processing Systems,35,26943-26954.16 Wang,X.and Yuan,Y.(2023)On the Convergence of Stochastic Gradient Descent with Bandwidth-Based Step Size.Journal of Machine Learning Research,24,1-49.