【作者】 吴涛；

【导师】 张超；

【作者基本信息】 北京交通大学 ， 运筹学与控制论， 2021， 硕士

【摘要】 本篇文章我们首次提出了带有Katyusha动量的SPIDER算法(Prox SPIDERK),并将其应用到求解非凸非光滑优化问题当中,继而给出算法的收敛性和复杂度分析。我们知道,2018年新提出的SPIDER算法在非凸优化中已证明具有近似最优的计算复杂度(Oracle复杂度),但我们知道SPIDER算法的的理论优势并没有导致其实际性能比其他随机算法(如SVRG,SARAH)有较大的提高。为了解决这一问题,动量技术成为我们提高SPIDER算法性能的一个不错选择。2019年带有Nesterov动量的SPIDER-M算法被提出,然而,传统的Nesterov动量方案在方差缩减类算法中的应用是专门为确定性优化问题和非随机类算法而设计的,不适用于随机场景,所以我们在本文中引入了Katyusha动量来解决这个问题。结果表明,我们的算法在满足广义一阶平稳条件下,同样达到了最优的计算复杂度。而通过大量的数值实验对比,也验证了我们算法所具有的理论优势,实现了所预期的理论结果。更多还原

【Abstract】 In this paper,we propose a SPIDER algorithm with Katyusha momentum for the first time(Prox SPIDER-K),and apply it to solving non-convex and non-smooth optimization problems.Then,we give the convergence and complexity analysis of the algorithm.We know that the newly proposed SPIDER in 2018 has been shown to achieve a near-optimal complexity(Oracle complexity)for nonconvex optimization,but the theoretical advantage of SPIDER does not lead to substantial improvement of practical performance over other stochastic algorithms(such as SVRG,SARAH).To address this issue,momentum technique can be a good candidate to improve the performance of SPIDER.In 2019,the SPIDER-M algorithm with Nesterov momentum was proposed.However,Traditional Nesterov momentum schemes used in variancereduced algorithms are designed specifically for deterministic optimization problems and non-random algorithms,and are not applicable to stochastic scenarios.So we first use Katyusha to fix this issue.Katyusha momentum is applied to nonconvex stochastic setting for the first time.And we show that the resulting algorithms achieve the optimal complexity for obtaining a point that satisfying a generalized first-order stationary condition.From our extensive experiments,we also demonstrate the superior performance of our Prox SPIDER-K method compared to the other stochastic variance-reduced algorithms.更多还原