PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning from History for Byzantine Robust Optimization

Sai Praneeth Karimireddy, Lie He, Martin Jaggi

arXiv:2012.10333v3cs.LGcs.DCmath.OCstat.ML

TL;DR

Existing Byzantine-robust aggregators can fail without attackers and can diverge under attacks coupled across time. The paper introduces iterative centered clipping and worker momentum to address these failures, with provable guarantees and experiments showing consistent superiority over baselines.

  • Problem

    Existing robust aggregation rules can fail to converge with i.i.d. data and no Byzantine attackers, while history-oblivious methods can diverge under time-coupled attacks.

  • Method

    The paper combines an iterative centered-clipping aggregator with worker momentum to handle distributional brittleness and time-coupled attacks.

  • Results

    The proposed strategies obtain provable robust convergence guarantees and consistently outperform all baselines across tested attacks and settings.

  • Takeaways & Limitations

    Centered clipping and worker momentum provide a simple, scalable strategy for Byzantine-robust stochastic optimization under the paper’s assumptions.

  • Takeaways & Limitations

    The guarantees assume a fixed Byzantine-worker subset; if different workers can be Byzantine each round, convergence is impossible under the stated lower bound.

Abstract

from arXiv · show

Byzantine robustness has received significant attention recently given its importance for distributed and federated learning. In spite of this, we identify severe flaws in existing algorithms even when the data across the participants is identically distributed. First, we show realistic examples where current state of the art robust aggregation rules fail to converge even in the absence of any Byzantine attackers. Secondly, we prove that even if the aggregation rules may succeed in limiting the influence of the attackers in a single round, the attackers can couple their attacks across time eventually leading to divergence. To address these issues, we present two surprisingly simple strategies: a new robust iterative clipping procedure, and incorporating worker momentum to overcome time-coupled attacks. This is the first provably robust method for the standard stochastic optimization setting. Our code is open sourced at https://github.com/epfml/byzantine-robust-optimizer.

1. Introduction

The paper identifies failures in Byzantine-robust aggregation under realistic stochastic settings and proposes iterative clipping and worker momentum to address distributional and time-coupled attacks.

  • Motivation: Existing robust aggregators can fail to converge even with i.i.d. data and no Byzantine attackers.The paper frames this as a brittleness problem in distributed and federated learning.
  • Motivation: History-oblivious aggregation rules can be forced to diverge when attackers couple small perturbations across multiple rounds.The perturbations can remain difficult to detect in individual noisy-gradient rounds while accumulating over time.
  • Approach: Iterative centered clipping provides a scalable robust aggregator requiring O(n) computation and communication per round.The method is also described as compatible with asynchronous updates and secure aggregation.
  • Approach: Worker momentum averages updates over time, reducing good-worker variance and exposing time-coupled perturbations.The paper states that its methods obtain optimal rates and that the theory clarifies momentum’s role in Byzantine resilience.
  • Setup: The paper formalizes robust non-convex stochastic optimization with a δ fraction of Byzantine workers and seeks a stationary point.Workers send messages to a server, which updates parameters across rounds.
  • Setup: The setup assumes smoothness and a lower-bounded objective, unbiased independent stochastic gradients with bounded variance, and a fixed Byzantine-worker subset.Byzantine workers may send arbitrary messages and are assumed omniscient.

2. Related work

Prior work largely replaces averaging with robust aggregation, while later attacks expose the need for defenses that use information across rounds and accommodate broader stochastic settings.

  • Robust aggregators: Common Byzantine-learning approaches replace averaging with coordinate-wise or geometric medians, majority voting, and related robust rules.These methods form the main aggregation-based line of prior work.
  • Robust aggregators: Reputation-based penalization and reweighting schemes require trusting workers to report correct statistics.Coding-theory approaches are discussed for settings with full control over workers, such as datacenters.
  • Time-coupled attacks and defenses: Recent attacks show that robust aggregation can be circumvented by coupling individually limited perturbations across rounds.The paper identifies defenses and guarantees against time-coupled attacks as a central concern.
  • Time-coupled attacks and defenses: Martingale-based prior methods achieve optimal Byzantine-robust rates for convex functions but do not directly apply to general non-convex functions.A subsequent extension handles non-convex objectives but assumes almost-surely bounded stochastic-gradient noise rather than only bounded variance.
  • Other concerns: Data heterogeneity is an important deployment concern because methods assuming i.i.d. worker data may fail in federated learning.The related work surveys variations designed to handle non-i.i.d. data with differing success.

