PaperlayerView exact revision on arXiv

Source-linked AI summary

DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation

Shashank Rajput, Hongyi Wang, Zachary Charles, Dimitris Papailiopoulos

arXiv:1907.12205v2cs.LGcs.DCstat.ML

TL;DR

Byzantine failures make gradient averaging unreliable, while existing robust or redundancy-based methods trade off scalability, guarantees, and fault tolerance. DETOX combines limited redundancy with hierarchical robust aggregation, achieving substantially improved robustness and efficiency, including almost a 40% accuracy increase under strong attacks.

  • Problem

    Existing Byzantine-resilient aggregation methods have high computational costs or limited robustness guarantees, while redundancy-based methods tolerate only limited Byzantine failures.

  • Method

    DETOX uses redundant gradient groups to filter Byzantine outputs before applying hierarchical aggregation with any robust aggregator.

  • Results

    Across real distributed large-scale experiments, DETOX improved robustness and runtime; under strong Byzantine attacks, it produced almost a 40% accuracy increase over vanilla Byzantine-robust aggregation.

  • Takeaways & Limitations

    DETOX can be paired with any robust aggregator to improve robustness and efficiency in Byzantine-resilient distributed training.

  • Takeaways & Limitations

    DETOX's robustness analysis assumes sample gradients are drawn from a distribution with mean G and variance σ2.

Abstract

from arXiv · show

To improve the resilience of distributed training to worst-case, or Byzantine node failures, several recent approaches have replaced gradient averaging with robust aggregation methods. Such techniques can have high computational costs, often quadratic in the number of compute nodes, and only have limited robustness guarantees. Other methods have instead used redundancy to guarantee robustness, but can only tolerate limited number of Byzantine failures. In this work, we present DETOX, a Byzantine-resilient distributed training framework that combines algorithmic redundancy with robust aggregation. DETOX operates in two steps, a filtering step that uses limited redundancy to significantly reduce the effect of Byzantine nodes, and a hierarchical aggregation step that can be used in tandem with any state-of-the-art robust aggregation method. We show theoretically that this leads to a substantial increase in robustness, and has a per iteration runtime that can be nearly linear in the number of compute nodes. We provide extensive experiments over real distributed setups across a variety of large-scale machine learning tasks, showing that DETOX leads to orders of magnitude accuracy and speedup improvements over many state-of-the-art Byzantine-resilient approaches.

1 Introduction

Distributed gradient averaging is vulnerable to Byzantine nodes, while existing robust aggregation and redundancy-based methods face scalability, guarantee, or tolerance limits. DETOX combines computational redundancy with hierarchical robust aggregation to improve robustness and efficiency at nearly linear complexity.

  • Motivation: A single Byzantine node can make average-based gradient aggregation produce arbitrarily bad global models.Byzantine failures may arise from unreliable hardware, communication failures, or security issues and can produce arbitrary outputs.
  • Limitations of prior approaches: Existing robust aggregators are often computationally expensive, scaling super-linearly or quadratically with node count, and provide limited Byzantine-robustness guarantees.Reported guarantees may establish only convergence in the limit or a positive inner product with the true gradient.
  • Our contributions: DETOX combines redundant gradient filtering with hierarchical robust aggregation, and can be paired with any robust aggregation method to improve robustness and efficiency.The framework first filters gradients using computational redundancy, then applies hierarchical robust aggregation.
  • DETOX method: DETOX groups nodes to compute identical gradients, then uses majority votes to filter gradients before robust aggregation.Setting the group size r logarithmic in the number of compute nodes enables faster parameter-server computation and improved robustness.
  • Our contributions: DETOX provides orders-of-magnitude stronger robustness guarantees than competing methods while achieving nearly linear complexity in the number of compute nodes p.This contrasts with methods such as Bulyan, whose runtime is quadratic in p.

2 Problem Setup

