BRIDGE: Byzantine-resilient Decentralized Gradient Descent

I. INTRODUCTION

• Undetected Byzantine failures can undermine decentralized learning, motivating algorithms with provable resilience and sample-complexity guarantees for convex and nonconvex losses.The paper frames sample complexity as the rate at which the ERM solution approaches the Bayes-optimal solution as the number of training samples grows.Source: §I · p. 1

A. Relationship to prior works

• Prior Byzantine-resilient decentralized methods addressed scalar models or specialized vector-valued problems, while general vector-valued learning remained an open need.ByRDiE addressed a restricted convex-loss class but its coordinate-wise updates make large-scale models costly; BRIDGE instead uses gradient-descent-style updates.Source: A. Relationship to prior works · p. 2

B. Our contributions

• BRIDGE uses gradient-descent-style updates to reduce computation and communication relative to ByRDiE’s one-coordinate-at-a-time approach.Nodes compute a d-dimensional gradient and exchange a d-dimensional model once per iteration, rather than performing d gradient computations and network-wide collaborative steps.Source: B. Our contributions · p. 3
• BRIDGE-T is analyzed for Byzantine resilience, with algorithmic and statistical convergence rates for certain convex and nonconvex loss classes.The convex-setting rates match those established for ByRDiE.Source: B. Our contributions · p. 3
• Experiments on MNIST and CIFAR-10 cover convex and nonconvex problems and both i.i.d. and non-i.i.d. data distributions across agents.The authors report that the results highlight BRIDGE’s benefits and validate the theoretical findings.Source: B. Our contributions · p. 3
• To the authors’ knowledge, BRIDGE is the first Byzantine-resilient decentralized learning algorithm combining scalability, results for a class of nonconvex problems, and both convergence-rate types.Source: B. Our contributions · p. 3

A. Preliminaries

• The preliminaries define statistical risk and empirical risk minimization, emphasizing that learning seeks both algorithmic convergence and statistical convergence to a risk minimizer.In practice, the statistical risk is unavailable when the data distribution is unknown, motivating empirical risk minimization from sampled data.Source: A. Preliminaries · p. 4
• The theoretical analysis treats strongly convex losses and nonconvex losses with local strong convexity; the latter guarantees are local and require initialization near a stationary point.The paper also notes that its convergence rates depend on model dimension.Source: A. Preliminaries · pp. 4–5

B. System model for decentralized learning

• A static, connected graph models M nodes that communicate with neighbors, each holding a local dataset; equal dataset sizes are assumed for simplicity.The paper states that extending results to unequal local dataset sizes is straightforward.Source: B. System model for decentralized… · p. 5
• Decentralized ERM has nodes maintain local models and collaborate, since the centralized empirical-risk problem requires gathering data at one location.Source: B. System model for decentralized… · p. 5

C. Byzantine-resilient decentralized learning

• A Byzantine node may deviate from its update rule or broadcast unintended information, and the number of such nodes is bounded by b.The paper denotes nonfaulty nodes by R and assumes their set is not known to the algorithm.Source: C. Byzantine-resilient decentralized… · p. 5
• Because Byzantine nodes prevent solving the decentralized ERM over all nodes, the goal is to solve a variant restricted to nonfaulty nodes despite their unknown identities.Source: C. Byzantine-resilient decentralized… · p. 5
• The network must retain a source component of at least b + 1 nodes in every reduced graph, ensuring nonfaulty nodes retain redundant information flow.Efficient certification of this connectivity assumption remains open; the authors report that Erdős–Rényi graphs often satisfy it when the least-connected node’s degree exceeds 2b.Source: C. Byzantine-resilient decentralized… · pp. 5–6
• The statistical analysis uses sample complexity to characterize the gap between local-only learning and collaboration on a common model.With finite samples, local empirical risks differ across nonfaulty nodes whether data are i.i.d. or non-i.i.d.Source: C. Byzantine-resilient decentralized… · p. 6

III. BYZANTINE-RESILIENT DECENTRALIZED GRADIENT DESCENT

• BRIDGE screens incoming neighbor messages before each local update and updates the entire model vector in one iteration, avoiding ByRDiE’s one-coordinate-at-a-time pattern.The framework does not permanently label nodes as malicious, allowing it to manage transitory Byzantine failures.Source: §III · p. 6
• BRIDGE-T trims the b largest and b smallest values per coordinate, averages the remainder, and requires at least 2b + 1 neighbors.Different neighbors may survive screening at different coordinates, so the filtered average is coordinate-wise rather than over whole vectors.Source: §III · p. 7
• BRIDGE-M uses coordinate-wise median screening and, unlike BRIDGE-T, requires neither explicit knowledge of b nor a minimum-neighbor constraint..Source: §III · p. 7
• BRIDGE-K retains one neighbor’s vector using Krum and requires neighborhoods larger than b + 2, while its pairwise-distance computations increase complexity relative to BRIDGE-T and BRIDGE-M.The screened vector is selected using its Euclidean distances to other neighborhood vectors.Source: §III · p. 7
• BRIDGE-B combines Krum selection with coordinate-wise trimmed-mean screening, at higher computational cost and with neighborhoods larger than max(4b, 3b + 2).BRIDGE-T and BRIDGE-B reduce to DGD when b = 0; the paper analyzes convergence guarantees only for BRIDGE-T.Source: §III · p. 7

