Byzantine Robustness and Partial Participation Can Be Achieved Simultaneously: Just Clip Gradient Differences

The computation of full gradients is time-consuming. Moreover, it is unknown whether the gradient clipping is empirically compatible with the PAGE estimator. I strongly suggest the authors empirically test the performance of the proposed method on some federated learning benchmarks such as LEAF.

We have conducted preliminary experiments with the proposed method. We kindly refer to our general response and the revised manuscript.

---

References:

[1] Tyurin, A., & Richtárik, P. (2022). A computation and communication efficient method for distributed nonconvex problems in the partial participation setting. arXiv preprint arXiv:2205.15580.

The main differences between Byz-VR-MARINA-PP and Byz-VR-MARINA are that Byz-VR-MARINA-PP adopts gradient clipping and thus allows partial participation (PP). There are typically two benefits of PP, i.e., tolerating inactive clients and accelerating training processes. However, Byz-VR-MARINA-PP seems to perform poorly in either of the two aspects.

Tolerating inactive clients and accelerating the training process are indeed among the main benefits of methods supporting partial participation. However, it is important to distinguish two different situations: the scenario with client sampling and the setup where partial participation appears due to the unavailability of a fraction of clients during particular communication rounds. Our work studies the first case, i.e., we assume in our analysis that all clients are available at any time. Therefore, we do not study the problem of tolerating inactive clients in theory in all generality. Next, one can model the inactiveness of the clients as follows: each client is equally likely unavailable during each particular round with some probability (1-q). This is a common assumption in the literature on PP. Then, our analysis and results will still hold if we multiply $p_G$ and $p_{{\mathcal G}_C^k}$ by $q$. Finally, in some cases, as our experiments show, Byz-VR-MARINA-PP works even faster than Byz-VR-MARINA, implying that partial participation can accelerate the training for our method.

As presented in Algorithm 1, in Byz-VR-MARINA-PP, the clients are sampled by the server before each round. Therefore, if a selected client becomes inactive, the whole training process will be blocked. In other words, Byz-VR-MARINA-PP cannot tolerate inactive clients.

This is not a problem of our approach but rather an inevitable drawback of all synchronized Byzantine-robust methods: if implemented naively, even in the case of full participation, synchronized methods can be blocked by one Byzantine worker, who can just wait as much as possible without sending anything to the server. A simple way of handling this situation in practice is just to use some timeout for communication round. In this case, no peer can block the method. Therefore, if all sampled clients are inactive, then after a timeout, the server can set $g^{k+1} = g^k$ and run the next round as if the current round never happened.

All clients will participate in the $k$-th training round if $c_k = 1$. That is to say, all clients will participate in the training per $1/p$ rounds in expectation. I understand that $p$ is typically small. However, it will also greatly limit the acceleration effect of PP since in federated learning (especially in cross-device federated learning), the fraction of selected clients in each round is usually small.

We agree with the reviewer that the usage of the full participation with (even small) probability $p$ is something undesirable for the method with PP. The main reason why Byz-VR-MARINA-PP requires full participation during a small fraction of randomly chosen rounds is in the estimator construction: it is inspired by and based on the Geom-SARAH/PAGE estimator that also uses a full gradient computation with some probability to reset the variance-reduced estimator and control the variance. We apply a similar mechanism to control the variance coming from the sampling of clients. Avoiding full participation is an important direction for future research that we plan to work on. One possible way is to adopt the technique from the recent work [1], where the authors develop a method improving upon MARINA-PP. The key idea in their paper is to use the momentum-based variance reduction for controlling the variance coming from compression and partial participation. This helps to avoid full participation as well as uncompressed vector communication.

We also want to emphasize that the main novelty of this paper is in the usage of gradient clipping to handle the Byzantine workers in the case of partial participation. Clipping was used to construct robust aggregation by Karimireddy et al. (2021), but it was never used in the way we apply it. We believe our work is an important step towards building more efficient Byzantine-robust methods supporting partial participation. Moreover, in our experiments, we still observe the acceleration of the training due to partial participation.

Given the reasons above, could the authors specify what benefits the partial participation mechanism can bring?

Summing up our responses above, we highlight the following benefits of Byz-VR-MARINA-PP: the ability to tolerate inactive clients when all regular workers can be inactive with equal probabilities and acceleration of the training.

I thank the authors for the detailed response, which has addressed some of my concerns. However, there are still some remaining concerns, which I list below.

1. About partial participation (PP). I thank the author for explaining the setting in their work, where all clients are available at any time. There are typically two settings in FL: cross-device FL and cross-silo FL (Kairouz et al., 2021). In cross-device FL, clients are very likely to be unavailable. In cross-silo FL, the participants are typically companies or organizations, and most participants attend each round (i.e., PP is not needed in this case) (Kairouz et al., 2021). Could the authors provide some real-world applications where all clients are available at any time and PP is required?

2. About the experiment. I appreciate that the authors have added some numerical results. However, my concerns have not been fully addressed for the following reasons: (a) The task is quite easy. (b) The ability to handle heterogeneous cases is a main strength of the proposed method, but only homogeneous cases are considered in the experiment.

3. About the acceleration. Could the authors further explain the benefit of acceleration of Byz-VR-MARINA-PP. Does it mean the same precision can be achieved with less computation cost or less wall-clock time?

4. (minor) There is a typo on page 2: 'heterogenous' -> 'heterogeneous'.

Comparison to Data & Diggavi (2021)

We thank the reviewer for providing the reference. We were not aware of this paper during the work on our submission. We have added a detailed comparison to the paper and also provided it below.

The main difference between Data & Diggavi (2021) and our work is that Data & Diggavi (2021) assume that the number of participating clients $C$ at each round is such that $B \leq \epsilon C$, where $B$ is the overall number of Byzantine workers and $\epsilon \leq \frac{1}{3} - \epsilon’$ for some parameter $\epsilon’ > 0$ that will be explained later. That is, the results from Data & Diggavi (2021) do not hold when $C$ is smaller than $3B$, and, in particular, their algorithm cannot tolerate the situation when the server samples only Byzantine workers at some particular communication round. We also notice that when $C \geq 4B$, then existing methods such as Byz-VR-MARINA or Client Momentum (Karimireddy et al., 2021, 2022) can be applied without any changes to get a provable convergence. In contrast, our method converges in more challenging scenarios, e.g., Byz-VR-MARINA-PP provably converges even when $C = 1$ and, in particular, the situation when the server samples only Byzantine workers at some rounds does not break the convergence of our method.

Next, Data & Diggavi (2021) derive the upper bounds for the expected squared distance to the solution (in the strongly convex case) and the averaged expected squared norm of the gradient (in the non-convex case), where the expectation is taken w.r.t. the sampling of stochastic gradients only and the bounds itself hold with probability at least $1 - \frac{K}{H}\exp\left( - \frac{\epsilon’^2(1 - \epsilon)C}{16}\right)$, where $H$ is the number of local steps. For simplicity, consider the best-case scenario: $H = 1$. Then, the lower bound for this probability becomes negative when either $C$ is not large enough or when $K$ is large or when $\epsilon$ is close to $\frac{1}{3}$, e.g., for $K = 10^6, \epsilon = \epsilon’ = \frac{1}{6}, C = 5000$ the above lower bound is smaller than $-720$, meaning that in this case the result does not guarantee convergence. In contrast, our results have classical convergence criteria, where the expectations are taken w.r.t. the all randomness.

Finally, the bounds from Data & Diggavi (2021) have non-reduceable terms even for homogeneous data case: these terms are proportional to $\frac{\sigma^2}{b}$, where $\sigma^2$ is the upper bound for the variance of the stochastic estimator on regular clients and $b$ is the batchsize. In contrast, our results have only decreasing terms in the upper bounds when the data is homogeneous.

Coordinate-wise trimmed mean satisfies Definition 1.1.

We have added this remark to the paper.

Bucketing (Karimireddy et al., 2021) is known to amplify the Byzantine fraction, and this may be problematic when considering partial participation.

Indeed, Bucketing amplifies the fraction of Byzantine workers, and the generalization of our results to different types of robust aggregation rules and formalisms (e.g., the ones presented by Allouah et al. (2023)) is a very promising research direction. However, we want to highlight here that our results for Byz-VR-MARINA-PP are valid for the same range of $\delta$ (fraction of Byzantine workers) as the results for Byz-VR-MARINA (without partial participation). From this perspective, the usage of Bucketing is not problematic for our method.

Justification of Assumption 1.

Aggregation rules such as Krum and geometric median (GM) satisfy Assumption 1. Indeed, since Krum returns one of the input points, the inequality from Assumption 1 holds. Next, since the geometric median belongs to a convex hull of the inputs, Assumption 1 holds as well. Since Bucketing is applied to the averages computed for each bucket and the norm is a convex function, the composition of Bucketing with Krum/GM satisfies Assumption 1.

However, coordinate-wise aggregators such as coordinate-wise median (CM) or coordinate-wise trimmed mean (CTM) do not necessarily meet Assumption 1 from the original version of our submission. To fix this issue, we modify Assumption 1 by introducing a multiplicative factor $F_{\mathcal{A}}$ in the right-hand side of the inequality. For CM (and Bucketing $\circ$ CM) and CTM $F_{\mathcal{A}} = \sqrt{d}$ and for Bucketing $\circ$ Krum/GM $F_{\mathcal{A}} = 1$. We have applied all the necessary changes to the paper.

