Generalization under Byzantine & Poisoning Attacks: Tight Stability Bounds in Robust Distributed Learning

• URL: http://arxiv.org/abs/2506.18020v1
• Date: Sun, 22 Jun 2025 12:59:15 GMT
• Title: Generalization under Byzantine & Poisoning Attacks: Tight Stability Bounds in Robust Distributed Learning
• Abstract summary: Two primary threat models have been studied: Byzantine attacks and data poisoning attacks.<n>We show that Byzantine attacks are intrinsically more harmful to generalization than data poisoning.
• Score: 11.915183759106412
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Robust distributed learning algorithms aim to maintain good performance in distributed and federated settings, even in the presence of misbehaving workers. Two primary threat models have been studied: Byzantine attacks, where misbehaving workers can send arbitrarily corrupted updates, and data poisoning attacks, where misbehavior is limited to manipulation of local training data. While prior work has shown comparable optimization error under both threat models, a fundamental question remains open: How do these threat models impact generalization? Empirical evidence suggests a gap between the two threat models, yet it remains unclear whether it is fundamental or merely an artifact of suboptimal attacks. In this work, we present the first theoretical investigation into this problem, formally showing that Byzantine attacks are intrinsically more harmful to generalization than data poisoning. Specifically, we prove that: (i) under data poisoning, the uniform algorithmic stability of a robust distributed learning algorithm, with optimal optimization error, degrades by an additive factor of $\varTheta ( \frac{f}{n-f} )$, with $f$ the number of misbehaving workers out of $n$; and (ii) In contrast, under Byzantine attacks, the degradation is in $\mathcal{O} \big( \sqrt{ \frac{f}{n-2f}} \big)$.This difference in stability leads to a generalization error gap that is especially significant as $f$ approaches its maximum value $\frac{n}{2}$.

Related papers

• High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking [69.90407799170687]
  We study high-probability (HP) convergence guarantees in decentralized optimization.<n>Our results establish the same conditions on the horizon as in achieving comparable times.
  arXiv  Detail & Related papers  (2026-04-30T22:45:21Z)
