# Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization

arXiv: https://arxiv.org/abs/2303.16279 · HTML: https://mlsanity.com/paper/2303.16279/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 43 references that are in the map.
- First posted on arXiv 28 Mar 2023.

## Builds on (most cited first, 27 of 27)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [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)
- [Block stochastic gradient iteration for convex and nonconvex optimization](https://mlsanity.com/paper/1408.2597/) (2014)
- [On Acceleration with Noise-Corrupted Gradients](https://mlsanity.com/paper/1805.12591/) (2018)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [Random extrapolation for primal-dual coordinate descent](https://mlsanity.com/paper/2007.06528/) (2020)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [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)
- [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)
- [Random Permutations Fix a Worst Case for Cyclic Coordinate Descent](https://mlsanity.com/paper/1607.08320/) (2016)
- [Analyzing Random Permutations for Cyclic Coordinate Descent](https://mlsanity.com/paper/1706.00908/) (2017)
- [Asynchronous Variance-reduced Block Schemes for Composite Nonconvex Stochastic Optimization: Block-specific Steplengths and Adapted Batch-sizes](https://mlsanity.com/paper/1808.02543/) (2018)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)

## 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)
- [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023)
- [Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities](https://mlsanity.com/paper/2603.29128/) (2026)

## Abstract (arXiv)

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.