BinSGDM:  Extreme One-Bit Quantization for Communication Efficient Large-Scale Distributed Training 
Authors: Hanyang Peng
Shuang Qin
Yue Yu
Jin Wang
Hui Wang
Ge Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: Distributed Learning
Optimizer
Communication Efficiency

Abstract: To alleviate the communication bottleneck of large-scale distributed training, a rich body of prior communication-compression optimizers have been proposed. These methods  focus mainly on high compression ratio to expect  acceleration. However, some recent works pointed out, when running with distributed training frameworks ( \emph{e.g.}, \emph{DistributedDataParallel} in pytorch), these methods may provide no acceleration over the off-the-shelve uncompressed SGD/Adam in the typical settings, due to heavy compression/decompression computation or incompatibility with efficient communication primitives or the requirement of uncompressed warmup at the early stage. For these reasons, we propose a novel extreme one-bit quantization optimizer, dubbed \emph{BinSGDM}. The quantization of \emph{BinSGDM} is computed easily and lightly, and it does not need to resort to uncompressed optimizers for warmup. We also theoretically prove that it can promise the same convergence speed as the original Adam. Moreover, we specially present a hierarchical communication scheme to further lower the communication volume.  Extensive experiments are conducted on 8 to 64 GPUs (1 to 8 nodes) for distributed training with \emph{DistributedDataParallel}, and the experimental results demonstrates that \emph{BinSGDM} with the communication scheme can achieve up to {$\bm{2.47 \times}$} speedup  for training ResNet-50 and $\bm{6.26\times}$ speedup for training BERT-Base, compared to the full-precision optimizers.

Under review as a conference paper at ICLR 2023
BINSGDM: EXTREME ONE-BIT QUANTIZATION FOR COMMUNICATION EFFICIENT LARGE-SCALE DIS- TRIBUTED TRAINING
Anonymous authors Paper under double-bling blind review
ABSTRACT
To alleviate the communication bottleneck of large-scale distributed training, a rich body of prior communication compression optimizers have been proposed. These methods focus mainly on a high compression ratio to expect acceleration. However, some recent works pointed out, when running with distributed training frameworks ( e.g., DistributedDDttaarulll acceleration over the off-the-shh sieelhe-shelve uncompressed SGD/Adam in the typical settings, due to heavy compression/decopressiio computation or incompatibil- ity with efficient communication primitives or the requirement of uncompressed warmup at the early stage. For these reasons, we propose a novel extreme one-bit quantization optimizer, dubbed BinSGDM. The quantization of BinSGDM com- puted easily and lightly. and it does not need to resort to uncompressed optimizers for warmup. We also theoretically prove that promises the same convergence speed as the original Adam. Moreover, we specially present hierarchical 1- bit All-Reduce technique to further lower the communication volume. Extensive experiments are conducted 8 to 64 GPUs (I to 8 nodes) for distributed train- ing with SetrriittedDttaaarrllle BinSGDM with the communication scheme achieve up to 2.5x speedup for training ResNet-50 and 6.3 x speedup for training BERT-Base. compared to the full- full-precision optimizers.
in Pytorch), these methods provide
and the experimental results demonstrate that
INTRODUCTION
With the rapid development of computational power, "bigger" and "bigger" deep neural network (DNN) models are proposed for expecting better performance, from the early classical models, such as AlexNet(61M parameters) (Krizhevsky et al. (2017), and ResNet (ResNet-500 20.5M parame- ters) (He al. )2 the current foundation models, such BERT (BERT-Lagre 340M pa- rameters D(Devlin et al. (2018)), and GPT (GPTT-3: 176B parameters) (Brown et al. (2020). Scalable parallelism across distributed computing workers for training these large-scale models becomes cessity. During training, millions to billions of parameters need to be communicated among workers each iteration, and the expensive communication cost becomes a bottleneck.
To address the communication bottleneck, a wide variety of lossy gradient compression optimizers have been proposed lower the communication volume. These algorithms can be typically divid- ed into three groups, including low-precision approximation (e.g.. 1-bit SGi(Se et al. (014)), SignSGD
al. (2018)), TernGrad (Wen al. (2017). and QSGD) (Alistarh
2017 ).
I-Bit Adam (Tang et al. (2021))), low-rank simplification (e.g., TroMO[Wang et al. (2018)) ). Pow- erSGD /Vggels et al. (2019)) and GradZip (Cho al. (2019)), and sparsification (e.g., Random-k
Stich et al. (2018). ), Top-k (Aji & Heafield (2017)) ), and MSTop-k (Shi et al. (202I)))
While much of the research on gradient compression algorithms has focused mainly on the high compression ratio, more important yet underexplored problem is how to decrease the actual system-level runtime and increase the distributed scaling efficiency. Actually, some recent works et 22020 Agarwal et al. (2022) pointed out, when distributedly training typical models (e.g., ResNet-50 0 and BERT-Base) with off the-shlleef Distributed (DDP) at typical bandwidth- (e.g., 10Gbps), these existing gradient compression algorithms with high compression ratios

---

Under review as a conference paper at ICLR 2023
still slower than the original uncompressed optimizers. This is because they exhibit one more of the following weaknesses (Xu et al. (2020) Agarwal et al. (2022): (i) Some gradient compression algorithms should perform comprrestoon/decomprsssst and communication within the limited time frame, and the time cost of conpression/decoopessiii
in some cases, is close to and even larger than the savings by the reduces communications; (fi) some gradient compression algorithms cannot take full advantage of overlapping between gradient computation and communication. Because if overlap, their intensive computation will
the gradient computation and compressinndeeompressii compete with each other for GPU resources, which can result in an overall slowdown; (λii) due to in- herent structures, some algorithms can only use inefficient collective communication primitive, such as All-Gather; (iv) some gradient compression algorithms need to harness uncompressed optimizers to warm up at the early stage. The warm-up time is commonly nontrivial which to some extent ren- ders their high compression ratios vacuous. Therefore, from system-level perspective, the design cthos of a system-efficient the patpressiiondccoppressset of the algorithm is computationally light and takes less time, and that the corresponding communication should also be friendly to efficient collective communication primitives. Additionally, there is need to resort to uncompressed optimizer for warm-up.
algorithm is that we should guarantee that
To this end, we propose a coamuunicattooccompessstee optimization algorithm, referred to as Binary SGD-Momentum (BinSGDM), in which the core updating rule is F++1 It ar Q
by where my f8m-1 (1 3) b, -bb--1 + (1 1yal and Ie is the gradient, and Q(-) is binary quantization operator. The main difference between BinSGDM and existing gradient-quaniizaiion algorithms is that we directly quantize the entire update my rather than quantize the gradient gr or by (b.)s S where (me)). (be) are the jth element of m,, by each element of my is easy to be randomly quantized to 1 or - 1 in probability, so the quantization is com- by putationally light. Another advantage of BinSGDM is that it does not need a full- cull-precision optimizer warm up the early stage ensure stable convergence. Besides, we theoretically demonstrate BinSGDM's convergence rate can match that of the original Adam. Moreover, according to the na- ture of BinSGDM, we specifically devise an efficient hicrarchical communication scheme further speed up communication, which sufficiently leverages the ultra-high intra- intra-bandwinn bandwidth among GPUs within the same node and efficient commutation primitives rather than All-Gather.
the momentum my Due to -1 < (me))
In particular, we make the following key contributions:
We propose novel communication comppess distributed optimizer, dubbed BinSGDM. To the best of our knowledge, it is the first algorithm that quantizes the entire model up- date of an adaptive optimizer and does not need to leverage uncompressed optimizers to warm up to address the convergence issue, which makes compressionddeoopresiin computationally light and the extreme quantization ratio exert its best function (Section 2).
We theoretically prove that even though extreme 1-bit quantization is employed, BinSGDM still promise the same convergence speed as the full-precision Adam (Section 3).
We present a new hierarchical communication scheme for 1-bit communication, called Hi- erarchical 1-bit All-Reduce which sufficiently harnesses the ultra-fast intra-connects to accelerate the local communication, and utilize more efficient commutation primitives to further reduce the communication overhead (Section 4).
We perform extensive distributed training experiments to demonstrate the effectiveness of the proposed algorithm. As far as we know, our algorithm is the first work to con- sistently trump the uncompressed optimizers with the highly system-level optimized DDP in overall running time at no inference performance cost, reaching up to 2.47x speedup for Resnet-50 and 6.26x speedup for BERT-Base on 64 GPUs. The better scala- bility makes BinSGDM promising to train more large-scale models (Section 5).
2 EXTREMELY ONE-BIT QUANTIZED BINSGDM
In this section, we focus on solving the following problem when training a DNN model distributedly:
min ZER4
f(x)
1 n i=1
Σ fa (())
(1)
2

