# Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 71 references that are in the map.
- First posted on arXiv 9 Dec 2022.

## Builds on (most cited first, 30 of 40)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [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)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [A globally convergent algorithm for nonconvex optimization based on block coordinate update](https://mlsanity.com/paper/1410.1386/) (2014)
- [Splitting methods with variable metric for KL functions](https://mlsanity.com/paper/1405.1357/) (2014)
- [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)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [Iteration Complexity Analysis of Block Coordinate Descent Methods](https://mlsanity.com/paper/1310.6957/) (2013)
- [Block-Randomized Stochastic Proximal Gradient for Low-Rank Tensor Factorization](https://mlsanity.com/paper/1901.05529/) (2019)
- [Finding Local Minima via Stochastic Nested Variance Reduction](https://mlsanity.com/paper/1806.08782/) (2018)
- [Alternating Randomized Block Coordinate Descent](https://mlsanity.com/paper/1805.09185/) (2018)
- [Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1509.01404/) (2015)
- [Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization](https://mlsanity.com/paper/1711.03439/) (2017)

## Built on by (most cited first, 9 of 9)

- [BAdam: A Memory Efficient Full Parameter Optimization Method for Large Language Models](https://mlsanity.com/paper/2404.02827/) (2024)
- [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)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [Unifying Temporal and Structural Credit Assignment in LLM-Based Multi-Agent Prompt Optimization](https://mlsanity.com/paper/2605.30227/) (2026)
- [Exploiting Block Coordinate Descent for Cost-Effective LLM Model Training](https://mlsanity.com/paper/2506.12037/) (2025)
- [Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities](https://mlsanity.com/paper/2603.29128/) (2026)
- [Turning Stale Gradients into Stable Gradients: Coherent Coordinate Descent with Implicit Landscape Smoothing for Lightweight Zeroth-Order Optimization](https://mlsanity.com/paper/2605.14373/) (2026)
- [Adaptive Gradient-Based Methods for a Broader Class of Optimization Problems under Performative Prediction](https://mlsanity.com/paper/2607.26562/) (2026)

## Abstract (arXiv)

Nonconvex optimization is central in solving many machine learning problems, in which block-wise structure is commonly encountered. In this work, we propose cyclic block coordinate methods for nonconvex optimization problems with non-asymptotic gradient norm guarantees. Our convergence analysis is based on a gradient Lipschitz condition with respect to a Mahalanobis norm, inspired by a recent progress on cyclic block coordinate methods. In deterministic settings, our convergence guarantee matches the guarantee of (full-gradient) gradient descent, but with the gradient Lipschitz constant being defined w.r.t.~a Mahalanobis norm. In stochastic settings, we use recursive variance reduction to decrease the per-iteration cost and match the arithmetic operation complexity of current optimal stochastic full-gradient methods, with a unified analysis for both finite-sum and infinite-sum cases. We prove a faster linear convergence result when a Polyak-Lojasiewicz (PL) condition holds. To our knowledge, this work is the first to provide non-asymptotic convergence guarantees -- variance-reduced or not -- for a cyclic block coordinate method in general composite (smooth + nonsmooth) nonconvex settings. Our experimental results demonstrate the efficacy of the proposed cyclic scheme in training deep neural nets.