Understanding A Class of Decentralized and Federated Optimization Algorithms: A Multi-Rate Feedback Control Perspective

• URL: http://arxiv.org/abs/2204.12663v1
• Date: Wed, 27 Apr 2022 01:53:57 GMT
• Title: Understanding A Class of Decentralized and Federated Optimization Algorithms: A Multi-Rate Feedback Control Perspective
• Authors: Xinwei Zhang, Mingyi Hong, Nicola Elia
• Abstract summary: We provide a fresh perspective to understand, analyze, and design distributed optimization algorithms. We show that a wide class of distributed algorithms, including popular decentralized/federated schemes, can be viewed as discretizing a certain continuous-time feedback control system.
• Score: 41.05789078207364
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Distributed algorithms have been playing an increasingly important role in many applications such as machine learning, signal processing, and control. Significant research efforts have been devoted to developing and analyzing new algorithms for various applications. In this work, we provide a fresh perspective to understand, analyze, and design distributed optimization algorithms. Through the lens of multi-rate feedback control, we show that a wide class of distributed algorithms, including popular decentralized/federated schemes, can be viewed as discretizing a certain continuous-time feedback control system, possibly with multiple sampling rates, such as decentralized gradient descent, gradient tracking, and federated averaging. This key observation not only allows us to develop a generic framework to analyze the convergence of the entire algorithm class. More importantly, it also leads to an interesting way of designing new distributed algorithms. We develop the theory behind our framework and provide examples to highlight how the framework can be used in practice.

Related papers

• A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
  Hamiltonian Learning is a novel unified framework for learning with neural networks "over time" It is based on differential equations that: (i) can be integrated without the need of external software solvers; (ii) generalize the well-established notion of gradient-based learning in feed-forward and recurrent networks; (iii) open to novel perspectives.
  arXiv  Detail & Related papers  (2024-09-18T14:57:13Z)
• Distributional Bellman Operators over Mean Embeddings [37.5480897544168]
  We propose a novel framework for distributional reinforcement learning, based on learning finite-dimensional mean embeddings of return distributions. We derive several new algorithms for dynamic programming and temporal-difference learning based on this framework.
  arXiv  Detail & Related papers  (2023-12-09T11:36:14Z)
• Neural Algorithmic Reasoning Without Intermediate Supervision [21.852775399735005]
  We focus on learning neural algorithmic reasoning only from the input-output pairs without appealing to the intermediate supervision. We build a self-supervised objective that can regularise intermediate computations of the model without access to the algorithm trajectory. We demonstrate that our approach is competitive to its trajectory-supervised counterpart on tasks from the CLRSic Algorithmic Reasoning Benchmark.
  arXiv  Detail & Related papers  (2023-06-23T09:57:44Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• 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)
• Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond [114.39616146985001]
  In machine learning and computer vision fields, despite the different motivations and mechanisms, a lot of complex problems contain a series of closely related subproblms. In this paper, we first uniformly express these complex learning and vision problems from the perspective of Bi-Level Optimization (BLO) Then we construct a value-function-based single-level reformulation and establish a unified algorithmic framework to understand and formulate mainstream gradient-based BLO methodologies.
  arXiv  Detail & Related papers  (2021-01-27T16:20:23Z)
• A general framework for decentralized optimization with first-order methods [11.50057411285458]
  Decentralized optimization to minimize a finite sum of functions over a network of nodes has been a significant focus in control and signal processing research. The emergence of sophisticated computing and large-scale data science needs have led to a resurgence of activity in this area. We discuss decentralized first-order gradient methods, which have found tremendous success in control, signal processing, and machine learning problems.
  arXiv  Detail & Related papers  (2020-09-12T17:52:10Z)
• Reinforcement Learning as Iterative and Amortised Inference [62.997667081978825]
  We use the control as inference framework to outline a novel classification scheme based on amortised and iterative inference. We show that taking this perspective allows us to identify parts of the algorithmic design space which have been relatively unexplored.
  arXiv  Detail & Related papers  (2020-06-13T16:10:03Z)
• Unbiased Deep Reinforcement Learning: A General Training Framework for Existing and Future Algorithms [3.7050607140679026]
  We propose a novel training framework that is conceptually comprehensible and potentially easy to be generalized to all feasible algorithms for reinforcement learning. We employ Monte-carlo sampling to achieve raw data inputs, and train them in batch to achieve Markov decision process sequences. We propose several algorithms embedded with our new framework to deal with typical discrete and continuous scenarios.
  arXiv  Detail & Related papers  (2020-05-12T01:51: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.