论文标题
去中心化随机变化不平等的最佳算法
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.
