Year: 2021

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 nonsmooth functions, with and without overparameterization. Moreover, our algorithm can also be tailored for the popular all-reduce primitive and shows promising empirical performance.

heading: 1 INTRODUCTION
text: Many recent breakthroughs in machine learning were made possible due to the introduction of large, sophisticated and high capacity supervised models whose training requires days or even weeks of computation (Hinton et al., 2015; He et 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 a distributed fashion across a 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 synchronization of gradients computed in a parallel fashion. Formally, to train a model, we want to solve the problem of parallel/distributed minimization of the average of n functions:
min x∈Rd
[ f(x)
def = 1n n∑ i=1 fi(x) ] , fi(x) def = Eξ[fi(x; ξ)], (1)
where we will compute the gradients of stochastic realizations fi(x; ξ). The two dominating protocols for gradient synchronization are all-reduce and 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-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).
A 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 from a worker to the server to the number of bits needed to represent it. Based on this abstraction, various elaborate vector compression techniques (see Table 1 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 is 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-gather implementation.
• Secondly, some compressors rely on expensive operations such as low-rank decomposition (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) to ensure the convergence. Alas, error feedback needs extra sequences that may not fit the low memory budget of GPUs. Moreover, to the best of our knowledge, no 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 et al., 2021). The first key component of SwitchML is the in-network aggregation (INA) by a programmable switch. INA reduces the communication cost and latency because the execution can be paralleled and pipelined. To be specific, it splits the vector to aggregate into chunks and processes them individually by the switch pipeline. The advantages 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 SwitchML 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 computation capability of the modern programmable switch, which only supports integer additions or logic operations. To increase the rounding precision, the gradient gki on device imultiplies a positive scaling factor αk known to every worker and then rounded to an integer number Int(αk ◦ gki ). 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 nαk to update the model.
However, Sapio et al. (2021) remark that the choice of the scaling factor αk requires special care. In their presentation1, one of the authors notes: “A bad choice of scaling factor can reduce the performance.” To this end, they propose a heuristic-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 as 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 αk that do not require the profiling employed by Sapio et al. (2021). As we will show in the remainder of the paper, our algorithm is perfectly suited for both in-network aggregation (INA) of SwitchML and for other efficient primitives such as all-reduce.

heading: 1.1 CONTRIBUTIONS
text: 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 a better alternative to the Heuristic IntSGD in (Sapio et al., 2021) that requires expensive operations and does not ensure convergence.
• 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 to constant factors. Our results are tight and apply to both convex and nonconvex problems. Our analysis does not require any extra assumption compared to those typically invoked for SGD. In contrast to other compression-based methods, IntSGD has the same rate as 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 issue it shares with vanilla SGD—and propose an alternative method, IntDI-
1https://youtu.be/gBPHFyBWVoM?t=606
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 et 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.

heading: 2 ADAPTIVE INTEGER ROUNDING AND INTSGD
text: By randomized integer rounding we mean the mapping Int : R→ Z defined by
Int(t) def=
{ [t] + 1, with probability pt def = t− [t],
[t], with probability 1− pt, where [t] denotes the floor of t ∈ R, i.e., [t] = k ∈ Z, where k is such that k ≤ t < k+ 1. Note that
E [Int(t)] = (t− [t])([t] + 1) + ([t] + 1− t)[t] = t.
We extend this mapping to vectors x ∈ Rd by applying in element-wise: Int(x)i def = Int(xi).

heading: 2.1 ADAPTIVE INTEGER ROUNDING
text: Given a scaling vector α ∈ Rd with nonzero entries, we further define the adaptive integer rounding operator Q : Rd → Rd by
Q(x) def = 1α ◦ Int(α ◦ x), (2)
where a ◦ b def= (a1b1, . . . , adbd) ∈ Rd denotes the Hadamard product of two vectors a = (a1, . . . , ad) ∈ Rd and b = (b1, . . . , bd) ∈ Rd. As we show below, the adaptive integer rounding operator (2) has several properties which will be useful in our analysis. In particular, the operator is unbiased, and its variance can be controlled by choice of a possibly random scaling vector α ∈ Rd++. Lemma 1. For any x ∈ Rd and α ∈ Rd++, we have
1 α ◦ E [Int(α ◦ x)] = x, (3) E [∥∥ 1 α ◦ Int(α ◦ x)− x ∥∥2] ≤ d∑
j=1
1 4α2j , (4)
Algorithm 1 IntSGD. Default setting for the tested problems: β = 0.9, ε = 10−8.
1: Params: Stepsizes ηk, scaling vectors αk ∈ Rd 2: Init: x0 ∈ Rd, x1 = x0 − η0 1n ∑n i=1 g 0 i 3: for k = 1, 2, . . . do 4: for each device i = 1, 2, . . . , n do 5: Compute stochastic gradient gki (E [ gki | xk ] ∈ ∂fi(xk)) 6: Maintain the moving average: rk = βrk−1 + (1− β)‖xk − xk−1‖2 {rk is a scalar} 7: Compute the adaptive scaling factor: αk = √ d√
2nrk/η2k+ε 2
8: Scale and round the local gradient Q(gki ) = Int(αk ◦ gki ) 9: end for
10: Aggregate Q(gki ) by either all-reduce or in-network aggregation (INA) 11: for each device i = 1, 2, . . . , n do 12: Compute the (sub)gradient estimator: g̃k = 1nαk ∑n i=1Q(g k i ) 13: Update the model parameter xk+1 = xk − ηkg̃k 14: end for 15: end for
The expectations above are taken with respect to the randomness inherent in the rounding operator.

heading: 2.2 NEW ALGORITHM: INTSGD
text: We are ready to present our algorithm, IntSGD. At iteration k, each device i computes a stochastic (sub)gradient vector gki , i.e., a vector satisfying
E [ gki | xk ] ∈ ∂fi(xk). (5)
Prior to communication, each worker i rescales its stochastic (sub)gradients gki using the same vector αk ∈ Rd++, and applies the randomized rounding operator Int. The resulting vectors Int(αk ◦ gki ) are aggregated to obtain ∑n i=1 Int(αk ◦ gki ), which is also an integer. Each device subsequently performs division by n and inverse scaling to decode the message, obtaining the vector
g̃k def = 1nαk ◦ n∑ i=1 Int(αk ◦ gki ) = 1n n∑ i=1 1 αk ◦ Int(αk ◦ gki ) (2) = 1n n∑ i=1 Q(gki ).
Here αk is a random adaptive scaling factor calculated based on the historical information. We left the design of αk to Section 4. By combining (5) and (3), we observe that gk is a stochastic (sub)gradient of f at xk. Finally, all devices perform in parallel an SGD-type step of the form xk+1 = xk−ηkg̃k and the process is repeated. Our IntSGD method is formally stated as Algorithm 1 with the suggested rule of α.
Relation to QSGD (Alistarh et al., 2017). QSGD bears some similarity to the IntSGD: Both of them scale gki by a factor before the quantization (the scaling factor in QSGD is 1/‖gki ‖ 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/‖gki ‖ 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 αk 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 allreduce primitive while QSGD does not. As seen in the experimental results in Section 5 , this makes a big difference in empirical performance. Moreover, the proof technique for IntSGD is also intrinsically different from that of QSGD. Please see the next section for the details.

heading: 3 ANALYSIS OF INTSGD
text: To establish convergence of IntSGD, we introduce the following assumption on the scaling vector αk = (αk,1, . . . , αk,d) > ∈ Rd++.
Assumption 1. There exists β ∈ [0, 1) and a sufficiently small ε > 0 such that d∑ j=1 E [ η2k α2k,j ] is
bounded above by η2kε 2 + 2n(1− β) k−1∑ t=0 βtE [ ‖xk−t − xk−t−1‖2 ] .
While this assumption may look exotic, it captures precisely what we need to establish the convergence of IntSGD, and it holds for several practical choices of αk, including the one shown in Section 4 and more choices in Appendix A.1.
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[‖Q(g) − g‖2] ≤ ω‖g‖2 for some ω > 0. For them, the convergence theory is simply a plug-in of the analysis of 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 ‖g‖2 → 0. Moreover, to estimate αk adaptively, we use the values of past iterates, which makes its value itself random, so the analysis of Compressed SGD cannot apply. As shown in our proofs, an extra trick is required: we reserve an additional term ∑k t=0 E[‖xt+1 − xt‖2] to control the variance of the rounding. Furthermore, the analysis of moving-average estimation is particularly challenging since the value of αk is affected by all past model updates, starting from the very first iteration.

heading: 3.1 NON-SMOOTH ANALYSIS: GENERIC RESULT
text: Let us now show that IntSGD works well even on non-smooth functions.
Assumption 2. Stochastic (sub)gradients gk1 , . . . , gkn sampled at iteration k satisfy the inequalities∥∥∥ 1n n∑ i=1 Ek[gki ] ∥∥∥2 ≤ G2, 1n n∑ i=1 Ek [∥∥gki − Ek[gki ]∥∥2] ≤ σ2, (6)
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, . . . , fn be convex and Assumptions 1 and 2 be satisfied. Then
E [ f(x̂k)− f(x∗) ] ≤ ‖x0−x∗‖2+2 ( G2+σ 2 n + ε2 4n )∑k t=0 η 2 t
2 ∑k−1 t=0 ηt
,
where x̂k = 1∑k t=0 ηt ∑k t=0 ηtx t is a weighted average of iterates.

heading: 3.2 SMOOTH ANALYSIS: GENERIC RESULT
text: We now develop a theory for smooth objectives.
Assumption 3. There exist constants L, σ∗ ≥ 0 such that the stochastic gradients gk1 , . . . , gkn at iteration k satisfy Ek[gki ] = ∇fi(xk) and
Ek [∥∥∥ 1n n∑
i=1
gki ∥∥∥2] ≤ L(f(xk)− f(x∗)) + σ2∗n . (7) Assumption 3 is known as the expected smoothness assumption (Gower et al., 2019). In its formulation, we divide the constant term σ2∗ by n, which is justified by the following proposition.
Proposition 1 (Section 3.3 in (Gower et al., 2019)). Let fi(x) = Eξ[fi(x; ξ)], gki = ∇fi(xk; ξki ), and fi(·; ξ) be convex and its gradient be Li-Lipschitz for any ξ. Then, the second part of Assumption 3 is satisfied with σ2∗ def = 2n ∑n i=1 Eξ [ ‖∇fi(x∗; ξ)‖2 ] and L def= 4 maxi=1,...,n Li.
Gower et al. (2019) state and prove this result in a more general form, so for the reader’s convenience, we provide a proof in the appendix.
Theorem 2. Assume that f is convex and Assumption 3 holds. If ηk ≤ 12L and x̂ k = 1∑k t=0 ηt ∑k t=0 ηtx t is a weighted average of iterates, then
E [ f(x̂k)− f(x∗) ] ≤ ‖x0−x∗‖2+2
( σ2∗ n + ε2 4n )∑k t=0 η 2 t
2 ∑k t=0 ηt
.
Corollary 1 (Overparameterized regime). When the model is overparameterized (i.e., the losses can be minimized to optimality simultaneously: σ∗ = 0), we can set ε = 0 and obtain O ( 1 k ) rate.

heading: 3.3 NON-CONVEX ANALYSIS: GENERIC RESULT
text: We now develop a theory for non-convex objectives. Assumption 4. The gradient of f is L-Lipschitz and there exists f inf ∈ R such that f inf ≤ f(x) for all x. Furthermore, for all i and k we have
E [ ‖gki −∇fi(xk)‖2 ] ≤ σ2. (8)
Our main result in the non-convex regime follows. Theorem 3. Let f be L-smooth and let Assumption 1 hold. If ηk ≤ 12L for all k, then
E [ ‖∇f(x̂k)‖2 ] ≤ 2 f(x0)−f inf+ ( σ2 n + ε2 4n )∑k t=0 η 2 tL∑k
t=0 ηt .
where x̂k is sampled from {x0, . . . , xk} with probabilities proportional to η0, . . . , ηk.

heading: 3.4 EXPLICIT COMPLEXITY RESULTS
text: Having developed generic complexity results for IntSGD in the non-smooth (Section 3.1), 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 αk satisfying Assumption 1, we recover the following complexities: (i) if f1, . . . , fn are convex, Assumption 2 is satisfied and ηt = η =
‖x0−x∗‖√ k(G2+σ2/n)
= O (
1√ k
) for
t = 0, . . . , k, then
E [ f(x̂k)− f(x∗) ] = O ( σ+ε√ kn + G√ k ) ; (9)
(ii) if f is convex, Assumption 3 holds and ηt = min { 1 2L , ‖x0−x∗‖ √ n√
k(σ∗+ε)
} , then
E [ f(x̂k)− f(x∗) ] = O ( σ∗+ε√ kn + ‖x 0−x∗‖ k ) ;
(iii) if f is non-convex, Assumption 4 holds and ηt = min { 1 2L , √ (f(x0)−f inf )n√
k(σ+ε)
} , then
E [ ‖∇f(x̂k)‖2 ] = O ( σ+ε√ kn + f(x 0)−f inf k ) .
Based on Corollary 2, our IntSGD has linear speed-up in case (ii) and (iii).
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 ( σ√ kn + ( G k )2/3) rate in Koloskova et al. (2019) when assuming the second moment of stochastic gradient is bounded by G2. Compared to their result, our rate is never worse and does not require the second moment of stochastic gradient to be bounded, which is 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 ( σ√ δk ) convergence rate of EF-SGD only for the single-worker case (n = 1), which is 1√ δ
-times worse than IntSGD (δ 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-smooth function when there are multiple workers. In contrast, our IntSGD has the same rate as SGD under the same set of assumptions.

heading: 4 DESIGN OF SCALING FACTORS

heading: 4.1 ADAPTIVE SCALING FACTOR WITH THE MOVING AVERAGE AND SAFEGUARD
text: We now present an effective rule of adaptive αk (presented in Algorithm 1) that satisfies Assumption 1 for the convergence rates listed in previous section. In the appendix, we provide more options that also satisfy Assumption 1 and the proof still goes through. For simplicity, we assume that the first communication is exact, which allows us to estimate αk adaptively without worrying about α0. Proposition 2. Assumption 1 holds if we choose β ∈ [0, 1), ε ≥ 0 and αk = √ d√
2nrk/η2k+ε 2 , where
rk = βrk−1 + (1− β)‖xk − xk−1‖2. Remark 1. Here β ∈ [0, 1) is a constant factor to control the moving average update of rk, which prevents the scaling factor αk from changing too rapidly. ε2 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 β and ε in Appendix C.4.

heading: 4.2 COMPRESSION EFFICIENCY
text: 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 ‖xk − xk−1‖ ≈ ‖ηkgki ‖ with some i. The adaptive scheme with β = 0, ε = 0 gives αk = ηk √ d√ 2n‖xk−xk−1‖ ≈ ηk √ d√ 2n‖xk+1−xk‖ = √ d√ 2n‖gki ‖ , so that ‖αkgki ‖∞ =
√ d√
2n ‖gki ‖∞ ‖gki ‖
≤ √ d√
2n . Since we only use signed integers, we need at most 1 + log2
√ d√
2n bits for each
coordinate. For instance, for d ∼ 1010 and n ∼ 100, the upper bound is 1 + log2( √
5 · 107) < 14 bits. The situation becomes even better when ‖gki ‖ ‖gki ‖∞, i.e., when the stochastic gradients are dense. This property has been observed in certain empirical evaluations for deep neural networks; see for example the study in (Bernstein et al., 2018).

heading: 5 EXPERIMENTS

heading: 5.1 SETUP
text: We empirically compare our IntSGD algorithm with several representative and strong baselines: SGD, Heuristic IntSGD (Sapio et al., 2021), SGD, PowerSGD + Error-feedback (PowerSGD (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).
We consider two tasks: image classification by ResNet18 (He et al., 2016) on the CIFAR-10 dataset and language modeling by a 3-layer LSTM on the Wikitext-2 dataset. The neural network architectures and hyperparameters are from some public PyTorch implementations2. Our code is built on the codebase of PowerSGD3. We also borrow their all-reduce-based implementations of SGD and PowerSGD. It is worth noting that QSGD and NatSGD do not support all-reduce. Thus, we implement their collective communications by all-gather. The implementations for compression and decompression in QSGD and NatSGD are from the authors of NatSGD4. For the sake of comparison, we also implement the all-gather-based SGD. We report the results of 3 repetitions with varying seeds.
Apart from the IntSGD with randomized integer rounding (IntSGD (Random)) analyzed in our theory, we also consider the variant of IntSGD with deterministic integer rounding (IntSGD (Determ.))
2ResNet18: https://github.com/kuangliu/pytorch-cifar; LSTM: https://github. com/pytorch/examples/tree/master/word_language_model
3https://github.com/epfml/powersgd 4https://github.com/sands-lab/grace
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 to Appendix C.1.

heading: 5.2 INTSGD VS. HEURISTIC INTSGD
text: 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: int8 and int32. Note that the rule of scaling factor in Heuristic IntSGD is α = 2
nb−1 n·2max_exp , 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 overflows, it cannot guarantee convergence, even with int32 as 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 is provably convergent.

heading: 5.3 INTSGD VS. OTHER BASELINES
text: 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 allreduce-based full-precision SGD on both tasks. Compared to IntSGD (Determ.), IntSGD (Random) leads to slightly more computation overhead due to the randomized rounding. However, IntSGD (Determ.) fails to match the testing performance of SGD on the language modeling task. Compared to PowerSGD (EF), our IntSGD variants are better on the task of training ResNet18 but inferior on
the task of training a 3-layer LSTM. Although IntSGD is not always better than PowerSGD (EF), there are several scenarios where IntSGD is preferrable as explained in in Section 1 and Section 3.4. In addition, as seen in Figure 3 of the Appendix C.3, PowerSGD (EF) converges much slower than SGD and IntSGD in the first 150 epochs of the ResNet training (which has non-smooth activations).

heading: 6 CONCLUSION
text: 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 it 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 performance. A limitation of our algorithm is that its compression ratio is bounded by 4, but we hope to address this in a future work.
Reproducibility statement. Regarding the theoretical results: We describe the mathematical setting and algorithms in Section 1, 2, and Appendix A; Assumptions and the main theoretical results are presented in Section 3; We provide the complete proof for those results in Appendix B. Regarding the experimental results: We report the number of repetitions, the computing infrastructure used, the range of hyper-parameters considered, and the evaluation metrics in Section 5 and Appendix C.1; We attach our code in the supplementary material.

heading: Appendix

heading: A OTHER VARIANTS OF INTSGD
text: A.1 OTHER CHOICES OF SCALING FACTOR αk
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 convergence proof still goes through. Proposition 3 (Adaptive αk). If we choose
αk = ηk √ d√
2n‖xk−xk−1‖ ,
then Assumption 1 holds with ε = 0 and β = 0.
One can also consider applying an integer quantization with individual values of αt for each coordinate or block, for instance, with an αt,l corresponding to the l-th layer in a neural network. It
is straightforward to see that this modification leads to the error ∑B l=1 dl η2k α2k,l , where B is the total number of blocks and dl is the dimension of the l-th block. Proposition 4 (Adaptive block αk). Assume we are given a partition of all coordinates into B ≤ d blocks with dimensions d1, . . . , dB , and denote by (xk)l the l-th block of coordinates of xk. Then Assumption 1 holds with
αk,(l) = ηk √ dl√
2n‖(xk)l−(xk−1)l‖ , for l = 1, . . . , B.
There are two extreme cases in terms of how we can choose the blocks. One extreme is to set B = 1, in which case we have a single scalar for the whole vector. The other extreme is to use B = d, which means that αk = ηk2√n|xk−xk−1| , where the division and absolute values are computed coordinate-wise.
Algorithm 2 IntSGD: adaptive block quantization 1: Input: x0 ∈ Rd, β ∈ [0, 1), ε ≥ 0, x1 = x0 − η0 1n ∑n i=1 g 0 i a partitioning of Rd into B blocks
of sizes d1, . . . , dB such that Rd = Rd1 × · · · × RdB 2: for k = 1, 2, . . . do 3: for each device i = 1, 2, . . . , n do 4: Compute independent stochastic gradients gki (Ek[gki ] ∈ ∂fi(xk)) 5: Maintain the exponetial moving average: rk,l = βrk−1,l+(1−β)‖(xk)l− (xk−1)l‖2 {for each block l = 1, . . . , B} 6: Compute the adaptive scaling factors: αk,l = ηk √ dl√
2nrk,l+η2k dl d ε 2
7: Scale and round the local gradient (Q(gki ))l = Int(αk,l(gki )l) 8: end for 9: Aggregate Q(gki ) by either all-reduce or in-network aggregation (INA)
10: for each device i = 1, 2, . . . , n do 11: Compute the (sub)gradient estimator: (g̃k)l = 1nαk,l ∑n i=1(Q(g k i ))l 12: xk+1 = xk − ηkg̃k 13: end for 14: end for
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 log2 √ dl 2 √ n
bits for block with dimension dl. However, for smaller blocks it is less likely to happen that ‖(xk)l−(xk−1)l‖ ≈ ‖ηk(gki )l‖, so the estimate should be taken
Algorithm 3 IntDIANA
1: Params: Stepsizes ηk, scaling vectors αk ∈ Rd 2: Init: x0 ∈ Rd, x1 = x0 − η0 1n ∑n i=1 g 0 i , h 1 i = 0, h
1 = 0 3: for k = 1, 2, . . . do 4: for each device i = 1, 2, . . . , n do 5: Compute stochastic gradient gki (E [ gki | xk ] ∈ ∂fi(xk)). 6: Compute the adaptive scaling factor: αk = ηk √ d√ 2n‖xk−xk−1‖ 7: Scale and round the local gradient Q(gki ) = Int(αk ◦ (gki − hki )) 8: Update the local shift hk+1i = h k i +Q(g k i )
9: end for 10: Aggregate Q(gki ) by either all-reduce or in-network aggregation (INA) 11: for each device i = 1, 2, . . . , n do 12: Compute the (sub)gradient estimator: g̃k = hk + 1nαk ∑n i=1Q(g k i ) 13: Update the model parameter xk+1 = xk − ηkg̃k 14: Update global shift hk+1 = hk + 1nαk ∑n i=1Q(g k i ) 15: end for 16: end for
with a grain of salt. We hypothesize that using ε as in Proposition 2 is required to make block compression robust. Notice that if stochastic gradients have bounded coordinates, i.e., ‖gki ‖∞ ≤ G∞ for all i, k, then we would need at most 1 + log2 √ dG∞ ε bits to encode the integers. Since any
ε ≤ σ + √ nG does not change the rate in the non-smooth case (see Equation (9)), we get for free the upper bound of 1 + log2 √ dG∞√ nG bits.

heading: A.2 HANDLING HETEROGENEOUS DATA
text: IntSGD can be equipped with the full gradient or variance-reduced gradient estimator to enjoy faster convergence than O ( 1√ k ) shown in Corollary 2. For example, if we plug σ∗ = 0 (no variance) and ε ≤ √ n√ k
(sufficiently small safeguard) into item 2 of Corollary 2, the convergence rate of IntSGD is O ( 1 k ) . However, when the data is heterogeneous (i.e., minimizing f(x) = 1n ∑n i=1 fi(x) will not make ‖∇fi(x∗)‖ = 0, ∀i ∈ [n]), the transmitted integer of IntSGD with σ∗ = 0, ε = 0 can be gigantically large, which leads to very inefficient communications or even exception value error. E.g., if we choose the adaptive αk and the full gradient gki = ∇fi(xk), the largest integer to transmit from worker i to the master is ‖αk∇fi(xk)‖∞ ≈ ‖∇fi(x k)‖∞ ‖xk−xk−1‖ , where the denominator is 0 while the numerator is nonzero as the iterate converges to the optimum. To alleviate this issue, one needs to compress gradient differences as is done for example by Mishchenko et al. (2019) in their DIANA method. By marrying IntSGD with the DIANA trick, we obtain IntDIANA (Algorithm 3).
For IntDIANA with adaptive αk, the largest transmitted integer from worker to the master is ‖αk(gki − hki )‖∞ ≈ ‖gki −h k i ‖∞
‖xk−xk−1‖ . We will show that both the nominator and the denominator are infinitesimal when xk converges to the optimum, such that the issue mentioned above can hopefully be solved.
Note that we can either use the full gradient gki = ∇fi(xk) or the L-SVRG estimator Kovalev et al. (2020) gki = ∇fi(xk; ξki )−∇fi(wki ; ξki ) + E [ ∇fi(wki ; ξ) ] on the i-th worker. For the variance-reduced method, we further assume that fi has a finite-sum structure, i.e.,
fi(x) = 1 m m∑ l=1 fil(x)
such that ∇fi(x; ξ) = ∇fil(x), E [∇fi(x; ξ)] = 1m ∑m l′=1∇fil′(x) and l is sampled from [m] uniformly at random by ξ.
Our main convergence theorem describing the behavior of IntDIANA follows:
Theorem 4. Assume that f is µ-strongly convex (µ ≥ 0) and f(·; ξ) has Li-Lipschitz gradient for any ξ, L def= 4 maxi Li.
1. If µ > 0, the iterates of IntDIANA with adaptive αk = η √ d√
n‖xk−xk−1‖ satisfy
E [ Ψk ] ≤ θkΨ0.
• For IntDIANA with the GD estimator gki = ∇fi(xk), we have θ def = max { 1− ηµ, 34 } < 1 and Ψk def= ‖xk − x∗‖2 + ‖xk − xk−1‖2 + η 2L2
4n2 n∑ i=1 ‖hki − ∇fi(x∗)‖2, where
ηk = η ≤ 12(L+ L32n ) ; • For IntDIANA with the L-SVRG estimator, we have θ def= max {
1− ηµ, 34 , 1− 3 8m
} < 1
and Ψk def= ‖xk − x∗‖2 + ‖xk − xk−1‖2 + 8η 2
n2 ∑n i=1 ∑m l=1 ‖∇fil(wki ) − ∇fil(x∗)‖2 +
η2L2
4n2 ∑n i=1 ‖hki −∇fi(x∗)‖2, where p = 1 m , and ηk = η ≤ 1 2(L+2L/n) .
2. If µ = 0, the iterates of IntDIANA with adaptive αk = η √ d√
n‖xk−xk−1‖ satisfy
E [ f(x̂k)− f(x∗) ] ≤ Ψ 0
η(k+1) ,
where x̂k = 1k+1 ∑k i=0 x
i. • IntDIANA with the GD estimator requires that ηk = η ≤ 14(L+ L32n ) , • IntDIANA with the L-SVRG estimator requires that ηk = η ≤ 14(L+2L/n) .
The above theorem establishes linear convergence of two versions of IntDIANA in the strongly convex regime and sublinear convergence in the convex regime.
Compression efficiency of IntDIANA. If µ > 0, for IntDIANA with adaptive αk and either GD or L-SVRG estimator, both ‖hki −∇fi(x∗)‖2 and ‖xk − xk−1‖2 converge to 0 linearly at the same rate, while gki → ∇fi(x∗). Thus, the largest integer to transmit is ‖αk(gki − hki )‖∞ ≈ ‖gki −h k i ‖∞
‖xk−xk−1‖ is hopefully upper bounded.

heading: B PROOFS

heading: B.1 PROOFS FOR INTSGD
text: In the section, we provide the complete convergence proof of IntSGD.

heading: B.1.1 PROOFS FOR LEMMA 1
text: Proof. Take y = α ◦ x and let py = y − [y], where [y] is the coordinate-wise floor, and py is the vector of probabilities in the definition of Int(y). By definition it holds
E [Int(y)] = py([y] + 1) + (1− py)[y] = py + [y] = y − [y] + [y] = y.
Plugging back y = α ◦ x, we obtain the first claim. Similarly,
‖y − Int(y)‖∞ = max j=1,...,d ∣∣yj − Int(yj)∣∣ ≤ max z∈R max ( z − [z], [z] + 1− z ) = 1.
After substituting y = α ◦ x, it remains to mention∥∥∥∥ 1α ◦ Int(α ◦ x)− x ∥∥∥∥ ∞ ≤ ‖Int(α ◦ x)− α ◦ x‖∞ max j=1,...,d 1 αj .
To obtain the last fact, notice that Int(y)− [y] is a vector of Bernoulli random variables. Since the variance of any Bernoulli variable is bounded by 14 , we have
E [∥∥∥∥ 1α ◦ Int(α ◦ x)− x ∥∥∥∥2 ] = d∑ j=1 1 α2j E [ (Int(yj)− yj)2 ] ≤ d∑ j=1 1 4α2j .
The staring point of our analysis is the following recursion. Let ρk def= ‖xk − x∗‖2, δk def= f(xk)− f(x∗) and ζk def= ‖ 1n ∑n i=1 g k i ‖2. Lemma 2. Assume that either i) functions f1, . . . , fn are convex, or ii) f is convex and f1, . . . , fn are differentiable. Then
Ek [ ρk+1 ] ≤ ρk − 2ηkδk +Ak +Bk,
where Ak def= 2η2kEk [ ζk ] and Bk def= 12n ∑d j=1 η2k α2k,j − ‖xk+1 − xk‖2 are the SGD and quantization error terms, respectively.

heading: B.1.2 PROOF OF LEMMA 2
text: Proof. The last term in the expression that we want to prove is needed to be later used to compensate quantization errors. For this reason, let us save one ‖xk+1−xk‖2 for later when expanding ‖xk+1− x∗‖2. Consider the IntSGD step xk+1−xk = ηk 1n ∑n i=1Q(g k i ), whereQ(g k i ) = 1 αk ◦Int(αk ◦gki ).
‖xk+1 − x∗‖2 = ‖xk − x∗‖2 + 2〈xk+1 − xk, xk − x∗〉+ ‖xk+1 − xk‖2
= ‖xk − x∗‖2 + 2〈xk+1 − xk, xk − x∗〉+ 2‖xk+1 − xk‖2 − ‖xk+1 − xk‖2
= ‖xk − x∗‖2 − 2ηk n n∑ i=1 〈Q(gki ), xk − x∗〉+ 2η2k ∥∥∥∥ 1n n∑ i=1 Q(gki ) ∥∥∥∥2 − ‖xk+1 − xk‖2. (10)
Now let us 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 Ek[Q(gki )] = Ek[gki ] ∈ ∂fi(xk) or 1 n ∑n i=1 Ek[gki ] = ∇f(xk), so we obtain by convexity
Ek [ −2ηk
n n∑ i=1 〈Q(gki ), xk − x∗〉
] (3) = −2ηk
n n∑ i=1 〈Ek[gki ], xk − x∗〉 ≤ −2ηk(f(xk)− f(x∗)).
Moreover, using the tower property of expectation, we can decompose the penultimate term in (10) as follows:
Ek [∥∥∥∥ 1n n∑ i=1 Q(gki ) ∥∥∥∥2 ] = Ek [ EQ [∥∥∥∥ 1n n∑ i=1 Q(gki ) ∥∥∥∥2 ]]
= Ek [∥∥∥∥ 1n n∑ i=1 EQ[Q(gki )] ∥∥∥∥2 + EQ [∥∥∥∥ 1n n∑ i=1 (Q(gki )− EQ[Q(gki )]) ∥∥∥∥2 ]]
(3) = Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] + 1 n2 n∑ i=1 Ek [ ‖Q(gki )− gki ‖2 ] ,
where in the last step we also used independence of the quantization errors (Q(gk1 ) − gk1 ), . . . , (Q(g k n)− gkn).
Next, we are going to deal with the quantization terms: n∑ i=1 Ek [ ‖Q(gki )− gki ‖2 ] = n∑ i=1 Ek [∥∥∥∥ 1αk ◦ Int(αk ◦ gki )− gki ∥∥∥∥2 ] (4) ≤ n∑ i=1 d∑ j=1 1 4α2k,j = n 4 d∑ j=1 1 α2k,j .
Dividing both sides by n2 and plugging it into (10), we obtain the desired decomposition into SGD and quantization terms.
We now show how to control the quantization error by choosing the scaling vector αk in accordance with Assumption 1. Lemma 3. If the assumptions of Lemma 2 hold together with Assumption 1, then
E [ ρk+1 ] ≤ ρ0 − 2 k∑ t=0 ηtE [δt] + 2 k∑ t=0 η2tE [ζt] + ε 2 2n k∑ t=1 η2t .

heading: B.1.3 PROOF OF LEMMA 3
text: Proof. Firstly, let us recur the bound in Lemma 2 from k to 0:
E [ ‖xk+1 − x∗‖2 ] ≤ ‖x0 − x∗‖2 − 2 k∑ t=0 ηtE [ f(xt)− f(x∗) ] + 2 k∑ t=0 η2tE [∥∥∥∥ 1n n∑ i=1 gti ∥∥∥∥2 ]
+ 1
2n k∑ t=1 d∑ j=1 E [ η2k α2k,j ] − k∑ t=0 E [ ‖xt+1 − xt‖2 ] .
Note that in the bound we do not have α0,j for any j as we assume that the first communication is done without compression. Assumption 1 implies for the quantization error
k∑ t=1 d∑ j=1 E [ η2t α2t,j ] ≤ k∑ t=1 ( η2t ε 2 + (1− β) t−1∑ l=0 βlE [ ‖xt−l − xt−l−1‖2 ])
= ε2 k∑ t=1 η2t + (1− β) k∑ t=1 ( E [ ‖xt − xt−1‖2 ] k−t∑ l=0 βl )
≤ ε2 k∑ t=1 η2t + (1− β) k∑ t=1 ( E [ ‖xt − xt−1‖2 ] ∞∑ l=0 βl )
= ε2 k∑ t=1 η2t + k∑ t=1 E [ ‖xt − xt−1‖2 ] . (11)
It is clear that the latter terms get canceled when we plug this bound back into the first recursion.

heading: B.1.4 PROOF OF THEOREM 1
text: Proof. Most of the derivation has been already obtained in Lemma 3 and we only need to take care of the SGD terms. To do that, we decompose the gradient error into expectation and variance:
Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] = ∥∥∥∥ 1n n∑ i=1 Ek[gki ] ∥∥∥∥2 + Ek [∥∥∥∥ 1n n∑ i=1 (gki − Ek[gki ]) ∥∥∥∥2 ]
= ∥∥∥∥ 1n n∑ i=1 Ek[gki ] ∥∥∥∥2 + 1n2 n∑ i=1 Ek [∥∥∥∥gki − Ek[gki ]∥∥∥∥2 ]
(6) ≤ G2 + σ
2
n .
Thus, we arrive at the following corollary of Lemma 3: 0 ≤ E [ ‖xk+1 − x∗‖2 ] ≤ ‖x0−x∗‖2− 2 k∑ t=0 ηtE [ f(xt)− f(x∗) ] + 2 k∑ t=0 η2t ( G2 + σ2 n + ε2 4n ) .
Furthermore, by convexity of f we have
f(x̂k)− f(x∗) ≤ 1∑k t=0 ηt k∑ t=0 ηt(f(x t)− f(x∗)). (12)
Plugging it back, rearranging the terms and dropping E [ ‖xk+1 − x∗‖2 ] gives the result.

