Source-linked AI summary
RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets
Liping Li, Wei Xu, Tianyi Chen, Georgios B. Giannakis, Qing Ling
TL;DR
Distributed learning must handle Byzantine workers that can send arbitrary messages, while existing robust methods often assume i.i.d. worker data. The paper proposes RSA, which uses regularization-based stochastic subgradient methods for heterogeneous datasets and reports near-optimal convergence with error dependent on Byzantine workers, alongside competitive empirical performance and reduced complexity.
Problem
Byzantine workers can arbitrarily modify messages in distributed learning, while many existing robust methods assume i.i.d. worker data and costly aggregation procedures.
Method
RSA introduces robust stochastic subgradient methods with ℓp-norm regularization for distributed learning over heterogeneous datasets under Byzantine attacks.
Results
RSA converges to a near-optimal solution at an O(1/k) rate with an optimality gap dependent on the number of Byzantine workers, while experiments show competitive performance and lower runtime complexity than alternatives.
Takeaways & Limitations
RSA provides a Byzantine-robust distributed-learning approach that does not rely on i.i.d. worker data and can reduce the impact of malicious-message magnitudes on updates.
Takeaways & Limitations
Existing robust aggregation methods face difficulty distinguishing statistical heterogeneity from Byzantine attacks, and RSA performance depends on the choice of λ and ℓp norm.
Abstract
from arXiv · showhide
In this paper, we propose a class of robust stochastic subgradient methods for distributed learning from heterogeneous datasets at presence of an unknown number of Byzantine workers. The Byzantine workers, during the learning process, may send arbitrary incorrect messages to the master due to data corruptions, communication failures or malicious attacks, and consequently bias the learned model. The key to the proposed methods is a regularization term incorporated with the objective function so as to robustify the learning task and mitigate the negative effects of Byzantine attacks. The resultant subgradient-based algorithms are termed Byzantine-Robust Stochastic Aggregation methods, justifying our acronym RSA used henceforth. In contrast to most of the existing algorithms, RSA does not rely on the assumption that the data are independent and identically distributed (i.i.d.) on the workers, and hence fits for a wider class of applications. Theoretically, we show that: i) RSA converges to a near-optimal solution with the learning error dependent on the number of Byzantine workers; ii) the convergence rate of RSA under Byzantine attacks is the same as that of the stochastic gradient descent method, which is free of Byzantine attacks. Numerically, experiments on real dataset corroborate the competitive performance of RSA and a complexity reduction compared to the state-of-the-art alternatives.
Introduction
Federated learning distributes data and computation across workers but remains vulnerable to Byzantine failures, especially when worker datasets are heterogeneous. The paper introduces RSA as a robust stochastic approach with theoretical guarantees and empirical evaluation.
- Motivation: Federated learning distributes data and computation across workers to reduce privacy risks from centralized training.Workers such as IoT devices collaboratively learn a model using distributed implementations of algorithms including SGD.
- Problem: Byzantine workers can arbitrarily alter messages, making distributed learning vulnerable to failures and adversarial attacks.The paper notes that SGD can be compromised by even one Byzantine worker.
- Related work: Existing robust aggregation methods commonly assume i.i.d. worker data and may require computationally costly procedures.These assumptions and procedures are difficult to extend to heterogeneous federated-learning settings.
- Contributions: RSA develops robust stochastic methods for heterogeneous datasets under Byzantine attacks, with variants based on ℓp-norm regularized objectives.The paper establishes convergence and Byzantine-error performance theoretically and evaluates classification accuracy and runtime on MNIST.
- Distributed SGD: Distributed SGD broadcasts the current iterate, collects worker gradients, and updates the model, but Byzantine messages can make the aggregate infinite or null.Regular workers compute local stochastic gradients from worker-specific distributions, while Byzantine workers send wrong messages.
- RSA motivation: The paper develops a counterpart of SGD for robust learning from distributed heterogeneous data because statistical heterogeneity complicates distinguishing benign variation from Byzantine attacks.The approach targets the stated difficulty of applying conventional robust gradient aggregation in federated learning.
RSA for Robust Distributed Learning
The paper reformulates the learning objective around regular workers because Byzantine workers can prevent access to their local data. It then represents the problem using regular-worker and master variables in a consensus-style formulation.
- Robust objective: The robust objective minimizes regular workers’ expected costs plus a regularization term instead of including Byzantine workers’ inaccessible objectives.The paper states that solving the original all-worker objective is meaningless when Byzantine workers can arbitrarily prevent access to their data.
- Consensus formulation: The equivalent formulation stacks each regular worker’s local variable with the master’s variable.The resulting formulation is aligned with consensus optimization.
ℓ1-norm RSA
ℓ1-norm RSA replaces direct optimization requiring Byzantine identities with a regularized model-aggregation procedure. Its penalty encourages local-master proximity while making Byzantine-message magnitudes less influential on the master update.
- Regularization: Directly solving the regular-worker formulation is impossible because the master does not know which workers are Byzantine.RSA therefore introduces an ℓ1-norm regularized form.
- Regularization: The ℓ1 penalty forces each regular worker’s local variable close to the master variable, with λ controlling the bias.The penalty relaxes exact equality while robustifying the objective against arbitrary Byzantine behavior.
- Algorithm: Regular workers send local iterates rather than stochastic gradients, and the master aggregates models to update its own iterate.This changes the procedure from gradient aggregation in SGD to model aggregation.
- Algorithm: Byzantine workers may replace their local iterates with arbitrary values before transmission to the master.The master update consequently uses regular-worker iterates together with potentially faulty values.
- Robustness: Only the number of Byzantine workers, rather than the magnitudes of their malicious messages, influences the ℓ1-norm RSA update.The paper contrasts this robustness with SGD’s vulnerability to a single Byzantine worker.
Generalization to ℓp-norm RSA
The paper extends RSA from ℓ1 regularization to ℓp-norm regularized objectives, retaining subgradient updates to mitigate Byzantine influence in heterogeneous distributed learning.
- Generalization to ℓp-norm RSA: RSA also solves an ℓp-norm regularized problem for p ≥ 1.The ℓp penalty is stated to mitigate the negative influence of Byzantine workers.
- Generalization to ℓp-norm RSA: The ℓp-norm RSA algorithm uses subgradient recursions for both regular workers and the master.The paper introduces local and master updates and gives a proposition for computing the required subgradients.
- Generalization to ℓp-norm RSA: For p ≥ 1, the subdifferential of the ℓp norm is characterized using a dual norm ℓb satisfying 1/p + 1/b = 1.The characterization specifies vectors whose inner product with x equals ∥x∥p and whose dual-norm magnitude is at most one.
- Generalization to ℓp-norm RSA: RSA is summarized in Algorithm 2 and illustrated as communication between the master, regular workers, and Byzantine workers.The figure distinguishes regular-worker responses from arbitrary wrong messages sent by Byzantine workers.
- Generalization to ℓp-norm RSA: Unlike gradient-aggregation methods relying on i.i.d. worker data, RSA targets distributed learning over heterogeneous datasets.The cited related-work passage identifies the i.i.d. requirement as impractical in federated learning.
Convergence Analysis
The convergence analysis establishes RSA guarantees under strong convexity, Lipschitz gradients, and bounded-variance sampling assumptions. With suitable regularization and step sizes, RSA converges sublinearly to near-optimal solutions, with asymptotic error depending on Byzantine workers.
- Convergence Analysis: The analysis assumes strongly convex local costs and regularization, Lipschitz continuous gradients, and bounded stochastic-gradient variance.The sampling assumption requires i.i.d. data across time at each worker; these conditions are described as standard for stochastic gradient methods.
- Convergence Analysis: A sufficiently large penalty λ makes the regularized problem’s optimizer identical to the original problem’s optimizer.The condition is λ ≥ λ0, where λ0 is defined using regular-worker gradient norms in the dual norm.
- Convergence Analysis: RSA iterates converge sublinearly to a near-optimal solution of the regularized problem under the stated assumptions and step-size choice.The bound has a decaying term and an asymptotic term whose constant satisfies Δ2 = O(λ^2q^2).
- Convergence Analysis: With appropriately selected λ, the limiting sub-optimality gap for the original problem is proportional to the number of Byzantine workers.For smaller λ, the analysis additionally uses a bound on the distance between the regularized and original optimizers.
- Convergence Analysis: Selecting λ and p creates a trade-off between consensus among local solutions and the sub-optimality gap.The paper reports that ℓ1 and ℓ2 norms perform well numerically, whereas ℓ∞ does not provide competitive performance.
Numerical Tests
Experiments on MNIST evaluate RSA against benchmark aggregation methods under both i.i.d. and heterogeneous data, without attacks and under several Byzantine attack types. RSA remains competitive in accuracy, especially as attacks intensify or data become heterogeneous, while incurring relatively low computational overhead.
- Experimental setup: MNIST experiments use 20 workers, one master, softmax regression, mini-batches of 32, and test top-1 accuracy as the performance metric.The evaluation includes randomly distributed i.i.d. data and a heterogeneous setting where every two workers share one digit’s samples.
- Without Byzantine attacks: Without Byzantine attacks, RSA and GeoMed remain close to Ideal SGD and significantly outperform Krum and Median.The result indicates that RSA’s regularization bias does not sacrifice performance in the regular case.
- Same-value attacks: Under same-value attacks, RSA and GeoMed stay close to Ideal SGD as q increases from 4 to 8, while Krum and Median worsen.The attacks use c = 100; the experiments also note that SGD works in this setting because of softmax regression’s special structure.
- Sign-flipping attacks: Under sign-flipping attacks with σ = −4, SGD fails for q = 4 and q = 8, while GeoMed, Median, and ℓ1-norm RSA show similar performance.Median is slightly worse than the other Byzantine-robust algorithms.
- Gaussian attacks: Under Gaussian attacks with g = 10000, SGD fails for q = 4 and q = 8, while RSA and GeoMed outperform Median and Krum.RSA and GeoMed obtain similar results in both Byzantine-worker settings.
- Runtime comparison: With q = 8 and c = 100, GeoMed has the largest runtime, whereas ℓ1-norm RSA and Median are slightly slower than Ideal SGD but faster than Krum.RSA’s only stated overhead relative to Ideal SGD is lightweight sign-function computation.
- Hyper-parameter λ: For varying λ under q = 8 same-value attacks, small λ slows information fusion, whereas large λ incurs remarkable error.The experiment runs RSA for 5000 iterations with hand-tuned step sizes.
- RSA with different norms: Across i.i.d. and same-value attack settings, ℓ1-norm and ℓ2-norm RSA are close in top-1 accuracy and outperform ℓ∞-norm RSA.ℓ∞-norm RSA has the largest variance of regular workers’ local iterates because choosing a smaller λ sacrifices consensus.
Conclusions
RSA is presented as an efficient approach to Byzantine-robust distributed learning over heterogeneous datasets, with convergence guarantees and competitive empirical performance.
- RSA converges at O(1/k) to a near-optimal solution, with the optimality gap depending on the number of Byzantine workers.
- In Byzantine-free settings, both SGD and RSA converge to the optimal solution at a sublinear rate.
- Real-data experiments corroborate RSA’s competitive performance against state-of-the-art alternatives.
- Under attacks on heterogeneous data, top-1 accuracy is evaluated for q = 4 and q = 8.
Distributed Learning from Heterogeneous Datasets”
The supplementary document provides omitted proofs from the main manuscript.
- The supplement presents proofs omitted from the main manuscript.
- Its role is to supply additional theoretical derivations supporting the manuscript’s results.
- The document supplements, rather than replaces, the main manuscript.
Proof of Proposition 1
The proof of Proposition 1 establishes the subdifferential characterization of the p-norm using dual-norm inequalities and subdifferential conditions.
- The proof establishes that {z ∈ R^d : ⟨z, x⟩ = ∥x∥p, ∥z∥b ≤ 1} is contained in ∂x∥x∥p.
- It uses Hölder’s inequality to bound ⟨z, y⟩ and verify the subdifferential condition.
- Conversely, any z ∈ ∂x∥x∥p satisfies ⟨z, x⟩ = ∥x∥p and ∥z∥b ≤ 1.
Proof of Theorem 1
The proof of Theorem 1 derives the required optimality conditions using the bound on regular-worker gradients and subdifferential properties of the norm regularizer.
- Because λ ≥ λ0, each regular-worker expected gradient belongs to {λz : ∥z∥b ≤ 1}.
- The proof sums the relevant conditions over regular workers and invokes the optimality condition of (3).
- Since each νi belongs to ∂∥0∥p, the resulting point satisfies the optimality condition of (9) and is unique under Assumption 1.
Proof of Theorem 2
The proof establishes a one-step expected-error recursion for RSA and derives its convergence bound under the theorem’s step-size rule. The argument combines worker and master updates, strong convexity, Lipschitz gradients, bounded variance, and induction.
- Technical estimates: The proof bounds worker-level terms using optimality conditions, strong convexity, Lipschitz continuity, bounded variance, and the RSA update equations.These estimates are assembled before summing over regular workers and incorporating the master bound.
- One-step bound: The worker and master update analyses are combined into a one-step recursion for E∥xk+1 − x∗∥2.The recursion contains a contraction term and error terms involving αk+1, λ, and problem-dependent constants.
- Induction: For sufficiently early iterations, the capped step size α yields geometric contraction up to an additive error term.The proof obtains E∥xk+1 − x∗∥2 ≤ (1 − ηα)E∥xk − x∗∥2 + α^2∆0 + α∆2.
- Induction: After the step size enters its decaying regime, induction proves E∥xk+1 − x∗∥2 ≤ ∆1/(k+1) + α∆2.This is the stated bound for all k ≥ k0.
Proof of Theorem 3
The proof of Theorem 3 separates the cases λ ≥ λ0 and 0 < λ < λ0. In the latter case, it combines Theorem 2 with a bound on the distance between the relevant solutions to obtain the result.
- Case analysis: For λ ≥ λ0, Theorem 3 follows directly by combining Theorems 1 and 2.
- Case analysis: For 0 < λ < λ0, the proof uses (a + b)^2 ≤ 2a^2 + 2b^2 and Theorem 2 to establish the claimed bound.It also invokes E[∥x∗ − [˜x∗]∥2] ≤ ∆3.