---

References:

[1] Tyurin, A., & Richtárik, P. (2022). A computation and communication efficient method for distributed nonconvex problems in the partial participation setting. arXiv preprint arXiv:2205.15580.

[2] Rammal, A., Gruntkowska, K., Fedin, N., Gorbunov, E., & Richtárik, P. (2023). Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates. arXiv preprint arXiv:2310.09804.

Numerical experiments.

Following the reviewers’ requests, we have conducted preliminary experiments with the proposed method. We kindly refer to our general response and the revised manuscript.

The choice of the clipping level.

We agree with the reviewer that the smoothness constants can be hard to estimate, and our work leaves an important open problem of how to avoid such a dependence in theory for future research. However, as our experiments show, Byz-VR-MARINA-PP does not significantly depend on parameter $\alpha$, if $\lambda_{k+1} = \alpha\|\| x^{k+1} - x^k \|\|$.

Non-vanishing term in (6).

This term is indeed not tight, as well as in the existing result for Byz-VR-MARINA. However, even the case of $\zeta = 0$ is important for Byzantine-robust literature, especially for collaborative learning applications when the data is open. We also have more general results under Assumption 9 in Appendix B, allowing a special type of heterogeneity that leads to the convergence to any predefined accuracy after a sufficiently large number of steps.

One possible way of improving this term is to apply our clipping idea to the Byzantine-robust version of DASHA-PP-PAGE from [1]. This algorithmic change should lead to the improvement of the non-vanishing term in (6), which was observed in a very recent preprint [2] in the context of full participation.

We also want to emphasize that the main novelty of this paper is in the usage of gradient clipping to handle the Byzantine workers in the case of partial participation. Clipping was used to construct robust aggregation by Karimireddy et al. (2021), but it was never used in the way we apply it. We believe our work is an important step towards building more efficient Byzantine-robust methods supporting partial participation. Moreover, in our experiments, we still observe the acceleration of the training due to partial participation.

Several quantities are undefined before they appear.

We thank the reviewer for spotting these minor issues. We have fixed them in the revised version.

Initialization of $g^k$.

From the theoretical analysis perspective, one can take any $g^0$ and just follow the pseudocode given in Algorithm 1. In practice, one can take $g^0 = 0$, $c_0 = 1$, and then follow Algorithm 1 from $k = 1$.

Binomial coefficient.

We thank the reviewer for spotting this minor issue. We have fixed it in the revised version.

The last sentence in Section 2.

We wanted to say that the clipping operation can be applied on the server side since the server needs to check that all norms of the received vectors are smaller than $\lambda_{k+1}$. We have made this sentence clearer.

We thank Reviewer Axn5 for engaging in the discussion with us.

Full participation at some rounds

The need for full participation with some (small) probability is indeed a limitation of our method, though this limitation is not very strong (it is not a limitation in the setup with client sampling) and is needed mostly to make the analysis easier. The main reason why Byz-VR-MARINA-PP requires full participation during a small fraction of randomly chosen rounds is in the estimator construction: it is inspired by and based on the Geom-SARAH/PAGE estimator that also uses a full gradient computation with some probability to reset the variance-reduced estimator and control the variance. We apply a similar mechanism to control the variance coming from the sampling of clients. Avoiding full participation is an important direction for future research that we plan to work on. One possible way is to adopt the technique from the recent work [1], where the authors develop a method improving upon MARINA-PP. The key idea in their paper is to use the momentum-based variance reduction for controlling the variance coming from compression and partial participation. This helps to avoid full participation as well as uncompressed vector communication.

We also want to emphasize that the main novelty of this paper is in the usage of gradient clipping to handle the Byzantine workers in the case of partial participation. Clipping was used to construct robust aggregation by Karimireddy et al. (2021), but it was never used in the way we apply it. Moreover, a noticeable part of the literature on partial participation of clients considers the client sampling model. The majority of samplings considered in the literature including the only existing work on Byzantine-robustness and partial participation (e.g., see the references on page 3) are sampling from the whole set of clients such that the probability of sampling each client is strictly positive. This means that all of these works implicitly require the availability of all clients at any time. We agree that this assumption does not always hold in practice, but we point out that this assumption is often used in papers focusing on theory. We believe our work is an important step towards building more efficient Byzantine-robust methods supporting partial participation. Our work opens a prominent direction for future research: one can apply clipping to the methods from [1] and to ClientMomentum by Karimireddy et al. (2021) to achieve Byzantine-robustness with partial participation.

