Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities
Authors: Aleksandr Beznosikov
Martin Takáč
Alexander Gasnikov
Venue: NeurIPS 2023 poster (2023)
Keywords: convex optimization
variational inequalities
similarity
local methods
compression
partial participation

Abstract: Variational inequalities are a broad and flexible class of problems that includes minimization, saddle point, and fixed point problems as special cases. Therefore, variational inequalities are used in various applications ranging from equilibrium search to adversarial learning. With the increasing size of data and models, today's instances demand parallel and distributed computing for real-world machine learning problems, most of which can be represented as variational inequalities. Meanwhile, most distributed approaches have a significant bottleneck -- the cost of communications. The three main techniques to reduce the total number of communication rounds and the cost of one such round are the similarity of local functions, compression of transmitted information, and local updates. In this paper, we combine all these approaches. Such a triple synergy did not exist before for variational inequalities and saddle problems, nor even for minimization problems. The methods presented in this paper have the best theoretical guarantees of communication complexity and are significantly ahead of other methods for distributed variational inequalities. The theoretical results are confirmed by adversarial learning experiments on synthetic and real datasets.

Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities
Aleksandr Beznosikov Innopolis University, Skoltech, MIPT, Yandex
Martin Takáč MBZUAI
Alexander Gasnikov MIPT, Skoltech, IITP RAS
Abstract
Variational inequalities are a broad and flexible class of problems that includes minimization, saddle point, and fixed point problems as special cases. Therefore, variational inequalities are used in various applications ranging from equilibrium search adversarial learning. With the increasing size of data and models, to- day's 's instances demand parallel and distributed computing for real-world machine learning problems, most of which can represented as variational inequalities. Meanwhile, most distributed approaches have significant bottleneck the cost of communications. The three main techniques reduce the total number of communication rounds and the cost of one such round are the similarity of lo- cal functions, compression of transmitted information, and local updates. In this paper, we combine all these approaches. Such a triple synergy did not exist be- fore for variational inequalities and saddle problems, nor even for minimization problems. The methods presented in this paper have the best theoretical guaran- tees of communication complexity and are significantly ahead of other methods for distributed variational incqualities. The theoretical results are confirmed by adversarial learning experiments on synthetic and real datasets.
Introduction
Variational Inequalities (VI) have rather long history of research. Their first applications were the equilibrium problems in economics and game theory 772 34 29]. Variational inequalities were seen universal paradigm, involving other attractive problems. including minimization, Saddle Point Problems (SPP), fixed point problems, and others. Whereas research for minimization was actively developed separately, research for saddle point problems was often coupled with science's development around variational inequalities. This trend continues even now. This is partly related to the fact that the methods for minimization problems are not always suitable for SPP and VI. Moreover, from the theoretical point of view, these methods give relatively poor or even zero guarantees of convergence. Therefore a separate branch of algorithms has been developed for VI and SPP. Such Tseng's ' method [84] and many others 14] Over time, VI found new applications, c.g. in signal processing [77]. the last decade, they also attracted the interest of the machine learning community, Nowadays, VI and SPP used in various aspects machine learning. For example, there are many applications for the already classical learning tasks in supervised learning (with non-separable loss [40); with non-separable regularizer (6) unsupervised learning (discriminative clustering [89]; matrix factorization (7]), image denoising
methods include, e.g. Extra Gradient 50 42
28
177, robust optimization [10]. It turns out that VI can be also linked with modern areas of
learning science, including reinforcement learning 73 39
adversarial training [62 and GANs
31 2
30
67
20.
57 74
few.
Machine learning's 's rapid development offers more possibilities for consumers, but poses challenges for engineers. To meet modern society's 's demands, the performance and generalization capacity of the model must be improved. This is currently done by increasing training data and model size [5]
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Hardware acceleration and most importantly distributed algorithm design are essential for effective handling of these workloads [85]. The distributed nature of the prob- lem occurs not only due to a de- sire to speed up the learning pro- cess via parallelization, but be- cause of the severe external con- straints, e.g. as in Federated Learn- ing (FL) 10 56
Table I: Summary of the results on the number of transmitted information in different approaches to communication bottle- neck for distributed VI/SPP.
Method
Approach
Commanication complexily
Extra Gradient KI 3M
o log !
Local SODA
local sleps
0 (1218-211 whftys
FedAvg-8 8
local steps
0 0 log + 345)))
FL is pio- neering area of distributed learning, where users' personal devices are computing machines. Private data transfer from local devices is pro- hibited due to privacy constraints, making distributed approaches the only practical option. Most dis- tributed algorithms have communi- cations as bottleneck. Communi- cation wastes time, slowing down training/optimization and prevent- ing effective parallelization. Differ- ent approaches can reduce commu- nication rounds and cost per round. The first popular approach is the compression of transmitted infor- mation 2 it helps to increase the speed of the communication round without much loss in the quality of learning. The second approach is use of local steps [e];; by increas- ing the number of local computa- tions, it is sometimes possible to significantly reduce the number of communication rounds. Finally, the third basic approach relies on data similarity (7).. Local steps are often employed help with this approach. Data similarity allows us to assume local loss functions on devices are similar, meaning local computations are close and replaceable. Both approaches and combinations have been extensively researched for minimizations, but a synergy of all three pillars of distributed algorithms has not been presented for either minimization problems or VI. Therefore, the purpose of this paper is to answer the following questions:
SCAFFOLD-S 1G
local steps
o [ log
SCAFFOLD Catalyst
10
local steps
0 log"
ESTWOK
sleps
(:: 1og 1 ,36%)
99DD 16
similarity local steps
0[1 + :] lug
MASHA 1
compression
0 vin kog b)
Optin MASHA
similarity compression
o ([+ - ()
similarity local steps
0(1 + :] luns :)
Accelerated Extra Gradient
11
similarity local steps compression
Algorithu I this pager)
o[1
bس.ح 1)
Algaritum 2 this paper)
similarity local steps
o o( vine. loy !)
partial participution
Lower bound hB
a [[++3 loo b)
similarity sleps
a(I++ + _ !)
Lower bound (this paper)
compressiion
Lower bound (this paper)
local steps
similarity
a a(I stos] !os!)
partial participution
lower haund is detemministic and does not take into account the poesibility of compression and partial participation. Notation: Je constant convexity strong concavity
monotonicity the operator (strong corresponding subile point problem). Lipschiiz similarity parameter (typically, 4, I.). hetemggeelity parameter, sumber devices, b local data size, c - precision of the solution.
Is it possible to combine the three main techniques for dealing with the comm. bottleneck into one algorithm? Does the new method have better convergence in both theory and practice?
2 Related works
Recent years have seen a surge of research into effective communication techniques for distributed algorithms. Much of this work focuses on minimization problems, but there are also methods for SPP and VI that address the communication bottleneck issue. We summarize these approaches in Table D Local methods. The use of local steps is probably the most popular approach to the communication bottleneck. Methods with local updates are also widely used in general distributed and FL. The idea of distributed minimization using methods similar to Local SGD is not an achievement of recent years and comes back to 664 65 D.. The development of theoretical analysis and new modifications
for the original methods can be traced in the following works [38] 80, 4d 45 87 86 48). With the
appearance of (99. local methods for distributed minimization problems get a new boost. The first local methods for VI and SPP were simply adaptations of local algorithms for the minimization
problem. In particular, the Local SGD/FedAvg method was adapted in the Scaffold method 45 for SPP. In [II), the Extra Gradient method, a key method for SPP and
25 36) 36) also analysed
VI, was modified by the use of local steps.
Compression. Methods with compression also have good background. Here can highlight

---

the basic methods that add compression to GD or SGD 2 and modifications of this approach using memory [68]. Also of interest are works investigating biased compression operators [S3] and
eroor-copeensation techniques 3 81 [6]. For VI and SPP, methods with different compressions were proposed [15]. These algorithms are based on the variance reduction method. See also [76] and
115
for a more detailed survey of compressed methods for distributed minimization problems.
Similarity. This paper examines the similarity of Hessians in distributed minimization problems, building on established theory and practice (Assumption 4. The first method for distributed
minimization problems with data similarity was DANE 77 The lower bounds on communications under similarity assumption was discussed in 4. The optimal method was obtained in [90] (for quadratic problems) and [51] (for general case). For details and a complete picture of the methods for the distributed minimization problems with similarity, see [51 and B5 The SPP were also considered under similarity assumption. In [166, both the lower bounds and the optimal method were obtained. In the current work, we "break down" these lower estimates by using compression (see Table with footnote 1). Our current study advances these concepts by integrating compression techniques, significantly outperforming previous estimates (see Table IT footnote 1). Most related methods (for the distributed problem with similarity) incorporate local steps.
Local methods with compression. The combination of local updates and compression for mini- mization problems has been presented in [9] 70 (note that the theoretical rates are not optimal and used restrictive assumptions). Using the same local approach as in 69 in papers [3 21 authors combine it with compression technique and get good convergence rates. For VI and SPP, there are no methods with both local steps and compression.
Compression and similarity. Recently, a new class of compressions called permutation compres- sors was introduced for the distributed minimization problem under the data similarity assumption 22) However, due to not using local steps technique, the gain from combining these two approaches was slight. For VI the close results were presented in [2].
3 Our contributions
We answer in the affirmative to the questions posed at the end of Section I In particular, our contributions are as follows.
Three Pillars Algorithm. We present a new method Three Pillars Algorithm (Algorithm D that combines three approaches: compression, similarity, and local steps for the efficient solution of distributed VI and SPP.
The best communication complexity. We analyze the convergence of the new distributed algo- rithm for smooth strongly monotone VI and strongly convex-strongly concave SPP under similarity assumption. As can be seen in Table [ our algorithm has better communication complexity than all available competitors. Since ō < T., it easy see that our algorithms always outperform all methods except Optimistis MASHA [12] One can note that in the worst case with 5 ~ L. we repeat the results of Optimistic MASHA. But if the data are uniformly distributed, then 5 ~ L even 4, where b the size of the local sample. Assume that N bn is the size of the whole data, then our methods outperform Optimistic MASHA when L 8yn, i.c. when N > n² Such a ratio is typical
vb
because already classic modern datasets contain hundreds of thousands [54 53 or even millions 24] of samples, and the number of devices rarely exceeds 100.
Main calculations on server. Many distributed approaches, such as one of the most popular from (661. use the power of all computing devices evenly. But in terms of FL, we prefer to have the main computational workload on the server, rather than on the local devices of the users [16, 51]. Our
algorithm has this feature.
Extension with partial participation. We present a modified version of our first method - Algo- rithm 2 (see Appendix A). Instead of compression, one device is selected to send uncompressed message. This reduces the local complexity on devices compared to Algorithm D while keeping the overall communication complexity the same.
Lower bounds. To demonstrate the optimality of our proposed approaches, we establish lower bounds for the communication complexities These estimates enhance those from [16) which did not consider the potential for compression and partial participation. Our results are shown to be unsurpassable in both scenarios involving compression and partial participation (see Table D
Extension with stochastic local computations. Motivated by applications where computation is expensive, we present a modification of Algorithm | that emphasizes the use of stochastic operators in local computations, termed Algorithm 3l (see Appendix A
Non-monotone analysis. Although we focus primarily on strongly monotone VI, many machine learning problems are non-monneee mon-mont,,ee, and hence we extend the convergence analysis to this case. Our
3

---

algorithm outperforms competitors in terms of communication complexity for both cases and is the first gain acceleration in the non-monotone case.
Experimental confirmation. Experimental results on adversarial training of regression models confirm the theoretical conclusion that both of our algorithms outperform their competitors.
Problem and assumptions
We denote standard inner product of z, E Rd as (x. y) = Ei= Teys, where z; corresponds to the i-th component of x: in the standard basis in Rdd induces fo-n in IRd in the following way ||>|| = / (z, z²). Operator E denotes full mathematical expectation and Eg [ introduces the conditional mathematical expectation on &.
Formally, the problem of finding a solution for the variation inequality can stated as follows:
Find =" E 2 such that (F(="), z =²) 2 0, Vz Z,
(I)
where F: 2 + R is an operator, and 2 S Rd is a convex set. We assume that the training data describing F is distributed across devices/nodes: F(z) = +Σ [=),,, where Pn : 2 IRd for
all & [n] = {1, ....,,............. n). J To emphasize the extensiveness of the formalism L.. we give some examples of variational inequalities.
.
Minimization. Consider the minimization problem:
min f()).
Suppose that F(z) = (=)... Then, f' convex, can be proved that 2 E Z is a solution for (I if and only if 2" E E is a solution for (
Saddle point problem. Consider the saddle point problem:
min= y)-
(3)
Suppose that F F(z) = F(z, y) Then, g is conexe,,nccvee can be proved that 2" E Z is solution for ① if and only if 2 E Z is a solution for (3).
V y). - Vyg(r,
(r, y)] and Z = X x with X' S R , V Rd
Fixed point problem. Consider the fixed point problem:
Find 2² E Rd such that T(=))
(4)
where T' _R + Hd is an operator. With F(z)
-T)),, it can be proved that 2" 2 Rd is solution for [ if and only if F(=*) = 0, i.e. 2 E R is a solution for E
In order to prove convergence results, the following assumptions are introduced on the problem
Assumption 4.1 (Lipschitzness). Each operator F; is L-Lipschitz continuous on Z, i.c. for all u, Z we have (u) F. s L/lu - v/|.
For problems 2 and i L-Lipschitzness of the operator means that the functions f(z) and f(r are L-smooth.
Assumption 4.2 (Strong monotonicity). The operator F is j-stronglyy monotone Z, i.e. for all
u, E 2 we have (F(u) F(v), u v) 2 pl|u - v1/2. Each operator F; is monotone on 2, i.e.
strongly monotone with μ
For problems and 3 strong monotonicity of F means strong convexity of f(z) and strong convexity-strong concavity of f(r,y).
Assumption 4.3 (ó-relatedness in mean). The operators {Fi} is ô-related in mean on Z. It means that for any j operators {F; - F2 is 6-Lipschitz continuous in mean on Z, i.e. for all u, v E Z we
have - [u( (v) (v) [v)) < 521|u-
While Assumptions
and are basic and widely known, Assumption
requires further
remarks. This assumption goes back to the conditions of data similarity (as discussed in Section 2 In more detail, consider distributed minimization (2) and saddle point 3 problems f()
+E=)((()) f(x (
- ">>"/ie y), and assume that for minimization local and global hessians
are 8-similar 79 90
ST i.c. V (z) f(())l < 8, and for SPP, second derivatives differ V fi y)ll & 8, 2 5 (z. v) - 2 fe y) < 8, 1V (1. y) 2 fir, Il < 6. In the worst case 8 ~ L. but often for practical machine learning problems 8 < L.
byd [1 51
V2 f,,
In particular, if we assume that the data is uniformly distributed between devices, can be proven (see Theorem 1.3 from 33 Theorem 2 from (35) that 5 ((LvVb) or even (L/b), where b is the number of local data points on each of the devices.
Let us note some of the terms we use the paper. By local steps/updates, we mean that some device i, using only local information about operator F,, changes the local value of variable z. Local computations//allllatti
includes all computations of F. on local device: local updates/steps may take place, or the value of the operator is accumulated and is sent to the other device without changes

---

Algorithm Three Pillars Algorithm
Parameters: stepsizes ? and т), momentum s, probability p E (0; 1J, number local steps Hi;
Initialization: Choose 20 = m = (x9,8)) E
1: for k = 0, ........ K - do
2: Server takes un = z":
3: for == 0, ....,................... H do
4:
Server computes u/+1/2 projzluž [už ((Fi (ut) Fi(m²) + F(mm) + " [ -² -T(m² - - 5: Server updates whzn = projglui FFF1 - Fi(m²) + F(m*) + (11 T(mm R 1)]]
6:
end for
7:
Server broadcasts u and Fi (u (r) to devices;
8:
Devices in parallel compute Q.(F (m Fi(m²) - - + and send to server; (.( (x
9:
Server updates 2k+1 proj 2 [ +
Qi(R(())))
10:
Server updates m
** with probability m with probubility 1-p,
if m+1 = z then
12:
Server broadcasts #+1 to devices;
13: Devices in parallel compute F.(m²) and send server;
14:
Server computes F(m++1)) - 1mm
15:
end
16:
end for
in local variables z. The local device complexity we mean the number of local computations of F; during the entire operation of algorithms, and by the total local complexity - the total number of computations of F; for all i. A communication round refers to establishing a connection between two devices and transmitting information in one or both directions. When multiple devices communicate in parallel-for instance, all nodes send information to a central device-it is counted as a single compressors, we quantify the transmitted
communication round. Since we employ sparsifiers information by the number of coordinates sent. Communication complexity is the total volume of information exchanged between all devices during the execution of the algorithm. Communication time, on the other hand, is the duration spent on all such communication rounds.
Three pillars algorithm
5.1 The algorithm
We consider centralized communication architecture where the main device is the server (node with number 1, which stores data associated with F1). All other devices can send information to the server and receive responses from it. We follow the standard assumption that forwarding from devices to the server takes considerably longer than broadcasting from the server to the devices (see Section 3.5 from 2 and Section M.3 from (68), hence we consider one-side compression from devices the server. Our approach can be generalized to two-sided compression.
We split the idea of our new method Three Pillars Algorithm (Algorithm) M into five parts. Local problem. The idea of the simplest local method is that the devices make a lot of independent gradient steps, using only their local operators/gradicnt and sometimes averaging the current value of the optimization variables 664 66). With this approach, between communications, the devices minimize their local functions and can move quite far away if the number local steps is large 47 Therefore, the estimates for Local SGDA, FedAvg-S, ESTVGM from Table [ depend on the data heterogeneity parameter. This problem can be solved by modifying original local operators/functions via regularization. For example, a||= 2, 11, where x, is the last point synchronized with all devices [45]. Statistical preconditioning the popular trick for most methods under similarity conditions, also regularization of the local problem 779 -0 It also can be considered as Mírror Descent with special Bregman divergence (see Section 1.1. of (551 for more details). The papers [5T] 16] suggest looking the stochastic
ask to locally minimize not the local f=)), but fz(2)
preconditioning in distributed optimization from different perspective. The authors propose to rewrite the original distributed problem
composite problem of two terms: 1 D
r(x) + ((x) = (=)] E [((x) fi (x)). The proximal method works well for composite problems with proximal-friene friendly functions (e.g, simple &, regularizer) where the calculation of the proximal operator for free, but, in the general case, proximal operator calculated by an
auxiliary method with another iteration loop inside the main algorithm. The key idea in [5] [6
5

---

is to use r(z) = fi( for the proximal operator. This implies the need of additional solving arg min, (fi + 2 =z|l): where 2, some point. Note that no commutation needed to calculate the proximal operator as to solution needs access only to fi and can be solved locally. This reasoning shows that the idea with composite reformulation is also related to the regularization of the local problem. To extend the idea with composite reformulation into VI (see ( for connections between min. prob, and VIs), we use the following proximal operator (see the loop in line B in Alg. D:
Find at E Z such that (G(i²), id)) 2 0, V/z E 2 with G(z)= (== 2²) and vZ = + T(m* )²) Y (F(m*)) Fi (m) where the essence of m² will be explained later. An important issue to be addressed is the selection of the basic method that should be used for an inexact calculation of the proximal operator (we will discuss in the next paragraphs). We also need to underline one more point. Our approach solves the local problem (proximal operator) only on the server that owns F1. It possible to solve different local problems on all devices in parallel as proposed in (79,, but this lead to non-optimal convergence guarantees. The method from (79 was revised in 99 which proposed local steps on one device and improved convergence rates. In 45, an algorithm was constructed that uses local updates on all devices and achieves the same convergence results as in 190 (only in the quadratic case). If no improvement is gained from running local updates on all devices, why should we do it?
Basic outer method. We need a basic method for solving the composite VI. Gradient Descent is one option for minimization problems, but VI and SPP have their own optimal methods. Therefore, the basic outer method for Algorithm| T also needs to be specialized for VI. In [5]] [6. the autors In our work, we selected Tseng's 's method [8 for this task. Local method. Since the subproblem in the inner loop from line 3 in Algorithm is a VI with strongly monotone and Lipschitz continuous operator, then it can be solved using the Extra Gradient method [50). It is optimal for this class of problems.
used Extra Gradi ent [50 7 42
Use of compression. In order to use compression in the method, an additional technique is also we take the idea of basing on the variance reduction technique from ①.. We introduce reference sequence (m*) k20 as in the classical variance reduction method 41. At point m we need to know the full values of operator F. When m² is updated (line L0). we transfer the full operators without compression (lines 12 and 3.. If probability p is small, m is rarely modified and hence condition 17 is satisfied with low probability. It turns out that in Algorithm M att each iteration all nodes send a compressed package and very rarely transmit a full operator. If p is chosen correctly, the effect of this is unnoticeable. But simply introducing
required. Following 775 32 15
additional m sequence is not enough, we also need to add negative momentum: T(m - 2 (lines and 5 This
dictated by the nature of the variance reduction method for VI.
Compression operators. In Algorithm| | reveal the 5-similarity (6 (6-relatedness), we apply the so-called permutation compressors {2]
(lines g 9 any unbiased compressor can be used, but to
Definition 5.1 (Permutation compressors (82). For different cases of n and d, we define
for d 2 nv. Assume that 2 n and d = gm, where q 2 1 is an integer. Let क = (TI, T.)
be a random permutation of {1....,d} d). Then for all u E Rd and each E {1, 2..... n) we define
(w) = n Σx 1)= Uny ','
for d < n. Assume that n 2 d, n > and n = qd, where 2 is an integer. Define the multiset S = (1...., 1,2, ... ,2 ................................ d, ......... d), where each number occurs precisely q times. Let (= n.. be random permutation of S. Then for all Rd and each i E 21,2,..., n) we define Q:(u)= = duz, CT.
In practice, the case of d n is more relevant. Permutation compressors require generating new permutation of numbers from to d each iteration. To ensure the same permutations are generated on all devices, random seed can be defined in each iteration in a predetermined way (e.g. iteration counter). The permutation organizes how compression operators correspond. Take d = 12 and n = 3: a permutation (5. 2, 10, 7, 4, 12, 1, 9, 3, 8, 11, 6) directs the first device send coordinates 5, 2, 10, 7: the second 4, 12, 1, 9; the third 3, 8, 11, 6. This system ensures non--verlappinn data transmission, reducing the data sent per device by factor of n. and avoiding the zeroed "gradient" average that random selection risks. Permutation compressors thus correct redundancy and omission errors. They also capitalize on data similarity, ensuring the "gradient" at the server closely mirrors the true average. The original paper 32) recognized the benefits of this compressor with similar data but didn't 't fully leverage it due to its focus on non-convex settings without local steps.
Summary. We use Tseng's method [84] for the composite VI, inaccurately computing the resolvent
(proximal operator) with the Extra Gradient method [50]. Our convergence analysis is novel for Tseng's 's method and can be regarded as byproduct and secondary contribution. We use a variance

---

reduction technique [1 for Tseng's 's method, remade into a compression technique in distributed settings 7
32 [5]. and choose a special compression for similarity setting
5.2 Convergence
This section presents the convergence results of Algorithm 1 and its analysis.
Theorem 5.2. Let {2 h>20 denote the iterates of Algorithm with compressors from Definition
for solving problem ①. which satisfies Assumptions 4.7 4.2 4.3 Then. if we choose the
stepsizes 7 = (min p. vp H 1),
+( and the momentum T = then we have the
4² L
-00-="1-- convergence guarantee Eill= -1'--==11 S (1 2 -11=0~='1' 11.
In Algorithm D one mandatory communication round with compression occurs (lines 7 and g
and possibly one more (without compression) with probability (lines 12 and 13p. Permutation
compressor compress by a factor of n:; hence each iteration requires O ( p) data transfers from
devices to the server on average: in line 8 we use compression and forward d coordinates from the
devices to the server, in line [ with probability p we transfer the full vector of d coordinates.
If p is close to 1, Theorem 5.2 gives faster convergence, but more data transfer is needed. If p tends to O, the transmitted information complexity per iteration decreases but the iterative convergence rate drops. The optimal choice of p is h. as stated in the corollary.
Corollary 5.3. Under the conditions of Theorem 5.2 the following number of the outer iterations is e) by Algorithm with p n
needed to achieve the accuracy (in terms E 2 z= 11
1.
O[n + 6Y +
L nH log
Next, let us give a brief discussion of the previous estimate.
Communications and local calculations. The iteration of Algorithm D has (1 + p) communication rounds and forwards O (1, + p) information on average. With A, the estimate in equation (5) is valid for both the number of iterations and communication rounds. To get an upper bound for the amount of information transmitted, divide 5 by n. The bound from Corollary 5.3 reflects the local complexity on all devices except the first (the server). To get an estimate for the first device, we need to multiply 5 by H.
Optimal choice of H. It clear from 5 that the number of local H steps can improve the number of communications, but there is a limit beyond which more iterations are not useful. Taking is optimal. If there no data similarity (6 L), then one can choose H 1, and Algo- rithm communication complexity estimate becomes similar to those of MASHA and Optimistin MASHA. Choosing H implies that local updates are meaningless when 5 ~ L. Papers A5 88 on distributed minimization problems show that collecting large batches works just as well as methods that perform many local updates. Our paper considers deterministic methods, so we collect full batches and need local steps only within the presence of data similarity.
H Jv
"Break" lower bounds. H from the previous paragraph yields estimates of Ö(n + 8/n/u) and Ö(1+ 8/ /īp) for the number of communications and transmitted information, respectively. These results are better than any existing methods and even superior to lower bounds for deterministic meth- ods. Note that our method uses randomized compression and hence lower bounds for deterministic methods does not apply for Algorithm (see Table D. To close this gap in Section 5.4 new lower bound estimates that show the optimality of our approach.
we provide
Variable server. In Algorithm [ the server can be reselected deterministically or randomly at each outer iteration. Communication with the server can be decentralized using reduce and gather procedures [8), for this kind of procedures compression also greatly speeds up communication both theoretically and in practice [55] Although the server can change, and decentralized communication networks can be used, it must still receive data from all devices. Asynchronous communication not supported, the lack of communication with the device is also problem for Algorithm [ This is potential problem that could slow down the method. This issue is partially solved by Algorithm in the next section, which assumes communication with only 1 device per iteration.
5.3 Extension with partial participation
We also propose a modification of Algorithm | with partial participation (see Algorithm in Appendix
A). The essence of this method is replace lines 8 of Algorithm [] with the following steps
8:
Generate uniformly i from [n], device in computes F., (uk) and sends to server;
9: Server updates 2++ proj juy + 7- (F.. (m²) Fi(m²) Fi, (u + Fi M)::
The following theorem is valid for Algorithm
7

---

Theorem 5.4. Let {=
J220
120 denote the iterates of Algorithm 2 solving problem T. which Then, if we choose the stepsizes 7 = Ó P. vp I.
satisfies Assumptions
4.1
4.2
4.3
-O((L= + + 1) and the momentum
p then we have the convergence Bill 2n ||²1
(1 7 K 2 -
While in lines and of Algorithm all devices compute the full local operators but forward only
O (()) information, in Algorithm 2 only one local device computes its operator and forwards this
full operator. Hence, the total amount of transmitted information from all devices is equivalent for
Algorithms Tan Therefore the optimal choice of p for Algorithm is the same as for Algorithm
2
Corollary 5.5. Under the conditions of Theorem 5.4 ( +
5ym +
WH log -====*11") outer
L
iterations are needed for the accuracy (in terms of 2 2 12]
S E) by Algorithm 2 with w
Despite the fact that the estimates from Corollary 5.3 and 5.5 are the same. Algorithm 2 is better
than Algorithm i terms of local devices (but not the server) complexity. In line lineBoof of Algorithm J all devices collect full operator, while in Algorithm only one node does it, then local complexity
(not for first node) of Algorithm 2 is n times better. But while Algorithm [ and Algorithm
2 are the
same in terms of the number of transmitted information, Algorithm 2 is n. times worse in terms of
communication time. This is due to the fact that in line Jof Algorithm || all devices in parallel send
information using O (t) units of time, while in Algorithm one node need O (1) units of time.
5.4 Lower bounds
To derive lower bounds, we define a "full package" as the amount of information transmitted in one complete communication round from all devices to the server without compression. We start from the lower bounds for algorithms with partial participation, as in the previous section.
Theorem 5.6. For any d. > O and n E N and K E N. there exists distirbuted variational inequality (satisfying Assumptions 4.2 and 4.3) on Id (where is sufficiently large) with =² + 0. such thut any output 2 of any distributed algorithm with partial participation after sending K full
packages from the devices to the server, it holds that Bl]l= == is M(exp(-16/()
V 16p
+ 1)
K)]L2 22)
The lower bounds confirm that results of the form (1 + ( (Tzu)) are optimal for distributed methods with partial participation; thus, our algorithm achieves this optimality. Lower bounds serve to present a "worst-case" distributed VI where any algorithm with partial participation cannot outperform the established bounds. For a formal classification of distributed algorithms with partial participation, an exemplification of a problematic case, and proofs of the lower bounds, see Appendix C.3] For the methods with compression, we can also show that our result is optimal. But here we have to restrict the class of compression operators and consider only random sparsifiers random choice of coordinates for forwarding (Permutation compressors are suitable). See Appendix C.4. How to obtain lower guarantees for arbitrary compressors remains an open question.
5.5 Extension with stochastic local computations
In this section, we consider stochastic formulation of 1 namely, we assume that each local term from 1 also has the form of finite sum: (2) M (z) Although we can compute F, locally on each ith device, would like to avoid this due to computational cost. The stochastic finite sum setting is common for machine learning and refers to Monte Carlo approach and empirical risk minimization context of similarity. For example, if we initially have a large dataset N = nMb and distribute it to n devices, then each device has Mb samples: F = = Σ F. = - Σ34 Feyl =
[78] Moreover, such setup is more than natural especially in the
1 Ei En Ei F. The nature of similarity goes precisely that F; have the form of a sub-sum taken from a whole large sum. As we noted in Section 4 the larger the sample size Mb for F, the smaller the similarity parameter 5. Now in the stochastic case consider Fú,j and they also have similarity, but with a larger ö, since Mb larger than b. To work with new setting we introduce two assumptions.
Assumption 5.7 (Lipschitzness in mean). Each operator F, is L-Lipschitz continuous in mean on Z. i.e. for all u, E Z we have 37 ΣØ (w) (1)(1)) < iu =112.
8

---

Assumption 5.8. The operators {Fis} is S-related in mean on Z. For any i operators
(Fr. F Figja) } is 5-Lipschitz continuous in mean E, i.e. for all u. Z we have nM? Eiz=1 -,, b1 (u) Pia.a (u) - F (v) + Ja (v)]l 81 - =ll2.
M
The modified version of Algorithm [ for the new setting looks as follows (see the full version in Appendix
Algorithm 3
2: Server takes un = w6 zh:
4: Server computes
1/41/2 proj locu + (1 a)wt ((F((w))) - Fi(m") )+ + F(m*) + (wo -r(m= 1M);
5: Server updates
ut+1 proj lart (1 -a)wt - sn(Fi, (ut+1/2) Ji (uf)) + Fi (((w)) Fi (m²) + F(m*))
+ (u/41/2 zt -T(m" })],, where J. is generated uniformly from [M];
Server updates w { uiyps with probability a:
wi:
with probability 1-9.
7: Server broadcasts / and Fi.st (wf1)) Fi.st (m*) devices, where j is generated uniformly
from [M];
8: Devices in parallel compute Qi( (a (m** - F1.33 (mm)) Fist (u F1.st (wf)) and send to server, where j& is generated uniformly from [M];
9: Server updates
=++1 = zrojzlu + + H Eaf (m²) - P155 (m²* - Fest (u + Fist (u)) )):
To deal with stochasticity we make two modifications in Algorithm D in lines 225 we switch the local algorithm from classical deterministic Extra Gradient stochastic Extra Gradient from I (Algorithm 1), in lines 7 we use stochastic operators for all {FA} instead of deterministic ones.
The next theorem and corollary provides the convergence.
Theorem 5.9. Let }=20 denote the iterates of Algorithm 3 with compressors from Definition 5.1
for solving problem Q. which satisfies Assumptions
4.2
5.7
5.8
Then, if we choose the stepsizes
p. = 1 and the probability q = M then we have the convergence guarantee Eil|=K 2=
Ómin f. 8 VMT, }). O(M-010(((())))
vP H1
", the momentums
119 S (1 7/4 K
2 -| 1|
Corollary 5.10. Under the conditions of Theorem 5.9
O [n + āv= +
/Mi log 2| 11? outer
HH
iterations are needed for the accuracy E (in terms of || 2 1| < E) by Alg
with p
5.6 Non-monotone case
In this section, we abandon the monotonicity assumption, but introduce the following assumption. Assumption 5.11 (Non-monone monnmmonotonicity), The operator F is non-monotone (minty), if and only if there exists 2" E IRd such that for all = E Idd we have (F(=), 2 2²) 2 0.
This assumption is called the minty or variational stability condition. It is not a general non-
monotonicity, but is already associated in the community with non-monotonicity [2 67
37 (26). particularly with the setup, which is somewhat appropriate for GANS 59 60 27
Theorem 5.12. Let {2^ 1420 denote the iterates of Algorithm for solving problem ①I with Then, if we additionally assume that
Z Idd, which satisfies Assumptions 4.1
5.11
4.3
|I*
< Ω and choose the slepsizes 7
17
177) the momentum T = = S
then R 1
5-22
LvE
+ 1) + 1 +1))
By substituting H1 K² (2 +
can obtain that I
F(l S
82 The pk
discussion of the optimal choice of the parameter p. in this case, the same as that following Theorem 5.2 Therefore, the following corollary is true.
Corollary 5.13. Under the conditions of Theorem 5.12 O no" outer iterations is needed to
achieve the accuracy E (in terms of E [=]]]
Se by Algorithm with p -
One can note that the number of information transmitted is n times less than the number of iterations in Corollary 5.13 Therefore, we have the communication complexity is equal O (6² This better than the estimate O (1.20²/e²) of a basic method that does not use local steps, similarity, and compression 333 The problem is that our estimate of communication complexity does not

---

benefit from large n. In the strongly monotone case, however, we observed more pleasant situation (see Table D. Unfortunately, this a standard problem of the non non-monotone case. For example, the methods from 15 with compression have the same complexity O (1,29²/ /s") as the basic method without compression. The methods from the paper [1]] converge only in the special case when all local operators are equal to each other. Other papers from Table not consider the non-monotone case or consider it under other assumptions, then their complexity results are hard to compare with ours. Finally, it turns out that our work is the first to get acceleration in terms of communication complexity in the non-monotone case. On the negative side, we can note that the estimate on the number of local iterations H in Theorem 5.12 is rather strict and grows with the number of iterations K. The results for Algorithm in the non non-monotone case can be obtained in a similar way.
6 Experiments
We conduct experiments on the robust linear regression problem. This problem is defined as milleedd Ia 2N >i (w" +r)) - y1)² + |||]2 - ||rll where w are model weights, {ax, yi J.y is the training dataset and is artificially added noise. We use éz-regularization on both w and r. We consider network with n = 25 devices and two types of datasets: synthetic and real. Synthetic data allows us to control the factor 8, which measures statistical similarity of functions over different nodes. We take local datasets of size
100 and generate the dataset { dt ) at the server randomly, with each entry drawn from the Standard Gaussian distribution. The datasets at other devices (i = ......,', n) are obtained by perturbing { }=}²- with normal noise S, having zero mean and controlled variance. Real datasets are taken from LibSVM library [I9] We uniformly divide the whole dataset between devices. The solution 2n is found using a large number of iterations of Extra Gradient [50 42
method. Algorithms D and are compared with (Extra Gradient [50 Local SGDA [25]. FedAvg- 36 SCAFFOLD-S
methods from Table []
SMMDS [16). MASHA [15] Optimistic MASHA Accelerated Extra Gradient 51 implemented in Python 3.7. All the methods are tuned as in the theory of the corresponding papers. The number of full operator transmissions by one of the arbitrary devices is used as the z-asis. The experiment results are shown in Figure L It is evident that Algorithm [ consistently outperform all other competing algorithms by a significant margin. Furthermore, as the value of 5 decreases, the superiority over Local SGDA, SCAFFOLD-S, MAAFFOD-CCatllstt MASHA, and Optimistic MASHA becomes even more pronounced.
36 SCAFFOLD- SEFFOOLD-Catllss--SS [b), ESTVGM
Sytthet DENEA
sathhik maduma
13-
3:00 SI0E 2018 (d) synthetic, 5 L
specddess
Communtations sperntess
(a) synthetic, small 5 (b) synthetic, medium 5 (c) synthetic, large 5
1207 SOE 190 DIOS STAN LSCO 1060
2:00 201 THE LNGS 12400 1908 17500
CANTARLGEer' specidr
real, a9a
(f) real, w7a
(g) real, w8a
Comparison of state-of-the-art methods for distributed VI. The comparison is made on synthetic datasets with small, medium, and large 8, as well as the real datasets a9a, w7a, w8a from LibSVM. The x-axis denotes the number of full operators transmitted by one of the devices.
Figure 1:
7 Conclusion and future works
We presented two new algorithms for solving distributed VI and SPP: Algorithm [ which combines compression, similarity, and local steps techniques; and Algorithm 2 which uses partial participation instead of compression. Both algorithms have the best communication complexity, outperforming existing methods in theory and practice. For future work we plan to i) derive new methods to stochastic settings (finite-uum or bounded variance setups); ii) obtain lower bounds on communication complexity with compression.
10

---

Acknowledgmentt
This research of A. Beznosikov has been supported by The Analytical Center for the Gov- ernment of the Russian Federation (Agreement No. 70-2021-00143 dd. 01.11.2021, IGK (00000D7700211500000)
References
[1] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. arXiv preprint (rXiv:2102.08332 2021.
[2] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances Neural Information Processing Systems, pages 1709-1720, 2017.
[3] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods, In Advances in Neural Information Processing Systems, 2018.
[4] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimiza- tion. Advances in neural information processing systems, 28, 2015.
[5] Sanjeev Arora, Nadav Cohen, and Elad Hazan. optimization of deep networks: Implicit acceleration by overparameterization. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
[6] Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Optimization with sparsity- inducing penaltics. arXiv preprint arXiv: 108.00/5 2011.
[7] Francis Bach, Julien Mairal, and Jean Ponce. Convex sparse matrix factorizations. arXiv preprint arXiv:0812. 1869, 2008.
[8] Babak Barazandeh, Tianjian Huang, and George Michailidis. decentralized adaptive momentum method for solving a class of min-max optimization problems. Signal Processing, 189: 108245, 2021.
[9] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. esparse-local--ee Distributed sgd with quantization, sparsification and local computations. Advances in Neural Information Processing Systems, 32, 2019.
[10] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust Optimization. Princeton University Press, 2009.
[11] Aleksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova, Valentin Samokhin, Sebastian Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. arXiv preprint orXiv:2106.088 08311, 2021.
[12] Aleksandr Beznosikov and Alexander Gasnikov. Compression and data similarity: Combination of two techniques for cummunication-effiicen solving of distributed variational incqualities. In International Conference on Optimization and Applications, pages 151-162. Springer, 2022.
[13] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002. 12100 2020.
[14] Aleksandr Beznosikov, Boris Polyak, Eduard Gorbunov, Dmitry Kovalev, and Alexander Gasnikov. Smooth monotone stochastic variational inequalities and saddle point problems-survey. arXiv preprint arXiv:2208. 13592, 2022.
[15] Aleksandr Beznosikov, Peter Richtárik, Michael Diskin, Max Ryabinin, and Alexander Gasnikov. Dis- tributed methods with compressed communication for solving variational inequalities, with theoretical guarantees. arXiv preprint 10.03321 2021.
[16] Aleksandr Beznosikov. Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Distributed saddle- point problems under data similarity, Advances in Neural Information Processing Systems, 34:8172-8184. 2021.
[17] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithu for convex problems with applications imaging. Journal of mathematical imaging and vision, 40(1):120 115,,145,5.. 2011.
11

---

[18] Ernie Chan, Marcel Heimlich, Avi Purkayastha, and Robert van de Geijn. Collective communication: theory, practice, and experience. Concurrency and Computation: Practice and Experience, 19(13)17749- 1783, 2007.
[19] Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):127,, 2011.
[20] Tatjana Chavdarova, Gauthier Gidel, Frangois Fleuret, and Simon Lacoste-Julien. Reducing noise in gan training with variance reduced extragradient. arXiv preprint arXiv: 19X.00994400899, 2019.
[21] Laurent Condat, Ivan Agarsky, and Peter Richtárik. Provably doubly accelcrated federated learning: The first theoretically successful combination of local training and compressed communication. arXiv preprint arXiv:2210. 13277, 2022.
[22] Cong D Dang and Guanghui Lan. On the convergence properties of non-Euclidean extragradient meth- ods for variational inequalitics with generalized monotone operators. Computational Optimization and Applications, 60(2):277-310, 2015.
[23] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. optimism. arXiv preprint arXiv:1711.0014/ 2017.
Training gans with
[24] Deng. Wei Dong. Richard Socher, Li-Jia Li, Kai Li, Fei-Fei. Imagenet: large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248- 248-255, 2009.
[25] Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: and communication efficiency. In International Conference Artificial Intelligence and Statistics, pages 1387-1395. PMLR, 2021.
Convergence analysis
[26] Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured nonconvex-nonconee min-max optimization. In International Conference on Artificial Intelligence and Stutistics (AISTATS), pages 3746-2754. PMLR, 2021.
[27] Zehao Dou and Yuanzhi Li. On the one-sided convergence of adam-type algorithms in non-convex non-concave min-max optimization. arXiv preprint arXiv:2 14213, 2021.
[28] Ernie Esser, Xianqun Zhang, and Tony F Chan, general framework for class of first order primal-dual algorithms for convex optimization in imaging science. SIAM Journal on Imaging Sciences, 301) 1046, 2010.
[29] Francisco Facchinci and Jong-Shi Shi Pang. Binte--Dimesiioal Variational Inequalities and Complementarity Problems. Springer Series in Operations Research. Springer, 2003.
[30] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. arXiv preprint arXiv:1802. 2018
[31] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems (NIPS), 2014.
[32] Eduard Gorhunov, Konstantin P. Burlachenko, Zhize Li, and Peter Richtarik. Marina: Faster non-convex distributed learning with compression. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 3788-3798. PMLR, 18-24 Jul 2021.
[33] Eduard Gorbunov, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. Convergence of proximal point and extragradient-based methods beyond monotonicity: the case of negative comonotonicity, 2022.
[34] P. T. Harker and J.-S. Pang. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Mathematical programming. 1990.
[35] Hadrien Hendrikx, Lin Xiao, Sebastien Bubeck, Francis Bach, and Laurent Massoulie. Statistically preconditioned accelerated gradient method for distributed optimization. International Conference on Machine Learning, pages 4203-4227. PMLR, 2020.
[36] Charlie Hou, Kiran K Thekumparampil, Giulia Fanti, and Sewoong Oh. Efficient algorithms for federated saddle point optimization. arXiv preprint arXiv:2102.06333, 2021.
12

---

[37] Yu-Guan Hsieh, Franck lutzeler. Jéröme Malick, and Panayotis Mertikopoulos. Explore aggressively. update conservatively: Stochastic extragradient methods with variable stepsize scaling, Advances in Neural Information Procexsing Systems, 33:16223-16234, 2020.
[38] Alfredo N lusem, Alejandro Jofré, Roberto Imbuzeiro Oliveira, and Philip Thompson. Extragradient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, 27(2):686-725 724, 2017.
[39] Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent. In Proceedings of the 37th International Conference Machine Learning (ICML), volume 119, pages 4890-4900. PMLR, 2020.
[40]
Thorsten Joachims, support vector method for multivariate performance measures, pages 377-384, 01 2005.
[41] Ric Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In C.J. Burges. L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[42] Anatoli Juditsky, Arkadii S. Nemirovskii, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm, 2008
[43] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, ct al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Leurning, 14(1-2):1-20,, 2021.
[44] Aswin Kannan and Uday V Shanbhag. Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74(3):779-820, 2019.
[45] Sai Pranceth Karimireddy, Satyen Kalc, Mehryar Mohri, Sashank Reddi, Schastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5132-5143, PMLR, 13-18 2020.
[46] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data, In International Conference on Artificial Intelligence and Statistics, pages 4519-4529, 2020.
[47] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtarik. Tighter theory for local sgd on identical and heterogeneous data. In Silvia Chiappa and Roberto Calandra, editors, Proceedings the Twenty Third International Conference on Artificial Intelligence and Statisticx, volume 108 Proceedings of Machine Learning Research, pages 4519 4529. PMLR, 26 28 Aug 2020.
[48] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized sgd with changing topology and local updates. arXiv preprint 2:XXi:2003.10422 2020.
[49] Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016.
[50] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. 1976.
[51] Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to distributed optimization under similarity. arXiv preprint arXiv:2205.151.6 2022.
[52] Dmitry Kovalev, Aleksandr Beznosikow, Abdurakhmon Sadiev, Michael Persiianov, Peter Richtarik, and Alexander Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. In S. Kayejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 31073-31088. Curran Associates, Inc., 2022.
[53] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 (canadian institute for advanced rescarch). http::/www. wtw.:ccc.ttooooooo torontorooo.ooooo. featu/"kri/ceee cifar html 2009.
[54] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
13

---

[55] Shigang Li and Torsten Hoefler. Near-optimal sparse allreduce for distributed deep learning. In Proceedings of the 27th ACM SIGPLAN Symposium Principles and Practice of Parallel Programming. pages 135- 149, 2022.
[56] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: challenges, methods. and future directions. IEEE Signal Processing Magazine, 37(3):50-61) 60, 2020.
[57] Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-See Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 907-915. PMLR, 16-18 Apr 2019.
[58] Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. arXiv preprint 1eXivv8808.072111 2018.
[59] Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. arXiv preprint arXiv: 11940, 2019.
[60] Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jerret Ross, Tianbao Yang, and Payel Das. A decentralized parallel algorithm for training generative adversarial nets. In Advances in Neural Information Processing Systems (NeurlPS), 2020.
[61] Weijie Liu, Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil, Zebang Shen, and Nenggan Zheng. A decentralized proximal point-type method for saddle point problems. arXiv preprint arXiv:1910.1 1910.143800 2019.
[62] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018
[63] Grigory Malinovsky, Kai Yi, and Peter Richtárik. Variance reduced proxskip: Algorithm, theory and application to federated learning. arXiv preprint arXiv:2207.04338, 2022.
[64] L. Mangasarian, Parallel gradient distribution unconstrained optimization. SIAM Journal on Control and Optimization, 33(6): 1916 1925, 1995.
[65] Ryan Medonald, Mehryar Mohri. Nathan Silberman, Dan Walker, and Gideon S. Mann. Efficient large- scale distributed training of conditional maximum entropy models. Bengio, D. Schuurmans, J. Lafferty, C. K. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems Curran Associates, Inc., 2009.
22, pages 1231-1238
[66] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effioiii learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[67] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan Sheun Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint 1807,0/ 2018.
[68] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint Netiv:/9//0090 2019.
[69] Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead communication acceleration! finally! International Conference on Machine Learning, pages 15750 15769. PMLR, 2022.
[70] Giorgi Nadiradze, Amirmojtaba Sabour, Peter Davies, Ilia Markov, Shigang Li, and Dan Alistarh. Decen- tralized sgd with asynchronous, local and quantized updates. arXiv preprint arXiv: 1ww.1.111000000 2019.
[71] Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15:229-251. 01 2004.
() for variational inequalities with Lipschitz
[72] J. Von Neumann and O. Morgenstern. Theory of games and economic behavior. Princeton University Press, 1944.
[73] Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P. How, and John Vian. Deep decentral- ized multi task multi agent reinforcement learning under partial observability. In Proceedings of the 34th International Conference Machine Learning (ICML), volume 70, pages 1681-20 1689- PMLR, 2017.
14

---

[74] Wei Peng. Yu-Hong Dai. Hui Zhang, and Lizhi Cheng. Training gans with centripetal acceleration. Optimization Methods and Software, 35(5)9555-97,, 2020.
[75] Xun Qian, Peter Richtarik, and Tong Zhang. Error compensated distributed sgd can be accelerated. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang. and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 30401-30413. Curran Associates, Inc., 2021.
[76] Peter Richtárik, Igor Sokolov, and Nyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. arXiv preprint arXiv:2106. 05203, 2021.
[77] Gesualdo Scutari, Daniel P Palomar, Francisco Facchinei. and Jong-Sh Pang. Convex optimization, game theory, and variational inequality theory. IEEE Signal Processing Magazine, 27(3):35-49 2010.
[78] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algorithms. Cambridge university press, 2014.
[79] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication--ffiiieee distributed optimization using an approximate newton-type method. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1000-1008, Bejing, China, 22 24 Jun 2014, PMLR.
[80] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.0976 2018.
[81] Sebastian U Stich, Jean- Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. arXiv preprint 18KYv08800007550 2018.
[82] Rafal Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:2110.03300, 2021.
[83] Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12:389-334 434, 2012.
[84] Paul Tseng. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):331-446 2000.
[85] Joost Verbracken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer. A survey on distributed machine learning. ACM Computing Surveys, 2019.
[86] Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogeneous distributed learning. arXiv preprint arXi::2006.04:: 04735, 2020.
[87] Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? arXiv preprint 2rX2v:2002.07839, 2020.
[88] Blake E Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srehro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Conference Learning Theory, pages 4336-4437. PMLR, 2021.
[89] Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurmans. Maximum margin clustering. In L.. Saul, Y. Weiss, and L.. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2005.
[90] Xiao- Xiao-Tong Yuan Ping Li. convergence of distributed approximate newton methods: Globalization, sharper bounds and beyond. arXiv preprint /908.0099000222. 2019.
[91] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J. Smola. Parallelized stochastic gradient descent. In J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylee R. S. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems 23, pages 2595-266666 2603. Curran Associates, Inc., 2010.
15


Reviews:
[{"review_id": "wB3lq5eSIh", "reviewer": "Reviewer_D8HM", "summary": "The paper proposes two novel distributed algorithms, for solving variational inequalities and saddle point problems. These algorithms combine three techniques - local updates, compression, and similarity - to address the communication bottleneck in distributed optimization for these problems. Algorithm 1 uses Tseng's method as the outer iteration and Extra Gradient for the local updates. It incorporates a compression technique based on variance reduction and permutation compressors that take advantage of data similarity. Algorithm 2 is an extension that uses partial participation to reduce local complexity.", "questions": "See above for questions.", "limitations": "They have discussed some of the limitations of their work in the paper, but it is more useful if we can have a detail explanation of them at the end.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper provides a thorough convergence analysis of the proposed algorithms under standard assumptions. The analysis derives competitive convergence rates and communication complexities that improve upon state-of-the-art methods. The analysis is also extended to the non-monotone case, demonstrating advantages over competitors. The theoretical work is a significant contribution. Comprehensive experiments on synthetic and real datasets confirm the benefits of the proposed algorithms over other baselines. The experiments show efficacy, especially as the degree of similarity between local functions increases. The results demonstrate both theoretical and practical significance.", "weaknesses": "Some concerns arise for this paper:\n\n- The main concern I have for this paper is that, at each communication round only one client is calculating the gradients and updating the model. Hence, what is the number of communication required for convergence compared to other baselines? This has not been studied in the empirical section either. \n\n- Also, there are other baselines in saddlepoint problems in federated learning, which this paper is missing to compare with, such as [A,B] with communication efficiency approaches.\n\n- The algorithms and analysis are for the deterministic case. While the deterministic case is standard in the literature, the stochastic case may be more representative of machine learning applications. Analysis of the stochastic case would strengthen the work.\n\n\n\n[A]Mohri, Mehryar, Gary Sivek, and Ananda Theertha Suresh. \"Agnostic federated learning.\" International Conference on Machine Learning. PMLR, 2019.\n\n[B]Deng, Yuyang, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. \"Distributionally robust federated averaging.\" Advances in neural information processing systems 33 (2020): 15111-15122.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer __D8HM__ for the time and the work! Next, we will answer the issues raised.\n\nBut before the response, we note that __we added new results to the new version of the paper__ - see our general response! We added __the extension of our algorithms to the stochastic case__ (as requested by Reviewer __D8HM__ in Weaknesses) - see the response to Reviewer __4qia__. Reviewer __JXTW__ requested __lower bounds__. We made them and showed that __our result is optimal and unimprovable!__ We hope that these results will further enhance the paper's contribution!\n\n__W1__(communications): \n\nUnfortunately we don't fully understand the reviewer's concern, but we'll try to answer. Please clarify the question if we misunderstood the issue. \n1) Algorithm 1 operates as follows. First (lines 2-6 of Algorithm 1), the server makes $H$ local iterations using only local information, communication is not needed here. Then (lines 7-8 of Algorithm 1), communication round occurs: the server sends parcels to all devices, and the devices in parallel send replies to the server. Thereafter (lines 9-10 of Algorithm 1), again only the local updates on the server take place (without communications). In lines 11-15 another communication round can also occur, but it happens with a small probability $p$. All of this is detailed in Sections 5.1 and 5.2. Section 5.2 also provides an estimate for the number of communication rounds required to achieve a solution with accuracy $\\varepsilon$  (lines 286-293). Briefly, the number of communication rounds is $\\mathcal{O}\\left(\\frac{\\sqrt{n} \\delta}{\\mu} \\log \\frac{1}{\\varepsilon}\\right)$. Note that this is not the final result, since we compress the information by $n$ times during forwarding, we can assume that the total communication time cost is $n$ times less than number of rounds and is equal to $\\mathcal{O}\\left(\\frac{\\delta}{\\sqrt{n} \\mu} \\log \\frac{1}{\\varepsilon}\\right)$ (see Table 1). And this result on communication costs is optimal (can't be better) (we proved lower bounds - see the general response). \n\n2) For Algorithm 2, we address partial participation. In this setting, only one device send response to the server during a communication round (see lines 8 and 9 in Algorithm 2, Appendix A). In comparison to Algorithm 1 (where compression is used and each device sends only a small portion of full vectoк), in Algorithm 2, only one device sends the whole vector; hence, the total amount of transmitted information is also $n$ times smaller than the number of communications rounds.  For partial participation our result on communication costs is also optimal (we proved lower bounds - see the general response). \n\n3) Note that the estimate on communication rounds (not on communication cost) $\\mathcal{O}\\left(\\frac{\\sqrt{n} \\delta}{\\mu} \\log \\frac{1}{\\varepsilon}\\right)$ is worse than $\\mathcal{O}\\left(\\frac{\\delta}{\\mu} \\log \\frac{1}{\\varepsilon}\\right)$ for the deterministic method (without compression) [16]. At the same time, our  total communication cost $\\mathcal{O}\\left(\\frac{\\delta}{\\sqrt{n} \\mu} \\log \\frac{1}{\\varepsilon}\\right)$ is better than $\\mathcal{O}\\left(\\frac{\\delta}{\\mu} \\log \\frac{1}{\\varepsilon}\\right)$ from [16]. This effect is not due to local steps, but to the use of compression, which introduces stochasticity. It is not the case that by sending significantly less we will not lose in the number of communication rounds, we will lose, but we will gain more in terms of communication cost. That is the goal - to win significantly more than we lose! This is effect is predictable and standard in the literature around compressions - see [R1] (and Table 1 inside) or [R2] (and Table 1 inside). \n\n[R1] Gorbunov, E., Burlachenko, K. P., Li, Z., & Richtárik, P.. MARINA: Faster non-convex distributed learning with compression. In _International Conference on Machine Learning_\n\n[R2] Richtárik, P., Sokolov, I., & Fatkhullin, I.. EF21: A new, simpler, theoretically better, and practically faster error feedback. _Advances in Neural Information Processing Systems_\n\n__W2__(papers):\n\nWe mentioned these papers in the new version of our paper, but they don't seem completely relevant to us. Let us explain with the example of the paper [B]. In this paper, the authors consider a general distributed/federated _minimization_ problem: $\\min_x \\frac{1}{n} \\sum_{i=1}^n f_i(x)$. Then, motivated by robustness issues, the authors rewrite this problem as a special saddle point problem: $\\min_x \\max_{\\lambda} \\frac{1}{n} \\sum_{i=1}^n \\lambda_i f_i(x)$. This is not a general saddle problem, but a narrow formulation. But we consider general distributed saddle: $\\min_x \\max_y \\frac{1}{n} \\sum_{i=1}^n f_i(x, y)$. The same situation with [A].\n\nTo give a clear example of our explanation before let us consider one probably the most famous modern and popular saddle point problem - GAN [R1]. This problem can be formalized as $\\min_x \\max_y f (x, y)$, where $x$ are weights of discreminator, $y$ are weights of generator. If we divide the training data among the devices, the problem becomes distributed: $\\min_x \\max_y \\frac{1}{n} \\sum_{i=1}^n f_i(x, y)$. Can this problem be rewritten as $\\min_x \\max_{\\lambda} \\frac{1}{n} \\sum_{i=1}^n \\lambda_i f_i(x)$. No\n\n[R1] Goodfellow et al. Generative adversarial nets\n\n__W3__(stochastic case):\n\nWe added this (see our general response), hopefully this is what the reviewer wanted."}, {"review_id": "m2ZWYeFyCW", "reviewer": "Reviewer_kubg", "summary": "This paper studies distributed variational inequalities. It combines three techniques – similarity, compression, and local updates – to reduce the total number of communication rounds. It establishes theoretical guarantees of communication complexity. ", "questions": "1 Which step of Algorithm 1 is the initialized $z_i^0$ used?\n\n2 In line 186, it mentions \"using only local information about operator $F_i$, changes the local value of variable $z$.\" In Algorithm 1, it seems that only the server updates $z$, and the device updates occur only in line 8 and line 13. There is no local $z_i$?\n\n3 Line 676, it should be `` Proof of Theorem 5.7’’. \n", "limitations": "Yes. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 It combines three techniques – similarity, compression, and local updates to reduce the total number of communication rounds for distributed variational inequalities. \n\n2 It establishes tight communication complexity. \n", "weaknesses": "The tight bound on communication complexity relies on the assumption of data similarity. However, this assumption is not always valid, such as in the case of highly heterogeneous data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer __kubg__ for the work, time, and positive feedback! Below we will respond to the issues raised.\n\nBut before the response, we note that __we added new results to the new version of the paper - see our general response!__ Reviewer __JXTW__ requested __lower bounds. We made them and showed that our result is optimal and unimprovable!__ Reviewers __D8HM__ and __4qia__ asked to extend the results of the paper to __the stochastic case. This we also added!__ (see the response to Reviewer __4qia__) We hope that these results will further enhance the paper's contribution!\n\n__W__(data similarity):\n\nWe agree that the assumption on data similarity is a bit limiting, yet it is popular in the literature. In the following, we cite papers from top conferences and journals where similarity was investigated [R1-11]. \n\n[R1] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-efficient distributed optimization using an approximate newton-type method - __ICML__\n\n[R2] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization - __NeurIPS__\n\n[R3] Yuchen Zhang and Xiao Lin. Disco: Distributed optimization for self-concordant empirical loss - __ICML__\n\n[R4] Xiao-Tong Yuan and Ping Li. On convergence of distributed approximate newton methods: Globalization, sharper bounds and beyond - __JMLR__\n\n[R5] Hadrien Hendrikx, Lin Xiao, Sebastien Bubeck, Francis Bach, and Laurent Massoulie. Statistically preconditioned accelerated gradient method for distributed optimization - __ICML__\n\n[R6] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning - __ICML__\n\n[R7] Amir Daneshmand, Gesualdo Scutari, Pavel Dvurechensky, and Alexander Gasnikov. Newton method over networks is fast up to the statistical precision - __ICML__\n\n[R8] Ye Tian, Gesualdo Scutari, Tianyu Cao, and Alexander Gasnikov. Acceleration in distributed optimization under similarity - __AISTATS__\n\n[R9] Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Distributed saddle-point problems under data similarity - __NeurIPS__\n\n[R10] Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to distributed optimization under similarity - __NeurIPS__\n\n[R11] Ahmed Khaled, Chi Jin. Faster federated optimization under second-order similarity - __ICLR__\n\n__Q1__:\n\nWe don't need them. Thanks! We removed them.\n\n__Q2__:\n\nIn Section 4 (including line 186) we give general definitions without reference to Algorithm 1. In Section 5, we introduce Algorithm 1 and explain that local updates occur only on 1 device (paragraph \"Local problem\"). $u^k_H$ that comes from the server (line 7 of Algorithm 1) can be considered as $z_i$, but they are updated via communications, not local updates.\n\n__Q3__: \n\nThanks! Fixed!"}, {"review_id": "2iD3MzHleo", "reviewer": "Reviewer_4qia", "summary": "The paper presents a study of distributed algorithms for solving variational inequalities in a centralized distributed optimization setting. The authors propose three improvements: compression, data similarity, and local steps. Compression reduces the communication complexity by transmitting compressed versions of the data, data similarity reduces the variance among workers by sending batches of data that are similar across workers, and local steps reduce the communication rounds by allowing each worker to perform multiple iterations locally before communicating with the central server. The paper's main contribution is achieving the best known theoretical convergence compared to other deterministic algorithms for solving variational inequalities bot for monotone and strongly monotone VI.", "questions": "The paper is clear and well-written, and the proposed algorithm's convergence and complexity are thoroughly analyzed. While I don't have any specific questions, I believe it would be helpful to know how the proposed algorithm performs in other distributed settings and to what extent the synchronization assumptions affect its performance, especially in the case of communication delays or worker failures. Providing insights on these aspects would enhance the applicability of the proposed algorithm and help readers understand its potential limitations.", "limitations": "In addition to the synchronization issue, I believe that a stochastic version of the algorithm would be more appropriate for handling large-scale distributed optimization problems, as mentioned by the authors.\n\nMoreover, the limitations are not sufficiently discussed by the authors.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper's major strength lies in its successful implementation of three known techniques to improve communication complexity in distributed learning, combined in a way that maximizes their effectiveness. The authors pushed these techniques to their limits and studied the best theoretical combination, which is a significant contribution to the field. While the techniques themselves are not novel, the authors' implementation and optimization sets their work apart. Additionally, the paper provides a thorough analysis of the convergence and complexity of the proposed algorithm, which adds to its strength.", "weaknesses": "However, a potential weakness of the paper is the centralized distributed optimization setting considered by the authors. The paper assumes the presence of a central server that synchronizes the work among the different workers, which may not always be feasible in real-life applications. \n\nMoreover, the author should address synchronization issues, such as a worker taking too long to send their result to the server. The paper could benefit from more discussion on the limitations and applicability of the proposed algorithm in different distributed settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer __4qia__ for the work, time, and positive feedback! Below we will respond to the issues raised.\n\nBut before the response, we note that __we added new results to the new version of the paper - see our general response!__  We added __the extension of our algorithms to the stochastic case__ (as requested by Reviewer __4qia__ in _Limitations_) - see the second part of this response. Reviewer __JXTW__ requested __lower bounds__. We made them and showed that __our result is optimal and unimprovable!__ We hope that these results will further enhance the paper's contribution!\n\n__W__ and __Q__(server and synchronization):\n\nThank you! This is really important!\n\nWe think that the answers to these issues have already been partially reflected in the original version of the papers (page 7 lines 307-314). In more detail,\n\n1) _(Server)_  (See lines 307 - 311) The existence of a central server to which all devices are attached is nominal. In fact, all devices can be equivalent and connected in a network, for example, in the form of a ring. We just need to select a nominal server. It is enough for us that at the right moments, all devices send messages to the \"server\", and the server then sends them responses. For this purpose, in decentralized networks we can apply various AllReduce/AllGather/etc procedures. \n\n2) _(Synchronization)_ (See lines 311 - 314) Here we honestly report that our Algorithm 1 does not support asynchronous communications, nor communications delays. And Algorithm 2 is proposed to partially solve this issue because in Algorithm 2, only 1 device communicates each iteration.\n\n__Stochastic case__\n\nConsider the following stochastic setting. Let $f_i$s have the sum type:\n$$\nF_i = \\frac{1}{M} \\sum\\limits_{j=1}^M F_{i, j}.\n$$\nAnd we assume that we can now call not the full operators $F_i$, but only the operators by batches $F_{i,j}$. Such a setup is more than natural especially in the context of similarity. For example, if we initially have a large dataset $N = nMb$ and distribute it to $n$ devices, then each device has $Mb$ samples:\n$$\nF = \\frac{1}{n} \\sum\\limits_{i=1}^n F_i = \\frac{1}{n} \\sum\\limits_{i=1}^n \\left[ \\frac{1}{M} \\sum\\limits_{j=1}^M F_{i,j}\\right] = \\frac{1}{n} \\sum\\limits_{i=1}^n \\left[ \\frac{1}{M} \\sum\\limits_{j=1}^M  \\left(  \\frac{1}{b} \\sum\\limits_{l=1}^b F_{i,j,l}\\right) \\right]\n$$\nThe nature of similarity goes precisely that $F_i$ have the form of a sub-sum (taken from a common large sum). The larger the sample size $Mb$ for $F_i$, the smaller the similarity parameter $\\delta$. Now in the stochastic case we consider $F_{i,j}$ and they also have similarity, but with a larger similarity parameter $\\tilde \\delta$ (since $Mb$ is larger than $b$). In particular, we use\n\n_Assumption 5.9_\nFor all $i_1, i_2 \\in 1,\\ldots n$, $j \\in 1,\\ldots M$ and $u, v \\in Z$\n$$\n\\frac{1}{M} \\sum\\limits_{j_2 =1}^M || F_{i_1,j_1}(u) - F_{i_2, j_2}(u)- F_{i_1,j_1}(v) + F_{i_2, j_2}(v)||^2 \\leq \\tilde \\delta^2 ||u - v||^2\n$$\n\nWe modify Algorithm 1 as follows:\n\n1) Line 7: Server broadcasts $u^k_H$ and $F_{1, j_k^1}(u^k_H) - F_{1, j_k^1}(m^k)$ to devices, where $j_k^1$ is generated uniformly from $[1, \\ldots, M]$\n\n2) Line 8: Devices in parallel compute $Q_i(F_{i, j_k^i}(m^k) - F_{1, j_k^1}(m^k) - F_{i, j_k^i}(u^k_H) + F_{1, j_k^1}(u^k_H))$, where $j_k^i$ is generated uniformly from $[1, \\ldots, M]$.\n\n3) Line 9: according to new line 8\n\nLet us consider how the proof changes in this case:\n\n1) Lines 624-625:\n\n$$\\mathbb{E_j} \\left[\\mathbb{E_Q} \\left[\\frac{1}{n} \\sum \\limits_{i=1}^n Q_i(F_{i, j_k^i}(m^k) - F_{1, j_k^1}(m^k) - F_{i, j_k^i}(u^k_H) + F_{1, j_k^1}(u^k_H))\\right]\\right] = F_{i}(m^k) - F_{1}(m^k) - F_{i}(u^k_H) + F_{1}(u^k_H))$$\n\nHere we use the unbiasedness of permutation compressors and of choices $j$ and their independence from previous points and iterations. As a result, the final result (up line 625) remains unchanged.\n\n2) Lines 634-635:\nHere as a final result we get \n$$\\frac{1}{n} \\sum \\limits_{i=1}^n || F_i (m^k) - F_1 (m^k) - F_i (u^k_H) + F_{1}(u^k_H) ||^2 \\to \\frac{1}{n} \\sum \\limits_{i=1}^n || F_{i, j_k^i}(m^k) - F_{1, j_k^1}(m^k) - F_{i, j_k^i}(u^k_H) + F_{1, j_k^1}(u^k_H)||^2$$\nWe directly use Assumption 5.9 (new, defined here) and get (8) with $\\delta \\to \\tilde \\delta$.\n\nThis means that in Lemma C.1 we have only $\\delta \\to \\tilde \\delta$.\n\nLines 3-6 of Algorithm 1 also need to be adapted. They used deterministic ExtraGradient and now need to be modified for the stochastic case. Algorithm 1 from [1] is suitable for this. In the proof then we need to consider lines 647-651. In particular, the convergence of the deterministic ExtraGradient is used there now. It should be changed to the results of Theorem 4.9 and Corollary 4.10 of [1]. In particular, we have the following changes:\n$$\n\\exp\\left( - \\frac{H}{4 \\left(\\gamma L + 1 \\right)} \\right) \\to \\exp\\left( - \\frac{H }{4 \\sqrt{M} \\left(\\gamma L + 1 \\right)} \\right),\n$$\n$$\n\\gamma = \\mathcal{O}\\left(\\frac{H}{L}\\right)  \\to \\gamma = \\mathcal{O}\\left(\\frac{H}{\\sqrt{M} L}\\right)\n$$\n\nAs a result of all changes, in the analogy of Corollary 5.3, we obtain the following estimate:\n$$\n\\mathcal{O} (  [n + \\frac{\\tilde \\delta \\sqrt{n}}{\\mu} + \\frac{L \\sqrt{M}}{\\mu(H-1)}]\\log \\frac{1}{\\varepsilon})\n$$\nWith $H = 1 + \\frac{L \\sqrt{M}}{\\tilde \\delta \\mu}$, we get\n$$\n\\mathcal{O} (  [n + \\frac{\\tilde \\delta \\sqrt{n}}{\\mu}]\\log \\frac{1}{\\varepsilon})\n$$\nIt turns out that the difference with the deterministic result is in $\\delta$ (now we have $\\tilde \\delta$, which is larger than the original $\\delta$) and in the number of local iterations of $H$.\n\nIn a similar way, we can consider the case where we have stochasticity not of finite sum, but the following: we have access only to $\\nabla_x f_i(x,y,\\xi)$ and $\\nabla_y f_i(x,y,\\xi)$ and assume that $\\mathbb{E}[\\nabla_x f_i(x,y,\\xi)] = \\nabla_x f_i(x,y)$ and $\\mathbb{E}[|| \\nabla_x f_i(x,y,\\xi) - \\nabla_x f_i(x,y) ||^2] \\leq \\sigma^2$ (the same for $y$)."}, {"review_id": "nhMGEUsIDe", "reviewer": "Reviewer_JXTW", "summary": "This paper investigates distributed variational inequalities (VI) problems in the context of a server-workers architecture. It proposes a method that combines three major communication-saving techniques: i) compression, ii) local steps, and iii) data similarity across workers. For strongly monotone VI and strongly-convex strongly-concave saddle point problems (SPP), the proposed method outperforms competing methods in terms of communication complexity. Furthermore, it improves on previous results for non-monotone operators. It also extends the technique to a partial participation setting, in which one random device is selected at each iteration to send an uncompressed parameter while all other devices remain idle.", "questions": "The lower bound mentioned in Table 1 does not consider compression and, in my opinion, appears irrelevant. Could you please provide a lower bound that takes compression into account? This would be valuable in assessing the optimality of the proposed method. I understand that this aspect is currently designated for future research, but I strongly believe that it would be a significant contribution that enhances the paper\n\nCould it be said that permutation compressors are more accurately characterized as a sparsification technique rather than a compression method?\n\nIn the context of this study, communication complexity is defined as the aggregate information transmitted. Specifically, in line 283, it is indicated that an average of $O(p+1/n)$ information is communicated. I would greatly appreciate a precise explanation of the concept of \"information\" within this context. Furthermore, I would appreciate more clarification regarding the division of communication rounds by $n$. Is this division influenced by compression techniques, such as sparsification, where $p$ corresponds to $1/n$?\nI would like to inquire about the validity of setting $H$ to 1 in line 296. In such a scenario, $\\gamma$ would be equal to 0, resulting in an undefined bound. Could you please provide clarification regarding this aspect?\n\nIs the probability $p$ required to be: $0 < p < 1$?\n\nI would appreciate clarification regarding Theorem 5.7, as I find it confusing. How is it possible for $H$ to be of the order $O(K^2)$? Multiplying the communication rounds rate by $H$ seems to result in a computational bound that increases with $K$. Could you please provide further explanation on this matter?\n", "limitations": "No. For example, the studied assumptions are strict and not practical. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "This paper employs three communication-saving techniques (local methods, compression, and similarity) to achieve the best theoretical communication complexity for distributed methods solving strongly-monotone VI problems.", "weaknesses": "- I believe that the writing and organization could be much improved. The paper is not well explained.  There several typos and unclear statements. (line 172, the inner product in assumption 4.2 a semicolon is used instead of comma) (Missing comma in line 174 after i.e.) (initial value of $m^k$ is not specified in Alg 1) (line 10 in alg 1 $z^{k+1}$ instead of $z^k$) (definition of communication complexity is unclear and uncommon) (line 203 ‘we’ is missing an e) (having the main computation on server is not a contribution since there are methods with the same feature)\n\nThe description of the algorithm is too long and not organized well. In page 6, lines 228—229 the author describe a reformulation that I find unclear where it came from. Moreover, in this part, variables $m^k,v^k$ are introduced where $m^k$ is a reference sequence that is only explained after several paragraphs. Similarly for the momentum term.\n\nThe contribution is incremental in my opinion and builds on prior works [12] and [16]. The result is also a minor improvement over [51]. Under strong monotonicity the analysis is not that challenging and follows by using basic techniques from the literature. Moreover, assumption 4.3 is a strong assumption since data heterogeneity is common in practice. This is not worth a NeuRIPS paper on its own.\n\nThe algorithm does not use full compression since it occasionally sends uncompressed vector in uplink (with small probability). Also it does not use compression in the downlink and it is unclear how to do that (even though the authors mention that their method can be generalized to two-sided compression).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer __JXTW__ for the time, work and detailed review of our paper! Next, we will answer the issues raised.\n\nBut before the response, we note that __we added new results to the revised paper__ - see our general response! Reviewer __JXTW__ requested __lower bounds__. We made them and showed that __our result is optimal and unimprovable!__ Reviewers __D8HM__ and __4qia__ asked to extend the results to __the stochastic case. This we also added!__(see the response to Reviewer __4qia__). We hope that these results will further enhance the paper's contribution!\n\n__W1__(writing):\n\nMany thanks for the attentive work with our paper!\n1) We independently proofread and revised the paper and tried to eliminate the problems not only put forward by the reviewers\n2) We added $m^0 =z^0$\n3) line 10 in alg 1 $z^{k+1}$ instead of $z^k$: this is not a typo, we really need $z^k$ (not $z^{k+1}$), we use $z^{k}$ in the proof (lines 638-639), we found it more convenient for proofs. It doesn't make much difference, we can change it to $z^{k+1}$, but then we have to change the proofs a bit\n4) communication complexity: The reviewer further clarifies the issue and asks what we understand by \"transmitted information\". Our response: due to the nature of our compressors (as the reviewer correctly notes we use a sparsifier, which reduces the number of transmitted coordinates), by \"transmitted information\" we mean the number of coordinates transmitted - we added this to line 195 in the revision\n5) We added in the paragraph \"Main calculations on server\" a mention of other works for VIs that also have this property. But we can remove this paragraph at all if it seems irrelevant\n\n__W2__(description): \n\nIn line 224 we give the idea the local problem reguralization. There it is given for the minimization problem $\\min_x [f_1(x)+\\lambda ||x-x_s||^2]$. In Section 4 (lines 160-162) we give that the minimization problem can be written as a variational inequality with $F=\\nabla f$. Then in the case of $f(z)=f_1(z)+\\lambda ||z-z_s||^2$ we can take $F(z)=\\nabla f_1(z)+\\lambda (z-z_s)=F_1(z)+\\lambda (z-z_s)$. This is what we have in line 229. We added a bit more explanation to the revised paper to avoid misunderstandings. We also added that the nature of the $v_k$ point will be defined later in the text\n\n__W3__(contribution):\n\n1) We agree that the assumption on data similarity is a bit limiting, but it is quite popular in the literature. In the response to Reviewer __kubg__ we cite papers from top conferences where similarity was investigated [R1-11]. All these papers consider (strongly) convex/monotone problems\n2) It is a known fact that the non-smooth non-convex problem is NP-hard [R1]. Acceptable theoretical estimates of convergence can be obtained only by introducing assumptions about the problem. At the same time, the same NNs, being non-smooth non-convex, often behave as convex problems in the process of training. Therefore, considering even convex problems can give a boost in terms of understanding optimization methods\n3) No one before this paper has combined all three techniques even for minimization problems. Yes, similarity for SPPs/VIs has been considered before us. Yes, some results (including with compression) have been done before. But the record and (judging by the lower bounds) unimprovable result is obtained here. This paper was able to unite all the past ideas and achieve optimality\n4) As we mentioned, [12,16,51] consider only monotone case, we also consider non-monotone case (Sec. 5.4)\n\n[R1] Kornowski et al. Oracle complexity in nonsmooth nonconvex optimization\n\n__W4__(compression):\n\nYes, these two things are the limitations of our algorithm, the paper doesn't hide it. Note that the setup when only one-side communication is used is really popular and most of the works on compression stop on this setting (see e.g. works from Table 1 from [R1], we also have motivation of it - see lines 202-203). Note also that people write separate papers to a) add two-side compression ([R1] $\\to$ [R2]) or b) remove rare sending of full packages ([R3] $\\to$ [R4]) \n\n[R1] Richtárik et al. EF21: A new, simpler, theoretically better, and practically faster error feedback __NeurIPS__\n\n[R2] Fatkhullin et al. EF21 with bells whistles: Practical algorithmic extensions of modern error feedback\n\n[R3] Gorbunov et al. MARINA: Faster non-convex distributed learning with compression __ICML__\n\n[R4] Tyurin et al. DASHA: Distributed nonconvex optimization with communication compression, optimal oracle complexity __ICLR__\n\n__Q1__(lower bounds):\n\nSee our general reply\n\n__Q2__(compression):\n\nYes, PermK is a sparsifier but the original paper [80] calls it compression. Moreover, in the literature sparsifiers are often considered as a subset of compressors \n\n__Q3__(complexity):\n\nDue to the nature of our compressors, by \"transmitted information\" we mean the number of coordinates transmitted - we added this to line 195 in the revision.  With probability $p$ we send a full vector with $d$ coordinates from the devices to the server.  And if we use PermK compression, we forward $d/n$ coordinates. Then the average number of coordinates from the devices to the server is equal to $dp+d/n=\\mathcal{O}(p+1/n)$. We added this explanation \n\nAbout $H$: it is a typo, we corrected this and wrote $H=\\mathcal{O}(1)$ in lines 296 and 298\n\n__Q4__($p$):\n\nYes, $p\\in (0;1]$. We added this to the text of the revised paper and to Algorithm 1\n\n__Q5__(Th. 5.7):\n\nThe computational complexity can be found as $T=H\\cdot K=O(K^3)$. Also from Th. 5.7 (as in Cor. 5.8), the iterative complexity $K=O(1/\\varepsilon^2)$ can be found. Using this $K$, we can find $T=O(1/\\varepsilon^6)$. \nPerhaps the reviewer would like us to leave the results of Th. 5.7 without choosing $H$. Then in Th. 5.7 we would have $||F(u)||^2= O(1/K+1/\\sqrt{H})$. Using this expression, we can find that $K\\sim O(1/\\varepsilon^2)$ and $H\\sim O(1/\\varepsilon^4)$ and $T=O(1/\\varepsilon^6)$ "}]

Author rebuttal:
Reviewer __JXTW__ requested lower bounds. We made them and showed that our result is optimal and unimprovable. Reviewers __D8HM__ and __4qia__ asked to extend the results of the paper to the stochastic case. This we also added. Because of the character limit, we give sketches of results and proofs. We are ready to provide detailed reasoning on the required facts upon separate request.

__Lower bounds__

We will slightly modify Assumption 4.3. The new version follows from the old one in the original paper.

_Assumption 4.3(new)_
For all $i \in 1,\ldots n$ and $u, v \in Z$
$$
\frac{1}{n} \sum\limits_{j=1}^n || F_i(u) - F_j(u)- F_i(v) + F_j(v)||^2 \leq \delta^2 ||u - v||^2
$$

1) _Upper bounds._ Since we change the Assumption 4.3, we need to show that this does not violate the old proofs.

We use Ass. 4.3 in line 635 (here we exactly need Ass 4.3(new)). We also use in (9) (lines 635-636):
$$
|| F(u) - F_1(u) - F(v) + F_1(v) ||^2 \le \frac{1}{n} \sum_{j=1}^n || F_j(u) - F_1(u) - F_j(v) + F_1(v) ||^2 \le \delta^2 ||u - v||^2
$$
Finally, we use Ass 4.3 in lines 666. Here to use Ass 4.3(new) we need to use that $i_k$ is generated uniformly:
$$
\mathbb{E}[ || F_{i^k}(m^k) - F_1(m^k) - F_{i^k}(u^k) + F_1(u^k) ||^2 ] = \frac{1}{n} \sum_{j=1}^n || F_j(u) - F_1(u) - F_j(v) + F_1(v) ||^2 \le \delta^2 ||u - v||^2
$$
It gives that all current proofs remain correct.

2) _Proof of lower bounds for partial participation._

We will show lower estimates for partial participation (Sec. 5.3), we give idea (by analogy with partial part.) of lower bounds for compression at the end. In this setup, we have a random set of devices that can participate in each communication. The point of obtaining lower bounds is to give a "bad" problem such that any algorithm from some class will perform no better than the lower bound. 

First, we describe the class of algorithms for which we obtain lower bounds. The general idea of definitions can be found in [4, 16], the essence is that each device has its own output, due to local computations this output can be changed, the outputs can also be changed by communications with other devices. The starting output is 0. The final output is the server's output. The only thing that needs to be specified is the communication process (since we consider partial participation):

_At each communication round the server can sample uniformly and independently batch $S$ from [1,\ldots, n-1] of any size $b \in 1\ldots n-1$ and communicate with devices with numbers from $S$. Batch of the size $n-1$ is equal to the communication with all devices._

Next, we move to the "bad" problem. We consider saddle point problem (since it is special case of VIs)
$$
    f(x,y) = \frac{\delta}{4\sqrt{n}} x^T A y + \frac{\mu}{2}||x||^2 - \frac{\mu}{2}||y||^2 +  \frac{\delta^2}{2n\mu} e_1^T y,
$$
with 
$$
A = \left(
\begin{array}{cccccccc}
1&-1 & & & & & &  \\\\
&1 &-1 & & & & &  \\\\
& & & &\ldots &\ldots & & \\\\
& & &   & & &1 &-1 \\\\
& & &  & & & &1 \\\\
\end{array}
\right)
$$
Construct functions $f_{i}$. Let define $a_q$ -$q$th row of the matrix $A$, $e_q$ - $q$th basis vector. We split function $f$ to sum $\frac{1}{n}\sum_{i=1}^n f_i$:
$$
    f_1 (x,y) = \frac{\mu}{2}||x||^2 - \frac{\mu}{2}||y||^2 + \frac{\delta^2}{8n\mu}e_1^T y
$$
for $i \in 2 \ldots n$: 
$$
    f_i (x,y) = \sqrt{n-1} \cdot \frac{\delta}{4} x^T \left[ \sum\limits_{j \equiv (i-1) \text{mod} (n-1)} e_j a_j^T \right]y + \frac{\mu}{2}||x||^2 - \frac{\mu}{2}||y||^2 + \frac{\delta^2}{2n\mu}e_1^T y
$$

_Lemma 1._ $f_i$ satisfies Ass. 4.3(new) with $\delta$; $f_i, f$ satisfies Ass. 4.2 with $\mu$.

_Lemma 2._
After $N$ communications, in expectation only the first $\lfloor \frac{N}{n} \rfloor$ coordinates of the global output can be non-zero while  the rest of the $d-\lfloor \frac{N}{n} \rfloor$ coordinates are strictly equal to zero.

The essence of the lower bounds in this case is classical - how the final output close to the real solution is measured in the number of non-zero coordinates in this output. On non-zero coordinates we can (in the best case) get a number corresponding to the real solution, but on zero coordinates we cannot. The point is that we broke the problem into pieces $f_i$ and without communication we cannot increase the number of non-zero coordinates. Only one $f_i$ can move us to new non-zero coordinate, and this $f_i$ still needs to be sampled in the batches $S$.

Further getting lower bounds is pure algebra. The initial function $f$ coincides with the function for deterministic non-distributed lower bounds from [R1], the number of non-zero coordinates we have already found, so further we can simply use the results of algebraic transformations from Sec. 3.1 and 3.2 of  [R1] and get the lower bounds:

$$
\Omega\left( \sqrt{n} \frac{\delta}{\mu} \log \frac{1}{\varepsilon}\right).
$$

These bounds for the number of communication rounds (not for the cost - since cost $n$ times cheaper) - they are the same as Corollary 5.5 (if $H = \frac{L}{\delta\sqrt{n}} + 1$). It means that our Algorithm 2 is optimal. 

3) _Proof of lower bounds for compression._

The idea here is exactly the same, but we need to restrict the class of compressors to random sparsification operators only (during communication round each device send random coordinates). In this case, all devices communicate, but each device samples the coordinate batch $S_i$ for sending. So we need to wait when the right device $f_i$ in its batch of coordinates $S_i$ find the right coordinate to increase the number of non-zero coordinates in the output.

[R1] Zhang et al. On lower iteration complexity bounds for the saddle point problems.

__Stochastic setup__

We proved the stochastic case of our algorithm in the response to Reviewer __4qia__.

Meta-review: Among the reviewers it is a general consensus that this is a solid paper that should appear in the proceedings.
Decision: Accept (poster)