ByRDiE Byzantine-Resilient Distributed Coordinate Descent for Decentralized Learning
Algorithms AIMech:ByrdieByzantineResilientDistributedCoordinateDescentForDecentralizedLearning DRAFT
Aliases: ByRDiE, Byzantine-Resilient Distributed Coordinate Descent, ByRDiE Decentralized Coordinate Descent
A Byzantine-resilient decentralized optimization algorithm (ByRDiE) that decomposes a P-dimensional empirical risk minimization problem across a directed network G(J, E) with up to b Byzantine nodes into an outer coordinate-descent loop over coordinates k in {1, ..., P} and an inner T-step scalar screening loop in which each nonfaulty node j in J' discards the b smallest (N_j^s) and b largest (N_j^l) received neighbor scalars [w_i^r(t)]_k before averaging the remaining |N_j| - 2b + 1 values (including self) and stepping along its local coordinate gradient -[grad f_hat(w_j^r(t), S_j)]_k.
Identity Notes & Concept Scope
Introduced by Zhixiong Yang and Waheed U. Bajwa (IEEE Transactions on Signal and Information Processing over Networks, Vol. 5, No. 4, pp. 611-627, 2019; arXiv:1708.08155). Distinct from BRIDGE (Fang, Yang, & Bajwa, IEEE TSIPN 2022, Round 546), which performs simultaneous full-vector gradient descent with coordinate-wise trimmed mean in a single loop rather than sequential coordinate-by-coordinate T-step inner updates; and distinct from ClippedGossip (He, Karimireddy, & Jaggi, 2022, Round 545), which clips neighbor model differences in L2 norm around a node's own iterate.
Claims & Grounded Evidence
4 Claims
Mechanism
#byrdie-coordinate-wise-trimmed-screening-and-stochastic-transition-mechanism
For each coordinate k in {1, ..., P} and inner step t in {1, ..., T}, each nonfaulty node j in J' partitions its incoming neighborhood N_j into the b smallest values N_j^s(r, k, t), the b largest values N_j^l(r, k, t), and the screened set N_j^*(r, k, t) = N_j \ N_j^s \ N_j^l, updating [w_j^r(t+1)]_k = (1 / (|N_j| - 2b + 1)) sum_{i in N_j^* U {j}} [w_i^r(t)]_k - rho(r + t - 1) [grad f_hat(w_j^r(t), S_j)]_k so that any retained Byzantine value is expressible as a convex combination of two trimmed nonfaulty neighbor values.
Scope
#byrdie-consensus-and-statistical-risk-convergence-scope
When every reduced graph G_r obtained by removing all b Byzantine nodes and up to b additional incoming edges per nonfaulty node contains a source component of size at least b + 1, ByRDiE achieves consensus at rate O(sqrt(P) * rho(r)) and converges in probability to the statistical risk minimizer w* with effective sample size N_eff = N / a_bar^2 in [N, |J'|*N] for both T -> infinity and T = 1.
Limitation
#byrdie-sequential-coordinate-communication-latency-limitation
Because ByRDiE updates and screens one coordinate k in {1, ..., P} at a time, each outer pass requires T * P sequential scalar communication rounds tc = (r - 1)*T*P + (k - 1)*T + t, and certifying the reduced-graph source-component condition (Assumption 3) is combinatorially hard on general directed graphs.
Application
#byrdie-decentralized-svm-and-neural-network-application
Applied to Byzantine-resilient decentralized linear SVM classification on the infinite MNIST dataset and decentralized multi-layer neural network classification on the Iris dataset under 10%-20% Byzantine node failures.
⚠️ Curated Limitations & Negative Results
- Requires at least 2b + 1 incoming neighbors per nonfaulty node so that |N_j| - 2b + 1 >= 1 after trimming b smallest and b largest values.
- Incurs P * T sequential scalar communication rounds per full coordinate cycle.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:FederatedLearning
Federated Learning
|
related_match | AIO:FederatedLearning covers collaborative distributed training, whereas ByRDiE is a serverless Byzantine-resilient coordinate-descent algorithm with two-sided scalar neighborhood screening. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r551-primary-pdf
|
Zhixiong Yang, Waheed U. Bajwa
|
primary paper
full_text
|
ID: https://dblp.org/rec/journals/tsipn/YangB19
sha256:ccf7bf274194…
|
r551-arxiv-abs
|
Zhixiong Yang, Waheed U. Bajwa
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/1708.08155
sha256:7676f11341d5…
|
r551-metadata-cr
|
Zhixiong Yang, Waheed U. Bajwa
|
primary paper
abstract_only
|
ID: https://dblp.org/rec/journals/tsipn/YangB19
sha256:27210c861ca8…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T10:34:00Z
Updated: 2026-10-19T10:34:00Z
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