Byzantine-Robust Gossip: Insights from a Dual Approach

• URL: http://arxiv.org/abs/2405.03449v2
• Date: Wed, 02 Jul 2025 18:12:55 GMT
• Title: Byzantine-Robust Gossip: Insights from a Dual Approach
• Authors: Renaud Gaucher, Aymeric Dieuleveut, Hadrien Hendrikx,
• Abstract summary: Distributed learning has many computational benefits but is vulnerable to attacks from a subset of devices transmitting incorrect information.<n>This paper investigates Byzantine-resilient algorithms in a decentralized setting, where devices communicate directly in a peer-to-peer manner within a communication network.
• Score: 15.69624587054777
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Distributed learning has many computational benefits but is vulnerable to attacks from a subset of devices transmitting incorrect information. This paper investigates Byzantine-resilient algorithms in a decentralized setting, where devices communicate directly in a peer-to-peer manner within a communication network. We leverage the so-called dual approach for decentralized optimization and propose a Byzantine-robust algorithm. We provide convergence guarantees in the average consensus subcase, discuss the potential of the dual approach beyond this subcase, and re-interpret existing algorithms using the dual framework. Lastly, we experimentally show the soundness of our method.

Related papers

• Trial and Trust: Addressing Byzantine Attacks with Comprehensive Defense Strategy [37.73859687331454]
  In this paper, we address a specific threat, Byzantine attacks, where compromised clients inject adversarial updates to derail global convergence.<n>We combine the trust scores concept with trial function methodology to dynamically filter outliers.<n>Our methods address the critical limitations of previous approaches, allowing functionality even when Byzantine nodes are in the majority.
  arXiv  Detail & Related papers  (2025-05-12T14:36:45Z)
• Multi-Agent Best Arm Identification in Stochastic Linear Bandits [0.7673339435080443]
  We study the problem of collaborative best-arm identification in linear bandits under a fixed-budget scenario.<n>We propose two algorithms, MaLinBAI-Star and MaLinBAI-Gen for star networks and networks with arbitrary structure.
  arXiv  Detail & Related papers  (2024-11-20T20:09:44Z)
• Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints [0.0]
  We present conservative distributed multi-task learning in linear contextual bandits with heterogeneous agents.<n>The exact context is unknown, and only a context distribution is available to the agents.<n>Our algorithm constructs a pruned action set during each round to ensure the constraints are met.<n>It includes synchronized sharing of estimates among agents via a central server.
  arXiv  Detail & Related papers  (2024-01-21T18:43:55Z)
• WiCo: Win-win Cooperation of Bottom-up and Top-down Referring Image Segmentation [37.53063869243558]
  We build Win-win Cooperation (WiCo) to exploit complementary nature of two types of methods on both interaction and integration aspects. With our WiCo, several prominent top-down and bottom-up combinations achieve remarkable improvements on three common datasets with reasonable extra costs.
  arXiv  Detail & Related papers  (2023-06-19T07:49:29Z)
• Networked Communication for Decentralised Agents in Mean-Field Games [59.01527054553122]
  We introduce networked communication to the mean-field game framework.<n>We prove that our architecture has sample guarantees bounded between those of the centralised- and independent-learning cases.<n>We show that our networked approach has significant advantages over both alternatives in terms of robustness to update failures and to changes in population size.
  arXiv  Detail & Related papers  (2023-06-05T10:45:39Z)
• Divide and Contrast: Source-free Domain Adaptation via Adaptive Contrastive Learning [122.62311703151215]
  Divide and Contrast (DaC) aims to connect the good ends of both worlds while bypassing their limitations. DaC divides the target data into source-like and target-specific samples, where either group of samples is treated with tailored goals. We further align the source-like domain with the target-specific samples using a memory bank-based Maximum Mean Discrepancy (MMD) loss to reduce the distribution mismatch.
  arXiv  Detail & Related papers  (2022-11-12T09:21:49Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  We consider a distributed reinforcement learning setting where multiple agents explore the environment and communicate their experiences through a central server. $alpha$-fraction of agents are adversarial and can report arbitrary fake information. We seek to identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents.
  arXiv  Detail & Related papers  (2022-06-01T00:44:53Z)
• Semi-supervised Domain Adaptive Structure Learning [72.01544419893628]
  Semi-supervised domain adaptation (SSDA) is a challenging problem requiring methods to overcome both 1) overfitting towards poorly annotated data and 2) distribution shift across domains. We introduce an adaptive structure learning method to regularize the cooperation of SSL and DA.
  arXiv  Detail & Related papers  (2021-12-12T06:11:16Z)
• Coarse to Fine: Domain Adaptive Crowd Counting via Adversarial Scoring Network [58.05473757538834]
  This paper proposes a novel adversarial scoring network (ASNet) to bridge the gap across domains from coarse to fine granularity. Three sets of migration experiments show that the proposed methods achieve state-of-the-art counting performance.
  arXiv  Detail & Related papers  (2021-07-27T14:47:24Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Federated Learning with Randomized Douglas-Rachford Splitting Methods [30.998685972581754]
  We develop two new algorithms called, textbfFedDR and textbfDRaa. Our analysis shows that the new algorithms match the communication efficiency up to lower under lower assumptions.
  arXiv  Detail & Related papers  (2021-03-05T03:24:04Z)
• Learning from History for Byzantine Robust Optimization [52.68913869776858]
  Byzantine robustness has received significant attention recently given its importance for distributed learning. We show that most existing robust aggregation rules may not converge even in the absence of any Byzantine attackers.
  arXiv  Detail & Related papers  (2020-12-18T16:22:32Z)
• Decentralized Deep Learning using Momentum-Accelerated Consensus [15.333413663982874]
  We consider the problem of decentralized deep learning where multiple agents collaborate to learn from a distributed dataset. We propose and analyze a novel decentralized deep learning algorithm where the agents interact over a fixed communication topology. Our algorithm is based on the heavy-ball acceleration method used in gradient-based protocol.
  arXiv  Detail & Related papers  (2020-10-21T17:39:52Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)
• Domain Adaptation by Class Centroid Matching and Local Manifold Self-Learning [8.316259570013813]
  We propose a novel domain adaptation approach, which can thoroughly explore the data distribution structure of target domain. We regard the samples within the same cluster in target domain as a whole rather than individuals and assigns pseudo-labels to the target cluster by class centroid matching. An efficient iterative optimization algorithm is designed to solve the objective function of our proposal with theoretical convergence guarantee.
  arXiv  Detail & Related papers  (2020-03-20T16:59:27Z)
• Contradictory Structure Learning for Semi-supervised Domain Adaptation [67.89665267469053]
  Current adversarial adaptation methods attempt to align the cross-domain features. Two challenges remain unsolved: 1) the conditional distribution mismatch and 2) the bias of the decision boundary towards the source domain. We propose a novel framework for semi-supervised domain adaptation by unifying the learning of opposite structures.
  arXiv  Detail & Related papers  (2020-02-06T22:58:20Z)

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.