Home / Curated / Algorithms / Krum and Multi-Krum Byzantine-Tolerant Gradient Descent

Krum and Multi-Krum Byzantine-Tolerant Gradient Descent

Algorithms AIMech:KrumAndMultiKrumByzantineTolerantGradientDescent DRAFT

Aliases: Krum, Multi-Krum, Krum Byzantine-Tolerant SGD, (alpha, f)-Byzantine Resilient Krum Aggregation

A Euclidean-distance neighborhood gradient aggregation rule (Krum and Multi-Krum) for distributed stochastic gradient descent with n workers of which up to f are Byzantine (2f + 2 < n). Given worker vectors V_1,...,V_n in R^d, Krum assigns each worker i the score s(i) = sum_{i -> j} ||V_i - V_j||^2 summed over the n - f - 2 closest neighbors V_j of V_i in squared Euclidean norm, and outputs the single vector Kr(V_1,...,V_n) = V_{i_*} with minimum score s(i_*); Multi-Krum (Kr_m) averages the m vectors with the smallest scores s(i_*^1),...,s(i_*^m) for 1 <= m <= n - 2f - 2.

Identity Notes & Concept Scope Distinct from Coordinate-wise Median and Coordinate-wise Trimmed Mean (AIMech:CoordinateWiseMedianAndTrimmedMeanByzantineRobustDistributedLearning, which aggregate each coordinate independently in O(n d) time rather than selecting whole gradient vectors via joint d-dimensional Euclidean neighborhood distances in O(n^2 (d + log n)) time) and from RFA Smoothed Weiszfeld Geometric Median (AIMech:RfaRobustFederatedAggregationSmoothedWeiszfeldGeometricMedian, which computes an iterative smoothed l_2 geometric median across all vectors up to f < n/2 rather than selecting among submitted worker vectors for 2f + 2 < n).

Claims & Grounded Evidence

4 Claims

Mechanism #r399-linear-aggregation-impossibility-and-alpha-f-byzantine-resilience

Lemma 1 proves that no non-zero linear combination of worker gradients can tolerate even a single Byzantine worker (f = 1), whereas Proposition 1 proves that for 2f + 2 < n and bounded isotropic variance sqrt(d) * sigma < ||g|| / eta(n, f) with eta(n, f) = sqrt(2 * (n - f + (f*(n - f - 2) + f^2*(n - f - 1)) / (n - 2f - 2))), Krum satisfies (alpha, f)-Byzantine resilience (<E[Kr], g> >= (1 - sin alpha) ||g||^2 > 0 and bounded 2nd-4th moments) in O(n^2 (d + log n)) time (Lemma 2).

supports Source: Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent · Locator: Section 3 (Lemma 1, Definition 1) and Section 4 (Lemma 2, Proposition 1), pp. 3-6

Mechanism #r399-almost-sure-nonconvex-quasi-martingale-convergence-and-multi-krum

Proposition 2 establishes almost-sure convergence of Krum-SGD gradients to zero on smooth nonconvex objectives via Fisk quasi-martingale convergence whenever the cone angle satisfies eta(n, f) * sqrt(d) * sigma < ||g||, and Proposition 3 extends (alpha, f)-Byzantine resilience to Multi-Krum Kr_m = (1/m) sum_{s=1}^m V_{i_*^s} when 2f + 2 < n - m, interpolating between 1-Krum selection and mini-batch averaging.

supports Source: Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent · Locator: Section 5 Convergence Analysis (Proposition 2) and Section 6 Discussion / Multi-Krum (Proposition 3), pp. 6-8

Limitation #r399-quadratic-worker-complexity-and-dimension-noise-cone-limitation

Computing all pairwise distances for Krum costs O(n^2 (d + log n)) per step, requires strictly more than 2f + 2 workers (n >= 2f + 3, or n > 2f + 2 + m for Multi-Krum), and its theoretical cone condition eta(n, f) * sqrt(d) * sigma < ||g|| degrades with sqrt(d) in high dimensions or under non-i.i.d. worker heterogeneity.

supports Source: Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent · Locator: Section 4 Lemma 2, Proposition 1, Section 5 Proposition 2, and Section 6, pp. 4-8

Application #r399-omniscient-gaussian-and-bit-flip-byzantine-defense-application

Evaluated on distributed training of multi-layer perceptrons (spambase) and convolutional neural networks (MNIST) under omniscient adversary, Gaussian noise, and bit-flipping attacks up to 45% Byzantine workers, where Multi-Krum maintains clean accuracy while naive averaging fails.

supports Source: Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent · Locator: Section 6 Discussion and Experiments (Figures 2-4), pp. 7-9

⚠️ Curated Limitations & Negative Results

Pairwise Euclidean distance computation scales quadratically with the number of workers as O(n^2 (d + log n)).
Requires knowing an upper bound f on the number of Byzantine workers with 2f + 2 < n (and 2f + 2 + m < n for Multi-Krum) and degrades when intra-honest variance sigma * sqrt(d) exceeds ||g|| / eta(n, f).

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	Krum and Multi-Krum are foundational Byzantine-resilient gradient aggregation rules used in distributed and federated optimization.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r399-primary-pdf`	Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, Julien Stainer	primary paper full_text	ID: https://doi.org/10.48550/arXiv.1703.02757 sha256:80f2f4aa9cfc…
`r399-arxiv-abs`	Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent (arXiv abstract) Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, Julien Stainer	primary paper abstract_only	ID: https://arxiv.org/abs/1703.02757 sha256:4e5f47badf42…
`r399-metadata-cr`	Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent (Crossref metadata) Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, Julien Stainer	primary paper abstract_only	ID: https://doi.org/10.48550/arXiv.1703.02757 sha256:aae2304f650f…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T08:02:00Z

Updated: 2026-10-19T08:02:00Z

Source File: data/curated/KrumAndMultiKrumByzantineTolerantGradientDescent.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