加速随机递归梯度下降算法的复杂度分析  

Complexity Analysis of Accelerated Stochastic Recursive Gradient Descent Algorithm

作　　者：费经泰 程一元 查星星 FEI Jingtai;CHENG Yiyuan;ZHA Xingxing(School of Mathematics and Big Data,Chaohu University,Chaohu Anhui 238024,China)

机构地区：[1]巢湖学院数学与大数据学院,安徽巢湖238024

出　　处：《萍乡学院学报》2024年第3期5-11,共7页Journal of Pingxiang University

基　　金：安徽省高校自然科学研究项目“分布式机器学习的算法设计与理论研究”(KJ2021A1033);巢湖学院校级科研项目“大数据背景下高效分布式计算的应用研究”(XLZ-202202);“加速随机方差缩减梯度下降算法研究”(XLY-202105)。

摘　　要：课题组为进一步降低传统随机递归梯度下降算法(SARAH)复杂度,利用内循环数目倍增技术,提出了一种新的算法--Epoch-Doubling-SARAH算法,并通过构造Lyapunov函数证明了Epoch-Doubling-SARAH算法在非强凸条件下具有线性收敛阶,且推导出了算法的复杂度为O(1/ε+nlog(1/ε)),该结果优于SARAH算法复杂度。再将Epoch-Doubling-SARAH算法与SARAH算法在Mnist和Mushroom两个数据集上进行对比实验,实验结果表明Epoch-Doubling-SARAH算法具有更快的收敛速度,进而说明了本文算法理论分析的正确性。In order to reduce the complexity of traditional stochastic recursive gradient descent algorithm(SARAH),by using the inner loop number multiplication technique,a new accelerated algorithm called Epoch-Doubling-SARAH is proposed,and the convergence of the algorithm is studied under non-strongly convex.It is proved that the Epoch-Doubling-SARAH algorithm has a linear convergence rate and the complexity isO(1/ε+nlog(1/ε))by constructing Lyapunov function,this result is better than the complexity of traditional SARAH algorithm.Finally,the Epoch-Doubling-SARAH algorithm is compared with SARAH algorithm on Mnist and Mushroom data sets,experimental results show that Epoch-Doubling-SARAH algorithm has faster convergence and justify the correctness of theoretical analysis.

关 键 词：机器学习 随机递归梯度 下降算法 循环倍增 收敛速率 算法复杂度 

分 类 号：O174.13[理学—数学]