Home / Curated / Algorithms / Bucketing Resampling for Heterogeneous Byzantine-Robust Optimization

Bucketing Resampling for Heterogeneous Byzantine-Robust Optimization

Algorithms AIMech:BucketingResamplingForHeterogeneousByzantineRobustOptimization DRAFT

Aliases: s-Bucketing for Byzantine-Robust Learning, Bucketing Agnostic Robust Aggregator, ARAgg via s-Bucketing, Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing

A randomized pre-aggregation resampling reduction (s-Bucketing, Algorithm 1) for Byzantine-robust distributed optimization on heterogeneous (non-i.i.d.) datasets that uniformly permutes the n worker vectors {x_1,...,x_n}, partitions them into ceil(n/s) buckets {B_1,...,B_{ceil(n/s)}} of size at most s, averages the vectors within each bucket y_i = (1/|B_i|) sum_{k in B_i} x_k to produce more homogeneous virtual workers, and feeds {y_1,...,y_{ceil(n/s)}} into a base robust aggregator Aggr (such as Krum, RFA geometric median, or Coordinate-wise Median), combined with worker momentum (Algorithm 2) to convert non-agnostic aggregators into (delta_max, c)-Agnostic Robust Aggregators (ARAgg).

Identity Notes & Concept Scope Distinct from standalone Krum (AIMech:KrumAndMultiKrumByzantineTolerantGradientDescent), Coordinate-wise Median (AIMech:CoordinateWiseMedianAndTrimmedMeanByzantineRobustDistributedLearning), and RFA (AIMech:RfaRobustFederatedAggregationSmoothedWeiszfeldGeometricMedian), all of which fail under inter-client data heterogeneity and the Mimic attack with Omega(rho^2) bias when applied directly to unbucketed worker vectors, and from Centered Clipping (AIMech:CenteredClippingAndWorkerMomentumForByzantineRobustOptimization, which is an iterative clipping rule requiring a clipping radius tau rather than a black-box resampling meta-wrapper).

Claims & Grounded Evidence

4 Claims

Mechanism #r401-mimic-attack-vulnerability-and-lemma1-bucket-variance-reduction

Section 3 shows that standard robust aggregators (Krum, CM, RFA) fail on heterogeneous datasets under the Mimic attack (where Byzantine workers copy a single good worker selected along the top variance direction via streaming Oja's method), whereas Lemma 1 and Theorem I prove that s-bucketing reduces expected pairwise variance between good bucket averages to E||y_i - y_j||^2 <= rho^2 / s while keeping at least ceil(n/s) * (1 - delta * s) buckets purely good, enabling Krum o Bucketing (delta_max < 1/4), RFA o Bucketing (delta_max < 1/2), and CM o Bucketing (delta_max < 1/2) with s = floor(delta_max / delta) to achieve O(delta * rho^2) MSE without knowing rho^2.

supports Source: Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing · Locator: Section 3 Failure of Existing Methods & Mimic Attack, Section 4 (Algorithm 1, Lemma 1, Definition A, Theorem I), & Appendix B, pp. 2-5, 14-15

Mechanism #r401-heterogeneous-nonconvex-convergence-lower-bound-and-strong-growth

Combining an (delta_max, c)-ARAgg with worker momentum (Algorithm 2), Theorem II proves convergence on heterogeneous non-convex objectives to E||nabla f(x)||^2 <= O(c * delta * zeta^2 + sigma * sqrt(L F^0 (c * delta + 1/n) / T)), matching the information-theoretic heterogeneity lower bound Omega(delta * zeta^2) of Theorem III, while Theorems IV and V establish exact convergence to 0 gradient under overparameterized strong growth E||nabla f_j(x) - nabla f(x)||^2 <= B^2 ||nabla f(x)||^2 whenever 60 c * delta * B^2 < 1.

supports Source: Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing · Locator: Section 5 Byzantine-Robust Optimization with Heterogeneity (Algorithm 2, Theorems II, III, IV, V), pp. 5-7

Limitation #r401-breakdown-point-shrinkage-and-fundamental-heterogeneity-floor-limitation

Bucketing with bucket size s multiplies the effective fraction of corrupted buckets by up to s (requiring delta * s <= delta_max, so s = floor(delta_max / delta) must be tuned using an upper bound on delta), and Theorem III proves an unavoidable Omega(delta * zeta^2) optimality gap under arbitrary bounded gradient dissimilarity zeta^2.

supports Source: Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing · Locator: Section 4 Lemma 1 & Theorem I, and Section 5.1 Theorem III (Lower Bounds under Heterogeneity), pp. 4-6

Application #r401-non-iid-mnist-and-cifar10-byzantine-defense-application

Evaluated on Dirichlet non-i.i.d. partitions of MNIST and CIFAR-10 against bit-flipping, little-is-enough (LIE), inner-product manipulation (IPM), and Mimic attacks, restoring high test accuracy for Krum, RFA, and Coordinate-wise Median where unbucketed versions degrade to random guessing.

supports Source: Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing · Locator: Section 6 Experiments (Figures 2-3), pp. 7-9

⚠️ Curated Limitations & Negative Results

Each Byzantine worker can corrupt an entire bucket of size s, requiring s <= floor(delta_max / delta).
Cannot eliminate the fundamental information-theoretic Omega(delta * zeta^2) optimization error floor under worst-case non-i.i.d. heterogeneity without overparameterized strong growth.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	narrow_match	Bucketing resampling is a Byzantine-robust aggregation meta-algorithm designed for heterogeneous distributed and federated learning.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r401-primary-pdf`	Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing Sai Praneeth Karimireddy, Lie He, Martin Jaggi	primary paper full_text	ID: https://doi.org/10.48550/arXiv.2006.09365 sha256:2a80ee2d6398…
`r401-arxiv-abs`	Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing (arXiv abstract) Sai Praneeth Karimireddy, Lie He, Martin Jaggi	primary paper abstract_only	ID: https://arxiv.org/abs/2006.09365 sha256:6b25d8a9e01d…
`r401-metadata-cr`	Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing (Crossref metadata) Sai Praneeth Karimireddy, Lie He, Martin Jaggi	primary paper abstract_only	ID: https://doi.org/10.48550/arXiv.2006.09365 sha256:d4026086f134…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

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

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

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