Kill a Bird with Two Stones: Closing the Convergence Gaps in Non-Strongly Convex Optimization by Directly Accelerated SVRG with Double Compensation and Snapshots

Recently, some accelerated stochastic variance reduction algorithms such as Katyusha and ASVRG-ADMM achieve faster convergence than nonaccelerated methods such as SVRG and SVRG-ADMM. However, there are still some gaps between the oracle complexities and their lower bounds. To fill in these gaps, this paper proposes a novel Directly Accelerated stochastic Variance reductIon algorithm with two Snapshots (DAVIS) for non-strongly convex (non-SC) unconstrained problems. Our theoretical results show that DAVIS achieves the optimal convergence rate O(1/(nS 2 )) and optimal gradient complexity O(n+ nL/ ), which is identical to its lower bound. To the best of our knowledge, this is the first directly accelerated algorithm that attains the lower bound and improves the convergence rate from O(1/S 2 ) to O(1/(nS 2 )). Moreover, we extend DAVIS and theoretical results to non-SC problems with an equality constraint, and prove that the proposed DAVIS-ADMM algorithm with double snapshots for each variable also attains the optimal convergence rate O(1/(nS)) and optimal oracle complexity O n + L/ for such problems, and it is at least by a factor n/S faster than existing accelerated stochastic algorithms, where n S in general.