Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks

Zhaoxian Wu; Qing Ling; Tianyi Chen; Georgios B. Giannakis

Source-linked AI summary

Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks

Zhaoxian Wu, Qing Ling, Tianyi Chen, Georgios B. Giannakis

arXiv:1912.12716v2Dec 29, 2019cs.LGcs.AIcs.CRstat.ML

TL;DR

Byzantine attacks make distributed finite-sum optimization difficult because stochastic-gradient noise can obscure malicious messages. The paper proposes Byrd-SAGA, which combines SAGA variance reduction with geometric-median aggregation. Under fewer than half Byzantine workers, it proves linear convergence to a neighborhood whose asymptotic error is determined by the number of attackers, with numerical tests supporting robustness to various attacks.

Problem
Stochastic-gradient noise makes it challenging to distinguish malicious Byzantine messages from noisy gradients sent by honest workers.
Method
Byrd-SAGA combines SAGA variance reduction with geometric-median aggregation of corrected stochastic gradients.
Results
With fewer than half the workers Byzantine, Byrd-SAGA achieves provable linear convergence to a neighborhood of the optimum, with asymptotic error determined by the number of Byzantine workers.
Takeaways & Limitations
Numerical tests support Byrd-SAGA’s robustness to various Byzantine attacks and its advantages over Byzantine-resilient distributed SGD.

Abstract

from arXiv · show

This paper deals with distributed finite-sum optimization for learning over networks in the presence of malicious Byzantine attacks. To cope with such attacks, most resilient approaches so far combine stochastic gradient descent (SGD) with different robust aggregation rules. However, the sizeable SGD-induced stochastic gradient noise makes it challenging to distinguish malicious messages sent by the Byzantine attackers from noisy stochastic gradients sent by the 'honest' workers. This motivates us to reduce the variance of stochastic gradients as a means of robustifying SGD in the presence of Byzantine attacks. To this end, the present work puts forth a Byzantine attack resilient distributed (Byrd-) SAGA approach for learning tasks involving finite-sum optimization over networks. Rather than the mean employed by distributed SAGA, the novel Byrd- SAGA relies on the geometric median to aggregate the corrected stochastic gradients sent by the workers. When less than half of the workers are Byzantine attackers, the robustness of geometric median to outliers enables Byrd-SAGA to attain provably linear convergence to a neighborhood of the optimal solution, with the asymptotic learning error determined by the number of Byzantine workers. Numerical tests corroborate the robustness to various Byzantine attacks, as well as the merits of Byrd- SAGA over Byzantine attack resilient distributed SGD.

I. INTRODUCTION

Federated learning preserves data locality but remains vulnerable to Byzantine devices whose arbitrary messages can mislead optimization. The paper addresses the difficulty of separating malicious messages from noisy honest stochastic gradients by combining variance reduction with robust aggregation.

Federated learning keeps data private by performing local computation and aggregating updates at a datacenter.
Byzantine devices can send malicious messages that mislead the learning process, making robustness important for secure federated learning.
Robust SGD can converge near the attack-free optimum, but carefully crafted attacks may produce a large neighborhood because stochastic gradients contain approximation noise.
Reducing stochastic-gradient noise is proposed to make malicious messages easier to distinguish from honest stochastic gradients.
Byrd-SAGA combines SAGA variance reduction with geometric-median aggregation and achieves linear convergence to a neighborhood whose asymptotic error depends on the number of Byzantine workers.
The model considers W workers with B unidentified Byzantine attackers and assumes B < W/2 for the proposed tolerance guarantee.

C. Byzantine attack resilient distributed SGD

Geometric-median aggregation improves Byzantine resilience, but stochastic-gradient noise makes malicious messages difficult to distinguish from honest updates. Variance reduction, particularly through SAGA, is introduced to address this challenge.

Geometric median represents received messages through majority voting and approximates the honest-message mean when B < W/2.
Under B < W/2, Byzantine-resilient distributed SGD converges to a neighborhood of the optimum.
Honest workers’ stochastic gradients are noisy because workers randomly select data samples, complicating detection of malicious messages.
Small honest-worker gradient variance narrows the gap between the true mean and geometric-median aggregate, making identical Byzantine attacks less effective.
Variance reduction compensates for stochastic-gradient noise and can yield faster convergence than SGD; the paper focuses on SAGA for finite-sum optimization.
Distributed SAGA stores local stochastic gradients, corrects each newly sampled gradient using stored values, and updates the model after aggregation.

B. Distributed SAGA with geometric median aggregation

Byrd-SAGA combines distributed SAGA’s corrected-gradient storage with geometric-median aggregation to withstand Byzantine messages. The method uses an approximate geometric median in practice, with only a slight reported effect on convergence.

Byzantine workers may send malicious messages instead of corrected stochastic gradients, so worker-to-master messages must accommodate adversarial behavior.
Byrd-SAGA replaces distributed SAGA’s mean aggregation with geometric-median aggregation and is specified in the Byzantine-resilient SAGA update.
Algorithm 1 initializes the model, gradient-storage tables, and average gradients before the master broadcasts iterates to workers.
The master aggregates worker messages with the geometric median before updating the model iterate.
Alternative aggregators include the median, Krum, marginal trimmed mean, and iterative filtering, while other variance-reduction methods remain possible extensions.
Because exact geometric-median computation is costly, the method typically uses an ϵ-approximate value, which only slightly affects Byrd-SAGA convergence.

IV. THEORETICAL ANALYSIS

The theoretical analysis explains how variance reduction improves geometric-median robustness and establishes Byrd-SAGA convergence under Byzantine attacks. With fewer than half the workers Byzantine, the method converges linearly to a neighborhood whose asymptotic error depends on attacker prevalence and gradient variation.

Variance reduction and geometric-median aggregation: The geometric-median mean-square error relative to the true gradient decomposes into inner variation and outer variation terms.Inner variation comes from stochastic-gradient variances at honest workers, while outer variation measures local-gradient deviations from the true gradient.
Variance reduction and geometric-median aggregation: Byrd-SAGA combines variance reduction with geometric-median aggregation to reduce the impact of stochastic-gradient noise under Byzantine attacks.The analysis focuses particularly on reducing inner variation while using robust aggregation.
Convergence of Byrd-SAGA: Under strong convexity, Lipschitz-continuous gradients, fewer than half Byzantine workers, and a suitable step size, Byrd-SAGA converges linearly to a neighborhood of the optimum.The theorem allows ϵ-approximate geometric-median aggregation.
Convergence of Byrd-SAGA: The convergence rate slows and the asymptotic learning error increases as the Byzantine-worker fraction grows.The convergence constant, step-size upper bound, and asymptotic error all worsen with the geometric-median factor C_α.
Comparison with Byzantine attack resilient SGD: The analysis compares both methods in mean-square error under geometric-median aggregation and relies on bounded outer and inner variation assumptions.The assumptions bound gradient variation across honest workers and stochastic-gradient variation within honest workers.
Comparison with Byzantine attack resilient SGD: Byrd-SAGA can have zero asymptotic error when outer variation is zero, regardless of inner variation, whereas resilient SGD remains proportional to inner variation.When honest workers have distinct data samples, resilient SGD’s error can be large while Byrd-SAGA achieves smaller learning error.

V. NUMERICAL EXPERIMENTS

The numerical experiments evaluate Byrd-SAGA and related distributed optimization methods on convex and nonconvex learning problems under three Byzantine attacks. Experiments use honest and Byzantine worker populations, approximate geometric medians, and comparisons across datasets and aggregation rules.

Experimental setup: Experiments use 50 honest workers and 20 Byzantine workers unless otherwise indicated.The tested attacks are Gaussian, sign-flipping, and zero-gradient attacks.
Experimental setup: The study tests Gaussian, sign-flipping, and zero-gradient Byzantine attacks using an ϵ-approximate geometric median with ϵ = 1 × 10^-5.The Gaussian attack uses variance 30, and the sign-flipping attack uses magnitude u = −3.
Dataset comparisons: Figure 3 evaluates distributed SGD, mini-batch BSGD, and SAGA with mean and geometric-median aggregation on IJCNN1.Rows show optimality gap and honest-message variance; columns represent no attack, Gaussian, sign-flipping, and zero-gradient attacks.
Dataset comparisons: Figure 4 applies the same method and aggregation comparisons to the COVTYPE dataset.The figure uses the same row and column organization as Figure 3, with dataset-specific step sizes.

A. ℓ2-regularized logistic regression

Experiments on logistic regression compare variance-reduced and stochastic methods under Byzantine attacks, showing that Byrd-SAGA combines low message variance with robust geometric-median aggregation. Its theoretical and numerical behavior includes linear convergence to an attack-dependent neighborhood and vanishing error when outer variation is zero.

Comparisons: Under Byzantine attacks, all three mean-aggregation algorithms fail, while Byrd-SAGA markedly outperforms geometric-median SGD and BSGD.Geometric-median BSGD performs better than geometric-median SGD.
Variance: 10^-3, 10^-2, and 10^-1 are the reported honest-message variance orders for Byrd-SAGA, resilient BSGD, and resilient SGD on IJCNN1.For COVTYPE, Byrd-SAGA and resilient BSGD have the same or closely related variance behavior in the reported comparison.
Theory and validation: When outer variation δ2 = 0, Byrd-SAGA’s asymptotic learning error is zero regardless of inner variation σ2.The second experiment assigns every honest worker the whole IJCNN1 dataset, yielding δ2 = 0.
Aggregation rules: Across aggregation rules, mean is best without attacks but fails under attacks; geometric median performs best against Gaussian attacks, while Krum performs best against sign-flipping and zero-gradient attacks.Geometric median and median do not require prior knowledge of the exact number of Byzantine attackers, unlike Krum.
Method: Byrd-SAGA combines SAGA variance reduction with geometric-median aggregation instead of distributed SAGA’s mean.The method aggregates corrected stochastic gradients from distributed workers.
Theory and validation: Byrd-SAGA converges linearly to a neighborhood of the optimum, with asymptotic learning error determined solely by the number of Byzantine workers.This is established for the proposed method when fewer than half of workers are Byzantine.

