Back to Search Start Over

Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization

Authors :
Marina Costantini
Nikolaos Liakopoulos
Panayotis Mertikopoulos
Thrasyvoulos Spyropoulos
Eurecom [Sophia Antipolis]
Amazon
Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS)
Inria Grenoble - Rhône-Alpes
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG)
Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )
Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )
Université Grenoble Alpes (UGA)
ANR-11-LABX-0025,PERSYVAL-lab,Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique(2011)
ANR-19-CE48-0018,ALIAS,Apprentissage adaptatif multi-agent(2019)
ANR-19-P3IA-0003,MIAI,MIAI @ Grenoble Alpes(2019)
European Project: 871780,H2020-EU.2.1.1. - INDUSTRIAL LEADERSHIP - Leadership in enabling and industrial technologies - Information and Communication Technologies (ICT),MonB5G(2019)
Source :
CDC 2022-61st IEEE Annual Conference on Decision and Control, CDC 2022-61st IEEE Annual Conference on Decision and Control, Dec 2022, Cancun, Mexico
Publication Year :
2022

Abstract

In decentralized optimization environments, each agent $i$ in a network of $n$ nodes has its own private function $f_i$, and nodes communicate with their neighbors to cooperatively minimize the aggregate objective $\sum_{i=1}^n f_i$. In this setting, synchronizing the nodes' updates incurs significant communication overhead and computational costs, so much of the recent literature has focused on the analysis and design of asynchronous optimization algorithms, where agents activate and communicate at arbitrary times without needing a global synchronization enforcer. However, most works assume that when a node activates, it selects the neighbor to contact based on a fixed probability (e.g., uniformly at random), 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 $f_i$ that covers the class of set-wise CD algorithms -- a class that directly applies to decentralized scenarios, but is not limited to them -- and we show that the proposed set-wise GS rule achieves a speedup factor of up to the maximum degree in the network (which is in the order of $\Theta(n)$ for highly connected graphs). The speedup predicted by our analysis is validated in numerical experiments with synthetic data.<br />Comment: Revised writing, added references

Details

Language :
English
Database :
OpenAIRE
Journal :
CDC 2022-61st IEEE Annual Conference on Decision and Control, CDC 2022-61st IEEE Annual Conference on Decision and Control, Dec 2022, Cancun, Mexico
Accession number :
edsair.doi.dedup.....27483332479c702fe2068a33a8922552