Delay-Separated Step Sizes for Asynchronous Hierarchical Optimization

Networks of devices that learn or optimize together often fall naturally into clusters. Links inside a cluster are short and fast. Links between clusters are slow, lossy, or long-range. The best-understood asynchronous algorithms ignore this structure. They are analyzed with a "synchronous abstraction": each delayed message is replaced by a chain of imaginary relay nodes, so a messy asynchronous system becomes an ordinary synchronous one on a larger graph. That analysis then forces every node to shrink its learning rate in proportion to the worst delay anywhere in the network. One slow inter-cluster link therefore slows every fast local computation.

This note proposes a two-tier version of that abstraction. Relay chains are placed only on inter-cluster links, and the inter-cluster tier runs on its own slower clock, so a delay of $\tau_g$ fast ticks shrinks to roughly one tick of the slow clock. With this construction we aim to prove, and then test, that local step sizes can be set by the local delay alone, while the global delay affects only how many slow rounds are needed. If the claim holds, it resolves an open tension in the literature between the delay penalty of flat delay-tolerant methods and the speedups that hierarchy delivers. If it fails, the experiments will show which part breaks.

Core Claim

Flat delay-tolerant gradient-tracking methods all carry a step-size bound that shrinks with the maximum network delay. This holds for R-ADD-OPT, which uses relay-node augmentation with ratio consensus and derives a closed-form step bound from $\tau_{\max}$ (Distributed Optimization with Gradient Tracking Over Heterogeneous Delay-Prone Directed Networks). It holds for DTAC-ADDOPT, which augments each node's state with a sliding window of past states up to the delay bound (Delay-Tolerant Augmented-Consensus-based Distributed Directed Optimization). It also holds for Asynchronous Gradient Push, which converges only to a neighborhood whose size grows with update-rate disparity (Asynchronous Gradient Push).

Hierarchical push-sum, in contrast, converges at a rate set by subnetwork diameters rather than the global diameter (Fast and Robust State Estimation and Tracking via Hierarchical Learning). That work, however, synchronizes subnetworks through a central server with a fixed period and models no inter-tier delay at all. Nobody has asked whether the hierarchy can also isolate delay.

We claim it can, under one condition: the algorithm must be designed so that the inner loop never consumes stale inter-cluster information mid-flight. Concretely, consider strongly convex smooth objectives with condition number $\kappa$. Let $\tau_\ell$ and $\tau_g$ be the intra- and inter-cluster delay bounds in fast ticks. Let $\Gamma$ be the number of fast ticks per slow round. The target result is a time-to-accuracy-$\epsilon$ of the form

$$T_{\text{hier}}(\epsilon) \;=\; O\!\Big(\big[\tau_\ell\,\kappa\, D_\ell \;+\; \Gamma\, R_c\big]\log(1/\epsilon)\Big), \qquad \Gamma \approx \tau_g,$$

where $D_\ell$ is a local mixing factor that depends on cluster diameter. $R_c$ is the number of slow rounds needed per $\log(1/\epsilon)$. It depends on the inter-cluster graph and on how different the clusters' objectives are, not on $\kappa$.

The flat bound behaves like $O(\tau_{\max}\,\kappa\,D_{\text{global}}\log(1/\epsilon))$. That form follows from a step size of order $1/\tau_{\max}$ multiplying a $\kappa$-dependent contraction. The prediction is therefore that the hierarchical method turns a product, $\tau_g \cdot \kappa$, into a sum, $\tau_\ell\kappa + \tau_g R_c$. This is a falsifiable scaling statement, not a constant-factor tweak.

Research Program

The algorithm has two tiers.

Inner tier. Inside each cluster, nodes run delay-tolerant gradient tracking on the directed intra-cluster graph. The method follows R-ADD-OPT, but the step size is tuned to $\tau_\ell$. The inner tier tracks the cluster's average gradient plus a fixed correction term. The correction is refreshed once per slow round and plays the role of a variance-correction offset: it pulls the cluster toward the global gradient rather than its own.

Outer tier. Boundary nodes exchange running-sum messages with neighboring clusters. We reuse the running-sum push-sum idea from P-ASY-SUM-PUSH in ASY-SONATA (Achieving Linear Convergence in Distributed Asynchronous Multiagent Optimization), so that dropped inter-cluster packets lose no mass. There is no single cluster head. Several boundary nodes carry inter-cluster traffic, which avoids the single-head stall that Asynchronous BFT Consensus Made Wireless identifies as its main weakness. Byzantine heads remain out of scope.

Analysis. The analysis builds the two-tier augmented graph. Each intra-cluster link carries a relay chain of length at most $\tau_\ell$. Each inter-cluster link carries a chain of length $\lceil \tau_g/\Gamma\rceil$, measured in slow ticks. Because the outer tier only reads relayed values at slow-round boundaries, the full system is a synchronous block system that contains two sub-systems: an inner system per cluster, and an outer system on the cluster graph.

Stability is then proved with a small-gain argument in the style of ASY-SONATA's error-system interconnection. One gain runs from outer error to inner error, through the correction term. The other runs back, through the cluster-average estimate. The two technical tasks are:

  1. Showing that the inner and outer graphs retain the irreducibility and aperiodicity that DTAC-ADDOPT verified for flat augmentation.
  2. Bounding the coupling gains so that the small-gain condition can be met with an inner step size that depends only on $\tau_\ell$.

A side benefit addresses the dimension blow-up flagged for flat augmentation. In fast ticks, the augmented state grows by $\sum \tau_{\text{link}}$. Here the inter-cluster part grows only by $\tau_g/\Gamma$ per link.

We will also check where the claim must fail, so the theorem states its own limits. If $\Gamma \ll \tau_g$, inter-cluster information arrives mid-round and the separation is lost. If cluster objectives are very different, $R_c$ grows until it dominates the sum.

Baselines

Naive reference: flat AGP. This is Asynchronous Gradient Push run on the full physical graph with the delays injected into the network (Asynchronous Gradient Push). It represents "ignore the hierarchy, just be asynchronous." It runs on identical data, delays, and tick budget, with its step size grid-searched over the same number of values as our method.

Strongest flat competitor: R-ADD-OPT. This is R-ADD-OPT on the same full graph. It is the strongest flat competitor because it already reaches exact linear convergence under heterogeneous bounded delays on directed graphs. We will run it twice:

  1. With its theoretical step bound computed from $\tau_{\max}$.
  2. With a step size tuned empirically by grid search, given the same tuning budget we give ourselves.

The tuned run is the fair comparison. The file reports no numeric convergence figures for this method, so we have no reported result to beat: no reported result found on Lacuna for R-ADD-OPT iteration counts on these benchmarks. ASY-SONATA, run with uncoordinated step sizes, serves as a second flat competitor; its paper reports faster convergence than AsySPA and AsySubPush on 30-agent regularized linear regression, without numbers in the file.

Hierarchical competitor: synchronous parameter-server hierarchy. This is the hierarchical push-sum scheme of Fast and Robust State Estimation and Tracking via Hierarchical Learning, with its synchronous inter-subnetwork server and the same period $\Gamma$. Server rounds wait for the slowest inter-cluster delivery. The only reported reference point is from that paper: near-zero error in roughly 1,000 delay units versus over 3,000 for a flat single network, on synthetic linear tracking. We will reproduce that setting and expect to at least match it while removing the central server.

Ablations. Three ablations isolate the key ingredient:

  1. Our exact algorithm, but with one network-wide step size set by $\tau_g$. This tests whether delay separation, rather than the hierarchy itself, is what helps.
  2. Our algorithm with $\Gamma = 1$, so the outer tier runs on the fast clock. This tests whether the slow clock matters.
  3. Our algorithm with the correction term removed. This tests whether the inner loop drifts toward its own cluster optimum.

