Home / Curated / Algorithms / Byrd-SAGA Byzantine-Resilient Distributed SAGA with Geometric Median Aggregation

Byrd-SAGA Byzantine-Resilient Distributed SAGA with Geometric Median Aggregation

Algorithms AIMech:ByrdSagaByzantineResilientDistributedSagaWithGeometricMedianAggregation DRAFT

Aliases: Byrd-SAGA, Byzantine Attack Resilient Distributed SAGA, Federated Variance-Reduced Byrd-SAGA

A Byzantine-resilient federated finite-sum optimization algorithm for minimizing f(x) = (1 / (W - B)) sum_{w notin B} (1 / J) sum_{j=1}^J f_{w,j}(x) across W workers Containing B < W / 2 Byzantine attackers, in which each honest worker w maintains a local table of stored per-sample gradients {f'_{w,j}(phi_{w,j}^k)}_{j=1}^J and their average g_bar_w^k = (1 / J) sum_{j=1}^J f'_{w,j}(phi_{w,j}^k), samples a random local index i_w^k in {1, ..., J} at iteration k, and transmits the SAGA variance-reduced gradient m_w^k = f'_{w,i_w^k}(x^k) - f'_{w,i_w^k}(phi_{w,i_w^k}^k) + g_bar_w^k to the master node, which updates the global model via the geometric median x^{k+1} = x^k - gamma * geomed_{w in W} {m_w^k}.

Identity Notes & Concept Scope Distinct from standard SAGA (AIMech:SagaStochasticAverageGradientAmeliore, which uses single-machine or fragile mean aggregation and fails under a single Byzantine worker) and from Byzantine-robust SGD aggregators such as Krum, Geometric Median SGD, Bulyan (AIMech:BulyanByzantineResilientGradientAggregation), RSA (AIMech:RsaByzantineRobustStochasticAggregationForHeterogeneousDatasets), and Bucketing (AIMech:BucketingForAgnosticByzantineRobustAggregationOnHeterogeneousDatasets): Byrd-SAGA (Wu, Ling, Chen, & Giannakis, IEEE TSP 2020) couples per-worker SAGA finite-sum variance reduction with server-side geometric median aggregation so that the inner stochastic gradient variance sigma^2 vanishes along the optimization trajectory, removing the O(C_alpha^2 sigma^2 / mu^2) asymptotic error floor of Byzantine-resilient SGD.

Claims & Grounded Evidence

3 Claims

Mechanism #byrd-saga-variance-reduced-geomed-update

At each iteration k, honest worker w samples i_w^k uniformly from {1, ..., J}, computes the SAGA-corrected gradient m_w^k = f'_{w,i_w^k}(x^k) - f'_{w,i_w^k}(phi_{w,i_w^k}^k) + g_bar_w^k, and updates its local gradient table entry and running average in O(p) time, while the master aggregates all W worker messages using an epsilon-approximate geometric median x^{k+1} = x^k - gamma * geomed_{w in W} {m_w^k}.

supports Source: Federated Variance-Reduced Stochastic Gradient Descent With Robustness to Byzantine Attacks · Locator: Section III-B p. 4 Eq. 8-11 & Algorithm 1

Scope #byrd-saga-linear-convergence-without-inner-variance-floor

For mu-strongly convex L-smooth objectives with bounded outer variation E_{w notin B} ||f'_w(x) - f'(x)||^2 <= delta^2 and B < W / 2 Byzantine workers (alpha = B / W < 1/2, C_alpha = (2 - 2 alpha) / (1 - 2 alpha)), Byrd-SAGA with step size gamma <= mu / (4 sqrt(5) J^2 C_alpha L^2) converges linearly as E||x^k - x*||^2 <= (1 - gamma mu / 2)^k Delta_1 + Delta_2 where Delta_2 = (10 / mu^2)(C_alpha^2 delta^2 + epsilon^2 / (W - 2B)^2), completely eliminating the inner-variance term O(C_alpha^2 sigma^2 / mu^2) present in Byzantine-resilient SGD (Theorems 1-2, Eq. 20-25).

supports Source: Federated Variance-Reduced Stochastic Gradient Descent With Robustness to Byzantine Attacks · Locator: Section IV-A Lemma 1 p. 5 Eq. 13; Section IV-B Theorems 1-2 p. 5-6 Eq. 20-25

Limitation #byrd-saga-memory-table-and-outer-heterogeneity-limitation

Byrd-SAGA requires each honest worker to store a table of J gradient vectors of dimension p (O(J p) local memory, or O(J) scalars for linear models), and under non-i.i.d. outer gradient variation delta^2 > 0 its asymptotic error floor Delta_2 = O(C_alpha^2 delta^2 / mu^2) remains non-zero and grows as the Byzantine fraction alpha = B / W approaches 1/2.

supports Source: Federated Variance-Reduced Stochastic Gradient Descent With Robustness to Byzantine Attacks · Locator: Section III-A p. 3-4; Section IV-B Theorem 1 p. 6 Eq. 20-22

⚠️ Curated Limitations & Negative Results

Requires each worker to store J historical gradients of dimension p in a local SAGA table (O(J p) memory per worker) and restricts the maximum step size by O(1 / J^2).
Retains an O(C_alpha^2 delta^2 / mu^2) asymptotic error neighborhood when honest workers have heterogeneous local data distributions (delta^2 > 0) and requires B < W / 2.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	Byrd-SAGA is a Byzantine-robust variance-reduced optimization method for federated finite-sum learning across distributed worker nodes.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r544-primary-pdf`	Federated Variance-Reduced Stochastic Gradient Descent With Robustness to Byzantine Attacks Zhaoxian Wu, Qing Ling, Tianyi Chen, Georgios B. Giannakis	primary paper full_text	ID: https://api.crossref.org/works/10.1109/TSP.2020.3012952 sha256:4e111043300d…
`r544-arxiv-abs`	Federated Variance-Reduced Stochastic Gradient Descent With Robustness to Byzantine Attacks (arXiv abstract) Zhaoxian Wu, Qing Ling, Tianyi Chen, Georgios B. Giannakis	primary paper abstract_only	ID: https://arxiv.org/abs/1912.12716 sha256:3f0c5c267be7…
`r544-metadata-cr`	Federated Variance-Reduced Stochastic Gradient Descent With Robustness to Byzantine Attacks (Crossref metadata) Zhaoxian Wu, Qing Ling, Tianyi Chen, Georgios B. Giannakis	primary paper abstract_only	ID: https://api.crossref.org/works/10.1109/TSP.2020.3012952 sha256:3b9fc66b6c87…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T10:27:00Z

Updated: 2026-10-19T10:27:00Z

Source File: data/curated/ByrdSagaByzantineResilientDistributedSagaWithGeometricMedianAggregation.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