Communication Efficient Distributed Training with Distributed Lion
Authors: Bo Liu
Lemeng Wu
Lizhang Chen
Kaizhao Liang
Jiaxu Zhu
Chen Liang
Raghuraman Krishnamoorthi
qiang liu
Venue: NeurIPS 2024 poster (2024)
Keywords: Distributed Optimization
Primary area: infrastructure
TL;DR: We introduce the distributed version of the Lion optimizer with efficient binary/low-precision communication. We provide both theoretical and empirical evidence to demonstrate it is a simple yet strong method.

Abstract: The Lion optimizer has been a promising competitor with the AdamW for training large AI models, with advantages in memory, computation, and sample efficiency. In this paper, we introduce Distributed Lion, an innovative adaptation of Lion for distributed training environments. Leveraging the sign operator in Lion, our Distributed Lion only requires to communicate binary or lower-precision vectors
between workers to the center server, significantly reducing the communication cost.  
Our theoretical analysis confirms Distributed Lion's convergence properties. Empirical results demonstrate its robustness across a range of tasks, worker counts, and batch sizes, on both vision and language problems. Notably, Distributed Lion attains comparable performance to standard Lion or AdamW optimizers applied on aggregated gradients, but with significantly reduced communication bandwidth. This feature is particularly advantageous for training large models. In addition, we also demonstrate that \mavolion{} presents a more favorable performance-bandwidth balance compared to existing efficient distributed methods such as deep gradient compression and ternary gradients.

Distributed Lion for Communication Efficient Distributed Training
Bo Liu"
Lemeng Wu"
Lizhang Chen'
The University of Texas at Austin bliudcs, utexas.eccoo edu
Meta AI
The University of Texas at Austin
1mwu@google.co com
1zchen@utexas.cm edu
Kaizhao Liang
Jiaxu Zhu Meta AI
Chen Liang
The University of Texas at Austin kaizhaol@utexas.
Google
jiaxuzhummeta.com com
crazydonkeyygooggee.co com
Raghuraman Krishnamoorthi
Qiang Liu
Meta Al
The University of Texas Austin lqiang utexas. edu
raghuramandmeta..cm com
Abstract
The Lion optimizer has been a promising competitor with the AdamW for training large Al models, with advantages in memory, computation, and sample efficiency. In this paper, introduce Distributed Lion, innovative adaptation of Lion for distributed training environments. Leveraging the sign operator Lion, our Distributed Lion only requires communicate binary lower-precision vectors between workers to the center server, significantly reducing the communication cost. Our theoretical analysis confirms Distributed Lion's convergence properties. Empirical results demonstrate its robustness across a range of tasks, worker counts, and batch sizes, both vision and language problems. Notably, Distributed Lion attains comparable performance to standard Lion or Adam optimizers applied on aggregated gradients, but with significantly reduced communication bandwidth. This feature is particularly advantageous for training large models. In addition, we also demonstrate that Distributed Lion presents more favorable performance- bandwidth balance compared to existing efficient distributed methods such as deep gradient compression and ternary gradients.
Introduction
The pursuit of modern artificial intelligence hinges on the training of large-scale models like large language models[28] and large vision models (LVM)200). As the stakes in terms of time, cost, and environmental impact grow ever higher for training expansive Al systems, the hunt for efficient optimizers becomes critical.
Recently, a new optimization named Lion (evolved sign momentum) [11] has been discovered with an evolutionary program. It was shown that it exhibits performance par with the current state-of- the-art Adam W [26] across a wide range tasks, while reducing the memory cost and training time.
'Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

workers
binary low-precision
server
82,t
03.L
maj. vote
average
Figure Illustration of Distributed-Lion. Each worker keeps its own optimizer state and applies the Lion optimizer individually to a binary update d,,, = Lion(x, D:) (without the weight decay), then the server aggregates all & to produce binary A: by majority vote (or an integer Ae by averaging) and send it back to all workers. The workers then apply A, and weight decay update their model parameters (Algorithm 1).
Consider optimizing a loss function fD(() on R2 with a dataset D, the update rule of Lion is:
M 82m; + (1 V/((t),
5. = Lion F4, D) def sign(3mm + (1 V))((()))
(1)
Tt+1 I₁ - <6; + Xx:),
where my plays the role of the momentum, is the learning rate, 81 [0, 1J2 momentum related coefficients, and À 2 0 is the weight decay coefficient. Comparing Lion against Adam one observes that Lion only requires the storage of the first-order momentum term, which results in more relaxed memory requirement.
In this study, we tailor the Lion optimizer for distributed training. The Lion optimizer is particularly suitable for this context due to two main attributes: (1) its simple update mechanism that relies solely on first-order momentum, and (2) its of the sign(-) function. We showcase the effective employ- ment of the sign(-) ) function to streamline communication processes, leading to the development of a novel distributed training framework named Distributed Lion. Within the Distributed Lion framework. each participating worker independently adjusts the model parameters using a distinct instance the Lion optimizer, thereby maintaining separate optimizer states. A distinctive feature of this framework the mode communication between workers and the central server, which is restricted to binary or low-precision vectors.
Crucially, in this setup, workers convey updates rather than raw gradients to the central server. The server, in turn, aggregates these updates through either straightforward averaging process (Distributed Lion-Avg) or a majority voting mechanism (Distributed Lion-MaVo). In the case of Distributed Lion-MaVo, the consolidated update is maintained as binary vector, whereas for Dis- tributed Lion-Avg, given the presence of workers, each element of the update vector encoded using Iog(n) bits. This approach markedly reduces the bandwidth requirements compared to tradi- tional distributed training methods, which typically rely on nigh-precision floating-poin vectors for communication. The bandwidth efficiencies achieved by method are detailed in Table 1. Our contributions are: 1) We introduce the Distributed Lion algorithm, simple yet effective approach extend Lion to distributed training, where all communications between workers and the server are done through binary or low-precision vectors (Section 2); 2) We provide theoretical analysis ensure the convergence of Distributed Lion (Section 3): 3) Empirically, we demonstrate that both vision and language modeling tasks, Distributed Lion achieves comparable performance against applying Lion and Adam with the synchronized gradients from all workers. while being significantly more communication efficient. In addition, we show that Distributed Lion achieves a better trade-off than existing efficient distributed training methods like deep gradient compression [24] and ternary gradients [36] (Section 5).
"Chen al. [11] suggests (Bi 0.9, 82 0.999 based empirical findings.

---

Bandwidth Requirement
Method
-Severr
Server-> >Worker
Global Lion/Adam
32d
32d
TemnGrd [36]
(1 - 1)) log(2n (2n 1)d
1.5d
DGC [24]
32d
Distributed Lion-Avg
d
log(n)d
Distributed Lion-MaVo
Table 1: Minimum bandwidth requirements of different methods for model with parameters and workers.
Deep Gradient Compression (DGC), 1) denotes the compression rate (default: 1) = 0.96).
2
The Distributed Lion
We introduce the distributed learning problem and then our Distributed Lion framework.
2.1 Distributed Training
In distributed training. we aim to minimize the following learning objective:
Σ Be ((o::))) N
1
min F(x)
Here, N denotes the number of workers. {D,} are N datasets." 3 and æ the model parameter (e.g.. the weights of a neural network). In the distributed learning setting, each worker i E [n] will get its own dataset Dr, and we assume there is a centralized server that all workers can communicate with. The simplest distributed training technique is to perform distributed gradient aggregation:
Di. where 9: = -E (x;](
Jverver
Here, each local gradient y: is an unbiased estimation of the true gradient V, F(r) when D, are i.i.d. drawn from the same underlying distribution. The server aggregates all local gradients into Iserver- and then applies optimizer like Adam [19] on top of Jerver- However, the aggregation step requires communicating the full gradient vectors gr. which can be expensive for large models.
Notation. Given a function fæ; {), the gradient V fz {) is taken with respect to variable a. We use ||- II. ||- II1. and Il denote the lz, l,, and for norm, respectively. & is the sampled data at time for the i-th worker and 9.,t = V f(ri Er,)) We similarly denote 2 as any variable 2 at time t from worker i.
2.2 Distributed Lion
The main idea of Distributed Lion to leverage the binary nature of the Lion's update for efficient communication. To enable that, want the workers to only send the binary updates the server. As a result, we let each worker keep tracks of its own optimizer state, i.e., the momentum m,,r- Then at each step, each worker first computes:
mi,+1 = B2ms, + (1 - (1-82)gm 82)
8 sign(3 mi, + (1 31)g..).
Then all workers send the d,, back the server. The server receives the binary "updates" from all workers and then aggregates them. Here, we propose two simple ways for aggregation. Denote S, = En 8i,, which is vector of integers in (O....N) N). Define the aggregation as follows:
2/4 St
(Averaging)
A aggregate
(5)
sign(S.)
(Majority Vote)
'Thooughout this work, we assume (D.) consist of i.d data samples, & sampled from D, is i.idd though method should be directly applicable non-i.i. data.

---

Algorithm Distributed Lion Training
Initial parameters 20 Rd. datasets (PI..... ... ]r loss function f. learning rate c, hyper-parameters 31, $2 E [0, 1] (default to 0.9, 0.99)", and the weight decay A.
Inputs:
Initialization: = 0, Vi, ma,0 = O, and 20,0
while not convergent do Worker-side: Each worker samples batch Eú,t E D,, computes the following, and sends 6,, to the server:
ift 0, Fi,t 3i,-- < (A -
X
d1,1 sign (3 + - of
m4++1 f2m., + (1
Server-side: The server computes the aggregated update A and broadcast it to all workers:
die) sign di.s)
(Averaging) (Majority Vote)
A, =
and t t ++1
end while
So we simply average or take the majority vote from all {ōt,))- Here, we denote binary vectors in magenta and low precision vectors cyan. the end, the server broadcasts A, back to each worker and each worker performs Zi.+1 Fi, e(A, Xxi,),, where is the step size and À is the weight decay coefficient.
Communication Cost In both variants of Distributed Lion, the N workers only need to send the binary vectors &G,, the server. The server then sends the aggregated update A, back to the workers. which is binary when using the majority vote aggregation, and an integer in {O..... .N3 when using the averaging aggregation. Note that an integer in (0...., N) can represented by at most log(N) bits. In practice, usually N < 232 hence log(N) < 32 and we still save the communication bandwidth even with the average aggregation, comparing against communicating with floating point numbers (Check Table 1). The full Distributed Lion algorithm is summarized in Algorithm 1.
3 Theoretical Analysis
We provide theoretical analysis of the Distributed Lion algorithm, both with the averaging and the majority vote aggregation methods. In the following, we first describe that the distributed training problem be viewed as a constrained optimization problem when Distributed Lion is used. We provide convergence results for Distributed Lion with both aggregation methods.
3.1 Lion as Constrained Optimization
Chen et al. [10] showed that the (global) Lion is a theoretically novel and principled approach for minimizing general loss function fxx) while enforeing box-constrained optimization problem:
min (x: s.l. || S 1,
ZERd
where the constraint is introduced due to the use of the weight decay coefficient X. Moreover, Chen al. [10] showed that the Lion dynamics consists of two phases:
[Phase 1] When the constraint not satisfied, that is, x & F, where F is the feasible set F def (x: ||xello < 13. it exponentially decays the distance to F: 3 E (0, 1), such that dist F) S a (I;,
where n 2 O. Hence, x, converges to F rapidly and stays within F once reaches it.
2) [Phase 2] After Aoz enters F. the dynamics minimizes the objective [(z) while being confined within the set F. This step proved in [10] by constructing a Lyapunov function when sign(-) treated the sub- aub-gradient of convex function.

---

3.2 Convergence Analysis
In this section, we analyze the convergence of distributed Lion algorithms. Similar to the case of global Lion, we show that distributed Lion also solves the box constrained optimization (6), Its dynamics also unfolds into two phases aligning with Lion's dynamics: Phase I shows rapid convergence to a feasible set F, while Phase II seeks to minize the objective f(z) within the feasible set F.. Different from the Lyapunov approach used Chen et al. [10], the proof of our Phase result is made by introducing a surrogate metric ((x) of constrained optimality, and providing upper bound of S (xx, following the algorithm. Our analysis makes the following assumptions.
Assumption 3.1 (Variance bound). D; is ii.d. drawn from common distribution nu. and the stochastic sample Ç¹ D, is iidd. and upon receiving query x E IR, the stochastic gradient oracle gives us independent unbiased estimate V (x {*) from the i-th worker that has coordinate bounded variance:
[x - vf(z). EE (IV V(()) So²
Assumption 3.2 (Smooth and Differentiable J) Function f()) differentiable and L-smooth. Assumption 3.3 (Bias Correction). Consider the sequence (m])rsassEM)) generated by Algorithm 1, E(mne//[(ssgnnmmt)) 2 0.
Note that assumption 3.1 and 3.2 are standard in the analysis of stochastic optimization algorithms [8, 34J. When Assumption 3.1 holds, x Ei V f( [z))] < o² /N. In distributed training setting, m.,, 12,,,. ... M.N, are i..d., so E[3im,, (1 31) and E[sign(mii+ don't 't depend on Assumption 3.3 evaluates the discrepancy between the expected value and the expected sign of measure, positing that the expected values of mi and sign(m;) ought share the same sign.
We now present our results. Similar to the case of global Lion, the dynamics of distributed lion can also be divided into two phases depending on if the constraint F is satisfied.
Phase I (or F) line with the behavior observed the global Lion, when the constraint not satisfied, both variants of distributed Lion decrease the distance the feasible set exponentially fast.
Theorem 3.4 (Phase D). Assume f: Fd - R L-smooth, B1, 32 E (0. 1), and B2 > B1, and e, À Let (Iz)120 be generated by Algorithm 1. Define F {z: || 1}. and dist(r,, F)
infzer = æell w.r.f. any norm |1-1|- For any two non-negative integers S t, then Vi S t, we have
dist(æ,, F) s (1 - ddst=
Hence, Ia converges to F rapidly and stays within JF once it arrived.
Phase II (x E F) Now, we present the main result of the analysis for Phase II in Theorems 3.6, 3.7, and 3.8. We start with introducing a surrogate metric that quantifies the optimality of the solution within Phase II:
S(x) (z) Vf(x)) + Ar).
Let's delve into the implications of S(x) =0 0.
Proposition 3.5. Assume is continuously differentiable, À > 0, and Axeloo S Then S(x) 0 implies a KKT stationary condition of ming f=x) ) s.t. ||Ax|l.o S 1.
This KKT score (7) is tailored to encompass the stationary solutions of the box constrained problem as described in (6). Building on this, we then proceed to analyze the convergence for the majority vote, averaging, and global LION strategies throughout this section.
Theorem 3.6 (Majority Vote). Assumptions 3.1, 3.2, and 3.3 hold, consider the Majority vote scheme in Algorithm 1, B1, B2 E 10,1), and B2 > 3r, and a < 2 d3, ( [ |] < S T, and e, >>> O. Let (zz)12 be generated by Majority Vote, and is in Phase II: [|raa oc I 1 for all t.
We have
[(x0) S 2D3, / (
48, 2ydo + VC) 2p
B[S(x:))
+2Led,
T
Tc
T(1 - 82) 1-32
VN
(8)
5

---

where C= (91 -2)
1 + (1-B1)². 1+.0
and D (f
S0
if Blsign(mi)+ [b]] 0.
PrlK]
El | (
otherwise
and maxigisT lpeell-
The result above shows that T EE= E[S(z)) decays with a rate of O + T(-))))) +ct vx²))
This rate is in fact on par with global Lion as we show in the following result.
Theorem 3.7 (Global), Assumptions 3.1 and 3.2 hold, Consider the scheme in Algorithm (16) with the same settings Theorem 3.6, we have
T T E[S(x:))
L f(00)-5 2
2(1 31)
+
+ 2Le.. (9)
Te
T(1 32)
1 1 1-82
VN
Theorem 3.8 (Averaging). Assumptions 3.1 and 3.2 hold, consider the Averaging scheme Algo- rithm! 1, with the same settings in Theorem 3.6, we have
1 T
- f
23,32v f
43 Led
231 do
E[S(x:)
+2
Te
T(1 52)
1- B2
vI B2
(10)
The Averaging method's convergence bound doesn't improve with more workers since + EEw sign(6 (6,,) doesn't approximate sign(E== 61,) effectively, unlike the Majority Vote's ap- proach sign EE= sign(
4 Related Work
this section, we provide a summary of optimizers that use the sign function and existing literature on bandwidth-friendly distributed training.
Sign Operation in Optimization The sign operation is integral to optimization for several reasons. Primarily, it acts normalization mechanism by disregarding the magnitude of gradients, thereby cquilibrating updates across different dimensions and potentially facilitating the avoidance of saddle points. Additionally, the binary nature of the sign function's 's output significantly reduces the memory footprint required for storing gradient updates. The concept of sign-based optimization dates back to RProp [30] and has seen renewed interest with the advent of SignSGD and its commentuu--nhaaneee variant, Signum [4]. more recent advancement the generalized SignSGD algorithm introduced by [14], which incorporates preconditioner, making it superset of SignSGD and akin to Adam in certain aspects. A noteworthy addition to sign-based optimizers the Lion optimizer, which emerged from evolutionary program search, achieving performance comparable Adam [19] and Adam [26] for the first time. Lion distinguishes itself from Signum by employing a different convex combination for outputting local updates, technique referred as the double-3 scheme, reminiscent of Nesterov's 's momentum update, and encapsulates Signum as particular case. On the theoretical front, SignSGD and Signum have been shown exhibit convergence rates comparable to traditional SGD [4]. Recent work by [34] has extended the theoretical understanding by providing convergence theory that relaxes the requirements for bounded stochastic gradients and enlarged batch sizes. Additionally. Lion has demonstrated its capability in performing constrained optimization under the fox -nor constraint [10].
Distributed Training In addressing the communication constraints of distributed training, the research community has devised several innovative strategies, prominently featuring asynchronous Stochastic Gradient Descent (SGD), gradient quantization, and sparsification techniques. Asyn- chronous SGD offers a solution by enabling parameter updates immediately after pack-propagation, bypassing the need for gradient synchronization, thereby expediting the training process [9, 40, 25]. Li et al. [21] utilizes sketch-based algorithms for lossless data compression [23], achieving an asymptotically optimal compression ratio [22]. However, its applicability is limited to highly sparse

---

gradients, making it orthogonal to our research. In the realm of gradient quantization, methods such as 1-bit SGD [33]. QSGD [2], and TernGrad [36] are pivotal. These approaches compact the gradient data, substantially reducing the required communication bandwidth, with 1-bit SGD demonstrating tenfold acceleration in speech applications and both QSGD and TernGrad confirming the feasibility of quantized training in maintaining convergence. Moreover, gradient sparsification further mitigates the communication load by transmitting only the most substantial gradients. Techniques like threshold quantization and Gradient Dropping [1] exemplify this, with Gradient Dropping notably achieving 99 reduction in gradient exchange with minimal impact on performance metrics, such as a mere 0.3 loss in BLEU score for machine translation tasks. The recent Deep Gradient Compression (DGC) strategy [24] also contributes to this field by incorporating momentum correction and local gradient clipping among other methods to maintain accuracy while significantly reducing communication demands, albeit at the cost of increased computational overhead. Compared to gradient quantization methods, Distributed Lion uniquely leverages the binary nature of Lion's update and can be viewed as performing quantization on updates rather than the gradient.
5 Experiment
In this section, we perform a thorough evaluation of the Distributed Lion algorithm, employing both the averaging and majority vote aggregation methods. The design of our experiments is aimed at addressing the following questions to ascertain the algorithm's 's efficacy and performance:
(Q1) How does Mavolion perform in comparison to traditional global distributed training methods, which aggregate gradients from local workers to apply an optimizer to the collective gradient?
(Q2) How does Mavolion measure up against established methodologies known for their communi- cation efficiency in distributed training?
(Q3) How does Distributed Lion scale on large vision or language problems?
5.1 Comparing Distributed Lion Against Established Methods on CIFAR-10
To address Q1 and Q2, we compare Distributed Lion with both the averaging and the majority vote methods, against established low-bandwidth distributed training techniques and the global distributed training methods. We consider the following baseline methods: 1) Global Adam where we apply AdamW with the averaged gradients from all workers. 2) Global Lion (G-Lion), where we apply Lion with the averaged gradients from all workers. Note that Global Adam W and Global Lion serve as the performance and communication upper bounds. 3) Distributed Lion with Averaged Updates (D-Lion (Avg)), In contrast to the majority vote mechanism used in Distributed Lion, this variant averages the binary update vectors from all workers. While D-Lion (Avg) might offer improved performance in principle, it comes at the cost of non-binary communication from the server to the workers. 4) TernGrad [36]. The main idea is to tenarize the gradient into a vector of (, 1}. which is similar to what Lion does. But this process is done on the gradient level instead of on the update level 5) Gradient Dropping (GradDrop) [1]. The main idea is to drop insignificant gradient entries and only transmit sparse gradient signals. 6) Deep Gradient
W,,,
Compression (DGC) [24]. DGC is built on top of the GradDrop, but additionally applies momentum correction, local gradient clipping, momentum factor masking, and warm-up training.
Experiment Setup For GradDrop. DGC, and TernGrad, we choose the compression rate of 0.04 (note that 1/32- = 0.03125) to match the bandwidth of the D-Lion (MaVo). We conduct experiments on the CIFAR-10 dataset using a vision transformer (ViT) with 6 layers. 8 heads, and hidden dimension of 512. This is because ViT has arguably become the most widely used architecture in computer vision, and we empirically found no additional gain in performance when using larger ViT on CI0 In addition, to validate how Distributed Lion performs with different numbers of workers, we consider & {4.8, 16, 32), each worker at each step samples an i.i.d batch of size 32.
We list the optimal hyperparameters selected for each method from Figure 2 Table 4. The learning rates are selected from (0.00005, 0.001, 0.005, 0.01} and the weight decays are selected from f0.0005, 0.001, 0.005). For each experiment, we use a cosine learning rate scheduler and run for 200 epochs, and ensure that in cach epoch, each local worker sees the entire dataset once.
7

