Randomized Block Coordinate Descent for High Dimensional Optimization

58 concepts55 papers2 proposals

When optimizing modern machine learning models with millions or billions of parameters, computing a full gradient vector at every step becomes a massive computational bottleneck. Traditional gradient descent updates every single parameter simultaneously. As the dimensionality $d$ grows, the cost of this full-vector update scales linearly $O(d)$, or even quadratically $O(d^2)$ if second-order curvature information is used.

Randomized block coordinate descent bypasses this bottleneck by breaking a massive optimization problem down into a sequence of smaller, cheaper subproblems. Instead of updating the entire parameter vector at once, the algorithm selects a random subset—a "block"—of coordinates to update at each iteration, drastically reducing per-iteration computational and memory overhead.

Why Randomization Beats Fixed Cycles

Early coordinate descent methods often updated variables in a fixed, deterministic sequence (e.g., updating block 1, then block 2, and so on). However, as surveyed by Stephen Wright in Coordinate Descent Algorithms, cyclic updates can easily get trapped in inefficient, repetitive patterns or exhibit poor worst-case performance on poorly conditioned landscapes.

Randomization fundamentally changes this dynamic. By picking a block uniformly at random in each step, the algorithm ensures that every direction is explored fairly in expectation. This stochastic selection smooths out pathological geometric traps, simplifies convergence analysis, and guarantees that the algorithm avoids worst-case cyclic stalling.

Decoupling Costs via Dual and Primal-Dual Updates

Many machine learning problems, such as regularized empirical risk minimization or saddle-point problems, involve balancing primal variables (like model weights) and dual variables (like sample-specific constraints). Updating the entire set of high-dimensional dual variables at every step is prohibitively expensive when the number of training samples is vast.

The block-coordinate philosophy elegantly resolves this. Yuchen Zhang et al. demonstrated in Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization that performing stochastic updates on a randomly selected subset of dual variables allows the per-iteration complexity to scale with the feature dimension rather than the total number of samples.

Furthermore, randomizing the step choices can unlock unexpected mathematical advantages. Ahmet Alacaoglu et al. showed in Random extrapolation for primal-dual coordinate descent that randomizing the extrapolation step in primal-dual algorithms decouples the iteration cost from step-size constraints. This allows coordinate-based updates to utilize the large step sizes typically reserved for full-update methods, maximizing progress per step without increasing the computational burden. For complex objectives like partial AUC maximization, Linli Zhou et al. showed in Stochastic Primal-Dual Double Block-Coordinate for Two- way Partial AUC Maximization that a double block-coordinate update mechanism—updating a mini-batch of both primal and dual variables simultaneously—bypasses the need to maintain high-dimensional auxiliary vectors entirely, yielding massive training speedups.

Doubly Stochastic Optimization: Rows and Columns

When datasets suffer from the "double whammy" of big data—massive sample sizes ($n$) and ultra-high dimensionality ($d$)—standard stochastic gradient descent (which samples data rows) or standard coordinate descent (which samples feature columns) only solve half the problem.

"Doubly stochastic" methods solve both simultaneously by integrating data sampling with coordinate sampling. As shown by Zebang Shen et al. in Accelerated Doubly Stochastic Gradient Algorithm for Large-scale Empirical Risk Minimization, sampling both data points and feature blocks at each step addresses both bottlenecks at once, touching only a tiny fraction of the data matrix per iteration. To scale this further, Aryan Mokhtari et al. leveraged this dual-randomization strategy in A Class of Parallel Doubly Stochastic Algorithms for Large-Scale Learning to enable asynchronous parallel updates across multiple workers, eliminating the synchronization bottlenecks that typically plague distributed systems.

Extending to Constrained and Higher-Order Settings

The block-coordinate framework is highly versatile and extends well beyond basic gradient descent into constrained optimization and second-order methods:

  • Constrained Optimization: When computing a projection back onto a feasible region is too expensive, projection-free methods like the Frank-Wolfe algorithm are used. Simon Lacoste-Julien et al. introduced this to block updates in Block-Coordinate Frank-Wolfe Optimization for Structural SVMs. By updating only a single data point or variable subset per iteration, the algorithm solves much smaller, localized linear subproblems, combining the low cost of online methods with the strict convergence guarantees of batch optimization.
  • Second-Order Optimization: Second-order methods achieve rapid convergence by utilizing the Hessian matrix, but computing and inverting a full $d \times d$ Hessian scales quadratically or cubically with dimension. In Randomized Block Cubic Newton Method, Nikita Doikov et al. showed that by partitioning variables into blocks and computing second-order derivatives only within a randomly selected block, one can drastically lower the per-step cost of cubic regularization while preserving its fast second-order convergence rates.

Ultimately, randomized block coordinate descent works because it aligns the computational effort of an optimization step with the structure of the data. By trading a single, prohibitively expensive global update for a series of cheap, mathematically sound local updates, it makes high-dimensional optimization practical.

Key Foundational Work

On the Complexity Analysis of Randomized Block-Coordinate Descent Methods (2013) — contributed 1 concept elements to this direction.
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2013) — contributed 1 concept elements to this direction.
A Randomized Mirror Descent Algorithm for Large Scale Multiple Kernel Learning. (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_block_coordinate_descent_1d9434fc,
  title = {randomized block coordinate descent},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-block-coordinate-descent/rdr_1d9434fc3b114eaca48ae7de305a5822},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_randomized_block_coordinate_descent_1d9434fc_v1,
  title = {randomized block coordinate descent},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-block-coordinate-descent/rdr_1d9434fc3b114eaca48ae7de305a5822/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake