Distributed Saddle-Point Problems Under Data Similarity
Authors: Aleksandr Beznosikov
Gesualdo Scutari
Alexander Rogozin
Alexander Gasnikov
Venue: NeurIPS 2021 Poster (2021)
Keywords: convex optimization
saddle point problem
distributed optimization
data similarity

Abstract: We study solution methods for (strongly-)convex-(strongly)-concave Saddle-Point Problems (SPPs) over networks of two type--master/workers (thus centralized) architectures  and  mesh (thus decentralized) networks. The local functions at each node are assumed to be \textit{similar}, due to statistical data similarity or otherwise. We establish lower complexity bounds for a fairly general  class of algorithms solving the SPP. We show that   a given suboptimality $\epsilon>0$ is achieved over master/workers networks in $\Omega\big(\Delta\cdot  \delta/\mu\cdot \log (1/\varepsilon)\big)$ rounds of communications, where $\delta>0$ measures the degree of similarity of the local functions, $\mu$ is their strong convexity constant, and $\Delta$ is the diameter of the network. The lower communication complexity bound over mesh networks reads     $\Omega\big(1/{\sqrt{\rho}} \cdot  {\delta}/{\mu}\cdot\log (1/\varepsilon)\big)$, where $\rho$ is the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes.  We then propose algorithms matching the lower bounds over either  types of networks (up to log-factors). We assess the effectiveness of the proposed algorithms on a robust regression  problem.