---

Under review as a conference paper at ICLR 2023
where x: is the d-dimensional model parameter, n is the number of distributed workers. 5(0) is the sampled min-batch data on the i-the worker. The sampled min-batch data on all the workers is independent and identically distributed (Li.d.). fi(e; g(6) the loss function. Note that fi(;; Ei) commonly abbreviated as fi(z) in the following.
When we directly employ vallina full-precision and dense-computation optimizers to train a large- scale DNN model distributed workers, the gradient communication among workers at each it- eration becomes a bottleneck. Elegant SignSGD was proposed to alleviate the bottleneck problem, which merely takes the sign of each coordinate of the gradients. Although it substantially duce the communication overhead, its practical performance is still inferior to popular optimizers, such Adam. Fortunately, we observe that the mathematical formulations of SignSGD and Adam have close connections, so leaves us an opportunity to propose a new optimizer that can com- bine their merits, i.e., considerably reducing the communication volume with light computation yet maintaining fast convergence speed and high inference performance.
The mathematical update step of SignSGD can be formulated as:
T++1 <- Zt o;Sinn(ge) = It
Ctt
9t
Iga
where is the learning rate, denotes the estimated unbias noisy gradient of f(z)) with random samples. Note that the divider here is an element-wise divider.
Whereas the updating rule of vallina Adam can be expressed as:
< B1m--1 + (1 B1 )9t.
Vt 32 (1 (1- -2)2
(3)
me
T++1 Tt. at Vee"
where 81 and 82 represents the exponential moving average factors
If taking the exponential moving average factors zero, 31, 33 - in Eq. (3) Adam will be equal to SignSGD.
Given the observations above, we propose new optimizer that an intermediate between SignSGD and Adam, referred to as BinSGDM, i.e.,
m + 8m;-1 + (1- 8)gr.
b, + Bb,-1 1 + (1- }3)
(4)
mi
I+41 3z a
by
where the j-th elements m, by rigorously satisfics -1 < quantization operator, and it quantizes the j-th element of as follows:
(me)
< 1, Q(.) is an element-wise
(b,),
(me))s ) - (br);
with probability ] (bi)
(me)s
+
-1. -1 with probability 1-p
(5)
where E. (0
m2 b.
m. b,
so 2(-) unbiased.
The detailed implementation of BinSGDM in parameter-server model is illustrated in Algorithm 1. Some appealing characters BinSGDM are summarized the following:
All the existing cmmmunication-efficieee optimizers are built upon gradient compression. In contrast, to the best of our knowledge, are the first to directly quantize the entire mod- el update, which will streamline the quantization. Moreover, each element of mi bounds by
For simplicity, we omit the bias correction for m, and ys and the small constant in the numerator.

---

Under review as a conference paper at ICLR 2023
Algorithm BinSGDM
I: Input: all workers's ' model parameter æt, 21 the ith worker's momentum m = 0,
6 = 0, the 1th worker's local error c = O, server's global error &g = O, exponential moving average factor (9, the threshold To. and the learning rate sequence {
2: for f = 1, ..... T do
3: (On the 8th worker)
4: Randomly sample < and compute local gradient:
v(((())(())
gg
5: Update the local my ; m,
8m
+ (1
9)
6: Update the local 85)) ((4) [bb + Bg
7: Update the local 6 if To { ()))) -maax
max 1 )) clse (6, 8,00²
8: Quantize the local update: u = 2
m
6.0 + (222)
9:
Update the local error feedback et
(1)
6--
+
m (
6
10:
Send u," to the server (On server)
11:
12:
Average all received qu and quantize it: u, = 2 Σ i= up 11
(1)
13:
Update the global error feedback é, ét 6 D U4 tse
14:
Send back de to workers
15:
(On the tth worker)
16: Update the local model parameter Zr+11 2++1 22 Cit Ust
17:
end for
This follows the uchnique AMSGrad al. 2018 is about theuretical significanes, and commenly implement practice.
in the range [-1, and then it is extremely quantized to binary 1 or -1. Thus, the quan- tization in BinSGDM is computed easily and lightly, compared to the existing gradient- quantized optimizers +.
Unlike SignSGD, Adam adaptively preconditions the gradients with Ut, which is the key ensuring fast convergence rate in practice. BinSGDM also inherits the character of adaptive preconditioning from Adam to accelerate the convergence speed. The difference is that we keep the exponential moving average factor for my and b, the same, so that each element of bounding in the range [1 1] can be strictly guaranteed, which is crucial to perform light quantization.
When the model parameter is close to local optimal value during training, ideal optimizer should make sure the updates gradually decay to zero, otherwise, 2₁ will oscillate around the optimum and cannot indeed approach it. SignSGD and Adam do not have this appealing property, while, as for unquantized BinSGDM (we refer to it as SoftSignSGD, and the implementation details for it please Algorithm 2 in the Appendix), the gradient 9: will continually change its sign around the optimum of which the gradient is zero, so that ma will damp zero. An Example illustrating this phenomenon is provided in Section C in the Appendix.
the update b,
Remark. We have noticed that the prior works 1-bit Adam (Tang et al. (202)) and its variants LLi et al. (202T). Lu et al. (2022)) also quantize the communication data to I-bit. However, the design ethos of T-bir Adam and the proposed BinSGDM are completely different. I-bit Adam is still built on gradient compression rather than the entire update. The motivation of I-bit Adam is to harness the error feedback (EF) technique (Seide al. (2014), Stich al. (2018) to compensate for the gradient information lost to alleviate the convergence issue. However, unlike SGD, the parameter update in Adam no longer linearly depends on the gradient, so that EF cannot be directly employed. Authors of 1-bit Adam observed that Adam's 's variance (non-linear term) becomes stable after the early stage, l-bit Adam runs full-precision Adam in the beginning (warmup phase) and utilizes
"The typical gradient-quannizedd optimizer QSGD quantizes the gradient follows:
{
|19. [lolllaign((()) ((o)),)
with probability p. *Kor)sl
@ (({e)))
with probability 1 lls:lla
[19.|] besinnniggg );)
where 0 <r< (r,7 and
Tec 12 15. r+1]
4

---

Under review as a conference paper at ICLR 2023
a precondition for SGDM during the rest of training (compression phase), and then EF in the compression phase help 1-bit Adam to converge as rapidly as uncompressed Adam. There are two aspects that influence 1-bit Adam to indeed accelerate communication. First, the warmup steps commonly make up 1,%%25% of the total steps in I-bit Adam, which to some extent discounts the high quantization ratio. Second, in the compression phase, 1-bit Adam should communicate the signs of the gradients of each layer as well as the average scale of all the gradients in this layer, while in DDP, raising communication efficiency, the gradients from many layers should be flatted to 1- 1-dimension and concatenated together, and then packed to one bucket to communicate, which means the scale factor of each layer cannot be computed. Therefore, 1-bit Adam is not compatible with DDP, which will also lower communication efficiency.
3 THEORETICAL ANALYSIS
In this section, we present the theoretical convergence guarantee for BinSGDM (Algorithm 1). We first introduce some necessary assumptions.
Assumption 1.[Bounded infimum] For any x and a constant f³, we have the objective value f(x) 2 f"
Assumption 2. [Lipschitz continuous gradient] The gradient V f(() is L-Lipschitz continuous, i.e., [Vf(x) Vy(il I L||z - vll2, Vx,y E Rd.
Assumption 3. [Unbias and indpendent noisy gradient] The gradient with respect to the random samples each worker and at a different time is independent identically distributed (i.i.d),, i.e. (5) (8) is independent of gt for i + j. and gt, is independent of 9tz for Blgt (1) V.())..V 2 1, 9t # t2
Assumption 4. [Bounded gradient] The noisy gradient and the full-set gradient are bounded i.e.,
| || GG [[Vf(())] S G, Vt 2 1.
Under the assumptions above, we then present the theoretical convergence for BinSGDM in Algo- rithm 1.
Theorem 1. For BinSGDM Algorithm 1, under Assumption 1-4, assuming (b²"), 2 p 0, Vj E [1,2, ..... choosing at
c_ Vt E [1. 2, ..., T] and Oip 0r and defining 21 = 21 + an (61 -1)
where 6, >.
Σ m(()) E 6
()) and = ej + E₁ we then have the following
2
C1
C2(1 log T)
E
(6)
VT
VT
where
3c2dL
BedG2
4edG2
+ 2
C = cG
[[f(21) f*1
+
+
16
(1 B)p
P
p² (P113)3)
(862 + 10, + +
G² + L)
C2 = c'G
2dL
(1-
2p
4 HIERARCHICAL 1-BIT ALL-REDUCE
The data in BinSGDM to communicate is one-bit, so it cannot be directly aggregated through the efficient All-Reduce. Moreover, the intra-node bandwidth and inter-node bandwidth are severely im- balanced. If we aggregate the data uniformly from intra-node and inter-nodes, the communication will be slowed down by the inter-node data exchanges.
In light of the problems above, we propose a hierarchical communication scheme, called Hierarchi- cal I-bit Rel-Reduce, to efficiently aggregate our 1-bit data, which can hierarchically take advantage
We commonly add small constant to by to avoid zero denominators for numerical stability, which guar- antees this assumption holds in practice.
5

---

Under review as a conference paper at ICLR 2023
Intervale comerraalle
Gaadae
Narins
bodkae
Modr3
Goler
1-8 AB-
GRU3
Sallen
Ave
GAV3
LAVE
Figure 1:
Paradigm of Hierarchical 1-bit All-Reduce
of the ultra-high intra-node bandwidth and reduce the inter-node communication overhead. Assum- ing we have n nodes and each node contains m GPUs and the overall volume for each GPU needs to communicate is P. as visually illustrated in Figure 8 the steps of Hierarchical 1-bit All-Reduce as follows: (i) Each GPU conducts Reduce-Scatio to locally aggregate the scatter the data within node, and the communication volume for each GPU is (m-1))P (it) Each GPU performs BinS- GDM to quantize the data, and then volume becomes P
32m; each GPU. (iit) Each GPUs conducts 1-bit All-Reduce to inter-aggregate data. This step includes two sub-steps: 1) Each GPU performs All-to-All collect the data of corresponding GPUs in other nodes, and the communication volume
(n-1) 2) each GPU averages and re-quantizes the data, and then conducts All-Gather to gather 32mn
the data, and the communication volume is also (n-1)P (iv) Each GPU performs All-Gather to intra-aggregate data, and the communication volume is (m-1))
32m
Compared to the time of inter-node communication, the time cost of inter-node communication is trivial. Hence, when leveraging Hierarchical 1-bit All-Reduce, the most communication cost comes from 1-bit All-Reduce in Step (iit), and then the communication volume across nodes for all GPUs is approximately 2(n-1)P In contrast, if we simply utilize the original All-Gather to 32
aggregate data, the communication volume across nodes for all GPUs approximately m²"(n--1)P 32 Therefore, Hierarchical I-bit All-Reduce is considerably more efficient than the original All-Gather.
5 EXPERIMENTS
Table 1: System throughput and Test Accuracy of SGDM, 1-bit Adam and BinSGDM for training ResNet-50
on ILSVRC2012 from scratch with 8, 16, 32, 64 GPUs.
32 samples per GPU
128 samples per GPU
Optimizer
#GPUs
Throughput (samples s)
Top-1 Acc. (%)
Throughput (samples /
Top-1 Acc.(%)
SGDM
3693 (1.00x)
76.19
5272 (1.00x)
75.05
1-bit Adam
8
32/13 (0.83x)
75.55
5229 (0.99x)
75.42
BinSGDM
3462 (0.91x)
75.98
5251 (0.99x)
75.45
SGDM
2959 (1.00x)
75.96
6189 (1.00x)
74.61
1-hit Adam
16
1745 (1.60x)
75.33
8836 (1 (1.42x)
75.05
BinSGDM
6015 (2.03x)
75.53
9633 (1.56x)
75.09
SGDM
4270 (1.00x)
75.47
9909 (1.00x)
74.54
1-bit Adam
32
7268 (1.70x)
75.18
13827 (1.40x)
74.82
BinSGDM
9416 (2.21x)
75.27
15950 (1.61x)
74.82
SGDM
6189 (1.00x)
75.37
16640 (1.00x)
74.22
1-bit Adam
64
5546 (0.89x)
75.54
16426 (0.99x)
74.34
BinSGDM
15253 (2.47x)
75.30
23727 (1.43x)
74.24

---

Under review as a conference paper at ICLR 2023
SGDM
50GM
1-b8t Adam
BInSSOM
BIIGGO
150
330
230
302
clock
(a) Epoch-wise, ResNet-50, batch size=32 64 (b) Time-wise, ResNet-50, batch size=32 x
SGOM bt Adam Bn6EDM
Adam
%
Epoch- Epoch-wise, RosNet-55, batch size=128 64(d) Time-wise, ResNet-50, batch size=128 x 64
4domil
Atammi 1 bit Adam BRrdDDN
35.
1-0 Adam
25-
BInGGOM
20-
k.5
300
spach
Will diekk time (min)
(e) Epoch-wise, Bert- Base, batch sizc=3 x 64 (f) Time-wise, Bert-Basc, batch size=3 x 64
Figure 2: Epoch-wise and time-wise convergence speed for training ResNet-50 with 32 samples per GPU, ResNet-50 with 128 samples per GPU, and fine tuning BERT-Base with 3 samples per GPU with 64 GPUs.
Table 2: System throughput and FI-Score/ Excat-Match of AdamW, I-bit Adam and BinSGDM for fine tuning BERT-base on SQuAD 1.1 with 8, 16, 32, 64 GPUs.
Optimizer
#GPUs
Throughput (samples/s)
FI-Score (%)
Exact Match (%)
Adam
413 (1.00x)
88.13
80.59
1-bit Adam
358 (0.87x)
88.05
80.06
BinSGDM
412 (1.00x)
88.71
81.18
AdamW
84 (1.00x)
88.47
81.07
1-bit Adam
(2.54x)
87.87
80.31
BinSGDM
431 (3x1
88.31
80.80
AdamW
119 (1.00x)
88.38
80.94
1-bit Adam
32
274 (2.30x)
87.78
80.08
BinSGDM
730 (6.13%)
88.08
80.50
AdamW
158 (1.00x)
88.13
80.94
1-bit Adam
64
252 (1.59x)
87.33
79.67
BinSGDM
990 (6.26x)
88.28
80.75
Recently, some recent works [Xu et al. (2020) Agarwal et al. (2022) ] have demonstrated that when running with the system-level optimized distributed data -trralll frameworks(e.g.. DDP the ex- isting typical communication cotpumiiccatiiocooopssiioooooo optimizers (not including 1-bit Adam) runs still slow- er than the full-precision original SGD/Adam (the reasons please refer to the section of Introduc- tion). Hence, we only evaluate the performances of BinSGDM, the uncompressed original SGDM IAdamW, and the closely relevant 1-bit Adam based on performing distributed training experiments with the benchmark model ResNet-50 (CNN) and BERT-Base (Transformer). We show that running with the distributed data- aata-parallel framework DDP in Pytorch, BinSGDM with the proposed specific commutation scheme is up to 2.47 times faster for ResNet-50 and 6.26 times faster for BERT-B- Base than the uncompressed optimizers with highly system-level optimized all-reduce at no accuracy cost.
7

---

Under review as a conference paper at ICLR 2023
1500E
SCDM SHOODM
25900
-- Adarm
1-bit Raam
Adami
BinSCOM
(8:0
30000
12000
(1.99)
3002
.00
(a) ResNet-50, 32 samples/ GPU (b) ResNet-50, 128 samples GPU (c) BERT-Base, samples GPU
Figure 3: System throughput of optimizers for training (a) ResNet-50 with 32 samples per GPU, (b) with 128 samples per GPU, and (c) fine tuning BERT-Basc with 3 samples per GPU with 8, 16, 32, 64 GPUs.
5.1 EXPERIMENTAL SETTINGS
Testbed. Our experiments are implemented on {1. 2, 4, 8} nodes connected with 10Gbps Ethernet, and each node is equipped with 8 Nvidia Tesla A100-80GB GPUs. The hardware and software the same in all instances. The operating system in each node Ubuntu 20.04.4 LTS. Our exper- iments are performed in Pytorch 1.11.0, and other related libraries CUDA-1166, cuDNN-8.2, NCCL-2.10. 10.3 and Pytorch 1.1..0. 0. Notably, to be compatible with DDP of Pytorch, parts of BinS- GDM and our hierarchical communication scheme implemented in the customized communica- tion hook of DDP in Pytorch.
Training details. For the experiments over ResNett50., we evaluate the convergence and perfor- mance of SGDM, 1-bit Adam and BinSGDM on ILSVRC2012. The batch size per GPU is set to 32 or 128 with the standard input resolution 224 224. When employing SGDM (baseline), the learning rate starts at 0.1 X
batch size with momentum of 0.9 and weight decay of 0.0001. When 256
employing /-bit Adam and BinSGDM, the learning rate starts at 0.001 batch size with weight decay of 0.0001, and [$1, for /-bit Adam is set to [0.9, 0.999) and /3 for BinSGDM is set to 0.95. Then, the learning rate is divided by 10 after 30, 60 and 90 epochs, and training is finally terminated after 100 epochs. Specifically, the first 15 epochs are used as the warmup stage for 1-bit Adam. For the experiments over BERT-Base, we access the convergence and performance of AdamW (baseline), 1-bit Adam and BinSGDM for SQuAD 1.1 fine-tuning task using pre-trained BERT-Bass model checkpoint from HuggingFace The batch size per GPU is set to 3. We perform fine-tuning for epochs. The learning rate linearly increases to 0.3x steps in the early 500 steps and then linearly decreases to the rest iteration. Specifically, the first 0.2x steps are used as the warmup stage for 1-bit Adam. [B1, [2] for AdamW, and 1-bit Adam is set to [0.9, 0.999] and / for BinSGDM is set to 0.9.
5.2 EXPERIMENTAL RESULTS
Figure shows the sample- wise and time-wiss wise training convergence behaviors for SGDM / Adam W (baseline), 1-bit Adam and BinSGDM with ResNet-50 and BERT-Base running on 64 GPUs. The experimental results demonstrate that BinSGD achieve similar sample-wise convergence rate to the baseline, while its actual speed is substantially faster than the baseline and I-bit Adam, up to about 2.5x speedup for ResNet-50 with batch size 32 per GPU and about 6.3x speedup for BERT-Base fine-tuning on SQuAD 1.1.
Figure 3 presents the system throughput for different optimizers running with ResNet-50 and BERT- Base on 8 GPUs to 64 GPUs When training on 8 GPUs, since computation rather than communi- cation dominates the rumning time, the throughput performance for BinSGDM is slightly inferior to SGDM and Adam W. but when the number of GPUs is growing, BinSGDM consistently outperforms the counterparts, and the more the number of GPUs is, the more the superiority becomes obvious. Furthermore, the system throughput for SGDM, AdamW and I-bit Adam even decreases with GPUs increasing some cases, whereas the throughput for BinSGDM steadily grows, which indicates that BinSGDM can offer better scalability efficiency.
In terms inference performance for ResNet-50, we evaluate the Top-1 accuracy after training on ILSVRC2012 from scratch. As the inference performance for BERT-Base, we measure the FI-score
8

---

Under review as a conference paper at ICLR 2023
WIDM mediden
MGU line
Alren Compurah
This
Compuration Time acalion
1-81 Comp
100ON cemprtation
ERSCOM Computation Tiee
150GO Compuistion Timee CSISM Carqulirine live
saGin Comqureecana
Eariciaa Ganry Chnann Time
103-
52.5
(a) ResNet-50, 32 samples / GPU (b) ResNet-50, 128 samples / GPU (c) BERT-Base, 3 samples / GPU
Figure 4: Computation time, communication time and compression/decoopession time per iteration of opti- mizers for training (a) ResNet-50 with 32 samples per GPU, (h)ResNet-50 with 128 samples per GPU, and (c) fine tuning BERT-Bast with samples per GPU with 8, 16, 32, 64 GPUs.
and exact-match score after fine-tuning on SQuAD 1.1. As shown in Table 1 when the batch size is set to 32 samples per GPU, the accuracy for BinSCDM is slightly lower than SGDM. For CNN architecture, some works (Keskar & Socher (2017). Zhou et al. (2020)) pointed out that adaptive optimizers commonly generalize worse than SGDM. However, when the batch size becomes larger (T I-bit Adam and BinSGIMM achieve better accuracy. The reason for it is that certain level of noise can be helpful for generalization (Smith & Le (2018)), biasing the optimizer towards wider valleys. Large batch size will reduce the randomness, while quantization errors in BinSGDM increase the randomness. Table 2 exhibits BinSGDM obtains similar or higher Fl-score and exact- match score, compared to Adam and 1-bit Adam, which validates the inferencing effectiveness of the proposed BinSGDM.
5.3 COMMUNICATION EFFICIENCY ANALYSIS
As illustrated in Figure 4 when perform training single node, the baseline full-precision SGDM and Adam is slightly faster than BinSGDM and 1-bil Adam. Since the inter-GPU bandwidth within node is ultra-high, the communication time becomes negligible, and the newly introduced compresion/ddcompresion by caamuunccationcomprssses to the fight-computation quantization, BinSGDM with ResNet-50 and BERT-Base only takes about 15ms and 8ms respectively for compression/decoppessiii on two nodes, the bandwidth between nodes is limited (10Gbps in our experimental testhed), and the communication time should be reckoned with. For the uncompressed SGDM and Adam, the communication time considerably exceeds the computation time for ResNet with 32 samples per GPU and BERT-Base, which makes the system throughput even lower than that on single node (shown in Figure 2). Since extreme quantization in BinSCDM substantially reduces the commu- nication overhead (up to 32x reduction), the compunction time for BinSGDM increases slightly. When the number of nodes is further increasing, a good communication scheme becomes signifi- cant. Leveraging our proposed Hierarchical I-bit All-Reduce, the overall inter-node communication volume exchanged is proportional to the number of nodes, while, for CompressedAllredses utilized by 1-bit Adam, the overall communication volume exchanged among nodes is proportional to the number of GPUs (8 times number of nodes in our experiment). Therefore, with the number of nodes increasing, the communication time for BinSGDM raises gently, but the communication time for 1-bit Adam grows abruptly.
optimizers takes up extra time. Due
When we perform distributed training
CONCLUSION
In this work, we present novel communication compression optimizer for distributed training. The optimizer is not only easy and light to compute but also quantizes the communication data to an ex- treme one bit. We also theoretically demonstrate that BinSGDM can converge as fast the original Adam. To further accelerate the communication. will specifically present a novel communication scheme for BinSGDM replace the inefficient naive All- Gather. Extensive experiments on train- ing the benchmark Re and BERT-Base have validated the effectiveness and efficiency of BinSGDM over the uncompressed Admm and the most relevant I-bit Adam.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Saurabh Agarwal, Hongyi Wang, Shivaram Venkataraman, and Dimitris Papailiopoulos. On the util- ity of gradient compression in distributed training systems. In Proceedings of Machine Learning and Systems, volume 4, pp. 652-672, 2022.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent.
arXiv preprint arXiv: 1704.0770000000 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effiienn sgd via gradient quantization and encoding. In Advances in neural in- formation processing systems, volume 30, 2017.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. Signs- gd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning. pp. 560-566 569, 2018.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:187771901,, 2020.
Minsik Cho, Vinod Muthusamy, Brad Nemanich, and Ruchir Puri. Gradzip: Gradient compres- sion using alternating matrix factorization for large-scale deep learning. In Advances in Neural Information Processing Systems, 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: /810,04805 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. IEEE Conference on Computer Vision and Pattern Recognition, pp- 770-778, 2016.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to sgd. arXiv preprint arXiv:1712.07628, 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. Communications of the ACM, 60(6):84-99) 90, 2017.
Conglong Li, Ammar Ahmad Awan, Hanlin Tang, Samyam Rajbhandari, and Yuxiong He. 1-bit lamb; Communication efficient large-scale larcc-batch training with lamb's convergence speed. arXiv preprint arXiv:2104.060000 2021.
Yucheng Lu, Conglong Li, Minjia Zhang, Christopher De Sa, and Yuxiong He. Maximizing com- munication efficiency for large-scale training via 0/1 adam. arXiv preprint arXiv:2202.06009, 2022.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference Learning Representations, 2018.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth annual conference of the international speech communication association, 2014.
Shaohuai Shi, Xianhao Zhou, Shutao Song, Xingyao Wang, Zilin Zhu, Xue Huang, Xinan Jiang, Feihu Zhou, Zhenyu Guo, Liqiang Xie, et al. Towards scalable distributed training of deep learn- ing on public cloud clusters. In Proceedings of Machine Learning and Systems, volume 3, pp. 401-412, 2021.
Samuel L Smith and Quoe V Le. A bayesian perspective on generalization and stochastic gradient descent. In International Conference on Learning Representations (ICLR), 2018.
Sebastian U Stich, Jean- nan--Bptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In
Advances in Neural Information Processing Systems, volume 31, 2018.
10

---

Under review as a conference paper at ICLR 2023
Hanlin Tang, Shaoduo Gan, Ammar Ahmad Awan, Samyam Rajbhandari, Conglong Li, Xiangru Lian, Ji Liu, Ce Zhang, and Yuxiong He. 1-bit adam: Communication efficient large-scale training with adams convergence speed. In International Conference Machine Learning, pp. 10118- 10129, 2021.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems, volume 32, 2019.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication-efficcenn learning via atomic sparsification. In Advances in Neural Information Processing Systems, volume 31, 2018.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Tergrad: Ternary gradients reduce communication distributed deep learning. In Advances in neural information processing systems, volume 30, 2017.
Hang Xu, Yuen-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.
Pan Zhou, Jiashi Feng. Chao Ma, Caiming Xiong, Steven Chu Hong Hoi, et al. Towards theoreti- cally understanding why sgd generalizes better than adam in deep learning. Advances Neural Information Processing Systems, 22221125--2196 2020.
A THEORETICAL ANALYSIS FOR ALGORITHM
In practice, we implement BinSGDM in non-parameterr-sevee model to further reduce the com- munication overhead, but the data exchange essentially equivalent to that in a parameter-server prototype. Hence, provide the theoretical analysis for BinSGDM in parameter-server model as shown in Algorithm
According to Algorithm 1, the update ūn can be recursively formulated as
T4
Q
+
i=1
+ 6
E141
71
(9)
m
+ 1t
+ - 2441
(
72
my
(1) 4+1
+ Ft - -
(1)
(6)
m
(1)
+
((41
Es - E
71
n
i=

---

Under review as a conference paper at ICLR 2023
Denote
1
())
91
91
1
Σ
m
8m4-1 + (1 B)gr.
(9)
b
A
(()
(10)
1=1
A
m
114
6.
(11)
b
n
(1)
Ct
6
Ce
(12)
71
(13)
Hence, the updating rule can be summarized as
Tx41
3t
0210
m4
(14)
a4
6,
et E
b1
A.1 AUXILIARY LEMMAS
Lemma Let ui me the element-wise quantization function is defined in (5, can be reformu- lated as
Q ((u))) ={ 1, with probability p = (w)y+
2
(1,2 d}. -15 (u)) S 11. (15)
-1, with probability
We have E, = ut - Q (u)). and then the following holds true
E Ble]]= = 0, E [[lex]]]] s d.
(16)
Proof. From Eq. 15 we know
E [et)) = E [u, - [
(17)
(uee) + ((4)) 1) (1
2 ((1)) +1))((u)) 1) 0,
and,
[et))]
E ((ue); 2((u))=))
1
((ut) + +1) ((ue)s - 1)) + (1 2 ((me)s + +1))((ue}} +
(18)
2
$1 25
Hence,
E [e:] 0, E [1|ea]| d.
(19)
Lemma Let 20 = I and 0o = ai in Algorithm 1, defining the sequence
21 2 + aq (81 é1)
(20)
(r Ft 1) + 0t-1 (51-1 - 222
2, Ft 1 3
(21)
12

---

Under review as a conference paper at ICLR 2023
Then the following equality will hold, i.e.,
B
04-1
0t
2++1 + 1
B
b-11
be
M
0t bt
-1-1-1-11 (as at-1)er
(22)
Proof. For 1 = 1, we have
22 - 21 = 82 B
222 x1)
+
a1
(8) + Bei - 62) - (2) + aa - e1))
- B
8
+ 1)(22
x1) + 1 (01 + Bei e2) - (61 -ei)
(23)
a1
(1 - B)91
+ 81 + - ) + - B
α1
(ō1 + Beg - -2) - -01 =1)
1
8
b1
91
01 bj
where the second equality follows the updating rule in Eq 14 [4
For t 2 2, following the updating rule in [q.(14) we have
m
#++1 It + are + et - -e+1) = a1
bt
8m- 1 + (1 (1- (1-3)
at
(24)
=B (xz - x4 + 00-1 + et-1 - -cs)
as-1
att
3 m4-1 - (1 - -8)ax gt
+ 3
b
bj
by
We know l4+1 Iy + anle - et41 = (1 3) (v141 + -ap(e411 - 6:)) - (1 - -B)( age) +
3(11-1 - 21 + (δ( + e e++1)) so Eq. (24 can be rearranged
(1 (5x+1 + (r - e)+1)) + 3(I++1 24 a e - Ec+1))
=(1 - (Iz - -arez) + 8 (xx, x1-1 + 16 + ec - -())
(25)
+ 8 a1-1 aq
3 m - (1 - 3)at 9t
b- bt
be
Divided both sides by 1 - B, we obtain
3
Je+1 + (ōe - e(+1) +
(5++1 - 84 + te e ec+1))
1- B
3
=1t + 04 04 (8.-1 ex) +
ex-1 (I: xt-1 + ar- - -ea))
1
B
(26)
B
at-1
at
+ 1 B
3 m
b--
b:
0t gt
04
85-1 - (or - 0z 1)et
b,
Rearranging Eq. 26 have
B
(I++1 - xz) + 0t
T++1
+
-xt)
(de + Be, ct+1)
1
1- B
0t-1 (8i-1 1 + Be,-1 - 6t)
=3t +
(It
FT-1)
+
1
3
1 3
(27)
B
at-1
at
m4-1
1- B
b-11
b,
St
0t
01-15--1
(or 1e
13

---

Under review as a conference paper at ICLR 2023
Define the sequence
2t +
B
(et
Tz-1) +
at-1
(d1-1 + 8ez-1 -et)
(28)
1
B
1
We finally obtain
2++1
2t
B B
04-1
0t
m
0tt
gt bt.
1 (ar a2-1)e
(29)
4-11
b,
Recalling 21 zo and 01 obtain the conclusion.
co. have
au bg
Then, combining Eq 23 and Eq 29
A.2 PROOF OF THEOREM 1
Proof. By the the gradient Lipschitz continuous in Assumption 2 and Lemma 2, we obtain
L
([f(2)+1) - f(=)) s ((V)(()), 2+11 - 2+)
El|
2el1
2
f(z),
04-1
Ott
2 m m
(Vf(z)),
St at
b--1
be
E
(VV f(z)) at
01-100-11
E [V f2()) (0: - ar)et-1)l
L
8
0t-1
at
- at gt
27
R
① m
at 01-16:-1 - (ar - 04 -)
2
1
3
b
by
by
3
f(x).
0t-1
a2
3 m
mm-11
-E
(Vf(zz),
at
gt
bt
L
B
a4
ai gt
27
+ E
Mm-1
a a
(ar as as-1)et-1
2
3
bt
b,
<E
3
(V
04-1
a
3
mm-1)
E
(V.(
at
91
bt
bt
a4-1
at
9t
+ LE
m
LE
a
B
b-11
b,
be
L
L
+ - E
8z_
[13]
E
[|(
-ax ar)e=11
2
2
(30)
where the second equality holds due E [8,-]
0 and [e 1] 0. The last inequality holds
owing to BIIaa b|[ = Eilla 1 + B|||b||
E(a] 0 or B[b = 0, and Ellla + b1 < |||||a|| +
6|| | if E[a] & and b) + O.
Taking telescope sum from 1 to T on the both sides of Eq. 30
we then have
Elf(2r) - [(x1)] <
B E
V
f(x)),
0t-1
E
T
(V]())
gt by
1- 3
by
Ti
Ta
C2
at
LE
Mp-1
3
b1-1 1
T3
LE
9t
27
+
L
T
||
1 8r
11
L
E
T
||a - at)e
f
2
2
[=1
t=1
(31)
14

---

Under review as a conference paper at ICLR 2023
Now focus bounding T1 below. From Assumption 4, we know |I G 1,2,.... .... T) and
[ & G. Due to my = 8m4-1 + (1 - 3)g, and m, = 91. it is easy to obtain ||m/] - G by complete induction.
Since f & G and ||m/|| - G, we have
Ti
B
E
f(())
a1-1
ae
m
1-
1:11
be
(8)
3
T
V
(2)
|||m
04-1
b--1
b
(80
B
G
Σ
T
04- at
1 1- 8
b be 1
(32)
(18)
3
G
04 Ot
1-
b
b
8 G
C40
60
(10)
30
G
(1 3)p
where (i) holds sice la @ bll < ||||| max, [(b) < ||||||| b611. (ii) holds due to [f(z)]| < G and ||m G. (iii) holds because (he 1),
0 for any [1,2,... d]. (iv) holds due to
0 for any j E [1, (1.2..... (b.)
2 (b.)
Let us turn bound T2.
T
f (Zx), as gt.
T2 -E
T
T
(33)
=
V (zx) f(xz),
at
gt. bi
E
f
x2
az
gt
bi
25
Te
15

---

Under review as a conference paper at ICLR 2023
We now analyze T5 below,
TB
-E
Vf(=)) - f(zz), at
9t.
bt
(1)
E
ll((z)) f(2))11
E
91
69
(0 2
Σ
T
||21 - 2211
+
T
9t
2
2
2
(08) 1
Σ
B
(Tt x(-1)
0tt1 (6,-1 + BBt-1 -621 62)
E
2
1
1 3
(in) B3
L
(1- 8)² E
Σ
100 11
(1 3)3 E
|ay- 10:-12
L
L
2
E
000-11-111 11
E
Σ 1ar- 1
+
9t
(1 8)²
(1 - 3)2 31-3)3
3)- 9
T Σ
M4-1
I
E
07-1
+ +6 +e-1 - et
+
E
|a.- 81-1
b--1
(1 - By²
T
I
T
T
E
IE
| 1a--1;111 1|
+ 1E
(1- B)2
By²
B²L
L²LL2
(1- 8)2 E
Σ
m
+
(1 By² IE
Σ
|| ||a- 100-180-11 1
b-1
1.
L2 EE
L
E
Σ 100-101-111 11
Σ 1ar-
a
8
(1- 31-
(1 8)²
(1 B)2
3T1 E (1- 3)²
T Σ
1
T
27
101-1c4-111 ?
(1 8y² EE
||a- 1
+
9t
2
b
B²1 E
T Σ
(1 BT)2 E
T
a
m4-1
a2 |1 1112
(1 By2
b-1
(1-8)²
(=1
1=1
23
+ (1+ 12
1
(1 3)²
E
Σ a
2
1|
E (1 8)²
a
2
1|eo11
+
2
E
1=11
1=1
(v))
BBIPd
4(1 L2d
23d
(1 L2
G²
2
(11-3)² B)²
a
31-
(1 3)2
9)-
2p²
(832 10,3+050 5)L2d
G²
T Σ
+
a7
8)2
2p²
(34)
where (i) holds by following (a, 6) < ||aa|2
+ ||l|
1 (ii) holds due to Assumption 1, (iii) holds
due to Assumption I owing to Eq. 21). (iii) holds since E[[la [||la+b]1- -6 = [|[||] if E
= 0
or [bb] = 0, (v) holds resulting from the updating rule in Eq. (1)). (wi) holds due to
(m,
< 1,
(b:)y
1(6),1 < 2 (the definition of s,in Eq. ). ||] < in Lemma 1, ||9.1l S G in Assumption
and min 2 p > 0.
16

---

Under review as a conference paper at ICLR 2023
We then bound To
To = E
(F())) Ots
--- E
(V(a)) a0 vf(m)))
E (xtt), 9t vf(re))
by
(
Vf(x)) vf(zz) - -f(x))-11 )
E
arl [
E
be
T
vf(z1)
E
arl (2
+ (Vi(z1).
a ar-1
+E ))
Vf(z1) 91)
+ E
(((())
- -90)
Σ
(V/(z)), 0
b
b,
b:-1
(8)
vf(x1) I1
-
E
04 (
+B ( (Vi(z)),
bi
at
+
(V(x)).
b
(66)
E
ar
+E [V
a1 gall
b
a411
+E
E
0rl
2
513
E
arl (x
2G
1
Q1
b
T
E
[
4G
(18)
4Gaa
E
odl ((x)))1
P
(35)
where (i) holds due to max,(b)). (b:); < |bb.1| < G. (ii) holds owing E fx,) 9.و
0 in
Assumption and gr, b,-1 are independent, (iii) holds sice ||a o [|a max, [6), $ ||]||b||]
(iv) holds resulting from [[V((x))] < G and [ gell < [V Ioa: 2G. and (v)
holds because a--1 (br-)) (be), 2 for any j E [1, d). (vr) holds due to (bn)():); 2 0 for
any 11,,....
17

---

Under review as a conference paper at ICLR 2023
Then, pay attention to T3,
T3 3 LE
Σ
T
8
Ct
Ott
④
m
1
B
b--1
b
8
E
at
m+
11
(1- B)
b--1
be
(0) LG
at-1
3y E
b,
(00 LL
at-1
a1
a1-1
a22
S
max
(1- 8)3
(b.-1)}
(be)}
b
be
(10) 00 LG
0t--1
(36)
A(1 - 8)2
max
(b:-1)j
b
be
0000LG LG"
C1
A(1 By2 E
b
(10) 80 LG P(1 8)² E
b
(v6) a0 LG
ao
QT
A(1 83
bo
br
(wii) LG2d P² -32-")
where (i) holds due to |a @ bll < ||||||||| (ii) holds owing to ||m- < G. (ii) holds due to ||l|2 < max, [[a)]]|aa]],, (iv) holds due to oe
(b.-1), (b.), and Wي (b.), 0 for any j E [1,2, d]. (v) holds resulting from min, (Be) 2 > for any and a₂ is non-increasing. (wi) holds resulting from (b,-1); (b.) 2 0 for any j [1,2, d), (vii) holds due to telescoping sum, and (vitt holds due to
2 p > 0 for any j E [1, 11.......... d].
Now we turn attention to T1.
T4
LE
0
gt
L
E
T
0 1
L
E.
T
-
be
2
2
(37)
1 G²
T'
dL
T
<
+
2dL
o
(0t-1 - (0k-1-a013 ax)2
22
2
tm1
where the inequality holds owing |m,-1l $ G and min,(b)), p 0. 1166,-1),)1 < 2, and
B||lc=||3] < d.
Combining 37 we can obtain
B(s(zr) [(=1)) <
30
62 + (8.3² + 103 + +
G
Σ 0
(1 B)p
(1-3)2
2p²
4Gaaid
32
E Σ ad
(38)
p²(1 - 13
(1
G2
T
dL
T
+
+ 2dL
Σ
at +
Σ
2
1=1
t=l
18

---

Under review as a conference paper at ICLR 2023
Reformulating Eq. 38
then have
12
- -
(168² + 103 + 5 (1+
(888
+ 2dl.
Σ 0
2p²
(39)
dL T
+
(0:-1 - -0,)
06 G + 4Gaaad 3
+ p² B)2
- (1-3)p
It is known the learning rate saftifies an ing non-increasing and Cauchy-Schwarz inequality, we know E EL= arl f
vi 1t 2 and oo 0n c. Utiliz-
2
T + [())())))] = c
TT
T Σ [+ Σ of = = - S e1
2
N |T dl) S (1 + log T), and Σ
(at-1 - ax)2 Er - -0a²² S Σ ύ[- S
d²
{ S - dt) (
30² 8,
we further have
2)
C1
C2(1 log T)
E
V
(40)
VT
VT
where we define
dc
BodG2
4odG2
C cG'
[[f((1) -
(41)
16
(1
3)p
P
103+++5)
G2 C² L)
C2= dG
+ +2dL
(42)
312
2p²
B UNQUANTIZED BINSGDM
Algorithm 2. SoftSignSGD
Input: model parameter 2o. कι momentum ml 0, a exponential moving average factor B, the learning rate sequence {au}
0, the
2: for t 1,...,''s I' do
3: Randomly sample & and compute the gradient: g. (xzitt)
4: Update the momentum my; m, 33mm-1 +
-8)g
Update the momentum by: b, = Bb,-1 + (1 - })]g=
6: Update the model parameter 2++1: Tt-1 37 by
mu
7: end for
We refer to BinSGDM without quantization as SoftSignSGD. The implementation details for Soft- SignSGD are shown in Algorithm 2. The gradients need be aggregated among different workers before SoftSignSGD is performed, just like full-precision SGD and Adam. Compared to Adam, the first difference that we utilize the exponential moving average of the absolute gradient, i.e. b; (1 (1- b, Igel the denominator of the updating amount for SoftSignSGD rather than ventionally adopt the squared root of the exponential moving average of the squared gradient, i.e. /o, = (11 3-) + (1 32) Another difference is that the exponential moving factors for the nominator m,, and the denominator by are the same in SofLSignSGD. Both of the distinctions make each element of the updating amount in SoftSignSGD satisfies -1 < (m) S 1, E (1,2,....d) d].
B. EXPERIMENTAL RESULTS FOR TRAINING VGG16
We assess the performances of Adam, SoftSignSGD and BinSGDM with VGG-16 on CIFAR100. We sample set of 128 examples with the replacement for each batch. for SoftSignSGD and
19

---

Under review as a conference paper at ICLR 2023
BinSGDM is set to 0.95, and $1, for Adam is set to 0.9, 0.999. The weight decay is uniformly set to 0.05. To simplify the tuning process and ensure fair comparisons, each case, we start with the same learning rate of 0.005, divide the learning rate by 10 after 75 and 130 epochs, and finally terminate the procedure after 150 epochs. As visually illustrated in Figure the convergence speed and the test accuracy of SoftSignSGD and BinSGDM comparative Adam for training VGG-16 on CIFAR100.
AdamiW
BinSGDM
SonSign5GD
Test hccuracy
Loss
1.2
40
Train
0.8
0.4
20-
AdamW
BinSGDM
SoftSignSGD
0.0
0
150
30
Epoch
Epoch
(a) Train Loss
(b) Test Accuracy
Figure 5: Training loss and test accuracy for VGG-16 on CIFAR100.
B.2 EXPERIMENTAL RESULTS FOR TRAINING VIT
We train VIT-B with Adam, SoftSignSGD and BinSGDM on the ILSVRC2012. We use the Pytorch official implementation for ViT and all experimental settings follow the recommended, expect that to 0.95 for SoftSignSGD and BinSGDM and total epoch for all optimizers is set to 150 rather than 300. As shown in Figure 6, the convergence speed and the test accuracy of SoftSignSGD and BinSGDM can match Adam for training ViT-B-16 on ILSVRC2012.
AdamtW
SoftSig55DD
Test Accuracy
Test Accuracy
AdamW
BinSGDM
SoftSignSGD
30
60
90
120
150
30
90
120
150
Epoch
(a) Train Loss
(b) Test Accuracy
Figure 6: Training loss and test accuracy for VIT-B-16 I.SVRC2012.
B.3 EXPERIMENTAL. RESULTS FOR TRAINING LSTM
We perform experiments for training 3-layer LSTM on the Penn TreeBank dataset validate the effectiveness of SoftSignSGD. Our implementations are built upon the codes of the paper AdaBelief ① and we use the default experimental settings for adaptive optimizers the code, expect that we set :3 to 0.99 for SoftSignSGD and BinSGDM and the weight decay to 0.3 for all the optimizers. Figure indicates that the convergence speed and the inference performance SoftSignSGD and BinSGDM are competitive to the widely-used Adam.
20

---

Under review as a conference paper at ICLR 2023
150
AdamW BinSGDM SoftšignSGD
Adamw BinSGDM
SortSignSGD
Test Perplexity
100
27ard
50
50
100
150
200
200
Epoch
Epoch
(a) Train Loss
(b) Test Perplexity
Figure 7: Training loss and test perplexity (the lower, the better) 3-layer LSTM on Penn TreeBank.
0.10
Adam
SoftSignSGD
0.08
Loss
0.04
0.02
50
100
150
200
250
300
Iteration
Figure 8: The convegence behaviors Adam and SoftSignSGD. The loss function is f(x) 0.5x². The learning rate set to 0.5, æo is initialized to 1.0. 81 and 32 for Adam set to 0.9 and 0.99, and 3 for SoftSignSGD is set to 0.95.
C THE POTENTIAL OSCILLATION FOR Adam
Compared SoftSignSGD (Please refer to Algorithm 2 Section B), Adam may oscillate around the optimum and cannot approach it. As for SoftSignSGD, in the final optimizing stage, the elements of 9t will frequently change their signs in the neighborhood of the optimal gradient g frequently the sign of the element of the gradient, (gt),, Vj [1, 2, ..., d]. change, the according (me), will smaller than the according (be),- Hence, when the loss approaches a local optimum, where m, 8mm,-1 +
The more
my will be gradually close to O. As for Adam, the update amount is /v.
and vs = 320, + (1 )2 Although the elements of the gradient will frequently change their signs in the final optimizing stage, the relationship of size between (me) and (Vrz); for any j [1, 2,... d] is uncertain. Hence when the loss is close to a local optimum, the updating amount m. /os may not damp to O, which may lead the loss to be oscillating and not indeed converge local minimum. We provide an example in Figure to visually illustrate the convergence behaviors for Adam and SofLSignSGD.
21

---

Under review as a conference paper at ICLR 2023
Table 3: System throughput (samples/s) of AdamW. 1-bit Adam and BinSGDM for training ResNet-50 ILSVRC2012 with 10Gbps Ethernet 200Gbps InfiniBand.
Ethernet (10Gbps)
InfiniBand (200Gipss)
#GPUs
Optimizer
Throughput
Speedup
Scale
Throughput
Speedup
Scale
(samples/s)
Efficiency
(samples/s)
Efficiency
SGDM
3693
1.00x
100%
3693
1.00x
100%
8
1-bit Adam
3243
0.83x
100%
3243
0.83x
100%
BinSGDM
3462
0.94x
100%
3462
0.94
100%
SGDM
2959
1.00x
40.1%
4673
1.00x
63.2%
16
1-bit Adam
4715
1.60x
72.7%
5708
1.22x
88.0%
BinSGDM
6015
2.03x
86.9%
6784
1.45x
97.9%
SGDM
4270
1.00x
28.9%
9063
1.00x
61.3%
32
1-bit Adam
7268
1.70x
56.0%
10249
1.13x
79.0%
BinSGDM
9416
2,21X
68.0%
12131
1.34x
87.6%
SGDM
6189
1.00x
20.9%
16608
1.00x
56.2%
32
1-bit Adam
5546
0.89x
21.3%
16920
1.02x
65.2%
BinSGDM
15253
2.47x
55.1%
19956
1.21x
72.1%
Table 4: System throughput (samples/s) of AdamW, 1-bit Adam and BinSGDM for fine tuning BERT-Base on SQuAD 1.1 with 10Gbps Ethernet and 200Gbps InfiniBand.
Ethernet (10Gbps)
InfiniBand (200Gbps)
#GPUs
Optimizer
Throughput (samples/s)
Speedup
Scale Efficiency
Throughput (samples/s)
Speedup
Scale
Efficiency
AdamW
413
L.00x
100%
413
1.00x
100%
8
1-bit Adam
358
0.87x
100%
358
0.83x
100%
BinSGDM
412
1.00x
100%
412
0.94x
100%
AdamW
84
1.00x
10.1%
272
1.00x
32.9%
16
1-bit Adam
213
2.54x
29.7%
522
1.92x
72.9%
BinSGDM
431
5.13x
52.3%
776
2.85
94.1%
AdamW
119
1.00x
7.20%
543
1.00x
32.8%
1-hit Adam
274
2.30x
19.1%
903
1.66x
63.1%
BinSGDM
730
6.13x
44.2%
1365
2.51 x
82.9%
AdamW
158
1.00x
4.78%
998
1.00x
30.2%
1-hit Adam
252
1.59x
8.80%
1496
1.50x
52.2%
BinSGDM
990
6.26x
30.0%
2299
2.30x
69.8%
22

---

Under review as a conference paper at ICLR 2023
D EXPERIMENTS WITH INFINIBAND CONNECTIONS
To further evaluate the communication efficiency of SGDM/Adom, SeftSignSGD and BinSGDM with high bandwidth connections, we implement experiments for training ResNet-50 and BERT- Base with distributed nodes connected with 200Gbps InfiniBand. All the experimental settings are the same as we perform experiments with Ethernet in Subsection 5.1, and the experimental results are listed in Table and T
As shown in Table 3 and Table 4 compared with the baseline SGDM/Adam, BinSGDM can still reach up to 1.45x speedup for ResNet-50 on ILSVRC201 and x speedup for BERT-Base on SQuAD 1.1, although the speed advantage is not so obvious as that with whwwih Ethernet connections. An interesting phenomenon is that the system throughput of BinSGDM with 10Gbps Ethernet can match that of SGDM/Adam with 200Gbps InfiniBand.
The experimental results in Table and Table 4 also show that as the number of GPUs is increasing, the scale efficiency of SGDM/Adam, SoftSignSGD and BinSGDM becomes lower. The reason for this phenomenon can be summarized in the following. When the number of GPUs doubles, the number of communication trips also multiplies. We take the communication schemeAll-Rede for example. If the number of GPUs is n, each GPU requires 2(n 1) trips across the network confections. When the number is non-trivial the computation time of the communication primitives may exceed the time of the pure communication itself and dominate the overall communication time, since the total communication overhead does not change with the number of GPUs. Notably, All-reduce is more efficient than All-to-All which is the core of our Hierarchical J-bit. Hence, as shown in in Table 3 and Table 4 the scale efficiency of BinSGDM decreases more quickly than SGDM/Adam with the number of GPUs growing.
E DISCUSSION
In the original 1-bit Adam paper (Tang et al. (202I)). reports that 1-bit Adam runs significantly (up to 3.8x) faster than the frel-precision Adam. Moreover, as the number of GPUs grows, the speed advantage more obvious. In contrast, in our experiments, I-bit Adam does not exhibit clear speed advantages over the original Adam, and when running on 64 GPUs, 1-bit Adam is not only slower than the original Adam, but also its throughput rate is even lower than that on 32 GPUs. The reason for this phenomenon the speedup of b-b Adam is obtained by comparing the throughput at the compression phase with the throughput at the warm-up phase. The warmup phase is excluded for assessing throughput, while, in our experiments, we evaluate the overall average throughput of the warm-up phase and the compression phase for I-bit Adam. Second, the baseline original Adam in (Tang al. (2021) does not run with system-level efficient DDP. Third, in (Tang et al. (02II), the authors customized highly efficient communication primitives for 1-bit Adam. For the sake of fairness, we just utilize the off- tre-the-shlff communication primitives in Pytorch for all the optimizers.
be summarized in the following. First, in (Tang et al. 2021
As shown in Figure 4, when the number of GPUs continually, the communication time for BinSGDM also grows superlinearly. One of the reasons is that the communication primitive All-to-All accounts for more and more communication time. But the native All-to-All in Step (iil) in Hierarchical I-bit All-Reduce is not less efficient than the native All-Reduce. Hence, we will further optimize All-to-All and All-Gather to further accelerate BinSGDM.
When training large-scale DNNs, the mix mix-precision technique is used to reduce the memory, which allows us to further increase the model size. optimizers, we still use the full-precision state and full-precision computation which commonly accounts for 33-75% of the total memory footprint (Tim Dettmers, et al. 8-bit Optimizer via Block-wise Quantization. ICLR 2022.). BinSGDM does not need full-precision state and full-precision computation. Moreover, due to randomly quantizing the update to 1 or 11, BinSGDM may leverage lower precision than FP16 gradients to estimate the update. Therefore, BinSGDM is promising find more applications in reducing memory.
23


Reviews:
[{"review_id": "QtFiQBNVJl", "reviewer": "Reviewer_kGZr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "summary_of_the_paper": "A major bottleneck in large-scale distributed deep learning is the communication bottleneck. The computational cost of the majority of existing compression algorithms to reduce the communication cost is too high. The authors proposed a new distributed optimization algorithm, Binary SGD-Momentum which 1- compresses the updates of the model's parameters at each worker, instead of the gradients commonly done in most other distributed DL methods, and 2-stochastically quantizes the values to +1 or -1. To aggregate the binary quantized values, they devise hierarchical 1-bit All-Reduce to take advantage of the 1-bit quantized values, and inter-node/intra-node communications. Finally, they theoretically analyzed their algorithm and evaluated it performance using numerous experiments.\n", "summary_of_the_review": "The paper has presented an interesting and somehow novel compression algorithm for the distributed DL.The authors have provided both theoretical analysis and to some extent complete simulation results.\nI believe that the paper needs some minor improvements, such as double-checking the proofs of theorems and fixing some mistakes, ", "strength_and_weaknesses": "**Strengths:**\n\nThe authors have considered all aspects of distributed DL in developing their algorithm, such as computational cost, communication, and aggregation. This paper is among the few works that have considered compressing model updates instead of the SGs, and the simulation results show that the training with Bin-SGDM is consistently faster (or at least as fast as) uncompressed optimizers (even with high-speed intra-node connections among multiple GPUs).\n\n**Weaknesses:**\n\nIn some parts, the paper is hard to read and the intent of the authors of some sentences/paragraphs are not clear. Moreover, some notations are not defined, and the reader has to search the appendix for the definition of some of the concepts. Moreover, the theoretical analysis seems to be flawed at some points.\n\n1. There is a disparity between algorithm 1 and BinSGDM equation (4). Algorithm 1, line 7, keeps the maximum of $b_t^{(i)}$ and uses it to compute the parameter update. The authors do not explain or motivate this seemingly critical point in distributed BinSGDM, and it is not clear whether equation 4 or Alg. 1 is used for simulations. Practically, since the magnitude of SGs are usually larger at the first few training epochs, using the maximum value ($b_t^{(i)}$) is similar to scaling the SGs with a large constant value to map them to [-1, 1]. In other words, after few epochs, Alg. 1 applies (almost) fixed scaling factors to the computed SGs before binarizing them.\n2. Theorem 1, what are the constants $\\rho$ and $I$? Also, $z_1$ should be defined in the theorem.\n3. The analysis and proofs in the appendix either have some flaws or unclear:\n- Equation 10, note that although $g_t=\\frac{1}{n}\\sum_i g_t^{(i)}$, but $|g_t| \\neq \\frac{1}{n}\\sum_i |g_t^{(i)}|$. Hence, the RHS equation is incorrect. I am not sure how this affects the validity of the proofs.\n- Equation 34, the reason for 3rd and 4th inequalities are not clear.\n", "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": "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": "ONVlgz2ktx", "reviewer": "Reviewer_C7p2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The authors proposed a new quantized distributed stochastic gradient algorithm which resembles Adam.\n\nThey prove the new algorithm BinSGDM bears the same convergence rate as Adam, and BinSGDM is more communication efficient than Adam. They also compare the new algorithm with other algorithms, including ADAMW, 1-bit Adam and SGDM to show that the BinSGDM implementation is more performant than other algorithms' implementations.", "summary_of_the_review": "The algorithm looks novel, but there remains some work to justify the effectiveness of the algorithm.\n\n1. The experiments need to be done in more realistic settings (for example A100 with RDMA connections)\n2. Since the algorithm is based on a different update rule than the original Adam, to justify the new algorithm is as good as Adam (as one of the key contributions states) more comprehensive experiments are needed to confirm the uncompressed version of the algorithm matches the convergence of Adam on most tasks.\n\nAlso some claims need to be adjusted according to the \"Strength And Weaknesses\" section.", "strength_and_weaknesses": "There are four key contributions listed by the authors\n\n1. The first algorithm that quantizes the entire update of an adaptive optimizer (which seems to me that it translates to less quantization steps) and does not need warm-up.\n  - This one looks novel and simplifies the usage of this algorithm.\n2. BinSGDM has the same convergence rate as the full-precision Adam\n  -  This one is based on strong assumptions such as the gradients are bounded by a constant, and it doesn't say much since the convergence rate is also the same as SGD's 1/\\sqrt{T} rate. A simple quantized SGD can achieve the same rate.\n3. Hierarchical 1-bit All-Reduce\n  - This is a standard system implementation, basically it treats a node as a single worker in distributed training. Already implemented in frameworks such as DDP, Horovod, Bagua, etc.\n4. First work to be consistently faster than DDP\n  - This is highly dependent on the system implementation and computer network. And also not true, Existing works like Bagua and HiPress already show significant speedup over DDP\n\nTherefore the novelty seems to be 1, but since the algorithm is completely different from the traditional Adam (the second-moment stat is also replaced by first-moment of the gradient absolute value), more comprehensive experiments are needed to confirm the uncompressed version of the algorithm matches the convergence of Adam on most tasks.\n\nAlso since the paper claims to have speedup in real-world settings, it should use more practical settings for experiments. Most people don't use A100-80G GPUs with only 10Gbps ethernet connection.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8X_MufkppNi", "reviewer": "Reviewer_YNiH", "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": "", "summary_of_the_paper": "The paper proposes to quantize ( two values)  the updates of the adam optimizer. The approach leverages the bounded nature of adam updates to design a unbiased quantization scheme - it uses the value of the update to define a bernoulli distribution (+1, -1). They show improvements in speed in several experiments. \n\nSome questions /  comments, \n1. What is \\mathcal{M} on page two . It is not defined. \n2. what does \"random gradient of f\" mean? Also i believe g_t is a vector . so what is g_t / |g_t|  .. Do you mean elementwise division?\n3. Page 4, \"Adam do not have this appealing property\" can you explain this point further. The point you are making claims that adam does not converge at local minimas but keeps oscillating. \n4. Theorem 1 \n      a. statement about \"spectral norm of b_i\" is bounded. Are we assuming b_i to be a matrix?\n5. lot of grammatical errors in the paper. like neede, Lagre, \"cost become a bottleneck\",  \"be friendly to efficient primitive communication primitives\" and a lot more.", "summary_of_the_review": "The paper seems to be making a novel contribution.", "strength_and_weaknesses": "Strength:\n1. novel quantization scheme which is easy to implement \n2. Provable convergence as update is same in expectation\n3. strong empirical results\n\n\nWeakness\n1. writing needs a lot of work - see some confusions / point outs above\n", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject