Distributed Saddle-Point Problems Under Similarity
Year: 2022

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 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 ✏ > 0 is achieved over master/workers networks in ⌦ · /μ·log(1/") rounds of communications, where > 0 measures the degree of similarity of the local functions, μ is their strong convexity constant, and is the diameter of the network. The lower communication complexity bound over mesh networks reads ⌦ 1/ p ⇢ · /μ · log(1/") , where ⇢ 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.

text: · /µ·log(1/") rounds of communications, where
> 0 measures the degree of similarity of the local functions, µ is their strong convexity constant, and is the diameter of the network. The lower communication complexity bound over mesh networks reads ⌦ 1/ p ⇢ · /µ · log(1/") , where ⇢ 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.

heading: 1 Introduction
text: We study smooth (strongly-)convex-(strongly-)concave SPPs over a network of M agents:
min x2X max y2Y
f(x, y) := 1
M
MX
m=1
fm(x, y), (P)
where X,Y ✓ Rd are convex and compact sets common to all the agents; and fm(x, y) is the loss function of agent m, known only to the agent. Problem (P) has found a wide range of applications, including, game theory [42, 10], image deconvolution problems [7], adversarial training [3, 12], and statistical learning [1]–see Sec. 2 for some motivating examples in 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 of communication among (suitably chosen) neighboring nodes. We address such a 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 †ISP RAS Research Center for Trusted Artificial Intelligence
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
from federated learning applications (e.g., [17]), 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 is 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 a finite quantity > 0; we will term such SPPs as -related SPPs. For instance, this is the typical situation in the aforementioned distributed empirical risk minimization setting [2, 14, 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 = Õ(1/ p n), where n is the local sample size (Õ hides log-factors and dependence on d).
While SPPs have been extensively studied in the centralized setting (e.g., [10, 29, 18, 30, 5]) and more recently over mesh networks [23, 27, 22, 26, 36, 4, 6], 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 problems over networks (e.g., [2, 38, 35, 45, 43, 11, 47, 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 -related SSPs in the form (P) remains unclear. This paper provides a 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), we establish lower complexity bounds for the -related SPP (P) with µ-strongly-convex-strongly -concave, L-smooth (twice-differentiable) local functions: an " precision on the optimality gap over master/workers system is achieved in ⌦ · /µ · log(1/") communication steps, where is the diameter of the network. The lower complexity bound over mesh networks reads ⌦ 1/ p ⇢ · /µ ·
log(1/") rounds of communications, where ⇢ is the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes. These new lower bounds show a more favorable dependence on the optimization parameters (via /µ) than that of distributed oracles for SPPs ignoring function similarity [5, 36], whose communication complexity, e.g., over mesh networks reads ⌦ 1/ p ⇢ · L/µ · log(1/") . The latter provides a pessimistic prediction when /µ ⌧ L/µ. 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, 14]). (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 µ-strongly-convex-strongly-concave, L-smooth SPPs, which do not exploit function similarity. Preliminary numerical results on distributed robust logistic regression support our theoretical findings.

heading: 1.1 Related works
text: Methods for SPPs ignoring function similarity: (Strongly)-convex-(strongly)-concave SPPs have been extensively studied in the optimization literature and as special instances of (strongly) monotone Variational Inequalities (VI) [10, 16]. 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 [18] and the scheme in [30]–they are readily implementable on master/workers architectures as well. For SPPs with µ-strongly-convex-strongly-concave, L-smooth loss, all these schemes achieve iteration complexity of O L/µ · log(1/") , which has been shown to be optimal for first-order methods solving such a 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 -related SPPs in the form (P), provide quite pessimistic predictions, in the setting 1 + /µ ⌧ L/µ.
Methods for sum-utility 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, µ-strongly convex and L-smooth functions over mas-
ter/workers networks. Lower complexity bounds are established in [2], and read ⌦ p /µ log(1/") , which contrasts with O p L/µ log(1/")
achievable by first-order (Nesterov) accelerated methods [31], certifying thus faster rates whenever /µ < L/µ. Solutions methods exploiting function similarity are mirror proximal-like schemes, and include [38, 35, 45] (for quadratic losses), [47] (for self-concordant losses), [43], and [11] (for composite optimization), with [14] employing acceleration. None of these methods are implementable over mesh networks, because they rely on a centralized (master) node. To our knowledge, Network-DANE [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 a communication complexity of eO((1/p⇢) · /µ · log(1/")), where eO hides logarithmic factors. None of the methods above however are applicable to the -related SPP (P).

heading: 1.2 Notation
text: Given a positive integer M , we define [M ] = {1, . . . ,M}. We use hx, yi := P d
i=1 xiyi to denote standard inner product of x, y 2 Rd. It induces `2-norm in Rd in the following way kxk := p hx, xi. We also introduce projZ(z) = minu2Z ku zk – the Euclidean projection onto Z . We order the eigenvalues of any symmetrix matrix A 2 Rm⇥m in nonincreasing fashion, i.e., max(A) = 1(A) . . . m(A) = min(A), with max(·) [resp. min(·)] denoting the largest (resp. smallest) eigenvalue.

heading: 2 Setup and Background
text: Problem setting: We begin introducing the main assumptions underlying Problem (P) and some useful notation.
Let us stack the x- and y-variables in the tuple z = (x, y); accordingly, define Z = X ⇥ Y and the vector-functions Fm, F : Z ! R2d:
Fm(z) := ✓ rxfm(x, y) ryfm(x, y) ◆ , and F (z) := 1 M MX
m=1
Fm(z). (1)
The following conditions are standard for strongly convex-strongly concave SPPs.
Assumption 1 Given (P), the following hold:
(i) ; 6= Z is a convex set;
(ii) Each fm : R2d ! R is twice differentiable on (an open set containing) Z , with L-Lipschitz gradient: kFm(z1) Fm(z2)k  Lkz1 z2k, for all z1, z2 2 Z;
(iii) f(z) is µ-strongly convex-strongly concave on Z , i.e., hF (z1) F (z2), z1 z2i µkz1 z2k2, for all z1, z2 2 Z;
(iv) Each fm(z) is convex-concave on Z , i.e. 0-strongly convex-strongly concave.
We are interested in finding the solution z⇤ = (x⇤, y⇤) of Problem (P) under function similarity.
Assumption 2 ( -related fm’s) The local functions are -related: for all (x, y) 2 Z ,
kr 2 xx fm(x, y) r 2 xx f(x, y)k  ,
kr 2 xy fm(x, y) r 2 xy f(x, y)k  ,
kr 2 yy fm(x, y) r 2 yy f(x, y)k  .
The interesting case is when 1 + /µ ⌧ L/µ. 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]), = Õ(1/ p n) with high probability (Õ hides log-factors and dependence on d)–some motivating examples falling in this category are discussed in Sec. 2.1 below. While such examples
represent important applications, we point out that our (lower and upper) complexity bounds are valid in all scenarios wherein Assumption 2 holds, 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} denotes the vertex set–the set of agents–while E , {(i, j) | i, j 2 V} represents the set of edges–the communication links; (i, j) 2 E iff there exists a communication link between agent i and j. We denote by 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 a matrix W (a.k.a. gossip matrix). The following assumptions on W are standard to establish convergence of distributed algorithms over mesh networks.
Assumption 3 The matrix W 2 RM⇥M satisfies the following: (a) It is compliant with G, that is, (i) wii > 0, 8i 2 [M ]; (ii) wij > 0, if {j, i} 2 E ; and (iii) wij = 0 otherwise; (b) It is symmetric and stochastic, that is, W1 = 1 (and thus also 1>W = 1>).
Notice that a direct consequence of Assumption 3 (along with the fact that G is connected) is that
⇢ , 1 max{ 2(W ), | min(W )|} < 1, (2) where ⇢ is the eigengap between the first and second largest (magnitude) eigenvalue of W . Roughly speaking, ⇢ measures how fast the network mixes information (the larger, the faster).

heading: 2.1 Motivating examples
text: 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:
min w max r
1
2N
NX
i=1
(wT (xi + r) yi) 2 + 2 kwk2 2 krk2, (3)
where w are the weights of the model, {(xi, yi)}Ni=1 are pairs of the training data, and r models the noise, and and are the regularization parameters. Let n be the local sample size (thus N = nm). The typical regularization parameter that is optimal for test predictive performance is = O(1/ p N). Assuming of the same order of and invoking function similarity = O(1/ p n) [25, 14] yield a condition number of the problem  = O( p m · n) while /µ = O( p m). This implies that first order methods applied to (3) will slowdown as the local sample size n grows. Rate scaling with /µ would be instead independent on the local sample size.
Adversarial robustness of neural networks: 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, 13]. To improve resistance to a variety of adversarial inputs, a widely studied approach is leveraging robust optimization and formulate the training as saddle-point problem [24, 32]:
min w max r
1
N
NX
i=1
l(f(w, xi + r, yi) 2 + 2 kwk2 2 krk2,
where w are the weights of the model, {(xi, yi)}Ni=1 are pairs of the training data, r is the so-called adversarial noise, which models a perturbation in the data, and and 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 transportation 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 -related, then the resulting saddle-point problem is also so.

heading: 3 Lower Complexity Bounds
text: In this section we establish lower complexity bounds for centralized (i.e., master/workers-based) and distributed (gossip-based) algorithms. We begin introducing the back-box procedure describing the class of algorithms these lower bounds pertain to.

heading: 3.1 Optimization/communication oracle
text: Our procedure models a 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 1 (Oracle) Each agent m has its own local memories Mx m and My m for the x- and y-variables, respectively–with initialization Mx
m = My m = {0}. Mx m and Mx m are updated as
follows.
• Local computation: Between communication rounds, each agent m computes and adds to its Mx m and My m a finite number of points x, y, each satisfying
↵x+ rxfm(x, y) 2 span x0 , rxfm(x 0, y0),
(r2 xx fm(x 00, y00) +D)x0 , (r2 xx fm(x 00, y00) +D)rxfm(x 0, y0)
(r2 xx fm(x 00, y00) +D) 1x0 , (r2 xx fm(x 00, y00) +D) 1rxfm(x 0, y0),
(r2 xy fm(x 00, y00))y0 , (r2 xy fm(x 00, y00))ryfm(x 0, y0) ,
✓y 'ryfm(x, y) 2 span y0 , ryfm(x 0, y0),
(r2 yy fm(x 00, y00) +D)y0 , (r2 yy fm(x 00, y00) +D)ryfm(x 0, y0)
(r2 yy fm(x 00, y00) +D) 1y0 , (r2 yy fm(x 00, y00) +D) 1ryfm(x 0, y0),
(r2 xy fm(x 00, y00))Tx0 , (r2 xy fm(x 00, y00))Trxfm(x 0, y0) ,
(4) for given x0, x00 2 Mx
m and y0, y00 2 My m ; some ↵, , ✓,' 0 such that ↵+ > 0 and ✓+ ' > 0;
and D is some diagonal matrix (such that all the inverse matrices exist).
• Communication: Based upon communication rounds among neighbouring nodes, Mx m and My m are updated according to
M x m := span
8 <
: [
(i,m)2E
M x
i
9 = ; , M y m := span 8 < : [
(i,m)2E
M y
i
9 =
; . (5)
• Output: The final global output is calculated as:
xK 2 span
( M[
m=1
M x
m
) , yK 2 span ( M[
m=1
M y
m
) .
The above oracle captures a gamut of existing centralized and distributed algorithms. For instance, local computations model either inexact local solutions–e.g., based on single/multiple steps of gradient or Newton-like updates, which corresponds to setting ↵ = ✓ = 1 and = ' = 0–or exact solutions of agents’ subproblems (via some subroutine algorithm), corresponding to ↵ = ✓ = 0 and = ' = 1. Multiple rounds of computations (resp. communications) can be 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).

heading: 3.2 Lower complexity bounds
text: We are in the position to state our main results on lower communication complexity–Theorem 1 pertains to algorithms over master/workers systems while Theorem 2 deals with mesh networks.
Theorem 1 For any L, µ, > 0 and connected graph G with diameter > 0, there exist a SPP in the form (P) (satisfying Assumption 1) with Z = R2d (where d is sufficiently large), x⇤ 6= 0, y⇤ 6= 0, and local functions fm being L-smooth, µ-strongly-convex-strongly-concave, -related (Assumption 2) such that any centralized algorithm satisfying Definition 1 produces the following estimate on the global output zK = (xK , yK) after K communication rounds:
kzK z⇤k2 = ⌦
0
BB@exp
0
BB@ K ·
1
1 8
r 1 + ⇣
32µ
⌘2
1 8
1
CCA ky ⇤ k 2
1
CCA .
Corollary 1 In the setting of Theorem 1, the number of communication rounds required to obtain a "-solution is lower bounded by
⌦
✓ ✓ 1 +
µ
◆ · log ✓ ky⇤k2
"
◆◆ . (6)
Theorem 2 For any L, µ, > 0 and ⇢ 2 (0; 1], there exist a SPP in the form (P) (satisfying Assumption 1) with Z = R2d(where d is sufficiently large), x⇤ 6= 0, y⇤ 6= 0, and local functions fm being L-smooth, µ-strongly-convex-strongly-concave, -related (Assumption 2), and a gossip matrix W over the connected graph G, satisfying Assumption 3 and with eigengap ⇢, such that any decentralized algorithm satisfying Definition 1 and using the gossip matrix W in the communication steps (5) produces the following estimate on the global output zK = (xK , yK) after K communication rounds:
kzK z⇤k2 = ⌦
0
BB@exp
0
BB@ K p ⇢ ·
1
1 20
r 1 + ⇣
32µ
⌘2
1 20
1
CCA ky ⇤ k 2
1
CCA .
Corollary 2 In the setting of Theorem 2, the number of communication rounds required to obtain a "-solution is lower bounded by
⌦ ✓ 1 p ⇢ ✓ 1 + µ ◆ · log ✓ ky⇤k2 " ◆◆ . (7)
These lower complexity bounds show an expected dependence on the optimization parameters and network quantities. Specifically, the number of communications scale proportionally to /µ–this generalizes existing lower bounds [5] that do not account for such similarity, resulting instead in the more pessimistic dependence on L/µ–typically  L. The network impact is captured by the diameter of the network for master/workers architectures– communications steps are required in the worst case to transmit a message between two nodes–and the eigengap ⇢ of the matrix W , when arbitrary graph typologies are consider; 1/p⇢ can be bounded as O(T ), where T is the largest hitting time of the Markov chain with probability transition matrix W [33]. For instance, for fully connected networks = 1/p⇢ = 1 while for star networks = 1 and 1/p⇢ = p M . For general graphs, 1/p⇢ can be larger than , see [28] for more details. To certify the tightness of the derived lower bounds, the next section designs algorithms that reach such bounds.

heading: 4 Optimal algorithms

heading: 4.1 Centralized case (master/workers systems)
text: Our first optimal algorithm is for SPPs over master/workers architectures or more generally networked systems where a spanning tree (with the root as master node) is preliminary set; it is formally described in Algorithm 1. We assumed w.l.o.g. 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 minx2X f(x) := 1M P M
m=1 fm(x), under Assumption 2. Following [38] we can solve it invoking the mirror descent algorithm, which reads
xk+1 = argmin x
⇥ h⌘rf(xk), xi+D (x, x k) ⇤ , (8)
where D (x, y) = (x) (y) hr (y), x yi is the Bregman divergence, with function (x) = f1(x)+ 2kxk 2. It is shown that we can take stepsize ⌘ = 1 ([48, 14]). Therefore, (8) can be rewritten as
xk+1 = argmin x
" 1
f1(x) +
1
2
x x k +
1
(rf(xk) rf1(x k)) 2 # . (9)
Noting that in Algorithm 1 ⇠ 1 (see Appendix B.1), one infers the connection between (9) and the updates in lines 3 (i) and 3 (ii). The extra step as in line 3 (iii) is due to the fact that Algorithm 1 solves a SPP (and not a classical minimization as postulated above): gradient descent-like 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-Backward-Forward algorithms [41] or the Extragradient [18] method, which leads to the step in line 3 (iii).
• Another interpretation of the proposed algorithm comes from looking at Problem (P) as a composite minimization problem, with objective function h1(x, y) + h2(x, y), with h1(x, y) = f1(x, y) and h2(x, y) = 1 M P M
m=1(fm(x, y) f1(x, y)). The first function h1 is L-smooth and convex-concave while h2 is -smooth and, in general, non-convex-non-concave. Such type of problems can be solved invoking sliding techniques [19, 36].
Algorithm 1 (Star Min-Max Data Similarity Algorithm)
Parameters: stepsize , accuracy e; Initialization: Choose z0 = (x0, y0) 2 Z , z0
m = z0, for all m 2 [M ];
1: for k = 0, 1, 2, . . . do 2: Each worker m computes Fm(zk) and sends it to the master; 3: The master node:
(i) computes vk = zk · F (zk) F1(zk) ;
(ii) finds uk, s.t. kuk ûkk2  e, where ûk is the solution of:
min ux2X max uy2Y
 f1(ux, uy) + 1
2 kux v
k x k 2
1 2 kuy v k y k 2 ; (10)
(iii) updates zk+1 = projZ ⇥ uk + · (F (zk) F1(zk) F (uk) + F1(uk)) ⇤ and broadcasts
zk+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 1. It accommodates either exact solutions of the strongly convex subproblems (10) (corresponding to e = 0) or inexact ones (up to tolerance e > 0)–the latter can be computed, e.g., using Extragradient method [16], which is optimal in this case.
The communication complexity of the method is proved in the next theorem, which certifies that the proposed algorithm is optimal, i.e., achieves the lower bound (6) on the number of required communications–we refer to Appendix B.1 in the supplementary material for a 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).
Theorem 3 Consider Problem (P) under Assumptions 1-2 over a connected graph G with a master node. Let {zk} be the sequence generated by Algorithm 1 with tuning as described in Appendix B.1 (cf. the supplementary material). Then, given " > 0, the number of communication rounds for kzk z⇤k2  " is O 1 + /µ log(1/") .

heading: 4.2 Distributed case (mesh networks)
text: We consider now mesh networks. Because of the lack of a master node, each agent m now owns local estimates um and vm of the common variables u 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, 44]–the latter being instrumental to propagate the updates of the u, v-variables and gradients across the network. The algorithm is formally introduced in Algorithm 2, with the accelerated gossip procedure described in Algorithm 3.
Algorithm 2 (Distributed Min-Max Data Similarity Algorithm)
Parameters: stepsize , accuracy e, e0, e1, communication rounds H0, H1; Initialization: Choose z0 = (x0, y0) 2 Z , z0
m = z0, for all m 2 [M ];
1: for k = 0, 1, 2, . . . do 2: Communications: F̄ k1 , . . . F̄ kM = AccGossip(F1(z k 1 ), . . . FM (z k M );H0); 3: Local computations: Choose an index mk 2 [M ] uniformly at random; then node mk (i) computes vk
mk = zk mk · (F̄ k mk Fmk(z k mk ));
(ii) finds ũk mk , s.t. kũk mk ûk mk k 2  e, where ûk mk is the solution of:
min ux2X max uy2Y
 fmk(ux, uy) + 1
2 kux v
k x,mk k 2
1 2 kuy v k y,mk k 2 ; (11)
4: Communications: Run accelerated gossip to propagate ũk mk and update gradient variables:
uk1 , . . . u k M = M · AccGossip(0, . . . , 0, ũk mk , 0 . . . , 0;H1),
F̄ k+1/21 , . . . F̄ k+1/2 M = AccGossip(F1(uk1), . . . FM (u k M );H0);
5: Update of z̃mk -variable: node mk performs
z̃k+1 mk = ũk mk + · (F̄ k mk Fmk(z k mk ) F̄ k+1/2 mk + Fmk(ũ k mk ));
6: Communications: Run accelerated gossip to propagate z̃k+1 mk :
ẑk+11 , . . . ẑ k+1 M = M · AccGossip(0 . . . , 0, z̃k+1 mk , 0 . . . , 0;H1);
7: Each worker update zk+1 i = projZ ⇥ ẑk+1 i ⇤ ; 8: end for
Algorithm 3 (AccGossip)
Input: z1, ..., zM 2 R2d, and H > 0 (communication rounds); Initialization: Construct matrix Z with rows zT1 , . . . , zTM ; Set
Z 1 = Z, Z0 = Z, and ⌘ = 1 p
1 22(W ) 1+ p 1 22(W )
. 1: for t = 0, 1, 2, . . . , H do 2: Zt+1 = (1 + ⌘)WZt ⌘Zt 1, 3: end for
Output: Rows of ZH+1
Convergence of the method is established in Theorem 4 below–we refer to Appendix B.2 in the supplementary material for a detailed description of the algorithmic tuning [choice of the stepsize , precision e, numbers of communications rounds H0, H1, and algorithm to solve (10)].
Theorem 4 Consider Problem (P) under Assumptions 1-2 over a connected graph G. Let {(zk
m )m2[M ]} be the sequence generated by Algorithm 2 with tuning as described in Appendix B.2 (cf. the supplementary material) and gossip matrix W satisfying Assumption 3. Then, given " > 0,
the number of communication rounds for kz̄k z⇤k2  " reads Õ 1/ p ⇢ · 1 + /µ log2 1
"
, where
z̄k = 1 M
P M
m=1 z k m .
While the algorithm achieves the lower bound (7), up to log-factors (which now however depends on " 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 to be not quite efficient. Designing alternative distributed algorithms overcoming these limitation is a challenging open problem.

heading: 5 Numerical Results
text: We simulate the Robust Linear Regression problem which is defined as
min w max krkRr
1
2N
NX
i=1
(wT (xi + r) yi) 2 + 2 kwk2 2 krk2. (12)
where w are the model weights, {xi, yi}Ni=1 is the training dataset, and r is the artificially added noise; we use `2-regularization on both w and r. We solve the problem over a master/workers topology; we consider a network with 25 workers. We test Algorithm 1 wherein the subproblems (10) at the master node are solved with high accuracy using Extragradient method. A description of the tuning of the algorithm parameters can be found in Appendix C. The algorithms are implemented in Python 3.73.
Our first experiment uses synthetic data, which allows us to control the factor , measuring statistical similarity of functions over different nodes. Specifically, we assume all local datasets of size n = 100. The data set {x̂i, ŷi}ni=1 at the master node is generated randomly, with each entry of x̂i and ŷi, i = 1, . . . , n drawn from the Standard Gaussian distribution. The datasets at the workers’ sides, i = 2, . . . ,M , are obtained perturbing {x̂i, ŷi}ni=1 by random noise ⇠i with controlled variance.
3Source code: https://github.com/alexrogozin12/data_sim_sp
Figure 1 compares the performance of Algorithm 1 and the Centralized Extragradient method [5] applied to Problem (12), under different level of noise added to 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. It can be seen that Algorithm 1 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 1). On the other hand, at high noise (amplitude 10.0) the performance of Extragradient and Algorithm 1 become comparable. In addition, we compare the performance of Alg.2 under different noise over networks with different topologies in Figure 2.
Our second experiment is using real data, specifically LIBSVM datasets [8]. In this scenario, we 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 at each node). Figure 3 compares Algorithm 1 and the Extragradient method: we plot the distance of the iterates from the solution vs. the number of communications. Quite interesting, Algorithm 1 compares favorably even when the number of workers becomes large. Figure 4 compares Algorithm 2 with Decentralized Extragradient method (EGD) [5] 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.

heading: 6 Conclusion
text: 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 µx and µy). 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 # N0001421-1-2673. The paper was prepared within the framework of the HSE University Basic Research Program.

Review summaries:
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.

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.

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.   The 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.   The paper provides lower bounds and algorithms meeting these lower bounds for solving the saddle point problems to $\epsilon$ accuracy. 

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.