Covariance-bound Agnostic Filter (CAF)#

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

Description#

Implements the Covariance-bound Agnostic Filter (CAF) [1], a robust aggregator designed to tolerate Byzantine inputs without requiring a bound on the covariance of honest vectors.

The algorithm iteratively estimates a robust mean by downweighting samples whose deviations from the mean are aligned with the dominant eigenvector of the empirical covariance matrix.

Precisely, given a set of input vectors \(x_1, \dots, x_n \in \mathbb{R}^d\), the algorithm proceeds as follows:

  1. Initialize weights \(c_i = 1\) for all \(i \in [n]\).

  2. Repeat until the total weight \(\sum_i c_i \leq n - 2f\):

    • Compute the weighted empirical mean:

      \[\mu_c = \frac{1}{\sum_i c_i} \sum_{i=1}^n c_i x_i\]

    • Using the power method [2], compute the dominant eigenvector \(v\) and maximum eigenvalue \(\lambda_{max}\) of the empirical covariance matrix:

      \[\Sigma_c = \frac{1}{\sum_i c_i} \sum_{i=1}^n c_i (x_i - \mu_c)(x_i - \mu_c)^\top\]

    • For each vector, compute the projection squared:

      \[\tau_i = ((x_i - \mu_c)^\top v)^2\]

    • Downweight outliers:

      \[c_i \leftarrow c_i \cdot \left(1 - \frac{\tau_i}{\max_j \tau_j}\right)\]

  3. Return the empirical mean \(\mu_c\) corresponding to the smallest maximum eigenvalue \(\lambda_{max}\) encountered.

This algorithm does not assume any upper bound on the spectral norm of the covariance matrix and is especially suited to settings with high-dimensional or heterogeneously distributed data.

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.CAF(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([4. 5. 6.])

Using torch tensors

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

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([4., 5., 6.])

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([4., 5., 6.])

References

On this page