PaperlayerView exact revision on arXiv

Source-linked AI summary

Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates

Dong Yin, Yudong Chen, Kannan Ramchandran, Peter Bartlett

arXiv:1803.01498v2cs.LGcs.CRcs.DCstat.ML

TL;DR

Large-scale distributed learning must remain useful when worker machines behave arbitrarily or adversarially, but the optimal statistical performance of Byzantine-robust methods is not fully understood. The paper analyzes median- and trimmed-mean-based distributed gradient descent across loss classes and proposes a one-round median-based method. It shows order-optimal rates for strongly convex losses and for strongly convex quadratic loss with the one-round algorithm.

  • Problem

    The paper addresses how to achieve statistically optimal learning while remaining robust to Byzantine worker failures in distributed systems.

  • Method

    The paper analyzes coordinate-wise median and trimmed-mean distributed gradient descent and proposes a coordinate-wise median one-round algorithm for aggregating local solutions.

  • Results

    The robust gradient descent algorithms achieve order-optimal statistical rates for strongly convex losses, while the one-round method achieves the optimal rate for strongly convex quadratic losses.

  • Takeaways & Limitations

    Byzantine robustness can be obtained without sacrificing statistical quality beyond the unavoidable Byzantine influence, and quadratic-loss robustness can use one communication round.

  • Takeaways & Limitations

    Some stated rates may not have optimal dependence on the parameter dimension d, leaving high-dimensional limits and dimension-optimal algorithms as future directions.

Abstract

from arXiv · show

In large-scale distributed learning, security issues have become increasingly important. Particularly in a decentralized environment, some computing units may behave abnormally, or even exhibit Byzantine failures -- arbitrary and potentially adversarial behavior. In this paper, we develop distributed learning algorithms that are provably robust against such failures, with a focus on achieving optimal statistical performance. A main result of this work is a sharp analysis of two robust distributed gradient descent algorithms based on median and trimmed mean operations, respectively. We prove statistical error rates for three kinds of population loss functions: strongly convex, non-strongly convex, and smooth non-convex. In particular, these algorithms are shown to achieve order-optimal statistical error rates for strongly convex losses. To achieve better communication efficiency, we further propose a median-based distributed algorithm that is provably robust, and uses only one communication round. For strongly convex quadratic loss, we show that this algorithm achieves the same optimal error rate as the robust distributed gradient descent algorithms.

1 Introduction

The paper develops Byzantine-robust distributed learning algorithms that target optimal statistical accuracy while controlling communication costs. Its analyses cover multiple loss classes, with order-optimal rates for strongly convex settings and a one-round quadratic-loss method.

  • Motivation: Large-scale and federated learning systems face arbitrary Byzantine behavior from faulty, unpredictable, or malicious worker machines.A single Byzantine machine can arbitrarily skew naive aggregation, and even a small number can significantly degrade performance.
  • Research goal: The central question is what statistical performance is achievable by learning algorithms that remain robust to Byzantine failures.The paper seeks algorithms that are both statistically useful and provably robust, rather than merely insensitive to worker messages.
  • Objectives: The paper targets statistical optimality at e O( α √n + 1 √nm) while restricting each communication exchange to O(d) data.The desired rate combines Byzantine influence with sampling and averaging effects; total communication depends on the number of rounds.
  • Algorithms and analysis: Two robust distributed gradient descent algorithms use coordinate-wise median and trimmed mean aggregation, with rates established for strongly convex, non-strongly convex, and smooth non-convex losses.The analysis addresses dependence across iterations caused by fixed data and potentially adaptive Byzantine machines using uniform bounds and covering arguments.
  • Statistical guarantees: Trimmed-mean-based GD achieves e O( α √n + 1 √nm) and is order-optimal for strongly convex loss.Median-based GD has an additional 1/n term in the stated rate and is order-optimal for strongly convex loss if n ≳m.

2 Related Work

Prior work addressed robust distributed learning, communication efficiency, and outlier-robust estimation separately, but left optimal statistical guarantees under Byzantine failures unresolved. The paper distinguishes its setting from these approaches and targets robust statistical learning with general losses and fixed data.

  • Outlier-robust estimation: Median-of-means work studied robust estimation, but this paper extends the challenge to arbitrary Byzantine outliers and iterative multidimensional optimization with convex and non-convex losses.The cited prior analysis mainly concerned one-shot algorithms for mean estimation.
  • Byzantine-robust learning: Feng et al. proved only a sub-optimal ẽO(1/√n) error rate for a one-shot median-of-means application.
  • Byzantine-robust learning: Chen et al. considered strongly convex losses, but their ẽO(√α/√n + 1/√nm) rate was non-optimal and their algorithm failed with one Byzantine machine per mini-batch.
  • Byzantine optimization: Blanchard et al. robustly aggregated stochastic gradients, but assumed unlimited independent oracle access and did not characterize statistical error for fixed data.
  • Communication efficiency: Communication-efficient distributed methods include one-round aggregation and more sophisticated approaches designed to improve accuracy while limiting communication costs.
  • High-dimensional robustness: High-dimensional robust-estimation methods are not directly applicable to this distributed setting with general loss functions.

3 Problem Setup

The paper models distributed ERM with a master, worker machines, fixed local datasets, and an α fraction of Byzantine workers. Its algorithms use coordinate-wise median and trimmed-mean aggregation under standard parameter-space, loss-function, and random-variable definitions.

  • Statistical model: Training data are sampled from D, each worker stores n independent points, and the worker empirical risk averages its local losses.
  • Distributed computation model: The parameter space W is convex and compact with diameter D, and the system contains one master machine and m workers.
  • Distributed computation model: An α fraction of m workers are Byzantine and may send arbitrary messages, while the master communicates with workers through a predefined protocol.
  • Robust aggregation: Coordinate-wise median aggregates vectors by taking the ordinary median independently in each coordinate.
  • Robust aggregation: The coordinate-wise β-trimmed mean removes the largest and smallest β fractions in each coordinate before averaging the remainder.
  • Probabilistic assumptions: The setup defines variance, absolute skewness, and sub-exponential random variables for analyzing the worker-level randomness.
  • Function properties: The analysis also uses standard convex-analysis properties, including Lipschitzness, smoothness, and strong convexity.

4 Robust Distributed Gradient Descent

The paper develops robust distributed gradient descent algorithms using coordinate-wise median and trimmed-mean aggregation, with guarantees for strongly convex, convex, and smooth non-convex losses. For strongly convex losses, the trimmed-mean method is order-optimal, while the median method is order-optimal when n ≳ m, up to logarithmic factors.

  • Algorithms: Coordinate-wise median and trimmed mean aggregate worker gradients in robust distributed gradient descent.Each iteration broadcasts the current parameter, collects local gradients, and applies a robust aggregate before updating.
  • Examples: In a linear regression example, gradient variance depends on dimension and parameter-space diameter, while coordinate-wise skewness remains universally bounded in the Gaussian-feature example.For bounded-diameter parameter spaces, the variance parameter has the stated dimension dependence; Gaussian features give a skewness bound of 429.
  • Guarantees: The algorithms analyze strongly convex, non-strongly convex, and smooth non-convex population losses under smoothness and gradient-moment assumptions.The median analysis assumes bounded gradient variance and coordinate-wise bounded skewness; the trimmed-mean analysis uses its own stated assumptions.
  • Median-based guarantees: The median-based method attains error rate e O( α √n + 1 √nm + 1 n), with the first two terms unimprovable and the full rate order-optimal when n ≳ m.The additional 1/n term reflects the dependence of the median on gradient skewness.
  • Trimmed-mean guarantees: The trimmed-mean method achieves e O( α √n + 1 √nm) for strongly convex losses, including when β is chosen as a constant multiple of α.Unlike the median method, this rate remains meaningful for small local sample sizes, but it requires sub-exponential derivative assumptions and an upper bound β on α.

5 Robust One-round Algorithm

The paper proposes a Byzantine-robust one-round algorithm that aggregates local empirical risk minimizers with a coordinate-wise median. For strongly convex quadratic losses, it achieves the same statistical rate as robust gradient descent while substantially reducing communication.

  • Communication: One communication round provides similar theoretical performance to robust gradient descent with significantly less communication cost.The paper also reports good empirical performance for other losses, although the theorem is established only for quadratic losses.
  • Algorithm: The one-round algorithm replaces averaging of local ERMs with coordinate-wise median aggregation to resist Byzantine machines.Workers compute local ERMs and send them to the master, which computes the coordinate-wise median.
  • Guarantee: The paper establishes an error-rate guarantee for this algorithm when the loss is quadratic, W = R^d, and normal-worker ERMs are unique under strong convexity.The analysis assumes convex quadratic losses, strongly convex population risk, and the stated empirical strong-convexity condition.
  • Statistical rate: e O( α √n + 1 √nm + 1 n) is the one-round algorithm’s quadratic-loss rate, matching coordinate-wise-median gradient descent in its dependence on α, n, and m.The rate is optimal when n ≳ m.

6 Lower Bound

The lower-bound analysis reduces robust distributed learning to distributed mean estimation and shows that Byzantine contamination and finite-sample averaging impose unavoidable error terms. This establishes order-optimality of the corresponding strongly convex upper bounds when n ≳ m.

  • Reduction: The lower bound uses distributed mean estimation as a special case of the general learning problem.The analysis considers machines that are independently Byzantine with probability α, so α is the expected Byzantine fraction.
  • Lower bound: For Gaussian data with covariance σ^2I and σ = O(1), any mean estimator has a constant-probability lower bound on its estimation error.The observation applies in the distributed setting with Byzantine failure probability α.
  • Implication: The α/√n + 1/√nm dependence cannot be avoided, implying order-optimality of the strongly convex results when n ≳ m.The lower bound applies to the rates associated with the median-based gradient descent and trimmed-mean analyses.

7 Experiments

Experiments on logistic regression and convolutional networks show that robust median and trimmed-mean aggregation substantially improves test accuracy under Byzantine attacks. A one-round median method also improves accuracy beyond mean aggregation in logistic regression.

  • The experiments evaluate multi-class logistic regression and convolutional neural networks using distributed gradient descent.The CNN experiment uses stochastic distributed gradient descent, with each worker computing gradients from 10% of its local data per iteration.
  • Table 2 reports logistic-regression test accuracy with m = 40 and trimmed-mean parameter β = 0.05.
  • Median and trimmed-mean aggregation significantly improves test accuracy over vanilla distributed gradient descent in adversarial settings.The comparison includes no-Byzantine mean aggregation, adversarial mean aggregation, adversarial median aggregation, and adversarial trimmed-mean aggregation.
  • Table 3 reports convolutional-neural-network test accuracy with m = 10 and trimmed-mean parameter β = 0.1.
  • The one-round median algorithm improves test accuracy over mean aggregation in the logistic-loss experiment, although its guarantee is proved only for quadratic loss.The one-round comparison uses logistic regression and m = 10.

8 Conclusions

The paper analyzes coordinate-wise median and trimmed-mean robust distributed gradient descent under several loss geometries, targeting statistically optimal error despite Byzantine workers. It also proposes a one-round median method that matches the optimal rate for strongly convex quadratic loss.

  • The trimmed-mean algorithm achieves order-optimal e O( α √n + 1 √nm) error rate.
  • The one-round coordinate-wise median algorithm achieves e O( α √n + 1 √nm + 1 n) for strongly convex quadratic problems, similar to median-based gradient descent.
  • The proof of Theorem 1 combines coordinate-wise median estimation of population gradients with convergence analysis of robustified gradient descent.

B.1 Proof of Theorem 8

The proof establishes robust gradient estimation by analyzing median-of-means behavior under adversarial workers, then extends fixed-parameter bounds uniformly over parameters and coordinates using covering nets and union bounds.

  • The proof analyzes robust estimation for m workers, q Byzantine workers, and normal workers holding n i.i.d. samples of a one-dimensional variable.
  • The median-of-means estimator obtains a high-probability accuracy bound from empirical distribution-function control for normal workers.
  • For a fixed parameter w and coordinate k, the gradient median-of-means estimator satisfies a high-probability bound under condition (32).
  • A covering net and union bound extend the fixed-w, fixed-coordinate result to all w ∈ W and all d coordinates.
  • The proof uses Berry–Esseen and bounded-difference inequalities to control the relevant empirical distribution functions.

C Proof of Theorem 2

