Random Permutations in Block Coordinate Optimization

This direction is merged into another direction: random reshuffling. Its last version stays readable and citable here.

Version 1 of 110 papers17 conceptsfrozen 2026-10-04

In large-scale optimization, we often solve complex problems by breaking them into smaller, manageable "blocks" of variables. Two of the most popular frameworks for this are Coordinate Descent (CD) and the Alternating Direction Method of Multipliers (ADMM).

Traditionally, these algorithms update blocks in a fixed, cyclic order (1, 2, ..., $n$). While simple, this deterministic approach has a hidden weakness: it can be incredibly slow or, in the case of multi-block ADMM, it can even diverge. To fix this, researchers have turned to a simple but powerful trick: randomly permuting the update order at the start of every epoch.

The Problem with Fixed Orders

To understand why shuffling helps, we first need to see why fixed orders fail. In Analyzing random permutations for cyclic coordinate descent, Stephen Wright and Ching-pei Lee describe "difficult" problems where the objective function forms a narrow, steep-sided "trench."

A fixed cyclic order can get caught in a zig-zag pattern that crawls painfully slowly along the bottom of this trench. Even worse, Zhi‐Quan Luo and Yinyu Ye show in On the Expected Convergence of Randomly Permuted ADMM that for ADMM with more than two blocks, a fixed update order can actually create structural instabilities that cause the algorithm to fly off to infinity.

Shuffling as a Stabilizer

The core idea of this research direction is to replace the fixed cycle with a random permutation. Instead of updating blocks in the order $(1, 2, 3)$, you might update them as $(2, 1, 3)$ in the first pass, and $(3, 1, 2)$ in the second.

This mechanism provides a "symmetrization" effect. As Luo and Ye demonstrate in On the Efficiency of Random Permutation for ADMM and Coordinate Descent, shuffling the blocks ensures that the cumulative update remains stable in expectation. By breaking the rigid sequence, you prevent the algorithm from reinforcing the specific directional biases that lead to divergence.

Why Permutations Beat Pure Randomness

You might wonder: why not just pick a random block to update at every single step (sampling with replacement)?

The answer lies in staleness. In Randomness and permutations in coordinate descent methods, Mert Gurbuzbalaban, Asuman E. Ozdaglar, and their colleagues explain that sampling with replacement is "wasteful." In a single pass of $n$ steps, pure random sampling will likely update some blocks multiple times while leaving others completely untouched.

Random permutation (sampling without replacement) ensures that every single coordinate is refreshed exactly once per epoch. This "shuffled index scheduling" ensures that no part of the model becomes too stale, leading to faster empirical convergence. This efficiency is put to practical use in algorithms like BC-RED, where Yu Sun and Ulugbek S. Kamilov use shuffled epochs to process massive image datasets block-by-block in Block Coordinate Regularization by Denoising.

Guaranteed Convergence

Beyond speed, permutations provide a theoretical safety net. For complex problems like Symmetric Nonnegative Matrix Factorization (SNMF), which involves difficult fourth-degree objective functions, Haoran Sun and Meisam Razaviyayn show in Inexact Block Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization that permutation-based selection guarantees monotonic convergence to a stationary set.

By combining the implementation simplicity of cyclic updates with the robust theory of stochastic methods, random permutations have become a fundamental tool for making multi-block optimization both stable and fast.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_random_permutations_in_block_coordinate__9298912d,
  title = {Random Permutations in Block Coordinate Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-permutations-in-block-coordinate-optimization/rdr_9298912dda7649599509b62dc413c930},
  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_random_permutations_in_block_coordinate__9298912d_v1,
  title = {Random Permutations in Block Coordinate Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-permutations-in-block-coordinate-optimization/rdr_9298912dda7649599509b62dc413c930/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}