PaperlayerView exact revision on arXiv

Source-linked AI summary

Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences

Grigory Malinovsky, Peter Richtárik, Samuel Horváth, Eduard Gorbunov

arXiv:2311.14127v2cs.LGcs.AIcs.DCmath.OC

TL;DR

Provable Byzantine-robust methods have required full client participation, although large distributed systems need client sampling and may encounter Byzantine majorities among sampled workers. This paper introduces a clipped, variance-reduced method with partial participation and communication compression. Its convergence guarantees match prior state-of-the-art results in stated regimes, and partial participation can be beneficial in some cases.

  • Problem

    Existing methods with provable Byzantine robustness require full participation, limiting their fit to settings where clients are sampled or unavailable.

    Source: §1 · pp. 1–2

  • Method

    Byz-VR-MARINA-PP combines recursive variance reduction, clipping of compressed stochastic gradient differences, and client sampling.

    Source: §1 · p. 2, §4 · p. 8

  • Results

    The method achieves an O(1/K) rate for general non-convex functions and linear convergence to a heterogeneity-dependent neighborhood for PŁ functions, with some cases matching Byz-VR-MARINA’s rate using O(C) workers on average.

    Source: §4 · pp. 7–8

  • Takeaways & Limitations

    Clipping offers a proposed heuristic for adapting Byzantine-robust methods to partial participation, while the paper identifies its rigorous analysis for other methods as future work.

    Source: §4 · p. 8, §6 · p. 10

    The analysis leaves open improving bounds’ dependence on ω, m, and C, proving the heuristic for other methods, and studying non-uniform or arbitrary participation.

    Source: §6 · p. 10

Abstract

from arXiv · show

Distributed learning has emerged as a leading paradigm for training large machine learning models. However, in real-world scenarios, participants may be unreliable or malicious, posing a significant challenge to the integrity and accuracy of the trained models. Byzantine fault tolerance mechanisms have been proposed to address these issues, but they often assume full participation from all clients, which is not always practical due to the unavailability of some clients or communication constraints. In our work, we propose the first distributed method with client sampling and provable tolerance to Byzantine workers. The key idea behind the developed method is the use of gradient clipping to control stochastic gradient differences in recursive variance reduction. This allows us to bound the potential harm caused by Byzantine workers, even during iterations when all sampled clients are Byzantine. Furthermore, we incorporate communication compression into the method to enhance communication efficiency. Under general assumptions, we prove convergence rates for the proposed method that match the existing state-of-the-art (SOTA) theoretical results. We also propose a heuristic on adjusting any Byzantine-robust method to a partial participation scenario via clipping.

1 Introduction

Distributed learning must withstand Byzantine workers, whose arbitrary updates can undermine standard aggregation, while accommodating partial client participation. The paper introduces a clipped, variance-reduced method for this setting and situates it among prior robustness and client-sampling approaches.

1 Introduction

  • Standard averaging is vulnerable because one Byzantine worker can send an arbitrarily large vector and shift the method arbitrarily far from the solution.Byzantine workers may violate the protocol intentionally or through faults, and may collude.Source: §1 · p. 2
  • Existing Byzantine-robust methods require full participation, an impractical condition for systems with millions of clients or unavailable participants.Naive partial participation can let Byzantine workers form a majority in a round and disrupt convergence.Source: §1 · p. 2
  • Byz-VR-MARINA-PP is presented as the first method with provable Byzantine robustness and partial client participation, using clipping to bound Byzantine harm even during majority-Byzantine rounds.The method also incorporates communication compression and is analyzed for smooth non-convex and Polyak–Łojasiewicz functions.Source: §1 · p. 2

1.1 Related Work

  • Prior Byzantine-robust approaches include robust aggregation and variance reduction, with Byz-VR-MARINA reporting improved convergence guarantees.The introduction notes that robust aggregation alone can be bypassed by specially designed attacks.Source: §1.1 · pp. 2–3
  • Data and Diggavi (2021) analyze partial participation but require at least three times as many participating clients as Byzantine workers.Byz-VR-MARINA-PP is described as converging even when the server samples one client that may be Byzantine.Source: §1.1 · p. 3

2 Preliminaries

The paper formulates distributed finite-sum optimization with regular and Byzantine clients, defines robust aggregation and compression assumptions, and lists conditions used in its convergence analysis.

Problem setting

  • The model separates regular clients from Byzantine clients and assumes the Byzantine fraction is bounded by δ < 1/2.The text states that the problem is impossible to solve in general when Byzantine workers form a majority.Source: §2 · p. 3

Robust aggregation

  • A (δ, c)-agnostic robust aggregator approximates the average of regular clients without requiring knowledge of their gradient variance.The definition builds on a robust aggregation rule whose guarantee is measured against the regular-client average.Source: §2 · p. 3

Compression operators

  • The analysis uses unbiased compression operators with relatively bounded variance, characterized in part by expected output density.The paper identifies random sparsification and quantization as examples of this compressor class.Source: §2 · p. 4

Assumptions

  • The assumptions include bounded aggregation output, smooth local losses, a lower-bounded objective, and bounded heterogeneity among regular clients.An optional bounded-compressor assumption is also used for some results; the text says results without it have worse dependence on some parameters.Source: §2 · p. 4
  • The framework also considers the optional Polyak–Łojasiewicz condition, which the paper associates with the possibility of linear convergence.The algorithm samples either C or bC clients and uses clipping coefficients in its updates.Source: §2 · p. 5

3 New Method: Byz-VR-MARINA-PP

Byz-VR-MARINA-PP extends Byz-VR-MARINA to partial participation by clipping compressed stochastic gradient differences. Recursive variance reduction makes the stochastic-gradient variance scale with the step difference, while clipping bounds updates even when all sampled clients are Byzantine.

Special case: Byz-VR-MARINA

  • With full participation and clipping disabled, Byz-VR-MARINA-PP reduces to Byz-VR-MARINA, whose regular workers use a GeomSARAH/PAGE-type gradient estimator.With probability p workers compute full gradients; otherwise they update the estimator using stochastic gradient differences.Source: §3 · p. 5
  • Recursive variance reduction makes the variance of regular workers’ estimators proportional to the squared step difference with probability 1 − p, progressively limiting Byzantine attacks.Unbiased compression fits the method because it is applied to the stochastic gradient difference.Source: §3 · p. 6

New ingredients: client sampling and clipping

  • With probability 1 − p, the method samples C clients; with probability p, it samples a larger group of bC clients.Clipping is applied to compressed stochastic gradient differences, and the critical case occurs when more than δC sampled workers are Byzantine.Source: §3 · p. 6
  • Clipping lets Byz-VR-MARINA-PP tolerate arbitrary attacks even when every sampled client is Byzantine, because the update remains bounded.Choosing the clipping threshold proportional to the step difference makes transmitted-vector norms decrease at the rate used by full-participation Byz-VR-MARINA.Source: §3 · p. 6

4 Convergence Results

Byz-VR-MARINA-PP combines client sampling with clipped gradient differences to tolerate Byzantine workers, including rounds when they form a majority. Its convergence guarantees broadly match Byz-VR-MARINA’s, though some bounds carry costs from clipping and partial participation.

Method

  • The method clips stochastic gradient differences within variance reduction to bound Byzantine harm, even when Byzantine workers form a majority in a round.It also incorporates communication compression; the theorem discussion covers general unbiased compression operators.Source: §4 · p. 6

Convergence guarantees

  • The method achieves O(1/K) convergence for general non-convex objectives and linear convergence to a heterogeneity-dependent neighborhood for PŁ-functions.These guarantees are similar to Byz-VR-MARINA’s, but the analyzed maximal stepsize is smaller under partial participation.Source: §4 · p. 7
  • The convergence bound’s constant scales as 1/p^2, and the full-participation special case does not recover Byz-VR-MARINA’s result under this theorem.The paper attributes the extra term to partial participation and notes the resulting bound can be worse when p is small.Source: §4 · p. 7
  • A second theorem uses a larger clipping level that can remove a 1/p factor from some terms, but its rates are not directly comparable because DQ may be large.In partial participation, the larger clipping level also comes with a reduced stepsize to compensate for increased Byzantine harm when attackers form a majority.Source: §4 · p. 8

Partial participation

  • When pG = 1, some regimes retain Byz-VR-MARINA’s convergence rate while using O(C) workers per round instead of n.The cited comparison identifies this as beneficial in some cases, particularly when cδ ≥ p/C.Source: §4 · p. 8

Heuristic extension

  • The authors suggest adapting other Byzantine-robust methods to sampled clients by clipping updates at a server-set level λk+1 = λ∥xk+1 − xk∥.Byz-VR-MARINA-PP is presented as an application of this scheme, up to a minor modification.Source: §4 · p. 8

5 Numerical Experiments

The experiments test clipping in Byzantine settings with partial participation, first on homogeneous logistic regression and then on heterogeneous neural-network tasks. Clipping supports convergence under shift-back attacks, while results across additional attacks show no performance degradation relative to the unclipped variant.

5 Numerical Experiments

  • The logistic-regression experiment uses a9a with 15 good and five Byzantine workers, each accessing the full dataset, and coordinate-wise median with bucketing.The attack sends x0 − xk when Byzantine workers are the round's majority; otherwise, they follow the benign protocol.Source: §5 · p. 9
  • Clipping yields linear convergence to the exact solution where the unclipped method fails, even in the favorable homogeneous setup with shift-back attacks.The unclipped method remains stuck because Byzantine workers can form a majority in some rounds.Source: §5 · p. 9
  • Partial participation with clipping converges faster by total computations than full participation without clipping, and all tested clipping multipliers retain linear convergence.A suboptimal multiplier slows convergence.Source: §5 · p. 9
  • On heterogeneous MNIST neural-network tasks, clipping performs on par with or better than its unclipped variant, while no tested robust aggregator withstands shift-back without clipping.The experiments use 20 clients, five malicious clients, four attacks, and coordinate median or robust federated averaging with bucketing.Source: §5 · pp. 9–10

6 Conclusion and Future Work

The conclusion identifies open questions about sharper bounds, rigorous guarantees for the heuristic, and broader participation patterns. The appendices compare related methods and give supporting facts, aggregation bounds, and refined assumptions.

6 Conclusion and Future Work

  • Open questions include improving dependence on ω, m, and C, proving the heuristic for client-momentum SGD and other robust methods, and analyzing non-uniform or arbitrary participation.Source: §6 · p. 10

A Extra Related Work

  • Earlier Byzantine-robust partial-participation work requires at least three participating clients per Byzantine worker, whereas this method can converge when only one client is sampled, even if Byzantine.Source: A Extra Related Work · pp. 16–17
  • The paper presents clipping for partial-participation robustness as a novel application, with GeomSARAH/PAGE-type variance reduction as a core building block.Source: A Extra Related Work · pp. 16–17

B Useful Facts

  • For a,b>0, γ≤1/√(a+b) ensures aγ^2+bγ≤1, and the bound is tight within a factor of 2.Source: B Useful Facts · p. 18

C Justification of Assumption 2.3

D.1 Refined Assumptions

  • Under smoothness of individual losses, the local Hessian variance assumption can hold for standard uniform and importance sampling strategies.Source: §D.1 · p. 21
  • The refined heterogeneity assumption recovers the original when B=0 and can cover some over-parameterized settings with smaller ζ^2.Source: §D.1 · p. 21

D.2 Technical Lemmas

The technical lemmas establish intermediate bounds for Byz-VR-MARINA-PP under smoothness, aggregation, and compression assumptions. They include a clipping result for bounded-mean random vectors and bounds for the method’s iterates.

D.2 Technical Lemmas

  • When E[X] = x and ∥x∥≤λ/2, Lemma D.6 analyzes the clipped random vector clipλ(X).The passage introduces this condition but does not include the lemma’s resulting bound.Source: §D.2 · p. 22
  • Lemma D.7 gives a descent inequality for an L-smooth function when the update is xk+1 = xk − γgk.It identifies the smoothness condition and update used in the inequality.Source: §D.2 · p. 22

Also let us introduce the notation

D.3 Main Results

The main-results section states convergence bounds for Byz-VR-MARINA iterates under specified assumptions. One result also describes a uniformly sampled iterate, but the supplied passages do not include the bound expressions.

D.3 Main Results

  • Theorem D.14 states a bound for Byz-VR-MARINA iterates under Assumptions 2.3, D.1, D.2, D.3, and D.5.The supplied theorem statement does not include the bound expression.Source: §D.3 · pp. 36, 38
  • The passage states that bxK is chosen uniformly at random from the iterates x0, x1, …, xK, and that Φ0 = f.Source: §D.3 · p. 36

E.1 Technical Lemmas

The technical lemmas give intermediate iterate bounds for Byz-VR-MARINA-PP under stated assumptions. The supplied passages also describe a clipping-threshold choice used in the analysis.

