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

课题组为进一步降低传统随机递归梯度下降算法(SARAH)复杂度,利用内循环数目倍增技术,提出了一种新的算法--Epoch-Doubling-SARAH算法,并通过构造Lyapunov函数证明了Epoch-Doubling-SARAH算法在非强凸条件下具有线性收敛阶,且推导出了算法的复杂度为O(1/ε+nlong(1/ε)),该结果优于SARAH算法复杂度。再将Epoch-Doubling-SARAH算法与SARAH算法在Mnist和Mushroom两个数据集上进行对比实验,实验结果表明Epoch-Doubling-SARAH算法具有更快的收敛速度,进而说明了本文算法理论分析的正确性。