Source-linked AI summary
Byzantine Stochastic Gradient Descent
Dan Alistarh, Zeyuan Allen-Zhu, Jerry Li
TL;DR
The paper studies distributed stochastic optimization when an α-fraction of workers can behave arbitrarily and adversarially. It introduces ByzantineSGD for convex objectives and establishes near-optimal convergence and sampling guarantees, while identifying a non-optimal first convergence term.
Problem
Distributed stochastic optimization must tolerate an α-fraction of Byzantine workers that can return arbitrary vectors.
Method
The paper develops ByzantineSGD algorithms for convex objectives, including smooth and strongly convex cases, using stochastic-gradient communication between workers and a master.
Results
ByzantineSGD supports α < 1/2 Byzantine workers and has convergence and sampling guarantees that are optimal up to logarithmic factors, including a necessary α^2-related error term.
Takeaways & Limitations
The algorithm preserves the desired distributed runtime and sampling properties in high dimensions while matching traditional SGD as α → 0.
Takeaways & Limitations
The first convergence-rate term in Theorem 1 is not optimal, although it is usually not dominant.
Abstract
from arXiv · showhide
This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of the $m$ machines which allegedly compute stochastic gradients every iteration, an $α$-fraction are Byzantine, and can behave arbitrarily and adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds $\varepsilon$-approximate minimizers of convex functions in $T = \tilde{O}\big( \frac{1}{\varepsilon^2 m} + \frac{α^2}{\varepsilon^2} \big)$ iterations. In contrast, traditional mini-batch SGD needs $T = O\big( \frac{1}{\varepsilon^2 m} \big)$ iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sampling complexity and time complexity.
1 Introduction
The paper develops Byzantine-resilient distributed stochastic optimization for convex objectives, targeting near-optimal sampling, runtime, robustness, and high-dimensional performance. ByzantineSGD tolerates α < 1/2 adversarial workers while preserving useful parallel speedup, and matching lower bounds establish near-optimality up to logarithmic factors.
- Problem: Distributed learning spreads data across worker machines that jointly optimize a global function, but some workers may crash or behave arbitrarily.The Byzantine model allows an α-fraction of workers to send corrupted or malicious information.
- Design goals: Algorithms must balance sample complexity with scalability and computational complexity, including useful performance in high dimensions.The paper seeks information-theoretically optimal samples, few data passes, and no polynomial degradation in dimension.
- Results: ByzantineSGD provides algorithms for smooth convex objectives with α < 1/2 Byzantine machines and extends to smooth, non-smooth, convex, and strongly convex settings.The stated results target finding x with f(x) − f(x*) ≤ ε, up to logarithmic factors and lower-order terms.
- Results: The Byzantine overhead includes an additive α^2-related error term, and a matching information-theoretic lower bound shows this error is necessary.The lower bound also includes the standard sampling terms needed to find an ε-approximate minimizer.
- Limitation: The first convergence-rate term is not optimal, although the paper states it is usually not dominant.This is identified explicitly as a limitation in the discussion of Theorem 1.
- Results: ByzantineSGD preserves an Ω(m) runtime speedup while m remains below a Byzantine- and accuracy-dependent threshold, and matches traditional SGD as α → 0.The paper also claims optimal stochastic-gradient computations and no additional dimension factors as dimension grows.
2 Preliminaries
The paper formalizes Byzantine stochastic optimization with convex objectives, worker-specific stochastic gradients, and arbitrarily adversarial Byzantine responses. Its preliminaries define the optimization model, regularity assumptions, concentration tool, and projected update framework.
- Model: At most an α fraction of m worker machines are Byzantine, and the unknown set of good machines provides bounded, unbiased stochastic-gradient information.Byzantine responses may be adversarially chosen, history-dependent, and collusive.
- Model: The objective is the expectation f(x) of random functions f_s drawn from a distribution over functions that need not be convex.The paper assumes the aggregate objective f is convex.
- Algorithmic setting: The paper measures progress through approximate minimization while targeting sample efficiency and distributed computational efficiency.Each iteration queries all m machines and each machine returns one vector.
- Analysis tools: Pinelis’ inequality supplies concentration for bounded martingale-difference vector processes used in the analysis.Its assumptions are conditional mean zero and a uniform norm bound.
- Analysis tools: The update framework uses a projected mirror-descent-style minimization with learning rate η and a bounded initial-distance region.The stated fact applies to points u satisfying ||u − x1|| ≤ D.
3 ByzantineSGD for Non-Strongly Convex Objectives
ByzantineSGD filters worker machines using accumulated scalar and vector consistency checks, then updates with the retained stochastic-gradient direction. Its guarantees preserve classical non-Byzantine rates while adding Byzantine-dependent error that is optimal up to logarithmic factors.
- Algorithm: ByzantineSGD maintains a candidate-good set and performs each stochastic-gradient update using only its retained machines.The retained direction is denoted ξ_k.
- Algorithm: Three consistency signals—A_i, B_i, and Δ_i—determine whether a machine remains close to robust central estimates.Machines are removed when they exceed thresholds T_A, T_B, or 4V.
- Error decomposition: The algorithm separates error into bias from stochastic and adversarial gradient noise and variance from approximating the true gradient with ξ_k.Good machines are retained, while remaining Byzantine noise is shown to be negligible.
- Guarantees: All good machines remain in every candidate set under the stated concentration events and threshold choices.This follows from the validity of good machines for the scalar, vector, and gradient median tests.
- Smooth case: For smooth convex objectives, Theorem 3.8 gives a convergence bound whose first terms match classical mini-batch SGD and whose Byzantine term is optimal in this setting.The theorem assumes L-smoothness, Assumption 2.2, η ≤ 1/(2L), and T_A = 4DV√…; the displayed bound is truncated in the supplied passage.
- Nonsmooth case: For nonsmooth convex objectives, Theorem 3.9 likewise matches the classical mini-batch SGD rate in its non-Byzantine terms and has an optimal Byzantine contribution.The result assumes differentiability, G-Lipschitz continuity, and Assumption 2.2.
4 ByzantineSGD in Strongly Convex Objectives
For strongly convex objectives, the paper repeatedly applies ByzantineSGD across shrinking-error epochs. The resulting smooth and nonsmooth guarantees retain classical mini-batch terms and achieve optimal Byzantine dependence up to logarithmic factors.
- Scope: The paper assumes the smooth strongly convex problem is unconstrained for its simplest presentation.An additional constraint ||x − x0|| ≤ D is possible but omitted.
- Epoch reduction: The strongly convex method is epoch-based: each epoch starts from a progressively smaller distance guarantee and invokes ByzantineSGD again.The method uses a logarithmic number of epochs.
- Smooth case: The smooth strongly convex bound’s first terms match classical mini-batch SGD, while its Byzantine term is optimal in the Byzantine setting.The comparison is stated for the non-Byzantine terms and Theorem 5.4 establishes optimality of the Byzantine term.
- Nonsmooth case: For nonsmooth strongly convex objectives, the classical mini-batch terms are retained and the Byzantine term is optimal in the stated setting.The result is based on repeatedly applying Theorem 3.9.
5 Lower Bounds in Byzantine Stochastic Optimization
The lower-bound section proves that Byzantine stochastic optimization remains hard even in one dimension, using subgaussian stochastic estimators and reductions from indistinguishable Gaussian-mixture cases. These bounds match the algorithmic rates up to logarithmic factors.
- Setup: The lower bounds apply even in d = 1 and establish optimality of the convergence rates up to logarithmic factors.The construction uses subgaussian stochastic estimators with variance proxy V^2.
- Setup: The lower-bound model differs from the upper-bound assumption by using subgaussian rather than uniformly bounded stochastic-gradient errors.Concentration makes this difference affect the bounds only by a log(mT) factor.
- Hardness reduction: Lemma 5.3 supplies two indistinguishable cases built from Gaussian distributions whose means differ by O(α), preventing reliable case identification.The impossibility holds for α in (0, 0.1) and success probability at least 2/3.
- Convex lower bound: Theorem 5.4 constructs linear objectives showing that no algorithm can achieve ε-approximate minimization with probability at least 2/3 below the stated sample threshold.The hard instances use functions f+(x) = εx/D and f−(x) = −εx/D on [−D, D].
- Convex lower bound: The linear lower bound is proved by converting any successful optimizer into a distinguisher for the two cases in Lemma 5.3.The optimizer’s output sign identifies which linear objective generated the samples.
- Strongly convex lower bound: Theorem 5.5 gives an analogous lower bound for strongly convex quadratic objectives, including objective-error implications from distance-error hardness.The theorem concerns output distance from the minimizer, and the following passage transfers it to function-value error.