Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning

• URL: http://arxiv.org/abs/2110.10858v1
• Date: Thu, 21 Oct 2021 02:41:19 GMT
• Title: Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning
• Authors: Shuo Liu, Nirupam Gupta, Nitin Vaidya
• Abstract summary: 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.
• Score: 1.8414221462731502
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This paper considers the problem of resilient distributed optimization and stochastic machine learning in a server-based architecture. The system comprises a server and multiple agents, where each agent has a local cost function. The agents collaborate with the server to find a minimum of their aggregate cost functions. We consider the case when some of the agents may be asynchronous and/or Byzantine faulty. In this case, the classical algorithm of distributed gradient descent (DGD) is rendered ineffective. Our goal is to design techniques improving the efficacy of DGD with asynchrony and Byzantine failures. To do so, we start by proposing a way to model the agents' cost functions by the generic notion of $(f, \,r; \epsilon)$-redundancy where $f$ and $r$ are the parameters of Byzantine failures and asynchrony, respectively, and $\epsilon$ characterizes the closeness between agents' cost functions. This allows us to quantify the level of redundancy present amongst the agents' cost functions, for any given distributed optimization problem. We demonstrate, both theoretically and empirically, the merits of our proposed redundancy model in improving the robustness of DGD against asynchronous and Byzantine agents, and their extensions to distributed stochastic gradient descent (D-SGD) for robust distributed machine learning with asynchronous and Byzantine agents.

Related papers

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization. We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• DCatalyst: A Unified Accelerated Framework for Decentralized Optimization [10.925931212031692]
  We study decentralized optimization over a network of agents, modeled as graphs, with no central server. We introduce DCatalyst, a unified black-box framework that integrates Nesterov acceleration into decentralized optimization algorithms.
  arXiv  Detail & Related papers  (2025-01-30T03:32:59Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  We consider a setting in which $N$ agents aim to speedup a common Approximation problem by acting in parallel and communicating with a central server. To mitigate the effect of delays and stragglers, we propose textttDASA, a Delay-Adaptive algorithm for multi-agent Approximation.
  arXiv  Detail & Related papers  (2024-03-25T22:49:56Z)
• Compressed Regression over Adaptive Networks [58.79251288443156]
  We derive the performance achievable by a network of distributed agents that solve, adaptively and in the presence of communication constraints, a regression problem. We devise an optimized allocation strategy where the parameters necessary for the optimization can be learned online by the agents.
  arXiv  Detail & Related papers  (2023-04-07T13:41:08Z)
• Impact of Redundancy on Resilience in Distributed Optimization and Learning [4.664766612388049]
  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.
  arXiv  Detail & Related papers  (2022-11-16T02:23:34Z)
• Federated Learning Using Variance Reduced Stochastic Gradient for Probabilistically Activated Agents [0.0]
  This paper proposes an algorithm for Federated Learning (FL) with a two-layer structure that achieves both variance reduction and a faster convergence rate to an optimal solution in the setting where each agent has an arbitrary probability of selection in each iteration.
  arXiv  Detail & Related papers  (2022-10-25T22:04:49Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  We propose to solve a regularized distributionally robust learning problem in the decentralized setting. By adding a Kullback-Liebler regularization function to the robust min-max optimization problem, the learning problem can be reduced to a modified robust problem. We show that our proposed algorithm can improve the worst distribution test accuracy by up to $10%$.
  arXiv  Detail & Related papers  (2022-08-29T18:01:42Z)
• On Accelerating Distributed Convex Optimizations [0.0]
  This paper studies a distributed multi-agent convex optimization problem. We show that the proposed algorithm converges linearly with an improved rate of convergence than the traditional and adaptive gradient-descent methods. We demonstrate our algorithm's superior performance compared to prominent distributed algorithms for solving real logistic regression problems.
  arXiv  Detail & Related papers  (2021-08-19T13:19:54Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates [70.9701218475002]
  We introduce a unified convergence analysis of decentralized communication methods. We derive universal convergence rates for several applications. Our proofs rely on weak assumptions.
  arXiv  Detail & Related papers  (2020-03-23T17:49:15Z)

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.