PaperlayerView exact revision on arXiv

Source-linked AI summary

Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing

Sai Praneeth Karimireddy, Lie He, Martin Jaggi

arXiv:2006.09365v6cs.LGstat.ML

TL;DR

Byzantine-robust federated learning typically assumes identical worker data, leaving heterogeneous settings vulnerable to attacks and aggregation failures. The paper introduces bucketing to augment robust aggregators, and combines it with worker momentum for theoretical and experimental guarantees. It establishes convergence results under heterogeneous data, while identifying conditions where exact convergence is impossible or recoverable.

  • Problem

    Existing Byzantine aggregation rules assume identical worker data, but heterogeneous workers are realistic and can cause failures even without Byzantine adversaries.

  • Method

    The paper adds a bucketing step before robust aggregation, formalizes robust aggregators, and combines them with worker momentum.

  • Results

    The approach is theoretically and experimentally effective against challenging attacks and establishes convergence to the optimum for heterogeneous Byzantine robust optimization under supported conditions.

  • Takeaways & Limitations

    Bucketing makes methods such as KRUM, coordinate-wise median, and geometric median provably robust aggregators for heterogeneous workers.

  • Takeaways & Limitations

    A lower bound shows that exact convergence may be impossible under heterogeneity, while CCLIP additionally requires a clipping radius depending on heterogeneity.

Abstract

from arXiv · show

In Byzantine robust distributed or federated learning, a central server wants to train a machine learning model over data distributed across multiple workers. However, a fraction of these workers may deviate from the prescribed algorithm and send arbitrary messages. While this problem has received significant attention recently, most current defenses assume that the workers have identical data. For realistic cases when the data across workers are heterogeneous (non-iid), we design new attacks which circumvent current defenses, leading to significant loss of performance. We then propose a simple bucketing scheme that adapts existing robust algorithms to heterogeneous datasets at a negligible computational cost. We also theoretically and experimentally validate our approach, showing that combining bucketing with existing robust algorithms is effective against challenging attacks. Our work is the first to establish guaranteed convergence for the non-iid Byzantine robust problem under realistic assumptions.

1 INTRODUCTION

Federated learning decentralizes model training across workers without transmitting their data, but Byzantine workers can send arbitrary messages. Existing defenses largely assume identical data, so this paper studies heterogeneous workers and proposes bucketing with robust aggregation.

  • 1 INTRODUCTION: Federated learning trains one model across distributed workers without directly transmitting their training data.Byzantine workers may instead send arbitrary messages, motivating robust aggregation rules.
  • 1 INTRODUCTION: Most current Byzantine defenses assume identical worker data distributions, despite heterogeneity being inherent in federated learning.The paper reports that existing rules can fail catastrophically under realistic heterogeneous settings.
  • 1 INTRODUCTION: Existing aggregation rules can fail to converge on heterogeneous data even when no Byzantine adversaries are present.The paper also introduces mimic, an attack that exploits heterogeneity and circumvents median-based defenses.
  • 1 INTRODUCTION: Bucketing is proposed as a preprocessing step that augments existing robust aggregation rules for heterogeneous workers.The paper formalizes robust aggregators and analyzes methods including KRUM, coordinate-wise median, and geometric median.
  • 1 INTRODUCTION: The analysis combines robust aggregation with worker momentum, while showing that heterogeneity can prevent exact convergence in general.Exact convergence is recovered when heterogeneity is mild or the model is overparameterized; the robustness level δ trades off attack tolerance against convergence speed.

2 RELATED WORK

Prior work primarily develops Byzantine defenses and attacks for iid worker data, while non-iid defenses remain comparatively under-examined. The paper situates its approach alongside clustering, centralized-data, and growth-condition analyses.

  • IID defenses: IID Byzantine defenses include KRUM, coordinate-wise median, approximate geometric median, and sign-based majority aggregation.These methods were developed for settings in which workers have identical data distributions.
  • IID vs. Non-IID attacks: IID attacks such as time-coupled attacks add small consistent biases that accumulate over time and can cause divergence.The paper instead focuses on attacks and defenses tailored to non-iid data.
  • Non-IID defenses: Non-iid defenses remain relatively under-examined, with prior approaches including outlier-robust clustering and settings where the server possesses the full training dataset.Hierarchical vote-group aggregation is noted as similar to bucketing, although its results are limited in the cited discussion.
  • Growth conditions: The paper uses the stronger growth condition, which bounds worker-gradient deviations by the squared norm of the global gradient.For smooth functions it implies the weak growth condition, while extending results to the weak condition remains open.

3 ATTACKS AGAINST EXISTING AGGREGATION SCHEMES

Heterogeneous worker data makes standard aggregation schemes vulnerable even without Byzantine workers, and enables mimic attacks that amplify perceived imbalance. Experiments show substantial degradation under these conditions.

  • 3.1 FAILURE ON IMBALANCED DATA WITHOUT BYZANTINE WORKERS: Existing aggregation schemes can fail on heterogeneous data because no single worker gradient represents the whole dataset.KRUM, coordinate-wise median, and robust federated averaging rely on worker-update relationships that become misleading under imbalance.
  • 3.1 FAILURE ON IMBALANCED DATA WITHOUT BYZANTINE WORKERS: When 2n + 1 workers alternate between -1 and +1, the true mean is approximately 0, but KRUM, CM, and RFA output either -1 or +1.The example illustrates how aggregation can select a locally representative value instead of the global mean.
  • 3.1 FAILURE ON IMBALANCED DATA WITHOUT BYZANTINE WORKERS: With n=20 and δ=0 on imbalanced MNIST, KRUM, CM, and RFA attain less than 90% accuracy in the non-iid case.They match ideal iid SGD performance but learn only the top 2–3 classes in the imbalanced setting.
  • 3.1 FAILURE ON IMBALANCED DATA WITHOUT BYZANTINE WORKERS: Increasing batch size does not remove the performance drop when worker data is non-iid, unlike the corresponding iid setting.The passage reports that CCLIP maintains performance in both iid and non-iid settings.
  • MIMIC ATTACK: The mimic attack copies a good worker’s output, consistently overemphasizing that worker while remaining indistinguishable from a genuine update.It therefore targets the non-iid structure rather than relying on visibly anomalous Byzantine messages.
  • MIMIC ATTACK: Under mimic attack with n=25 and |B|=5, robust aggregators retain iid performance but suffer in the non-iid setting, with KRUM and CM performing worst.RFA performs slightly better, while the passage states that all are worse than simple averaging.

4 CONSTRUCTING AN AGNOSTIC ROBUST AGGREGATOR USING BUCKETING

Bucketing makes heterogeneous worker updates more homogeneous before aggregation, allowing existing Byzantine-robust rules to satisfy an agnostic robustness guarantee. The resulting error is information-theoretically optimal, although coordinate-wise median retains a dimension-dependent limitation.

  • Motivation: Mixing workers across buckets reduces the chance that an aggregation rule consistently ignores a subset of the data.This addresses the failure mechanism identified for existing methods in heterogeneous settings.
  • Bucketing algorithm: Bucketing randomly partitions inputs into buckets, averages each bucket, and feeds the resulting values to an existing aggregation rule.The averaged bucket outputs have lower pairwise variance than the original inputs.
  • Bucketing properties: Bucketing reduces pairwise variance by s while potentially increasing the Byzantine fraction by a factor of s, creating a variance-versus-adversarial-influence trade-off.With s = 1, bucketing only shuffles the inputs.
  • Guarantees: Krum, geometric median, and coordinate-wise median become agnostic Byzantine-robust aggregators after bucketing, tolerating δmax < 1/4, δmax < 1/2, and δmax < 1/2, respectively.Their expected errors are O(δρ2), O(δρ2), and O(dδρ2), respectively.
  • Guarantees: The bucketing-based error O(δρ2) is information-theoretically optimal, unlike previous analyses with error O(ρ2).The agnostic guarantee does not require knowing ρ2; it only requires δ.
  • Limitations: Coordinate-wise median has error depending on dimension d, which is problematic when d ≫n.The paper reports that geometric median often outperforms Krum, while coordinate-wise median can outperform Krum in practice.

5 ROBUST NON-IID OPTIMIZATION USING A ROBUST AGGREGATOR

The paper analyzes Byzantine-robust optimization with heterogeneous worker data, showing both fundamental limits and conditions under which bucketing and robust aggregation recover convergence. Worker momentum reduces stochastic-gradient variance, while mild heterogeneity or overparameterization can enable convergence to the exact optimum.

  • Problem setting: Data heterogeneity makes Byzantine-robust optimization especially challenging, motivating lower bounds and convergence analysis for robust aggregators.The section studies optimization with heterogeneous workers and arbitrary Byzantine behavior using aggregators satisfying the paper’s robust-aggregation definition.
  • Algorithm description: Worker momentum replaces stochastic gradients with momentum vectors before robust aggregation, reducing within-worker variance while leaving cross-worker heterogeneity.Momentum averages over approximately 1/(1−β) independent stochastic gradients, but the resulting worker vectors remain heterogeneous.
  • Convergence rates: The unified analysis establishes convergence guarantees for bucketing combined with robust aggregators, including KRUM, RFA, and coordinate-wise median.Theorem II provides a common analysis in iid and non-iid settings, while prior methods lacked most end-to-end convergence guarantees.
  • Convergence rates: When δ → 0, the rate recovers the optimal O(σ√(T/n)) non-convex SGD rate and achieves linear speed-up with respect to n workers.The cited comparison also notes that prior non-iid algorithms do not improve their rates as the Byzantine fraction decreases.
  • Lower bounds and the challenge of heterogeneity: When δ > 0 and ζ > 0, convergence is generally only to a radius O(δζ) around the optimum, matching an information-theoretic lower bound.Thus, exact convergence is not generally possible under simultaneous Byzantine corruption and heterogeneous worker objectives.
  • Circumventing lower bounds using overparameterization: Under mild heterogeneity or sufficient overparameterization, the method can circumvent the lower bound and converge to the exact optimum, matching the optimal iid rate.The stronger assumption requires worker gradients to agree at the optimum and is described as typically holding in sufficiently overparameterized models.

6 EXPERIMENTS

The experiments evaluate Byzantine-robust aggregation on heterogeneous MNIST under multiple attacks, using bucketing, momentum, and varied data distributions. Across these settings, bucketing generally improves aggregator performance, with mild bucketing often sufficient.

  • Experimental setup: The experiments train an MLP on heterogeneous MNIST, distributing label-sorted data among good workers while Byzantine workers access the full dataset.Implementations use PyTorch; setup and runtime details are deferred to the appendix.
  • Attacks and defenses: The study evaluates bit flipping, label flipping, mimic, IPM, and ALIE attacks against KRUM, CM, CCLIP, and RFA.IPM and ALIE exploit variance among workers and are reported to be stronger in non-iid settings.
  • Main findings: Bucketing improves the performance of almost all aggregators under all tested attacks.Worker momentum and bucketing reduce gradient variance, whereas momentum alone is not sufficient in the reported comparisons.
  • Bucketing hyperparameters: Mild bucketing with s = 2 improves performance, while increasing s gives faster convergence for CCLIP on the IPM-attacked heterogeneous MNIST task.The same s = 2 setting remains effective as the Byzantine fraction q approaches 25%.
  • Dataset construction: Long-tailness is created by exponentially decreasing class proportions, with α = 1/γ^9 measuring the largest-to-smallest class ratio.For γ = 1, α = 1; for γ = 0.5, α = 512.

A.1.3 SETUP FOR EACH EXPERIMENT

The appendix specifies experiment-specific hyperparameters, attack strengths, runtime reporting, and the default MNIST settings used throughout the evaluations.

  • Experiment settings: Table 6 lists the setup and hyperparameters for each experiment.The appendix separately specifies the IPM and ALIE attack settings used in Figure 1 and Figure 2.
  • Attack parameters: The IPM attack uses strength ϵ = 0.1 in Figures 1 and 2.The ALIE parameter z is computed according to Baruch et al. (2019), with z ≈ 0.25 in this setup.
  • Implementation environment: The appendix summarizes the running environment in Table 7.Default experimental settings for MNIST are listed in Table 5.

A.2.1 CLIPPING RADIUS SCALING

This section studies how momentum changes gradient norms and how CCLIP’s clipping radius should be scaled, alongside bucketing, overparameterization, and resampling effects.

  • Gradient norms: Because momentum increases gradient norms, CCLIP’s clipping radius should increase accordingly.The radius depends on the norm of good gradients, and Figure 3 compares norms with and without momentum under different attacks.
  • Overparameterization: Overparameterized models decrease training loss faster and retain smaller training loss despite Byzantine workers.The underlying base aggregator for the corresponding heterogeneity analysis is RFA.
  • Heterogeneity bound: Increasing overparameterization decreases the heterogeneity bound B2, supporting exact convergence when the model is sufficiently overparameterized.The result is presented as empirical support for the theory in Section 5.4.
  • Resampling: Bucketing with resampling has almost the same convergence rate as bucketing by gradient repetition, while reducing the number of input gradients and computational complexity.Figure 8 evaluates convergence under different attacks using RFA as the underlying aggregator.

B IMPLEMENTING THE MIMIC ATTACK

The mimic attack identifies a high-variance direction and has Byzantine workers imitate a fixed good worker, making the attack difficult to detect while increasing data imbalance. Supporting lemmas characterize the effect of bucketing on good outputs.

  • Direction estimation: An initial phase of approximately one epoch estimates the maximum-variance direction before the attack is implemented online.The direction is computed using a streaming procedure corresponding to Oja’s top-eigenvector method.
  • Illustrative comparison: In the random-vector example, RFA performs slightly better than CM and KRUM, but all three have higher error than simple averaging.This comparison holds across the reported settings of Byzantine fraction δ and variance ρ.
  • Attack construction: The mimic attack has Byzantine workers copy a fixed good worker’s vector, allowing them to evade filtering while increasing data imbalance.The construction uses independent Rademacher inputs with mean 0 and variance ρ^2 = d.
  • Good buckets: After s-bucketing, at least m(1−δs) outputs are composed only of good vectors.Here m = ⌈n/s⌉, so the fraction of potentially Byzantine-influenced buckets scales with δs.
  • Bucketing effect: Good bucket outputs preserve the mean and satisfy E∥y_i−y_j∥ ≤ ρ^2/s for fixed good buckets.The corresponding lemma also states E[y_i] = E[x̄] and bounds each good bucket’s variance by ρ^2/s.
  • Assumptions and limits: Under standard second-moment stochastic assumptions, the lower-bound analysis uses m = ⌈n/s⌉ and ρ̃^2 = ρ^2/s.The passage notes that stronger higher-moment noise assumptions could tighten the lemma, but they are not used here.

C.2 PROOFS OF ROBUSTNESS

Bucketing makes KRUM, geometric median, and coordinate-wise median robust aggregators for heterogeneous data, with explicit breakdown points and error bounds. The KRUM analysis avoids an extra factor of m by accepting a smaller breakdown point.

  • The KRUM proof avoids an extra factor of m by using an alternate analysis with breakdown point δmax = 1/4.The difficulty arises because KRUM’s selected worker depends on sampling, so fixed-worker variance bounds do not directly apply.
  • Bucketing converts KRUM into a robust aggregator with δmax = 1/4 − ν and c = 4/(3ν(1/4−ν)).
  • Bucketing makes geometric median robust with δmax = 1/2 − ν and c = 1/(ν(1/2−ν)), giving better theoretical performance than KRUM.
  • Bucketing makes coordinate-wise median robust with δmax = 1/2 − ν and c = d/(ν(1/2−ν)).The analysis treats each coordinate as a separate scalar geometric-median problem.

D LOWER BOUNDS ON NON-IID DATA (PROOF OF THEOREM III)

The lower-bound construction uses two heterogeneous optimization problems that produce indistinguishable worker-function sets despite different good-worker identities. Consequently, any algorithm must incur error on at least one problem, so exact optimization is generally unattainable under heterogeneity.

  • With a δ-fraction of Byzantine workers, no algorithm can distinguish the two constructed problems.
  • The construction can have gradient heterogeneity of 0 while Byzantine attackers imitate workers associated with the alternative function family.
  • Two function families can have different optima while inducing exactly the same set of worker functions, making them indistinguishable to the algorithm.The good-worker identities differ between the two constructions, but the algorithm does not observe those identities.
  • Because the algorithm has the same output on both indistinguishable problems, it makes a large error on at least one of their different optima.

E CONVERGENCE OF ROBUST OPTIMIZATION ON NON-IID DATA (THEOREMS II AND IV)

The convergence analysis combines a robust aggregator satisfying Definition A with worker momentum under smooth, possibly non-convex local objectives and stochastic-gradient assumptions. It also identifies adaptive aggregation as an open issue because the robustness parameter ρ² is not directly known to the aggregator.

  • Theorem V assumes a (δmax, c)-ARAGG, at least n(1−δ) faithful workers, L-Lipschitz gradients, and independent unbiased stochastic gradients.
  • The condition δ ≤ 1/(60cB²) need not impose an extra strict practical constraint because B² can be decreased while ζ² is increased over a sufficiently large domain.
  • The convergence proof combines descent and momentum-error bounds with the aggregation-error lemma for the robust optimization update.
  • A major caveat is that ρ² depends on E∥∇f(x^{k−1})∥², which the robust aggregation rule cannot access; provably adaptive clipping remains open.
  • The analysis separates intra-worker gradient variance σ² from inter-client variance ζ², with worker momentum addressing the former and heterogeneity remaining the main challenge.
Loading 2006.09365v6…