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 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.
master/workers networks Q A-0 A-0//ploog1///
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 ISP 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)))) 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 33 45
self-concordant losses), +4 and [T]] (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/ yy (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 ++2210000
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 (11/V/1 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/μ = (( This implics that first the local sample size n grows. Rate scaling with 8/μ would be instead independent on the local sample size.
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 [( + 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 Optinizationccommnitttooon 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 (allm yy + D) -'d, (Vialm(" (1","") + -V- 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 y) and (22 v) मे. Em=1< (Jm (2,,3) y) f1 (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) + Ellus 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 COnSORT 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(11: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 04870, 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 hamesssng 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, 7000: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": "yA1BRo43hRr", "reviewer": "Reviewer_VL91", "summary": "In this work a distributed (strongly)-convex-(strongly)-concave saddle point problem (SPP) is studied, over two different types of networks, i.e., master/worker, and meshed networks. In both cases lower bounds are derived for the number of communication rounds required  to reach an $\\epsilon$ optimal solution. Differently than previous works on distributed SPP, the new analysis takes into account the similarity between the local functions. The lower communication complexity for reaching an $\\epsilon$-optimal solution is shown to be in the order of $\\Omega \\left( \\frac{\\Delta \\delta}{\\mu} \\log \\left( \\frac{1}{\\epsilon}\\right) \\right)$ for a master/worker network and  $\\Omega \\left( \\frac{ \\delta}{\\mu \\sqrt{\\rho}} \\log \\left( \\frac{1}{\\epsilon}\\right) \\right)$ for a meshed one; the parameter $\\delta$ captures the function similarity while $\\Delta, \\rho$ depend on the properties of the network. Then, two algorithms are developed, one for each network type, that match these bounds, up to logarithmic factors. Finally, the proposed algorithms are evaluated on a robust linear regression problem over synthetic and real data.", "questions": "", "limitations": "", "rating": 6, "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": "Some of the positive aspects of this work are the following:\n\n1. The authors derive novel communication complexity bounds for a setting (where the similarity between the local functions is leveraged) that has not been studied before in distributed SPPs. These new results generalize known lower bounds in the sense that the known ones offer more pessimistic estimates in the setting where function similarity is considered.\n \n2. The algorithm class under which the lower bounds are derived is wide enough to capture many interesting distributed algorithms (e.g. using gradient or Newton updates)\n    \n3. Both types of networks, that is master/worker and meshed, are common and their study is motivated by applications. For instance, master/worker networks appear in federated learning applications.\n\nThe weak points of this work, as well as some other minor comments, are given below.\n\n1. The utility of the derived lower bound is limited, since it is useful/interesting under the condition that $\\frac{\\delta}{\\mu} << \\frac{L}{\\mu}$, where $\\delta$ captures function similarity, $\\mu$ is the strong convexity modulus, and $L$ is the smoothness parameter. \n\n2. A central assumption in this work is the $\\delta$-similarity of the local functions. However, the specific similarity concept defined in assumption 2 is not sufficiently motivated.  For instance, why not consider similarity in terms of gradients (rather than Hessian)?  Overall, why it is important to study the problem under the assumption of function similarity?\n\n3. The last two motivating examples in Section 2.1 do not seem to motivate the distributed SPP problem, but rather a general SPP problem. Since this is a work about distributed SPPs I think it would be fitting to discuss why these problems are interesting in the distributed setting. \n\n4. Comments about the experiments\n\n    a. In the experiments Algorithm 1 is compared with the extragradient method, which is ‘‘applied directly on problem (10)’’. I presume this means that the extragradient method solves problem (10) as a non-distributed problem. Then, it is not clear how the communication rounds are defined for the extragradient algorithm, in figures 1 and 2. Also,  the authors need to explain why the comparison with a non-distributed algorithm is meaningful.\n\n    b. There is no comparison with a distributed SPP algorithm. Thus, we cannot see if the proposed algorithm is indeed better in practice in terms of communication complexity compared with algorithms developed for the same setting. Why not perform a comparison with one of the distributed SPP methods mentioned in the ‘Introduction’ section?\n\n    c. It is mentioned in the text that the experiments over meshed networks are located in the supplementary material. However, I cannot find these results. Are they missing?\n\n   d. What is ‘sliding’ in the legend of figure 1? Also, the legends in figures 1 and 2 are different, although according to the description both experiments compare the same algorithms.\n\n  e. It is mentioned that ‘We solve the problem over a master/workers topology; we consider networks with 10 and 15 workers’. However, in the figures 1 and 2 the numbers are 10 and 20, respectively.\n\n5. In the four theorems of the main text the solution $z^{\\ast}$ is not defined.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the Main Review Section for some of this works limitations/weak points that remain to be addressed.\n", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-10"}, "extra_text": {}}, {"review_id": "pfzaAJfdoz", "reviewer": "Reviewer_J36K", "summary": "In this paper, the authors have studied solution methods for strongly-convex-strongly-concave saddle-point problems over two types of networks, namely, master/workers networks and meshed networks. For each type of network, the authors have established lower and upper complexity bounds that depend on the problem parameters, such as the degree of similarity of the local functions and the strongly convex/concave parameter. \n\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": "The paper is well written and also improves the state of the art in the field. The main weakness of the paper is that the experimental results are limited and Algorithm 3 requires global information of the network.  The detailed comments are as follows:\n\n1. The parameter $\\eta$ in Algorithm 3 depends on the second largest eigenvalue of the communication matrix $W$, i.e. $\\lambda_{2}(W)$, which requires the global information of the network. Can you discuss this point and provide some distributed methods that can provide a good estimate of $\\lambda_{2}(W)$?\n\n2. In experimental results, it is preferred to study the effects of the graphs (ring, random, $k$-regular expander, etc.) on the convergence of the proposed algorithm.\n\n3. The comparison with related work in experiments seems lacking. It is preferred to compare with the algorithms in [4] and [34]. It is also of interest to see the performance comparisons when the problem is ill-conditioned. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "I_749wJPfKU", "reviewer": "Reviewer_HYkt", "summary": "This paper studies distributed (both centralized and decentralized) saddle point problems. The focus is to relate the complexity to the similarity between objective function (determined by data) on different machines, thus the complexity will be reduced when the local objectives are similar to each other.", "questions": "", "limitations": "", "rating": 5, "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": "Merits: Developed distributed algorithms that take advantage of local function similarity, reducing communication complexity compared to existing works when \\delta/mu << L/mu.\n\nConcerns:\n\n1. My first concern is the correctness of the lower bound. In the centralized case (master/workers network),  the lower bound of O(\\delta/mu \\log(1/\\epsilon)) in this submission is different from the one in reference [2], i.e. O(\\sqrt(\\delta/mu)\\log(1/\\epsilon)), which means the lower bound in this submission is higher (tighter) than that one when \\delta/\\mu > 1. What causes this difference? Is the lower bound in [2] not tight? Since reference [2] already proposed an algorithm that can hit the lower bound for a special class of problems (quadratic problem) which can satisfy the assumptions in this submission, I doubt the correctness of the lower bound in this submission. The authors may want to highlight the setting difference and proof technique difference if the lower bound in this submission is indeed correct and tighter than reference [2].  \n\n2. Theorem 1, 2 in the paper and theorem 5, 6 in the supplement material use extra assumptions f and f_m is 1-smooth and 1-Lipschitz continuous. These coefficients are critical (or even the whole point given the problems considered in this paper), thus I would highly suggest to keep them as parameters explicitly (e.g., L-smooth and G-Lipschitz), only then we can make sure the theorems are telling the right story. Also, please double check other theorems in case these assumptions are used implicitly.  \n\n3. At each iteration, full gradients are required and a subproblem has be solved accurately enough. This makes the algorithm impractical, especially considering the fact that problem scales are usually quite big in distributed scenarios.\n\n4. In Algorithm 1, F_1 and f_1 are used, are they typos? Otherwise, what is the insight to utilize F_1 and f_1 in that way?\n\n5. Please relate the theorems in the supplement materials more clearly to the theorems in the paper, i.e., which is which.\n\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": {}}, {"review_id": "-Z5MdiM4Dgs", "reviewer": "Reviewer_TSma", "summary": "This paper considers the problem of solving smooth strongly convex strongly concave saddle point problems over both centralized and decentralized networks. The main novelty is the consideration of the similarity between local functions in terms of second-order information. It provides better complexity lower bounds for both centralized and decentralized cases when the similarity of local functions is better than the smoothness of the objectives, as well as a near-optimal algorithm for the centralized case.", "questions": "", "limitations": "", "rating": 6, "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": "This work provides novel and solid complexity results for distributed SPPs under the local function similarity framework. Empirical studies are also discussed.\n\nMajor questions and concerns are: \n1. The paper only discusses the empirical loss (i.e., the robust regression) example that is related to the key Assumption 2 throughout the paper, which might limit its potential scope. It is beneficial to include more examples to discuss how strong it is in practice.\n2. Sometimes x and y play unsymmetric roles in SPPs, while Assumption 2 treats them equally. Can the authors comment on the potential generalization of Assumption 2 to handle x, y differently to give an even tighter analysis?\n3. At Line 176, is limiting $\\alpha + \\beta >0$ and $\\theta + \\psi >0$ necessary for obtaining the lower complexity bounds? Why?\n4. Algorithm 1 does not explicitly use any similarly related quantities, it is just a tighter analysis under Assumption 2 to make it optimal? Authors should provide more insights about the analysis to explain how the algorithm takes advantage of similarity assumptions. Authors should also explain what example you construct to prove complexity lower bounds in the main text. \n5. The results for the decentralized case do not seem ideal as the complexity depends on $O(\\log^2 \\frac{1}{\\epsilon})$. There are also no empirical results for this case.\n\nMinor comments are: \n1. Title in pdf file mismatches with the submission\n2. Line 97, n should be d\n3. Line 111, L-smooth gradient should be either L-Lipschitz gradient or L-smooth\n4. Line 143 and 144, notation n is reused and can cause confusion\n5. Line 183 and 185, $\\phi$ should be $\\psi$\n6. Line 3 in Alg 3, $t+1$ should be $t$", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this work a distributed (strongly)-convex-(strongly)-concave saddle point problem (SPP) is studied. The authors provide communication lower bounds to reach an  $\epsilon$-optimal solution. Differently than previous works on distributed SPP, the result in this work takes into account the similarity between the local functions. Further, algorithms are developed which  match the proposed lower bounds. Finally, the proposed algorithms are evaluated on a robust linear regression problem over synthetic and real data.

Pros:

1) The authors derive communication complexity bounds for the SSP setting, which appears to generalize known lower bounds for the same class of saddle point problems, but without taking the similarity into consideration. 

2) The authors developed two algorithms, one for the case with central controller, and one for the case without central controller, for the considered problems. Further, the authors developed analysis for the proposed algorithms, and show that the lower bound derived can be in fact met. 

Cons:

1) The intuition behind algorithm design is not clear; nor is it clear whether a few design choices is necessary for not. For example, in Algorithm 1, why instead of performing a single gradient descent step, one needs to do step (iii) combined with step (i). Consider the simple case where there is no constraint, and f_1 = 0, then it seems that step (iii) does not provide any benefit in addition to step (i). As some reviewers have pointed out, it is difficult to understand a few design choices of the proposed algorithm. 

2) There is a lingering issue about how the lower bounds depends on how the fact that the authors' assumption about f and f_m being 1-smooth and 1-Lipschitz continuous (instead of having constants explicitly written down) will affect the proof.  This is an important question. The authors provided answers to it, but this requires the current proof to be changed. 

3) A question related to 2)  is that when constructing lower bound, it has assumed that the function is 1-Lipschitz continuous, while everywhere in the paper, such condition is not considered. Typically this will not pose any issue since the upper bound (for a wider class of problem without assuming Lipschitz-continuous function) matches the lower bound (constructed using a smaller class). However, since the dependency on the Lipschitz constant is not clear, and the key here is to understand whether the upper bound is tight in \delta, there could be an issue. Assume that the constructed problem is L-Lipschitz. It could be that the lower bound depends on \delta and L through $\frac{\delta}{L}$. In this case, the larger the L, the weaker the dependency on \delta. However, the upper bound does not quantify such a dependency, since there is no assumption on the Lipschitzness of the function. My point is that, it is important to explicitly write down the dependency on the Lipschitz constant, and the gradient Lipschitz constant, especially when the constructed problem requires additional assumption. 

3) As a minor comment, the algorithm itself is not particularly designed for problems with similarity. The similarity constant appears when providing the analysis, and in particular, when setting the accuracy for solving local problems. 

Overall, I think the paper is interesting and contains good results. However, there are still a few places,  that require some substantial revision.  I believe that this paper will be made much better if these issues are addressed. 


Decision: Accept (Poster)