Computer-aided analysis of decentralized optimization methods
(2024)
Files
thesis_COLLA.pdf
Open Access - Adobe PDF
- 3.61 MB
Details
- Authors
- Supervisors
- Hendrickx, Julien
- Abstract
- This thesis develops and exploits computational techniques for automatically and accurately calculating the worst-case performance of decentralized optimization algorithms. These algorithms aim to minimize the average of local functions that are distributed across a network of computers (called agents), with many applications in machine learning, sensor networks, and power systems. Decentralized optimization algorithms are iterative, with agents alternating between local computations and communication steps. Despite the abundance of decentralized algorithms, accurately analyzing their worst-case performance remains challenging. This analysis is crucial for their effective application, parameter tuning, and comparison. Therefore, we propose a computer-aided methodology based on the Performance Estimation Problem (PEP) approach, which computes the worst-case performance and identifies a worst-case instance of first-order optimization algorithms by solving a semidefinite program. In the first part of this thesis, we extend the PEP framework to decentralized optimization by providing a practical description of communication steps. We also identify conditions where the worst-case performance of a decentralized algorithm is independent of the number of agents, enabling analysis with just two agents. In the second part, we apply our PEP-based techniques to analyze, tune, and compare decentralized algorithms, yielding improvements over existing literature and addressing open questions. We also explore optimal communication weights for given network topologies, revealing that current strategies are suboptimal and can be enhanced.
- Affiliations
UCLouvain SST/ICTM/INMA - Pôle en ingénierie mathématique
Citations
Colla, S. (2024). Computer-aided analysis of decentralized optimization methods. https://hdl.handle.net/2078.5/233135