• High-Dimensional Robust Mean Estimation with Untrusted Batches [38.14592862692954]
  We study high-dimensional mean estimation in a collaborative setting where data is contributed by $N$ users in batches of size $n$.<n>We formalize this challenge through a double corruption landscape: an $varepsilon$-fraction of users are entirely adversarial, while the remaining good'' users provide data from distributions that are related to $P$, but deviate by a proximity parameter $$.<n>Our algorithms achieve the minimax-optimal error rate $O(sqrtvarepsilon/n + sqrtd/nN + s
  arXiv  Detail & Related papers  (2026-02-24T08:59:37Z)
• Trade-off in Estimating the Number of Byzantine Clients in Federated Learning [51.015234193544636]
  Federated learning is vulnerable to Byzantine clients that can send any erroneous signals.<n>We show that underestimation ($hatfge f$) can lead to arbitrarily poor performance for both aggregators and federated learning.<n>All these optimal bounds are proportional to $hatf/(n-f-hatf)$ with $n$ clients, which monotonically increases with larger $hatf$.
  arXiv  Detail & Related papers  (2025-10-06T02:01:56Z)
• Distributionally Robust Optimization with Adversarial Data Contamination [49.89480853499918]
  We focus on optimizing Wasserstein-1 DRO objectives for generalized linear models with convex Lipschitz loss functions.<n>Our primary contribution lies in a novel modeling framework that integrates robustness against training data contamination with robustness against distributional shifts.<n>This work establishes the first rigorous guarantees, supported by efficient computation, for learning under the dual challenges of data contamination and distributional shifts.
  arXiv  Detail & Related papers  (2025-07-14T18:34:10Z)
• Towards Model Resistant to Transferable Adversarial Examples via Trigger Activation [95.3977252782181]
  Adversarial examples, characterized by imperceptible perturbations, pose significant threats to deep neural networks by misleading their predictions.<n>We introduce a novel training paradigm aimed at enhancing robustness against transferable adversarial examples (TAEs) in a more efficient and effective way.
  arXiv  Detail & Related papers  (2025-04-20T09:07:10Z)
• Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients [27.433334322019675]
  Federated Learning (FL) enables clients to collaboratively train models without sharing raw data.<n>FL is vulnerable to Byzantine attacks and data heterogeneity iterations, which can severely degrade performance.<n>We propose effective Federated Normalized Gradients Algorithm (NGA)<n> Experimental results on benchmark convergence over existing methods.
  arXiv  Detail & Related papers  (2024-08-18T16:50:39Z)
• $k$-Submodular Interdiction Problems under Distributional Risk-Receptiveness and Robustness: Application to Machine Learning [0.8233493213841317]
  We study submodular optimization in adversarial context, applicable to machine learning problems such as feature selection.<n>We focus on Stackelberg games between an attacker (or interdictor) and a defender where the attacker aims to minimize the defender's objective of maximizing a $k$-submodular function.<n>We introduce Distributionally Robust $k$-SIP and Distributionally Risk-Receptive $k$-SIP along with finitely convergent exact algorithms for solving them.
  arXiv  Detail & Related papers  (2024-06-18T19:30:46Z)
• Advancing Generalized Transfer Attack with Initialization Derived Bilevel Optimization and Dynamic Sequence Truncation [49.480978190805125]
  Transfer attacks generate significant interest for black-box applications. Existing works essentially directly optimize the single-level objective w.r.t. surrogate model. We propose a bilevel optimization paradigm, which explicitly reforms the nested relationship between the Upper-Level (UL) pseudo-victim attacker and the Lower-Level (LL) surrogate attacker.
  arXiv  Detail & Related papers  (2024-06-04T07:45:27Z)
• Federated Learning Resilient to Byzantine Attacks and Data Heterogeneity [59.17297282373628]
  This paper addresses Gradient learning (FL) in the context of malicious attacks on data.<n>We introduce a novel Average Robust Algorithm (RAGA) which uses the median for both convergence analysis and loss functions.
  arXiv  Detail & Related papers  (2024-03-20T08:15:08Z)
• Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
  We investigate the problem of corruption in offline reinforcement learning (RL) with general function approximation. Our goal is to find a policy that is robust to such corruption and minimizes the suboptimality gap with respect to the optimal policy for the uncorrupted Markov decision processes (MDPs)
  arXiv  Detail & Related papers  (2023-10-23T04:07:26Z)
• An Improved Analysis of Gradient Tracking for Decentralized Machine Learning [34.144764431505486]
  We consider decentralized machine learning over a network where the training data is distributed across $n$ agents. The agent's common goal is to find a model that minimizes the average of all local loss functions. We improve the dependency on $p$ from $mathcalO(p-1)$ to $mathcalO(p-1)$ in the noiseless case.
  arXiv  Detail & Related papers  (2022-02-08T12:58:14Z)
• Towards Variable-Length Textual Adversarial Attacks [68.27995111870712]
  It is non-trivial to conduct textual adversarial attacks on natural language processing tasks due to the discreteness of data. In this paper, we propose variable-length textual adversarial attacks(VL-Attack) Our method can achieve $33.18$ BLEU score on IWSLT14 German-English translation, achieving an improvement of $1.47$ over the baseline model.
  arXiv  Detail & Related papers  (2021-04-16T14:37:27Z)
• Online Adversarial Attacks [57.448101834579624]
  We formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases. We first rigorously analyze a deterministic variant of the online threat model. We then propose algoname, a simple yet practical algorithm yielding a provably better competitive ratio for $k=2$ over the current best single threshold algorithm.
  arXiv  Detail & Related papers  (2021-03-02T20:36:04Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing [55.012801269326594]
  In Byzantine robust distributed learning, a central server wants to train a machine learning model over data distributed across multiple workers. A fraction of these workers may deviate from the prescribed algorithm and send arbitrary messages. We propose a simple bucketing scheme that adapts existing robust algorithms to heterogeneous datasets at a negligible computational cost.
  arXiv  Detail & Related papers  (2020-06-16T17:58:53Z)
• Estimating Principal Components under Adversarial Perturbations [25.778123431786653]
  We study a natural model of robustness for high-dimensional statistical estimation problems. Our model is motivated by emerging paradigms such as low precision machine learning and adversarial training.
  arXiv  Detail & Related papers  (2020-05-31T20:27:19Z)
• Toward Adversarial Robustness via Semi-supervised Robust Training [93.36310070269643]
  Adrial examples have been shown to be the severe threat to deep neural networks (DNNs) We propose a novel defense method, the robust training (RT), by jointly minimizing two separated risks ($R_stand$ and $R_rob$)
  arXiv  Detail & Related papers  (2020-03-16T02:14:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.