DECENTRALIZED CONDITIONAL GRADIENT METHOD ON TIME-VARIABLE GRAPHS

R. A. Vedernikov; Ведерников Р. А.; A. V. Rogozin; Рогозин А. В.; A. V. Gasnikov; Гасников А. В.

doi:10.31857/S0132347423060080

DECENTRALIZED CONDITIONAL GRADIENT METHOD ON TIME-VARIABLE GRAPHS

Authors: Vedernikov R.A.¹, Rogozin A.V.¹, Gasnikov A.V.²^,3
Affiliations:
1. Moscow Institute of Physics and Technology
2. Institute for Information Transmission Problems of the RAS (Kharkevich Institute)
3. Caucasian Mathematical Center of the Adyghe State University
Issue: No 6 (2023)
Pages: 27-35
Section: DATA ANALYSIS
URL: https://ruspoj.com/0132-3474/article/view/675727
DOI: https://doi.org/10.31857/S0132347423060080
EDN: https://elibrary.ru/FDENUK
ID: 675727

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription or Fee Access

Abstract

In this paper, we consider a generalization of the decentralized Frank-Wulff algorithm for network time variables, study the convergence properties of the algorithm, and carry out the corresponding numerical experiments. The changing network is modeled as a deterministic or stochastic sequence of graphs.

About the authors

R. A. Vedernikov

Moscow Institute of Physics and Technology

Author for correspondence.
Email: vedernikov.ra@phystech.edu
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9

A. V. Rogozin

Moscow Institute of Physics and Technology

Author for correspondence.
Email: aleksandr.rogozin@phystech.edu
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9

A. V. Gasnikov

Institute for Information Transmission Problems of the RAS (Kharkevich Institute)
; Caucasian Mathematical Center of the Adyghe State University

Author for correspondence.
Email: gasnikov@yandex.ru
Russia, 127051, Moscow, Bolshoi Karetny lane, 19, build. 1; Republic of Adygea, 385016, Maykop, st. Pervomaiskaya, 208

References

Braun G., Carderera A., Combettes C.W. Hassani H., Karbasi A. Mokhtari A., Pokutta S. arXiv (2022) https://arxiv.org/pdf/2211.14103.pdf
Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений. Журнал вычислительной математики и математической физики 6.5. 1966. P. 787–823.
Nedic Angelia. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine 37.3. 2020. P. 92–101.
Forero Pedro A., Alfonso Cano, and Georgios B. Giannakis. Consensus-based distributed linear support vector machines. Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks. 2010.
Gan Lingwen, Ufuk Topcu, and Steven H. Low. Optimal decentralized protocol for electric vehicle charging. IEEE Transactions on Power Systems 28.2. 2012. P. 940–951.
Ram Sundhar Srinivasan, Venugopal V. Veeravalli, and Angelia Nedic. Distributed non-autonomous power control through distributed convex optimization. IEEE INFOCOM 2009. IEEE, 2009.
Ren Wei, and Randal W. Beard. Distributed consensus in multi-vehicle cooperative control. V. 27. № 2. London: Springer London, 2008.
Rogozin A., Gasnikov A., Beznosikov A., Kovalev D. Decentralized convex optimization over time-varying graphs: a survey. arXiv (2022) https://arxiv.org/pdf/2210.09719.pdf
Wai Hoi-To et al. Decentralized FrankвЂ“Wolfe algorithm for convex and nonconvex problems. IEEE Transactions on Automatic Control 62.11. 2017. P. 5522–5537.
Райгородский А.М. Модели случайных графов и их применения. Труды Московского физико-технического института, 2010.