What counts as beating a baseline. We beat tuned R-ADD-OPT if time-to-$\epsilon$ is lower by a margin that grows with $\tau_g/\tau_\ell$. A constant gap would not count.

Why not just…?

Why not just run a flat delay-tolerant method on the clustered graph? The hierarchy is only a topology, and flat theory covers any topology. This is the real threat. The $\tau_{\max}$ step bound may be pessimistic, and a tuned flat method may in practice already use large steps inside clusters. The tuned-step R-ADD-OPT baseline settles this directly.

If tuned R-ADD-OPT's time-to-$\epsilon$ also grows additively rather than multiplicatively in $\tau_g$, then our algorithm is unnecessary. The contribution would shrink to a tighter analysis of existing flat methods on clustered graphs. We would report that and redirect the theory accordingly.

Why not just let each node pick its own step size, as ASY-SONATA allows? Uncoordinated step sizes remove the need to agree on one value. They do not remove the coupling: a node inside a fast cluster still ingests stale gradient-tracking information from far clusters at every tick. Its usable step is still limited by that staleness. The ASY-SONATA baseline, given per-node step tuning, tests whether this freedom alone recovers the separation.

Why not just use randomized peer sampling like Epidemic Learning? Epidemic Learning breaks topology bottlenecks by contacting random peers each round. It reports 1.7× faster convergence and 2.2% higher CIFAR-10 top-1 accuracy than a 7-regular static graph at equal communication. It assumes, however, that any node can reach any other node, and it uses synchronized rounds. Both assumptions fail on the multi-hop, range-limited networks that motivate hierarchy. We include it only in the all-to-all CIFAR-10 setting as a reference point, not as a competitor on delay-structured graphs.

Why not just use a central server with shuffled asynchronous SGD? AsGrad shows that rates can depend on average rather than maximum delay under bounded gradients. Its shuffled variant reaches gradient norms about 10× smaller than plain asynchronous SGD on w7a. Its master-worker structure assumes direct links to a central server, which our setting lacks. Its average-delay insight is complementary rather than competing, and extending it to the outer tier is a possible follow-up.

Proposed Experiments

Strongly convex workloads.

  1. Synthetic least squares with 2.56 million instances and 50 features, following AGP, over 16–64 agents.
  2. Regularized multinomial logistic regression on Covertype (581,012 instances, 54 features).
  3. An MNIST logistic-regression subset on 16 agents with $\tau_\ell = 5$, matching DTAC-ADDOPT's setting.

Agents form 4–8 directed clusters. Intra-cluster delays are drawn from 1 to $\tau_\ell$ ticks. Inter-cluster delays are drawn from 1 to $\tau_g$, sweeping $\tau_g \in \{10, 30, 100, 300\}$. A random 0–20% of inter-cluster packets are dropped. Cluster heterogeneity is controlled by sorting data by label or feature cluster.

Metrics. Optimality gap and consensus error, reported as a function of fast ticks and of total messages, averaged over five seeds.

Non-convex check. CIFAR-10 with Dirichlet non-IID splits on 96 nodes, using decentralizepy. Its arbitrary-topology support lets us impose the clustered graph with injected delays. This check asks only whether the separation trend survives without strong convexity. The theory does not cover that case.

Decisive checks. The main check plots time-to-$\epsilon$ against $\tau_g$ at fixed $\tau_\ell$ and $\kappa$, and against $\kappa$ at fixed delays. The core claim predicts a specific pattern:

  1. For tuned flat R-ADD-OPT, the slope in $\tau_g$ increases with $\kappa$.
  2. For our method, the slope in $\tau_g$ is nearly independent of $\kappa$.
  3. The single-step-size ablation behaves like the flat method.

A second check sweeps cluster heterogeneity to locate where $R_c$ overtakes the inner-loop term. A third sweeps $\Gamma/\tau_g$ to confirm that the advantage disappears when $\Gamma$ falls well below $\tau_g$. If the product-versus-sum pattern does not appear against the tuned flat baseline, the claim is refuted.