Layer-wise Quantization for Quantized Optimistic Dual Averaging
Authors: Anh Duc Nguyen
Ilia Markov
Frank Zhengqing Wu
Ali Ramezani-Kebrya
Kimon Antonakopoulos
Dan Alistarh
Volkan Cevher
Venue: ICML 2025 poster (2025)
Keywords: Adaptive Compression
Layer-wise Compression
Optimistic Dual Averaging
Distributed Variational Inequality
Primary area: optimization->large_scale_parallel_and_distributed
TL;DR: This paper study adaptive layer-wise compression and optimistic dual averaging for distributed variational inequalities.

Abstract: Modern deep neural networks exhibit heterogeneity across  numerous layers of various types such as residuals, multi-head attention, etc., due to varying structures (dimensions, activation functions, etc.), distinct representation characteristics, which impact predictions. We develop a general layer-wise quantization framework with tight variance and code-length bounds, adapting to the heterogeneities over the course of training. We then apply a new layer-wise quantization technique within distributed variational inequalities (VIs), proposing a novel Quantized Optimistic Dual Averaging (QODA) algorithm with adaptive learning rates, which achieves competitive convergence rates for monotone VIs. We empirically show that QODA achieves up to a $150$% speedup over the baselines in end-to-end training time for training Wasserstein GAN on $12+$ GPUs.

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Anh Due Nguyen' Ilia Markov Frank Zhengqing Wu
Ali Ramezani-Kebrya 456 Kimon Antonakopoulos Dan Alistarh 72 Volkan Cevher
Abstract
compressed variants while providing substantial savings in communication costs (Alistarh et al., 2017; Wen et al., 2017; Zhang et al., 2017; Faghri et al., 2020).
Modern deep neural networks exhibit heterogene- ity across numerous layers of various types such as residuals, multi-head attention, etc., due to varying structures (dimensions, activation func- tions, etc.), distinct representation characteristics, which impact predictions. We develop general layer-wise quantization framework with tight vari- ance and code-length bounds, adapting the het- erogeneities over the course of training. We then apply a new layer-wise quantization technique within distributed variational inequalities (VIs). proposing a novel Quantized Optimistic Dual Av- eraging (QODA) algorithm with adaptive learning rates, which achieves competitive convergence rates for monotone VIs. We empirically show that QODA achieves up to 150% speedup over the baselines in end-to-end training time for training Wasserstein GAN on 12+ GPUs.
Popular DNNs including convolutional architectures, trans- formers, and vision transformers have various types of layers such as feed-forward, residual, multi-head attention includ- ing self-attention and cross-attention, bias, and normaliza- tion layers (He et al., 2016; Vaswani et al., 2017; Doso- vitskiy et al., 2021). Different types of layers learn dis- tinct hierarchical features ranging from low-level patterns to high-level semantic features (Zeiler & Fergus, 2014; He et al., 2016). They are also diverse in terms of number of parameters and their impact on the final accuracy (Dutta et al., 2020). Similar heterogeneity has been observed for attention layers in large-scale transformers (Markov et al., 2022). The current communication not rigorously take into account heterogeneity in terms of representation power, impact on the final learning outcome, and statistical heterogeneity across various layers of neural networks and across training for each layer. Recently, layer- wise and adaptive compression schemes have shown tremen- dous empirical success in accelerating training deep neural networks and transformers in large-scale settings (Markov et al., 2022; 2024), but they have yet to have theoretical guar- antees and to handle statistical heterogeneity over the course of training. Hence, these layer-wise compression schemes suffer from a dearth of generalization and statistically rigor- ous argument optimize the sequence of quantization and the number of sparsification levels for each layer.
literature does
1. Introduction
In modern large-scale machine learning (ML) settings, com- munication costs for broadcasting huge stochastic gradi- ents and dual vectors are the main performance bottle- neck (Strom, 2015; Alistarh et al., 2017; Kairouz et al., 2021). Several methods have been proposed to accelcrate large-scale training such as quantization, sparsification, and reducing the frequency of communication through local updates (Kairouz et al., 2021). In particular, unbiased quan- tization is unique due to offering both strong theoretical guarantees and communication efficiency on the fly, i.e., it converges under the same hyperparameters tuned for un-
In distributed learning, empirical risk minimization (ERM) and finite-sum optimization problems are commonly tackled using first-order solvers, which scale by distributing com- putations across multiple nodes synchronously (McMahan et al., 2017; Kairouz et al., 2021; Li al., 2020; Ramezani- Kebrya et al., 2022; Xie et al., 2024). These nodes, for instance hospitals and mobile devices, collaborate by parti- tioning data and aggregating local updates.' ! However, many real-world problems extend beyond ERM and require more complex mathematical formulations. particular, training generative adversarial networks (GANs) (Goodfellow et al.,
'National University of Singapore (NUS), mostly work done LIONS, EPFL "Neural Magic Laboratory for Information and Inference Systems (LIONS), Bcole Polytechnique Fédérale de Lau- sanne (EPFL) "University of Oslo (UiO) 'Integreat, Norwegian Centre for Knowledge-driven Machine Learning Visual Intelli- gence Centre "Institute Science and Technology Austria (ISTA), Correspondence to: Anh Due Nguyen <ducna@nus Sudinaa
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
For simplicity, we use the term node to refer to clients, FPGA, APU, CPU, GPU, workers throughout this work.

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
2014) is more complex than ERM because it involves minimax problem rather than single-objective loss mini- mization. This adversarial interaction between the genera- tor and discriminator requires equilibrium modeling, often formulated as a variational inequality (VI) to address chal- lenges like cyclic behaviors and instability (Daskalakis et al., 2017: Gidel et al., 2018; Mertikopoulos et al., 2018). As a well-studied mathematical framework (Facchinei & Pang, 2003; Bauschke & Combettes, 2017), VIs also have other ML applicationn in reinforcement learning (Jin & Sidford, 2020; Omidshafiei et al., 2017), auction theory (Syrgkanis et al., 2015), and robust learning (Schmidt et al., 2018).
QODA with layer-wise compression achieves up 150% speedup in both the convergence and training time compared to the global quantization baseline Q- GenX (Ramezani-Kebbl pressed baseline for training Wasserstein Generative Ad- versarial Network (Arjovsky et al., 2017) on 12+ GPUs.
et al., 2023) and the uncom-
1.2. Related Works
The layer-wise structure of DNNs has been explored for optimizing training loss. Zheng et al. (2019) propose SGD with layer-specific stepsizes, while Yu et al. (2017) ex- plore layer-wise normalization for normalized SGD. Be- yond training loss optimization, this structure also enables sketch-based and bandwidth-awand compression methods (Xin et al., 2023; Li et al., 2024). In addition, block quanti- zation, partitioning vectors into blocks before quantization, is studied in (Horváth et al., 2023; Mishchenko et al., 2024). In Appendix A.2, we show that our layer-wise quantization is fundamentally different from block quantization.
In this work, we aim to tackle the problems of providing a general layer-wise quantization framework that takes into account the statistical heterogeneity across layers and then applying that layer-wise quantization framework to propose efficient novel solver for distributed VIs.
1.1. Summary of Contributions
Theoretical Framework and Tight Guarantees for Layer-wise Quantization: We propose a general frame- work for layer-wise (and adaptive) unbiased quantization schemes with novel fine-grained coding protocol analysis. We also establish tight variance and code-length bounds, which encompass the empirical layer-wise quantization methods (Markov et al., 2022: 2024) and generalize the bounds for global quantization frameworks (Alistarh et al., 2017; Faghri et al., 2020; Ramezani Kebrya et al., 2021) with general I normalization and multiple sequences of quantization levels. In fact, under the special case of L normalization and global quantization, our variance bound matches the lower bound from (Ramezani- Kebrya et al., 2021) while our code-length bound is optimal in the problem dimension with respect to the lower bounds from (Tsitsiklis & Luo, 1987; Korhonen & Alistarh, 2021).
Several papers study distributed methods for VI and saddle points problems. Kovalev et al. (2022) considers strongly monotone VI; Beznosikov et al. (2023b) concerns with VI problems under co-coercivity assumptions. Strong mono- tonicity and co-coercivity assumptions can be quite restric- tive for ML applications. Beznosikov et al. (2022; 2023a) consider VI problems with finite sum structure with an extra 8-similarity assumption in (Beznosikov et al., 2023a). Prior studies (Duchi et al., 2011; Yuan et al., 2012; Tsianos & Rab- bat, 2012) explore dual averaging for distributed finite-sum minimization in networks
We include further literature reviews and discussions on un- biased, adaptive quantization and optimistic gradient meth- ods in Appendix A.
In Section 2, preliminaries quanti- zation, VIs and noise profiles are covered. In Section 3, we propose the general framework for layer-wise quantization with a novel coding protocol. We then leverage the layer- wise quantization scheme to design QODA (Algorithm 1) for distributed VIs in Section 4. In Section 5.1, we provide the variance and code-length bounds for layer-wise quanti- zation and show the improvements over previous bounds. In Section 5.2, discuss the joint convergence and communi- cation bounds of QODA. We then extend QODA to almost sure boundedness noise model in Section 6, and prove its convergence without co-coercivity. In Section 7, we provide empirical studies on GANs and Transformer-XI..
Paper organization:
Optimistic Quantized Adaptive VI Solver Under Fewer Assumptions Leveraging the novel layer-wise compression framework, we propose Quantized Opti- mistic Dual Averaging (QODA) and establish its joint convergence and communication guarantees with com- petitive rates (LLVTT) and (1/TT) under absolute and relative noise models, respectively. To our knowledge, QODA is the first incorporate optimism for solving distributed VI to reduce one "extra" gradient step that extra gradient type methods such as the global quanti- zation distributed VI-solver Q-GenX (Ramezani-Kethee Kebrya et al., 2023) take. Importantly, we obtain the above guar- antees without the restrictive almost sure boundedness assumption of stochastic dual vectors that is essential in related VI works (Bach& & Levy, 2019; Hsich al., 2021: Antonakopoulos et al., 2021) including Q-GenX.
2. Preliminaries
2.1. Common Notations
We use lower-case bold letters to denote vectors, EE|-] de- notes the expectation operator. ||
Empirical Speedup for GAN Training: We show that
llo and || ||+ are number
2

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
of nonzero elements of a vector and dual norm, respectively. I. denotes the length of a binary string. the length of vec- tor, and cardinality of a set. Sets are typeset in calligraphic font. The b logarithm is denoted by log, and the set of binary strings is denoted by (0, 1 For any integer n. [r] denotes the set nI....,n.. n).
where ((; denotes the (possibly random) error in the measurement noise. Next, formally define two im- portant noise profiles, i.e. absolute noise and relative noise.
Assumption 2.4 (Absolute Noise), Let æ E IR, w ~ P. The oracle g g( is unbiased [[g(a;w) = A(x), and
denotes the indicator function.
there exists o E RR such that EE [I]((, S o².
2.2. Vector Representations
As the noise variance is independent of the value of the operator at the queried point, this type of randomness is absolute. Absolute noise is common in the (distributed) VI literature (Woodworth al., 2021; Ene & Le Nguyen, 2022). It is also known as the bounded variance assumption in stochastic optimization literature (Nemirovski et al., 2009; Juditsky et al.. 201 I). Alternatively, a more favorable noise profile is observed when the stochastic error vanishes near a solution of VI. This is formally captured by the notion of relative noise (Polyak, 1987):
Let U E IR be a vector to be quantized. For some E Z_.. v can be uniquely represented by a tuple (1|0|]g. s, u) where I|ollo is the L norm of v. 8 := (iggn())).....ssnn((( " comprises of signs of each coordinate Us and u :=
(u.,...; (ur.....ua]" ua]", where 14 / is the i-th normalized coordinate. Note that 0 < u, for all i E [d].
2.3. Variational Inequalities
Formally, for an operator A Rd - Rd, variational inequality (VI) finds some xx E Ed such that
Assumption 2.5 (Relative Noise). Let E I& and P. The oracle g(æ; w)) is unbiased [[y(a;;)) = A(x)), and there exists OR E IR such that E [[]U( (x) [1:] < on (z:))1
(A(x*), x x²) 2 for all x EER.
(VI)
We now present the standard VI assumptions:
Relative noise model has been studied in several ML appli- cation like over peeeraaammttiiziioonnn (Oymak & Soltanolkotabi, 2020), representation learning (Zhang et al., 2021), and multi-agent learning (Lin et al., 2020). In Appendix B.3, we provide more specific relative noise examples. Relative noise model may result in the well-known order-optimal rate of (1/TT) in deterministic settings.
Assumption 2.1 (Monotonicity). We have that for all x, 2 E R.d (A(z)= - A(2), x 2) 2 O.
Assumption 2.2 (Solution Existence). The solution set X² ====(0 "xx E Rdd s'solves (VD) # 0.
Assumption 2.3 (T-LLipschitz). Let L. E R+ Then an operator A is L-Lipschitz if
Remark 2.6. Various adaptive methods for (distributed)
|A(x)- - A(x')I, s L|| - x'll Vx, e Rd.
VI (Bach & Levy, 2019; Hsieh al.,, 2021; Antonakopoulos et al., 2021) including the baseline Q-GenX (Ramezani- Kebrya al., 2023) assume almost sure boundedness of stochastic dual vectors under both absolute and relative noise profiles. In addition, previous theoretical results on global quantization (Alistarh et al., 2017; et al., 2021; Faghri et al., 2020) are also established un- der a similar assumption with bounded second moments of stochastic gradients (stochastic dual vector in our set- ting). In Section 5, we establish the joint convergence and communication guarantees of our VI-solver with layer-wiss quantization without this assumption.
This fairly broad VI class covers all bilinear min-max, co-coercive and monotone games with applications such as GANs (Chavdarova et al., 2019) and robust RI. (Ka- malaruban et al., 2020; Hsich et al., 2020; Lin et al., 2020).
The main measure evaluate the quality of a candidate VI solution is the restricted gap function (Nesterov, 20099 (more details in Appendix B):
G*) = sup (A(x), 2 x).
(GAP)
x
3. Adaptive Layer- wise Quantization
where X C Rd is non-empty and compact test domain.
Adaptive layer-wise quantization is only studied empirically in (Markov et al., 2022; 2024) with promising results in training Transformer-Xi XL on WikiText- and ResNet50 on CIFAR-100. Our goal is hence to provide general formulation incorporating the statistical heterogeneity across layers and establish tight theoretical guarantees for layer-wise quantization with tailored coding schemes.
2.4. Noise Models
We study VI methods that rely on a stochastic first-order oracle (Nesterov, 2004). This oracle, when called at x, draws an i.i.d. sample from a complete probability space (R,F, F. P) and returns a stochastic dual vector g(x:w) as
g( A(x) + Ux);w)
In Figure 1, we provide an intuitive visualization for layer-
3

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Layer
Leyer 2
L
Layer
4 Layer
quence of quantization levels for each layer based on statis- tical heterogeneity throughout training. This key novelty is also absent in prior block quantization variants (Wang et al., 2022; Horváth et al., 2023; Mishchenko et al., 2024) which apply the (similar) predefined quantization procedures to each block or layer. Details are provided in Appendix A.2.
Global Quantization
Layer-wise Quantization
From here on to the end of Section 3, we fix time & and a type foror simplicity in notations. We hence drop the superseript time index L and subscript type index m. The formulation holds for each iteration & E [2] and each type m E [M].
Low Compression
Medium Compresaton
Type 3: Compresston
Figure 1. A Visualization for Layer-wise vs Global Quantization
Quantization variance: Let 7 denote the index of level with respect to an entry u E [0, 1] such that (+(u) S
wise and global quantization. In the global scheme (middle row), every layer has the same compression regardless of their impact on the accuracy. In the layer-wise approach (bottom row), each layer is assigned the suitable compres- sion scheme based on its impact on the accuracy, which preserves overall accuracy while still reducing model size.
u < (71)411 Let {(u) = (u be the relative distance of u to the level r(u) + 1. For
- (w)))
sequence l, we define the following random variable
(T())) with probability 1 E (r(()) with probability E(u)
ge(n)=
3.1. General Framework
We then define the random quantization of vector v as QLM(())
Distributed and synchronous setting with K nodes: This setup is along the lines of the standard setting for data- parallel SGD (Dean et al.. 2012; Alistarh et al., 2017). Here, the nodes partition the entire dataset among themselves such that each node retains only local copy of the current pa- rameter vector while having access to independent private stochastic dual vectors. In each iteration, each node re- ceives stochastic dual vectors, aggregates them, computes an update, and broadcasts the compressed update to acceler- ate training. These compressed updates are decompressed before the next aggregation step at each node. We study unbiased compression, where, in expectation, the output of the decompression of compressed vector equal to the original uncompressed vector.
[QM QL (va)) where QLM (U,) ||lll sign(v;) qe- (u:) for m E [M], and any u, E S i.e. the set of all normalized coordinates that use type sequence pm
Let q.M Pq represent d variables {ge- (u.) sam- pled independently for random quantization. As this scheme is unbiased, we can measure the quantization error by mea- suring the variance Fgg, [l]Q (w) w112] given by
M Σ m=1 mm
|101
Σ
oQ (uiiem))
(Var)
where oz (u;; (T²) = [gem (u.) u, = (fT [u.)=1
Layer-wise global quantization: At each time t, in- stead of a global sequence of quantization levels for all coordinates - like QSGD and its variant (Alistarh et al., 2017; Faghri et al., 2020; Ramezani-Kebyy. et al., 2021) we consider a set L of M types of sequences (er-1 [er....... e...,
u;)(u; - pm (m)( the variance of quantization of single
coordinate u, SmM We can optimize M quantization sequences by minimizing the overall quantization variance
min EuEg [110)M A(x) IMELM
be optimized with flexible and ad- justable numbers of levels or,,..., Oras, respectively. We denote ft.m E I.
where L = (1e eM : Vm E [M]. Vj e [am], CT < Ef41. 0, 0, = 1}, denoting the col- lection of all feasible sets of type m levels. Since random quantization and random samples are statistically indepen- dent, the above minimization is equivalent
the sequence of type m at time given by RR. et "e.,..,..,,,, p. +1] where 0 = to < et.m < < et.m < <am+1 = 1. That is, at time t, each layer of the DNN follows one of the M types of quantization se- quences. The intuition that layers with similar or different functionalities and features have correspondingly similar or different quantization sequences, while less important layers adopt fewer quantization levels.
min Ey [1[Qr, (g(x:w)) g( w| (MQV) LMEEM
In Figure 1, give simple visualization to show the difference between layer-wise and global quantization.
Remark 3.1. Unlike previous adaptive global quantization works (Wang et al., 2018; Faghri et al., 2020; Agarwal et al., 2021), our layer-wise quantization adaptively adjust the se-
The time index t will return in Section since the algorithm iterates over all iterations.

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Remark 3.2. We now elaborate on how layer-wise quan- tization is always better than global quantization in (Alistarh et al., 2017; Faghri et al., 2020; Ramezani- Kebrya et al., 2021; 2023). We optimize M quantiza- tion sequences by minimizing quantization variance (MQV). Global quantization models will find an overall optimum sequence L. for all the M types. Hence, the collection of M sequences in this global case is simply Lgt (L.,..,f,), where l. repeats M times. By the minimality of (MQV), we obtain the quantization variance for layer- wise quantization is always upper bounded by that of global quantization: minga IE [[Q (g(x;w)) - ((;; w|] S
Algorithm 1:
Quantized Optimistic Dual Averaging (QODA)
Require: Local training data; local copies of X,, Yú; update steps set L4; learning rates {re), (7+)
1: for t = I,..., I" do
2:
if / E 4 then
3:
for i : K do
4:
Efficiently estimate distributions of normalized dual vectors and update L. L. (Remark 4.1)
5: Update M sequences of levels in parallel
6: end for
7: end if
8: for i = I...., K do
E [1Qug, (g(z:w)) ((=; w)]l
9: Retrieve previously stored V/.1-122 K X1+1/2 + X, - 7t Σ V V K Vu++1/2 + (X(+1/))) + (,(X211/2)
10:
3.2. Main Coding Protocol
11:
12:
di, < ENCODE (QrAM (V4441/2); (LM.)
We now apply practical coding schemes on top of our layer-
13: Broadcast di,t
wise quantization to further reduce communication costs.
14:
Receive di, from each node
We process the coordinates of all M types simultaneously in parallel, i.e. coordinates of different types are quantized,
15:
VLL+1/2 + DECODE(d,,;; (LMM)
encoded and transmitted the same time. Although each
16:
Store V2,,+1/2
quantization type has its own codebook, different types may share similar codewords to reduce the overall code length. The receiver is always aware of the type of each coordinate upon reception, allowing it to apply the correct codebook for decoding. The overall composition of coding and quantiza- tion, [] 8, (Lar) consists of M parallel encoding maps ENC([]e])g s, q uses a standard floating point encoding with C, bits to represent the positive scalar ||v|] encodes the sign of each type coordinate with one bit, and then utilizes correspondingly type m integer encoding scheme Tm : . > (0, 1)" to efficiently encode every type m coordinate with the minimum expected code-length.
17:
Y1+1 < Yt > V K
18:
X 11441111 Y41 + X1
19: end for
20: end for
programming algorithm optimizing the total compression ratio while minimizing compression error (MQV) from (2). The decoding DEC 10, - F first reads C2 bits to reconstruct || then applies decoding schemes (Tm=)- 10. - Am to obtain normalized type m coordinates without confusion since the number of coordi- nates 1STh their order, and the corresponding codebook are known at the decoder. A further discussion for the choice of a specific lossless prefix code and more details on cod- ing schemes are included in Appendix D.3. Alternating Coding Protocol: In the cases that the receiver is not aware use separate
To solve the quantization variance (MQV), we first sample Z stochastic dual vectors {g(a:; ...)..... ......ggle g(æ; wz)) }. Let FT denote the marginal CDF of normalized coordinates of type m conditioned on observing (u(=:w>))l By the law of total expectation, (MQV) can be approximated by solving M minimization problems in parallel for each e.=:
the quantization type of the coordinates, codebooks for M quantization types. We elaborate on the details and guarantees of Alternating Coding Protocol in Appendix D.2 and provide a comparison between the two protocols in Remark D.3.
z min Em
11g( 112
Σ
++1 (u; (e"dd"F(((( (u),
or equivalently min
o lm dd (2)
Remark 3.3. Our layer-wise quantization and coding pro- tocol are general and hence applicable for all distributed optimization settings that follow the stochastic first order oracle models 1. Empirically, (Markov et al., 2024) have applied layer-wise quantization for loss function minimiza- tion (with SGD-type methods) in the context of training language and vision tasks such as ResNet50 on CIFAR-100. We showcase similar applications with training Transformer- XL on WikiText- 103 in Section 7.2.
where (u)( = E._ (u) is the weighted sum of the conditional CDF' of normalized coordinates of type m with weights Ag as follows
|1 w 11
A=
Σ |1 |1
In our practical implementation (Section 7), we utilize L- GreCo (Markov et al., 2024) which executes a dynamic
5

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
4. Quantized Optimistic Dual Averaging
5. Theoretical Guarantees
We now study an application in solving distributed VI with our novel Quantized Optimistic Dual Averaging (QODA), Algorithm 1. Importantly, this optimistic approach reduces one "extra" gradient step that extra gradient methods and variants such as Q-GenX -Ramezani-Kebrya et al., 2023) take (by storing the gradient from the previous iteration, refer to lines 9 and 16). Therefore, QODA reduces the communication burden by half decoupled from acceler- ation due to quantization compared to Q-GenX. At certain steps, every node calculates the sufficient statisties of a para- metric distribution to estimate distribution of dual vectors in lines 3 to 5. Let Vi.e and Vi, denote the uncompressed and compressed stochastic dual vectors in node k at time t, respectively. Let VA,e (Vv..) - (A,, + (X,)) denote the unbiased and quantized stochastic dual vectors for node & E [K] and iteration E [T]. The optimistic dual averaging updates in (ODA) appear in lines 10, 17 and 18. (2 mimroc 1 (id d
5.1. Layer-wise Quantization Bounds
Since the bounds hold for each iteration t, we can fix and drop the index in this subsection for notation simplicity. Let q E 24 and L maxos/Sam. em //t1/"" //g, and eas maxismSM 8T Denote the largest level 1 across M types EM max fT" Let der (2/ēM ) ymin(2.0), We now present variance bound for layer-wise quantization with the proof in Appendix C:
Theorem 5.1 (Variance Bound), With unbiased layer-wise quantization with L normalization of a vector e E R., i.e. Fgg [Q (T) v. we have that
B [11 -v1ž] S =
(5)
11--11² 4BM + (R/ d dimita fd 2 deh +
where EQ
Our layer-wise quantization with QL and coding proto- col are applied in lines 12 and 15. The loops are executed in parallel on the nodes.
Remark 5.2. For the special case of M = 1, our bound (5) recovers (Ramezani-
et al., 2023, Theorem 1). Under M 1, this bound holds for general L normalization and arbitrary sequence of quantization levels opposed to (Alis- tarh et al., 2017, Theorem 3.2) and (Ramezani- 2021, Theorem 4), which only hold for I,2 normalization with uniform or exponentially spaced levels, respectively. In the specific case of M = 1, large d (i.e. d 2 dea. in most practical situations), and r,2 normalization, our bound matches the lower bound 22(va) (Ramezani- Kebrry et al., 2021 (02))rT 7].
K
1/22-1/2
X441/2 = Xt - 7/. Σ
et al.,
k=1
K
V 1/,2-1/2
Y+1 =Y- - Σ
(ODA)
K
k=1
X = X1 + 77- 1
In general, learning rates Yt and nh can be chosen such that they are non-increasing and % 2 nh > 0. We propose the following adaptive learning rate schedules for updates in Algorithm 1.
We now establish code-length bounds for the coding proto- col with the proof in Appendix D.I:
Theorem 5.3 (Code-length Bound). Let Le denote the prob- ability of occurrence of ey for m E [M] and j E [am] Under the setting specified in Theorem 5.1, the expecta- tion Eny [FNC (QIM (g(#; [L)]] of bits is bounded by
122
K
Vn.et1/2 - V/.0-112
1
of the number
K2
(4)
Ey
EEC (Q1. (g( (g(x:w)):
The two learning rates here are equal, but they can be differ- ent in an alternative setting in Section 6. This learning rate separation for optimistic dual averaging is also explored for online multiplayer games in (Hsieh et al., 2022).
M
= =0
Po
P7 log P3
)umd
(6)
m=1
m=
where 1tth is the proportion of rype m coordinates.
Remark 4. One way to efficiently estimate the distribu- tions of dual vectors (line in Algorithm 1) is use a parametrie model of density estimation such as modeling via truncated normal with efficiently computing sufficient statistics (Faghri et al., 2020). The set of update steps U in Algorithm 1 is determined by the dynamics of distribu- tion of normalized dual vectors over the course of train- ing. In Section 7, we dynamically update levels using L- GreCo (Markov et al., 2024).
Remark 5.4. For the special case of M 1, our bound recovers KRamezani-Kebry et al., 2023, Theorem 2). Under the special case of M = 1, L normalization, and = vd as in (Alistarh et al., 2017, Theorem 3.4), our bound can be arbitrarily smaller than (Alistarh et al., 2017, Theorem 3.4) and (Ramezani-Kebnnn on the probabilities {Po.... P--1). Under similar settings, this upper bound is optimal in the problem dimension d,
et al., 2021, Theorem 5) depending
6

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
matching the lower bound for distributed convex optimiza- tion problems with finite-sum structures (Tsitsiklis & Luo, 1987;
suPpex [|X -pll- Under Assumptions 2.1, 2.2, 2.3, 2.3, 2.5, and 5.6, we have
Korhonen & Alistarh, 2021).
(oneeq + tq + +R))D2
E [Gapx (Xe+1/2)] =
TK
5.2. Joint Communication and Convergence Bounds
where eq variance bound.
-EM= Ej=1 Tm.j&q.m.5l T is the average
We now outline the guarantees for QODA in Algorithm 1. Here, QODA is executed for T' iterations on K nodes with learning rates (4). Quantization sequence e is up- dated Jm times, and eT is used for Tm.j iterations where EmE E Tm. =T. Note that en has variance bound EQ. (5) and code-length bound No.ms in (6). Denote Eiz X1+1/2/ = X
The proof details are included in Appendix E.3.
Remark 5.8. Both theorems show that increasing the num- ber of processors K lead to faster convergence for mono- tone Vls, matching the asymptotic rates for T and K of Q-GenX (Ramezani-Kebryy et al., 2023) without an extra almost sure boundedness assumption. Under the absolute noise model and by setting the number of gradients per round one, our results match the known lower bound for convex and smooth optimization Q(1/vTK) (Woodworth et al., 2021, Theorem 1).* Previously, (Ramezani-eebr) et al., 2023, Theorem 3) can only match this lower bound with an extra almost sure boundedness assumption.
Algorithm 1 requires each node to send in expectation at most NQ communication bits per iteration, where No = (i.e., the average expected code-length bound). Under the absolute noise model, we can bound GAP of Algorithm as follows with the proof in Appendix E.2:
Em " j=1 Tm..Nq..m.
Theorem 5.5 (Algorithm under Absolute Noise). Suppose the iterates X, of Algorithm I are updated with learning Let
6. Almost Sure Boundedness Model
rate schedule given in (4) for all t = 1/2,1,.... X R.d. be a compact neighborhood of a solution and 1 pup - p Under Assumptions 2.1, 2.2, 2.3, and 2.4, we have
To further highlight the advantages of QODA, we now an- alyze its performance under a setting similar to the global quantization VI-solver Q-GenX, while relaxing another key assumption of co-coercivity. We first present the almost sure boundedness assumption of the operator
E [Gapx (Xe+1/a) (ILD + ||A(XX))la + + + D2)
Assumption 6.1 (Almost Sure Boundedness). There exists J > 0 s.t. [z; S almost surely.
vTK
Under this Q-GenX's setting' for the relative noise case, we can actually obtain the similar rate O(1/T) to Q- GenX (Ramezani- Kebrya et al., 2023, Theorem 4) with- out the co-coercivity Assumption 5.6. We consider the alternative adaptive learning rates with q E (0, 1/4]:
where EQ
>M Σラ Tm. /EQ.E 'T is average
square root variance bound.
Only for the relative noise profile, we introduce a regularity condition of co-coercivity, similar to QGen-X (Ramezani- Kebrya et al., 2023) to obtain the fast rate (1/T)):
t-2
K IV K2
Assumption 5.6 (Co-coercivity). For > 0, we say opera- tor A is B-cocoercive when for all x; y E RRdd
T (1+
+
+IIX,
X [13
(-2
I 1 4-2
22 = +1(+
(A(x) A(y), x y) 2 A(x) A(y)l
(Alt)
K2
The derivation details for this alternative (Alt) learning rates are included in Appendix F.2. Two learning rates allow a larger extrapolation step in the first line of (ODA), so the noise is an order of magnitude smaller than the expected variation of utilities (Hsieh et al., 2022). We now provide the convergence of Algorithm I under relative noise with learn- ing rates (Alt) and without the co-coercivity assumption.
Further details about this assumption in Appendix B.2. With this assumption, we obtain the following faster con- vergence guarantee for Algorithm under relative noise:
Theorem 5.7 (Algorithm I under Relative Noise). Suppose the iterates X, of Algorithm I are updated with learning rate schedule in (4) for all t = 1/2, 1....,T. Let X C Idd be compact neighborhood of a VI solution. Let D² :=
T.
'In (Woodworth et al., 2021) their function F is I-smooth implies that the F,, or the operator in our case, is ipssiiic
OOur guarantees for quantization, coding procedures and con- vergence under absolute noise do not require co-coercivity. It is only used establish the fast rate (1/T) under relative noise.
'In this model, the proposed learning rate (4) and its conver- gence guarantees Section 5.2 still hold.
7

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
225
Baseline Q-GenX
300
Baseline
Q-GenX
250
RID score
150
FID score
200
125
100
75
100
50
150k
200k
Number of steps
Number of steps
CIFARIO
CIFAR
Figure 4. FID evolution during training. We compare basic Adam optimization against QODA-based extension of Adam with global (Q-GenX (Ramezani Hemezani-Keebya al., 2023)) and layer-wise (L-GreCo) quantizations.
Theorem 6.2 (Algorithm under Relative Noise without co-coercivity assumption). Suppose the iterates X, of Al- gorithm are updated with learning rate schedule in (Alt) for all 1/2,1, .I....III ,T. Let X Id be a compact neigh- borhood of a solution for (VI), EQ as in Section 5.2 and 1 = pup [|X 2l.. Under Assumptions 2.1, 2.2, 2.3, 2.5, and 6.1, for Algorithm with learning rates (Ali):
NVIDIA RTX 3090 GPU, multi-node Genesis Cloud enviromment with 5 Ghps inter-node bandwidth. For the communication backend, we pick the best option for quan- tized and full- coll-preciioon regimes: OpenMPI (ope, 2023) and NCCL (ncc, 2023), respectively. The maximum bandwidth between nodes is estimated to be around Gbit/second.
We follow the training recipe of Q-GenX et al., 2023), where authors set large batch size (1024) and keep all other hyperparameters as the original codebase of (Gidel al., 2018). For global and layer-wise 5 bits (with bucket size 128), and run the L-GreCo adaptive compression algorithm every 10K op- timization steps for both the generator and discriminator models The convergence results over three random seeds are presented in Figure The figure demonstrates that the adaptive QODA approach not only recovers the baseline ac- curacy but also improves convergence relative Q-GenX.
Heamezani-Kebbry
E [Gapx (X (x+11/2)] = = (OREO + +5q DRR
T
The proof is in Appendix G. To underscore the significance of eliminating the co-coereivity assumption, note that several important class of games such as bilinear games are not co-coercive. Furthermore, we also include the guarantees for absolute noise for this model in Theorem F.15, where we also obtain the rate O(1V/T) similar to Q-GenX Hemnezani-Kebrye et al., 2023, Theorem 3).
pression,
In order to illustrate the impact of QODA on the wall-clock training time, we have benchmarked the training in three dif- ferent communication setups. The first is the original Gbps bandwidth, whereas the second and the third reduce this to half and 1/5 of this maximum bandwidth. We measured the time per training step for uncompressed and QODA 5-bit training. Here, the optimization step includes forward and backward times. More precisely, the backward step consists of backpropagation, compression, communication and de- compression. Note that time per step is similar for both data sets. Table shows that layer-wise quantization achieves up to a 47% improvement in terms of end-to-end training time. Table demonstrates the scalability of QODA up to 16 GPUs under weak scaling, i.e. with constant global
7. Numerical Experiments
7.1. GAN Training
To further validate our theoretical findings, we have imple- mented QODA in Algorithm based on the codebase of (Gidel et al., 2018) and train WGAN (Arjovsky et al., 2017) on CIFARIO and CIFAR100 (Krizhevsky, 2009). To support efficient compression, we use the torch_egx Pytorch ex- tension (Markov al., 2022). Moreover, we adapt compres- sion choices layer-wise, following the L-GreCo (Markov et al., 2024) algorithm. Specifically, L-GreCo periodically collects gradients statistics, then executes a dynamic pro- gramming algorithm optimizing the total compression ratio while minimizing compression error.
Forr a fair comparison QGen-X, we did not include any additional encoding on top of quantization just as QGen-X did not.
In our experiments, we use nodes, each with a single
8

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
batch size. We observe significant up to 150% speedup in comparison to the uncompressed baseline. Moreover, baseline step time degradation makes the scaling useless, whereas QODA allows to avoid such degradation.
quanti- -zation
test
compression
rank
perplexity
rate
baseline
23.20 =00.0
1.0
global
23.73 1o.18
27
16
layerwise
23.70 1:..3
40.38
[1.47x)
power SGD
32
global
23.54
=o0.3
14.07
Mode
Gbps
2.5 Gbps
Gbpss
layerwise
24.08 111.8
20.90
[1.49x]
Baseline
291
265
251
64
global
23.42
to.13
7.12
layerwise
23.49
to.13
10.84 1152x)
QODA5
197
195
195
Speedup
1.47x
1.36x
1.28x
Table 3. Layer-wise Global Quantization for Transformer-XL.
Table 1. Time per optimization step (in ms) for baseline and QODA5 with different inter-node bandwidths.
262
embreding
Mode
4 GPUs
GPUs
12 GPUs
16 GPUs
baseline
251
303
318
285
25.0
QODA5
195
165
127
115
Speedup 1.28x
1.83x
2.50x
2.47x
Table 2. Time per optimization step (in ms) for baseline and QODAS with different node counts.
7.2. Transformer-XL Training
Figure 5. Ablation Study for Transformer-X XT.
We now showcase the superiority of layerwise methods (I.-
GreCo) global ones by applying quantization on top of powerSGD for training Transformer-XL. on WikiTeext 103. We used the implementation of (Markov et al., 2024) and
8. Conclusion and Future Directions
In brief, we propose the theoretical framework and tight guarantees for layer-wise quantization. We then leverage this quantization scheme to design QODA (Algorithm 1) for distributed VIs with competitive joint communication and convergence rates, Finally, we apply QODA empirically to obtain up to 150% speed up for training GANs.
provide our code in the supplementary material. We used 8 NVIDIA GH200 120GB GPUs for the experiments here.
The results are shown in Table 3, in which we observe the compression rates achieved by the layerwise quantization (with L-GreCo) is consistently higher than that by the global (uniform) quantization given the same parameter for the derlying powerSGD (rank in Table 3). To ensure fair comparison, we trained all the methods for the same iter- ations as the baseline, which is a vanilla training process without any parameter compression, and reached the same perplexity level the latter.
While monotone VIs can cover a wide range of MI ap- plications, there are situations that general non-monotone or (weak) minty VIs are required (lusem et al., 2017; Beznosikov et al., 2022). Hence, for future directions, one may look into communicationa.. communication-effcccent schemes to solve non-monotone VIs with an adaptive layer-wise compres- sion. Moreover, given theoretical guarantees for layer- wise quantization and the communication-effiicee QODA method, subsequent studies might extend these techniques beyond GAN training, for example, to accelerate adversarial training via layer-wise quantization.
To further demonstrate the advantage of performing quanti- zation layer-wise basis, we also conduct ablation ex- periment on Transformer-XL XL. In this test, we compared the test perplexity resulting from quantizing only the position- wise feed-forward layer (FF), the embedding layer, and the attention layer (i.e. the matrices containing all the param- eters of k, q, and 0 at each layer), respectively. We used PowerSGD with varying quantization levels (ranks). Each setup repeated four times with different seeds, and the results are shown in Figure 5. Given the same compres- sion level. quantizing the embedding layer results in much larger drop in performance. This supports our intuition that wise quantization is more beneficial, as different layers exhibit varying sensitivity to quantization.
Impact Statement
We provide substantial theoretical results layer com- pression and VI solvers that contribute to number of sub- fields such as large-scale training, optimization, and general machine learning. Our paper focuses on theoretical advance- ments and does not introduce likely risks relevant to bias, privacy violations, or misuse of sensitive data.

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Acknowledgment
Bauschke, H. H. and Combettes, P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2017.
This work was supported by Hasler Foundation Program: Hasler Responsible AI (project number 21043). The re- search was also sponsored by the Army Research Office and was accomplished under Grant Number W91 1 1-0048. This work was further funded by the Swiss Na- tional Science Foundation (SNSF) under grant number 200021 We also acknowledge project All of the Swiss National Supercomputing Centre (CSCS) for providing computing resources. Dan Alistarh and Ili Markov were supported in part through the ERC Proof- of of-Concept grant FastML (Grant Agreement 101158077). Ali Ramezani Ramezani-Keerya was supported by the Research Coun- cil of Norway through FRIPRO Grant under project number 356103, its Centres of Excellence scheme, Integreat - Nor- wegian Centre for knowledge-drie driven machine learning under project number 332645 and its Centre for Research- Innovation funding scheme (Visual Intelligence under grant no. 309439).
Beznosikov, A., Richtárik, P., Diskin, M., Ryabinin, M., and Gasnikov, A. Distributed methods with compressed communication for solving variational inequalities, with theoretical guarantees. Advances in Neural Information Processing Systems (NeurIPS), volume 35, pp. 14013- 14029, 2022.
Beznosikov, A., Dvinskikh, D., Semenov, A., and Gasnikov, A. Bregman proximal method for efficient communica- tions under similarity, 2023a.
Beznosikov, A., Gorbunov, E.,, Berard, H., and Loizou, N. Stochastic gradient descent-ascent: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 172-235. PMLR, 2023b.
Chambolle, A. and Pock, T. A first-order primal-dual algo- rithm for convex problems with applications imaging. Journal of Mathematical Imaging and Vision, 40(1):120- 145, May 2011.
References
NVIDIA Collective Communication Library. https:// developer deveeoper.nvicia.com www.iiiiiiiio... com caaam//ncc,,0000
Chavdarova, T.. Gidel, G., Fleuret, F., and Lacoste-Julien, S. Reducing noise in gan training with variance reduced ex- tragradient. Advances in Neural Information Processing Systems, 32, 2019.
Open MPI: Open Source High Performance Computing. https: / www. open-mpi pttpen/mmiorrr....... /,23/
Agarwal, S., Wang, H., Lee, K., Venkataraman, S., and Papailiopoulos. D. Adaptive gradient communication via critical learning regime identification. In Conference on Machine Learning and Systems (MLSys), 2021.
Chiang, C.-K., Yang. T., Lee, C.-J,, Mahdavi, M., Lu, C.-J., Jin, R., and Zhu, S. Online optimization with gradual variations. In COLT '12: Proceedings of the 25th Annual Conference on Learning Theory, 2012.
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD: Communication-effiee efficieen SGD via gradient quantization and encoding. In Advances in Neural Infor- mation Processing Systems (NeurIPS), 2017.
Cover, T. M. and Thomas, A. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience,, USA, 2006. ISBN 0471241954.
Antonakopoulos, K., Pethick, T., Kavis, A., Mertikopoulos, P., and Cevher, V. Sifting through the noise: Universal first-order methods for stochastic variational inequalities. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pp. 13111, 2021.
Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H. Training gans with optimism. arXiv preprint 17Xiv:1711.0014 2017.
Arjovsky, M., Chintala, S., and Bottou, L. Wasserstein generative adversarial networks. In International Confer- ence on Machine Learning (ICML.,, pp. 214-223. PMLR, 2017.
Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng H. Train- ing GANs with optimism. In ICLR II: Proceedings of the 2018 International Conference on Learning Repre- sentations, 2018
Ashkboos, S., Verhoef, B.., Hoefler, T., Eleftheriou, E., and Dazzi, M. Efqat: An efficient framework for quantization- aware training. arXiv preprint arXiv:2411.1 1038, 2024.
Dean, J., Corrado, G. S., Monga, R., Chen, K., Devin, M., Mao, M. 7.,, Ranzato, M., Senior, A., Tucker, P., Yang, K., Le, Q., and Ng, A. Y. Large scale distributed deep networks. In Advances in Neural Information Processing Systems (NeurIPS), 2012.
Bach, F. and Levy, K. Y. A universal algorithm for vari- ational inequalities adaptive to smoothness and noise. In Conference on learning theory, pp. 164-194. PMLR, 2019.
Dosovitskiy, A., Beyer, L.,, Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M.,
10

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Heigold, G., Gelly, S., al. An image is worth 16x16 words: Transformers for image recognition scale. In International Conference Learning Representations (ICLR), 2021.
Guo, J., Liu, W. Wang, W., Han, J., Li, R., Lu, Y., and
Hu, S. Accelerating distributed deep learning by adaptive gradient quantization. In IEEE International Conference on Acoustics, Speech and Signal Processing, 2020.
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research (JMLR), 12(7), 2011.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016
Dutta, A., Bergou, E. H., Abdelmoniem, A. M., Ho, C.-Y., Sahu, A. N., Canini, M., and Kalnis, P. On the discrep- ancy between the theoretical analysis and practical imple- mentations of compressed communication for distributed deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3817-3824, 2020.
Horváth, S., Kovalev, D., Mishchenko, K., Richtárik, P., and Stich, S. Stochastic distributed learning with gradient quantization and double-variance reduction. Optimization Methods and Software, 38(1):91-106, 2023.
Hsieh, Y.GG., Jutzeler, F., Malick, J., and Mertikopoulos, P. Explore aggressively, update conservatively: Stochas- tic extragradient methods with variable stepsize scaling. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Elias, P. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21 (2):194-200) 203, 1975. doi: 10. 19.10/9T..1195550555399
Hsich, Y.-G., Antonakopoulos, K., and Mertikopoulos, P. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Confer- ence on Learning Theory, pp. 2388-2422. PMLR, 2021.
Ene, A. and Le Nguyen, H. Adaptive and universal al- gorithms for variational inequalities with optimal con- vergence. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 6559-6567,2002
Hsieh, Y.G.,, Antonakopoulos, K., Cevher, V., and Mer- tikopoulos, P. No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate sep- aration. In Advances in Neural Information Processing Systems (NeurlPS). 2022.
Facchinei, F. and Pang. J.-S. minite-dimensionll variational inequalities and complementarity problems. Springer, 2003.
Faghri, F., Tabrizian, I. Markov, I., Alistarh, D., Roy, D. M., and Hemnezani-Kebrya A. Adaptive gradient quantization for data-parallel SGD. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Huffman, D. A. A method for the construction of minimum- redundancy codes. Proceedings of the IRE, 40(9):1098- 1101, 1952. doi: 10. 1119///PRO..1952200
Frantar, E., Ashkboos, S., Hoefler, T., and Alistarh, D. OPTQ: Accurate quantization for generative pre-trained transformers. In The Eleventh International Confer- ence on Learning Representations, 2023. URL https: //openreview net/ fortm ? iidiidddtftfwwssee
Iusem, A. N., Jofré, A., Oliveira, R. I., and Thompson, P. Ex- tragradient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, (7(2):66-7224 2017.
Jin, Y. and Sidford, A. Efficiently solving mdps with stochas- tic mirror descent. In International Conference on Ma- chine Learning, pp. 4890-4900 PMLR, 2020.
Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, S. A variational inequality perspec- tive on generative adversarial networks. arXiv preprint arXiv:1802.10551. 2018.
Juditsky, A., Nemirovski, A., and Tauvel, C. Solving varia- tional inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-5,, 2011. 2011.
Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste- Julien, S. A variational inequality perspective on genera- tive adversarial networks. In ICLR '19: Proceedings of the 2019 International Conference on Learning Repre- sentations, 2019.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M. Bhagoji. A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., D' Oliveir,, R. G. L., Rouayheb, S. E., Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, P. B., Gruteser, M., Harchaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konečný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Raykova, M., Qi,
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Fariey, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial nets. In Advances in Neural Information Processing Systems (NeurIPS), volume 27, 2014.

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
H., Ramage, D., Raskar, R., Song, D., Song, W., Stich, S. U., Sun, Z.., Suresh, A. T., Tramèr, F., Vepakomma, P., Wang. J., Xiong, L., Xu, Z., Yang. Q. Yu, F, X., Yu, H., and Zhao, S. Advances and open problems in federated learning. Foundations and Trends o in Machine Learning, 14(1-2)11-210, 2021.
Markov, I., Alim, K., Frantar, E., and Alistarh, D. L-greco: Layerwise-adaptive gradient compression for efficient data-parallel deep learning. Proceedings of Machine Learning and Systems, 6:312-324, 2024.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication--fficcenn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273- 1282. PMLR, 2017.
Kamalaruban, P., Huang, Y.-T., Hsich, Y.PP., Rolland, P., Shi, C., and Cevher, V. Robust reinforcement learning via adversarial training with langevin dynamics. Advances in Neural Information Processing Systems (NeurIPS), 33: 8127-8138, 2020.
McMahan, H. B. and Streeter, M. Adaptive bound opti-
mization for online convex optimization. arXiv preprint arXiv: 4908, 2010.
Korhonen, J. H. and Alistarh, D. Towards tight com- munication lower bounds for distributed optimisation. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S., Chan- drasekhar, V., and Piliouras, Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv:1807.02623) 2018.
Korpelevich, G. M. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Mishchenko, K., Wang, B., Kovalev, D., and Richtárik, P. Intsgd: Adaptive floatless compression of stochas- tic gradients. In International Conference on Learning Representations, 2021. URL https: / www.atttttcccoool.e.........o. 247594371.
Kovalev, D., Beznosikov, A., Sadiev, A., Persiianov, M., Richtárik, P., and Gasnikov, A. Optimal algorithms for decentralized stochastic variational inequalities. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pp. 31073-31088, 2022.
Mishchenko, K., Gorbunov, E., Takáč, M., and Richtárik. P. Distributed learning with compressed gradient differ- ences. Optimization Methods and Software, pp. 1-16, 2024.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Mokhtari, A., Ozdaglar, A., and Pattathil, A unified anal- ysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach. ht https: / / f/arxiv.
Levy, K. Y., Yurtsever, A., and Cevher, V. Online adaptive methods, universality and acceleration. In Advances in Neurul Information Processing Systems (NeurIPS), vol- ume 31, 2018
901. 08000811111 1v2, 2019a.
Mokhtari, A., Ozdaglar, A., and Pattathil, S. Convergence of ((1/k) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point prob- lems. https: /ols:///axivve wttp://..rrrgdff///1000 001.9966.11110 01115. pdł, 2019b.
Li, H., Karagulyan, A., and Richtárik, P. Det-cgd: Com- pressed gradient descent with matrix stepsizes for non- convex optimization. In The Twelfth International Con- ference on Learning Representations, 2024.
Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. Feder- ated learning: Challenges, methods, and future directions. IEEE signal processing magazine, 3703):50-60, 2020.
Nemirovski, A. Prox Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz contin- uous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251 2004.
Lin, T., Zhou, Z., Mertikopoulos, P., and Jordan, M. Finite- time last-iterate convergence for multi-agent learning in games. In ICML., pp. 6161-6171. PMLR, 2020.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Ro- bust stochastic approximation approach to stochastic pro- gramming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
Malitsky, Y. Projected reflected gradient methods for mono- tone variational inequalities. SIAM Journal on Optimiza- tion, 25(1):502-53) 520, 2015.
Nesterov, Y. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2004.
Markov, I., Ramezanikebrya, H., and Alistarh, D. Cgx: adaptive system support for communication--ffiee deep learning. In Proceedings of the 23rd ACM/IFIP In- ternational Middleware Conference, pp. 241 241-254, 2022.
Nesterov, Y. Dual extrapolation and its applications to solv- ing variational inequalities and related problems. Math.
12

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Program., 1099-3):319-344, mar 2007. ISSN 0025- 5610.
Tsianos, K. I. and
and Rabbat, M. G. Distributed dual averaging for convex optimization under communication delays. In 2012 American Control Conference (ACC), pp. 1067- 1072. IEEE, 2012.
Nesterov, Y. Primal-dual subgradient methods for convex problems. Mathematical programmingg 120(1):221-25) 2009.
Tsitsiklis, J. N. and Luo, Z.-Q. Communication complexity of convex optimization. Journal of Complexity, 3(3): 231-243, 1987.
Omidshafiei, S., Pazis, J., Amato, C., How, J. P., and Vian, Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In International Con- ference on Machine Learning, pp. 2681 26900 PMLR, 2017.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Atten- tion is all you need. In Advances in Neural Information Prucessing Systems (NeurIPS), 2017.
Oymak, S. and Soltanolkotabi, M. Toward moderate overpa- rameterization: Global convergence guarantees for train- ing shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84-105, 2020. doi: 10.1 109//SAT.2202022993333
Verma, D., Zhang, H., and Ferrari, D. Delay jitter con- trol for real-time communication packet switching network. In Proceedings TRICOMM 191: IEEE Confer- ence on Communications Software: Communications for Distributed Applications and Systems, pp. 3p.35-444 35-43, 1991. doi: 10. 109//ROMM CTT.RIIOO...9911111 152873.
Polyak, B. T. Introduction to optimization, 1987.
Wang. B., Safaryan, M., and Richtárik, P. Theoretically bet- ter and numerically faster distributed optimization with smoothness-awarc quantization techniques. Advances in Neural Information Processing Systems, 35:9841-9852, 2022.
Popov, L. D. modification of the AuroweHurwiez method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845-848, 1980.
Ramezani- Kamezani-Kebrya, A., Faghri, F., Markov, I., Aksenov, V., Alistarh, D., and Roy, D. M. NUQSGD: Provably commanication--effiiee. data-parallel SGD via nonuni- form quantization. Journal of Machine Learning Re- search (JMLR), 22 14):1-43,220
Wang, H., Sievert, S., Liu, S., Charles, Z., Papailiopoulos, D., and Wright, S. Atomo: Communication- learning via atomic sparsification. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., and Li, H. TernGrad: Ternary gradients to reduce communi- cation in distributed deep learning. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Ramezani-Kebryae A., Tabrizian, I., Faghri, F., and Popovski, P. Mixtailor: Mixed gradient aggregation for robust learning against tailored attacks. Transac- tions on Machine Learning Research, 2022. ISSN 2835- 8856. URL https: http://///eeeeeeeeeeeeee n forum? id=tqDhrbKJIS.
Woodworth, B. E., Bullins, B., Shamir, O., and Srebro. N. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Anmual Conference Computational Learning Theory, 2021. URL https: /appi semant escholas ar. org/ :ttp/CoopuI:::::33 :
Kebrya, A., Antonakopoulos, K., Krawezuk, I., Deschenaux, J., and Cevher, V. Distributed extra- gradient with optimal complexity and communication guarantees. In International Conference on Learning Representations (ICLR), 2023.
Xie, W., Pethick, T., Ramezani- A., and Cevher, V. Mixed nash for robust federated learning. Transac- tions on Machine Learning Research, 2024. ISSN 2835- 8856. URL https: http:////ppeeeeeeeeeeeeeee.eee.e net net/forum? forum? i id=mqMzerrVOB.
Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Madry, A. Adversarially robust generalization requires more data. In Advances in Neural Information Processing Systems (NeurIPS), 2018
/
Xin, J.. Ilin, I., Zhang, S., Canini, M., and Richtárik, P. Kimad: Adaptive gradient compression with bandwidth awareness. In Proceedings of the 4th International Work- shop on Distributed Machine Leurning, DistributedMI. '23, pp. 35-48, New York, NY, USA, 2023. Associa- tion for Computing Machinery. ISBN 9798400704475. doi: 01114/5526300488666006888 URL ht ttsp:: :app:s/ne /doi. 84.
Strom, N. Scalable distributed DNN training using com- modity GPU cloud computing. In INTERSPEECH, 2015.
Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
13

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Yu, A. W., Huang, L., Lin, Q.. Salakhutdinov, R., and Car- bonell, J. Block-normalized gradient method: An empiri- cal study for training deep neural network. arXiv preprint arXiv: 2017.
Yuan, D., Xu, S., Zhao, H., and Rong, L. Distributed dual averaging method for multi-agent optimization with quan- tized communication. Systems & Control Letters, 61(11); 1063-1061, 2012.
Zeiler, M. D. and Fergus, Visualizing and understand- ing convolutional networks. In Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6- 12, 2014, Proceedings, Part I 13, pp. 818- 833. Springer, 2014.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning (still) requires rethinking generalization. Commun. ACM, 64(3):107-115, feb 2021. ISSN 0001-0782. doi: 10. 10.1145/34 URL https:
//doi. aaggioorg/lee 110 11 141444434467
Zhang, H., Li, Kara, K., Alistarh, D.,
Liu, J., and Zhang, C. ZipML: Training linear models with end-to-end low precision, and little bit of deep learning. In International Conference on Machine Learning (ICML), 2017.
Zheng, Q. Tian, X., Jiang, N., and Yang, M. Layer-wise learning based stochastic gradient descent method for the optimization of deep convolutional neural network. Journal of Intelligent & Fuzzy Systems, 37(4):5641-563 2019.
14

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
A. Addition Information
A.1. Further Literature Review
For empirical risk minimization, adaptive quantization adapt quantization levels (Faghri et al., 2020; Wang et al., 2018) and the number of quantization levels (Guo et al., 2020; Agarwal et al., 2021) over the trajectory of optimization. Previous studies show that these adaptive methods offer tighter variance bounds than non-adaptive ones (Mishchenko et al., 2021).
These quantization schemes are global w.E.. layers and do not take into account heterogeneities in terms of representation power and impact on the learning outcome across various layers of neural networks. Markov et al. (2022; 2024) have proposed unbiased and layer-wise quantization where quantization parameters are updated across layers in heuristic manner and have shown tremendous empirical success in training popular DNNs in large-scale settings.
Recently, Quantization-Aware Training (QAT) methods seek to produce models with quantized weights and activations during training, and as such, compress these elements during the training process (Frantar et al., 2023; Ashkboos et al., 2024). Furthermore, Post- Training Quantization (PTQ) techniques aim do so in a single compression step, e.g. by using layer-wise solvers find a good quantized weight assignment (Frantar al., 2023; Ashkboos et al., 2024). By comparison, our focus is on gradient compression: we aim to reduce communication overhead during distributed training by applying a layer-wise quantization scheme to gradient updates. This objective is orthogonal to that of QAT and PTQ. so our method can be combined with either approach to further improve end-to-end efficiency.
Unbiased quantization provides communication efficiency on the fly for empirical risk minimization, i.e., quantized variants of SGD converge under the same hyperparameters tuned for uncompressed variants while providing substantial savings in terms of communication costs (Alistarh et al., 2017; Wen et al., 2017; Zhang al., 2017; Faghri al., 2020; Ramezani- et al., 2021; Markov et al., 2024; 2022).
Beyond distributed VI settings, extra gradient methods and their optimistic variants have long history in the field of optimization. Extra-gradient, first introduced by (Korpelevich, 1976), is known to achieve an optimal rate of order (1/TT) in monotone VIs. This method has been further extended in (Nemirovski. 2004; Nesterov, 2007) by introducing Mirror and its primal-dual counterpart tttappetttpootiinn However, all these methods require two oracle calls per iteration (one for the extrapolation and one for the update step) which makes them more expensive than the standard Forward/Backward methods. The first issue to address this issue was Popov's modified Arrow-Hurwicz algorithm (Popov, 1980). To that end, several extensions have been proposed such as Past Extra- gradiet (PEG) from (Chiang et al., 2012: Gidel et al., 2019), Reflected Gradient (RG) from (Chambolle& & Pock, 2011; Malitsky, 2015), and Optimistic Gradient (OG) from (Daskalakis et al., 2018; Mokhtari et al., 2019a;b).
A.2. Comparisons to Related Methods
Improvements over Q-GenX (Ramezani-Kebrya et al., 2023): Our proposed algorithm QODA (Algorithm 1) essentially consists of a distributed VI solver- Optimistic Dual Averaging (ODA)- and a layer-wise compression general framework (Section 3). We will now state our improvements with respect to both the optimistic VI solver and layer- layer-wise compression framework:
Optimism: Our optimistic dual averaging distributed update step (ODA) reduces one extra gradient step compared to the extra-gradient approach of Q-GenX, hence reducing the overall communication burden by half.
Relaxed Assumptions: Our algorithm QODA also requires fewer assumptions than Q-GenX (Remark 2.6). In particular, we obtain joint communication and convergence guarantees without the almost sure boundedness of the dual vectors.
Layer-wise Compression: Our layer-wise compression framework is much more general and is always better than the global compression framework in Q-GenX (Remark D.3). Our compression framework also comes with two fine- tne-grained coding protocols, among which the Alternative Coding Protocol is generalization of Q-GenX coding protocol while the Main Coding Protocol is novel.
Experimental Results: We improve the convergence relative to Q-GenX in training WGAN (Figure 4).
Rigours Formulations and Tight Guarantees for Layer-wise Compression such as L-Greco (Markov et al., 2024): We provide a novel and general theoretical formulation and establish guarantees for adaptive layer-wise quantization with tailored coding schemes, which is not studied in L-Greco. Layer-wise wise quantization schemes such as L-Greco have only been studied empirically without strong theoretical guarantees to handle the statistical heterogeneity across layers and over the course of training. Our tight variance and code-length bounds actually hold for any general layer-wise and unbiased
15

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
quantization scheme. Under the special case of L normalization and global quantization, our variance bound matches the lower bound from Himmernni-Kebbya et al., 2021, Theorem 7) (more details in Remark 5.2) while our code-length bound is optimal in the problem dimension with respect to the lower bounds from (Korhonen & Alistarh, 2021; Tsitsiklis & Luo, 1987) (more details in Remark 5.4).
Remark A.1. In brief, a combination of QGen-X and L-Greco does not represent our novel and general layer-wise framework with the corresponding theoretical guarantees and an associated fine-grained coding analysis while performing twice the number of gradient computations as do.
Comparison to Block Quantization (Mishchenko et al., 2024; Horváth et al., 2023; Wang et al., 2022): We highlight that block (p- >quantization is fundamentally different from layer-wise quantization in our paper. As Mishchenko et al. (2024, Definition B.1) suggests, the various blocks here follow the same scheme that is p-quantization (Quant,)) which is explained in (Mishchenko et al., 2024, Definition 3.2). Here are three fundamental distinctions between block quantization and our layer-wise quantization:
Each of our layer or block in this context has different adaptive sequences of levels (Section 3). This is why our method is named "layer-wise." (Mishchenko et al., 2024) on the other hand applies the same p-quantization scheme Quant, blocks with different sizes, implying that the nature and analysis of two methods are very different. Hence block quantization is not "layer-wise," and its analysis does not apply to the convergence of our methods.
The way the quantization is calculated for each block layer different. Mishchenko et al. (2024) study and provide guarantees for the following type of p-quantization (for all blocks): A || sign(A) o &, where the are stacks of random Bernoulli variables. In our work, the sequence of levels for each layer is adaptively chosen according to the statistical heterogeneity over the course of training (refer to (MQV)).
The guarantee in (Mishchenko et al., 2024, Theorem 3.3) only cover p-quantization rather block p-quantization. In our Theorem 5.1, we provide the quantization variance bound for any arbitrary sequence of levels for each layer in contrast to that for only levels based on p-quantization (Mishchenko et al., 2024).
In brief, the block quantization is similar to bucketing in unbiased global quantization - QSGD (Alistarh et al., 2017), NUQSGD Kearezani-Kebbya et al., 2021) - which takes into account only the size of different blocks (sub-vectors), while for layer-wise quantization we take into account the statistical heterogeneity and impact of different layers on the final accuracy. Due to fundamental differences, our variance and code-length bounds require substantially more involved and different analyses that possible by simple extensions of block quantization in those works.
Comparison with (Dutta et al., 2020): They study a similar method to block quantization but using the same name "layer-wise quantization" to our framework. In short, the authors propose to use the same quantization operator for each layer, i.c. breaking the stochastic gradients into different blocks corresponding to different layers before quantization. Furthermore, their analysis only concerns with the relative noise case, obtaining a slower rate (VVT).
B. Variational Inequality Background
B.1. GAP
Several properties of (GAP) have been explored in the literature (Nesterov, 2009). In particular, the following classical result characterizes the solutions of (VI) via zeros of (GAP).
Proposition B.1. (Nesterov, 2009) Let C Rd be non-empty and convex set. Then, we have
( 2 0 for all á E X;
If GAPx x a = 0 and X contains a neighbourhood of i. then à is a solution of (VI).
B.2. Co-coercivity Assumption
We recall the co-coercivity assumption (Bauschke & Combettes, 2017) is as follows
Assumption B.2 (Co-coercivity). For O, we say operator A is 3-cocoercive when
(A(x) A(y), x y) 2 (1)(() A Væ, Rd.
16

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Note that by Cauchy-Schwarz, further deduce for a co-coercive operator
[|A(x) - - yl12 2 (()A(()) - A(y) 12.
implying
| - 1--yl 2 3 11({)) - A(v)l1
We refer the readers to (Bauschke & Combettes, 2017, Section 4.2) for further properties of co-coercive operators.
B.3. Relative Noise Examples
Here provide two examples in practice where the noise profile can be characterized as relative noise:
Random coordinate descent (RCD): At iteration t, the RCD algorithm for smooth convex function over ER draws coordinate & [d] uniformly random and computes the partial derivative Vi Of f The i-th derivative is updated as X = Xit d- Viet for step-size a > 0. This update rule can also be written as x = x og((x; (4) where 9: (x: μu) = 1..fffāzz a and is drawn uniformly at random from the set of Idd basis vectors {ei,..., ed Since 0f/ = at the minima of f. we also have g (x"; ;4) = 0 x" is minimizer of f. i.e., the variance of the random vector g x; μu) vanishes at the minima of f.
Random player updating: Given N N-player convex game with loss functions fi, E [M]. Suppose, at each stage, player i is selected with probability p; to play an action following its individual gradient descent rule X, = Xx,, + ht/p/ Vi, where V V.fa (X₂) denotes player i individual gradient at the state X₁ = (X1.,...., XN,e) and pæ is included for scaling reasons. One can show that all individual components of A vanish at the game's Nash equilibria.
C. Proof of Quantization Variance Bound
Theorem 5.1 (Variance Bound). With unbiased layer-wise quantizaatinn with L normalization of vector Rd. Le. Eayy 1Q (v)] v. we have that
[1](LM(V) - -1l S E
(5)
where EQ = JEM -1) 4e3
+ (EM d mimnaay - 1)1fd 2 deh } + (EM1)2 minna oe 1sd < d
Proof. First let us remind ourselves of the notations in the main paper. Fix time t. Let the normalized coordinates be u. Let (t maxesi$am. 1/ and (M smx M edd Denote the largest level among the M sequences ENd maxigmEM CNM Also let deh = 22/22)mmin/22. Let B = [ey ettl for m E [M], [am]]
Now, we can rewrite the equation (Var) for a fixed time l follows
M
Egys [1IQLAr (v) U1 = ||0 ?
Σ
Σ
(T)
m=1
M
||001 1
pm (ms)+)+1 - u;)( (m)(
Uy m5
M
||l
Σ (CT uc u; +
(e u:)(u; - eg))
m=1
M.EB
We now find the minimum km satisfying (eT
us) - (T) < kmu for us E BT for m E [M] j E [am]- Let
u; = 0 for < 0 S pm / Then, we have
( v:)(uu - CT)
( PT
0) 1)
(ftt//eT 1)2
m
max 1<85 17
0))
max 15850T-11e
02
4(e7+1/050
17

---

Layer-wisc Quantization for Quantized Optimistic Dual Averaging
where the last equality follows from simple differentiation with respect to 0. Since the function (xr 1)2/(4x) is monotonically increasing function for x > 1, we obtain
(7t1// ee 11
(EM - 1)?
5+1 /41/ey)) eeg))
4Ph
which leads to
Oryz
Cm
(e /4t// - 1)2
Σ
Σ
(5+1 ui)(u: 29
k U
U
4(0 (gg)
j=1 "E
j=1 u
j=1 N
(M 1)2
(EM 1)2
"
Σ
u
46M
4PM
j=1 U.EB
My M1 /55""
yielding
Cnn
M
(PM - 1)2
(EM 1)2
|
ΣΣ j= E
Σ
(ett u14 egt) S || 2 Σ
E
us = 11012
Σ
Σ
u
4QM
4CM
a, ES /B0
My ES
(EM
1)²
1
(
1)²
< |/
|1012-
4PM
|
4EM
Next, we attempt to bound Em= En,eBg (eT u.)u, with these two known lemmas
Lemma C.I. Let u E Rdd Then, for all 0 < < 9. we have ||lll S ||1||p S d //1//l////lll This holds even when q < 1
and || || is merely seminorm.
Lemma C.2. where
et al., 2021, Lemma 15) Let p E (0, 1) and u E Bo. Then we have u(t1 - u) S K2P--P1
1/p
1/p 1-p 2/p -
Kp 2/p -
Now, from these two lemma, for any < p < 1 and q S 2, we obtain that
M
M
M
a
2
Σ (CT
u.)u
Kp (PT
2-
q
M.
m
My.
T22
M
by P
= =|10||
TM
< K (2 01 2|2-p
m
B
S K
2 p (EM p/ 1
where the penultimate inequality holds due to the first given lemma and ||00|1 S ||0a|2 for q > 2. Now combining the bounds, we obtain
(ēM -1)2
Ey 11 10--ll ( <
+ k2(()))--d--1/2
||0|
4PM
Moreover, g 2 1, note that |1012 < ||001/2 101l?-00 2-p |ل
2-2
yielding
(1M-1)²
(RM
By Q1 (v) x
4PMM + K2 (2M)) 2 p mi |10113.
Now we can minimize EQ with finding the optimal p" by minimizing
1/p ( 1/pp 1-p
1-p ul-p= = (2-p)-- 21 p
A(p) 2/p
(2/p-1)
-1-p
1
1 pp
2/p
--p
2 - p
18

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
where U = eg dimutaau) This is equivalent to minimizing the log
log X(p) = (p - 2) log(2 p) + (1 - p) log(1 - p) + (1 - p) log(u)
Setting the derivative of log X(p) to zero, we have
-1 + log(2 p3) + 1-o(11 - p²) + log(u) = 0,
yielding the optimal p" to be
v
V V 2 or d2 deh
p'
0,
or der.
In brief, we have
(BM 1)²
+ (11 dinttrd 1)1(d den + - (dddddmaaa lld < den
EQ
4PM
D. Coding Framework
D.1. Proof of Code Length Bound for Coding Protocol
Theorem 5.3 (Code-length Bound). Let f3 denote the probability of occurrence of ET for m E [M] and [amm] Under
the setting specified in Theorem 5.1, the expectation Ea ENG (QrMM w)) IL of the number of bits is bounded by
Ew Eg
[ENC (QLM (g(a;w));
M
M
Po
m
log D7 1md
(6)
mP
where nthh is the proportion of type m coordinates.
Proof. We first use a constant C, bits to represent the positive scalar ||ll| with a standard 32-bit floating point encoding, We now carry out the encoding and decoding procedure in parallel for each of the M types of coordinates. We use bit to encode the sign each nonzero type-m entry. Next, probabilities associated with the symbols to be encoded, i.e.. the type-m levels, can be computed using the weighted sum of the conditional CDFs of normalized type-m coordinates as follows.
Proposition D.I. Let j [om]] have the probability 17 of occurrence of CT is
D P
u 5- dF (u) +
s+1
d.
Jen
pm
3+1
where (u) is the weighted sum of the type-m conditional CDFs in (2), Hence we get
mm
pm
pm
po Pr((T)) =
(u)
Fm
(u),
Eg
pm
pm
fm
21
pm
pm
m +1
Pr(
m
(u)
=
Om
(u).
pm
pm
From
am
mm
Then, we can get the expected number of non-zeros after quantization.
19

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Lemma D.2. For arbitrary Rd, the expected number of non-zeros in Q (v)
is
M
E (v)loo = _
(1
Po
p pmd d.
m=1
The optimal expected code-length for transmitting one random symbol within one bit of the entropy of the source (Cover Thomas, 2006). Hence, we can transmit entries of normalized u in at most Em (Hm) + +1 pd'd,, where j²"h the proportion of type-m coordinates w.rt all coordinates and H( - mm Pj
log(p)) is the entropy in bits.
In brief, obtain
M d
E, By (ENC(QLM (I(x:)) = C. +
Σ
(1-Po
-1-
Po
Σ
Pj log(0"") + 1
112 mml
M
M
0
Σ
py log
umdd
m==
m=
j=1
as desired.
D.2. Alternative Coding Protocol
..... amm +-1+ be the collection of all the levels of the sequence etmm Let S2 = - A be the collection of all the levels of M sequences at time I. The overall encoding, i.e., composition of coding and quantization, ENC([|vlly s, que.ar) R_ x [=1]d yd + {0, 1}r uses a standard floating point encoding with Cy bits to represent the non-negative scalar lllg. encodes the sign of each coordinate with one bit, and then utilizes an integer encoding scheme (D..M)d - {0, 1}* efficiently encode every quantized coordinate with the minimum expected code-length. To solve (MQV), we sample Z stochastic dual vectors (1( wi)..... g (z;;ww)), Let F. denote the marginal cumulative distribution function (CDF) of normalized coordinates conditioned on observing (Zg llg. By law of total expectation, for L. E LtM,, (MQV) can be approximated by:
Let A = =m ........ pt.m gl.m
M
Cnn
min Σ
(
1
Σ
og ( dF; or min Σ
( dF((u),
where F(u)= Ei= F=))( is the weighted sum of the conditional CDFs with
z (1 ll)
A = (1 w. ||2/
(8)
Remark D.3. We note that the Main Protocol offers higher compression ratios through code- word sharing across different types. The improved compression ratio comes the expense of increased encoding and decoding complexity along with possibility of increased re-transmission overhead in case of unstable networking environment. When the end-to-end delay for message passing in the underlying network is highly random such as jitters (Verma et al., 1991), Alternative Protocol will be optimal since every quantization level for every type has a unique code-word. However, Main Protocol will possibly require several transmissions in case of unstable networks. When the network is stable and delays are deterministic, we propose to adopt the Main Protocol. Our coding alternatives provide a trade-off between compression ratio, re-transmission probability, and encoding/decoding complexity.
D.3. Further Details on Coding Framework
The choice of specific lossless prefix code for encoding au .r relies on the extent to which the distribution of the discrete alphabet levels is known. If we can estimate or know the distribution of the frequency of the discrete alphabet M we can apply the classical Huffman coding with an efficient encoding/decoddng scheme and achieve the minimum expected code-length among methods encoding symbols separately (Cover Thomas, 2006; Huffman, 1952). On the other hand, if
20

---

Layer-wisc Quantization for Quantized Optimistic Dual Averaging
only know smaller values are more frequent than larger values without knowing the distribution of the discrete alphabet. can consider Elias recursive coding (ERC) (Elias, 1975).
The decoding DEC: {0, - - I first reads Cg bits to reconstruct ||m||q-- then applies decoding scheme V -1 [0, +
(I to obtain normalized coordinates.
Given quantization levels e and the marginal PDF of normalized coordinates, nodes can construct the Huffmann tree in parallel. A Huffman tree of source with 8 + symbols can be constructed in time O(s) through sorting the symbols by the associated probabilities. is well-know that Huffman codes minimize the expected code-length:
Theorem D.4. (Cover & Thomas, 2006, Theorems 5.4.1 and 1) Let Z denote random source with discrete alphabet
Z. The expected code-length of an optimal prefix code to compress Z is bounded by (Z) S [[L] - H(Z) + 1 where H (Z) < log2() Z)) is the entropy of Z in bits.
D.4. Proof of Code Length Bound for Alternative Protocol
Theorem D.5 (Code-length Bound for Alternative Protocol). Let Pz denote the probability of occurrence of of for m E [M] and j E [am]] Under the setting specified in Theorem 5.1, the expectation EnglEg [ENC (QLM (g(x; L of the number of bits under Alternative Protocol is bounded by
E, ENC (QLM (I(33))); =0 -0((->
M
M
Pu
T
Σ m=
Pj th
log Pj )d)
112
Proof. We first use a constant C, bits to represent the positive scalar ||ll, with a standard 32-bit floating point encoding. Then we use bit encode the sign of each nonzero entry of u. Next, the probabilities associated with the symbols be encoded, i.c., the levels in Q., can be computed using the weighted sum of the conditional CDFs of normalized coordinates as follows.
is Proposition D.6. Let j E [0mL), we have the probability Pl of occurrence of ET
pm dF(u) + 1
pm - V
pf = Pr((T)
dF(u),
where F()) is the weighted of the conditional CDFs as defined in (7). Consequently deduce
pm
gm
P0 = Pr(
dF(())
dF(u).
Pm
pm
gm Ovm
pm Oun
Pom +1 Pr(e
dF(u) =
dF(u)..
pm
pm C
pm
Then, get the expected number of non-zeros after quantization. Lemma D.7. For arbitrary E Rd, the expected number of non-zeros in Q (v) is
M
E ( (o)llo}
Po
d.
The optimal expected code-length for transmitting one random symbol is within one bit of the entropy of the source
(Cover& & Thomas, 2006). Hence, we can transmit entries of normalized u at most (MM.) H(m)) + 1) d, where (E")) = - 1 pr log(p"") is the entropy in bits.
In brief, obtain
M Σ
Eng By aM
ENC (Q (p(x: = C. + 1
Po
d +
Σ
H(em) ) +1 d.
m=1
m=1
21

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
D.5. Unbiased Compression under Both Noises Profiles
The following two lemmas show how additional noise due compression affects the upper bounds under absolute noise Assumption 2.4 and relative noise models Assumption 2.5, respectively. Let's keep in mind that 91 PQ represent d variables sampled independently for random quantization, and qu is independent of random sample w ~ I..
Lemma D.8 (Unbiased Compression under Absolute Noise). Let E X and w P.. Suppose the oracle g(x;w) satisfies Assumption 2.4, Suppose QL satisfies Theorem 5.1 and Theorem D.5, then the compressed Q1, (g(x:w)) satisfies Assumption 2.4 with
E [lQQLM (s(aww) A( S E + +2|A(()) + o
Proof. The unbiasedness property immediately follows from the construction of the unbiased quantization QLA. Next, we note that that the maximum norm increase when compressing QI (Q(=:w) occurs when each normalized coordinate of w(:;w), (u, hela, is mapped to the upper level en (w,)- for some E [M] We can show bounded absolute variance as follows
E Eg (g(x:w)((w - A(x) [5]
= E, g
[1Q (g(x:w)) - g(>;w) + g(x::w) - [ [1Q M (g(#:w)) - g( + EN (1x
= E Ba
S Ew
[1g();)))1 + 02
= Eq [||A(z) + (x; + o²
= =EQl |l (Ax))(; + =q (
+o²
S A(x))((x)) +EQ²² +o²
where the second equality occurs due to unbiasedness of qLM, the third steps follos from Theorem 5.1, and the last inequality holds according to Assumption 2.4 for g(æ; w).
Now note that in Theorem 5.5, D := sup | 21 where X c Rd is compact neighborhood of a VI solution. Since A is L-Lipschitz (Assumption 2.3), we note that
[|A(X)) A(=) - 12 - =013 D2D2 V
Since X1 is our initialization, A(X1) has finite value, so A(x) is bounded for all x E X. Hence for the quantization in Algorithm 1, we can obtain
|A(x)) 21)) A(x) $ 211
which implies the desired conclusion.
Lemma D.9 (Unbiased Compression under Relative Noisc). Let X and w ~ P. Suppose the oracle g(x;w) satisfies Assumption 2.5. Suppose Q satisfies Theorem 5.1 and Theorem 5.3, then the compressed QIM (g(#; satisfies
Assumption 2.5 with
E [||Q (g(z;))) A(x) < + +Eo + +R))
(9)
Proof. The unbiasedness assumption holds similar to D.8. We can show bounded absolute variance as follows
Ew E [[]Qr (g(x:w)) - A(x) I = Ba [1[Q (g(=;w) - g(x;w) + g(x:w) A
Eg, [l M (g(=:w) - g(=:w)ll + E, [I[[(=:
S En |||9(0); W) [|3] + R {<
= =Eq [||A(x)) + ( | + +
= =eql EQ E.. (1) w|] + a A(x)
S (EQσn Eq + Rn) A
where the second equality occurs due to the unbiasedness of qr the fifth equality holds because of the unbiasedness of the noise model and the last inequality holds according to Assumption 2.5 for g(x;
22

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
E. Analysis in the General Setting
E.1. Template Inequality
Proposition E.1 (Template Inequality). Suppose the iterates X, of (ODA) are updated with non-increasing step-size schedule Y/s and qu as in (4) for all 1/2,1, 1.... Then for any X E R.,, we have
|
U
Vast1/2 V 2
X 1
1+/2 X
21
2K 2
2TT
k=1
Proof. First, decompose the LHS individual term
1
Ek K
(he-1/2,x4411/1 x) into two terms follows
K
K
X - X = -A+B.
K
where
K
K
A
Σ
V X41122 - Xe+1 - B= K
(4441/2XX4+1 - X
K
From the update rule of ODA (with me), note that
B (Ye Y41, X X)
Y; 7741 Y 1+1 Xx+1 Xx)
Nh+1 Y441
X141, -x) x)
T/t
(1 -1)
11)
(n.Y -1411 10411 X141 x)+ +
(-14221441 X141 - X)
M/41
170
(X2 -(X,
X x++1 - Xx +
1 1
1
(X1-X141, X141 - X)
1)c
7t++1
7/
(IXx,
x13
1X, - x1-1112 - ||xe+1- -x113)
2Tj
1
1
(I|XI x1 -1x - Xe+1112 - || - x113)
20j++1
27/(
1
1
1)
Xxx
XII
1 - Xe+1
|| - x11
||x - XI3,,
21je
2np
21/++1
21/++1
21jr
1)
the last inequality holds as the non-positive term inequality as
|X| | - X
1 is dropped. We can rearrange the above
27/1+1
211²
||x++1
XII
<
-
1
-11
-11
- -
_1 1||x,
Xe+1 12-
1
1
|
B
21/111
2111
21/
21/+1
21///
1
1
1
1
1|X,
x113
_IX,, 1|x,,
X
13.
||x11
=2n
21
27++1
21//
)
1
1k411/2
X
Xx+1
V ha41122 X x)
(*)
K
K
Next, also by the update rule (with 7)), we have for any X Rd
K
K
T
Ve 1/2 X141/2
X
X
k==
(X, - Xe+1/22 X1+1/2 X)
1 - x1i
1
X Xe+1/211 [X XI3
1
23

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Substituting X X441 and dividing both sides of the inequality by Me. have
1
Vg 1 1/2, X/+1/2
X1+1
K
| X
||x 11+1/211
|
Xe+1lle.
2Tp
2T)t
21
Combining (*) with (**) and after some rearrangements, we obtain
K
( 2n 21/
1/ X2+1/2 X
$ 277
|X XII
|x, - -x
K
200+1
K
+
Vk.+1/2 (4.-112:- Xe+1
K
k=1
|| Xx X x+11/211
|X X++1 12.
27p
2fje
Then, by summing the above expression over f = 1,2.... ..... , and with some telescoping terms, we obtain
T
K
( (2 2m
1 1 - x1
Σ
V Xx+1/2 -
| - xIe
2 |Xr+1- - -x11 +
K
2m71
[=1
T
K
Vi.421/2
V X2t1/2 - Xe+1
t=1
T Σ
|
X X++1/211
1| 1
27
2T
Next we consider the substitution X1 which is just for notation simplicity and can be relaxed at the expense of obtaining slightly more complicated expression. We can further drop the term
|
-X to obtain
21/T+1
K
Vr.41/2, X1+1/2
X
<
|
(V.041/2 - V2,c-123) Xet1/2 X1+1
K
21/++1
K
T
T
1
||
X++1/211
Σ
||
X1+1112.
(t)
217
217:
Note that by Cauchy-Schwarz and triangle inequalities, we have
1
Σ (V.441/2 - V2.--/2)= Xi+1/2 - -x++1
Vx.4+1/2 - VK.0-1/20 Xet1/2 - XIt1)
K
k=1
K
X1+1/2 - Xx+1
V - V/,c-1/2
K
Combining with the AM-GM inequality of the form
K2
xy -
+
2K
21/.
deduce from (f) further that
T
K
1
VE.+1/2 Vea-112) Xe+1/2 - Xet1
K
Tht
VR.e-1/2
Σ
1
|
X1+1
(it)
2K2
2n
24

---

Layer-wisc Quantization for Quantized Optimistic Dual Averaging
Plugging (t1) into (f), obtain
| 20/++1
V X
T 2k²
VK.41/22 - V2.1-1/3
Σ tml
X
X141/21l
21):
Am
as desired.
E.2. GAP Analysis under Absolute Noise
We first introduce following useful lemmas that will help bound the (GAP):
Lemma F.2. (Levy et al., 2018; McMahan & Streeter, 2010) For all non-negative numbers 01,::11 Ot it holds that
T at
at S
at
04
Lemma E.3. (Bach & Levy, 2019) Let C Rd be convex set and h C - R. be I-strongly convex w.E.. norm || Assume that h(x:)) minzec l(x=)) < for all a: E C. Then, for any martingale difference (z:) E Rd and any C,
D
E
Zt,
Σ
El|
(10)
Now we state and prove the complexity of Algorithm under absolute noise and fixed compression scheme. Theorem 5.5 (Algorithm under Absolute Noise). Suppose the iterates X, of Algorithm are updated with learning rate schedule given in (4) for all 1/2,1, 1, .., T. Let X I& be compact neighborhood of VI solution and D suppex [|x pl2.- Under Assumptions 2.1, 2.2, 2.3, and 2.4, we have
E Gapx (X++1/2)
((LD + [|A(X1))22 + o) + + + D&12 D VTK
=0
where EQ = M Σj / is average square root variance bound.
Suppose first that no compression is applicd, i.c., EQ = Using the result of the template incquality Proposition E.1, we can drop the negative term to obtain
Proof.
X
T
V X X
Tt
V2,e+1/2 1/,2-1/2212.
K
2mp+1
2K2
Next expand the LHS with the absolute noise model Assumption 2.4 as follows
1
LHS
11(X++122)
X
Un (xxxx111)) X
K
K
E=
Σ
Ax(X), X -X
Σ
(
K
K
K
T
T
T
K
(x),
X1+1/2
Σ
X
Un U2(( X
K
K
1=1
1=1
1=1
T
Σ
Σ
U X x),
K
K
t=1
25

---

Layer-wisc Quantization for Quantized Optimistic Dual Averaging
where the second inequality follows from the monotonicity of A and XT+1/2 Ei= X441/2/T. Plugging this back the result from template inequality with some rearrangement, obtain
K
X
T
X111/2
+
|Va44122 1/2-1/2112
K
T
21T+1
2k
(=1
K
Un (2++1/2)))
K
k=
By taking the supremum over X, then dividing by T and then taking expectation both sides, get
K
sup
1
x)
$ T (SI + S2 + Sz),
K
where
D2
T
K
S
E
S2
V V4.441/2 - V
21/T+1
2k
R=
S3 = E
sup
K
Us(X, (x((x+112) -xx+1//)
X4t11a)
K
Here make important observation that
K
2
K
E
Ve.41/22
V1,0-1/2
1
S 2E
Σ
| - Ax
K
+ 21E
U1a(X - Un( -
k=1
< L'E
| - 11:22-X-11111 X
+4Ko²
< 2KL 4Ko2,
(11)
where the second inequality comes from I-Lipschitzness the operator for the first summand and the absolute noise assumption for the second summand. Now we proceed to bound these terms one by one. For Sj, from the choice of learning rates S 1, with Equation (11) obtain
S D
1
Vi.41//2 V
D
1
E
Va441/2 V
K2
2T I D + 20
D2
K
26

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Next, we proceed to bound 2₂
K
S2 = E
N
Vi4411/2 1/21-1/2122
2K2
T
K
T
K
E
1h
M++1
|V2,41/2
1/20-122122
+
7h- V 2K
V,,+1/2 - Vn,e- 112
2K
2K
k=1
$ B
1++1 2K²
(2KL2D2 + 4Ko0)
2K
T K
|VA441/2 - VR, 1/21///2
B
(from Equation (11))
2
//att1/2 V1/2-112 2 /K2
[=] k=1
14 Σ s= Ex=1
K
1
Vest1/2 -Vao-1/11 12
<2L2D2 + +402
=
1 + K2
(from Lemma E.2)
2
t=1 k=1
2T 2 + 20
s 22 2
2V
1+
K
Lastly, let's consider S3
T
K
|
T
K
(2((x112))x+11/)) )
S = sup
Σ
-E
sup
Σ
K
K
We can bound the first term with Lemma E.3 as follows
D
T
K
DooTT 2/K
E
sup
Σ
(2(X)112))xx
I
E
|R,,41/2112
S
X
t=1
1==
2K
k=1
For the second term, use law of total expectation
E
U2(X(1/2)) -E
E
(Ux((())))) Xx41/22 [X411/2]
implying S3 S
D 2VK
Combining the bounds St, S2 and Sz, we finally obtain the complexity without compression as
K (
x) S t
VTD2L2 =
D2
[Gapx (8+41/2)]
sup
K
VK
VTK
Now, we consider applying layer-wise compression to this bound. Firstly, recall that the average square root expected code-length bound is denoted
T /Q.ma
T
Finally, by applying compression bound Lemma D.9 along the ideas of (Faghri et al., 2020, Theorem 4) and (Ramezani- Kebrya et al., 2023, Theorem 3), we get the desired result
E [Gapx (8+11/2)]= =0 ((LD (A(()))ll + t0)5 1212
VTK
27

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
E.3. GAP Analysis under Relative Noise
Theorem 5.7 (Algorithm 1 under Relative Noise). Suppose the iterates Xt of Algorithm I are updated with learning rate schedule in (4) for all 1/2, 1/., Let X C B be compact neighborhood of VI solution. Let D :=
suppex ||X1 pll Under Assumptions 2.1, 2.2, 2.3, 2.5, and 5.6, have
E [aapx (X++1/2) = ( (LonEe + EQ + oR (RR D2
TK
where EQ = >m Ej=1
Tm.eq.m. a T is the average variance bound.
Proof. Plugging X into part of the LHS of template inequality Proposition E.1 and then taking expectation, we obtain
K
X xxr )
K
km1
K
E
(V Xx-1/2 - Xx)
= E
(A
(x xx)
K
K
k=1
E [(A
X2+1/2 -x)) 2 E [A((++112)
A(X*)
X X*)
1 K
B
z BE [1A4(X+1/22)11)) 3IE
Σ |A(( K
2
+
where the fifth step occurs due to the B-co-coercivity assumption and the last step follows from this inequality resulted from Assumption 2.5
I 1 ||V,,+1/2 + UK,4+1/2 1 s 2 + 2||U (2 20 lo
Plugging this back into the template inequality, we deduce
8
T
K
1/221/22122
SE
+
T
Tkt
K
Va,+1/2 - Vr, 1/2
2 T
Σ
||,
X 1/212
n
+
K
2TT+1
2K
21
t=1
implying
3
T
K
|
T T
K
Vk.41/2 Va.-1// 1,]
12.41/2112
SE
+
(Inql)
2
+
K
21
2K
t=1
k=1
On the other hand, we consider
Xx
X 1/211
T
8²
Σ
3|12(x++1/2111
||A(x,) A(Xe+1/2)11
2/t.
21h
B2
T
min
3,
E
[IIA(X 1 (IA(X)) A(X(+1/2)11)
2n10
1
>
min
B,
E [IIA(X))13
2
2110
1=1
32
min
B,
40R
2mm
where the second step comes from the consequence of the co-coerceivity assumption. Plugging this back to template inequality, obtain
1
min
B,
82
E
E
X
112
Th Σ
Va.41/22 V Val-1/2
(Inq2)
4 +
R
21j0
K
R
2
2K2
t=l
28

---

Layer-wisc Quantization for Quantized Optimistic Dual Averaging
Now summing the above inequalties Inql and Inq2, we have
B
T
1
K
min
B,
E
Va,ell
+
R
I
4 4
2no
K
non
+
2
K
1=1
1=1
k=1
X 11
< E
T
V V1.41//2 Vk,1-1/2
#T+1
K
Next, from the bounding of S2 from Theorem 5.5, we have
VRs4I/2
V
SE
+1
yielding
32
K
T
K
1 13 +1
min
B,
E
V
E
V
S E
4 + 4
2770
K
2
+
2
71++1
On the other hand, we can consider the lower bound for the LHS of this inequality
1
B 82
1
K
T
K
min
E
E
V 11,44122122
4 + 4
21j0
K
2
+
2
k=1
t=1
k=1
82
T
K
T
K
2 + 40R
min
B,
+ >>
E
1IVe++1/212
II
2110
K
K
1=1
K
1²
2 + 20R
min
8: 2/j0
E
K2
V
k,0+1/2
Vaselle
K
882
T
1
Va,e Ve.t-1/all )
2 + 40
min
B,
E
k2 2 - Valel
2100
K2
k=2
K
82
K
2
min
B. 2mo
E
V Vn.e1122 V/,0-1/2113
2 + 20R
K2
K
182
min
B,
E
+
20
2njo
Hence we have
82
1
1
X 1I +1
1
min
3,
< E
[|| + 1)E
(1I*112 + 11 E
2 20
2710
7T+1
where the last inequality follows from Jensen's inequality. Therefore, obtain
2 2
2njo
max
3
(12)
Similar to the proof of Theorem 5.5 for the absolute noise case, we consider
K
x3)
S - + S Sa),
E
sup
(x)
K
where
D
T K
S = E
S2 = E
M 2K
[ - 1
2mT+11
(=1 1=
Un Ue(X (5((111/2),x X141/2 )
S3 E
sup X
K
29

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Similar to the proof of Theorem 5.5, we have
S S2L 4 EE
M1+1
Again, decompose S3 similarly to the proof of Theorem 5.5
x
>)
T
K
U2((x+1/2), X11111))))
S3 = E
sup
(x((2+1/2),
E
sup
X
For the first term of the above expression, we note that
K
)|
K X0
D
T
K
E
sup
Uk(X (1(x)+ x)
R
Uk,+1/2,
E
U 1
K
K
2K
R=1
D
T
D2
X X
E
OR Σ
||A((
TRR
2/K
2VK
2
For the second term of S3, use law of total expectation
|1
E
11(
Σ
(X(+112)))) X2+1/2) [x+11/2
0.
Therefore, from the bounds for S₁, S2. Sz. we have the complexity for no compression is
(Ax( - x) 00 D2
E Gapx (Xx+1/2) = E
Σ
sup
K
T
k=1
Now, we consider layer-wise compression. Firstly, recall that the average variance upper bound is
M 5
Tm.
T
Now with the bound from Lemma D.9, we can follow along the line of (Faghri et al., 2020. Theorem 4) and (Ramezani- Kebrya et al., 2023, Theorem 4) to obtain the final computation complexity with layer-wise compression
Gapp (X++1/2)] =0 ( + EQ + o D2
F. Analysis in Almost Sure Boundedness Model
F.1. Useful Lemmas
For the sake of convenience, we introduce the following new notations:
t Pt Σ IX, X 112
X
K2
yielding
(1 1/2-00
V + X + 14-2
We now establish some basic lemmas that will be reused through out this theoretical analysis.
For é S dr = pt 0.
30

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Lemma F.1. Let Assumption 2.4 holds. Then for T N, have
XT S + +
Proof. Using Assumption 2.4, note that
K
R
k
1/2
V4,41122 + Uk.+1122)
k=1
K
1
V2,4+1/2
+
1//2 1/2
K
k=1
K
k
VEa+1/2
11
+
2
U
2
K k=1
K
k=1
$ J 20
implying \r 2T + 2T Lemma F.2. (Hsieh al., 2022, Lemma 14) Let T E N,e > O, and q E [0, 1). For any sequence of non-negative real Or, we have
mumbers 01....,00 aT,
1-9
1
a2
E
Σ a=1 0g
9
g
Combining the above lemmas, we deduce the following useful bound
Lemma F.3. Suppose that Assumption 2.4 holds, let N, and [0, 1), then for T E N, oblain
k=l Vr.0+1/2/K12
1-r +2s(J oz)).
(1+ )=-
Proof. Note that
1
S
(1+ x1)
(1 )
EK V /| in Lemma F.I, we deduce
Combining the above inequality with bound of
K Σ
Vr.44/22K
$ (TT (1+ (1+ 22
) (1+
A,)"
A=1
Combining this inequality with Lemma F.2, derive
Dk=1 V
D K Ek=1
V
Σ V
(1 + )=
(1+)
(1+>1-a))
(1+ Xx)=
K V
1
k=1
2(J² + +z0
(1+)))"
(1+ >
(1+ A.)
1=1
2(J² + 02)
1-r 2s +02).
1-r
(1+ Ar)
31

---

Layer-wisc Quantization for Quantized Optimistic Dual Averaging We also establish the following lemma bound the inverse of 7]t Lemma F.4. (Hsieh et al., 2022, Lemma 17) For T N, and a, R4,, it occurs that
a
T |
X+t1ll
S Sav1 1 + Ar +
a²
1/+1
1/t
4b
1=1
Proof. Note that
a
av 1+ \T -T-1 + +aUUT-1
MT+1
And also have
T
Xt
X
T
b
| - X1+1112 b1
1/
t=1
Define function h R - R, (()) = the proof.
oz
1x22 We notice 0//TT11 bpt S maxsER f(x) = =a/4b. This concludes
F.2 Important Inequalities
We start with constructing an energy inequality for (ODA) (without quantization).
Proposition F.5. [Energy Inequality] Let (Xt)LeN and (Xx+1/2)eeN be generated by (ODA) with non-increasing learning rates. For any p E X and t 2, it holds
[|
211
||
p112
||x,
11+1
1
(1xx
- -|111 --112-11
(2+111?)
M++1
Nl
11+11
T)c
Vi.441/2, Σ V/,--112 )
2
2///
V1,44122,
X1+1/2 DD
Vr,44122 X, Xot1
K
K2
Proof. Using the fact that Etm V K -X,- X1)/ (X++1 X1) have
K
V
1/,4+1/2
X1 -X
X0+1 - X1
X1+1-1 -
Xe+1 -D)
K
11.
M1+1
1
- (
17t11 170 ) (X1 - -X+11. p)
(X, -
n1
1
(IIX: - 112--1xx42 - -pl? -11Xe- - -x++113))
2mp.
1 1) (IIx -1p1- 212 -111111111 p|12- 2- -11x -x44113).
21/++1
2th
Multiplying both sides by 2 and rearranging, we obtain
|X 2
[r, - 21
[[, - Xet1l12
(1- -.) (1X, -112 - 111 Xx+1 12)
7/+1
4/
T/
1/+1
2
Vr,441/2,, Xe+1 -p)
K
k=1
32

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Lastly, note that
K
Vk,+1/2, X141
/P/
X141//2 -P)
-/+
V 1 X1 -X+11/2
V 1 X, -XXe41
K
K
K
V X141/2
+
Tk K
1/.41/2
Σ Vhu-1/2
Vr,4+122, X, -Xet1
yielding the desired expression.
Corollary F6 (Energy inequality). Let (Xt)eeN and (X++1/2)tEN be generated by (ODA) with non-increasing learning rates. For any p E X and t E N, it holds that
Xt+1 pl1
[x, pll
1
1)
||x,
-pl22
2
Σ
Ve.+1/2, X141/2 -/
7-+1
1t
71+1
7)
K
K
K
K
2%
11/2-1/2
+
VR. Vk,
n²
K2
1==1
1=1
K
2
1|x, - X1+2 11?
+ min
V
.0
K²
217/
Proof. By Young's inequality,
K
2
V 1/22
Xz -Xx11
K
2
min
1Jx
Ve+1 1/2
|X Xet1l1
27e
1/2
X
X 112
K2
17t
K22
21
A=mm
K
V/+1/2
Xr
Xe+1 1|
+ min
0.
T7e
1+12
||X, - X1+1 11
K
n
K
217.
1=1
1 m/
Using this inequality and dropping the non-positive term we can obtain the required inequality.
||
X 1| from the result of Proposition F.5,
71+1
Next, can evaluate the noise and further expand the energy inequality (Corollary F.6) in the following lemma Lemma F.7 For &. 2 2, it holds that
K
K
)
K
K
K 2
Vr.41/22
1/2
Σ
V
R2
1/241/2
+
K2
1/2
km1
A=
K
2
+
7/'
VE,41/2
Σ
Vh 1/2
K
k=1
k=1
+L(?? + (7u + n
33

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Proof. We V as shorthand for (x(),) and V&,e- Vise + Uk where UK is the zero mean noise. By the law of total expectation
27
2
Ve,e-117 1/2 )
1
VR, 1/22
1/22-122 1/2
E
E
Σ V
12.+1/2
Σ
V
K²
K²
k=1
h=1
K
K
2
E
11,
Vi,t-1/2
K2
K
K
22
Uk,C-1/3 /
+
Vk 1//2
K2
k=1
First, note that
2%
Vk 1//11/2
Vk.c-1/2
-Y6 K2
Σ
V
1/.+1/2
% K2
Σ
R. 1/2
K²
7
Vi,e+1/2
1/22-112
K2
implying
K
K
K
K
E
K2
27
Σ
V2.+1/2
1/2:
Σ
Vi-- 1/2 )
=B
K2
VA
1/2
K2
7/t
Vn
M 1/2
1=11
km
k=
R=1
K
K
2
7/
($)
+
Vi,+1/22
V/,2-122
K2
k=1
K
V1,++1/2
Uk
K2
k=1
From the update rules of (ODA), we have
K
K
X1+1/2- X,
V
X1 = X1
Vk.0+1/2
K
K
k=1
k=1
Combining these two equations, we get
t-1 K
K
X =
1/t
1/,0+1/2
7t
VI.t-1/2 1/2
K
K
k=1
k=1
2-2
11t
7/ + 11t K
-
k,,+1/2
V
1-2 K
K
Xi
1/t
Σ
1/2
7t + 11t
(Vi,-1122 + URD-1/2)-
K
K
Now, let Σk= Un.e/ K = U, as the sum of all the noises from nodes at time t. It clear that U, also has zero mean. Let
X241/2 = X X2+1/2 + (1h + U, to be surrogate for X when removing the noise of time - 1. We then obtain
8411/2 = X1
11t K
V
7t + T1t K
V V/2-1/2-
1/2
34

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Applying the notations U/-1/2 E Uk.t-1/2/H and Ag (X(+1/2)
V2,++1/2 into (i), we have
E
K2
2
Vn 1//11/2
Σ
11/2-112 )
R
K2
7t
1/2
R²
7t
k
1/2
k=1
k=1
K
+
VA,++122
Σ
Vi,0-1/2 k=1
K2
2
A& (x(112/2) (10,1/2),U--1111 12-1/2
K
We now bound the last term of the RHS of the above expression. First, notice that
K
(x(x)112))U Un-112 )
E
Ax ((U) =0
With that and the L-Lipschitz of Ag, we deduce
K
)) =-B
K
A - Ax(Xe+1/2) U1-1/2)
E
Aa (x(x111/2), U,-1/2)
Ax(X(1122) U2-1/2) }
E
A& (x - Ax -(( (x(++1/))) U,_1/2)) }
E
< E
KL -x+1/2al|
1X:t1/2-X1t1/al
7'. 1-1/211 11
< E
KL
27.
2
(1 mp) 1
1 U||1111/221 )
E
KL
2%
yielding
K
Ax(X(41/2); Ur-1//)) )
-27
< E [L ((1x mh) 2 +
In brief, we get
V1.1-1/2 )
E
2%
Σ
V
1
Σ
E
Vt
Vx 1/211/2
Yt
Σ k=1
V 1/2
R2
K
2
K2
+
Vk.++1/2
Vk,t-1/2 1/2
+ L(7 + (76 + +n) m
K2
A=
as desired.
Now we can establish the quasi-descent inequality for (ODA) as follows
35

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Theorem E.8 (Quasi-descent Inequality). For & 2 2, it holds that
X 1+ - 2|1
[X, pll
1
2
K
E
|X
-
71+1
1/
71+11
K
K
K
K
K
2
Yt
7t
Σ
1 1/2
+
Yt K2
V
Σ
Vi.e-1/2
K²
K²
k=1
k=
k=1
K
2
||x, - X1+111
+
min
V1,+1/2
K
217
k=1
K
+
T
V 1//2
+ ((re + mm)² + 1 1/21=
K
Proof. This result immediately follows from plugging Lemma F.7 into Corollary F.6.
With this quasi-descent inequality, we pick the learning rates as follows
4-1
t-2 2
K Vv.s+ 1/2
K
1/2
Tt =
1
, 7) =
+ ||,, X
K
K
Similar to AdaGrad (Duchi et al., 2011), we include the the sum the squared norm of the feedback in the denominators, helping control the various positive terms appearing in the quasi-descent inequality, like K
Σ Ve,411/2 and
L ((7, n + 7/7) 1|22-1/21 Nonetheless, this sum is taken to the same exponent in the definition of the two learning rates. This scale separation ensures that the contribution of the term which is crucial for deriving constant regret under multiplicative noise. As technical detail, the term Σ I| Xx+1 1 included the definition of T/e for controlling the difference
7tt
E
2
V
remains negative,
K2
Ft
Σ
K
Vr,11122
K Σ
1
||,,
N
21/1.
Some technical insight is that " and ne should least be in the order of Ω (1/t3-9) and Ω (1/th).
We can restructure the quasi-descent inequality Theorem F.8 as follows.
Lemma F9 (Alt Template Inequality). Let (Xt)xe and (X141/2)eN be generated by (ODA) with non-increasing learning rates Th and "/t from the Alt schedule, such that nu I no for all t E N. For any p X and T E N, it holds
V X - b)
X1
2l1
T
T
K
3I +
T
K
< E
21TT+1
2k
11/2
K2
V&.t
1/2
A=
1=1
A
2=
R
3L
5L
rel|X, X
+
7e
2
U1-1/2112
U
2
2
2
Proof. From Theorem F.8. by dropping non-posinn posiiosie terms and using the fact that
Xx, X 112
min
T/
V 1/2
S 0,
R
2n
36

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
obtain
X p|l21
X, pll?
)
E
||X1
pll
11++1
1/t
7/++1
7t
K
2
14,44122:40 Xe+1/2
p)+ +
7t K²
Σ
Vi,41122
Vi 1/2
K
k=1
T/ K
V 1//+1/2
+ L ((7 + n1)2 2 + 72) ||U/-1/211
Rearranging the terms, and multiplying both sides by 1/2, we obtain
K
Xe41/2-1 -P) |
E
V,.+1/2,
K
k=1
<
[ - pll
Xe+1 - -pl1? +
1
|X1 - -pll?
M
K
Vz, 1/2
21Te.
21/+1
21h+1
21/:
2K
K
K Σ
L ((7 +
1113 + 7??)
Yt
Σ
V/,+1/22
V/22-122 1/2
+
U 1/21
2K
2
km
Note that this incquality holds for t 2 2 as suggested by Theorem F.8. Ift = L, then know
K
||x2- - 152-p113= || pll
20/2
Σ
V Vk3/2, X1 - p/
Σ V k,3/2
K
Setting X3/2 X1 = 0 and 711 = 1/2, we can obtain
K
|| 2|
[ pll
m
Σk=1
Ve,3/2
E
Vk.3/2, X1 -
(x+)
K
20p
21p2
2K²
Now, we sum the inequality (+) over from 2 to T and then add (**), yielding
E
V 1,t41/2:X+11/
-P)
K
1=1
|| 2|1
K
E
71t
V
1//211/2
Yt
Σ
V
Vi,41122
Vv. V
2MT++1
2K²
2K
t=1
t=2
k=1
L. ((T + n2 +2))
U,-1/211
2
|| 2l1
K
E
Th
V
Va.441/2
Yt
V VA.41/2
V
U
101110
1/ 2
21T++1
2K2
2
t=2
($t)
where the last step follows
S Tt- We also can bound the difference term as follows
k
Σ V.
1/241/2
Σ
V
1/22-/2
3
V
1/241/2
+3
V
k.t
V
-
k=1
K
+3
Σ
Vh,t-1
Vk 1/2
k=1
k=1
37

---

Layer-wisc Quantization for Quantized Optimistic Dual Averaging
Note that by the L- L--ipschitz continuity and the update rule of (ODA), we have
K
K
K
K
3
1//+1/2
Va,
3
(Ax(X++1/2) -xxh)/
33
L|| 1-1222 X.1
1=1
k=1
K
Σ
V 1/2
A=1
After bounding the second and third terms in a similar manner, we obtain
K
K
Σ Vi,+1/22
Vv.
33L322
Σ
1/2
k
+ 3K
x,-1 +3
Σ 3/23
(D.1.1)
Using the initialization that 1 [K], we have
K VV..c11 1/22
31.27 K2
2
T
31 7t
Σ
7
Σ V
1/212
Σ Σ
V
1/2 1/2
Σ
1x,
x,-1
(D.1.2)
2K
2
k=1
t=2
Combining this with the inequality (#t), we finally obtain
( - D)
-
[X] pl1
T Σ
K
3L
T
K
E
E
21T++1
2
VR. 1,/41/2
+
K2
ft
V 1/2
t=1
k=1
t=2
3L
5L
Vo 7el|x X,-11 11
7t. U 1
2
2
1=2
F.3. Bound on Sum of Squared Norms
We start to bound the sum of squared norms by first revamping the quasi-descent inequality Theorem F,8 in different way. Lemma F.10. Lei (Xt)ten and (X++1/2)teN be generated by (ODA) with non-increasing learning rates T and its from Alt schedule, such that no S Yt for all N. For T E N and x² E X*, we have
K
K
E
K2
Σ
Vr,+1122
1/2
V K
Σ
Vi 1
1/2
2
A=1
|
2+1
T
K
T
3
K
K
E
7T
K2
V
VRRt-1/2 1/2
+
K
Vi
V
k1++1
2=2
tm1
k=1
k=1
T
X1+1112
T + Σ
21k
K Σ
T +5L Σ
V4.441/2
U/1//11
21)r
K2
2
1=2
Proof. is straightforwards that
min
n
V Vk.+11/2
X
X 1|2
0
K
V V
X - xx+x 112
K
21/z
K
2n
Next, similar to (D.1.1), we have
K Σ
Σ Vk.41/22
Σ
Vx V1k-11222
< <3L222
V
kt 1/2
+3
k.t
V kit-l
+ 3 7
Σ
V V.1-3/2
k=1
k=1
k=1
k=1
38

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
And since 7/1 S 7t, note that
((% + +
With these inequalities, we can rewrite quasi-descent inequality Theorem F.8 as
Xe+1
x²1
E
7/t+1
E
111
x011
+
111+1
11
1) )
|x1 -2
M K2
Σ
K
Vi,t-122 1/2
K
7/t
K
Vk.
k
3/
18
3
K
Vk. k 1/2
2
3L 2 70
K
VR, 3//2
+
37t K
Σ
K
Vh,
K
k
K2
K2
A=1
R=1
2M
X1 Xe+1112
+
Vk, 12,4+1/2
+ 5. /
K
217
Summing from t= to T of the above, we obtain the following after some rearrangements
T
K
E
K2
V2,0+1/2
K2
VR, k
1/2-1/2
2
||x
x=
11?
+
1
1
||x1
=x11²+
Σ
T
6I223 3
Σ
K
Vi,t 1/2
2
-
-
T
1x, - X
(D.2.1)
7/2
MT++1
772
K2
21
1=2
k=1
1
T
K
K
T
K
T
3
217
VE,t
Vk,t-
+
+ 5L.
2
11-1/211
K
K2
2
1=1
1=2
which we use the fact that V/.1/2 = 4. k E [K] and get the bound similar to (D.1.2). Next, note that
K
T
K
K
3
Vg.e+1
V
K?
K2
K
k
t=2
1=1
1=1
1=1
k=1
1=1
A=
k=1
(D.2.2)
where the last step stems from 7t 2 741 Ift 1, then we know
K
||2-- - x²1 111 11x
x²1
21/2 K
Vk.3/2 X1
x²
)
+
1/2
V 3/222
||
2²12 +
V
V.3/22
K2
K2
This implies
X 2*1
|X 1+1
K
E
SE
172
V Vk.a/2
1/2
K2
|X 112
21/2
X X2
< E
V k.3/2
(D.2.3)
1/2
K
21/1
39

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Now plugging (D.2.2) into (D.2.1), and adding (D.2.3), we eventually obtain
7t
Vt
K
1//+1/22
K
1/2
E
|X|
x= 1
+
6L
Σ Vk,t 1/2
2
+
T Σ
37
K
VeLt
VR. 1+1
1T+1
K²
K
t=2
1=1
k=1
T
Xe
X
2M7
K
T
+
Vr,141/2
+ 5L
2
1
2ttt
K
2
1=2
Next, we establish the following lemma to control the sum of some differences
Lemma F.11. Let (Xi)ten and (X++1/2)teN be generated by (ODA) with non-increasing learning rates Th and N from Alt schedule, such that qu S for all & N. For all T E N, with almost sure boundedness assumptions from either Assumption 2.4 or 2.5 it holds that
3
Xx
Xe+1 11
Vi,++1
4327. 24J
K2
4n
1
Proof. Define == max E (O....,T) 11 2
So as to ensure i is always well-defined, we can set 7/u 2 12
12
By definition of μe and fE. we can deduce that 2 S 114L². Now since S 1, we have
T
K
K
3%
Va,441
K2
k.t
1=1
k=1
K
3
VE.
Vi,e+1
K2
1=1
k=1
k=1
K
K
K
Σ
Σ
3
Vh.t
V
VEL+i
K2
K2
k=1
k=1
(E(1-1.0)
k=1
k=1
K
2
K
K
Ves+1 1)
Σ
L| - XeH1ll
+
Σ
6
Σ
+
Σ
K2
K2
k=1
(E(1-1,8)
Σ
3T,2
11+111+
Σ
12.
(T/(LL)))))
(E(F-1.8)
Σ
31,1|X, 2 24.2 24.
2-2
Σ 3L fl, - X2+1112
Σ
3L21|X, 11+1112
+ 24.2
1=1+1
= 3L2 -3L2Mi -
Σ
3 X +
t=t+1
T
< 4 +
I. - 2 2 24,2.
t=
40

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
As 11
for 2 i
note that
12L.
X
X
1
|
X
2
T
Σ
Σ
3
3L
X++1l1.
477t
477t
t=1+1
t=f+1
yielding
3% K
2
T
1X,
X
11?
Σ
Vest
Vi
k,1+1
I
4321
+ 24J
47p
A simple rearrangment of the term
Di |r Xx+1l13/(4n))) will give the desired expression.
Finally, we can establish the bound on sum of squared norms.
Lemma F.12 (Bound Sum of Square Norms). Let (Xt)een and (Xx+1/2) be generated by (ODA) with non-increasing learning rates nu and "t from Alt schedule, such that np I "/ for all t N. Denote D suppex || pl12. For all T E N, we have
T
Xx
12+1/12
E
1//+1/2
S aE
V
+ +b,
K
8m)
k=1
where and b constants with the following values
a = -121²+ + 10L + 4 D2, b= (12L² + 10L + 8)(2 + + 4322 + 24J + D2 + 2D
Proof. From Lemma F.10 and Lemma F.11, we have
T
K
T
K
X
X,+1
E
K"
V1
1//2
+
K
V
kit
1/2
+
81p
2-
A=1
2=
k=
1=1
<
E
T
2
K
VE 1/2
+
T
3%
K
Vhe
Σ
K
V
V4++1
T
X₂
Xe+1112
K2
K2
4nl
2=
1=1
1=1
|X
x+11
T
|
X1+1112
1|
T Σ
21/
Σ VR.++122
K
+5L
T
72 U
1/2 1|2
(D.4.1)
7T+1
817t
K
Am1
2m
1=1
2
x+11
T
6L 2
K Σ
<
V
V 1/2
+ 4321* 24.2
1M+1
K2
1=2
||
11
21
T
Σ
V 1x,+1/2
+ 5L
7t U111/112
817
R

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
Now, since Y 1, |
V/, Ek=1
k
12
/K2, and 22-1 S 1/ V
1 A+t1, we have
T
E
Σ
Vi, 1/2-1/2
+ 5L
2 U
K
1=2
K Σ 1=
K
E
1.0-1/2 1/2
1/22 1/2
K2
K²
R=1
SLT2 R²
K
27
T-1
K
27
E
K2
1/2 1=
E
(6I. - -5L) 7r
Vn. V K
t=1
E
K
V
27
S (6L + 5L)E
S (6L2 + +LL) 21E
v AT- + +2( + +0²))
V1+1~11
In similar manner, we can bound
T
K
Σ
2Tk
Σ
k.1+1/2
< <E
|T- + + +
K2
2
With these two inequality, rewrite (D.4.1) as
2
X2 X 1
E
K2
V
1/2
K2
k 1/2
81)
t=2
1=1
(6I2
(2E
2[ +²)) 4321 + 24.
4E
/
+ +
| 101
T
| X 2
E
1/+11
817t
(12L2 + 100 + 4)
AT-1 + (12L2 + 10L + 8)(2 +02)+ 432L 24.2
[ - 11
T
| - X ?
+ E
7T+1
81/t
Note that by the initialization X3/2
X1 and 72
71, we can further simplify the LHS of the above inequality follows.
T
K
T
K
T
Ix X 112
E
K2
V
VE
K2
Vh
1/2
8m7
1=2
T
K
2
||
X
2
E
Vr.441/2
+
K2
81Jt
Now, we just have to deal with the last term of the sum. With Lemma F.4, we have
X
x 112
X
11+1l12
E
EE
||X1
x 2011 111111+ + =11111
1
8t/
DD
VI+ 2 +
DdB
+ D2 2D VDr-1
yielding the desired result.
42

---

Layer-wisc Quantization for Quantized Optimistic Dual Averaging
We now establish an useful bound for Σt= E
E
Lemma F.1.. With the Alt learning rate updating schedule and for T E N, we have
27
Σ
V 1//+1/2/ K
O(TI-9).
Proof. For t [T]] note that
$ (1 + 2 max 2)2 + + S (1 + 2J + 02)))//2-0'
(1+ (2-2)
where the second steps follows from Lemma F.1. Now plugging this bound to Lemma F. 12, we obtain
Σ E
E / /
I aE Ar
+ bb,
(1+ + 02))
where a and b are constants defined similarly to Lemma F.12. By using Lemma F.1 again get v\r is of order O(VT), obtain
1 K
$ (OE [vr] + +b) (1 (1+ 2T + 022)2//2-4
= (VVV) (1+ (1+ 2T(J² + 102)
which equates to O (T2-9) as desired.
E4. GAP Analysis under Absolute Noise
Lemma F.14 (General Bound for GAP). Let X C. Rd denote a compact neighborhood of a solution for (VI). Let D² == supppe ||X, - ?l? Suppose that the oracle and the problem (VI) satisfy Assumptions 2.1, 2.2 and 2.3. Let (X,)ee and (X++1/2)EN be generated by (ODA) with non-inon increasing learning rates tu and "i from Alt schedule, such that n S n for all t N. holds
E sup (A(p). -p) PEE
-D)
6L +5L+ D2 - 1 (
V
Ar
+
D2 VTT-I
+ +6L2 + 5L) +
2
2
D2
3L T-1
+ 2(J + 02) +
Σ
|X++1 x,13
2
1=1
Proof. First note that
Vk,44122 X/41/22 1
1 K
sup EE
Σ
sup E PEt
VEL+1/2
X -P)
K
K
PEA
1=1
1
K
Ak(p), Σ X141/2 - 1)
2 sup E pEt
K
K
sup E pE
(A) 8 X.11/2 -p)
K k=1
(A(p), 8 - 1
TE
sup
pEx
43

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
where the second inequality stems from the monotonicity of operators Aş. for h [K]. From the template inequality (Lemma F.9) and the two facts that 7/ 2 1 and Ek= 12,t-1/2/K2 2 1/-1 we deduce
K
sup pEX
E
1
p)
K
k=1
|
pll
31,²
T
K
31.2 T
< E
211++1
K2
7t
ViLt- k 1/2
+
2
Y
IX2 - X1-1112
1=2
R=1
t=2
T
K
2
5L
T
K
27
+
2K
k.4+1/2
+
2K
11
2
1/2
2=2
k=1
D2
1
AT- + PT-1
6T. +
5L
T-1
K
11,2+1/2
2
2K
1++1
3L T-1
T
K
Σ
|X - X,I12+
+
Σ
TJ
VE.++1/2
2
2K
t=1
Now we can analyze three terms of this sum in the following three inequalities.
D2 + Ar- + PT-1
D²(1 + Ar- +
11-11
2
2
From Lemma F.3 and the fact that r241
V 1 11
A we next have
6L2+50 5L
T-1
3L2+5L
T
k== VI.441/2
K
Σ
Σ
1/2+1/2
2K2
1+11
2K2
VI+ + A
k=1
6I.2 + 5L T-1
Σ K Ve.t1//2/K1
-=
2
V1+ 1
- (6I.2 + 5T.
(V + J2 + +22)
where the last step stems from Lemma F.3 with s = 1, 1/2. With a similar observation that n7e S 1/ /1 11 we can similarly apply Lemma F.3 and obtain
2
ΣK V V 2
K
Ek kkl 1/2
T
Σ
The 2K
Σ
V4.441/2
1
Σ
/V +2(J2+00)
2K
VI+ Ae
2 Ar-
Combining the above three inequalities, we obtain
K
V1. Xe41/2 1)
s E (12at² + 6L. + 5L+ +
D2
vtr + D2 V Voi++V>+++
sup E nEX
K
2
2
D2
VHT-1 +2( + +1212b
+ +(6L² +
2
implying
sup (A(p), Xet1/2 - p)} s _ (0L 6LL + 5L + LeeX
2 2² V VV-++VAr+++ Vx++
D2 VPT-I
2
D2
31.2 T-1
+(112 + 5T) +07) +
2( + 02) +
| Xel13
2
44

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
We will now show the convergence of Algorithm 1 with Alt learning rates under absolute noise
Theorem F.15 (Convergence under Absolute Noise with Alt learning rates). Let X' C IR denote compact neighborhood of a solution for (VI). Let D² == suppex ||X; pll. Let the average square root expected code-length bound EQ 3m=Li j== Tmi /m..m.//TT Suppose that the oracle and the problem (VI) satisfy Assumptions 2.1, 2.2, 2.3, and 2.4. Let (Ke)ten and (Xx+1/2)EEN be generated by (ODA) with non increasing learning rates tp and itt from Alt schedule, such that Tt S Yt for all E N. It holds that
Jm
[[AD+IIA(X,]Il +0)=++))D)
+
[aapx (X++1/2)] =0
VT
Proof. First we consider no compression, ie. EQ 0. Note that from Lemma F.I, we have AT and Ar-1 are O(T), so VTT and v -1 1 are (VVT). Next by note that
D2 VPT-
3L T-1
D2
3L
T
D2
3L
[ - X
11-1- -x|l
X - X,l12
2
2
2
81/t
1=1
t=1
12
31?
[vr-i +b) = o D*VTT)
where the second last step holds due to Lemma F.12 with the constants a and b defined in the same above lemma, and the last step holds from Lemma F.1. Combining these bounds with Lemma F.14, we obtain
K
(Va.41/2 X411/2 - p) o (DVT)..
sup E PE
K
k=1
Then, without compression, we have
E
1 K
Σ
K
sup PEX
(All)) 1) < sup
1
E
K (14-1/2,X44117
-p) b)
-0 D
T PEX
K
k=1
Now, we consider applying layer-wise compression to this bound. Firstly, recall that the average square root expected code-length bound is denoted as
M J T mm. VEQ.m
T
17 1=1
With Lemma D.8, we can follow the ideas established by (Faghri et al., 2020, Theorem 4) and (Ramezani-Kebry) et al., 2023, Theorem 3) and obtain the final computation complexity with layer-wise compression
E Gappx (X++1/2) =0 (LL ((xx) + a oeē + +)))
VT
G. GAP Analysis under Relative Noise
Next for the relative noise case, we first consider this known general bounds for any N non-negative real-valued random variables.
Lemma G.1. (Hsieh et al., 2022, Lemma 21) Let p. r, E R, such that p > r, s E R_,,, and (al "a'.....'"" aN) be a collection of any N non non-tegative real-valued random variables. !f. we have
N
N
E((a))]
< Σ B(()))
then we obtain
Σ El < Nsw Σ
Bl < -
45

---

Layer-wise Quantization for Quantized Optimistic Dual Averaging
To obtain a better complexity, now provide set of improved bounds for the key quantities in the analysis.
Lemma G.2. Assume that the assumption Assumption 2.5 is satisfied, and Alt learning rate update schedule is used. Then, for any T E N, we obtain
E [1 1/ V1+ Ar| ((1 + b) 1)
- (11+ + b) +))
E
E [ur] I 8a((1 + b) + 1) 2 + 8b,
where a, b are defined constants Lemma F.12
Proof. To begin with, we have from Assumption 2.5 that
K
K
K
E
K2
Σ
1/2
=
E
K
Σ
V
+
Σ
1R
k=l
K
IF
V
V2,
+
UR
1k/+11/2
K
k=1
E
VK,++1/2
U1,++1/2| 1
K
E
V2,1+1/2
OR K
Au (xe(21222)
K
IE
Vk,4+1/2
+on ||((1+1/2))
K
2
1
< IF
VR,1+1/2
+oR
A (x(+1/12)
K
K
A=1
k=
K
= (1 + RE
VR
VR 1/2
K
1m
where the last few steps utilize the fact that A Aj A for all i [K]. Since the learning rates T/t are non-increasing. can write
T
K
T
K
T
K
74
Yt
7r
E
A.4+1/2
Vx.e+1/2
K2
K2
K2
tm1
2 /K2
T
E Vr.c+1/2
\r + 1 -
E
1 0R
(1+ 1/2-
1 OR
(1 2/224
E
(1 + Ar.)) 1/2+0]
E
1 oR
1 1 +
(1+ 12)2221/220
E (1+ 1/220
1 oR
1 oR.
implying that
K
E (1 + \T) 1/2+0
51 (R)
E
7t
V Vx,+1/22
+1.
K2
A=1
46

---

Layer-wisc Quantization for Quantized Optimistic Dual Averaging
By Lemma F.12, deduce
E (1+ aa(1 OR)B VAr-i b(1 (1++OR) +1+ +15 (R)(aaaa+)) 1) [ 1+ Ar-
where a, are constants defined in Lemma F.12. Now we utilize Lemma G.I for N 1, p 1/2 + 1/2. (1 + σR)(a + b) and a' = 1 Ap. This implies
E (1 [1+AAr) // - ((1 an) + + +1)
V A I ((1+on)(a + 1)
Now combining the second inequality above and Lemma F.12, we finally get
1x, X
jur]
Σ Xx X
8a((1 + +n) b) 1) 8b.
8m
where a, b are defined constants in Lemma F.12.
Theorem 6.2 (Algorithm 1 under Relative Noise without co-coercivity assumption). Suppose the iterates X₃ of Algorithmm I are updated with learning rate schedule in (Alt) for all t 1/2, 1...., Let X' C TR. be a compact neighborhood of solution for (VI), EQ as in Section 5.2 and D == suppex || - plž- Under Assumptions 2.1, 2.2, 2.3, 2.5, and 6.1, for Algorithm I with learning rates (Alt):
Gapx (X++1/2)] =0 (LoREe + Eq + D1)
T
Proof. By plugging Lemma G.2 into Lemma F.14, we have the complexity with no compression is O (D*/T)) With the bound from Lemma D.9, we can follow the ideas established by (Faghri et al., 2020, Theorem 4) and (Ramezani-Kebr) et al., 2023, Theorem 4) and obtain the final computation complexity with layer-wise compression
(oREO + EQ + DR)
Gaapx (X++1/2) =
T
where Eq average variance upper bound as
M 5
T @m.
EQ
T
m
j=1
47


Reviews:
[{"review_id": "u3TJSZOpYp", "reviewer": "Reviewer_goUV", "summary": "Based on theoretical analysis, this paper presents a layer-wise quantization framework that adapts to the unique properties of different neural network layers. This framework leads to the development of the Quantized Optimistic Dual Averaging (QODA) algorithm, which uses adaptive learning rates to achieve competitive convergence in variational inequalities and significantly speeds up training of Wasserstein GANs on GPUs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We would like to thank the reviewer for reviewing and giving us feedbacks. We will address your comments in a QnA temmplate. \n\nQ1: The motivation in terms of layer-wise quantization (which is directly related to Mishchenko et al., 2024 or [4]) in training could be further clarified, as layer-wise quantization is not a well-known concept in this field.\n\nA1: Based on the reviewer's feedback, we propose adding the following brief summary at the beginning of Section 3: As mentioned in the introduction, previous literature has shown that different types of layers in deep neural networks learn distinct hierarchical features—from low-level patterns to high-level semantic representations [1, 2]. These layers also vary in the number of parameters they contain and in their impact on final accuracy [3]. Thus, the key motivation for our layer-wise quantization scheme is to account for this heterogeneity and provide a more effective approach to quantizing neural network training. \n\nWe also want to stress that our method is not \"directly related\" to the block (p-)quantization approaches described in [4, 5]. In lines 58-59 on the right-hand side of the page, we emphasize that block (p-)quantization [4, 5] is **fundamentally different** from the layer-wise quantization presented in our paper, as detailed in Appendix A.2. These are three fundamental distinctions between block quantization and our layer-wise quantization:\n\n- Each of our layer or block in this context has different adaptive sequences of levels (Section 3). This is why our method is named **layer-wise**. The works [4, 5] on the other hand applies the same p-quantization scheme $\\text{Quant}_p$ to blocks with different sizes, implying that the nature and analysis of two methods are very different. \n\n- The way the quantization is calculated for each block or layer are different. [4] study and provide guarantees for the following type of p-quantization (for all blocks): $\\widetilde{\\Delta}=\\|\\Delta\\|_p \\operatorname{sign}(\\Delta) \\circ \\xi,$ where the $\\xi$ are stacks of random Bernoulli variables. In our work, the sequence of levels for each layer is adaptively chosen according to the statistical heterogeneity over the course of training (refer to equation (MQV) in the main paper).\n\n- The guarantee in [8, Theorem 3.3] only cover p-quantization rather block p-quantization. In our Theorem 5.1, we provide the quantization variance bound for any arbitrary sequence of levels for each layer in contrast to that for only levels based on p-quantization [4].\n\n\nQ2: For GANs, do the authors observe any instabilities during training? Or did the authors attempt to train GANs on more challenging datasets besides CIFAR to observe the effectiveness of the method?\n\nA2: We did not observe any additional training instabilities when applying our compression method to GANs. As demonstrated in the FID plots (Figure 1 of the paper), the training curves for QODA closely follow — and at times are even smoother than — the no compression baseline, indicating that our method does not introduce extra instability. We believe the results and speedup observed on CIFAR-10 and CIFAR-100 provide strong evidence that QODA is as stable as the baseline. \n\nReferences: \n\n[1] Zeiler et al., Visualizing and understanding convolutional networks, ECCV 2014. \n\n[2] He et al., Deep residual learning for image recognition, CVPR 2016.\n\n[3] Dutta et al., On the discrepancy between the theoretical analysis and practical implementations of compressed communication for distributed deep learning, AAAI 2020.\n\n[4] Mishchenko et al., Distributed learning with compressed gradient differences. Optimization Methods and Software 2024.\n\n[5] Wang et al., Theoretically better and numerically faster distributed optimization with smoothness-aware quantization techniques, NeuRIPS 2022.", "claims_and_evidence": "- The motivation in terms of layer-wise quantization (which is directly related to Mishchenko et al., 2024) in training could be further clarified, as layer-wise quantization is not a well-known concept in this field.", "methods_and_evaluation_criteria": "This paper provides a theoretical analysis for previous empirical work very well, it provides a tight guarantees for layer-wise quantization.", "theoretical_claims": "I have checked the theoretical analysis. Although promising, I personally believe that the use of symbols can be further reduced to improve readability as the underlying math is straightforward.", "experimental_designs_or_analyses": "The experimental results of this paper are relatively limited as most of the main body is used for theoretical analysis.", "relation_to_broader_scientific_literature": "This work extends the previous works, e.g., adaptive layer-wise quantization (Markov et al.) and QGen-X (Ramezani-Kebrya et al.).", "essential_references_not_discussed": "As far as I know, this submission discusses the related works properly.", "other_strengths_and_weaknesses": "More empirical experiments could further enhance this paper, however, since the contributions of this paper lie mainly in theoretical analysis, I would not consider this as a major weakness.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "For GANs, do the authors observe any instabilities during training? Or did the authors attempt to train GANs on more challenging datasets besides CIFAR to observe the effectiveness of the method?", "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": "E5w6YFJDQM", "reviewer": "Reviewer_j331", "summary": "This paper introduces a layer-wise quantization framework that adapts to heterogeneities over the course of training (DNNs). Instead of applying a uniform quantization strategy across all layers, the proposed approach optimizes quantization sequences per layer with tight variance and code length. Building on this framework, the authors propose Quantized Optimistic Dual Averaging (QODA), a distributed solver for variational inequalities (VIs) that integrates optimism to reduce communication overhead and improve convergence rates. Empirical results show that QODA accelerates Wasserstein GAN training by up to 150% while maintaining competitive performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you very much for your time and your comments on our work. We will address comments in the following QnA format:\n\nQ1: The paper does not analyze accuracy trade-offs-does layer-wise quantization affect generalization or model stability?\n\nA1: We hope to clarify that in Figure 1, we show that our method can recover the accuracy of the full-precision baseline model. This suggests that layerwise quantization does not have an adverse impact on accuracy, while significantly reduces the time per optimization step (Table 1 and 2). Moreover, for the Transformer-XL task, Table 3 shows that layer-wise compression provides a better accuracy-compression trade-off than global compression, obtaining better perplexity score while improving training speed. \n\nQ2: A comparison with other quantization techniques would highlight the benefit of this approach. How does QODA compare to quantization-aware training (QAT) and post-training quantization (PTQ)?\n\nA2: In brief, the methods are complementary. Quantization-Aware Training (QAT) methods seek to produce models with quantized _weights and activations_ during training, and as such, compress these elements during the training process. PTQ methods aim to do so in a single compression step, e.g. by using layer-wise solvers to find a good quantized weight assignment [1,2]. By contrast, we investigate _gradient_ compression, with the goal of reducing the amount of communication employed during the training process itself. As such, the objectives are orthogonal, and QAT methods could be used in conjunction with QODA. We will add the above discussion with references [1,2] to related work section for future manuscripts. \n\nQ3: I believe the Introduction could be improved a bit to provide the context. Paper also seems to be a bit overusing the notations. Writing could be improved a bit.\n\nA3: Understanding the complexity of layer-wise quantization, we have tried to simplify the notations whenever possible (line 176-178, line 278-279). Since the paper is theory-focused, we try to provide the most rigorous model and anlysis. We will try to improve as follows: \n- We make and will add the following schematic to help the visualization of our framework in the introduction: https://imgur.com/a/P3AFsPo, which highlights how layer-wise quantization can optimally choose different compression type depending on the importance of the layers. \n\n- For notational simplicity, we consider an arbitrary layer type and remove index $m$ in the initial discussion of Section 3.1 as follows:\n(Fix a type $m$.) Let $\\upsilon$ denote the index of a level with respect to an entry $u\\in[0,1]$ such that $\\ell_{\\upsilon} \\leq u < \\ell_{\\upsilon+1}$. Let $\\xi(u) = (u - \\ell_{\\upsilon})/(\\ell_{\\upsilon+1} - \\ell_{\\upsilon})$ be the relative distance of $u$ to the level $\\upsilon + 1$. For a sequence $\\bf{\\ell}$, we define the following random variable $q_{\\bf{\\ell}}(u) = \\ell_{\\upsilon} \\text{ with probability } 1-\\xi(u)$ and $\\ell_{\\upsilon+1} \\text{ with probability } \\xi(u)$. The later part in Section 3.1 will follow a similar simplication.\n\nQ4: How does layer-wise quantization affect final model accuracy?\n\nA4: We refer the reviewer to Figure 1, where we compare applying layer-wise quantization with the full-precision baseline. The figure indicates that the adaptive QODA approach not only recovers the full-precision baseline accuracy but also improves convergence relative to Q-GenX [3] (line 373-375 on the right half page). Moreover, Table 1 and 2 show that QODA achieves this accuracy under much faster time per optimization than the full-precision baseline.\n\nQ5: Can QODA be integrated with mixed-precision methods to further improve efficiency? A discussion on QODA’s compatibility with mixed-precision training would be valuable.\n\nA5: Yes, indeed. Mixed-precision methods seek to reduce the computational cost of one or more of the three matrix multiplications employed during training for e.g. linear layers (one on the forward and two on the backward pass). As noted above, QODA is complementary to such techniques, as it serves to reduce the precision in which the gradient is stored and transmitted. Thus, mixed-precision techniques do not directly address communication costs, but could be applied in conjunction with QODA, to reduce both computational and communication costs. From the reviewr feedback, we will elaborate this extension in the future manuscript. \n\nQ6: Adding an ablation study on how different layers benefit from different quantization levels would strengthen the paper.\n\nA6: We are currently running the experiments and will provide the result in the discussion period. \n\nReferences: \n\n[1] Ashkboos et al., EfQAT: An Efficient Framework for Quantization-Aware Training, 2024.\n\n[2] Frantar et al., GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers, ICLR 2023.\n\n[3] Ramezani-Kebrya et al., Distributed extra-gradient with optimal complexity and communication guarantees, ICLR 2023.", "claims_and_evidence": "The claims seems to be well supported by empirical evidence an theory.", "methods_and_evaluation_criteria": "Experiments focus on training speed, comparing QODA against Q-GenX and uncompressed baselines on GANs (WGAN on CIFAR-10/100) and Transformer-XL (WikiText-103).", "theoretical_claims": "The convergence guarantees for QODA follow principles from distributed optimization and variational inequalities, though I did not verify every proof in depth.", "experimental_designs_or_analyses": "I checked the experimental design design and anlyses and it appears okay to me.", "relation_to_broader_scientific_literature": "- The work extends gradient quantization techniques (e.g., QSGD, adaptive compression methods) by making them layer-aware and variance-optimal.\n- It contributes to distributed optimization by integrating optimistic gradient methods into quantized variational inequality solvers.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n- The layer-wise quantization approach is well-motivated.\n- The variance and code-length bounds extend previous quantization results and improve efficiency.\n- The empirical results demonstrate significant training speed improvements.\n- The scalability study (Table 2) confirms that QODA maintains efficiency up to 16 GPUs.\n\nWeaknesses:\n\n- The paper does not analyze accuracy trade-offs—does layer-wise quantization affect generalization or model stability?\n- A comparison with other quantization techniques would highlight the benefit of this approach.\n- For someone who is not that experienced in this area, this paper is not easy to understand. I believe the Introduction could be improved a bit to provide the context. Paper also seems to be a bit overusing the notations.", "other_comments_or_suggestions": "- A discussion on QODA’s compatibility with mixed-precision training would be valuable.\n- Adding an ablation study on how different layers benefit from different quantization levels would strengthen the paper.\n- Writing could be improved a bit.", "questions_for_authors": "- How does layer-wise quantization affect final model accuracy?\n- How does QODA compare to quantization-aware training (QAT) and post-training quantization (PTQ)?\n- Can QODA be integrated with mixed-precision methods to further improve efficiency?", "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": {"ethical_review_concerns": "NA"}}, {"review_id": "XPlechyXOj", "reviewer": "Reviewer_tMrp", "summary": "Authors  develop a general layer-wise quantization framework with tight variance and code-length bounds, adapting to the heterogeneities over the course of training on variational inequalities (VIs) method. Authors first apply layer-wise minimizing quantization variance upon the quantization progress. Then authors proposing a novel Quantized Optimistic Dual Averaging (QODA) algorithm with adaptive learning\nrates, which achieves competitive convergence rates for monotone VIs.Experimental results reveal that the proposed methods achieve 150% speedup over the baselines in end-to-end training time for training Wasserstein GAN on 12+ GPUs.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Thank you for the detailed comments.\n\n1: Regarding (1), we believe our significant speedup with 16 GPUs are sufficent for a **theory** paper on distributed VIs (DVIs). We list all the related theory DVIs works (in top ML conferences) and no. of GPUs used. [2] is the only one with 16 GPUs like us, while the rest use fewer or only simulated nodes on CPU.\n|Paper| no. of GPUs|\n|--------|-------|\n|[1]|4|\n|[2]|16|\n|[3]|0, simulated nodes|\n|[4]|0, simulated nodes|\n|[5]|0, only CPU|\n\nRegarding (2), our main novelty is not to show the known heterogenity in the literature. This heterogenity provides the motivations for us to design our quantization method. Our focus is on providing the **theoretical** framework and bounds for layerwise quantization and introducing QODA for distributed VIs with strong theoretical guarantees. \n\n2: There is a misunderstanding. Throughout the paper, we usually denote a vector that will be quantized later $\\mathbf{v}$, simply represented by the tuple ($ ||\\mathbf{v}||_q, s, u$). \n\nThis does not mean that the vector $\\mathbf{v}$ is quantized as such. For quantization, we refer you to lines 188-192, where the quantization of $\\mathbf{v}$ is defined with quantization random variable $q_\\ell$. We will move the Section 2.1 to Section 3 to improve clarity. \n\n3: The assumption 2.4 is standard in stochastic VIs [6, 7]. Classical work [7] list out several general operators in Section 2.2 that falls under this assumption, such as the Matrix Minimax problem [8,Section 2.2.2].\n\n4: $\\sigma_R$ is a constant that shows how the error vanishes near a solution of VI [6]. We will fix the writing as: ... and there exists $\\sigma_R >0$ such that $\\mathbb{E}\\left[\\|U(\\mathbf{x}, \\omega)\\|^2_\\ast\\right] \\leq \\sigma_R \\|A(\\mathbf{x})\\|_\\ast^2$.\n\n5+8: The key point is that our layer-wise quantization framework is versatile and independent of the underlying optimizer. For instance, we demonstrate its applicability with Transformer XL (Table 3). Meanwhile, QODA is a novel method we introduce with theoretical guarantees for DVIs, and its contribution is distinct from the broader layer-wise quantization framework. For Qn8, QODA is our novel method along with its guarantees for DVIs since it recovers the order optimal O(1/T) rate which Adam and GD cannot [8].\n\n6: We simplify the notations as follows: \n\nWe consider an arbitrary layer type and remove index $m$. Let $\\upsilon$ be the index of a level w.r.t an entry $u\\in[0,1]$ such that $\\ell_{\\upsilon} \\leq u < \\ell_{\\upsilon+1}$. Let $\\xi(u) = (u - \\ell_{\\upsilon})/(\\ell_{\\upsilon+1} - \\ell_{\\upsilon})$ be the relative distance of $u$ to the level $\\upsilon + 1$. For a sequence $\\bf{\\ell}$, define the random variable $q_{\\bf{\\ell}}(u)= \\ell_{\\upsilon} \\text{ with probability }1-\\xi(u)$ and $=\\ell_{\\upsilon+1} \\text{ with probability }\\xi(u)$. The rest will follow a similar simplication.\n\n7: For optimistic methods, this extra variable serves as a predictive term. It is used to \"look ahead\" to the gradient in the next iteration based on previous gradient information. That is, this anticipatory step with $Y_t$ allows the update rule to be more informed, improving convergence speed and stability.\n\n9: Our novelties here are to design quantization with ODA and to propose adaptive learning rates that leads to optimal guarantees (section 5) under milder assumptions. Firstly, our optimistic approach reduces one “extra” gradient step that extra gradient methods like Q-GenX [1] take, hence reduceing the communication burden by half. Secondly, we design the adaptive learning rates (equation (4)) to obtain guarantees with fewer assumptions.\n\n10: We selected 5-bit compression because our experiments indicated that it is the lowest bit-width at which we reliably recover baseline accuracy. We also tested 4-bit compression, the training performance was nearly identical. Our goal is to show that even with aggressive compression, our method maintains baseline performance while offering significant computational benefits. \n\n11: We refer the reviewer to Figure 1. In lines 373-375 (right half page), we states that in Fig 1, QODA approach not only recovers the baseline accuracy but also improves the performance relative to Q-GenX. \n\nRefs: \n\n[1] Distributed extra-gradient with optimal complexity and communication guarantees, ICLR 2023, \n\n[2] Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees, NeuRIPS 2022\n\n[3] Byzantine-Tolerant Methods for Distributed Variational Inequalities, NeuRIPS 2023\n\n[4] Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods, AISTATS 2023\n\n[5] Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates, ICLR 2024\n\n[6] Polyak, Introduction to optimization, 1987\n\n[7] Solving Variational Inequalities with Stochastic Mirror-Prox algorithm, Stochastic Systems 2011 \n\n[8] Training GANs with Optimism, ICLR 2018", "claims_and_evidence": "Some claims are not supported in the manuscripts. See \"Other strengths and weaknesses\" for details.", "methods_and_evaluation_criteria": "I've checked all theoretical and qualitative analysis and claims in this paper. See \"Other Strengths And Weaknesses\" part of this review for my major & minor concerns about the methodology and equation derivation.", "theoretical_claims": "I've checked all theoretical and qualitative analysis and claims in this paper. See \"Other Strengths And Weaknesses\" part of this review for my major & minor concerns about the methodology and equation derivation.", "experimental_designs_or_analyses": "I've checked all experimental settings, comparison and results in this paper. See \"Other Strengths And Weaknesses\" part of this review for my major & minor concerns about the experimental part.", "relation_to_broader_scientific_literature": "All contributions are technical and all datasets used for experiments are open-sourced. Thus no key contributions of this paper related to the broader scientific literature.", "essential_references_not_discussed": "All necessary references are discussed.", "other_strengths_and_weaknesses": "## Major weaknesses\n1. Many claims in the section of introduction are not proved or solved by the methods proposed by authors, maybe they are, but authors do not provide any experiment about these claims:\n(1). From line32 to line45, authors mention \"large-scale distributed training\", however, I do not find any experiments about NNs trained on \"large-scale\" nodes. \n(2). In the second paragraph of introduction, authors claim that layers and structures in different DNNs can be diverse and previous arts lack generalization. Also I do not find extensive enough experiments about different structured NNs, e.g., RNN, CNN, RWKV, Mamba, etc.\n(3). The first three paragraphs are talking about diverse NNs and distributed across nodes, which can be different devices. Then why in the last paragraph, authors only proposed a method based on distributed VIs. The writing logic is weird. \n2. In section 2.1, authors claim that this method is quantization, however, $\\\\mathbf{s} := [sign(v_i), \\\\cdots]^{\\\\top}$, the sign function is only used in network binarization, which is an extreme condition of quantization. Therefore, the claim or the definition of $\\\\mathbf{s}$ is wrong, if quantization, it would be $\\\\mathbf{s} := [round(v_i), \\\\cdots]^{\\\\top}$\n3. How is the Assumption 2.4 obtained? If just define the oracle $g(\\\\cdot)$ to satisfy the two conditions, then how to prove that authors can always find a proper $g(\\\\cdot)$?\n4. What does the $\\\\sigma_R$ in the Assumption 2.5 represent for?\n5. In the first paragraph in section3.1, authors use SGD as optimizer and QSGD with several series work as baseline. However, when distributed training large-scale LLMs, ViTs, and MLLMs, Adam and Admaw are the most chosen optimizers. Thus the methods proposed by authors can not be directly generalized to the aforementioned conditions. \n6. The \"Quantization Variance\" paragraph in section 3.1 is just describing that first calculate the quantization variance of each $m$ level and minimizing them, second based on absolute noise, replacing $A(x)$ by the oracle $g(\\\\cdot)$. However, there are too many different symbols and notations, the writing is very hard to follow, while the method itself is simple. \n7. What does $Y_t$ in Algorithm1 represent for?\n8. Same as question 5, if Adam and Adamw are applied, the equation ODA would be different and need specialized design. \n9. Seems like the only novelty of section 4 is proposed a middle variable $Y_t$ compare to previous methods?\n10. Why only use 5-bit for experiments? What about other bit-width setting? The experiments are not extensive enough to prove the effectiveness of the proposed method.  \n11. Why only compare the timecost in Table 1&2, what about the performance?Would your methods affect the performance?", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "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": "BSv07toZzr", "reviewer": "Reviewer_X8sM", "summary": "*I am not familiar with this line of research, so my confidence in the following review is limited. While I will provide feedback based on my understanding, please keep in mind that my assessment may not be entirely precise.*\n\n- The paper provides theoretical guarantees for layer-wise quantization and demonstrates its advantages over global quantization.\n- It then introduces a new layer-wise quantization algorithm, QODA, designed to solve the variational inequality problem in a distributed setting. \n- By leveraging gradients stored from previous iterations, QODA improves the computational efficiency of the existing method, Q-GenX.\nThe authors evaluate their approach on GAN fine-tuning, showing that QODA with layer-wise quantization outperforms its global quantization counterpart, Q-GenX.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you very much for your time and your comments on our work. We will address your concern as follows:\n\nQ1: To my understanding, the QODA algorithm appears to be agnostic to the choice between layer-wise and global quantization. The authors present results for both approaches under the QODA-based extended Adam optimizer. However, the impact of the QODA algorithm itself does not seem to be explicitly ablated in the experiments. It would be helpful if the authors could provide results comparing Q-GenX training and QODA, both using the global quantization setting.\n\nA1: In Appendix G, we have compared Q-GenX and QODA in full precision setting with no quantization for a bilinear game with the feedback that is is corrupted by relative noise. Under this setting, Q-GenX and QODA are equivalent to GEG and ODA, respectively. From Figure 2, we can observe that the performance of ODA is significantly better than GEG. In fact, it is known in the literature that GEG diverges for certain standard settings like this simple bilinear problem [1,2]. ODA with stepsize seperation can help to prevent this issue [1]. \n\nReferences:\n\n[1] Hsieh et al., No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation, NeuRIPS 2022\n\n[2] Daskalakis et al., Training GANs with Optimism, ICLR 2018", "claims_and_evidence": "**Q1:**\nTo my understanding, the QODA algorithm appears to be agnostic to the choice between layer-wise and global quantization. The authors present results for both approaches under the QODA-based extended Adam optimizer. However, the impact of the QODA algorithm itself does not seem to be explicitly ablated in the experiments. It would be helpful if the authors could provide results comparing Q-GenX training and QODA, both using the global quantization setting.", "methods_and_evaluation_criteria": "See the comments and questions above.", "theoretical_claims": "See the comments and questions above.", "experimental_designs_or_analyses": "See the comments and questions above.", "relation_to_broader_scientific_literature": "See the comments and questions above.", "essential_references_not_discussed": "See the comments and questions above.", "other_strengths_and_weaknesses": "See the comments and questions above.", "other_comments_or_suggestions": "See the comments and questions above.", "questions_for_authors": "See the comments and questions above.", "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:

Meta-review: This paper introduces a layer-wise quantization framework to adapt to heterogeneity across deep neural network layers during training. The authors extend this framework and propose Quantized Optimistic Dual Averaging (QODA), a distributed optimization algorithm to solve variational inequalities (VIs) with adaptive learning rates. The method comes with convergence guarantees and provides up to a 150% speedup on tasks such as training Wasserstein GANs with 12+ GPUs.

While adaptive layer-wise quantization has been studied empirically in prior work, the paper provides a general theoretical framework and establishes tight bounds for layer-wise quantization. Despite some clarity issues and limited scope of empirical validation, all reviewers found that the paper provides a significant contribution to the area of quantized optimization for distributed training.
Decision: Accept (poster)