SAGDA: Achieving $\mathcal{O}(\epsilon^{-2})$ Communication Complexity in Federated Min-Max Learning
Authors: Haibo Yang
Zhuqing Liu
Xin Zhang
Jia Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: federated learning
min-max
optimization
variance reduction

Abstract: Federated min-max learning has received increasing attention in recent years thanks to its wide range of applications in various learning paradigms. Similar to the conventional federated learning for empirical risk minimization problems, communication complexity also emerges as one of the most critical concerns that affects the future prospect of federated min-max learning. To lower the communication complexity of federated min-max learning, a natural approach is to utilize the idea of infrequent communications (through multiple local updates) same as in conventional federated learning. However, due to the more complicated inter-outer problem structure in federated min-max learning, theoretical understandings of communication complexity for federated min-max learning with infrequent communications remain very limited in the literature. This is particularly true for settings with non-i.i.d. datasets and partial client participation. To address this challenge, in this paper, we propose a new algorithmic framework called \ul{s}tochastic \ul{s}ampling \ul{a}veraging \ul{g}radient \ul{d}escent \ul{a}scent ($\mathsf{SAGDA}$), which i) assembles stochastic gradient estimators from randomly sampled clients as control variates  and ii) leverages two learning rates on both server and client sides. We show that $\mathsf{SAGDA}$ achieves a linear speedup in terms of both the number of clients and local update steps, which yields an $\mathcal{O}(\epsilon^{-2})$ communication complexity that is orders of magnitude lower than the state of the art. Interestingly, by noting that the standard federated stochastic gradient descent ascent (FSGDA) is in fact a control-variate-free special version of $\mathsf{SAGDA}$, we immediately arrive at an $\mathcal{O}(\epsilon^{-2})$ communication complexity result for FSGDA. Therefore, through the lens of $\mathsf{SAGDA}$, we also advance the current understanding on communication complexity of the standard FSGDA method for federated min-max learning.