The proof of Theorem 2 converts a uniform robust-gradient noise bound into convergence guarantees for convex and non-convex objectives. The trimmed-mean analysis reuses the same bounded-noise convergence argument after establishing its own gradient estimator bound.

  • Theorem 2: For non-strongly convex objectives, the uniform gradient bound remains valid without assuming convexity of F(w).
  • Theorem 2: The proof keeps iterates inside W without projection under the stated assumptions, then analyzes descent using smoothness and bounded gradient noise.
  • Theorem 2: With η = 1/LF, the convex analysis bounds the optimization error after T parallel iterations using the uniform gradient-noise level Δ.
  • Theorem 2: For non-convex objectives, the same uniform event is used, and smoothness yields a convergence bound involving Δ and Δ^2.
  • Trimmed mean: The trimmed-mean proof separately analyzes its gradient estimator, then applies essentially the same robustified-gradient-descent convergence analysis.

E.1 Proof of Theorem 11

The proof establishes concentration for trimmed means under Byzantine contamination, then extends coordinatewise bounds uniformly over the parameter space using a covering net and union bounds.

  • Robust estimation setup: The analysis models m worker machines, including q Byzantine machines storing adversarial data and m(1 −α) normal machines with n i.i.d. samples.Here α := q/m.
  • Robust estimation setup: Lemma 3 gives a trimmed-mean concentration result when normal-machine samples are i.i.d. v-sub-exponential with mean µ.The result applies for any t ≥0.
  • Uniform extension: A covering net over W and a union bound extend coordinatewise concentration from finitely many net points to all parameters and coordinates.The net size satisfies Nδ ≤(1 + D δ )d.
  • Uniform extension: Bernstein’s inequality supplies the sub-exponential concentration tool used in the proof.The proof first recalls the inequality for i.i.d. v-sub-exponential random variables.
  • Trimmed mean analysis: The trimmed mean is analyzed by separating normal and Byzantine machines and comparing trimmed normal-machine means with the largest normal deviation.The proof assumes the trimming fraction β is at least the Byzantine fraction α.

F Proof of Theorem 7

The proof of Theorem 7 analyzes quadratic empirical risks through matrix and vector sample means, applying a Hilbert-space Berry–Esseen bound and concentration arguments to robust coordinate estimates.

  • Quadratic-loss representation: For quadratic losses, the empirical risk on each machine is represented using a Hessian matrix, a linear coefficient, and a constant term.The loss is expressed through quadratic, linear, and constant components.
  • Local estimator analysis: The proof centers on the coordinatewise distribution of each normal machine’s local estimator relative to the population optimum.The k-th coordinate is studied using centered Hessian and linear-term variables.
  • Local estimator analysis: Because the local estimator is not a sample mean of i.i.d. variables, the proof applies a Berry–Esseen bound for functions of sample means.This replaces the vanilla Berry–Esseen argument.
  • Concentration tools: A Hilbert-space Berry–Esseen theorem and moment quantities such as eσ, νp, and ς support the probabilistic control of the estimator.The theorem is stated for random variables in a normed Hilbert space with specified moment conditions.
  • Concentration tools: Lemma 6 yields a probability bound of at least 1 −4e−2t, while the coordinatewise aggregation gives a bound of at least 1 −4de−2t.The latter uses eC = maxk∈[d] Ck.

G Proof of Observation 1

The proof derives a Gaussian indistinguishability lower bound under Byzantine contamination, showing that adversarial machines impose an unavoidable error scale for distributed mean estimation.

  • Gaussian indistinguishability: The lower-bound argument considers two d-dimensional Gaussian distributions with common covariance σ2I and compares their n-sample joint distributions.The joint distributions are equivalent to dn-dimensional Gaussians with repeated mean vectors.
  • Lower bound: The proof reproduces a lower-bound result from robust mean estimation literature for completeness.It cites Chen et al. (2015) and Lai et al. (2016).
  • Gaussian indistinguishability: The construction chooses the means so that the total variation distance between the n-sample distributions matches the adversarial contamination ratio.The stated relation is ∥φ1 −φ2∥1 = α 1 −α.
  • Lower bound: ∥µ1 −µ2∥2 ≥ 2ασ √n(1 −α) ≥2ασ √n is the resulting separation between the Gaussian means.This is the key quantitative lower-bound relation.
  • Lower bound: When the mean separation is Ω( α √n), an adversary can make the distributions impossible to distinguish in the worst case.Consequently, distributed mean estimation has constant-probability error Ω( α √n).
Loading 1803.01498v2…