Byzantine machine learning: exact robustness coefficients of aggregation rules, and their limits

par Gilles Bareilles (École Polytechnique)

mardi 20 oct. 2026, 11:15 → 12:15 Europe/Paris

Salle K. Johnson (1R3, 1er étage)

In distributed and federated learning, a server minimizes an average of losses by aggregating gradients sent by $n$ participants, $f$ of which may be adversarial ("Byzantine"): they can send arbitrary vectors, collude, and adapt to the honest ones. Replacing the average of gradients by a robust aggregation rule (trimmed mean, median, Krum, etc.) allows gradient descent to reach approximate critical points of the honest objective. The guaranteed accuracy depends on the rule only through a single statistical quantity: its robustness coefficient $\kappa^\star$, the worst-case error in estimating the honest mean, relative to the honest spread.

We compute $\kappa^\star$ exactly for several classical rules. The coordinate-wise trimmed mean is optimal: its coefficient matches the lower bound $f/(n-2f)$ that holds for any rule, and it remains optimal when the number of adversaries is overestimated. The coordinate-wise and geometric medians are worse by a factor of about $n/f$, in any dimension. Krum and MultiKrum, both widely used in practice, also have a finite robustness coefficient. Finally, comparing the theoretical and practical behavior of several aggregation rules reveals what the robustness coefficient misses; I will discuss ways to go beyond the worst case.