Maximizing Communication Efficiency for Large-scale Training via 0/1 Adam
Authors: Yucheng Lu
Conglong Li
Minjia Zhang
Christopher De Sa
Yuxiong He
Venue: ICLR 2023 poster (2023)

Abstract: 1-bit gradient compression and local steps are two representative techniques that enable drastic communication reduction in distributed SGD. Their benefits, however, remain an open question on Adam-based large model pre-training (e.g. BERT and GPT). In this paper, we demonstrate the non-linearity in Adam causes slow convergence even when 1-bit compression or local steps are individually applied. To alleviate this limitation, we propose \textbf{0/1 Adam} that linearizes each Adam step via approximating its optimizer states using their stale estimates and linear correlation. \textbf{0/1 Adam} performs an Adam-like step to preserve the adaptivity, while its linearity allows utilizing 1-bit compression and local steps simultaneously for wall-clock time speed up. We provide convergence guarantee for \textbf{0/1 Adam} on smooth non-convex objectives. On various large-scale benchmarks such as BERT-Base, BERT-Large, GPT-2 pre-training and ImageNet, we demonstrate on up to 128 GPUs that \textbf{0/1 Adam} is able to reduce up to 87\% of data volume, 54\% of communication rounds, and achieve up to 2$\times$ higher training throughput and end-to-end training time reduction compared to the state-of-the-art baseline 1-bit Adam; while enjoying the same statistical convergence speed and end task model accuracy on GLUE dataset and ImageNet validation set. 

Published as a conference paper at ICLR 2023
MAXIMIZING COMMUNICATION EFFICIENCY FOR LARGE-SCALE TRAINING VIA 0/1 ADAM
Yucheng Lu Cornell University
Conglong Li Microsoft
Minjia Zhang Microsoft
Christopher De Sa Cornell University
Yuxiong He Microsoft
ABSTRACT
1-bit gradient compression and local steps are two representative techniques that enable drastic communication reduction in distributed SGD. Their benefits, however, remain an open question on Adam-base large model pre-training (e.g. BERT and GPT). In this paper, demonstrate the non-linearity in Adam causes slow convergence even when 1-bit compression or local steps are individually applied. To alleviate this limitation, we propose 0/1 Adam that linearizes each Adam step via approximating its optimizer states using their stale estimates and linear correlation. 0/1 Adam performs Adam-like step to preserve the adaptivity, while its linearity allows utilizing 1-bit compression and local steps simultaneously for wall-cloc' time speed up. We provide convergence guarantee for 0/1 Adam on smooth non-convex objectives. On various large-scale benchmarks such as BERT- -Bss,, BERT-Large, GPT-2 pre-training and ImageNet, we demonstrate on up to 128 GPUs that 0/1 Adam is able to reduce up to 87% of data volume, 54% of communication rounds, and achieve up to 2 higher training throughput and end-to-end training time reduction compared to the state-of-the-arr baseline 1 1-bit Adam; while enjoying the same statistical convergence speed and end task model accuracy on GLUE dataset and ImageNet validation set.
INTRODUCTION
Over the past few years, have witnessed outstanding performance of foundation models on many ap- plications. However, these models, including BERT et al. (2018) and Radford et al. (2019a); Brown et al. (2020), usually have hundreds of millions or even billions of parameters and require be trained on massive GPUs. For example, the largest dense transformer model, 530B MT-NL et al. (0022) was trained over 4000 GPUs more than month. At this scale, the expensive communication overhead across computing processors and servers hinders the scalability (Alistarh et al. (017).
1-bit gradient compression and local steps are two representative methods mitigate the commu- nication bottleneck. 1-bit compression drastically reduces the communication volume by quantizing each value in gradients with ultra-low bits (i.e., as low as bit) Seide et al. (2014); [Bernstein et al. (2018a); and local steps alternatively saves the bandwidth by periodically skipping communication rounds Stich 2018). While these techniques demonstrate tremendous success on distributed SGD, their benefits over large-scale Adam-bass model training. such as for BERT and GPT pre- trainining, remains an open question (Kingma and Ba 2014 Wang et al. 2019a). Comparing to SGD where the model parameters
linearly dependent on the gradients, the non-linearity in Adam updates (Kingmal and Ba 2014) limits the direct usage of compression or local steps. In particular, this non-linearity incurs challenges: 1) when aggressively compressing the gradient such with 1-bit quantizer, all the coordinate-wii effect learning rate will become the same value, so that Adam no longer enjoys adaptive and fast convergence:
2) ensure all parallel workers reach consensus on the optimizer states, which is critical for convergence, the existence of non-linearity incurs the overhead of iteratively synchronizing the states when using local steps.
Tang et al. (2021) undertook the first investigation of fixing this non-linearity towards compression and proposed 1-bit Adam. The algorithm follows two-stage training paradigm: first run Adam
"This work was done during Yucheng Lu's internship at Microsoft. Contact: y12967 eddu.

---