Distributed Saddle-Point Problems Under Similarity
Aleksandr Beznosikov
Gesualdo Scutari
MIPT, University and Yandex, Russia anbeznosikov@gmail com
Purdue University, USA
Sscutari@purdue.com edu
Alexander Rogozin
Alexander Gasnikov
MIPT and HSE University, Russia aleksandr rogozin@phystech.coomm edu
MIPT, HSE University and ISP RAS! Russia gasnikovdyandex.rg
Abstract
We study solution methods for (strongly-Jconve- jeonvex-(strongyy-coneee Saddle-Point Problems (SPPs) over networks of two type-master/workers (thus centralized) architectures and mesh (thus decentralized) networks. The local functions at each node are assumed to similar, due to statistical data similarity or otherwise. We establish lower complexity bounds for fairly general class of algorithms solving the SPP. We show that given suboptimality >> 0 is achieved over master/workers networks Q A-0 (-0//-llog(/e)) rounds of communications, where 8 > 0 measures the degree of similarity of the local functions, is their strong convexity constant, and À the diameter of the network. The lower communication complexity bound over mesh networks reads (21/ VP 8/μ log(1/E)), where p the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes. We then propose algorithms matching the lower bounds over either types of networks (up to log-factors) We assess the effectiveness of the proposed algorithms on robust regression problem.
Introduction
We study smooth (froogly)oommeee-frrrooyyyoooooo SPPs over network of M agents:
M Σ (m, m=1
min max f(x
= M
#EX yEY
where X, Y C Rdd are convex and compact sets common to all the agents; and fm,(2, y) is the loss function of agent m, known only the agent. Problem (P) has found a wide range of applications, including, game theory [42 10 image deconvolution problems (77) adversarial training 3 12). and statistical learning -eese Sec. for some motivating examples the distributed setting, We are particularly interested in learning problems, where each fm. is the empirical risk that measures the mismatch between the model to be learned and the local dataset owned by agent m.
Since the functions fm can be accessed only locally and routing local data to other agents is infeasible or highly inefficient, solving (P) calls for the design of distributed algorithms that alternate between a local computation procedure at each agent's side, and a round communication among (suitably chosen) neighboring nodes. We address such design considering explicitly two type of computational architectures, namely: (i) master/workers networks-these are centralized systems suitable for parallel computing: for instance, they are the typical computational architecture arising
Moscow Institute of Physics and Technology
1 IIP RAS Research Center Trusted Artificial Intelligence
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

from federated learning applications (e.g., [77), where data are split across multiple workers and computations are performed in parallel, coordinated by the master node(s); and (ii) mesh networks- these are distributed systems with no special topology (modeled just as undirected graphs), which capture scenarios wherein there no hierarchical structure (e.g., master nodes) and each node can communicate only with its intermediate neighbors.
Function similarity: Motivated in particular by machine learning applications, our design and analysis pertain to distributed algorithms for SPPs P where the local functions fm 's are related- quantities such as gradients and the second derivatives matrices of fm. 's differ only by finite quantity 5 > O; we will term such SPPs as 5-related SPPs. For instance. this is the typical situation in the aforementioned distributed empirical risk minimization setting 1244 47]: when data are i.i.d. among machines, the fm 's reflect statistical similarities in the data residing at different nodes, resulting in a 5 = (11 where is the local sample size (Ô hides log-factors and dependence on d).
While SPPs have been extensively studied in the centralized setting (e.g., 110 29
and more recently over mesh networks 23] 27 22 26, 36 4 [. we are not aware of any analysis or (distributed) algorithm that explicitly exploit function similarity to boost communication efficiency-either lower complexity bounds or upper bounds. On the other hand, recent works for sum-utility minimization
18
[
problems over networks (e.g., 38 35
14| 39 20 show that employing some form
of statistical preconditioning in the algorithm design provably reduces communication complexity. Whether these improvements are possible/achievable for d-related SSPs in the form P remains unclear. This paper provides positive answer to the above open problem.
Major contributions: Our major results are summarized next. (a) Lower complexity bounds: Under mild structural assumptions on the algorithmic oracle (satisfied by a variety of methods), establish lower complexity bounds for the d-related SPP (P) with j--strongly-come sereely-oovex--tooneeee -concave, L-smooth twice-diiferentiabble local functions: an é precision on the optimality gap over master/workers system is achieved in Ω ?(A 5/p- log(1/e)) communication steps, where A is the diameter of the network. The lower complexity bound over mesh networks reads 2211v/ 8/n. log)) rounds of communications, where p is the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes. These new lower bounds show more favorable dependence on the optimization parameters (via (4) than that of distributed oracles for SPPs ignoring function similarity (5) (6). whose communication complexity, e.g., over mesh networks reads (11/VP L/ (og(1/e))
The latter provides a pessimistic prediction when 0/p < L/p. This is the typical situation of ill-conditioned problems, such as many learning problems where the regularization parameter that is optimal for test predictive performance is so small that a scaling with L/μ is no longer practical while ō/μ is (see, e.g., 25
(b) Near optimal algorithms: We proposed algorithms for such SPPs over master/workers and mesh networks that match the lower bounds up to logarithmic factors. They are provably faster than existing solution methods for u-strongly convex-strongly
L-smooth SPPs, which do not exploit function similarity.
Preliminary numerical results on distributed robust logistic regression support our theoretical findings.
1.1 Related works
Methods for SPPs ignoring function similarity:
-concave SPPs have been extensively studied in the optimization literature and special instances of (strongly) monotone Variational Inequalities (VI) [10] [6]. Several algorithms are available in the centralized setting, some directly imported from the VI literature; representative examples include: the mirror-proximal algorithm 29 Extragradient method [8] and the scheme in [30] -they are readily implementable on L-smooth loss, all these schemes achieve iteration complexity of (LL/ log 1/2)), which has been shown to
master/workers architectures well. For SPPs with sestronglycooneee-stoooyyyyyy--
be optimal for first-order methods solving such class of SPPs 46 34 Lower bounds and optimal algorithms in the distributed setting for SPPs without similarity have been studied in [5].
Note that none of the above lower (and upper) complexity bounds or (centralized or distributed) algorithmic designs capture function similarity. As a consequence, convergence rates certified in the aforementioned works, when applicable to 5-related SPPs in the form P provide quite pessimistic predictions, in the setting 1 + 8/μ² μ < L/p..
Methods for sum sum-utilite utillity minimization exploiting function similarity: Several works exploited the idea of statistical preconditioning to provably improve communication complexity of solution methods for the minimization of the sum of ò-related, ju-ttroglyy convex and L-smooth functions over mas-
2

---

ter/workers networks. Lower complexity bounds are established in [2], and read O ( log(/// which contrasts with LLVLL/poogl log(/g) achievable by first-order (Nesterov) accelerated methods BII. certifying thus faster rates whenever 8/p. < L/p. Solutions methods exploiting function (for quadratic losses), [47] (for
similarity are mirror proximal-like schemes, and include [38 35 45
self-concordant losses), +4 and [TT] (for composite optimization), with [14] employing acceleration. None of these methods are implementable over mesh networks, because they rely on centralized (master) node. To our knowledge, Network-DANN [20] and SONATA [39] are the only two methods that leverage statistical similarity to enhance convergence of distributed methods over mesh networks;
20 studies strongly convex quadratic losses while 39 considers general objectives, achieving communication complexity of (((1/ vP) 5/P p.
where hides logarithmic factors. None of the methods above however applicable the d-related SPP P
1.2
Notation
Given a positive integer M, we define [M] = , M.. We use (x, == Ei aty; to denote standard inner product of x; y E TR.. It induces lz-norm in Rd in the following way | == / (x. v). We also introduce projz(z) the cigenvalues of any symmetrix matrix A E R in nonincreasing fashion, i.c., Amax A1 (A) 2 ... Z (A) Amin (A), with Amax (-) [resp. Amin (-)] denoting the largest (resp. smallest) eigenvalue.
min |/u z|l the Euclidean projection onto Z. We order
2 Setup and Background
Problem setting: We begin introducing the main assumptions underlying Problem ( and some useful notation.
Let us stack the x- and y-variables in the tuple (z, y): accordingly. define X' y and the vector-functions Fm: F R2d.
(z) ( Va (x, (-
1 Σ Fm(().
and F(2)
M
The following conditions are standard for strongly convex-strongly concave SPPs.
Assumption Given P.. the following hold:
(i) 0 + 2 is a convex set;
(ii) Each fm R2dd - R is twice differentiable (an open containing) 2, with L-Lipschitz gradient: [|Fm (21) Fm S L| - 22l1. for all 21, 22 E 2;
(iii) f(z) is j-strongly comvex-strongly concave on 2, ie.. (F(z1) - F(22), - 22) 2 1ll21 22 for all 21,22 Z;
(iv) Each fm(2) is conver-concave on Z, i.e. O-strongly convev-strongly concave.
We are interested in finding the solution = = =x",, ,y²)
) of Problem (P) under function similarity.
Assumption (6-related fm 's) The local functions are 8-related: for all (z.y) Z.
2 (x 4) v2 f v) <
|V xy fm (x, y) fz, y)ll < 5,
1/ y (I,
/ v)ll <
The interesting case is when 1 + 6/14 < L/p. When the fm 's are empirical loss functions over local data sets of size n, under standard assumptions on data distributions and learning model (e.g..
47 14 ) = ((1/v/)) with high probability (Ō hides log-factors and dependence on d) domsome motivating examples falling in this category discussed in Sec. 2. below. While such examples
3

---

represent important applications, we point out that our (lower and upper) complexity bounds are valid in all scenarios wherein Assumption hholds. not necessarily due to statistical arguments.
Network setting: The communication network is modeled as a fixed, connected, undirected graph, g _ (V,E), where V - {1....,M M) denotes the vertex set set-the set of agents & - {(i.j) i.j E v) represents the of edges the communication links; (i.j) E iff there exists a communication link between agent i and j. We denote by A the diameter of the graph. When it comes to distributed algorithms over mesh networks, we leverage neighbouring communications among adjoining nodes. Communications of d-dimensional vectors will be modeled as a matrix multiplication by matrix W (a.k.a. gossip matrix). The following assumptions on W are standard to establish convergence of distributed algorithms over mesh networks.
The matrix W RMM satisfies the following: (a) It is compliant with G, that is, (i) wa 0, Vi [M]; (ii) wig > 0, if (j.i} E E; and (iii) waj = 0 otherwise; (b) It is symmetric and stochastic, that is, W1 = (and thus also 1 W 1
Assumption
Notice that a direct consequence of Assumption B (along with the fact that G is connected) is that
p - 1 max (W), (W)) < 1,
where p is the cigengap between the first and second largest (magnitude) eigenvalue of W. Roughly speaking, measures how fast the network mixes information (the larger, the faster).
2.1 Motivating examples
Several problems of interest can be cast in the SPP P for which function similarity arises naturally, some are briefly discussed next.
Robust Regression: Consider the robust instance of the linear regression problem in its Lagrangian form:
N Σ (wi +r) y2)² +
2 11w0112 ++=210000
B 2 11r11.
min max
(3)
6
2N
where are the weights of the model, {(x;, 1:) pairs of the training data, and models the noise, and À and are the regularization parameters. Let n be the local sample size (thus = nm).
The typical regularization parameter that is optimal for test predictive performance is X Assuming 3 of the same order of À and invoking function similarity 5 (1/vn) 25 44 yield a condition number of the problem x = O(v m n2) while 0/μ = ((v This implics that first the local sample size n grows. Rate scaling with 8/μ would be instead independent on the local sample size.
( (1/VN).
order methods applied to ( will slowdown
Recent works have demonstrated that deep neural networks are vulnerable to adversarial examples-inputs that are almost indistinguishable from natural data and yet classified incorrectly by the network [40 33. To improve resistance to variety of adversarial inputs, a widely studied approach is leveraging robust optimization and formulate the
Adversarial robustness of neural networks:
training saddle-poin problem [24 32);
> |1wl122 1 1( + 2
B 11r113
min max un
N
where are the weights of the model, {xx, 34 3)) pairs of the training data, is the so-called adversarial noise, which models a perturbation the data, and À and 3 are the regularizers.
Other optimization problems: Other instances of the SPP are the (online) transport or Wasserstein Barycenter (WB) problems, see [15] 9 This representation comes from the dual view of transporta- tion polytope. b) Another example is Lagrangian based optimization problems. For instance, consider the minimization of the sum of loss functions, each one associated to one agent, subject to some (common) constraints. The problem can be equivalently rewritten as a saddle-point problem using Lagrangian multipliers. It is easy to check that if the agents' functions are d-related, then the resulting saddle-point point problem is also

---

3 Lower Complexity Bounds
In this section we establish lower complexity bounds for centralized (i.e., master/workers-baaeee and distributed (gossip-basee -asiip---ddddeee algorithms. We begin introducing the back-box procedure describing the class of algorithms these lower bounds pertain to.
3.1 Optinizattonccommnitttooon oracle
Our procedure models fairly general class of (centralized and distributed) algorithms over graphs, whereby nodes perform local computation and communication tasks. Computations at each node are based on linear operations involving current or past iterates, gradients, and vector products with local Hessians and their inverses, as well as solving local optimization problems involving such quantities. During communications, the nodes can share (compatibly with the graph topology) any of the vectors they have computed up until that time. The black-box procedure can be formally describe as follows.
Definition (Oracle) Each agent m has its own local memories M and My for the and g-variables. respectively-with initialization M = =M = {0}. M and Mm are updated as follows.
Local computation: Between communication rounds, each agent m computes and adds its M and My a finite number of points I, y, each satisfying
or + VV VV.mm(z y) E spanfa' x', Vatm(a',
(V fm""
D)z', (Vanf ,"") ) DVV (allml yy + D) -'d, (Vialm(" (1","") + DV- mm
(V fmy"mm" N') (V Zy Vfm 3/)}
By - VV E spanty/ (v' Vyfm(c''./
(V fmm 3/" D)y' (mm + D)V (V fm of + D) (y , 3²) + D) vyfmm (2',1))
(Vzyllld of') " d' (Vey ))) V vm (x', ,2')}
(4)
for given x' x² E M and , E My some o, 3, 0, x such that and D is some diagonal matrix (such that all the inverse matrices exist).
and 0 + & >
Communication: Based upon communication rounds among neighbouring nodes, M and My are updated according to
M == span
U (LM)EE
Mr
My = span
U My (i,B)E
(5)
Output: The final global output is calculated
M
span U m=1
UM. M
nk span
UUM m=1
M
E
The above oracle captures a gamut of existing centralized and distributed algorithms. For instance. local computations model either inexact local solutions-ed e.g., based on single/multiple steps of gradient or Newton-like updates, which corresponds setting a 0 1 and 3 & 0-or exact solutions of agents' subproblems (via some subroutine algorithm), corresponding to a = 0 = 0 and
33 = & 1. Multiple rounds of computations (resp. communications) can performed between communication rounds (resp. computation tasks). Notice that the proposed oracle builds on (37 2 for minimization problems over networks-the former modeling only gradient updates and the latter considering only centralized optimization (master/workers systems).
5

---

3.2 Lower complexity bounds
We are in the position to state our main results on lower communication complexityTTheone pertains to algorithms over master/workers systems while Theorem D deals with mesh networks.
|
Theorem For any L. p.
and connected graph G with diameter A O, there exist a SPP in the form Py (satisfying Assumption with Z = R (where d is sufficiently large), x² # 0. y & O. and local functions Im being I-smooth, u-strongly-conver were--oooooooocccccee
8-related (Assumption 2 such that any centralized algorithm satisfying Definition D produces the following estimate on the
global outpua 2 (a K ,yx after communication rounds:
K
1
1| 2=1 exp
11y 112
A
6 32
Corollary In the setting of Theorem the number of communication rounds required to obtain e-solution is lower bounded by
1 11
Ω
A
log
(6)
11
Theorem For any L, p. > 0 and p E (0; 11. there exist SPP in the form (satisfying Assump- tion with 2 = R2 (where d is sufficiently large), x² + 0, y" & O, and local functions fm being 8-related (Assumption 2) and gossip matrix W over the connected graph G. satisfying Assumption Band with eigengup p. such that any decentralized algorithm satisfying Definition / and using the gossip matrix W the communication steps 5 produces the following estimate the global output 2 (x y after K communication rounds:
L-smooth,
1|2 - =1112== exp - -K
1 11?
+
20
32p
20
Corollary 2 In the setting of Theorem E-solution is lower bounded by
the number of communication rounds required to obtain
1+ [ log
ly 112
(7)
These lower complexity bounds show expected dependence the optimization parameters and network quantities. Specifically, the number of communications scale proportionally to 8/u-this generalizes existing lower bounds 5 that do not account for such similarity, resulting instead in the more pessimistic dependence on L/ L/p-typically å < L. The network impact is captured by the diameter A of the network for master/workers architectures-A communications steps are required in the worst case to transmit message between two nodes-and the eigengap of the matrix W, when arbitrary graph typologies are consider; 1/ /p can be bounded O('), where T' is the largest hitting time of the Markov chain with probability transition matrix W 13 For instance, for fully connected networks A = 1/VP = while for star networks A = and 1/Vp- VM. For general graphs, 1/ 1/ can be larger than A, see [28] for more details. To certify the tightness of the derived lower bounds, the next section designs algorithms that reach such bounds.
4 Optimal algorithms
4.1 Centralized case (master/workers systems)
Our first optimal algorithm is for SPPs over master/workers architectures more generally networked systems where a spanning tree (with the root as master node) preliminary set; it is formally described in Algorithm|] | We assumed w.l.ogg. that the master node owns function f1.

---

Some insights on the genesis of this method are discussed next.
Consider for a moment the minimization problem min f(x) == 37 Em= fm (2), under Assumption 2. Following [X
we can solve invoking the mirror descent algorithm, which reads
x+ arg min (1x ), + Do(a,
(8)
where Do y) = Φ(x) - d(v) (Voly), x y) is the Bregman divergence, with function Φ(x) = Therefore,
fi (x) + ||ll is shown that we can take stepsize
48
can be rewritten
k+I = arg min [ (1(()) +
1 2 x- x" (VF(t)) -Vf((*))
|
(9)
Noting that in Algorithm 7 (see Appendix B.1), one infers the connection between and the updates in lines 3 (i) and 3 (ii). The extra step in line 3 (iii) is due to the fact that Algorithm 1 solves SPP (and not classical minimization as postulated above): gradient descent- methods as (8) are not optimal for SPPs; in fact, they might diverge when applied to general convex-concave SPPs. Out approach is then to employ Forward- Backdwar warrd-oowrrdddd algorithms 18
the Extragradient
method, which leads to the step in line 3 (iii).
Another interpretation of the proposed algorithm comes from looking at Problem (P) composite minimization problem, with objective function hy (z, y) + h2(2, y). with h1 (z, y) = fa 3) and (22 v) मे. Em=1< ( (2,,3) y) f1 [1 (x,,))) v)). The first function hı is L-smooth and convex-concave while h2 is b-smooth and, in general, non-convex-non non-concave. Such type of problems can be solved invoking sliding techniques [1 36
Algorithm (Star Min-Max Data Similarity Algorithm)
Parameters: stepsize 7, accuracy
Initialization: Choose 2d (x", ,y²) E 2, =m 2", for all m [M];
1: for = 0, 1,,,2...dl do
2: Each worker computes Fm (2* and sends it to the master;
3: The master node:
(i) computes v = 2t - (F((t)) ( (2*);;
finds w², s.t. I|ue - 2 S e, where at is the solution of:
min max 751 (un, uy) + bllus w/11 - 1 Ex U,E
2 | - =113
(10)
(iii) updates *+1 projz [ut + (F(=)) Fi(**) - F(ut) Fi (u++t) and broadcasts
s+1 to the workers
4: end for
It is not difficult to check that Algorithm 1 is an instance of the oracle introduced in Definition I accommodates either exact solutions of the strongly convex subproblems (10) (corresponding to = 0) or inexact ones (up to tolerance e > O)ethe latter can be computed, e.g., using Extragradient method [6]. which optimal this case.
The communication complexity of the method is proved in the next theorem, which certifies that the proposed algorithm optimal, i.e., achieves the lower bound (6) on the number of required communications-ww refer to Appendix (. the supplementary material for detailed description of the algorithmic tuning as well as a study of the computational complexity when Extragradient method is employed to solve subproblems 10
(up to a suitably chosen tolerance).
7 over a connected graph G with a master node. Let {2t} be the sequence generated by Algorithm with luning described in Appendix B. (cf. the supplementary material). Then, given e > 0, the number of communication rounds for
Theorem Consider Problem under Assumptions
112 - 2² < is ((11 + 8/pb log(1/s)).
7

---

4.2 Distributed case (mesh networks)
We consider now mesh networks. Because of the lack of a master node, each agent m now owns local estimates um and Um of the common variables and v, respectively, which are iteratively updated. At each iteration, a node is selected uniformly at random, which plays the role of the master node, performing thus the update of its own local variables, followed by some rounds of communications via accelerated (inexact) gossip protocols [21 4 the latter being instrumental to propagate the updates of the u. e-variables and gradients across the network. The algorithm is formally introduced in Algorithm 2 with the accelerated gossip procedure described in Algorithm S
Algorithm 2 (Distributed Min-Max Data Similarity Algorithm)
Parameters: stepsize 7, accuracy e, co, E1, communication rounds Ho. H1; Initialization: Choose 20 (x") v²) E Z, 2n 2.. for all m [M];
1: for k ==00 0, 1,2,... do
2: Communication ...... & = AccGossip F1 (= FM (= Ho):
3: Local computations: Choose an index my [M] uniformly random; then node ma
(i) computes U/ = 2 -7- (Fit me Fm ( ));
iii finds Umn s.t. ||ū um 112 Se where un, is the solution of:
1
min max u. EyEY Jmm (Miz Uyy) + ||uz
2 1
yymme 113
(11)
2
4: Communications: Run accelerated gossip to propagate utt and update gradient variables:
2 . u M AccGossip(O........ ..., ū O.... H1),
F Fk+1/2 ..... #k+1/2 AccGossip(Fi (F FM (ufx)):: Ho):
5: Update of 3m variable: node my performs
sk+1 mm
i + y (F Fm (= Fk+1/2 F Fi (ū });
6: Communications: Run accelerated gossip to propagate gk+1. mma
0. ..... 00 H2); gk+1 M AAcCoosssppO..... ..... 0, mm
M
7: Each worker update A+1 projz [#/t]]]
8: end for
Algorithm 3 (AceGossip)
Input: $1...., ..., 2M Rdd, and H > 0 (communication rounds); Initialization: Construct matrix with rows of' ...., , Set
(-3
1: for 0, 1, --1 Z, do 2: z++1= = (1 7) 2t_ Z
z Z, and n 1+
3: end for
Output: Rows of #
Convergence of the method is established in Theorem g below-we refer to Appendix B.2 in the supplementary material for detailed description of the algorithmic tuning [choice of the stepsize 7, precision e, numbers of communications rounds Hn, H1, and algorithm to solve (10)].
Theorem 4 Consider Problem under Assumptions {(> ( be the sequence generated by Algorithm with tuning as described in Appendix
over connected graph G. Let B.2
(cf. the supplementary material) and gossip matrix W satisfying Assumption 3 Then, given
8

---

the number of communication rounds for || - 201 - reads O (1/Vp- (1 5/1) log² 1), where
zh 1 "m
While the algorithm achieves the lower bound 7. up log-factors (which now however depends on E as well), there is room for improvements. In fact, selecting only one agent at time performing the updates does not fully exploit the potential computational speedup offered by the networking setting. Also, the use of gossip protocols to propagate the updates of a single agent across the entire network seems be not quite efficient. Designing alternative distributed algorithms overcoming these limitation is a challenging open problem.
Numerical Results
We simulate the Robust Linear Regression problem which is defined
1 2N
A (w" (1; +r) -1:² + 2 110 8 2 |r|
min max IIIER
(12)
==1
where w are the model weights, { y4 y is the training dataset, and r is the artificially added noise; use fg-regularization
both and We solve the problem consider a network with 25 workers. We test Algorithm wherein the subproblems (10 at the master node solved with high accuracy using Extragradient method. A description of the tuning of the algorithm parameters can found in Appendix C
master/workers topology;
The algorithms are implemented in Python 3.7 3.7
noise 0.001
noise 0.1
noice 10.0
Alg. with different nolse
D60
000
EGO
nclee 20ae-0.00 01
reae-03
10
10
10.00000.0
10-4
10-0
12*
10-11
10-13
500
1000
communicattonn 1937
500 communications
1000
communications
communications
Figure 1: Centralized case, simulated data, 25 workers, ambient dimension = 40
d graph, 25 nodes
star graph, 25 nodes
10"5
etst to COnSIRT GHUS
Mangne www
diz. to
003
Inbeedd 5001-0.2
rolee3
Fcben
02
65
33
0.2
20
20
cummunizations
communica ores
communical
commranit lorn
Figure Decentralized case, Alg. 2 with different noise
Our first experiment synthetic data, which allows to control the factor 6, measuring statistical similarity of functions over different nodes. Specifically, we assume all local datasets of size = 100. The data set {2,, de 1r at the master node is generated randomly, with each entry of ā; and ÿt, 1...., drawn from the Standard Gaussian distribution. The datasets the workers' sides, 2,..., M,, are obtained perturbing {ār, de 1n by random noise & with controlled variance.
A1. neaes rodio modes
communications
SSource code: hutp://gthhbboommlleeegoozz/zzz
Figure 3: Centralized case, a9a dataset

---

Figure I compares the performance of Algorithm| and the Centralized Extragradient method [S] applied Problem (12), under different level of noise added local datasets (level of similarity), and two different problem and network dimensions we plot the distance of the iterates from the solution versus the number of communications, can be seen that Algorithm [ consistently outperforms the Extragradient method in terms of number of communications- the smaller the noise (the more similar the local functions are), the larger the gap between the two algorithm (in favor of Algorithm D. On the other hand, at high noise (amplitude 10.0) the performance of Extragradient and Algorithm D become comparable. In addition, we compare the performance Alg.2 under different noise over networks with different topologies in Figure
with different number of nodes
4 nodes. 8/L 4.7
25 nodes. 61L 1155=1550 115
100 nodes. 8/L 7.7 2.7
37"
10
30
3371
20"1
20"
10"1
30
122521
E50
307
12256T
133
10
:CB-CT
000
10"1
14 nodex
100 scdes
communicatiins
163
communnications
communnications
communications
Figure 4: Decentralized case, a9a dataset, grid graph
Our second experiment is using real data, specifically LIBSVM datasets [ In this scenario, do not use additional noise, but still can control the data similarity by choosing the number of workers. The larger the number of workers, the less similar the local functions (less data each node). Figure compares Algorithm| D and the Extragradient method: we plot the distance of the iterates from the solution the number of communications, Quite interesting, Algorithm I compares favorably when the number of workers becomes large. Figure + compares Algorithm 2 with Decentralized Extragradient method (EGD) [ and Extragradient method with gradient-tracking (EGD-GT) [27]. The simulations are carried out with parameters tuned according to the theoretical results in the corresponding papers.
6 Conclusion
We studied distristributed SPPs over networks, under data similarity. Such problems arise naturally from many applications, including machine learning and signal processing. We first derived lower complexity bounds for such problems for solution methods implementable either on star-networks or on general topologies (modeled as undirected, static graphs). These algorithms are optimal, in the sense that they achieve the lower bounds, up to log factors. The implementation of the proposed method over general network, however, is improvable: by selecting only one agent at time performing the updates, it does not fully exploit the potential computational speedup offered by the parallelism of the networking setting. Also, the use of gossip protocols to propagate the updates of a single agent across the entire network is not very efficient. Another interesting extension would be designing methods that take into account the asymmetry of the function f with respect to the variables x and y (for example, various strong-convexity constants μt, and (yy). Finally, it would be interesting to combine the proposed methods with stochastic/variance reduction techniques to alleviate the cost of local gradient computations.
Acknowledgments and Disclosure of Funding
The research of A. Rogozin was supported by Russian Science Foundation (project No. 21-71-30005). The work of G. Scutari is supported by the Office of Naval Research, under the Grant N00014- 21-1-2673. The paper was prepared within the framework of the HSE University Basic Research Program.
10

---

References
[1] S.S. Abadeh, P.M. Esfahani, and D. Kuhn. Distributionally robust logistic regression. In Advances in Neural Information Processing Systems (NeurIPS)), pages 1576-1584, 2015.
[2] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimiza- tion. Proc. of the 28th International Conference on Neural Information Processing Systems (NIPS), volume 1, pages 1756-1764, December 2015.
[3] M. Arjovsky, S. Chintala, and L. Bottou, Wasserstein generative adversarial networks. Proceedings of the 34th International Conference on Machine Learning (ICML), 70(1):214-233, 2017.
[4] Aleksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova, Valentin Samokhin, Sebastian Stich, and Alexander Gasmikov. Decentralized local stochastic extra-gradient for variational inequalities. arXiv preprint 2 08315, 2021.
[5] Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle-point problems: Lower bounds, optimal algorithms and federated gans. arXiv preprint arXiv:2010.1311 2021.
[6] Aleksandr Beznosikov, Vadim Sushko, Abdurakhmon Sadiev, and Alexander Gasnikov. Decentralized personalized federated min-max problems. arXiv preprint wrXiv:2106.07289 2021.
[7] Antonin Chambolle and Thomas Pock. A first-order primal- dual algorithm for convex problems with applications imaging. Journal of mathematical imaging and vision, 40(1):120-144 2011.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2 2011.
[9] Darina Dvinskikh and Daniil Tiapkin. Improved complexity bounds in wasserstein barycenter problem. In International Conference on Artificial Intelligence and Statistics, pages 1738-1746. PMLR, 2021.
[10] F. Facchinei and J.S. Pang. Finite Dinee--Dimnsion Variational Inequalities and Complementarity Problems. Springer Series Operations Research and Financial Engineering. Springer New York, 2007.
[11] Jianqing Fan. Yongyi Guo, and Kaizheng Wang. Communication efficient accurate statistical estimation. arXiv:1906.044 048700 2019.
[12] Goodfellow, Pouget-Abadie, M. Mirza, Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems (NeurlPS)), pages 2672 2680, 2014.
[13] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamessing adversarial examples. arXiv preprint 1412.6:412.6572 2014.
[14] Hadrien Hendrikx, Lin Xiao, Sebastien Bubeck, Francis Bach, and Laurent Massoulie. Statistically preconditioned accelerated gradient method for distributed optimization. In Proc. the 37th International Conference on Machine Learning, volume 119, pages 4203-4227, 13-18 Jul 2020.
[15] Arun Jambulapati. Aaron Sidford, and Kevin Tian. A direct tilde (O)(pssilo))) iteration parallel algorithm for optimal transport. Advances Neural Information Processing Systems, 12:11 11370, 2019.
[16] Anatoli Juditsky, Arkadii S. Nemirovskii, and Claire Tauvel. Solving variational inequalities with stochastic mirror-pro, algorithm. 2008
[17] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjum Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint 1912:4991,, 2019.
[18] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. 1976.
[19] Guanghui Lan. Gradient sliding composite optimization. Mathematical Programming, 159(1):201-235. 2016.
[20] Boyue Li, Shicong Cen, Yuxin Chen, and Yuejie Chi. Communication-cffcccen distributed optimization in networks with gradient tracking and variance reduction. Journal of Machine Learning Research, 21(180):1-51, Sept. 2020.
[21] Ji Liu and A Stephen Morse. Accelerated linear iterations for distributed averaging. Annual Reviews in Control, 35(2):160-16 -65, 2011.

---

[22] Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jerret Ross, Tianbao Yang, and Payel Das. A decentralized parallel algorithm for training generative adversarial nets. arXiv preprint arXiv:1910.1222 12999. 2019.
[23] Weijie Liu, Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil, Zebang Shen, and Nenggan Zheng. decentralized proximal point-type method for saddle point problems. arXiv preprint arXiv: 19/0. 14380, 2019.
[24] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:/706, 700::00066,,0,, 2017.
[25] Ulysse Marteau-Feree Ferey, Francis Bach, and Alessandro Rudi. Globally convergent newton methods for ill-conditioned generalized self-concordant losses. In Advances in Neural Information Processing Systems, pages 7636-7646, 2019.
[26] David Mateos- and Jorge Cortés. Distributed subgradient methods for saddle-point problems. In 2015 54th IEEE Conference on Decision and Control (CDC), pages 5462-5467, 2015.
[27] Soham Mukherjee and Mrityunjoy Chakrahorty. A decentralized algorithm for large scale min-max prohlems. In 2020 59th IEFE Conference on Decision and Control (CDC), pages 2967-2972, 2020.
[28] A. Nedić, A. Olshevsky, and M. G. Rabbat. Network topology and communcaaioon-compuaaiio tradeoff's in decentralized optimization. Proceedings of the IEEE, 106:953-9999 976, 2018
[29] Arkadi Nemirovski. Prox-method with rate of convergence of o(I/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15:229-251, 01 2004.
[30] Yuri Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming. 109(1-2)311-334, 2007.
[31] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018
[32] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min- max games using iterative first order methods. arXiv preprint arXiv:1902.08253 002909297 2019.
[33] A. Olshevsky. Linear time average consensus on fixed graphs. In 3rd IFAC Workshop Distrib, Estimation Control Netw. Syst. 2015.
[34] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Progrumming, pages 1-35, 2019.
[35] Sashank J Reddi, Jakub Konečný, Peter Richtárik. Barnabás Póczós, and Alex Smola. Aide: Fast and communication efficient distributed optimization. arXiv preprint arXiv:1608.06877 2016.
[36] Alexander Rogozin, Alexander Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurcchensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. arXiv preprint arXiv:2102.07753 2021.
[37] Kevin Scaman, Francis Bach, Séhasticn Bubeck, Yin Tat Lee, and Laurent Massoulié, Optimal algorithms for smooth and strongly convex distributed optimization in networks. arXiv preprint arXiv: I 1702088744 2017.
[38] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication efficient distributed optimization using an approximate newton-type method. In Proc. of the 31 International Conference Machine Learning (PMLR), volume 32, pages 1000-1008, 2014.
[39] Y Sun, Daneshmand, and Scutari. Distributed optimization based on gradient-tracking revisited: Enhancing convergence rate via surrogation. arXiv preprint (.Ki:0990.00633 2019.
[40] Christian Szegedy, Wajeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and
Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.6199, 2013.
[41] Paul Tseng. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431444 2000.
[42] J. von Neumann, O. Morgenstern, and H. W. Kuhn. Theory of Games and Economic Behavior (commemo- rative edition). Princeton University Press, 2007.
12

---

[43] Shusen Wang, Farbod Koosta-Khorasse Peng Xu, and Michael W. Mahoney. Giant: Globally improved ap- proximate newton method for distributed optimization. In Proc. of the 32nd 32nd International Conference on Neural Information Processing Systems, volume 37, pages 2338-2348, 2018.
[44] Haishan Ye, Luo Luo, Ziang Zhou, and Tong Zhang. Multi-consensus decentralized accelerated gradient descent. arXiv preprint arXiv:2005.00799 2020.
[45] Xiao-Tong Yuan and Ping Li. On convergence of distributed approximate newton methods: Globalization, sharper bounds and beyond. arXiv preprint arXiv: 02246, 2019.
[46] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the saddle point problems. arXiv preprint arXiv: 1912.07811 2019.
[47] Yuchen Zhang and Lin Xiao. Disco: Distributed optimization for self-concordant empirical loss. In Proc. of the 32nd International Conference on Machine Learning (PMLR), volume pages 362-377 (62-370, 2015.
[48] Yuchen Zhang and Lin Xiao. Communication--fliccenn distributed optimization of self-concordant emppriorrdaattmmiiiiaalill loss. Large-Scate and Distributed Optimizaaiion, pages 289-341. Springer, 2018.
13


Reviews:
[{"review_id": "tRjHDxBICK6", "reviewer": "Reviewer_PG9W", "summary": "This paper studies the distributed convex-concave saddle point problem under the relative smooth condition. Lower bounds are proved for strongly convex-strongly concave problems over centralized and decentralized networks. Optimal methods are proposed mathching the lower bounds.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper studies the lower bound for strongly convex-strongly concave saddle point problem under the relative smooth condition. The lower bound combines [4,34] (saddle point problems without the relative smooth condition) and [2] (strongly convex problems with the relative smooth condition).  Optimal algorithms are proposed matching these lower bounds. The contribution is solid.\n\nQuality: The theory is technically solid. The theories are supported by proofs. This is a complete work.\n\nClarity: This paper is written well.\n\nSignificance: Distributed optimization under the relative smooth condition is a significant topic. This paper extends it to the strongly convex-strongly concave saddle point problem. It is significant.\n\nMinor comments:\n\n1. This paper proves the communication complexity of the proposed algorithms for the general convex-concave saddle point problem in the supplementary material. Why do not include it in the main paper?\n\n2. What is the mitivation of Algorithm 1? It looks different from the classical statistically preconditioned Bregman gradient method for strongly convex problems. I suggest to explain why the updates are designed in the form of the three steps in Algorithm 1.\n\n3. The master node is defined to own function $f_1$. What about the first worker? I suggest to use $f_0$ for the master in Algorithm 1.\n\n4. I suggest to include a conclusion section. \n\n5. What is $\\beta$ on line 94? I think it should be $\\delta$.\n\n6. I suggest to provide more details about the experiment using real data, especially the numerical size of $\\delta$ in Assumption 2 and $\\mu$ in your experimental setting.\n\n7.  There is no mehotd compared in the experiment. I suggest to compare with the ones designed for the general strongly convex-strongly concave saddle point problems to verify whether the relative smooth condition helps to reduce the communication cost.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No limitation is discussed. Algorithm 2 is not very interesting because it strongly depends on the multi-consensus gossip subroutine. So the proof framework is indeed the same with the centralized problems. I suggest the authors to discuss the development of more practical decentralized algorithms in the conclusion section and leave it as a future job.", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "sETmR2C949M", "reviewer": "Reviewer_Crdz", "summary": "This paper studies distributed algorithms for convex-concave saddle point problem under both centralized and decentralized setting. Under similarity assumption, the proposed algorithms with nearly matching the lower bounds over either types of networks.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies distributed convex-concave saddle point problem for both centralized and decentralized settings. The proposed algorithms are based on extragradient iterations. updates, which contains time-varying communication topologies and federated learning.\nThe theoretical analysis show the proposed algorithm has near optimal communication complexities.\n\nMy main consideration is the theoretical results of this paper is based on $\\delta$-related assumption. However, the real distributed system usually needs to address the heterogeneous data setting, especial in decentralized case. The assumption of $\\delta$-related looks too strong. I hope the author could explain why it is reasonable and provide more detailed discussion.\n\nThere are also some comments for the experiments\n1. It prefers to provide some reference for robust linear regression model. If $||w||$ tends to infinity, can we guarantee problem (10)  is concave in $\\rho$?\n2. Explain how to partition data for dataset from LIBSVM.\n3. It is necessary to provide some experiments for decentralized setting.\n\nAdditionally, it is prefer to append a conclusion section after experiment part.\n\n---------\n\nThanks for the author response. I decided to raise my rating.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper focuses on the theory of distributed optimization. It is unnecessary to address the societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "o6TLBQn9r6", "reviewer": "Reviewer_6jmq", "summary": "The paper studies saddle-point problems with objective being a sum of strongly convex-concave functions, $\\min_x \\max_y f(x,y) = \\sum_{m = 1}^M f_m(x,y)$, in the setting of distributed communication. Specifically, each component in the sum of functions is local to an agent $m$, and communication between agents is expensive, which forces algorithms of two forms: master-worker type, and meshed grid type. \n\nThe paper's chief assumption is that the functions $f_i$ are $\\delta$-similar, which means an upper bound of $\\delta$ on  the operator norm  of the difference between the Hessians of $f_m$ and $f$, evaluated with respect to $(x,x)$, $(x, y)$, and $(y, y)$ directions. This assumption is reasonable in the case of robust linear regression and in proving adversarial robustness of neural networks. \n\nThe paper provides lower bounds and algorithms meeting these lower bounds for solving the saddle point problems to $\\epsilon$ accuracy. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies saddle-point problems with objective being a sum of strongly convex-concave functions, $\\min_x \\max_y f(x,y) = \\sum_{m = 1}^M f_m(x,y)$, in the setting of distributed communication. Specifically, each component in the sum of functions is local to an agent $m$, and communication between agents is expensive, which forces algorithms of two forms: master-worker type, and meshed grid type. \n\nThe paper's chief assumption is that the functions $f_i$ are $\\delta$-similar, which means an upper bound of $\\delta$ on  the operator norm  of the difference between the Hessians of $f_m$ and $f$, evaluated with respect to $(x,x)$, $(x, y)$, and $(y, y)$ directions. This assumption is reasonable in the case of robust linear regression and in proving adversarial robustness of neural networks. \n\nPROS: \n\n1. The paper provides lower bounds for runtime of solving a saddle-point problem to $\\epsilon$-accuracy, and, exploiting the assumption on function similarity,  the paper is able to improve the lower bounds that do *not* use function similarity. These lower bounds are provided for both the master-worker and meshed network models of communication. \n\n2. The paper provides algorithms that actually achieve these optimal runtimes (upto logarithmic factors), in both communication models. \n\nCONS: \n\n1. It is unclear to me what the significance of the paper's improvement is. \n\n2. I think it would be better to provide a proof sketch of the main techniques used in the main body itself. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A ", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "HfY19gtnbL", "reviewer": "Reviewer_ngA2", "summary": "The paper discusses the (strongly-)convex-(strongly-)concave distributed saddle point problems with $\\delta$-related functions in both master/worker networks and meshed networks. It provides lower bounds for each setting and the matching upper bounds, $O(\\Delta \\cdot \\delta / \\mu \\cdot \\log (1 / \\varepsilon))$ and $O(1 / \\sqrt{\\rho} \\cdot \\delta / \\mu \\cdot \\log (1 / \\varepsilon))$ respectively for two settings. ", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: I believe the theoretical results on distributed saddle point problem with $\\delta$-related assumptions are new.\n\nClarity: The structure and writing of the paper look fine. However, in the section 4, the authors provide little explanation for their algorithms. Although the algorithms are similar to some existing ones, it is easier for the readers to understand if there are some intuitions put in the paper. Same for the lower bound part, there is no overview for the hard instance in the main text. \n\nComments and questions:\n1. For the lower bounds in Theorem 1 and 2, on the right hand sides of the equations include only $\\|y^\\star\\|$. First, I think the authors did not define $\\|y^\\star\\|$ in the paper and I assume it is the optimal value for $y$. Second, the right hand side is not in terms of $\\|x_t-x_0\\|^2 + \\|y_t-y_0\\|^2$. Here if $\\|y^*\\|=0$, the lower bounds are not informative. \n\n2. The paper is based on many existing work, for example the lower bounds for smooth strongly-convex-strongly-concave minmax optimization and lower bounds for distributed minimization problem with $\\delta$-related assumption. Can the authors explain what is the technical novelty in this paper?\n\nminor:\n1. There is a typo under line 154 in the equation. \n2.  In line 17, the authors assume $X, Y$ to be compact, but in lower bound the case has unbounded domain. I think in the main text, the paper only discusses strongly-convex-strongly-concave setting and does not need to assume boundedness. It seems it is only needed in the convex-concave setting in the appendix. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall the majority of reviewers liked the paper and found the contributions interesting for NeurIPS. I also went over the paper and I think it provides an interesting and worthy contribution to distributed algorithms, studying saddle-point optimization problems under data-similarity (mostly motivated from statistical settings) and providing lower bounds on communication and matching upper-bounds. I recommend acceptance.
Decision: Accept (Poster)