Median Aggregation

The algorithm operates independently on each parameter dimension of the model update vector. For a given parameter (e.g., weight W_i), the server collects all values for W_i from the N client updates, sorts them, and selects the median value. This process is repeated for every parameter in the model. This per-coordinate approach is crucial because a malicious update may only corrupt a subset of parameters, and median aggregation can filter those specific dimensions without discarding the entire client contribution.

Median aggregation has a theoretical breakdown point of 50%. This means the global model update remains correct (unbiased towards the malicious values) as long as fewer than half of the participating clients in a given round are Byzantine (malicious or faulty). If malicious clients constitute a majority (>50%), they can control the median value. This property makes it suitable for scenarios with a known, bounded minority of adversaries.

• Key Implication: The system's robustness is defined by the client selection strategy for each round.

Unlike the mean, the median is highly resistant to extreme values. In federated learning, a malicious client can submit an update with arbitrarily large magnitudes (e.g., setting a parameter to 1,000,000) in an attempt to skew the global model. During coordinate-wise median calculation, this extreme value will simply sit at one end of the sorted list and be ignored, provided it's not the majority. This makes median aggregation a robust defense against sign-flipping attacks and scaling attacks, where adversaries multiply their updates by a large constant.

While robust, median aggregation can have slower convergence rates compared to FedAvg under non-IID (Independent and Identically Distributed) data. The median is a non-linear operator, and its application disrupts the theoretical convergence guarantees of standard stochastic gradient descent. Research shows it converges under assumptions of bounded client dissimilarity. In practice, it may require more communication rounds to achieve target accuracy, representing a trade-off between robustness and statistical efficiency.

The primary cost is computational on the server. For a model with P parameters and N client updates per round, the server must sort N values for each of the P parameters, leading to a time complexity of O(P * N log N). This is more expensive than FedAvg's O(P * N) but is generally manageable for the central server. Communication costs remain identical to standard federated learning: clients send full model updates, and the server broadcasts the new global model.

Pure coordinate-wise median is often enhanced or combined with other techniques:

• Trimmed Median: Discards a fraction of the highest and lowest values in each dimension before taking the median of the remainder, offering even higher robustness.
• Median-of-Means: Clients are partitioned into groups, the mean is computed within each group, and then the median of those group means is taken. This can improve statistical efficiency.
• Meta-Algorithms (Bulyan): Uses median (or other robust aggregators) to select a candidate set of updates, then applies a second aggregation (like trimmed mean) for final refinement.

A class of server-side algorithms designed to produce a correct global model update even when a predetermined fraction of participating clients are malicious or faulty and send arbitrary updates. This is the overarching defensive category to which Median Aggregation belongs.

• Goal: Achieve Byzantine fault tolerance in distributed optimization.
• Key Challenge: The server cannot trust individual updates and must aggregate them robustly.
• Examples: Includes Median, Krum, Bulyan, and Trimmed Mean.

A robust statistical aggregation rule where, for each model parameter (coordinate), the server discards a fraction (β) of the highest and lowest values from all client updates before computing the mean of the remaining values.

• Comparison to Median: More statistically efficient than the median when the distribution of honest updates is symmetric and outliers are few, but less robust to extreme outliers on both sides of the distribution.
• Parameter: The trimming fraction β must be set based on the expected fraction of malicious clients.

A Byzantine-robust aggregation rule that selects a single client's model update as the global update. It chooses the vector whose Euclidean distance to its nearest neighbors is the smallest, effectively filtering out statistical outliers.

• Mechanism: For each client update, sum the distances to its n - f - 2 closest neighbors, where n is total clients and f is the tolerated number of malicious clients. The update with the smallest sum is selected.
• Use Case: Highly effective when malicious updates are designed to be colluding and shift the mean, but computationally more expensive than coordinate-wise methods.

A meta-aggregation Byzantine defense that combines a robust selection rule with a robust averaging rule. First, it uses Krum or Multi-Krum to select a subset of candidate updates deemed trustworthy. Then, it applies a coordinate-wise trimmed mean to this subset to produce the final global update.

• Advantage: Provides stronger theoretical guarantees than Krum alone, as the second averaging step further mitigates the influence of any remaining outliers within the selected set.
• Robustness: Proven to be resilient against a higher proportion of adversarial clients under certain attack models.

A server-side defense technique that analyzes the statistics and distribution of submitted client model updates (gradients) to detect anomalies indicative of malicious behavior or poor data quality.

• Common Methods: Checking update norms (L2, L-infinity), comparing against a running mean/covariance, and using dimensionality reduction (like PCA) to visualize clusters of updates.
• Limitation: Sophisticated attacks can craft updates that appear statistically normal (stealthy poisoning) to evade simple inspection, necessitating more advanced geometric or spectral analysis.

A dynamic defense mechanism that assigns a credibility score to each federated client based on the historical quality and consistency of their updates. This score is then used to weight their contribution during aggregation.

• How it works: Scores can be based on update similarity to a robust aggregate (like the median), contribution to model improvement on a held-out validation set, or behavioral consistency over time.
• Synergy with Median: A trust score can be used to perform a weighted median, where updates from higher-trust clients have more influence, creating an adaptive, reputation-based robust aggregation system.