LEGACY: A Lightweight Dynamic Gradient Compression Strategy for Distributed Deep Learning
Authors: Mostapha Essoullami
El houcine Bergou
Aritra Dutta
Venue: ICLR 2026 Poster (2026)
Keywords: Distributed Computing
Compressed Communication
Federated Learning
Primary area: optimization
TL;DR: In this work, we propose a lightweight and efficient dynamic gradient compression method that changes the compression ratio of each layer based on the layer size and the training iteration.

Abstract: Distributed learning has achieved remarkable success in training deep neural networks (DNNs) on large datasets, but the communication bottleneck limits its scalability. Various compression techniques have been proposed to alleviate this limitation; however, they either use fixed parameters throughout training or rely on complex and computationally intensive methods to adapt compression parameters. Instead of the hard-to-tune hyperparameters required by adaptive compressors, this paper investigates the impact of two fundamental factors in DNN training—the layer size of the networks and their training phases—to design a simple yet efficient dynamic scheduler for any compressor, guiding the selection of compression parameters. We present a **L**ightweight **E**fficient **G**r**A**dient **C**ompression strategy**Y** or LEGACY, which, in theory, can work with any compression technique to produce a simple dynamic counterpart. We benchmark LEGACY on distributed and federated training, involving seven different DNN architectures, ranging from ResNet, Transformer-XL, to GPT-2, across large and challenging datasets, including ImageNet, WikiText-103, and OpenWebText. On ImageNet-1K, with an equivalent average data volume, LEGACY's dynamic compression strategies improve the Top-1 accuracy of ResNet-50 by 7-11% compared to uniform Top-0.1% compression, while on WikiText-103, the layer-based dynamic strategy reduces the perplexity of Transformer-XL by ~26% relative to the same baseline. In addition, we evaluate LEGACY under constrained and federated settings, and demonstrate that it scales effectively to a 100-worker configuration while maintaining strong accuracy under aggressive compression. We publish anonymized code at: https://github.com/LEGACY-compression/LEGACY.

Published as a conference paper at ICLR 2026
LEGACY: A LIGHTWEIGHT DYNAMIC GRADIENT COMPRESSION STRATEGY FOR DISTRIBUTED DEEP LEARNING
Mostapha Essoullami & El Houcine Bergou College of Computing
Aritra Dutta
School of Data, Mathematical, and Statistical Sciences University of Central Florida Orlando, USA
Mohammed VI Polytechnic University Ben Guerir, Morocco
ABSTRACT
Distributed learning has achieved remarkable success in training deep neural net- works (DNNs) on large datasets, but the communication bottleneck limits its scalability. Various compression techniques have been proposed to alleviate this limitation; however, they either use fixed parameters throughout training rely complex and computationally intensive methods to adapt compression pa- rameters. Instead of the hard-to-tune hyperparameters required by adaptive com- pressors, this paper investigates the impact of two fundamental factors in DNN training-the layer size of the networks and their training phases to design a simple yet efficient dynamic scheduler for any compressor, guiding the selec- tion of compression parameters. We present a Lightweight Efficient GrAdient Compression strategY or LEGACY, which. theory, can work with any com- pression technique to produce a simple dynamic counterpart. We benchmark LEGACY on distributed and federated training, involving seven different DNN ar- chitectures, ranging from ResNet, Transformer-Xl. to GPT-2, across large and challenging datasets, including ImageNet, WikiText-103, and Open Webtext. On ImageNet-1K K, with an equivalent average data volume. LEGACY's dynamic com- pression strategies improve the Top-1 accuracy of ResNet-50 by 7 11% com- pared to uniform Top-0.1% compression, while on WikiTexxt 103, the layer- based dynamic strategy reduces the perplexity of Transformer-XL. by ~ 26% relative to the same baseline. In addition, we evaluate LEGACY under constrained and feder- ated settings, and demonstrate that it scales effectively 100-worker configura- tion while maintaining strong accuracy under aggressive compression. We publish code at //q1 thub. www.Lo/..//////../ wwt.cecwwwccoccccocccccocccoccce L.EGAY
INTRODUCTION
Distributed learning on multiple computing nodes is widely adopted achieve optimal training per- formance for large deep neural networks (DNNs) (You et al. [0188] WWngpanich et al. [021]] | Xu
al. 2021a). However, the training requires exchanging gradients between the nodes; the massive volume of the exchanged data creates a communication bottleneck, and different compressed com-
munication techniques (quantization (Dettmers) 2015 Alistarh et al. 2017] Bernstein et al. 2018).
sparsification (Aji & Heafield 2017 Stich et al. 2018 Alistarh al. 2018] Dutta
2020)
low-rank (Vogels et al. 2019), and hybrid (Basu et al. 2019)) are designed to mitigate this problem.
Among these techniques, sparsifiers achieve baseline performance by only sending a small subset of the gradient components. E.g., by communicating only 0.36% of the largest gradient elements of ResNet-50 (He et al., 2016) trained on ImageNet-1K IK (Deng et al. 2009), Lin et al. (2018) achieves baseline no compression performance. Nevertheless, almost decade after its introduction by Aji & Heañeld (2017) for gradient compression, there no clear recipe for choosing for training different DNN models using the Top-k sparsifier. While Top-k sends fixed data volume in each training iteration, the threshold sparsifier (a.k.a hard-threshold (Strom) 2013 Sahu et al.) 202T) communicates gradient components with absolute magnitude greater than threshold, X 2 0. It sets anything less than À to zero. This allows the threshold sparsifier to send variable amount of data in each iteration and has better convergence guarantee (Sahu et al. (022)) One can view the threshold sparsifier as a simple adaptive counterpart Top-k;, since it sends variable amounts of data in each training iteration. However, the same question persists how to tune the threshold, X, in practice?
Not only the sparsifiers, (or Top-k in particular) for any compressors, the existing literature predom- inantly focuses uniform compression throughout the training, where the same compression ratio

---

Published as a conference paper at ICLR 2026
Very small( 102)
Medium < 1
Very largel 109)
Uniform Topk
Small[ < 6.10")
Large( < <109)
Global compression ratio
No 3.7%
50
Topk 3.22%
1:0
100-
Top 422%
40-
80
100 201
100
100 A01
40-
-0
20
10:
50
300
150
200
250
300
Simal Stad Larger
0
5
10
13
20
22
30
Very
Smail Mediumaarge
Epoch
small
large
Epoch
large
(a) Compression by epoch (b) Total compression
(c) Compression by epoch (d) Total compression
Figure 1: Compression ratio (in percentage, we use 5 100) vs. the training iterations and layer size in training ResNet-18 on CIFAR-100 ((a) and (b)) and NCF on Moviel.ens M ((c) and (d)) using the Top-k
and Threshold sparsifiers. For R8sNet18 and NCF, is set to 3.92%, and 4.22%, respectively, and 0.1.
is used for all layers. Although varying the compression ratio for each layer at different stages of training is feasible, this area is not well-explored and most available literature proposes compute- heavy methods find the best compressor (Khirirat al., 202T Xin et al.) 2023 Markov et al.] (u24).Attempe were made to achieve optimal compression performance by adopung different adap- tive strategies; see Ş In contrast, we investigated Occam's 's Razor principle: "plurality should not be posited without necessity." Instead of employing computationally intensive strategies, can we provide a simple yet efficient strategy for quickly selecting a compression parameter for each layer, achieving good balance between compressed data volume and model performance?
In that pursuit, we train two DNN architectures: (i) ResNet-18 (He et al., 2016) on CIFAR 100 (Krizhevsky et al.] 2009) (baseline no compression Top-1 accuracy IS 73.38%) and (ii) NCF on MovieLens-20N% (Harper & Konstan (013) 2015) (baseline no compression best Hit- Rate @ 10 95.59%) on standard PyTorch benchmark using 2 NVIDIA A100-SXM4 GPUs with 80 GB memory, con- nected via 400 Gbps network bandwidth. We use the Top-k and threshold sparsifiers and set the hyperparameters & and Å to send the same data volume. While uniform Top-k achieves a Top-1 accuracy of 73.00 73.04% on ResNet-18 18 and a best Hit-Rate@ 10 of 91.33% on NCF, the threshold sparsi- iysigh 73.32% on ResNet- 18 and a best Hit-Rate @ 10 of 92.7% on NCF, respectively. To get better insight into threshold sparsifier's superior performance over the Top-k, we plot the compression ratio for different layers of ResNet-18 over iterations and the total aver- age compression of its different size layers; see Figures [a)- We observed that the small and medium layers (dimension less than 102 to up to 109) are not severely compressed during the training compared to the large and very large layers (dimension more than larger layers expe- rience extremely aggressive compression even more aggressive than the uniform Top-k for those layers. Additionally, regardless of their sizes, during the beginning phase of the training, the layers are less aggressively compressed compared to the final training phase. We made almost identical observations in the NCF training; see Figures (d))
fier achieves a Top-1 accuracy of
Our empirical observations in using the Top-k sparsifier and its adaptive counterpart for DNN train- ing indicate two key factors: (a) the layer size of the DNNs influence in choosing how much one needs compress, and (b) the training phase of the DNNs can be a critical contributor in the dynamic compressor design. Moreover, the second observation is consistent with recent research on the critical training regine of DNNs (Achille et al.] 2019; Agarwal et al.) 2021a| Zhang et al. 2022). Although our quest for designing a dynamic compressor primarily started with sparsiferr, the above-mentioned simple factors can be used conjointly with any compressor in designing its ef- ficient counterpart. Based on them, we propose a compression framework that dynamically sets the compression level based on the epoch and layer size. Although both words, adaptive and dynamic, can depict our framework, we prefer to refer to it as dynamic, as we do not use any complicated, cormptte infeasible gradient statistics during training.
We list our contributions as follows:
Dynamic compressor scheduler ($2). We present a Lightweight Efficient GrAdient Compression Strateg or LEGACY that, in theory, can work with any compression technique to produce its sim- ple dynamic counterpart. LEGACY is based casy-to-obtain information layer size and training phase. Designing LEGACY is empirically motivated and stands on solid technical intuitions; see $21 Irrespective of the DNN models and training dataset, LEGACY can guide the selection of compression parameters based on the layer size or training phase; see system design in $C To simplify hyper- parameter selection, we propose a simplified version of LEGACY in C called Simple-LEGACY or S-LEGACY,
how the two LEGACY approaches can be combined.
2

---

Published as a conference paper at ICLR 2026
Theoretical insights (Sder the usual assumptions for stochastic first-order algorithms in the compressed, distributed setup, we validate the influence of our policies on the convergence of com- pressed SGD using biased and unbiased d-compressors; see Theorem in $4
Benchmarking ($5). We benchmark LEGACY through a variety of numerical experiments involv- ing diverse DNN architectures (convolution and residual networks, transformer, recommender sys- tem and GPT-2 a total of 7 models) trained for different tasks (image classification on CIFAR and collab- total of 6 datasets; see Table 6 in DD.I by using Top-k, Random-k (sparsifiers), QSGD Alistarh QSGD/Alistar
10, CIFAR 100, and ImageNet- 1K, text prediction on WikiText-103, OpenOeee
orative filtering Movielens- Doviilles-20M----
al. (017) (quantizer), and PowerSGD (low-rank) Vogels jct al. (2019) as base compressors. We report our results using test accuracy, communicated data volume, throughput, and computation time. Additionally, we compared LEGACY against 5 state-of- the-art adaptive compressors
et al. (202)) Variance-basee compression I'suzuku et al. 2018 Accordion Agarwal et al. (2021a), AdaComp Chen et al. (2018a), and L-Greco|Markoo et al. (024 Finally, in $D.3 we evaluate LEGACY in resource-constranned environments (compute and network bandwidth; SD.3. 1), federated learning ($.2..2), and large-scale configuration with 100
CPU workers D$3.33 demonstrating its scalability.
1.1
RELATED WORK AND BACKGROUND
Due to limited space, we moved the related work to $A
Notations. We use || to denote the fz-norm stochastic gradient and full gradient, respectively, at the ith node iteration t.
vector x. By Ii.t and Vii,t, we denote the
Compressor: A random operator, C(-) IRd > Rd is a compression operator if Ecllæ - C(x) < (1 - 1=:1| for all E R2,, where 5 > is the compression factor. A smaller indicates a more aggressive compression. In our setup, 8 E (0, and C is d-compressor. The popular sparsifiers, Top; and Random,, have 5 = á. and E| To); I El|x Randomy (z)]l² < (1 |
2 DESIGNING A DYNAMIC COMPRESSOR
From Figure D we observe two key factors in DNN training. First, the compression ratio has more impact at the beginning of training than the end. Second, it is better to compress large layers and keep small layers uncompressed (or easy compression). But can these observations also be theoretically justified so that we can build a dynamic compressor scheduler based on them?
To answer this, we formulate the impact of unbiased compressors on the decrease rate for the gradi- ent descent (GD) algorithm under two relatively easier-to toe-to--nnn to-analyze cases: (?) smooth, strongly convex functions, and (ii) smooth, nonconvex functions with PL condition. There is no loss of generality in considering GD instead of distributed SGD analysis of GD offers ease of notation, and under simple arguments, leads us to a practical scheduler.
Setup. Consider the empirical risk minimization (ERM) problem with computing nodes:
F(z) = -(x)=--\ f((x)
min
(1)
where f((x) := E,,-D, 24) is the loss function at node on input 2; sampled from its distribution,
D. Let Dt,t be the stochastic gradient computed at the ith node in iteration and of the form
Ir.1 V fi, + Ei,,, with [[ = 0. We made general assumptions in B.1 to prove our results.
2.1 INSIGHT THROUGH THE LENS OF THE COMPRESSED GD
Let C, be unbiased 8, compesssss for all t E [T). The iterative update rule of the compressed GD algorithm with fixed stepsize, 1) 2 0 and unbiased commopprsss in solving is given by
It+1 I >CC((VF())).
In the following lemma, we quantify the decrease in the quantity, ||x.41 -x,l 2 under the smoothness and strong convexity assumption; the proof in |B.2
Lemma 1. Let F follow Assumptions [ andd [ Then with fixed stepsize n, the sequence of iterates,
fixe
(#th20 of compressed GD updates satisfy
Ee, F
11 < (1 2,m 17 (T 56) 1| xr 1.,111
(( Real decrease
3

---

Published as a conference paper at ICLR 2026
Algorithm/ 1: Compressed distributed training without error feedback (EF)
Table Functions used in our framework.
Input: Number of nodes n, learning rate 7/ number of iterations T. batch-size B per node Roatch
Function
Description
Chooseparam
Decide compression
Output: The trained model r
parameters
for t= = 0, 1,.,...77 do
Compress
Apply compression
On each node i:
each layer
gi.t Calculateggadientt/ maatch))
Communicate
Send compressed gradient to the server
k phooseparammgg.t.
g Compress (gr,e, ki,e)
Receive
Gather the compressed gradients from workers Restore the original tensor shape
Communicate(ā...
On Master:
Decompress
91,4......0. _m.. Receive(n)
(r.l...... Sn.1
AverageGrads
Average the received gradients
Decompress Er.t
Ba,el)
AverageGrads ((9,,) gn.,))
Broadcast
Broadcast the averaged gradient
Broadcast (g.)
On each node i:
Update
Optimizer independent
2141
(2t,
parameter update
Note that (66)) is function of the compression factor. For compression, 6, 1, we obtain:
| x= 11? - (1 2pm μn2 L) || x. 1|2 = D(1) == Ideal decrease.
Ideally, we are interested in & E (0, 1] such that ((5e) (i.e., the compressed GD decrease) as close possible to (11) (i.e., the non-compressed GD decrease). We have
D(6,) D(1) -o 6t) 11x x+
To have A x O, we require:
(i) Strategy I: Compression based on the training phase. the beginning of the training, we have ||,r - x.. > 0. Therefore, to make A Rs O we need to choose 6, - 1 (no or easy compression). At the end of the training, || x. 2 xv O. Hence, no strong control needed on 6, to keep A small. In this case, one can choose 6, R 0 (aggressive compression).
(ii) Strategy II: Compression based on the layer sizes. We observed that a small subset of layers in DNN training dominates the communication overhead. E.g., for the models benchmarked in this paper, the largest 20% of layers account for 90% of the total parameter volume, while the remaining 80% contribute to only 10%. This makes large layers ideal candidates for aggressive compression, as they are usually overparameterized with more redundancy and can tolerate higher compression without significantly affecting model quality.
In contrast, smaller layers, while contributing little to total communication volume, often contain gradients that are critical for stable and efficient convergence. Maintaining higher fidelity for these gradients is therefore important. By compressing large layers more aggressively and reallocating the resulting bandwidth savings to smaller, more sensitive layers, we can reduce compression severity where accuracy is most impactful. thereby improving overall gradient quality without increasing to- tal communication cost. E.g.. for Top-k, the contribution of compressed elements from large layers to the quantity | x. small. The small layers with less redundancy than the large layers crucial, and their suboptimality (if compressed too much) may lead to larger errors. Therefore, com- pared to uniform 6-compressors, with strategy II, it is better to easily or not compress small layers, ie., 8, s 1, and focus on compressing large layers with compression & R 8. With this strategy, result in similar data volume and improved convergence. Even slight increase in compression aggressiveness for large layers, such as reducing the transmitted gradient volume from Top-k with 9.95%, can yield a substantial benefit. While the 0.05% reduction is negligible for a large layer in terms of both volume and performance impact, the reclaimed budget can represent a significant increase for smaller layers, potentially allowing a shift from transmitting just 10% to over 50% of their gradients; in some cases, can be 100% reduction redistributions dramatically enhance gradient representation in small layers, improving convergence stability and overall model accuracy with minimal trade-offs; see practical example and another angle to look at Strategy II in CC...3
= 10%
compression. Such
To further extend our theoretical insight for Strategy-I, in the next lemma, we consider GD for minimizing a smooth nonconvex function under the PI. condition and quantify the functional sub- optimality gap, Fe, (F++)) F.; see the proof in B.2
4

---

Published as a conference paper at ICLR 2026
Function 3: [ayeesiiaedorrraaaiio4421111 (4))m
Function apochCoupressioo((AA/) (im)
Input: Gradient : iteration from worker
Input: Current iteration,
Output: compression parameters list for each layer L in 9t,, do
Output: Compression parameter, 6, j = index the smallest threshold from {A: such that iteration S A
index of the smallest threshold from (A.)= P
such that [T_] S Ay;
return 8y
Append 6, to compression parameters list;
return compression parameters list;
ML Framework TensorFlow, PyTorch
Punction
Transmitting worker
Epoch based compression
Receiving worker
Correnantio mniicate
Communicate
Decompression
Network
Compression operator
chooseparam
Topp etc.
Tensorf Flo, PyTorch
Layer based compression
Figure 2: System architecture. The LEGACY framework is highlighted in blue.
Lemma 2. Let F follow Assumptions ! and 4 Then with stepsize = 1 the sequence of it-
erates, f2e)e20 of compressed GD updates satisfy Ec, (F(+1) F. S (1 4
(Fr F.)
D(5))= == Real decrease.
gives the ideal decrease, ie., the decrease in the functional suboptimality gap without compression: Fr+1 F. < +) (Fi 117--P)) F.) D(I) Ideal decrease. To have A = (())) - D(1) = (1 - 6 (F, F.) ~ 0, we require: (i) At the beginning of the training F. F. >> 0. Therefore, we need to choose ó se (no or easy compression) to keep A s O. (ii) At the end of the training F; F. as 0. Therefore, we can choose 6, s 0 (aggressive compression).
Substituting
2.2 A DYNAMIC COMPRESSOR SCHEDULER
Motivated by the previous section, formally define dynamic compressor scheduler for com- pressed distributed training plicity, we consider the optimizer to be SGD. Given stepsize sequence, {"e 2 0f120 and ò,- compressors, the update rule for compressed distributed SGD on n workers is given by
workers. Although our scheduler is optimizer agnostic, for sim-
03 Σ Cg..))
It+1 Ft.
Algorithm 1 provides general compressed communication framework without error feedback Karimireddy et al., 2019). Our approaches build on this framework by adjusting the compression level via the chooseparam function; unimodal trai in blue. We require two user-inferred hyperpa- rameters: (i) a sorted list of p decreasing compression levels, {6.}² 1o of the d-compressor C,, where 6p being the most aggressive compression factor, and (ii) a sorted list of p non-decreasing thresh- olds, {): 2 0) which represents either an iteration or layer size which we use certain compression level 8, in Algorithm I
The threshold change is based on the following approaches:
(i) Training epoch dependent. We start with a less intense compression and gradually increase its intensity during the training. Epoch compression, we progressively increase the compression level 5 as training progresses; see Function 2 In this case, the non-decreasing thresholds (A; ) denote the iterations epochs at which the compression intensity increases.
(i)) Layer size. We employ an easy compression for small layers as their size is insignificant com- Function In this
pared to the larger ones. We achieve this through Function, we used the thresholds {A₃ 1/= to group layers by their sizes; smaller layers are affected by a less intense compression, while the larger layers experience a more aggressive compression.
SYSTEM ARCHITECTURE, HYPERPARAMETER CHOICE, LEGACY VARIANTS
We present Lightweight Efficient GrAdient Compression Strateg or LEGACY; illustrated in Fig- 2 LEGACY is framework-agnostic (e.g., compatible with TensorFlow and Py Porch) and provides
5

---

Published as a conference paper at ICLR 2026
6100 Bo Ea..ss 8y
BisEos BisEs Spla.
Sicke. S1g41 Sicfog
610
BazE:
BgE base line
S14
6:
BosEis
0on
0.32
0.74
0,50
0:82
0.15
6.75
Accuracy.
0.00
0.25
0.54
0.22
0.33
0.62
0.755
0.60
0.20
022
0.750
0.28
0.22
9.70
Relalive Avg. Data
10
10
13
fug. Data Volume
10
Relative Avg.
(a) AlexNet (CIFARIO)
(b) ResNet 9 (CIFARI0)
(c) ResNet 18 (CIFARI00)
0.56
163
0.90
200
HR@30
Perploor loxkyy
0,000
Accuracy
3,81
0.0
3.87
100
0.55
0.60
80 1.00% 0.001
0.2
1,000
10"h
Avg. Volume
15%
12
Relative Avg. Data Volume
17
20-h
Aug. Valume
20
(d) NCF (Moviclens-20m)
(c) Seanssfomer-xlWWWiiiiee
(f) ResNet 50 (ImageNet-
Figure 3: Layer-size and training epoch dependent Top-k and uniform Top-k (denoted by Ócompression)
Relative average data volume vs. model quality.
a simple API that supports arbitrary gradient compressors such as Top-k and QSGD. For clarity, Algorithm instantiates LEGACY within a parameter-serrer architecture; however, this serves only proof of concept. LEGACY is independent of both the underlying base compression method and the communication protocol. We conducted Top-k with NCCL AllGather NCr demon- strate scalability via (PU-based experiments using Gloo gloo in SD.] and use AllReduce for PowerSGD experiments in $5.4 Since LEGACY only governs compression parameter selection, it in- tegrates seamlessly into any distributed training setup (e.g., parameter-server, ring all-reduce) where gradient compression is applicable.
For transmitting workers, LEGACY is executed through the intermediary API call chooseparam in Algorithm [ responsible for selecting the appropriate compression parameters for each layer. After gradient computation through any ML benchmark, based on the user's strategy, epoch compres-
= 0) is invoked to dynamically determine the compression parameters for each layer, which are then applied to the gradient com- pressor in the worker. Additionally, Functions 2 and 3 in LEGACY can be used conjointly with the cosseeorpress,r, the blue three-point arrow. Other than chooseparam LEGACY uses other well- known APIs for communication, averaging. broadcasting, etc.; see Table The receiving worker applics reverse operations and decompresses the received gradient. LEGACY can be used for uplink and downlink bidirectional compression by simply compressing the gradient sent from the server.
sion Function 2
1) or Layer size compression Function
To simplify the selection of hyperparameters used in LEGACY (fA.)/- for thresholds and { for compression levels), we propose a simplified version of LEGACY in called Simple-LEGACY or S-LEGACY. This version requires only two hyperparameters for the epoch or layer- ap- proach and three for the mixed approach. That is, S-LEGACY-E requires only a default compression parameter 8, and the number of training phases S-LEGACY-L requires ò, and decrease ratio s; S-LEGACY-M (stands for using both layer and epoch-based) in C.I. demonstrates how the two LEGACY approaches can combined and requires óu, n, and
4 CONVERGENCE GUARANTEE
In this Section, we establish the nonconvex convergence of distributed SGD with 6e-compressors. To prove a general distributed convergence with 8 compressor, biased or unbiased, we want to estimate the quantity, E' | (Σi1 ll | as this highly influenced by LEGACY 's strategies. To achieve that, adopt slightly different approaches for biased and unbiased compressors, C..

---

Published as a conference paper at ICLR 2026
Denote 3, := (1 6,) +1) + M, where M. o² 2 0 are constants such that for all 2; E IR, the stochastic noise, E.. follows xl x2| & M| V fe + o²; see Assumption [S) The constants appearing are due to the general Assumptions in $B. For biased compressors, we adopt a few extra assumptions. First, we consider a (C, (²) bounded similarity assumption on the variance of the gradients among the workers. This Assumption is stronger than Assumption [6] but similar assumption proposed in Sahu et al. (202I), and we rely on it for algebraic purposes in proving the convergence for the general case. Due limited space, we defer the biased-compressor results, including intermediate Lemmas and the main complexity theorem, to (B.3.2
Lemma 3. (Compression Bounds) Let the stochastic noise n Assumption 5 Let Ct be unbiased
d: comoorrssss for all l. [T], and let F follow Assumption
6 (2-b 0²2
We have E En_ C( S
2.8 (F. - P.)
A1 m |VF +
B&
m
n
Using the previous Lemma, the following theorem gives the complexity results for unbiased 6, com- pressors. which are similar to the classical complexity results for compressed SGD-type algorithms: see et al. (202)): Stich & Karimireddy (2020); |Sauu et al. (202T). The proof is given in BB.
Theorem 1. (Nonconvex convergence) (i) Let Assumptions
7 and hold. Let C, be unbiased
o--compressors for all E [T]. For a stepsize 1 S min
AL(2M+1IT)
we have:
min E
VFl <
3(Fo-F.) + +G, where δ Tv Lp Lm
Ln( (12
2n(1- Lu
Theorem primarily guarantees that the (nonconvex) convergence of distributed SGD with d5- compressors in each iteration (which the policies of LEGACY govern: a changing compression level over iteration and & modulates the effect of epoch- or layer-based strategies). The factor, (B(
2n La La:2M-11 is the so-called variance, incurred due to the effect of multiple factors,
including compression ratio, 8, However, the theoretical analysis does not distinguish the relative performance of the epoch- or layer-based strategies.
5 BENCHMARKING AND EVALUTAION
Environment and Configuration. We run our experiments on 4 NVIDIA A100-SXM4 GPUs (2 GPUs for AlexNet, ResNet-9, ResNet-18, and GPT-2 training. and 4 GPUs for Transformer-XL. NCF, and ResNet-50 training) with 80GB memory and interconnected with 400 Gipss bandwidth. LEGACY is built on Dutta et al.) (020); Sahu et al. 20 for Transformer-XL. we used the NVIDIA Training Examples benchmark Nviddal with reduced steps; CIFARIO. CIFAR and NCF tests were implemented using Dutta al. (202)). Sahu al. (202T), and Nvidial respectively. We used 30 epochs for AlexNet, ResNet-9, and NCF training. 300 epochs for 18 training, and 4,500 steps for the Transformer training. For ImageNet-IK, we employed PPTooch and trained ResNet-50 for 50 epochs. We follow karpathy Andrej (2023) implementation for our GPT-2 experiments and use 100K training iterations; see Tables 6 and in SD1 for detailed summary and Tables 14 in $D.I reproduciiiil...
LEGACY Setup. In the main paper, for simplicity, split the training into two phases: beginning B (first half of the total epochs) and end E (rest of the total epochs); each phase uses different compression level. For layer sizes, we categorize layers into two groups: small layers, S with fewer than 10 elements, and large layers, L with 10* elements more. With this formalization, Sş, Ls, means small layers are compressed with compression factor, ón and large layers compressed with compression factor, 82, and Bs, Es, denotes two-phase training, beginning phase with compression factor, d,, and end phase with d2. In $D.2, we show the efficacy of LEGACY by adding multiple training phases and more layer granularity.
5.1 MODEL QUALITY VS. TRANSMITTED DATA VOLUME
Figure 3a shows the accuracy of AlexNet on CIFAR-10; uniform Top-k compression with k = 0. 1%d corresponding to the dg 1) results in an accuracy of 75.7%. However, using Top-k as base compression in LEGACY, the strategy, Fo.us which starts with compression ratio of 0.15% for the first half of the epochs and then switches to an aggressive compression ratio of 0.05% %, achieves a higher accuracy of 79.18%. Notably, the reverse strategy 00.00 results in a lower accuracy of 73.6%. When we compress smaller layers at I 1% while keeping the larger layers at the 0. 11 ratio, To.1. the accuracy improves by 5.14% over the uniform compression. Figures 3b show similar results across different DNN models and challenging, larger datasets, including
7

---

Published as a conference paper at ICLR 2026
2.80
0.75
Perplexitt
2805
0.73
Throughput
Throughput
Throughput
(a) ResNet9 (CIFARIO)
(b) AlexNet (CIFARIO)
(c) Transfromer Transfromer-LL(WiiiTBee XL(WikiText- 103)
Figure 4: Layer-size and training epoch dependent Top-k and uniform Top-k Throughput vs. model quality.
where experiments with similar global compression ratios are linked with a dotted line; see legend in Figure
Variance(a 2. 0.999)
Adacomp(L-100)
CAT
Bo.Foo.
Sylo.s
60.
0.8
0.3
Accuracy
Accuracy
Accuracy
0.77
0.6
0.4
0.5
0.2
0.4
0.0
Epoch
20
Wall Clock Time (s)
2000
100
Data Volume (MB)
200
300
400
560
(a) Test accuracy vs. epoch
(b) Test accuracy Time
(c) Test accuracy vs. data volume
Figure 5: Comparison of LEGACY with Top-k and other adaptive compressors in training ResNet9 CIFARIO.
ImageNet- 1K and WikiText, with accuracy improvements up 1-11% on ImageNet- IK compared to the uniform compression strategy. For language model in Figure 3e the perplexity improves 26%, from 253.57 with uniform 6o.1 to 188.8 with dynamic compression S10L0.1.
Takeaways. For comparable data volumes, starting with mild compression and gradually increasing it outperforms uniform inverse strategies by allowing DNN models retain crucial information during early training phases. This approach balances the need for sufficient data the early stages with the efficiency of higher compression later. Similarly, leaving small layers uncompressed or lightly compressed results in only minor increase in data volume but improves perplexity by 26% on WikiTeet- 103 and accuracy by 7% on ImageNet-1K.
5.2 MODEL QUALITY VS. TRAINING THROUGHPUT
F shows the impact of compression on model quality as a function the relative throughput. Test cases with a similar average compression ratio (=10%) are connected with dotted lines. The throughput under compression is lower than the no-compression baseline because the workers are connected through high-bandwidth links, making the compression overhead relatively higher than the communication cost. Analyzing the groups (connected by the dotted lines), observe that the average compression ratio influences the model performance and throughput; sending more data improves accuracy but reduces throughput. Applying moderate compression during the initial training phase and to smaller layers yields better performance for a similar average compression ratio. In Figure 4aj for ResNet9, a uniform Top-0.1% compression results in 75% accuracy, and 50.29% relative throughput. while throughput but improved accuracy, reaching 79. 19.88 Meanwhile, the layer size-based strategy, Lo further improves throughput to 53. 53.16% and accuracy to 80.85%, yielding gains of 5.7% in throughput and 6.6% in accuracy compared to the uniform compression. We observe similar findings in Figures 4b 4c Generally, the dynamic strategies in LEGACY (denoted by '+' for bpsch and x for layer size-hased) for linked points positioned either above (indicating better accuracy) or the right (indicating better throughput) of the uniform case for AlexNet and ResNet9. For the Transformer- XL. LEGACY strategy points are located to the right of or below the uniform case, under similar average compression ratios, indicating better perplexity, with improvements of up to ~66 in perplexity and ~4.5% in throughput compared to uniform compression.
epoch- strategy, Eo.1s yields similar relative
Takeaways. Our based strategy can increase accuracy and throughput compared to the uni- form or inverse approaches, although the throughput gains are limited due to the high-speed network in the data center. For the layer size-based approach, not compressing small layers eliminates the
8

---

Published as a conference paper at ICLR 2026
Table 2: Comparison of LEGACY with uniform QSGD training ResNet9 on CIFAR 10.
Methods
Uniform QSGD Alistarh et al. 20117)
(2117)
LEGACY-E
LEGACY-L
Top-1 Accuracy
87.21
87.98
88.42
Avg. relative data volume
18.78%
18.76%
16.4%
computational overhead. For the epoch- basce approach, sending more data the beginning appears to balance out the aggressive communication towards the end, yielding similar throughput while leveraging the early training stages to achieve better accuracy.
5.3 COMPARISON WITH ADAPTIVE GRADIENT COMPRESSORS
We evaluate our approaches, B,, Es,, and Ss, Li... using Top-k in LEGACY against three state-of of-the- art adaptive compressors (Adacomp Chen et al. (2188). sariance-based compression Tsuzuuu et al.) 20188), and CAT Khirirat et al. (202I)) in terms of the trained model quality and the traming tume. As shown in Figures SaH our scheduler achieves higher accuracy at comparable data volumes. Although we are slower than AdaComp. which is threshold-base
and 2 faster than the uniform 'Tp-k and our strategies, we achieve a 12% accuracy gain while sending only 77MM more data; see Figure 5c Variance-based compression requires access to per-sample gradients, which are not supported by most deep learning frameworks; obtaining these values using a batch size of one is extremely slow. We used OPACUS Yousefpour ct al. (2021) to get faster per-sample gradients. Still, it remains ~ 6x slower than our approaches with a 15% lower accuracy. CAT requires testing many values each iteration before choosing the sparsity, resulting in 11x slower performance, sending around 575Mb of data, and incurring 25% lower accuracy than our approaches. Our strategies are robust as they choose the compression ratios and control the total and ver-iteration data volume. In contrast, except for Accordion, other adaptive methods can neither be applied to different com- pressors nor provide an estimate of the data volume. We also found that at the core, these methods exhibit similar behavior to our strategies, confirming the effectiveness of our approach, which does not require additional computation. See the complexity results in D.4
5.4 QUANTIZATION AND LOW-RANK FACTORIZATION WITH LEGACY
QSGD Alistarh et al. 2017) experiment details and results. We train ResNet-9 on CIFAR-10
using 2 workers for 30 epochs. QSGD has one user-defined parameter 8 2 1, the quantization level. For uniform QSGD, we fix = 32. For LEGACY
introduce more granularity, we use 3 groups to represent three different training phases, the beginning of training (1-10 epoch, with s 64), the middle of training (11-20 epoch, with s = 32), and the end of training (21-30 epoch, with s = 16); and 4 groups to represent four distinct layer sizes, very small layer, S(< 600) are left uncompressed, medium-sized layers. M (< 100, 000 with s = 256). large layers, L (< 1, 000, 000, with s = 64) and huge layers. H (2 1, 000. 000. with s 16). Table 2 shows LEGACY-L renders 1.39% accuracy gain relative to uniform QSGD by sending about 12.67% less data.
PowerSGD Vogels et al. (2019) experiment details and results. We train ResNet-18 18 the CIFAR-100 dataset using? workers for 200 epochs with PowerSGD as the base compressor, and we compare LEGACY with two adaptive compressors, Accordion Agarwal et al. (2021a) and L-GreCo Markov et al. 2024). PowerSGD has one user-defined parameter, rank (r). The smaller the rank, the more aggressive the compression is. For uniform PowerSGD. we use = 3, for L-GreCo and Accordion, kept the same configuration as in their public implementation. We note that in those implementations, to improve accuracy, the authors used no compression for the first 1,000 itera- tions. This strategy leads to a higher volume of transmitted data. For LEGACY-E, we use 4 groups to represent 4 different training phases, the first quartile of training Q1 (1-50 epoch, with r = 6), the second quartile Q2 (51-100 epoch, with r 4), third quartile Q3 (101-150 epoch, with r 3), and the final quartile Q4 (150-200 epoch, with r 2); and for LEGACY-L (stands for layer-based) we use groups to represent distinct layer sizes, small layer, S(< 600) are left uncompressed, medium-sized layers, M (< 100, 000 with r = 8) large layers, L (< 1, 000, 000, with r = 3) and huge layers. H (2 1, 000, 000, with r = 2). Table 3 shows the results on PowerSGD combined with LEGACY. Uniform rank-3 PowerSGD transmits about 2.85% of the total data volume and achieves 74.58% test accuracy. All adaptive compressors outperform uniform rank-3 PowerSGD, albeit by smaller margin. Interestingly. both strategies in LEGACY outperform the adaptive compressors while only sending half of their communicated data volume; see Table 3 Moreover, in contrast to L- GreCo, LEGACY is compute-free; it does not need to calculate optimal parameters per layer at each call. Our results demonstrate that LEGACY is compatible with different compression paradigms, and show its flexibility and versatility in handling different compression techniques.
9

---

Published as a conference paper at ICLR 2026
Table 3: Comparison of LEGACY and adaptive compressors ResNet-18 18 training CIFAR-100 using PowerSGD as the base compressor. The arrows indicate the relative data-volume gain com- pared to the baseline PowerSGD, while the arrows indicate the performance gain compared to the baseline PowerSGD. By sending way less data compared to PowerSGI and other SOTA adaptive compressors, GrrrCO and Accordion, LEGACY achieves superior performance.
Metric
PowerSGD
L-GreCo
Accordion
LEGACY-E
LEGACY-L
Top-1 Acc.
74.58
75.23 (10.87%)
75.11 (10.71%)
75.55 (11.3%
75.21 (70.84%)
Avg. data volume
2.85%
2.19% (123.11%%
2.02% (129%)
1.1 1.11%((61%)
1.1 (16%%))))
Table 4: Training GPT-2 with LEGACY scheduler; validation loss the lower the better. The + arrows indicate the relative improvement compared to the baseline uniform Top-k.
Metric
Uniform Top-k
LEGACY-E
LEGACY-L.
Validation Loss
3.14
3.05 (42.87%)
3.01(14.14%)
Avg. relative data volume
5%
5%
5.02%
5.5 EVALUATING LEGACY ON GPT-2
In addition to evaluating LEGACY on classical benchmarks. which include ResNet-9, ResNet-50, and Transformer-Xe models trained on CIFAR-100, ImageNet- and WikiText-1033 103, we further evaluate LEGACY in a modern setting by training GPT-2 small (124M parameters) Radford et al. (2019) on the Open OeenWeeText corpus ( 4)G Gokaslan ( & Cohen (2019) using 2 A A100 For uniform Top-k, we fix the sparsification ratio at 5%, For LEGACY bayer- we introduce structural granularity by grouping layers by parameter count: small layers (< 000) are left uncompressed, medium layers (< 1, 000, 000) transmit the top 10%, large layers (< 10, 000, 000) transmit 5%, and the largest layers (2 10, 000, 000) transmit 4% of their updates. For LEGACY epoch-based the sparsification ratio varies across training phases: 10% for the first 10% of iterations, 7% for the next 10%, followed by 5% and 4% across the next two 30% segments, and 3% for the remainder. Table summarizes the resulting validation losses. Both LEGACY variants outperform the uniform Top-k while transmitting a similar amount of data, with the layer-based strategy yielding the best results.
5.6 ADDITIONAL BENCHMARKING AND DISCUSSIONS
Due to limited space, we perform diverse set of experiments in $ that demonstrate the efficacy, scalability, and ease of use of LEGACY in different scenarios. This Section serves guide to them. We use Random-k as the base compressor in LEGACY and show accuracy vs. data volume results in SD.2.1 Figure 6 D Table [ reports the average Top-1 test accuracy of ResNet9 and AlexNet on CIFAR 10, derived from 7 independent runs; the results are in agreement with $5.1 By using Top-k provide the model quality
as the base compressor (with and without eπror feedback) in LEGACY, vs. wall clock time results in ID.31 The model accuracy depends on the compressed gradients being transmitted, not on their transter speed; the results are generalizable across different bandwidths. In $D.333 we perform the scalability of LEGACY to 100 workers in a data center environment without constraining the network bandwidth. compression benefit (Xu et al. 2021a), compression overhead can be significant; in $D.3] show the efficacy of LEGACY in bandwidth-limited federated training. See the limitations and future direction in $
We also note that fast networks do not always harvest the
6 CONCLUSION
We introduce LEGACY, open-source, lightweight framework for dynamic gradient compression in distributed DNN training. In contrast to the compute-intene intensive adaptive compressors, LEGACY operates dynamically based on two simple factors-layee size and training phase-and simple yet efficient dynamic scheduler for any compressors. Our benchmarking of LEGACY using Top-k; Random-k, QSGD, and PowerSGID as base compressors show consistent performance gains compared the uniform compressors and five other state-of-the-art adaptive compressors across large and challenging datasets, including ImageNet- IK and OpenWebTexx Finally, in bandwidth- constrained federated training, we profile the efficacy and scalability of LEGACY and establish the need of simple, dynamic scheduler.
and provides a
A Acknowledgment. Aritra Dutta is partially supported by the Florida Department of Health Grant, AWD00007072, and the National Science Foundation Grant, 2321986. The authors gratefully ac- knowledge the support and computing resources from the Toubkal Supercomputer Kissami et al. 2025) at UM6P, Morocco.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Alessandro Achille, Matteo Rovere, and Stefano Soatto. Critical learning periods in deep networks. In Proc. of ICLR, 2019.
Saurabh Agarwal, Hongyi Wang, Kangwook Lee. Shivaram Venkataraman, and Dimitris S. Papail- jopoulos, Accordion: Adaptive gradient communication via critical learning regime identification. In MLSys, 2021a.
Saurabh Agarwal, Hongyi Wang, Shivaram Venkataraman, and Dimitris S. Papailiopoulos. On the utility of gradient compression in distributed training systems. CoRR, 2021b.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proc. of EMNLP. 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-effccieent SGD via gradient quantization and encoding. In Proc. of NeurlPS, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In Proc. of NeurIPS, 2018.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qxparse-local-SGD. Distributed SGD with quantization, sparsification, and local computations. In Proc. of NeurIPS, 2019.
El Houcine Bergou, Konstantin Pavlovich Burlachenko, Aritra Dutta, and Peter Richtárik. Person- alized federated learning with communication compression. Transactions on Machine Learning Research, 2023.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Arizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Proc. of ICMI., 2018.
Chia-Yo Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, and Kailash Gopalakr- ishnan. Adacomp: adaptive residual gradient compression for data-parallel distributed training.
Proc. of AAAI, 2018a.
Chia-Yo Yu Chen, Jiamin Ni. Songtao Lu, Xiaodong Cui, Pin-Yo Chen, Xiao Sun, et al. Scalecom: Scal- able sparsified gradient compression for communication-cffiiiic distributed training. In Proc. of NeurlPS, 2020a.
Mengqiang Chen, Zijie Yan, Jiangtao Ren, and Weigang Wu. Standard deviation based adaptive gradient compression for distributed deep learning. In IEEE/ACM CCGRID, 2020b.
Tianyi Chen, Georgios B. Giannakis, Tao Sun, and Wotao Yin. Lag: lazily aggregated gradient for communication-efficee distributed learning. Proc. of NeurlPS, 2018b.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In Proc. of CVPR, 2009.
Xiaoge Deng. Dongsheng Li, Tao Sun, and Xicheng Lu. Communication-efficieen distributed learn- ing via sparse and adaptive stochastic gradient. IEEE Transactions on Big Data, 2024.
Tim Dettmers. 8-bit approximations for parallelism in deep learning. ICLR, 2015.
Nikoli Dryden, Tim Moon, Sam Ade Jacobs, and Brian Van Essen. Communication quantization for data-parallel training of deep neural networks. In Proc. of MLHPC, 2016.
Aritra Dutta, El Houcine Bergou, Ahmed M. Abdelmoniem. Chen-Yu Yu Ho, Atal Narayan Sahu, Marco Canini, and Panos Kalnis. On the discrepancy between the theoretical analysis and prac- tical implementations of compressed communication for distributed deep learning. In Proc. of AAAI, 2020.
Negar Foroutan Eghlidi and Martin Jaggi. Sparse communication for training deep networks. arXiv preprint arXhv:2009.09271, 2020.
gloo. Gloo: Cowlective communicatioon library with various primitives for multi-mann machine training.
Aaron Gokaslan and Vanya Cohen. Openwehtext corpus. http://Skyliont/ thhh. 1o/
OpeenWebTexttCorpus 2019.
11

---

Published as a conference paper at ICLR 2026
Aaron Gokaslan, Vanya Cohen, Ellie Pavlick, and Stefanie Tellex. Openwebtext corpus. 2019.
http:
Jinrong Guo, Wantao Liu, Wang Wang, Jizhong Han, Ruixuan Li, Yijun Lu, and Songlin Hu. Ac-
celerating distributed deep learning by adaptive gradient quantization. In ICASSP, 2020.
Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM
Trans. Interact. Intell. Syst., 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proc. of CVPR, 2016.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and trends in machine learning, 2021.
Sai Praneeth Karimireddy, Quentin Rebjock, Sehastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In Proc. of ICMI, 2019.
karpathy Andrej. nanogpt.
2023.
Sarit Khirirat, Sindri Magnússon, Arda Aytekin, and Mikael Johansson. A flexible framework for communication-efficentt machine learning. Proc. of AAAI, 2021.
Diederik P. Kingma and Jimmy Ba. ADAM: A Method for Stochastic Optimization. In Proc. of ICLR, 2015.
Imad Kissami, Robert Basmadjian, Othmane Chakir, and M Riduan Abid. Toubkal: high- performance supercomputer powering scientific research in africa. The Journal of Supercom- puting, 2025.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William Dally. Deep gradient compression: Re- ducing the communication bandwidth for distributed training. In Proc. of ICLR, 2018.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, In Proc. of ICLR, 2019,
Rongwei Lu, Jiajun Song, Bin Chen, Laizhong Cui, and Zhi Wang. DAGC: Data-aware adaptive gradient compression. In IEEE INFOCOM, 2023.
Peng Luo, F. Richard Yu, Jianyong Chen, Jianqiang Li, and Victor C. M. Leung. A novel adap- tive gradient compression scheme: Reducing the communication overhead for distributed deep learning in the internet of things. IEEE Internet of Things Journal, 2021.
Ilia Markov, Kaveh Alim, Elias Frantar, and Dan Alistarh. L-GreCo: Layerwise-adaptiv gradient compression for efficient data-parallel deep learning. In MISys, 2024.
Lin Meng, Yuzhong Sun, and Weimin Li. Near-linear scaling data parallel training with overlapping- aware gradient compression. In IEEE ICPADS, 2023.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In Proc. ICLR, 2017.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. Proc. of NeurlPS, 2020.
Yuki Miyauchi, Haruki Mori, Tetsuya Youkawa, Kazuki Yamada, Shintato Izumi, Masahiko Yoshi- moto, Hiroshi Kawaguchi, and Atsuki Inoue. Layer skip learning using LARS variables for 39% faster conversion time and lower bandwidth. In ICECS, 2018.
NCCL. NCCL: NVIDIA Collective Communication Library. https://developer..niiii
Com/ |ccl
Yuri Nesterov. Gradient methods for minimizing composite functions. Mathematical Programming, 2013.
12

---

Published as a conference paper at ICLR 2026
Nvidia. Nvidia
deep
learning
examples.
https://gitub..omm/
Deeplearninggxxmplees
PyTorch. Pytorch examples. httppp/:/ggihhu...co////rrrrrrea
Linping Qu, Shenghui Song, and Chi-Ying Tsui. FedAQ: Communication-effiiene federated edge
learning via joint uplink and downlink adaptive quantization. arXiv preprint urXiv:2406. 18156, 2024.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Πya Sutskever. Language models are unsupervised multitask learners. 2019.
Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematical Statistics, 1951.
Mengzhe Ruan, Guangfeng Yan, Yuanzhang Xiao, Linqi Song, and Weitao Xu. Adaptive Top-K in SGD for communication-effiieenn distributed learning. In IEEE GLOOBECMM, 2023.
Atal Narayan Sahu, Aritra Dutta, Ahmed M. Abdelmoniem, Trambak Banerjee, Marco Canini, and Panos Kalnis. Rethinking gradient sparsification as total error minimization. In Proc. of NeurlPS, 2021.
Shaohuai Shi, Zhenheng Tang, Qiang Wang, Kaiyong Zhao, and Xiaowen Chu. Layer-wise adaptive gradient sparsification for distributed deep learning with convergence guarantees. In Proc. of ECAI, 2020.
Sebastian U Stich and Sai Praneeth Karimireddy. The eroo-feedback framework: Sgd with delayed gradients. Journal of Machine Learning Research, 2020.
Sebastian U Stich, Jean- -an-tttt Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Proc. of NeurlPS, 2018.
N. Strom. Scalable distributed DNN training using commodity GPU cloud computing. In Proc. of INTERSPEECH, 2015.
Guangyu Sun, Matias Mendieta, Aritra Dutta, Xin Li, and Chen Chen. Towards multi-modal trans- formers in federated learning. In Proc. of ECCV, 2024.
Yusuke Tsuzuku, Hiroto Imachi, and Takuya Akiba. Variance-based gradient compression for effi- cient distributed deep learning. In Proc. of ICLR, 2018.
Thijs Vogels, Sai Praneeth Reddy Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Proc. of NeurlPS, 2019.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication--fficienn learning via atomic sparsification. In Proc. of NeurIPS. 2018.
Hui-Po Wang, Sebastian Stich, Yang He, and Mario Fritz. ProgFed: Effective, communication, and computation efficient federated learning by progressive training. In Proc. of ICML, 2022.
Yiding Wang, Decang Sun, Kai Chen, Fan Lai, and Mosharaf Chowdhury. Egeria: Efficient dnn training with knowledge-guidee layer freezing. In Proc. of EuroSys, 2023.
Zeqin Wang, Qingyang Duan, Yuedong Xu, and Liang Zhang. An efficient handwidth-adaptii gra- dient compression algorithm for distributed training of deep neural networks. Journal of Systems Architecture, 2024.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. Proc. of NeurIPS, 2017.
Arissa Wongpanich, Hieu Pham, James Demmel, Mingxing Tan, Quoc Le, Yang You, and Sameer Kumar. Training efficientnets at supercomputer scale: 83% imagenet top-1 accuracy in one hour. In IEEE IPDPSW, 2021.
Jihao Xin, Ivan Ilin, Shunkang Zhang, Marco Canini, and Peter Richtárik. Kimad: Adaptive gradient compression with bandwidth awareness. In DistributedMI, 2023.
13

---

Published as a conference paper at ICLR 2026
Hang Xu, Chen- Yu Ho, Ahmed M. Abdelmoniem, Aritra Dutta, El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, and Panos Kalnis. Grace: compressed communication framework for distributed machine learning. In IEEE ICDCS, 2021a.
Hang Xu, Kelly Kostopoulou, Aritra Dutta, Xin Li, Alexandros Ntoulas, and Panos Kalnis. Deepre- duce: A sparse-tensor communication framework for federated deep learning. Proc. of NeurlPS, 2021b.
Yang You, Zhao Zhang, Cho-Jui Hsieh, James Demmel, and Kurt Keutzer. Imagenet training in minutes. In Proc. of ICPP, 2018.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. In Proc. of ICLR, 2020.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, et al. Opacus: User-friendly differential privacy library in pytorch. In Proc. of NewrlPS, 2021.
Mingchao Yu, Zhifeng Lin, Krishna Narra, Songze Li, Youjie Li, Nam Sung Kim, Alexander G. Schwing, Murali Annavaram, and Salman Avestimehr. Gradiveq: Vector quantization for bandwidth-effiiient gradient aggregation in distributed CNN training. In Proc. NeurlPS, 2018.
Hao Zhang, Tingting Wu, Zhifeng Ma, Feng Li, and Jie Liu. Dynamic layer-wise sparsification for distributed deep learning. Future Generation Computer Systems, 2023a.
Jingzhao Zhang, Haochuan Li, Suvrit Sra, and Ali Jadbabaie. Neural network weights do not con-
verge to stationary points: An invariant measure perspective. In Proc. ICMI, 2022.
Lin Zhang, Longteng Zhang, Shaohuai Shi, Xiaowen Chu, and Bo Li. Evaluation and optimization of gradient compression for distributed deep learning. In IEEE ICDCS, 2023b.
14

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
1.1
Related work and background
2
Designing dynamic compressor
2.1
Insight through the lens of the compressed GD
2.2 A dynamic compressor scheduler
3
System architecture, hyperparameter choice, LEGACY Variants
Convergence guarantee
5
Benchmarking and evalutaion
5.1
Model quality transmitted data volume
5.2
Model quality vs. training throughput
5.3
Comparison with adaptive gradient compressors
5.4
Quantization and Low-rank factorization with LEGACY
5.5
Evaluating LEGACY on GPT-2
10
5.6
Additional benchmarking and discussions
10
6
Conclusion
10
Related work
16
B Theoretical results
17
B.I Assumptions
17
B.I.I Inequalities used
18
B.2
Convergence of GD
18
B.2.1
Convergence of GD on strongly convex functions
19
B.2.2
Convergence of GD on nonconvex functions with PL condition
19
B.3
Convergence proofs for nonconvex distributed SGD
20
B.3.1
Unbiased compressors
20
B.3.2 Biased compressors
22
Variants of LEGACY
24
Simple LEGACY
25
C.I.I
Mixed approach
25
C.1.2
Numerical results of S S-LEGACY-M
26
C.1.3 Strategy II: Example
26
D Addendum to experimental evaluations
26
D.I
Reproducibility
26
D.2
LEGACY on different compression classes
27
15

---

Published as a conference paper at ICLR 2026
D.2.1
Random-k in LEGACY as base compressor
27
D.3
Scalability of LEGACY
28
D.3.1
LEGACY on constrained environments
28
D.3.2
Federated training of ResNet-18 on CIFAR
29
D.3.3
Scaling LEGACY to 100 Workers in a Data Center
30
D.4 Time and space complexity of LEGACY and other adaptive compressors
30
L Limitation and future direction
31
Ethics statement and potential negative impact
33
APPENDIX
Organization. We organized the Appendix follows: In Section detail the related work. In
Section B we quote the general assumptions and provide detailed proofs of our theoretical results quoted in the main paper. We present the system architecture tion, different variants of LEGACY, including simplified LEGACY in Section C Section D discusses additional numerical results. Finally, in Section directions.
LEGACY, hyperparameter selee-
we discuss the limitations and future research
A RELATED WORK
Gradient compression techniques are broadly divided into four classes: quantization (Dettmers)
2013
Alistarh et al. 2017; Wen et al. 2017 Bernstein et al. 2018), sparsification (Aji Heaheed
2017
Stich et al. 2018 Alistarh et all (2018). low-rank (Wang et al. 2018 8, Yu et al. 2018 Vogels
al
2019). and hybrid (Strom 2013 Dryden al. 2016 Basu al (2119).
Adaptive compression. L-Greco Markov et al. (2024) utilizes dynamic programming to determine the optimal compression parameter for each layer under a fixed communication budget. Kimad Xin et al. (2023) and ACE WCnna al. (2024) dynamically monitors network bandwidth instead of using fixed communication budget; Khirrir al. (2021) employs communication cost model to optimize compression efficiency per communicated bit at each iteration Achille et al. (2019) empha- sizes model sensitivity in a certain period, Accordion Agarwal et al. (202 la) amm to Identify and respond to this regime by applying lighter compression during the eritiaal periods. Conversely, LAGS- Shi et al. 2020), and COVAP COve et al. (2023) take different approach by adjusting the compression level overlap gradient communications with computational tasks.
Among less compute-intensive strategics, Luo et al. (02T decides the compression based on a probability that depends on the gradient value and the layer size. SDAGC [Chnn et al. (2020)) ad- justs thresholds based on the standard deviation of gradients of each layer. AdaComp Chen et al. (2018a) is similar to the threshold compressor, divides gradient components into bins and selects sigmifiantt components relative the maximum value each bin. Guo al. (2020) determines the quantization level based on the gradient's s arean-to-standare deviation ratio; DAGC et al. (2023) assigns compression ratios to workers based on the data distribution. DLS DLS el al. (2023a) tries to find a layer-wise Top-k compression level. AdapTop-k Ruan et al. (2023) sends more components at the beginning and end of the training and fewer components the middle. Chen et al. (2018b);
Wang et al. (2022] 2023); Deng et al. (2024) suggest freezing or skipping some layers based on their deviation from the previous lerration or by evaluating the importance of the learning of each layer. It can reduce communication and computation by avoiding the gradient computation for the first layers Miyauchi et al. (2018): Wang et al. (2022). Chen et al. (2020a): Qu et al. (2024) compress up and downlink communication.
Transition to bow-bandwitth network. Compute-intensive techniques such as CAT Khirirat et al. (221)) face performance trade-offs, particularly in fast network environments Agarwal al. (002Tb). such cases, using basic compressors might take longer than no compression baselines Eghltdi & Jaggi (2020): Xu et al. (2021a): Zhang et al. (203bb). The scenario changes in federated learning (FL) (Karouz et a JL.]2022pp 2 et al. 2021bb Bergou et al. 2023 Sun et al. 2024). where low-bandwidth heterogeneous network is de facto. Hence, compression becomes necessary, but employing complex adaptive compressors may reduce the data-saving advantages in FI., especially
16

---

Published as a conference paper at ICLR 2026
when weaker nodes involved. As result, need to focus lightweight and simple principles achieve adaptive compression.
B THEORETICAL RESULTS
This section complements Sections and in the main paper. We start with the Assumptions used in the main paper.
B.1 ASSUMPTIONS
We make the following general assumptions.
Assumption 1. (Smoothness) The loss function fo Rd - R at each node [m] is L-smooth, i.e. f(()) [x) (Vf((x), x²) + 1/2 [ly -yy-x x|I² for all x, E R.d.
Assumption (j-strongly convex) The loss function fs Rd + at each node i E [n] is p- strongly convex, i.e. f((y) 2 fa(x) + (V x) + 2/4 flly x11 for all x, y E Rd. Remark 1. The above two assumptions together imply that F L-smooth and p-strongly convex.
Assumption 3. (Global minimum) There exists z. such that, F(z.)= S F(x), all æ R
Assumption 4. Yollykk-oojsiiwice Condition) The function F satisfies Polyak- Lojasiewissiiiicz (PL) condition with parameter μ 2 0 if for all x E Rd the following holds:
VF(x) 2 (F(()) F.).
Assumption 5. ((M, o²) bounded noise) There exist constants M. 2 2 0, such that for all xt E Fd the stochastic noise, Ei, follows
E| a S MI/V/ll + o
Remark 2. The above implies, Elll | S. (M + ft,ll +
Assumption 6. (Bounded variance of gradients) There exist constants A, B 2 such that, for all E R2d, the variance of gradients among nodes follow
Eien [V((z) -V(())-V((())) 2A(F(x)) F.)+ B.
We adopt a few assumptions than the previously stated ones for biased compressors. First, consider (C,4 (2) bounded similarity assumption on the variance of the gradients among the workers This Assumption is stronger than Assumption 6,, but similar assumption was
in Assumption proposed in Sahu et al. (2021), and we rely it for algebraic purposes proving the convergence for the general case.
Assumption 7. ((C,(2) bounded similarity) The variance of gradients among workers is bounded, i.e., there exist constants, C,ç 2 such that, [I fz)) F= < C[]VF(=)]++ for all x E Rdd
We impose an extra assumption on the expected direction of the compressed gradient for biased compressors. A similar assumption was made in Dutta et al. (2020) and several classic biased compressors, such as Top-k, follow it.
Assumption 8. (Descent property of the compressed stochastic gradient) Let C, be a biased 8- compressor such that Dn (g 9. There exists 0 < S. 2 and 3 > 0 such that
g VEIVE Z VEI -R,
where a small scalar residual that may appear due to the numerical inexactness of some oper- ators or other computational overheads.
Remark The above assumption general, and one can characterize many compressors with this, For instance, for Top-k, we have a 2, generality, one can consider a = 2, 3 =
For simplicity and without loss of and R = O.
d and
Assumption 9, There exists G such that, F. for all & ET).
17

---

Published as a conference paper at ICLR 2026
B.1.1 INEQUALITIES USED
1. If aaa Ra then relaxed version of Peter-Paul inequality:
|a + bll - 2||a|| + 2||b|
(4)
2. If a, E Rd then the following holds:
1
2/a, b) S 2|1a|| +
2 1101
(5)
3. For 21,..., In E Rd we have:
x
|.,|
(6)
4. If is a random variable then:
B|X|1² = ||[[I]1| + E[X]1|]
Lemma 4. Let (() :R TRd be 6-compressor.
(i) IfC(g) is unbiased then We have B||C())|I - (2 8 8)lla11?
(ii) If (gg) is biased then El((()) < 2(2 - 8)||91??.
Proof. (i) Recall for unbiased d-compressors, we have Elg - C(g) < (1 l)gl. Since
B(C(g) g, from equation we have,
[1 By equation Ellg - + -
= (2 5) ||ا|
(ii) On the other hand, for biased d-compressors, we have,
Ellg- - By equation 4
B|
2E
2(2 2((2-))llll
Lemma 5. Let F follow Assumption
Then we have for all t 2 0.
1 - - B |
(8)
T
Proof. The proof follows from the fact that 1 Σ 2 E. IVA. and P.
VA VRI2
Σ Sú, for all / 0. Therefore,
V f
Vh. - +
VV VF |VA
n
By Assumption
D <
2A(F. F.) + B 1
Hence the result.
B.2 CONVERGENCE OF GD
This section provides the convergence proofs GD on strongly convex and nonconvex functions with PL. conditions given in Lemma
and and Lemma
18

---

Published as a conference paper at ICLR 2026
B.2.1 CONVERGENCE OF GD ON STRONGLY CONVEX FUNCTIONS
Lemma 1. (Gradient descent with unbiased compressor) Let F follow Assumptions | and 2 Then with stepsize S (2-8.)1 the sequence of iterates, {2a )120 of compressed GD updates satisfy
Ec, (1 xr.1²)) < (1 2pm + 1/ 2L - 5z)) 1 x.112.
(9)
Proof. From the GD update in equation 2 we have
1 2, Ir Da (VF(()))
Squaring both sides and expanding, we have
| x.1l² = ||=, - 2.11² 2 2 (VF.)* (x, (01-x,) x.) (
By taking expectation on the randomness of the compressors C. we get:
Ec, (1+=+11 2²1
| 2211 F (r) 2x) + 17 Ec, (VV)))
By Assumption P
||,, -
x x,11 11 21/ (F. Ft) - -1yl|se - 1=
+nf VFll?
By Assumption 1
112e - 2.2 11 + 2m (F. Fi) - wull 2.11
+2n 8.) - -F.)
(1 - (1- x.11² + 2n (nL(2 5t) 1) (Fi - F.)
By Assumption 0
(1 - |n)ll - x, 112 + pm (n/ - 6,) 1) ||,, - =..1
IA
(1 2nm + 1f2 6:)) | - x.1l
This completes the proof.
B.2.2 CONVERGENCE OF GD ON NONCONVEX FUNCTIONS WITH PI CONDITION
Lemma 2. (Gradient descent with unbiased compressor) Let F follow Assumptions 7 and 4 Then with stepsize 1) I, the sequence of iterates, {11):20 of compressed GD updates satisfy
8.p1
Ro.(Fit1) F. S
1
(F: - F.)
(10)
L
Proof. Using the T-smoothness of F as in Assumption 1 we have
F
F + (VF,, 31411 - 2i) + || -x 12112
By equation
F. - VVF, ((F(x))) T2 (c((F(())))1
By taking the expectation on the randomness of C, and by using the GD updates from equation
we have
1
Ec, (Ft+1)
F /F.11
Bc, (C
2L
By Lemma 4
1
2-
6e
|/FF11
L
2L
Fi
Frl2
2L
By Assumption 3
8
2u(FF F.).
2L
Finally, subtracting F, from both sides, we get
Ec, (F++1) F. 5 (1 (1-
8r
71 (F.-F.).
This completes the proof.
19

---

Published as a conference paper at ICLR 2026
B.3 CONVERGENCE PROOFS FOR NONCONVEX DISTRIBUTED SGD
In this section, we provide the convergence proofs of compressed distributed SGD on nonconvex functions, We start with the key inequalities used in our proofs.
B.3.1 UNBIASED COMPRESSORS
Lemma 3. (Compression variance) Let Ct be unbiased oy-compressor for all E [T], and let follow Assumption 0 and the stochastic noise follow Assumption S Then we have
)|
E
Colgr.) - -E Vie
(11)
1 n ((1 (11-60 (2A F.)+ + /VF.)) + (2 5c)o²
Proof. We note that the compression operator, C, and the stochastic noise, E, are independent. Therefore, while taking expectation on the randomness of the compression operator, C., we condition on the other source of randomness, and vice versa. We use Ec, to denote the expectation taken on the randomness of the compression operator, Ct, and conditioned other sources of randomness. So, taking expectation on the randomness of the compression operator, Ct we have
n
Ee,
Ca(ge,)) - Vii
Be, (==
1
Ec, (or,)) - Vfclel2++
2
Σ
Vf.. Vfza)
n²
n²
1=1
B1.e Veettee
1
Ec, (C(,)))))) - 9t,t E1,ell
Vians Vszaa
n1
n²
itj
Bc, (=)
[c,1IC((99n)) 01.el12 + Ec. 1Ex.e11
+ Σ
2
(gh, - Vheisghh Vfne)
n²
nr
i=1
itj
Σ
((1
11 11E,,e11)) + n
Σ
(gt.
Vf.,,9ff - fz,)).
n
1=1
ifj
Taking expectation conditioned on zz, and by using the tower property expectation, we get
17] late
E
Co(aea)) - Σ ViL
E.) + BBll (111 (())))))
n
The equality holds as E(g.,lx))) = fu. and E(g,a(=.)) Assumption write the above expression as
Vf for all # j.ú,j E [m]. By using
((1- E,) |/| 11
-
n
Σ
((1 6M 1)1 + +1 -0)0 M 1
2 +02)
By Lemma 5
1 ((1 6. + M) F.) + || + 1 -8.)02
n
Hence the result.
Based the previous Lemma, the next lemma quantifies the quantity E Σ. ((
20

---

Published as a conference paper at ICLR 2026
Lemma 6. Let Ct be unbiased be-compresoor for all t [T). Let F follow Assumptions 6 and the stochastic noise follow Assumption 5 Then
24 (F. F.) +
1+ 86 |V
Bßc +
2 - de
E
E Co
o² (12))
where :=:= 6M +1) M.
Proof.
Taking expectation on the randomness of the compression operator, C., we have
Ec,
= Ec. | Σ
Cg(gr VF, + VF
1=1
i=1
Ee,
Σ C(
VF.
+ +11F.111 +(2 Σ Di.t VF, VF.)
By Leimaa 8
((1 (M + +1) + M) (2A(F) F.) + +B+ (V + (2 8,)0²
"
+IVF:11 + + Σ 9..t VF. VF).
(13)
Finally, we note that xx+) = fr. By using the tower property of expectation. we denote E >i Ce(gr.))2 E(Ec, 1/4 H (o...)))))rr). Taken together, from equation 13 we have
E Σ (
< 1 ((L - 6M +)+ (2A(F: F.) B [VF 1 -2)00- + |/E2/
n
Hence the result.
Finally, we can quote the non-convex descent lemma for compressed distributed SGD.
Lemma 7. (Non-convex descent lemma for unbiased compressors) Let Assumptions 7 and hold, and let C, be unbiased ò to-ompressor for all t [T]. Then
(1+
F.) - 71 (1
Latt
Lap33
E(F++1) F. S
(B(F.)
E F1
n
n
Lit
B3
2 8
+
+
0²
2
n
n
Proof. By using the T-smoothness of F we have
FH1S F. (V FVF,, II-1 FV-1 - 2z) + || 2z 2111?
By using the update rule F+41
T4 Th Σ (gr.)) the above becomes
F41S F. - FV, Pt C
C(g,,))
Ln - Co(gn.))
(14)
Taking expectation with respect to the randomness of C, on the above expression for all E [T], we find
Ec, (F+1)s F - (VF,, Ti a Ein19a)) + Lnd Ee, E. C.
Taking expectation conditioned on It. we have
Lo E 2
B(F(41/z)
< -
11 [ Cc(o,.))) )
t=1
21

---

Published as a conference paper at ICLR 2026
By using Lemma the above, find
B(F+41/04)
Lni
2.3 (Fr F.)
|+ &e (1+
Bgg +
(2-
6c 02)
2
Taking the final expectation, by using the tower property of expectation, and rearranging the terms, have
(1+
&
1
Lite
Lm
B(F++1) - F. S
(B(F)) - F.)) - 71
E1 V Vrll?
71
2
11
Li
B3c
2 8z
+
+
0²
(15)
2
n
Hence the result.
B.3.2 BIASED COMPRESSORS
Lemma 8. Let Ct be biased 6-compressors for all I [T], and let F follow Assumption 7 and the stochastic noise follow Assumption [5] Then have
E 1 Σ 11 21
< 322-6:((M + 1)(C + 1II + 2(2 5.) ((M + 1)ç² + +
Proof. Taking expectation, Ec, on Em (g we have
Ee, - Σ ((
By equation g
Ec, (9.
By Lemma
2(2 6c)
1=1
By Assumption
2(2 (M + +1)
Σ
V fr.ll 2222- o2)o
n
1=1
2(2 (M + 1)
1
Σ
fV. VF + - 1) 2(( -8,)
n
By Assumption
7
2(2 (M + I) + + + 2(2 - (M +.][M+1)|VV/.)) 1) + 2(2 6.)0².
Now, by taking the conditional expectation on I; and using Lemma 5
we obtain the result.
Lemma 9. (Non-convex descent lemma for biased compressors) Let Assumptions and let C2 be biased d-compressor for all E [I'] that follows Assumption 8 Then
5 and hold,
VF. T. - 5:)(M 1)(C + 1)
S E(F: F(-1)
+In 56) (o² (M +){²) n. R.
Proof. By using the T-smoothness of F, and using the update rule x441 - Jt 2t Σx C.(ox) have from equation 14
Lak 11
F < F (V. de Σ C((g,)) +
Σ C.
2
22

---

Published as a conference paper at ICLR 2026
Taking expectation with respect to the randomness of VF, the above expression for all t [T] and by using Assumption g
we find
Lak TE
B(F++1)
Fi -
B + + R +
| Σ C.
2
Taking expectation conditioned on Zt. we have
L E
EE(F+11 I
Fi V + T. +
11
Co
Now using Lemma ((F
8 we get
F. Bn 7
+ Lig ((2 (M + () C)II + (2-6,) 6.) ((M 1)ς² +o²))
Taking the final expectation, by using the tower property of expectation, and rearranging the terms, we have the result.
NONCONVEX CONVERGENCE RESULTS
The next Lemma is instrumental in proving the nonconvex convergence of distributed SGD with 5-compressors.
Lemma 10. Mishchenko et al. 2220 Let for t T the the following holds:
P++1 S (1 + a)p: by: + c,
(16)
where {pelT- and {ge T are non-negative sequences and a, b, 2 are constants. Then
(1 a))
min
q:
Po
(17)
bT
Proof. Dividing both sides of equation have
16 by + a) and summing from / 0, 1..
T
T
T
(1+
a)r
Pt
+1+ a)
(1 + ta)++1>
1=
t=0
t=0
which after rearranging
b
Σ
(1 a1+4)++ 4: S Po
(1 + a) PT+1
(1 a)
Noting E (I+a)e+1 S
-1 1
1
we have
T
Po
min t=0,1,--7
qt
(1 + a)
(1 + a)
4:
S
b ab"
+
(18)
Hence the result.
Finally, we are set to prove Theorem
Theorem 1. (Nonconvex convergence) (i) (Unbiased) Let Assumptions and let C, be unbiased 61-compressor for all t [T]. For a fixed stepsize T min
and hold,
S
AL(2M+1) n
we have:
LI
Ln (B(2M + +1) 20 (Fo F.)+
V 1-1
min
< Tn
Lg
1n{2M+1) 2n L7
12
(ii) (Biased) Let Assumptions
5 and hold, and let C. be biased 5-compressors for all t E [T] that follow Assumption and For stepsize n L:3-,xM4411++100= we
3
have: min E
(Fo F.) T
o, where 2L (L+(0)+ + 3.4
Jt
and
BA
A = (1 402--61MMM
23

---

Published as a conference paper at ICLR 2026
Proof. (i) From Lemma 7
we have
ALaE Be
Latt
Lape.
B(F++1) - F* s
1
(B()t) - F.) - -tt
E V Fil1
2
Lak
B
(2-
81 0²
+
2
Alap(2 b
The above incquality satisfies the condition of equation 16 with a (1-2 Ln Ln(2M+1)
Tap
B(2M+1)
Therefore, we obtain
2
(21 T 1
Ly B(2M+1)
20
min 1-
E V
n
(Fo F.) +
(19)
Tn
1
La Ln(2M+11
7)
Ln 2
Ln(2M+1]
Using that x-1 S exp.r and with S
AL(2M+1)
in the first term of the RHS of equation 19
we get
1 AL + 1)
T
AL 1)T
S
exp
S <xx((1) - 3.
n
Finally, using the above in the inequality
19
have
Ln (B(2M + 1) + 20
min E VF(x)]]
(Fo F.) +
Tn
Ln
2n
bn
Ln(2M+1)
12
Hence the result.
(ii) With |VFl & G from Assumption 9 we have
7h 3E VF, 1 L2 6. + D)(C + 1)G2
S EFF FFF (2- (o² + (M + +)) +n.
B
Consider Ná 1 < L(2 L[2-)(M+)CC++]C>> Then the above inequality reduces to
8
E(F. Fit1) + Ln(2 6,) (o² (M + 1)(3)
E VFF v
+
nBA
3A
3A
By unrolling the recurrence relation, we have
T-1
Fo E(F) Ln (o² + (M 1)(2)
T-1
R
Σ
VII <
Σ
(2
56)
+
T 1=
Tn3A
T3A
3A
t=
With 0 < 6, < 1 we get (also, using Assumption 3
T-1
Fo-F. F.
2L (a² + (M + +))2)
R
EIVEI
<
+
T
TrBAA
BA
3A
1=
which further reduces
Fg F.
2Lm (0² + (M + 1){3)
R
E
V <
+
10 T-1
Tn3A
3A
3.
Hence the proof.
C VARIANTS OF LEGACY
To simplify the selection of byperparameters used in LEGACY (())² for compression levels), we propose simplified version of LEGACY in C.1 called Simple-LEGACY or S-LEGACY.
1 for thresholds and {8, 1
24

---

Published as a conference paper at ICLR 2026
C.I SIMPLE LEGACY
We note that there no recipe for choosing compression parameters. The choice of compression parameters depends on multiple factors such as the dataset used, DNN model architecture, network topology, network bandwidth, and many more; see Xu et al. (222 and references therein. In contrast to compute-heae
state-of-the-ar adaptive compressors, LEGACY is based on two simple propositions: (a) the layer size of the DNNs influences in choosing how much one needs compress, smaller layers have insignificant effect compared to large layers, and (b) the training phase of the DNNs can be a critical contributor in the adaptive compressor design, the end training phase can tolerate severe compression without any accuracy lost. While the layer sizes can be determined and grouped based on their relative sizes, the only rule for choosing compression parameters based on the training phase is to choose decrease compression parameters over iterations; $5.4 validates this on QSGD and PowerSGD.
To simplify the selection of hyperparameters used in LEGACY ((),)² i=] for thresholds and V6 for compression levels), we proposed a simplified version called S-LEGACY. This version requires only two hyperparameters for the epoch or layer-based approach and three for the mixed approach. That is, S-LEGACY-E requires only a default compression parameter on and the number of training phases n; S-LEGACY-L. requires 6n and a decrease ratio s; S-LEGACY-M (stands for using both layer and epoch-based) requires 6,, nt, and s.
S-LEGACY determines grouping and compression parameters based on the specified hyperparame- ters and two additional functions that depend on the compressors used during training: (i) (o) computes or estimates the communicated data volume for given compression parameter ó; and (ii) (v) determines or estimates the compression parameter that produces a specified data volume v.
Grouping. In LEGACY, we used (Mr)== to define training phases or layer groups In S-LEGACY, we simplify this grouping as follows:
S-LEGACY-E. The training duration T' is uniformly divided into n phases. Group Ii consists of iterations within the interval ((i 1) "" "
S-LEGACY-L. Layers are grouped by order of magnitude. Group gi consists of layers L satisfying 100 | < 100', where [L] denotes the layer size.
Compression parameters. S-LEGACY eliminates the need to set the compression parameters for each group manually. Instead, these parameters are automatically calculated to ensure similar communicated data volume as the default compression parameter 8.., while following the principles established by LEGACY.
S-LEGACY-E. First, compute the uniform data volume Vn, that would be communicated with 5n- For group gi, the compression parameter is 6, vol (Vi). where V; is the data volume V/2 1.5 i-1
R-1 Vu- This ensures progressively aggressive compression across training phases, starting at 1.5V, (first phase) and ending at 0.5V, (last phase).
S-LEGACY-L. Compress the largest layer group 9p more aggressively than s,: 6p Rd vol, ((1 - s) vol)(,.)), where S 5% the decrease ratio, and vol,(6) represents the data vol- ume of the group 9p when compressed with Distribute the saved volume s vo,,) uniformly across the other groups: = =ol,"' (مr (ol,( v6l) Since the groups are ordered by magnitude, this adjustment applies lighter compression to smaller groups and progressively more aggressive compression to larger groups, ensuring that 5, is not exceeded except for Ip-
C.I.1 MIXED APPROACH
The mixed approach, S-LEGACY-M, combines S-LEGACY-L and S-LEGACY-E, requiring the previ- ously defined parameters: the default compression parameter 8,, the number of training phases n, and the decrease ratio s. S-LEGACY-M begins by applying S-LEGACY-E to partition the training period, then uses S-LEGACY-L determine compression parameters for each layer group, with the compression parameter 6, from S-LEGACY-E for the current phase serving as the default compression parameter. Use the epoch-based method (S-LEGACY-E) to divide the training period into n phases and compute {o. Then for each phase i, use ò as the default compression parameter for the layer-based method (S-LEGACY-L.) to calculate compression parameters for layer groups within that phase; results in C.1.2
25

---

Published as a conference paper at ICLR 2026
Table 5: Accuracy for S-LEGACY methods.
Network
Method
Uniform
S-LEGACY-L.
S-LEGACY-E
S-LEGACY-M
AlexNet
Top-k
78.1
79.3
78.6
81.1
Random-k
67.7
72.4
71.13
72.6
ResNety
Top-k
85.86
86.7
87.52
88.03
Random-k
77.58
81.8
81.9
82.04
ResNet18
Top-k
64.4
66.2
66.18
66.5
Random-k
50.4
51.9
52.2
52.1
C.1.2 NUMERICAL RESULTS OF S-LEGACY-M
We train AlexNet and ResNet9 CIFAR- 10 and ResNet18 CIFAR- 100 using two workers. We compare the uniform compression methods, Top-1% 1% and Random- 1%, with S-LEGACY approaches using n 5 phases and decrease ratio of 8 5%.
The results in Table [
demonstrate that the simplified S-LEGACY approaches outperform uniform compression methods and alleviate the burden of manually selecting the hyperparameters required by LEGACY.
C.1.3 STRATEGY II: EXAMPLE
To illustrate this approach, consider using a sparsifier with a baseline sparsity of 1%. Instead of applying uniform compression, we divide layers into quartiles: QI (largest 25%) to Q4 (smallest 25%), and slightly reduce Q1's sparsity to 0.99%, reallocating the saved compression budget across the other quartiles. In AlexNet, this small adjustment enables Q2 be compressed 8.4%, Q3 37.6%, and Q4 at 74.2%. Similarly, in ResNet18, with Q1 compressed 0.99%, Q4 receives a full 100%, meaning all gradients are transmitted uncompressed. Though the difference in QI is minimal, the resulting improvement for smaller layers is substantial, justifying the observed gains in model performance.
Another angle in understanding compression across layers is from the perspective of communicated data volume. Let divide the layers into groups: small and large. Let S represent the total size of the small layers (e.g., layers with fewer than 10st elements) and L. represent the total size of the large layers (e.g., layers with more than 10 elements). We assume S < L. E.g., in our experiments, the ratio, s+1. is 0.9996, 0.987, and 0.997 for Transformer, ResNet-9, and AlexNet, respectively.
We aim select & and 5; such that the overall data volume remains consistent with that obtained using uniform compression, 8, throughout the training. Let the compressed data volume when using a uniform compression be Vuniform and layer-based LEGACY (when using d, on the small layers and 6 on the large layers) be Vdynamic-
We have Vuniform & 8( + S) and Vaynamic X 5, 8,5. Therefore, to keep the same overall data volume, Vuniform Vdynamier implies 8(L+ R 6, + 8,S, that is, 8L v 8, + (6, d)S. Based on assumption. S < L, together with 6; 8 < 8, < we obtain 5 zs 6j. (6, 5) 0. We do not have any explicit assumption on 8,, so we can choose it close to 1, that is, easy compression. We postulate, it is better to compress the large layers and leave the small layers uncompressed.
D ADDENDUM TO EXPERIMENTAL EVALUATIONS
In this section, we provide additional experimental details and benchmarking results, which we were unable to discuss in the main paper due to limited space.
D.1 REPRODUCIBILITY
We implement the sparsifiers in PyTorch. Tables 9 [ 12 E and 14 provide the experimen-
tal details for each of the tasks. We used the defaulT d hyperparameters provided in the mentioned repositories for each task.
We postulated that LEGACY can be used conjointly with any compression techniques designing its compute-free, adaptive counterpart. In this section, we provide additional experimental details and benchmarking results to demonstrate that LEGACY can be seamlessly integrated with other compression classes: sparsification (Random-k), quantization (QSGD Alistarh et al. (2017)). and
26

---

Published as a conference paper at ICLR 2026
Table 6: Summary of the benchmarks and quality metrics used in this work.
Training paramelers
Quality metrri
Bascline quality
Task
Model
Dataset
Optimizer
AlexNet
CIFAR-10 CIFAR 10
2,255,296
Accuracy
84.99%
SGD Robbins Monro
1951
Image
ResNet9
6,573,120
Accuracy
92.07%.
SGD Romoiss & Mtnnr
SGD
1931
Classification
ResNet18
CIFAR-100
11,220,132
Accurncy
73.43%
ResNet50
ImageNet
25,559.081
Accuracy
59.43%
SGD Robbins Mobro
Recommendation
NCF
Moviclens-20ng
31,832,577
95.53%
ADAM Kingma Ba
2015
Modelling
Language
Transfomer-XL.
WikiText-103
191,950,298
Perplexity
39.47
LAMB You et al.
2020
GPT-2 small
OpenWebieext
124,373,760
Validation loss
2.85
Adam Loshemor Honer
2019
Federated
Leurinng
ResNet18
CIFAR-10
11,173,962
Accuracy
85.37%
SGD-M Nesteroo 2013
Table Dataset and training configuration.
Dataset
Training
Name
Size
Workers used
Time (min)
Independent Runs Performed
CIFARI0 Krizhevsky et al. 2009)
160MB
5
CIFAR100 Krizhevsky et al 20099
160MB
20
15
ImageNet Dengg et al 2009)
140GB
2100
Movielens-20mm/Harree Konstan 2015
190MB
2
10
WikiText--03 Merity et al (0177)
500MB
190
WeenWeeTex 2019)
40GB
1440
low-rank factorization (PowerSGD Vogels et al. 2019)). These results, which could not cover in detail the main paper due to limited space, turther validate LEGACY's versatility across different compression approaches.
D.2 LEGACY ON DIFFERENT COMPRESSION CLASSES
In this Section, we show the efficacy of LEGACY on Random-k as the base compressor.
D.2.1 RANDOM-K IN LEGACY AS BASE COMPRESSOR
Following the contiguration described Section 5 we provide additional tests, using the Random- as the base compressor in LEGACY. Figure 6 displays the accuracy versus relative average data volume throughout training for AlexNet, ResNet-9, and Transformer-XI..
In Table 8
report the accuracy of ResNet-9 and AlexNet, including standard deviations ob- tained through independent runs using Top-k and Random-k as base compressors LEGACY. Top-k demonstrates superior performance relative to Random-k. The tests revealed comparable findings to those discussed Subsection [.1] further validating the importance small layers and the initial training phase in improving compression efficiency.
Table 8: Comparison of average compression ratios vs. mean accuracy with standard deviation
derived from runs.
ResNe19
AlexNet Average ratio
Method
Compression ratio
Average ratio
Accuracy
Accuracy
Baseline
N/A
100%
92.07 + 0.13
100%
84,98
0.34
Topk
0.1%
0.1%
75.72 +: 1.07
0.1%
65.53 +: 0.86
Topk-epoch
05.05 Eo.15
0.1%
73,65 + 0.16
0.1%
59.85 + 4,9
Topk-epach
Bo Eo.05
0.1%
79.18 + 0.26
0.1%
66.25 + 0.62
Topk-layer
L0.1
0.12%
82.94 + 0.79
0.13%
70.27 - 0.91
Randomk
0.1%
0.1%
50.04 1 0.8
0.1%
43.58 + 0.45
Randomk-laye layer
Sw.La
0.12%
68.67 + 0.53
0.13%
62.13 0.45
27

---

Published as a conference paper at ICLR 2026
Bice Bs
S1,55os BysEs Sykea
Sinka 5tokt Stakas
Saala Sylao Bps
Dc.ss
Oza
DcaEi BasEis
BoEi: base line
BacsEa
B:Gna
*
400
Accuracy
0.7
Accuracy
0.0
Perplexis beyleittyy
66
02
10
287
15
1F-
Rolative Aug. Volume
Relative Avg. Data Volume
Relative Aug. Data Valume
(a) AlexNet (CIFAR10)
(b) ResNet9 (CIFARIO)
(c) Transformer-Xi (wikitext- 103)
Figure 6: Liyer-size and training epoch dependent Random-k compression, where S5, L&, means small layers(s 10º) compressed with compression factor, 61 and large layers compressed with com- pression factor, 52, and B5, Es, denotes two-phase training, beginning phase (half of the total train- ing epoch) with compression factor, ò1 and ending phase with compression factor 82.
D.3 SCALABILITY LEGACY
We performed our previous experiments on high-performance GPUs in a data center, connected by a fast network, and consisting of a limited number of workers. To evaluate performance in more constrained environments, we now simulate scenarios with a larger number of workers and restricted resources.
D.3.1 LEGACY ON CONSTRAINED ENVIRONMENTS
Testbed and setup. We trained ResNet- 18 on CIFAR-10 using 50 workers, sharing Gbbs network bandwidth, with every worker operating on an Intel Xeon Platinum 8276 CPU instead of a GPU. In this part, we integrated error feedback (EF) in our tests; the implementation of EF is based on (ahu et al. (2021). We use Gloo AllGather for internodal communication. 7 the accuracy per wall clock time for 4100 seconds, which is the time required for compressors to complete 30 epochs. For the compression parameters of each method, we employed the following that all methods transmit (almost) equal average data volume:
Top-k: 1.7% uniform compression.
Accordion: Set low and high compression ratio to flow = 0.1% and khigh 10%, respec- tively, achieving an average compression ratio of 1.98%.
Top-k Epoch-based: The total training duration of 30 epochs was divided into four seg- ments: three segments of epochs each, followed by a final segment of 7 epochs. Compres- sion ratios were set to 5%. 1%, 0.5%, and 0. %% for each segment, respectively, resulting in average compression ratio of 1.75%.
Top-k Layer-based Layers were categorized based on size into five groups: very small (< 100), small (S 600), medium (< 10º), large (< 10%), and very large (2 10%). Assigned compression ratios were 80%, 50%, 20%, 5 %, and 0. 1% for each group respectively, trans- mitting 1.77% of the gradients.
Results. Although the no-compression baseline achieves the highest accuracy, the time required is also large in environments with limited and weak resources. In this test, the baseline needed more than 6 hours complete 30 epochs, while the compression tests took 4100 seconds, thereby achieving the best return for time. From Figure 7al we can observe that the Epoch-based Top-k strategy achieves the best performance in the first T000 seconds, which expected as the method is running through a light compression of 5% during this period, compared to the other compressors that are using around 1.7% compression ratio. The uniform compressors required approximately double the time (a little less than 2000s) reach this level of accuracy. On the other hand, the Top-k strategy based on layer size, stands out with the best accuracy when the layer size groups are more refined; creating more groups helps in controlling the compression for sensitive and small layers to achieve better accuracy.
Takeaways. In resource-limited environments, the strategies in LEGACY perform better in terms of obtaining better accuracy faster. The initial mild compression phase of the epoch-based strategy
28

---

Published as a conference paper at ICLR 2026
Accordion
No compression
Topk-epoch
Topk-layer
Topk
50000
0.9
Data Volume (MB)
03030
Accurccy
5.06
30022
0.3
0.4
10030
0.2
0.2
Accordonn
LEGACY COGAM bx
1030
2000
3000
4000
1050
2400
3000
4000
Wall Clock Time
Wall Clock Time (s)
(c) ResNet18 training in Fl environ-
(a) ResNet18 training (with EF)
(b) ResNet18 training (without EF) ment, total data volume.
Figure 7: (a) and (b), we show accuracy vs. wall clock time training ResNet- 18 on CIFARIO, with and without EF, respectively. In (c), we show the total communicated data volume in ResNet- 18 on CIFAR10 training in an FL environment; see legend in Figure 8
Accordion(B, 0.2)
5100
B2Eo.6
S15L12
61.3
0.9
0.9
0.8
0.8
0.6
Accurae
Accuracy
0.6
0.5
0.5
0.4
0.3
0.2
0.2
0.1
0.1
Epach
(MB)
(a) Accuracy vs. Epoch
(b) Accuracy vs. Time
(c) Accuracy data volume
Figure 8: Training ResNet18 CIFARIO FL Environment; 8100 compression baseline.
allows it benefit from the early training phase and outperform other methods, which take signif- icant time match its performance, even after the epuch strategy enters the aggressive phase. On the other hand, applying light compression to small layers enhances model performance. In both strategies, creating more groups aids in refining the compression more effectively to achieve better performance.
D.3.2 FEDERATED TRAINING OF RESNET-18 ON CIFAR-10
Fast networks do not always harvest the compression benefit Xu al. (2021)); bandwidth-limited federated training is authentic area in assessing our strategies.
Testbed and setup. We emulate constrained federated learning (FL) environment with 50 CPU workers by using the same configuration before. Additionally, we partition the CIFAR- dataset into 50 subsets using a Dirichlet distribution with parameter a 10 to mimic a non-i.i.d. data distribution among the workers. We use Top-k as the base compressor in LEGACY and compare the results with no compression baseline and Accordion Agarwal et al. (2021a). This configuration more accurately reflects the limitations encountered in real-world FL environment, characterized by heterogeneous data, constrained networks, and computational resources.
Result. We do not accumulate gradients at local nodes but communicate immediately test the resilience of training when the slow network burdened with heavy communication. Our strategies are robust in FL and outperformed the uniform Top-1.3% and Accordion, achieving a 16-35% gain in accuracy, while being 6x faster than the no-compression baseline; see Figure 8b Our layer- based policy's 's test accuracy is almost similar to the no-compression baseline, while the epoch-based policy outperforms the uniform Top-1.3%. The adaptive policies in LEGACY significantly lower the communicate data volume overhead in FL deployments: Ep.6 and S15 communicate only 1.3% and I 1.23% of the data, respectively, compared to the no-compression baseline (Figure [c); also, see total communicated data volume during training in Figure /cc Together, this indicates the high quality of the trained model, consistent with the findings in data center training, and validates our claim that the simple yet efficient principles in LEGACY are beneficial for federated deployments.
29

---

Published as a conference paper at ICLR 2026
Table 9: CIFAR-I0 experiments
Dataset
CIFAR-10 AlexNet. ResNet-9
Architecture
Repository
Layer- Wise-AAAI2 Dutta et al. 2020
See https:///itthuui com/ sands- Tab/ wer--wis--aal
License Number of workers
MIT
Global Batch-size
256 2
Optimizer
vanilla SGD
LR scheduler
piecewise-lineas function that increases the learning rate from 0 to 0.4 during the first 5 epochs and then decreases to 0 till the last epoch
Number of Epochs Repetitions
30
15, with different seeds
Table 10: Evaluation of LEGACY in large scale training of Resnet-18 18 on CIFAR-10.
Methods
No compression
Top-k
LEGACY-E 71.8
LEGACY-L
Top-1 Accuracy
89.34
69.1
80.76
D.3.3 SCALING LEGACY TO 100 WORKERS IN DATA CENTER
Testbed and setup. We used the same configuration as in D.3.I but scaled the system to 100 workers and removed the handwidth limitation to accelerate training As in the previous setup, each worker operated an Intel Xeon Platinum 8276 CPU, and all other parameters were kept identical. The model accuracy depends the compressed gradients being transmitted, not on their transfer speed; the results are generalizable across different bandwidths (e.g., 400 Gbps. 10 Gbps, or Gbps). In practice, the compression strategy remains unchanged regardless of bandwidth; only the transfer time varies. Consequently, under low-bandwidth conditions, LEGACY provides substantial speedups over uncompressed training while also achieving higher accuracy than uniform compression.
For compression, configured each method transmit approximately 1% of the gradients on average, using the following parameters:
Top-k: 1% uniform compression.
Top-k Epoch-based the first epoch used 5% ratio, the second epoch 2%, followed by 1% for the next 18 epochs (epochs 3-20). For the final 10 epochs, we applied 0.7% ratio, resulting in average compression ratio of 1.06%.
Top-k Layer-based: layers were grouped by size into four categories: small (s 600), medium (< 10%) large (S 10%), and very large (2 10%). The small layer group was left uncompressed. Compression ratios of 15%. 2%, and 0.1% were applied to the medium, large, and very large groups, respectively, yielding average compression ratio of 0.99%.
Results and takeaways. Table 10 reports the results for the 100-worker setting. The no- compression baseline achieves the highest accuracy (89.34%), but the cost of substantial com- munication overhead. Uniform Top-k suffers from significant accuracy drop (69.1%), whereas both variants of LEGACY perform considerably better, with LEGACY-E reaching 71.8% and LEGACY-L achieving 80.76%. These results confirm that LEGACY scales effectively to 100-worker configura- tions while maintaining strong accuracy under aggressive compression. Combined with the earlier experiments in constrained environments, this demonstrates that LEGACY both efficient and robust across resource-liman limited and large-scale deployments, making it a practical solution for challenging distributed training scenarios.
D.4
TIME AND SPACE COMPLEXITY OF LEGACY AND OTHER ADAPTIVE COMPRESSORS
The time complexity of LEGACY is equivalent the time complexity of the base compressor used. LEGACY does not involve any mack-of-the-ham calculation in choosing the adaptive version of the compressor and needs negligible additional memory only to store the hyperparameters. Therefore, LEGACY does not require time and space complexity while granting the capability to regulate the communicated data volume, select the compressor, and decide whether use enror feedback.
30

---

Published as a conference paper at ICLR 2026
Table 11: CIFAR-100 experiments
Dataset
CIFAR-100
Architecture
ResNet-18 18
Repository
rethinking-sparsffictttion Sahu et al. 2021
See https::/gitthbb..co
License Number of workers
MIT
Global Batch-size
256 x 2
Optimizer
SGD with Nesterov Momentum
Momentum
0.9
Post warmup LR
0.1 x 16
LR-decay
/00 at epoch 150 and 250
LR-warmup
Linearly within epochs, starting from 0.1 300
Number of Epochs
Weight decay Repetitions
10
15, with different seeds
Table 12: Language modelling task
Dataset Architecture
WikiText103
Transformer-Xi
Repository
NVIDIA Deep Learning Examples Nvidia
See ht httpp://gichub.
com/ /
License
Apache
Number of workers
4
Global Batch-size
256
Optimizer
LAMB
LR-decay
Cosine schedule from 0.01 to 0.001
LR-warmup
Linearly within 1 1,000 iterations, reaching 0.01
Number of training steps
4500
Weight decay Repetitions
4, with different seeds
In contrast, Accordion Agarwal et al. (202 does not provide control over the communicated data volume since the duration the critical regime unknown, and it requires extra memory equivalent to twice the size of the model store accumulated gradients from the current and previous epoch used in the algorithm. L-GreCo MMrkov et al. (2024) require additional computations, which are hidden during training by invoking L-GreCo mfrequently (once per epoch in the conducted exper- iments) and also necessitates extra memory keep accumulated gradients and some intermediate matrices used in the algorithm (according to the paper, it possesses time complexity of O(D L|(C)) and memory complexity of ((L)) where [L] is the number of layers. C' list of compression parameters to tests, and D is the discretization factor (with default value D 10, 000) -the hyper- parameters used in L-Greco. Finally, Adacomp Chen et al. (0018)), variance-based method Tsuzuku al.) (2018), and CAT Khirirat et al. (202T) not give the possibility select the compression method or control the communicated volume.
E LIMITATION AND FUTURE DIRECTION
Although adapting compression ratios based on layer size and training phase can significantly en- hance model performance, introduces additional hyperparameters. These hyperparameters define the groups and the compression ratios for each group. While following the guidelines established by LEGACY can improve performance, identifying optimal hyperparameters is challenging and depends on multiple factors, such as the dataset, DNN model architecture, network bandwidth, and the num- ber and performance of workers. Regardless, in Section C.I we presented simplified approach that requires only two hyperparameters. In the future, we aim to develop more robust methods for selecting LEGACY parameters, making the process more efficient and adaptable to varying scenarios.
In this work, we explored the impact of adapting compression based on two parameters- size and training iteration-tie require no additional computation to determine. Additionally, we in- vestigated the potential of optimizing compression using the layer position within the model. To evaluate this, grouped layers into two or three categories based their position: the first and
31

---

Published as a conference paper at ICLR 2026
Table 13: Recommendation task
Dataset Architecture Repository
Movielens-2OMG
NCF
NVIDIA Deep Learning Examples Nvidia
See sechtttss///gtthbb com/ NV IVIIIAIIIAAA A
Number of workers
2
Global Batch-size
2
Optimizer
ADAM
ADAM 81
0,25
ADAM 32
0.5
ADAM LR
4.5 10-3
Number of Epochs
30
Weight decay
0
Dropout
0.5
Repetitions
10, with different seeds
License
Apache
Table 14: ImageNet experiments
Dataset
ImageNet
Architecture
Re
Repository
PyTorch Examples Porcor
See /attps://g1thhe
com
pttp///tttoccccccc examples
License Number of workers
BSD 3-Clause
4
Global Batch-size
256
Optimizer
SGD
Momentum
0.9
LR-decay
LR decayed by every 30 epochs
Number of Epochs
50
Weight decay
10
Repetitions
32

---

Published as a conference paper at ICLR 2026
last halves, the first, middle, and last parts, respectively. Similar to previous experiments, we applied different compression strategies (aggressive for one group and mild for another, while maintaining a similar data volume) and compared them to uniform compression. Our results did not identify a clear best approach: strategies that performed well in one case failed in another. We attribute this to model layer distributions some models have smaller layers predominantly at the beginning. while others have them concentrated at the end. Ignoring these distributions when ap- plying compression can lead to aggressive compression on smaller layers, resulting in degraded performance. We believe more in-depth study that integrates layer position with layer size and training phase could refine compression parameter selection and improve performance outcomes.
The paper primarily focuses on synchronous communication and does not consider addressing asyn- chronous SGD setups, which is a nontrivial extension of this work. However, the dynamic compres- sion strategies proposed by LEGACY are based layer size and training phase, which are general principles and could be adapted for asynchronous setups. This extension would require further care- ful theoretical and experimental validation to ensure convergence and efficiency, and is left to future work.
LEGACY is feasible for real-time edge deployments because it uses lightweight meta-scheduling on base compressor based on simple factors like layer size and training phase, avoiding compu- tationally intensive methods. The framework does not rely on hard-to-compp commppue gradient statistics, making it suitable for not provide explicit latency metrics for real-time edge deployments, it emphasizes its applicability in several comparable settings: Minimal computational overhead in scheduling compression parame- ters; Empirical results on distributed setups (e.g., training on GPUs with 400 Gbps bandwidth) show that LEGACY does not introduce significant delays compared to uniform compression strategies. To further harvest the compression benefit of LEGACY in bandwidth-
environments like edge devices. While the paper does
federated training, we deploy it using 50 and 100 workers, with every worker operating on an Intel Xeon Platinum 8276 CPU instead of GPU, sharing a Gbbss network bandwidth and no constraint the bandwidth, re- spectively. In both cases, LEGACY demonstrates superior performance compared to the base uniform compressor. Taken together, LEGACY's lightweight nature makes it promising candidate for edge deployments.
With the advent of large multimodal models, fine-tuning can be seen as training a DNN model with a special starting point. So, LEGACY's compression strategy, based on layer size and training phase, can be applied equally well to fine-tuning it does to training from scratch. Fine-tuning typically involves fewer updates for certain layers, so LEGACY for tine-tuning will dynamically adjust compression parameters to these layers, making it robust to both training and fine-tuning scenarios. However, when LEGACY relies on dynamic adjustments during different training phases, in scenarios of fine-tuning with very short training durations, the benefits of LEGACY scheduling may be diminished.
Finally, we note that adversarial attacks are orthogonal the gradient compression strategies. How- ever, LEGACY's simple, layer- and epoch- based dynamic meta-scheduling makes it less prone to adversarial gradient perturbations compared to adaptive compression strategies that depend on gradi- ent magnitudes or other dynamic metrics. Thus, LEGACY can be combined safely with adversarial attacks-resilient methods (methods using robust aggregation mechanisms). However, test this efficacy is not in the primary scope of this work.
F ETHICS STATEMENT AND POTENTIAL NEGATIVE IMPACT
Gradient compression techniques have been widely adopted since their introduction to the machine learning community. The strategies used in developing our adaptive compression scheduler in this work, theoretically and empirically, demonstrate their capability of achieving better accuracy in DNN training in a distributed and federated setup. The present work is theoretically driven, and experiments corroborate the theoretical claims. Therefore, we do not see any foreseeable harm can pose to human society. However, it is always possible that some individual or an organization can use this idea to devise a technique that can appear harmful to society and bear evil consequences. As authors, we are absolutely against any detrimental usage, regardless of, by any individual or organization, under profit or pro-pttiie motivation, and pledge not to support any detrimental endeavors concerning our idea therein.
33


Reviews:
[{"review_id": "CiCzWaRXBv", "reviewer": "Reviewer_WieB", "summary": "This work itroduce  a lightweight, open-source framework, referred to as LACACY, which dynamically compresses gradients in distributed DNN training. Its scheduler, guided only by layer size and training phase, offers a simple  alternative to compute-intensive adaptive compressors. Benchmarking with Top-k, Random-k, QSGD, and PowerSGD shows that LEGACY achieves consistent performance gains over uniform on Cifar10, Cifar100 and other datasets.", "questions": "1. The architectures (e.g., ResNet-9, ResNet-18) and datasets (e.g., CIFAR-10/100, WikiText) used for evaluation are somewhat outdated. Could the authors demonstrate LEGACY's effectiveness on more modern benchmarks (e.g., Vision Transformers or contemporary datasets)?\n\n2. In Table 5, the reported baseline accuracy for training ResNet-50 on ImageNet-1K is 59.43%, significantly lower than standard benchmarks. Could the authors explain this discrepancy in their training setup?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper presents a unified framework that enables various communication-compression algorithms to dynamically adjust their compression levels. Experimental results demonstrate that this proposed scheme is both simple and effective.", "weaknesses": "1. **Theoretical Motivation:** The motivations for the dynamic compression strategies are not fully convincing.\n   * The **training phase-based** strategy is justified by Lemma 1, which relies on convergence properties of Gradient Descent for convex objectives. However, this theoretical foundation may not directly translate to the non-convex and stochastic optimization of Deep Neural Networks, limiting its applicability.\n   * The **layer size-based** strategy relies on the unverified assumption that larger layers are more over-parameterized and can tolerate higher compression. This claim lacks theoretical or empirical support within the paper.\n\n2. **Insufficient Experimental Evidence:** While the paper claims LEGACY is a \"lightweight yet effective dynamic scheduler,\" the experiments do not fully substantiate this claim.\n   * There is no evidence demonstrating that LEGACY's lightweight design translates to significant wall-clock time reduction compared to compute-intensive adaptive methods like L-GreCo and Accordion. The time saved by its simple scheduler might be negligible compared to overall compression computation.\n   * Performance comparisons against key counterparts are limited, primarily appearing in the ResNet-18 on CIFAR-100 experiment. This narrow scope limits generalizability.\n   * The reported accuracy for uniform PowerSGD and L-GreCo is notably lower than results in the original L-GreCo paper [1] under similar settings. Additionally, the compression ratio used for Accordion is lower than for other methods, potentially creating an unfair comparison. These issues undermine the reliability of the experimental findings.\nIn summary, the comparative experiments lack breadth, and their results are not entirely convincing.\n\n\n[1] Alimohammadi, Mohammadreza, et al. \"L-GreCo: Layerwise-Adaptive Gradient Compression for Efficient and Accurate Deep Learning.\" arXiv:2210.17357, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "47iN0w0YJj", "reviewer": "Reviewer_xMGk", "summary": "This paper presents a communication-efficient federated learning method. The proposed method is scheduler of gradient compression, which is agnostic to compression (quantization) method. The proposed method is based on the observation that the number of parameters for individual layers could be very different. Furthermore, at different stages of model training, different compression strength is necessary to achieve good balance between performance and communication cost reduction. To demonstrate the above ideas, this paper provides theoretical analysis on the compression bounds and convergence. Although theoretical analysis is provided, the experiments are still empirical. Testing on several datasets and model architectures, including ResNet and Transformer, this paper shows better results with different quantization methods, compared with other adaptive compression techniques like Accordion. \n\nFrom my perspective, the complexity of layers and the training stages are essentially related to gradient norm (later epochs produce smaller norms) and direction. It can be analyzed from the compression errors in norm and cosine similarity after applying the quantization. Therefore, a more controlled scheduler might be easier to deploy than an empirical method studied in this work, by checking the compression errors caused by layer size and training epoch numbers. \n\nI vote this paper as \"6: marginally above the acceptance threshold. But would not mind if paper is rejected\", but could change my decision in my final voting.", "questions": "In the research history, it's known that early layers are learned at the beginning of training. In particular, when we finetune from a pretrained model, the early layers do not change drastically, compared with later layers. It is interesting to know how to balance the compression strength for lower / higher layers at the beginning / end of training.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. A very simple and quantization-agnostic approach is proposed for communication-efficient federated learning. Based on this approach, several models and datasets are applied with better performance than previous work.\n\n2. Theoretical analysis is provided, which enhances the motivation of this work.", "weaknesses": "1. The selection of compression strength is still empirical. It increases the challenge of deployment of this model in the real world. For example, the data from individual clients might be very different, that some clients may provide training data very different to major distribution. For this client, the gradient norm will be very different to others. Therefore, different clients may also need different compression strength. \n\n2. It will be helpful to show the performance curves over different training epochs and different communication costs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rA3hAjGN4E", "reviewer": "Reviewer_NtMi", "summary": "The paper introduces LEGACY, a simple scheduler to make gradient compression dynamic in distributed deep learning. Instead of using a fixed compression ratio, LEGACY adapts compression by training phase (light compression early, heavy later) and by layer size (compress large layers more, small layers less). \nThe scheduler works with any existing compressor without additional compute overhead or per-iteration tuning. Theoretical analysis shows the intuition behind the proposed method and guarantees the convergence of compressed stochastic gradient descent. Comprehensive experiments under different settings demonstrate the effectiveness of LEGACY compared to other compression methods.", "questions": "1. In practice, is the chosen compression schedule consistent with the theoretical assumptions and requirements?  There appears to be a gap between the theory and the experimental settings that is not clearly explained or discussed.\n2. The paper introduces two dynamic compression strategies: by training phase and by layer size. And it also states that they can mix the two strategies up. Is there any theoretical analysis for the mixed strategy?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper explores a dynamic compression strategy that adapts to training phase and layer size, which can potentially improve the efficiency of distributed deep learning.\n2. It provides sufficient experimental results under various settings that support the effectiveness of the proposed method.\n3. The proposed compression method is lightweight and can be integrated with other compression techniques.", "weaknesses": "Compared to existing adaptive compression methods such as Accordion and L-GreCo (Section 4.3.1), LEGACY does not clearly demonstrate advantages in either accuracy or data volume. Therefore, the novelty and practical impact of the method appear somewhat limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nWFj5gMlqG", "reviewer": "Reviewer_i63J", "summary": "This manuscript introduces a practically-driven compression strategy for federated learning, supported by theoretical analysis and extensive benchmarking. A central finding is that compression should be adapted to individual layer sizes and the training phase. This insight offers valuable guidance for designing more efficient communication in federated learning. The work effectively balances theory and experimentation, providing useful design principles for adaptive compression methods.", "questions": "1、To better assess the practical applicability of the method, could the authors delineate the scenarios or conditions under which the proposed compression framework might exhibit performance degradation? A discussion of such limitations would be valuable for understanding the robustness of the approach.\n2、The theoretical analysis presented, while sound, appears to align with established convergence rates for standard compressors in the literature. Could the authors clarify the novel theoretical contribution of their work in this context?\n3、The experimental validation primarily uses smaller-scale architectures. To demonstrate the scalability and general applicability of the method, could the authors provide results on larger, contemporary models, such as generative transformers (e.g., GPT variants)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1、The paper is supported by rigorous simulations that empirically validate the proposed method. The experiments are well-constructed, employing relevant baselines and metrics to clearly demonstrate the approach's effectiveness across diverse conditions.\n2、Complementing the empirical work, the authors include a theoretical analysis that grounds the core principles of their compression strategy. Although not the paper's central thrust, this analysis adds valuable depth and strengthens the overall argument.", "weaknesses": "1、While the paper explores a broad parameter space, the sensitivity of the method to specific parameter choices and its potential failure conditions remain unclear. A more systematic investigation, or at least a discussion of possible failure modes, would help to better assess the approach's reliability and practical applicability.\n2、Regarding the theoretical contribution: as noted in the manuscript, the analysis of compression operators and their convergence rates appears to align with existing theoretical frameworks. It would be helpful to clarify the novel theoretical insights offered by this work compared to prior analyses.\n3、The models used in the experiments are relatively small and may not reflect modern large-scale architectures. Since their communication overhead is inherently limited, the results may not fully demonstrate the method's effectiveness in high-communication settings. Experiments on larger generative models, such as GPT-family architectures, would strengthen the evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)