Accelerated proximal stochastic variance reduction for DC optimization

In this article, we study an important class of stochastic difference-of-convex (SDC) programming whose objective is given in the form of the sum of a continuously differentiable convex function, a simple convex function and a continuous concave function. Recently, a proximal stochastic variance reduction difference-of-convex algorithm (Prox-SVRDCA) (Xu et al., 2019) is developed for this problem. And, Prox-SVRDCA reduces to the proximal stochastic variance reduction gradient (Prox-SVRG) (Xiao and Zhang, 2014) as the continuous concave function is disappeared, and hence Prox-SVRDCA is potentially slow in practice. Inspired by recently proposed acceleration techniques, an accelerated proximal stochastic variance reduction difference-of-convex algorithm (AProx-SVRDCA) is proposed. Different from Prox-SVRDCA, an extrapolation acceleration step that involves the latest two iteration points is incorporated in AProx-SVRDCA. The experimental results show that, for a fairly general choice of the extrapolation parameter, the acceleration will be achieved for AProx-SVRDCA. Then, a rigorous theoretical analysis is presented. We first show that any accumulation point of the generated iteration sequences is a stationary point of the objective function. Furthermore, different from the traditional convergence analysis in the existing nonconvex stochastic optimizations, a global convergence property with respect to the generated sequences is established under the assumption: the Kurdyka-Łojasiewicz property together with the continuity and differentiability of the concave part in objective function. To the best of our knowledge, this is the first time that the acceleration trick is incorporated into nonconvex nonsmooth SDC programming. Finally, extended experimental results show the superiority of our proposed algorithm.