Source-linked AI summary
Generalized Byzantine-tolerant SGD
Cong Xie, Oluwasanmi Koyejo, Indranil Gupta
TL;DR
Distributed synchronous SGD needs aggregation rules that tolerate arbitrary, dimension-wise Byzantine corruption in Parameter Server systems. The paper proposes three median-based rules, proves their resilience and convergence properties, and reports good empirical performance, while noting attack and sampling assumptions that bound the scope of those results.
Problem
The paper asks which aggregation rules and conditions allow synchronous SGD to converge under generalized Byzantine failures that can corrupt transmitted values arbitrarily.
Method
It proposes geometric median, marginal median, and mean-around-median aggregation rules and studies their theoretical resilience and convergence in the generalized model.
Results
The proposed algorithms have provable convergence to critical points, low time complexity, and good empirical performance in practice.
Takeaways & Limitations
Mean-around-median performs best in almost all reported cases, while also having lower time complexity than Multi-Krum.
Takeaways & Limitations
The resilience analysis assumes i.i.d. correct gradients, and the gambler attack can break the robust rules’ prerequisites and crash training.
Abstract
from arXiv · showhide
We propose three new robust aggregation rules for distributed synchronous Stochastic Gradient Descent~(SGD) under a general Byzantine failure model. The attackers can arbitrarily manipulate the data transferred between the servers and the workers in the parameter server~(PS) architecture. We prove the Byzantine resilience properties of these aggregation rules. Empirical analysis shows that the proposed techniques outperform current approaches for realistic use cases and Byzantine attack scenarios.
1. Introduction
The paper studies synchronous SGD in Parameter Server systems under generalized Byzantine failures, where arbitrary transmitted gradient values may be corrupted without row-wise constraints. It proposes median-based aggregation rules with dimensional resilience, provable convergence, and nearly linear computation.
- Distributed training improves scalability but increases exposure to crashes, computation errors, stalled processes, and compromised subsystems.
- The Parameter Server architecture distributes data across workers, which compute gradients while servers aggregate updates and broadcast model parameters.
- Generalized Byzantine failures allow arbitrary gradient corruption anywhere in the n×d worker-gradient matrix, unlike the classic model’s row constraint.
- Dimensional Byzantine resilience requires fewer than half of the n worker values in each dimension to be Byzantine.
- The paper proposes geometric median, marginal median, and mean-around-median aggregation rules with provable convergence to critical points.
- The proposed rules have nearly linear time complexity, matching the order of ordinary averaging.
2. Model
The model uses synchronous SGD in a Parameter Server architecture, where servers aggregate one gradient from each worker before updating and rebroadcasting parameters. Byzantine processes may replace transmitted values arbitrarily and may possess complete system knowledge.
- In each synchronous round, servers collect n worker gradients, aggregate them, update x_t to x_{t+1}, and broadcast the new parameters.
- A worker’s transmitted vector may be Byzantine, so received gradients can be partially replaced by arbitrary values.
- Workers compute gradients from their local data partitions after pulling the latest server parameters.
- Attackers may know the entire system, including all worker gradients and the aggregation rule, and may collaborate.
3. Byzantine Resilience
The paper extends Byzantine resilience from worker-level corruption to dimension-level corruption and analyzes when aggregation preserves useful gradient direction and moment control. It shows that averaging and selection-based rules such as Krum fail under the generalized model, while dimensional resilience implies almost-sure convergence under stated assumptions.
- Generalized Byzantine model: The generalized model permits up to q arbitrary replacements independently in each gradient dimension, rather than restricting Byzantine values to the same workers.
- Dimensional resilience: Dimensional (α, q)-Byzantine resilience requires positive expected alignment with the true gradient and bounded output moments.
- Resilience definitions: Classic Byzantine resilience is a special case of dimensional resilience because classic corruption uses the same Byzantine workers across dimensions.
- Impossibility results: Averaging and any rule that outputs one received vector are not dimensional Byzantine resilient; therefore Krum is not dimensional Byzantine resilient.
- Convergence: If the resilience property and regularity, learning-rate, variance, and gradient-growth assumptions hold, synchronous SGD converges almost surely to critical points.
4. Median-based Aggregation
The paper introduces three median-based aggregation rules for Byzantine-resilient synchronous SGD and establishes conditions under which they retain provable resilience. The rules differ in how they aggregate vector information, with mean around median extending coordinate-wise median aggregation by averaging nearby values.
- 4. Median-based Aggregation: Marginal median and mean around median provide dimensional rather than only worker-level resilience, matching the paper’s generalized failure model.The model allows Byzantine values anywhere in the worker-by-coordinate matrix, while classic resilience restricts them to the same workers.
- 4.1. Geometric Median: The geometric median aggregates workers’ vectors through a robust multivariate estimator and has provable classic Byzantine resilience under a bound on q.Its approximate computation is nearly linear in O(dn).
- 4.2. Marginal Median: The marginal median computes each output coordinate as the one-dimensional median of that coordinate across workers and is dimensionally Byzantine-resilient.The theorem permits arbitrary replacements independently within each dimension under its stated condition.
- 4.3. Beyond Median: Mean around median averages the n−q coordinate values nearest each coordinate’s median, filtering values far from the median.It is a trimmed average centered at the median and is dimensionally Byzantine-resilient under the theorem’s condition.
- 4.3. Beyond Median: The mean-around-median rule is dimensionally Byzantine-resilient when q satisfies the stated bound involving 10(n−q).The theorem expresses its angular parameter through sin α3.
- 4. Median-based Aggregation: Marginal median and mean around median have lower stated computational complexity than Krum and Multi-Krum.Their complexity is O(dn log n) with sorting, or average O(dn) for median selection; Krum and Multi-Krum require O(dn2).
5. Experiments
Experiments on MNIST and CIFAR10 compare Mean, Medoid, Krum, Multi-Krum, GeoMed, MarMed, and MeaMed under benign and Byzantine settings. MeaMed performs best in almost all cases, while MarMed and MeaMed are the only rules shown to remain dimensional Byzantine resilient under bit-flip and gambler attacks.
- Experimental setup: The experiments use 20 workers on MNIST with an MLP and CIFAR10 with a CNN, comparing four baselines with GeoMed, MarMed, and MeaMed.Each experiment is repeated ten times and averaged; CNN results are reported as representative because they resemble the MNIST experiments.
- No Byzantine failures: Without Byzantine failures, Multi-Krum, GeoMed, and MeaMed have the least bias and behave like averaging, while MarMed, Medoid, and Krum converge more slowly.The accuracy gaps between algorithms are tiny; Medoid and Krum have the slowest convergence.
- Classic Byzantine attacks: Under Gaussian attack with 6 of 20 vectors replaced, averaging is not Byzantine resilient, whereas the other algorithms retain small accuracy gaps.The attack uses zero-mean Gaussian random vectors with standard deviation 200; GeoMed and MeaMed perform like the benign baseline.
- Classic Byzantine attacks: Under omniscient attack, MeaMed performs as if there were no failure, while Multi-Krum is worse but remains close.Each of 6 Byzantine vectors is replaced by the negative sum of correct gradients scaled by 1e20.
- Dimensional Byzantine attacks: Under bit-flip attack, only MarMed and MeaMed are dimensional Byzantine resilient; Krum-based methods violate their assumptions because all 20 vectors are partially manipulated.The attack flips specified bits in one value among 20 for each of the first 1000 dimensions, making every vector Byzantine under the classic vector-level assumption.
- Discussion: MeaMed performs best in almost all cases and has lower time complexity than Multi-Krum, while MarMed has the cheapest computation and does not require the number of Byzantine values.The paper suggests MarMed for most applications because its worst-case omniscient attack is considered difficult to implement in reality.
6. Related Works
The paper positions its median-based aggregation rules as cheaper, less knowledge-dependent, and more resilient to generalized Byzantine failures than prior approaches. It also highlights reduced communication needs for disjointly partitioned parameters across multiple servers.
- Prior and proposed aggregation: Geometric median, marginal median, and mean around median provide alternatives to prior Byzantine-resilient aggregation approaches.The paper studies these rules under nonconvex settings, alongside related work on geometric-median aggregation for strongly convex functions.
- Computational cost: O(nd) time complexity for marginal median and mean around median is lower than Krum's O(n2d).Geometric median also has nearly linear approximately O(nd) complexity.
- Prior knowledge: Geometric median and marginal median do not require the number of Byzantine workers q, whereas Krum requires q.When q is known or well estimated, mean around median shows better robustness than Krum and Multi-Krum in most cases.
- Failure model: Marginal median and mean around median tolerate dimensional Byzantine failures, while Krum and geometric median tolerate only classic Byzantine failures.Dimensional resilience allows Byzantine values to occur across dimensions rather than being restricted to whole worker rows.
- Multiple servers: Marginal median and mean around median need no additional communication when disjoint parameter partitions are stored on multiple servers.Krum and geometric median require communication among server nodes in this setting.
7. Conclusion
The paper studies generalized Byzantine resilience in parameter-server synchronous SGD and proposes three median-based aggregation rules. These algorithms combine provable convergence to critical points with low time complexity and good empirical performance.
- Contribution: The paper proposes three median-based aggregation rules for synchronous SGD under generalized Byzantine failures.The studied architecture is the parameter server architecture.
- Theory and efficiency: The proposed algorithms have low time complexity and provable convergence to critical points.The conclusion presents these as core properties of the proposed aggregation rules.
- Empirical results: Empirical results show good performance in practice.The conclusion reports this outcome without specifying a single benchmark value.
8. Appendix
The appendix develops counterexamples, lemmas, and theorems supporting the paper's resilience claims, then reports additional experiments. It shows limits of averaging and vector-selection rules, establishes conditions for the proposed rules, and compares their empirical behavior under benign and gambler attacks.
- Impossibility results: Averaging is not dimensional Byzantine resilient because an attack can make the expected aggregated direction oppose the true gradient.The counterexample uses one Byzantine value per dimension and implies failure to converge to critical points.
- Impossibility results: Any aggregation rule that outputs one submitted worker vector is not dimensional Byzantine resilient.The appendix constructs an attack manipulating one dimension of each vector so that every selectable vector can have an arbitrarily adverse inner product.
- Geometric median: The geometric median is proved classically Byzantine resilient under a condition relating Byzantine count, gradient variance, and gradient magnitude.The appendix derives a bound placing its expected output near the true mean.
- Marginal median: If q ≤ ⌈n/2⌉−1, a scalar median lies between the minimum and maximum correct values.This lemma supports marginal median's dimensional Byzantine resilience under its stated variance and gradient conditions.
- Mean around median: Mean around median stays within the maximum correct deviation from the median when correct values dominate the sequence.This lemma supports the stated dimensional resilience theorem for mean around median under its q and variance conditions.
- Additional experiments: Without Byzantine failures, GeoMed, Multi-Krum, and MeaMed perform like Mean, while MarMed converges slightly more slowly.The convergence gap narrows as batch size increases; Krum and Medoid are the slowest in the reported experiment.
- Additional experiments: Under gambler attack, Krum-based algorithms always crash across the tested q estimates, while MeaMed usually performs well and resembles MarMed.MeaMed also crashes when the estimated q is too small, such as q = 2.
- Additional experiments: CNN experiments on CIFAR10 generally show results similar to the MLP experiments on MNIST.The appendix presents these additional experiments for completeness.