Optimal Algorithms for Decentralized Stochastic Variational Inequalities
  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.
