Impact of Redundancy on Resilience in Distributed Optimization and Learning

• URL: http://arxiv.org/abs/2211.08622v2
• Date: Thu, 14 Dec 2023 08:06:53 GMT
• Title: Impact of Redundancy on Resilience in Distributed Optimization and Learning
• Authors: Shuo Liu, Nirupam Gupta, Nitin H. Vaidya
• Abstract summary: This report considers the problem of resilient distributed optimization and learning in a server-based architecture. The system comprises a server and multiple agents, where each agent has its own local cost function. We show that $(f, r; epsilon)$-resilience can indeed be achieved in practice, given that the local cost functions are sufficiently redundant.
• Score: 4.664766612388049
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This report considers the problem of resilient distributed optimization and stochastic learning in a server-based architecture. The system comprises a server and multiple agents, where each agent has its own local cost function. The agents collaborate with the server to find a minimum of the aggregate of the local cost functions. In the context of stochastic learning, the local cost of an agent is the loss function computed over the data at that agent. In this report, we consider this problem in a system wherein some of the agents may be Byzantine faulty and some of the agents may be slow (also called stragglers). In this setting, we investigate the conditions under which it is possible to obtain an "approximate" solution to the above problem. In particular, we introduce the notion of $(f, r; \epsilon)$-resilience to characterize how well the true solution is approximated in the presence of up to $f$ Byzantine faulty agents, and up to $r$ slow agents (or stragglers) -- smaller $\epsilon$ represents a better approximation. We also introduce a measure named $(f, r; \epsilon)$-redundancy to characterize the redundancy in the cost functions of the agents. Greater redundancy allows for a better approximation when solving the problem of aggregate cost minimization. In this report, we constructively show (both theoretically and empirically) that $(f, r; \mathcal{O}(\epsilon))$-resilience can indeed be achieved in practice, given that the local cost functions are sufficiently redundant.

Related papers

• Communication Efficient Decentralization for Smoothed Online Convex Optimization [9.449153668916098]
  We study the multi-agent Smoothed Online Convex Optimization (SOCO) problem, where $N$ agents interact through a communication graph. In each round, each agent $i$ receives a strongly convex hitting cost function $fi_t$ in an online fashion. Our results hold even when the communication graph changes arbitrarily and adaptively over time.
  arXiv  Detail & Related papers  (2024-11-13T05:59:04Z)
• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  A network of $N$ agents communicate locally to minimize their collective regret while keeping their expected cost under a specified threshold $tau$. We propose a safe distributed upper confidence bound algorithm, so called textitMA-OPLB, and establish a high probability bound on its $T$-round regret. We show that our regret bound is of order $ mathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)
  arXiv  Detail & Related papers  (2024-10-22T19:34:53Z)
• On the Resilience of Multi-Agent Systems with Malicious Agents [58.79302663733702]
  This paper investigates what is the resilience of multi-agent system structures under malicious agents. We devise two methods, AutoTransform and AutoInject, to transform any agent into a malicious one. We show that two defense methods, introducing a mechanism for each agent to challenge others' outputs, or an additional agent to review and correct messages, can enhance system resilience.
  arXiv  Detail & Related papers  (2024-08-02T03:25:20Z)
• Data Sharing for Mean Estimation Among Heterogeneous Strategic Agents [11.371461065112422]
  We study a collaborative learning problem where $m$ agents estimate a vector $muinmathbbRd$ by collecting samples from normal distributions. Instead of working on their own, agents can collect data that is cheap to them, and share it with others in exchange for data that is expensive or even inaccessible to them.
  arXiv  Detail & Related papers  (2024-07-20T17:45:40Z)
• Self-Localized Collaborative Perception [49.86110931859302]
  We propose$mathttCoBEVGlue$, a novel self-localized collaborative perception system. $mathttCoBEVGlue$ is a novel spatial alignment module, which provides the relative poses between agents. $mathttCoBEVGlue$ achieves state-of-the-art detection performance under arbitrary localization noises and attacks.
  arXiv  Detail & Related papers  (2024-06-18T15:26:54Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  Markov Games (MG) is an important model for Multi-Agent Reinforcement Learning (MARL) This paper first refines the AVLPR framework by Wang et al. (2023), with an insight of designing pessimistic estimation of the sub-optimality gap. We give the first algorithm that tackles the curse of multi-agents, attains the optimal $O(T-1/2) convergence rate, and avoids $textpoly(A_max)$ dependency simultaneously.
  arXiv  Detail & Related papers  (2024-02-11T01:51:15Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost [48.288452411283444]
  We study distributed contextual linear bandits with contexts, where $N$ agents act cooperatively to solve a linear bandit-optimization problem with $d$-dimensional features. We propose a distributed batch elimination version of the LinUCB algorithm, DisBE-LUCB, where the agents share information among each other through a central server. We prove that over $T$ rounds ($NT$ actions in total) the communication cost of DisBE-LUCB is only $tildemathcalO(dN)$ and its regret is at most $tildemathcalO
  arXiv  Detail & Related papers  (2022-05-26T05:56:23Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. An $varepsilon$-solution is achieved in $tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$ number of communications steps. This rate matches (up to poly-log factors) for the first time lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest.
  arXiv  Detail & Related papers  (2021-10-24T04:03:00Z)
• Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning [1.8414221462731502]
  This paper considers the problem of resilient distributed optimization and machine learning in a server-based architecture. The system comprises a server and multiple agents, where each agent has a local cost function. We consider the case when some of the agents may be asynchronous and/or Byzantine faulty.
  arXiv  Detail & Related papers  (2021-10-21T02:41:19Z)
• Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy [1.7188280334580197]
  We consider the problem of Byzantine faulttolerance in federated machine learning. In fault-free setting, the agents collaborate with the coordinator to find a minimizer of the aggregate of their local cost functions. We show that, under $2f$-redundancy, the federated local algorithm with CE can indeed obtain exact fault-tolerance.
  arXiv  Detail & Related papers  (2021-08-26T13:04:28Z)

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.