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\) by default. With \(m = 1\) it reduces to Bulyan(Krum).

Note

Krum scores are recomputed at every iteration on the remaining candidates, following Algorithm 1 in the paper: removed gradients leave the distance matrix, so each iteration scores the \(n - i\) remaining candidates on their \(n - i - f - 2\) closest peers.

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 0 <= 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.