Randomized Block Coordinate Methods for Large Scale Optimization

This direction is split into other directions: randomized block coordinate descent. Its last version stays readable and citable here.

Version 1 of 1270 papers328 conceptsfrozen 2026-10-04

In modern machine learning and signal processing, we often encounter optimization problems with millions or even billions of variables. In these high-dimensional regimes, traditional gradient descent becomes a victim of its own precision. Computing a full gradient—which requires a pass over every single variable—is not just slow; it is often computationally and memory-prohibitive.

The research direction of Randomized Block-Coordinate Descent (RBCD) and its variants offers a way out. Instead of updating every variable at every step, these methods update only a small, randomly selected "block" of variables. This "lazy" approach drastically reduces the per-iteration cost, allowing algorithms to scale to massive datasets while maintaining rigorous convergence guarantees.

The Intuition of Partial Updates

The core insight behind block-coordinate methods is that we don't need to move in the direction of the steepest descent for the entire function to make progress. By partitioning variables into subsets (blocks), we can perform cheaper, local updates.

Zhaosong Lu and Lin Xiao in On the Complexity Analysis of Randomized Block-Coordinate Descent Methods demonstrate that by selecting these blocks randomly rather than cyclically, we can achieve sharper convergence rates and better high-probability complexity bounds. Randomization prevents the algorithm from getting stuck in "unlucky" update orders that plague deterministic coordinate descent.

This mechanism is particularly effective for problems where the objective function has a block-separable structure or where memory constraints prevent loading all variables into the cache simultaneously. As Zhi-Quan Luo explains in his Unified Algorithmic Framework, we can replace complex global optimization steps with simpler "conservative" upper-bound surrogates for each block, making the subproblems much easier to solve.

Scaling Beyond Simple Minimization

The power of randomized block updates extends beyond simple convex minimization into more complex structures like saddle-point problems and variational inequalities.

For instance, in large-scale games or robust optimization, we often deal with primal-dual frameworks. Zhanxing Zhu and Amos Storkey introduced SP-BCD in Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problems. By updating only a subset of variable blocks per iteration, they transformed heavy batch primal-dual processes into efficient stochastic ones that are naturally parallelizable.

Similarly, Farzad Yousefian and colleagues applied this logic to Stochastic Mirror-prox Algorithms, showing that updating one random block in an extra-gradient framework maintains optimal convergence rates while significantly lowering the computational burden per step.

Overcoming the Step-Size Hurdle

One major challenge in block-coordinate methods is determining the right step size. Standard line searches usually require a full gradient evaluation, which would defeat the purpose of updating only one block.

To solve this, A. Jalilzadeh and N. S. Aybat developed Randomized Primal-Dual Methods with Adaptive Step Sizes. They introduced a backtracking line search that only requires partial gradients of the selected block. This allows the algorithm to adapt to the local geometry of the function without ever needing to look at the full vector of variables.

Acceleration and Structural Constraints

Can we make these "lazy" updates as fast as accelerated gradient methods? Yang Luo shows in Randomized Block-Coordinate Optimistic Gradient Algorithms that by using a specific change of variables, momentum-based acceleration can be integrated into block-coordinate updates. This achieves an $O(1/k^2)$ convergence rate while still only touching a fraction of the variables at each step.

This efficiency is vital for specialized tasks like training Structural SVMs. Simon Lacoste-Julien and Martin Jaggi demonstrated in Block-Coordinate Frank-Wolfe Optimization that updating a single data point's contribution (a block) allows for an "online" speed that outperforms traditional batch solvers on complex structured prediction tasks.

Applications in High-Dimensional Science

The impact of this research direction is visible across diverse fields:

  • Biological Networks: Yijie Wang used stochastic block Frank-Wolfe to align massive species networks 300 times faster than previous methods (SBCFW).
  • Imaging: Antonin Chambolle and Peter Richtárik applied arbitrary sampling to primal-dual algorithms, enabling high-resolution image reconstruction with an order of magnitude fewer passes over the data.
  • Distributed Learning: Yonggang Zhang and Bicheng Ying showed that networked agents can learn effectively even when they only communicate random subsets of their gradient coordinates, reducing communication overhead in decentralized systems.

By breaking down massive problems into manageable, randomized pieces, these methods provide the mathematical foundation for optimization in the age of big data.

Papers in this version

Showing 60 of 270 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_block_coordinate_methods_for__d1e758b0,
  title = {Randomized Block Coordinate Methods for Large Scale Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-block-coordinate-methods-for-large-scale-optimization/rdr_d1e758b0841441409d3073184c92790e},
  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_methods_for__d1e758b0_v1,
  title = {Randomized Block Coordinate Methods for Large Scale Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-block-coordinate-methods-for-large-scale-optimization/rdr_d1e758b0841441409d3073184c92790e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}