heading: B.1.5 PROOF OF PROPOSITION 1
text: Proof. Fix any i. By Young’s inequality and independence of ξk1 , . . . , ξ k n we have
E [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] = E [∥∥∥∥ 1n n∑ i=1 ∇fi(xk; ξki ) ∥∥∥∥2 ]
≤ 2E [∥∥∥∥ 1n n∑ i=1 ∇fi(x∗; ξki ) ∥∥∥∥2 ] + 2E [∥∥∥∥ 1n n∑ i=1 ( ∇fi(xk; ξki )−∇fi(x∗; ξki ) )∥∥∥∥2 ]
= 2
n2 n∑ i=1 E [ ‖∇fi(x∗; ξki )‖2 ] + 2E [∥∥∥∥ 1n n∑ i=1 ( ∇fi(xk; ξki )−∇fi(x∗; ξki ) )∥∥∥∥2 ] .
Substituting the definition of σ2∗ and applying Jensen’s inequality, we derive
E [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] ≤ σ 2 ∗ n + 2 n n∑ i=1 E [ ‖∇fi(xk; ξki )−∇fi(x∗; ξki )‖2 ] .
By our assumption, fi(·; ξ) is convex and has Li-Lipschitz gradient, so we can use Equation (2.1.7) in Theorem 2.1.5 in Nesterov (2013):
2E [ ‖∇fi(xk; ξki )−∇fi(x∗; ξki )‖2 ] ≤ 4LiE [ fi(x k; ξki )− fi(x∗; ξki )− 〈∇fi(x∗; ξki ), xk − x∗〉 ]
= 4LiE [ fi(x k)− fi(x∗)− 〈∇fi(x∗), xk − x∗〉 ]
≤ LE [ fi(x k)− fi(x∗)− 〈∇fi(x∗), xk − x∗〉 ] .
Taking the average over i = 1, . . . , n and noticing ∑n i=1∇fi(x∗) = 0 yields
E [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] ≤ σ 2 ∗ n + L n n∑ i=1 E [ fi(x k)− fi(x∗)− 〈∇fi(x∗), xk − x∗〉 ]
= σ2∗ n
+ LE [ f(xk)− f(x∗) ] ,
which is exactly our claim.

heading: B.1.6 PROOF OF THEOREM 2
text: Proof. The proof is almost identical to that of Theorem 1, but now we directly use Assumption 3 and plug it in inside Lemma 3 to get E [ ‖xk+1 − x∗‖2 ] ≤ ‖x0 − x∗‖2 − 2
k∑ t=0 ηtE [ f(xt)− f(x∗) ] + 2 k∑ t=0 η2tE [∥∥∥∥ 1n n∑ i=1 gti ∥∥∥∥2 ] + ε2 2n k∑ t=1 η2t
(7) ≤ ‖x0 − x∗‖2 − k∑ t=0 2ηt(1− ηtL)E [ f(xt)− f(x∗) ] + 2 ( σ2∗ n + ε2 4n ) k∑ t=1 η2t
≤ ‖x0 − x∗‖2 − k∑ t=0 ηtE [ f(xt)− f(x∗) ] + 2 ( σ2∗ n + ε2 4n ) k∑ t=1 η2t .
Rearranging this inequality yields
k∑ t=0 ηtE [ f(xt)− f(x∗) ] ≤ ‖x0 − x∗‖2 − E [ ‖xk+1 − x∗‖2 ] + 2 ( σ2∗ n + ε2 4n ) k∑ t=1 η2t
≤ ‖x0 − x∗‖2 + 2 ( σ2∗ n + ε2 4n ) .
To finish the proof, it remains to upper bound f(x̂k) using convexity the same way as it was done in Equation (12).

