Deterministic Cyclic Schedules in Iterative Optimization

20 concepts15 papers1 proposal

In machine learning and large-scale optimization, randomization is often treated as a default necessity. Algorithms like Stochastic Gradient Descent (SGD) and Randomized Coordinate Descent (RCD) rely on random sampling to escape adversarial worst-case paths and simplify theoretical analysis.

However, a compelling body of research turns this conventional wisdom on its head. By updating variables or data points in a fixed, deterministic cyclic order, algorithms can achieve faster convergence, smoother trajectories, and more stable performance than their randomized counterparts. Deterministic cyclic scheduling works not by avoiding structure, but by directly exploiting it.

Bounding the Age of Information

In incremental optimization methods, the algorithm updates a global model by processing one component function or data sample at a time. Because computing the full gradient or Hessian across millions of samples is too expensive, these methods typically maintain an aggregate memory of past gradients or Hessians.

When samples are selected uniformly at random, some components are inevitably neglected for many iterations while others are sampled repeatedly. This uneven sampling causes the "stale" information in memory to age unpredictably, introducing high stochastic variance.

Random Sampling:  [Sample 2] -> [Sample 2] -> [Sample 1] -> [Sample 5] (Sample 3 and 4 are neglected)
Cyclic Schedule:  [Sample 1] -> [Sample 2] -> [Sample 3] -> [Sample 4] (Every sample refreshed predictably)

A deterministic cyclic schedule solves this by guaranteeing that every single component function is visited exactly once per epoch. This predictable refresh rate places a strict upper bound on the age of the stored information.

Mokhtari et al. leverage this exact mechanism in their Incremental Quasi-Newton (IQN) framework. Because the age of the Hessian information is deterministically bounded, the authors prove that IQN achieves a local superlinear convergence rate—a speed previously thought unattainable for incremental methods without expensive full-batch computations. In a follow-up work, Mokhtari et al. demonstrate that this cyclic routine allows the algorithm to bound current optimization errors directly based on the errors of a fixed number of preceding steps.

This principle extends to first-order methods as well. Mokhtari et al. introduce the Double Incremental Aggregated Gradient (DIAG) method, showing that a cyclic data pass allows the algorithm to achieve a linear convergence rate that provably surpasses the worst-case bounds of standard gradient descent. Similarly, in the context of second-order incremental methods, Rodomanov et al. show that a fixed cyclic order ensures every sample's contribution to the aggregate Hessian and gradient is refreshed regularly, outperforming uniform random sampling.

Aligning with Landscape Structure

In coordinate descent methods, the optimization problem is broken down by updating one variable (or block of variables) at a time. Randomized coordinate descent chooses the next variable blindly, which averages out bad interactions but ignores the underlying geometry of the problem.

When the optimization landscape possesses structural coupling—such as diagonal dominance or network dependencies—a deterministic sequence can navigate the landscape much more efficiently.

Gurbuzbalaban et al. demonstrate that for quadratic problems involving M-matrices or 2-cyclic matrices (which frequently appear in graph-based learning and Gaussian Markov Random Fields), Cyclic Coordinate Descent (CCD) is asymptotically faster than randomized descent by a factor of two or more. By sweeping through the coordinates sequentially, the algorithm directly exploits the combinatorial properties of the Hessian matrix.

The specific choice of this deterministic sequence is critical. Gurbuzbalaban et al. prove that in well-conditioned, highly diagonally dominant landscapes, a fixed cyclic update order consistently outperforms both random sampling and random permutations.

To capitalize on this, researchers design optimal scanning sequences offline:

  • Mitliagkas et al. introduce an offline coordinate descent procedure that minimizes a theoretical variation bound to discover the most efficient variable scan order before sampling even begins.
  • In signal processing for massive MIMO systems, Yongming Huang demonstrates that sorting the execution order of iterative block updates based on the descending Frobenius norm of the channel matrix blocks maximizes error reduction per iteration, entirely eliminating random-sampling overhead.

