Bulyan#

Bulyan aggregation rule, two-stage Multi-Krum + trimmed mean.

Reference:: El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. “The Hidden Vulnerability of Distributed Learning in Byzantium.” In Proceedings of the 35th International Conference on Machine Learning (ICML 2018).

class krum.primitives.aggregators.bulyan.Bulyan[source]#

Bases: Aggregator

Bulyan aggregation rule, two-stage Multi-Krum + trimmed mean.

Bulyan first iteratively applies Multi-Krum to select a set \(S\) of \(\theta = n - 2f - 2\) aggregated vectors. At each iteration the Multi-Krum output (average of the \(m\) gradients with smallest Krum scores) is added to \(S\), and the gradient closest to that output is removed from the candidate pool. It then aggregates \(S\) coordinate-wise via TrimmedMean with the same \(f\), keeping \(\beta = \theta - 2f = n - 4f - 2\) values per coordinate.

This implementation uses Bulyan(MultiKrum) — i.e. the base aggregator is Multi-Krum with \(m = n - f - 2\) by default. With \(m = 1\) it reduces to Bulyan(Krum).

Note

Krum scores are computed once on the full candidate set and removed gradients are masked with inf rather than recomputing pairwise distances at every iteration. This is an approximation of Algorithm 1 in the paper: a removed gradient still appears in the distance matrix of the remaining workers, so individual scores do not get updated after each removal. The selection order may therefore differ slightly from the paper, though the impact on the final trimmed mean is minimal when the honest majority forms a tight cluster.

classmethod aggregate(gradients: Sequence[Tensor] | Tensor, /, out: Tensor | None = None, *, n: int, f: int, m: int | None = None, **specialized: Any) → Tensor[source]#

Aggregate the gradients.

Parameters:

gradients – Sequence of 1-D tensors containing gradients from workers.
out – Optional pre-allocated tensor to write the result into.
n – Total number of workers. Must satisfy \(n \ge 4f + 3\).
f – Number of Byzantine workers to tolerate. Must satisfy 1 <= f <= (n - 3) // 4.
m – Number of gradients selected by Multi-Krum at each iteration. Defaults to \(n - f\).
**specialized – Additional keyword arguments.

Returns:

Aggregated gradient of shape `` (d,)

Raises:

ValueError – If \(n\), \(f\), \(m\), or the gradients count is invalid.