Timezone: »

Optimal Algorithms for Decentralized Stochastic Variational Inequalities
Dmitry Kovalev · Aleksandr Beznosikov · Abdurakhmon Sadiev · Michael Persiianov · Peter Richtarik · Alexander Gasnikov

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #740

Variational inequalities are a formalism that includes games, minimization, saddle point, and equilibrium problems as special cases. Methods for variational inequalities are therefore universal approaches for many applied tasks, including machine learning problems. This work concentrates on the decentralized setting, which is increasingly important but not well understood. In particular, we consider decentralized stochastic (sum-type) variational inequalities over fixed and time-varying networks. We present lower complexity bounds for both communication and local iterations and construct optimal algorithms that match these lower bounds. Our algorithms are the best among the available literature not only in the decentralized stochastic case, but also in the decentralized deterministic and non-distributed stochastic cases. Experimental results confirm the effectiveness of the presented algorithms.

Author Information

Dmitry Kovalev (UCLouvain)
Aleksandr Beznosikov (Moscow Institute of Physics and Technology)
Abdurakhmon Sadiev (King Abdullah University of Science and Technology)
Michael Persiianov (Moscow Institute of Physics and Technology)
Peter Richtarik (KAUST)
Alexander Gasnikov (Moscow Institute of Physics and Technology)

More from the Same Authors