IntSGD: Adaptive Floatless Compression of Stochastic Gradients
Authors: Konstantin Mishchenko
Bokun Wang
Dmitry Kovalev
Peter Richtárik
Venue: ICLR 2022 Spotlight (2022)
Keywords: optimization
distributed optimization
compression
theory
parallel training
switchML

Abstract: We propose a family of adaptive integer compression operators for distributed Stochastic Gradient Descent (SGD) that do not communicate a single float. This is achieved by multiplying floating-point vectors with a number known to every device and then rounding to integers. In contrast to the prior work on integer compression for SwitchML by (Sapio et al., 2021), our IntSGD method is provably convergent and computationally cheaper as it estimates the scaling of vectors adaptively. Our theory shows that the iteration complexity of IntSGD matches that of SGD up to constant factors for both convex and non-convex, smooth and non-smooth functions, with and without overparameterization. Moreover, our algorithm can also be tailored for the popular all-reduce primitive and shows promising empirical performance.

Published as a conference paper at ICLR 2022
INTSGD: ADAPTIVE FLOATLESS COMPRESSION OF STOCHASTIC GRADIENTS
Konstantin Mishchenko
Bokun Wang
CNRS, École Normale Supérieure, Inria konsta mishh@mmail com
KAUST bokunw Bokkun.wang@gmal .com
Dmitry Kovaley
Peter Richtárik KAUST
KAUST
da lakkoaaees lev1 @emraliie@@maiii com
ABSTRACT
We propose a family of adaptive integer compression operators for distributed Stochastic Gradient Descent (SGD) that do not communicate a single float. This is achieved by multiplying floating-point vectors with a number known to every device and then rounding to integers. In contrast the prior work on integer compression for SwitchML by Sapio et al. (2021), our IntSGD method is prov- ably convergent and computationally cheaper as estimates the scaling of vectors adaptively. Our theory shows that the iteration complexity of IntSGD matches that SGD up to constant factors for both convex and non-convex, smooth and non- smooth functions, with and without overparameterization. Moreover, our algo- rithm can also be tailored for the popular all-reduce primitive and shows promising empirical performance.
INTRODUCTION
Many recent breakthroughs machine learning were made possible due to the introduction of large, sophisticated and high capacity supervised models whose training requires days even weeks of computation (Hinton et al., 2015; He al., 2016; Huang et al., 2017; Devlin et al., 2018). However, it would not be possible to train them without corresponding advances in parallel and distributed algorithms capable of taking advantage of modern hardware. Very large models are typically trained on vast collections of training data stored in distributed fashion across number of compute nodes that need to communicate throughout the training process. In this scenario, reliance on efficient communication protocols is of utmost importance.
Communication in distributed systems. The training process of large models relies on fast syn- chronization of gradients computed parallel fashion. Formally, train a model, we want to solve the problem of parallel/distributer minimization of the average of n functions:
((x) def
[xx) def Eg (x);
min ZERd
where we will compute the gradients of stochastic realizations ft The two dominating pro- tocols for gradient synchronization are all- reduce and all- all-gather aggregation, which may use either Parameter Server or all-to-all communication under the hood. The core difference between them lies in that all all-gather communicates all vectors, whereas all-reduce only outputs their average. As shown in previous works, current distributed deep learning algorithms predominantly use all-reduce as it scales much better than all-gather (Vogels et al., 2019; Agarwal et al., 2021).
popular way to reduce the communication cost of both all-reduce and all-gather primitives is to use lossy compression of gradients (Ramesh et al., 2021). To study the benefit of lossy compression, large swaths of recent literature on distributed training attribute the cost of sending a single vector
Work done when the author research intern KAUST.

---

Published as a conference paper at ICLR 2022
from worker to the server to the number of bits needed to represent it. Based this abstraction, various claborate vector compression techniques (see Table in Beznosikov et al. 2020; Xu et al. 2020: Safaryan et al. 2020) and algorithms have been designed for higher and higher compression ratios. However, in real systems, the efficiency of sending a vector not fully characterized by the number of bits alone, because:
First, many compressors with high compression ratio (e.g., natural compression (Horváth et al., 2019), quantization (Alistarh et al., 2017), top-k sparsification, sign (Bernstein et al., 2018)) are not compatible with the efficient all-reduce primitive and require all- all-gather im- plementation.
Secondly, some compressors rely on expensive operations such as low-rank decomposi- tion (Wang et al., 2018; Vogels et al., 2019) or bit-level operations (Horváth et al., 2019), whose computation overhead may outweigh the benefits of reduced communication load.
Thirdly, algorithms with biased compressors such as Top-k SGD, SignSGD, PowerSGD (Vogels et al., 2019), require the error-feedback (EF-SGD) mechanism (Stich et al., 2018; Karimireddy et al., 2019) ensure the convergence. Alas, enror feedback needs extra sequences that may not fit the low memory budget of GPUs. Moreover, to the best of our knowledge, convergence guarantee has been established for EF-SGD on the non-smooth objectives with multiple workers.
SwitchML. Another approach to combating long communication times is to improve the hardware itself. The recently proposed SwitchML is an alternative to the NVIDIA Collective Communications Library (NCCL) on real-world hardware (Sapio al., 2021). The first key component of SwitchML is the in-network aggregation (INA) by programmable switch. INA reduces the communication cost and latency because the execution can be paralleled and pipelined. To be specifie, it splits the vector to aggregate into chunks and processes them individually by the switch pipeline. The advan- tages of INA over parameter server and all-reduce in terms of latency and communication cost have been theoretically and empirically justified by Sapio et al. (2021). The second key component of SwitchMI. is stochastic gradient descent with integer rounding and aggregation. Instead of reducing the data volume to exchange, the goal of integer rounding in SwitchML is to fit the limited com- putation capability of the modern programmable switch, which only supports integer additions or logic operations. To increase the rounding precision, the gradient of on device multiplies a positive scaling factor (vı known to every worker and then rounded to an integer number Inl(ax gf¹). As there is no additional scaling or decompression before aggregating the communicated vectors, their sums can be computed on the fly. Then, each worker can divide the aggregated gradient by nog to update the model.
However, Sapio et al. (2021) remark that the choice of the scaling factor ag requires special care. In their presentation', one of the authors notes: "A bad choice of scaling factor can reduce the performance." To this end, they propose a heuristic-based based profiling step that is executed before the gradient aggregation and keeps the rounded integers small to fit in 32 bits. We refer to their algorithm including the profiling step Heuristic IntSGD. Unfortunately, no convergence guarantee for that algorithm has been established. This is where our theory comes to the rescue. By rigorously and exhaustively analyzing integer rounding based on scaling, we find adaptive rules for the scaling factor ag that do not require the profiling employed by Sapio et al. (2021). As we will show in the remainder of the paper, our algorithm perfectly suited for both in-network aggregation (INA) of SwitchML and for other efficient primitives such as all-reduce.
1.1 CONTRIBUTIONS
We summarize the key differences of our algorithm and prior work in Table 1, and we also list our main contributions below.
Adaptive IntSGD. We develop a family of computationally cheap adaptive scaling factors for provably convergent IntSGD. It is better alternative to the Heuristic IntSGD in Sapio et al. (2021) that requires expensive operations and does not ensure convergence.
2

---

Published as a conference paper at ICLR 2022
Table 1: Conceptual comparison of our method the related literature. If all-reduce supported, the method does not need any decompression. If a'll-reeuce is not supported, the expensive all- gather operation required and decompression slow. See also Section for numerical comparisons.
Supports all-reduce
Supports switch
Provably works
Fast compression
Works without error-feedback
Algorithm
Adaptive
Reference
IntSGD
Ours
Heuristic
X
/
X
Sapio al. (2021)
IntSGD
PowerSGD
X
X
X
X
Vogels ct al. (2019)
(theoretical)
PowerSGD
X
X
X
Vogels et (2019)
(practical)
NatSGD
X
N/A
Horväth et al. (2019)
QSGD
X
/
N/A
Alistarh et al. (2017)
SignSGD
X
/
N/A
Karimireddy et al. (2019)
(1) theory, PowerSGD requires computing low rank decompasitions. In practice, an upproximation found by power iteration, which analyzed theoretically and might he less stable.
requires just few matrix-veatt vector mulriplications
()) PowerSGD requires tuning the rank of the low-rank decomposition. Nogels et al. (2019) reported that rank-1 PowerSGD consistently underperfomeed
experiments, mereover, rank-2 optimal image classification while language modeling required Ramesh et al. (2021) reported that much larger rank was needed to avoid gap in the training loss.
rank-4,
Rates. We obtain the first analysis of the integer rounding and aggregation for distributed machine learning. For all of the proposed variants, we prove convergence rates of IntSGD that match those of full-precision SGD up constant factors. Our results tight and apply to both convex and non- convex problems. Our analysis does not require any extra assumption compared to those typically invoked for SGD, In contrast other compression-based methods, IntSGD has the same rate that of full-precision SGD even on non-smooth problems.
IntDIANA. We observe empirically that IntSGD struggles when the devices have heterogeneous (non-identical) data-an an issue it shares with vanilla SGD-and propose an alternative method, IntDI- ANA, that can provably alleviate this issue. We also show that our tools are useful for extending the methodology beyond SGD methods, for example, to variance reduced methods (Johnson & Zhang, 2013; Allen-Zhu Hazan, 2016; Kovalev al., 2020; Gower et al., 2020) with integer rounding. Please refer to Appendix A.2 for theoretical results and Appendix C.5 for the empirical verification.
2 ADAPTIVE INTEGER ROUNDING AND INTSGD
By randomized integer rounding we mean the mapping Ind R + defined by
[td(t) del
[t] + 1, with probability pt f [t].
[t].
with probability 1 Pt.
where [t] denotes the floor of t IR, i.c., [t] = ke e Z, where & is such that k < t < ks + 1. Note that
E [Ind(()) = (1 [1) 1) + ((4 + ()[+]= =1
We extend this mapping to vectors Rd by applying in element-wise Int(x); def Int(x;).
2.1 ADAPTIVE INTEGER ROUNDING
Given scaling vector a E dd with nonzero entries, we further define the adaptive integer rounding operator Q Rd Rd by
Q(x) def o Int(a x),
(2)
where a def .a........ azba) E Rd denotes the Hadamard product of two vectors a =
(a),.... aa) Rd and i = (b....., ba) RRd
3

---

Published as a conference paper at ICLR 2022
Algorithm IntSGD. Default setting for the tested problems: 0.9, E 10-8.
1: Params: Stepsizes Tek scaling vectors O4 E Rd
2: Init: x² R.d xx'
70 Σi= g.
3: for k = 2...... do
4: for each device 1, 1, ..... do
5: Compute stochastic gradient of (E | x²1 Edf((**))
6:
Maintain the moving average: T Brk-1 +1 (1 3) x
7:
Compute the adaptive scaling factor: Ork 2 /nn +52
vi
8:
Scale and round the local gradient Q(a.) Int(ar o gf) end for
9:
10:
Aggregate ((g,") ) by either all-reduce or in-network aggregation (INA)
11:
for each device = 1, ...., n do
12:
Compute the (sub)gradient estimator: 3 1 > Q(at)
13:
Update the model parameter xk+1 xz m end for
14:
end for
As we show below, the adaptive integer rounding operator (2) has several properties which will be useful our analysis. In particular, the operator unbiased, and its variance can be controlled by choice of possibly random scaling vector E IR
Lemma 1. For any Rd and R$ have
o E [Inl(ar 2,
(3)
E
||
Int(aos) -
1a
The expectations above taken with respect to the randomness inherent in the rounding operator.
2.2 NEW ALGORITHM: INTSGD
We are ready to present our algorithm, IntSGD. At iteration k, each device computes a stochastic (sub)gradient vector g i.e., vector satisfying
E
[ot
[ E 0fi(z*).
(5)
Prior to communication, each worker i rescales its stochastic (sub)gradients of using the same vector O% E T and applies the randomized rounding operator Int. The resulting vectors Int(a g are aggregated to obtain Σ/=1 Inf(ax o g which is also an integer. Each device subsequently performs division by n and inverse scaling to decode the message, obtaining the vector
def
FORE Σ Ind(ax gt) Σ az Inl((x g 2 1 Q(g)). Q(1t).
"
Here ag is a random adaptive scaling factor calculated based on the historical information. We left the design of ag to Section By combining (5) and (3), we observe that g² is stochastic (sub)gradient of at x² Finally, all devices perform in parallel an SGD-type step of the form 2k+1 - - and the process is repeated. Our IntSGD method is formally stated Algorithm with the suggested rule of a.
Relation to QSGD (Alistarh al., 2017). QSGD bears some similarity to the IntSGD: Both of them scale of by a factor before the quantization (the scaling factor in QSGD is 1/ for normalization). However, some key difference makes the communication efficiency of IntSGD much better than that of QSGD. It is worth noting that the normalization factors 1/ || in QSGD are different for various workers. Then, the quantized values of various workers need to be gathered and decompressed before aggregation. On the contrary, the scaling factor aę in our IntSGD is the same for all workers such that the sum of integers can be computed on the fly. Thus, IntSGD supports the efficient all- reduce primitive while QSGD does not. As seen in the experimental results in Section this
4

---

Published as a conference paper at ICLR 2022
makes big difference in empirical performance. Moreover, the proof technique for IntSGD is also intrinsically different from that QSGD. Please see the next section for the details.
ANALYSIS OF INTSGD²
To establish convergence IntSGD, we introduce the following assumption on the scaling vector 0g (0g,1,...., ,kk. ++
Assumption 1. There exists 3 E [0, and a sufficiently small é > 0 such that
E
is
k-1
bounded above by n + 2m(1 - 3) Σ B'E B'E 111].
While this assumption may look exotic, captures precisely what we need to establish the con- vergence of IntSGD, and it holds for several practical choices of ag including the one shown in Section and more choices in Appendix A.I.
Challenges in IntSGD analysis. Although the Int operation is unbiased and has finite variance as shown in Lemma 1, we highlight that it is non-trivial to obtain the convergence analysis of IntSGD and the analysis is different from that of QSGD and similar methods. Indeed, QSGD, Rank-k, and NatSGD all use unbiased operators Q with variance satisfying E]] 2(g) > For them, the convergence theory is simply plug-in of the analysis Compressed SGD (Khirirat et al., 2018). However, the integer rounding operator Int does not satisfy this property, and the variance of the integer compressor will not decrease to zero when |[ - 0. Moreover, to estimate ag adaptively, we use the values of past iterates, which makes its value itself random, so analysis of Compressed SGD cannot apply. As shown in our proofs, an extra trick is required:
| S. 2 for some
we reserve an additional term Et [[[|==/+1 - ==| to control the variance of the rounding. Fur- thermore, the analysis of moving-average estimation is particularly challenging since the value of og is affected by all past model updates, starting from the very first iteration.
3.1 NON- NON-SMOOTH ANALYSIS: GENERIC RESULT
Let us now show that IntSGD works well even on non-smooth functions. Assumption 2. Stochastic (sub)gradients
.f.....hh .th sampled at iteration satisfy the inequalities
Enght G²,
M Ex |lst
Exlo/111 <
where the former inequality corresponds to G-Lipschitzness of f and the latter to bounded variance of stochastic (sub)gradients.
Theorem 1. Let functions F1,...,Jo Sa be convex and Assumptions and be satisfied. Then
E [ - [xx)]] ||00 - +12 2 Eiso
where ik
Ec-o Th Et=o max is a weighted average of iterates.
3.2 SMOOTH ANALYSIS: GENERIC RESULT
We now develop a theory for smooth objectives.
Assumption 3. There exist constants L, o. 2 such that the stochastic gradients of ...... iteration & satisfy [x[g]]] Vfi(a*) and
........ gt
E
C((())) f(x)))
In our analysis, use the red color to highlight the extra terms coming from our integer compression, in contrast the blue terms, which from SGD itself.

---

Published as a conference paper at ICLR 2022
Assumption 3 is known the expected smoothness assumption (Gower al., 2019). In its formu- lation, we divide the constant term of by n, which is justified by the following proposition.
Proposition (Section 3.3 in Gower et al. 2019). Let f((x)) = Eg (e( {) of E) be convex and its gradient be Li-Lisschitz for any Then, the second part of Assumption is satisfied with o² 2 E 1=1 B [ =]]]]] and C def max L,
and
Gower et al. (2019) state and prove this result a more general form, so for the reader's convenience, provide proof in the appendix.
Theorem 2. Assume that is corvex and Assumption holds.
If mh S 22 and 5
Eiso dh Ei=o nhx is weighted average of iterates, then
11 - +2
Ee
E [(())) f(x*))
2E W
Corollary (Overparameterizeed regime). When the model is overparameterized (i.e., the losses be minimized to optimality simultaneously: d. = 0), we can set and obtain O ( rate.
3.3 NON-CONVEX ANALYSIS: GENERIC RESULT
We now develop a theory for non-convex objectives.
Assumption 4. The gradient of f is L-Lipschitz and there exists finl E such that fint S f(x) for all x. Furthermore, for all and k we have
E [llof Vf(l=") S so²
(8)
Our main result in the non-convex regime follows.
Theorem 3. Let f be L-smooth and let Assumption I hold. 1f S
1 for all k; then
2I
[ < f(x") pint ( Etzo n
Ei We
where j*t is sampled from (w0 , r²} with probubilities proportional to flos..
3.4 EXPLICIT COMPLEXITY RESULTS
Having developed generic complexity results for IntSGD in the non-smooth (Section 3. smooth (Section 3.2) and non-convex (Section 3.3) regimes, we now derive explicit convergence rates.
Corollary 2. For any sequence of scaling vectors 0g satisfying Assumption 1, we recover the fol- lowing complexities:
(i) if fi...., fn are convex, Assumption 2 is satisfied and = 17
12 O
1
vT for
V
1 0, ..... ki then
E [ 5 [(x))] 0
ats Vkn
(9)
Vkb
11ا0 lIvA
(ii) if f convex, Assumption holds and = min
then
Vklo. +2)
E [[($*) - f(x))] =0
gott vin
|100-0011
((((2))-
(iii) if f is non-convex, Assumption 4 holds and = min 2L
then
Vklote)
E [|V o
ate
f(a")-
Vkn
Based Corollary IntSGD has linear speed-up in case (ii) and (iii).

---

Published as a conference paper at ICLR 2022
Comparison with error-feedback (EF-SGD). Distributed SGD with biased compressors (like PowerSGD, SignSGD, Top-k SGD) requires the error-feedback modification to converge. In the non-convex and smooth case, EF-SGD leads to the O (vin (2)
rate Koloskova et al. (2019) when assuming the second moment of stochastic gradient is bounded by G². Compared to their result, our rate is never worse and does not require the second moment of stochastic gradi- ent to be bounded, which often violated in practice even for quadratic objectives and simplest neural networks. The convergence guarantee of EF-SGD for the convex and non-smooth function (Assumption 2) is even weaker: Karimireddy et al. (2019) show the O
convergence rate of EF-SGD only for the single-worker case (n = 1), which is 1 -ties worse than IntSGD (6 could be fairly small, e.g., ô 1/d in Top-1 compression). To the best of our knowledge, there is no convergence guarantee of EF-SGD for the non- oon-smooth function when there are multiple workers. In contrast, our IntSGD has the same rate as SGD under the same set of assumptions.
DESIGN OF SCALING FACTORS
4.1 ADAPTIVE SCALING FACTOR WITH THE MOVING AVERAGE AND SAFRGUARD
We now present effective rule of adaptive og (presented in Algorithm 1) that satisfies Assump- tion 1 for the convergence rates listed in previous section. In the appendix, we provide more options that also satisfy Assumption I and the proof still goes through. For simplicity, we assume that the first communication is exact, which allows us to estimate or adaptively without worrying about onp.
Proposition Assumption holds if we choose 3 [0, 1), 2 0 and og
where
22urx/
Th Bra- + 11 111
Remark 1. Here 3 E [0, 1) is constant factor control the moving average update of T&, which prevents the scaling factor 0g from changing too rapidly. E² could be any sufficiently small number, which serves as a safeguard to avoid the potential "divide by zero" error. We study the sensitivity of our IntSGD to 3 and e in Appendix C.4.
4.2 COMPRESSION EFFICIENCY
Let us now discuss the number of bits needed for the compressed vectors. Although the main attraction of IntSGD is that it can perform efficient in-network communication, we may also hope to gain from the smaller size of the updates.
Consider for simplicity the case where 1|at x
||ng with some i. The adaptive scheme Th v V2n||a --1--|
with 3 = 0, = 0 gives ag
Th V V2nli=* -
Va so that ||awo" ll = V2n a
va of =0 V2n [la""
Va Since we only signed integers, we need at most 1 loga
Vd bits for each /in
<
22n
coordinate. For instance, for 0 and n 100, the upper bound + logg(V3 ( < 14 bits. The situation becomes even better when ||,/'|| > l1 blo i.e., when the stochastic gradients dense. This property has been observed certain empirical evaluations for deep neural networks;
for example the study in (Bernstein et al., 2018).
EXPERIMENTS
5.1
SETUP
We empirically compare our IntSGD algorithm with several representative and strong baselines: SGD, Heuristic IntSGD (Sapio et al., 2021), SGD, PowerSGD + Error-feedback (EF) (Vogels et al., 2019), NatSGD (Horváth et al., 2019), and QSGD (Alistarh et al., 2017). The experiments are performed on 16 NVIDIA Tesla V100 GPUs located on 8 compute nodes of a cluster (2 GPUs per node) following the PowerSGD paper. The compute nodes in the cluster utilize InfiniBand HDR-100 Director Switch at 100Gbps speed for network connection. The cluster also supports the NVIDIA Collective Communications Library (NCCL).
7

---

Published as a conference paper at ICLR 2022
We consider two tasks: image classification by ResNet18 (He al., 2016) on the CIFAR-10 dataset and language modeling by a 3-layer LSTM on the Wikitext-2 dataset. The neural network architec- tures and hyperparameters are from some public PyTorch implementations" Our code is built on the codebase of PowerSGD'. We also borrow their all-reduce-basse erSGD. It is worth noting that QSGD and NatSGD do not support all-reduce. Thus, we implement their collective communications by all all-gather. The implementations for compression and decom- pression in QSGD and NatSGD are from the authors of NatSGD*. For the sake of comparison, we also implement the all- aul-gather--aase SGD. We report the results of 3 repetitions with varying seeds.
implementations of SGD and Pow-
Apart from the IntSGD with randomized integer rounding (IntSGD (Random)) analyzed in our the- ory, we also consider the variant of IntSGD with deterministic integer rounding (IntSGD (Determ.)) which can use the PyTorch built-in function torch. round. For all IntSGD variants, we clip the local stochastic gradients to ensure that each aggregated value fits in either 8 bits or 32 bits.
For more details of the experimental setup, please refer Appendix C.I.
5.2 INTSGD vs. HEURISTIC INTSGD
First, we compare our IntSGD with the most related algorithm Heuristic IntSGD (Sapio et al., 2021). For both algorithms, we consider two potential communication data types: int and int32. Note that the rule of scaling factor in Heuristic IntSGD is a = n aug where "nb" represents the number of bits to encode each coordinate and "max_exp" is the rounded exponent of the largest absolute value in the communicated package. Although this scaling rule is straightforward and avoids over- flows, it cannot guarantee convergence, even with int32 the communication data type. Indeed, the Heuristic IntSGD may fail to match the testing performance of full-precision SGD according to Figure 1. On the contrary, our IntSGD can perfectly match the performance of full-precision SGD on both image classification and language modeling tasks, which is in accordance with our theory that IntSGD provably convergent.
-1
Rea
Rea
43
Heumat IN:00034M:
SPL
40
50
200
43
50
100
350
200
102
Specis
Figure 1: Comparison among IntSGD (8-bit or 32-bit), Heuristic IntSGD (8-bit or 32-bit), and full-
precision SGD on the tasks of training ResNet18 and LSTM.
5.3 INTSGD vs. OTHER BASELINES
We also compare our IntSGD algorithms to the other baselines including the all-gather-based SGD, QSGD, NatSGD and the all-reduce-based SGD, PowerSGD (EF) on the two tasks. See the test performance and time breakdown in Table 2 and Table 3.
First, we can observe that the all- gather based SGD + compressors (e.g., QSGD, NatSGD) are indeed faster than the all-gather based full-precision SGD, which shows the benefit of lossy compressions. However, they are even much slower than the all-reduce-based full-precision SGD. Unfortunately, QSGD and NatSGD) does not support the more efficient all-reduce primitive. Similar observation can be seen in previous works (Vogels et al., 2019; Agarwal et al., 2021).
All of PowerSGD (EF), IntSGD (Random), and IntSGD (Determ.) are consistently faster than the all- reduce-based frel-precision SGD on both tasks. Compared to IntSGD (Determ.), IntSGD (Random) leads to slightly more computation overhead due to the randomized rounding. However, IntSGD
RRssNe11: http:://g....tbooooooo///ggg//// com/ hwtpoort//eeeeeppeeeeee//aaaee/e /nttps:///gttuub.crr/ wtt.t/ttc..caaaaaaaaaa//////////
com
far; LSTM: https://github.
8

---

Published as a conference paper at ICLR 2022
Table Test accuracy and time breakdown in one iteration (on average) training ResNet18 on the CIFAR-10 10 dataset with 16 workers. All numbers of time are in millisecond (ms). In each column, the best one is highlighted in black and the second-best one is highlighted in gray.
Computation Overhead
Algorithm
Test Accuracy (%)
Communication
Total Time
SGD (All-gather)
94.65 + 0.08
261.29 0.98
338.76 + 0.76
QSGD
93.69 + 0.03
129.25 + 1.58
138.16 + 1.29
320.49 + 2.11
NatSGD
94.57 + 0.13
36.01 1.30
106.27 1.43
197.18 + 0.25
SGD (All-reduce)
94.67 + 0.17
18.48 + 0.09
74.32 + 0.06
PowerSGD (EF)
94.33 + 0.15
7.07 = 0.03
5.03 = 0.07
67.08 + 0.06
IntSGD (Determ.)
94.43 + 0.12
2.51
0.04
6.92 0.07
64.95 +: 0.15
IntSGD (Random)
94.55 + 0.13
3,20 + 0.02
6.21 + 0.13
65.22 +: 0.08
(Determ.) fails to match the testing performance of SGD on the language modeling task. Compared PowerSGD (EF), our IntSGD variants are better on the task of training ResNet18 but inferior on the task of training 3-layer LSTM. Although IntSGD is not always better than PowerSGD (EF), there are several scenarios where IntSGD is preferrable as explained in Section and Section 3.4. In addition, seen in Figure 3 of the Appendix C.3, PowerSGD (EF) converges much slower than SGD and IntSGD the first 150 epochs of the ResNet training (which has non-smooth activations).
Table 3: Test loss and time breakdown one iteration (on average) of training 3-layer LSTM on the Wiki-text2 dataset with 16 workers. All numbers of time are in millisecond (ms). In each column, the best one is highlighted black and the second-best one is highlighted in gray.
Computation Overhead
Algorithm
Test Loss
Communication
Total Time
SGD (All-gather)
4.52 + 0.01
733.07 + 1.04
796.23 + 1.03
QSGD
4.63 + 0.01
43.67 + 0.11
307.63 + 1.16
399.10 + 1.25
NatSGD
4.52 + 0.01
64.63 + 0.12
309.87 + 1.32
422.49 + 2.15
SGD (All-reduce)
4.54 +: 0.03
22.33 + 0.02
70.46 + 0.05
PowerSGD (EF)
4.52 + 0.01
4.22 + 0.01
2.10 + 0.01
54.89 + 0.02
IntSGD (Determ.)
4.70 + 0.02
3.04 0.01
6.94 0.05
57.93 + 0.03
IntSGD (Random)
4.54 + 0.01
4.76 + 0.01
7.14 + 0.04
59.99 + 0.01
CONCLUSION
In this paper, we propose the provably convergent and computationally cheap IntSGD algorithm for efficient distributed machine learning. The core component of IntSGD is the adaptively estimated scaling factor shared by all users, which makes compatible with the widely used communication primitive all-reduce and the recently proposed in-network aggregation (INA) (Sapio et al., 2021). The convergence rates of IntSGD match that of SGD up to constant factors on a broad spectrum of problems. Experimental results on two deep learning tasks show its promising empirical perfor- mance. A limitation of our algorithm is that its compression ratio is bounded by 4, but we hope to address this in future work.

---

Published as a conference paper at ICLR 2022
Reproducibility statement. Regarding the theoretical results: We describe the mathematical set- ting and algorithms in Section 1, 2, and Appendix A; Assumptions and the main theoretical results presented in Section 3; We provide the complete proof for those results in Appendix B. Regard- ing the experimental results: We report the number repetitions, the computing infrastructure used, the range of sayper-parameee We attach our code in the supplementary material.
considered, and the evaluation metrics in Section 5 and Appendix C.I;;
REFERENCES
Saurabh Agarwal, Hongyi Wang, Shivaram Venkataraman, and Dimitris Papailiopoulos. On the utility gradient compression in distributed training systems. arXiv preprint arXiv:2103.00543, 2021.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD:
Communication-fficieett SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In The 33th International Conference on Machine Learning, pp. 699-707, 2016.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Arizzadenesheli, and Animashree Anandkumar. SignSGD: Compressed optimisation for non-convex problems. In Jennifer Dy and Andreas Krause (eds.), Proceedings the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 560-569, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compres- sion for distributed learning. arXiv:2002.124100 2020.
Lisandro Dalcín, Rodrigo Paz, and Mario Storti. MPI for Python. Journal of Parallel and Distributed Computing, 65(9): 1115, 2005.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. BERT:
Pre-training of deep
bidirectional transformers for language understanding. arXiv preprint arXiv: 18100008/10048800 2018.
Robert M. Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for machine learning. Proceedings of the IEEE, (1811))1168-198) 2020.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2200-5209, Long Beach, Califor- nia, USA, 09-15 Jun 2019. PMLR.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint 17X.vv:700.02000 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint Sttt::5503.053.11 2015.
Samuel Horváth, Chen-Yu Ho, L'udovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint arXiv: 10988, 2019.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
10

---

Published as a conference paper at ICLR 2022
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:315-3222 1211113-3,32 2013.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In International Conference on Machine Learning, pp. 3252-3261, 2019.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with com- pressed gradients. arXiv preprint arXiv: 06573, 2018
Anastasia Koloskova, Tao Lin, Scbastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint /00.00999709935 2019.
Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Algorithmic Learning Theory, pp. 451-467. PMLR, 2020.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik, Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.000 0996999 2019.
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87, Springer Science & Business Media, 2013.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8821-882 1-811. PMLR, 18 24 Jul 2021.
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication com- pression in distributed and federated learning and the search for optimal compressor. arXiv preprint arXiv:2002.08955 2020.
Amedeo Sapio, Marco Canini, Chen-Y Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan R. K. Ports, and Peter Richtárik. Scaling distributed ma- chine learning with ne-nek aggregation. To appear in 18th USENIX Symposium on Networked Systems Design and Implementation, 2021.
Sebastian U. Stich, SannBBaptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, pp. 4447-4458, 2018.
Thijs Vogels, Sai Pranceth Karinireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. Advances In Neural Information Processing Systems 32 (Nips 2019), 32(CONF), 2019.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. ATOMO: Communication-effie efficient learning via atomic sparsification. Advances in Neu- ral Information Processing Systems, 31:9850-9861, 2018.
Hang Xu, Chen-Yu Yu Ho, Ahmed M. Abdelmoniem, Aritra Dutta, El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, and Panos Kalnis. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report, 2020.

---

end for end for Published as a conference paper at ICLR 2022
Appendix
A OTHER VARIANTS OF INTSGD
A.1 OTHER CHOICES OF SCALING FACTOR Oi
In Section 4.1, we provide an effective scaling factor with the moving average and the safeguard. However, there are other choices of scaling factor that also satisfy Assumption 1, and the conver- gence proof still goes through.
Proposition 3 (Adaptive ay.). we choose
Va Ofk /2n 2 g I1I
then Assumption 1 holds with and 0.
One can also consider applying an integer quantization with individual values of a for each co- ordinate or block, for instance, with an 0t, corresponding the I-th layer in a neural network.
straightforward see that this modification leads to the error Σ di of where B is the total number of blocks and di is the dimension of the I-th block.
Proposition 4 (Adaptive block az.). Assume we are given partition of all coordinates into B S d blocks with dimensions d dp, and denote by (x*)), the 1-th block of coordinates of x* Then Assumption holds with
Te V ( V2n||(=* (2 Dill
for I....,..
B.
There are two extreme cases in terms of how we can choose the blocks. One extreme is set B 1, in which case we have single scalar for the whole vector. The other extreme is to use B which means that ag 2/7pa" where the division and absolute values are computed coordinate-wise.
Algorithm IntSGD: adaptive block quantization
Input: _0 E R2, [0, 1), 0, x²
=x0
no Σn df partitioning of Rd into B blocks Rd
of sizes d,, .,.....4 d such that Idd Rd
2: for k = 1. 2.. do
3: for each device = 1, 2, ...., n do
4: Compute independent stochastic gradients of (Ea[g (z)(())) Maintain the exponetial moving average: Th,1 Br (1-8)((22)) -cx (for each block = l...., B)
5:
6:
Compute the adaptive scaling factors: dge1 V 2nra. on 452
7:
Scale and round the local gradient (Q(x))) = Int(on. end for
8:
9:
Aggregate Qgg.t k) by either all-reduce or in-network aggregation (INA)
10:
for each device = 1,,,..., n do
11:
Compute the (sub)gradient estimator: (ī*); nai,
1 Σn (Q((((9)))
2+1 x n
13:
14:
Compression efficiency of IntSGD with adaptive block quantization. Our block-wise and coordinate-wise compression can further benefit from reduced dimension factors in the upper bounds, leading to the estimate of log, 2/ bits for block with dimension dr. However, for smaller blocks is less likely happen that [1 ( (x*-1) [[ )xll, the estimate should be taken
Vir
12

---

Published as a conference paper at ICLR 2022
Algorithm 3 IntDIANA
1: Params: Stepsizes 'Jk, scaling vectors ouk E R.d
2: Init: 5. E RRd x² = r.0 70 Ei=1 L. h = 0, = 00
3: for 1.2.... do
4: for each device = 1, 2, do
5: Compute stochastic gradient of (E g 2$1 E )
1/6 vi
6:
Compute the adaptive scaling factor: ak = v2n 1 -
7:
Scale and round the local gradient ((9.)) = [nt o (g kt))
8:
Update the local shift h k++ end for
= h + Q(9!)
9:
10:
Aggregate ((g.) ) by either all-reduce or in-network aggregation (INA)
for each device = 1, ...., n do
12:
Compute the (sub)gradient estimator: g = 11th + nar E. Q(o))
Update the model parameter xk+1 x 7
14:
Update global shift A++1 = h + naw
1 2i=1 Q(st))
15:
end for
16:
end for
with grain of salt. We hypothesize that using & as in Proposition is required to make block com- pression robust, Notice that if stochastic gradients have bounded coordinates, i.e., I1o llx S Go for all i, k. then we would need at most 1 + log, ydG bits to encode the integers. Since any E I + vTG does not change the rate in the non-smooth case (see Equation (9)), we get for free the upper bound of log2 /OG bits.
VTG
A.2 HANDLING HETEROGENEOUS DATA
IntSGD can be equipped with the full gradient or variance-reduced gradient estimator to enjoy faster convergence than ? +
shown in Corollary 2. For example, if we plug (no variance) and
VE
S (sufficiently small safeguard) into item 2 of Corollary 2, the convergence rate of IntSGD is O (+). However, when the data are heterogeneous (i.e., minimizing f(x) = ヒ fx(x) will not make [[V]((=)]| = O, Vi E [n]). the transmitted integer of IntSGD with a. = 0, E = 0 can be gigantically large, which leads very inefficient communications
exception value error. ), the largest integer to transmit T==- II where the denominator O while the numerator is nonzero as the iterate converges to the optimum. To alleviate this issue, one needs to compress gradient differences is done for example by Mishchenko al. (2019) in their DIANA method. By marrying IntSGD with the DIANA trick, we obtain IntDIANA (Algorithm 3).
E.g., if we choose the adaptive og and the full gradient g. = fi(**),
from worker to the master ||ag V (e(**)) R [V I
For IntDIANA with adaptive ag, the largest transmitted integer from worker the master is ||au (g 1l when * converges to the optimum, such that the issue mentioned above can hopefully be solved.
| - We will show that both the nominator and the denominator infinitesimal
Note that we can either use the full gradient of fi((x*) or the L-SVRG estimator Kovalev et al. (2020)
of = fi(a - fl e + E [V on the i-th worker. For the variance-reduced method, further assume that fo has finite-sum structure, i.e.,
f(()) = = - fa(z)
such that (z:=z) = fa(x), EVV Ir= fa)( and I is sampled from [m] uniformly at random by &
Our main convergence theorem describing the behavior of IntDIANA follows:
13

---

Published as a conference paper at ICLR 2022
Theorem 4. Assume that f is j-sttrongly convex (μ 2 0) and f(=E) has L,-Lipschitz gradient for def any 5. L 4max; Li-
1. If O, the iterates of IntDIANA with adaptive vn wi x
nva
satisfy
Tp - 0=
gf (x(xx)) we have def max {1 nHt mu, 3
For IntDIANA with the GD estimator
1 and yirk
11
1=11 + 112 x 12 +
| Vfi((*))l )l13, where
In
Me 1
2 s2n)
For IntDIANA with the L-SVRG estimator, we have def max {1 1724, 3: 8m }
and u def
|| 2²112 + I|a - 1² -12 + Sy Ei= E1=1 | Sal (w - ffa(x*) 122 122
n² 12
In Dim
||h (x()2))11 where p i and TJs 17 S 2T--22/2
2. If = 0, the iterates of IntDIANA with adaptive vn 1a - satisfy
nva
E
go S m(++1)
where at 1
K+1 1= x².
IntDIANA with the GD estimator requires that Tl: 1j S 1(L+ win)
IntDIANA with the L-SVRG estimator requires that T/s 17 1L+22/n))
The above theorem establishes linear convergence of two versions of IntDIANA in the strongly con- vex regime and sublinear convergence the convex regime.
Compression efficiency of IntDIANA. 4 > 0, for InIDIANA with adaptive og and either GD or L-SVRG estimator, both l Vf(("")) and | - 112 converge to O linearly at the same
rate, while of¹ + f((x)). Thus, the largest integer to transmit is ||au(s h )l so la. A is hopefully upper bounded.
B PROOFS
B. PROOFS FOR INTSGD
In the section, we provide the complete convergence proof of IntSGD.
B.1.1 PROOFS FOR LEMMA
Proof. Take y a æ and let Py y [v]. where [y] is the coordinate- wise floor, and Py is the vector of probabilities in the definition of Int(y). By definition it holds
[y)] = Py (lv + 1) + (1 - pw) (w] = Pv + [vl - y [w] + [w] = y,.
Plugging back = a: o x, we obtain the first claim.
Similarly,
lly Int(y) max |y Int(y j=I....d
< max max [z], [2] +1 2) 1.
=ER
After substituting y a v. remains mention
Int(a o x) 2
< Int(a o x) a x/100 max
j= Oj
14

---

Published as a conference paper at ICLR 2022
To obtain the last fact, notice that [nt(v) [y] is vector of Bernoulli random variables. Since the variance of any Bernoulli variable is bounded by z. we have
d E (Int(us)- uz) S
E o Int(a
= Σ j=1
4a 2.
j=1
The staring point of our analysis is the following recursion. Let p def || - x 8h def f(xt)
f(a*) and ç* def | E 9f 1|..
Lemma 2. Assume that either i) functions fI.....Jh .n are convex, or ii) f is convex and .i..... Sn are differentiable. Then
Es [[ S ph
2mk0* + A B*t
where A def Bx [5*] and B def error terms, respectively.
n 11 1211 are the SGD and quantization
2=== at.;
2n
B.1.2 PROOF OF LEMMA
Proof. The last term in the expression that we want to prove needed to be later used to compensate quantization errors. For this reason, let us save one
||
x=Il2 112 for later when expanding ||x
x" I=.... Consider the IntSGD step x² g++1 x Th Ei=l Q(g ) where Q(
o [In((ar of
|| x² 21 || 1=1 2
2(11 k+ xt x²) + | - 1x1
|| k x² 2(x 2x1 xt, -x)) + 21|x 20112 || 111
|| - x²112 22 Σ (Q0))) x - x²) + 2
1 Σ Q
/|2
-11
x xx113
(10)
Now let forget about the first and last terms, which will directly go into the final bound, and work with the other terms. By our assumptions, we either have T2 [x(((=))] = Exlol1 E af((2*) or
D Ex = (x("), so we obtain by convexity
n
Ex
2 Tk
(9()))
x²)
7k
En 19. -x)) - -f(xt))(xz)
n
n
Moreover, using the tower property of expectation, we can decompose the penultimate term in (10)
follows:
|T]
Eg
(o.))
= E
EQ
1=1
/|
H (Qa)) - Rxl0
Ex
E
(2(
+ BQ
Ex
En [I((())) 12]]
where in the last step we also used independence of the quantization errors (Q(gf) of).....((()))))) g
Next, we are going to deal with the quantization terms:
En [1(((t) of [2]
Σ
Ex
1
Int(as o gt) of
[
n
Σ
d
Ork
4a
j=1
Dividing both sides by n and plugging into (10), we obtain the desired decomposition into SGD and quantization terms.
15

---

Published as a conference paper at ICLR 2022
We now show how control the quantization error by choosing the scaling vector og in accordance with Assumption Lemma 3. If the assumptions of Lemma 2 hold together with Assumption 1, then
E [p S pd
nBB [04] + 2 +
n
B.1.3 PROOF OF LEMMA
Proof. Firstly, let us recur the bound in Lemma 2 from & to 0:
k
1
B [|| - x*11²] & ||
x²11
2
B
- f(x")]
+
1
9
1=0
t=
E
V k.j
E -11"'t--2'11
2n
Note that in the bound do not have 00. for any done without compression. Assumption implies for the quantization error
assume that the first communication is
1-1
m + +1 (1-B)
Σ
E ||
11
1
k
k
2
Mh + +(1 (1- -3 Σ
|| x
11
3d
t=1
k
111 + - 8) Σ
2
E || -
11 3d
t=1
1=0
E -1
x
(11)
t=1
1=1
It is clear that the latter terms get canceled when we plug this bound back into the first recursion.
B.1.4 PROOF OF THEORFM
Proof. Most of the derivation has been already obtained in Lemma and we only need to take care of the SGD terms. To do that, we decompose the gradient error into expectation and variance:
Ex
of
ExIg.
+
E&
Ex 1)
27
Eg |
+
Ex
9
Exlo,"
n
<
G
Thus, we arrive at the following corollary of Lemma 3:
0 < [||a++1 2²112] < || - 12122-2 - Σ EE [f(z)) - f(x))]
+2 >
k
(c
Ge
-
0²
E²
n
4n
1=0
Furthermore, by convexity of f we have
f( - f(x²)())))))))))))))
Σ
-
(12)
Σk Ttt
t=0
Plugging it back, rearranging the terms and dropping E [[],
x01] gives the result.
n
16

---

Published as a conference paper at ICLR 2022
B.1.5 PROOF OF PROPOSITION
Proof. Fix any By Young's 's inequality and independence of < ..... gk we have
Σ
71(4 |
||
=E
Vi( + < 11 + 2E
- 2
2
2 n
12
E
[VV 21E
Σ
V : -
Substituting the definition of o and applying Jensen's 's inequality, we derive
n E [IV =f(=2)
E
By our assumption, fi(:;)) E) is convex and has L.-Lisschitz gradient, so we can use Equation (2.1.7) in Theorem 2.5.5 in Nesterov (2013):
2E
[ ff(="; : < 4L, ( - - fi(="; (Vfi(z= xt x²)]
AL, [f( fi(x²) (VI1(==),, ---==x x²)]
I CI [f((z*)- - ff((x) - (V.((")), x0)}
Taking the average over i = I,.... n2 and noticing Σ/= V5((=*) = 0 yields
a² +
L
E
E [f((**) - fx(x) - (Vi((*), - =="}]
i=1
LE [f(=*) - f(x"))
which is exactly our claim.
B.1.6 PROOF OF THEOREM 2
Proof. The proof is almost identical to that of Theorem 1, but now we directly use Assumption 3 and plug in inside Lemma 3 to get
k
2
[|latt] - 1=] S
||
121
Σ E [f(x*) - f(x*)] +
M
9
n
2n
1=U
t=
1=1
h
02
|1
x²
2n (1 C)B [f(xt) - -fxx))
+2
1/
2
4n
1=0
(
0
2
11000 x= 112
Mr [f(xt) [(x)]] +2
7
n1
4n
Rearranging this inequality yields
2
x² Σ n. [fx')) f(x")] < 1,000 - [1
+2
m
4n
t=1
o22
E2
0 x² 122
+2
+
n
4n
To finish the proof, remains to upper bound f(**) using convexity the same way as was done in Equation (12).
17

---

Published as a conference paper at ICLR 2022
B.1.7 PROOF OF THEOREM
Proof. By L-smoothness of f we have
Ex [x < f(x*) + E&I(V ), - - -0 + マ Bu Bxlllattt - x011991
7 = [aaa²)
(x((V Q((()) + 2 Ex 11 - 11
n
2 f(x*) TH f ||
L Bxlll=tt1 - -
L
-((*) mh V )|
LE [|
- ==1131]
Ex 11ll0 - xx11
2
1"]
=f(x²) - mh f LE
Σ
L - -xllettt- =111
72
Similarly to Lemma 2, we get decomposition into SGD and quantization errors:
||
Ex E
=
Ex
EQ
(g,
= Fx
+
E
(1()((()))
n
< Ex
We proceed with the two terms separately. To begin with, we further decompose the SGD error into its expectation and variance:
Ex
Ex
Σ lof
Es
1 (s )12 +
Σ
Bs [llet {12(
n
1=1
0²
3
V ||
Moving on, we plug it back into the upper bound Ex (x++t))) Assuming Th S z.z we get
0²
L
d
Es [f(xkt]]] f(((²) TM - L) 11
+
+
Ex 1| - x1
4n
2
2
j=1
$ f((x))
?h 2
|f + n
L
Ex
h+1
- 1111
n
4n
2
j=1
Finally, reusing Equation (11) produces the bound
k
2 k
22 k
E [[[ < f(x0)
Th [V((<19111
m
+
7 L.
4n t=
1=
Notice that by Assumption pinl < f f(*++1,, so we have
B | f(x')] < f(x:0) pint +
0²
+ In
> t nh L
Σ t=
Σ The
The left-hand side is equal E |/ f+ [| by definition of .it and we conclude the proof. n
18

---

Published as a conference paper at ICLR 2022
B.1.8 PROOF OF COROLLARY 2
Proof. For the first part, have
| x= 112 2 G2 o² n
2 4n
E
Ei=
(
[
2 > 7 The other complexities follow similarly.
=
Σt Et=0 1/1
=0
k
B.1.9
PROOF OF PROPOSITION
Proof. By definition of on
E
The + 2n [rx] = n2 2n(1 B)
Σ
3 | b-
- 11-1-111
k.j
==1
B.1.10 PROOF OF PROPOSITION
Proof. Indeed, we only need to plug in the values of onk.j
k-1
E
2n
||
x* - 119
$=0
2n(1 - B) Σ
[|
x
t=0
B.1.11 PROOF OF PROPOSITION 4
Proof. Since the I-th block has coordinates, we get
B
d
U
2n
Σ E [[((a*)
2nB [1|0** k 1133 (x.*-))[13]
kij
R.(1))
B.2 PROOFS FOR INTDIANA
Assumption 5. fa) has Lu-Lipschitz gradient. We define L def 4 maxiejmi maxie[m] Li- Proposition Suppose that Assumption holds. Then, we have the following for IntDIANA and any 2 E Rdd
C (((()) f(x)))
[[a(() v(a(>)))
(13)
2
Proof. Based on Assumption 5 and Theorem 2.1.5 Nesterov (2013), we have:
[V(((z) f=((=") < 2L (fa(z) - fa(x*) (V fa(æ" ",")) - x²1))
Thus, double averaging leads to:
Vaa(x) {[a(=")|1
mm
2
Lu (fa(z) -fol=*) (Vfalz"), x²))
mm
< ma max Lu
f(x) - -(x²) - mn
fa(x"), (xx)),)) x²))
Considering that 1 Σn Em fa(x²) = 0 and defining 4 max;e maXie[m] Lst leads to the my.
claim in the proposition.
19

---

Published as a conference paper at ICLR 2022
Lemma 4. For IntDIANA (Algorithm 3) and ge def (((*)) and:
1 n
( + (( we have Es [gt]
=
1
E&
11!
+ Ex
g
(14)
4n
k.j
Proof. By definition, g = Ei= + QQ )),
so
1
1
1
Ex [
Ex [
Ex
[ot]
Σ
h
ff(tt)
T2
Thus, we have shown that o is an unbiased estimate of (z(*)). Let us proceed with the second moment of gx:
1
1
E& |1l9 |12]
Ex
o Int(ax o (o. - -k)) - (g. h + 9
12
ac
T
1
Int(ax (o) -b²)) (o) - h::) ||
1
E&
+ 1E
9
n
0xk
Int(ay o (of ht)) (0 ntt) || 1|2
27
Ex
1
+ Es
1
>
n2a
ak
72
+
Ex
4n
j=l
Lemma 5. L-SVRG estimator of = fual=" ( - vfu(w?; + uf is used in IntDIANA, we
have Ex [of]] = V and
H
17
17 S (2L + n
=) (((t)))((0)) + 2
B
(15)
11
Ex To 1] S (1 - -p)ot + PC (f(x*) - ff(x)),
(16)
where of 1 a
Ei=1
Σm m
i=1 (w vz(
Proof. Recall that E
[||XX - [ < E [[]]]]]] for any random variable X. For the L-SVRG
estimator of¹ -faa v (uf ( uft we have:
n
v((())) ||
Ex
+ EE
Σ (at v(((a*)))
< 2L (f(+t) -(x)))
(xa (la(t))
(f Vfar(w())
2TT (s(A)) 1(x'))
(**) via(at))1
n
m
P=1
2 1
2 1
22 (1(+t) - -s(x))
+
Vfa(x* v.a(<'))
+
[la(u)) - -Vla(=))1
n1. mm
YL mI
1=1
(13)
- -(xx)) x 22 2 + 1) (s(ct)-s(07))
2
20

---

Published as a conference paper at ICLR 2022
where of . Ei= En= Vfa(w()) fa(x")]1?
Based the update of control sequence in
L-SVRG, we have:
Ba
[oo
1- p
V[a(w,)) fa(x")]1
[a((x²) - fa(x"))l
mn
1=1
(13)
PL (8a*)) - -sx))) 2
S
(1 - ()- +
Lemma 6. Define 02 def 1
|
V1( For IntDIANA algorithm, we have:
i=
Es 0
k+l
I n1
Es [lllst
V/i Σ o
(17)
For the full gradient, we have 1 SVRG estimator, we have -i=1 Ex [llg vf(((*))11) S 4of + -(ff((())((()))
Σ
Ex
||lo
- ((f(=*) f((x)). For the L-
Proof. We define of def 1 E | - V1(("))12 Consider the step h k++ = h + Q(gh),
where (ga²)) = 1 o Int(ax o (g_t - h₂)). Note that Ex [(o - h/ of - 2V f((x*) + ht)) =
au
Ek [llst ff ||2 1 vf((=*)]1 which explains the last equality below:
Eg 102
1+1
= E&
1
||
vf((2))+ + ?
n1
i=1
=0
+
Ex
o Ina (ax o (o.t - -nt))
+ +
1
K [1Q())) - V
17
Okk
72
(4) k
02
1
Ex [lla] 1|]1]]] + 2
Gof
A6 - -((())))
+
Σ
1=1
1=1
j=1
Es Riot , - (V +1
n
Ex [1l9 (o((2>)133 +
j=1
For the full gradient of )z*t,, we have:
1 Ex [llst Vf(((()) 1 = - Σ Es
(
For the L-SVRG estimator, we have by Young's inequality:
2 " n
E& [llgt Vf((2))11
< 72 Σ
E& [lla Vir(a+))1
Σ [V -
n
2 n
[[a(a*)
Via -(S(x)) ((x'))
mn
4
Vfa((*) - vfa(=)) 4
Vla(w,)) + - ((x)))
-((())))(x))
i=1 1=1
1=1
(13)
<
4ot + ([ff(**) - f(x))).
21

---

Published as a conference paper at ICLR 2022
Lemma 7. Suppose that Assumption 5 holds. Besides, assume that f(-) is j--strongly convex
(a 2 0). For IntDIANA with adaptive an Vnliz m
and GD gradient estimator, we have:
En |||0 - x =1 + Ex |||a - 11
$ 51 m11))1 x=112= + ] 11 1 - 2T 2mx (ffe)) f(x))),
1
2
C (f(=t)) - f(0=-((x))) nl|0** - x==1112
En 02 1 <
2
For InIDIANA with adaptive Og and L-SVRG gradient estimator, we have:
Ex
[|| - x² [1 + Ex [| - -xx11= 13]
(1 11m-)/))1==+ - 2= + ~ 11 - 11- 2073 (1- 217
L 2m ) (f(())))( f(x²))
-((=)) + Am
ot
Ex 1o2 51 (1-1p)p p)o + PC (f(2²) - (iit)-f((0) -)(x")),
2
Eg [o s 4 3[(((x*) f(x')) nlllx* 1²h 112
Proof. By p-strong convexity, we have:
12 (Q(g)), -x²) (3) -2 7k
Ex
[E x - -x")
92
1=1
1=1
1 <mm - -f(x))) -Tollll - xx1112
Besides, || - 11112 = 2n 3 g/13 -1atht - 1=112,
Es [1|0*t] x² x=11 + Ex [| - 11]
(1 - -mm4))l1** - 20112 3 (f²*) ff(x'(()))))))))))>))) + 2T [|oa*]]]
(14)
|
n
d Σ
S (1 maH)ll x² 12 (f f(x*)) 2T
Σ
2n
j=1
Applying Proposition 3 to the obtained bound results in the following recursion
Eg [| x² 1=] + Ex [| 11
12
S (1 7111)11*** - x= 112 + E& [||e* x² 111 -n f(x'))
E
91
n
With the GD estimator, the produced bound simplifies to
Ex [||a - x= 12] [1] + Es
[||2 x* [[2]
S (1- - m/))la=* x² 112 + マタ | M 111 211 21 -(())))))((((()))
Based Lemma 6, the following is satisfied for IntDIANA with GD estimator and adaptive nvVd
Og
Vxllz
Ex 0 x+1 E (100))
((x))) + nlla** 111
|l D of [11
In turn,
Lemma
gives for L-SVRG estimator
Es
S
(2L + +) (f(x*) - f(x*)) + 2of, so we can derive that
Ep [|| x² 112] + En [1| [1
6) (n)) ( - 2n
4 o
(1 1/ - x0 "12 + |1at -111
211k
1
211s
[
22

---

Published as a conference paper at ICLR 2022
Let us now combine Equation (16) and Lemma 6:
Ex [o + 1 (1 p)o PL - )2² -
Ex 0
++1 - 40 33([((²) - [(x)) + +nll=* - -m-111
Lemma 8. We define the Lyapunov function as & def || - -x 112 + 1| x4-111 + cn +
o2 Assume that the conditions of Lemma hold. If p > O, we have:
v ++|
0E
[
where 0 def max {1 M.H) 1 G1 0,
C2
4n
L2
and 7k 2 s
for IntDIANA
with GD estimator.
Alternatively, for IntDIANA with L-SVRG estimator, we have 0 def
max { (1 m),,), (1 (1-1m)) and set C1
8m
C
L2 4n
and 1h S 3[L420/0) If
0, we have
ThE [f(*) f(x") >] S E [ E W
where S 4[L+ 3mm
for the GD variant and S I(L+2c/n)
for the L-SVRG variant.
Proof. We define the Lyapunov function as & def | - x1 + 1| - -²11112 + no + conko For IntDIANA with GD estimator, can set C₁ and derive the following inequality from Lemma 7 and 7 S T):
( cznin E [||e* -
E [ < (1 maa) [||** - xx113]] +
L+ c2L )) E [f(x*) - f(()))]
2mp
1 21T
We first consider μ case. Let C2 max {(1 MEP,) 3 E [v]].
1a and
in
m7
2(++
We have E [M*+t]] s
For IntDIANA with L-SVRG estimator, we have the following based on Lemma 7:
E [ < Ta E
|| -x=-=11"" 11] +
c2rR2)
E [|1x= -
4
vi
+
4c2
(1 p)c1
E [ot]]
m
L
Pc1C + 302L)
27 1
L 1-11
2111
EE -(0)))(((((()
Let Ci Sm
C2 4n
L2 1 and 1/s S 2L
Plugging these values into the recursion, we
get E [
< max { (1 m)),) 3. (1 8m E [.
μ 0, we instead let 7) S 4(L+ J for the GD variant and Tp S A(L22//) for the L-SVRG variant to obtain from the same recursions:
B (f(²)) f(x*)] <E K E [
C DETAILS AND ADDITIONAL RESULTS OF EXPERIMENTS
C.I MORE DETAILS
Here we provide more details of our experimental setting. We use the learning rate scaling technique (Goyal al., 2017; Vogels et al., 2019) with 5 warm-up epochs. As suggested in previous works
23

---

Published as a conference paper at ICLR 2022
(Vogels al., 2019; Alistarh al., 2017; Horváth et al., 2019), tune the initial single-worker learning rate on the preciiiin SGD and then apply it to PowerSGD, QSGD, and NatSGD.
For the task of training ResNet18 the CIFAR-10 dataset, utilize momentum 8 0.9 and weight decay with factor 10-4 (except the Batchnorm parameters) for all algorithms. All algorithms for 300 epochs. The learning rate decays by 10 times at epoch 150 and 250. The initial learning rate is tuned in the range (0.05, 0.1, 0.2, 0.5) and we choose 0.1.
For the task of training a 3-layer LSTM, all algorithms embeddings to 650, the sequence length to 30, the number of hidden units per layer to 650, and the dropout rate 0.4. Besides, tie the word embedding and softmax weights. We tune the initial learning rate in the range of {0.6, 1.25, 2.5, 5 and we choose 1.25. For both tasks, we report the results based on repetitions with random seeds {0, 1, 2}. To measure the time of computation, communication, and conpressiondecompeesiio of the algorithms, we use the timer (a Python context manager) implemented the PowerSGD code".
for 90 epochs. We set the size of word
For PowerSGD, we use rank 2 in the task of training ResNet18 on the CIFAR-10 10 dataset and rank 4 in the task of training LSTM on the Wikitext-2 dataset as suggested by Vogels al. (2019). For QSGD, we use the gradient matrix of each layer as a bucket and set the number of quantization levels to be 64 (6-bit).
C.2 TOY EXPERIMENT ON TIMINGS
8 Nodes x 2 GPUs/Node
FP32
All-Reduce Time (MS)
Int8
10a
100
106
107
# #Coordinates
Figure 2: Time of communicating FP32 and Int8 messages based on all-reduce.
Figure 2 shows the different manners of PowerSGD and IntSGD to save the communication time based on the all-reduce compared full-precision SGD: 1) IntSGD (8-bit) communicates the data with int data type but does not reduce the number of coordinates; 2) PowerSGD does not change the data type but breaks one communication round of big number of coordinates into three com- munication rounds of much smaller numbers of coordinates.
C.3 CONVERGENCE CURVES OF THE DEEP LEARNING TASKS
Please see Figure and Figure 4.
C.4 SENSITIVITY ANALYSIS OF HYPERPARAMETERS
We analyze the sensitivity IntSGD to hyperparameters 3 and 6. shown Figure 5,
the performance of IntSGD is quite stable across the choices of B E (0.0,0.3. 0.6, 0.9} and E E (10-1, 10-6, 10-$} on the two considered tasks. Overall, B 0.9 and & 10- 8 default setting for our IntSGD algorithm.
good
'https:/ //gi thub. com/epff wttp///pfmm//oowoggggggg /powersgd
24

---

Published as a conference paper at ICLR 2022
ResNet18
ResNet18
90
Test Accuracy
Test Accuracy
SGD
QSGD
70
PowerSGD(EF)
70
NatSGD
IntSGD(Determ.)
IntSGD(Determ.)
IntSGD(Random)
IntSGD(Random)
60
60
50
100
150
200
250
300
100
150
200
250
300
Epochs
Epochs
ResNet18
ResNet18
10a
10a
5GD
SGD
PowerSGD(EF)
QSGD
IntSGD(Determ.)
NatSGD
Test loss
IntSGD(Random)
Test loss
IntSGD(Determ.)
IntSGD(Random)
10a
10a
0
50
100
150
200
250
300
100
200
250
300
Epochs
Epochs
Figure 3: Convergence curves of IntSGD (Random) and IntSGD (Determ.) and the baseline algo-
rithms on the task of training ResNet18 on the CIFAR-10 dataset.
LSTM
LSTM
10a
10a
SGD
SGD
9 100
9 10
PowerSGD(EF)
QSGD
8 109
IntSGDDDeterm.)
8 109
NatSGD
Test loss
IntSGD(Random)
Test loss
IntSGD(Determ.)
7 x 100
7 10
IntSGD(Random)
1000
6 x 10
5 x 10"
5 x 10
20
40
20
40
60
80
Epochs
Epochs
LSTM
LSTM
SGD
SGD
4 102
4x
PowerSGD(EF)
QSGD
Test Perplexity
3 1
IntSGDDDeterm.)
Test Perplexity
3 302
NatSGD
IntSGD(Random)
IntSGD(Determ.)
IntSGD(Random)
x 10
2 x 10
10a
102
20
40
60
Epochs
Epochs
Figure 4: Convergence curves of IntSGD (Random) and IntSGD (Determ.) and the baseline algo-
rithms on the task of training a 3-layer L.STM on the Wikitext-2 dataset.
25

---

Published as a conference paper at ICLR 2022
Test Loss |
Test Accuracy (%)
94.7
4.600
0.9
94.6
94.6
0.9
4.57
4.58
4.57
4.595
94.6
0.6
94.5
94.5
94.4
4.59
4.59
4.59
4.590
94.5
-4.585
94.5
94.6
94.5
0.3
4.59
4.59
4.59
4.580
94.4
44575
0.0
94.7
94.7
94.3
94.3
0.0
4.60
4.59
4.60
4.570
10-6
10-6
10
10-6
10- e
10-1
Figure 5: Test accuracy the image classification task) and test loss the language modeling task) of IntSGD under different hyperparameters / and E. "1" or "I" denotes the larger, the better or vice versa.
C.5 LOGISTIC REGRESSION EXPERIMENT
Setup: We run the experiments on the fz-regularized logistic regression problem with four datasets (a5a, mushrooms, w8a, real-sim) from the LibSVM repository", where
f(x)
f((x)
m
and
m m
X2 |1:11
[(x))
log(1 exp(- (ap(-ATTarr.)))
and x E Rd, Ag is chosen proportionally to 1 and A,, E Rd b,, E {-1,1} are the feature and label of i-th data point on the i-th worker. The experiments are performed on a machine with 24 Intel(R) Xeon(R) Gold 6246 CPU @ 3.30GHz cores, where 12 cores are connected to socket (there are two sockets in total). All experiments use 12 cpu cores and each core is utilized worker. The communications are implemented based on the MPI4PY library Dalcín et al. (2005). The "optimum" x* obtained by running GD with whole data using one cpu core until there are 5000 iterations or [[ < 10
Table 4: Information of the experiments le-regularized logistic regression.
Dataset
#Instances N
Dimension
X2
a5a
6414
123
5 10-4
mushrooms
8124
112
6 x 10-4
w8a
49749
300
10-4
real-sim
72309
20958
5 x 10-5
The whole dataset is split according to its original indices into n folds, and each fold is assigned to local worker, i.e., the data are heterogeneous. There m [ data points each worker. For each dataset, we run each algorithm multiples times with 20 random seeds for each worker. For the stochastic algorithms, we randomly sample 5% of the local data minibatch (i.c.. batch size to estimate the stochastic gradient of on each worker. We set = in VR-IntDIANA.
"htps://www.csie.mttt edu tw/ gjin///bssmmoookdasss/sinnan.nne
26

---

Published as a conference paper at ICLR 2022
Apart from IntSGD with of GD or L-SVRG estimator (called IntDIANA and VR-IntDIANA, respectively).
(x(" (IntGD), also evaluate IntDIANA (Algorithm 3) with the
1ee22
100
500
VT. WT-HIDNNAAL-D
211 127
10"1
32
12
10.4
1033
2031
#gix2hten
2100
1102
2231
#grcdim
1331
2XC
#grucmm
Prashoorn, mo12
7
1003
2000
3003
4000
3006
2000
3500
4030
1300
2000
3300
4000
Figure 6: Objective gaps and the max integer in the aggregated vector Σ Q(g.).
As shown in Figure 6, IntSGD with of = (x (IntGD) suffers from low compression efficiency issue (very large integer in the aggregated vector Σi=1 )(a and IntDIANA can solve this issue and only requires less then bits per coordinate the communication. IntDIANA with SVRG gradient estimator (VR-InDDINNA) further improves IntDIANA with GD estimator in terms of gradient oracles.
27


Reviews:
[{"review_id": "nf9lPOPJ6-", "reviewer": "Reviewer_GF5a", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The authors find a clever scaling factor that makes the convergence proof work. In the experiments, they show that their method works best on one task, but not as well as PowerSGD on another task.\n\n* Can this approach be extended to popular optimization methods such as Adam?\n* In Table 2, it will be useful to have the results for Heuristic SGD as well. How does Heuristic SGD perform without the factor $n$ in the denominator of the scaling factor? That will reduce the quantization error, at the cost of removing the protection against overflow. There is no guard against overflow in IntSGD as well.\n\nMinor:\n* In Algorithm 1, line 6, is $\\| x^k - x^{k-1} \\|^2$ a scalar? Is $r_0 = 0 \\in R^d$? That would mean all the entries of $r_k$ are equal at any iteration $k$. Looking at Algorithm 2 in the appendix clarifies this, but the authors should explain this in the main text.\n* Page 6: What is the linear speedup with respect to?\n* After Assumption 1, the authors claim they show several choices of scaling factors $\\alpha$. But they show only one choice (the other choice in the supplement is a special case of the first choice) Please adjust the claim accordingly.\n* In Tables 1, 2, why are the communication latencies so different for IntSGD(Determ) and IntSGD (Random)? The discrepancies are too high be explained with the standard deviations reported.\n* Please run through a spell-checker to fix the few typos.\n", "summary_of_the_paper": "The authors propose a quantized parallel SGD where the gradient coordinates are rounded after scaling: $Q_\\alpha(g) = $ round$(\\alpha g )/\\alpha.$ The scaling factor $\\alpha$ determines the quantization error: higher the $\\alpha$, lower the quantization error. The authors propose a clever $\\alpha$ shared across workers. Such sharing of $\\alpha$ allows for in-network aggregation of gradient updates using programmable switches. It also allows for an all-reduce model of parallel SGD which can be much more efficient than the all-gather model. A previous version Heuristic IntSGD uses a scaling factor that is more intuitive (uses all available bits binning the known range), but interestingly its accuracy is suboptimal on some tasks. Other integer rounding methods such as QSGD use a scale $\\alpha$ that is not the same across workers and hence it does not allow the all-reduce primitive.\n\n", "summary_of_the_review": "The scaling factor proposed by the authors helps them show convergence of their quantized SGD. Empirically, the authors were able to show that their method beats competitors only one task out of the two considered. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KL76X_x8KeC", "reviewer": "Reviewer_7fYz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "PAPER SUMMARY: This paper presents a new compression algorithm for distributed machine learning, the algorithm is similar to QSGD, but uses a global scaling factor that is known to all parties. This adds additional benefits that the compressed results on each worker are addable.\n\nNOVELTY & SIGNIFICANCE: Having compression results directly addable is a very useful property to support broader range of applications and improve the system performance.\nThe algorithm itself seems to be a simple trick based on QSGD (and indeed), but this simple trick seems to be quite effective. There are existing work on this topic (such as heuristic-SGD that was referenced in this paper). This paper adds theoretical analysis and better scaling factor choice.\n\nTECHNICAL SOUNDNESS: The proof should be easy just following existing QSGD theoretical analysis with minor modifications. The only concern would be if the magnitude on different party varies a lot, there will be much larger compression error for the parties with smaller magnitude. But this shouldn't affect the (asymptotic) convergence rate.\n\nOTHERS Experiments look fine.\n", "summary_of_the_paper": "QSGD with compression results addable", "summary_of_the_review": "This paper proposes a new compression algorithm for distributed deep learning where the compression results are addable). There are existing work on this topic, and the main contributions of this paper are providing theoretical analysis and giving better scaling factor choice.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KFcmIP_b8WP", "reviewer": "Reviewer_q8za", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper is clearly written, and the experiments show that the convergence issues with the nearest competitor (HeuristicSGD) are not just theoretical.  The main contribution really does seem to be the theoretical analysis of the convergence behavior.  The timing results show a 10-15% improvement over uncompressed distributed SGD (the all-reduce version); not a bad improvement, but not enormous, either.  The point remains that the proposed method requires only all-reduce communication (unlike many competitors) and does not require error feedback (unlike PowerSGD), and so does have a number of advantages over recently-published competitors.\n\nI would have appreciated a little discussion of any shortcomings of the method, or next steps for future work.\n\nAlso, though I appreciated the experimental results, having a little more about the IntDIANA results in the body text (as opposed to the appendix) would have been more consistent with the claim that this is a main contribution of the paper.\n\nMinor issues: \n\n- \"By combing (5) and (3)\" -> \"By combining (5) and (3)\"\n\n- \"image classifcation\" -> \"image classification\"\n\n- I do not understand the red-blue color coding in some of the equations.\n\n- In the experiments, are the data types float32 (for computation + SGD communication) and int8 for the intSGD communication?  This seems likely based on the communication timing, but it's hard to be sure.", "summary_of_the_paper": "The paper introduces a randomized compress-to-integer operator with a shared scaling factor for use in data communication in distributed SGD.  The resulting algorithm is provably convergent, matches the behavior of SGD up to constant factors, and works well with the all-reduce primitive.  The authors claim three main contributions: the IntSGD algorithm itself, the analysis of convergence rates, and the IntDIANA variant for heterogeneous data distributions (though this is only discussed in the appendices).", "summary_of_the_review": "The proposed algorithm represents an improvement in theory over the nearest competitor (the Heuristic IntSGD algorithm), requires only all-reduce style communication, and does not require error feedback.  Though the performance improvements in experiments were not enormous, there certainly were improvements.  I'd like to see the paper in ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a theoretically sound and practically effective method to compress quantized gradients and reduce communication in distributed optimization. The method is interesting and worth publication.
Decision: Accept (Spotlight)