Smallest Maximum Eigenvalue Averaging (SMEA)#

class byzfl.SMEA(f=0)[source]#

Description#

Implements the Smallest Maximum Eigenvalue Averaging (SMEA) rule [1], a robust aggregation method that selects the subset of client vectors whose covariance has the lowest maximum eigenvalue, then returns their average.

Formally, given a set of input vectors \(x_1, \dots, x_n \in \mathbb{R}^d\) and an integer \(f\) representing the number of potential Byzantine vectors, the algorithm proceeds as follows:

  1. Enumerate all subsets \(S \subset [n]\) of size \(n - f\).

  2. For each subset \(S\), compute its empirical mean:

    \[\mu_S = \frac{1}{|S|} \sum_{i \in S} x_i\]

  3. Compute the empirical covariance matrix:

    \[\Sigma_S = \frac{1}{|S|} \sum_{i \in S} (x_i - \mu_S)(x_i - \mu_S)^\top\]

  4. Using the power method [2], compute the maximum eigenvalue \(\lambda_{\max}(\Sigma_S)\) of each subset’s covariance.

  5. Select the subset \(S^\star\) that minimizes the maximum eigenvalue:

    \[S^\star = \arg\min_{S: |S|=n-f} \lambda_{\max}(\Sigma_S)\]

  6. Return the empirical mean of the optimal subset \(S^\star\):

    \[\text{SMEA}(x_1, \dots, x_n) = \frac{1}{|S^\star|} \sum_{i \in S^\star} x_i\]

While computationally expensive due to its combinatorial nature, SMEA provides state-of-the-art robustness guarantees [1]. This method is thus particularly well-suited to federated settings where the number of clients is not too large.

Initialization parameters:

f (int, optional) – Number of faulty vectors. Set to 0 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.SMEA(1)

Using numpy arrays

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

Using torch tensors

>>> import torch
>>> x = torch.tensor([[1., 2., 3.],   # torch.tensor
>>>                   [4., 5., 6.],
>>>                   [7., 8., 9.]])
>>> agg(x)
tensor([2.5000, 3.5000, 4.5000])

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([2.5, 3.5, 4.5])

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([2.5000, 3.5000, 4.5000])

References

On this page