Home / Curated / Algorithms / Coordinate-wise Median and Trimmed Mean Byzantine-Robust Distributed Learning

Coordinate-wise Median and Trimmed Mean Byzantine-Robust Distributed Learning

Algorithms AIMech:CoordinateWiseMedianAndTrimmedMeanByzantineRobustDistributedLearning DRAFT

Aliases: Coordinate-wise Median Gradient Descent, Coordinate-wise Trimmed Mean Gradient Descent, Byzantine-Robust Coordinate-wise Trimmed Mean, Yin-Chen-Kannan-Bartlett Trimmed Mean and Median GD

A family of dimension-separable robust gradient and parameter aggregation algorithms for Byzantine-resilient distributed optimization across m worker machines with an alpha-fraction of adversarial workers (alpha < 1/2), comprising: (1) Coordinate-wise Median Gradient Descent, which updates w_{t+1} = w_t - eta * med{nabla F_i(w_t)}_{i=1}^m by taking the 1D median independently along each coordinate k in [d]; (2) Coordinate-wise beta-Trimmed Mean Gradient Descent (alpha <= beta < 1/2), which sorts the m worker values along each coordinate k, discards the largest beta*m and smallest beta*m values, and averages the remaining (1 - 2*beta)*m entries; and (3) One-round Coordinate-wise Median ERM aggregation w_hat = med{w_hat_i}_{i=1}^m for quadratic objectives.

Identity Notes & Concept Scope Distinct from Krum and Multi-Krum (AIMech:KrumAndMultiKrumByzantineTolerantGradientDescent, which select complete worker vectors via joint d-dimensional pairwise Euclidean distances in O(m^2 d) time rather than coordinate-wise 1D order statistics in O(m log m * d) or O(m d) time) and from RFA Smoothed Weiszfeld Geometric Median (AIMech:RfaRobustFederatedAggregationSmoothedWeiszfeldGeometricMedian, which computes the rotation-equivariant l_2 geometric median iteratively rather than coordinate-separable l_1 median or trimmed mean statistics).

Claims & Grounded Evidence

4 Claims

Mechanism #r400-trimmed-mean-order-optimal-statistical-error-rates

For v-sub-exponential gradient coordinates and trimming level alpha <= beta <= 1/2 - epsilon, Theorems 4, 5, and 6 prove that Coordinate-wise beta-Trimmed Mean GD achieves uniform gradient concentration O_tilde(v * sqrt(d) * (alpha / sqrt(n) + 1 / sqrt(n m))) and converges on strongly convex, non-strongly convex, and smooth nonconvex losses to the statistical error rate O_tilde(alpha / sqrt(n) + 1 / sqrt(n m)), matching the minimax information-theoretic lower bound Omega(alpha / sqrt(n) + sqrt(d / (n m))) of Observation 1 in sample dependency.

supports Source: Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates · Locator: Section 4.2 Guarantee for Trimmed Mean (Theorems 4-6), Section 6 Lower Bound (Observation 1), & Table 1, pp. 4-8

Mechanism #r400-coordinate-median-berry-esseen-skewness-and-one-round-erm-rate

Using a Berry-Esseen normal approximation in terms of the gradient skewness S, Theorems 1-3 prove that Coordinate-wise Median GD achieves statistical error O_tilde(alpha / sqrt(n) + 1 / sqrt(n m) + 1 / n) requiring only bounded 3rd central moments (skewness), while Algorithm 2 and Theorem 7 show that for quadratic losses a single round of coordinate-wise median parameter aggregation achieves O_tilde(d / sqrt(n m) + sqrt(d) / n + alpha * sqrt(d / n)).

supports Source: Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates · Locator: Section 4.1 Guarantee for Median (Theorems 1-3) & Section 5 One-Round Aggregation for Quadratic Loss (Algorithm 2, Theorem 7), pp. 4-8

Limitation #r400-skewness-bias-one-over-n-and-beta-knowledge-limitation

Coordinate-wise Median GD incurs an extra O(S / n) bias term when per-sample gradients have non-zero skewness S (Because the median of a skewed distribution differs from its mean by O(1/sqrt(n)) per worker), and Coordinate-wise beta-Trimmed Mean requires knowing an upper bound beta >= alpha on the Byzantine fraction alpha < 1/2.

supports Source: Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates · Locator: Section 3 Definition 2 & Section 4.1 Discussion of Theorem 1 and Skewness S, pp. 3-5

Application #r400-distributed-regression-and-classification-byzantine-defense-application

Provides order-optimal Byzantine-tolerant distributed gradient aggregation for strongly convex, convex, and nonconvex empirical risk minimization when up to alpha < 1/2 of worker machines suffer arbitrary crashes, software bugs, or adversarial gradient corruption.

supports Source: Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates · Locator: Section 1 Introduction, Section 2 Problem Setup, and Section 4 Main Results (Table 1), pp. 1-7

⚠️ Curated Limitations & Negative Results

Coordinate-wise Median suffers an O(1/n) skewness bias when local gradients are asymmetrically distributed.
Coordinate-wise beta-Trimmed Mean requires configuring a trimming threshold beta >= alpha with beta < 1/2.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	Coordinate-wise Median and Trimmed Mean are standard Byzantine-robust distributed gradient aggregation rules used across distributed and federated learning.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r400-primary-pdf`	Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates Dong Yin, Yudong Chen, Ramchandran Kannan, Peter Bartlett	primary paper full_text	ID: https://doi.org/10.48550/arXiv.1803.01498 sha256:d7a7e3a89a64…
`r400-arxiv-abs`	Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (arXiv abstract) Dong Yin, Yudong Chen, Ramchandran Kannan, Peter Bartlett	primary paper abstract_only	ID: https://arxiv.org/abs/1803.01498 sha256:21cc0190e58e…
`r400-metadata-cr`	Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (Crossref metadata) Dong Yin, Yudong Chen, Ramchandran Kannan, Peter Bartlett	primary paper abstract_only	ID: https://doi.org/10.48550/arXiv.1803.01498 sha256:170b8c3ed072…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

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

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

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