Trajectory Regularity and Extrapolation

Randomized algorithms produce jagged, stochastic optimization paths because each random choice introduces a localized shock to the parameters. While this randomness can help jump out of local minima, it destroys the predictability of the optimization trajectory.

In contrast, deterministic cyclic updates generate a highly regular, smooth path of iterates. This geometric regularity is a powerful asset because a predictable trajectory can be mathematically extrapolated to leap ahead toward the optimum.

Iterate Trajectory:
Randomized:  (x0) -> ↗ -> ↘ -> ↗ -> ↘ -> (Stochastic jitter, hard to predict)
Cyclic:      (x0) ───> (x1) ───> (x2) ───> [Extrapolated Jump] ───> (Optimum)

Massias et al. exploit this phenomenon to build Celer, a state-of-the-art Lasso solver. Because cyclic coordinate descent produces a smooth and predictable path, the authors can apply dual extrapolation—using the history of previous cycles to predict the ultimate dual solution. This high-quality estimation allows the algorithm to aggressively prune irrelevant features early in the computation, yielding massive practical speedups over randomized solvers.

Stable Guarantees and Broader Domains

A key limitation of randomized scheduling is that its guarantees are statistical: they hold in expectation or with high probability. A user running an algorithm once might happen to draw a poor sequence of random samples. Deterministic cyclic processing provides stable, reliable convergence trajectories for every single execution.

Afrooz Jalilzadeh demonstrates this stability by developing the Primal-Dual Incremental Gradient (PDIG) method for nonsmooth, constrained convex optimization. By iterating through constraints and data components in a strict cyclic order, the algorithm guarantees stable convergence trajectories for both suboptimality and infeasibility on every run.

Similarly, Beck et al. prove that deterministic cyclic block updates in conditional gradient (Frank-Wolfe) methods achieve a global sublinear convergence rate of $O(1/k)$, offering a structured alternative that is simpler to implement in hardware than randomized block selection. Even in complex nonconvex settings, Cai et al. show that combining cyclic block coordinate descent with variance reduction matches the theoretical convergence rates of randomized methods while maintaining superior implementation efficiency.

This deterministic paradigm is expanding across diverse computational domains:

  • Discrete Sampling: Fixed-order variable scanning can occasionally encounter structural traps in discrete spaces. Fischer et al. resolve this for the Metropolis algorithm on binary distributions by showing that a tiny modification—setting the acceptance probability of equally likely states to exactly 50%—mathematically guarantees convergence for fixed-order updates.
  • Hardware Acceleration: Burns et al. utilize cyclic block selection to coordinate updates across partitioned variable sets in hybrid analog-digital systems, integrating digital control logic cleanly with analog dynamical cores.
  • Non-Euclidean Spaces: Absil et al. demonstrate that strategically re-ordering data points based on computation history accelerates the iterative calculation of multi-variable means on Riemannian manifolds, breaking the local bottlenecks that slow down standard cyclic or random approaches.

By replacing blind randomness with structured, predictable sequences, deterministic cyclic scheduling transforms optimization from a game of chance into a well-orchestrated, highly efficient traversal of the problem landscape.

Key Foundational Work

A Superlinearly-Convergent Proximal Newton-type Method for the Optimization of Finite Sums (2016) — contributed 2 concept elements to this direction.
The Cyclic Block Conditional Gradient Method for Convex Optimization Problems (2015) — contributed 2 concept elements to this direction.
Extending a two-variable mean to a multi-variable mean (2016) — 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_deterministic_cyclic_scheduling_bc48cac1,
  title = {deterministic cyclic scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/deterministic-cyclic-scheduling/rdr_bc48cac13efa410c92547078dfb8472d},
  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_deterministic_cyclic_scheduling_bc48cac1_v1,
  title = {deterministic cyclic scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/deterministic-cyclic-scheduling/rdr_bc48cac13efa410c92547078dfb8472d/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