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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimal Extragradient-Based Algorithms for Stochastic Variational Inequalities with Separable Structure
We consider the problem of solving stochastic monotone variational inequalities with a separable structure using a stochastic first-order oracle. Building on standard extragradient for variational inequalities we propose…
Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
This paper is a survey of methods for solving smooth (strongly) monotone stochastic variational inequalities. To begin with, we give the deterministic foundation from which the stochastic methods eventually evolved. Then…
SurveyDecentralized Local Stochastic Extra-Gradient for Variational Inequalities
We consider distributed stochastic variational inequalities (VIs) on unbounded domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the c…
Federated LearningAdaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence
We develop new adaptive algorithms for variational inequalities with monotone operators, which capture many problems of interest, notably convex optimization and convex-concave saddle point problems. Our algorithms autom…
Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems
In this work, we conduct the first systematic study of stochastic variational inequality (SVI) and stochastic saddle point (SSP) problems under the constraint of differential privacy (DP). We propose two algorithms: Nois…