Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper studies distributed learning in the presence of Byzantine workers in the asynchronous setting. Its main contributions include generalization of the existing literature on Byzantine fault tolerance in distributed learning to incorporate the case of asynchronous learning. This generalization involves an algorithm, convergence analysis for the algorithm, and experimental results. While the results presented in the paper appear to be correct, I would like the authors to focus on the following points during their revision.

1. In Section 2.2, the definition of Byzantine worker, it is not clear why the worker is being indexed with $k_t$? What is the meaning of $t$ in this usage of the worker index?
2. The writing of the paper could use some proofreading. Some of the sentences are hard to parse on first read, while some other sentences suffer from grammatical errors. As a specific example, I could not understand the meaning of "Only when all buffers have got changed since the last SGD step, ..." in Section 3.1 until I reread the main parts of the paper.
3. Related to the previous point, the discussion in Section 3.1 in general is hard to parse because of the notation and could benefit from revision. Also, $m$ in this section is undefined up to this point in time and it is not clear what it means.
4. A number of aggregation functions have been proposed in prior works (see e.g. Adversary-resilient distributed and decentralized statistical inference and machine learning: An overview of recent advances under the Byzantine threat model). Do all of these previous aggregation functions satisfy the characterization of Section 3.2? It would be helpful to have some discussion of this.
5. Theorem 1 and Theorem 2 leave something to be desired. Since the task is to engage in distributed learning, one expects to see some sort of speedup from the fact that $n$ workers are being used to divide up the work. However this speed-up does not seem to be coming up in the analysis or the discussion. In the absence of such a speed-up, it is not clear if the authors are really providing guarantees that are useful for distributed learning.
6. It would be useful to discuss the impact of heavily delayed workers on the algorithm. What if the sum of the number of heavily delayed workers and Byzantine workers exceeds $r$?
7. The plots corresponding to the experimental results are too small and should be modified to have bigger font and size.

***Post-discussion period comments***
The authors have done an adequate job of responding to my queries and have also revised the paper in light of the comments of all the reviewers. While the paper could always be improved, I believe it is now above the threshold of acceptance and it should be accepted into the program, if possible. I am raising my score for this paper in light of the discussion and the revised paper.
review_title: A decent paper, but a number of important points are not carefully discussed in it.

final_score: rating: 6: Marginally above acceptance threshold
review_content: #### Summary

This work proposes a method for Byzantine learning in a parameter-server setting using asynchronous updates, and without the need for storing training instances on the master node. They provide theoretical guarantees and some experiments on small-scale tasks.

---

#### Originality

Synchronous methods for byzantine learning enable one to compare communicated gradients with one another in order to filter out byzantine workers. When updates are asynchronous, such a procedure cannot be employed because gradients are not necessarily communicated to the master node at the same time. Previous work on Asynchronous byzantine learning stores training instances on the master node to alleviate this issue. This work proposes instead to use gradient buffers on the server to eliminate the need to store training instances on the master node; this is the main selling point of the algorithm, and deems the method sufficiently novel in my opinion.

However, the motivation for avoiding storing instances on the master node is not well fleshed out in my opinion. Though the applications to Federated Learning are mentioned, updates are typically performed locally on-device and *parameters* are communicated back to the master, and therefore this method is not applicable to that setting. It is unclear exactly what the privacy concerns are, but I would suggest reworking the motivation exposition a little.

---

#### Significance and Quality

The method is actually quite nice and intuitive. The significance relates back to improving the motivation, but the method may be of sufficient interest to the community.

*On the theory*:

Note that the bounded gradient assumption is very strong! when combined with the L-smoothness assumption, it implies a convergent subsequence a priori! In short, it is like assuming ahead of time that the algorithm convergence.

$N^t_b$ is used in the main paper (e.g., page 5), but is only defined in the appendix on page 14. I would suggest including a one sentence description that these are the number of gradients stored in buffer $b$ at iteration $t$.

Under asynchrony or non-iid data, theorem 1 does not guarantee convergence to a stationary point… even with a diminishing step-size. Moreover, even with iid data and fully synchronicity and a diminishing step-size, the algorithm still does not converge to a stationary point due to the extra variance term on the r.h.s. I do not mean to criticize the results; only to point out this fact. Moreover, these bounds are somewhat vacuous due to the presence of the non-degrading $D$ gradient boundedness term on the r.h.s of Theorem 1 in the variance term. With L-smoothness and the assumption of $D$-bounded gradients, as I mentioned above, all iterates of any objective (regardless of the algorithm), will remain with a ball of a stationary point, the size of which is proportional to $D$. (To the authors credit, I have seen similar bounds in previous byzantine learning methods).

For Theorem 2, as I understand it, the $\alpha^{1/2}$ term actually has a $\mathcal{O}(1/\sqrt{T})$ dependence, so unless i’m missing something, why not remove the constant $\alpha$ and substitute in a quantity that decays with $1/\sqrt{T}$, and state the theorem results for all $T \geq$ some threshold (to satisfy the current $\alpha < 1$ constraint). this reformulation will make it clearer that the only lingering (non-decaying factor) is $A_1$, which is due to gradient bias.

More generally, I am curious if there is a way to correct for the convergence errors and improve the results to guarantee convergence to a stationary point (and not some neighborhood thereof), given that a $\frac{1}{\sqrt{T}}$ step-size is employed. 

---

#### Clarity

Work is sufficiently clear. One minor point is that Asynchronous SGD is missing a reference (common references for this method include Dean et al., or Bengio et al.)

