Birder: Communication-Efficient 1-bit Adaptive Optimizer for Practical Distributed DNN Training
Authors: Hanyang Peng
Shuang Qin
Yue Yu
Jin Wang
Hui Wang
Ge Li
Venue: NeurIPS 2023 poster (2023)
Keywords: optimizer
1-bit optimizer
distributed learning
optimization for deep networks
communication efficiency
TL;DR: Communication-Efficient 1-bit Optimizer for Practical Distributed DNN Training

Abstract: Various gradient compression algorithms have been proposed to alleviate the communication bottleneck in distributed learning, and they have demonstrated effectiveness in terms of  high compression ratios and theoretical low communication complexity. However, when it comes to practically training modern deep neural networks (DNNs),  these algorithms have yet to match the inference performance of uncompressed SGD-momentum  (SGDM) and adaptive optimizers (e.g.,Adam). More importantly,  recent studies suggest that these algorithms actually offer no speed advantages over SGDM/Adam when used with common  distributed DNN training frameworks ( e.g., DistributedDataParallel (DDP)) in the typical settings, due to heavy compression/decompression computation or incompatibility with the efficient All-Reduce or the requirement of uncompressed warmup at the early stage. For these reasons, we propose a novel 1-bit adaptive optimizer, dubbed *Bi*nary *r*andomization a*d*aptive optimiz*er* (**Birder**). The quantization of Birder can be easily and lightly computed, and it does not require warmup with its uncompressed version in the beginning. Also, we devise Hierarchical-1-bit-All-Reduce to further lower the communication volume. We theoretically prove that it promises the same convergence rate as the Adam. Extensive experiments, conducted on 8 to 64 GPUs (1 to 8 nodes) using DDP, demonstrate that Birder achieves comparable inference performance to uncompressed SGDM/Adam, with up to ${2.5 \times}$ speedup for training ResNet-50 and ${6.3\times}$ speedup for training BERT-Base. Code is publicly available at https://openi.pcl.ac.cn/c2net_optim/Birder.

Birder: Communication--ffcien 1-bit Adaptive Optimizer for Practical Distributed DNN Training
Hanyang Peng"', Shuang Qin',, Yue Yu Jin Wang', Hui Wang', Ge Lift
Peng Cheng Laboratory, Shenzhen, China School of Electronic and Computer Engineering, Shenzhen Graduate School, Peking University, Shenzhen, China
penghy@pel ac. cn, qinsh@pcl ac. yuyēpcl ac. wangj050pcl.aae ac. en, wangh066pc1. ac. cn, gelißece pku. edu, cn
Abstract
Various gradient compression algorithms have been proposed to alleviate the communication bottleneck in distributed learning, and they have demonstrated ef- fectiveness in terms of high compression ratios and theoretical low communication complexity. However, when it comes to practically training modern deep neural networks (DNNSs), these algorithms have yet to match the inference performance of uncompressed SGID-momentum (SGDM) and adaptive optimizers (e.g. Adam). More importantly, recent studies suggest that these al algorithms actually offer speed advantages over SGDM/Adam when used with common distributed DNN training frameworks e.g., DistributedDataaaratte (DDP)) in the typical settings, computation or incompatibility with the efficient All-Reduce or the requirement of uncompressed warmup the early stage. For these reasons, we propose a novel 1-bit adaptive optimizer, dubbed Binary randomization adaptive optimizer (Birder). The quantization of Birder can be easily and lightly computed, and it does not require warmup with its uncompressed version in the beginning. Also, we devise Hierarchical-1 -hai----------eeeeeee lower the communication volume. We theoretically prove that it promises the same convergence rate the Adam. Extensive experiments, conducted on 64 GPUs (I to nodes) using DDP, demonstrate that Birder achieves comparable inference performance to uncompressed SGDM/Adam, with up to 2.5x speedup for training ResNet-50 and 6.3 x speedup for training BERT-Base. Code is publicly available at https://openi..cl..ee wwwppppww........ccce.eeee/e httpei2eeetooti/iiieeieeee
due to heavy compression/aecopprsiii
to further
Introduction
With the rapid development of computational power, "bigger" and "bigger" deep neural network (DNN) models are proposed for expect better performance, from the early classical models, such as
AlexNet(61 million parameters) (15), and ResNet (ResNet-50: 20.5 million parameters) [12] the current large language models (LLMs), such as BERT (BERT-Lagre: 340 million parameters [[0)
and GPT (GPT-3: 176 billion parameters) 5]. Scalable parallelism across distributed computing workers for training these large-scale models becomes a necessity. During training. millions to billions of parameters need to be communicated among workers each iteration, so distributed large-scale DNN training almost invariably suffers from the communication bottleneck.
To address the communication bottleneck, wide variety of lossy gradient compression algorithms have been proposed to lower the communication overhead. The algorithms can be broadly divided
"Equal Contribution
Conresoonding Author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

into three categories based on the compression techniques, including low-precision approximation
(e.g.. SignSGD TernGrad [31] and QSGD 3. 1-bit Adam (28)). low-rank simplification (e.g..
ATOMO 30 PowerSGD [29] and GradZip ) and sparsification (e.g.. Random-k [27]. Top-k [2],
and MSTop-k (4).. In addition to the specific compression techniques, some other works, such
as Error (e)dback(EF) (6), EF21 21, DIANA [19] and MARINA [I. focus on changing the compression objects from the gradient to the gradient and delayed error summation, or the gradient
differences to mitigate compressing errors and/or accelerate the convergence rate.
Gradient compression algorithms have demonstrated promising results with a high compression ratio and low oracle/communication complexity in theory. However, when practically training DNNs, they are still inferior uncompressed SGDM/Adam in terms of inference performance. This is because, these gradient compression algorithms are SGD-type optimizers, which will be commonly reduced to vanilla SGD without momentum if compression is not employed. The performance for a compressed optimizer is commonly upper bounded by its uncompressed counterpart, while vanilla SGD is typically less effective than SGDM for training DNNs. Particularly SGD-type optimizers are known to be substantially inferior to adaptive optimizers (e.g., Adam) for training Transformer-based networks which have become predominant in the DNN community. Supporting empirical evidences for this phenomenon can be found in Section B in the Appendix. Furthermore, if we apply the techniques of gradient compression algorithms to compress and communicate the gradients, and subsequently utilize the compressed gradients to construct adaptive optimizers in the local nodes, the final performance will be degraded (28). Therefore, designing native communication coattion-ommressionn adaptive optimizers is an underexplored problem that requires further research.
17 34
As for the system-lever speed, recent studies (33) pointed out, when distributedly training typical DNN models (e.g.. ResNet-50 and BERT- Base) with off-the-shed DistrbbuteDDataPari (DDP) at typical bandwidths (e.g. 10Gbps), existing gradient compression algorithms are still slower than uncompressed SGDM/Adam. This is because, the compressor for these algorithms are either quantization or sparsification or low-rank simplification, which exhibit one or more weaknesses below. (i) Vector-wise quantization and low-rank simplification compressors are commonly computationally heavy, and their time cost, in some cases, is close to and even larger than the savings from the reduces communications, empirical evidence has shown in [33 ; (ii) Sparsification compressors and bias quantization compressor are not naively combatable with the efficient communication primitiveA// Reduce due their inherent structures, and they have utilize All-Gather for aggregation in stead, which will significantly slow down the communication speed, as empirically shown in I ; (iii) Some low-rank simplification compressors 29) and quantization compressors (28 18 need to harness their uncompressed counterparts for warm-up at the early stage to stabilize the convergence, and the warm- up time is commonly nontrivial which some extent renders their high compression ratios vacuous. Therefore, from a system-level perspective, the design ethos of a system-efficient communication- compression algorithm is that we should guarantee that the compression/Decompessii algorithm is computationally light and takes less time, and it should also be friendly to efficient collective communication primitives. Additionally, there is no need to resort an uncompressed optimizer for warm-up.
of the
To this end, we propose 1-bit adaptive optimizer, called Binary randomization adaptive optimizer (Birder). which use the following updating rule is 22+1 = Iz= Q
mh where m, -:m--1 + (1
8) 14 = -3,-1 + (1 3) and g. is the gradient, and ((-) is a elem binary quantization operator. The main difference between Birder and existing gradient-quantization algorithms is that we directly quantize the entire adaptive update by rather than quantize the gradient gi or the momentum
my Because- - < (m.)) < 1, where (mz)s. (be) are the jth element of m, by respectively, each (be))
element of b. is easy to be randomly quantized to 1 or -1 in probability, making the quantization
computationally light. Another advantage of Birder is that it does not require full-precision optimizer to warm up at the early stage to ensure stable convergence. We also demonstrate Birder's 's convergence rate can match that of Adam. Moreover, taking into accost the nature of Birder, we devise an efficient hierarchical communication scheme to further speed up communication, which sufficiently leverages the uigh intra-bandwidth among GPUs within the same node.
In partieular, we make the following key contributions:
We propose novel 1-bit optimizer, dubbed Birder, which native communication- compression adaptive algorithm that element-wise quantizes the entire model update

---

and does not need to leverage its uncompressed counterpart for wprm-up, making compresion/ddeomprssionn computationally light and the extreme quantization ratio exert its best function (Section 2).
We theoretically prove that despite emolying extreme 1-bit quantization employed, Birder still promise the same convergence speed as the full-precision Adam (Section 3).
We develop new communication scheme for I-bit communication, called Hierarchical-l- bit-All- bit-AllRReduce, which sufficiently harnesses the ultra-fast intra-connects 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, running with DDP, our algorithm is the first work to consistently trump SGDM/Adam in terms of entire running time at little/no inference performance cost, reaching up to 2.47 x speedup for ResNet-50 and 6. x speedup for BERT-Base on 64 GPUs. (Section 5).
2 One-Bit Adaptive Optimizer Birder
In this section, we focus on solving the following problem for distributed training
min f(x) ((2;(())
(1)
ZER
where x is the d-dimensional model parameter, n is the number of distributed workers. g(9) the sampled min-batch data on the i-the worker. The sampled min-batch data all the workers is independent and identically distributed (i..dd). g(())(()) is the loss function. Note that fa {i) is commonly abbreviated as (z) in the following.
When distributedly training large-scale DNN models, using vanilla full-precision optimizers can cause communication bottleneck issues in gradient communication among workers at each iteration. To alleviate this problem, elegant SignSGD[I] was proposed, which merely takes the sign of each coordinate of the gradients. While this algorithm can substantially reduce the communication overhead, its practical performance is still inferior to popular adaptive optimizers, such as Adam. Fortunately, observe that the mathematical formulations connections, providing opportunity to propose a new optimizer that can combine their merits. This new optimizer can considerably reducing the communication volume with light computation, while maintaining fast convergence speed and high inference performance.
SignSGD and Adam have close
The mathematical updating rule of SignSGD can be formulated
Tz+1 < 3t (ggin(( =
9t [9.1
where a₁ is the learning rate, Jr denotes the estimated unbias noisy gradient of f(r)) with random samples, Sign(-) element- wise signum, and | an element wise absolute operator.
Whereas the updating rule of vanilla Adam 14 can be expressed as:
m < 81m+-1 + (1 81)gt.
1/ <- 321111 (1 12)
(3)
m
#++1 F1 at
Voi
where 31 and 32 represents the exponential moving average factors
If taking 31 and 32 to zero, B1, B2 0 in Eq. 3 Adam will be reduced to SignSGD.
For simplicity, omit the bias correction for and vs and the small constant in the numerator.
3

---

Given the observations above, we propose new optimizer that is an intermediate between SignSGD and Adam, referred Birder, i.e.
t 8m4-1 + (1 - 3)
b. 5- 30--1 + (1 1- 13)
(4)
m4
T++1 -- 3t - 2
where the j-th elements of my rigorously satisfies -1 quantization operator, and it quantizes the j-th element of mas be as follows:
I 1, 2()) is an element-wise
[b,]
(me)s (br);
- 1, with probability ] (m))2
+ 1)
1 11, with probability - (bi)
(5)
where E
(o
me )) by
mi by
so Q(-) is unbiased, and proof is provided in Section A of the appendix.
The detailed implementation of Birder in parameter-serve model is illustrated in Algorithm
Algorithm 1. Birder
I: Imput: all workers's model parameter wo, #1 the 7th worker's momentum me = 0.
60 O, 5t worker's local error e 0, server's global error ép 0, exponential moving average factor 3, the threshold To. and the learning rate sequence {axe).
2: for f = 1, I,.... T do
(On the 7th worker)
4: Randomly sample ((() and compute local gradient: gr
(9)
5: Update the local my : vn! 3m (4)
(0),
+ (1
3)9h (5)
6: Update the local B(0) ((9) [b(4 +
8)
9
7: Update the local 6 if t To [ by max
(b
else (b( B800
(4)
8: Quantize the local update: ut 2 m 2
9:
Update the local error feedback ( e
(8)
10:
Send u/") to the server (On server)
11:
12:
Average all received ge and quantize it: u. = 2 _
Σn
U1 1
(5)
13:
Update the global error feedback é, é, = 6z + Σ u,
Ut.
14:
Send back u, to all workers
15:
(On the tth worker)
16:
Update the local model parameter 2441 2141
17:
end for
This step Follows the technique in AMSGrad 30 It more about theoretical significance, and we commonly do not implement
The appealing characters of Birder are summarized in the following:
Compared to SGD-type optimizers, Adam provides fast convergence rate in practice by adaptively preconditioning the gradients with D; Birder inherits this feature to accelerate convergence speed. On the other hand, unlike Adam, Birder employs the same exponential moving average factor 3 for both m, and b, This eliminates the need for bias correction and reduces the amount of tuning work required.
Existing quantization optimizers are built upon vector-wise quantization 3 sides the quantization, they also require heavy computations to compute the norm a vector
19
Be-
'The typical gradient-quamtized optimizer QSGD quantizes the gradient as follows:
((9c);) signn())))(())))) I. with probability skeedl Tlasllo
(iggl\)ii r-1 with probability 1
where ||g:|p (E, D. and Allgelal E [5. [+d]
llolla

---

and estimate the sign of each element, which will renders the saved communication time cost somewhat meaningless. In contrast, Birder element-wise quantizes the update, and the subtle design for m, and by ensures the unquantized update is strictly bounded in the range 1-1, allowing quantization computed easily and lightly. Further, unlike most quantization optimizers that only compress the gradients [6]. Birder performs the quantization for the entire adaptive update, which further streamlines the optimization process.
Remark. We have noticed that the prior works 1-bit Adam ((28) and its variants ((16), [8] are also categorized as 1-bit adaptive optimizers. However, the design ethos of 1-bit Adam and Birder differ significantly. 1-bit Adam is still built on gradient quantization and and essentially functions as a preconditioned SGDM. 1-bit Adam runs full-precision Adam in the beginning (warm-up phase) and utilizes it as fixed precondition for SGDM during the rest of training (compression phase). There three aspects that influence 1-bit Adam to indeed accelerate communication. First, the warm-up stage constitutes approximately 15%-25% of the total steps, which to some extent discounts the high quantization ratio. Second, the vector-wise quantization employed by 1-bit Adam necessitates extra computations, including the calculation of vector norms and estimation of element signs, which are then transmitted as additional data. These factors diminish the time savings achieved through reduced communication bits. Third, the vector-wist quantization technique employed by 1-bit Adam is not compatible with the common-usee distributed framework DDP (system-level engineered distributed framework). In DDP, communication data is uniformly divided into buckets of equal size on the sender's side enhance communication efficiency. Consequently, when vector-wise quantization is used, communication data from a single layer may be divided into different buckets, resulting in substantial errors during restoration on the receiver's end.
3 Theoretical Analysis
In this section, we present the thcoretical convergence guarantee for Birder (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(z) 2 f"
Assumption 2. [Lipschitz continuous gradient] The gradient ( is L-Lipschitz continuous, i.e., [Vf(z)) - ff(v) & L|| vll2, Vz, Rd.
Assumption 3. [Unbias and indpendent noisy gradient] The gradient with respect to the random samples on each worker and at a different time is independent identically distributed (i.id.), i.e. (5) (1) independent of 91z for
Elgt (0) ((.)). 2 1, Di (1) independent of 9t (5) for i + j. and Its
h 12-
Assumption 4. [Bounded gradient] The noisy gradient and the full-set gradient are bounded i.e., l1g. (9) S G. [+)] S G, Vt 1.
Under the assumptions above, we then present the theoretical convergence for Birder in Algorithm 1.
For Birder in Algorithm 1, under Assumption 1-4, assuming (b))), 2 p 0, Vj e [1. 2, choosing
Theorem 1.
Vi Vt E [1, 2, ......... T7 and og = a1 and defining 21 21 + a0 -1)
(1) Eis ml) Σ" BoT
and el + ei (i) Et we then have the following
where 8,
X==1
2
Ci C2(1 + log
E
[
(6)
T
VT
VT
where
ddd
BedG
4cdG²
LBLGad
G = cG
+
+ p²11 1333
16
(1
B)p
P
(8,32 + 10,3 +
G2 + L)
C2 = è.G
+ 2dL
312
2p2
'ee commonly add a small constant to b, to avoid zero denominators for numerical stability, which guarantees this assumption holds in practice.
5

---

communication
Internede commuriation
1
Suafte:
Qlarfice
Subuc
Theeter
Bodice
Meec
kacter
Quallir
st-al Bedsce
Pepartio
OPe
Reguntie
Oran
ONUS
Figure 1: Paradigm of Hierarchical---ii--e -il---l---euueee
The theoretical results suggested that 1-bit Birder essentially achieve the convergence rate (0( )) as the uncompressed Adam
Hieerarchical---iitAAllRBe-
The data communication for Birder one-bit, which cannot be directly aggregated using the efficient All-Reduce. Additionally, there is significant imbalance between the intra-node and inter-node bandwidths. If we attempt to aggregate the data uniformly from both intra-nodes and inter-nodes, the communication process will be hindered by the inter-node data exchanges, resulting in slower overall communication.
In light of the problems above, propose hierarchical communication scheme called Hierarchical- 1-bit-Al-Redice This scheme efficiently aggregates our 1-bit data by leveraging the ultra-high intra-node bandwidth and reducing the inter-node communication overhead. Assuming we have nodes, each containing m GPUs, and the overall volume for each GPU needs to be communicated follows: (i) Each GPU performs Reduce- -Saatter to locally aggregate and scatter the data within its node. The communication volume for each GPU in this step is (m-1)P (ai) GPU then applies Birder to quantize the data, resulting in reduced volume of P 32m each GPU. (fii) The GPU proceeds with J- bit-All-Reduus to inter-aggregat the data. This step consists two sub-steps: 1) Each GPU performs All-to-All to collect the corresponding data from GPUs in other nodes, with communication volume of (m-1)P Each GPU averages and re-quuatizes the data, followed by All-Gather operation to 32mm
is P.as visually depicted in Figure [ the steps of
gather the data. The communication volume in this sub-step is also Pn-1)P (iv)Finally, each GPU 32mm
performs All-Gather to antra-aggeegat the data, with a communication volume of (m-1)P
32m
Compared to the time cost of inter-node communication, the time cost of intra-node communication relatively insignificant. Thus, when utilizing Hierarchical- -ii-------------- All--Rducee the majority of the communication cost arises from the 1-bit All-Reduce step in Step (iit). The communication volume 32 In contrast, we were to simply employ the original All-Gather to aggregate data, the communication volume across nodes for all
across nodes for all GPUs in this scheme is approximately 2(n-1)P
m²n(n- Consequently, Hierarchical- -il---l-ee proves 32
GPUs would be approximately significantly more efficient than the original All-Gather.
Notably, the work [32] also introduces 1-bit data communication scheme among nodes, but it can only guarantee the expected value of the gathered 1-bit data equals to the average of the original 1-bit data among nodes, thereby will bring performance deterioration. In contrast, All-to-All in Hierarchical- --riiccll--bit- --bit-Alll Reduce ensures the final data exactly equals to the average of the original data.

---

500M
560 b Adam Bisder
Adat: Binc
3
Epoch-wise, ResNet-50, batch size=32 x 64 (b) Time-wise ResNet-50, batch size=32 64
50DM Adam Brow
SC0M
3
Spach
Wall clock me (m)))
(c) Epoch-wiss ResNet-50, batch size=128 128 x 64 (d) Time-wise, ResNet-50, batch size= x 64
BersAcam
65-
60
0.5
10
15
20
13
166
Spach
(c) Epoch-wise, Bert- Bert-Base, batch sizc=3 64
Time-wise, Bert-Base, batch size=3 x
Figure 2: Epoch-wise and RcsNet-50 with 128 samples per GPU, and fine tuning BERT- Base with samples per GPU with 64 GPUs.
convergence speed for training ResNet-50 with 32 samples per GPU,
Experiments
Table 1: System throughput and Test Accuracy of SGDM, 1-bit Adam and Birder 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) 3693 (1.00x)
Top-1 Acc. (%)
Throughput (samples /s)
Top-1 Acc.(%)
SGDM
76.19
5272 (1.00x)
75.05
1-bit Adam
3243 (0.53x)
75.55
5229 (0.99x)
75.42
Birder
3462 (0.94x)
75.98
5251 (0.99x)
75.45
SGDM
2959 (1.00x)
75.96
6189 (1.00x)
74.61
1-bit Adam
16
4745 (1.60x)
75.33
8836 (1.42x)
75.05
Birder
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.62
Birder
9416 (2.21x)
75.27
15950 (1.61
74.82
SGDM
6189 (1.00x)
75.37
16640 (1.00x)
74.22
1-bit Adam
64
5546 (0.89x)
75.55
16426 (0.99x)
74.14
Birder
15253 (2.17xx)
75.30
23727 (1.43x)
74.24
Recently, several works [3 have shown that when utilizing the system-level engineered distribut- ed data-parallel framework DDP, the existing
optimizers (excluding 1-bit Adam) still perform slower than the uncompressed SGDM/Adam. Therefore, in our evaluation, we focus on assessing the performance of Birder, the uncompressed SGDM/Adam, and the closely related algorithm 1 1-bit Adam through distributed training experiments using the benchmark models ResNet-50 (CNN) and BERT- BERT-Base (Transformer). More extensive experiments be founded in Section B of the appendix.

---

Table 2: System throughput and Fl-Score Excat-Match of BertAdam, 1-bit Adam and Birder for fine tuning BERT-base on SQuAD 1.1 with 8, 16, 32, 64 GPUs.
Optimizer
#GPUs
Throughput (samples/s)
FI-Score (%)
Exact Match (%)
BertAdam
413 (1.00x)
88.
80.59
1-bit Adam
8
358 (0.87x)
88.05
80.06
Birder
412 (1.00x)
88.71
81.18
BertAdam
84 (1.00x)
88.47
81.07
1-bit Adam
16
213 (2.51x)
87.87
80.31
Birder
431 (5.18x)
88.31
80.80
BertAdam
119 (1.00x)
88.38
80.94
1-bit Adam
32
274 (2.30x)
87.78
80.08
Birder
(6.13x)
88.08
80.50
BertAdam
158 (1.00x)
88.13
80.94
1-bit Adam
64
252 (1.59x)
87.33
79.67
Birder
990 (6.26x)
88.28
80.75
5.1 Experimental Settings
Our experiments were conducted a testhed consisting of 1, 2, 4, 8 nodes interconnected via 10Gbps Ethernet. Each node was equipped with 8 Nvidia Tesla A A100-80GB GPUs. The hardware and software configurations were identical across all instances, with Ubuntu 20.04.4 LTS serving as the operating system. PyTorch 1.11.0 was used as the primary framework, accompanied by CUDA-11.6 cuDNN-8.2, NCCL-2.10.3, and PyTorch 1.11.0 for other relevant libraries. Notably, to ensure compatibility with PyTorch's DDP, certain components of Birder and our hierarchical communication scheme were implemented within the customized communication hook of DDP.
Training details. For the experiments over ResNet-50, we evaluate the convergence and performance of SGDM, 1-bit Adam and Birder IISVRR22012 The batch size per GPU is set 32 128 with the standard input resolution 224 x 224. When employing SGDM (baseline), the learning rate starts at 0.1 hoteh size with momentum of 0.9 and weight decay of 0.0001. When employing 1-bit Adam
256
and Birder, the learning rate starts at 0.001 x batch size with weight decay of 0.0001, and [$], 82] for 256
1-bit Adam is to [0.9, 0.999) and / for Birder set 0.95. Then, the learning rate 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 BertAdam (baseline), 1-bit Adam and Birder for SQuAD 1.1 fine-tuning task using pre-trained BERT-Base model checkpoint from HuggingFace 4 The batch size per GPU is set to 3. We perform fine-tuning for 2 epochs. The learning rate linearly increases to 1 10-4 steps in the early 500 steps and then linearly decreases
in the rest iteration. Specifically, the first 0.2x steps are used as the warmup stage for 1-bit Adam. [B,, 322] for BertAdam, and 1-bit Adam is set to [0.9, 0.999] and for Birder is set to 0.9.
5.2 Experimental Results
Figure shows the convergence behaviors of epoch-wise and time-wise training for SGDM BertAdam (baseline), 1-bit Adam, and Birder using ResNet-50 and BERT Base models running on 64 GPUs. The experimental results clearly demonstrate that Birder achieves a similar epoch-wise convergence rate compared to the baseline. However, the actual training speed of Birder surpasses both the baseline and 1-bit Adam by significant margin.
Figure illustrates the system throughput of different optimizers when running ResNet-50 and BERT-Base on 8 GPUs 64 GPUs node to 8 nodes). When training on 8 GPUs node), where computation takes precedence over communication, the throughput of Birder is slightly lower than that of SGDM and BertAdam. However, as the number of GPUs increases, Birder consistently outperforms its counterparts, and this superiority becomes increasingly evident with more GPUs. Additionally, the system throughput for SGDM. BertAdam, and 1-bit Adam occasionally decreases the number of GPUs increases, whereas the throughput of Birder steadily grows. This observation indicates that Birder offers better scalability efficiency.

---

BertAdam
17300
Rinder
1-20t Adam
823
L2000
12000
10000
1090
5 5/1
10 GTVs
52 GMC
64 Gits
G
16 C/P
52 GMUs
8 GPUs
15 GPUs
32 GRU
OPUS
(a) ResNct-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, Re) with 128 samples per GPU, and (c) fine tuning BERT-Bas with 3 samples per GPU with 16, 32, GPUs.
Compate ban Time
Bariddar Computatoo Time
computatann Line
1:08 Alies Cormastttion fime
Care eutaii
1-00 Adem Compu Docoma Thee
U-0 Adies Usuan lewe
64 Carr Decaraa lome
Binder
sirer Coneee time
3-1 Oring aDeceme
S-di quvieromee time
(a) ResNet-50, 32 samples/ / GPU (b) ResNet-50, 128 samples GPU (c) BERT-Base, samples GPU
Figure 4: Computation time, communication time and compression/decomprssiio time per iteration of optimizers for training (a) ResNet-50 with 32 samples per GPU, Re) with 128 samples per GPU, and (c) fine tuning BERT BERT-Base with samples per GPU with 8, 16, 32, 64 GPUs.
In terms of inference performance for ResNet-50, we evaluate the Top-1 accuracy after training on ILSVRC2012 from scratch. For BERT-Base, measure the Fl-score and exact-match score after fine-tuning on SQuAD 1.1. Table I that when the batch size is set to 32 samples per GPU, the accuracy of Birder is slightly lower than that of SGDM. It has been suggested in some works (I3). (35)) that adaptive optimizers generally yield worse generalization compared to SGDM for CNN architectures. However, as the batch size increases (Table 2). both 1-bit Adam and Birder achieve better accuracy. This can be attributed to the beneficial effect of introducing a certain level of noise for generalization ([25)) which biases the optimizer towards wider valleys. Table demonsttrats that Birder achieves similar or higher F1 F1-score and exact-match score compared to BertAdam and 1-bit Adam, validating the effectiveness of Birder for inference tasks.
5.3 Communication Efficiency Analysis
As shown in Figure training single node demonstrates that the baseline SGDM and BertAdam algorithms are slightly faster compared to Birder and 1-bit Adam. In this scenario, the inter-GPU bandwidth within node is extremely high, rendering communication time negligible. However, the newly introduced compression/decoopeestt its implementation. Thanks to costtcoomptttion quantization, the compression/dccoopresti time for Birder with ResNet-50 and BERT-Base is significantly reduced to approximately 15ms and 8ms respectively. When conducting distributed training across two nodes, the bandwidth between them is relatively limited (10Gbps in our experiment), making communication time critical factor. In the case of uncompressed SGDM and BertAdam, the communication time substantially exceeds the computation time for ResNet with 32 samples per GPU and BERT- Consequently. the system throughput lower compared a single node (as depicted Figure 2). However, the extreme 1 1-bit quantization implemented in Birder effectively reduces communication overhead, resulting in only a marginal increase the total time required for Birder. the number of nodes continues to increase, the importance of an efficient communication scheme becomes paramount. By leveraging
process by Birder and 1-bit Adam adds extra time due

---

our proposed fferarchical-I--it-Al -eehcce the overall inter-node communication volume exchanged scales proportionally with the number of nodes. In contrast, the Compressed-All -lldeeecce method employed by 1-bit Adam 28 results in the overall communication volume exchanged among nodes being proportional the number of GPUs (eight times larger than the number of nodes our experiments). Consequently, as the number of nodes increases, the communication time for Birder exhibits a gradual rise, while the communication time for 1-bit Adam experiences sudden surge.
Reduce
Conclusion
In this study, we introduce novel 1-bit adaptive optimizer for distributed training. Our optimizer offers the advantages of being lightweight in terms of computation while employing extreme 1 1-bit quantization for the communication data. Furthermore, we provide theoretical evidence demonstrating that Birder can achieve convergence rates comparable to the uncompressed Adam. To enhance communication speed, we propose novel communication scheme tailored specifically for Birder, replacing the inefficient naive All-Gather approach. Through extensive experiments on benchmark models such ResNet-50 and BERT-Base we validate the effectiveness and efficiency of Birder in comparison to uncompressed methods like SGDM/Adam as well as the relevant 1-bit Adam.
Acknowledgments
This work supported by the National R&D Program China (Grant No. 20227D01 153001 the Major Key Project of PCL (Grant No. PCI.2023AS7-I), and the National Natural Science Foundation of China (Grant No. 61806128).
References
[1] Saurabh Agarwal, Hongyi Wang, Shivaram Venkataraman, and Dimitris Papailiopoulos. On the utility of gradient compression in distributed training systems. In Proceedings of Machine Learning and Systems, volume 4, pages 652 672, 2022.
[2] Alham Fikri Aji and Kenneth Heafield, Sparse communication for distributed gradient descent. arXiv preprint Xiv: 15021,021, 2017.
[3] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication efficient sgd via gradient quantization and encoding. In Advances in neural information processing systems, volume 30, 2017.
[4] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashrce Anandkumar. Signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning. pages 560-569, 2018.
[5] Tom Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33: 13:1877-1901, 2020.
[6] Congliang Chen, Li Shen, Haozhi Huang, and Wei Liu. Quantized adam with error feedback. ACM Transactions on Intelligent Systems and Technology (TIST), 2021.
[7] Jacques Chen, Frederík Kunstner, and Mark Schmidt. Hcavy-tailed noise does not explain the gap between sgd and adam on transformers. In 13th Annual Workshop on Optimization for Machine Learning, 2021.
[8] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv: 1808.0294. 2018.
[9] Minsik Cho, Vinod Muthusamy, Brad Nemanich, and Ruchir Puri. Gradzip: Gradient compression using alternating matrix factorization for large-scale deep learning. In Advances in Neural Information Processing Systems, 2019.
[10] Jacob Devlin, Ming-Wei Chang, Kenton Lec, and Kristina Toutanova. Bert: Pre-training of deep bidirec- tional transformers for language understanding, arXiv preprint 1810::1810004800 2018.
[11] Eduard Gorbunov, Konstantin P Burlachenko, Zhize Li, and Peter Richtárik. Marina: Faster non-convex distributed learning with compression. In International Conference on Machine Learning, 2021.
10

---

[12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition, pages 770-778, 2016.
[13] Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to sgd. arXiv preprint
2017.
[14] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
[15] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84-90, 2017.
[16] Conglong Li, Ammar Ahmad Awan, Hanlin Tang, Samyam Rajbhandari, Yuxiong He. 1-bit lamb: Communication efficient large-scale large-batch training with lamb's convergence speed. arXiv preprint arXiv: 144,0990, 2021.
[17] Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han, Understanding the difficulty of training transformers. arXiv preprint arXiv: 2020.
[18] Yucheng Lu, Conglong Li, Minjia Zhang, Christopher De Sa, and Yuxiong He. Maximizing communication efficiency for large-scale training via 0/1 adam. arXiv preprint arXiv:2202.066 06009, 2022.
[19] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáš, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901. (tto::991.09200 00069, 2019.
[20] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018
[21] Peter Richtárik, Igor Sokolov, and llyas Fatkhullin. E121: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems, 2021.
[22] Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In International Conference on Machine Learning, 2021.
[23] 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.
[24] 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 learning on public cloud clusters. In Proceedings of Machine Learning and Systems, volume 3. pages 401-412, 2021.
[25] Samuel L. Smith and Quoc V Le. A bayesian perspective on generalization and stochastic gradient descent. In International Conference Learning Representations (ICLR), 2018
[26] Sebastian Stich and Sai Pranceth Karimireddy. The crror-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint arXiv: 05350, 2019.
[27] Schastian Stich, lean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in Neural Information Processing Systems, volume 31, 2018.
[28] Hanlin Tang. Shaoduo Gan, Ammar Ahmad Awan, Samyam Rajbhandari, Conglong Li, Xiangru Lian, Liu, Zhang, and Yuxiong He. 1-bit adam: Communication efficient large-scale training with adam's convergence speed. In International Conference on Machine Learning, pages 10118-10129, 2021.
[29] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient com- pression for distributed optimization. In Advances in Neural Information Processing Systems, volume 32, 2019.
[30] Hongyi Wang. Scott Sievert, Shengehao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication--lffiiieee learning via atomic sparsification. In Advances in Neural Information Processing Syxtems, volume 31, 2018
[31] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li, Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in neural information processing systems, volume 30, 2017.
[32] Feijie Wu, Shiqi He, Song Guo, Zhihao Qu, Haozhao Wang. Weihua Zhuang, and Jie Zhang. Sign bit is enough: a learning synchronization framework for multi-hop hop all-reduce with ultimate compression. In Proceedings of the 59th ACM/IEEE Design Automation Conference, 2022.
11

---

[33] Hang Xu, Yuen-Yu Ho, Ahmed M Abdelmoniem, Aritra Dutta, El Houcine Bergou, Konstantinos Karat- senidis, Marco Canini, and Panos Kalnis. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report. 2020.
[34] Jingzhao Zhang. Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good attention models? Advances in Neural Information Processing Systems, 2020.
[35] Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Chu Hong Hoi, et al. Towards theoretically understanding why sgd generalizes better than adam in deep learning. Advances Neural Information Processing Systems, 33:21285 21296, 2020,
12

---

Appendix
A Theoretical Analysis for Algorithm
practice, we implement Birder in a con-parameter-senne server model to further reduce the communication overhead, but the data exchange is essentially equivalent to that in a parameter-server prototype. Hence, we provide the theoretical analysis for Birder in parameter-server model as shown in Algorithm 1.
According to Algorithm 1. the update ú, can be recursively formulated
(6) +
i
1=1
U1 + E
El71
(
+ (1)
+ - Ect1
(9)
(1)
(1)
600
+
6+1
+ ex+1
(2)
m
(0)
) + 0t Ex-1
- 4-1)
n
Denote
91
(8)
mh
mi
8m, + (1 3)g.
(9)
(0)
(10)
1
m
(1)
8,
(11)
(0)
bc
e1
+
é1
(12)
71
(13)
Hence, the updating rule can be summarized as
1t++1
Ft
Cke Ust
me
(14)
=I+
+ bz + -
b
A.1 Auxiliary Lemmas
Lemma 1. Let we me the element-wise quantization function is defined in Eq.(5) can be reformulated
= = { 1, with probability p
[Me),
@ ((w)))
(1,.1,2....,), d}, -1 (mc) $ 1))
(15)
-1 with probability 1 1-p
We have es Q (m)) and then the following holds true
F[e=]=00 0, E [|ee]] d.
(16)
Proof. From Eq. 15 we know
E (ex)))
= E. [14 2 (ue)
1
(17)
2 ((u)) + 1) ((ur)s - 1) + (1 / ((m1) + ())(()), + +1) = 0.
13

---

and,
B [(x))]] E [((ue) 2 ((())))))
2 ((r))) + 1) ()u()) - 112 + (1 [(uu); 1))((u)) + 1)²
(18)
((uc)s)* 1.
Hence,
E E = 0, E [lee: S d.
(19)
Lemma 2. Let To 31 and On 01 in Algorithm I, defining the sequence
21 + cr (d1 - e1)
(20)
01-1 + 1 8 (It 22-1)
(ô1-1 + Be--1 et),
(21)
1 B
Then the following equality will hold, iee,
2141 2t +
B
04-1
at
3 m
au St
ar 10-1 (ar au 1).1)
(22)
I-
b
bi
Proof. For l we have
22 - 21 = 22
(72 x1) + 01
(61 + Beg 02) - (x1 + 01 - e1))
3
1-
8
1)(22
x1) + ' 8
on
(6) + Bei 62) Q6 E1)
(23)
On
3)91
0 (61 Ber -2) a1 -ei)
+ -1
bi
91
where the second equality follows the updating rule in Eq. 14
For 2 2, following the updating rule in Eq. 14), we have
Øt+1 It + (be + e - es+1) at by
ma
3m + (1 -39
(24)
=8 (s+ Ft-1 + 01-1166 + ct-1 - Et))
0r-1 a1
3 mi-1 (1 - -8)aa gt
+ 3
b-
b:
b.
We know 2141 - Iı + ai(e el+1) (1 3)(411 + aa(ee11
0:)) (1 (=) - aseie) + 3(1411
2t + (6 + c1 c1+1)), so Eq. (24) can be rearranged as
(1 - ()(+1 + as ce+1)) + B(xe+1 3z + (6 + c(+1))
= (1 - ()( -aee) + 3 (x: #1-1 + cn- (ō)-1 E1-1 -ca)
(25)
3 at- ai
gt c m (1-3)0m -3)a
be-1 b
b.
Divided both sides by 1 - B, we obtain
B
Øe+1 + a0 - e++1) +
1- (1e+1 2; + (0. + -(+1))
8
=0
18 ct)
(xx
ta 6-1 -i))
I-
(26)
at-1 1
a
m
I
3
b
at Dr
cc-181-11 - (ere at- e
14

---

Rearranging Eq.
26 we have
8
3++1
+
c++1 It) + 1- (ōe + geg ce+1)
-2 +
(2)
I1-1) 1) + 1 B
at-1
(6--1 + 9 -ec)
8
(27)
Qt-1
at
① m,-1
b
a
at-1
10-11
(ar - ai e)
Define the sequence
+
(xx 3 x2-1)
04-1
(d 3et-1 ee)
(28)
1
3
1 8
We finally obtain
20+1
B
04-1
di
0 m
gt by
-0-111-11 (ar a--1)e4-
(29)
-
b
b
Recalling 31 and Oro, we have conclusion.
21
00.
Then, combining Eq, 23 and Eq. 29
we obtain the
A.2
Proof of Theorem
Proof. By the the gradient Lipschitz continuous in Assumption 2 and Lemma 2, obtain
T
(x(41) f(x)]] & BB ((x)(()), - 21) +
Ellee11 =2
E
2
B
at-1
a1
3 m 1)
E (V)())) 2t)
8
bc-1
be
B f(x),
ar
- E
(V f2t), (ar - ac)
E
L
B
Ct-1
a
2 m
St b
a1-18.-1
(are a )
2
b
b
B
(V
f(x),
a111
a
3 m 1)
- (V
(Vf(2)),
ac 21
8
b
4
by
E
3
Qt-1
b
ar
14-1
a 9t
bi
24
8
(ar a- 10
12
f(+)),
au1
a
②
mm-1) 1)
a F. (V)(2))
9t
b
b
b
at
gt
LE
b
m1t-1
a
1 [|| 8, [13]
||| [a]
ax)cr
(30)
where the second equality holds due to 1 [6,-]] 16 - 0 and See = 0. The last inequality holds owing to
Ell + ]1]2] = ]]] [][[||?] if B[a] = 0 or E|6]
0. and Elle + 6 < 2E|l|a 13] + 2 if
Ela] and [(]]
15

---

Taking telescope sum from 1 to T on the both sides of Eg.
30
we then have
B B[S(2T) -(=i) -
T
V
(zx);
ar-1
o
m
E
(VI(=))
3
b
be
be
O1-11
+ LE
B
by
T3
+ LE
91
2
+
E
0
6
11
L E
L t=1
(a:11
a.)el1
2
2
(31)
Now we focus on bounding Ti below. From Assumption 4. we know || S G (1 = 1. T) and
[+][l & G. Due to m,, = -1m-11 + (1 3)gr and mi = gr. it is easy to obtain |ma.|| I G by complete
induction.
Since [+)((=)]l < G and |mm s G, we have
T
E
0u-1
ae
m
1
8
b-11
V m
(8)
8 G
a1-1
Qr
3
b-11
b
(32)
GPE
au-1
1 B
b--1
bx
8 C
(iv)
ag3d
G²
(1 - 3)
where (i) holds sice @ | < ||a|| max, [(b),l < ||a||][6|1.. (ii) holds due to ff(=)]] < G and ||me|| < G, (fit) holds because (b,-1); (i) 0 for any E [1, .... d). (iv) holds due min, (br), p > 0 for any j (1,2,...,4) d.
Let to bound T2.
St fV((z)
T2 -
ac
by
T
(33)
f(z))))
VV
f(x))( a
St.
EE
Σ
V
(
g1
T6
16

---

We now analyze T; below,
T3
E
(V((2) f(x)),
at )2)
E
[s(=)) s(x))11
+ E
(6) L2
S 2
E
Σ
|| - =1,l?
+ 2
(60) L
E
8 (w) T2-1) +
(ō.-1 + ser- es)
1112
M
-18
2
(40)
L2 E
L
T
Σ
22 H--1 1|
E
181-1111111
(1 8)2
(1 - By²
1
|a-
10--111-11 1||
(1 - 8yz E
lan-1e||
(1 B)²
2
L2
Σ 0t-1
T
114-1
+ + ct-1 1
2
T
0
8)2
8)
L²
L
+ (1 8)
|0-- 16-116t-1 1|
|0t-16||1
R
(1 8y2
L2L
L
|0
10--18.-11)
(1 - B)²
b-
(1 8)2
L
L²LL E
2
+ (1 B)² TR
1a--16t-11 161- 11
Σ 1ar-1e0|2
E
|| a4 8
11?
(1- 8y
By² (1
L?
La
T Σ
B)² IE
|a C1 11?
E (1 By²
|an-1e112
E
L
(1+ )))
(1 8y²
Σ 01-1
M
(1-3) E
Ck
||
1
2/
+ (1- 8)²
E
01-1 ||t-1 1
+ (1 (1-3)² 8)²
Σ
a ||ee||
C22
by
(e))
LLddd
4(1 + L)d
2Bd (1+
G²
(1-88)²
(1- -)2
(1 (1-
(1- 8)2
2p²
0111
(833
103 + L)L'd
G
18)²
2p
0
1=1
(34)
where (i) holds by following (a, b) < 1 |||||
+ + || (ti) holds due to Assumption (iii) holds due
Assumption 1 owing to 21) (fit) holds since B ||a + b1l ||lla| + B[]][[] if B[a] 0 or E(b] 0. (e) holds resulting from updating rule in Eq. 14b. (wi) holds due (me),
1 (5), < (the definition of in Eq. 11 B|]lee]11] [ < d in Lemma 1, lg G in Assumption and miny(b:); 2 e 0.
(b2)
17

---

We then bound T3
fars) at 21
To =
V (xa)) au vi(xn))
VV(a)). 9: V.f((rr))
=-B
be
b,
[V(()) vf(x,)) -
a.l (<)))
E
bi
vf(a1)- -
(VI[(()))))
+ (VI(m))
61
0c-1 a:
Vf((e)) - gt
(z)))
((f(x)) 9
+E (VV(()),
b
bi
be-1
vf(z1) - m
+E (Vf(x)),
+ E
b
(R8)
+E [V
91ll
VV \/(
0t-1
20
Qt-1
(<:))|
+ 2
Ot-1
51
b
b
R
(()))1
1G²F
(oi)
aGa
P
(35)
where (i) holds due max, (b.), < |b.|| S G. (ii) holds owing to E ( 9.] in Assumption and
gr. bi_1 are independent, (zi1) holds sice |a @ bll < ||a| max; [b), < |a [[]]]] (iv) holds resulting from
f < G and ||V fxze) gell < [x)) + Ilgell S 2G, and (v) holds because (b--1); (0+) 2 0
oe-1
for any j 21, .... d. (vi) holds due to min, 2 p for any E [1, ....d d.
18

---

Then, pay attention to Ts
Qr-1
T3 LE
m
b
T. E
2
Σ
Ct-1
ar
m
1|
(1 8)²
b--1
b
69 G.
E
a--1
ae
(1-
b
be
(1)) 18 E
a
a1
a
a
01-
max
(be-1)s
{be);
b
(6) LG
a1-1
(36)
p11 11--93 9)²
E
max
(b- 1)s
LG A(1 B)2 E
by
(2)) ooo*G LG"
p(1 3/2 E
(v1) I.G E 00
A1 B)² (vi))
(² 8)2
where (i) holds due to ||a @ bll I ||a|||b|l. (ti) holds owing | I G. (ti) holds due |all < maxy (a),llla|I (iv) holds due 1h--1 (be) 2 and _h for any j E 21, d), (v) holds resulting from min,(b:); 2 > 0 for any j and ov is non-increasing, (vi) holds resulting from (u-10 (be) for any j E [1, 2,.., d]. (wi) holds due to telescoping sum, and (wiii holds due to minn((b).. 2 p > for any [1, 2.... dJ..
(6,)
a--1
Now turn attention T4.
L
T4 = LE
a a 8
=1
( aa)ei_)
b
(37)
G² L
dl
+
2dL
(a--1 -a))3
2
where the inequality holds owing to ||m--/| < G and min, 2 0. (166-1)))) s 2. and Bl[le.]l") < d.
Combining Eq. 31 37 we can obtain
B[f()r) - f(2)) <
ag
G² +
(832 + 103 +5
G²
Σ
T
(1
3)p
(1-9)²
2p²
1 E
Σ ar
ar(|Vf((z))11
40aad
a LC
(38)
p² 3)²
r, 0²
T Σ
dl
+
+ 2dl,
ot
(at-1 aa)
2
[=1
[=1
19

---

Reformulating Eq. 38
we then have
B
a
{(=))l
-B([(a)) - [(xr)
(882 + +108+
G2 L)
+
+ 2dL
Σ a
(1-
2p²
(39)
dL
T
(a =i)²
2
1=1
4G and a03 LG'd
+ (1 B)p
G²
p² B)²
It is known the learning rate saftifies az = v v1 2 and an = o1 = =c Utilizing non-increasing
Ore and Sauchy-Schward incquality, know
E ail [V+))))
> TorB | E [V((x)))]]
TT د [V Σt Ob 2im & s (1 - ,dt) s e1 + log T), and
Σ (a.-1-a.)² (a-1-----
DT কলা S (1+ = शरंं = 3
we further have
T
Ci V
C2(1+ log
E
[
(40)
T
VT
t=1
where we define
dd
BedC²
4cdG²
C cG [B(f(z)) +f+++
+ p² -111889 3y2
(41)
16
(1
B)p
P
(882 +088+
G² L)
C2 = ed
02=00
+ 2dL
(42)
B)-
2p²
B Experiments for Comparing Vanilla SGD, SGDM, Adam, Birder and SoftSignSGD
To address the bottleneck in communication during distributed training, numerous gradient compression al- gorithms have been proposed, aiming reduce the communication volume. Most of these algorithms can be reduced to Vanilla SGD without momentum if compression is not performed. Generally speaking. the epoch-wise wise convergence rate and inference performance a compressed algorithms is upper bounded by its uncompressed counterpart. In the experiments. inference performance of of Vanilla SGD, SGDM, Adam, Birder and its uncompressed version in training typical CNN-base, LSTM-base and Transformer- base DNNs.
conducted empirical experiments evaluate the training and
Algorithm 1. SoftSignSGD
1: Input: model parameter zo, the momentum my = 0, b = 0, the exponential moving average factor 8, the learning rate sequence {ar}
(3)
2: for = 1,..., do
3: Randomly sample & and compute the gradient: g. (x
4: Update the momentum my: my = 3m + -1 3)g
5: Update the momentum by: b, Bb:-1 (1 - [g
6: Update the model parameter 2: #1-11 = 2F ck mi
by
end for
We refer to the uncompressed Birder as SoftSignSGD, The implementation details for SoftSignSGD are presented in Algorithm When comparing SoftSignSGD to Adam, there two key differences. First, instead using the square root of the exponential moving average of the squared gradient, denoted as / =
B2 f SoftSignSGD utilizes the exponential moving average the absolute gradient, represented as b, = (1 - 3)b, + Ig. Second, in SoftSignSGD, the exponential moving factors for both the numerator m: and the denominator b, are the same. These differences ensure that each element of the updating amount in SoftSignSGD satisfies the condition -
v(1 32)0;,) 1 +
(b) S L.
20

---

B.1 Experimental Results for training ResNet-20
We evaluated the performance of five optimization algorithms: Vanilla SGD, SGDM, AdamW, Birder and SoftSignSGD, for training ResNet-22 CIFAR100. Each batch consisted of of 128 examples sampled SGDM, we set momentum parameter
0.9, while for SoftSignSGD and Birder, was set to 0.95. For AdamW, the parameters 31 and B2 were set to 0.9 and 0.999, respectively. The weight decay was uniformly set to 0.0005 for Vanilla SGD and SGDM, and 0.05 for AdamW, Birder and SoftSignSGD. initialized the learning rates 0.1 for Vanilla
with replacement.
To simplify the tuning process and ensure fair comparisons, SGD and SGDM, and 0.005 for AdamW, Birder and SoftSignSGD. We divided the learning by 10 after 75 and 130 epochs, and terminated the training after 150 epochs.
Figure visually demonstrates that Vanilla SGD exhibits slower convergence speed and lower test accuracy compared to SGDM. In contrast, both Birder and SoftSignSGD show comparable training and inference performance to the commonly used SGDM and AdamW. This observation suggests that Birder outperforms existing gradient compression algorithms when training CNN-based ResNet-20 models.
Vanilla SGD
4-
SGDM
AdamW
SoftSignSGD
Birder
Test Accuracy
Train
Vanilla 5GD
SGDM
1
AdamW
SoftSignSGD
Birder
30
90
120
150
60
120
Epoch
Epoch
(a) Train Loss
(b) Test Accuracy
Figure 5: Training loss and test accuracy for ResNet-20 on CIFAR100.
B.2 Experimental Results for training LSTM
We conducted experiments to train 3-layer LSTM model the Penn TreeBank datasct to evaluate the performance of five optimization algorithms: Vanilla SGD. SGDM, AdamW. Birder and SoftSignSGD. default
Our implementations were built upon the code provided in the AdaBelief paper" and we used experimental seltings for SGDM and AdamW. For Vanilla SGD, we used the experimental settings of SGDM with the exception that we set the momentum parameter 3 to O. For Birder and SoftSignSGD, we adopted the experimental settings of AdamW, except that set the momentum parameter to 0.99.
As visually illustrated in Figure 6 Vanilla SGD is still less effective than SGDM in terms of the convergence speed and the test accuracy, while the training and inference performance of SoftSignSGD and Birder comparative to common-used SGDM and AdamW. indicates the Birder superior to exiting gradient compression algorithms for training LSTM.
B.3 Experimental Results for training VIT
We train VIT-B with Vanilla SGD, SGDM, AdamW. SoftSignSGD and Birder the ILSVRC2012 with 32 GPUs (4 nodes). We use the Pytorch official implementation for ViT For AdamW, SoftSignSGD Birder, we followed the recommended experimental settings, with the exception that we set the momentum parameter to 0.95 for SoftSignSGD and Birder. As for Vanilla SGD and SGDM. we set the basic learning rate to 0.1 and the weight decay 0.001, while keeping other settings the same AdamW. Instead of the default 300 epochs, we uniformly the total number of epochs 150 for all optimizers
As visually illustrated in Figure 7 Vanilla SGD is still less effective than SGDM in of the convergence speed and the test accuracy, while the training and inference performance SoftSignSGD and Birder are comparative to common-used SGDM and AdamW. Notably, the performance of SGD-type optimizers are substantially inferior to that of adaptive optimizers.
21

---

150
Vanilla 5GD
Vanilla SGD
SGDM
SGDM
AdamW
AdammW
SoftSignSGD Birder
SoftsignSGD
Perplexity
Birder
Train
100
4-
3
50
50
100
150
200
50
100
150
200
Epoch
Epoch
Train Loss
(b) Test Perplexity
Figure 6: Training loss and test perplexity (the lower, the better) for 3-layer LSTM on Penn TreeBank.
Vanilla
AdamW
SoftSignSGD
Birder
Accuracy
Train
40
Vanilla SGD
SGDM
AdamW
SoftSign5GD
Birder
120
150
120
Epoch
Epoch
(a) Train Loss
(b) Test Accuracy
Figure 7: Training loss and test accuracy for ViT-B-16 on ILSVRC2012.
C Experimental Results for pre-training BERT-Base
We employed BertAdam and Birder to pre-train BERT-Base Wikipedia using 64 GPUs (8 nodes). The sequence length 37, 000 iterations. The learning rate started 4 x 10 and linearly increased after which it linearly decreased to 0 for the remaining iterations. ForBertAdam, the parameter values [3, 8a] were set to [0.9, 0.999], and for Birder, the momentum parameter beta was set to 0.9.
512, and the batch size per GPU was set 16. The training process consisted of 12, 500 iterations,
As depicted in Figure Birder demonstrates comparable iteration-wise convergence rate to BertAdam. However, in terms of time-wise convergence, Birder achieves 4.2x faster convergence rate compared to BertAdam.
D Experiments with InfiniBand connections
To further evaluate the communication efficiency of SGDM/Adam, SoftSignSGD and Birder with high bandwidth connections, 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 Table
As shown in Table 3 and Table 4 compared with the baseline SGDM/Adam, Birder can still reach up to 1.45x speedup for ResNet-50 50 on ILSVRC2012 and 2.85x speedup for BERT-Base on SQuAD 1.1. although the speed advantage is not obvious that with lower- wwwr-bandwidth Ethernet connections. An interesting phenomenon
22

---

BertAcam dler
BertAcam
SK
15K
205
25R
30k
35K
10
20
Wall (hour)
(a) Iteration-wise, BERT-Base, batch size=16 16 x 64
(b) Time-wise, BERT-Base, batch size=16 x 64
Figure 8: Iteration- wise and time-wise convergence speed for pre-training BERT-Base with 16 samples per
GPU with 64 GPUs.
Table 3: System throughput (samples/s) SGDM. 1-bit Adam and Birder training ResNet-50 on ILSVRC2012 with 10Gbps Ethernet and 200Gips InfiniBand.
Ethernet (10Gbps)
InfiniBand (200Gipss)
#GPUs
Optimizer
Throughput (samples/s)
Speedup
Scale Efficiency
Throughput
Speedup
Scale
(samples/s)
Efficiency
SGDM
3693
1.00x
100%
3693
1.00
100%
8
1-bit Adam
3243
0.83x
100%
3243
0.83x
100%
Birder
3462
0.94x
100%
3462
0.94x
100%
SGDM
2959
1.00x
40.1%
4673
1.00
63.2%
16
1-bit Adam
4715
1.60x
72.7%
5708
1.22x
88.0%
Birder
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%
Birder
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.89
21.3%
16920
1.02x
65.2%
Birder
15253
2.47x
55.1%
19956
1.21x
72.1%
Table 4: System throughput (samples/s) of BertAdam, 1-bit Adam and Birder 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
BertAdam 1-bit Adam
413
1.00x
100%
413
1.00x
100%
8
358
0.87
100%
358
0.83x
100%
Birder
412
1.00x
100%
412
0.94x
100%
BertAdam
84
1.00x
10.1%
272
1.00x
32.9%
16
1-bit Adam
213
2.54x
29.7%
522
1.92x
72.9%
Birder
431
5.13x
52.3%
776
2,85x
94.1%
BertAdam
119
1.00x
7.20%
543
1.00x
32.8%
32
1-bit Adam
274
2.30x
19.1%
903
1.66x
63.1%
Birder
730
6.13x
44.2%
1365
2.51x
82.9%
BertAdam
158
1.00x
4.78%
998
1.00x
30.2%
32
1-bit Adam
252
1.59
8.80%
1496
1.50x
52.2%
Birder
990
6.26x
30.0%
2299
2.30x
69.8%
the system throughput of Birder with 10Gbps Ethernet can match that of SGDM/Adam with 200Gbps InfiniBand.
The experimental results in Table 3 and Table 4 also show that as the number GPUs is increasing, the scale efficiency of SGDM/dda, SoftSignSGD and Birder 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
23

---

multiplies. We take the communication scheme All-Reduce for example. If the number of GPUs is each GPU requires 2(n trips across the network confections. When the number is non-trivial, the computation time of the communication primitives may exceed time 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-All- Reduce. Hence, shown in in Table and SGDM/Adam with the number of GPUs growing.
and Table the scale efficiency of Birder decreases more quickly than
E
Discussion
The original paper 1-bit Adam reports significant speed advantage (up to 3.8x) ) for 1 1-bit Adam compared to full-pr full-precision Adam, with the advantage becoming more prominent the number GPUs increases. However, our experiments, we did not observe clear speed advantages for 1-bit Adam over the original Adam. In fact, when running on 64 GPUs, 1-bit Adam was not only slower than the original Adam, but its throughput rate was even lower than that on 32 GPUs. There are several reasons for this phenomenon. First, the speedup of 1-bit Adam is obtained by comparing the throughput of the compression phase with that of the warm-up phase. However, in our experiments, we evaluated the overall average throughput of both the warm-up phase and the compression phase for 1 1-bit Adam. Second, the baseline Adam did not run with system-leve efficient DDP. Third, the authors of 1-bit Adam customized highly efficient communication primitives specifically for their optimizer, whereas utilized off-the-shelf communication primitives in Py PyTorch for all the optimizers to ensure fairness.
As shown in Figure as the number of GPUs increases, the communication time for Birder also grows superlinearly. One of the reasons for this is that the communication primitive All-to-All accounts for an increasing portion of the communication time. However, the native All-to-All in Step (iii) of the Hierarchical- Set-All-Reduce is not less efficient than the native All-Reduce. Therefore, we plan to further optimize the All-to-All and All-Gal All-Gather primitives accelerate Birder.
When training large-scale DNNs, the mixed-precision technique is commonly used to reduce memory con- sumption, allowing for larger model sizes. While optimizers still utilize full full-precision states and computations, which typically contribute to 33-75% of the total memory footprint, Birder does not require full-precision states or computations. Moreover, due to the random quantization of updates to 1 or -1, Birder can leverage lower precision than FP16 gradients to estimate the update. Therefore, Birder shows promise for applications that focus reducing memory usage, as highlighted in recent research 8-bit optimizers via block-wise quantization (Tim Detmmers et al., ICLR 2022).
24


Reviews:
[{"review_id": "MzgBTX2lEt", "reviewer": "Reviewer_sXik", "summary": "The paper proposes BRAM, a new 1-bit optimizer that directly quantizes the entire adaptive update. It theoretically proves that BRAM promises the same convergence speed as the full-precision Adam even with extreme 1-bit quantization. Considering the difference between intra-node and inter-node bandwidth, the paper also proposes Hierarchical-1-bit-All-Reduce,  a hierarchical communication scheme that aggregates our 1-bit data by leveraging the ultra-high intra-node bandwidth. The experiments show that BRAM can achieve empirical high performance on top of Hierarchical-1-bit-All-Reduce.", "questions": "Can BRAM be applied to pipeline parallel distributed training of foundation models?", "limitations": "The authors do not mention the limitations of their work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The presentation is good. The writing is clear and easy to follow.\n2. The paper makes a detailed evaluation and analysis of 1 Adam.\n3. The appendix proves that the element-wise quantization function is unbiased.", "weaknesses": "1. It is unclear whether using the same hyperparameters for both the exponential moving averages of gradients and the squared gradients would have negative effects.\n2. BRAM has less room for further optimization and can only be employed in very few applications because it sends updates directly back.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our sincere gratitude for your volunteering time and your valuable comments. In response to your feedback, we have organized our response into the following points:\n\n**Q1.**  *It is unclear whether using the same hyperparameters for both the exponential moving averages of gradients and the squared gradients would have negative effects.*\n\n**R1.** Thank you for bringing this matter to our attention.  Drawing from both our theoretical analysis and empirical findings,  it becomes evident that sharing the same moving average factor $\\beta$ for $m_t$ and $b_t$  for BRAM can still guarantee the same theoretical convergence rate as Adam with different moving average factors, and the experiments also demonstrate it achieves s a similar training speed and comparable, or even superior, inference performance when compared to Adam. In summary, sharing the moving average factor $\\beta$ for $m_t$ and $b_t$  for BRAM does not lead to negative effects. Instead, it bestows  tangible advantages,  eliminating the necessity for bias correction and significantly reducing the amount of required tuning work.\n\n**Q2.** *BRAM has less room for further optimization and can only be employed in very few applications because it sends updates directly back.*\n\n**R2.** Thank you for your valuable feedback. It appears you might have inferred a constraint on the application of BRAM due to the difficult implementation of the entire update rather than the gradient. However, I would like to clarify that this implementation is actually straightforward through a communication hook in DDP of PyTorch. Further details, including code examples, can be found in the uploaded zip file. As highlighted in our paper, we have extensively applied BRAM to train a wide range of neural networks, encompassing various architectures such as convolutional-based, LSTM-based, and Transformer-based models. These applications cover diverse computer vision (CV) and natural language processing (NLP) tasks, including normal training, retraining, and fine-tuning. Through these practical examples, we have demonstrated BRAM's user-friendly nature and its versatility.\n\n**Q3.** *Can BRAM be applied to pipeline parallel distributed training of foundation models?*\n\n**R3.** The latest influential work ZeRO++ [1] (it posted on arXive subsequent to our NeuRIPS submission ) incorporated a similar method (gqz) to Hierarchical-1-bit-All-Reduce of BRAM,  employing it to reduce the communication overhead across inter-nodes during the training of giant foundational models. This implementation exemplifies the expansive potential of BRAM for foundational model training. As we emphasized in the paper,  BRAM is applicable to data parallel for distributed training, which is orthogonal to pipeline parallel.\n\n[1] G. Wang, et al. \"ZeRO++: Extremely Efficient Collective Communication for Giant Model Training.\" arXiv:2306.10209, 2023.\n"}, {"review_id": "eJyh0Sx3so", "reviewer": "Reviewer_gDkh", "summary": "The paper introduces a 1-bit adaptive optimizer called BRAM for distributed training of deep neural network models. BRAM combines the merits of SignSGD and Adam optimizers to achieve fast convergence speed, high inference performance, and reduced communication overhead. The proposed optimizer employs extreme 1-bit quantization for communication data while being lightweight in terms of computation. A hierarchical communication scheme called Hierarchical-1-bit-All-Reduce is also introduced to enhance communication efficiency. Extensive experiments on benchmark models, including ResNet-50 and BERT-Base, validate the effectiveness and efficiency of BRAM compared to uncompressed methods like SGDM/Adam and the 1-bit Adam optimizer. The experimental results demonstrate that BRAM achieves similar convergence rates to the baseline methods while significantly outperforming them in terms of training speed and system throughput, especially with a larger number of GPUs. Inference performance results show that BRAM performs comparably or even better than the baseline methods. Overall, BRAM offers a promising solution for distributed training with improved communication efficiency and convergence speed.", "questions": "Please see the weaknesses.", "limitations": "There is no limitation discussion.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper introduces BRAM, a 1-bit adaptive optimizer that combines the strengths of SignSGD and Adam. This optimizer effectively reduces communication overhead while maintaining fast convergence speed and high inference performance.\n\n- The paper provides a theoretical convergence analysis for BRAM under certain assumptions. The analysis demonstrates that BRAM achieves a convergence rate comparable to uncompressed Adam, providing a solid theoretical foundation for its effectiveness.\n\n- It proposes a hierarchical communication scheme called Hierarchical-1-bit-All-Reduce specifically designed for BRAM. This scheme leverages high intra-node bandwidth and reduces inter-node communication overhead, resulting in better scalability efficiency and improved system throughput.\n\n- Extensive experimental validation: The paper conducts extensive experiments on benchmark models, including ResNet-50 and BERT-Base, LSTM, ViT etc., using different numbers of GPUs. The experimental results demonstrate the superiority of BRAM over uncompressed methods like SGDM/Adam and the 1-bit Adam optimizer in terms of training speed and system throughput, while maintaining comparable or even better inference performance.", "weaknesses": "- The theoretical convergence analysis of BRAM relies on several assumptions, such as bounded infimum, Lipschitz continuous gradient, and unbiased and independent noisy gradients. The sensitivity of BRAM's performance to these assumptions should be discussed to provide a more realistic assessment of its convergence properties.\n\n- The paper briefly mentions the selection of hyperparameters such as the learning rate and exponential moving average factor, but there is limited discussion on the sensitivity of BRAM to these hyperparameters. A more thorough analysis and discussion of hyperparameter tuning would provide insights into achieving optimal performance. The paper does not include ablation studies to analyze the individual contributions of different components of BRAM. Investigating the impact of each component and analyzing their relative importance would enhance the understanding of the optimizer and provide insights for further improvements.\n\n- Limited analysis of robustness to noisy gradients: The paper does not extensively discuss the robustness of BRAM to noisy gradients. While the theoretical analysis assumes unbiased and independent noisy gradients, a more in-depth investigation of BRAM's performance in the presence of varying levels of gradient noise would provide a comprehensive understanding of its behavior in practical scenarios.\n\n- Although the paper mentions the reduced compression/decompression time of BRAM compared to 1-bit Adam, a more detailed analysis and comparison of the time required for compression and decompression would provide a better understanding of the overhead introduced by the quantization process.\n\n- The paper focuses on communication efficiency but does not thoroughly discuss the memory efficiency of BRAM. Analyzing the memory requirements of BRAM compared to other optimizers would be valuable, especially in scenarios with limited memory resources.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our sincere gratitude for your volunteering time and your valuable comments. In response to your feedback, we have organized our response into the following points:\n\n**Q1.**  *The theoretical convergence analysis of BRAM relies on several assumptions, such as bounded infimum, Lipschitz continuous gradient, and unbiased and independent noisy gradients. The sensitivity of BRAM's performance to these assumptions should be discussed to provide a more realistic assessment of its convergence properties.*\n\n**R1.**  We greatly appreciate your efforts in highlighting this significant matter.  These assumptions  also serve as foundations for analyzing the theoretical convergence of prior adaptive optimizers, and they are common met during DNN training. Moreover,  they also serve as foundations for analyzing the theoretical convergence of prior adaptive optimizers. The theoretical impact of these assumptions on convergence is detailed in Equation (6) of Theorem 1. However, when considering their practical implications during real-world training, we acknowledge the inherent challenge of assessment, a aspect that also has not been addressed in prior research.\n\n**Q2.** *The paper briefly mentions the selection of hyperparameters such as the learning rate and exponential moving average factor, but there is limited discussion on the sensitivity of BRAM to these hyperparameters. A more thorough analysis and discussion of hyperparameter tuning would provide insights into achieving optimal performance. The paper does not include ablation studies to analyze the individual contributions of different components of BRAM. Investigating the impact of each component and analyzing their relative importance would enhance the understanding of the optimizer and provide insights for further improvements.*\n\n**R2.** Thank you for your valuable suggestion. Given the extensive number of experiments that needed to be carried out, we faced limitations in terms of the availability of numerous valuable GPUs (Nvidia A100-80G), over extended periods. Consequently, we opted not to employ grid search for hyperparameter selection. Instead, the hyperparameter values in BRAM followed the recommended value for Adam in official source codes or the paper on 1-bit Adam. Noting that the only exception is the value of $\\beta$ in BRAM, fixed at $0.95$. Regarding the ablation experiments, we have conducted a comparison between BRAM and its uncompressed counterpart (SoftSignSGD). We appreciate your suggestion, and we intend to incorporate additional experiments to assess the sensitivity of these hyperparameters and gauge finer individual contributions, if numerous GPU resources become available in the future.\n\n**Q3.** *Limited analysis of robustness to noisy gradients: The paper does not extensively discuss the robustness of BRAM to noisy gradients. While the theoretical analysis assumes unbiased and independent noisy gradients, a more in-depth investigation of BRAM's performance in the presence of varying levels of gradient noise would provide a comprehensive understanding of its behavior in practical scenarios*\n\n**R3.** We appreciate your guidance on this matter.we have employed BRAM to train a diverse array of neural networks, including convolutional-based, LSTM-based, and Transformer-based models on various datasets with varying batch sizes. This methodology has provided an avenue for indirectly assessing the impact of varying levels of gradient noise. Thank your for this reminder, and we will add the direct robustness analysis to noisy gradient in the revised version.\n\n**Q4.** *Although the paper mentions the reduced compression/decompression time of BRAM compared to 1-bit Adam, a more detailed analysis and comparison of the time required for compression and decompression would provide a better understanding of the overhead introduced by the quantization process.*\n\n**R4.**  In fact, as depicted in Figure 4, we have included a comparison of the time required for compression/decompression of SGDM/Adam, 1-bit Adam, and BRAM,  and a comprehensive analysis of this aspect can be found in detail within Subsection 5.3.\n\n**Q5.** *The paper focuses on communication efficiency but does not thoroughly discuss the memory efficiency of BRAM. Analyzing the memory requirements of BRAM compared to other optimizers would be valuable, especially in scenarios with limited memory resources.*\n\n**R5.** The primary objective of this paper is to address the communication bottleneck issue in distributed training. As such, we have delved into a comprehensive analysis of communication efficiency within the main text. It's worth noting that we also touch upon memory efficiency in Section E of the Appendix. Owing to the presence of the error feedback state, BRAM exhibits less memory efficiency than Adam. However, as elaborated upon in Section E of the Appendix, the similarity in orders of magnitude between $m_t$ and $b_t$, coupled with the bounded range of $e_t$ within [-1, 1], enables BRAM to harness lower precision, such as FP16 or even FP8, to store the states $m_t$, $b_t$, and $e_t$, diverging from the FP32 state used in Adam. This, in turn, allows for the utilization of low-precision gradients to estimate updates. Consequently, BRAM presents a more memory-efficient potential than Adam. We are committed to further exploring and advancing this area in our future endeavors.\n\n\n\n\n\n\n\n\n"}, {"review_id": "NOkQUdUlVt", "reviewer": "Reviewer_5r9C", "summary": "This paper proposes a compute-efficient gradient compressor named BRAM which randomly quantifies the update direction into 1-bit for communication. A theoretical convergence bound is also provided to prove BRAM’s convergence property. To improve communication efficiency, BRAM also integrates a novel Hierarchical-1-bit-All-Reduce algorithm that can better utilize high-bandwidth intra-node communication. Experiments conducted on two popular DNNs (ResNet-50 with ImageNet and BERT-Base with SQuAD1.1) show BRAM seems to outperform SGDm, Adam, and 1-bit Adam.", "questions": "1. Experiments seem not to be conducted fairly. 1) The ResNet-50 model was not trained with standard accuracy (i.e., 75.9% top-1 accuracy according to MLPerf and many other benchmarks). For example, in Table 1, top-1 accuracy drops to 74.+% on 64 GPUs with 128 samples per GPU (i.e., a global batch size of 8K), but many studies show ResNet-50 on ImageNet can be scaled to a mini-batch size of 32K to reserve 75.9% top-1 accuracy. 2) The testbed has a very high intra-node bandwidth but relatively low inter-node bandwidth, thus the *Hierarchical-1-bit-All-Reduce* algorithm is important. However, the experimental setting seems deliberately constructed to show the effectiveness of BRAM according to Table 1 where only 128 samples were used for each Nvidia A100 GPU such that the computation-to-communication ratio is low. To fairly compare with SGDM, the local batch size is possible to be 512 or 1024 on an Nvidia A100-80G GPU. It is similar to the BERT-Base experiments, where the local mini-batch size is only 3. Is it out of memory if setting a larger mini-batch size?\n\n2. The paper claims that BRAM doesn’t need a warmup strategy to align the accuracy to the dense version, but the benchmarks don’t have standard accuracy. Is it possible that 1-bit Adam, MSTop-k (with HiTopKComm), and PowerSGD also achieve similar accuracy achieved by BRAM even if they train DNNs without warmup? How about comparing MSTop-k and PowerSGD in terms of end-to-end training time to achieve target accuracy?\n\n3. It seems that the convergence analysis in Section 3 is based on the theoretical framework from [8]. Is the theoretical convergence analysis providing new insights in this paper compared with [8]?\n\n4. The *1-bit-All-Reduce* algorithm converts all-reduce to all-to-all, how about the communication complexity of *Hierarchical-1-bit-All-Reduce* compared to state-of-the-art all-reduce algorithms (e.g., ring-based, tree-based, etc.)? A communication complexity comparison is suggested to be provided to help understand the advantage of  Hierarchical-1-bit-All-Reduce.\n\n5. The key idea of the *Hierarchical-1-bit-All-Reduce algorithm* is almost the same with HiTopKComm in [23] though they are used under different scenarios. Should credit be given to [23]? and what are their main differences?", "limitations": "See above.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. A compute-efficient lightweight compressor on model updates (not gradients) is proposed to reduce communication volume in distributed data-parallel training.\n2. A novel *Hierarchical-1-bit-All-Reduce* algorithm is proposed to better utilize the high-bandwidth intra-node communication and alleviate the communication through low-bandwidth inter-node interconnect.", "weaknesses": "1. Experiments are not strong to support the claims of the paper. \n2. Some state-of-the-art compressed methods like HiTopKComm (with MSTop-k) and PowerSGD were not compared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our sincere gratitude for your volunteering time and your valuable comments.  We organize our response into the following points:\n\n**Q1.**  *The top-1 accuracy drops to 74.+\\% with globe batch size of 8k for training ResNet-50, while methods in MLPerf can reserve 75.9\\% with batch size of 32k.*\n\n**R1.**  In response to your observation, we carefully examined the source codes of the top-20 methods on MLPerf. Our investigation revealed  that all these methods select the specifically designed LARS for large batch-size training.  In fact, a decline in test accuracy with larger batch sizes is a well-established phenomenon, as demonstrated in the paper on LARS [1].  Thank you for your reminder,   we will incorporate the LARS technique into BRAM in our upcoming research.\n\n**Q2.** *128 samples per GPU were used to train ResNet-50, and 3 samples per GPU were used to finetune BERT.*\n\n**R2.** Thank you for sharing your acute observation.  The decision regarding the number of samples per GPU  followed closely-related prior papers and  source code tutorials. [2-4] train ResNet on IMAGENET with 64, 128 and 256 samples per GPU respectively to show the efficiency of communicaiton-compression optimizers, and the HuggingFace tutorial (https://huggingface.co/bert-base-uncased) and the paper [3] pretrain BERT on  English Wikipedia with 16 samples per GPU and finetune BERT on SQuAD with 3 samples per GPU. In alignment with these established practices, we  chose  a sample count of 128 per GPU for training ResNet-50, and 16/3 samples for the pretraining/finetuning BERT.\n\n**Q3.** *Comparison to MSTop-k and PowerSGD in terms of end-to-end training time.*\n\n**R3.**   It seems there might be some misunderstandings. In the section of Introduction, our intention was to emphasize that some rather than all existing communication-compression optimizers require warmup.\n\n Both in the Section 1 and Section 5, we've highlighted the findings from recent works [2][5]  that  PowerSGD and MSTop-k  are an overall slower than SGDM/Adam,  when employed with  DDP.  Specifically, PowerSGD incurs heavy compression/decompression computation costs that outweigh the communication reduction gains, while MSTop-k, when coupled with HiTopKComm, encounters incompatibility with All-Reduce and resorts to AllGather, which significantly escalates the communication complexity.  Therefore, considering that our paper focuses on communication efficiency and we have compared BRAM with uncompressed SGDM/Adam, we thought a direct comparison with PowerSGD and MSTop-k might not be necessary.\n\n**Q4.** Is the theoretical convergence analysis providing new insights compared with Ref (8)?\n\n**R4.** We agree with you that the convergence analysis is inspired by Ref (8).However,  the theoretical analysis for BRAM encompasses more intricate elements, including  local/global quantization  and error feedback, along with the fixed and uniform $\\beta$ for $m_t$ and $b_t$. Consequently, these factors render the theoretical investigation  more complicated than that in Ref (8).  Notably,  the theorectical convergence analyses of numerous recent works, such as ZO-AdaMM [6], AdaBelief [7], and FedAMS[8], were also motivated by Ref (8). However, this does not affect the theoretical significance or contributions of these individual studies.\n\n**Q5.** *The main differences and the communication complexity comparison between Hierarchical-1-bit-All-Reduce and HiTopKComm.*\n\n**R5.** The notion of hierarchicy in Hierarchical-1-bit-All-Reduce are from HiTopKComm, but we respectfully disagree with you that  Hierarchical-1-bit-All-Reduce is almost the same with HiTopKComm.  We originally propose 1-bit-All-Reduce to communication data cross inter-nodes with the bottleneck bandwidth.  In contrast, HiTopKComm relies on existing All-Gather in a more straightforward manner. Specifically,  1-bit-All-Reduce combines sequential processes, including All-to-All, local averaging and re-quantization, and All-Gather. As detailedly analyzed in Section 3, when considering $n$ nodes and an communication volume of $P$ per GPU, the communication complexity of both All-to-All and All-Gather within 1-bit-All-Reduce is $\\frac{(n-1)P}{n}$, equivalent to the ideal 1-bit All-Reduce without overflow. In contrast, the complexity of \\emph{All-Gather} in HiTopKComm is $(n-1)P$. This distinction demonstrates the significantly higher communication efficiency of Hierarchical-1-bit-All-Reduce ove HiTopKComm.\n\nIn summation, the notion of hierarchy may appear intuitive and straightforward, with 1-bit-All-Reduce playing a pivotal role. This is evidenced by the recent influential work ZeRO++ [9], which adopts a scheme, called qgZ, nearly identical toHierarchical-1-bit-All-Reduce for large language model training.  ZeRO++ does not cite the paper on HiTopKComm, and its alignment with Hierarchical-1-bit-All-Reduce effectively varifies the efficacy and broader applicability of our approach.\n\n\n[1] Y. You, et al. \"Large batch training of convolutional networks.\" arXiv:1708.03888, 2017.\n\n[2] S. Agarwal , et al. \"On the utility of gradient compression in distributed training systems.\" MLSys, 2022.\n\n[3] T., Hanlin, et al. \"1-bit Adam: Communication efficient large-scale training with Adam’s convergence speed.\" ICML, 2021.\n\n[4] S. Shi et al. \"Towards scalable distributed training of deep learning on public cloud clusters.\" MLSys, 2021.\n\n[5] X. Hang, et al. \"Compressed communication for distributed deep learning: Survey and quantitative evaluation.\" 2020.\n\n[6] X. Chen, et al. \"Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization.\" NeurIPS, 2019.\n\n[7] J. Zhuang, et al. \"Adabelief optimizer: Adapting stepsizes by the belief in observed gradients.\" NeurIPS, 2020.\n\n[8] Y.Wang. et al.\"Communication-efficient adaptive federated learning.\" ICML, 2022.\n\n[9] G. Wang, et al. \"ZeRO++: Extremely Efficient Collective Communication for Giant Model Training.\" arXiv:2306.10209, 2023.\n\n\n"}, {"review_id": "aMn2xsWKZl", "reviewer": "Reviewer_jDqW", "summary": "The authors propose a novel 1-bit adaptive optimizer by compressing the total update in each iteration. Besides, the author modifies the adam update with the absolute value of the gradient. No bias correction is needed and error feedback is applied in algorithm 1. Hierarchical-1-bit-All-Reduce is proposed, where intra-node communication is full precision, while inter-node communication is compressed. Experiments verifies that the proposed method achieves faster convergence and the model performance is roughly the same.", "questions": "- m and b are not synchronized across workers. how do you make sure that the workers do not diverge because of different b?\n- have you tried signsgd instead of Eq(5)? Error feedback could work better for biased compressor.\n- how do you get rid of batch size in convergence results, which is considered as a theoretical difficulty in Adam?", "limitations": "The authors did no discuss societal impact. I don't see potential negative societal impact neither.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- experiments show wall-clock time acceleration under different local batch size settings. Typically, when local batch size is larger, the computation to communication ratio is higher, and communication compression will lead to lower speedup compared with full-precision training.\n- Hierarchical-1-bit-All-Reduce is proposed and sounds reasonable, since the intra-node communication could have a higher bandwidth.\n- the wall-clock training time comparison explicitly show the faster convergence speed of the proposed method.", "weaknesses": "- all-gather instead of all-reduced is used in figure 1\n- noticeable performance drop could be observed from Table 1\n- gradient norm needs to be bounded in assumption 4\n- the theoretical analysis is rather short and lacks insight.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our sincere gratitude for your volunteering time and your valuable comments. In response to your feedback, we have organized our response into the following points:\n\n**Q1.**  *All-gather instead of All-Reduce is used in figure 1*\n\n**R1.** Thank you for raising this concern.  We hold a respectful difference of opinion that Hierarchical-1-bit-All-Reduce just simply substitutes All-Reduce with All-gather.  In fact, two key innovations define Hierarchical-1-bit-All-Reduce. First, it hierarchically harnesses the ultra-fast intra-node bandwidth to boost local communication efficiency. Second, it originally introduces 1-bit-All-Reduce to further reduce communication overhead across inter-nodes.\n\nWhile the traditional All-Reduce comprises Reduce-Scatter and All-Gather.  We recognize the limitations of Reduce-Scatter in the context of 1-bit communication due to potential overflow.  Consequently, as elaborated in Section 3 and visually displayed in Figure 1, our work has ingeniously proposed the concept of 1-bit-All-Reduce. This innovative approach substitutes Reduce-Scatter with a combination of 1-bit All-to-All , local average and re-quantization and All-Gather. Assuming we have $n$ nodes, and  the overall volume for each GPU needs to be communicated is $P$, the communication complexity of All-to-All and All-Gather in 1-bit-All-Reduce is $\\frac{(n-1)P}{n}$, which equals to that of the ideal 1-bit ring-based All-Reduce without overflow. In contrast, the complexity of simply subsituting All-Redeuc with All-Gather is $(n-1)P$. \n\n**Q2.** *Noticeable performance drop could be observed from Table 1*\n\n**R2.** We appreciate your attention to detail. We followed the PyTorch official source codes  for training ResNet-50 using SGDM and BRAM. Noting that a decline in test accuracy with larger batch sizes is a well-established phenomenon, as demonstrated in prior research [1]. Our focus is on enhancing training efficiency, rather than chasing state-of-the-art performance with large batch sizes.\n\n**Q3.** *Gradient norm needs to be bounded in Assumption 4*\n\n**R3.**   Assumption 4 is commonly used to analyze the theoretical aspects of adaptive optimizers, *e.g.*, Adam and its variants [2-5]. Notably, Assumption 4 is typically met during the training of DNNs in practical scenarios.\n\n**Q4.** *The theoretical analysis is rather short and lacks insight*\n\n**R4.**  Our theoretical convergence analysis for BRAM spans approximately 9 pages, which we consider to be a substantial coverage. Notably, the length of the theoretical analysis may not necessarily correlate with its theoretical significance and depth of insight.\n\n**Q5.** *$m_t^{(i)}$ and $b_t^{(i)}$ are not synchronized across workers. How do you make sure that the workers do not diverge?*\n\n**R5.** We appreciate your attention to this matter. Despite the potential lack of synchronization for $m_t^{(i)}$ and $b_t^{(i)}$ among workers, it's important to note that the parameter $x_t$ achieves synchronization across all workers with each iteration. Furthermore, the independently and i.i.d. nature of the sampled data on each worker guarantees that $m_t^{(i)}$ and $b_t^{(i)}$ are inherently i.i.d., thus ensuring theoretical convergence. Notably,  Signum with majority vote (the momentum version of signSGD) [6] also doesn't necessitate synchronization for momentum across workers, and it theoretically proves that Signum with majority vote will be converged.\n\n**Q6.** *Have you tried signSGD instead of Eq(5)? Error feedback could work better for biased compressor.*\n\n**R6.** We did not explore the utilization of signSGD with error feedback (EF-signSGD) [7] as a replacement for Eq. (5). The main reason is that EF-signSGD, like signSGD,should  employs a majority vote mechanism to aggregate data across workers,  rendering it compatible solely with the less efficient All-Gather instead of All-Reduce.  Consequently, its applicability for practical large-scale distributed training  becomes limited, which has been validated in previous studies [8]. Moreover, EF-signSGD aligns more closely with SGD-type optimizers rather than Adam-type optimizers, making it inapplicable to train Transformer-based DNNs, as we discussed in Section 1. This is also experimentally validated in figure 1 presented in the \"globe response\" PDF file.\n\n**Q7.** *How do you get rid of batch size in convergence results, which is considered as a theoretical difficulty in Adam?*\n\n**R7.**  Thank you for taking our attention to this crucial problem that we were not aware of. Actually, we did not fully get rid of the mini-batch size $m$ in the convergence analysis. In Assumption 4, we assume   $\\Vert g_t^{(i)} \\Vert \\le G$. It is known that ${\\mathbb E} [\\Vert g_t^{(i)} \\Vert^2] = \\Vert {\\mathbb E} [g_t^{(i)} ]\\Vert ^2 + {\\mathbb E} [\\Vert g_t^{(i)} -  {\\mathbb E} [g_t^{(i)} ] \\Vert^2] = \\Vert {\\mathbb E} [g_t^{(i)} ]\\Vert ^2 + \\Vert {\\mathbb V} [g_t^{(i)} ]\\Vert ^2$. $\\Vert {\\mathbb E} [g_t^{(i)} ]\\Vert ^2$ is commonly small, and $\\Vert {\\mathbb V} [g_t^{(i)} ]\\Vert ^2$ is inverse proportion to the mini-batch size $m$. Thus,  $G$ is inherently interconnected with the mini-batch size $m$.\n\n\n[1] Y. You, et al. \"Large batch training of convolutional networks.\" arXiv:1708.03888, 2017.\n\n[2] Diederik P. Kingma, and. Ba. \"Adam: A method for stochastic optimization.\"  arXiv:1412.6980, 2014.\n\n[3] M.  Zaheer et al. \"Adaptive methods for nonconvex optimization.\" NeurIPS, 2018.\n\n[4] L. Luo , et al. \"Adaptive gradient methods with dynamic bound of learning rate. ICLR, 2019.\n\n[5] Y. You, et al. \"Large batch optimization for deep learning: Training bert in 76 minutes.\" ICLR, 2020.\n\n[6] J. Bernstein, et al. \"signSGD with majority vote is communication efficient and fault tolerant.\" ICLR, 2019.\n\n[7] SP Karimireddy, et al. \"Error feedback fixes signsgd and other gradient compression schemes.\" ICML, 2019.\n\n[8] S. Agarwal , et al. \"On the utility of gradient compression in distributed training systems.\" MLSys, 2022.\n\n\n\n"}, {"review_id": "iFZxQXtoO9", "reviewer": "Reviewer_yyED", "summary": "With the increasing size of the model, communication compression plays an important role in distributed machine learning because the model needs to transmit among the nodes. Toward this goal, this paper introduces a one-bit adaptive optimizer named BRAM and further extends the method to hierarchical all-reduce. Specifically, the method is lightly computed because it requires compression only, which significantly saves the time spent on the decompression step. Theoretical analysis shows the efficiency of the proposed algorithm, and the empirical studies validate the method is comparable with one-bit Adam and uncompressed SGDM.", "questions": "**Q1.** The introduction claims that the proposed algorithm performs similarly to uncompressed SGDM/Adam. However, the experiments compare the proposed work with one-bit Adam only. Is it over-claimed because we cannot see how close it is between the proposed work and uncompressed Adam? Can the authors provide the results for uncompressed Adam?", "limitations": "**L1.** The method designed for Hierarchical-1-bit All-Reduce cannot guarantee every transmission using 1 bit only. It will require extra steps to encode the transmitted gradients at the sender and decode them at the receiver.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**S1.** The authors give a convergence rate of the proposed algorithm, which matches the state-of-the-art approach. Although I do not check the proof details, the result sounds reasonable. \n\n**S2.** The experiment setup is comprehensive. It evaluates ResNet-50 and BERT-based models and conducts experiments on various numbers of GPUs.", "weaknesses": "**W1.** The literature review is poor. The authors did not comprehensively survey the works of one-bit compression, e.g., SSDM [1] and Marsit [2]. The unbiased design of Equation (5) has previously been proposed by the method proposed in [1], and [2] discusses a more complex all-reduce case. \n\n**W2.** This work is not very surprising. The existing works on one-bit compression generally use Adam/Momentum as the adapters in their experimental evaluation [1, 2, 3], although their approaches are discussed under SGD settings. \n\n**W3.** As the paper is discussed under the one-bit transmission, the readers expect the proposed method can use single-bit only for each parameter at every transmission. However, the proposed method seems incapable under multihop all-reduce [2] settings. \n\n***\n\n**References:**\n\n[1] Safaryan, Mher, and Peter Richtárik. \"Stochastic sign descent methods: New algorithms and better theory.\" International Conference on Machine Learning. PMLR, 2021. \n\n[2] Wu, Feijie, et al. \"Sign bit is enough: a learning synchronization framework for multi-hop all-reduce with ultimate compression.\" Proceedings of the 59th ACM/IEEE Design Automation Conference. 2022. \n\n[3] Bernstein, Jeremy, et al. \"signSGD with Majority Vote is Communication Efficient and Fault Tolerant.\" International Conference on Learning Representations. 2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our sincere gratitude for your volunteering time and your valuable comments. In response to your feedback, we have organized our response into the following points:\n\n**Q1.** *The literature review is poor. The authors did not comprehensively survey the works of one-bit compression, e.g., SSDM [1] and Marsit [2]. *\n\n**R1.** Thank you for bringing Ref [1-2]. Due to space limitations, our manuscript mainly discussed classic methods like signSGD,  TernGrad, QSGD, DIANA, 1-bit Adam, etc.,  did not cover variants of signSGD such as SSDM[1] and Marsit[2]. We guess you might misunderstand our proposed BRAM was also a variant of signSGD, so we shall  discuss SSDM and Marsit. As we emphasized in Section 2 in detail, BRAM is not a variant of signSGD. Thus, it might not be necessary to survey  [1-2].\n\n\n**Q2:** *The existing works on one-bit compression generally use Adam/momentum as the adapters in their experimental evaluation [1-3].*\n\n**R2:**  We respectfully disagree that all existing 1-bit compression optimizers are closely resemble those discussed in [1-3]. While character limitation  prevents an exhaustive comparison between the methods in [1-3] and prior classic methods, we focus on  distinctions between the methods in [1-3] and BRAM. The methods in [2-3] are essentially signSGD,  and we have extensively examined the differences between signSGD and BRAM in Section 2. Marsit, as presented in [2], introduces a 1-bit data communication scheme, and the contrast between Marsit and our Hierarchical-1-bit-All-Reduce is elaborated in **R3**.  Signum (signSGD witht momentum)  in [3] markedly  differ from that of BRAM. This dissimilarity  can be also validated by the experimental results; [3] shows that Signum  exhibits significantly inferior performance to Adam, while our paper demonstrate BRAM achieves comparable and even superior performance, compared  to Adam.\n\nBelow, we will focus on a comprehensive analysis of the distinctions between BRAM and SSDM [1], addressing your foremost concerns.\n\nBRAM can be simplified as \n$$\nm_{t} = \\beta m_{t-1} + (1-\\beta)g_t, \nb_{t}  = \\beta b_{t-1} + (1-\\beta)|g_t|, \nx_{t+1}  = x_t - \\alpha_t {\\mathcal Q_B} \\left(\\frac{m_{t}}{b_t}\\right),\n$$\nwhere ${\\mathcal Q _B}(\\cdot)$ is element-wise , and it quantizes the $j$-th element  as\n$$\n{\\mathcal Q_B} \\left(\\frac{(m _{t})_j}{(b _t)_j} \\right) =\n\\begin{cases}\n1& {\\rm with ~ prob}~ p= \\frac{1}{2}(\\frac{(m _{t})_j}{(b _t)_j}+1) \\\\\\\\\n-1& {\\rm with ~ prob}~ 1-p\n\\end{cases}\n$$\n\nSSDM can be simplified as\n$$\nm_{t}  = \\beta m_{t-1} + (1-\\beta)g_t, \\\\\\\\\nx_{t+1} = x_t - \\alpha_t {\\mathcal Q_S} \\left(\\frac{m_{t}}{\\Vert m_t \\Vert_2}\\right),\n$$\n\nwhere ${\\mathcal Q_S}(\\cdot)$ is  vector-wise,  *i.e.*, :\n$$\n{\\mathcal Q_S}\\left(\\frac{(m _{t})_j}{\\Vert m_t \\Vert_2}\\right) = \n\\begin{cases}\n1&  {\\rm with ~ prob}~ p= \\frac{1}{2}(\\frac{(m _{t}) _j}{\\Vert m_t \\Vert_2}+1)\\\\\\\\\n0& (m_t)_j=0\\\\\\\\\n-1& {\\rm with ~ prob}~ 1-p\n\\end{cases}\n$$\n\nThe primary divergence lies in their quantization, where ${\\mathcal Q_B}(\\cdot)$ in BRAM is element-wise, while ${\\mathcal Q_S}(\\cdot)$ in SSDM is vector-wise.  As for BRAM,   ${\\mathbb E}\\left(\\alpha_t{\\mathcal Q_B}\\left(\\frac{(m _{t})_j}{(b _t)_j}\\right)\\right) =  \\frac{\\alpha_t}{(b _t)_j}\\cdot(m _{t})_j$ where $\\frac{\\alpha_t}{(b _t)_j}$ is the adaptive learning rate, just like Adam. In contrary, SSDM maintains a uniform learning rate $\\frac{\\alpha_t}{\\Vert m_t \\Vert_2}$ due to its vector-wise quantization.  Moreover,  the dimension of $m_t$ for DNNs is much large, so that $\\frac{(m _{t})_j}{\\Vert m_t \\Vert_2} \\approx 0$, which will cause $x_t$ to mostly stay constant, rendering it unsuitable for training large DNNs. Conversely, BRAM's quantization ensures that each update is independent of the dimension of $m_t$. In brief, the contrast empowers BRAM to achieve quicker convergence and superior performance compared to SSDM.\n\n\nAnother differentiation is that ${\\mathcal Q_B}(\\cdot)$  employs 2 states ($-1$ and $1$), while ${\\mathcal Q_S}(\\cdot)$ employs 3 states ($-1$, $0$, and $1$). This means that BRAM requires fewer communication bits compared to SSDM.  Consequently, BRAM is more communication-efficiency than SSDM.\n\nMore importantly, the vector-wise quantization in SSDM can trace back to earlier work QSGD. In contrast, BRAM is the first adaptive optimizer that element-wise quantizes the entire update.\n\n\n**Q3.** *The method designed for Hierarchical-1-bit All-Reduce cannot guarantee every transmission using 1 bit only. The proposed method seems incapable under multihop all-reduce [2] settings.*\n\n**R3.** We respectfully disagree again with you on this issue. You might have skipped Section 4 and Figure 1.  They depict in detail how to communication 1-bit data with multi-hop communication scheme via Hierarchical-1-bit-All-Reduce.  \n\nMoreover, let's consider Marsit's methodology. Marsit can only guarantee the expected value of the final 1-bit data equals to the average of  the original 1-bit data among nodes, thereby it will bring performance deterioration. In contrast, Hierarchical-1-bit-All-Reduce ensures the final  data exactly equals to  the average of  the original data. Hierarchical-1-bit-All-Reduce effectively utilizes primitives natively supported by NCCL and Gloo, while Marsit needs to customization. Thus, Hierarchical-1-bit-All-Reduce is also more efficient than Marsit.\n\nNotably, the latest influential work ZeRO++  incorporated a method taht is nearly identical toHierarchical-1-bit-All-Reduce for LLM training . This demonstrates its effectiveness and generalization for large-scale distributed training.\n\n**Q4.** *There are no experimental results for uncompressed Adam.*\n\n**R4.** We appreciate your attention to our experiments. We want to highlight that our experimental results for uncompressed Adam are comprehensively presented in Section 5.2, Table 2, and Figure 2(e-f) of the main text. Additionally, more extensive results for  it are provided in Section B and Figures 1-4 in the Appendix."}]

Author rebuttal:

I greatly appreciate the efforts put forth by the chairs and reviewers to ensure high-quality reviews. We have studied the comments and suggestions seriously and carefully, which have definitely helped us improve the work. We now respond to the reviewers' comments as follows. The reviewer comments are presented below in italicized font, and our responses are provided in normal font.

Before addressing the reviewers' comments, we would like to reiterate the novelties of our work:

-  We propose a novel 1-bit  optimizer, dubbed  BRAM. To the best of our knowledge, it is the first native communication-compression adaptive optimizer that element-wise quantizes the entire model update, making compression/decompression computationally light and the extreme quantization ratio exert its best function.

- We theoretically prove that despite emolying extreme 1-bit quantization is employed,  BRAM still promise the same convergence speed as the full-precision Adam.

- We develop a new communication scheme for 1-bit communication, called Hierarchical-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.

- We perform extensive distributed  training experiments to demonstrate the effectiveness of the proposed algorithm. As far as we know, running with DDP,  our algorithm is the first work to consistently trump SGDM/Adam  in terms of entire running time at little/no inference performance cost}, reaching up to $2.47\times$ speedup for ResNet-50 and ${6.26}\times$ speedup for BERT-Base on $64$ GPUs.

It is important to note that our work primarily focuses on enhancing communication efficiency without compromising test accuracy compared to the baseline SGDM/Adam. Our emphasis is not on pursuing state-of-the-art performance, but rather on achieving improved efficiency in distributed training.



Meta-review: The paper proposes a 1-bit adaptive optimizer for distributed learning. In discussion, most of the reviewers tended towards accepting the paper, and I agree with that consensus. The main issue was the lack of comparison to multiple compressed ADAM baselines, but I don't view this as being a bar to acceptance.
Decision: Accept (poster)