Byzantine-Robust Aggregation

"They sent me twenty numbers and swore that all twenty were honest. I sorted them, looked at the one in the middle, and politely ignored the rest of the argument."

A Median, Refusing to Be Dragged Around by Outliers

In Section 35.4 we watched one compromised worker take over a training run by submitting a gradient that the coordinator dutifully averaged into the model. The mechanism was not a software bug; it was the aggregation rule. Standard data-parallel training and federated learning both combine worker updates by averaging them, the exact identity that made distribution painless in Section 1.1 and that returns as gradient all-reduce in Chapter 15 and as FedAvg in Chapter 14. The average is exact, cheap, and catastrophically fragile: it trusts every contributor equally. Once we drop the assumption that every worker is honest, the threat model of Section 35.3 forces a different question. Not "what is the mean of these updates?" but "what is a value that the honest majority would endorse, no matter what the rest send?" That question has a classical answer in robust statistics, and porting it onto the fleet is the subject of this section.

1. The Breakdown Point of the Mean Is Zero Intermediate

The breakdown point of an estimator is the smallest fraction of the input that an adversary must corrupt to drive the output arbitrarily far from the value the clean data would have produced. It is the right lens for Byzantine robustness because it asks exactly the adversary's question: how little do I have to control to win? For the sample mean the answer is brutal. Let $N$ workers submit update vectors $g_1, \dots, g_N \in \mathbb{R}^d$, and let the aggregate be $\bar{g} = \frac{1}{N} \sum_{i=1}^{N} g_i$. Suppose a single worker $j$ is Byzantine and sends $g_j = c \cdot v$ for any direction $v$ and any scalar $c$. Then

and as $c \to \infty$ the aggregate runs off to infinity along $v$. One worker out of a thousand, out of a million, suffices. The breakdown point of the mean is $1/N$, which tends to zero as the fleet grows; in the limit, the most widely scaled aggregation rule in this book is the least robust one. This is the formal statement of the Section 35.4 attack, and it connects directly to the Byzantine fault tolerance and consensus material of Chapter 2: just as a replicated state machine cannot agree if it counts every vote naively, a fleet cannot aggregate if it averages every update naively.

2. Median and Trimmed Mean: Robustness Coordinate by Coordinate Intermediate

The oldest fix in robust statistics is to replace the mean with the median, and it ports directly to vectors if we apply it independently along each coordinate. The coordinate-wise median aggregate $\hat{g}$ has entries

The median of a list does not move until more than half of its entries move, so its breakdown point is $1/2$: the coordinate-wise median tolerates any $f < N/2$ Byzantine workers, because along each coordinate the honest majority still owns the middle order statistic. The coordinate-wise trimmed mean reaches the same regime with smoother behavior. Fixing a trim count $\beta$ with $f \le \beta < N/2$, it discards the $\beta$ largest and $\beta$ smallest values along each coordinate and averages what remains:

Discarding the $\beta$ extremes on each side throws away any value an adversary placed at the tail, so the surviving average is computed over honest-dominated entries. Both estimators share a weakness that matters for high-dimensional models: they decide each coordinate in isolation, so a clever adversary can stay just inside the kept band on every coordinate while still pushing a coherent direction. They also blur the honest signal, because the median and the trimmed mean are less statistically efficient than the mean when the data really are clean. That loss of efficiency is the price of the positive breakdown point, and Code 35.5.1 measures it directly.

3. Krum: Trust the Update That Looks Like Its Neighbors Advanced

Median and trimming work coordinate by coordinate; Krum instead treats each worker's update as a single point in $\mathbb{R}^d$ and asks which point sits deepest inside the crowd. For each candidate $i$, let $i \to j$ denote the set of the $N - f - 2$ other workers closest to $i$ in Euclidean distance, and define the Krum score as the sum of squared distances to exactly those closest neighbors,

Krum selects the single update with the smallest score, $\hat{g} = g_{i^\star}$ where $i^\star = \arg\min_i s(i)$. The intuition is that an honest update is near the $N - f$ other honest updates, so its sum of distances to its closest $N - f - 2$ neighbors is small; a Byzantine update that sits far away to do damage is also far from those same honest points and scores poorly. The neighbor count $N - f - 2$ is chosen so the sum is taken only over points that an honest worker is guaranteed to be close to even when $f$ of the workers collude. Krum's guarantee is tighter than the median's: it requires $2f + 2 < N$, that is $f < (N-2)/2$, and is usually quoted as tolerating $f < N/3$ in the regimes where its convergence proof is clean. Because it returns one actual worker's vector, Krum never invents a value in between, which helps in non-convex landscapes but throws away the averaging that makes clean training fast. Multi-Krum recovers some of that speed by selecting the $m$ lowest-scoring updates and averaging them, interpolating between single-Krum robustness and FedAvg efficiency as $m$ ranges from $1$ to $N - f$.

The demonstration below pits all three robust rules against the plain mean on a fleet of twenty workers, six of which are Byzantine and collude on a single wrong direction. The honest workers cluster around a target gradient; we measure each aggregate by its distance to the mean the honest workers alone would have produced.