Moreover, in our experiments, despite all the drawbacks and limitations of the proposed method, we observe a noticeable acceleration of the training due to partial participation for the proposed method.

Numerical experiments

We plan to add additional evaluation on different tasks but given the time constraints, we managed to finish the experiments with logistic regression only. The main contributions of our paper are purely theoretical and algorithmic. In particular, we obtained the first rigorous results with provable convergence even when Byzantines form majority at some rounds and we the key idea that we proposed and that was never considered before is to use clipping in the context of Byzantine-robust learning with partial participation.

We are currently running extra experiments with different attacks to illustrate that Byz-VR-MARINA-PP efficiently tolerates all kinds of Byzantine attacks. We also want to emphasize that other methods cannot withstand the considered attack since when Byzantines form the majority, they can arbitrarily damage the convergence.

Acceleration observation (Figure 1)

The current analysis does not provide benefits of partial participation -- this is a very standard situation for the analysis of methods with client sampling in the worst case. However, when workers have similar or even identical data, the optimal number of participating clients can be smaller since the estimator becomes quite tight and increasing the batchsize does not lead to noticeable improvements.

Heterogeneous settings

The case of heterogeneous data is very important, but we want to emphasize that under heterogeneity, any predefined accuracy of the solution cannot be achieved due to the lower bound from (Karimireddy et al., 2022). Due to these reasons, homogeneous setup is still quite popular in Byzantine-robust learning.

SOTA results

When data is homogeneous, the results are SOTA. The neighborhood factor can be improved when the data is heterogeneous -- and we explained how in our rebuttal. We will modify this claim to make it more accurate.

---

References:

[1] Tyurin, A., & Richtárik, P. (2022). A computation and communication efficient method for distributed nonconvex problems in the partial participation setting. arXiv preprint arXiv:2205.15580.

Numerical experiments.

Following the reviewers’ requests, we have conducted preliminary experiments with the proposed method. We kindly refer to our general response and the revised manuscript.

In the algorithm, it is said that the clipping levels $\lambda_k$ are given as inputs, how is it possible since they depend on the value of $x^{k+1}$ and $x^k$?

We thank the reviewer for the comment. To avoid any confusion, we reformulated the algorithm’s description: we need coefficients $\alpha_k$ as inputs and define $\lambda_{k+1} = \alpha_{k+1} \|\| x^{k+1} - x^k \|\|$. In Theorem 3.1, we use $\alpha_k = 2\max_{i \in \mathcal{G}} L_i$ and, in Theorem 3.2, $h_k$ is chosen as $\alpha_k = D_Q \max_{i,j} L_{i,j}$. Although theoretical values of coefficients $\alpha_k$ depend on the smoothness constants, the algorithm’s behavior is quite robust to the choice of $\alpha_k$ as our experiments show.

How are the gradients clipped at the first iteration since $\lambda_0$ is not defined?

We notice that during the first step, the sampled workers first do a step and get $x^{1}$ (line 7), and only then apply clipping (if $c_k = 0$) in line 8 using $\lambda_1 \sim \|\| x^1 - x^0 \|\|$. From the theoretical analysis perspective, one can take any $g^0$ and just follow the pseudocode given in Algorithm 1. In practice, one can take $g^0 = 0$, $c_0 = 1$, and then follow Algorithm 1 from $k = 1$.

Can the authors explain why full participation Is needed in some rounds? Would it be possible to avoid full participation and use only partial participation in each round?

We thank the reviewer for an excellent question. The main reason why Byz-VR-MARINA-PP requires full participation during a small fraction of randomly chosen rounds is in the estimator construction: it is inspired by and based on the Geom-SARAH/PAGE estimator that also uses a full gradient computation with some probability to reset the variance-reduced estimator and control the variance. We apply a similar mechanism to control the variance coming from the sampling of clients. Avoiding full participation is an important direction for future research that we plan to work on. One possible way is to adopt the technique from the recent work [1], where the authors develop a method improving upon MARINA-PP. The key idea in their paper is to use the momentum-based variance reduction for controlling the variance coming from compression and partial participation. This helps to avoid full participation as well as uncompressed vector communication.

We also want to emphasize that the main novelty of this paper is in the usage of gradient clipping to handle the Byzantine workers in the case of partial participation. Clipping was used to construct robust aggregation by Karimireddy et al. (2021), but it was never used in the way we apply it. We believe our work is an important step towards building more efficient Byzantine-robust methods supporting partial participation. Moreover, in our experiments, we still observe the acceleration of the training due to partial participation.

---

References:

[1] Tyurin, A., & Richtárik, P. (2022). A computation and communication efficient method for distributed nonconvex problems in the partial participation setting. arXiv preprint arXiv:2205.15580.