heading: B.1.7 PROOF OF THEOREM 3
text: Proof. By L-smoothness of f we have
Ek[f(xk+1)] ≤ f(xk) + Ek[〈∇f(xk), xk+1 − xk〉] + L
2 Ek[‖xk+1 − xk‖2]
= f(xk)− ηk n n∑ i=1 Ek[〈∇f(xk), Q(gki )〉] + L 2 Ek[‖xk+1 − xk‖2]
(3) = f(xk)− ηk‖∇f(xk)‖2 +
L 2 Ek[‖xk+1 − xk‖2]
= f(xk)− ηk‖∇f(xk)‖2 + LEk[‖xk+1 − xk‖2]− L
2 Ek[‖xk+1 − xk‖2]
= f(xk)− ηk‖∇f(xk)‖2 + η2kLEk [∥∥∥∥ 1n n∑ i=1 Q(gki ) ∥∥∥∥2 ] − L 2 Ek[‖xk+1 − xk‖2].
Similarly to Lemma 2, we get a decomposition into SGD and quantization errors:
Ek [∥∥∥∥ 1n n∑ i=1 Q(gki ) ∥∥∥∥2 ] = Ek [ EQ [∥∥∥∥ 1n n∑ i=1 Q(gki ) ∥∥∥∥2 ]]
= Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] + 1 n2 n∑ i=1 Ek[‖Q(gki )− gki ‖2]
≤ Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] + 1 4n d∑ j=1 1 α2k,j .
We proceed with the two terms separately. To begin with, we further decompose the SGD error into its expectation and variance:
Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] = ∥∥∥∥ 1n n∑ i=1 Ek[gki ] ∥∥∥∥2 + Ek [∥∥∥∥ 1n n∑ i=1 (gki − Ek[gki ]) ∥∥∥∥2 ]
= ‖∇f(xk)‖2 + 1 n2 n∑ i=1 Ek [ ‖gki −∇fi(xk)‖2 ] (8) ≤ ‖∇f(xk)‖2 + σ 2
n .
Moving on, we plug it back into the upper bound Ek[f(xk+1)]. Assuming ηk ≤ 12L , we get Ek [ f(xk+1) ] ≤ f(xk)− ηk(1− ηkL)‖∇f(xk)‖2 + η2kL σ2
n +
L
4n d∑ j=1 η2k α2k,j − L 2 Ek[‖xk+1 − xk‖2]
≤ f(xk)− ηk 2 ‖∇f(xk)‖2 + η2kL
σ2
n +
L
4n d∑ j=1 η2k α2k,j − L 2 Ek[‖xk+1 − xk‖2].
Finally, reusing Equation (11) produces the bound
E [ f(xk+1) ] ≤ f(x0)− k∑ t=0 ηt 2 E [ ‖∇f(xt)‖2 ] + σ2 n k∑ t=0 η2tL+ ε2 4n k∑ t=0 η2tL.
Notice that by Assumption 4 f inf ≤ f(xk+1), so we have
1∑k t=0 ηt k∑ t=0 ηtE [ ‖∇f(xt)‖2 ] ≤ 2
f(x0)− f inf + ( σ2
n + ε2 4n )∑k t=0 η
2 tL∑k
t=0 ηt .
The left-hand side is equal to E [ ‖∇f(x̂k)‖2 ] by definition of x̂k, and we conclude the proof.

