Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
This work provides an incremental improvement in optimization algorithms for machine learning and related fields, offering better theoretical guarantees for handling complex regularizers in large-scale problems.
The authors tackled the problem of optimizing objectives with non-separable, non-smooth regularizers by proposing ASVRCD, an accelerated stochastic variance reduced coordinate descent method that incorporates Nesterov's momentum, achieving improved iteration complexity over existing methods like SEGA and SVRCD and recovering optimal oracle complexity for finite-sum problems.
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.