  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.
