Adaptive Gradient Clipping for Robust Federated Learning

We thank Reviewer n1Gk for the comments, which we discuss below.

Comparison With Static Clipping

We appreciate the reviewer’s insight into the importance of a direct comparison between ARC and static clipping methods. However, we believe there may be a minor misunderstanding, as we have indeed included an extensive comparison with static clipping in Appendix F (referenced in line 256, Section 3). In this section, we perform experiments using Robust-DSGD on MNIST, evaluating the performance of static clipping across different settings and comparing it with ARC. Specifically, we tested a range of clipping values $C \in$ {0.02, 0.2, 2, 20}, covering various heterogeneity levels.

Our findings indicate that no single static clipping value consistently yields robust performance across diverse scenarios, largely due to the inherent sensitivity of static clipping to factors like data heterogeneity and the nature of Byzantine attacks. Since the server cannot directly access data or a priori determine the attack executed by Byzantine workers, tuning $C$ optimally for static clipping becomes infeasible. This highlights the necessity of a robust, adaptive clipping mechanism like ARC that naturally adjusts to these conditions. In contrast, ARC consistently adapts to different heterogeneity levels and adversarial settings, providing robust performance without the need for parameter tuning.

In addition to the results presented on MNIST, we have also conducted further empirical tests on Fashion-MNIST and CIFAR-10, which support the same observations. Although these results were omitted from the paper, we would be happy to provide them in Appendix G of the revised paper, demonstrating that ARC consistently outperforms static clipping across datasets and conditions. Additionally, for the final version of the paper, we intend to move some key results from Appendix F to the main body to also showcase ARC’s advantages over static clipping.

Large-scale experiments

We acknowledge the reviewer’s point regarding network size and appreciate the suggestion to evaluate ARC’s performance with a greater number of agents. While we used 10 honest workers on MNIST to simulate extreme heterogeneity by assigning each worker a single label, we agree that expanding our study to larger networks would enhance the practical relevance of our results. Preliminary experiments with 30 honest workers on MNIST (tripling the initial system size) affirm ARC’s consistent empirical advantages even in larger setups. We are currently running additional experiments in this setting, and will make these results available shortly in Appendix G of the revised paper. Regarding CIFAR-10, we chose a network of 17 workers to create a system larger than what we had for MNIST, as suggested. However, we are constrained by the significant computational resources required for these experiments, which limits our ability to expand further. We hope the reviewer can appreciate this trade-off, as CIFAR-10’s computational demands are high, and we aimed to balance system size with experimental feasibility.

On the Overhead of ARC

ARC’s complexity is $\mathcal{O}(nd + n\log(n))$(see Appendix A), with $n$ as the number of workers and $d$ as the model dimension. While it is true that ARC incurs a linear dependence on $d$, it is worth noting that this is unavoidable, as all robust aggregation methods must process gradients across model dimensions. Thus, ARC’s linear dependence on $d$ is a fundamental requirement shared across robust aggregations. What is particularly critical to consider, however, is the dependence on $n$, the number of workers, as this truly distinguishes between efficient and costly aggregation methods, especially in the context of scaling to large language models. ARC’s complexity in terms of $n$ remains modest whereas more costly aggregation schemes like Nearest Neighbor Mixing (NNM), which is crucial in high heterogeneity, exhibit $\mathcal{O}(dn^2)$ complexity. In distributed ML scenarios where $n$ is large, this difference in $n$-scaling makes ARC a comparatively efficient choice. However, we recognize the value of further efficiency improvements and agree that developing a more computationally efficient adaptive clipping mechanism that retains ARC’s resilience could be an interesting avenue for future research. We will make this clear in the paper and we thank the reviewer for pointing this out.

On ARC Clipping Aggressively

We thank the reviewer for this interesting question. As explained above, the clipping threshold depends on the number of tolerated Byzantine workers $f$. By construction, therefore, the clipping applied by ARC depends on the threat under consideration. If the number of Byzantine workers is small, then ARC will clip only a small portion of the gradients; on the contrary, if the number of Byzantine workers $f$ is large, ARC clips more gradients to limit the impact of malicious vectors while ensuring that at least one honest gradient will remain unclipped (see Lemma B.1).

Loss Example where $B$ is Small

Indeed, there is no guarantee of convergence if $\kappa B^2 \geq 1$. In Figure 3 of Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity (Allouah et al., page 9), the authors trained a logistic regression model on MNIST and showed that the associated error (taking into account $G$ and $B$) is small, while empirically guaranteeing that $\kappa B^2 < 1$. In this case, the loss function used was the Negative Log Likelihood loss.

We thank Reviewer Ap5T for the comments, which we discuss below.

Small Static Clipping Threshold

We appreciate the reviewer’s recommendation to examine the impact of larger static clipping thresholds. In fact, we already tested a broad range of clipping values in our experiments to provide a robust comparison between ARC and static clipping methods. Appendix F presents the results of this comparison, which spans several static clipping parameters (from $0.2$ to $20$) across different levels of heterogeneity, numbers of Byzantine workers, and Byzantine attacks. As our results indicate, no static clipping threshold provides consistent robustness across various heterogeneity levels and Byzantine attack scenarios. By contrast, ARC’s adaptive mechanism enables it to consistently adjust to these changing conditions, delivering stable performance. For further details, please refer to our response to Reviewer n1Gk.

Additionally, we highlight ARC’s adaptivity in Figure 19, where we plot the evolving adaptive clipping parameter over time under the same conditions as those in our static clipping experiments. This demonstrates ARC’s ability to dynamically adjust its threshold in response to ongoing training conditions.

Influence of Model Initialization

We believe the reviewer may have overlooked our analysis of model initialization on ARC's performance, which is presented in Figure 2b of the Introduction and Figure 6 in Section 5.2. In these experiments, we assess the impact of progressively worse initialization conditions on ARC-enhanced Robust-DSGD for MNIST with 10 honest workers, under extreme heterogeneity and at $\alpha = 0.1$ with $f = 1$ adversarial worker. Beginning with well-chosen initial parameters, we scale them by a factor $\mu$ where increasing $\mu$ corresponds to worse initialization ($\mu \in \{1, ..., 5\}$). Our findings indicate that ARC significantly improves performance under good initialization ($\mu=1$), resulting in substantial gains in accuracy. As initialization degrades, ARC’s advantage over vanilla Robust-DSGD gradually diminishes. However, even under poor initialization ($\mu=5$), ARC still matches the performance of unmodified Robust-DSGD. Importantly, ARC’s behavior aligns closely with Byzantine-free DSGD (which also degrades in performance under unfavorable initialization conditions), while plain Robust-DSGD struggles to leverage well-initialized models effectively, maintaining lower accuracy around 20% in Figure 2b. This analysis underscores the positive influence of good initialization on ARC’s effectiveness and empirically supports our theoretical insights.

Intuition for the Design of ARC

We thank the reviewer for prompting a discussion on ARC’s design and clipping mechanism. Lemma B.1 in Appendix B shows that $\mathbf{F} \circ \mathbf{Clip}_C$ is $(f, \tilde \kappa)$-robust, provided that $\lvert S \setminus S_c\rvert \geq 1$ for all subsets $S$ of size $n - f$. Note that this condition is impossible to guarantee when using a fixed clipping threshold that does not depend on the given set of input vectors. In order to ensure that $\lvert S\setminus S_c\lvert \geq 1$ for all subsets $S$ of size $n-f$, the clipping threshold $C$ should be large enough such that less than $n - f$ input vectors are clipped. Accordingly, we propose to choose a clipping threshold such that the total number of clipped vectors is of the form $\lfloor \lambda (n-f) \rfloor$, where $\lambda < 1$. Note that it is natural to clip more vectors when the fraction of adversarial workers $\frac{f}{n}$ is large, to control the impact of Byzantine behavior. Therefore, we set $\lambda \coloneqq \zeta \frac{f}{n}$ where $0 \leq \zeta \leq 2$. Since $\frac{f}{n}<\frac{1}{2}$ and $\lambda < 1$, the number of clipped vectors $\lfloor \zeta \frac{f}{n} (n - f)\rfloor < n-f$ for all $\zeta \in [0, 2]$. This constitutes the underlying idea behind our adaptive clipping strategy ARC. Furthermore, note that our theory holds for all $\zeta \in [0, 2]$, but we observed empirically that $\zeta = 2$ provides ARC with the best performance. We thank the reviewer for this question. We will indeed include this discussion in the paper.

