Median Aggregation

Median Aggregation is a Byzantine-robust aggregation rule for federated learning that takes the coordinate-wise median of client updates — for each gradient coordinate, the median value across all clients is selected, making the aggregation resilient to outlier or adversarial updates.

Median Aggregation Details

• Coordinate-Wise: For each dimension $i$: $\hat{g}_i = \text{median}(g_{1,i}, g_{2,i}, \ldots, g_{n,i})$.
• Robustness: Tolerates up to $f < n/2$ Byzantine clients — the median is determined by the honest majority.
• Geometric Median: Alternative — find the point minimizing the sum of distances to all updates (considers dimension correlations).
• Computational: Coordinate-wise median is $O(n \log n)$ per dimension. Geometric median requires iterative optimization.

Why It Matters

• Simple and Effective: Drop-in replacement for simple averaging — just change mean to median.
• Breakdown Point: The median has a breakdown point of 50% — can tolerate up to half the values being adversarial.
• Baseline: Often used as the baseline robust aggregation method for comparison.

Median Aggregation is the majority vote for gradients — selecting the middle value to ignore extreme outliers from malicious or faulty clients.