import numpy as np

rng = np.random.default_rng(7)
N, d = 20, 100            # workers, gradient dimension
f = 6                     # Byzantine workers among the 20
g_true = rng.standard_normal(d)   # the direction honest workers concentrate around

# Honest updates: a tight cloud around g_true.
honest = g_true + 0.15 * rng.standard_normal((N - f, d))
# Byzantine updates: a large coordinated push in a fixed wrong direction.
attack = -8.0 * g_true + 0.15 * rng.standard_normal((f, d))
U = np.vstack([honest, attack])          # server sees all N rows, identities unknown
rng.shuffle(U)

honest_mean = honest.mean(axis=0)        # the answer a clean fleet would produce
def err(v): return float(np.linalg.norm(v - honest_mean))

# Plain mean: the non-robust baseline (FedAvg / all-reduce mean).
plain = U.mean(axis=0)

# Coordinate-wise median: per-coordinate middle order statistic.
cw_median = np.median(U, axis=0)

# Coordinate-wise trimmed mean: drop the f largest and f smallest per coordinate.
S = np.sort(U, axis=0)
trimmed = S[f:N - f].mean(axis=0)

# Krum: pick the update whose sum of squared distances to its
# closest N - f - 2 neighbors is smallest.
D2 = ((U[:, None, :] - U[None, :, :]) ** 2).sum(axis=2)   # pairwise squared distances
m = N - f - 2
scores = np.array([np.sort(D2[i])[1:m + 1].sum() for i in range(N)])  # skip self (the 0)
krum = U[int(np.argmin(scores))]

print(f"workers N            : {N}   (Byzantine f = {f}, fraction {f/N:.0%})")
print(f"plain mean   error   : {err(plain):8.3f}")
print(f"coord median error   : {err(cw_median):8.3f}")
print(f"trimmed mean error   : {err(trimmed):8.3f}")
print(f"Krum         error   : {err(krum):8.3f}")
sel = "Byzantine" if (krum @ g_true) < 0 else "honest"
print(f"Krum selected a worker that is {sel}")

workers N            : 20   (Byzantine f = 6, fraction 30%)
plain mean   error   :   24.052
coord median error   :    0.815
trimmed mean error   :    0.960
Krum         error   :    1.206
Krum selected a worker that is honest

4. Geometric Median and Bulyan: Stronger Rules at Higher Cost Advanced

The coordinate-wise median has the weakness that it judges each axis separately. The geometric median fixes this by minimizing total Euclidean distance jointly across all coordinates,

which is rotation-invariant and has breakdown point close to $1/2$. It has no closed form, but the classical Weiszfeld iteration converges quickly, and approximate geometric-median aggregators such as RFA are used in production federated systems. Bulyan goes further by composing two defenses: it first runs Multi-Krum to select a robust shortlist of candidate updates, then applies a coordinate-wise trimmed mean over that shortlist. Layering catches the failure mode of single Krum, where an attacker crafts an update that is near the honest cluster in aggregate distance yet skews one coordinate hard; the trimming step at the end removes that per-coordinate skew. Bulyan inherits the tightest requirement of the family, roughly $N \ge 4f + 3$, which is the cost of its stronger guarantee. The whole family, from median through Bulyan, is summarized in Table 35.5.1.

# pip install flwr
import flwr as fl

# Plain, non-robust baseline:  strategy = fl.server.strategy.FedAvg()
# Byzantine-robust drop-in replacements, same Strategy interface:
strategy = fl.server.strategy.Krum(num_malicious_clients=6, num_clients_to_keep=1)
# or fl.server.strategy.FedTrimmedAvg(beta=0.2)   # coordinate-wise trimmed mean
# or fl.server.strategy.Bulyan(num_malicious_clients=6)

fl.server.start_server(config=fl.server.ServerConfig(num_rounds=20), strategy=strategy)

5. The Two Tensions: Secure Aggregation and Non-IID Data Advanced

Robust aggregation does not compose freely with the other guarantees a fleet wants. The first tension is with secure aggregation, the cryptographic protocol from Chapter 14 that lets the server learn only the sum of client updates, never any individual one, to protect privacy. Every robust rule in this section needs to inspect individual updates: the median compares per-coordinate values, Krum computes pairwise distances, trimming sorts each axis. A server that can only see the masked sum cannot run any of them directly. Reconciling the two is an active research problem, addressed by computing robust statistics inside multi-party computation, by verifiable distance proofs, or by having clients cluster themselves before masking. The second tension is with non-IID data, the realistic case in federated learning where each client's gradient legitimately differs because its local distribution differs. A robust rule cannot tell a genuinely heterogeneous honest update from a malicious one by distance alone, so it may discard the very clients whose data is rarest and most valuable. The more non-IID the fleet, the wider the honest cluster in Figure 35.5.1, and the harder it is to draw a boundary that keeps every honest worker inside while keeping every attacker out.