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.

翻译：变分不等式是包含博弈、最小化、鞍点和平衡问题等特殊情况的形式化描述。变分不等式的方法因此成为许多应用任务（包括机器学习问题）的通用方法。本文集中于分散设定，这是越来越重要但仍不被很好理解的。特别地，我们考虑在固定和时变网络上进行分散随机（求和型）变分不等式。我们提出了通信和本地迭代的较低复杂度下限，并构建了与这些下限匹配的最优算法。我们的算法不仅在分散随机情况下是最优的，也在分散确定性和非分布式随机情况下是最优的。实验结果证实了所提出算法的有效性。