IV. BRIDGE-T: CONVERGENCE GUARANTEES

• The analysis establishes algorithmic and statistical convergence guarantees for convex and nonconvex losses, with statistical rates assuming i.i.d. training data and bounded distance of regular-node iterates from the target.For nonconvex losses, the target is a first-order stationary point; for strongly convex losses, it is the unique global minimizer.Source: §IV · p. 8

A. Consensus guarantees

• Under Assumptions 1 and 4, BRIDGE-T’s iterates at all nonfaulty nodes approach a consensus vector for both convex and nonconvex losses.The consensus guarantee does not require Assumptions 2 and 3 or 3′.Source: A. Consensus guarantees · p. 9
• With step size ρ(t) = O(1/t), the consensus rate is O(dρ(t)), and the slowest-decaying term determines that rate.The analysis uses a nonincreasing step-size sequence whose squared values have finite sum.Source: §IV · p. 8, A. Consensus guarantees · p. 9

B. Statistical optimality guarantees

• Consensus alone cannot characterize the gap to the global minimizer for convex losses or a first-order stationary point for nonconvex losses; the analysis also bounds a1(t), a2(t), and a3(t).These distances track the consensus-based update’s optimization error, its sampling-related gap, and the gap between the consensus iterate and that update.Source: B. Statistical optimality guarantees · p. 9
• With i.i.d. training data and Assumptions 1 and 2, g2(t) converges in probability to the expected gradient at v(t), supporting a probabilistic bound on a2(t).Lemma 1 gives a probability bound for any fixed δ in (0, 1).Source: B. Statistical optimality guarantees · p. 10
• The nonconvex bound on a1(t) requires Assumption 3′, whereas the convex bound uses Assumption 3.The bounds for a2(t), a3(t), and a4(t) are obtained in the same manner for both settings.Source: B. Statistical optimality guarantees · p. 10

• A recursive bound controls the distance of v(t+1) from w* using terms that can be made arbitrarily small for sufficiently large t and N.The argument combines this bound with the closeness of nonfaulty-node iterates to v(t).Source: 1) Statistical optimality for the… · p. 10
• For any ϵ > C2(N), each nonfaulty node’s iterates eventually lie within ϵ of w* with probability at least 1−δ.This holds for sufficiently large t under the stated assumptions and i.i.d. training data.Source: 1) Statistical optimality for the… · p. 10
• With N→∞ and ρ(t)=O(1/t), bound (33) yields sublinear convergence in t.Source: 1) Statistical optimality for the… · p. 10
• BRIDGE-T’s statistical learning rate lies between centralized learning and DGD, reducing each node’s sample complexity versus local learning by ∥αm∥2 but not reaching the fault-free rate.The passage characterizes this as a trade-off between sample complexity and robustness.Source: 1) Statistical optimality for the… · p. 11

2) Statistical optimality for the nonconvex case:

• Lemma 4 characterizes a sufficient radius Γ for keeping all nonfaulty-node iterates within B(w*, Γ) ⊆ B(w*, β).The text says this helps justify the bounded-iterates assumption used in the analysis.Source: 2) Statistical optimality for the… · p. 11
• Under Assumptions 1, 2, 3′, and 4 and the stated initialization, BRIDGE-T converges sublinearly to stationary point w* at each nonfaulty node.The approach targets local convergence by using Assumption 3′, which specifies local strong convexity.Source: 2) Statistical optimality for the… · p. 11
• The convergence rates depend on dimension d; dimension-independent rates for Byzantine-resilient decentralized learning are left for future work.Source: 2) Statistical optimality for the… · p. 11

V. NUMERICAL RESULTS

• Experiments cover MNIST and CIFAR-10 with a linear classifier, those datasets with a convolutional neural network, and MNIST with non-i.i.d. agent data.The stated purpose is numerical validation across convex, nonconvex, and non-i.i.d. settings.Source: §V · p. 11

A. Linear classifier on MNIST and CIFAR-10

• On MNIST, BRIDGE-T/-M/-K match DGD in faultless learning (87.6%, 87.3%, 86.9% versus 87.8%), while all BRIDGE variants resist attacks that defeat DGD.In faulty settings, BRIDGE uses b = |B|.Source: Figure 2 · p. 12, A. Linear classifier on MNIST and… · p. 12, Figure 1 · p. 12
• BRIDGE-T and -M perform similarly under many Byzantine nodes, with -K close behind; only -M runs at b = 24 and p = 0.5 because it satisfies the neighborhood-size condition.BRIDGE-T cannot run at b ≥ 18 when p = 0.5, and -K cannot run at b = 24 and p = 0.5.Source: A. Linear classifier on MNIST and… · pp. 12–13, Figure 3 · p. 13
• BRIDGE-T and ByRDiE both tolerate two Byzantine nodes, but ByRDiE takes thousands-fold longer to reach the final solution.BRIDGE nodes compute local gradients and communicate with neighbors once per iteration.Source: Figure 4 · p. 13, A. Linear classifier on MNIST and… · p. 13
• On CIFAR-10, BRIDGE-T approaches ∼39% state-of-the-art accuracy for a linear classifier; BRIDGE-B is omitted because of its relatively high computational complexity on larger-dimensional data.Source: Figure 5 · p. 13, A. Linear classifier on MNIST and… · pp. 13–14