3. Brittleness of existing aggregation rules

The paper shows that popular middle-seeking aggregators can fail under multimodal or skewed stochastic noise, including without Byzantine workers, because they discard informative distributional tails.

  • Brittleness of existing aggregation rules: Most state-of-the-art aggregators require strong, unrealistic restrictions on the noise distribution and can fail without Byzantine workers.The section presents counterexamples where robust aggregation fails despite the absence of adversarial behavior.
  • Practical implications: Middle-seeking rules such as Krum, coordinate-wise median, RFA, and Bulyan tend to discard tail gradients as outliers under non-unimodal noise.Their use is therefore sensitive to multimodal, heavy-tailed, or otherwise insufficiently concentrated gradient distributions.
  • Bimodal noise: Krum, coordinate-wise median, and Bulyan return either +1 or −1 for odd samples from symmetric bimodal ±1 noise, even with infinite samples and no corruptions.This counterexample demonstrates fragility to bimodal noise.
  • Heavy-tailed noise: A skewed power-law distribution has mean 1.5 but median 21/3 ≈1.26, so median-based rules can miss the true optimum even with infinite samples.The passage links this issue to imbalanced distributions and reports that heavy-tailed distributions occur in deep learning.
  • Failure theorem: Coordinate-wise median, RFA, and Krum may fail to reach the optimum almost surely even when traditional distributed SGD converges.Theorem I states that this occurs in simple convex stochastic settings with bounded variance, for any number of workers and no Byzantine workers.

4. Necessity of using history

The paper shows that history-free robust aggregation can fail fundamentally: permutation-invariant methods may not converge, while time-coupled attacks can accumulate hidden perturbations across rounds.

  • Limits of history-free methods: Any aggregation rule oblivious to the past can retain non-zero error after infinite time and fail to converge to the optimum.The attack hides small perturbations within stochastic-gradient noise, allowing them to accumulate across rounds.
  • Permutation invariance: Permutation-invariant algorithms remain unchanged when worker gradients are permuted independently across rounds.Memoryless methods are necessarily permutation invariant because worker indices carry no information without tracking history.
  • Lower bound: Theorem II constructs strongly-convex instances where permutation-invariant algorithms necessarily incur error after t rounds.The theorem applies when δn ≥ 4(1 + log t).
  • Implications for existing rules: Coordinate-wise median, trimmed mean, Krum, Bulyan, RFA, and geometric median are permutation invariant and therefore fail to converge under the theorem’s conditions.As strong convexity decreases, the resulting error becomes unbounded.
  • Fixed-worker assumption: If the Byzantine-worker set changes across rounds, the lower bound applies to all algorithms and convergence is impossible.The paper notes that preregistration or identification can help address Sybil-style worker impersonation.

5. Robust robust aggregation

The paper defines robustness through breakdown and approximation quality, proves unavoidable error for arbitrary aggregation, and proposes iterative centered clipping as a scalable robust alternative.

  • Robustness specification: A robust aggregator is evaluated by its breakdown point δmax and quality constant c, seeking large δmax and small c.The target is graceful degradation as the Byzantine fraction increases below δmax.
  • Limits of robustness: Any aggregation rule can incur error at least δρ2 when good vectors have pairwise variance bounded by ρ2.The error can be unbounded when δ ≥ 1/2, establishing the tightness of the robust-oracle notion.
  • Centered clipping: Iterative centered clipping updates a center by clipping each vector’s displacement relative to the current center and averaging the clipped displacements.The procedure starts from v0 and repeats the clipping update for L iterations.
  • Scalability and deployment: Centered clipping requires O(n) computation and communication per step and is compatible with asynchronous updates and secure aggregation.A single iteration is often sufficient in practice, unlike Krum or Bulyan, which require O(n2) computation.
  • Centered clipping guarantees: For δ ≤ 0.1, centered clipping converges from any initial center under an i.i.d. good-worker variance bound.The guarantee is formalized in Theorem IV, which bounds the output after l iterations.
  • Centered clipping guarantees: Running CC for l = 100 log(3B2/δρ2) yields a (δmax, c)-robust aggregator with c = 4000 and δmax = 0.1.If the initial error is at most ρ2, one clipping step is sufficient.
  • Limitations: The paper leaves optimization of the constants, including bringing δmax closer to 0.5 and reducing c, for future work.The authors state that their theorem constants were not optimized.

6. Robust optimization using momentum

Worker momentum reduces the variance of honest updates, exposes time-coupled Byzantine perturbations, and enables robust convergence when combined with Byzantine-resistant aggregation. The approach uses centered clipping and achieves optimal-rate guarantees under the stated assumptions.

  • Momentum defense: The momentum-based algorithm aggregates worker momentum vectors with a Byzantine-resilient rule and updates the model using the aggregated vector.Workers recursively compute momentum, communicate it to the server, and the server applies AGG before the model update.
  • Momentum defense: Worker momentum averages each worker’s updates over time, reducing honest-worker variance and making time-coupled Byzantine perturbations easier to detect.The paper sets β = 1 − α and explains that averaging over roughly 1/α gradients reduces honest-worker variance while Byzantine perturbation variance does not similarly decrease.
  • Theory: Theorem VI proves Byzantine-robust convergence for worker momentum combined with any aggregation rule satisfying the paper’s robustness definition.The guarantee assumes a δ-robust optimization problem and an aggregation rule robust up to at least the Byzantine fraction.
  • Theory: The convergence rate contains a worker-scaling term and an adversarial term that does not improve with more workers, matching the classical robust mean-estimation phenomenon.When δ = 0, the rate recovers the optimal σ/√(nT) dependence; the adversarial contribution depends on δ and T rather than improving with n.
  • Theory: Momentum variance reduction can be combined with Byzantine aggregation to obtain a faster Byzantine-robust algorithm with an asymptotic speedup over traditional momentum.The MVR result matches the cited lower bound when δ = 0 and is described as compatible with state-of-the-art optimization methods.
  • Empirical behavior: Centered clipping is empirically strongest across tested attacks, while its final accuracy remains stable across clipping iterations and radii.The experiments test CIFAR-10 attacks and report that CC consistently performs best; the hyperparameter study supports l = 1 as the default.

7. Experiments

Experiments evaluate robust aggregation and momentum on MNIST and CIFAR-10 under imbalance, attacks, and hyperparameter variation. Centered clipping avoids the middle-seeking failure and momentum generally improves convergence.

  • Experimental setup: The experiments study MNIST on 16 nodes and CIFAR-10 on 25 nodes, repeating each experiment at least twice.The setup includes distributed image classification experiments, with detailed configurations deferred to the appendix.
  • 7.1. Failure of “middle seekers”: Under drastic MNIST imbalance with γ = 0.5, median and geometric-median rules reach only 75% accuracy, corresponding to classes 1 and 2.The result is obtained without attackers using exponentially decaying class frequencies and minibatch size 1 per node.
  • 7.1. Failure of “middle seekers”: Centered clipping and trimmed mean avoid the same accuracy bound because they incorporate gradients from tail distributions.The paper presents this as a practical example of middle-seeking rules failing on imbalanced data.
  • 7.2. Impact of momentum on robust aggregation rules: Momentum generally makes convergence faster and better across robust aggregators and attacks, while centered clipping achieves the best performance in almost all experiments.The CIFAR-10 study uses BF, LF, ALIE, and IPM attacks, with 5 adversaries except 11 for IPM.
  • Hyperparameters: Centered clipping is stable across tested clipping radii and iteration counts and achieves good accuracy even without momentum.The grid search varies τ over [0.1, 10, 1000] and l over [1, 3, 5].

8. Conclusion

The paper argues that inconsistent assumptions can conceal failures in Byzantine-robust learning and advocates end-to-end guarantees under realistic assumptions. Its proposed strategies are centered clipping and worker momentum, supported by convergence analysis and experiments.

  • 8. Conclusion: The paper identifies disparate assumptions as a barrier to comparing Byzantine-robust methods and a source of hidden failure modes.The conclusion motivates evaluating methods with end-to-end convergence guarantees under realistic assumptions.
  • 8. Conclusion: The paper’s final strategy is the combination of centered clipping and worker momentum, which it reports as consistently outperforming the evaluated baselines.The conclusion characterizes the pair as simple, effective, and tested across a variety of attacks.
  • Convergence analysis: The analysis develops convergence results for stochastic gradient descent with momentum, including a low-variance update that supports robust optimization.The proof combines descent and momentum-error bounds to establish the stated convergence theorem.
  • Related analysis: Earlier momentum analyses often treat SGDm as approximate SGD, whereas this work uses a different viewpoint to obtain rates supporting decreasing momentum parameters.The cited contrast concerns both the achievable rates and the restriction to constant momentum in prior analyses.
  • Convergence analysis: The SGDm rate matches the optimal rate of SGD for smooth non-convex functions, with high momentum used when stochastic-gradient variance is present.In the deterministic case σ = 0, the analysis recovers the optimal 1/T rate and does not require variance reduction.

B. Proof of Theorem II - Failure of permutation-invariant methods

The lower-bound proof constructs two indistinguishable robust optimization instances whose stochastic gradients coincide with substantial probability. Consequently, permutation-invariant methods must incur error related to the separation between the instances’ minima.

  • Proof strategy: The proof constructs two δ-robust optimization instances satisfying the definition and argues that they are indistinguishable.The indistinguishability is used to force an error on at least one of the two instances.
  • Instance construction: The first instance uses a quadratic objective with a shifted optimum and stochastic gradients containing a rare perturbed outcome.The construction chooses G = σ˜δ^1/2 so the stochastic gradient remains unbiased with variance bounded by σ^2.
  • Instance construction: The second instance is a centered quadratic with deterministic stochastic gradients, while Byzantine workers corrupt selected gradients to mimic the first instance.The number of corrupted workers is tied to the count of workers drawing the rare stochastic-gradient outcome in the first setting.
  • Probability argument: Chernoff and union-bound arguments ensure the construction satisfies the required worker-count condition across all rounds with the stated probability.The proof sets ˜δ = δ/6 and assumes n is large enough for the bound used over T rounds.
  • Lower bound: With probability at least 0.5, the stochastic gradients are identical up to permutation, so no permutation-invariant algorithm can distinguish the settings.The resulting unavoidable error is of the order of the difference between the two minima.

C. Proof of Theorem III (Limits of robust aggregation)

The proof establishes that robust aggregation has fundamental limits: without enough good workers, the good subset is unidentifiable, and even with fewer Byzantine workers, indistinguishable cases force nonzero estimation error.

  • When δ ≥ 1/2, it is impossible to determine which half of the inputs corresponds to good workers.If half the inputs equal a and half equal b, either subset may be the good workers even when ρ = 0.
  • For δ ≤ 1/2, two scenarios can be statistically indistinguishable even though one contains only good samples and the other has only zero-valued good samples.The construction uses iid samples from P and an adversary that changes up to δn variables to ρδ^-1/2.
  • The indistinguishability occurs with probability at least 1/2, so every estimator must incur error proportional to the difference between the scenarios’ means.The first scenario has all samples good, whereas in the second only the zero samples are good.
  • With no Byzantine workers, setting the clipping radius to infinity reduces centered clipping to averaging and recovers the mean exactly.The proof treats δ = 0 separately, choosing τ_l = Õ(ρ/δ) = ∞.
  • A single centered-clipping step is analyzed using an independent estimate v of the mean, decomposing error into good-worker bias, good-worker variance, and Byzantine-worker error.The analysis assumes E∥v − µ∥2 ≤ O(ρ2) and independence from the good-worker samples.
  • Under the stated independence and starting-error conditions, one centered-clipping iteration suffices to obtain a robust aggregate.For example, if E∥x_i∥2 ≤ bρ2 and v_l = 0, the required initialization condition holds.

D.2. Robustness starting from arbitrary point

Starting from an arbitrary point, the method repeatedly applies centered clipping on one data subset to obtain an accurate estimate, then uses a second independent subset for a final robust aggregation step.

  • The procedure randomly partitions the data into X1 of size 2n/3 and X2 of size n/3 before applying centered clipping.The partition ensures the intermediate estimate computed from X1 is independent of X2.
  • The two-stage strategy guarantees final aggregation error O(δρ2) after computing an O(ρ2)-accurate estimate on X1.The authors use the two-stage construction for a technical reason and believe a single-stage method has similar guarantees.
  • Repeated centered clipping from an arbitrary starting point maintains an error bound for every iteration without requiring assumptions on the current estimate.The recursion combines bounds for clipping bias, variance, and Byzantine-worker error.
  • For δ ≤ 0.1, the second-stage estimate uses δ2 = 3δ and inherits a bound from the independent X2 subset.The first stage uses δ1 = 1.5δ to compute the starting estimate from X1.

E. Proof of Theorem VI - Byzantine-Robust Convergence

The convergence proof combines worker momentum with robust aggregation: momentum reduces good-worker variance and exposes temporally coupled perturbations, while smoothness and aggregation bounds yield convergence.

  • The aggregation-error lemma bounds the distance between ideal average momentum and the robust aggregate for t ≥ 2.The bound applies when the aggregation rule satisfies Definition C and uses α1 = 1 with constant α afterward.
  • Good workers’ momentum vectors become close over time, with ρ2 = 2σ2(α + (1 − α)t−1).This concentration supports applying the robust aggregation guarantee to the worker momenta.
  • The descent analysis assumes an L-smooth objective and step sizes satisfying ηt ≤ 1/L.The proof introduces the ideal momentum error ¯e_t := ¯m_t − ∇f(x_t−1).
  • Momentum error is controlled through recursions involving prior error, gradient norms, worker disagreement, and stochastic variance reduced by averaging over at least n/2 good workers.The variance term appears as σ2/n because good-worker momenta are averaged.
  • The proof assumes conditionally unbiased stochastic gradients with bounded variance and an expected Lipschitz condition across consecutive stochastic gradients.The latter is stronger than requiring only that the full gradient be Lipschitz.
  • Choosing α sufficiently large relative to L2η2 and aggregation constants closes the recursion and yields the theorem’s convergence rate.The proof concludes after summing the recursion and substituting the appropriate step size.

G.1.2. CONSTRUCTING DATASETS

The experiments use MNIST and CIFAR-10 under specified default settings, including long-tailed class sampling, Byzantine-worker data access, local-SGD comparisons, and attacks against CC and Safeguard.

  • CONSTRUCTING DATASETS: Long-tailed MNIST is constructed by sampling class i with an exponentially decreasing fraction γi, and the same procedure is applied to the test set.MNIST contains 10 classes with similar original sample counts.
  • CONSTRUCTING DATASETS: Good workers collectively have full training-set information, while Byzantine workers can access the entire training dataset.The training set is divided according to the number of good workers.
  • Exploring local steps between aggregations: Figure 7 evaluates CC with 1, 2, 8, and 32 local steps on MNIST without attackers, finding that more local steps improve accuracy and convergence rate.The result supports CC’s compatibility with local SGD.
  • Comparison with (Allen-Zhu et al., 2021): Figure 8 compares CC with Safeguard on CIFAR-10 using 10 workers, 4 Byzantine workers, batch size 32, and learning rate 0.1.The Gaussian attack uses standard deviation 108 and is injected at iteration 1 or 2000.
  • Comparison with (Allen-Zhu et al., 2021): Safeguard requires attack-specific parameter tuning, whereas CC uses τ = 100 and l = 1 across the reported experiments.Adaptive attackers make robustness without additional tuning important in this comparison.
Loading 2012.10333v3…