Setwise Coordinate Descent for Dual Asynchronous Decentralized Optimization This article has been accepted for publication in IEEE Transactions on Automatic Control, DOI 10.1109/TAC.2025.3543463. © 2025 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all o
Marina Costantini, Nikolaos Liakopoulos, Panayotis Mertikopoulos, Thrasyvoulos Spyropoulos · 2025
Read Setwise Coordinate Descent for Dual Asynchronous Decentralized Optimization This article has been accepted for publication in IEEE Transactions on Automatic Control, DOI 10.1109/TAC.2025.3543463. © 2025 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all o by Marina Costantini, Nikolaos Liakopoulos, Panayotis Mertikopoulos, Thrasyvoulos Spyropoulos (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-19004.txt.
Introduction
Networks of computers that solve one problem together waste time when every node must wait for the others. Marina Costantini and three co-authors study looser, asynchronous schemes in a 2025 paper, where any node may wake, pick one neighbor, and update with it. Their twist: instead of picking a neighbor at random, each node picks the one promising the largest improvement in a dual score.
That greedy pick resembles a classic rule from coordinate methods, but here only some coordinates are reachable at each step. The authors build a new proof framework for this setting and show the greedy rule can cut the needed rounds by a factor tied to neighborhood size.
Catalog record
| CREATOR | Marina Costantini, Nikolaos Liakopoulos, Panayotis Mertikopoulos, Thrasyvoulos Spyropoulos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19004
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Setwise Coordinate Descent for Dual Asynchronous Decentralized Optimization This article has been accepted for publication in IEEE Transactions on Automatic Control, DOI 10.1109/TAC.2025.3543463. © 2025 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Marina Costantini, Nikolaos Liakopoulos, Panayotis Mertikopoulos, Thrasyvoulos Spyropoulos Abstract In decentralized optimization over networks, synchronizing the updates of all nodes incurs significant communication overhead. For this reason, much of the recent literature has focused on the analysis and design of asynchronous optimization algorithms where nodes can activate anytime and contact a single neighbor to complete an iteration together. However, most works assume that the neighbor selection is done at random based on a fixed probability distribution (e.g., uniform), a choice that ignores the optimization landscape at the moment of activation. Instead, in this work we introduce an optimization-aware selection rule that chooses the neighbor providing the highest dual cost improvement (a quantity related to a dualization of the problem based on consensus). This scheme is related to the coordinate descent (CD) method with the Gauss-Southwell (GS) rule for coordinate updates; in our setting however, only a subset of coordinates is accessible at each iteration (because each node can communicate only with its neighbors), so the existing literature on GS methods does not apply. To overcome this difficulty, we develop a new analytical framework for smooth and strongly convex functions that covers our new class of setwise CD algorithms –a class that applies to both decentralized and parallel distributed computing scenarios– and we show that the proposed setwise GS rule can speed up the convergence in terms of iterations by a factor equal to the size of the largest coordinate set. We analyze extensions of these algorithms that exploit the knowledge of the smoothness constants when available and otherwise propose an algorithm to estimate these constants. Finally, we validate our theoretical results through extensive simulations. 1 Introduction Many timely applications require solving optimization problems over a network where nodes can only communicate with their direct neighbors. This may be due to the need of distributing storage and computation loads (e.g. training large machine learning models [ 1 ] ), or to avoid transferring data that is naturally collected in a decentralized manner, either due to the communication costs or to privacy reasons (e.g. sensor networks [ 2 ] , edge computing [ 3 ] , and precision medicine [ 4 ] ). Specifically, we consider a setting where the nodes want to solve the decentralized optimization problem \underset{\theta\in\mathbb{R}^{d}}{\text{minimize}}\quad\sum_{i=1}^{n}f_{i}(\theta), (1) where each local function f_{i} is known only by node i and nodes can exchange optimization values (parameters, gradients) but not the local functions themselves. We represent the communication network as a graph \mathcal{G}=(\mathcal{V},\mathcal{E}) with n\,{=}\,|\mathcal{V}|\,{<}\,\infty nodes (agents) and E\,{=}\,|\mathcal{E}| edges, which are the links used by the nodes to communicate with their neighbors. Existing methods to solve this problem usually assign to each node a local variable \theta_{i} and execute updates that interleave a local gradient step at the nodes followed by an averaging step (usually carried out by a doubly-stochastic matrix) that aggregates the update of the node with those of its neighbors [ 5 , 6 , 7 , 8 , 9 , 10 ] . Alternatively, the consensus constraint can be stated explicitly between node pairs connected by an edge: \displaystyle\underset{\theta_{1},\ldots,\theta_{n}\in\mathbb{R}^{d}}{\text{minimize}}\quad \displaystyle\sum_{i=1}^{n}f_{i}(\theta_{i}) (2a) subject to \displaystyle\theta_{i}=\theta_{j}\quad\forall\;(i,j)\equiv\ell\in\mathcal{E}, (2b) where \ell\equiv(i,j) indicates that edge \ell links nodes i and j . This reformulation allows solving the decentralized optimization problem through its dual problem. Interestingly, dual decentralized algorithms are among the very few that have been shown to achieve optimal convergence rates [ 11 , 12 , 13 ] when using acceleration. However, these algorithms are synchronous , in the sense that they require coordinating the updates of all nodes at each iteration. In contrast, by exploiting connections with coordinate descent theory naturally derived from the dual formulation, here we propose an alternative way to speed up convergence in dual decentralized optimization that does not require network-wide synchronicity. In our setup, nodes activate anytime at random and select one of their neighbors to make an update together. Methods with such minimal coordination requirements avoid incurring extra costs of synchronization that may also slow down convergence [ 14 , 15 , 16 , 17 , 18 ] . However, most of these works assume that when a node activates, it simply selects the neighbor to contact randomly, based on a predefined probability distribution. This approach overlooks the possibility of letting nodes choose the neighbor to contact taking into account the optimization landscape at the time of activation. Therefore, here we depart from the probabilistic choice and ask: can nodes pick the neighbor smartly to make the optimization converge faster? In this paper, we give an affirmative answer and propose algorithms that achieve this by solving the dual problem of ( 2 ). In the dual formulation, there is one dual variable \lambda_{\ell}\in\mathbb{R}^{d} per constraint \theta_{i}=\theta_{j} , hence each dual variable can be associated with an edge \ell in the graph. Our algorithms let an activated node i contact a neighbor j so that together they update their shared variable \lambda_{\ell},\;\ell\equiv(i,j) with a gradient step. In particular, we propose to select the neighbor j such that the updated \lambda_{\ell} is the one whose directional gradient for the dual function is the largest , and thus the one that provides the greatest cost improvement at that iteration. Beyond the preliminary version of this work that appeared in [ 19 ] , such dual greedy choice has not yet been considered in the literature. Interestingly, the above protocol where a node activates and selects a \lambda_{\ell} to update can be seen as applying the coordinate descent (CD) method [ 20 ] to solve the dual problem of ( 2 ), with the following key difference: unlike standard CD methods, where any of the coordinates may be updated, now only a small subset of coordinates are accessible at each step , which are the coordinates associated with the edges connected to the node activated. Moreover, our proposal of updating the \lambda_{\ell} with the largest gradient is similar to the Gauss-Southwell (GS) rule [ 21 ] , but applied only to the parameters accessible by the activated node. We name such protocols setwise CD algorithms, and we analyze a number of possibilities for the coordinate (or equivalently, neighbor) choice: random sampling, local GS, and two extensions that take into account the smoothness constants of the dual function. Compared to standard CD literature, three difficulties complicate the analysis and constitute the base of our contributions: (i) for arbitrary graphs, the dual problem of ( 2 ) has an objective function that is not strongly convex, even if the primal functions f_{i} are strongly convex, (ii) the fact that the GS rule is applied to a few coordinates prevents the use of standard norms to obtain the linear rate, as commonly done for CD methods [ 20