B. Convolutional neural network on MNIST and CIFAR-10

• Faultless MNIST CNN accuracy was 92% to 95%; on attacked CIFAR-10, BRIDGE-T and -M match centralized accuracy while -K stalls at a suboptimal critical point.On attacked MNIST, DGD fails with two or four Byzantine nodes, while all BRIDGE variants learn relatively good models.Source: Figure 6 · p. 14, B. Convolutional neural network on… · p. 14, Figure 7 · p. 14

VI. CONCLUSION

• BRIDGE is a Byzantine-resilient decentralized learning framework; BRIDGE-T has algorithmic and statistical convergence rates for certain convex and nonconvex loss classes.Future work targets greater Byzantine tolerance, faster convergence, broader nonconvex objectives, and additional non-i.i.d. settings.Source: §VI · p. 15

C. Non-i.i.d. data distribution on MNIST

• In extreme label-partitioned MNIST, four Byzantine agents caused about a 9-point accuracy drop, while moderate splits matched i.i.d. performance with two or four faulty agents.In the extreme worst case, 80% of one label's samples were withheld from training.Source: C. Non-i.i.d. data distribution on MNIST · pp. 14–15, Figure 9 · p. 15, Figure 10 · p. 15

A. Proof of Lemma 1

• The proof first fixes an arbitrary coordinate, then extends the resulting bound to the entire vector.It uses the fact that the coordinate k is arbitrary.Source: A. Proof of Lemma 1 · pp. 15–16
• Hoeffding’s inequality bounds the deviation for an arbitrary coordinate using the i.i.d. training data.The proof writes g2(t) as an inner product and notes that the elements of h(t) are identically distributed.Source: A. Proof of Lemma 1 · p. 16
• Covering sets Sα and V extends the bound uniformly over the vectors and simplex elements under consideration.The proof uses a ζ-covering of V and a ξ-covering of Sα, then invokes covering-number bounds.Source: A. Proof of Lemma 1 · p. 16

B. Proof of Lemma 2

• The argument is conditioned on a high-probability event and accumulates the update terms from v(0) through v(t + 1).The event has probability at least 1 − δ.Source: B. Proof of Lemma 2 · p. 17
• The first term in the bound is the initial distance C1 = ∥v(0) − w∗∥.Source: B. Proof of Lemma 2 · p. 17
• The remaining terms are simplified using the sum a4(0) + · · · + a4(t).The proof further simplifies this sum using (22).Source: B. Proof of Lemma 2 · pp. 17–18

C. Proof of Lemma 3

• For every j ∈ R, the proof obtains a bound by combining Theorem 1 with the result from Lemma 2.The argument is conditioned on the high-probability event described in Appendix A.Source: C. Proof of Lemma 3 · p. 18
• The proof bounds a4(t + 1) by choosing t to be even, then applies similar remaining steps.Source: C. Proof of Lemma 3 · p. 18
• For any ϵ > C2(N)/λ, some t1 makes ∥wj(t + 1) − w∗∥ ≤ ϵ for all t ≥ t1 with probability at least 1 − δ.The proof notes that the terms other than C2(N)/λ decrease monotonically with t.Source: C. Proof of Lemma 3 · p. 18

D. Proof of Theorem 2

• The slowest-decaying term in the distance bound is identified using the O(1/t) convergence rate of a4(t).The proof identifies this term as a sum involving 1/(t + t0).Source: D. Proof of Theorem 2 · p. 18
• A harmonic-series approximation is used to derive the convergence rate.Source: D. Proof of Theorem 2 · p. 18
• BRIDGE-T converges to the minimum of the global statistical risk at a sublinear rate.Source: D. Proof of Theorem 2 · p. 18

E. Proof of Lemma 4

• The nonconvex bound on each iterate’s distance to w* monotonically decreases with t.Consequently, the distances are bounded by the bound at t=1.Source: E. Proof of Lemma 4 · p. 18
• The initialization gives C1 = ∥v(0)−w*∥ ≤ β0.This is used to bound the initial distance in the nonconvex argument.Source: E. Proof of Lemma 4 · p. 18

F. Proof of Theorem 3

• Local strong convexity on B(w*, β), Γ-bounded iterates, and β ≥ Γ let the proof of Theorem 3 replicate the convex-case proof of Theorem 2.The argument also uses Assumption 3′ and Lemma 4.Source: F. Proof of Theorem 3 · pp. 18–19