Delay-Aware Power-Law Memory for Asynchronous Optimization

Momentum speeds up gradient descent by adding a running average of past gradients to each step. That running average decays exponentially, and it becomes a liability when workers are asynchronous. In an asynchronous cluster, gradients arrive late, computed on parameters the model has since left behind. Exponential momentum amplifies each stale gradient and pushes the parameters further from where the gradient was measured. The known result is harsh: in asynchronous momentum SGD the tolerable delay shrinks like $(1-\mu)^2$ in the momentum coefficient $\mu$, so practitioners turn momentum down exactly when they have more workers (Towards Understanding Acceleration Tradeoff between Momentum and Asynchrony in Nonconvex Stochastic Optimization). A different kind of memory, one whose weights on past gradients fall off as a power of the lag rather than exponentially, has been shown to speed up synchronous distributed optimization on ill-conditioned problems. That approach is fractional-order memory, borrowed from fractional calculus, where derivatives depend on the whole past trajectory. Its cost is a stored buffer of every past gradient, and it has never been run with delays (Fractional Order Distributed Optimization).

This note proposes a concrete construction and a falsifiable claim. The construction approximates the power-law memory by a small bank of exponential buffers whose decay rates are spread geometrically across timescales. Each late gradient is inserted into every buffer as if it had arrived on time, discounted by exactly the decay it missed. Memory and compute then scale with the number of buffers, roughly logarithmic in the horizon, instead of with the history length. Arrival order also stops mattering. The claim is that under this delay-exact insertion, delay tolerance is governed by how much memory weight sits at lags shorter than the delay, not by the total gain of the memory. A power-law kernel keeps most of its weight in slow buffers, and slow buffers barely care about staleness. So it should keep long-range acceleration at delay levels where exponential momentum must be turned down.

Core Claim

Let $w_k$ be the weight the optimizer places on a gradient $k$ steps old. For power-law memory with fractional order $\lambda \in (0,1)$, $w_k$ decays like $k^{-(1+\lambda)}$, following the discretization used by FrODO. We approximate it as

$$w_k \approx \sum_{j=1}^{m} c_j \beta_j^{k},$$

where the $m$ decay rates $\beta_j$ are spaced geometrically toward 1 and the coefficients $c_j$ are fit once, offline, for a given $\lambda$. This is the standard route by which fractional-calculus numerics avoid quadratic cost. Each buffer $b_j$ decays by $\beta_j$ every server step. When a gradient $g$ computed at step $s$ reaches the server at step $t$, the update is

$$b_j \leftarrow b_j + c_j \beta_j^{\,t-s} g, \qquad x \leftarrow x - \eta \sum_{j} b_j,$$

where $x$ is the model and $\eta$ the step size. After insertion, each buffer holds exactly what it would have held had the gradient arrived on time, minus the contributions it would have made during steps $s$ through $t-1$, which are unavoidably lost. Fast buffers ($\beta_j$ small) automatically discount a stale gradient to almost nothing. Slow buffers keep most of it.

The testable prediction concerns the maximum tolerable delay $\tau^\star$. For exponential momentum, $\tau^\star$ tracks $(1-\mu)^2$. For delay-exact power-law memory, $\tau^\star$ should be governed by the fast-buffer mass $\sum_{k<\tau} w_k$. The heuristic behind this: in a linearized analysis of a delayed quadratic, the destabilizing term is the portion of the memory that reacts within the delay window. As a result, $\tau^\star$ should stay large even when the total gain $\sum_k w_k$ is comparable to high-$\mu$ momentum.

Relation to Prior Work

The proposal draws on three strands of prior work, each playing a different role.

FrODO (Fractional Order Distributed Optimization) supplies the motivation and the kernel. It weights the last $T$ gradients by a power law, reports 2–3x speedups over Nesterov and Heavy Ball in federated training and up to 4x on ill-conditioned quadratics, and finds the best $\lambda$ between 0.1 and 0.2. It is lock-step synchronous, stores $O(Tn)$ floats per agent for an $n$-parameter model, and says nothing about stale gradients. We change both of those properties.

Ordered Momentum (OrMo; Ordered Momentum for Asynchronous SGD) supplies the mechanism we generalize. OrMo re-indexes late gradients by the model version they were computed on and applies a geometric correction so that exponential momentum is reconstructed exactly. Our insertion rule is the same idea applied per buffer across a power-law spread of timescales. OrMo has a single timescale and so cannot separate delay-sensitive from delay-insensitive memory.

The delay literature constrains the design. DANA (Taming Momentum in a Distributed Asynchronous Environment) shows that the gap between current and stale parameters is what destroys momentum under asynchrony. The Liu et al. tradeoff paper quantifies this as the $(1-\mu)^2$ law. Zhou et al. (Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?) show that plain averaging of past iterates performs worse than the raw iterates on the 101-dimensional Rosenbrock function. This is a direct warning, since power-law memory is a form of weighted averaging. We address it by averaging gradients, not iterates, and by testing on the same Rosenbrock setup.

For the decentralized extension, Delay-Agnostic DGD and DGD-ATC (Delay-Agnostic Asynchronous Distributed Optimization) supply the peer-to-peer communication pattern with delay-independent step sizes. DGD-ATC is decentralized gradient descent in which each agent takes its gradient step and then averages with neighbors. Those updates are memoryless.

The fractional neural-dynamics work (FROND; Efficient Training of Neural Fractional-Order Differential Equation via Adjoint Backpropagation) documents the quadratic time cost of exact history integration and the sliding-window fix. We avoid both by replacing the history with an $m$-buffer state.

Research Program

