Bulyan (Byzantine-Resilient Gradient Meta-Aggregation Rule)
Algorithms AIMech:BulyanByzantineResilientGradientAggregation DRAFT
Aliases: Bulyan, Bulyan Gradient Aggregation, Bulyan Byzantine-Resilient Meta-Aggregation
Bulyan (or Bulyan(A)) is a two-stage Byzantine-resilient gradient meta-aggregation rule for distributed stochastic gradient descent over n >= 4f + 3 workers (up to f Byzantine) that eliminates the high-dimensional coordinate-wise poisoning leeway Omega(d^{1/p}) of l_p-norm distance-based aggregation rules A (such as Krum, Brute, or GeoMed) by (1) recursively invoking A without replacement theta = n - 2f >= 2f + 3 times to build a selection set S = (S_1, ..., S_theta) guaranteed to contain a strict majority of non-Byzantine gradients, and (2) computing each i-th coordinate of the aggregated gradient G[i] = (1/beta) sum_{X in M[i]} X[i] as the average of the beta = theta - 2f >= 3 values in S closest to the coordinate median median[i] = argmin_{m=Y[i], Y in S} sum_{Z in S} |Z[i] - m|.
Identity Notes & Concept Scope
Introduced by El Mahdi El Mhamdi, Rachid Guerraoui, and Sebastien Rouault in 'The Hidden Vulnerability of Distributed Learning in Byzantium' (ICML 2018, PMLR 80:3518-3527; arXiv:1802.07927). Distinct from Krum and Multi-Krum (Blanchard et al. NeurIPS 2017), which select and average whole vectors using Euclidean pairwise distance scores without coordinate-wise median trimming and thus remain vulnerable to single-coordinate O(sqrt(d)) poisoning; and distinct from Coordinate-Wise Median and Trimmed Mean (Yin et al. ICML 2018), which apply coordinate-wise order statistics directly to all n submitted vectors without a first-stage (alpha, f)-Byzantine-resilient vector selection quorum S.
Claims & Grounded Evidence
3 Claims
Mechanism
#bulyan-high-dimensional-lp-norm-poisoning-leeway-analysis
In dimension d >> 1, any l_p-norm distance-minimization gradient aggregation rule (including Brute, Krum, and GeoMed) allows an omniscient adversary submitting B(gamma) = (1/(n - f)) sum_{V in Q} V + gamma E on a single coordinate E = (0, ..., 1, ..., 0) to be selected while injecting a coordinate-wise poisoning margin of gamma_m = O(bar_delta d^{1/p}) for Brute and gamma_m = O(bar_delta f^{1/q} d^{1/p}) for Krum (q=2) and GeoMed (q=1), or driving l_infty-norm rules along E = (1, ..., 1) into ineffective non-convex subspaces.
Mechanism
#bulyan-two-stage-selection-and-coordinate-wise-leeway-reduction
Given n >= 4f + 3 workers and any (alpha, f)-Byzantine-resilient rule A, Bulyan(A) recursively selects theta = n - 2f >= 2f + 3 vectors into S and averages the beta = theta - 2f >= 3 closest values to median[i] on each coordinate i in [1..d]; Proposition 2 proves that every selected coordinate B[i] in M[i] is bracketed by at least two honest workers g_l[i] <= B[i] <= g_r[i], narrowing the expected component-wise attacker leeway to E|Bu_t[i] - g_k[i]| = O(sigma / sqrt(d)) while preserving (alpha, f)-Byzantine-resilience and almost-sure convergence (Corollaries 1-2).
Application
#bulyan-amortized-quadratic-complexity-and-empirical-resilience
Proposition 1 proves that Bulyan(A) has average master complexity O((n - 2f) C + d n) and, by reusing pairwise distance computations across the theta iterations of Krum or GeoMed, achieves the same O(n^2 d) asymptotic complexity as base Krum or GeoMed; on MNIST (d approx 8 x 10^4) and CIFAR-10 (d approx 10^6) with 30 honest and 9 Byzantine workers under the curse-of-dimensionality attack, Bulyan(Krum) matches unattacked honest averaging while standalone Krum and GeoMed degrade or fail to learn (Figures 4-5).
⚠️ Curated Limitations & Negative Results
- Requires n >= 4f + 3 total workers (tolerating less than 25% Byzantine workers), compared to n >= 2f + 3 for standalone Krum and n >= 2f + 1 for Brute or Coordinate-Wise Median.
- When using very small mini-batch sizes in Byzantine-free settings, trimming 2f coordinates around the median slightly reduces convergence speed relative to arithmetic averaging (Figure 6).
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:FederatedLearning
Federated Learning
|
related_match | Bulyan is a Byzantine-resilient gradient meta-aggregation rule for distributed parameter-server and federated optimization related to AIO:FederatedLearning. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r518-primary-pdf
|
El Mahdi El Mhamdi, Rachid Guerraoui, Sebastien Rouault
|
primary paper
full_text
|
ID: https://dblp.org/rec/conf/icml/MhamdiGR18
sha256:5234c45a295f…
|
r518-arxiv-abs
|
El Mahdi El Mhamdi, Rachid Guerraoui, Sebastien Rouault
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/1802.07927
sha256:54577000dfe2…
|
r518-metadata-cr
|
El Mahdi El Mhamdi, Rachid Guerraoui, Sebastien Rouault
|
primary paper
abstract_only
|
ID: https://dblp.org/rec/conf/icml/MhamdiGR18
sha256:72596d3756ca…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T10:01:00Z
Updated: 2026-10-19T10:01:00Z
Source File:
data/curated/BulyanByzantineResilientGradientAggregation.yaml
· Schema:
curated_concept.yaml
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories