Geometric Median#

class byzfl.GeometricMedian(nu=0.1, T=3)[source]#

Description#

Apply the smoothed Weiszfeld algorithm [1] to obtain the approximate geometric median \(y\):

\[\mathrm{GeometricMedian}_{\nu, T} \ (x_1, \dots, x_n) \in \argmin_{y \in \mathbb{R}^d}\sum_{i = 1}^{n} \big|\big|y - x_i\big|\big|_2\]

where

  • \(x_1, \dots, x_n\) are the input vectors, which conceptually correspond to gradients submitted by honest and Byzantine participants during a training iteration.

  • \(\big|\big|.\big|\big|_2\) denotes the \(\ell_2\)-norm.

  • \(d\) is the dimensionality of the input space, i.e., \(d\) is the number of coordinates of vectors \(x_1, \dots, x_n\).

Initialization parameters:

  • nu (float, optional) – Smoothing parameter. Set to 0.1 by default.

  • T (int, optional) – Number of iterations of the smoothed Weiszfeld algorithm. Set to 3 by default.

Calling the instance

Input parameters:

vectors (numpy.ndarray, torch.Tensor, list of numpy.ndarray or list of torch.Tensor) – A set of vectors, matrix or tensors.

Returns:

numpy.ndarray or torch.Tensor – The data type of the output will be the same as the input.

Examples

>>> import byzfl
>>> agg = byzfl.GeometricMedian()

Using numpy arrays

>>> import numpy as np
>>> x = np.array([[1., 2., 3.],       # np.ndarray
>>>               [4., 5., 6.],
>>>               [7., 8., 9.]])
>>> agg(x)
array([3.78788764 4.78788764 5.78788764])

Using torch tensors

>>> import torch
>>> x = torch.tensor([[1., 2., 3.],   # torch.tensor
>>>                   [4., 5., 6.],
>>>                   [7., 8., 9.]])
>>> agg(x)
tensor([3.7879, 4.7879, 5.7879])

Using list of numpy arrays

>>> import numpy as np
>>> x = [np.array([1., 2., 3.]),      # list of np.ndarray
>>>      np.array([4., 5., 6.]),
>>>      np.array([7., 8., 9.])]
>>> agg(x)
array([3.78788764 4.78788764 5.78788764])

Using list of torch tensors

>>> import torch
>>> x = [torch.tensor([1., 2., 3.]),  # list of torch.tensor
>>>      torch.tensor([4., 5., 6.]),
>>>      torch.tensor([7., 8., 9.])]
>>> agg(x)
tensor([3.7879, 4.7879, 5.7879])

References

On this page