Decentralized Optimization in Time-Varying Networks with Arbitrary Delays

• URL: http://arxiv.org/abs/2405.19513v2
• Date: Tue, 01 Oct 2024 18:19:34 GMT
• Title: Decentralized Optimization in Time-Varying Networks with Arbitrary Delays
• Authors: Tomas Ortega, Hamid Jafarkhani,
• Abstract summary: We consider a decentralized optimization problem for networks affected by communication delays. Examples of such networks include collaborative machine learning, sensor networks, and multi-agent systems. To mimic communication delays, we add virtual non-computing nodes to the network, resulting in directed graphs.
• Score: 22.40154714677385
• License:
• Abstract: We consider a decentralized optimization problem for networks affected by communication delays. Examples of such networks include collaborative machine learning, sensor networks, and multi-agent systems. To mimic communication delays, we add virtual non-computing nodes to the network, resulting in directed graphs. This motivates investigating decentralized optimization solutions on directed graphs. Existing solutions assume nodes know their out-degrees, resulting in limited applicability. To overcome this limitation, we introduce a novel gossip-based algorithm, called DT-GO, that does not need to know the out-degrees. The algorithm is applicable in general directed networks, for example networks with delays or limited acknowledgment capabilities. We derive convergence rates for both convex and non-convex objectives, showing that our algorithm achieves the same complexity order as centralized Stochastic Gradient Descent. In other words, the effects of the graph topology and delays are confined to higher-order terms. Additionally, we extend our analysis to accommodate time-varying network topologies. Numerical simulations are provided to support our theoretical findings.

Related papers

• NetDiff: Deep Graph Denoising Diffusion for Ad Hoc Network Topology Generation [1.6768151308423371]
  We introduce NetDiff, a graph denoising diffusion probabilistic architecture that generates wireless ad hoc network link topologies. Our results show that the generated links are realistic, present structural properties similar to the dataset graphs', and require only minor corrections and verification steps to be operational.
  arXiv  Detail & Related papers  (2024-10-09T15:39:49Z)
• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  We consider the task of minimizing the sum of convex functions stored in a decentralized manner across the nodes of a communication network. Lower bounds on the number of decentralized communications and (sub)gradient computations required to solve the problem have been established. We develop the first optimal algorithm that matches these lower bounds and offers substantially improved theoretical performance compared to the existing state of the art.
  arXiv  Detail & Related papers  (2024-05-28T10:28:45Z)
• Deploying Graph Neural Networks in Wireless Networks: A Link Stability Viewpoint [13.686715722390149]
  Graph neural networks (GNNs) have exhibited promising performance across a wide range of graph applications. In wireless systems communication among nodes are usually due to wireless fading and receiver noise consequently in degradation of GNNs.
  arXiv  Detail & Related papers  (2024-05-09T14:37:08Z)
• Estimation Network Design framework for efficient distributed optimization [3.3148826359547514]
  This paper introduces Estimation Network Design (END), a graph theoretical language for the analysis and design of distributed iterations. END algorithms can be tuned to exploit the sparsity of specific problem instances, reducing communication overhead and minimizing redundancy. In particular, we study the sparsity-aware version of many established methods, including ADMM, AugDGM and Push-Sum DGD.
  arXiv  Detail & Related papers  (2024-04-23T17:59:09Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Graph Neural Networks for Power Allocation in Wireless Networks with Full Duplex Nodes [10.150768420975155]
  Due to mutual interference between users, power allocation problems in wireless networks are often non-trivial. Graph Graph neural networks (GNNs) have recently emerged as a promising approach tackling these problems and an approach exploits underlying topology of wireless networks.
  arXiv  Detail & Related papers  (2023-03-27T10:59:09Z)
• 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)
• Decentralized Optimization with Heterogeneous Delays: a Continuous-Time Approach [6.187780920448871]
  We propose a novel continuous-time framework to analyze asynchronous algorithms. We describe a fully asynchronous decentralized algorithm to minimize the sum of smooth and strongly convex functions.
  arXiv  Detail & Related papers  (2021-06-07T13:09:25Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay. We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
  arXiv  Detail & Related papers  (2021-05-01T10:18:34Z)
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks [124.33353902111939]
  We propose ADOM - an accelerated method for smooth and strongly convex decentralized optimization over time-varying networks. Up to a constant factor, which depends on the network structure only, its communication is the same as that of accelerated Nesterov method.
  arXiv  Detail & Related papers  (2021-02-18T09:37:20Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  We study a distributed variable for large-scale AUC for a neural network as with a deep neural network. Our model requires a much less number of communication rounds and still a number of communication rounds in theory. Our experiments on several datasets show the effectiveness of our theory and also confirm our theory.
  arXiv  Detail & Related papers  (2020-05-05T18:08:23Z)

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.