Stragglers as Stale Neighbors: Delay-Tolerant Local Plasticity for Distributed Representation Learning

Distributed computations stall on their slowest worker, the "straggler." The standard fix inserts algebraic redundancy so that the result can be rebuilt from whichever workers finish first. This note asks whether a class of brain-inspired learning rules makes that redundancy unnecessary. These are networks in which every synapse updates using only the activity of the two neurons it connects, a requirement known as the synaptic locality constraint. In such a network, a neuron only ever needs its neighbors' current activity. If the neurons are spread across machines, a straggling machine is no longer a missing piece of a global calculation. It becomes a neighbor whose activity is slightly out of date.

The specific claim concerns similarity-matching networks, which learn principal subspaces or separate mixed signals using two kinds of connections: excitatory feedforward connections that strengthen when input and output neurons fire together (Hebbian) and inhibitory lateral connections that strengthen the same way (anti-Hebbian). If the output neurons are sharded across workers, these networks can run fully asynchronously, with no coding and no barriers, and still converge when workers lag. More surprisingly, their delay tolerance should grow during training. The lateral inhibition drives outputs toward decorrelation, which shrinks exactly the cross-worker couplings that make staleness harmful. The network learns to need its stragglers less.

Core Claim and Mechanism

In the principal-subspace network of Pehlevan and colleagues, summarized in Neurons as Canonical Correlation Analyzers, outputs $y$ settle under the recurrent dynamics $\dot y = Wx - My$. Here $x$ is the input, $W$ holds the feedforward weights and $M$ the lateral weights. The weights then update locally as $\Delta W \propto yx^\top - W$ and $\Delta M \propto yy^\top - M$.

Suppose the output units are partitioned across $n$ workers. Each worker owns a block $y_k$, the rows $W_k$, and the lateral rows $M_{k\cdot}$. Each settling step for worker $k$ then needs only the other workers' $y_j$, which is one small vector each. In synchronous execution this is a barrier per step, and one slow worker idles everyone. We instead let worker $k$ iterate with whatever possibly stale copies $y_j(t-\tau_{kj})$ it last received:

$$ y_k \leftarrow y_k + \eta\Big(W_k x - M_{kk} y_k - \sum_{j\neq k} M_{kj}\, y_j(t-\tau_{kj})\Big), $$

where $\eta$ is the step size and $\tau_{kj}$ is the unbounded but finite delay on the link from $j$ to $k$.

Classical theory of asynchronous fixed-point iterations says this converges for arbitrary bounded delays when the synchronous iteration is a contraction in a weighted max-norm. A sufficient condition is block diagonal dominance, $\|M_{kk}^{-1}\| \sum_{j\neq k}\|M_{kj}\| < 1$. The quantity on the left, which we call the cross-worker coupling $\rho$, is the object the proposal is built around.

The prediction follows from the plasticity rule itself. $M$ tracks the output covariance $yy^\top$, and the anti-Hebbian competition drives outputs toward decorrelation. So the off-diagonal blocks $M_{kj}$ shrink as learning proceeds, and $\rho$ should fall over training. A network whose lateral weights are learned locally should therefore become more straggler-tolerant precisely as it becomes a better representation.

The same structure holds for the determinant-maximization network of Biologically-Plausible Determinant Maximization Neural Networks for Blind Separation of Correlated Sources. That network separates correlated sources with feedforward, lateral and feedback connections, all updated by local Hebbian and anti-Hebbian rules. It is our second testbed because its sources are deliberately correlated. Decorrelation is therefore incomplete there, which makes it the hard case for the self-decoupling prediction.

How This Sits Against Prior Work

The coded-computing literature supplies both the baselines and the motivation. MatDot and PolyDot codes (On the Optimal Recovery Threshold of Coded Matrix Multiplication) and Gradient Coding (Gradient Coding) recover an exact product or gradient from any sufficiently large subset of workers. They pay for this with redundant computation and, for low recovery thresholds, larger messages. Serverless Straggler Mitigation using Local Error-Correcting Codes is the closest system to ours. It protects matrix-vector and matrix-matrix kernels on serverless workers with locally recoverable product codes, so that repairing a lost block reads only nearby parity. Its "locality" is the coding-theoretic repair locality. It still insists on the exact output of each kernel, and it treats each kernel as a one-shot job.

We keep that paper's computation and deployment setting, iterated matrix-vector products on serverless workers, but drop the exactness requirement. Our argument is that an iterative contraction does not need any single step to be exact. Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework already relaxes exactness by approximating missing outputs with smoothing splines. It still decodes centrally at a master and treats each call independently, whereas we use no decoder at all.

Sequential Gradient Coding For Straggler Mitigation motivates our delay model. It reports that slowdowns on AWS Lambda are temporally correlated, so the same worker tends to lag for several rounds. That is the worst case for a staleness-based scheme, so we must test it directly.

On the locality side, Formalizing locality for normative synaptic plasticity models defines locality as dependence on a parameter's statistical Markov blanket in the network's computational graph. Our contribution can be read as making that definition operational. A rule's Markov blanket, weighted by coupling strength, determines the blast radius of a straggler.

ODE-Inspired Analysis for the Biological Version of Oja's Rule in Solving Streaming PCA supplies the single-machine quality ceiling: local Oja-type rules achieve optimal streaming convergence rates.

One piece of prior work constrains the design. Equilibrium Propagation with Continual Weight Updates reports that local continual updates run slower than batched backpropagation on GPUs because of frequent memory writes. We therefore make no claim about raw single-node speed. The comparison is wall-clock time to a target quality under stragglers, on matched hardware.

Research Program

The work has three parts.