We thank Reviewer zvxn for the comments, which we discuss below.

On Combining ARC with NNM

We appreciate the reviewer’s suggestion to explore ARC’s performance independently of NNM. In the main paper, our experiments primarily highlight ARC’s improvement when paired with NNM, the state-of-the-art mixing algorithm for addressing heterogeneity in Byzantine ML. This choice is driven by prior findings showing that NNM significantly enhances the robustness of existing aggregations, especially under conditions of high data heterogeneity or a large proportion of Byzantine workers. Without NNM, robust aggregations such as CWTM or GM alone yield poor empirical results in high heterogeneity regimes, as demonstrated in prior work on NNM (see Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity (Allouah et al.)). Furthermore, in homogeneous settings where NNM is not required, ARC results in comparable or better empirical performance compared to vanilla robust aggregations without ARC. Additionally, we confirm that NNM was indeed used in Figure 6, and we will clarify this in the final version.

On CIFAR-10 and More Complex Datasets

In our CIFAR-10 evaluation, we used only one Byzantine worker among $n=17$, aiming to demonstrate that even a single adversarial worker ($f=1$, or under 6% of the system) can significantly degrade the learning when ARC is not used in Robust-DSGD. We agree that assessing ARC under a higher proportion of Byzantine workers would further underscore its practical value. We have already begun running additional experiments with more Byzantine workers, which so far confirm ARC’s robustness benefits under increased $f$ values. We will include these results in the revised version of the paper in Appendix G when they are finalized.

Regarding dataset complexity, our current evaluation leverages standard benchmarks in Byzantine ML: MNIST, Fashion-MNIST, and CIFAR-10. Although these datasets are less challenging in conventional ML, they introduce considerable difficulty under Byzantine settings, as confirmed by prior research (see Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity (Allouah et al.), Byzantine machine learning made easy by resilient averaging of momentums (Farhadkhani et al.),Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing (Karimireddy et al.)). Extending Byzantine ML evaluations to more complex datasets is a promising future direction, and we agree that it could further substantiate ARC’s applicability in practical, large-scale scenarios.

Performance of ARC in Homogeneous Settings Compared to Static Clipping

Thank you for raising the question about ARC’s performance under homogeneous conditions compared to static clipping. As detailed in Appendix F, we compared ARC with various static clipping strategies across three heterogeneity levels. Notably, in moderate heterogeneity in Figure 17 (corresponding to sampling from a Dirichlet distribution with parameter $\alpha = 1$) — the closest setting to homogeneity considered — ARC performs on par with the best static clipping strategies (e.g., $C = 2$ and $C = 20$) and outperforms others (e.g., $C = 0.2$ and $C = 0.02$). Additional experiments we conducted in completely homogeneous settings further support these observations, showing that ARC matches or exceeds the performance of the best static clipping strategies available. Thus, ARC remains effective even in low-heterogeneity environments, adapting well to homogeneous scenarios without compromising robustness.

On NNM's Importance for the Guarantees of Theorem 5.2

We thank the reviewer for this insightful question. NNM ensures that the robustness coefficient $\kappa \in \mathcal{O}(f/n)$ (more specifically, see Lemma 2.5), making it possible to induce an improvement when $f/n$ approaches the breakdown point. This improvement could not be demonstrated otherwise, i.e., if $\kappa$ is not proportional to $f/n$.

We thank Reviewer KAQT for the comments, which we discuss below. We would like to clarify the purpose of this theorem and address the specific points raised.

