Convergence Analysis of Distributed Optimization: A Dissipativity Framework

A. Karakai, J. Eising, A. Martinelli, F. Dörfler · 2025

Read Convergence Analysis of Distributed Optimization: A Dissipativity Framework by A. Karakai, J. Eising, A. Martinelli, F. Dörfler (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-2510-27645.txt.

Introduction

Aron Karakai, Jaap Eising, Andrea Martinelli, and Florian Dörfler offer a systems view of distributed optimization in 2025. In such problems, many units each hold part of a cost and must agree on a shared best choice. Past proofs tend to be built case by case, which makes new designs hard to check.

The team models each method as a web of linked dynamic systems. Tests for success rest on dissipativity, an energy-like balance rule, and on contraction, which means gaps shrink over time. Steps for the check fit any web shape, with rules written as matrix conditions. A numeric test on shared gradient descent shows the gain over older proofs. The frame gives designers a clear, repeatable check.

Catalog record

CREATORA. Karakai, J. Eising, A. Martinelli, F. Dörfler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-27645

Browse the full library · About the Tower of Babel

Full text

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

Convergence Analysis of Distributed Optimization: A Dissipativity Framework Thanks: The authors are with the Automatic Control Laboratory, ETH Zürich, Switzerland (e-mails: {akarakai, jeising, andremar, doerfler}@ethz.ch). A. Karakai, J. Eising, A. Martinelli, F. Dörfler Abstract We develop a system-theoretic framework for the structured analysis of distributed optimization algorithms. We model such algorithms as a network of interacting dynamical systems and derive tests for convergence based on incremental dissipativity and contraction theory. This approach yields a step-by-step analysis pipeline independent of the network structure, with conditions expressed as linear matrix inequalities. In addition, a numerical comparison with traditional analysis methods is presented, in the context of distributed gradient descent. I Introduction The use of system-theoretic tools for the analysis and design of numerical algorithms has received significant research attention in recent years. As argued in [ 1 ] , the increasing prevalence of such algorithms in engineering systems in fast control loops requires a bridge between the analysis tools used in both domains. A prominent place in this is taken by optimization algorithms in closed-loop control, such as in model predictive control [ 2 ] or online feedback optimization [ 3 , 4 ] . In this paper, we take this system-theoretic view in order to analyse distributed, or interconnected, optimization algorithms. Distributed optimization problems arise in a wide range of scenarios, including multi-agent control [ 5 ] , sensor networks [ 6 ] , and privacy-preserving machine learning [ 7 ] . In all of these, agents aim to optimize a shared global objective, relying solely on local computation while communication is restricted to a given network. For an overview of distributed optimization, see [ 8 ] and the references therein. Indeed, system-theoretic tools have proven useful in analysing distributed optimization schemes. For instance, [ 9 ] discusses how singular perturbation theory can be used for the analysis and design of distributed algorithms. One of the main tools from systems theory used to analyse optimization algorithms is dissipativity theory [ 10 , 11 ] . In particular, [ 12 ] sets out a dissipativity-based approach for the convergence analysis of single optimization algorithms. The core idea there is to decompose such an algorithm into a feedback loop of a linear time-invariant (LTI) system and a static nonlinearity, such as a gradient operator. Monotone operator theory allows us to derive appropriate incremental bounds, called sector bounds , on the latter from common assumptions on the optimization problem. Convergence is then verified by proving that the LTI system is asymptotically stable under any feedback that satisfies the sector bound. That is, convergence analysis reduces to the classical problem of absolute stability [ 13 ] . A parallel approach instead employs integral quadratic constraints [ 14 ] to analyse the closed loop and to synthesise algorithms. Dissipativity theory places the analysis of systems in the context of interaction with the environment. Building on that, in [ 15 ] , it was shown useful in analysing robustness and performance in interconnections of an optimization algorithm with a plant. More generally, by characterising system behaviour in terms of (abstract) energy exchange with the environment, it provides a powerful framework for analysis and design in a networked setting [ 16 , 17 , 18 , 19 , 20 ] . This observation, combined with the successful application of the theory to individual optimization algorithms, motivates a system-theoretic approach to distributed optimization algorithms based on dissipativity theory. To be precise, we propose a system-theoretic framework for the analysis of distributed optimization algorithms through the incremental form of dissipativity theory [ 21 ] . We model a distributed algorithm as a set of local optimization algorithms interconnected over a network. Our aim is to guarantee convergence by proving that the network interconnection is contractive , that is, the distance between pairs of trajectories shrinks over time (see e.g. [ 22 ] ). Contribution Our proposed framework provides a structured and systematic pipeline for analysis. In addition, it does not depend on a priori assumptions on network topology and is suitable for heterogeneous distributed algorithms, where the local algorithms are either entirely different or tuned individually. This framework 1. yields semi-definite programs to verify (exponential) contraction of arbitrary linear interconnections of optimization algorithms, 2. naturally links to monotone operator theory by employing the incremental form of dissipativity, and 3. places distributed optimization algorithms into the broader context of interconnected dynamical systems, allowing us to repurpose system-theoretic tools to analyse algorithms. Notation We use I_{n}\in\mathbb{R}^{n\times n} to denote the identity matrix in dimension n . Dimensions are not written when they are clear from the context. When discussing discrete-time dynamical systems or iterative algorithms, x^{+} and x are to be understood as x(k+1) and x(k) , respectively. The Euclidean norm is written as \mathinner{\!\left\lVert\cdot\right\rVert}_{2} . For symmetric matrices, the symbols \prec ( \preceq ) and \succ ( \succeq ) denote inequality in the (semi-) definite sense and \lambda_{\max}(\cdot) stands for the largest eigenvalue. II Distributed Optimization In this paper, we consider optimization problems of the form \min_{x\in\mathbb{R}^{n}}\quad\sum_{i=1}^{N}f_{i}(x), (1) where each f_{i}\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\to\mathbb{R} is a local cost function that belongs to an agent in a network. In distributed optimization, the goal is to solve this global problem, while performing all computations related to f_{i} , such as evaluations of the gradient \nabla f_{i} , at agent i and restricting communication to a given network. A common approach is to reformulate ( 1 ) as \begin{split}&\min_{x_{1},x_{2},\dots,x_{N}\in\mathbb{R}^{n}}\quad\sum_{i=1}^{N}f_{i}(x_{i})\\ &\textrm{subj. to}\quad x_{1}=x_{2}=\dots=x_{N}.\end{split} (2) Then, ( 2 ) is typically solved by iterative algorithms that combine updates aimed at minimising f_{i} with ones that asymptotically enforce the consensus constraint x_{1}=x_{2}=\dots=x_{N} . That is, the problem is decoupled into local optimization and distributed consensus estimation. An elaborate discussion of this idea from a system-theoretic viewpoint is given in [ 9 ] . Some algorithms have an explicit bilevel structure with a separate consensus mechanism, while others use updates that are linear combinations of optimization and consensus directions, based on communication through a network. Here, we consider the latter class. Examples include distributed gradient descent [ 23 ] and EXTRA [ 24 ] . II-A System-Theoretic Modelling The class of optimization algorithms we consider is inspired by [ 12 , 15 , 14 ] and is introduced next. In line with those works, we consider agents modelled as discrete-time dynamical systems with inputs u_{i} and y_{i} . Adopting the standard notation of u=[u_{1}^{\top}\hskip 5.0ptu_{2}^{\top}\ldots u_{N}^{\top}]^{\top} , and similar for other signals, we model the communication between the agents as a linear relation u=My , where M can be, for example, the Laplacian or adjacency matrix of the communication graph. The autonomous dynamics of the agents, that is, for u=0 , constitute optimization algorithms. To model that, we follow the ideas of [ 12 ] and write the optimization dynamics as a feedback loop between an LTI system and a static nonlinearity. The latter is denoted by \varphi_{i} and referred to as an oracle . It can be, for example, a gradient or a proximal operator. It is shown in [ 12 ] that a wide range of common optimization algorithms, such as ADMM or Nesterov’s accelerated method, can be cast in this form, and a number of case studies

Read the complete text