Home / Curated / Algorithms / Zeno Suspicion-Based Fault-Tolerant Distributed Stochastic Gradient Descent

Zeno Suspicion-Based Fault-Tolerant Distributed Stochastic Gradient Descent

Algorithms AIMech:ZenoSuspicionBasedFaultTolerantDistributedStochasticGradientDescent DRAFT

Aliases: Zeno, Zeno Distributed SGD, Zeno Suspicion-Based Aggregation, Stochastic Descendant Score Aggregation

A Byzantine-tolerant synchronous distributed stochastic gradient descent algorithm in which the parameter server samples a small validation mini-batch f_r(x) = (1/n_r) sum_{i=1}^{n_r} f(x; z_i) at each iteration, computes a regularized stochastic descendant score Score_{gamma, rho}(u, x) = f_r(x) - f_r(x - gamma * u) - rho * ||u||^2 for each of the m worker gradient candidates {tilde_v_i}, sorts candidates in descending score order, and averages the top m - b candidates (with m > b >= q) to update the global model.

Identity Notes & Concept Scope Distinct from majority-based geometric or coordinate-wise robust aggregation rules that require q < m/2 without a server validation loss check (Krum, Bulyan, Trimmed-Mean, Coordinate-Wise Median), and distinct from FLTrust (which computes a server reference gradient on a root dataset and ReLU-clips cosine similarities rather than evaluating loss descent f_r(x) - f_r(x - gamma u) - rho ||u||^2). Specifically denotes the Zeno algorithm of Xie, Koyejo, & Gupta (ICML 2019, PMLR 97:6893-6901, Definitions 2-3, Algorithm 1, Lemma 1, Theorem 1).

Claims & Grounded Evidence

3 Claims

Mechanism #r523-stochastic-descendant-score-and-top-subset-averaging

Using a validation mini-batch f_r(x) = (1/n_r) sum_{i=1}^{n_r} f(x; z_i) sampled after receiving worker candidate updates {tilde_v_i : i in [m]}, Zeno evaluates Score_{gamma, rho}(tilde_v_i, x) = f_r(x) - f_r(x - gamma * tilde_v_i) - rho * ||tilde_v_i||^2 (Definition 2) to reward loss decrease while penalizing update magnitude, sorts candidates as Score(tilde_v_{(1)}) >= ... >= Score(tilde_v_{(m)}), and outputs Zeno_b({tilde_v_i}) = (1/(m - b)) sum_{i=1}^{m-b} tilde_v_{(i)} (Definition 3).

supports Source: Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance · Locator: Section 3, Definitions 2-3 and Algorithm 1, p. 3

Scope #r523-dishonest-majority-nonconvex-convergence-guarantee

By Lemma 1, the i-th highest candidate score dominates the i-th highest honest worker score Score_{gamma, rho}(tilde_v_{(i)}, x) >= Score_{gamma, rho}(v_{(i)}, x) for all i in [m - q]; consequently, for any number of Byzantine workers q < m (including a dishonest majority q >= m/2) with m > b >= q, Theorem 1 and Corollaries 1-2 prove O(1/sqrt(T)) convergence to a stationary point of smooth non-convex objectives under both i.i.d. and disjoint non-i.i.d. worker data.

supports Source: Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance · Locator: Section 4, Lemma 1, Theorem 1, and Corollaries 1-2, p. 4; Appendix A, pp. 10-15

Limitation #r523-server-validation-batch-and-forward-pass-overhead

Zeno requires the central server to hold a trusted validation dataset from the target learning distribution and to evaluate the validation loss f_r(x - gamma * tilde_v_i) across all m candidate updates at every iteration.

supports Source: Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance · Locator: Section 3.1-3.2 and Section 4.1 Assumption 1, pp. 3-4

⚠️ Curated Limitations & Negative Results

Requires a clean validation dataset at the parameter server drawn from an unbiased target distribution.
Incurs m validation mini-batch forward evaluations f_r(x - gamma * tilde_v_i) on the server at every synchronous SGD step.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	broad_match	Zeno is a Byzantine-robust gradient aggregation rule for distributed and federated stochastic gradient descent.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r523-primary-pdf`	Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance Cong Xie, Oluwasanmi Koyejo, Indranil Gupta	primary paper full_text	ID: https://dblp.org/rec/conf/icml/XieKG19.json sha256:addb078699e5…
`r523-arxiv-abs`	Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance (arXiv abstract) Cong Xie, Oluwasanmi Koyejo, Indranil Gupta	primary paper abstract_only	ID: https://arxiv.org/abs/1805.10032 sha256:8b179e9bd6aa…
`r523-metadata-cr`	Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance (Crossref metadata) Cong Xie, Oluwasanmi Koyejo, Indranil Gupta	primary paper abstract_only	ID: https://dblp.org/rec/conf/icml/XieKG19.json sha256:800e006e941b…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

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

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

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