Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity

Summary

The paper studies distributed learning in the presense of Byzantine workers (that is, nodes that output adversarial results) and data heterogeneity. A previous notion of robustness for distributed learning, namely G-gradient dissimilarity, is not sufficient to capture data heterogeneity. In fact, this holds even in fairly simple tasks such as least-squares regression (i.e., for any G>0). Motivated by this observation, the paper defines a new notion of robustness for distributed learning, (G,B)-Gradient Dissimilarity. This allows for some additional error term in the average gradient difference between workers, proportionally to B. The proposed theory is used in a least squares regression task to justify observed robustness of stochastic gradient descent under small sets of dishonest workers.

Strengths

The paper presents an interesting notion of robustness in distributed learning. It is shown that this notion captures distributed gradient computation when a small number of workers can output arbitrary results. The theory is compelling and seems to justify observed behavior in a realistic setting. A theoretical criterion is given for algorithms to be robust against (G,B)-gradient dissimilarity. This is an interesting theoretical contribution.

Weaknesses

The precise formula used in the definition of (G,B)-Gradient Dissimilarity makes sense because the analysis is done for a variant of stochastic gradient descent. However, it is unclear whether this notion is also relevant to other distributed learning tasks. The precise setting regarding honest and Byzantine workers is confusing (see Questions section of this review).

Questions

What is the (G, B)-gradient dissimilarity in the experiments? Observation 1 does not require any Byzantine workers, right? Perhaps this should be emphasized. In Proposition 1, H is the set of honest workers. How do the honest workers know who is honest? Earlier in the paper it is mentioned that trying to compute any statistic over the whole set of workers is generally impossible in the presence of Byzantine workers. Does this mean that the task in Proposition 1 is impossible to perform in reality because H must be known to all honest workers? If so, this renders the whole model not very realistic.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors have adequately addressed the limitations of this work.

Summary

This paper considers under the robust distributed learning settings, the conventional learning error bounds are vacuous as they rely on restrictive assumptions as $G$-gradient dissimilarity (equation 2). The paper relaxes the assumption to a more general $(G, B)$-dissimilarity model that relaxes the bounds on gradients norm of honest workers with a constant of $B$. A new breakdown ratio between Byzantine and honest workers $f / n$ that would yield theoretical robustness guarantees is established as $ 1 / (2 + B^2) $. The authors finally show the tightness of $f / n < 1 / (2 + B^2)$ bound via analyzing the state of the art robustness coefficient $ \kappa = f / (n - 2f) $ on a robust D-GD that would also yield $ 1 / (2 + B^2) $ instead of $ 1 / 2 $ breakdown point. In this way, the gap between the previous theory and the empirical observation of the largest amount of Byzantine workers to have robustness guarantee on global honest loss (equation 1) is reduced.

Strengths

The paper borrows the data heterogenity model ($(G, B)$-dissimilarity) from the classical distributed learning settings to the Byzantine distributed learning and build a nice and intuitive theory on the breakdown point on the fraction of Byzantine workers to melt down the robustness guarantee. The paper narratives are clear and easy to follow, and the experiments (Figure 2, 3, 4) are well conducted.

Weaknesses

The novel breakpoint essentially involves a dependency over the constant over honest workers' gradient norm. It would be better to have an ablation study on logistic regression that if such constant $B$ is changed, we would observe similar changes in the breakpoint point. Otherwise, it is a great paper!

Questions

I am confused on the heuristic method to compute $G$ and $B$ in Appendix D.3, line 743. Could you explain such formula?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I didn't find any other limitations of this paper.

Summary

The work focuses on the analysis of the limits of Byzantine-robust learning under so-called $(G,B)$-dissimilarity assumption -- a generalization of the standard bounded gradient dissimilarity assumption. The main result of the paper is in establishing the upper bound for the maximal admissible ratio of Byzantine workers: $\delta < \frac{1}{2+B^2}$ that is separated from $\frac{1}{2}$ (and can be very small). The authors also derive the lower bound for the optimization error that matches the known upper bounds (up to numerical factors) and the derived upper bound for the robust version of the distributed gradient descent.

Strengths

1. The authors derive the limits on robustness under $(G,B)$-gradient dissimilarity that are quite interesting. In particular, the ratio of Byzantine workers has to be smaller than $\frac{1}{2+B^2}$ to guarantee the convergence to some neighborhood of the solution. Moreover, the lower bound for the optimization error $\varepsilon$ is established. These bounds are quite pessimistic ($B^2$ is proportional to the condition number in the worst case) and emphasize the non-triviality of Byzantine-robustness in the heterogeneous case. The construction of the worst-case examples is quite simple. 2. The paper is well-written in general, the idea is explained well in the main part of the paper. 3. The proofs look correct to me.

Weaknesses

The results of Theorem 2 are not completely novel. In particular, there exist results under $(G,B)$-dissimilarity assumption, see Theorem V from [18] and Theorems E.1, E.2 from [14]. These results are derived for the different notions of robust aggregator, but up to the replacement of $\kappa$ with $c\delta$ they recover Theorem 2 from this submission. Moreover, the method from [14] with $p=1$ and no compression coincides with Robust D-GD. The paper should be modified accordingly. Nevertheless, I see Theorem 1 as the main contribution.

Questions

1. In [17,18], another notion of robust aggregation was introduced. Are there any benefits of using a different notion of robustness? 2. Theorem 2, "let $f < n/2$": this is a bit confusing, because $\kappa$ implicitly depends on the ratio of Byzantines. 3. Although the proofs are detailed and look correct to me, it is a bit inconvenient to read them. In particular, I suggest moving the proofs of Lemmas 1 and 2 to Appendix B.1.2.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors adequately addressed the limitations.

Summary

In the present paper the authors study the problem of distributed learning in the presence of adversarial learners (aka Byzantine workers) and hetogeneous data. The paper aims to generalize and improve previous results on homogeneous data, an assumption that is claimed to be very restrictive in practice. For this they introduce a new concept of (G,B) gradient dissimilarity which has the same relation to the more standard G gradient dissimilarity as an affine variance assumptions has to a bounded variance assumption in stochastic optimization. Under their assumption they first prove that the breakdown point, i.e., the share of Byzantine workers beyond which the optimization breaks down is upper bounded by $\tfrac{1}{2+B^2}$, where previous results only yield the intuitive bound of $\tfrac12$. They also confirm this theoretical observation numerically. Second, they also establish sharp error bounds in the regime below the breakdown point by proving a lower bound as well as an upper bound, attained by robust distributed gradient descent.

Strengths

I find the paper very clear and well written. The theoretical contributions are very interesting and appear to be novel. Furthermore, the experiments illustrate the sharpness of the results. The proofs in the appendix seem to be sound although I have to say that I didn't check all the details in the proof of Theorem 1. I did check the convergence statement of Theorem 2 the proof of which is rather standard.

Weaknesses

I cannot list any significant weaknesses besides the few questions that I have in the next block.

Questions

p.2: Maybe you can make the connection between the G and (G,B) assumptions and bounded / affine variance assumptions in the analysis of SGD. p.6, last paragraph: can one estimate B here to see whether it is close to $\sqrt{2}$ which would fit to the $\tfrac14$ you observe numerically? p.7: Definition 4 should be followed by a few examples for $(f, \kappa)$-robust aggregation rules. Please also mention that in the absence of adversaries, one can just average the gradients and gets a $(0,0)$-robust aggregation rule. p.8: Here you start using nicefrac excessively which, at least for my brain, is very hard to read and process. Maybe you can use or stick to tfrac for inline fractions which you seemed to have used earlier. p.30: Number of honest workers should just be $n-f$ not $n-f=10$. If I understand this correctly $n=10$ and $f$ ranges from $1$ to $9$.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors did make the point that probably not all of their results are sharp, e.g., in terms of constants or the slow down factor for linear convergence in the presence of adversaries. Negative societal impact is not to be expected in my opinion.

Reply to rebuttal

Thanks for the clarifications. It would be great if you could also add the examples after Definition 4 but besides that I'm happy with the submission and will maintain my score.

Reply to the rebuttal

Thank you for the clarification. I now understand the estimation approach on $B$ in Appendix D.3.

Thank you for the clarifications

I thank the authors for the clarifications: all my questions are adequately addressed. Since the authors promised to modify the paper accordingly, I decided to keep my score unchanged.