The first component is analysis on delayed quadratics and streaming PCA (principal component analysis computed incrementally from a data stream), the setting where the $(1-\mu)^2$ law was proved. For fixed delay $\tau$, the delay-exact update is a finite-dimensional linear recursion in the model and the $m$ buffers. We will compute its stability region exactly by eigenvalue analysis and derive a bound on the step size and delay in terms of fast-buffer mass. We will then check whether that bound or total gain predicts $\tau^\star$ across $\lambda$ and $m$.

The second component is the master-worker optimizer, called delay-aware fractional memory (DAFM). Its state is $m$ buffers, a per-gradient version stamp, and one scalar power per buffer per arrival. We will fix $m$ between 8 and 16 and measure how far the approximation departs from FrODO's exact kernel.

The third component is a decentralized variant. Each agent keeps DAFM buffers over its local gradients and mixes with stale neighbor models under the asynchronous DGD-ATC protocol. Timestamps are local, so no global clock is needed. This phase is secondary. It tests whether the benefit survives when staleness also enters through consensus, not only through gradients.

Baselines

The naive reference is asynchronous SGD with standard momentum and no delay correction. On CIFAR-100 with ResNet18, 64 workers, and 10x-slowed stragglers, OrMo reports naive momentum ASGD at 59.96% test accuracy.

The strongest existing competitor is OrMo itself, including its delay-adaptive variant. It is the only method in the file that reconstructs history-based memory exactly under arbitrary delays, and on that same CIFAR-100 setup it reports 65.48% test accuracy. We will re-run OrMo in our own harness rather than trust the transferred number. To count as a win, DAFM must exceed OrMo's re-run accuracy at equal wall-clock time by more than seed-to-seed variation, or reach OrMo's final accuracy measurably faster.

DC-ASGD (Asynchronous Stochastic Gradient Descent with Delay Compensation) is a Taylor-expansion correction for stale gradients, reporting 8.19% CIFAR-10 test error versus 9.27% for ASGD with 4 workers. It represents correction without memory. Delay-adaptive step sizes that scale by $1/(\tau_k+1)$ (Delay-Adaptive Step-sizes for Asynchronous Learning) represent throttling without memory.

A naive asynchronous FrODO, which pushes stale gradients into the exact $T$-length buffer at arrival time, is the obvious combination that we must beat.

Two ablations isolate the key ingredient. The first uses DAFM buffers but inserts gradients at arrival time with no $\beta_j^{t-s}$ correction, which isolates delay-exact insertion. The second keeps the same buffers and insertion but lets the coefficients $c_j$ be tuned freely instead of fixed by $\lambda$, which isolates the power-law prescription.

For fairness, every method gets the same grid-search budget over step size and its memory parameter. All methods share the same seeds and replayed delay traces: we record each worker's compute-time trace once and reuse it for every method. The decentralized phase compares against asynchronous DGD-ATC and ASY-SONATA (Achieving Linear Convergence in Distributed Asynchronous Multiagent Optimization). No reported result was found in the file for DGD-ATC on Covertype or ASY-SONATA on Cleveland Heart Disease, so those numbers will be produced here.

Why not just…?

Why not just use OrMo with a tuned momentum coefficient? This is the main threat. If OrMo at its best $\mu$ matches DAFM across delay levels, the power-law spread contributes nothing. The $(1-\mu)^2$ law predicts that OrMo's best $\mu$ falls as workers are added. The tradeoff paper found the best $\mu$ dropped from 0.9 to 0.5 going from 1 to 8 workers, and tolerable delay fell from 120 at $\mu=0.7$ to 10 at $\mu=0.95$ in streaming PCA. Our sweep over worker counts and replayed delay distributions will show directly whether DAFM's advantage grows with delay, as claimed, or stays flat.

Why not just use several momentum buffers with freely tuned weights? DAFM is itself a bank of exponential buffers, so fractional calculus might add nothing beyond a sensible choice of weights. We accept this framing. The claim is about spreading memory across timescales and correcting each timescale for delay; the power law is a one-parameter prior on how to weight them. The free-coefficient ablation settles the question. If it wins at equal tuning budget, we report that the power law is only a convenient parameterization. If it matches only with far more tuning, the prior earns its place.

Why not just throttle step sizes with delay, or Taylor-correct stale gradients? Delay-adaptive step sizes ignore curvature. The authors of that method note it does not consistently beat synchronous baselines in wall-clock time. DC-ASGD's first-order correction is designed for small delays. Both are run on the Rosenbrock and ill-conditioned quadratic tests, where curvature dominates, and at the 10x-straggler CIFAR-100 setting, where delays are large. If either matches DAFM there, the memory is unnecessary.

Proposed Experiments and Decisive Checks

The first check is streaming PCA with synthetic covariance, following the Liu et al. tradeoff paper. We sweep delay and record $\tau^\star$ for exponential momentum at $\mu=0.7$ and $\mu=0.95$ (reported: 120 and 10) and for DAFM at matched total gain. The claim fails if DAFM's $\tau^\star$ follows total gain rather than fast-buffer mass.

The second check is the 101-dimensional Rosenbrock function with linearly growing delays, as in Zhou et al., together with FrODO's ill-conditioned quadratics. We measure iterations to target and whether the trajectory leaves the valley, which directly tests the iterate-averaging warning.

The third check is CIFAR-100 with ResNet18, 64 workers, and 10x stragglers, tracking test accuracy versus wall-clock time against OrMo's reported 65.48% and naive momentum ASGD's 59.96%. We also report per-worker memory and server compute for DAFM against the $O(Tn)$ cost of exact FrODO.

The fourth check covers the decentralized variant: Covertype logistic regression and MNIST logistic regression under asynchronous DGD-ATC, reporting optimality gap versus time.

Two results decide the proposal. The arrival-time ablation must lose clearly to delay-exact DAFM as delay grows. And DAFM's margin over tuned OrMo must widen with worker count. If either fails, the central claim is wrong.