Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
arXiv:2002.04670
Abstract
We propose an accelerated version of stochastic variance reduced coordinate descent -- ASVRCD. As other variance reduced coordinate descent methods such as SEGA or SVRCD, our method can deal with problems that include a non-separable and non-smooth regularizer, while accessing a random block of partial derivatives in each iteration only. However, ASVRCD incorporates Nesterov's momentum, which offers favorable iteration complexity guarantees over both SEGA and SVRCD. As a by-product of our theory, we show that a variant of Allen-Zhu (2017) is a specific case of ASVRCD, recovering the optimal oracle complexity for the finite sum objective.
30 pages, 8 figures
References in corpus (9)
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- A Universal Catalyst for First-Order Optimization
- Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- Direct Acceleration of SAGA using Sampled Negative Momentum
- ASVRG: Accelerated Proximal SVRG
- L-SVRG and L-Katyusha with Arbitrary Sampling
- One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
- Stochastic Subspace Descent