# On the Complexity Analysis of Randomized Block-Coordinate Descent Methods

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2013.

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

- [BAdam: A Memory Efficient Full Parameter Optimization Method for Large Language Models](https://mlsanity.com/paper/2404.02827/) (2024)
- [Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training](https://mlsanity.com/paper/2201.01965/) (2022)
- [MoFO: Momentum-Filtered Optimizer for Mitigating Forgetting in LLM Fine-Tuning](https://mlsanity.com/paper/2407.20999/) (2024)
- [Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference](https://mlsanity.com/paper/2409.17401/) (2024)
- [Block Policy Mirror Descent](https://mlsanity.com/paper/2201.05756/) (2022)
- [Convergence rate of random scan Coordinate Ascent Variational Inference under log-concavity](https://mlsanity.com/paper/2406.07292/) (2024)
- [SGD with Coordinate Sampling: Theory and Practice](https://mlsanity.com/paper/2105.11818/) (2021)
- [Stability and Generalization for Randomized Coordinate Descent](https://mlsanity.com/paper/2108.07414/) (2021)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2109.04228/) (2021)
- [Coordinate Descent Methods for Fractional Minimization](https://mlsanity.com/paper/2201.12691/) (2022)
- [Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updating](https://mlsanity.com/paper/2303.16241/) (2023)
- [DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regime](https://mlsanity.com/paper/2305.10294/) (2023)
- [Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization](https://mlsanity.com/paper/2206.14981/) (2022)
- [Decentralized Entropic Optimal Transport for Distributed Distribution Comparison](https://mlsanity.com/paper/2301.12065/) (2023)
- [Convergence of Batch Updating Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Results](https://mlsanity.com/paper/2209.05372/) (2022)
- [MARL-LNS: Cooperative Multi-agent Reinforcement Learning via Large Neighborhoods Search](https://mlsanity.com/paper/2404.03101/) (2024)
- [Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning](https://mlsanity.com/paper/2503.01530/) (2025)
- [Randomized Subspace Nesterov Accelerated Gradient](https://mlsanity.com/paper/2605.00740/) (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)
- [DECA: Decentralizing Block-Wise Adam for Efficient LLM Full-Parameter Fine-Tuning on Non-IID Data](https://mlsanity.com/paper/2606.03209/) (2026)

## Abstract (arXiv)

In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in [8,11] for minimizing the sum of a smooth convex function and a block-separable convex function. In particular, we extend Nesterov's technique developed in [8] for analyzing the RBCD method for minimizing a smooth convex function over a block-separable closed convex set to the aforementioned more general problem and obtain a sharper expected-value type of convergence rate than the one implied in [11]. Also, we obtain a better high-probability type of iteration complexity, which improves upon the one in [11] by at least the amount O(n/ε), where ε is the target solution accuracy and n is the number of problem blocks. In addition, for unconstrained smooth convex minimization, we develop a new technique called it randomized estimate sequence to analyze the accelerated RBCD method proposed by Nesterov [11] and establish a sharper expected-value type of convergence rate than the one given in [11].