Distributed Learning with Adversarial Gradient Perturbations

• URL: http://arxiv.org/abs/2605.03313v1
• Date: Tue, 05 May 2026 02:57:46 GMT
• Title: Distributed Learning with Adversarial Gradient Perturbations
• Abstract summary: We consider the problem of learning convex and $L$-smooth functions under adversarial gradient perturbations.<n>We establish tight feasibility thresholds on the sub-optimality gap and provide algorithms that achieve these thresholds with provable query complexity guarantees.
• Score: 0.7734726150561088
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Privacy concerns in distributed learning often lead clients to return intentionally altered gradient information. We consider the problem of learning convex and $L$-smooth functions under adversarial gradient perturbation, where a client's gradient reply to a server query can deviate arbitrarily from the true gradient subject to a distance bound. Our study focuses on two fundamental questions: (i) what is the smallest achievable sub-optimality gap (i.e., excess error in optimization) under such responses, and (ii) how many queries are sufficient to guarantee a given sub-optimality gap? We establish tight feasibility thresholds on the sub-optimality gap and provide algorithms that achieve these thresholds with provable query complexity guarantees.

Related papers

• Online Learning with Gradient-Variation Interval Regret [54.59204826681113]
  We propose the first online learning algorithm that achieves an interval regret bound scaling with gradient variation.<n>Our method employs a simple and efficient two-layer online ensemble structure that achieves strong theoretical guarantees.
  arXiv  Detail & Related papers  (2026-06-02T16:16:45Z)
• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  gradient-variation online learning aims to achieve regret guarantees that scale with variations in gradients of online functions. Recent efforts in neural network optimization suggest a generalized smoothness condition, allowing smoothness to correlate with gradient norms. We provide the applications for fast-rate convergence in games and extended adversarial optimization.
  arXiv  Detail & Related papers  (2024-08-17T02:22:08Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Provably Personalized and Robust Federated Learning [47.50663360022456]
  We propose simple algorithms which identify clusters of similar clients and train a personalized modelper-cluster. The convergence rates of our algorithmsally match those obtained if we knew the true underlying clustering of the clients and are provably robust in the Byzantine setting.
  arXiv  Detail & Related papers  (2023-06-14T09:37:39Z)
• Analyzing Inexact Hypergradients for Bilevel Learning [0.09669369645900441]
  We introduce a unified framework for computing hypergradients that generalizes existing methods based on the implicit function theorem and automatic differentiation/backpropagation. Our numerical results show that, surprisingly, for efficient bilevel optimization, the choice of hypergradient algorithm is at least as important as the choice of lower-level solver.
  arXiv  Detail & Related papers  (2023-01-11T23:54:27Z)
• Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity [34.84170466506512]
  We propose a new zeroth-order hard-thresholding (SZOHT) algorithm with a general ZO gradient estimator powered by a novel random sampling. We find that the query complexity of SZOHT is independent or weakly dependent on the dimensionality under different settings.
  arXiv  Detail & Related papers  (2022-10-11T09:23:53Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Robust learning with anytime-guaranteed feedback [6.903929927172917]
  gradient-based learning algorithms are driven by queried feedback with almost no performance guarantees. Here we explore a modified "anytime online-to-batch" mechanism which admits high-probability error bounds. In practice, we show noteworthy gains on real-world data applications.
  arXiv  Detail & Related papers  (2021-05-24T07:31:52Z)
• Learner-Private Online Convex Optimization [24.204781914017758]
  We study how to optimally obfuscate the learner's queries in first-order online convex optimization. Our results apply to the significantly richer family of general convex functions with full-gradient feedback.
  arXiv  Detail & Related papers  (2021-02-23T23:00:44Z)
• Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
  Neural networks can learn complex, non- adversarial functions, and it is challenging to guarantee their correct behavior in safety-critical contexts. Many approaches exist to find failures in networks (e.g., adversarial examples), but these cannot guarantee the absence of failures. We propose an approach that integrates the optimization process into the verification procedure, achieving better performance than the naive approach.
  arXiv  Detail & Related papers  (2020-10-07T08:19:48Z)

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.