APPENDIX A PROOF OF LEMMA 1

The appendix proves a geometric-median bound for random vectors and extends it to an ϵ-approximate geometric median. The argument uses norm inequalities, the geometric-median definition, squaring, and expectation-taking.

Lemma 2: Lemma 2 bounds the geometric median’s relation to a subset of random vectors when that subset contains fewer than half of the vectors.The proof separates vectors inside and outside the subset, then sums distance inequalities.
Proof: The proof completes by squaring the resulting inequality and taking expectations.Variance decomposition is used in the surrounding proof steps.
Approximate geometric median: Because the exact geometric median is difficult to compute, the appendix introduces an ϵ-approximate counterpart of Lemma 2.The same proof pattern is applied to the approximate geometric median bound.

APPENDIX C LEMMA 4 AND ITS PROOF

Lemma 4 analyzes the bias and mean-square error of Byrd-SAGA’s ϵ-approximate geometric-median aggregate. Its condition requires fewer than half of the workers to be Byzantine, and the bound includes a time-varying term S_k.

Proof: The geometric-median aggregate is treated as a biased gradient estimate, whose error is bounded through a mean-square analysis.The proof begins by upper-bounding E∥m_k^w − f′(x_k)∥^2.
Lemma 4: When B < W/2, Lemma 4 characterizes the error between the ϵ-approximate geometric median of worker messages and the true gradient f′(x_k).The lemma applies under Assumptions 1 and 2.
Proof: The resulting error bound contains the time-varying quantity S_k, whose evolution is handled separately.S_k is defined in the lemma’s notation and recurs in the subsequent bound.

APPENDIX D LEMMA 5 AND ITS PROOF

Lemma 5 bounds the evolution of the variance-reduction state S_k in Byrd-SAGA. The recursion depends on the update residual, distance to the optimum, smoothness, and a contraction term.

Lemma 5: Lemma 5 gives a recursion for E[S_{k+1}] under Assumption 1.S_k is the time-varying quantity appearing in the Lemma 4 error bound.
Bound: The bound includes 4J·E∥x_{k+1}−x_k+γf′(x_k)∥^2 and 4Jγ^2L^2∥x_k−x∗∥^2.It also contains a coefficient beginning with the contraction term (1 − 1…, as shown in the displayed passage.
Proof: The proof uses norm inequalities, uniform random selection of one data sample, and f′(x∗) = 0.These steps bound the update residual and the distance-dependent term in the recursion.

APPENDIX E PROOF OF THEOREM 1

The proof bounds the optimization error using strong convexity, Lipschitz gradients, and a Lyapunov function. A suitable step size and telescoping argument then complete the convergence analysis.

Strong convexity and Lipschitz continuity bound the gradient terms by the squared distance to the optimum.The proof uses f′(x∗) = 0, µ-strong convexity, and L-Lipschitz continuous gradients.
The analysis constructs a non-negative Lyapunov function T_k from the error and the non-negative quantity S_k.The constant c is chosen positive, ensuring T_k is non-negative.
The resulting recursion is controlled by imposing bounds on the step size γ and the coefficient multiplying S_k.The proof explicitly invokes conditions (52), (58), and (59), including γµ + µ/(2γL^2) ≤ 5γµ/2.
Telescopic cancellation across slots converts the one-step inequality into the stated convergence bound.The argument applies cancellation from slot 1 through slot k before concluding the proof.

APPENDIX F PROOF OF THEOREM 2

Theorem 2’s proof adapts the preceding error analysis to Byzantine attack-resilient SGD. It preserves the main recursion under a stricter step-size condition and completes the argument through telescoping.

The Byzantine-resilient SGD analysis retains inequality (53) when γ < µ/(2L^2).The passage identifies this step-size restriction as sufficient for the corresponding error bound.
The Byzantine setting changes the stochastic-error term E∥x_{k+1} − x_k + γf′(x_k)∥^2 while the remaining derivation is analogous.The proof states that the altered term is the only difference in the corresponding bound.
Telescopic cancellation from slot 1 to slot k yields the final result for Byzantine attack-resilient SGD.The proof then concludes after applying the cancellation argument.