Sparse training methods that let pruned weights come back to life work much better than pruning that is permanent. The catch is the cost of that revival. A method has to keep a dense "shadow" copy of every weight so that pruned weights keep collecting gradient updates and can return when they become useful. In decentralized learning, where many devices train one model by repeatedly averaging with their graph neighbors instead of reporting to a central server, that dense copy wipes out the memory and compute savings that motivated sparsity in the first place. We propose to remove it. Each device keeps only its own sparse slice of the model. It learns whether a weight it dropped should return by reading the importance of that weight from neighbors who still hold it. The dense model then exists collectively across each neighborhood rather than on any single device.
This turns a modeling question into an allocation question. Which weights should each device hold, given its own memory and compute budget, so that every important weight is held somewhere in every neighborhood? We score weights with the first-order Taylor estimate, the product of a weight and its loss gradient, which approximates how much the loss would rise if that weight were removed. Because these scores add up across weights, the allocation becomes a weighted coverage problem over the communication graph. Exact solution is intractable in general, but a greedy procedure carries a provable approximation guarantee. The graph's shape then becomes a resource constraint as well as a statistical one: sparse graphs like rings give each device few neighbors to borrow revival information from. We expect this to interact with the known result that such graphs already generalize worse.
Core Claim
The proposal makes two claims, and both are testable. The first is that neighborhood-distributed revival can match the accuracy of per-device dense-shadow revival, such as Dynamic Model Pruning with Feedback (DPF) run independently on every node, while each device stores only a sparse fraction of the weights. The second is that how much accuracy this costs is governed by a measurable graph quantity: the importance-weighted coverage that the allocation reaches on each neighborhood. We expect coverage to explain the gap between topologies better than spectral gap alone does.
Notation used below: $n$ is the number of devices, $d$ the number of weights (or filters, for structured sparsity), $N(i)$ device $i$ plus its graph neighbors, $S_i$ the set of weights device $i$ holds, and $B_i$ its budget. The allocation objective is
$$\max_{S_1,\dots,S_n}\; \sum_{i=1}^{n}\sum_{k=1}^{d} \hat I_k \,\mathbf{1}\!\left[k \in \textstyle\bigcup_{j \in N(i)} S_j\right] \quad \text{s.t. } |S_i| \le B_i,$$
where $\hat I_k$ is a running estimate of the Taylor importance $|w_k\,\partial L/\partial w_k|$ pooled from whichever devices hold weight $k$.
This is weighted coverage under a per-device cardinality budget. Coverage functions are monotone submodular, which means each extra weight held adds less value once others nearby already cover it. A per-device budget is a partition-matroid constraint. Simple greedy therefore achieves at least half of the optimum, and the problem is NP-hard in general because it contains set cover. This is the "joint resource allocation complexity" piece. Allocating memory per device and choosing masks per device cannot be separated, but additivity of the Taylor score keeps the joint problem tractable to approximate.
Where this sits in prior work
Three lines of work motivate the proposal and supply its parts.
The first line shows that revival matters. DPF updates a dense shadow vector with gradients computed on the sparse network. It loses only 0.47% top-1 on ImageNet ResNet-50 at 80% sparsity, and retraining its final mask from scratch does worse, which suggests the trajectory of dropping and reviving weights is itself useful. CLIP-Q uses the same mechanism of temporarily zeroed but still-updated weights. Accelerating Convolutional Networks via Global & Dynamic Filter Pruning recalls filters whose Taylor score recovers. PDP avoids shadow weights through soft masks, but the full dense tensor still stays resident. All of these assume one machine holding the whole model. We replace the local dense copy with neighbors' sparse copies.
The second line supplies the scoring and allocation machinery. Pruning Convolutional Neural Networks for Resource Efficient Inference introduced Taylor saliency on feature maps, with layer-wise normalization so scores can be compared globally. We reuse that normalization. ElasticTrainer shows that Taylor scores can drive a knapsack-style selection at runtime, with overhead below 1% of total computation. It also reports that scoring on training batches risks discarding weights needed for generalization, which constrains our design. FedSAC uses neuron-level Taylor importance to hand clients submodels of different size, but a central server does the allocation. We perform allocation through local exchanges on an arbitrary graph, with no server.
The third line ties topology to accuracy. Topology-aware Generalization of Decentralized SGD proves a generalization bound depending on spectral gap. It finds that fully connected and exponential graphs generalize better than grids, which generalize better than rings, on CIFAR-10 with 64 workers. Its analysis is for dense, IID training. Decentralized Deep Learning with Arbitrary Communication Compression (CHOCO-SGD) shows that sparsifying messages, for example sending only the largest entries, converges on any connected graph. It also reports an unexplained generalization gap as node count grows. Beyond Exponential Graph gives finite-time-consensus BASE graphs for arbitrary $n$, which we use as a sparse but well-mixing topology. Topology-Aware Knowledge Propagation in Decentralized Learning reweights neighbors by centrality but needs global graph knowledge, a limitation we avoid by using only one-hop information. Compression in CHOCO-SGD reduces bandwidth while every node still computes and stores dense weights. Our method makes computation and storage sparse, and treats communication as the channel through which revival happens.
Research Program
The algorithm alternates between two timescales.
On the fast timescale, each device runs decentralized SGD on its support $S_i$. When it gossips, it sends values and Taylor scores for its held weights to neighbors, compressed in CHOCO style. A weight that device $i$ dropped but some neighbor holds keeps a running importance estimate at $i$, built from neighbors' scores. That estimate stands in for DPF's shadow magnitude.
On the slow timescale, every $T$ steps, each device re-runs a local greedy step for the coverage objective using only one-hop information. It drops its lowest-marginal-coverage weights and adds those whose neighborhood-pooled importance is high but that are thinly covered. A revived weight is initialized from the neighborhood average of its value.
Three technical issues need direct study. First, a neighbor's gradient was computed at the neighbor's parameters, not device $i$'s. The borrowed importance is therefore biased by consensus distance, and that bias should grow as spectral gap shrinks. We will measure it directly against the true local Taylor score, obtained by computing dense gradients offline on held-out checkpoints. Second, under non-IID data, neighbors may value a weight for reasons irrelevant to device $i$. We will test whether pooling importance helps or hurts in that regime. This matters because the generalization theory in the topology-aware generalization paper does not cover it. Third, following ElasticTrainer's warning, we will compare scoring on training batches with scoring on a small local validation split.
On the analysis side, we will relate the coverage achieved under the budget to a topology statistic: the minimum neighborhood size weighted by budget. We will then test whether this statistic predicts final accuracy across graphs that share a spectral gap but differ in degree.
Baselines
The do-nothing reference is dense decentralized SGD with no pruning and no compression, run on the same graph. It sets the accuracy ceiling and the cost we aim to cut. A second naive point is training dense, then pruning by global magnitude with a short fine-tune. This shows how much training sparse buys at all.
The strongest competitor for accuracy is per-node DPF: every device runs DPF with its own dense shadow vector inside decentralized SGD. It is the strongest because it has strictly more information than our method, a full local dense copy, and DPF is the best reversible method in the file. The reported reference point is 0.47% top-1 drop at 80% sparsity on ImageNet ResNet-50, and 91.76% accuracy at 99.9% sparsity for WideResNet-28-8 on CIFAR-10, both from Dynamic Model Pruning with Feedback. For decentralized sparse training of any kind, no reported result was found on Lacuna. We will run it ourselves with identical graphs, data partitions, sparsity schedules, step counts, and the same hyperparameter search budget for both methods. Beating it means matching its accuracy within 0.5 points at equal active sparsity while using at most the sparse fraction of its per-device weight memory, or exceeding its accuracy at equal per-device memory.
The strongest competitor for communication is CHOCO-SGD with top-$k$ messages, reported as sending 32x fewer bits per weight than full precision on a 32-GPU cluster. We will match its bits per round and compare accuracy, per-device FLOPs, and memory. We do not expect to beat it on bits. We expect to win on compute and memory at comparable accuracy.
Three ablations isolate the key ingredients. Using a single shared static mask on all devices removes both diversity and revival. Replacing Taylor scores with random allocation under the same coverage-greedy step removes the importance signal. Disabling revival, so dropped weights never return, removes the dynamic path DPF found essential. A centralized allocation in the FedSAC style, computed with global knowledge, serves as an oracle upper bound on the allocation step.
Why not just…?
Why not just run DPF on every node? This is the real threat, and when memory is not binding it may simply win. Its cost is a dense $d$-dimensional shadow per device, so it gives no memory reduction during training, which is the regime that motivates on-device decentralized learning. The experiment settles it directly. If neighborhood revival falls more than half a point short of per-node DPF at equal sparsity on BASE and exponential graphs, the claim fails and we will say so. If it matches on well-connected graphs but not on rings, that is the predicted coverage effect, and the claim narrows accordingly.
Why not just compress messages with CHOCO-SGD? Top-$k$ compression cuts bandwidth, but every node still stores and computes on the dense model. It also does nothing about the large-scale generalization gap its authors report. We will report FLOPs and memory alongside accuracy at matched bits. If CHOCO-SGD paired with a final magnitude prune reaches the same accuracy-to-compute tradeoff, our allocation step is unnecessary.
Why not give every node the same mask? A shared mask needs no coordination and keeps averaging exact on the support. However, it covers only $B$ weights in total, no matter how many devices there are, and it can only revive weights through local magnitudes that are zero by construction. The shared-mask ablation measures exactly this. If it ties our method, distributed coverage is not doing work.
Why not solve the allocation exactly? Exact weighted coverage under per-device budgets is NP-hard and needs global state, the same problem Sakarvadia et al. note for betweenness centrality. On small graphs of 16 nodes we will solve the integer program and report how far the local greedy falls from the optimum, to check that the approximation is not the bottleneck.
Proposed Experiments
The main testbed follows the topology-aware generalization study: CIFAR-10 with ResNet-20 and WideResNet-28-8 on 64 workers. We will compare ring, grid, exponential, and BASE-2 graphs, each at 80%, 95%, and 99% sparsity, under IID partitions and Dirichlet non-IID partitions. A scale check runs ImageNet ResNet-50 on 16 to 32 workers at 80% sparsity, which allows direct comparison with DPF's single-machine number. Structured sparsity at filter level, using normalized Taylor saliency as in Molchanov et al., tests whether the gains turn into real speedups.
The metrics are top-1 test accuracy, the generalization gap between train and test loss, per-device peak memory, FLOPs per step, bits communicated, and the measured bias between borrowed and true local importance.
Three checks decide the outcome. First, at equal per-device memory, our method beats per-node DPF configured to fit that memory. At equal sparsity, it comes within half a point of unconstrained per-node DPF on BASE and exponential graphs. Second, across graphs, achieved coverage predicts the accuracy drop better than spectral gap does. We test this by building degree-matched graphs that differ in spectral gap, and spectral-gap-matched graphs that differ in degree. Third, turning revival off costs more accuracy on sparse graphs than on dense ones. If none of these hold, the distributed-shadow idea does not earn its complexity.
References
- Dynamic Model Pruning with Feedback
- CLIP-Q: Deep Network Compression Learning by In-Parallel Pruning-Quantization
- Accelerating Convolutional Networks via Global & Dynamic Filter Pruning
- PDP: Parameter-free Differentiable Pruning is All You Need
- Pruning Convolutional Neural Networks for Resource Efficient Inference
- ElasticTrainer: Speeding Up On-Device Training with Runtime Elastic Tensor Selection
- FedSAC: Dynamic Submodel Allocation for Collaborative Fairness in Federated Learning
- Topology-aware Generalization of Decentralized SGD
- Decentralized Deep Learning with Arbitrary Communication Compression
- Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence
- Topology-Aware Knowledge Propagation in Decentralized Learning