The section formulates empirical risk minimization and its distributed mini-batch SGD implementation, where a parameter server aggregates gradients from compute nodes. It then models Byzantine nodes as unrestricted, potentially colluding adversaries, assuming their fraction is below one-half.

  • 2 Problem Setup: The objective is empirical risk minimization over model parameters w, with mini-batch SGD updating an initialized model using randomly sampled data subsets.
  • 2 Problem Setup: Distributed mini-batch SGD stores the global model at a parameter server, which broadcasts it, receives node-computed gradient sums, and updates the model from their mean.
  • 2 Problem Setup: The parameter server owns the entire dataset of size n, while p compute nodes receive assigned subsets and evaluate the corresponding gradients.
  • Distributed training with Byzantine nodes: A fixed subset Q of q Byzantine nodes may return arbitrary d-dimensional vectors, with no restrictions on information, coordination, or collusion; the assumed fraction is ϵ = q/p < 1/2.

3 DETOX: A Redundancy Framework to Filter most Byzantine Gradients

DETOX combines redundancy-based majority filtering with hierarchical robust aggregation to reduce Byzantine gradients before updating the model. Its filtering step decreases the expected Byzantine-vote count exponentially in the redundancy ratio, and logarithmic redundancy can reduce effective Byzantine votes to a constant with high probability.

  • DETOX framework: DETOX partitions compute nodes into fixed groups of size r, assigns each group a shared mini-batch partition, and uses majority voting to produce one vote per group.If no majority exists, the group vote is set to zero.
  • DETOX framework: The parameter server applies hierarchical aggregation by running A0 within vote groups and A1 across their outputs, then updates the model with the resulting gradient estimate.HIER-AGGR uses user-specified aggregation methods and resembles median-of-means aggregation on the votes.
  • Byzantine-vote filtering: The expected number of Byzantine votes decreases exponentially with redundancy ratio r, while the number of vote groups decreases only linearly with r.Thus, a constant-factor loss in compute resources can yield an exponential reduction in Byzantine votes.
  • Byzantine-vote filtering: With redundancy r ≥ 3 + 2 log2(q) and Byzantine ratio ϵ ≤ c, DETOX has at most 1 + 2 log(1/δ) Byzantine votes with probability at least 1 − δ.This guarantee follows from concentration for the negatively correlated group-failure indicators.

4 DETOX Improves the Speed and Robustness of Robust Estimators

DETOX combines redundancy-based filtering with hierarchical robust aggregation to improve both runtime and robustness. Its guarantees remain nearly independent of the Byzantine fraction and worker count, aside from logarithmic dependence on q.

  • Hierarchical aggregation: DETOX’s filtering reduces Byzantine votes to roughly a constant when r ≈ log(q), after which HIER-AGGR improves efficiency and robustness.The hierarchical stage partitions votes into groups before applying robust aggregation.
  • Improved speed: When T = O(d), Krum, Multi-Krum, and Bulyan require O(p^2d) time, whereas DETOX requires O(pd).Thus, DETOX’s runtime advantage grows with the number of workers.
  • Improved robustness: Honest DETOX votes have mean G and variance σ^2p/rb because each node receives rb/p samples.The variance reduction supports the framework’s robustness analysis through an inexact-gradient-oracle bound.
  • Improved robustness: DETOX’s robustness guarantees are virtually independent of Byzantine ratio ϵ and worker count p, with only logarithmic dependence on q.The paper contrasts this scaling with direct Krum, geometric median, and coordinate-wise median aggregation, whose guarantees worsen as p increases.

5 Experiments

Experiments show that DETOX substantially improves the speed and Byzantine resilience of robust aggregation methods across distributed training tasks. Pairing DETOX with existing aggregators and SIGNSGD yields large end-to-end speedups and major accuracy gains under strong Byzantine attacks.

  • Byzantine-resilience under various attacks: DETOX substantially improves Byzantine resilience: BULYAN raises VGG13-BN accuracy under ALIE from 11% to 60%, while SIGNSGD rises from 34.92% to 78.75% under constant attack.The broader ALIE comparison covers MULTI-KRUM, BULYAN, and coordinate-wise median on both datasets, while Figure 6 reports SIGNSGD results.
  • Scalability: DETOX reduces aggregation overhead despite slightly higher per-iteration compute, because redundancy lowers parameter-server computation and can reduce communication costs.The communication reduction is attributed to greater variance in compute-node time under heavier computational redundancy.
  • Byzantine-resilience under various attacks: Under the weaker reverse-gradient attack, vanilla MULTI-KRUM, BULYAN, coordinate-wise median, and their DETOX variants all defend well, with DETOX still providing end-to-end speedups.Figure 4 compares convergence, and Figure 5 reports speedups for ResNet-18 on CIFAR-10 and VGG13-BN on CIFAR-100.
  • Scalability: Up to an order-of-magnitude end-to-end speedup is observed with DETOX, including 5× faster convergence to 90% accuracy for coordinate-wise median on CIFAR-10.On VGG13-BN trained on CIFAR-100, coordinate-wise median with DETOX achieves up to an order-of-magnitude speedup; Figure 5 reports the speedups.
  • Byzantine-resilience under various attacks: DETOX also increases the robustness of geometric-median and coordinate-wise-median estimators while reducing the error’s dependence on dimension.This estimator experiment varies dimension from 20 to 100 and uses Byzantine vectors with ℓ2 norm 100.

6 Conclusion · A Proofs

DETOX is presented as a Byzantine-resilient distributed-training framework that can work with any robust aggregator to improve robustness and efficiency. The paper supports these improvements theoretically and empirically, while identifying privacy preservation as future work.

  • 6 Conclusion: DETOX is introduced as a new framework for Byzantine-resilient distributed training.
  • 6 Conclusion: DETOX can immediately incorporate any robust aggregator.
  • 6 Conclusion: The framework is intended to increase the robustness of integrated robust aggregators.
  • 6 Conclusion: The framework is intended to improve the efficiency of integrated robust aggregators.
  • 6 Conclusion: The paper demonstrates DETOX’s robustness and efficiency improvements both theoretically and empirically.
  • 6 Conclusion: Future work will develop a privacy-preserving version of DETOX because the current version requires the parameter server to own the data and partition it among compute nodes.

A.1 Proof of Theorem 1

The proof establishes Theorem 1 for r > 3, p ≥2r, and ϵ < 1/40, showing that E[ˆq] decreases at an O-rate exponential in r. A separate lemma handles r = 3 under n ≥6.

  • A.1 Proof of Theorem 1: For r > 3, p ≥2r, and ϵ < 1/40, E[ˆq] falls at an O-rate that is exponential in r.These are the theorem’s stated conditions and asymptotic conclusion.
  • A.1 Proof of Theorem 1: For r > 3, the proof derives the needed coefficient from the binomial expansion of 1 = 1r = (x + (1 −x))r and sets x = 1/2.The proof also notes that odd r > 3 implies r ≥5.
  • A.1 Proof of Theorem 1: When r = 3 and n ≥6, E[ˆq] ≤q(4ϵ −2ϵ2)/3.This special case is stated as Lemma 4.

A.2 Proof of Corollary 2 · A.3 Proof of Lemma 5

The proofs derive Corollary 2 by bounding the expected leftover Byzantine count and establish Lemma 5 using Bernoulli-variable concentration and reduced conditional majority probabilities. Together, they connect redundancy assumptions to probability guarantees and block-level Byzantine reduction.

  • A.2 Proof of Corollary 2: If ϵ ≤ 1/80 and r ≥ 3 + 2 log_2 q, then the expected leftover Byzantine count satisfies E[ˆq] ≤ 1.This follows from the bound E[ˆq] ≤ 2q(40ϵ)^(r−1)/2.
  • A.2 Proof of Corollary 2: Setting δ := 2^(−E[ˆq]θ/2) yields the probability bound, while δ ≤ 1/2 ensures θ ≥ 2.The proof uses E[ˆq] ≤ 1 for the first implication and θ ≥ 2 for the second.
  • A.3 Proof of Lemma 5: The proof sets βˆp = E[ˆq](1 + θ) and assigns each Bernoulli variable marginal probability P[X_i = 1] = E[ˆq]/ˆp.These definitions establish the parameters used in the subsequent probability argument.
  • A.3 Proof of Lemma 5: A block has X_i = 1 only when its Byzantine machines form a majority, so removing that block reduces the remaining Byzantine pool more than the honest pool.Because Byzantine machines are fewer than honest machines overall, their probability of forming a majority in another block decreases.

A.4 Proof of Theorem 3

The proof combines concentration bounds with geometric-median and coordinatewise-median arguments to establish Theorem 3. It first controls cluster means under corruption, then extends the result coordinatewise using a union bound.

  • Proof setup: With total probability at least 1 − 2δ, the preliminary bound on ˆq and the remainder of the theorem hold simultaneously.The proof obtains each event with probability at least 1 − δ and combines them multiplicatively.
  • Coordinatewise median: For coordinatewise median, applying the one-dimensional argument to each coordinate and union bounding yields failure probability at most δ.The proof sets k = 128 log(d/δ) and bounds each coordinate’s deviation by δ/d before taking the union bound.
  • Coordinatewise median: The coordinatewise result therefore bounds the α-trimmed mean’s deviation from G with probability at least 1 − δ when k = 128 log(d/δ).The condition αk ≥ 2ˆq is satisfied under this choice, yielding the stated bound for some constant C3.

B Extra Experimental Details · B.1 Implementation and system-level optimization details · B.2 Hyper-parameter tuning

Appendix B details DETOX’s implementations, system-level optimizations, and attack-specific hyper-parameter tuning. The optimizations parallelize robust aggregation and achieve a 2–4× speedup in that stage.

  • B.1 Implementation and system-level optimization details: BULYAN, MULTI-KRUM, and coordinate-wise median were combined with DETOX using assignments of 15 winning gradients tailored to each method’s requirements.BULYAN uses one cluster; MULTI-KRUM uses groups of sizes 7 and 8; coordinate-wise median uses five clusters of size 3.
  • B.1 Implementation and system-level optimization details: BULYAN’s post-majority-voting requirement becomes p ≥ 4q̂ + 3 = 11, so all 15 winning gradients are assigned to one cluster.This assignment follows the stated BULYAN requirement after the first majority voting level.
  • B.1 Implementation and system-level optimization details: MULTI-KRUM assigns 15 winning gradients into two uneven groups of sizes 7 and 8, while coordinate-wise median assigns them to five clusters of size 3.These assignments follow the stated method requirements and the theoretical analysis in Section 3.1.
  • B.1 Implementation and system-level optimization details: The system-level implementation first vectorizes and concatenates gradients from all neural-network layers before applying robust aggregation across compute nodes.This restructuring is one of the two stated optimization ideas used for fairer comparisons.
  • B.1 Implementation and system-level optimization details: 2–4× speedup was achieved in the robust aggregation stage through system-level optimization of computationally heavy operations.The optimization vectorizes and concatenates all neural-network layer gradients, then parallelizes median calculations over evenly chunked high-dimensional vectors.
  • B.2 Hyper-parameter tuning: Hyper-parameter tuning provides stepsize schedules for experiments under reverse gradient Byzantine attacks.The tuned schedules are reported in Table 2.
  • B.2 Hyper-parameter tuning: Hyper-parameter tuning also provides stepsize schedules for experiments under ALIE Byzantine attacks.The tuned schedules are reported in Table 3.

B.3 Data augmentation and normalization details · B.4 Comparison between DETOX and DRACO

The appendix specifies CIFAR-10/100 preprocessing with standard augmentation and channel-wise normalization, and presents runtime-convergence comparisons between DETOX-backed robust aggregators and DRACO under reverse-gradient Byzantine attacks.

  • B.3 Data augmentation and normalization details: CIFAR-10/100 images use random cropping and horizontal random flipping for data augmentation.
  • B.3 Data augmentation and normalization details: Each CIFAR-10/100 color channel is normalized using a specified mean and standard deviation.The channel-wise normalization subtracts the channel mean and divides by the channel standard deviation.
  • B.4 Comparison between DETOX and DRACO: The appendix reports experimental results comparing DETOX with DRACO.
  • B.4 Comparison between DETOX and DRACO: DETOX-backed robust aggregation methods and DRACO are compared by convergence with respect to runtime under reverse-gradient Byzantine attacks.The comparisons cover ResNet-18 on CIFAR-10 and VGG13-BN on CIFAR-100.
  • B.4 Comparison between DETOX and DRACO: The runtime-convergence comparisons include ResNet-18 trained on CIFAR-10.
  • B.4 Comparison between DETOX and DRACO: The runtime-convergence comparisons include VGG13-BN trained on CIFAR-100.
Loading 1907.12205v2…