|
SPECIAL ISSUE: ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING TECHNOLOGIES
Min-max optimization over slowly time-varying graphs
N. T. Nguyena, A. Rogozina, D. Meteleva, A. Gasnikovabcd a Moscow Institute of Physics and Technology, Moscow, Russia
b Institute for Information Transportation Problems, Moscow, Russia
c Caucasus Mathematic Center of Adygh State University, Moscow, Russia
d Ivannikov Institute for System Programming of the Russian Academy of Sciences, Research Center for Trusted Artificial Intelligence, Moscow, Russia
Abstract:
Distributed optimization is an important direction of research in modern optimization theory. Its applications include large scale machine learning, distributed signal processing and many others. The paper studies decentralized min-max optimization for saddle point problems. Saddle point problems arise in training adversarial networks and in robust machine learning. The focus of the work is optimization over (slowly) time-varying networks. The topology of the network changes from time to time, and the velocity of changes is limited. We show that, analogically to decentralized optimization, it is sufficient to change only two edges per iteration in order to slow down convergence to the arbitrary time-varying case. At the same time, we investigate several classes of time-varying graphs for which the communication complexity can be reduced.
Keywords:
saddle point problem, decentralized optimization, time-varying graph, extragradient method.
Citation:
N. T. Nguyen, A. Rogozin, D. Metelev, A. Gasnikov, “Min-max optimization over slowly time-varying graphs”, Dokl. RAN. Math. Inf. Proc. Upr., 514:2 (2023), 158–168; Dokl. Math., 108:suppl. 2 (2023), S300–S309
Linking options:
https://www.mathnet.ru/eng/danma461 https://www.mathnet.ru/eng/danma/v514/i2/p158
|
|