MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods

• URL: http://arxiv.org/abs/2403.02589v1
• Date: Tue, 5 Mar 2024 02:02:00 GMT
• Title: MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods
• Authors: Mou Wu, Haibin Liao, Zhengtao Ding, Yonggang Xiao
• Abstract summary: In this paper, we propose an accelerated framework named as MUSIC allowing each agent to perform multiple local updates and a single combination in each iteration. We equip inexact and exact distributed optimization methods into this framework, thereby developing two new algorithms that exhibit accelerated linear convergence and high communication efficiency.
• Score: 6.800113478497425
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gradient-type distributed optimization methods have blossomed into one of the most important tools for solving a minimization learning task over a networked agent system. However, only one gradient update per iteration is difficult to achieve a substantive acceleration of convergence. In this paper, we propose an accelerated framework named as MUSIC allowing each agent to perform multiple local updates and a single combination in each iteration. More importantly, we equip inexact and exact distributed optimization methods into this framework, thereby developing two new algorithms that exhibit accelerated linear convergence and high communication efficiency. Our rigorous convergence analysis reveals the sources of steady-state errors arising from inexact policies and offers effective solutions. Numerical results based on synthetic and real datasets demonstrate both our theoretical motivations and analysis, as well as performance advantages.

Related papers

• Towards Differentiable Multilevel Optimization: A Gradient-Based Approach [1.6114012813668932]
  This paper introduces a novel gradient-based approach for multilevel optimization. Our method significantly reduces computational complexity while improving both solution accuracy and convergence speed. To the best of our knowledge, this is one of the first algorithms to provide a general version of implicit differentiation.
  arXiv  Detail & Related papers  (2024-10-15T06:17:59Z)
• Nonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Data [23.661713049508375]
  We propose an algorithm that learns over a submanifold in the setting of a client. We show that our proposed algorithm converges sub-ly to a neighborhood of a first-order optimal solution by using a novel analysis.
  arXiv  Detail & Related papers  (2024-06-12T17:53:28Z)
• Optimizing the Optimal Weighted Average: Efficient Distributed Sparse Classification [50.406127962933915]
  ACOWA allows an extra round of communication to achieve noticeably better approximation quality with minor runtime increases. Results show that ACOWA obtains solutions that are more faithful to the empirical risk minimizer and attain substantially higher accuracy than other distributed algorithms.
  arXiv  Detail & Related papers  (2024-06-03T19:43:06Z)
• On the Communication Complexity of Decentralized Bilevel Optimization [40.45379954138305]
  We propose two novel decentralized bilevel gradient descent algorithms based on simultaneous and alternating update strategies. Our algorithms can achieve faster convergence rates and lower communication costs than existing methods. This is the first time such favorable theoretical results have been achieved with mild assumptions in the heterogeneous setting.
  arXiv  Detail & Related papers  (2023-11-19T14:56:26Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• 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)
• 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)
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization [85.84019017587477]
  Distributionally robust supervised learning is emerging as a key paradigm for building reliable machine learning systems for real-world applications. Existing algorithms for solving Wasserstein DRSL involve solving complex subproblems or fail to make use of gradients. We revisit Wasserstein DRSL through the lens of min-max optimization and derive scalable and efficiently implementable extra-gradient algorithms.
  arXiv  Detail & Related papers  (2021-04-27T16:56:09Z)
• Fast Rates for Contextual Linear Optimization [52.39202699484225]
  We show that a naive plug-in approach achieves regret convergence rates that are significantly faster than methods that directly optimize downstream decision performance. Our results are overall positive for practice: predictive models are easy and fast to train using existing tools, simple to interpret, and, as we show, lead to decisions that perform very well.
  arXiv  Detail & Related papers  (2020-11-05T18:43:59Z)
• FedSplit: An algorithmic framework for fast federated optimization [40.42352500741025]
  We introduce FedSplit, a class of algorithms for solving distributed convex minimization with additive structure. Our theory shows that these methods are provably robust to inexact computation of intermediate local quantities.
  arXiv  Detail & Related papers  (2020-05-11T16:30:09Z)
• Dynamic Federated Learning [57.14673504239551]
  Federated learning has emerged as an umbrella term for centralized coordination strategies in multi-agent environments. We consider a federated learning model where at every iteration, a random subset of available agents perform local updates based on their data. Under a non-stationary random walk model on the true minimizer for the aggregate optimization problem, we establish that the performance of the architecture is determined by three factors, namely, the data variability at each agent, the model variability across all agents, and a tracking term that is inversely proportional to the learning rate of the algorithm.
  arXiv  Detail & Related papers  (2020-02-20T15:00:54Z)

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.