Purpose of Theorem 5.2

Theorem 5.2 aims to demonstrate the improvement induced by ARC over existing methods in strong adversarial regimes, specifically when the corruption fraction $\frac{f}{n}$ approaches the breakdown point (BP) of the system. In this extreme setting, ARC ensures that the error is strictly better than the lower bound, provided the norms of honest gradients are bounded at model initialization.

Addressing the Reviewer’s Concerns

The reviewer’s calculations are correct, but they do not fully consider the role of $\xi$, which measures how close the corruption fraction $\frac{f}{n}$ is to the BP. In Theorem 5.2, $\xi$ explicitly influences the final error bound $\upsilon\varepsilon_o$. Therefore, the lower bound of $\upsilon\varepsilon_o$ computed by the reviewer can be made arbitrarily small since it is proportional to $\xi$, by considering $f/n$ to be arbitrarily close to the BP. While $\rho^2$ can indeed be much larger than $\zeta^2$, this does not render the theorem meaningless. The large value of $\rho^2$ reflects the difficulty of maintaining robustness in extreme adversarial regimes. However, the proportionality of $\upsilon\varepsilon_o$ to $\xi$ ensures that the bound remains relevant. Specifically, as $\xi$ becomes small, the influence of $\rho^2$ diminishes relative to the overall bound. We refer the reviewer to Appendix C, specifically Theorem C.4 and Corollary C.5, for additional details on the convergence of Robust DGD with ARC. We hope that these additional results will make things clearer.

Proposed Revisions for Clarity

To address potential confusion and enhance the clarity of Theorem 5.2, we will include specific values for $v$ and $\xi_0$ in the final version of the paper. Indeed, we will consider a special case of the theorem by choosing $\xi_o = 0.5$. In this case, $\rho \coloneqq \exp\left( \frac{2 (2 + B^2)\Delta_o L}{G^2} \right) \zeta$. Furthermore, let $\boldsymbol{\upsilon} \leq \xi_o = 0.5$. Since, in this particular case, $\frac{\boldsymbol{\upsilon}}{\Psi(G, B, \rho)} \leq \xi_o$ (because $\Psi(G, B, \rho) \geq 1$), Theorem 5.2 implies that if $0 < \xi \leq \frac{1}{2}\frac{\boldsymbol{1}}{\Psi(G, B, \rho)}$ then $\mathbb{E} {\lVert \nabla \mathcal{L}_{\mathcal{H}} \hat{\left ( \theta \right)} \rVert}^2 \leq \boldsymbol{\frac{1}{2}} ~ \varepsilon_o < \varepsilon_o$. This special case focuses on the regime of small $\xi$, explicitly illustrating how $\upsilon\varepsilon_0$ (where $\upsilon = \frac{1}{2}$) improves over existing methods under these conditions. Additionally, we will emphasize that the strict improvement shown in Theorem 5.2 is particularly significant when $\frac{f}{n}$ is close to the BP, aligning with the theorem's primary objective.

Meaningfulness of Theorem 5.2.

We believe Theorem 5.2 presents an important result in Byzantine-robust distributed learning. The theorem shows that if the fraction of adversarial workers $f/n$ is close to the breakdown point then the lower bound on the learning error under $(G, B)$-gradient dissimilarity can be circumvented, provided that the honest workers' gradients at model initialization are bounded. This result opens up a new line of research of considering pragmatic distributed learning settings that avoid the worst-case scenarios in the presence of adversarial workers, thereby improving robustness guarantees.

Robustness Preservation by ARC

Yes, we agree that Theorem 3.2, which shows that ARC preserves $(f, 3 \kappa)$-robustness, is not sufficient for proving an improvement. Indeed, we show that ARC has an additional property shown in Lemma 5.1 (in Section 5), which in conjunction with Theorem 3.2, yields an improvement in the learning error characterized in Theorem 5.2.

We hope that the above properly addresses the reviewer's concerns. In which case, we expect the reviewer to raise the score of our paper.