Quantized Optimistic Dual Averaging with Adaptive Layer-wise Compression

Authors: Anh Duc Nguyen, Ilia Markov, Ali Ramezani-Kebrya, Kimon Antonakopoulos, Dan Alistarh, Volkan Cevher
Primary area: optimization
Keywords: Adaptive Compression, Layer-wise Compression, Distributed Variational Inequality, Optimistic Dual Averaging

Abstract:
We develop a general layer-wise and adaptive compression framework with applications to solving variational inequality problems (VI) in a large-scale and distributed setting where multiple nodes have access to local stochastic dual vectors. This framework encompasses a broad range of applications, spanning from distributed optimization to games. We establish tight error bounds and code-length bounds for adaptive layer-wise quantization that generalize  previous bounds for global quantization. We also propose Quantized and Generalized Optimistic Dual Averaging (QODA) with adaptive learning rates, which achieves optimal rate of convergence for distributed monotone VIs. We empirically show that the adaptive layer-wise compression achieves up to a 150% speedup in end-to-end training time for training Wasserstein GAN on 12+ GPUs.

Decision: reject
Reviewer scores: 5, 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1729098584862

thread_type:
official_review

<thread_object>
creator: reviewer_qdmj

<content>
summary:
The paper develops a general layer-wise compression framework to solve variational inequalities in a large scale distributed setting. Convergence guarantee for the proposed QODA algorithm with adaptive learning rates is provided. Empirical evidences supporting the claims of the paper are also provided.

strengths:
1. The paper provides theories and guarantees for layer-wise adaptive compression schemes, including tight-variance and code length bounds. The proposed algorithm combines optimism with adaptive layer-wise quantization, achieving state of the art performance.

2. Numerical evidences are provided in support of the effectiveness of the proposed algorithm, with improved in convergence performance.

3. The assumptions used in the paper are less restrictive compared to other existing work.

weaknesses:
See questions.

questions:
1. How do we select between protocal 1 and 2 in real scenario? Is there a clear guideline we can rely on?

2. Will the proposed mechanism impact on the stability of training especially in GANs, are there any experimental evidence? 

3. The layer-wised scheme in the paper refers to using different hyper-parameters for compression happens at each layer. Given the importance determined by existing information of each layer, is it possible to develop a compressor, that selects certain layers at some probabilities while temporarily ignores the other layers in this iteration? Previous studies suggests that this leads to benefits in solving empirical risk minimization problem, see [1].

4. The experiments focus on a relatively narrow range of applications (WGAN training), it could benefits from further validation on other models if possible.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730637617833

thread_type:
official_review

<thread_object>
creator: reviewer_738y

<content>
summary:
The authors develop a general layer-wise and adaptive compression framework with applications to solving variational inequality problems (VI) in a large-scale and distributed setting. This paper also propose a specific algorithm called Quantized and Generalized Optimistic Dual Averaging (QODA) with adaptive learning rates. The best convergence rate is achieved under the monotonicity assumption. Finally, the authors demenstrate the superiority of the QODA algorithm in training time through experiments.

strengths:
1.This work is the first to incorporate optimism in solving distributed VI with adaptive learning rates and layer-wise quantization. The authors propose QODA algorithm and establish joint convergence and communication guarantees for it.

2.The authors provide a very detailed and solid theoretical proof.

3.The experimen show that QODA with layer-wise compression significantly improves the convergence and training time compared to both the SoTA Q-GenX and the full precision baseline.

weaknesses:
I have tried my best to understand the authors' contributions in this paper, but I am not very familiar with the authors' research field. I can only give the authors some suggestions from the perspective of writing.

questions:
I am not an expert in this field, I can only give some advice on writing papers：

1.Line 116, "our work is the first work", deleting the second work.

2.Line 119, missing comma at the end of sentence.

3.Line 166, "such that each node retains only local copy of the current parameter vector" -> "such that each node retains only a local copy of the current parameter vector".

4.Line 179, "We first outline the general formulation for the layer-wise and unbiased quantization." -> "We first outline the general formulation for layer-wise and unbiased quantization.".

5.Line 344, "The proof is in Appendix C." -> "The proof is provided in Appendix C.".

6.Line 365, "The proofs are in Appendix D.2 and D.3, respectively." -> "The proofs are provided in Appendix D.2 and D.3, respectively.".

7.Line 385, "...... are updated with learning rate schedule in (6) for all t=......" -> "...... are updated with the learning rate schedule given in (6) for all t=......".

8.Line 456~Line 460, the tense is different.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730651958489

thread_type:
official_review

<thread_object>
creator: reviewer_rc6n

<content>
summary:
This paper proposes a theoretical framework for layer-wise and adaptive unbiased quantization with novel fine-grained coding protocol analysis, which is the first to incorporate distributed VI with adaptive learning rate and layer-wise quantization. They obtain acceptable convergence results under standard noises without the almost sure boundness.

strengths:
1. The theoretical analysis of compression bounds and convergence complexity propose a new framework for understanding distributed VI with layer-wise quantization, illustrating that distributed VI with layer-wise quantization can obtain standard $\Omega(d)$ variance and $\mathcal{O}(1/ \sqrt{T})$ or $\mathcal{O}(1/T)$ convergence rate.
2. The theoretical analysis achieve same rate with more relaxed assumptions compared with SOTA algorithm.

weaknesses:
1. This paper needs more clarification on the importance on the problem they study. In other words, why $\textbf{layer-wise}$ quantization is important in distributed VI? Even though the author introduces the heterogeneity observed by other work, this paper is also lack of enough examples and evidences to explain why this setting makes sense. In large-scale models (more than 1b parameters), especially beyond Transformer-XL or ResNet mentioned in [1], the effect of layer-wise quantization seems not obvious.  
2. Even though this paper proposes the compression bounds and convergence rates, it is lack of the theoretical analysis of total communication complexity, which is the per-iteration communication cost multiplies the communication rounds. Noticing that the convergence rate includes $\epsilon_Q$ which is $\Omega(d)$, I think the total communciation complexity is the same order of the algorithm without quiantization, which means no improvement in theory.
3. The writing of  this paper need improvement. This paper is lack of motivation and has too much notations and definitions (like encoding techniques) in main body, and the main theorem needs more remarks. Some typo needs to be modified like a superfluous "literature" in line 60.   

[1]  Ilia Markov,Kaveh Alim,Elias Frantar,and Dan Alistarh.L-greco:Layerwise-adaptive gradient compression for efficient data-parallel deep learning.

questions:
1. In this paper, the author considers the unbiased quatization in VI. However, in distributed optimization error feedback technique is widely used to reduce the information loss when encoding. I am interested in whether error feedback and corresponding biased quantization can be  applied to distributed VI and obtain faster rate?
2. The whole framework is still worthy, especially loosing the assumption. If author could explain my concerns in weakness and questions, I would like to improve my scores.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730766337340

thread_type:
official_review

<thread_object>
creator: reviewer_696t

<content>
summary:
## Update

After some discussion with the authors, I am increasing my score as they clarified the novelty of their quantization scheme compared to the prior literature. I remain convinced that the studied setting is still somewhat niche and the empirical results are very limited.

---


This paper develops a theoretical framework for adaptive layer-wise compression in distributed variational inequality (VI) problems, along with a novel algorithm called Quantized Optimistic Dual Averaging (QODA). The work makes several key contributions:
1. It establishes a rigorous theoretical framework for layer-wise and adaptive quantization schemes that accounts for heterogeneity across layers, providing variance and code-length bounds that generalize previous bounds for global quantization.
2. It introduces QODA, which uses optimistic updated with adaptive learning rates. The algorithm achieves optimal convergence rates of $O(1/\sqrt{T})$ and $O(1/T)$ under absolute and relative noise models respectively, without requiring the common assumption of almost sure boundedness of stochastic dual vectors. The provided theory shows how convergence rates depend on the gradient compression constant.
3. The authors also test QODA in training Wasserstein GAN on distributed systems with 4/8/12/16 GPUs.

The work builds upon the combination of Markov et al. (2022, 2024) and Ramezani-Kebrya et al., (2023). The former presented compression schemes and their empirical evaluations, while the latter had theory for distributed VI problems.

strengths:
1. Distributed training remains a challenge and good methods that compress gradients are desired to make it faster.
2. Relaxation of common boundedness assumptions while maintaining optimal convergence rates.

weaknesses:
This paper presents two contributions. The first one is to study the compression schemes previously proposed and studied empirically. 
1. It appears to me that the theoretical study is very similar to the well-known bounds of Alistarh et al. (2017), and while the notation is heavy, the underlying math is quite simple. I'm also not confident how important the studied compressions techniques are as they have not been around for a long time and do not seem to be popular in practice, for instance, the github repo of L-Greco has 12 stars.
2. The algorithmic contribution of QODA is marginal. It is a method based on the combination of two widely studied techniques: gradient/operator compression and optimism. Since the compression operator is unbiased, it seems very straightforward to derive the convergence guarantees. The adaptive learning rates have been used in the prior literature on VI problems too.
3. The experimental evaluation is a bit limited and serves more as a proof of concept. However, the work appears to be mostly theoretical, so I wouldn't put too much emphasis on this.

## Minor
line 48 "communication though local updates" -> "communication through local updates"  
line 60 "literature communication-efficient liteature" -> "communication-efficient literature"  
line 66, "dearth of generalization" -> "death of generalization"?

questions:
1. The authors refer to Q-GenX as "SoTA". Can you clarify in what sense it is state of the art? What exactly makes it worthy improving upon? Is there evidence the method is widely used in practice?
2. The authors study a general family of compressors using arbitrary $\ell_q$ norms. Should we expect a specific choice to always perform better in practice?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732634750316

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Revisions

comment:
Dear Reviewers, 

