AKSEL#

AKSEL aggregation rule, median-pivot nearest-neighbor averaging.

Reference:

Amine Boussetta, El-Mahdi El-Mhamdi, Rachid Guerraoui, Alexandre Maurer, and Sébastien Rouault. “AKSEL: Fast Byzantine SGD.” In 24th International Conference on Principles of Distributed Systems (OPODIS 2020), Leibniz International Proceedings in Informatics, Volume 184, pp. 8:1–8:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021).

class krum.primitives.aggregators.aksel.Aksel[source]#

Bases: Aggregator

AKSEL aggregation rule, median-pivot nearest-neighbor averaging.

AKSEL computes the coordinate-wise median of the \(n\) worker gradients as a robust pivot, then selects the \(n - f\) gradients closest to this pivot (by Euclidean distance) and returns their mean.

This achieves optimal time complexity \(\mathcal{O}(nd)\), an optimal breakdown point \(n > 2f\), and the lowest known upper bound on the expected angular error \(\mathcal{O}(\sqrt{d})\) among full-gradient approaches.

classmethod aggregate(gradients: Sequence[Tensor] | Tensor, /, out: Tensor | None = None, *, f: int, **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.

  • f – Number of Byzantine workers to tolerate. Must satisfy \(0 \le f\) and len(gradients) > 2f.

  • **specialized – Additional keyword arguments.

Returns:

  • Mean of the :math:`n - f` gradients closest to the coordinate-wise

  • median, of shape `` (d,)

Raises:

ValueError – If \(f\) is negative or if there are not enough gradients (len(gradients) <= 2f).

See also

For a simple mean baseline, see Average. For coordinate-wise median, see Median. For distance-based selection, see Krum or Bulyan.