Published as a conference paper at ICLR 2023
with full precision communication (full-precision stage_ and then switch to 1 bit when the variance becomes stable (compression stage). While this paradigm avoids compressing non-linear information with one-time frozen variance, the experimental results from (Tang et al., 202I indicate the full- precision stage still incurs non-trivial overhead. Furthermore, 1-bit Adam is restricted in the scope of gradient compression, and cannot be trivially adapted when other techniques are used, such as local steps. Besides, the empirical success of (Tang ct al. (202I) was not substantiated on GPT-style models, for instance, 175B GPT-3 Brown et al. (020). 530B MT-NLG/Smith al. (2022), etc.
In this paper, we address this gap by proposing 0/1 Adam. 0/1 Adam breaks the barrier of non-linearity from two aspects: first it adaptively freezes variance, so that given agreement on a stale variance state, the parallel workers only need to communicate momentum that is linearly dependent on the model update; This technique allows reducing the previous two-stage compression scheme to a unified single stage; 2) it leverages the insight that in adjacent Adam steps, the changes to optimizer states are generally bounded, so that with frozen variance, parallel workers can linearly approximate momentum and parameter updates locally without additional synchronization. This further pushes the limit of communication reduction towards its extreme, achieving the state-of-the-ar speed up for large-scale model training. To summarize, our contributions are as follows:
We propose 0/1 Adam, which addresses the limitations of previously proposed 1-bit Adam when applying aggressive 1-bit quantization and local steps (Section
We provide convergence guarantee of 0/1 Adam on smooth and non-convex objectives (Section 55) We conduct experiments on wide range of large-scale model training tasks, including BERT-Base, BERT-Large, GPT-2 pre-training and ImageNet. We demonstrate on up to 128 GPUs that 0/1 Adam is able reduce up to 87% of data volume, 54% of communication rounds, and achieve up 2x higher throughput and training time reduction compared to the tlaeeoffttheaa 1-bit Adam without compromising end-to-end model accuracy (Section (
The 0/1 Adam optimizer and corresponding experimental scripts (e.g. BERT pre-training and GLUE
finetuning) have been open sourced in a deep learning optimization library called DeepSpeed
2 RELATED WORK
Communication--ffiient training. There has been various lines of research focusing on improving
communication efficiency in large-scale training, such as using asynchrony (Niu et al. 2011 Lian et al.
2015 et al. 2220), decentralization (Lian et al. 2017 Lu and De Sa 2021), 1), gradient quantization
(Alistarh al. [2177] Wen al. (017). gradient sparsification (Wangni et al. 2017 Wang et al. 201 Sa). local steps (Stich) 2018 Lin et al. 2018)) 8), etc. In this paper we study the aggressive I-bit compression, which was first introduced in (Seide et al. 2014)) to speed up speech model training, where an algorithm called 1-bit SGD is proposed. After that, Wen et (2017) proposes adding 0 as an additional numerical level and et al. (2018) discusses the use of zero-th order oracle in 1-bit SGD. Chen et al. (019a)):
SGI..Chen Balles and Hennig 2018)) Xu and Kamilov (2019) study the correlation and combination between
I-iit SGD and other techniques. Convergence analysis on 1-bit SGD is given in (Bernstein et al.
201 Sa
Karimireddy et al. 2019 /aaaayan and Richtárik (021). Bernstein et al. 8018b)
al.
(011)):
Le Phong and Phuong (020); Lyu (2021) investigate the robustness of 1-bit SGD. Among all the variants of 1-bit communicatinn, the design with error feedback mechanism has shown to work best both empiricallyy (Seide et al. (014)) and theoretically (Karimireddy al. 2019). Other lines of research applies 1-bit communication various scenarios such federated learning (Jin et.l. 2020 Yue et al.
2021). decentralized learning (Lu and De Sa 2020 Koloskova et al. 2019). meta learning (aan et al. 2021). etc. Perhaps the closest works to this paper are (Tang et al. 202 Lietal 202 which propose using two-stage training to enable 1-bit Adam and 1-bit Lamb, respectively. Different from those two work, 0/1 Adam addresses non-lineyy challenges in adaptive optimizers by considering both extreme quantization and local steps. Furthermore, we also study how to apply extreme communication compression on GPT-style models, which to the best our knowledge is still under-explored.
Adaptive learning rate optimizers. One of the most popular adaptive optimizers is Adam, which was first introduced in (Kingma and 2014). It uses both first and second moment information of stochastic gradient to perform optimizer steps and has shown significant benefits training deep
I In the original 1-bit Adam paper, this stage is referred to as warmup stage. We use slightly different term to avoid confusion with learning rate warmup.
2

---

Published as a conference paper at ICLR 2023
c,008
530
Hno mbll
1-bit Adam
0.0
Freezing Point
6,000
10
Stept 1Tes
s (1-5)
Step (le5)
Step Cle5)
(a)
00-- 0
(b)
0 (0)
wx
(c)
Im m4-1
(d)
me
Figure I: Momentum and variance Profiling for BERT-Large sequence 128 pretraining with original Adam using 64 GPUs. For variance, we profile two types of metrics: the first the difference between local and global variance: ||u (0) -vell: where v. and v, denotes the variance term computed via local gradient worker-O and the gradient from full-precision AllReduce, respectively. We also profile the variance difference in adjacent step ||0, - 01-1 Similarly, we profile the same two metrics for the momentum.
learning models. Reddi et al. (2019) spots the issue of Adam convergence and provides variant called AMSGrad phile/Zahea et al. (2018) argues the Adam only converges with large batch sizes.
Multiple lines of theoretical study on Adam are given (Fang and Klabjan| 2019 Alacaoglu et al.)
Défossez et al.) (020). Additionally, Chen et al. (2018) Zhou et al. (20T8a); Lu et al. (2020); Danilova et al. (2020); Zou et al. (2019) provide more general analysis on Adam- optimizers.
Subsequently, other variants of Adam proposed in (Luo et al. 2019 Chen et al. 2019b Huang et al. 2018 Wang et al. 2019b Zhou et al. 2018b Zhuang et al. 2021 (020). Unlike these methods, which focus improving the convergence of generic optimizations for DNN models, our work studies
how to maximize the communication efficiency of Adam large-scale distributed training settings.
A CLOSER LOOK AT NON-LINEARITY IN ADAM
In this section, we provide a more formal description on the problem setting and illustrate the limitations from the original Adam and the stale-of-the-art 1-bit Adam (Tang al. 2021.
Problem Formulation. In this paper, we consider the following optimization problem:
min f(x) (z)== = =B<=Df(x;() #ER"
(I)
where denotes the d-dimensional model. D denotes the training set and f(::() is the loss incurred over sample Ç given model parameters æ. The structure of the problem naturally captures many of the model training problems.
The non-linearity Adam. step 12 0, denote z; and gr as the model parameters and stochastic gradient computed step respectively. The update formula of SGD and Adan can be summarized as:
SGD update:
#++1 + -911
Adam update: m + Bim,
)
v++1 B28 (1-B2) (g.)
Øt+1 Et
m&,
Vurte
elfective learning rale
where y is the learning rate, is a small constant to prevent zero division, B1 and Ba are tunable decaying factors. The linearity in SGD update implies when using compression or local steps, the potential noise from (accumulated) gradients is in the order of O which approaches zero when learning rate is decaying or set to be small. By comparison, the two auxiliary optimizer states in Adam, momentum (m) and variance (v), introduce non- non-lineerity in the model update.
Equation (3) gives the formula of Adam when running it sequentially. In distributed setting with n workers, St in Equation (3) is often computed in parallel on different workers. Mathematically.
(8) we denote gi as the stochastic gradient computed on the i-th worker at step i, then distributed Adam
Note that in Adam, operations like division should clement-wise.
3

---

Published as a conference paper at ICLR 2023
can be written as replacing 9: with 1/n (
in Equation 3 as follows:
(8) Mx+ + -1-3m Σ. Ii Ue+1 + 320, + (2 (1)0 9 g(
Issue with non-linearity on 1-bit compression. The main bottleneck in running distributed Adam al.; al.
is the accumulation of 1 //12/111 9. since the gradients are usually nigh-dimensional Based on the profiling results from (Tang et al. 2021; Li
[221aa), the communication of gradients could take up to 94% of the total training time on modern clusters. Gradient compression mitigates this issue by sending and averaging gradients with fewer bits. However, in Adam this causes the loss the learning rate adaptivity. Consider using the aggressive 1-bit compression (Liu et al. (0118), which sends each gradient with only signs and a shared, usually the average over all the coordinates, magnitude. More specifically, denote C[-] as the 1-bit compression, then
Cia] = |al|
It is straightforward to observe that naively applying bit to compress gradients in the original Adam loses coordinate-vee wise adaptivity since sharing magnitude makes all the coordinates- wise learning rate 7/V /B, te the same value. This makes Adam difference than momentum SGD.
Issue with non-linearity on local steps. In SGD (Equation (2), the model updates are linearly dependent the gradients and has zero additional states. It implies with local steps, the parallel workers can entirely reach consensus after a single round of synchronization, even with compression (Basu al. 2020). However, in Adam simply synchronizing the model can still leave the momentum and variance out-of-sync. This makes parallel workers fail to capture the global adaptivity when the system scales up. To give more concrete example. we profile a full run of BERT-Large pre-training with original Adam, and summarize different metrics of momentum and variance in Figure| I| As shown in Figure J T(b), the difference between local and global optimizer states, momentum and variance, remain constants and do not decrease to zero.
1-bit Adam and its limitations. 1-bit Adam (Tang et al., 2021 is a state-of- of-te-of-the-art solution that addresses non-linearity in 1-bit compression. 1-bit Adam adopts pre-conditioned variance state from running original Adam for To steps first. The intuition there is that at later stage of training, the variance state becomes stable so that tr, can be good approximation of variance state for the remaining steps. As paritally illustrated in Scction I the full-precision stage of 1-bit Adam still presents non-trit non-trivial overhead. For instance: as illustrated in (Tang al. (021). when training BERT-
64 GPUs using Ethernet, while the full- prll-preciiion stage contains 15% 5 of the total steps, it can take more than 50% of the entire training in terms of the wall-clock time Additionally, 1-bit Adam is restricted in the scope of compression, how it handles other techniques such as local steps remains open question.
4 0/1 ADAM
In this section, we give the full description of 0/1 Adam. To maximize the communication efficiency, ideally we want an algorithm that enables adaptive convergence like Adam, while allowing aggressive compression (e.g. bit) and requires no additional synchronization on the optimizer states when using local steps. 0/1 Adam solves this problem from two aspects.
Adaptive Variance Freezing. To begin with, 0/1 Adam creates a linear environment that freezes the variance adaptively. The intuition is leveraged from the observation in Figure [(a] the change of variance over steps in Adam is generally smooth. While 1-bit Adam captures reasonable variance estimate via one-time freezing, it reasonable to also presume that before its freezing point, the variance within several adjacent steps will stay close due to its smoothness. This motivates to extend the one-time freezing policy in -ibt Adam into an adaptive one, by letting workers agree upon the freezing The frozen variance creates multiple intervals
points from a given step index set To C (O....,TT --... 1}. over training, during which the workers have agreement on the denominator (Equation (3) and the only uncertainty then left in the nominator that is linearly dependent on the model update, just like SGD.
'Concretely, shows in Tang et al. 2021) Section 7.1 that to train BERT- on 64 GPUs using Ethernet, the full- prlecisiiionn Adam takes 174.3 hours in total while 1-bit Adam takes 51.5 hours. By simple calculation. we know that full-precision stage of 1-bit Adam takes approximately 26.37 hours while the compression stage takes 25.13 hours.
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 Proposed 0/1 Adam Algorithm
Require:
local model the i-th node x.) lcarning rate f' K= my = 0, 00 auxiliary buffer Uu 0, total number of iterations decaying factor 31, S2 from Adam, numerical constant variance update step index set Tu, Synchronizaionnnn step index set Tu, the most recent step with synchronization =0.
1: for O.....TTT 1 do
Compute local stochastic gradient g
Update momentum: m
++ =
(5)
=8mm
+ (1-81)97
4: Update model:
(8)
m /v.
5: Update buffer:
tmm!
144
6: ift Tu then
7:
Perform 1- I-bit AllReduce: n Ibit-AllReduce
(1+2)
8:
Approximate momentum with compressed buffer: m (+1 u //+ Eh
9:
Update model with compressed buffer: < æ u /Vitte
10:
Reset the auxiliary buffer: u/+1 =0.
11:
Update the synchronization step: t' =t
12:
else
2 = (6) [+] mm: = =m (2) (1)
13:
e+ u41 = 5+2
14:
end if
i To then
16:
Perform full-precision AllReduce: 9. AllReduce (g
17:
Update the variance: U:41 (1-
18: else
19:
Use the stale variance next iteration: 1/++1 1/+-
20:
end if
21:
end for
22:
return æT.
Including 1-bit Compression and Local Steps. With frozen variance, we make another observation based on Equation (3) that the model difference on workers will be linearly dependent to the momentum. So that, the momentum can be approximated locally rather than synchronized additionally based on the communicated model difference, given the premise that the change of momentum is not abrupt
within close steps. Formally, denote (² m (4) e as the model, momentum, variance on worker i at step l,, respectively. Suppose all the workers are synchronized at step I', then with frozen variance over all the workers,
u - k="
(i) Ykm
Actual sent tensors in the communication.
1/n
F+++
xx
Sync model parameters with the sent tensors.
Vo+e
1/
(1)
m ~
Approximate momentum via linear estimates via sent tensor.
Σk
where we omit the compression part for brevity. Combined with compression, we provide the full description of 0/1 Adam Algorithm| [ Note that here we defer the details of 1-bit compression to Appendix A and treat it as a black-box procedure named 1bit-AllRedie while the original full- full-precision AllReduce is referred as AllReduce.
We also remark that although both techniques appear to be natural, to the best of our knowledge, we are the first to apply them addressing the non-linearity challenges 1-bit compression and local steps for maximizing the communication efficiency of Adam optimizer.
'The name comes from the fact that the algorithm can potentially reduce the per-parameter volume some number between 0 and bit on average.
5

---

Published as a conference paper at ICLR 2023
5 CONVERGENCE ANALYSIS
In this section, we provide the convergence guarantee for 0/1 Adam (Algorithm[]) 1 under arbitrary freezing policy To and local steps policy Tu- In the main paper, we provides the convergence rate in the general case. However, different To or Tu gives us the opportunity to obtain tighter bounds. We leave these discussion in the appendix. We start by making the following assumptions.
Assumption 1. Lipschitzian gradient: f(.) is assumed to be with L-Lipschirzian gradients, which means
| (=)) (g))l S L|| - ",,,,
Assumption 2. Bounded variance: The stochastic gradient computed on each worker is unbiased and has bounded variance:
(x:{)) V V fz)) <o²,
Vz.
Assumption 3. Bounded gradient: The infinity norm of stochastic gradient is bounded by a constant Go >0 such that || S VL.
Assumption 4. Compression error in Algorithm 7 For arbitrary x: E RR,, there exists constant A, such that the output of compressor C[-] has the following error bound: [||[[[]] < Assumption 5. Given ordered set Tu. denote 13 as the j-th element in Te, we assume there exists constant H 2 0, it holds that m (1i+1- 11p) H.
Remarks on the assumptions. Assumption 2 and 3 are standard in the domain of non-convex optimization. Comparing with the 1-bit Adam paper (Tang et al. 2021), we do not explicitly assume the uniform lower bound the variance coordinate, i.e., e bound on the gradient as in Assumption 3 which is more realistic.
Umin 0,Vý for some constant Umin-
Instead we assume an infinity-none Assumption i also assumed in (Tang et al.) (2021), in the appendix we discuss the variant of 0/1 Adam that converges with weaker condition on the C.
The convergence for Algorithm iis then given in the follow theorem.
Theorem 1. Under Assumption to let = (Tel. select B1, A3 E [0, 1) that fulfills
m m ( (1))_//o0))))))) if we run Algoriam 1
with constant learning rate: for all t2
2 G +e
7t =im
02T 4L AL +
6
then it holds that
H² (m 1
V 11 00
+ +T) T
VnT
T
where ã, = -1/n - and we omit f(f)-infZeRe f(x), Goc, d, 3r, B2 and L as constants.
Theorem [ shows that 0/1 Adam Algorithm D
essentially admits the same convergence rate as distributed SGD in the sense that it achieves linear speed up, at rate 1 1/O(vnTT) 'he effect of compression (A) and local steps (H) only appears non-dominating term.
EXPERIMENTS
In this section we evaluate the performance of 0/1 Adam over several large-scale model training tasks comparing with baselines (1-bit Adam (Tang et al. 2021) and original Adam (Kingma and Ba 2014)). Since Tang et al. (20TT) already demonstrated that 1-bit Adam has similar statistical results to Adam, omit the comparison of end-to-end model accuracy to Adam for brevity. Throughout the experiments, we enable FP16 training for all the tasks following (Tang et al. 202I). That makes the full- full-precision communication (including Adam, full-precision stage in 1-bit Adam and full-preciss pprecisionn AllReduce 0/1 Adam) use 16-bit per number. We use the 1-bit compressor (Equation 4 0/1 Adam.
Experimental details. We adopt the following tasks for the evaluation: BERT-Base (L= H 768. A 12, 110M params) and BERT-Large (L 24, /l = 1024,
16, 340M params) pre-training. training Resnet18 (12M params) ImageNet (He et al. 2016) and GPT-2 pre-training. For BERT model, we use the same dataset as (Dellin et al.) 2018). which is a concatenation of Wikipedia and BooksCorpus with 2.5B and 800M words respectively. We use the GLUE fine-tuning benchmark (Wang ctt al. 20188) to evaluate the convergence of the BERT models trained by different algorithms. For ImageNet, adopt ImageNet- 1 dataset, which contains 1. 1.28M images for training and 50K images

---

Published as a conference paper at ICLR 2023
7.5
1-bit Adam
Training Locs
7.5
5.0
0/1 Adam
5.0
2.5
2.5
1000
2000
3000
4000
5000
250
500
750
1000
1250
1500
1750
Sample (1e5)
(min)
(a) BERT-Base Base pretraining seq 128
Trering Las
7.5
1-bit Adam 0/1 Adam
Training Loss
7.5
5.0
5.0
2.5
2.5
2X
1000
2000
3000 Sample (1e5)
4000
5000
6000
0
1000
2000
3000
4000
Time (min)
BERT-Large pretraining seq128
Adam
Training Locs
Thaining
2
1.4X
0
200
400
600
800
1000
200
400
600
800
1000
1200
Sample (1c5)
Time (min)
(c) Resnet18 88 on ImageNet
Figure 2: Sample-wise and time-wise convergence for BERT- LERT-Base/Large pre-training sequence length 128 and Resnet18 8 pretraining on ImageNet using 128 GPUs on the Ethernet cluster. Note that the time the right side is measured on both algorithms processing the same number of samples.
Adart
L-be Adam
2-2t
Acem
$000
Adam
2o0t Acom
Adam
6000
4000
2000
2000
Navcer CLOMS
(a) BERT-Base (Ethernet) (b) BERT-Laage (Ether-(c) BERT-Laare (Infini-(d) ImageNet (Ethereet) batch size=4096
net) batch size=4096
Band) batch size=4096 batch size=256
Figure 3: End-to-end average throughput for BERT-Base/Larg pre-training sequence length 128 and Resnet18 pretraining on ImageNet using 128 V100 GPUs on the Etthenet//nniniiaand cluster. Note that since for ImageNet, both batch size (256) and model (Resnet18) are small compared to BERT, and its parallelism speed up will be limited if applied to the same large system on BERT (128 GPUs). And so we test for to 32 GPUs in Figure (d).
for validation (Deng 2009). For GPT-2 we adopt the model from its original paper (Radford et al.
2019b), which contains 11 7M parameters (48 layers, 1600 hidden size, 25 attention heads). ). For training
data, we adopt the same dataset blend as in (Shoeybi et al. 2019h: Wikipedia (Devlin al. 2018
CC-Stories (Trinh and Le| 2018). RealNews (Zellers et al. 2019). and Open Webtext (Radford et al.
2019b). Other details including learning rate schedules, hyperparameters can be found in Appendix C
Hardware. We evaluate two clusters: one with 4 NVIDIA V100 GPUs per node and 40 Gigabit Ethernet inter-node network (2.7 Gbps effective bandwidth); the other one with 8 V100 GPUs per node and 100 Gigabit InfiniBand EDR inter-node network (close to theoretical peak effective bandwidth). We use 128 GPUs for BERT and ImageNet pretraining tasks to measure 0/1 Adam's 's performance gain. We use 64 GPUs for GPT-2 pre- pre-training. Additionally, for ImageNet training apply the accelerated data loading technique from Imdt
Policy for To and Tu, in 0/1 Adam. We first illustrate our policy Te. Observing from our motivation study (Figure T that the variance difference in adjacent steps decreases roughly exponentially. Denote k, as the step where j-th variance update takes place, we select T, such that, kj+1 - k, = //5/ V. > We adopt x 16 for all the three tasks.
7

---

Published as a conference paper at ICLR 2023
Table 1: GLUE development results. BERT- LareT---a//aargeooriii arge(original) results from Devlli et al. 2018). BERT-Basc/Laare(AA
and 1-bit Adam) results are from (Tang et al. 2021). The scores
are the median scores over 10 runs with different seeds, and are obtained on the checkpoints trained
by both sequence 128 and sequence 512 datasets.
RTE MRPC STS-B CoLA
SST-2
QNLI
QQP MNLI-(m/mm)
Avg
BERT (oseini)g
66.4
84.8
85.8
52.1
93.5
90.5
89.2
84.6/83.4
81.1
BERT-Base
68.2
84.8
85.1
56.8
91.8
90.9
90.9
83.6/83.5
81.8
BERT-Basee1- (1bit Adam)
69.0
84.8
83.6
55.6
91.6
90.8
90.9
83.6/83.9
81.5
BERT-Bascc0/11 Adam)
69.7
85.1
84.9
54.4
91.9
90.3
90.7
83.7/83.7
81.6
BERRT-LargeeOrrginnl
70.1
85.4
86.5
60.5
94.9
92.7
89.3
86.7/85.9
83.6
BERT-Large(Adann
70.3
86.0
86.9
60.3
93.1
92.2
91.4
86.1/86.2
83.6
BERT-Large(I-bee Adam)
70.4
86.1
86.1
62.0
93.8
91.9
91.5
85.7/85.4
83.7
BERT-Large(0r/ Adam)
71.7
86.2
86.9
59.9
93.2
91.6
91.4
85.6/85.6
83.6
Table 2:
The first column shows Topl accuracy on ImageNet Resnet Resnet the end of epoch 90 from differ- algorithms. The original accuracy is provided by Pytorch pretrained model library (Pytorch) 2014). For the other two algorithms, the accuracy is the highest score zero-shot evaluation of the trained GPT-2 on WikiText- 103 and LAMBADA datasets, the evaluation methodology follows (Shocybi et al. 2019). The number for Adam is obtained from (Li et al. 2021b).
score over runs. The other two columns shows
ImageNet Iopl Acc. f WikiText Perplexity 4 LAMBADA Acc. 1
Original Adam b- Adam 0/1 Adam
69.76
27.78
33.19
69.93
28.37
33.21
69.88
28.07
33.51
Then on discuss the policy for Tu. Based on the derivation in Section the approximation noise from local step is proportional to the learning rate. And so if we denote t as the step where j-th synchronization takes place, then intuition is to increase 1 - roughly inversely proportional to the learning rate l so as to make the approximation noise bounded. For BERT-Base// Large pretraining, illustrated before, the learning rate exponentially decreases by 0.99 every 520 steps after 12.5K linear for the first 12.5K steps and after that let it multiply
increase warmup steps. So that we set + by 2 every 32678 steps based on the calculation that the learning rate will decrease by half. Similarly. for ImageNet we set f -t every 50050 steps (10 epochs). We clip the interval at 16 all the tasks. This corresponds to Assumption 5 Finally, since our theory in Section 5 iindicaess that approximation will be more accurate when the variance is frozen. So that we additionally stop updating variance when 1j+1 - 1 > 1.
-t, tt= =
for the first 50050 steps (10 epochs) and after that let it multiply by 2 16 in
Remarks on the selected policy. As described, the policies for T, and Tu generally follow the learning rate schedule adopted. This is favored in practice for three reasons: (1) It does not require too much hyperparameter tuning. Consider adopting constant decaying policy based on some utility function, capturing the dynamics of the training to reach a useful interval would require tedious search- ing on the hyperparameters and retraining: (2) Learning rate policy is well motivated. As naturally, communication a way of eliminating the difference among workers. If workers adopt a larger learning rate, more frequent communication will be needed since the workers are taking large steps the weight space and so require ffrquett communication for them to reach consensus; (3) Learning rate schedule is universally used in all the ML/DL applications, and thus the method can be easily adapted to other applications. In fact, if consider the scope of large model training, typical learning rate schedule is a linear warm-up followed by decaying phase, which is very similar to our test cases here.
6.1 CONVERGENCE SPEED AND QUALITY ANALYSIS
Figure presents the sasple-wise and timewwise convergence results for different algorithms with 128 GPUs the Ethernet cluster. We find that 0/1 Adam provides the same sample-wise convergence speed compared to the baseline, with up to 2x time-wise speed up. Table [ummariizess the GLUE results using the checkpoints from our BERT pretraining experiments. 0/I Adam achieves similar end task accuracy compared to the numbers reported in previous work. 0/1 Adamachieves faster training time than prior work because it reduces the communication overhead in distributed training
8

---

Published as a conference paper at ICLR 2023
4,0
1-btt Adam
#omm Rounds
bbbl ImageNet
3.0
02
2.5
0Bit per
1.5
844
0.
L40
148
0.0
BERT Base
BERT-Large
ImageNet
GPT-2
0.
BERT-Base BERT-Large
GPT-2
Figure 4: Reduction on number of bits per parameter used and number of communication rounds in different tasks. Note that the communication round numbers are normalized due to scale difference in different tasks. Note that original Adam uses 16bits per parameter and communicate at evert step.
3 Adam
1i Adam
(1 Adam wib Local Staps
WV Adam wo Local Stops
5.0
25
1.2
2.5
1.30
250
300
750
1000
1250
1500
3730
3000
2000
3000
4000
Time
Figure 5: Evaluation BERT-Base/Large pretraining throughput using Adam without communica- tion rounds skipping. Comparing with Figure and local steps breaks the barrier the performance gain.
by using both 1-bit quantizer to compress the communication volume (up 32x reduction) and 1-bit AllReduce to reduce the expensive synchronization overhead for local steps in both warmup and non-warmup phases. Provieess the ImageNet validation accuracy of trained models from different algorithms, and we find the final accuracy can achieve the reported accuracy from Pytorch library (Pytorch 2014). For brevity, convergence comparison on GPT-2 is given the Appendix
6.2 TRAINING THROUGHPUT ANALYSIS
Figure 3 summmrrzess the throughput results on different tasks and different clusters. We observe that 0/1 Adam can consistently outperform baselines all settings. is also worth mentioning that 0/1 Adam on Ethernet (2.7 Gbps effective bandwidth, 4 GPUs per node) is able to achieve comparable throughput as 1-bit Adam on InfiniBand (near 100 Gbps effective bandwidth, 8 GPUs per node), as shown in the red line in Figure (bb) and the blue line in Figure 3(c) which demonstrates 0/1 Adam further removes the redundancy in communication effectively that exceeds the hardware barrier.
Communication reduction and the role of local steps. To better understand the importance and effect of local steps, we additionally run a special case of 0/1 Adam where we keep the same policy of T, but use Tu . 1}. This special version of 0/1 Adam does not skip rounds but use the same variance freezing policy. We plot the data volume usage and throughput results in Tigure4aadl
respectively. We see that although no local steps suffice to reduce the data volume overhead from 1-bit Adam towards 1-bit-per-parametter in general, the throughput improvement is limited compared to Figure
7 CONCLUSION
In this paper, we study the challenges of using 1-bit communication on Adam, and limitations of the state-of-the-art 1-bit Adam algorithm. We propose an algorithm named 0/1 Adam that adopts two novel design: adaptive variance state freezing and 1-bit sync. We provide convergence proof for 0/1 Adam and measure effectiveness over baseline Adam and 1-bit Adam on various benchmarks, including
GPT-2 pretraining and ImageNet.
ACKNOWLEDGMENTS
Yucheng Lu is supported by Meta PhD Fellowship. The authors would like to thank anonymous reviewers from ICI,20233 for providing valuable feedback.

---

Published as a conference paper at ICLR 2023
REFERENCES
Jacob Devlin, Ming-Wai Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arxiv:1810.048005, 2018.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models unsupervised multitask learners. 2019a.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Gretchen Krueger. Tom Hemighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jefffre Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. CoRR, 2020. URL
/ httptpp://aaxxi.oggo//bbbbbe///s wbtgg/ab//2005.00 14165
Shaden Smith, Mostofa Patwary, Brandon Norick, Patrick LeGresley, Samyam Rajbhandari, Jared Casper, Zhun Liu, Shrimai Prabhumoye, George Zerveas, Vijay Korthikanti, Elton Zheng, Rewon Child, Reza Yazdani Aminabadi, Julie Bernauer, Xia Song, Mohammad Shoeybi, Yuxiong He, Michael Houston, Saurabh Tiwary, and Bryan Catanzaro. Using deepspeed and megatron to train megatron- turtinnoottunngggo NLG 530b, A lurge-scale generative language model. CoRR, abs/2201.119900 2022.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30: 1099177909 1720, 2017.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application data- aata-parallel distributed training of speech dnns. Fiffeenth Annual Conference the International Speech Communication Association. Citeseer, 2014.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pages 560-569. PMLR, 2018a.
Sebastian Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv: 2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
Dong Wang. Yicheng Liu, Wenwo Tang. Fanhua Shang. Hongying Liu, Qigong Sun, and Licheng Jiao. signadam++: Learning confidences for deep neural networks. In 2019 International Conference on Data Mining Workshops (ICDMW), pages 186-195. IEEE, 2019a.
Hanlin Tang, Shaoduo Gan, Ammar Ahmad Awan, Samyam Rajbhandari, Conglong Li, Xiangru Lian, Liu, Ce Zhang, and Yuxiong He. 1-bit adam: Communication efficient large-scale training with adam's 's convergence speed. arXiv preprint arXiv:2102.02888, 2021.
Feng Niu, Benjamin Recht, Christopher Ré, and Stephen Wright. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. arXiv preprint arXiv: 106.,730 2011.
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. Advances Neural Information Processing Systems, 28:2737-2745, 2015.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous sgd. In
International Conference Machine Learning, pages 10495-10503, PMLR, 2020.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang. and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. arXiv preprint arXiv:170S.09056 2017.
Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In International Conference Machine Learning, pages 7111-7123. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2023
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. arXiv preprint arXiv:1705.07878, 2017. 2017.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparssfiiaiinnnn for communication- efficient distributed optimization. arXiv preprint arXiv:1710.09855, 2017.
Hongyi Wang, Scott Sievert, Zachary Charles, Shengchao Liu, Stephen Wright, and Dimitris Papailiopoulos. Atomo: Commumication--cficccni learning via atomic sparsification. arXiv preprint arXiv:1806.04099 8a.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large local sgd. arXiv preprini arXiv: 1888088877777 2018.
use
Sijia Liu, Pun-Yu Chen, Xiangyi Chen, and Mingyi Hong. signsgd via zeroth-order oracle. In International Conference on Learning Representations, 2018
Xiangyi Chen, Tiancong Chen, Haoran Sun, Zhiwei Steven Wu, and Mingyi Hong. Distributed
training with heterogencous data: Bridging median-and mean-based algorithms. arXiv preprint arXiv:1906.01736. 2019a.
Lukas Balles and Philipp Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. In International Conference on Machine Learning, pages 404-413. PMLR, 2018.
Xiaojian Xu and Ulugbek S Kamilov. Signprox: One-bit proximal algorithm for nonconvex stochastic optimization. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (aaeiigg//AAAS (ICASSP), pages 7800-7804, IEEE, 2019.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages
PMLR, 2019.
Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In International Conference Machine Learning, pages 9224-9234. PMLR, 2021.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadeneshelli and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. arXiv preprint arXiv:1810.05291, 2018b.
Jy-yong Sohn, Dong-Jun Han, Beongjun Choi, and Jaekyun Moon. Election coding for distributed learning: Protecting signsgd against byzantine attacks. arXiv preprint arXiv: 2019.
Trieu Le Phong and Tran Thi Phuong. Distributed signsgd with improved accuracy and network fault tolerance. IEEE Access, 8: 1:191839-191849, 2020.
Lingjuan Lyu. Dp-signsgd: When efficiency meets privacy and robustness. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3070-3074. IEEE, 2021.
Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-sign sgd for federated learning with theoretical guarantees. arXiv preprint arXiv:2002.10999 2020.
Kai Yue, Richeng Jin, Chau-Was Wong, and Huaiyu Dai. Federated learning via plurality vote. arXiv preprint arXiv:2 1r.vv22110.02993 10.02998, 2021.
Yucheng and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized
sgd. In International Conference on Machine Learning, pages 6415-6425. PMLR, 2020.
Anastasia Koloskova, Tao Lin, Sebastian Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXiv:1907.093330 2019.
Chen Fan, Parikshit Ram, and Sijia Liu. Sign-maml: Efficient model-agnostic meta- meta-learning by signsgd. arXiv preprint arXiv: 109.07499 2021.

---

Published as a conference paper at ICLR 2023
Conglong Li, Ammar Ahmad Awan, Hanlin Tang, Samyam Rajbhandari, and Yuxiong He. 1-bit lamb: Communication efficient acaeescale large-batch training with lamb's ' convergence speed. arXiv preprint arXiv:2104.000 06069, 2021a.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXivv:/944099237, 2019.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances in neural information processing systems, 31, 2018.
Biyi Fang and Diego Klabjan. Convergence analyses of online adam algorithm in convex setting and two-layer relu neural network. arXiv preprint arXiv: 1905. 09356, 2019.
Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher. A new regret analysis for adam-type algorithms. In International Conference Machine Learning, pages 202-210 PMLR, 2020.
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv preprint arXiv:2003. 02399, 2020.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non non-convex optimization. arXiv preprint arXiv: 02941, 2018.
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arw.vv:808..066777777.1 2018a.
Yucheng Lu, Jack Nash, and Christopher De Sa. Mixml: A unified analysis of weakly consistent parallel learning. arXiv preprint arXiv:2005.06700 2020.
Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov, Eduard Gorbunov, Sergey Guminov, Dmitry Kamzolov, and Innokentiy Shibaev. Recent thcoretical advances in non-convex optimization. arXiv preprint arXiv:2012.06111 00w.0.0........... 2020.
Fangyu Zou, Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11127-11135,20 2019.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv: wet::0902.0.. 2019.
Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. Zo- adamm: Zeroth-order adaptive momentum method for black-box optimization. arXiv preprint arXiv:1910.0651.. 13, 2019b.
Haiwen Huang, Chang Wang, and Bin Dong. Nostalgic adam: Weighting more of the past gradients when designing the adaptive learning rate. arXiv preprint arXiv:1805.0755 2018.
Guanghui Wang, Shiyin Lu, Weiwei Tu, and Lijun Zhang. Sadam: A variant of adam for strongly convex functions. arXiv preprint arXiv: 1905.00900 2019b.
Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu. Adashift: Decorrelation and convergence adaptive learning rate methods. arXiv preprint 13X1v:1810.00143. 2018b.
Juntang Zhuang, Yifan Ding, Tommy Tang, Nicha Dvoreck, Sekhar C Tatikonda, and James Duncan. Momentum centering and asynchronous update for adaptive gradient methods. Advances in Neural Information Processing Systems, 34, 2021.
Juntang Zhuang, Tommy Tang. Yifan Ding, Sckhar C Tatikonda, Nicha Dvornek, Xenophon Papademetris, and James Duncan, Adabelief optimizer. Adapting stepsizes by the belief in observed gradients. Advances in neural information processing systems, 33:18795-1888 2020.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas N Diggavi. Osparse-local-see Distributed sgd with quantization, sparsification, and local computations. JEEE Journal on Selected Areas in Information Theory, 1(1::117-22, 2020.
12

---

Published as a conference paper at ICLR 2023
Pytorch. Torchvision 0.11.0 documentation -pytorch.rrg http://ssss////cccccooo///////o.
stable/models. htt.//.mmmesssmmmmmm.... html 2014.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper. and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv:/909.000 2019.
Conglong Li, Minjia Zhang, and Yuxiong He. Curriculum learning: A regularization method for efficient and stable billion-scale gpt model pre-training. arXiv preprint urXiv:2108.00008 2021b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint 1xXvv:/804.07461 2018b.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale scale hierarchical image database. In 2009 IEEE conference computer vision and pultern recognition, pages 248-255, leee, 2009.
Sutskever. Better language models and their implications. OpenAl blog, 1:2, 2019b. Alec Radford, Jeffrey Wu, Dario Amodei, Danicla Amodei, Jack Clark, Miles Brundage, and Ilya
Tricu H Trinh and Quoc V Le. A simple method for commonsense reasoning. arXiv preprint arXiv:1806.00287, 2018.
Rowan Zellers, Ari Holtzman, Hannah Rashkin, Yonatan Bisk, Ali Farhadi, Franziska Roesner, and Yejin Choi. Defending against neural fake news. Advances in neural information processing systems, 32, 2019.
A FULL DESCRIPTION TO ALDREDUCE
As introduced Section 2 the error feedback based Ibit-AllReduce works best both in theory and in practice. In fact, the original 1-bit Adam also adopts the error-feedback design (Tang et al. (2021). We give the full description
this Ilit-AllReduce in Algorithm [ to replace the Ibit-AllReduce in Algorithm!!! []] In the theoretical analysis, proofs will also rely this algorithm. Note that this algorithm does not require any additional assumptions for our theory to hold, since this fits the black-box procedure in Algorithm| 4nd Algorithm
Algorithm 2 The full description of Error Feedback bit Communication (Ibit-AllReduce)
Require: communication buffer (() worker error 6!!) server error J,, 1-bit compressor C[+]. Both worker and server errors will be initialized 0 at t0
1: (On i-th node)
2: Compress 2, (1) into 2(10)
Cl2 (7)
+ 800) and update the compression error by
6/01=2/ =x +8 (1) (0)
Send ({{) to the server.
4: (On server)
E 5: Take the average over all the (t) and compress it into - 200 + -e), and update the
compression error by 8.+1= - - +5, Zt.
a(1)
6: Send E, to all the workers.
7: (On i-th node)
8: return 2;, 8 8,+1-
13

---

Published as a conference paper at ICLR 2023
Algorithm 3 The full description of AllReduce
Require: communication buffer z(")
1: (On i-th node)
2: Send =[") to the server.
3: (On server)
4: Take the average over all the 2, into 2, = -E 14
(8)
5: Send & to all the workers.
6: (On i-th node)
7: return zz.
B PROFILING RESULTS FOR FIXED COST OF COMMUNICATION
We profile the time taken in computation and others (including initialization of communication round and compression) during one 1-bit AllReduce round at different scales on Ethernet cluster Table 3
Table 3: Profiling on Ethernet cluster the time taken in computation and others (including initialization of communication round and compression) during 1-bit AllReduce round at different scales.
ImageNet
node (16 GPUs) node (32 GPUs) 16 node (64 GPUs) 32 node (128 GPUs)
Computation
73ms
68ms
44ms
51ms
Others
8ms
6ms
21ms
19ms
BERT-Base
node (16 GPUs)
node (32 GPUs)
16 node (64 GPUs)
32 node (128 GPUs)
Computation
94
490ms
263ms
162ms
Others
153ms
250ms
397ms
658ms
BERT-Large
node (16 GPUs)
node (32 GPUs)
16 node (64 GPUs)
32 node (I28 GPUs)
Computation
1840ms
970ms
640ms
332ms
Others
340ms
510ms
590ms
93 ms
C ADDITIONAL EXPERIMENTAL DETAILS
Training Parameters. For BERT pretraining, we follow the settings from (Devlin et al. 2018) and let the learning rate linearly increases to 4 x 10-1 as warmup in the first 12.5K steps, then decays into 0.99 of the original after every 520 steps. We set 31 = 0.9 and B3 0.999 for all the algorithms. We adopt the batch size of 4096. For 1-bit Adam, we follow the hyperparameters given in (Tang et al. 202I) and the full cull-irccision stage for 1-bit Adam as 16K and 23K on BERT-Base and BERT-Large. respectively. All the hyperparameters used here (e.g. learning rate) strictly follow (Tang et al. 1021) for fair comparison. For ImageNet, we follow the example script from Pytoretaana and use batch size of 256 and milestone decay learning rate schedule: starting at 1e-4 4 and decay a factor of 10 at epoch and 60, with 90 epochs total. We set 10 epochs (50050 steps) as the full-precision stage for 1-bit Adam. For GPT-2 we set batch size to be 512, and use 300K training steps (1558 tokens). The learning rate schedule follows a linear warmup of 3K steps and a single cycle consine decay over the remaining 297K steps (1 x 10 10005min min). For 1-bit Adam, we set its full- precisiccnnnn stage length be 80K steps, and for the 0/1 Adam, we follow the same learning rate based policy from BERT on T. and T..-
For GLUE benchmarks Following the setup in the BERT paper (Devlin et al. 2018)) and 1-bit Adam paper (Tang et al.) 2021), we search over the hyperparameter space with batch sizes {8, 16,32] and learning rates [1x 1001 33 10-5 5 10-5 5, 18x10--5.
Adam optimizer and perform single-task training on the dev set.
The convergence plots for GPT-2 pre-training are given in Figure
14

---

Published as a conference paper at ICLR 2023
Traiiin Loss
1-bit Adam
1000
1-bit Adam
0/1 Adam
Volidate
0/1 Adam
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
1.6
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4 1.6
Token (1ell)
Taken (1e11)
Figure 6: Training loss (left) and validation perplexity (right) with respect Tokens for 1-bit Adam and 0/1 Adam.
40
1.0
Validation Error
Training Loss
0.8
30
0/1 Adam Original Adam
0/1 Adam
Original Adam
0.4
20
0.2
0.0
10
25
50
75 Epoch
100
125
150
0
25
50
75 Epoch
100
125
150
Figure 7: Training loss and Validation enror of ResNet18 CesNee18-CIFARIO task. Hyperparameterss that not related to 0/1 Adam is set to be |learning rate: 1e 1e-4, weight decay: 5e-4). For hyperparameters associated with 0/1 Adam, use the
used in ImageNet with additional tuning.
D THEORETICAL ANALYSIS
D.1 ANALYSIS TO AN INTERMEDIATE VERSION OF 0/1 ADAM
Algorithm 4 Generic framework of applying 1-bit communication to Adam with frozen variance state. 1-bit Adam can be viewed as a special case of setting T, = ,o - -1 where To denotes its total number of steps in the full-precisio stage.
-0.
Require: initialized model worker i: ( learning rate {y mo Du total number of iterations T', decaying factor 9r, 8a from Adam, numerical constant c, variance update step index set Te. 1: for 00. do
Locally compute stochastic gradient ( over az
3:
ift To then
4:
g. = AllReduce (
Set 0.+1 32 2. (2
else
7:
9. -.-peeeessed--lleednee gg
Set 0::111120 v..
9:
end if
10:
Update momentum: m,+1 = 3mm, (1 B1)0.-
11:
Update model: (i) =x! m/ /2 tE.
12:
end for
13:
return Vi.
We start from a special case of 0/1 Adam that compresses gradients without local steps. This is given in Algorithm Note that the following proof will use Algorithm 2 to replace Compressed-AlReddce in Algorithm as introduced in Section
Algorithm Salrithmmallow Fallows us work with weaker assumption as given in the following
Assumption 6. Compression error Algorithm 4 For arbitrary Rdd there exists constant 0 < (w<+ 1, such that the output of compressor C[-] has the following error bound:
E||[[=] x=| 2 w||x:
15

---

Published as a conference paper at ICLR 2023
Theorem 2. Under Assumption !
2 and 6 let (Tol. and select 31,82 [0,1) such that
m S m -00((11))) Ie run Algorithm with a constant learning rate: for allt20
1
7t m
o2T 2 Go +e 125
then holds that
(1-w)IT 7)
m+n
BlV
VnT
where we omit f(0) fin)-inf f(x), Go., d, e, $1, B2 and L as constants.
Proof. The main update of Algorithm 4 (with constant learning rate) can be summarized as: for every t=0, 01,
m
m,m, +1m
(1-1))11))) -32) (
tET..
01+1
Vt
t Ts
m.
C++1
Ve: +C
where the 9t is the output of the 1-bit AllReduce algorithn aradientapproximaati approximation term follows:
Note that based on Algorithm 2 the
9:
(1)
8, 0
(1)
((6)
+ō. - -d+1
1
1
-
8
-
8,
8
1+1
88+1
1=1
1=1
1=1
-tt + 8, 8,+1,
where we denote
n
(8)
9:
91
11
1
8,
6
71
2=1
To prove the convergence, we now define the following auxiliary sequence: for any 220,
mm,
76,
y = 22 (1-31)
Vo,te
The rest of the proof is to use this auxiliary sequence to bound two types of steps separately. We call step as reuse step if & To and update step otherwise. We see for all the update steps, V; * vt+1 while for all the reuse steps ---1- The bounds on two different types of steps are provides by Lemma
and Lemma 6 Specifically, denoting Vi =
Fei+z
from Lemma we obtain for all the reuse steps,
Σ 1ET 4
E {x;)(1
G2 +c
(17 G (T (1- w)
2n,3m
ETT.
"In the original Algorithm 4 the is the output of the AllReduce when E E.. This, however, does not affect analysis, since proof holds for noisier case. The original Algorithm 4 mainly for practical concer avoid redundant AllReduce rounds when 1-bit AllReduce performed.
16

---

Published as a conference paper at ICLR 2023
while from Lemma we obtain for all the update steps,
E LETo 4v Gx
B|| [
B[s(w:) ([((w))-((+++))) ((1++1)]+
347
(
0
L
4 tc
4
TET
32> [1 31) VL
31 31 ((1-w)
Note that the two inequalities above hold when the learning rate fulfills
3
1
75 min
2V +C 125
Combine them together,
1(0)
(1+w) 30 dl G (T m))
Lya (I (T-
4v G2 tc
7T
335hh (1 81 )2 1-)
2n,32
34
0² G d
32(1+311)
dmL
T,
4V G +e
n1
T
(1-3))((1-))
Dropping the constants, we finally obtain
E f
=0
1(0)
722
702
wmn
71'
32m (1-31)
(1 w1-
1292
3T (1- (1 1-
'T
n'
f(00 <o
72
70?
wm
o2m
n(1- +
AI'
(1-3))
(1-31)
nT
where in the last step the condition in the theorem that B of learning rate we set
>
1
1 31. To meet the requirement
7/1 n=min
(V
n
1
02T 2L C2 +E
125
then holds that
T-
20
0
+
m+n
+ 1
T 1=
VnT (1-w)4T T
That completes the proof.
D.2 PROOF TO THEOREM
Note that the following proof will use Algorithm 2 to replace Ibit-AllReduce Algorithm T as introduced in A
Theorem 1. Under Assumption I to let (Tel select B1, B2 [0. 1) that fulfills logo - (-00//l(((())) if we run Algoritam 7 with constant learning rate: for all 12
G +e 1
= min
TT 4L GG
L
6
then holds that
T
(2 1
so
B f(
VnT
T
T
t=
(6) where ã; = -1/n and we omit ((n)-inlaeee (xx), Goo, d, Br, B2 and I. as constants.
Proof. We prove Theorem 1 Similar the proof to Theorem 2 in this proof we discuss the case of LET, and / TT, separately. Following the proof of Theorem we define the following auxiliary sequence
m
dd,
91 -. (1- B1 1-1) Vu.te
Vo,te
where
1
17
17

---

Published as a conference paper at ICLR 2023
(1)
m
71
And we additionally define that
(1)
01
11 i=1
1
9:
T1
Note that the definition of 9: is different from the gr in Theorem local models which potentially can be different before the syne step.
2 since the former is computed on
To expect compression emor bound to scale in the order of O(^²), we slightly modify the update of line 5, 9 of [ into
(4)
m (6)
t 7
U
( m
u++ Σ
- Vu,+e.
Note that since Theorem Saaeeemm[ssae states the convergence results for constant learning rate, such modification does not change the semantics of the original Algorithm Based on Algorithm we know that
U 1
+ +
8
(+
m
i 1+
+0,00
0,41 +5.
-
8t
i+1
5 de+1
3 + 8e+1.
Based Lemma 10
we know that for all the t E Te, we have the following bound.
B
2
2yo2m 106 (M A yL
Ef(E) Ef
GV +e
nL
(1-
AE
ET
2 m
G
dm
4n C +
GV
On the other hand, for all the t To. we have the following bound. /BIlVf((..)
G/
1TT
(e +T+1)(T-m)
Ef(ū:) - E+(+)+1)+
(1- /G
TT
L V o'
48 48 V/ ( (424 +
+
m2,3m
(1-31))
Note that they hold if learning rate set to be
2 G/22 + 1
75 min
4V G2 +e
L
Combine them together, we obtain
1=1 4/
+2
f(0) f(0) f
20²m
10M++1710 mLL
a2m
G2
L2Vi0
TT
nLT
8y (1-3,)
4n G G2 tel
G2 tel
n.37
18

---

Published as a conference paper at ICLR 2023
36, 3,- +c+1)
(1- +e 48 ( d+24
Ge
3T (1)
Omitting constants:
T-1
[100) 7e A²
70²
o²m
H2 m
B(V)(()))
50
+
+
+
+
T
7/T
12
n52
nTT
T
T
f(0) f(0) -f" 7 A²
70²
o m
(1- )T + m
2
<0
+T
7/
1-3
31
n11
31)
nT
where in the last step we use the condition in the theorem that of learning rate set
3
2
31.
To meet the requirement
VV
2 Go +e
1
mimi
T2T 4L
G +
6 5
then holds that
H² (
1 + T
B [(
VnT
T
t= And that completes the proof.
D.3 TECHNICAL LEMMA
Lemma 1. Consider running Algorithm 2 over a communication buffer x (same notation in
Algorithm 2
under Assumption 6 let d denote:
8 D
im1
then based on Assumption and it holds that t2 0, 2
1|²5500 C for some constant C> 0.
E15..11
w1-w)4
Proof. Note that the error is initialized by 0, so that when t = 0 the bound trivially holds. We next prove the case for t2 1.
For any iE (1, and t2 1, by the definition of the sequence 8(")
8 =F
2(10 +2
21(2 -(1 (1)
=F
2
+
(0)
(0 + ((00
Assumption
(8)
WE
w (1+1))
(i)
+ (w1+1111)10 2(20 |
Assumption
(1 (1(+ (1+1//mm)
3=0
w(1+1/1) 1-w(1+1) C.
Selecting = 1-w 2w
we obtain
|(60
2w (1+))
5
C.
(1 2
Similarly, show that for any 121,
E b.
-
Σ
+ 5
5.-1 1 zt-1
1-
7
19

---

Published as a conference paper at ICLR 2023
E
1
+
0
8
1-1
71
SwE
+ 8
2
1
(w(1+n)BBll 0 || +w(1+1/1))
sw(1+n) || + + (1+1/1)
E
||
where in the last step we apply the Jensen Inequality. Since we do not assume bound on the need to bound it in terms of
(1)
+
+
1
(1) (6) 2 +2R 0.00
22B
2
(1+w)
C+ (w(1+w) C
w1-w)² (1-w)²
((+w)) (1-w)²
C
where we apply the results from the bound on 6/ |
Given this bound, and following the analysis
for E (:00 (1) we can now bound the E 8.1 follows
2w [w(1+w) 4(1+w)2
E
6, ||
(1-w)2 (1-w)² C
8w 11 +w)
C.
w1-w)²
Finally, obtain t
1 (1)
B 2 =E
6
i=1
<2E
6,
2E
((1)
n
n
<2R
3.11
11
32w(1
+W)
(1-w)4
That completes the proof.
Lemma 2. For the variance term, we have the following upper and lower bound: for any t 2 1,
2m / tos Gz -c,
where the inequality holds element-wise.
Proof. On one hand, for any L, 511(1 where L denotes an update step, we obtain element-wise:
V, U22,20r, 2 2... 21
so that
Voite2 / 11
())= /
20

---

Published as a conference paper at ICLR 2023
On the other hand, for any t 22 and j (l,,..,d.
2
[Del] = Σ 12) -
9
S (1 82)
3/ =
1=1
k=1
so that
Vestos V G +c.
That completes the proof.
Lemma 3. In Algorithm for any t 120
195 195(1+w) dd
Bl| B||me||²=
w)
Proof. For any t 120,
E m,
2=
(1 31)
$1 9x
k=0
S(1 (11-p) 31)
81 E E
A==
<(1- 81)
81 E g + 8x 8x+1 12
EBgg
k=0
<(1 31)
8
3E
gk 1 +3E||6R 2 +x+110x++11?
n
<(1- 91
81-
3E
6 2 6 11?
71
k=0
<(1 91
8
11
9
(1)
2
+3E
0 11
+331 12
11
A=
(
192w G
S(1 31)
81
3G2 d+
(1-w)s
k=
3(1 3(1+W)&22
192(1 (02(1+4)3G2 d
20
(1
31) Σ
(1-w)
(1-w)*
195
w1
where in the step (i) we use Lemma That completes the proof.
Lemma 4. any
any a, be Rd, the following bound holds:
2
<
2
vb
b
Proof. Denote the subseript as the index of the coordinate.
d
a
<
Σ
||l|
6
Note that the second step holds not because Cauchy-Schwan Inequality but due the fact that az. by > 0 (since vb would implicitly assume so).
Lemma 5. In Algorithm 4 for all the 22 1 that fulfills 1 014 Lee., such that t & To. if we let
2V LV
21

---

Published as a conference paper at ICLR 2023
the following bound holds,
Σ
Av G +E
1ETv
227 +e(T-m)
V
(1-W +
2n/32
TT
Proof. Recall the auxiliary sequence
m
70:
y: - 2i (1- 31) 1.
Vuite'
For all the steps 12 that fulfills 1 = Ut we obtain
7
m++1
m7
6c+1
8.
yt+1
3-
v Vi+++e
ve,+c)
-7
Vu++++
Vu,tc
m
7
(1 (1-31)9; 10 mm. -1-(1111)00
Voc+ +c
(1 (1-B))oo+e
79:
Ut -
From Assumption
I
we have
Ef(y++1) Ex(()
<E(V (VVV -y)
E
E
Yt 1|
2
(y))), 9t
L
9t
=-
+
Vo
V0 +
E
(V))), fx(x)
L 2
B
g:
Vu,tc
2
Ur +c
((x.))
V((z.)
L
=-
V )
+YB
V (f(x,) vf(H.).
E
Volte
2
v 0/
=-1E
(x,)) ff()))
+yB Vz(x.) V.(()))
vVx();))
L
91
Vu:te
VU,te
2
U +
W- 2 11
Y
E
f(xx)) - (zr)
27
[
L7
9t
G2 te
21
00 +
2
where in the last step use Lemma and the fact that for any a, and 1)
(a.b) < "7 a 12
1
161
2m
Set - +E) -1, with Assumption and Lemma -
VI G +
L
E1
y:11 1
E
9t
2/ G2 +e
2,37m
/ +
(x
>L2V G2 E
7/
78,
L
9t
2/ G2 +c
2,37
(1- 11 Uz +
V +
v 01 +
V (xx))1
3 L2V G2 +e
m.
3 L2V,
G +e
2/G +c
8Th (1 (1 )1)
+e
3m
U/ +
L RR
9t
2
V
7 V f1
L2V2222 2 G
L2V2
GZ +e
I Vi 2,3
E m. 1|
E
8,
E|gge
E
2/ G2 +C
2ndh 31
32
22

---

Published as a conference paper at ICLR 2023
where in the last step we apply Lemma 2and Using the bound on the enror from Lemma and the assumption on the stochastic gradient, we obtain
1
Lemma
L 2
7
E| [
G2 te
3 L2 v Go +
B1 112 L2V3 Go
V +c
L
<B)(()) 1(16+1)]
B118,|1
83 -31)²
33
2n133
195, VV, (1+w) G do
G
Go te
329 3 L2
+ > G
te
<BI((U)- ((U+))))+
32
32 (1-w)²
L7
2n,32
227 2 (1+
G2 te +
10
{ f(y++))
52 (1 (1-31)2(1-04) w)
2n,52
Based on the learning rate bound
3
75 2V //
and summing over all the reuse steps, obtain
Σ1 y
Σ
{x;)1=
4v G2 +E
1ET.
LV, +c(T
V/202V -m)
-(f().)-
2n,5g
1ET That completes the proof.
Lemma 6. In Algorithm 4 for all th 0 that fulfills u141, i.e. tE Te, the learning rate fulfills
7 125
the following bound holds
344
)
(
Σ TETv 4 G +E
[f(x))] <
([f (30+1)++
L V +
KET.
32 (1+ (LC
3r (1-)))))(111)
Proof. For all the steps that fulfills v # 1141.
?
m4+1
mi
6.
8,41
Vi+1 y1 2++1
Et
ty
1 1-
Vu++tt
Vuitc)
Vu
Vu+tIte
m.
Mi+1
Mi
6;
sc+11
7 Ve: 1- $1
V1+1+6
Voite
0e+itt
7/81
mi
Mi41
6
8
+y
1-31 Votte 1-31 V0+++e
Vo,te
0o+i+t)
Based on the smoothness assumption, for constant 77 > that will be assigned later,
(((41)))Bf()))
<V(V ((.))(/()).)+11111 y.) - I.
2 Ellyt++1 2
77 [|[[
L BllBt+1 -1
2L
'77
1
+ 2,
27 1: 2
L
g yrl1
L
n
"
M
9e11
77 E Elg. 1| LB
1|
El v.
E
L
23

---

Published as a conference paper at ICLR 2023
E
(x:)
gt
(4)
2
77
R.
9t
(8)
+
177
/.
yr-
2r112
2
L
13
ye+1 vel1"
I
n.
187
i=1
17
G
to
LE yr
2t
L
E
M1+1
L
π
7
Now we can bound the last two terms as follows, note that
Blyy-- 2. -B
ym
70g
(1 /itt
272
E
m4
+2
(1 (1-31)²
Vut+c
2y
11222/1155 B110,11 11
2/
E m 11²
31 BTT
32"
390y² (1 (1+w) ViG
(1+
B3 (1- (1-
(1"(1-w)
454 (1 (1u)
35 (1 (L-
where in the last step apply Lemma]
1
On the other hand,
yell
y++1
7B1
m.
7
m
8
8.41
E
B1
Vutt
1-
VoL+itE
VU,+e
Vu++1+ +E
7/1
mi
mi+1
6;
8,41
<E
1 B1
VitE
Vi++1t 1-
Vutte
Vu41 +E
472
18
m4
+
IE (1- (1-81)2
422
mi+1
2
+
6,
+
8
)2
Voitc
VuL+1 +e
Vv +C
41 B9V2
V/
4/
2
Bl|mml
El B||m++1/ 11
11 7+
8 11+1?
11-31)3833
BTT
780 (1+ +w)
G
25 +w)
3 3G2dd
(1))
8
(1
R2d
<
(1-
where we again apply Lemma I and Lemma 3
Put everything together,
- Ex))
77
GG2
+n 3/: xz 112
L EE | 11 yel1
L
n
117
77
o²
+ G
454m7 (1+))(( G2 dL + 1L36
<
L
n
(1 (1) -w)+
(1- (1)
'7
02
GG2
45 1036 17
V/ dl
L
ST (1-B1))21
Set 34., and considering 7
125. we get
347
o²
32 (1 (1 &L
Ef(y.1))
+ GG
L
(1-331))
Summing over all the update steps, obtain
34>
o2m
32; (L+ G2 dmL
05 (lf()))-(y111
+ Gr.dm)
L
(1- (1-3))((111
IET
Adding G EieT, E El (xx))) 2 on both sides, and note that
E3 E
Σ
E f( 9e112
E6 El
T.
24

---

Published as a conference paper at ICLR 2023
22m m
dm,
we finally obtain
Σ
[
- (((+))))+
344
(m= +
)
00²
1V G2 Gh +e IET.
L
4 G tc
KET.
32> (1
(1 ww
That completes the proof.
Lemma 7. Under Assumption 4 for any 20, holds that
|| <
Proof.
Based on the definition of the compression error, we obtain
1
61 =E
o
<2B
21E
5
t=1
22
8,
71
<4A²
That completes the proof.
Lemma 8. In Algorithm 7 for any t 2 0, the momentum term is uniformly bounded by the following:
3
E
m
(1-B1)2
3G d
I
(4)
(1-B,)2
3G2 24241
E
mi
(1- B1)2
30 d+24A²
E
m
11
Proof. We prove this lemma via induction. Note that when -0 the inequality trivially holds due to initialization at 0 and Jensen Inequality. Now suppose the inequality holds up step 0, then for /++
if Tu then
E
m
11+
ú 1
8 8,+1
t-k k
Σ ++ + m; + 8, -8441
t-k
Σ 1==++1 (8) ai-kking
m + (1-
(1-81)
h-1 gn
+ 8:t1
t-k
25

---

Published as a conference paper at ICLR 2023
=B
8
m
1-33
81-111 9h th+ - 61+1)
t-k
j=
j=k- 1h=k
8n
1-
j-1
Σ E
mk
+(1+1/n)E
B1
gh On+(6g 8c+1)
t
k
t- k
-=++1
j=k+ 1h=
1+
E
B
m
2
311+1/n)
Σ
J-1
B
9 E
9 11
tーk k
t-k
k+1
+ + + 1/ 6011 (1/nn) - 18++111
1-1/8-1
(1+1) 3G d+24 -3(1+1/m)00,4442441111111/
(1 31
=31 3G d+24
(13
(1-3))2
3G2d4244
(1-31)2
On the other hand, ift of Tu. then
E
m (1)
=E
m
(8)
|
=E
m.m+ (4)
+(1 -1-131111 31)g )g, (8)
1+
| +(1 31 g |0 3G 3G d+2442
33,18 IE
B m
(1-3,)2
For all the 1+ case, the inequality holds trivially due to Jensen Inequality. Finally, all the bound can also be obtained via Jensen Inequality. And that completes the proof.
Lemma 9, In Algorithm 7 for all the t such that & T it holds that if we set learning rate
32
G/ +
75 min
4V - +E
L
then,
E f |1
4v G2
ET
367 (3
(T+1)(T-m)
Ef( - -Ef((++))
Go
thT
o (T
48 (T+
(+24A (1-33)
+eT
n2,3%
Proof. Since when & Te, can either belongs Tu not. We first prove the case for te Tu. From the definition of the auxiliary sequence, we obtain,
7
m
m:
(7d641 78 7ō,
U T = x.
1-31 Uu+1te
Vo.te)
(ee+ite Vu,+e)
7
-5+11 31
1ib-1-mi
Vu,tc (78141-9/4
(1- 1-Bi)vutte
7
(
-m:
(1-91) (1-3))vutte
+
-e+4 (1 (1-31)vuse Vutte
?
m++1 -m++1) Vu,te
1
(78:11-700)
=4:
mm 7
+ -m:) +
Vu.te (1-Bi)vo+te
26

---

Published as a conference paper at ICLR 2023
79c
9:-
Vu+c
From Assumption 1 we have
L
Wt) +t)+2
y1+ 11
E1
g.
=->13
fğr)) v
+ 2 +
-B f(tt).
9t)
L
B
11
Vu,
Vo +
Aa
A
A
A2
We now bound A to A4 separately. Note that from Lemma 8 the momentum term can be uniformly bounded by a constant. For brevity of the derivation, we use M to denote such constant bound, and fit in its value the end of the proof.
For A1
A
=
V +
+ V/ 16
(2)
=-
Vf(i)),
Voite
1
V
(1)
((+))
(..)) v)((z))
=->E
-713 (.
Ve:tc
Vu,tc
V((ia))
vf()t)
-yE
1 (..))
- Vf(ū.)) - -V((.))(((.))
Vottc/
Vutte
+Σ Vf x (3) - v((()t)))
((
7m1
B f( ||
7 E
+ 77/1
E ff()))) )12
G +e
2
21/1
Vittc
2
Vf(ūi) -V(ii--v((())) Vf(it)
|
- v
Vs
2
-V ((x))
E
E E
vf(Ea)1 -
E
21/1
Vott
2
21/1
Vutte
<-
MI
E V
22
E 1 5z
1|
L2222
7 L2
E| y -ell 2
G2 +e
3Thh m
2 1/1
2
where in the last step Assumption I Lemma 2 the last sync step before t is k then we have:
and Lemma 4
For the second term, denote
E
x
x
(6)
k
(6)
(#.
xx) 2
(i)
<2E
+
+2E
#
m (4)
<2
2
m
12 +C
v
(5)
m (6)
m (4)
<2 k))
E
+2 (1-
E
Vo
Vo
j=k
4 H22VVM
5m
27

---

Published as a conference paper at ICLR 2023
where the first step holds because Lemma For the third term, we have
Lemma
and the fact that at the syne step k. 0t. 3 2.
70g
E Bl
Øz 1| =1
(1- 1---BBi
VUr
V/
2V
Bl/r,l1' 11
132" - -,1))
132"
(6)
Lemma -
7
V/ M
27
.4A2
(1111113)
3
VM
132 (1
3
where we again apply the Lemma
and Lemma
Then we can get
L.
7hh
E f
1
2
(3)
22
Go
+e
35 11
Bllă:
2, m
2
4 4Y
E B( 112
7M1
Go +E
8T V/
1.1.2
M1
2/²V/M
+
2,5TTh 7h
2
8TT - (1-31)²
ST
4 H
V
B 12+
G +E
mm
1T
m,.32 3m 71.32m(1-1) (1-
m ML2
47 V
32 (1 - 3
m mm32
3
where in the second step we reuse Equation 5 Next we can bound A2 follows
91 VUL+E
2
V
(5)
gr
8m
n
2/2
T
E
V
f
(1)
n,2
1=1
V102
2I,2V1 E
2
f (z)1))
- ((t))
+
B f(:))) 2
9T
BT
V1022
V 12
||
21 2
IE V (a)
n
V12
8 ML
V E
V / (.: )1
8t
where in the sixth step we reuse Equation
For Ag.
A3 -D==-B(V/Oe) ((:).
= -V / -B V f(t))..))
vm3>00002 E V 11 712 E f()))(())))))))))) - V f(
7
El|qe
2
112
< E (
MA2L?
V
+
2
E
q 2
2
2
3hth 8,
172
28

---

Published as a conference paper at ICLR 2023
V 1/' S
M2 E V
E q
2
(1-
where in the last step reuse Equation
6 Combine the bound of A to A4, we obtain
-
MLL
7
71/2 2
G +E 7/11
E
m1 1 (1-31)²
? ViML²
473V/A22,2
3 (1 B1))
m
47 m 1?
Vn2
2
E
f
n
35
1/2 V1ML?
4ry
12 V
Y + In?
51 (1-B,)²
1/2
We set the two constants 171772 as
1
111
4v C%
/ +e
1
1/2
2/ G2 / +E
then we have,
E 1)
E V HY
V
702
GG +e
7m
2
11 31-331)
111 Vi ML2
473V2
3T (1 -,,
1h.22m
M V2
Ly
8- SYSPHMML
2
E
((=))
3T
3T
3 V1 ML2
4 V222
Y +Tg2
q:
3T -31)2
7
2I,2Vi
367 $12 ( +e+1) [(x;)
C2 +E
(1- +e
V102
+ (2
Gz
+c+ 1/111
Finally, need to bound the norm of qr. If we denote the last sync step steps before f, then,
7
(mit1-m++) m+++)
70.+1 77.
l: 2++1 le+4 (1 (1-B))vor
vu,
=b,1 3t Øt-k+1 -1t-++1 -#++3
7
( -m+++)
70,+1 76,
(1 votte
V0
Mu+4
? 111+1-1mu - -m++4
mm
Vuite
j=t-k+1 VuLte
(1-Bi)oote
mi+1 m, +1(1-31)) Σ my
(1-Bi)oott
J j
based on which obtain
E q. 2 =E
m 11++--,,+3 +2(1-11) -1) Σ my
(1-31)vorr
-+
29

---

Published as a conference paper at ICLR 2023
V/
3E m++1
11
+33
3E
m++ 7
2
+12(1-B11
Σ -=1-
E E|m
(1 - )1)2
2 (
32 (1-31)²
Put everything together, and let y fulfills
32
2V G +E
7 min
LV Go +
L
we finally obtain
7B V f()))11
36, (
+(+1)
V + n1
AV G +E
(L-B3))3
48 () Go
3Thh 31)
To this end, we have provided bound to all the syne steps with (t To and t TT)) For all the t with & To and & & Tu). they can be seen as special case of q: =0 Since A3+AA > 0, this bound will continue to hold for them, so that to sum over all the with Tu. we obtain
B V f
4 GV +e
ET
36 1 (T
Ef(ū.) - Ef((++))
00
(1) G te
tgTo
V10
487 18
d d+2442 V G3 +e(T-m-
n0,35T
3 (1 31)
where we replace M with Lemma 8 That completes the proof.
Lemma 10. In Algorithm 7 For all the t 0 that fulfills + B44 i.e. te To. the learning rate fulfills
1
7 6
the following bound holds
V
Σ
4/ G/G2++ +e
1ET.
2702m m
( )
702m
7G2 dm
nL
8T (1-13))
An G +e
4 C +e
IET
Proof. From the definition of the auxiliary sequence, obtain,
m
180+1 -
70+
Ji+I ēz+1 Et
Vo(te)
1- 31
Vo-
Vu,+e
Based on Assumption] !
-
T, TE ji++ 12
SE(V (1:)
Uz)
2
m
L
Ut+1 11:41-100 11
2L
117
m
E V
21
LE ÿ. - - 2
E 9r 1 - grl1
L
717
2177
E
プ (0)
2 E L
1 Σ
v
20!1)
1
Σg
9 (
+ LE 8. -1,1
n
n
L
+ 177
Ell@r+1 - 2
30

---

Published as a conference paper at ICLR 2023
L
[0|
2
L -
+,7
E
nL
1/7
We now bound the three norm terms separately. From Equation
we obtain for the first term,
E
32
where we again use M to denote the constant bound from Lemma for brevity. On the other hand, based on a similar derivation to Equation (6), we obtain
27 V V
E 5 zz || <
3Thh (1-3))
B
Finally, for the last norm, it's possible that the update towards L-1 step contains synchronization on the buffer. So that we need to discuss the two cases separately. First, for all the t Tu. denote the last sync step before is k then we have
E Wc+1
3e11
7
M
Vuc+e) me_
mr
)
(- 70,
78
=F
1e+1
3-
V0--1 16
/1+++++ +
V0
$7B|
#1-
1
3 1+1-+11 $
+7E
$
||
772
E
M
1-331
/u++1+
772
m
12
78
76,
2
B
+7E
+7E
1 1-31
Vuu+t +c
11+1+ +E
Vu
<7B| T141
C #1++11
12 +
2 #+4
+ +7 2
m.
7-2
m, 1
Vu +0
1- 8
1 +
772
mi
2
78t41
96
2
+7E
7
3
V Vo++
Ve++1+ +E
V2
<7B
Σ
jj=t 1+1 7
+8,- 8141
+7E
k+1 m
+ 2
m
Vuk+e
0k
v 1
7-2
M
7 EE
m
78
78,
+
+7E
+7B
1 31
Voi-tt
11 31
U/ +
+
11: +c
105 2 H2V, (M (M+ 22
<
(1-8))
where in the last step we use Lemma 7
It is straightforward to verify that this bound also holds for t & Tu (since there will be noise from the sync step). Combine the three norm term bounds, we obtain
and 4
Ef(0++1) Eff
2/7 L
E
i
x
(1)
2 21770"
+
+E - 2,112+ E 1111++11 2
nL
177
1=1
8 HV 2m7
V/
1/
nL +mL (1-
-1,
3
n1 (1-B1)²
207r02
18
V
nL
(1-(1-11)
2x0 nL
106 H2V, (M+
33 (1-31)2
where in the last step we set 17= and use the requirement that y < 1/6. Summing over all the t Te. we get
2702m 2
10 V
05
-f -Ef(
nL
AT (1- (1-31)
TET
31

---

Published as a conference paper at ICLR 2023
Adding
1/ ITT
E
E
both sides, and note that
[
B
Σ
g.1l++ +
Σ
E
BE
BET
o m
2
We finally obtain
[
Σ 1ETv
4/ Gg +e
2
7 dm
Ef(ū)) Ef(ū++1)+
+
nL
-1-
/
4V
TET. That completes the proof.
32


Reviews:
[{"review_id": "uIV2hkflZAz", "reviewer": "Reviewer_en2k", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors proposed 0/1 Adam to reduce communication during training. 0/1 Adam addresses the existing issues by adaptively freezing variance and linearly approximating momentum and parameter update locally. The authors provide theoretical convergence guarantee and experimental results on large-scale training tasks, showing that the proposed optimizer can achieve similar accuracy compared to fp16 training at a higher throughput. ", "summary_of_the_review": "Generally, I think this is a good paper. It contributes to the distributed training area by reducing communication to increase throughput. The method outperforms existing work by further reducing the high-precision training steps. My only concern is the difficulty of hyper-parameter adjustment. ", "strength_and_weaknesses": "Strength:\n1. Firstly, the paper is generally well-written and easy to follow. \n2. The evaluation is comprehensive. The authors provided experimental results on language model training (transfer learning and zero-shot evolution) and ImageNet classification, where the proposed optimizer can match the performance of fp16 Adam. \n3. The proposed method achieves higher training throughputs across different benchmarks and hardware setups, which seems to be pretty general.\n4. The motivation of the method is \n\nWeakness:\n1. The adjustment of hyper-parameter T_v and T_u seems a bit non-trivial (especially the latter one). Can the author confirms that the same hyper-parameter can scale across model scales without careful tuning? For example, does the same hyper-parameter scale to training on the CIFAR dataset with the same learning schedule?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NruMwPBHgI8", "reviewer": "Reviewer_SjhX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "With the deep-learning revolution, large-scale training has been at the forefront of innovation. As the data sizes grow, the training time and cost explode. There have been techniques such as compression and bit quantization to alleviate these problems. These techniques work well in linear information but not in non-linear information. The paper proposes a new method called 0/1 Adam, leveraging insights within updates and stationary via steps. \n", "summary_of_the_review": "The paper focuses on an important problem to speed up model training. Though there are some minor limitations on generalization, I think it is good enough to be represented in the venue. I wanted to vote 7/10 (but only 6 or 8 are available). ", "strength_and_weaknesses": "They provide convergence guarantees with theoretical analysis and experimental results comparing 1-bit Adam on language modeling training and image-net training showing a much faster reduction in training loss in both cases. The authors also open-sourced their algorithm. \n\nOne missing piece in this setup is the generalization, I think. I believe the experimental setup might be decent, and the problems are large enough to demonstrate efficacy. But I am not sure about the broader applicability to various other applications of AI, such as siamese networks (wide-and-deep models) or GANs, where the scale might come from a different angle than language models.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5UZoYuB0nAu", "reviewer": "Reviewer_LNoo", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces 0/1 Adam, a variant of the 1-bit Adam algorithm.  While the 1-bit Adam algorithm leveraged a fixed burn-in period wherein vanilla Adam was run before the variance term stabilized and was frozen, 0/1 Adam proposes an adaptive variance-freezing policy.  Additionally, 0/1 Adam leverages local SGD wherein synchronicity rounds among workers are skipped.  Convergence results similar to 1-bit Adam are provided for 0/1 Adam, and experimental results showing the efficacy of the algorithm for Imagenet and BERT are provided.", "summary_of_the_review": "The paper makes some natural extensions to the 1-bit Adam algorithm, while providing convergence guarantees for the resulting 0/1 Adam algorithm.  Furthermore, the results seem compelling.  However, the presentation of the paper's novelty and contributions requires serious reevaluation.  Also, the general presentation and writing has significant room for improvement, particularly discussion of the presented results.  Important key details regarding figures are lacking or insufficient to understand exactly what is being stated.  Finally, while the extensions made from 1-bit Adam to produce 0/1 Adam make intuitive sense, it is unclear how exactly these are (or can be made) adaptive in practice, particularly given their predefined values in Algorithm 1.", "strength_and_weaknesses": "Strengths\n-The paper extends 1-bit Adam in a natural and intuitive way.  Both adaptive variance-freezing and local SGD are promising directions to improve the original 1-bit Adam algorithm\n-The results are compelling\n\nWeaknesses\n-Presentation of results could be significantly improved (see clarity section for further information).\n\n-The writing and description of the novelty of the presented work requires extensive reevaluation.  The description of 0/1 Adam as a novel algorithm is not correct, it builds upon 1-bit Adam (also borrowing a large amount the analysis from the corresponding paper) and this point should be made clear throughout the paper (however, adaptive variance freezing is an important and novel contribution to the 1-bit Adam algorithm). Furthermore, 0/1 Adam is not the first work to consider local SGD for distributed algorithm.\n\n-Even after reading the paper, it is unclear how adaptive variance-freezing or local SGD (i.e., skipping rounds/local steps) may be set in practice.  Indeed, these two policies must be known \\emph{before} running Algorithm~\\ref{1}.\n\n-Claims are made without substantiation or are misleading.  E.g.:\n\n         1) \"the change of variance over steps in Adam is generally smooth\" <- Please substantiate this claim.  In the 1-bit Adam paper, they \n              assumed this was the case and stated so explicitly.\n\n         2) \"While this paradigm avoids compressing non-linear information with a one-time frozen variance, the experimental results from \n             (Tang et al., 2021) indicate the fullprecision stage still incurs non-trivial overhead.\" <- Overhead discussed in the paper was with \n              regards to vanilla Adam.  Please remove this claim or provide additional evidence to substantiate it\n\n         3) \"Furthermore, 1-bit Adam is restricted in the scope of gradient compression, and cannot be trivially adapted when other \n              techniques are used, such as local steps.\" <- In the 1-bit Adam paper, several variants were \n              implemented and contrasted against, including compressing the gradient and compressing the momentum.  Why can it not be \n              trivially adapted?  Furthermore, how to leverage local SGD with Adam is not an open problem, previous work in [1] has tackled \n              this. 1-bit Adam could trivially be combined with CADA.  Please reassess, and support, your claim.\n\n         4) \"Besides, the empirical success of (Tang et al., 2021) was not substantiated on generative models (GPT-style models), for instance, \n              175B GPT-3 Brown et al. (2020), 530B MT-NLG Smith et al. (2022), etc.\" <- This is disingenuous; 1-bit Adam was evaluated on \n              GANs (generative model) as well large-scale models (BERT).  530B MT-NLG Smith et al. was also \n              published after the 1-bit Adam paper, and neither GPT-3 no MT-NLG are evaluated using 0/1 Adam.  I would recommend revising \n              this claim, as well as elaborating why BERT is not a significant enough benchmark that GPT model evaluations are required.\n\nReferences:\n[1] Chen, Tianyi, et al. \"Cada: Communication-adaptive distributed adam.\"\nInternational Conference on Artificial Intelligence and\nStatistics. PMLR, 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster