- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The authors present a new algorithm that aims to make asynchronous SGD robust to Byzantine clients. The algorithm bridge asynchronous SGD and synchronous Byzantine-robust SGD via a parameter . This parameter , central to their method, serves to downweight exponentially a client's step size by for repeated updates within the same round. It then synchronize all clients at the end of a round. They claim robustness by providing a convergence rate upper bound and evaluate the method empirically against known Byzantine attacks and other algorithms tackling the same problem. Interestingly, they also provide empirical evaluation of the proposed method without Byzantine clients.
Critical strengths
The problem tackled by the authors is very interesting. The soft throttling mechanism is an intuitive idea, and the two-stage virtual sequence is a creative analytical approach
Critical weaknesses
The paper is clearly presented until Section 3, where the contribution is detailed. There, there are presentation flaws:
- Validity of Theorem 1 (see questions). Indeed, the authors use a random step-size that they falsely treat as constant in the theory part of the paper. This is compounded by the fact that some of the important quantities (specifically the random one: , ) are not defined in the main text.
- In experiments, is set quite low when the theory requires high . Moreover, the claim "THROTTLE is robust and outperforms existing algorithms in almost all type of attacks." does not match the experiments. Indeed, in every experiment, at least one existing algorithm achieve similar or better accuracy. We acknowledge the fact that momentum might be one of the explanation as important in Byzantine optimization, but then why not directly doing the analysis with momentum as proven necessary for noisy Byzantine optimization? Moreover, the graph is very difficult to read due to the color choices (which change between different graph...): I cannot be sure which is BSGD and which is -SGD reading the graph. I would advise the authors to use dotted or dashed lines. Additionally, the Figure 2 would probably gain to stop prior 15 000 simulated wall-clock time as it shadow the interesting first steps. In Figure 3, the authors "averaged over three seeds" but does not report variance.
Questions for authors
Theoretical section.
I have one major question which if not resolved is a major flaw invalidating Theorem 1.
- and are not defined in Theorem 1, while they are important quantities to analyze the main terms of the bound through . is not analyzed or explained. Upon deeper inspection (Appendix C.2, lines 888, 896, and 941), , , are a random variables while they appear in an expected bound, which is a fundamental flaw. To prove a valid bound, the authors need to prove (1) an almost sure bound that holds for every single possible realization; or (2) show how constraints the worst-case and when a Byzantine adversary tries to flood the server. As stated, the learning rate of the Theorem 1 depends on the random variable and , and hence using variables that depend on the future, which is a flaw invalidating Theorem 1. Here, some instances of this error:
- In the proof of theorem 1, the line 1192 is invalid because is random and correlated with .
- In the appendix, the filtration , used throughout the proofs, is only defined fuzzily in an optional Lemma 1. More importantly, in Lemma 6 (Line 1076) and Theorem 2 (Line 1152), the authors write the conditional expectation assuming where this is not true because for , . Similarly, Line 1188 (Proof of Theorem 1) if false.
Upon answering the validity or invalidity of the main theorem (Theorem 1), I have the following other questions.
- Why do you choose a diameter-based aggregation compared to -robustness which prove better in their problem parameters dependence?
- The authors rely on assuming the partition between Byzantine and good client is fixed (line 067). I wonder whether Throttle algorithm would hold without this assumption.
- In Algorithm 1 between processing first arrivals (Line 5) and repeated arrivals (Line 7) requires jumping to the appendix to fully decipher. Why after first arrival the authors only clip the gradient?
Experimental section.
- Why experiments use different setting than in theory (lines 321-323)? Indeed, the author used instead of . How the authors expect the result change with this parameter? Why does throttle fail under the Empire attack compared to BASGDm, and why were baselines only tuned on non-Byzantine data with such a coarse grid? Does this not risk confounding algorithmic failure with poor hyperparameter selection?
- The authors acknowledge the necessity of using momentum to make the term in the convergence rate of synchronous Byzantine optimization vanish. What are the main difficulties to use momentum in their framework?
- How do you justify the practical utility of the convergence bound in Theorem 1 (if made true) when the optimal empirical setting () causes the error term to be huge, thereby nullifying the theoretical robustness guarantee?
- Why does throttle fail under the Empire attack compared to BASGDm? Why were baselines only tuned on non-Byzantine data with such a coarse grid? Does this not risk confounding algorithmic failure with poor hyperparameter selection?
If clearly addressed, I am willing to increase my score for acceptance.
Minor comments.
- Line 026, the claim "Distributed learning trains a shared model faster by spreading the training workload across many clients." requires a citation or a proof.
- Line 066, "dataset" instead of "data distribution"? Is the sample in Equation (1) a fresh sample every time or drawn from a dataset?
- As stated, Assumption 1 contain a superfluous conditioning on a constant vector , or does not encompass the definition the authors would want to assume.
- Line 416, "drawn with probability proportional to its index" instead of "inversely proportional"?
2 comments
Thanks for the answers. Given the limitation of the current manuscript, I will keep my score but I hope this reviewing round helps the authors to carefully revise their manuscript.
RM1b
We thank the reviewer for the constructive comments.
Theory
Clarification on Teff
We appreciate the careful check of our proof. We agree the proof is incorrect: the decomposition at line 1192 does not give the conditional unbiasedness used in the descent step. We have fixed this by assuming the schedule S is independent of the gradient samples. Given S and the past, ηt, x(t) and z(t) are fixed and gt is still unbiased, so the updated Theorem holds for E[⋅∣S] with the same bound as before. The assumption may look restrictive but the fixed computation model (Mishchenko et al., 2022; Tyurin & Richtárik, 2023) satisfies the assumption. We have made new detailed remarks on this matter after the proof of the Theorem 1 in the paper.
Aggregator Choice
We thank the reviewer for this insightful comment. We agree that (f,κ)-robustness (Allouah et al., 2023, Proposition 9) provides strictly better dependence on problem parameters such as the dimension d, compared to the diameter-based (c,δ)-robustness criterion used in our current analysis. We appreciate the reviewer bringing this comparison to our attention.
Byzantine Partition
We are grateful for this question. There are potential three cases to consider:
Necessity of Gradient Clipping
We thank the reviewer for pointing this out. We chose clipping for repeated arrivals to simplify the analysis. With (λt=G), clipping leaves honest gradients unchanged under Assumption 3, while every clipped vector has norm at most (G). Soft throttling then bounds the total contribution of repeated Byzantine updates within each round. These properties are sufficient for our convergence guarantee.
Experiments
Choice of Clipping Parameter λt
We welcome this point. As in above section, for theory, we set λt=G in the theorem for analytical tractability. In practice, the clipping radius is a tunable parameter, and we used λt=1 in our paper's experiments (see Table below for more values of λ).
This type of argument also arises in differentially private optimization. There, theoretical analyses (Feldman et al., 2018; Feldman et al., 2020) commonly assume uniformly bounded gradients (equivalent to Lipschitz assumption under the regularity of the loss in our paper), whereas empirical large-scale language model training uses thresholds that actively clip most gradients (Li et al., 2022).
Additional Hyperparameter tuning for Empire Attack (Improved!)
This suggestion was very helpful. After this comment, we re-ran the experiments for Empire case with other hyperparameters centered clipping parameter τ and gradient clipping parameter λ (other than this, we made other factors fixed).
The following table shows the final accuracy for Throttle with three different seeds.
Throttle's performance significantly improved (if not best among all methods) with careful tuning of hyperparameters even without momentum.
Minor comments
We thank the reviewer for catching this typo. “Proportional” is correct (clients are sampled pi∝i,). We have updated the manuscript accordingly for other points.
References