heading: B.1.8 PROOF OF COROLLARY 2
text: Proof. For the first part, we have ‖x0 − x∗‖2 + 2 ( G2 + σ 2
n + ε2 4n )∑k t=0 η 2 t
2 ∑k t=0 ηt
= O ( 1∑k t=0 ηt ) = O ( G+ σ+ε√ n√ k ) .
The other complexities follow similarly.

heading: B.1.9 PROOF OF PROPOSITION 2
text: Proof. By definition of αk d∑ j=1 E [ η2k α2k,j ] = η2kε 2 + 2nE [rk] = η2kε2 + 2n(1− β) k−1∑ t=0 βt‖xk−t − xk−t−1‖2.

heading: B.1.10 PROOF OF PROPOSITION 3
text: Proof. Indeed, we only need to plug in the values of αk,j : d∑ j=1 E [ η2k α2k,j ] = 2nE [ ‖xk − xk−1‖2 ] β=0 = 2n(1− β) k−1∑ t=0 βtE [ ‖xk−t − xk−t−1‖2 ] .

heading: B.1.11 PROOF OF PROPOSITION 4
text: Proof. Since the l-th block has dl coordinates, we get d∑ j=1 E [ η2k α2k,j ] = B∑ l=1 dlE [ η2k α2k,(l) ] = 2n B∑ l=1 E [ ‖(xk)l − (xk−1)l‖2 ] = 2nE [ ‖xk − xk−1‖2 ] .

heading: B.2 PROOFS FOR INTDIANA
text: Assumption 5. fil(x) has Lil-Lipschitz gradient. We define L def = 4 maxi∈[n] maxl∈[m] Lil.
Proposition 5. Suppose that Assumption 5 holds. Then, we have the following for IntDIANA and any x ∈ Rd:
1
mn n∑ i=1 m∑ l=1 ‖∇fil(x)−∇fil(x∗)‖2 ≤ L 2 (f(x)− f(x∗)) (13)
Proof. Based on Assumption 5 and Theorem 2.1.5 Nesterov (2013), we have: ‖∇fil(x)−∇fil(x∗)‖2 ≤ 2Lil (fil(x)− fil(x∗)− 〈∇fil(x∗), x− x∗〉)
Thus, double averaging leads to:
1
mn n∑ i=1 m∑ l=1 ‖∇fil(x)−∇fil(x∗)‖2
≤ 2 mn n∑ i=1 m∑ l=1 Lil (fil(x)− fil(x∗)− 〈∇fil(x∗), x− x∗〉)
≤ 2 max i max l Lil
( f(x)− f(x∗)− 〈 1
mn n∑ i=1 m∑ l=1 ∇fil(x∗), x− x∗〉 ) Considering that 1mn ∑n i=1 ∑m l=1∇fil(x∗) = 0 and defining 4 maxi∈[n] maxl∈[m] Lil leads to the claim in the proposition.
Lemma 4. For IntDIANA (Algorithm 3) and gk def= 1n ∑n i=1(h k i + Q(g k i )), we have Ek [ gk ] = ∇f(xk) and:
Ek [ ‖gk‖2 ] ≤ 1
4n d∑ j=1 1 α2k,j + Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] . (14)
Proof. By definition, gk = 1n ∑n i=1(h k i +Q(g k i )), so
Ek [ gk ] = 1
n n∑ i=1 hki + 1 n n∑ i=1 Ek [ Q(gki ) ] (3) = 1 n n∑ i=1 hki + 1 n n∑ i=1 Ek [ gki ] − 1 n n∑ i=1 hki = ∇f(xk).
Thus, we have shown that gk is an unbiased estimate of ∇f(xk). Let us proceed with the second moment of gk: Ek [ ‖gk‖2 ] = Ek
[∥∥∥∥ 1n n∑ i=1 ( 1 αk ◦ Int(αk ◦ (gki − hki ))− (gki − hki ) + gki )∥∥∥∥2 ]
(3) = Ek [∥∥∥∥ 1n n∑ i=1 ( 1 αk ◦ Int(αk ◦ (gki − hki ))− (gki − hki ) )∥∥∥∥2 ] + Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ]
= 1
n2 n∑ i=1 Ek [∥∥∥∥ 1αk ◦ Int(αk ◦ (gki − hki ))− (gki − hki ) ∥∥∥∥2 ] + Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ]
(4) ≤ 1 4n d∑ j=1 1 α2k,j + Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] .
Lemma 5. If L-SVRG estimator gki = ∇fil(xk; ξki ) −∇fil(wki ; ξki ) + uki is used in IntDIANA, we have Ek [ gki ] = ∇fi(xk) and
Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] ≤ ( 2L+ L n )( f(xk)− f(x∗) ) + 2 n σk1 , (15)
Ek [ σk+11 ] ≤ (1− p)σk1 +
pL 2
( f(xk)− f(x∗) ) , (16)
where σk1 = 1 mn ∑n i=1 ∑m l=1 ‖∇fil(wki )−∇fil(x∗)‖2. Proof. Recall that E [ ‖X − E [X] ‖2 ] ≤ E [ ‖X‖2 ] for any random variable X . For the L-SVRG
estimator gki = ∇fil(xk; ξki )−∇fil(wki ; ξki ) + uki , we have:
Ek [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] = ∥∥∥∥ 1n n∑ i=1 ∇fi(xk) ∥∥∥∥2 + Ek [∥∥∥∥ 1n n∑ i=1 ( gki −∇fi(xk) )∥∥∥∥2 ]
≤ 2L ( f(xk)− f(x∗) ) + 1
n2 n∑ i=1 1 m m∑ l′=1 ∥∥∥∥∇fil(xk)−∇fil(wki )− 1m m∑ l′=1 ( ∇fil′(xk)−∇fil′(wki ) )∥∥∥∥2 ≤ 2L ( f(xk)− f(x∗) ) + 1
n2 n∑ i=1 1 m m∑ l′=1 ∥∥∇fil(xk)−∇fil(wki )∥∥2 ≤ 2L ( f(xk)− f(x∗) ) + 2
n
1
mn n∑ i=1 m∑ l=1 ∥∥∇fil(xk)−∇fil(x∗)∥∥2 + 2 n 1 mn n∑ i=1 m∑ l=1 ∥∥∇fil(wki )−∇fil(x∗)∥∥2 (13)
≤ (
2L+ L n
)( f(xk)− f(x∗) ) + 2
n σk1 ,
where σk1 = 1 mn ∑n i=1 ∑m l=1 ‖∇fil(wki ) − fil(x∗)‖2. Based on the update of control sequence in L-SVRG, we have:
Ek [ σk+11 ] =
1− p mn n∑ i=1 m∑ l=1 ∥∥∇fil(wki )− fil(x∗)∥∥2 + pmn n∑ i=1 m∑ l=1 ∥∥∇fil(xk)− fil(x∗)∥∥2 (13)
≤ (1− p)σk1 + pL 2
( f(xk)− f(x∗) ) .
Lemma 6. Define σk2 def = 1n ∑n i=1 ‖hki −∇fi(x∗)‖2. For IntDIANA algorithm, we have:
Ek [ σk+12 ] ≤ 1 n n∑ i=1 Ek [ ‖gki −∇fi(x∗)‖2 ] + d∑ j=1 1 α2k,j , (17)
For the full gradient, we have 1n ∑n i=1 Ek [ ‖gki −∇fi(x∗)‖2 ] ≤ L2 (f(x
k) − f(x∗)). For the LSVRG estimator, we have 1n ∑n i=1 Ek [ ‖gki −∇fi(x∗)‖2 ] ≤ 4σk1 + 3L(f(xk)− f(x∗)).
Proof. We define σk2 def = 1n ∑n i=1 ‖hki − ∇fi(x∗)‖2. Consider the step h k+1 i = h k i + Q(g k i ), where Q(gki ) = 1 αk ◦ Int(αk ◦ (gki − hki )). Note that Ek [ 〈gki − hki , gki − 2∇fi(x∗) + hki 〉 ] =
Ek [ ‖gki −∇fi(x∗)‖2 − ‖hki −∇fi(x∗)‖2 ] , which explains the last equality below: Ek [ σk+12 ] = Ek [ 1
n n∑ i=1 ‖hki −∇fi(x∗) +Q(gki )‖2 ]
= σk2 + 1
n n∑ i=1 Ek [∥∥∥∥ 1αk ◦ Int (αk ◦ (gki − hki )) ∥∥∥∥2 ] + 2 1 n n∑ i=1 Ek [ 〈Q(gki ), hki −∇fi(x∗)〉 ] (4) = σk2 + 1
n n∑ i=1 Ek [ ‖gki − hki ‖2 ] + 2 1 n n∑ i=1 〈gki − hki , hki −∇fi(x∗)〉+ d∑ j=1 1 α2k,j
≤ σk2 + 1
n n∑ i=1 Ek [ 〈gki − hki , gki − 2∇fi(x∗) + hki 〉 ] + d∑ j=1 1 α2k,j
= 1
n n∑ i=1 Ek [ ‖gki −∇fi(x∗)‖2 ] + d∑ j=1 1 α2k,j .
For the full gradient gki = ∇fi(xk), we have:
1
n n∑ i=1 Ek [ ‖gki −∇fi(x∗)‖2 ] = 1 n n∑ i=1 Ek [ ‖∇fi(xk)−∇fi(x∗)‖2 ] ≤ L 2 (f(xk)− f(x∗)).
For the L-SVRG estimator, we have by Young’s inequality:
1
n n∑ i=1 Ek [ ‖gki −∇fi(x∗)‖2 ] ≤ 2 n n∑ i=1 Ek [ ‖gki −∇fi(xk)‖2 ] + 2 n n∑ i=1 ‖∇fi(xk)−∇fi(x∗)‖2
≤ 2 mn n∑ i=1 m∑ l=1 ‖∇fil(xk)−∇fil(wki )‖2 + L(f(xk)− f(x∗))
≤ 4 mn n∑ i=1 m∑ l=1 ‖∇fil(xk)−∇fil(x∗)‖2 + 4 mn n∑ i=1 m∑ l=1 ‖∇fil(wki )−∇fil(x∗)‖2 + L(f(xk)− f(x∗))
(13)
≤ 4σk1 + 3L(f(xk)− f(x∗)).
Lemma 7. Suppose that Assumption 5 holds. Besides, we assume that f(·) is µ-strongly convex (µ ≥ 0). For IntDIANA with adaptive αk = ηk √ d√
n‖xk−xk−1‖ and GD gradient estimator, we have: Ek [ ‖xk+1 − x∗‖2 ] + Ek [ ‖xk+1 − xk‖2 ] ≤ (1− ηkµ)‖xk − x∗‖2 + 1
2 ‖xk − xk−1‖2 − 2ηk(1− 2ηkL)(f(xk)− f(x∗)),
Ek [ σk+12 ] ≤ L
2 (f(xk)− f(x∗)) + n‖xk − xk−1‖2.
For IntDIANA with adaptive αk and L-SVRG gradient estimator, we have: Ek [ ‖xk+1 − x∗‖2 ] + Ek [ ‖xk+1 − xk‖2 ] ≤ (1− ηkµ)‖xk − x∗‖2 + 1
2 ‖xk − xk−1‖2 − 2ηk
( 1− 2ηk ( L+
L 2n
)) (f(xk)− f(x∗)) + 4η 2 k
n σk1 ,
Ek [ σk+11 ] ≤ (1− p)σk1 +
pL 2 (f(xk)− f(x∗)),
Ek [ σk+12 ] ≤ 4σk1 + 3L(f(xk)− f(x∗)) + n‖xk − xk−1‖2.
Proof. By µ-strong convexity, we have:
Ek [ −2ηk
n n∑ i=1 〈Q(gki ), xk − x∗〉
] (3) = −2ηk
n n∑ i=1 〈Ek[gki ], xk − x∗〉
≤ −2ηk(f(xk)− f(x∗))− ηkµ‖xk − x∗‖2.
Besides, ‖xk+1 − xk‖2 = 2η2k‖gk‖2 − ‖xk+1 − xk‖2, so Ek [ ‖xk+1 − x∗‖2 ] + Ek [ ‖xk+1 − xk‖2 ] = (1− ηkµ)‖xk − x∗‖2 − 2ηk(f(xk)− f(x∗)) + 2η2kEk
[∥∥gk∥∥2] (14)
≤ (1− ηkµ)‖xk − x∗‖2 − 2ηk(f(xk)− f(x∗)) + 2η2kEk [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] + 1 2n d∑ j=1 η2k α2k,j
Applying Proposition 3 to the obtained bound results in the following recursion Ek [ ‖xk+1 − x∗‖2 ] + Ek [ ‖xk+1 − xk‖2 ] ≤ (1− ηkµ)‖xk − x∗‖2 + 1 2 Ek [ ‖xk − xk−1‖2 ] − 2ηk(f(xk)− f(x∗)) + 2η2kEk [∥∥∥∥ 1n n∑ i=1 gki ∥∥∥∥2 ] .
With the GD estimator, the produced bound simplifies to Ek [ ‖xk+1 − x∗‖2 ] + Ek [ ‖xk+1 − xk‖2 ] ≤ (1− ηkµ)‖xk − x∗‖2 + 1
2 ‖xk − xk−1‖2 − 2ηk(1− 2ηkL)(f(xk)− f(x∗)).
Based on Lemma 6, the following is satisfied for IntDIANA with GD estimator and adaptive αk = ηk √ d√
n‖xk−xk−1‖ :
Ek [ σk+12 ] ≤ L
2 (f(xk)− f(x∗)) + n‖xk − xk−1‖2.
In turn, Lemma 5 gives for L-SVRG estimator Ek [∥∥ 1
n ∑n i=1 g k i ∥∥2] ≤( 2L+ Ln ) ( f(xk)− f(x∗) ) + 2nσ k 1 , so we can derive that
Ek [ ‖xk+1 − x∗‖2 ] + Ek [ ‖xk+1 − xk‖2 ] ≤ (1− ηkµ)‖xk − x∗‖2 + 1
2 ‖xk − xk−1‖2 − 2ηk
( 1− 2ηk ( L+
L 2n
)) (f(xk)− f(x∗)) + 4η 2 k
n σk1 .
Let us now combine Equation (16) and Lemma 6: Ek [ σk+11 ] ≤ (1− p)σk1 +
pL 2 (f(xk)− f(x∗)),
Ek [ σk+12 ] ≤ 4σk1 + 3L(f(xk)− f(x∗)) + n‖xk − xk−1‖2.
Lemma 8. We define the Lyapunov function as Ψk def= ‖xk − x∗‖2 + ‖xk − xk−1‖2 + c1η2kσk1 + c2η 2 kσ k 2 . Assume that the conditions of Lemma 7 hold. If µ > 0, we have:
E [ Ψk+1 ] ≤ θE [ Ψk ] ,
where θ def= max { (1− ηkµ), 34 } , c1 = 0, c2 = L 2 4n and ηk ≤ 1
2(L+ L32n ) for IntDIANA
with GD estimator. Alternatively, for IntDIANA with L-SVRG estimator, we have θ def= max { (1− ηkµ), 34 , ( 1− 38m )} and set c1 = 8mn , c2 = L2 4n , p = 1 m , and ηk ≤ 1 2(L+2L/n) . If µ = 0, we have
ηkE [ f(xk)− f(x∗) ] ≤ E [ Ψk ] − E [ Ψk+1 ] ,
where ηk ≤ 14(L+ L32n ) for the GD variant and ηk ≤ 1 4(L+2L/n) for the L-SVRG variant.
Proof. We define the Lyapunov function as Ψk def= ‖xk − x∗‖2 + ‖xk − xk−1‖2 + c1η2kσk1 + c2η 2 kσ k 2 . For IntDIANA with GD estimator, we can set c1 = 0 and derive the following inequality from Lemma 7 and ηk+1 ≤ ηk:
E [ Ψk+1 ] ≤ (1− ηkµ)E [ ‖xk − x∗‖2 ] +
( 1
2 + c2η
2 kn
) E [ ‖xk − xk−1‖2 ] − 2ηk ( 1− 2ηk ( L+
c2L 8
)) E [ f(xk)− f(x∗) ] .
We first consider µ > 0 case. Let c2 = L 2 4n , and ηk ≤ 1
2(L+ L32n ) . We have E
[ Ψk+1 ] ≤
max { (1− ηkµ), 34 } E [ Ψk ] .
For IntDIANA with L-SVRG estimator, we have the following based on Lemma 7:
E [ Ψk+1 ] ≤ (1− ηkµ)E [ ‖xk − x∗‖2 ] +
( 1
2 + c2η
2 kn
) E [ ‖xk − xk−1‖2 ] + η2k ( 4
n + 4c2 + (1− p)c1
) E [ σk1 ]
− 2ηk ( 1− 2ηk ( L+
L 2n + pc1L 8 + 3c2L 4
)) E [ f(xk)− f(x∗) ] Let c1 = 8mn , c2 = L2 4n , p = 1 m , and ηk ≤ 1 2(L+2L/n) . Plugging these values into the recursion, we
get E [ Ψk+1 ] ≤ max { (1− ηkµ), 34 , ( 1− 38m )} E [ Ψk ] .
If µ = 0, we instead let ηk ≤ 14(L+ L32n ) for the GD variant and ηk ≤ 1 4(L+2L/n) for the L-SVRG variant to obtain from the same recursions:
ηkE [ f(xk)− f(x∗) ] ≤ E [ Ψk ] − E [ Ψk+1 ] .

heading: C DETAILS AND ADDITIONAL RESULTS OF EXPERIMENTS

heading: C.1 MORE DETAILS
text: Here we provide more details of our experimental setting. We use the learning rate scaling technique (Goyal et al., 2017; Vogels et al., 2019) with 5 warm-up epochs. As suggested in previous works
(Vogels et al., 2019; Alistarh et al., 2017; Horváth et al., 2019), we tune the initial single-worker learning rate on the full-precision SGD and then apply it to PowerSGD, QSGD, and NatSGD.
For the task of training ResNet18 on the CIFAR-10 dataset, we utilize momentum β = 0.9 and weight decay with factor 10−4 (except the Batchnorm parameters) for all algorithms. All algorithms run 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 run for 90 epochs. We set the size of word embeddings to 650, the sequence length to 30, the number of hidden units per layer to 650, and the dropout rate to 0.4. Besides, we 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 3 repetitions with random seeds {0, 1, 2}. To measure the time of computation, communication, and compression/decompression of the algorithms, we use the timer (a Python context manager) implemented in the PowerSGD code5.
For PowerSGD, we use rank = 2 in the task of training ResNet18 on the CIFAR-10 dataset and rank = 4 in the task of training LSTM on the Wikitext-2 dataset as suggested byVogels et 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).

heading: C.2 TOY EXPERIMENT ON TIMINGS
text: Figure 2 shows the different manners of PowerSGD and IntSGD to save the communication time based on the all-reduce compared to full-precision SGD: 1) IntSGD (8-bit) communicates the data with int8 data type but does not reduce the number of coordinates; 2) PowerSGD does not change the data type but breaks one communication round of a big number of coordinates into three communication rounds of much smaller numbers of coordinates.

heading: C.3 CONVERGENCE CURVES OF THE DEEP LEARNING TASKS
text: Please see Figure 3 and Figure 4.

heading: C.4 SENSITIVITY ANALYSIS OF HYPERPARAMETERS
text: We analyze the sensitivity of IntSGD to its hyperparameters β and ε. As shown in Figure 5, the performance of IntSGD is quite stable across the choices of β ∈ {0.0, 0.3, 0.6, 0.9} and ε ∈ {10−4, 10−6, 10−8} on the two considered tasks. Overall, β = 0.9 and ε = 10−8 is a good default setting for our IntSGD algorithm.
5https://github.com/epfml/powersgd

heading: C.5 LOGISTIC REGRESSION EXPERIMENT
text: Setup: We run the experiments on the `2-regularized logistic regression problem with four datasets (a5a, mushrooms, w8a, real-sim) from the LibSVM repository6, where
f(x) = 1
n n∑ i=1 fi(x)
and
fi(x) = 1
m m∑ l=1 log(1 + exp(−A>i,lxbi,l)) + λ2 2 ‖x‖2,
and x ∈ Rd, λ2 is chosen proportionally to 1mn and Ai,l ∈ R d, bi,l ∈ {−1, 1} are the feature and label of l-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 a socket (there are two sockets in total). All experiments use 12 cpu cores and each core is utilized as a worker. The communications are implemented based on the MPI4PY library Dalcín et al. (2005). The “optimum” x∗ is obtained by running GD with the whole data using one cpu core until there are 5000 iterations or ‖∇f(x)‖2 ≤ 10−30.
The whole dataset is split according to its original indices into n folds, and each fold is assigned to a local worker, i.e., the data is heterogeneous. There are m = bNn c data points on 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 as a minibatch (i.e., batch size τ = bm20c) to estimate the stochastic gradient g k i on each worker. We set p = τ m in VR-IntDIANA.
6https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/binary.html
Apart from IntSGD with gki = ∇fi(xk) (IntGD), we also evaluate IntDIANA (Algorithm 3) with the GD or L-SVRG estimator (called IntDIANA and VR-IntDIANA, respectively).
As shown in Figure 6, IntSGD with gki = ∇fi(xk) (IntGD) suffers from low compression efficiency issue (very large integer in the aggregated vector ∑n i=1Q(g k i )) and IntDIANA can solve this issue and only requires less then 3 bits per coordinate in the communication. IntDIANA with SVRG gradient estimator (VR-IntDIANA) further improves IntDIANA with GD estimator in terms of gradient oracles.

Review summaries:
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).

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.