Decentralized Optimization via RC-ALADIN with Efficient Quantized Communication

Xu Du, Karl H. Johansson, Apostolos I. Rikos · 2025

Read Decentralized Optimization via RC-ALADIN with Efficient Quantized Communication by Xu Du, Karl H. Johansson, Apostolos I. Rikos (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-2508-06197.txt.

Introduction

Xu Du, Karl Johansson, and Apostolos Rikos design a split optimization method for linked nodes with thin links in 2025. Nodes must agree on one best answer while each holds its own goal curve, and messages can carry only rough, quantized values. Their method joins a cut-down consensus scheme with a fast quantized pact step.

Proofs show straight-line approach to a zone near the best answer, with zone size set by the rough grade of messages. The same pace holds for plain convex goals. Tests beat current rivals while using far less link space.

Catalog record

CREATORXu Du, Karl H. Johansson, Apostolos I. Rikos
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-06197

Browse the full library · About the Tower of Babel

Full text

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

Decentralized Optimization via RC-ALADIN with Efficient Quantized Communication Xu Du, Karl H. Johansson, Apostolos I. Rikos Abstract In this paper, we investigate the problem of decentralized consensus optimization over directed graphs with limited communication bandwidth. We introduce a novel decentralized optimization algorithm that combines the Reduced Consensus Augmented Lagrangian Alternating Direction Inexact Newton (RC-ALADIN) method with a finite time quantized coordination protocol, enabling quantized information exchange among nodes. Assuming the nodes’ local objective functions are μ \mu -strongly convex and simply smooth, we establish global convergence at a linear rate to a neighborhood of the optimal solution, with the neighborhood size determined by the quantization level. Additionally, we show that the same convergence result also holds for the case where the local objective functions are convex and L L -smooth. Numerical experiments demonstrate that our proposed algorithm compares favorably against algorithms in the current literature while exhibiting communication efficient operation. I Introduction Decentralized optimization has garnered significant attention in recent years, driven by advances in areas such as control systems [ 1 ] , machine learning [ 2 ] , and power grids [ 3 ] . This growing interest is largely due to the increasing need to address optimization problems that involve vast amounts of data and heterogeneous objective functions. Decentralized optimization distributes data across multiple network nodes, typically using two main approaches: (i) primal decomposition and (ii) dual decomposition. Both methods locally optimize the objective functions. Primal decomposition methods focus on sharing primal information among nodes, such as local optimal solutions or first- and second-order objective function data (e.g., [ 4 , 5 ] ). In contrast, dual decomposition methods update both the primal and the dual variables associated with coupling constraints (e.g., [ 6 ] , [ 7 ] ). In general, dual decomposition methods achieve faster convergence and higher accuracy than primal decomposition approaches [ 8 , Section I] . In this paper we focus on dual decomposition methods. Existing Literature. Dual decomposition-based optimization methods are built upon several core frameworks: Dual Decomposition [ 9 ] , the Alternating Direction Method of Multipliers (ADMM) [ 6 ] , and the Augmented Lagrangian Alternating Direction Inexact Newton (ALADIN) method [ 7 ] . While ADMM has undergone significant developments in both convergence theory and practical applications [ 6 , 10 , 11 ] , ALADIN improves convergence performance—achieving faster rates and ensuring convergence for both convex and nonconvex problems—by incorporating sequential quadratic programming techniques [ 7 , 12 ] . Subsequent developments have introduced specialized variants of ALADIN designed to tackle diverse computational complexity challenges [ 13 , 14 , 15 , 1 , 12 ] . However, two key limitations of these approaches are (i) their reliance on centralized coordination mechanisms (which limits scalability in distributed systems), and (ii) the requirement of nodes transmitting real-valued messages requiring a significant amount of bandwidth (which creates a scalability bottleneck). To address the first challenge, the works [ 16 , 8 , 17 ] investigated its decentralization for both resource allocation and consensus problems. Furthermore, recent works [ 18 , 1 ] have extended ALADIN to decentralized settings, however focusing only on resource allocation problems. Note that, despite some existing studies on variants of consensus ALADIN, such as [ 12 , 19 ] , a decentralized version of this framework has yet to be explored and addressed in the literature. Meanwhile, to address the second challenge of inefficient communication due to transmission of real-valued messages, the works in [ 20 , 21 ] investigated decentralized Consensus ADMM with quantized communication on undirected graphs. Although the aforementioned works have advanced ADMM development, they have only addressed some of the identified bottlenecks. The aforementioned literature has certain limitations, such as assuming a centralized coordinator, requiring nodes to exchange real-valued messages, or being restricted to undirected graphs. To the best of our knowledge, [ 22 ] is the only study to explore decentralized Consensus ADMM on directed graphs while enabling nodes to communicate in a resource efficient manner by exchanging quantized valued messages. Note that, although Consensus ALADIN exhibits superior convergence performance compared to Consensus ADMM [ 12 ] , its decentralized variant which however exhibits efficient communication with quantized value on directed graphs remains a problem that is unexplored in the literature. Main Contributions. Motivated by the aforementioned challenges, we introduce a novel decentralized optimization algorithm leveraging Consensus ALADIN to tackle these issues. Note that to the authors knowledge, it is the first that Consensus ALADIN to address (i) fully decentralized algorithm operation, (ii) communication over directed graphs, and (iii) quantized communication among nodes. Inspired by [ 22 ] and [ 23 ] , we note that adopting a two-layer algorithmic structure—where the optimization steps are decoupled from the decentralized averaging procedure—can achieve faster convergence compared to approaches that interleave optimization and communication in a single layer. Our contributions are the following. A. We present a novel two-layer decentralized optimization algorithm, termed Quantized Decentralized Reduced Consensus ALADIN (QuDRC-ALADIN) (see Algorithm 1 ), designed to operate over directed communication graphs. The inner layer (Algorithm 2 , inspired by [ 22 ] ) enables efficient communication among nodes via the exchange of quantized messages. The outer layer (i.e., the remaining steps of Algorithm 1 ) is responsible for updating the primal and dual variables of the original optimization problem. B. We prove that our algorithm converges to a neighborhood of the optimal solution (where the neighborhood depends on the quantization level) with global linear convergence rate for the case where the local cost function of each node is \mu -strongly convex, closed, proper, and simply smooth (see Theorem 1 ). Additionally, we show that our algorithm exhibits global linear convergence rate also for the case where the local cost function of each node is convex, closed, proper, and L -smooth (see Corollary 1 ). II Notation and Preliminaries Notation. We use the symbols \mathbb{R} , \mathbb{Q} , \mathbb{Z} , and \mathbb{N} to represent the sets of real, rational, integer, and natural numbers, respectively. Matrices are indicated by capital letters (e.g., A ), and vectors are represented by lowercase letters (e.g., a ). The transpose of matrix A\in\mathbb{R}^{n\times n} and vector a\in\mathbb{R}^{n} are represented as A^{\top} and a^{\top} , respectively. For a real number a\in\mathbb{R} , \lfloor a\rfloor and \lceil a\rceil denote the greatest integer less than or equal to a and the least integer greater than or equal to a , respectively. For the real vector a\in\mathbb{R}^{n} , \lfloor a\rfloor\in\mathbb{R}^{n} and \lceil a\rceil\in\mathbb{R}^{n} denote the element-wise operation. Furthermore, \mathbf{1} represents the vector of all ones and I denotes the identity matrix with appropriate dimensions. In addition, \|a\| denotes the Euclidean norm of the vector a . The value of a variable x of node i at iteration k is denoted as x_{i}^{[k]} . The updated value is denoted as (\cdot)^{+} . Furthermore, |\mathcal{S}| denotes the cardinality of a countable set \mathcal{S} (e.g. |\mathcal{V}|=N as we can see below). The notation a|b denotes b\in\mathbb{R}^{n} as the dual variable of constraint a\in\mathbb{R}^{n} . Graph Theory. The communication network is captured by a directed graph (or digraph) \mathcal{G}=(\mathcal{V},\mathcal{E}) . The set of agents (nodes) is denoted as \mathcal{V}=\{1,\cdots,N\} (where |\mathcal{V}|\geq 2 ). The set of edges

Read the complete text