Quantized Distributed Nonconvex Optimization Algorithms With Linear Convergence Under the Polyak–Łojasiewicz Condition
- 22 April 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 70 (10) , 6853-6860
Abstract
This article considers distributed optimization for minimizing the average of local nonconvex cost functions, by using local information exchange over undirected communication networks. To reduce the required communication capacity, we introduce an encoder–decoder scheme. By integrating it with distributed gradient tracking and proportional integral algorithms, respectively, we then propose two quantized distributed nonconvex optimization algorithms. Assuming the global cost function satisfies the Polyak–Łojasiewicz condition, which does not require the global cost function to be convex and the global minimizer is not necessarily unique, we show that our proposed algorithms linearly converge to a global optimal point. Moreover, we show that a low data rate is sufficient to guarantee linear convergence when the algorithm parameters are properly chosen. The theoretical results are illustrated by numerical examples.Keywords
Funding Information
- National Natural Science Foundation of China (62133003)
- National Natural Science Foundation of China (61991403)
- National Natural Science Foundation of China (61991400)
- Shanghai Municipal Science and Technology Major (2021SHZDZX0100)
- Knut och Alice Wallenbergs Stiftelse
- Swedish Foundation for Strategic Research
- Vetenskapsrådet
This publication has 41 references indexed in Scilit:
- Distributed quantized mirror descent for strongly convex optimization over time-varying directed graphScience China Information Sciences, 2022
- Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak–Łojasiewicz conditionJournal of Global Optimization, 2022
- Loss landscapes and optimization in over-parameterized non-linear systems and neural networksApplied and Computational Harmonic Analysis, 2022
- Distributed Gradient Tracking Methods with Finite Data RatesJournal of Systems Science and Complexity, 2021
- A survey of distributed optimizationAnnual Reviews in Control, 2019
- Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition2016
- Distributed convex optimization via continuous-time coordination algorithms with discrete-time communicationAutomatica, 2015
- Distributed dual averaging method for multi-agent optimization with quantized communicationSystems & Control Letters, 2012
- Convergence time analysis of quantized gossip consensus on digraphsAutomatica, 2012
- Gossip consensus algorithms via quantized communicationAutomatica, 2010