# Cyclic Coordinate Dual Averaging with Extrapolation arXiv: https://arxiv.org/abs/2102.13244 · HTML: https://mlsanity.com/paper/2102.13244/ ## Key facts - Cited by 3 papers in the map (data through 14 Oct 2026). - Builds on 36 of its 64 references that are in the map. - First posted on arXiv 26 Feb 2021. ## Builds on (most cited first, 30 of 36) - [Improved Techniques for Training GANs](https://mlsanity.com/paper/1606.03498/) (2016) - [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015) - [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018) - [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018) - [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021) - [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015) - [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018) - [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019) - [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014) - [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017) - [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017) - [An Asynchronous Parallel Stochastic Coordinate Descent Algorithm](https://mlsanity.com/paper/1311.1873/) (2013) - [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013) - [Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling](https://mlsanity.com/paper/1512.09103/) (2015) - [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020) - [On the Convergence Rate of Incremental Aggregated Gradient Algorithms](https://mlsanity.com/paper/1506.02081/) (2015) - [Iteration Complexity Analysis of Block Coordinate Descent Methods](https://mlsanity.com/paper/1310.6957/) (2013) - [A Primer on Coordinate Descent Algorithms](https://mlsanity.com/paper/1610.00040/) (2016) - [Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Rate](https://mlsanity.com/paper/1611.00347/) (2016) - [A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization](https://mlsanity.com/paper/1706.02882/) (2017) - [A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions](https://mlsanity.com/paper/1508.04625/) (2015) - [Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches](https://mlsanity.com/paper/1809.09354/) (2018) - [Random extrapolation for primal-dual coordinate descent](https://mlsanity.com/paper/2007.06528/) (2020) - [A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/1803.01401/) (2018) - [Linear Convergence of Cyclic SAGA](https://mlsanity.com/paper/1810.11167/) (2018) - [Alternating Randomized Block Coordinate Descent](https://mlsanity.com/paper/1805.09185/) (2018) - [Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization](https://mlsanity.com/paper/1711.03439/) (2017) - [Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity](https://mlsanity.com/paper/1811.01182/) (2018) - [Worst-case Complexity of Cyclic Coordinate Descent: O(n2) Gap with Randomized Version](https://mlsanity.com/paper/1604.07130/) (2016) - [Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications](https://mlsanity.com/paper/1611.02456/) (2016) ## Built on by (most cited first, 3 of 3) - [Last Iterate Convergence of Incremental Methods and Applications in Continual Learning](https://mlsanity.com/paper/2403.06873/) (2024) - [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023) - [Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities](https://mlsanity.com/paper/2603.29128/) (2026) ## Abstract (arXiv) Cyclic block coordinate methods are a fundamental class of optimization methods widely used in practice and implemented as part of standard software packages for statistical learning. Nevertheless, their convergence is generally not well understood and so far their good practical performance has not been explained by existing convergence analyses. In this work, we introduce a new block coordinate method that applies to the general class of variational inequality (VI) problems with monotone operators. This class includes composite convex optimization problems and convex-concave min-max optimization problems as special cases and has not been addressed by the existing work. The resulting convergence bounds match the optimal convergence bounds of full gradient methods, but are provided in terms of a novel gradient Lipschitz condition w.r.t.~a Mahalanobis norm. For m coordinate blocks, the resulting gradient Lipschitz constant in our bounds is never larger than a factor √m compared to the traditional Euclidean Lipschitz constant, while it is possible for it to be much smaller. Further, for the case when the operator in the VI has finite-sum structure, we propose a variance reduced variant of our method which further decreases the per-iteration cost and has better convergence rates in certain regimes. To obtain these results, we use a gradient extrapolation strategy that allows us to view a cyclic collection of block coordinate-wise gradients as one implicit gradient.