The first is analysis. We will prove a delay-robust convergence statement for the asynchronous settling dynamics and the coupled asynchronous plasticity updates. The analysis treats the $\Delta M$ update for a cross-worker entry, which needs $y_j$ from a remote worker, as also using stale values, under a two-timescale argument in which the weights move slowly relative to the settling. It will express the tolerated delay as a function of $\rho$. We will also derive how $\rho$ evolves under the learning rule for the principal-subspace case. In that case the off-diagonal lateral weights should decay at a rate set by the gap between eigenvalues of the input covariance. Whether a comparable statement holds for determinant maximization is an open question we expect to answer only empirically.

The second is a system. We will build a sharded implementation in which each worker owns a block of output neurons and exchanges only its output block, of dimension equal to its number of neurons, through a shared store. The serverless deployment mirrors the one in the serverless coded-computing paper. A simulated cluster with injected delays allows controlled sweeps. Delays follow a two-state bursty Markov model, in which a worker is either "fast" or "slow" with sticky transitions, as motivated by the temporal-correlation finding in the sequential gradient coding paper. Burst length and slowdown factor are swept rather than fixed to one number.

The third is the decisive measurement. We will track $\rho$ across training and measure, at checkpoints, the largest delay at which the asynchronous network still reaches the synchronous solution. We then test whether these two curves move together.

Baselines

The naive reference point is synchronous uncoded execution. Every settling step waits for all workers, so wall-clock time is set by the slowest worker in each step. This gives the quality ceiling under distribution and the time floor we must beat.

A second naive point is drop-the-straggler. At each step a worker substitutes zeros for any block not yet received. This isolates whether the stale values we keep are doing useful work. Gradient Coding reports that discarding slow workers damaged predictive quality (AUC) on sparse tabular data, so we expect it to hurt, but it must be measured.

The strongest existing competitor is coded matrix-vector computation applied to each settling step. Concretely, this is the local product code of Serverless Straggler Mitigation using Local Error-Correcting Codes and, on the simulated cluster, MatDot-style coding from On the Optimal Recovery Threshold of Coded Matrix Multiplication. It is the strongest competitor because it was designed for exactly these kernels in exactly this serverless setting, and it gives exact steps.

The closest reported number is from the serverless paper on a different task. It reports a 42.1% reduction in total job time on ADULT and 44.5% on EPSILON, relative to speculative execution, for kernel ridge regression. No result is reported on Lacuna for coded computing applied to similarity-matching or other local-plasticity networks. We will therefore reimplement the code with the same worker count, the same delay traces, and a redundancy level tuned over a grid of equal size to our step-size and synchronization grid. Total worker compute, including parity computation, is reported alongside time.

We also run speculative re-execution with the same tuning budget. As an approximate-decoding competitor we run the spline decoder of Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework applied to missing output blocks.

Beating the strongest baseline means two things together. First, reaching a fixed subspace error, or a fixed separation quality for determinant maximization, in less wall-clock time than the best-tuned coded scheme across the burst-length sweep. Second, using strictly less total worker compute. Matching its time while using less compute is a weaker but still reportable outcome.

Two ablations isolate the key ingredient. The first freezes $M$ at its initial value, so the network cannot self-decouple. If tolerance does not degrade relative to learned $M$, the self-decoupling story is wrong. The second assigns neurons to workers adversarially, grouping strongly coupled neurons on different workers, to check that $\rho$, and not mere asynchrony, governs robustness.

Why not just…?

Why not just run asynchronous gradient descent on the same objective? This is the most serious alternative. Asynchronous solvers on a decomposable objective share much of our mechanism, and the similarity-matching updates are themselves a gradient descent-ascent. Our answer is empirical rather than rhetorical. We include an asynchronous block power-iteration baseline for the same subspace problem, with matched staleness. The distinctive prediction is that only the local-plasticity network's coupling, and hence its delay tolerance, improves during training. A fixed-objective asynchronous solver has a fixed coupling given by the data covariance. If the two show the same delay-tolerance curve over training, our contribution reduces to an application of known asynchronous theory, and we will say so.

Why not just use coded computing, which already works on these kernels? It does work. The question is cost. Exact codes pay redundant computation on every step and decode centrally, and the sequential gradient coding results show that one-shot codes over-provision redundancy when slowdowns are bursty. The head-to-head above, with compute accounting, settles whether skipping exactness is cheaper for an iterative contraction.

Why not just drop stragglers or re-execute them speculatively? Speculative execution has known overheads in serverless settings: it was the comparison point that local product codes improved on in the serverless paper. Dropping is a real threat whenever coupling is already small. In that regime zeros and stale values are nearly interchangeable. The drop-the-straggler baseline at late training checkpoints will show whether staleness or simple sparsity is what helps.

Proposed Experiments

We use MNIST and natural image patches drawn from CIFAR-10 for principal-subspace learning, measuring subspace error against a centralized eigendecomposition. We also use synthetic correlated polytope sources plus natural image patches for determinant maximization, following the Bozkurt, Pehlevan and Erdogan setup and measuring signal-to-interference-plus-noise ratio. Runs use 16 to 256 workers, the upper end matching the worker count in the sequential gradient coding Lambda experiments.

The first decisive check is the coupling-tolerance curve. Across training checkpoints, measured $\rho$ should predict the maximal tolerated delay, and this relationship should collapse when $M$ is frozen.

The second is the bursty regime. As mean burst length grows, the asynchronous network's advantage over coded execution should shrink. We will report where, if anywhere, it reverses.

The third is the correlated-source stress test. Because determinant maximization targets correlated sources, its decorrelation is partial, $\rho$ should plateau higher, and its tolerance should be correspondingly lower. If that holds, it confirms the mechanism rather than merely the method.