  We propose the \emph{Cyclic cOordinate Dual avEraging with extRapolation
(CODER)} method for generalized variational inequality problems. Such problems
are fairly general and include composite convex minimization and min-max
optimization as special cases. CODER is the first cyclic block coordinate
method whose convergence rate is independent of the number of blocks, which
fills the significant gap between cyclic coordinate methods and randomized ones
that remained open for many years. Moreover, CODER provides the first
theoretical guarantee for cyclic coordinate methods for solving generalized
variational inequality problems under only monotonicity and Lipschitz
continuity assumptions. To remove the dependence on the number of blocks, the
analysis of CODER is based on a novel Lipschitz condition with respect to a
Mahalanobis norm rather than the commonly used coordinate-wise Lipschitz
condition; to be applicable to general variational inequalities, CODER
leverages an extrapolation strategy inspired by the recent developments in
primal-dual methods. Our theoretical results are complemented by numerical
experiments, which demonstrate competitive performance of CODER compared to
other coordinate methods.
