Sequential Update Schedules for Stable Optimization

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 129 papers51 conceptsfrozen 2026-10-04

In many large-scale optimization and inference problems, we are faced with a fundamental tension: we want the speed of parallel execution, but we need the stability of sequential logic. When algorithms like Belief Propagation or Approximate Message Passing (AMP) are implemented with parallel (synchronous) updates, they often suffer from "asynchrony noise," infinite oscillations, or outright divergence.

A growing body of research suggests that the solution lies in sequential update schedules. By carefully ordering how information flows through a system—updating variables one by one or in structured "sweeps"—we can guarantee monotonic convergence and numerical stability that parallel systems often lack.

The Problem with Parallelism: Feedback Loops and Oscillations

To understand why sequential updates work, we must first understand why parallel updates fail. In a parallel update scheme, every node in a graph or every variable in a matrix is updated simultaneously based on the state of the system at the previous timestep.

In loopy or highly connected graphs, this creates a "feedback loop" problem. As Gal Elidan, Daphne Koller, and Ian McGraw observe in Residual Belief Propagation, synchronous updates allow contradictory signals to propagate simultaneously. These signals interfere with each other, leading to infinite oscillations where the system never settles into a stable state.

This instability is particularly acute in "messy" real-world data. For example, standard AMP algorithms typically fail when measurement matrices have non-zero means or high correlations. Andre Manoel, Florent Krzakala, and colleagues demonstrate in Sparse Estimation with the Swept Approximated Message-Passing Algorithm that these failures are often artifacts of the parallel update rule itself, rather than the underlying model.

The Sequential Advantage: Monotonicity

Sequential updates—often called "swept" or "asynchronous" updates—solve this by ensuring that each variable update has access to the most recent information from all previously updated variables. This creates a property called monotonicity.

In Convergent tree-reweighted message passing for energy minimization, Vladimir Kolmogorov introduced TRW-S, which uses a sequential update schedule to ensure that a lower bound on the energy function never decreases. By decomposing a graph into monotonic chains and updating them in order, the algorithm avoids the oscillations of parallel tree-reweighted methods. This same principle appears in discrete physics; Yatin Dandi and David Gamarnik show in Sequential Dynamics in Ising Spin Glasses that sequential "Glauber" dynamics prevent the limit cycles found in parallel updates, ensuring a steady trajectory toward local minima.

The intuition is simple: if you adjust one leg of a wobbly table at a time while checking the level, you will eventually stabilize it. If you try to adjust all four legs simultaneously, you are likely to overcorrect and make the wobble worse.

Achieving Serial Equivalence in Parallel Systems

If sequential updates are so much more stable, how do we scale them to modern hardware like GPUs or distributed clusters? The research direction has shifted toward achieving serial equivalence—designing parallel systems that produce the exact same results as a sequential execution.

Several strategies have emerged to bridge this gap:

  1. Conflict-Free Partitioning: Xinghao Pan and Ce Zhang introduced CYCLADES (/work/cyclades-conflict-free-asynchronous-machine-learning), a framework that partitions updates to eliminate memory conflicts. This allows for asynchronous execution speed while maintaining the convergence guarantees of a sequential algorithm.
  2. Informed Scheduling: Instead of updating nodes randomly, algorithms like Residual BP prioritize updates based on which messages are most "unstable" or have the largest residual error. This ensures that the most critical information propagates first, as noted by Elidan et al..
  3. Coloring and Structure: In reservoir simulation and power grid modeling, researchers like Li Zhao and Chen-Song Zhang use graph coloring to identify independent sets of variables that can be updated in parallel without violating the numerical dependencies of a sequential smoother (/work/parallel-multi-stage-preconditioners-with-adaptive-setup).

Why It Works: A Summary

The shift from parallel to sequential (or serially-equivalent) updates works because it enforces a consistent causal dependency within each iteration.

  • Stability: It prevents divergent feedback loops in ill-conditioned problems, such as phase retrieval (/work/robust-phase-retrieval-with-the-swept-approximate-message).
  • Convergence: It allows for mathematical proofs of monotonicity, ensuring that every step of the algorithm moves closer to a global or local optimum (/author/aut-b46332270917411bb6b1ce65a83971ea/aut_b46332270917411bb6b1ce65a83971ea).
  • Efficiency: By avoiding the "noise" of simultaneous contradictory updates, these algorithms often require fewer total iterations to reach a solution, even if each iteration is more structured (/work/research-of-power-flow-parallel-partition-algorithm-applied).

By treating the order of operations as a first-class design constraint, researchers are building optimization tools that are both fast enough for massive datasets and robust enough for real-world noise.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_update_schedules_for_stable_o_c55cc456,
  title = {Sequential Update Schedules for Stable Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-update-schedules-for-stable-optimization/rdr_c55cc456d2504951a8cd1ebcf0b9c457},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sequential_update_schedules_for_stable_o_c55cc456_v1,
  title = {Sequential Update Schedules for Stable Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-update-schedules-for-stable-optimization/rdr_c55cc456d2504951a8cd1ebcf0b9c457/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}