ProxSPIDER-K Algorithm For Nonconvex Composite Optimization

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.