Incorporating valuable comments and recommendations from reviewers, we hope summarize the main changes in the revised manuscript as follows:
1. Regarding Reviewer 696T's comment on block quantization: We have included two references (Mishchenko et al., 2024, and Horvath et al., 2023) in Related Works Section 1.2 along with a follow-up discussion (Appendix A.2) that highlights how our layer-wise compression fundamentally differs from block quantization. In brief, each of our layer (or block in this context) has different adaptive sequences of levels (refer to our Section 3.1), while block quantization (Mishchenko et al., 2024) applies the same p-quantization scheme to blocks with various sizes. We are grateful that Reviewer 696T has recognized the novelty of our framework after the discussion on block quantization. 

2. Regarding Reviewer 696T's comment on using "SoTA" for Q-GenX (Ramezani-Kebrya et al., 2023): We have changed Q-GenX description to the global quantization baseline. Published in ICLR 2023, Q-GenX is a suitable distributed VI-solver with global quantization for us to compare against. Under similar theoretical settings with one less assumption of almost sure boundedness (of the operator), we achieve similar rates as Q-GenX. Our code-length bounds are also generalizations of Q-GenX (Remark 4.2, 4.5). Finally, we practically outperform this global quantization baseline in Figure 1. 

3. Regarding the typos raised by reviewers: We have fixed all of the mentioned typos. 

4. Regarding Reviewer rc6N's suggestion that the theorems need more remarks for clarity: We have formatted the text after key theorems as remarks for the sake of clarity. Hence there are three new remarks: Remarks 4.2, 4.5, and 4.9. We hope to clarify that these discussions with previous bounds in the literature are present in the past manuscript, so we only now formatted them as remarks for better clarity.

5. Regarding Reviewer qDMJ's comment on a relevant work for layer-wise compression for neural networks (Li et al., 2024): We have include this relevant work in our introduction, and the Section 1.2 of related works that leverage the layer-wise structure of DNNs for more efficient training techniques. 

6. Regarding the comment of limited experiments: We have provided realistic experiments, as opposed to simulation in the global quantization baseline QGen-X, on up to 16 GPUs in a multi-GPU system for this theory-oriented paper. As acknowledged by our section on weaknesses, we agree additional applications beyond training GANs can be provided, but it will also make the paper overly convoluted. Several applications of layer-wise quantization, such as training Transformer-XL on WikiText-103, have been explored in (Markov et al. 2022; 2024), which is not our main focus or novelty. We hope our theoretical novelty of the layer-wise compression framework and optimal theoretical guarantees under fewer assumptions outweight this limitation. 

We hope these changes strengthen our work and look forward to further discussion if you identify additional areas for improvement. Thank you very much!

Best regards,

Submission 6044 Authors

References:
- Mishchenko, Konstantin, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. "Distributed learning with compressed gradient differences." Optimization Methods and Software (2024): 1-16.

- Horváth, Samuel, Dmitry Kovalev, Konstantin Mishchenko, Peter Richtárik, and Sebastian Stich. "Stochastic distributed learning with gradient quantization and double-variance reduction." Optimization Methods and Software 38, no. 1 (2023): 91-106.

- Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NeurIPS), 2017.

- Ali Ramezani-Kebrya, Kimon Antonakopoulos, Igor Krawczuk, Justin Deschenaux, and Volkan Cevher. Distributed extra-gradient with optimal complexity and communication guarantees. In International Conference on Learning Representations (ICLR), 2023.

- Li Hanmin, Avetik Karagulyan, and Peter Richtárik. Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization. In International Conference on Learning Representations (ICLR), 2024
</content>
</thread_object>

</thread>


Metareview:
metareview:
Dear Authors,

Thank you for your valuable contribution to ICLR and the ML community. Your submitted paper has undergone a rigorous review process, and I have carefully read and considered the feedback provided by the reviewers.

This work presents a framework for adaptive layer-wise compression in distributed variational inequality problems. The approach uses adaptive learning rates and layer-wise quantization.

The paper received borderline final review scores (5,5,6,6). Reviewers pointed out certain critical issues including (i) issues with clarity and heavy notation, (ii) limited experimental results, (iii) limited novelty of the proposed methods. The authors provided a detailed rebuttal refuting some claims of the reviewers, in particular, regarding the novelty of the layer-wise quantization scheme, and relations to Mishchenko et al., 2024. I disagree the reviewer comment regarding the relevance of the popularity or number of Github stars of the L-Greco repository. Nevertheless, the reviewers did not find the rebuttal convincing enough to improve their scores further.

Given the current form of the paper and the reviewer discussion, I regret to inform you that I am unable to recommend the acceptance of the paper for publication at ICLR. I want to emphasize that this decision should not be viewed as a discouragement. In fact, the reviewers and I believe that your work has valuable insights and, with further development and refinement, can make a meaningful impact on the field.

I encourage you to carefully address the feedback provided by the reviewers and consider resubmitting the paper. Please use the comments and suggestions in the reviews to improve and refine your work.

Best,
AC