Source-linked AI summary
The Hidden Vulnerability of Distributed Learning in Byzantium
El Mahdi El Mhamdi, Rachid Guerraoui, Sébastien Rouault
TL;DR
The paper asks whether convergence guarantees are sufficient for distributed SGD with Byzantine workers in high-dimensional, non-convex settings. It analyzes attacks that exploit this gap and introduces Bulyan, which narrows attackers’ influence while empirically avoiding ineffective convergence. The method requires a worker quorum and assumes an adversary controlling f workers.
Problem
Existing Byzantine-resilient schemes guarantee SGD convergence despite a minority of adversarial workers, but the paper examines whether convergence is sufficient in high-dimensional, non-convex neural-network settings.
Method
The paper analytically studies attacks on Byzantine-resilient aggregation rules and proposes Bulyan(A), a generic enhancement that repeatedly selects vectors and enforces coordinate-wise agreement.
Results
Bulyan avoids convergence to ineffective models and learns models comparable to a non-attacked averaging benchmark; under continuous attack, Krum’s accuracy decreased 33% by epoch 1000 and GeoMed failed to produce a useful model.
Takeaways & Limitations
Convergence alone is not enough for Byzantine-resilient distributed SGD, whereas Bulyan reduces attackers’ influence and retains practical convergence behavior.
Takeaways & Limitations
Bulyan’s stated quorum condition is n ≥ 4f + 3, limiting its applicability to systems that can provide enough workers.
Abstract
from arXiv · showhide
While machine learning is going through an era of celebrated success, concerns have been raised about the vulnerability of its backbone: stochastic gradient descent (SGD). Recent approaches have been proposed to ensure the robustness of distributed SGD against adversarial (Byzantine) workers sending poisoned gradients during the training phase. Some of these approaches have been proven Byzantine-resilient: they ensure the convergence of SGD despite the presence of a minority of adversarial workers. We show in this paper that convergence is not enough. In high dimension $d \gg 1$, an adver\-sary can build on the loss function's non-convexity to make SGD converge to ineffective models. More precisely, we bring to light that existing Byzantine-resilient schemes leave a margin of poisoning of $Ω\left(f(d)\right)$, where $f(d)$ increases at least like $\sqrt{d~}$. Based on this leeway, we build a simple attack, and experimentally show its strong to utmost effectivity on CIFAR-10 and MNIST. We introduce Bulyan, and prove it significantly reduces the attackers leeway to a narrow $O( \frac{1}{\sqrt{d~}})$ bound. We empirically show that Bulyan does not suffer the fragility of existing aggregation rules and, at a reasonable cost in terms of required batch size, achieves convergence as if only non-Byzantine gradients had been used to update the model.
1. Introduction
Distributed SGD can converge despite Byzantine workers, but in high-dimensional, non-convex neural-network settings convergence may still produce ineffective models. The paper analyzes this vulnerability and proposes Bulyan to narrow attackers’ influence while retaining practical convergence.
- Background: SGD reaches global minima for convex objectives but may settle in flat regions or local minima when the loss is non-convex.Neural-network objectives are described as far from convex.
- Distributed robustness: Distributed implementations aggregate gradients from multiple workers, whose estimates can be biased by noisy data or Byzantine workers.Robust aggregation replaces simple linear combinations with estimators designed to tolerate adversaries.
- Problem: Existing Byzantine-resilient aggregation rules guarantee SGD convergence, motivating the question of whether convergence is sufficient for neural networks.The paper frames this question specifically in non-convex, high-dimensional settings.
- Problem: A single Byzantine worker can make known Byzantine-resilient rules converge to ineffective models by exploiting high dimensionality and non-convexity.This attack does not contradict convergence proofs; it redirects convergence toward ineffective models.
- Contribution: Bulyan(A) narrows the selected vectors’ cone from angle α to α′ ≤ α and reduces Byzantine workers’ leeway.The paper also evaluates convergence speed against other aggregation rules and reports comparable speed to averaging at typical batch sizes.
2. Model
The model uses a parameter server with honest and Byzantine workers that submit gradients for aggregation. It formalizes Byzantine-resilient aggregation rules and describes Brute, Krum, and GeoMed, including their requirements and practical constraints.
- Distributed SGD: The distributed system contains one master and n workers, with at most f Byzantine workers controlled by an adversary.Honest workers compute stochastic gradient estimates from i.i.d. mini-batches.
- Adversary: The adversary knows the complete system state but can only submit gradients through its controlled workers.It cannot modify system state, impersonate workers, or delay communications.
- Gradient aggregation rules: A gradient aggregation rule transforms workers’ submitted gradients into one gradient used to update the model parameters.The paper contrasts Byzantine-resilient rules with averaging and other linear combinations.
- Resilience definition: Expectations in the Byzantine-resilience definition are over honest workers’ i.i.d. mini-sample randomness, while Byzantine behavior is analyzed in the worst case.The definition’s conditions support a global confinement proof for SGD.
- Brute: Brute requires n ≥ 2f + 1 and selects the n − f most clumped gradients before averaging them.Its exhaustive subset search makes it impractical at scale: n = 57 and f = 27 would take more than five months at 10^9 subsets per second.
- Krum: Krum requires n ≥ 2f + 3 and outputs the received gradient with the lowest distance-based score.Its Byzantine-resilience is attributed to the original Krum result.
- GeoMed: GeoMed uses the medoid of submitted gradients, while the resilience angle α for the median is not known from the cited results.The medoid is chosen because it is easier to compute than the exact geometric median.
3. Effective attack on ℓp norm–based GARs
The paper presents a simple attack that exploits the inability of ℓp-distance-based aggregation rules to distinguish distributed coordinate-wise disagreement from concentrated poisoning. The resulting aggregated gradients can drive SGD toward ineffective models, while the attack’s maximum strength depends on the aggregation rule and dimension.
- Any ℓp-norm-based GAR using distance minimization can be bypassed by the proposed attack.
- In high dimensions, small coordinate-wise disagreements can mask much larger disagreement concentrated on one coordinate.
- A poisoned coordinate can make the aggregated gradient unusually large, pushing parameters into a rarely reached sub-space.
- The attack’s effect depends on the learning rate and can produce sub-optimal to utterly ineffective models.
- The adversary estimates the largest accepted γ, submits the resulting vector through every Byzantine worker, and obtains rule-dependent poisoning leeway.
- For infinite norms, modifying non-maximal coordinates can preserve distance sufficiently for a related attack to proceed.
4. Bulyan
Bulyan enhances any Byzantine-resilient aggregation rule by repeatedly selecting gradients and aggregating coordinate-wise values near their medians. It narrows Byzantine workers’ coordinate-wise influence while preserving resilience and convergence, at a computational cost characterized for general and specific base rules.
- Algorithm: Bulyan(A) recursively applies A to select θ = n − 2f gradients before performing coordinate-wise median-based aggregation.The selected set contains a majority of non-Byzantine gradients when n ≥ 4f + 3; each output coordinate averages the β = θ − 2f closest values to the selected-coordinate median.
- Algorithm: Bulyan(A) requires n ≥ 4f + 3 received gradients and ensures majority-supported coordinate medians during its two-step construction.The quorum condition provides 2f + 3 workers for each use of A, while β ≥ 3 values remain for the final coordinate-wise averaging step.
- Cost: The average computational complexity is O((n − 2f)C + dn) per master-side epoch, with additional amortization available for Krum and GeoMed.Here C is the cost of running the base aggregation rule A once; for Krum or GeoMed, repeated distance computations can be reused.
- Byzantine leeway reduction: Proposition 2 bounds each Bulyan output coordinate’s expected distance from any honest worker’s corresponding coordinate by O(1/√d).This reduces the attacker’s component-wise deviation margin while the aggregated gradient can still influence the result.
- Byzantine leeway reduction: If A selects vectors within a cone of angle α around the true gradient, Bulyan(A) selects vectors within a cone of angle α′ ≤ α.Thus Bulyan narrows the attacker’s leeway without adding bias beyond the base rule’s cone guarantee.
- Resilience and convergence: Bulyan(A) preserves (α, f)-Byzantine resilience and therefore almost-sure convergence to a region where ∇Q(x) = 0.The convergence guarantee follows from retaining the base rule’s resilience while reducing coordinate-wise attacker influence.
5. Evaluation
Experiments on MNIST and CIFAR-10 show that the attack can make existing aggregation rules learn ineffective models, whereas Bulyan resists it with a moderate convergence-speed cost.
- Attack evaluation: On MNIST, a 50-epoch attack was sufficient to keep the model ineffective for at least 950 further epochs, except under Brute.The attack phase ended at epoch 50, but the parameter vector remained in an ineffective sub-space.
- Attack sensitivity: Higher learning rates and smaller batches increased attack effectiveness, and some alternative initial settings completely prevented learning.
- Bulyan evaluation: On CIFAR-10, Bulyan was the only evaluated rule unaffected by the attack in the corresponding comparison with Krum and GeoMed.
- Bulyan evaluation: With 30 non-Byzantine and 9 Byzantine workers, Bulyan resisted the attack on MNIST and matched the accuracy obtained by averaging only non-Byzantine gradients.
- Cost of Bulyan: Without adversaries, Bulyan’s convergence-speed loss was minimized at batch sizes of 24 images for MNIST and 36 for CIFAR-10.
6. Concluding remarks
The paper argues that Byzantine-resilient convergence can still yield ineffective models in high-dimensional, non-convex learning, and presents Bulyan as a defense against this drift. Its scope is training-time poisoning rather than attacks on already trained models.
- Concluding remarks: The Byzantine-failure model is also argued to apply to poisoning on single machines and to centralized learning with unreliable data.
- Concluding remarks: Existing defenses may converge in very high-dimensional, highly non-convex settings yet still reach the worst possible region; Bulyan is theoretically shown to reduce this adversarial leeway.
- Concluding remarks: Empirically, Bulyan avoids ineffectual models and learns models comparable to a non-attacked averaging scheme.
- Scope: The paper addresses poisoning during training but does not address evasion attacks against already trained models.
- Related robustness perspectives: The paper places poisoning robustness alongside propagated-error and evasion-attack analyses, including bounds with exponential dependence on network depth.
A.1. Background
The background defines Byzantine resilience through an aggregation rule’s expected alignment with the true gradient and bounded higher moments under adversarial submissions.
- Definition: Definition 2 introduces (α, f)-Byzantine resilience for an aggregation rule operating with n−f honest and f potentially dependent Byzantine vectors.
- Definition: The definition allows Byzantine vectors to depend on honest vectors and on one another, while honest vectors are identically distributed with expectation G.
- Definition: The aggregation output must have expected inner product with G at least (1−sin α)||G||^2, which is positive.
- Definition: The output’s expected norms of orders 2, 3, and 4 must be bounded by linear combinations of corresponding moments of G.
A.2. Definition
The formal setup assumes at least 2f+1 workers, models honest and Byzantine submitted gradients separately, and considers all subsets containing n−f submitted gradients.
- Assumptions: The setup requires n ≥ 2f + 1 workers and permits ℓp norms for finite positive integer p or p = +∞.
- Assumptions: Honest gradients are independent and identically distributed with expectation G, whereas Byzantine vectors may depend on honest vectors and each other.
- Aggregation setup: The submitted gradients form Q, and R contains every subset of Q with cardinality n−f.
A.3. Proof
The proof establishes conditions under which distance-based aggregation remains Byzantine-resilient, then analyzes how an attacker can construct submissions that satisfy those conditions while poisoning gradients.
- Resilience proof: 2 f σ̄ < (n − f)∥G∥p is the sufficient assumption used to prove Byzantine resilience.Under this condition, the expected aggregated gradient remains aligned with the true gradient.
- Resilience proof: The proof handles the case where Byzantine vectors are excluded by observing that averaging unbiased non-Byzantine vectors gives E[F] = G.This makes the resilience conditions immediate in that case.
- Resilience proof: The proof then characterizes selected sets containing Byzantine vectors and compares their aggregated gradient with the non-Byzantine average.Several intermediate observations ensure suitable non-Byzantine vectors remain available for the comparison.
- Attack construction: The attack analysis models coordinates as normally distributed and studies high-dimensional gradients under d ≫ 1.It examines an attacked coordinate formed as B = V + αmE and focuses on worst-case Byzantine proportions.
- Attack construction: The worst-case analyses use n = 2f + 1 for Brute and n = 2f + 3 for GeoMed and Krum.For GeoMed and Krum, q is set to 1 and 2 respectively while evaluating the Byzantine submission’s score.
- Attack construction: The resulting poisoning condition is necessary and approximate, providing broad insight into how hyperparameters relate to the attack magnitude αm.The passage states that, with p and q fixed, αm follows an O-bound.
C.1. Attack on Brute, Krum and GeoMed
The experiments compare Brute, Krum, GeoMed, and Average on MNIST and CIFAR-10 under the proposed attack. Across both datasets, the aggregation rules remain trapped in ineffective models for at least 1000 epochs.
- Experimental setup: MNIST uses η0 = 1, rη = 10000, and batch sizes of 83 images, or 256 for Brute.Krum and GeoMed use 30 non-Byzantines plus 27 Byzantines; Brute uses 6 plus 5; Average uses 30 non-Byzantines.
- Experimental setup: CIFAR-10 uses η0 = 0.5, rη = 2000, and batch sizes of 128 images, or 256 for Brute.Krum and GeoMed use 21 non-Byzantines plus 18 Byzantines; Brute uses 6 plus 5; Average uses 21 non-Byzantines.
- MNIST: On MNIST, the attack stops after 50 epochs, yet none of the presented aggregation rules prevents ineffective-model behavior through at least epoch 1000.The attack variant targeting ℓ∞-norm-based rules has a very strong impact.
- CIFAR-10: On CIFAR-10, the attack continues throughout training, and none of the presented aggregation rules prevents ineffective-model behavior through at least epoch 1000.The figure compares testing accuracy with Average as the non-Byzantine reference.