review_title: Interesting method

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes a practical asynchronous stochastic gradient descent for Byzantine distributed learning where some of transmitted gradients are likely to be replaced by arbitrary vectors. Specifically, the server temporarily stores gradients on multiple  (namely $B$) buffers and performs a proper robust aggregation to compute a more robust from them. When $B = 1$,  BASGD is reduced to ASGD. They also conduct experiments to show the performance of BASGD. 

The paper is well written and easy to follow. All proof seems correct though I didn’t check very carefully. However, there are some issues:
1. Compared to other asynchronous SGD methods, one advantage of BASGD is it doesn’t have the need of storing any samples on the server. However, I didn’t understand why such property is meaningful. The authors declare that it helps BASGD take less risk of privacy leakage. Noting the server store gradients on buffers and gradients may leak privacy [1]. If a third party can have access to the buffers, privacy leak can still happen. BASGD didn’t use techniques like differential privacy, so it seems ill-founded to say “BASGD takes less risk of privacy leakage”.
2. In my opinion, Theorem 1 doesn’t guarantee that BASGD is able to find a stationary point of $F$ since the extra constant variance will not vanish when $T$ goes infinity. By contrast, ZENO++, a robust fully asynchronous SGD, could ensure convergence to a stationary point. This strikes me that the theorem is quite weak. Theorem 2 has the same problem.
3. It makes me feel strange to assume the gradient is biased (Assumption 2). For example, If we want to minimize $F(w)$ but we use stochastic gradients computed from another $\tilde{F}(w)$ (that is totally different from $F(w)$), could we still guarantee the algorithm converges to the stationary point of $F(w)$? I am afraid the answer is NO. This thought experiment not only shows using biased gradients doesn’t help convergence but also shows Theorem 1 doesn’t guarantee the convergence of BASGD.
4. Some parts of the algorithm are not well explored. For example, how the performance of BASGD changes when we vary the value of $q$ or the value of $B$. The experiment didn’t explore these aspects. Besides, Noting that the number of buffers $B$ is quite important for good performance, however, there is no investigation on how $B$ affects convergence and no suggestion on how to choose a proper $B$. In experiments, $B$ is set in advance for no reason.

[1] Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems, pages 14747–14756, 2019.

---------
I have read the authors' response. The authors have addressed most of my concerns, but I still think the motivation is a little farfetched. Considering the paper indeed explorees some aspects (in theories and experiments) of the use of buffers in asynchronous Byzantine Learning, I will improve my point to 5.

review_title: Ok but not good enough

final_score: rating: 5: Marginally below acceptance threshold
review_content: Review: This paper proposes BASGD which uses buffers to perform asynchronous Byzantine learning. In each SGD step, all workers compute gradients and send them to the server where their ad buffer is updated. When all of the buffers are updated, the server performs an model update. When a worker send a gradient to the server, it also pulls the latest model and compute the gradient on it no matter the server update the model or not. The main contribution in this paper is to introduce a new approach to do asynchronous Byzantine learning without storing training samples on the server like zeno++.

=======================================================

Pros:

+ The problem of Byzantine learning in the asynchronous environment is interesting and has rarely been studied, especially under the assumption that the server has no training data.

+ The idea of using buffer on the server to achieve (partial) asynchrony is interesting.

+ This paper provides extensive experiments to demonstrate its effectiveness.

=======================================================

Concerns:

- BASGD is not fully asynchronous as the paper claims to be. The server only updates the model when all of the buffers are non-zero. That is, the whole system will be slowed down by the slowest buffer. The remaining good workers, at the time of waiting, are computing the gradients on the same model weight. In this case, BASGD resembles SBL with larger batch size but at the cost of tolerating less Byzantine workers.

- This paper does not explicitly state how to choose the number of buffers $B$ in order to achieve both asynchrony and Byzantine-robustness. In page 3, there are "BASGD introduces $B$ buffers ($0<B\le m$) on server". However, when $B$ is small, there is no robustness; when $B$ is large, there is no asynchrony.

- The Definition 1, 4, 5, are not common in Byzantine robust learning. Are these definitions used only to make the proof easier?

- The results in the theorems are not clearly presented. The $O(1/T)$ in Theorem 1 and 2 does not reflect how $B$, $q$ influence the convergence rate.

=======================================================

Minor comments:

- The negative gradient attack and random disturbance attack are very easy to defend. It would be better to choose some more challenging attacks.

- It is better to improve the writing in section 4 for better readability.

review_title: Good paper, but not fully asynchronous.

Meta-review: The authors present BASGD and asynchronous version of SGD that attempts to be robust against byzantine failures/attacks. 
The papers is overall well written and clearly presents the results. Some novelty is present as there have been limited work in asynchronous algorithms for byzantine ML. 

However, there have been several concerns raised by the reviewers, on which I agree, and they have not been fully addressed:
1) the tradeoff between asynchrony and robustness, as BASGD cannot handle the case of a buffer being straggler, which limits some of the novelty in this work
2) issues with the definition of privacy leakage has not been fully addressed
3) some reviewers mentioned the theoretical results being of limited importance, but arguably this is true for other related work in this area. Perhaps a general criticism is valid as to what is the operational value of the proposed guarantees. That is convergence does not exclude a model that has undesirable properties, eg has bad prediction accuracy for a small subset of tasks.
4) Finally, the motivation of the system model of the paper ( eg storing gradients as opposed to instances) paper is of unclear practical relevance, as was raised by multiple reviewers. 

Overall the consensus was that the paper does have merits, however, some of the most major concerns were not properly addressed. This paper can potentially be improved for a future venue.


Decision: Reject