Home / Curated / Algorithms / Centered Clipping and Worker Momentum for Byzantine-Robust Optimization

Centered Clipping and Worker Momentum for Byzantine-Robust Optimization

Algorithms AIMech:CenteredClippingAndWorkerMomentumForByzantineRobustOptimization DRAFT

Aliases: Centered Clipping (CC), Byzantine-Robust Worker Momentum with Centered Clipping, Learning from History for Byzantine Robust Optimization, Byzantine-Robust Momentum Variance Reduction (MVR)

A stateful Byzantine-robust distributed optimization framework combining: (1) local Worker Momentum m_{t,i} = (1 - alpha_t) m_{t-1,i} + alpha_t g_i(x_{t-1}) (or Momentum Variance Reduction, MVR) maintained across steps to average out stochastic gradient noise and defeat time-coupled adversaries; and (2) iterative Centered Clipping (CC), which aggregates worker momentum vectors {x_1,...,x_n} around a reference iterate v_0 by updating v_{l+1} = v_l + (1/n) sum_{i=1}^n (x_i - v_l) min(1, tau_l / ||x_i - v_l||_2) for l >= 0 with clipping radius tau_l, achieving (delta_max, c)-robust aggregation E||v_L - x_bar_G||^2 <= c * delta * sigma^2 in O(n d) time.

Identity Notes & Concept Scope Distinct from memoryless middle-seeking aggregators such as Krum (AIMech:KrumAndMultiKrumByzantineTolerantGradientDescent), Coordinate-wise Median (AIMech:CoordinateWiseMedianAndTrimmedMeanByzantineRobustDistributedLearning), and RFA (AIMech:RfaRobustFederatedAggregationSmoothedWeiszfeldGeometricMedian), which Theorem I and Counterexamples 1-3 prove can fail to converge even with zero Byzantine workers (delta = 0) under asymmetric/bimodal stochastic gradient noise and suffer an Omega(delta * sigma^2 / mu^2) lower bound under time-coupled attacks (Theorem II), and from Bucketing (AIMech:BucketingResamplingForHeterogeneousByzantineRobustOptimization, which addresses inter-client data heterogeneity via random s-bucketing rather than intra-client stochastic noise via centered clipping).

Claims & Grounded Evidence

4 Claims

Mechanism #r403-middle-seeker-counterexamples-and-memoryless-time-coupled-lower-bound

Section 3 (Counterexamples 1-3, Theorem I) proves that memoryless middle-seekers (CW Median, RFA, Krum) fail to converge even with delta = 0 corruption under asymmetric, bimodal, or imbalanced zero-mean noise, and Theorem II proves that any permutation-invariant memoryless algorithm incurs an Omega(delta * sigma^2 / mu^2) non-vanishing optimality gap against time-coupled Byzantine attacks.

supports Source: Learning from History for Byzantine Robust Optimization · Locator: Section 3 Failure of Existing Methods (Counterexamples 1-3, Theorem I) & Section 4 Lower Bounds for Memoryless Algorithms (Definition B, Theorem II), pp. 2-5

Mechanism #r403-centered-clipping-contraction-and-worker-momentum-convergence

Theorem IV and Corollary V prove that Centered Clipping contracts toward the true honest average and satisfies (delta_max = 0.1, c)-robustness E||x_hat - x_bar||^2 <= c * delta * rho^2 (matching the Omega(delta * rho^2) lower bound of Theorem III), while Theorem VI and Theorem VII prove that combining Centered Clipping with Worker Momentum or Momentum Variance Reduction (MVR) converges to a stationary point on nonconvex objectives at rates O((c * delta + 1/n)^{1/2} / T^{1/2}) and O((c * delta + 1/n)^{1/3} / T^{2/3}), respectively, driving asymptotic error to zero as T -> infinity.

supports Source: Learning from History for Byzantine Robust Optimization · Locator: Section 5 (Definition C, Theorems III-IV, Corollary V) and Section 6 (Theorems VI-VII), pp. 5-8

Limitation #r403-clipping-radius-tuning-and-delta-point-one-threshold-limitation

Theoretical contraction of Centered Clipping in Theorem IV requires the Byzantine fraction delta <= 0.1 (or bounded variance ratio) and requires setting the clipping threshold tau_l proportional to the honest variance and current distance to the honest mean.

supports Source: Learning from History for Byzantine Robust Optimization · Locator: Section 5.2 Analysis of Centered Clipping (Theorem IV, Corollary V), pp. 5-6

Application #r403-time-coupled-and-little-is-enough-cifar10-defense-application

Evaluated on distributed CIFAR-10 and MNIST training against time-coupled, Little-Is-Enough (ALIE), inner-product manipulation, and bit-flipping attacks, where Worker Momentum + Centered Clipping matches uncorrupted SGD accuracy while memoryless Krum, Median, and RFA stagnate.

supports Source: Learning from History for Byzantine Robust Optimization · Locator: Section 7 Experiments (Figures 1-3), pp. 7-9

⚠️ Curated Limitations & Negative Results

Theoretical contraction guarantees for Centered Clipping require delta <= 0.1 and an appropriately scaled clipping radius tau.
Requires stateful workers or synchronized momentum buffers across iterations.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	Centered Clipping with Worker Momentum is a Byzantine-robust distributed and federated optimization algorithm.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r403-primary-pdf`	Learning from History for Byzantine Robust Optimization Sai Praneeth Karimireddy, Lie He, Martin Jaggi	primary paper full_text	ID: https://doi.org/10.48550/arXiv.2012.10333 sha256:8be5b65b7aad…
`r403-arxiv-abs`	Learning from History for Byzantine Robust Optimization (arXiv abstract) Sai Praneeth Karimireddy, Lie He, Martin Jaggi	primary paper abstract_only	ID: https://arxiv.org/abs/2012.10333 sha256:7ba0305f9d04…
`r403-metadata-cr`	Learning from History for Byzantine Robust Optimization (Crossref metadata) Sai Praneeth Karimireddy, Lie He, Martin Jaggi	primary paper abstract_only	ID: https://doi.org/10.48550/arXiv.2012.10333 sha256:20b12cc5eab3…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

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

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

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