Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization
This addresses scalability issues in optimization for practitioners, though it is incremental as it builds on prior cyclic and extrapolation methods.
The paper tackles the theoretical gap in cyclic coordinate methods for composite convex optimization by proposing A-CODER, which achieves optimal convergence rates with improved block dependence, and introduces a variance-reduced variant, VR-A-CODER, with state-of-the-art complexity guarantees.
Exploiting partial first-order information in a cyclic way is arguably the most natural strategy to obtain scalable first-order methods. However, despite their wide use in practice, cyclic schemes are far less understood from a theoretical perspective than their randomized counterparts. Motivated by a recent success in analyzing an extrapolated cyclic scheme for generalized variational inequalities, we propose an Accelerated Cyclic Coordinate Dual Averaging with Extrapolation (A-CODER) method for composite convex optimization, where the objective function can be expressed as the sum of a smooth convex function accessible via a gradient oracle and a convex, possibly nonsmooth, function accessible via a proximal oracle. We show that A-CODER attains the optimal convergence rate with improved dependence on the number of blocks compared to prior work. Furthermore, for the setting where the smooth component of the objective function is expressible in a finite sum form, we introduce a variance-reduced variant of A-CODER, VR-A-CODER, with state-of-the-art complexity guarantees. Finally, we demonstrate the effectiveness of our algorithms through numerical experiments.