E.1 Technical Lemmas

  • Lemma E.1 introduces an ideal estimator under assumptions including compression and sets λk+1 using DQ maxi,j Li,j.The passage does not show the resulting estimator bound.Source: §E.1 · p. 40
  • The analysis states that this λk+1 choice can make the clipping operator identical under the specified condition on clients in G.The supplied statement begins with λk+1 = DQ maxi,j Li,j∥xk+1 − xk∥ and gives the condition only partially.Source: §E.1 · p. 45

E.2 Main Results

Theorems E.4 and E.5 state bounds for Byz-VR-MARINA iterates under specified assumptions and clipping-threshold settings. The supplied passages do not include the bound expressions.

E.2 Main Results

  • Theorem E.4 states a bound for Byz-VR-MARINA iterates under Assumptions 2.3, D.1, D.2, D.3, D.5, and 2.4.Its statement sets λk+1 using maxi,j Li,j and xk+1 − xk; the supplied text omits part of the expression.Source: §E.2 · p. 50
  • Theorem E.5 states a bound for Byz-VR-MARINA iterates under Assumptions 2.3, 2.4, D.1, D.2, D.3, D.5, and 2.7.Its supplied statement gives a clipping-threshold setting but omits part of the expression and the resulting bound.Source: §E.2 · pp. 50–51

E.3 On the Technical Non-Triviality of the Analysis

The analysis uses a movement-scaled clipping threshold to control Byzantine shifts, including rounds when Byzantine workers are the majority. It also addresses the added difficulties from client sampling and compression.

E.3 On the Technical Non-Triviality of the Analysis

  • Setting the clipping level to λ_k+1 = α_k+1∥x_k+1 − x_k∥ lets the method bound Byzantine shift second moments at the scale of ∥x_k+1 − x_k∥².The passage says this is comparable to the variance of good-worker gradient differences, which goes to zero.Source: §E.3 · p. 51
  • With uncompressed communication and sufficiently large α_k+1, clipping leaves good-worker gradient differences unchanged, supporting analysis when good workers are the round's majority.The threshold choice also bounds Byzantine shifts when Byzantine workers form a majority.Source: §E.3 · p. 51
  • The proof handles two stochasticity sources—client sampling and stochastic gradients—and compression prevents direct use of the usual unbiased-compression property.The passage identifies a variance bound for an average of a random number of random vectors as a non-standard step.Source: §E.3 · p. 51
  • Unlike Byz-VR-MARINA, Byz-VR-MARINA-PP needs only a sufficiently large sampled cohort with probability p, not full participation even at small p.Such rounds ensure Byzantine workers are a minority.Source: §E.3 · p. 51

F.1 Experimental Details

The experiments use fixed-step training without learning-rate warmup or decay, and partial participation samples 20% of clients per round. Runs use three random seeds and report mean optimality gaps with one standard error.

F.1 Experimental Details

  • For partial participation, each round uniformly samples 20% of clients.The step size is tuned from {0.1, 0.01, 0.001} and then fixed, with no learning-rate warmup or decay.Source: §F.1 · p. 52
  • All methods use batches of size 32, and the clipping coefficient λ is selected from {0.1, 1., 10.}.Clipping uses λ_k = λ∥x_k − x_k−1∥.Source: §F.1 · p. 52
  • Each experiment runs with three random seeds and reports mean optimality gap with one standard error, using 1000-epoch full-dataset gradient descent for the optimum.Attack and robust-aggregation implementations are based on Gorbunov et al. (2023).Source: §F.1 · p. 52

F.2 Extra Experiments

The extra neural-network experiments evaluate two aggregation rules under four attacks on heterogeneous MNIST splits. Figures 3 and 4 present training loss and testing accuracy, respectively.

F.2 Extra Experiments

  • The experiments use MNIST with heterogeneous splits, 20 clients, and five malicious clients.Figures 3 and 4 show the training-loss and testing-accuracy results for this setting.Source: §F.2 · p. 52, Figure 3 · p. 52, Figure 4 · p. 52
  • The four attacks are A Little is Enough (ALIE), Bit Flipping (BF), Label Flipping (LF), and Shift-Back (SHB).The figure captions identify these attacks as the conditions under which the aggregation rules are evaluated.Source: §F.2 · p. 52, Figure 3 · p. 52, Figure 4 · p. 52
  • Coordinate median (CM) and robust federated averaging (RFA) with bucketing are the aggregation rules evaluated.Figure 3 reports training loss, while Figure 4 reports testing accuracy.Source: §F.2 · p. 52, Figure 3 · p. 52, Figure 4 · p. 52
Loading 2311.14127v2…