Distributed Optimization with Gradient Tracking over Heterogeneous Delay-Prone Directed Networks

Evagoras Makridis, Gabriele Oliva, Kasagatta Ramesh Narahari, Mohammadreza Doostmohammadian, Usman A. Khan, Themistoklis Charalambous · 2025

Read Distributed Optimization with Gradient Tracking over Heterogeneous Delay-Prone Directed Networks by Evagoras Makridis, Gabriele Oliva, Kasagatta Ramesh Narahari, Mohammadreza Doostmohammadian, Usman A. Khan, Themistoklis Charalambous (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10964.txt.

Introduction

Makridis and co-authors present a 2025 method for shared problem solving across a network where links run one way and messages can be delayed. Each node holds part of a larger best fit problem, and all nodes must settle on the same best answer. Delays differ by link, which can break older shared methods.

Their updated method, a hardened form of a known directed method, tracks slopes as it works and stands up to bounded delays. The authors prove that nodes reach the best answer when the step size sits in a set range. That range can be worked out ahead of time from the largest delay in the network.

Catalog record

CREATOREvagoras Makridis, Gabriele Oliva, Kasagatta Ramesh Narahari, Mohammadreza Doostmohammadian, Usman A. Khan, Themistoklis Charalambous
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-10964

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distributed Optimization with Gradient Tracking over Heterogeneous Delay-Prone Directed Networks Evagoras Makridis, Gabriele Oliva, Kasagatta Ramesh Narahari, Mohammadreza Doostmohammadian, Usman A. Khan, Themistoklis Charalambous Abstract In this paper, we address the distributed optimization problem over unidirectional networks with possibly time-invariant heterogeneous bounded transmission delays. In particular, we propose a modified version of the Accelerated Distributed Directed OPTimization (ADD-OPT) algorithm, herein called Robustified ADD-OPT (R-ADD-OPT), which is able to solve the distributed optimization problem, even when the communication links suffer from heterogeneous but bounded transmission delays. We show that if the gradient step-size of the R-ADD-OPT algorithm is within a certain range, which also depends on the maximum time delay in the network, then the nodes are guaranteed to converge to the optimal solution of the distributed optimization problem. The range of the gradient step-size that guarantees convergence can be computed a priori based on the maximum time delay in the network. I Introduction Recently, there has been an increasing number of multi-agent optimization problems where a group of agents aims at optimizing the sum of their objective functions, by allowing local information exchange over an underlying communication network. Such formulation arises in cases where each agent has a local objective and the objective is to reach a compromise without resorting to central coordination. Such a distributed formulation is extensively used to solve multi-node optimization problems for several large-scale applications, including distributed energy resource management [ 1 , 2 ] , resource allocation in data centers [ 3 ] , large-scale machine learning [ 4 , 5 ] , and distributed localization in sensor networks [ 6 , 7 ] . In particular, in a multi-agent system comprised of a set of n agents communicating over a network, each agent j , represented by a node in a graph, has access only to its own local objective function f_{j}:\mathbb{R}\rightarrow\mathbb{R} , and aims at minimizing the sum of objectives \sum_{j=1}^{n}f_{j}(z) , where the common decision variable 1 1 1 To simplify the presentation and analysis, in this work, we use a scalar decision variable. However, the results presented herein can be readily extended to vector variables. z\in\mathbb{R} is computed via information exchange and agreement with its neighbors. More specifically, the agents aim at solving cooperatively the following optimization problem: \min_{z}\frac{1}{n}\sum_{j=1}^{n}f_{j}(z). (1) Over the past decade, considerable research efforts have been dedicated in consensus-based distributed optimization problems over networks with bidirectional links, forming undirected graphs. Such contributions have been extensively studied and presented in [ 8 , 9 , 10 ] . These works exploit the symmetry of bidirectional communication structure to enable the construction of doubly-stochastic consensus weight matrices, so that local decision variables of networked agents collaboratively converge towards the solution of the distributed optimization problem in ( 1 ). While initial efforts yielded valuable insights and algorithms, attention has shifted to more realistic scenarios with unidirectional network links, where the information might flow in only one direction. This attribute is prevalent in wireless communication due to varying transmission power and interference levels. Such (possibly asymmetric) networks are represented as directed graphs (digraphs), where directed edges represent unidirectional communication links. To address the distributed optimization problem over unidirectional links, there have been different approaches that are based on the following distributed average consensus methods: (a) the distributed weight balancing [ 11 ] where agents adjust the weights on their outgoing links to asymptotically reach weights that form a doubly-stochastic matrix, (b) the surplus-based approach [ 12 ] where the asymmetry of the digraph is mitigated by augmenting the state of each agent with an additional variable (often called surplus ) that locally tracks individual state updates through the assignment of weights on both the incoming and outgoing links that form both row-stochastic and column-stochastic matrices, respectively, and (c) ratio consensus [ 13 ] where agents run an extra concurrent iteration that asymptotically learns the right eigenvector of the column-stochastic matrix that is formed by having agents assign weights on their outgoing links. For more information and comparison between these distributed average consensus methods over digraphs, the interested reader is referred to [ 14 ] . In the context of distributed optimization over reliable and time-invariant digraphs, Xi et. al. introduced two algorithms based on the ratio consensus protocol: the Directed EXact firsT-ordeR Algorithm (DEXTRA) [ 15 ] and ADD-OPT [ 16 ] that incorporates gradient tracking to record and correct the locally aggregated gradients at each agent, and accelerate the convergence to the optimal solution. Moreover, Nedich et. al. in [ 17 , 18 ] proposed the Subgradient-push and Push-DIGing algorithms for time-varying digraphs, based on the push-sum consensus algorithm. Using the surplus-consensus method, Xi et. al. introduced the Directed-Distributed Projected Subgradient (D-DPS) and Directed-Distributed Gradient Descent (D-DGD) algorithm, respectively, to solve distributed optimization problems over digraphs, in [ 19 ] and [ 20 ] , respectively. Although the aforementioned distributed optimization algorithms can successfully overcome the asymmetry of unidirectional networks and potentially find the optimal solution in ( 1 ), none of them considered unreliable networks where the information flow between agents might be delayed. This factor arises inherently as the number of agents in the network grows, and hence a corresponding increase in the quantity of communication links can occur. This surge of links often results in information congestion within the network, giving rise to transmission delays that exert a significant degradation on the performance and efficacy of distributed optimization algorithms. Extensive work has been done, towards the development of mitigation strategies for addressing the challenges posed by congested networks, including the transmission delays encountered over communication links. These challenges have been analysed in the works presented in [ 21 , 22 ] , in the context of distributed average consensus. Interestingly, in the context of distributed optimization, an early work in [ 23 ] by Tsianos et. al. analyzed a push-sum consensus-based distributed optimization algorithm for digraphs that can handle fixed bounded communication delays. However, this work lacks the analysis of convergence, as well as the incorporation of gradient tracking, a crucial feature known for expediting the convergence to the optimal solution [ 24 , 25 , 26 ] . The aforementioned works illustrate the promising potential in the study and development of communication-aware strategies tailored to overcome the challenges posed by communication delays in the context of consensus-based distributed optimization algorithms. To the best of our knowledge, our work is the first to propose and analyze a distributed optimization algorithm with gradient tracking over directed graphs in the presence of time-invariant delays, as highlighted in Table I . TABLE I: Gradient-based distributed optimization algorithms over directed graphs ( k denotes the number of algorithm iterations, and 0<\mu<1 the convexity constant, introduced in the subsequent section). Algorithm Delays Converg. Rate Grad. Tracking D-DGD [ 20 ] – \mathcal{O}\left(\frac{\ln k}{\sqrt{k}}\right) – D-DPS [ 19 ] – \mathcal{O}\left(\frac{1}{\sqrt{k}}\right) – S-Push [ 17 ] – \mathcal{O}\left(\frac{\ln k}{\sqrt{k}}\right) – PS-DDA [ 23 ] fixed \mathcal{O}\left(\frac{1}{\sqrt{k}}\right) – DEXTRA [ 15 ] – \mathcal{O}\left(\mu^{k}\right) ✓ ADD-OPT [ 16 ] – \mathcal{O}\left(\mu^{k}\right) ✓ Push-DIGing [ 18 ] – \mathcal{O}\left(\mu^{k}\right) ✓ R-ADD-OPT fixed \mathcal{O}\left(\mu^{k}\right) ✓ In this work, we tackle the problem of distributed optimization over directed graphs, where the transmission links are prone to heterogeneous

Read the complete text