SAGDA: Achieving ( Communication Complexity in Federated Min-Max Learning
Haibo Yang Dept. of ECE
Zhuqing Liu Dept. of ECE
The Ohio State University Columbus, OH 43210 yang www.59950ssueeee
The Ohio State University Columbus, OH 43210 1iu. 93848osu. edu
Xin Zhang Dept. of Statistics Iowa State University Ames, IA 50010
Jia Liu Dept. of ECE The Ohio State University Columbus, OH 43210 liu8ece. osu. edu
xinzhang@iastate.ccm edu
Abstract
Federated min-max learning has received increasing attention in recent years thanks to its wide range of applications in various learning paradigms. Similar to the conventional federated learning for empirical risk minimization problems, commu- nication complexity also emerges one of the most critical concerns that affects the future prospect of federated min-max learning. To lower the communication complexity of federated min-max learning, natural approach is to utilize the idea of infrequent communications (through multiple local updates) same as conventional federated learning, However, due to the more complicated inter-outer problem structure federated min-max learning, theoretical understandings communication complexity for federated min-max learning with infrequent commu- nications remain very limited in the literature. This is particularly true for settings with non-i..d. datasets and partial client participation. To address this challenge, in this paper, we propose new algorithmic framework called stochastic sampling averaging gradient descent ascent (SAGDA), which i) assembles stochastic gradient estimators from randomly sampled clients as control variates and ii) leverages two learning rates both server and client sides. We show that SAGDA achieves linear speedup in terms both the number clients and local update steps, which yields O(E -2) communication complexity that is orders of magnitude lower than the state of the art. Interestingly, by noting that the standard federated stochastic gradient descent ascent (FSGDA) is in fact control-variate-fre special version of SAGDA, we immediately arrive at an O(e communication complexity result for FSGDA. Therefore, through the lens of SAGDA, we also advance the current understanding on communication complexity of the standard FSGDA method for federated min-max learning.
Introduction
Recently, min-max optimization has drawn considerable attention from the machine learning com- munity. Compared with conventional minimization problems (e.g., empirical risk minimization), min-max optimization has richer mathematical structure, thus being able to model more sophis- ticated learning problems that emerge from ever-emerging applications. particular, the subclass
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of nonconvex-conee and nonconvex- PL (ojisak---jsiiiicz)) min-max problems has important applications in, e.g,, AUC (area under the ROC curve) maximization 2 adversarial and robust learning 4 and generative adversarial network (GAN) (5]. The versatility of min-max optimiza- tion thus sparks intense research on developing efficient min-max algorithms. In the literature, the family of primal-dual stochastic gradient methods is one of the most popular and efficient approaches. For example, the stochastic gradient descent ascent (SGDA) method in this family has been shown effective in centralized (single-machine) learning, both theoretically and empirically. However, as over- per-parameterized models (e.g.. deep neural networks) being more and more prevalent, learning on single machine becomes increasingly inefficient. To address challenge, large-scale distributed learning emerges as an effective mechanism to accelerate training and has achieved astonishing successes in recent years. Moreover, as more stringent data privacy requirements arise in recent years, centralized learning becomes increasingly infeasible due to the prohibition of data collection. This also motivates the need for distributed learning without sharing raw data. Consequently, there is a growing need for distributeed/federated min-max optimization, such as federated deep AUC maximization 66.
federated adversarial training (8] and distributeddfederrteed GAN
Similar to conventional federated learning for minimization problems, federated min-max learning enjoys benefits of parallelism and privacy, but suffers from high communication costs. One effective approach to reduce communication costs is to utilize infrequent communications. For example, in conventional federated learning for minimization problems, the FedAvg algorithm [12] allows each client performs multiple stochastic gradient descent (SGD) steps to update the local model between two successive communication rounds. Then, local models are sent to and averaged periodically at the server through communications. Although infrequent communication may introduce extra noises due to data heterogeneity, FedAvg can still achieve the same convergence rate distributed SGD, while having a significant lower communication complexity. Inspired by the theoretical and empirical success of FedAvg, natural idea to lower the communication costs of federated min-max optimization is to utilize infrequent communication in the federated version of SGDA. Despite the simplicity of this idea, existing works can only show unsatisfactory convergence rates (O(L/vmT)) [13 and O(1/ (mKT))1/3 (14)) for solving
or non- convex-PL by federated SGDA with infrequent communication (m is the number of clients, K is the number of local steps, and is the number of communication rounds). These convergence rates do not match with that of the FedAvg method. These unsatisfactory results are due to the fact that federated min-max optimization not only needs to address the same challenges in conventional federated learning (e-g., data heterogeneity and partial client participation), but also handle the more complicated inter-outer problem structure. Thus, a fundamental question in federated min-max optimization is: Can a federated SGDA-type -eppe method with infrequent communication provably achieve the same convergence rate and even the highly desirable linear speedup effect for federated min-max problems?
In this paper, we answer this question affirmatively. The main contributions of this paper are summarized as follows:
We propose a new algorithmic framework called SAGDA(stochastic sampling averaging gradient descent ascent), which assembles stochastic gradient estimators as control variates and leverages two learning rates on both server and client sides. With these techniques, SAGDA relaxes the restricted "bounded gradient dissimilarity" assumption, while still achieving the same convergence rate with low communication complexity. We show that SAGDA achieves the highly desirable linear speedup in terms of both the number of clients (even with partial client participation) and local update steps, which yields an O( communication complexity that is orders of magnitude lower than the state of the art in the literature of federated min- min-max optimization.
Interestingly, by noting that the standard federated stochastic gradient descent ascent (FSGDA) is in fact a from our theoretical analysis of SAGDA that FSGDA achieves an rate for non-convex-PL problems with full client participation, which further implies the highly desirable linear speedup effect. This improves the ofate-of-the-art result of FSGDA by factor of
special version of our SAGDA algorithm, we can conclude convergence
0(1/ (mKT) 1/6 //6 [14) and matches the optimal convergence rate of non-convex FL. Therefore, through the lens of SAGDA, we also advance the current understanding on the communication complexity of the standard FSGDA method for federated min-max learning.

---

Table 1: Number of communication rounds and stochastic gradients per client to reach e-stationary point (I|V S c) for federated non-convex-PL. min-max learning, denoted as communication and client sample complexity. We omit the higher orders. Here m is the number of clients. BGD means bounded gradient dissimilarity, which requires bounded data heterogeneity. SAGDA supports client sampling and does not require BGD assumption.
BGD Assumption
Client Sampling?
Per-Client Sample
Communication Complexity
Methods
Complexity
SGDA
Local SGDA
14
max 4, m2738
((L/m)e 9)
(Momentum)
(((L/m)E
O
Local SGDA
1.5
CD-MAGE
(((1/m)
((11m))=1)
SAGDA (Cor.
Not needed
((1/m)c
FSGDA (Cor.
O ((1/m)E
(
The rest of the paper is organized as follows. In Section 2 we first introduce SAGDA And its convergence analysis, and then build the connection between SAGDA and FSGDA. We present numerical results in Section 4 and conclude the work in Section 5
we review related work. In Section 3
Due to space limitation, we relegate all proofs and some experiments to the supplementary material.
Related work
1) Federated Learning: In federated learning (FL), the seminal federated averaging (FedAvg) [16] algorithm was first proposed as a heuristic to improve communication efficiency and data privacy, but later theoretically confirmed to achieve highly desirable O(1/v ((1/vmKT) convergence rate in FL (implying linear convergence speedup as the number of clients m increases). Since then, many follow-up works have been proposed to achieve the ((1/ convergence rate for i.i.d. datasets (17 23 and non-i.i.d. datasets 33). For comprehensive survey on FL convergence rate order, we refer readers to Section 3 in 34]
2) Min-max Optimization: Min-max optimization has a long history dating back to at least [35 36].
For wwwoeee-ttroggl--ooooe
min-max problems, simple approach is the stochastic gradient descent ascent (SGDA), which performs stochastic gradient descent on primal variables and stochastic gradient ascent on dual variables, respectively. It is well-known that SGDA achieves an ((/vVT) convergence rate (37 for seo-convee-sttrongyy-comm
min-max problems, matching that of SGD in non-convex optimization. However, in the federated con-comvex-stroonlyy-oom in [33 and (14) only proved O(1/Vm7) and O (11((m/k) (mKT))133 convergence rates, respectively. So far, it remains unknown whether federated SGDA could achieve the same desirable convergence as FedAvg. In this paper, we show that our SAGDA algorithm and FSGDA (implied by SAGDA) indeed achieve the (11 (T///mKT) convergence rate, matching that of FedAvg.
setting, studies
rate of
3 Problem statement and algorithm design
We consider general min- max optimization problem in federated learning setting as follows:
min max f(x,y) min max M
1
Σ f((,y), RE[M]
XER yeRd
XER YER
where f((xy) := E, {:) is the local loss function associated with local data distribu- tion D, and M the number of workers. Similar to FL., these exist two main challenges federated min-max optimization: 1) datasets are generated locally at the clients and generally non-i.i.d., i.e., D, & D,, for * j: 2) potentially only a subset of clients may participate in each communication round, leading to partial client participation.
3

---

problems. Before presenting the algo- rithms and their convergence analysis, we first state several assumptions.
In this paper, we focus on general non non-convex- PL
Assumption 1. (Lipschitz Smooth) fi(x. y) is sm-othhhh i.e., there exists constant Ly > 0, that (x), - 82)2 - LJ (I|x- xxll2 3 + lly: y2ll²), Vx1, V1.22 R E [M.] Assumption 2. (Polyak- (PL.) Condition) There exists constant ps > 0 such that Vx
[x,)(xx, 2 2μ max (f(x, [[x f(x,)).
Further, we assume the stochastic gradients with respect to x and y in each local update step at each client are unbiased and have bounded variances.
Assumption 3. (Unbiased Local Stochastic Gradient) Let 5¹ be a random local data sample at client The local stochastic gradients with respect and y are unbiased and have bounded variances:
f. y, 5.] = y),, E (( E [IV - (xx,(xx S ozy where the expectation is taken over local distribution D.-
(xf((x,))11) on.
To analyze the convergence performance of min-max algorithms, we define surrogate function & for the global minimization as follows: (xx := maxy y(.y). We will use as a metric to measure the performance of an algorithm on min-max problems, and the goal is to find an approximate stationary point of & efficiently. Then, we can conclude from previous works (see Lemma A.5 39] or Lemma that & is L-smooth, where L == L5 L//Pu.
4.3 (38)
Definition (Stationarity). For a differentiable function 4 is an e-Stationary point if ([)( S e. Definition 2 (Complexity). The communication and client sample complexity are defined as the total number of rounds and stochastic grudients per client to achieve an e-stationary point, respectively.
3.1 The Stochastic Averaging Gradient Descent Ascent (SAGDA) Algorithm
To solve Problem ( FedAvg could be naturally extended to federated min-max problems by applying SGDA with multiple local update steps in primal and dual variables respectively. However, current show that there exists two limitations: 1) limited data heterogeneity is often assumed, e.g., bounded gradient dissimilarity assumption; 2) communication complexity is unsatisfactory. In this paper, we propose the SAGDA (stochastic sampling averaging gradient descent ascent) algorithm by utilizing the assembly of stochastic gradients from (randomly sampled) clients as control variates to mitigate the effect of data heterogeneity in federated min-max problems. As will be shown later, SAGDA is able to achieve better communication complexity under arbitrary data heterogeneity.
results 13 [5]
As illustrated in [ SAGDA contains the following two stages:
1. On the Server Side: In each communication round, the server initializes the global model (xt, yt) at 1 = 0 or updates the global model accrodingly when > 0 (Line 3). Specifically, for / >> O. upon the reception of all returned parameters from round t - the server aggregates them using global learning rates J2 and 77.g for x and y, respectively. Then server samples a subset of clients S, to participate in the training and broadcast the current global model (x,, Yr) these clients (Line 4). Here, we follow the same common assumption on client participation as in FL: the clients are uniformly sampled without replacement and a fixed-size subset (i.e., |S, m) is chosen in each communication round. A key step here is to construct the control variates (Vz: Vy. Va,i. Vg.i) for server and client. Afterwards, the primal and dual variables alongside their control variates are transmitted to each participated client E S₁ (Line 7).
2. On the Client Side: Upon receiving the latest global model yz), each client synchronizes its local model (Line 10). Then, each client performs K local updates for x and y simultaneously (Line 11). Upon the completion of local computations, the new local model is sent the server.
We provide two options in SAGDA. First, in each communication round, client and server need to respectively obtain control variates (Var,, Vy,a) and (V.,, Vy)) for "variance reduction" " purpose in primal variable and dual variable y (Lines 5 and 6). Option I requires each client to maintain the control variates (Va,a, Vy,i) across rounds locally (Line 12). As a result, (Vz, Vy) are constructed iteratively (Line 5). In Option II, (Vz.á, Vy.)) are instantly calcuated by another round of communication, and

---

Algorithm The Stochastic Averaging Gradient Descent Ascent (SAGDA) Algorithm.
1: for 0.... T
do
2: for Server do
3:
Initialize Xo, Yo for t 0, update global model from previous round for t O:
X = x n2.9 Eiss.,, x
1-1, X(-1
K+1
Lis K+1 -1-1)
Yr Y 1y.9
4: Randomly samples subset St of clients with |Sp] = m.
5:
Option I: Construct sampling averaging Vei Vy from the return in the previous round:
V, + To Eies. Avz, Vy -.=V Vy Eies. Avg.i.
6:
Option II: The server sends current parameters Z1 = (x), to clients in St and collects stochastic gradients:
Vz,i = VzJi(2i,, S.,), Vy.i = VyJi(zz,,..)) V, 1 m Eies, Va,i. V. = m Eies, Vy.i- Send (xe: yr) and (Va, Vy) to each client i E St-
7:
8:
end for
9:
for Each client i E St do
10:
Synchronization: x Xt, y2. Yz and receiving Va,to ya Local updates (k E [K]):
x IV, (cf. Eq. for v
v
Ye A+1 y + Vy (cf. Eq. 3 for v v.));
12:
Option I:
Calculate: Ve,a Vali(ze Er,i), usi = Vysi(Ze, St,i).
K+1 Send (xf,1 .Y..
)+ and (Avz,i, Avy.)) (Vaii Va,is Vy ve.))
to server.
Assign: V2,1 = Va.i Va.i = Ve.i.
13:
Option II: Send (x(** .i,
K+1) to server
14: end for
end for
then (Va.s, Vy.s) i are constructed accrodingly (Line 6). We note that Option needs client to be stateful and thus being more challenging to implement in cross-device FL (34] while Option II may incur extra communication overhead due to the need for one more communication session, although the total communication size remains the same. In the local computation phase, each participated client performs steps (Line 11) based on Eq. (2) and (3), which can be interpreted as "variance reduction." Here, we use 2 == (xl yf, for notational simplicity.
h 2, Vefilzi, chis) V2,1 + Vz1
(2)
M. VyJi(zi st, Vy. + Vy.
(3)
In classic variance reduction methods, the key idea is to utilize full gradient (or approximation) to reduce the stochastic gradient variance the expense of high computation complexity compared to SGD. Note that, in federated learning, the gradient dissimilarity (due to data heterogeneity) a crtical challenge and more problematic than stochastic gradient variance. Therefore, we calculate 2-tuple (Vz.e: v) of stochastic gradients from all clients as control variates to mitigate the potential gradient deviation due data heterogeneity. Note that SAGDA does not require full gradient calculation for each client. With the help from the local steps in (2) and (3), each client no longer generate large deviation in local updates even with arbitrary data heterogeneity. The reason that, for small local learning rates, the local steps in each client could be approximated by
VaSi(al, V (yfi sh.) Vg.i
Va.i
v Vx.
y.a R Vy.
In other words, SAGDA mimics mini-batch SGDA the centralized learning by using an approxi- mation of mini-batch stochastic gradient for the updates. As result, SAGDA is able to provide
5

---

desirable convergence rate, while allowing arbitrary data heterogeneity. We state the convergence rate result of SAGDA as follows:
Theorem 1 (Convergence Rate of SAGDA). Under Assumptions 7 10
define Ct ((xx)
1 (x,, y1), the output sequence {xi} generated by SAGDA satisfies:
For Option with learning rates nn 111, ly.g. and ny, satisfying
8K(K - 1)(2K - 11)13 max
(vE,t, max
n1 1
442T.3 122 (1/h + (
(ar + a2 1. K2 (1/² + n)) 160 (v + nig)) 1.3 2 0,
10 7 K - 4azk 1/=
- [ai + k24L3k²
(1 + n 40K nz 2 0,
1
Th I.3
7
4azk B/y
- [01 + az (1 + m 40K ny. 2 0,
20
f7 p
where 01 KL3
(31
22 n2
+ 20 nv) and a2
L + : + +1+
M m
M it holds that
2 (Lo - C.) Th KT
Iif 10
9
L
4
(n 2 + 11 n200)) +
T
local update error
optimization error
statistical error
where Ui is defined as follows:
Nh )
1/
31
fl
+
2 L
Lif
+2 4L3K 10
1o ns
[20K* (12, + n
20
20
T/x
For Option II with learning rates Bg.g. nr Ny.s. and Nyd satisfying
8K(K- - 1)(2K T) max (n Ny1) S 1,
10 7rK
2 (2 L
T.f
n R2 + +40K2
2 0.
10
(1
Th 17
Ky
L + 40K 440K2 2 0,
20
my n²²
5
where by = L3
31 nre K
ny K +
L + 1o
Ls
n2 + 1 K² it holds that
Σ E
2Co Lc.) naK KT
(++
Ls
9
02
+
F o
+ t/2.
10
m
10
where 4/2 defined as follows:
4/2 L7
31
K
nu 20
K 2
L+
L1j 10 naK? +
nh K² bs
1
[16 + 1)] (12,02 + ny)10)
20
The
n
Here 7h -Z,, and By My... The convergence rate results in Theorem contain three terms: optimization error, statistical error and local update error. The first two errors are similar to those in first-order stochastic methods, which are optimization errors due to initial point and statistical error originated from stochastic gradient variance. The local updates without synchronization among clients result in deviations that contribute the third error. For the learning rates, if we use sufficiently small local learning rates 72,t and Ty. it requires that 7). K = O(1) and K = O())
Based on Theorem
we immediately have the following result:

---

Algorithm 2 Federated Stochastic Gradient Descent Ascent (FSGDA) Algorithm.
1: for 1, T do
2: for Server do
3:
Initialize (xo, Yo) for t = 0, or update global model from previous round for > 0:
X; = x x 72
Σ
x1-1) -x--1
- V1-1
Σ
Y St-1,
vt-1)
K+1
iES
iES,
4:
The server randomly samples subset St of clients with |Sel and sends current parameters Yt).
5:
end for
6: for Each client i E St do
7:
Synchronization: x Xt, yt. = Yt-
8:
Local updates (k E [K]):
x - Tao Vx Vxfi(xx,, y SE.),
++1 yh, + nu. Vyfi
K+1 9: Send (x y
k+) to server.
end for
11: end for
Corollary 1 (Convergence Rate of SAGDA Let The O
VKT 1 T72
vm
O
/KT nu.1
S
minf 1723377 1//47174
K3//
Tyt S min m77K
m4/4117 }. and T = 9(mK)) the convergence
K3/4
rate of SAGDA is O
VmKT
Corollary 1 says that, for sufficiently many communication rounds (7 = (2m SAGDA achieves the linear speedup in both and K. In other words, the per-client sample complexity and commu- nication complexity are ((L/mme and ( 2), respectively. The per-client sample complexity indicates the benefits of parallelism the number of clients increases. The communication complexity significantly improves those in existing works by at least a (1/e)-factor (cf. Table
3.2 Special case of SAGDA: Federated stochastic gradient descent ascent (FSGDA)
We note that, if we set all the control variates to zero, SAGDA reduces to the federated stochastic gradient descent ascent (FSGDA) method, which natural extension of FedAvg and SGDA to federated min-max learning"" We show that much improved convergence rate results of FSGDA can be directly implied by SAGDA.
For fair comparison with existing works, we also adopt the same bounded gradient dissimilarity assumption in [1415] [5] bound the second moment between gradients of local and global loss functions (i.e., quantifying data heterogeneity).
Assumption (Bounded Gradient Dissimilarity) There exist two constants Oz.G 2 0 and g.G 2 such that E [||V.f((x.))
vxf(xx < o². and E [ v,f(x,)))1 0² G.G.
Assumption is commonly-used assumption quantify the data heterogeneity [14 15 Based the results and analysis of SAGDA, we can show the following convergence results for FSGDA:
Theorem 2 (Convergence Rate for FSGDA). Under Assumptions to (x,, Yx), ), the learning rates 72 na, Qy.9- and Ny,1 satisfy:
define L. = $(x.)
8K(K 1)(2K 1) max (122 11 S 1, 1/2
01 - 03 30,4 2
7g a4 40L, 3 K2 2 2 0,
nh 401, K 12 as 400. A...KKKK K2 1/, 2 0,
02
03
7l
'Our FSGDA is in fact a generalized version of local FSGDA 14 15 as our FSGDA has two-sided learning
rates and client sampling. If 1)..9 No.s our FSGDA is exactly the same the standard FSGDA.

---

(10 - 2(2L + b. , = ( bL
De 1
where
01 =
as
[81
20 + (2L + ( m) and = (3) + L)SKH,K, then the output sequence {x+} gener-
ated by FSGDA satisfies:
T-1
2 (Lo LT)
21 m
L+ lig
T.g 5mn
o +
3/3
T
nrKT
100
local update error
sampling
optimization
statistical error
Here, v/3 and dh4 are defined as follows:
23 2 ( |oL + +as Yu 13)
4002m2,0020 + 40K2 n.G + +5Km 5k
1/4 = (2L -(2
() (1-
2 M 20 + 5m Ly
m
2
K lh T/2
(1-
m
og.00
M
The convergence rate result in Theorem 2 contains four parts. The first three terms are similar the errors in SAGDA analysis. However, one difference is that the local update error heavily depends on the data heterogeneity parameter ox,G and ogG.. Specifically, the error grows at least linearly with respect to the local step terms stochastic variance of and oy and quadratically in the gradient dissimilarity 2².G and a dy.-- This indicates that data heterogeneity is more problematic than stochastic gradient variance, yielding larger error in local updates and thus necessitating smaller local steps. Fortunately, this eтror is associated with the square of local learning rates ne and ny.1 So, with sufficiently small local learning rates, 1/1 can be easily reduced. In other words, under bounded gradient dissimilarity (i.c., data heterogeneity), small local learning rates render controllable local update error among clients.
Partial client participation by random sampling without replacement is unbiased estimation of the global loss function and has a bounded variance, contributing to the third term 1/4. Will full clients participation (m M), this error term can be reduced zero through our analysis.
Theorem 2 implies a new result for FSGDA: if we use sufficiently small local learning rates under full client participation, FSGDA achieves similar convergence rate to those of SGD and SGDA:
Corollary (Convergence Rate of FSGDA under Full Client Participation). Considering full client participation (m = M), let The = O
KKT The =
O
VKT
Tad S (mT))/KKr Ny. To. S
(mT) g/554 and T (2mK)) the convergence rate of FSGDA algorithm is: O <MKTT
This convergence rate indicates the linear speedup effect in terms of both M and K. However, note that this is subject to learning rates constraints, which does not allow arbitrarily many local steps. Specifically, the number of local step FSGDA is on the order of K O /M). Hence, FSGDA achieves per-client sample complexity O and communication complexity O ( ). We improve the ofte-oof-the-rt communication comoplexity from ( in 15 to ( in our paper.
For partial client participation m < M, however, FSGDA can only have the following convergence rate under appropriate learning rates.
Corollary (Convergence Rate of FSGDA under Partial Client Participation). Let Ti
O(
). Na.1 S (mTT)// and fy. S (mTT)/44' the convergence rate of FS- GDA algorithm is mLI)
2 VTK ), = ( Lm
VTK
For partial client participation, we note that only the linear speedup in is achievable and the linear speedup in K is not achievable due to the impact of sampling variance. According to previous works in federated minimization problem, the convergence bounds also have this observation (28 3T). To our knowledge, we are not aware of any existing results on linear speedup in K with partial client participation. We will leave this as an open problem in our future studies.
4 Numerical Experiments
In this section, we conduct numerical experiments using two machine learning problems (Logistic Regression and AUC Maximization) verify our theoretical results for SAGDA as well FSGDA.
8

---

SLODA spleed
SARDA enttard
SAGONeastand SaGawasstons
16
54000 earland
CD EU-MA---
20
10400
FSGDA
CD His
do 1é0
100
Corn muntroatioon
Communicaton
Communication round
Communical
(a) Logistic regression un- (b) Logistic regression (c) AUC maximization (d) AUC maximization der "a9a" dataset.
under "MNIST" dataset. Figure I: Comparisons of federated min-max learning algorithms in terms of communication rounds.
under "MNIST" dataset. under "a9a" dataset.
SA-E eptiinn Spttnn
10
SIGRA oqtenz
iScoA
CD HICEE
SAADA aprinn
Maike
-3
CO-MACE-
Purelli SCDA
ParalalSG2A
10"
60
0.3
04
03
0.5
1.6
1.5
09
0.5
30
1.5
Sample complesity
Sample complextty
Sample complexity
Sample complesity
(a) Logistic regression un- (b) Logistic regression (c) AUC maximization
(d) AUC maximization un- der "MNIST" dataset.
der "a9a" dataset.
under "MNIST" dataset. under "a9a" dataset.
Figure Comparisons of federated min-max learning algorithms in terms of sample complexity.
Due to space limitation, detailed discriptions for machine learning models and additional experiments for parameter tuning are relegated to our supplementary material.
We compare our algorithms using Parallel-SGDA [4 38). CD-MA [13) and CD-MAGE+ [3] as baselines in our experiments. We note that the CD-MAGE+ method is the state-of the-art federated minimax algorithm.
Parallel-SGDA 114 38): Parallel-SGDA is the parallel version of the stochastic gradient descent Aascent(SGDA algorithm. Each agent updates its local parameters as: X;-1; Xt, T2, V. yt, fr,;) and yr+1, - ix
CD-MA [3): Each agent updates its local parameters with mini-batch estimators. The server
computes X,+1 = + Eies, K+1 Vx+1 y: + m Eies, y where S, is the subsets of clients.
CD-MAGE+ [13]: Each agent updates its local parameters with a recursive nomentum-basee estimator. The server does the same procedure as in CD-MA.
1) Datasets: We test the convergence performance of our algorithms using the "a9a" dataset [40 and "MNIST" [4I] from LIBSVM repository. The "a9a" " readily contains two categories for classification. To generate data with two categories for "MNIST", we split it into two classes by treating the number "1" class as the positive class and the remaining as the negative class. We randomly selected 5000 data points from the positive class and 5000 data points from the negative class in the data repository. To generate heterogeneous data, the training data is first sorted according to the original class label and then equally partitioned into 100 workers so that all data points
client from the same class.
2) Parameter Settings:
We initialize all algorithms at the same point, generated randomly from the random number generator in Python. The learning rates are chosen as 7/r, fly, 10 Me.g
ly. = 2, local updates K = 10. We have m = 100 clients and each client has n = 100 samples.
3) Performance Comparisons: As shown in Fig. we conduct experiments by using distributionally robust optimization with non-convex regularized logistic loss and by AUC maximization on both "a9a" and "MNIST" datasets. We compare the convergence results in terms of the number of communication rounds and sample complexity. For better visualization, the results are smoothed by averaging the values over window of size five. It can be seen from Fig. 2 that SAGDA converges

---

faster than the baseline algorithms (CD-MA, CD-MAGE+, Parallel-SGDA) in terms of the total number of communication rounds. We can also observe that SAGDA have lower sample complexity than all the other algorithms. As mentioned in Section. 3 the local learning rates are necessarily small since they are used to control the local update errors. Thanks to the relatively large step-size Tz..: Vy. in SAGDA, the actual learning rate T Ta, M/. and f/y = yy,1 Ty.a help us achieve better convergence performance in each communication round. Our experimental results thus verify our theoretical analysis that SAGDA is able to achieve both low sample and communication complexities.
5
Conclusion
In this paper, considered federated min-max learning with the goal of achieving low communi- cation complexity. We proposed a new algorithmic framework called SAGDA, which i) assembles stochastic gradient estimators from randomly sampled clients as control variates and îi) leverages two learning rates on both server and client sides. We showed that SAGDA achieves a linear speedup in terms of both the number of clients and local update steps, which yields O(c-2) communication complexity that is orders of magnitude lower than the state of the art. Also, by noting that the standard federated stochastic gradient descent ascent (FSGDA) is in fact a special case of SAGDA, also obtained an O communication complexity result for FSGDA. Extensive numerical experiments corroborated the effectiveness and efficiency of our algorithms.
Acknowledgements
This work has been supported in part by NSF grants CAREER CNS-21102593 CNS-2112471) ECCS-2140277, and CCF-2110252.
References
[1] Y. Ying, L. Wen, and S. Lyu, "Stochastic online auc maximization," Advances in neural information processing systems, vol. 29, pp. 451-459, 2016
[2] M. Liu, Z. Yuan, Y. Ying, and Yang, "Stochastic auc maximization with deep neural networks," International Conference on Learning Representations, 2019.
[3] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, "Towards deep learning models resistant to adversarial attacks," in International Conference on Learning Representations, 2018.
[4] A. Sinha, H. Namkoong, and Duchi, "Certifying some distributional robustness with principled adversarial training," in International Conference on Learning Representations, 2018.
[5] I. Goodfellow, J. Pouget-Abaade Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, "Generative adversarial nets." Advances in neural information processing systems, vol. 27, 2014.
[6] Z. Guo, M. Liu, Z. Yuan, L. Shen, W. Liu, and T. Yang, "Communication-eficceen distributed stochastic auc maximization with deep neural networks." in International Conference on Machine Learning. PMLR, 2020, pp. 3864-3874.
[7] 7.. Yuan, 7. Guo, Y. Xu, Y. Ying, and T. Yang, "Federated deep auc maximization for hetero- geneous data with a constant communication complexity," arXiv preprint (02iv:200200466: 2021.
[8] A. Reisizadeh, F. Farnia, R. Pedarsani, and A. Jadbabaie, "Robust federated learning: The case of affine distribution shifts," arXiv preprint wxXiv20066.08907 2020.
[9] A. Brock, J. Donahue, and K. Simonyan, "Large scale gan training for high fidelity natural image synthesis," arXiv preprint arXiv: 1096, 2018.
[10] S. Augenstein, H. B. McMahan, D. Ramage, S. Ramaswamy, P. Kairouz, M. Chen, Mathews et al., "Generative models for effective ml on private, decentralized datasets," arXiv preprint 1XX1:19111006799 2019.
[11] M. Rasouli, Sun, and R. Rajagopal, "Fedgan: Federated generative adversarial networks for distributed data," arXiv preprint 2tfi:20000.022266 2020.
10

---

[12] H. B. McMahan, E. Moore, D. Ramage, S. Hampson et al., Commuuiictiion-efieiee efficient learning of deep networks from decentralized data," arXiv preprint arXiv:1602.0562) 2016.
[13] J. Xie, C. Zhang, Z. Shen, W. Liu, and H. Qian, "Efficient cross-device federated learning algorithms for minimax problems," arXiv preprint
2021.
[14] Y. Deng and M. Mahdavi, "Local stochastic gradient descent ascent: Convergence analysis and communication efficiency." in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 1387-1395.
[15] Sharma, R. Panda, G. Joshi, and P. K. Varshney, "Federated minimax optimization: Improved convergence analyses and algorithms." in International Conference Machine Learning. PMLR, 2022.
[16] B. McMahan, F. Moore, Ramage, S. Hampson, and B. A. y Areas, "Communication-efficeeen learning of deep networks from decentralized data," in Artificial intelligence and statistics. PMLR, 2017, pp- 1273-1282.
[17] S. U. Stich, "Local sgd converges fast and communicates little," arXiv preprint 1rXiv:1805.09765 2018.
[18] H. Yu, S. Yang, and S. Zhu, "Parallel restarted sgd with faster convergence and less communica- tion: Demystifying why model averaging works for deep learning." in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, 2019, pp. 5693-5700.
[19] J. Wang and G. Joshi, "Cooperative sgd: A unified framework for the design and analysis of communication-efficcent sgd algorithms," arXiv preprint arXiv:1808 1xXi::888.005777 07576, 2018.
[20] S. U. Stich and S. P. Karimireddy, "The freor-feedbac framework: Better rates for sgd with delayed gradients and compressed communication," arXiv preprint arXiv: 1909.05350, 2019.
[21] T. Lin, S. U. Stich, K. K. Patel, and M. Jaggi. "Don't 't use large mini-batches, use local sgd," 07211, 2018.
arXiv preprint
[22] A. Khaled, K. Mishchenko, and P. Richtárik, "Better communication complexity for local sgd," arXiv preprint arXiv: 1909.04499 2019.
[23] F. Zhou and G. Cong, "On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization," arXiv preprint (xXiv:1708000010 2017.
[24] Sattler, S. Wiedemann, K.-R. Müller, and W. Samek, "Robust and communication-eff efficiient federated learning from non-iid data," IEEE transactions on neural networks and learning systems, 2019.
[25] Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra, "Federated learning with non-iid data," arXiv preprint arXiv:
2018.
[26] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, "Federated optimization in heterogeneous networks," arXiv preprint arXiv:1812.06127 2018.
[27] J. Wang, V. Tantia, N. Ballas, and M. Rabbat, "Slowmo: Improving communication-efficcent distributed sgd with slow momentum," arXiv preprint arXiv:1910.0064 2019.
[28] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and Suresh, "SCAFFOLD: Stochastic controlled averaging for federated learning," in Proceedings of the 37th International Conference on Machine Learning, ser. Proceedings Machine Learning Research, H. D. III and A. Singh, Eds., vol. 119. PMLR, 13-18 Jul 2020, pp. 5132-5143.
[29] L. Huang, Y. Yin, Z. Fu, S. Zhang, H. Deng, and D. Liu, "Loadaboost: bassd adaboost federated machine learning on medical data," arXiv preprint arXiv:1811.12629, 2018
[30] E. Jeong, S. Oh, H. Kim, J. Park, M. Bennis, and S.-L. Kim, coamuumication-effccin on- device machine learning: Federated distillation and augmentation under non-iid private data," arXiv preprini arXiv: 18/ I. 1479, 2018
[31] H. Yang, M. Fang, and J. Liu, "Achieving linear speedup with partial worker participation in non-lID federated learning." in International Conference on Learning Representations, 2021.
[32] Khanduri, P. SHARMA, H. Yang, M. Hong, Liu, K. Rajawat, and P. Varshney, "STEM:
A stochastic two-sided momentum algorithm achieving near-optimal sample and communica- tion complexities for federated learning," in Thirty-Fifih Conference on Neural Information Processing Systems, 1021.
11

---

[33] H. Yang, X. Zhang. P. Khanduri, and J. Liu, "Anarchic federated learning," in International Conference on Machine Learning. PMLR, 2022. pp. 331-22 363.
[34] Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings el al., "Advances and open problems in federated learning," arXiv preprint
2019.
[35] J. Neumann, "Zur theoric der gesellschaffsspielee" Mathematische annalen, vol. 100, no. 1,
pp. 295-320, 1928.
[36] A. Wald, "Statistical decision functions which minimize the maximum risk," Annals of Mathe- maticy, pp. 265-280, 1945.
[37] H. Rafique, M. Liu, Q. Lin, and T. Yang, "Weakly-conyex-coneee min-max optimization: provable algorithms and applications in machine learning." Optimization Methods and Software,
pp. 1-35, 2021.
[38] T. Lin. C. Jin, and M. Jordan, "On gradient descent ascent for nonconvex-conee minimax problems," in International Conference Machine Learning. PMLR, 2020, pp.
[39] M. Nouiehed, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn, "Solving class of non- convex min-max games using iterative first order methods," arXiv preprint /902..00000000 2019.
[40] C.-C. Chang and C.-J. Lin, "Libsvm: a library for support vector machines," ACM transactions on intelligent systems and technology (TIST), vol. 2, no. 3, pp. 1-27, 2011.
[41] Y. LeCun, C. Cortes, and C. Burges, "Mnist handwritten digit database." Available: http://yann. lecun. com/exdb/mmnist, 1998.
[42] H. Karimi, J. Nutini, and M. Schmidt, "Linear convergence of gradient and mooiimal-gradicn methods under the pojyak-lojaseewicz condition," in Joint European Conference Machine Learning and Knowledge Discovery in Databases. Springer, 2016, pp. 795-811.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section D
(b) Did you describe the limitations of your work? [Yes] We need a set of control variates to transmit in each round.
(c) Did you discuss any potential negative societal impacts of your work? [No] As theoretical paper towards further understanding of federated min-max optimization, we do not a direct path any negative applications.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
3
(b) Did you include complete proofs of all theoretical results? [Yes] See Section
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See detailed instructions Section 4 and Appendix, but codes are private.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and Appendix.
(c) Did you report error bars (e.g., with respect the random seed after running experi-
ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
12

---

(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "xsXK1RwGmK", "reviewer": "Reviewer_ACTs", "summary": "The authors provide a variance reduction algorithm SAGDA for federated min-max optimization which covers Federated SGDA as a special case. They analyze the theoretical convergence and communication costs of these algorithms improving upon existing rates and matching that of federated convex optimization, obtaining the \"linear speedup in the number of workers\". Further, they compare these algorithms against existing baselines for federated min-max optimization and obtain better performance empirically.\n", "questions": "- What is the effect of $\\kappa$ in the convergence rates and how does it compare to other existing federated min-max algorithms?\n- How does SAGDA compare to SCAFFOLD? Is this comparison equivalent to that of comparing GDA methods to GD methods in the centralized setup or does federation change something?\n- What are the key ideas in the proof technique which allow for better rates? From what I could understand in the appendix, the authors use the Error-Feedback framework with control variates for the update steps of $x$ and $y$, extending that of SCAFFOLD, but I would like to know if there were additional ideas needed for the proof to go through?\n", "limitations": "Most of the suggested improvements have been mentioned in Strengths and Weaknesses.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The proposed algorithm SAGDA achieves best possible convergence and communication under standard assumptions, and can also handle arbitrary client heterogeneity \n- Using the analysis of SAGDA for Federated SGDA provides better convergence rates over existing analyses.\n- The experimental results sufficiently validate the theoretical rates, and SAGDA outperforms existing methods.\n\n### Weaknesses\n- Presentation : The presentation of results and their discussion could be improved substantially. Especially for Theorems 1 and 2, most of the math could be simplified and moved to the appendix keeping only $\\mathcal{O}(\\cdot)$ rates in the main paper. Further, there were several typos in the equations or terms that were not defined( some of them are mentioned in minor issues) . The paper would greatly benefit by improving the presentation.\n- Comparison to SCAFFOLD[1] : SAGDA seems to be the extension of SCAFFOLD to min-max optimization. Similar to SCAFFOLD, the analysis technique obtains the best possible rates for the control-variate free version, Federated SGDA. Therefore, I feel it is important to appropriately credit the SCAFFOLD paper. Further, a comparison of SCAFFOLD v/s SAGDA can help establish the difference between variance-reduced methods in convex optimization and min-max optimization.\n- Effect of condition number $\\kappa$: It would have been interesting to see if SAGDA achieves optimal $\\kappa$-dependence in addition to improving the sample and communication complexity.\n- Experiments on deep learning tasks: Since min-max optimization is a core component in training GANs, and the performance of variance reduction methods in deep learning is not easy to handle [2], conducting a few toy experiments on deep learning tasks would further improve the paper.\n\n### Minor Issues \n- Proof Idea:  Since the theoretical results of this paper improve upon the existing rates, even for Federated SGDA, highlighting the key ideas in the convergence proof which allow this improvement would help understand what previous analyses missed.\n- Extension to different classes of non-convex objectives: The authors only consider nonconvex-PL objectives, while the analysis technique might also be applied to more classes, for instance, those in  Table 1 in [3]). It would also be interesting to see if this has the same effect of mitigating heterogeneity and if it improves upon existing rates.\n- Typos and issues with presentation: \n    - In Section 2 (Related Work), Lines 101-104, it is not clear what $K$ is. Later in the paper, it is defined as the number of local steps, but it would be better to mention this here as well.\n    - Eq.(2) $\\nabla_x f_i(z_{t,i}^j, \\xi_{t,i}^k)$ -> $\\nabla_x f_i(z_{t,i}^k, \\xi_{t,i}^k)$\n    - Unnumbered Eq after Line 171, there is an additional $\\xi_{t,i}^k$.\n\n### References \n1. Karimireddy, S.P., Kale, S., Mohri, M., Reddi, S., Stich, S. &amp; Suresh, A.T.. (2020). SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. *Proceedings of the 37th International Conference on Machine Learning*, in *Proceedings of Machine Learning Research* 119:5132-5143 Available from https://proceedings.mlr.press/v119/karimireddy20a.html.\n2. Defazio, A., & Bottou, L. (2019). On the Ineffectiveness of Variance Reduced Optimization for Deep Learning. In Advances in Neural Information Processing Systems. Curran Associates, Inc..\n3. \nSharma, P., Panda, R., Joshi, G. &amp; Varshney, P.. (2022). Federated Minimax Optimization: Improved Convergence Analyses and Algorithms. *Proceedings of the 39th International Conference on Machine Learning*, in *Proceedings of Machine Learning Research* 162:19683-19730 Available from https://proceedings.mlr.press/v162/sharma22c.html.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kLRb62Lmrzz", "reviewer": "Reviewer_oLiX", "summary": "-----After rebuttal\n\nI thank the author for answering my two questions. Given my assessment of the novelty and significance of the paper, I am keeping the score as is.\n\n-----Original review\n\nThis paper studies the federated min-max problems which has applications to distributed robust optimization for instance. Two federated versions of the celebrated SGDA algorithm are explored by leveraging standard technique. SAGDA which uses global variance reduction by employing control variates and FSGDA which only employs client sampling and local updates (the latter is an existing method). The convergence of these methods are analyzed for nonconvex-PL min-max problems and it is shown they achieve similar iteration and communication complexity as those of FedAvg for federated minimization problem.", "questions": "1. It seems the CD-MAGE+ algorithm achieves a superior sample and communication complexity compared to the result of the present paper. Can you elaborate on the comparison of the two? (answered in rebuttal)\n\n2. The title is misleading as $O(\\epsilon^{-2})$ is already achieved by the prior work.  (answered in rebuttal)", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. Improving sample and communication complexity over [14]\n\nWeakness\n1. The results while theoretically appleaning does not seems surprising. The proposed algorithm and the proofs seem to be an application of the known techniques in federated and stochastic optimization.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IVSeWGV6dp3", "reviewer": "Reviewer_YJdZ", "summary": "The paper provides a new algorithm, SAGDA, for federated learning in min-max learning, and proves a theoretical communication complexity guarantee that significantly improves upon previous results (without harming sample complexity). The main idea of SAGDA is to leverage new control variates, and to update a sample of them, based on the variations of the clients’ gradients. In particular, the control variates are used by the clients to update their local models, thereby avoiding model drift. Interestingly, this also allows the authors to remove the bounded gradient dissimilarity assumption, which was needed in prior works. Empirical results also comfort the effectiveness of SAGDA.\n\nThe paper also shows the same communication complexity for the standard FSGDA algorithm, by proving that FSGDA is a special case of SAGDA where the control covariates are canceled.\n", "questions": "It is not clear to me if the techniques of the paper apply to minimization learning in general (and not just min-max learning). Could SAGDA be easily generalized into SAGD? (in particular, the use of control variates) \n\nIf not, it would be interesting to discuss why not.", "limitations": "The paper is fully dedicated to machine learning performance, under the assumption that it is desirable to generalize collected data. This clearly raises major societal concerns, if the collected data is undesirably biased, or if it is harmed by poisoning data attacks. Similarly, since it relies on averaging clients’ inputs, SAGDA is arbitrarily manipulable by malicious clients. On the Internet, such malicious clients are ubiquitous.\n\nI believe that the authors have a responsibility to highlight this, and to warn against the use of such algorithms in environments where the quality of the data is not sufficiently guaranteed, or when the clients are not all extremely trustworthy. A discussion on the need for developing Byzantine-resilient variants of SAGDA would be ethically productive.\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Given the increasing cost of communications in federated learning, the paper provides an original and significant contribution to the design and understanding of efficient federated learning algorithms.\n\nI have however found the paper hard to read, especially as the authors aim to present two variants of SAGDA at once. I would encourage the authors to first focus on only one flavor of SAGDA and to make it as clear as possible for the reader. The other variant may then be briefly discussed in the main paper, and described more thoroughly in the appendix. Moreover, I would have found it useful to also include Equations (2) and (3) directly in the algorithm.\n\nI also feel that too much space is dedicated to the case of FSGDA, which seems less important to me than SAGDA. I would have found it more valuable to dedicate more space to explaining the intuition of SAGDA.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept