Byzantine-Robust Aggregation Methods

While Federated Averaging (FedAvg) provides a simple mechanism for aggregating client contributions, its reliance on a standard mean calculation makes it highly susceptible to disruptions. In environments where some participants might be faulty or actively malicious (so-called Byzantine clients), FedAvg can be easily compromised. A single client submitting a carefully crafted, arbitrarily large, or simply nonsensical update can drastically shift the global model away from the optimal solution, potentially causing divergence or even introducing hidden backdoors. This vulnerability necessitates aggregation strategies designed specifically to withstand such adversarial behavior.

The core idea of Byzantine-robust aggregation is borrowed from robust statistics. Instead of using the arithmetic mean, which is sensitive to outliers, these methods employ estimators that are less affected by extreme values. The goal is to identify and downweight or discard updates that appear anomalous compared to the majority, assuming that Byzantine clients constitute a minority and their updates deviate significantly from those submitted by honest clients.

Let's examine several aggregation methods:

Coordinate-wise Median

Perhaps the simplest alternative to the mean is the coordinate-wise median. Instead of averaging the update vectors component by component, we compute the median for each coordinate across all received client updates.

Suppose we receive $n$ update vectors $v_1, v_2, ..., v_n$, each of dimension $d$. The aggregated update $v_{agg}$ is computed such that its $j$-th component ($v_{agg, j}$) is the median of the $j$-th components of all received updates:

$v_{agg, j} = \text{median}(v_{1,j}, v_{2,j}, ..., v_{n,j})$

for each dimension $j = 1, ..., d$.

This approach is computationally efficient, significantly faster than more complex methods like the geometric median. While its theoretical guarantees are sometimes weaker, it often performs well in practice and can tolerate a fraction of nearly 50% Byzantine clients under certain assumptions. Its primary weakness is that it treats each dimension independently, potentially missing malicious updates crafted across multiple dimensions in a correlated way.

Trimmed Mean

The Trimmed Mean offers another computationally reasonable approach. It works by discarding a fraction of the updates deemed most likely to be outliers before calculating the mean of the remaining ones.

Specifically, for each coordinate $j$, the server sorts the values $v_{1,j}, v_{2,j}, ..., v_{n,j}$. Assuming an upper bound $\beta$ on the fraction of expected Byzantine clients, the server removes the $\beta n$ smallest and $\beta n$ largest values for that coordinate. The $j$-th component of the aggregated update $v_{agg, j}$ is then the mean of the remaining $(1 - 2\beta)n$ values.

The effectiveness of Trimmed Mean hinges on correctly estimating $\beta$. If $\beta$ is set too low, the aggregation might still be vulnerable to Byzantine influence. If set too high, updates from honest clients might be unnecessarily discarded, potentially slowing down convergence or reducing model quality, especially in highly heterogeneous (Non-IID) settings where honest updates might naturally have large variations.

Krum and Multi-Krum

Krum takes a different approach by selecting a single update deemed most "representative" or "central". It assumes that honest clients' updates will be relatively close to each other in the parameter space, while Byzantine updates will be outliers.

For each received update $v_i$, Krum calculates a score based on the sum of squared Euclidean distances to its $k$ nearest neighbors among the other updates. Let $N_k(i)$ be the set of indices of the $k$ updates closest to $v_i$ (excluding $v_i$ itself). The score for $v_i$ is:

$score(i) = \sum_{l \in N_k(i)} ||v_i - v_l||_2^2$

The server then selects the single update $v_{i^*}$ with the minimum score as the aggregated result for the round:

$i^* = \arg \min_i score(i)$ $v_{agg} = v_{i^*}$

The parameter $k$ must be chosen carefully based on the assumed maximum number $f$ of Byzantine clients, typically $k = n - f - 2$, ensuring that the neighborhood calculation for the best honest client excludes all Byzantine clients.

Krum guarantees robustness if the number of Byzantine clients is less than $(n - k - 1) / 2$. However, selecting only one update can lead to slow convergence or instability. Multi-Krum addresses this by selecting the $m$ updates with the lowest Krum scores (where $m$ is typically small, e.g., $m=5$ or $m=10$) and averaging them. This often provides a better balance between robustness and stability.

Illustration of Krum. Honest updates (blue) cluster together, while Byzantine updates (red) are outliers. Krum identifies an update (e.g., the filled blue circle) whose nearest neighbors are close by, indicating it's likely honest.

Other Aggregators (Geometric Median, Bulyan)

• Geometric Median: Finds a point $w$ that minimizes the sum of Euclidean distances to all client updates $v_i$: $w = \arg \min_w \sum_{i=1}^n ||w - v_i||_2$. It has strong theoretical robustness (tolerating up to 50% Byzantine clients) but is computationally expensive as it requires an iterative optimization process.
• Bulyan: A more complex method that combines Krum-like selection stages with coordinate-wise median or trimmed mean filtering in an iterative process. It achieves high theoretical robustness but comes with significant computational overhead.

Practical Considerations and Trade-offs

Choosing an aggregator involves several trade-offs:

1. Robustness vs. Computation: Methods like Coordinate-wise Median and Trimmed Mean are computationally cheaper than Krum, Geometric Median, or Bulyan, but may offer weaker theoretical guarantees or require careful parameter tuning (like $\beta$ in Trimmed Mean).
2. Assumptions: Most methods assume Byzantine updates are outliers. Sophisticated attackers might try to craft updates that lie within the cluster of honest updates, potentially evading detection by distance-based methods like Krum.
3. Impact on Convergence: Aggregators can sometimes slow down convergence compared to FedAvg when no attack is present. This is because they might discard valid updates, especially in Non-IID scenarios where honest client updates naturally exhibit high variance.
4. Parameter Tuning: Krum requires setting $k$ based on an estimate of the number of attackers $f$. Trimmed Mean requires setting the trimming fraction $\beta$. Incorrect estimates can degrade performance or robustness.

In practice, the choice depends heavily on the specific application, the anticipated threat level, the computational resources available at the server, and the degree of statistical heterogeneity across clients. If Byzantine attacks are a significant concern, the computational overhead of methods like Coordinate-wise Median, Trimmed Mean, or Multi-Krum is often a worthwhile investment compared to the potential failure of standard FedAvg. These advanced aggregation rules are essential tools for building dependable federated learning systems in potentially adversarial environments.