# Inexact Coordinate Descent: Complexity and Preconditioning

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

## Key facts

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

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

- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Stronger NAS with Weaker Predictors](https://mlsanity.com/paper/2102.10490/) (2021)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent](https://mlsanity.com/paper/2207.01560/) (2022)
- [A dual approach for federated learning](https://mlsanity.com/paper/2201.11183/) (2022)
- [An Inexact Weighted Proximal Trust-Region Method](https://mlsanity.com/paper/2601.09024/) (2026)

## Abstract (arXiv)

In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. In his work we relax this requirement, and allow for the subproblem to be solved inexactly, leading to an inexact block coordinate descent method. Our approach incorporates the best known results for exact updates as a special case. Moreover, these theoretical guarantees are complemented by practical considerations: the use of iterative techniques to determine the update as well as the use of preconditioning for further acceleration.