---

G-Lion
G-AdamW
GradDrop
DBC
TerGGrd
D-Lion (Aug)
D-Lion (MaVo)
k
4
k 16
32
90-
90-
80-
70
70
60
40
40
150
200
5.0
100
200
50
100
150
200
100
130
200
Epoch
Epoch
Epoch
Epoch
Figure 2: Performance of Distributed Lion v.s. baseline distributed optimizers on CIFAR-I0 with 4, 8, 16, and
32 workers, cach worker at each step runs local batch with size 32. All results are averaged over threc sccds.
Each experiments are conducted with three random seeds {42, 52, 62), which results in total of x 84 experiments.
G-Lion
Error (1 Accuracy)
20.0
G-Lion
G Adami
Performance
87.5
G-AdamW
GradDrop
17.5
TennGrad
GradDrop 96)
85.0
DGC
15.0
D-SIGNUM (Avg)
DGC (0.90 (6)
TemGrad
12.5
D-SIGNU
82.5
Lion (Avg)
Di Lion (Ava)
80.0
D-Lion (MaVo)
10.0
D-Lion (MaVo)
Bits / Iteration
Number of Workers
Figure 4: Test Error v.s. Communication Bits Itera- tion (closer the lower-left is better). Note that set G-Lion and G-AdamW are both because they re- quire 32 bits per parameter, and there are both worker- to-server and server-to-worker communications.
Figure 3: Performance of G-Lion, G-AdamW, Grad- Drop, DGC, TernGrad, and D-Lion (Avg/MaVV) v.s. the number of workers k.
Observation We plot the testing accuracy (Test Acc.) over epochs for different methods in Figure 2, the best testing accuracy of different methods over the number of workers in Figure 3, and the performance versus per-iteration bandwidth in Figure 4 when using k = 4 workers. From the above plots, we make the following observations.
Compared to global methods, D-Lion (MaVo) performs on par with G-Lion. D-Lion (Avg) performs slightly worse than G-Lion but is on par with G-Adamw (Figure 2).
Compared to established communication efficient methods, both D-Lion (MaVo) and D-Lion (Avg) outperform GradDrop, DGC and TernGrad by a large margin (Figure 2).
We observe that both D-Lion (MaVo) and D-Lion (Avg) exhibit strong performance while being 30x more communication efficient than global distributed training methods like G-AdamW. To broaden our comparison, we introduced two additional baseline methods: D- SIGNUM (Avg) and D-SIGNUM (Ma Vo). These baselines apply proposed techniques to the SIGNUM framework instead Lion.3 5 We set 3 = 0.99 for D-SIGNUM. According to results, depicted in Figure 4, these baseed methods do not perform well as their Lion-based counterparts.
We notice that the overall performance of the same optimizer is worse as l is larger, this is consistent with the observation made in DGC [24]. We hypothesize that this may be due the larger effective batch size resulting in smaller stochasticity, which is consistent with why D-Lion (Ma Vo) performs bit better than G-Lion on CIFAR-10 (Figure 3).
Note that D-SIGNUM (Avg/MaVo) further subsumes D D-SignSGD [S, 6].

---

5.2 Scale to Larger Models on Larger Datasets
To answer Q3, we validate Distributed Lion on several large-scale setups including both vision and natural language processing tasks. Under this setting, we compare D-Lion (MaVo) and D-Lion (Avg) against G-AdamW and G-Lion. For the vision task, we tested ViT-S/16 [16] and ViT-B/16 on the ImageNet- K [31] classification benchmark. For the natural language processing task, we perform both language pretraining and finetuning tasks. This because Lion has shown good results on language modeling. For the language model pretraining task, we pretrain GPT2++ [29] (the GPT-2 model with modern training techniques adopted from the LLaMA model [35]] on the OpenWebText [17] benchmark, for both 350M and 760M size models. For the language model finetuning task, we conduct few-shot finetuning of the LLaMA 7B model [35] and evaluate the models' downstream performance standard downstream evaluation benchmarks [13, 37, 12, 27, 32].
For the Image benchmark, train all methods for 300 epochs, using a global batch size of 4096 and data augmentations MixUp [39] of 0.5 and AutoAug [15]. When training ViT-S/16, we use a learning rate of 3e for G-AdamW, with betas of (0.9, 0.999) and weight decay of 0.1. For G-Lion, D-Lion (MaVo), and D-Lion (Avg), we use a learning rate of 3e betas of (0.9, 0.99). and a weight decay of 1 1.0. As for ViT-B/16, we use a learning rate of 1e-3 for G-Adam W. with betas of (0.9, 0. 0.999) and a weight decay of 1.0, while for all Lion variants, we use a learning rate of le- 4 betas of (0.9. 0.99), and a weight decay of 10.0. For pretraining language models on the Open WebnWeeText dataset, we build GPT2++ models using the original GPT2 model, but with modern training techniques from LLaMA model, including using the Gated Linear Unit activation for the multilayer layer perceptron layers (MLPs) and the RMSNorm [38] instead of the LayerNorm [3]. Following the Chinchilla scaling law [18), we trained the 350M model for 14,000 iterations and the 760M model for 30,000 iterations, both with 1,024 tokens. For G-AdamW, use learning rate of 3e betas of (0.95, 0.99), and a weight decay of 0. For all Lion variants, we use a learning rate of 9e betas of (0.9, 0.99), and weight decay of 1.0. All the models are trained under a global batch size of 480. For the instruction finetuning task, we instruct finetune a LLaMA 7B model for 3 epochs with batch size 32. We use 2e-5 learning rate, betas of (0.9, 0.999), O weight decay for G-Adam and 6e-6, (0.9, 0.99) betas, 0.01 weight decay for all Lion variants. For all pretraining experiments, we use 4nodes x Sgpus 32 workers. For instruction finetuning experiments, we use 4 workers per experiment.
Experiment Setup
Table 2: Results ImageNet classification and WebTWe language modeling. For ImageNet experiments, report the Top-I accuracy. For language modeling experiments, report the validation perplexity. The best performance marked with bold text, the second best with an underline.
Image Classification
Language Modeling
Method
VIT-S/16
VIT-B/16
GPT-2++ (350M)
GPT-2++ (760M)
AdamW
79.74
80.94
18.43
14.70
G-Lion
79.82
80.99
18.35
14.66
D-Lion (MaVo)
79.69
80.79
18.37
14.66
D-Lion (Avg)
80.11
81.13
18.39
14.69
Table 3: 3-Shot instruction finetuning downstream evaluation results on various datasets. We mark the best performance with bold text and the second one with underline.
Method
Arc-Easy
Arc-Challenge
BoolQ
PIQA
SIQA
HellaSwag
OBQA
0-Shot
76.64
43.06
76.43
78.64
45.96
56.87
33.53
G-AdamW
77.06
46.06
77.23
79.18
48.97
59.23
35.51
G-Lion
77.11
45.54
77.50
79.18
49.64
58.93
35.51
D-Lion (M)
76.86
45.72
77.14
78.92
49.75
58.96
35.71
D-Lion (Avg)
76.35
45.54
76.90
78.76
48.06
59.06
32.14
Observation We summarize the results Table 2 (ImageNet 1K and
Language
Model Pretraining) and Table 3 (Instruction Finetuning). Both D-Lion (Avg) and D-Lion (MaVo)

---

can maintain performance similar to, or even better than, that of G-AdamW and G-Lion, on both large-scale vision and language tasks. We observe that D-Lion (Avg) outperforms D-Lion (MaVo) on ImageNet, and observe the opposite on language modeling and instruction finetuning. We hypothesize that these differences are due the impact of global batch size. As a result, we recommend using D-Lion (Avg) (Ma Vo) when the global batch size is large / small.
6 Conclusion and Future Work
In this paper, we introduced Distributed Lion, a communication- -fffccii distributed training strategy that builds upon the Lion optimizer's binary update mechanism. Distributed Lion is designed to minimize communication overhead by allowing workers to independently manage their optimizer states and exchange only binary low-precision update vectors with the server. We proposed two aggregation techniques within the Distributed Lion framework: average-based (Distributed Lion Avg) and majority vote-based (Distributed Lion MaVo) algorithms. We provide both theoretical and empirical results to demonstrate Distributed Lion's effectiveness, scalabílity, and efficiency. Notably, we show that Distributed Lion performs significantly better than existing communication-friint methods. In the meantime, Distributed Lion demonstrates performance on with strong global distributed training baselines, while being 32x more communication efficient. As our method is orthogonal to existing communication-ceee -effiiicaatin-efiiiinnt both techniques for further improvement. As a limitation, currently Distributed Lion (Avg Ma performs inconsistently across different datasets and benchmarks, it will be an interesting future research direction understand when and why one performs better than the other.
efficientt methods, an interesting future direction is to combine
Acknowledgment
The research is conducted in Statistics & Al group UT Austin, which receives supports in part from NSF CAREER I 846421, SenSE2037267, Office of Navy Research, and NSF Institute for Foundations of Machine Learning (IFML).
10

---

References
[1] Alham Fikri Aji and Kenneth Heafield, Sparse communication for distributed gradient descent. arXiv preprint trXiv:/70.005000 2017.
[2] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-efficieee sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
[3] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint 1607 0.45006650 2016.
[4] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandku- mar. signSGD: Compressed Optimisation for Non-Convex Problems, August 2018. arXiv:1802.04433 [cs, math].
[5] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Arizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pages 560-569. PMLR, 2018.
[6] Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar, signsgd with majority vote is communication efficient and fault tolerant. arXiv preprint 110.0218/0005521,, 2018.
[7] Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. Piga: Reasoning about phys- ical commonsense in natural language. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 7432-7439, 2020.
[8] Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-311, 2018.
[9] Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting distributed synchronous sgd. arXiv preprint arXiv: 1604.0098 2016.
[10] Lizhang Chen, Bo Liu, Kaizhao Liang, and Qiang Liu. Lion secretly solves constrained optimization: As lyapunov predicts. arXiv preprint arXiv:2310.05899, 2023.
[11] Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsich, et al. Symbolic discovery of optimization algo- rithms. arXiv preprint arXiv:2302.06675. 2023.
[12] Christopher Clark, Kenton Lee, Ming-Woe Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. In NAACL, 2019.
[13] Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. ArXiv, abs/1803.0555 180.005557 2018.
[14] Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. arXiv preprint arXiv:2208. 11195, 2022.
[15] Ekin Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoe V Le. Autoaugment: Learning augmentation policies from data. arXiv preprint arXiv: 10Xiv:80000090/ 2018.
[16] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani. Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint 1992 2020.
[17] Aaron Gokaslan and Vanya Cohen. Openwehtext corpus. http:///kyyloon077. .it..b..ttttt....... io/ 2019
OpenNebTextCorpuss, 2019.

---

[18] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbi, Aidan Clark, al. Training compute-optimal large language models. arXiv preprint arXiv:2203. 1.xx::22033/555,, 2022.
[19] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
[20] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al. Segment anything. arXiv preprint arXiv:2304.002643 02643, 2023.
[21] Haoyu Li, Qizhi Chen, Yixin Zhang, Tong Yang, and Bin Cui. Stingy sketch: a sketch framework for accurate and fast frequency estimation. Proceedings of the VLDB Endowment, 15(7):1426-) 1438-14886 2022.
[22] Haoyu Li, Liuhui Wang, Qizhi Chen, Jianan Ji, Yuhan Wu, Yikai Zhao, Tong Yang, and Aditya Akella. Chainedfilte:: Combining membership filters by chain rule. Proceedings of the ACM on Management of Data, 1(4):1-27, 2023.
[23] Haoyu Li. Yuchen Xu, Jiayi Chen, Rohit Dwivedula, Wenfei Wu, Kegiang He, Aditya Akella, and Dachyeok Kim. Accelerating distributed deep learning using lossless homomorphic compression, 2024.
[24] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep gradient com- pression: Reducing the communication bandwidth for distributed training. arXiv preprint 17Xiv:1712.00887,,22 2017.
[25] Bo Liu, Rachita Chhaparia, Arthur Douillard, Satyen Kale, Andrei A Rusu, Jiajun Shen, Arthur Szlam, and Mare' Aurelio Ranzato. Asynchronous local-sgd training for language modeling. arXiv preprint arXiv:2401.09135 2024.
[26] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017.
[27] Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can a suit of armor conduct electricity? new dataset for open book question answering. In Conference on Empirical Methods in Natural Language Processing, 2018.
[28] OpenAl. Gpt-4 technical report. ArXiv, abs/2303.087744 2023.
[29] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[30] Martin Riedmiller and Heinrich Braun. A direct adaptive method for faster backpropagation learning: The rprop algorithm. In IEEE international conference on neural networks, pages 586-591 696.591.10 IEEE, 1993.
[31] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy. Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211-2555) 2015.
[32] Maarten Sap. Hannah Rashkin, Derek Chen, Ronan LeBras, and Yejin Choi. Socialiqa: Com- monsense reasoning about social interactions. arXiv preprint arXiv: 1xXv::990.009728, 2019.
[33] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to lata-parallel distributed training of speech dnns. In Fifteenth annual conference of the international speech communication association, 2014.
[34] Tao Sun, Qingsong Wang. Dongsheng Li, and Bao Wang. Momentum ensures convergence of signsgd under weaker assumptions. In International Conference on Machine Learning, pages 33077-33099, PMLR. 2023.
12

---

[35] Hugo Touvron, Thibaut Lavril, Gautier Izacard. Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et Llama: Open and efficient foundation language models. arXiv preprint (tt.::3002.13771 2023.
[36] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication distributed deep learning. Advances in neural information processing systems, 30, 2017.
[37] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can machine really finish your sentence? arXiv preprint arXiv: 2019.
[38] Biao Zhang and Rico Sennrich. Root mean square layer normalization. Advances in Neural Information Processing Systems, 32, 2019.
[39] Hongyi Zhang, Moustapha Cisse, Yann Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXi:: 2017.
[40] Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Tie- Yan
Liu. Asynchronous stochastic gradient descent with delay compensation. International Conference Machine Learning, pages 4120-4129. PMLR, 2017.
13

---

A Additional Experiment Details
In this section, we provide additional experiment details.
CIFAR Experiments We list the optimal hyperparameters selected for each method from Figure in Table 4. The learning rates are selected from (0.00005, 0.001, 0.005, 0.01) and the weight decays selected from (0.0005, 0.001, 0.005). For each experiment, scheduler and run for 200 epochs, and we ensure that in each epoch, each local worker sees the entire dataset once.
cosine learning rate
Method
LR
WD X Compression Rate
G-AdamW 0.0001
0.0005
G-Lion
0.00005
0.005
DGC
0.01
0.0005
0.96
GradDrop
0.001
0.0005
0.96
TernGrad
0.001
0.0005
D-Lion (Avg)
0.00005
0.005
D-Lion (MaVo)
0.00005
0.005
Table Hyperparameters for each method Figure 2. Where represents learning and represents weight decay.
B Theory
This section is focusing the proof of Lion dynamics, and will be organized into these folders:
Phase
Constraint enforeing: Discrete time
Phase II:
Majority Voting convergence
Avg update convergence
Global LION convergence
line with the behavior observed the global Lion approach, Lion under a distributed setting also exhibits the two phases. In Section B. show that converging to box can be exponentially fast using our Algorithm We start with introducing a notion KKT score function that quantifies a stationary solution the box constrained optimization problem (6) in Section B.2. Building this, we then proceed to analyze the convergence in terms of the KKT score function for the majority vote (Section B.2.1). averaging (Section B.2.2), and global LION strategies (Section B.2.3).
B.1 Phase I: Constraint Enforcing
We study phase I in this section. We show that when the constraint is not satisfied, both variants of distributed Lion decrease the distance to the feasible set exponentially fast.
Theorem B.1 (Phase I). Assume f: Rd - IR is L-smooth, 31, 82 E (0, and B3 > Br, and e, À > and 1 eA E (0, 1). Let (xz)12a be generated by Algorithm 1. Define F {x: ||Ar|l 1}, and dist(x,, F) = infzer || Iell w.r.t any norm [|-1]-
For any two non-negative integers S then Vs < I, we have
"dist(Ie, F). dist(2r, F) s (1 eX)* -
14

---

Proof. Recall Algorithm 1:
d2 - sign( (Bimi, + (1 V.)
mi,+1 - 82m + (1 a. (F) Ead))
A +/ Σ 1= d1,))
(Averaging)
sign Σ 64,1)
(Majority Vote)
1++ = di <(A + Xxae)
Rewrite the update into the following form:
2(41 (1 eA) ed..
Define W8-+1 (1 =x)==.. m. Unrolling this update yields,
Ens k=z Wk uk-r(-Ae/A)
3t (1 Wg-1) Wo
28-11
k Wh-st
We have Z E F since - E F. For any > O, let to E F be the point satisfying |& raIl S dist(x,, 77. Hence, have
dist(It: F)
inf | - 2||
sEF
S || - (1 - W Wg-+1) -5-21 - W we-+
ui I3 8zll
(1 (dist( n))
As -> achieve the desired result.
L
B.2
Phase
We study the convergence of Phase II in this section. We begin by defining a KKT score function to quantify stationary solutions for the box-constrained optimization problem discussed in Section B.2. Following this, we analyze convergence through the KKT score across majority vote (Section B.2.1) averaging (Section B.2.2), and global Lion strategies (Section B.2.3).
First, we list the following assumptions used in our proof.
Assumption B.2 (Smooth and Differentiable f). Function f(-) is differentiable and L-smooth.
Assumption B.3 (Variance bound). DD is i.idd. drawn from a common distribtion w.. and the stochastic sample ç D, is i.i.d. and upon receiving query RR, the stochastic gradient oracle gives us an independent unbiased estimate ff(x; from the i-th worker that has coordinate bounded variance:
Vf(x; Vf)x),
E [IV)(=;E') - So?
Assumption B.4 (Bias Correction). Consider the sequence {miteso.EIM generated by Algorithm 1, Blmij/E[ssggu(mt)) 2 0.
Here we define the a KKT score function for box constrained problem (6):
S(x) == (V f (z) sig. + Az).
Proposition B.5. Assume f continuously differentiable, 0, and |Axlla $1. Then S(x) = implies KKT stationary condition of min, [() s.l. ||xr|| <
Proof. We will verify that S(x) coincides with the first order KKT conditions of the box constrained optimization problem (6).
15

---

Recall the box constrained problem in (6), we can rewrite it into the following formulation:
min f(x) s.t. Aay - 1110 O, - -xx; - 110, V [d].
SER
Let μa (M) (M1,M2," P2, uaa) and = (fi1 M2, ... pa) then its first order KKT stationary condition can be written as:
0z.f(x) + 14 - p=;== =0
//Stationarity
14(A0;; -1) =0, ( -1) =0
//Complementary slackness
14 2.20, 20
//Dual feasibility
Xæ; 15
xx; 150
//Primal feasibility
E (1,2, ,..
Expressing (z) element-wisely, we obtain:
((x) = Σ (x(),,
with
= = (x)) (sign(O.. (
ArE),
where Fy denotes the k-th element of vector x. Since |1 S 1, we have Sy Sx(x) 2 0, because
Sx(x)
Sx, (siig((2z,)) [2)) + Aare)
f()) + A02, f(x 2x
12, 10., / (2) |
Oze (x))
(x) (1 - \xxx))
0 //since Axll S
Hence, if S(x) = 0, we have Sy(x) 0 for each component k. It means that we have either
sign(O., Azy = or f = 0 for each coordinate k.
There are two primary cases to consider for each A:
Case I: 0z) 0. This suggests that we reach a stationary condition of f(z) w.r.t coordinate Tk. and the KKT condition is satisfied this case with μı = jāa
Case II: sign(0rn Ar = follows that øy. (i
sign(0,, fxx 1, then fzx)(x) 2 O, and the KKT condition satisfied with M4 = 0 and i = fz)//A
if si, (x)) -, then 0n (xx < 0, and the KKT condition is satisfied with es = 0 and μr = {x))/A
It turns out the two cases above exactly covers the KKT stationary solution pair (z, p4 Øi) of the box constrained problem in (6).
In conclusion, S(x) = 0 signifies reaching a stationary point of the bound-constrained optimization problem, as formulated (6). providing critical insights into the convergence behavior of the algorithm under consideration.
B.2.1 Majority Vote
Assume f: Rd + R is L-smooth, and N the number of workers, on the i-th worker, consider the following scheme based on the majority vote:
gi V f(rz; E
m Bym; + (1 B2)9t
mi+1 3img + (1 B1 )9ì
(11)
N
Tt+1 = Jt
sign Σ sign(m((1))
- Xar
//ajorriy Voting
16

---

Theorem B.6 (Convergence in Phase II,, Assumption B.2 B.3 B.4 hold, consider the scheme in Algorithm 11, and Bn, 52 (0, 1), and B Sn, and e, x 0. ||Axollo 1.
We have
(100 -
+ 2D V(
43y 2v VC) + 2p 2Ledd
T [S(())
<
Te
(1))5)
1-
VN
where - B - B2) 1+02
1
+ +1 (1-)))). D max // (2Vd3, | [(w)))) and
FE|sign(m + [k)) = 0,
Pr[k] [l / [+]]
else.
Proof. Following Theorem B.I from phase 1, once we have ||Arollao S 1, we stay within the constraint set with | || < 1 for all subsequent time 2 O.
For notation, write M,+1 Σ N have
i=1 sign(mi(1). This yields 24+1 It - esign(Me++) exa,, We
(04t1)-((a)) & (VI(x)), 14+1 - xxa) + || - -xx11
III-smoothness of
I
- sign(MM++ + >xxe)) + | 10441-x011 x2l1
2
L
-<<(Vf(z,) Sig VV xare) + || - xrl12
2
+ +c(V sign (V)())) sign-signnMMn sign( (++1)))
S((x) + 2L e sign (V f((())) sign( (12)
where we used | - 2; 2
sign (M++1) + Az² s 4e2d, because || S 1.
By Assumption B.3, mf m 1i m are i...d, so E[m and ((sign(m((+.)) )] don't depend on i. Hence we can define Ro41 El EEigg/ (m ,)] where the division operation element wise, so R TR...
By Assumption 3.3, Rg is non-negative, one special case for the ratio RG is when E[sign [k]] = 0, 400 for
yet [[m][k]] f 0, leading [.]k] [k]
[d]. In such instance, P(m > 0) 1/2 derived from the equation E Elsign m; [k]] = 2P > 0) - 1 0, for k [d].
First, recognizing that E[sign( (aaggnMM,laa M, [k])] = 0 straightforward as we model as bino- 0. This leads the result E E [zx))]]]]
mial distribution with success probability p 1/2 for
EV (k:))]] (sign((
sign(M,((k)
Given that [[X] = arg min, E E| - =||2 defines the expectation of random variable X as the value minimizes the expected euclidean distance to X, and the median X arg min, E ||X - =|| defines the median as the value minimizing the expected absolute distance to X, for a R.V. X in R, recall our case where [km 0) 1/2, which is equivalent to that the median is O. From this, follows that
E V fzx))[(]] [K]] (V
fz)) |,11 E Ee [M) v fz.)))
<
To bound the last term in (12) (x signn (vf(x))) sign(Me+)) follow structured approach. Here's an outline for bounding this term:
To bound the last term in Equation (12), (V.( (Vf(z))) sign 1)), we follow a struc- tured approach:
1. Transform Inner Product into Norm of Difference: Using Lemma B.8 convert the inner product (V fxx), (V sign(Mr++1) into the norm of a difference.
17

---

2. Introduce RG as a De-bias Ratio: R; is defined to adjust correct for any bias in the expected value of m and the expected sign of mi as in Assumption B.4.
3. Handle Cases of R2 Separately: Given the possibility of R = +oo, it's essential to treat the scenarios of [k]k] < +00 and Rg [k] to0 with separate proofs.
For [k( < +00, standard bounding techniques can be applied, potentially leveraging properties of establish finite upper bound.
For [ = +00, it's actually bounding V V This can be bounded by the variance of the stochastic gradient g/-
4. Merge Cases with Finite Replacing RG After separately proving bounds for each case of Rg, the results are unified by substituting R2 with a finite Pt, where Pt serves similar purpose but ensures a manageable, finite adjustment.
Case (Finite R₂-1)
The first step is to expand this inner product, we have
E(V ((v)(x)) sign) sign(MM++))
sign) sign( Me+1))
E
[b
sign(V - sign( N Metal [K))
2E
R [k]
Vf(z,)]k] R441 N Met1 [k]
k=1
21E
R [k]
(
//Lemma B.8 and Assumption 3.3
By definition of R., it is debiasing ratio between Elmi and E(sign(mm(_)), so construct a difference between 1 Σiz sign(m{+1141) and 1 E. 1 by decoupling the difference between (x(x)) / [k] and (mi
1
ER [k]
[x(x:)
R+
sign m m
N
N
1 N
ER [k]
m
[k]/R4+11 [k]
Σ m [k///Re4 R
Σ
sign (m [k])
N
N
N
N Σ
[R
m [k]] Re+1
+ Ret1 [k]
mi+ [ki// Ret1l
sign
aom [k])
N
N
N
1=
N
N
1
E V (x))))
m [k]]
+ R [k]
m
[bt] R
sign (B6)
N
N
N
1=1
18

---

The first term E
[
Nे4 E== mi+1 [k]
doesn't t depend on Ri+1, we can bound this term
across d coordinates using Lemma B.10:
N
1
[xx)
m
[k]
S Vd
V (f(xa)
m++1
N
N
1=1
N
1
S VR
V(()))
V
(Bim) + (1 Bi)gi)
N
1=1
N
1
< <V
B1 (VI(x)) mi)
N Σ (VS((e))) - st)
N
( + 2LeVd
vdo -31)
vd3a
I/Lemma B.
32
VN(++ 32)
VN
The second term ER [k]]
N E [ R N Em sign(m [k))
can be decoupled
into the variance of NV Ei=1 sign(m;+11) [k:]) and the variance of + E 1
N
1
E
R
[
m R0///
N
N
d
N
N
E
Re+1 [k]
m m [k]// - 1 [k)/ + Emi+1 [t]]/[+11
Σ
sign m [b]]
N
N
i=1
N
N
E
R [c:]
Σ
m (k))////
1 Re+ [A]
+ Esign (oignii++100 [k:))
Σ
sign (m + [4:)
N
N
==1
E
Re+1 [k:]
Σ
m [k]//(44 Re41 [k]
Em [k]]/ [k]/R(+ R [k]]
+ Rut1 [k]
Esign( [b:)
Σ
sign [b])
d
N
E
m m
+ Re+ilk [k]
sign sign(m{+1) Esign(mi(+))
N
k=1
1=1
i=1
N
< LVV
Emi+1
+ 1|
Σ
sign (m)42) Esign(m)(+))
Ñ
m
N
i=1
Now we have got the variance of 1 En us bound them one by one:
sign [k]) and the variance of 1 E N
m/ [K).. let
The variance of 1/2 EN
[k
N
N
1
E
m
Em
5 Vd.
E
m
Emi
N
N
1=1
N
Vd.
E
|
- Em
N
Cd
/emmm B.11
N
where C= C=B9((1 - B22) I+3s
1 + (1 - B1)
19

---

The variance of 1
Em 1=
sign(m;+1[A)
N
N N
N
[
E
sign(m)+1)
Esign(
E
sign (1 //N E Elsign (m
sigg((mi++)) (msign(mi)+))]]
N2
S ||eeall V
//Lemma B.9
In above, we have the bound of the last term in (12)
sign( sign(M++1))
f(Vf( sign (xx))
(ggnMM+11)
N
S 2E
m
[k:]
+ 2E
Ret1lB
[+]
m [k] Ret1
i [+)
N
N
N
N
1
1
1
< 2 de
V)(z2)
m
+ +2EV d
Σ
m
Emi++
+
sign(m - Esign(())))
N
N
N
1=1
1=1
< 2Vd
( +
2Levd
+
σ
vdo - +
311
+2
Cd
+ 2 21
Il N
1 82
VN(+ 32)
VN
N
Case II (Infinite R)
From our discussion above, we know that P > 0) 1/2 since Elsign (m [+]] = 2P(
0) 1 O, where & E [d]. For notion, write D (j E [d] IE [sign (m [i)) 0}. In this case, we have
Σ (xx)) (ign(V[((x))))) sign Siggg(M.ii (Mbl)
E
V [xx))
JED
JED
E
Eg
V f
- V(cm)
JED
< E
EE
fa -
JED
S a.
So. the inner product (V f(xz), sign( (Vf(=,)) sign sign(Me+ 1)) is still bounded. Hence we merge both cases into a unified bound by simply replacing RG by p::
0 [ [m (iigg///
if o.
[k]
[k]]
else.
Adding one constant D make the bound in finite adpative to infinite case:
s 2l Vr,
Hence,
E [((a)]i
(sin)(V
sign (Mgn(M)ii))
JED
4LdBie
2vdo + VC) + 211p+
2
1- B2
VN
20

---

Finally, we have the bound for both cases:
B(VI(a)) sign v((z)) sign( sign(Me+1))
2LeVd
Vdo(1 31)
Cdo²
<2ddB { + - 82
+ 22
N + 22lpe+tll| V
VN(1 82)
VN
2DV + 4LdB1c
2vdo(1 + VC) + 2 211ptt1ll
1 B2
VN
Then we have
f(1411) f(x)) -(S(m) ((V sign((())))) sign(M++1))
4Td31e
2vdo + VC) + 2 21
+ 2DV
B2
VN
Hence, a telescope yields
1
((x0) V 48d
2Vdo + VC) + 2p 2Lcd,
(S(x) v
Te +
T 1=1
T(1 ((1-32) (2)
1- B2 VN
where p = maxIgIST lpelll-
Lemma B.7. Let (X,Y) is a joint random variable I& Rdd For any constant E (0, +o0),
have
[X, sign(X) sign(Y)) S 2av /EEia//a----- YII.
Proof.
Without loss of generality, set a = 1. E((X, sign())
(Y)g = B||| 11 (X, sig)(
< 2|[ X YIhal
Memma B.8
< 22/ - -
//by Cauchy-Schwarz,
where |1-111 is the & norm and ||-|| denotes the Euclidean norm.
Lemma B.S. For any v, y R. we have
| - zsign(y) S 2 yl
Proof. If sign(y) = sign(z) (x). we have |x]| - asign(y)) (y) < 2 |x: y/- If sign(y) = si) we have |x]| asign(y) = 2xr S 2 |x| + +llyl = 2 1/.
If sign(y) O. we have |ac| usign(y) |o|| |r yl s 2 r yl
Lemma B.9. Let X be a random variable in IR we have E |siinn (X) - E[sign (x)] < 1.
Proof. The result is direct derivation from Bernoulli distribution's 's variance,
-(sss)))))(sss(VVVVV E (X) EEssinn [|]] (iign(X)) - E[sign(X))
Lemma B.10. Following the same setting in Theorem B.6, we huve
N mi - vf(x)))
2Le/d
s (((l\
+ 0
32
VN(1 22)
21

---

Proof. We use the notions: oi == Vf(zri()), Mr = N +Z= mi Es = M, vf(z)), gr
N EN Di. dc = Dt (z)),, and 8, - ( V/(ar)
Et Mr - v((()))
1 + (1 - -32)9t Vf(z))
B2(M V[((x(11) + (1- (2) V Vs((1)
8261-1 (1 82)6: + $28:.
That is
= B + (1 -1- (1)3 + 828t.
Under the L-smoothness assumption B.2:
|
[[V - f(xx))l S L| xxll S 2L 2LVde,
(13)
where e is the step size. Using mathematical induction, we have
= -5550 +
1 s; + (1 - 32)
32
St.
(14)
1=1
i=1
By taking the norms of both sides of the above equation and using the strong bound 13 we obtain
|| < |اماا + 2L de
3l-it1 + (1- - -2211 Σ 32 Sell 1l.
1=1
Taking expectations on both sides,
2L
B||l||| < Eool + - B2
+ (1 B2)1
Σ
82 5z
Note that r.v.s (dt) are mean zero, using 1.11, we have
21 o²
E
de
=
N
S
VN(1
(8)
Hence,
2L
E E|ll < Allloll
+
1- 32
NN(+ 32)
Note that Mo = 0 under our setting, so 50 = f(zo)) we have
2L
Ellea|l s V (zo)ll +
B2
VN(++3)
Lemma B.11 (Cumulative error of stochastic gradient [4]). Assume the same sellings as in Theo- rem B.6. Define Ys == -hh agzz where 5; == 9t f((x)) with g. = =E oi and g; == V (x E following the update in (11), and {ay: 0, o..... is deterministic sequence. Then Y, a mar- tingale, and
k
k
Σ
=
a
02
N
1=1
22

---

Proof. We simply check the definition of martingales. First, we have
1 = E
Jay [B|[1]
//riangle inequality
| mx]]
//law of total probability
[60 mm] 1o [8|
//Jensen's 's inequality
laylo < <0
/Assumption B.3.
Second, again using the law of total probability,
E[ V .. Yal E
andj
0 51
aRoR
Vx 0xk+1
E [ōk+1 on 51 ..., dgdgg
Yx + axx
E 16x+ 10+1 a al a lajo)....,
Y% a641
E E 18441/2441
...,
= Y/-
This completes the proof that it is martingale. We now make use of the properties of martingale difference sequences to establish a variance bound on the martingale.
E
21
+2
6
8 + Σ
aja,B
6, [(6, 1|]
[cj
a
LE
0 _ +0
8
-=1
Σ 07
N
As direct result of Lemma B.11, we have the following.
Lemma B.12. Under the same settings as in Theorem 3.6, we have
E m Elm(+1)1 < (8 32) 1 B2
1
+ +1 (11-8)3²00 0².
Proof.
m Bim! + (1 - -B1)
=1 -12) (oi-1 + B29t +... 1.....3---06 + (1 (1-31)gi-
Note that
(11-32)) 1 + 82 + ... + 3 (2((-11) + 21=) Bî B2)² :320
+ (1-
1-
By using lemma B. 1. we have
+ (1-1311) (11-1132) +(1-8193)09 0².
E | Em
< {8((1 - 32)
1 B2
23

---

B.2.2 Averaging Update Convergence
Assume fi R + R is L-smooth, N is the number of workers, on the i-th worker, consider the following scheme based on the averaging:
o = Vxts <1),
Vi = I N
m Bam; (1 32)9
Vi ......N
M Sym; (1 31)
Vi I.....N N
(15)
N
2441 = T2 e
sign sign(mi+1) + Aoee)
I|Average aggregation
N
Theorem B.13 (Convergence in Phase II). Under Assumption B.2 B.3, consider the scheme in (15), and B1, f2 E (0, 1), and B2 > Br. and e, X > || S have
1 T (S)))) < ((xp) - +
231 32 ((()))
4ed
2310
+ 2(1 -31)0 + 2Led.
Te
T(1 82) 1- 32 v1+ 32
Proof. For notation, write M,+1 = Σi sign(m)+ 1). This yields x241 = 2, cM,+1 cxx
Following Theorem B.I from phase 1, once we have |Arollo S 1, we stay within the constraint set with | || S 1 for all subsequent time 2
Following a similar procedure in B.6, we have
f(1++1) f(x1) - [V(())) - xx) + || - =relé
$ -<((f(())) M + )ma) + / "110041 - =zeli
L
s -v(Vf((()) sign sign() )xx)) + 2
|| - =xe
+ (
- MM+1)
< -2)())) 2L d 2e sign( (Vf()) -M411).
Let us bound the last term (Vf(z,), sign V (xx)) Mc+1),
sign - Mc+1)
sigV 1 N
Σ sign(m)..)
B(V sVgV sign (m)(11)
= RVV signi (x)()) -ign((()))))))) Mii+ are independent
< 22 V (22) - m/+1||
//Lemma B.7
< 2VdE |8| V miil
+ B1) | [xxz silll
//triangle inequality
2Leevd
< 2vd
31 {
+ (1 8130)
//Lemma B.
1- 32
vI 3z
Then we have
f(141) - f(xz) - +2L (eeedde((V[(x)))) ((V sign (V) -M+1)
= +d 2e B1
(BB1B1/ + 2Le/d
σ
(1 (-11))
+ VI+ B2
1- B2
24

---

Hence, a telescope yields
1
(100) -
231 13
43,
28
[S(x) <
+
+ + - -Bi + 2Led.
T
Te
T(1 - 82)
1 1 82
vI+ 32
B.2.3
Global Lion Convergence
Assume Rd + I is L-smooth, N is the number of workers, the i-th worker, consider the following scheme based on the global Lion:
V (xr +t
m4+1 B2m, + (1 B2)g
mi+1 = Bim; + + - Bi)gi
(16)
T++1 It
sign(
Σ
mi41) + Azy
//Global Lion
1=1
Theorem B.14 (Convergence in Phase II). Under Assumption B.2 and B.3, consider the scheme in (16), and $1, B2 E (0, 1), and B2 > 81, and c, x > 0. || S 1. We have
1 T
Σ ES(x)
- ft 23 v V (xoo)
48d
do
TE
T( 32)
8g VN
Proof. For notation, write G.41 = Σ m4+1- This yields T4-1 I esign(((++)) exT,
Following Theorem B. from phase once have |Arullo I 1, we stay within the constraint set with | || < 1 for all subsequent time 2
Following the same procedure in B.6, we have
((141)) < [f(z)), - 2z) + L
| - xell3
|1t11
2
s - [Vf(( sig sign sign(( + +Axr)= + ||,1011 x112
< <<<(V/(m)), sig
+ Aare) + 2
|.5e+11 - 1z
+ +iVV -ignn(
< + 2 2 (V((x))) - sign (in,()
Let us bound
- sign (G++1))
(ivl( sign(
N Σ mL
=E(V/(x;) sign) ((/( - sigu( sigut( N
N
1
< 2V
V Vf(xz)
m++1
i
/emmma B.7
N
1=1
1 N Σg g
1
<V
31
V
f(())
m
+ (1- B1)
v((x.)
//triaggl inequality
N
N
1=1
i=1
<2/d
31
111 fzv))l
+ 1 33
2Le/d
+
o
+
(1 31)0 VN
//emmaa B.10
/ N(1 + 32)
2Levd
- 31)0
< <2vd
B1
f(oo|l + 1- 32
VN
25

---

Then we have
f(1++1) - f(x)) --((x)))( + 2L + (VVf( sign(( Me+1)
$ <<S(x) + 2Le + 20vd 3) (S)IV
2Le
(1 (1)3
3i)0
1 32
N
Hence, a telescope yields
T
[S(x)) - f(x0) -
V ((1-g)
2(1 -1) 2Led.
Te + T(1- 32)
T
1- 82 VN
26

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:[Yes
Justification:
The claims are supported with theoretical and empirical results.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the Conclusion section, we mentioned that Distributed Lion can be further improved when combined with compression techniques. Currently, limitation is that D-Lion (Avg) and D-Lion (MaVo) perform inconsistently across datasets and benchmarks, and will good to understand why in future work.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We list our assumptions and results explicit in the theory section.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [es]]
Justification: We provide the benchmark, algorithm, and hyperparameters for reproducing our results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA].
Justification: All the data we use are public. We will release code upon acceptance.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: answerYes
Justification: We provide the details for training and testing in the experiment section for reproducing our results.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Justification: We average the results over seeds and report the mean Figure for the CIFAR experiment. But for larger scale experiment, it is extremely computationally expensive conduct the experiments multiple times, and known that the result relatively stable. Hence we only once for each large-scale experiment.
8. Experiments Compute Resources
27

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes)
Justification: We provided how many workers are needed for each experiment, the GPU resource can be arbitrary as long as it fits in memory.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: https:// httpeerrpp...ppli///teeaeteeeeee
Answer: [Yes]
Justification: We think our paper confirms in every respect with the Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We do not think our work leads to any negative socictal impact.
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We think the paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: we cite the data and benchmarks use, and the baseline methods we compare against.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing research with human subjects.
28


Reviews:
[{"review_id": "kMoURNX8HA", "reviewer": "Reviewer_7ynU", "summary": "This paper proposes Distributed Lion, a new variant of Lion optimizer for distributed training. The proposed algorithm only requires to communicate binary or lower-precision vectors between workers to the center server, significantly reducing the communication cost. The theoretical analysis proves the convergence of the proposed algorithms. The empirical results show that the proposed algorithms have comparable model performance on CV/NLP applications but with significantly less communication overhead compared to the baselines.", "questions": "1. Is it possible to provide a convergence analysis based on non-i.i.d. data?\n\n2. For the experiments, are the local dataset on each worker i.i.d. or non-i.i.d.?\n\n3. Since the proposed algorithm can compress the communication to an extreme extend, I wonder whether it could also be applied to the federated learning scenario, where the local datasets are not only non-i.i.d., but also highly heterogeneous.\n\n4. Is there any empirical results reporting wall-clock time of training?", "limitations": "The limitations are well discussed and addressed in this paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes Distributed Lion, a new variant of Lion optimizer for distributed training.\n\n2. The proposed algorithm only requires to communicate binary or lower-precision vectors between workers to the center server, significantly reducing the communication cost.\n\n3. The theoretical analysis proves the convergence of the proposed algorithms. The empirical results show that the proposed algorithms have comparable model performance on CV/NLP applications but with significantly less communication overhead compared to the baselines.", "weaknesses": "1. According to Assumption 3.1, the convergence requires i.i.d. local datasets, while real-world distributed training typically uses non-i.i.d. local data.\n\n2. In the empirical results, there seems to be no wall-clock time for training is reported. Note that the overall goal of communication reduction is to reduce the training time. Thus, it is important to report loss/acc vs. wall-clock time in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. i.i.d assumption.**\n\nIndeed, currently, we assume data are i.i.d (the dataset on each worker is pre-sharded before training). We leave it as a future work to show the convergence of distributed Lion under a non-i.i.d setting.\n\n\n**2. Wall-clock time comparison and communication reduction.**\n\nPlease check the common response.\n\n\n**3. Whether the method can be applied to federated learning?**\n\nYes, in principle we expect the method to work in a federated fashion. However, when distributed Lion is applied in a local-SGD fashion, the local update will involve multiple steps of the Lion update, so the aggregated server update will be quantized instead of being binary.", "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": "", "extra_scores": {}}, {"review_id": "i3NB1843Su", "reviewer": "Reviewer_ZPCr", "summary": "This paper extends the Lion optimizer to data parallel distributed training. Unlike optimizers like SGD and Adam, the binary update in Lion can be exploited to minimize the communication. They investigate two cost effective methods for the communication of  binary updates; averaging and majority vote. Experimental results show that both methods yield competitive results to global Lion and AdamW.", "questions": "How different are the global binary updates between averaging and majority vote?\nAre the results similar because they are similar or despite their large difference?", "limitations": "The limitations pointed out above are not explicitly stated in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The convergence analysis provided in Section 3 gives some reassurance to this non-conventional optimization method. Results are promising and experimental conditions seem adequate.", "weaknesses": "The proposed method is a trivial extension of Lion to data parallel distributed training, so the only interesting contribution seems to be the convergence analysis. \n\nThe main contribution of this work is supposed to be the reduction of communication overhead, but there are no results showing the actual breakdown of the training time. Therefore, it is not possible to determine whether the reduction of communication volume is actually contributing to the reduction of the overall training time. Since the results seem to vary quite a bit for different models and datasets, such information is useful for determining whether the experiments are conducted for configurations that actually show a significant impact on the training time. There remains a possibility that the current method does not work as well for extremely large models trained with ZeRO 3 data parallelism, which is where the communication overhead really becomes a problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Wall-clock time reduction.**\n\nWe refer the reviewer to the common response for this question.\n\n\n**2. Compatibility with ZeRO3 data parallelism.**\n\nAlthough large-scale parallelism techniques such as ZeRO3 and FSDP require additional inter-node gather operations that cannot be accelerated by our algorithm, we can still optimize intra-node optimizer state synchronization. In the common large-scale training scenario where the model size increases and intra-node latency becomes significant, our optimizer can reduce communication time by around 50%. While our algorithm does not reduce inter-node gather time in this case, it is compatible with other gradient-size compression algorithms like Galore[1]. In optimal cases, combining these algorithms can lead to even greater reductions in communication time.\n\n**3. Difference between majority vote and averaging.**\n\nBased on our empirical observations, we do not observe too much difference between the two schemes and one could potentially perform better than the other on different datasets. The two reduction schemes are indeed similar, as the majority vote method can be seen as applying an actual sign() activation on top of the averaging.\n\n---\n\n[1] Zhao et al, GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projection.", "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": "", "extra_scores": {}}, {"review_id": "u8zvfjhfKH", "reviewer": "Reviewer_aXYH", "summary": "Large-scale AI model training has increasingly higher requirements on time, cost and environmental impact, so it is crucial to develop efficient optimizers. As an emerging optimizer, Lion optimizer has advantages in memory, computation and sample efficiency compared with AdamW. Distributed Lion: The paper proposes Distributed Lion, which is an innovative adaptation of Lion optimizer in distributed training environment. Using symbolic operations in Lion, Distributed Lion only requires binary or low-precision vectors to be communicated between working nodes and central servers, significantly reducing communication costs.", "questions": "1. How do you ensure that the hyper-parameters of different optimizers are set as a suitable combination for them? Suitable hyper-parameter settings can ensure the fair comparison.\n\nIf the above weaknesses and questions are addressed, I'm happy to raise the score.", "limitations": "Two minor points considering the realistic device constraints:\n1. The experiment scalability is with 32 GPUs, which is not a large scale distributed training setting.\n2. The training model is small-scale with less than 1B parameters.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Distributed Lion significantly reduces communication overhead by communicating only binary or low-precision vectors between workers, which is particularly beneficial for large-scale distributed training.\n2. The paper provides theoretical analysis to prove the convergence of Distributed Lion.\n3. Experimental results show that Distributed Lion can achieve comparable performance to the standard Lion or AdamW optimizer while reducing communication bandwidth.", "weaknesses": "1. The actual updating on local worker parameters is gradients, while the communicated message is signs. While the theoretical analysis shows this updating can guarantee the convergence, the actual updating style looks like the quantization. The important baselines like QSGD and SignSGD are missed. \n2. The performance of Distributed Lion can be sensitive to hyperparameter choices, especially those related to communication and aggregation strategies.\n3. The code is not provided. Thus the reproducibility of the experiments is weakened.\n4. The experiment performance on the CIFAR-10 is very low. Considering that the well-known validation performance of CIFAR-10 can be achieved as 94%, the proposed results are around 90%. Why the performance decreases?\n5. The important baseline SGD with momentum is not provided.\n6. The convergence curves on training with ImageNet and OpenWebText are not provided. This makes it hard to identify the convergence speedup between different optimizers.\n7. The wall-clock time is not provided. The quantization operation and the majority vote require extra time, it will be better to show this optimizer can reduce the real-world throughputs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Comparison to quantization methods.**\n\nThe actual update on each worker is actually not the gradient, but rather the Lion’s update (the sign() plus weight decay). To our knowledge, the quantization methods often quantize the gradients before feeding the quantized gradient to the optimizer. In our case, the sign() operation is applied to the reweighted momentum, which is computed using exact gradients. Moreover, unlike quantization methods, the sign() function in distributed Lion is a feature, instead of any approximation.\n\nGiven the limited time for rebuttal, we are not able to run QSGD and SignSGD distributedly. However, note that the Ternary gradient baseline is a specific quantization method, where the gradient is quantized to a ternary. Moreover, we provide a comparison against a stronger baseline than SignSGD (Sign SGD momentum, a.k.a., SIGNUM), and also the SGD momentum (as requested by the reviewer) in the following:\n\n| Algorithm        | worker = 4 | worker = 8 | worker = 16 |\n|------------------|------------|------------|-------------|\n| SGD Mom          | 79.3       | 81.8       | 82.5        |\n| SIGNUM           | 88.3       | 87.2       | 85.5        |\n| Dist Lion (MaVo) | 90.9      | 89.6      | 88.9       |\n| Dist Lion (Avg)  | 90.5      | 87.9      | 87.9       |\n\nFrom the result, we see that the distributed Lion still results in better performance.\n\n\n**2. Sensitivity to hyperparameters.**\n\nEmpirically we observe that the performance of distributed Lion is not sensitive to hyperparameters. In our experiments, we did not tune the betas, and chose the default betas suggested in the Lion paper, and only tuned the learning rate and weight decay, which are the two hyperparameters shared by all optimizers. **According to our findings in Table 4, the best hyperparameters for distributed Lion are the same as in the Global Lion.** Therefore, we expect that the default hyperparameters for Lion will always be a good configuration for distributed Lion.\n\n**3. Reproducibility.**\n\nThe actual implementation requires further internal review to be made publicly available. But we provide an implementation of our distributed Lion optimizer in this [link](https://anonymous.4open.science/r/dist_lion-6789/dist_lion.py).\n\n\n**4. Performance on CIFAR-10.**\n\nNote that as mentioned in Line 224, we are applying all optimizers to ViT models with 6 layers and 8 heads, as it is easier and faster to train. We chose ViT models as they are broadly used in practice. As a result, given the limited size of the ViT model, a performance with nearly 90% accuracy is already pretty high. The overall architecture is similar to the ViT small from this codebase [https://github.com/kentaroy47/vision-transformers-cifar10/tree/main] (note that it is ViT small, not the ViT small (timm transfer)). The training result from their repo is around 80% accuracy.\n\n**5. Convergence Curve.**\n\nWe provide the training curves of Distributed Lion, Global Lion, and Global AdamW on ImageNet training in the uploaded PDF from the common response. From the curve, we can tell that Distributed Lion performs slightly better throughout the training.\n\n\n**6. Wall-clock time comparison.**\n\nWe refer the reviewer to the common response for this question.", "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": "", "extra_scores": {}}, {"review_id": "WcWMS0HWuI", "reviewer": "Reviewer_gUvC", "summary": "The paper introduces Distributed Lion, a variant of the Lion optimizer, tailored for distributed training environments. Lion, known for its memory and computational efficiency, is adapted to reduce communication costs between workers and a central server. This is achieved by communicating binary or low-precision vectors rather than high-precision floating-point vectors. The paper presents theoretical convergence properties and empirical results that demonstrate Distributed Lion’s robustness and efficiency across various tasks, worker counts, and batch sizes. It shows comparable performance to standard Lion or AdamW optimizers but with significantly reduced communication bandwidth.", "questions": "What is the fundamental difference between distributed Lion and SIGNUM-like algorithms?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ Innovation in Communication Efficiency: The use of binary or low-precision vectors for communication significantly reduces bandwidth requirements, which is a critical factor in distributed training.\n+ Theoretical Validation: The paper provides a solid theoretical foundation confirming the convergence properties of Distributed Lion.\n+ Empirical Evidence: Extensive experiments demonstrate the robustness and efficiency of Distributed Lion across a variety of tasks, making a strong case for its practical applicability.", "weaknesses": "- Incompatible with Allreduce: after converting the gradients to binary or low-precision, Allreduce cannot be used for gradient synchronization. One of my concerns is about its communication efficiency in real-world distributed systems, especially training with a high number of workers.\n- Computation Overhead: While the communication cost is reduced, the overhead of converting updates to binary or low-precision vectors and back might offset some of the gains in certain scenarios. It helps if the end-to-end training throughput comparison is reported.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Incompatible with all reduce.**\n\nOur current algorithm indeed requires a customized all_reduce, but we believe the code should be relatively simple to apply to various real-world applications. Additionally, we are exploring ways to optimize the communication process for low-bit information.\nYou are right, due to the limited operator support in practical all reduce such as PyTorch, which is ring-based reduce, it makes the low-bit information hard to broadcast and maintain its information when broadcast through the whole ring. This issue widely exists in all our baselines. Our current practical solution is packing and encoding our binary information into a low-bit tensor and then using an int8 tensor as a container to broadcast through the ring all reduce. This can still compress the information from 2-4x depending on the number of workers, we show the empirical result under different works below together with question 2.\nFor sure, we are looking forward to some core updates that can be made by the NCCL library or pytorch team to support more low-bit friendly operators or datatypes like fp4, and fp8 during communication, which could greatly help with low-bit communication algorithms.\n\n**2. Computation overhead.**\n\nPlease check the common response.\n\n**3. The difference between Distributed Lion and SIGNUM-like algorithm.**\n\nThe main differences are two-fold:\n- Lion has an additional reweighting before the sign(), as in sign( $\\beta_1 m_t + (1 - \\beta_1) g_t$) and the weight decay term, which are crucial for performance improvement. The unique form of Lion presents the special $\\ell_\\infty$ constraint optimization view of the algorithm.\n\n- Usually, when applying SIGNUM to distributed training, we aggregate the gradient and then apply the sign operation. In distributed Lion, we transmit the signed results and their majority vote, not the gradient. The weight decay, as a result, is applied locally in distributed Lion.", "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": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank the reviewers for their valuable feedback. In the following, we provide the general response and address individual concerns separately in individual responses.

**1. Wall-clock time comparison.**

Several reviewers have requested a wall-clock time comparison. Our study primarily focuses on the theoretical and empirical performance of distributed Lion algorithms, rather than the practical aspects of implementation. Currently, we employ a majority vote strategy using int8 combined with a built-in all-reduce operation, which already achieves notable speedup in wall-clock time and reduces communication overhead. In particular, using a 3B Transformer model, with 1K token length, across 64 A100 40G devices, with batch size 1, using our current implementation, we have:

| Method                  | Forward Time (ms) | Backward Time (ms) | Optimizer State Communication (ms) | Total (ms) |
|-------------------------|-------------------|--------------------|------------------------------------|-------|
| AdamW                   | 18                | 141                | 132                                | 291   |
| Lion                    | 18                | 137                | 133                                | 288   |
| Distributed Lion (MaVo) | 18                | 128                | 61                                 | 207   |

As we can see, the communication overhead is saved by more than 50% even with our int8 implementation. This could be further improved if customized all reduce is supported for binary inputs.

Reviewer gUvC raised concerns about the limited support for low-bit operations in ring-based all-reduce frameworks like PyTorch. This challenge affects not only our approach but also all our baseline comparisons. We address this by packing binary information into low-bit tensors and then broadcasting it using an int8 tensor container through the ring all-reduce.
We anticipate future enhancements from the NCCL library or the PyTorch team that introduce more efficient low-bit operations or data types, such as fp4 or fp8. Such developments would significantly improve the efficiency of low-bit communication algorithms.

**2. Release of the Code.**

We release our implementation of the distributed Lion [here](https://anonymous.4open.science/r/dist_lion-6789/dist_lion.py). We intend to publicly release the method for the convenience of future research.

Meta-review: This paper considered a distributed version of the Lion optimizer, which reduces the communication cost. The authors provided theoretical analysis of this algorithm and showed empirical results on vision and language tasks. The reviewers unanimously recommended to accept this paper. I suggest the author incoporate the extra wall-clock time experiments and communication reduction experiments in the final version of the paper.
Decision: Accept (poster)