Home / Curated / Algorithms / RFA Robust Federated Aggregation via Smoothed Weiszfeld Geometric Median

RFA Robust Federated Aggregation via Smoothed Weiszfeld Geometric Median

Algorithms AIMech:RfaRobustFederatedAggregationSmoothedWeiszfeldGeometricMedian DRAFT

Aliases: RFA, Robust Federated Aggregation, Smoothed Weiszfeld Geometric Median Federated Aggregation, One-Step RFA

A Byzantine-robust and secure-aggregation-compatible federated learning algorithm (RFA, Algorithm 1) that replaces the weighted arithmetic mean in FedAvg with an approximate weighted l_2 geometric median (GM) argmin_{v in R^d} sum_{i in S_t} alpha_i ||v - w_i^{(t)}||_2 computed via R steps of the Smoothed Weiszfeld algorithm (Algorithm 2). At each inner iteration r = 0,...,R-1, the server and clients execute a linear Secure Average oracle call to form v^{(r+1)} = (sum_{i in S_t} beta_i^{(r)} w_i^{(t)}) / (sum_{i in S_t} beta_i^{(r)}) with smoothed inverse-distance weights beta_i^{(r)} = alpha_i / max(nu, ||v^{(r)} - w_i^{(t)}||_2) for smoothing parameter nu > 0, alongside communication-reduced One-Step RFA (R = 1, Algorithm 3) and Personalized RFA (Algorithm 4).

Identity Notes & Concept Scope Distinct from Coordinate-wise Median and Trimmed Mean (AIMech:CoordinateWiseMedianAndTrimmedMeanByzantineRobustDistributedLearning, which compute coordinate-separable l_1 medians or trimmed means that cannot be implemented via a small number of linear Secure Aggregation sum queries and lack rotation equivariance) and from Krum (AIMech:KrumAndMultiKrumByzantineTolerantGradientDescent, which requires server inspection of all O(m^2) pairwise client model distances, incompatible with cryptographic Secure Average oracles).

Claims & Grounded Evidence

4 Claims

Mechanism #r402-smoothed-weiszfeld-surrogate-convergence-and-secure-aggregation-privacy

Algorithm 2 derives the Smoothed Weiszfeld update as exact alternating minimization of the jointly convex surrogate G(v, eta) = (1/2) sum_{i=1}^m alpha_i (||v - w_i||_2^2 / eta_i + eta_i) over v in R^d and eta_i >= nu, with Proposition 2 proving O(1 / (nu_bar R)) convergence to the geometric median objective and Proposition 3 bounding each device's normalized weight beta_i^{(r)} / sum_j beta_j^{(r)} <= (1 + (m - 1) nu_bar / B)^{-1} across R linear Secure Average oracle calls.

supports Source: Robust Aggregation for Federated Learning · Locator: Section IV The RFA Algorithm and Convergence (Algorithm 2, Propositions 2 and 3), pp. 1144-1146

Mechanism #r402-corruption-tolerance-up-to-half-and-heterogeneous-local-sgd-convergence

For corruption level rho < 1/2 (measuring the total weight of corrupted devices), Theorem 4 proves that RFA with tail-averaged local SGD on strongly convex least-squares objectives achieves linear convergence in communication rounds T up to a neighborhood controlled by geometric median tolerance epsilon^2 / m^2, local SGD noise sigma^2 / N_0, and bounded input/output heterogeneity Omega^2 = Omega_X^2 * Omega_{Y|X}^2, amplified by (1 - 2*rho)^{-2} (or (1 - 2*rho)^{-4} when rho > 1/3).

supports Source: Robust Aggregation for Federated Learning · Locator: Section IV-A Convergence Analysis (Assumptions 1-3, Theorem 4, Corollary 5), pp. 1146-1148

Limitation #r402-r-round-secure-average-communication-overhead-and-heterogeneity-amplification-limitation

Executing R steps of the Smoothed Weiszfeld algorithm increases per-round communication and cryptographic Secure Average invocations by a factor of R (unless approximated by One-Step RFA with R = 1), and the heterogeneity neighborhood in Theorem 4 scales with (1 - 2*rho)^{-4} as the corruption fraction rho approaches the 1/2 breakdown point.

supports Source: Robust Aggregation for Federated Learning · Locator: Section IV Proposition 3, Section IV-A Theorem 4, and Section IV-B Practical Extensions (Algorithms 3-4), pp. 1145-1148

Application #r402-femnist-sent140-and-shakespeare-corruption-defense-application

Evaluated on federated character recognition (EMNIST), sentiment analysis (Sent140), and character-level language modeling (Shakespeare) under data poisoning, label flipping, and omniscient parameter corruption up to rho < 1/2, outperforming FedAvg and Coordinate-wise Median with 3 steps of Smoothed Weiszfeld or One-Step RFA.

supports Source: Robust Aggregation for Federated Learning · Locator: Section V Numerical Experiments (Figures 2-6, Table I), pp. 1148-1152

⚠️ Curated Limitations & Negative Results

Multi-step Smoothed Weiszfeld requires R sequential rounds of linear Secure Aggregation per federated update.
Theoretical error bounds degrade by (1 - 2*rho)^{-4} as the corrupted device weight fraction rho approaches 1/2.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	narrow_match	RFA is a geometric-median-based Byzantine-robust aggregation algorithm for FederatedLearning compatible with secure aggregation.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r402-primary-pdf`	Robust Aggregation for Federated Learning Krishna Pillutla, Sham M. Kakade, Zaid Harchaoui	primary paper full_text	ID: https://doi.org/10.1109/TSP.2022.3153135 sha256:4f53ba8e0d4f…
`r402-arxiv-abs`	Robust Aggregation for Federated Learning (arXiv abstract) Krishna Pillutla, Sham M. Kakade, Zaid Harchaoui	primary paper abstract_only	ID: https://arxiv.org/abs/1912.13445 sha256:1241ddb7cee6…
`r402-metadata-cr`	Robust Aggregation for Federated Learning (Crossref metadata) Krishna Pillutla, Sham M. Kakade, Zaid Harchaoui	primary paper abstract_only	ID: https://doi.org/10.1109/TSP.2022.3153135 sha256:d6f202803142…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T08:05:00Z

Updated: 2026-10-19T08:05:00Z

Source File: data/curated/RfaRobustFederatedAggregationSmoothedWeiszfeldGeometricMedian.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories