Federated Minimax Optimization with Client Heterogeneity
Authors: Pranay Sharma
Rohan Panda
Gauri Joshi
Venue: Accepted by TMLR ()

Abstract: Minimax optimization has seen a surge in interest with the advent of modern applications such as GANs, and it is inherently more challenging than simple minimization. The difficulty is exacerbated by the training data residing at multiple edge devices or \textit{clients}, especially when these clients can have heterogeneous datasets and heterogeneous local computation capabilities. We propose a general federated minimax optimization framework that subsumes such settings and several existing methods like Local SGDA. We show that naive aggregation of model updates made by clients running unequal number of local steps can result in optimizing a mismatched objective function -- a phenomenon previously observed in standard federated minimization. To fix this problem, we propose normalizing the client updates by the number of local steps. We analyze the convergence of the proposed algorithm for classes of nonconvex-concave and nonconvex-nonconcave functions and characterize the impact of heterogeneous client data, partial client participation, and heterogeneous local computations. For all the function classes considered, we significantly improve the existing computation and communication complexity results. Experimental results support our theoretical claims.

Published in Transactions on Machine Learning Research (12/2023)
Federated Minimax Optimization with Client Heterogeneity
Pranay Sharma
pranayshS@ndreew.c edu
Deportment of Electrical and Computer Engineering Carnegie Mellon University
Rohan Panda
rohanpaunSanddru..com cww.. edu
Department of Electricol and Computer Engineering Carnegie Mellon University
Gauri Joshi
goartfSiondre.ccm..com
Deportment of Electriool and Computer Engineering Cornegie Mellon University
Reviewed OpenReview: https: opwprevveeeevveeeeeeemmee net/ forum? id= dnUmmiihhhLL
Abstract
Minimax optimization has seen surge in interest with the advent of modern applications such as GANss and it is inherently more challenging than simple minimization. The difficulty is exacerbated by the training data residing at multiple edge devices or clients, especially when these clients can have heterogeneous datasets and heterogeneous local computation capabilities. We propose a general federated minimax optimization framework that subsumes such scttings and several existing methods like Local SGDA. We show that naive aggregation of model updates made by clients running unequal mumber of local steps can result in optimizing mismatched objective function phenomenon previously observed in standard federated mininization. To fix this problem, propose normalizing the client updates by the number of local steps. We analyze the convergence of the proposed algorithm for classes of nonconvex-coneave and noncomvex-monconcan functions and characterize the impact of hetcrogencous client data, partial client participation, and heterogencous local computations. For all the function classes considered, we significantly improve the existing computation and communication complexity results. Experimental results support our theoretical claims.
1
Introduction
The massive surge in machine learning (ML) rescarch in the past decade has brought forth applications that cannot be modeled as simple minimization problems. Many of these problems, including generative adversarial networks (GANs) Goodfellow et al. (2014); Arjovsky et al. (2017); Sanjabi et al. (2018), adversarial neural network training Madry et al. (2018), robust optimization Namkoong & Duchi (2016); Mohajerin Esfahani & Kuhn (2018), and fair machine learning Madras et al. (2018); Mohri et al. (2019), have an underlying min-max structure. However, the underlying problem often nonconvex, while classical minimax theory dcals almost exclusively with convex-concave problems.
Another feature of modern ML applications is the inherently distributed nature of the training data Xing et al. (2016). The data collection is often outsourced to edge devices or clients. However, the clients may then be unable (due to resource constraints) unwilling (due to privacy concerns) to share their data with a central server. Federated Learning (FL) Konečný et al. (2016); Kairouz el. al. (2019) was proposed to alleviate this problem. In exchange for retaining control of their data, the clients shoulder some of the computational load, and run part of the training process locally, using only their own data. The communication with the server is infrequent, leading further resource savings. Since its introduction, FL has been an active area of research, with some remarkable successes Li et al. (2020); Wang et al. (2021). Research has shown practical

---

Published in Transactions on Machine Learning Research (12/2023)
Table 1: Comparison of (per client) stochastic gradient complexity and the number communication rounds needed to reach an e-stationary solution (Definition 1), for different classes of nonconvex minimax problems. Here, n is the total number of clients. For a fair comparison with existing works, our results in this table are spocialized to the case when all clients (i) have equal weights (p; 1/n); (fi) perform equal number of local updates (ra r), and (iii) use the samee local update algorithm SGDA. See Table's 2 for comparison under more general settings, when (i)- do not hold.
Setting and Assumptions
Full Client Participation (FCP)
Work
System
Partial Client
Stochastic Gradient
Communication
Heterogeneity"" Participation
Complexity
Rounds
Nanconvex-Strongly-oonwww (NC-SC) NNnnoooooo Pollyk-Looysssaiiiiiieee (NC-PL): Theorem
1) Lin et al. (2020a)
O(1/e))
Sharma et al. (2022)
x
x
(1/((ne ))
O(1/c))
Yang et (2022a)
X
/
((1((ne))
0(1/()
Ours: (Corollary 1.2, Remark
V
① (1/(ne))
(1/e²
Nonconvex-Concave (NC-C): Theorem 2
(n = 1) Lin et al. (2020a)
O(1/e))
Sharma et al. (2022)
x
x
(11((ne))
o(1/e))
Ours: (Corollary 2.2)
o (1/(nc")
(1/c*)
Nonconvex- One-point-concane (NC-1PC): Theorem
Deng & Mahdavi (2021)
x
x
((1/2
(en
Sharma et al. (2022)
x
X
O(1/e))
O(1/e")
Ours: (Remark 5)
V
O (1/(ne))
(1/e²)
Individual clients can run an unequal number of local iterations, using different local optimizers (see Section 4).
benefits of, and provided theoretical justifications for commonly used practical techniques, such as, multiple local updates at the clients Stich (2018); Khaled et al. (2020); Koloskova et al. (2020); Wang & Joshi (2021), partial client participation Yang et al. (2021), communication compression Hamer et al. (2020); Chen et al. (2021). Further, impact of heterogeneity in the clients' local data Zhao et al. (2018); Sattler et al. (2019), as well as their system capabilities Wang et al. (2020); Mitra et al. (2021) has been studied. However, all this research has been focused almost solely on simple minimization problems.
With its increasing usage in large-scale applications, FL systems must adapt wide range of clients. Data heterogeneity has received significant attention from the community. However, system-level heterogeneity remains relatively unexplored. The effect of client variability heterogeneity can be controlled by forcing all the clients to carry out an equal number of local updates and utilize the same local optimizer Yu et al. (2019); Haddadpour et al. (2019). However, this approach is inefficient if the client datasel sizes are widely different. Also, it would entail faster clients sitting idle for long durations Reisizadeh et al. (2022); Tziotis et al. (2022), waiting for stragglers to finish. Additionally, using the same optimizer might be inefficient or expensive for clients, depending on their system capabilities. Therefore, adapting to system-level heterogeneity forms a desideratum for real-world FL schemes.
Contributions. We consider general federated minimax optimization framework, in the presence of both inter-client data, and system heterogeneity. System heterogeneity means the participating clients can run an unequal number of local steps, and utilize different local solvers. We consider the problem
min max x= = En y)) (I) XER yEy
(1)
where fa is the local loss of client i, pe the weight assigned client i (e.g., the relative sample size), and n is the total number of clients. We study several classes of nonconvex minimax problems (see Table 1). Further,
In our proposed algorithm, the participating clients may each perform different number local steps, with different local optimizers. In this setting, naive aggregation of local model updates (as done existing methods like Local Stochastic Gradient Descent Ascent) may lead convergence in terms of a mismatched global objective (Corollaries 1.1, 2.1). We propose simple normalization strategy to fix this problem.
2

---

Published in Transactions on Machine Learning Research (12/2023)
We achieve order-optimal state-of-the-art computation complexity and significantly improve the com- munication complexity of existing methods (Corollaries 1.2, 2.2).
Under the special case where all the clients (i) are assigned equal weights p: = 1/n in (1), (ii) carry out equal number of local updates (T; = 7 for all i), and (iii) utilize the same local-update algorithm, our results become directly comparable with existing work (see Table 1) and improve upon them as follows.
1. For sanconves-stroongy-ooneee concave (NC-SC- - Corollary 1.2) and nonconvex-PL, (NC-PL- - Remark 3) problems, our method has the ordor-optimal gradient complexity O(1/(nct)). Further, we improve the communication from (1/e²) in Sharma et al. (2022) to ((1/e²).
2. For nonconvex-coneave (NC-C Corollary 2.2) and mark 5) problems, we achieve state-of-the-art gradient complexity, while siguificantly improving the communication costs from O(1/e)) in Sharma et al. (2022) to ((1/et). For NC-1PC functions, we prove the linear speedup in gradient complexity with n that was conjectured in Sharma et al. (2022). 3. As an intermediate result in our proof, we prove the theoretical convergence of Local SGD for in--ooint-oonvr function minimization (see Lemma C.5 in Appendix C.4). The achieved convergence rate is the same as that shown for convex minimization in the existing literature Khaled et al. (2020).
(NC-1PC Re-
It is worth pointing out that our proof technique is different from existing minimax literature (e.g., Sharma et al. (2022); Yang et al. (2022b)). With all the clients carrying out the same number of local steps, the existing federated analyses rely on virtual sequences of average iterates, to mimic the proof steps in centralized scttings Lin et al. (2020a); Yang et al. (2022c). In our case, since different clients run different number of local steps, this strategy is no longer viable (see Remark 9).
2 Related Work
2.1 Single-client minimax
(NC-SC). To our knowledge, Lin et al. (2020a) is the first work to analyze a single-loop algorithm for stochastic (and deterministic) NC-SC problems. Although the O(x3/e4) complexity shown is optimal in e, the algorithm required O(c22) batch-size. Qiu et al. (2020) utilized momentum to achieve O(e convergence with O(1) batch-size. Recent works Yang et al. (2022c); Sharma et al. (2022) achieve the same rate without momentum. Yang et al. (2022c) also improved the dependence on the condition number K. Second-order stationarity for NC-SC has been recently studied in Luo & Chen (2021). Lower bounds for this problem class have appeared in Luo et al. (2020); Li et al. (2021); Zhang et al. (2021).
Sunconvex-Stronllycconeee
Sonconvex-Concart (NC-C). Again, Lin et al. (2020a) was the first to analyze a single-loop algorithm for stochastic NC-C problems, proving (ee-*) complexity. In deterministic problems, this has been improved using nested Nouiched et al. (2019); Thekumparamii et al. (2019) as well as single-loop Xu et al. (2020); Zhang et al. (2020) algorithms. For stochastic problems, Rafique et al. (2021) and the recent work Zhang et al. (2022) improved the complexity to (). However, both the algorithms have a nested structure, which at. every step, solve a simpler problem iteratively. Achieving O(e -9) complexity with single-loop algorithm has so far proved elusive.
2.2 DistributeddFedderaee Minimax
Recent years have also seen increasing body of work in distributed minimax optimization. Some of this work is focused on decentralized settings, as in Rogozin et al. (2021); Beznosikov et al. (2021b,c); Metelev et al. (2022).
Of immediate relevance to us is the foderated setting, where clients carry out multiple local updates between successive communication rounds. The relevant works which focused on convex-concave problems include Reisizadeh et al. (2020); Hou et al. (2021); Liao et al. (2021); Sun & Wei (2022). Special classes of nonconvex
The recent work Yang et al. (2022a) proposes FSCDA algorithm and also achieves ((1/²)) communication cost for NC-PL functions. However, our work more general since allow different number local steps and different. local solvers at the clients.
3

---

Published in Transactions on Machine Learning Research (12/2023)
minimax problems in the federated setting have been studied in recent works, such as, nonconvex-linen Deng et al. (2020), nonconvex-PI. Deng & Mahdavi (2021); Xie et al. (2021), and nonconvex-on--poiti-cocee. Deng & Mahdavi (2021). The complexity guarantees for several function classes considered in Deng & Mahdavi (2021) were further improved in Sharma et al. (2022). However, all these works consider specializod Tederated settings, either assuming full-client participation, or system-wise identical clients, each carrying out equal number of local updates. As we see in this paper, partial client participation is the most source of error in simple FL algorithms. Also, system-level heterogeneity can have crucial implications on the algorithm performance.
Comparison with Wang et al. (2020); Sharma et al. (2022); Yang et al. (2022a). Wang et al. (2022a) was, to our knowledge, the first work to consider the problem of system heterogeneity in simple minimization problems, and proposed a normalized averaging scheme to avoid optimizing an inconsistent objective. Compared to Wang et al. (2020), we consider a more challenging problem and achieve higher communication savings (Table 1)a. Sharma et al. (2022) studied minimax problems in the federated setting but assumed equal number of SGDA-like local updates, with full client participation. The recent work Yang et al. (2022a) considers NC-SC problem with full and partial client participation and achieves similar communication savings as ours. In comparison, our work considers a more general minimax FL framework with partial client participation, clients running an unoqual number local updates, and using different local solvers. Further, we analyze multiple classes of nonconvex-concave and improving the communication and computation complexity of existing minimax methods.
functions,
3 Preliminaries
Notations, We let II=II denote the Euclidean norm 1/-122- Given a positive integer m, the set {1,2...., m) de- noted by (m]. Vectors at client are denoted with subscript i, c.g., x,, while iteration indicos are denoted using superscripts, e.g., y(t)) or (t.kk) Given a function g, we define its gradient vector as V))(x.y)) Vxg(x,)) and its stochastic gradient as Vg(x, y: E), where & denotes the randomness.
Convergence Metrics, In the presence of nonconvexity, we can only prove convergence to an approzimate stationary point, which is defined next.
Definition (<-Stationarity). A point x is e-stationary point of a differentiable function if [Vg(x)] S Definition 2. Stochastic Gradient (SG) complexity is the total number of gradients computed by all the clients during the course of the algorithm.
In special cases, where all the clients are weighted equally (p. = 1/n, for all i E [m]) and carry out equal number of local steps T, we state the per-elient gradient complexity for comparison with existing work. See Table and Corollaries 1.2 and 2.2.
Definition 3 (Communication Rounds). During a single communication round, the server sends its global model to a set of clients, which carry out multiple local updates starting from the same model, and return their local vectors to the server. The server then aggregates these local vectors to arrive at a new global model. Throughout this paper, we denote the number of communication rounds by T.
Next, we discuss some assumptions used in the paper.
Assumption (Smoothness). Each local function fa is differentiable and has Lipschitz continuous gradients. That is, there exists constant T. such that at each client i [n], for all x, x' E Rd, and y, E e,,
(V - V.i(x y' S Ly [xxx x'1l
Assumption 2 (Bounded Diameter). The constraint set y is convex and bounded.
2Inder the conditions Ps = 1/n,, = for all for smooth minimization problems, Wang al. (2020) requires (11+3) communictionn rounds. For NC-SC problems (a harder problem class), we show an improved 0(1/22) commuication rounds.
4

---

Published in Transactions on Machine Learning Research (12/2023)
Assumption 3 (Local Variance). The stochastic gradient oracle at each client is unbiased. Also, there exist constants oL, 3r. 2 0 such that at each client i E [n], for all x,y,
B (V = (x, V Vf(( $2 (x)x + oz.
Assumption 4 (Globol Heterogeneity)). For any of non-negalive weights {wili= such that E wi 1, there exist constants Pg 2 1,0G 0 such that for all x,y,
n
w/ VV (x,)) s b
Σ wi VaJe (x,y)
+ 000
g.fs (x. y)1 s 88
+ 0 Σ wi V ff (x. y)
If all ft's are identical, we have 3g = 1, and og = 0.
Most existing work uses simplified versions of Assumptions 3, 4, assuming 31 0 and/or 8G 0.
4 Algorithm for Heterogeneous Federated Minimax Optimization
In this section, we propose a federated minimax algorithm to handle system heterogeneity across clients.
4.1 Limitations of Local SGDA
Following the success of FedAvg McMahan al. (2017) in FL, Deng & Mahdavi (2021) was the first to explore simple extension Local stochastic gradient descent-ascent (SGDA) in minimax problems. Between successive communication rounds, clients take multiple simultaneous descent /ascent steps to respectively update the min-variable x and max-variable y. Subsequent work in Sharma et al. (2022) improved the convergence results and showed that LocaISGDA achieves optimal gradient complexity for several classes of nonconvex minimax problems. However, existing work on LocaISGDA also assumes the participation of all n clients every communication round. More crucially, as observed with simple minimization problems Wang et al. (2020), if clients carry out an unequal number of local updates, or their local optimizers are not all the same, LocaISGDA (like Fed might converge to the stationary point of different objective. This is further discussed in Sections 5.1 and 5.2, and illustrated in Figure 1, where the learning process gets disproportionately skewed towards the clients carrying out more local updates.
(x((o))
-V222 (Vyfz2)
(t.1) 2
y((0)
(t.1)
Hcterogencous setting (I, < T2)
-Vaa VVyaa)
(TT))
(CT2))
2
(001)
y2
(CTz))
X2
Figure 1: FedAvg with heterogeneous local updates. The green (red) triangle represents the local optimizer of ff2), while y²) is the global optimizer. The number of local updates at the clients 71 2, 72 = 5.
5

---

Published in Transactions on Machine Learning Research (12/2023)
Generalized Local SGDA Update Rule. To understand this mismatched convergence phenomenon with naive aggregation in local SGDA, recall that Local SGDA updates are of the form
x (++1) =x x(0
7a 1=1
P.
x,61
(0) 2,81
y((+2)=
P. y,
1=1
where Tas y are the server learning rates, A 1 (t.T,
of. (x:
- 4 = 1 (y: (((
y(()) -y()) are the scaled
local updates. (t.!!") is the iterate at client after taking 70 local steps, and ne my are the client learning x;
rates. Let consider generalized version of this update rule where A x,5: y,s lincar combinations (1.h) V (x of local stochastic gradients computed by client i, 1 Ee 10-1 a
(e)
(t.a) .y; (t( <((xA)), where dj (t.R) 2 0. Commonly used client optimizers, such as, SGD, local momentum, variable local learning rates be accommodated in this general form (see Appendix A.1 for some examples). For this more general form, we can rewrite the y,y updates at the server as follows
x ((+1) = xx(1) - Di
G
(t) Xi
||a
I1,
=x(0) p=llaf 11,
la
(+)
x.
(t)
700
a
(2)
==1
oeff
((+1)) = (1( (t) + (1)
7/ Ei=1 w/gy,
where ((t) V4 (x (t.k)
yi (( (t. (t)
k=o E Idd ( contains the T stochastic gradients stacked column-
wise, a; (t) Feff is the effective number of local steps. Note that for simplicity, we assume that the constraint set y has a large diameter. However, algorithm be easily modified to accommodate projection steps. Similar to
= la; 1.0 1 (.7 JT 8x By, are the normalized aggregates of the stochastic gradients and
(1) (1)
a,
x(ee0
B
A5
v(co)
B
45.2
(((+100)
(1722)
X2
(((++10)
(t/2))
Figure Generalized update rule in (2). Note that (o (gx.) (1.) (A (4)
(.)) Also, at the server, the
(t) weighted sum Σ w.gk gets scaled by T (t)
the observation for simple minimization problems in Wang et al. (2020), we see Theorems 1, 2 that the resulting iterates of this general algorithm end up converging to the stationary point of a different objective F ""= w.fs. Further, in Corollary 1.1, we observe that this mismatch is a result of using weights w, in (2) to weigh the clients' contribution.
4.2 Proposed Normalized Federated Minimax Algorithm
From the generalized update rule, we can see that setting the weights w, equal p; will ensure that the surrogate objective F matches with the original global objective F. Setting w; = pt results in normalization

---

Published in Transactions on Machine Learning Research (12/2023)
Algorithm Fed-Norm-SGDA and Fed-Norm-SGDA+
Input: initialization x ( yy( Number of communication rounds T, learning rates: client (nh, my), server
(72. (g): #local-updates {T: (4)
Ji,t, S, S ===-
2: for t= to T' - do
3: Server selects client set C(t); sends them (x("), y())
if mod S 0 then
+
6:
Server sends x(e) = x(0) to clients in CLO)
7:
end if
(2.0) (1),, y((10) y(t) for i C(a)
for k = 0, Ti
(t) - do
10:
x (1,++1) (1,k) ai
=x:
(1.K)
V fix
(1.K)
(1,b)
.ii (1,)) ((()))
11:
y, (1,++1) =y (1,k) n
(t.h)
(x(())))) .Yi (t.R), g c(tah))
# y-update for Fod-Norm-SGDA+
12:
(1,k+1) y (1,k) + n (xx (1,b) ..!! (((A))
(t.k)
# y-update for Fed-Norm-SGDA
13:
end for
(e)
14:
Client aggrogates its gradients to compute 8x.1 8y.
(0)
(t)
(1,k)
V (x
(t,k)
.y: (( )((i))
15:
8x,
km
[
16:
gy
Σi
km
(0)
(t.b)
(8(())
,((th); c((cb))
||a
17:
By,
Zk=0
-1
11 |a
a
(t,k)
V (xx
(1.k) .y!
(1,K), ; k((.)))
18:
Clients E ((t) communicate (B Sy.s } to the server
(1)
19: Server computes aggregate vectors (gx) g using (3)
(1) Server step: fx(++)) =x x(1) off (igh) y(t+)) y
(t)
20:
off nggy
21:
end for
22: Return: x(T) drawn uniformly random from {x
of the local progress at each client before their aggregation at the server. As result, preserve convergence to a stationary point of the original objective function F, even with heterogencous (T(")) see in Theorem 1 and Theorem 2.
(t)) }, as we
The algorithm follows the steps given in Algorithm 1. In each communication round t, the server selects client set ((*) and commmicatess its model parameters <<(,)(()) to these clients. The selected clients then rum multiple local stochastic gradient steps. The number of local steps {7(") } can vary across clients and across rounds. At the end of 7(") local steps, client aggregates its local stochastic gradients into (e By,), which
are then sent to the server. Note that the gradients at client i, (V. 5 ()) )===> are normalized by ||a!" Ih, (.7(*)
where (*) la! 411 a, -.-!"--1T 11T is the vector of weights assigned to individual stochastic gradients in (t) the local updates. 3 The server aggregates these local vectors to compute global direction estimates gx .gy which are then used to update the server model parameters (x((), (t)).
For LocaISGDA Deng & Mahdavi (2021); Sharma et al. (2022), (t.b) for all i (i), [T], (1) and I|a!91, 7(0 (t)
Therefore, 8 By. simply the average the stochastic gradients computed the 1-th round.

---

Published in Transactions on Machine Learning Research (12/2023)
Client Selection. In each round the server samples |c()| clients uniformly at random without replacement (WOR). While aggregating client updates at the server, client update is weighed by ú; w;n//c(t) i.e.,
8x
Σ (EC()
Σ
uggy.
RECO
Note that [gol|g
[g
En=
w,xxii
w.
Be(e))
[g
-i== WiBy,i'
5 Convergence Results
Next, we present the convergence results for different classes of nonconvex minimax problems. For simplicity, throughout this section we assume the parameters utilized in Algorithm be fixed across t. Therefore, (t,K) (1) = ai, T = Ti eff = Teff and [c(0) = P, for all t. ag
(t)
5.1 Non-convex-Stronglee Concavee (NC-SC) Case
Assumption 5 (u-Strong-conccavity (SC) in y). A function f is p-strong concave (p 0) in y if
M -f(x,g) -fxx,) - (V ()) y) 2 I1 s/1. for all Rd,, and y. Rdx
General Convergence Result. We first show that the iterates of Algorithm 1 converge to the stationary point of surrogate objective F, where F(x, y) wx), {w;]/= by the server (Line 19). See Appendix B for the full statement and proof.
are the aggregation weights used
Theorem 1. Suppose the local loss functions {fi]i satisfy Assumptions 1, 2, 8, 4, 5. Suppose the server selects |c(0|| = P clients in each round t. Given appropriate choices of client and server learning rates, (Tf nly) and (7ān 1 respeclively (see Appendix B.2), the ilerales generaled by RGd-NArm-SGDA salisfy
P En n - 1 PT
A + B 1200 PT
+0 122 Cwoz DoG
min V so maayy (E[T]
+0 2
72T
Partial participation error
Error with full synchronization
Local updates error
(4)
where, x = Lg/H is the condition number, ((x) & maxy F(x,y) the envelope function, AT - ((x(0))
minx (xx), F 1.2 Ei To Teff = E.=1 Pilla An & nTell Ei= Talli B nT max,
willa:
wylla,
C A
Talli 2) and
Ei_ w. (1l, [a 1p)), D A max; (32 ||a, ||a.--1 [13, where a & (a (1) En nmax, Wte
Remark 1. The first term in (4) results from client subsampling <P)).. This explains its dependence on the data heterogencity dg. The second term represents the optimization error for a centralized algorithm (see Appendix C.3 in Lin al. (2020a)). The last term represents client-drift the error if the client(s) run multiple local updates.
Theorem 1 states convergence for a surrogate objective F. Next, we see convergence for the true objective F. Corollary 1.1 (Convergence in terms of F). Given ((x)= maxy F(x,y), under the conditions of Theorem 1,
min tE[T] [x(x1)) < (2xx 8y + Capt + 4x 2 c
4L2 -T ly (x
(5)
(pi-w;)² wi Eopt 2 ET- (x)x()) denotes the optimization error in (4). 1f Pt w for all i E [n], then xpl O. Also, then F(x.y) F(x,y). Therefore, y*(x) = -rrg arg,ax, F(x,y) v) and y yx(x)= = arg max, F(x,y) identical, for all Hence, (5) yields mintery V 26
where xpllw A E
8

---

Published in Transactions on Machine Learning Research (12/2023)
It follows from Corollary 1.1 that if in Algorithm 1, the server aggregation weights {w;} (Line 19) are the same as } we get convergence to a stationary point of the true objective F. For the rest of this subsection, we assume w, = for all i E [n].
Table 2: Comparison of convergence rates of Citt-Nom--GGA.. (Theorem 1) and + (Theo- rem 2), if all the clients run SGDA/SGDA+ based local updates, i.e., ag (t.kk = 1, for all i, i,k, t. The results are stated for (i) (p; = 1/n, T, = r, i E [n]]; and (ii) (p; # Pj), (T, Ty). The additional factors in (ii) relative to (i) are highlighted in blue. We state the results under partial-client participation (PCP). FCP results follow by choosing P = n. For simplicity, we assume uniformly bounded local variance (B2 in Assumption 3).
Nonconvex- Nonconvex-Stronggye Strongly-concave System Setting
Saapeconvex--olla----iioii Convergence Rate
(NC-PL): (Theorem 1, Remark 3)
Sharma et al. (2022) with P n:
O
x-oj
x²nr T
[ + +
VnrT
Pi- 1 Vi [n] Ti [n]]
Yang et al. (2022a) with < n: 0
2
P.
1 zi + o8)
VPT
n
/PT
Ours with P n: O NNaGV
(n- 1)PT
(n-P) P)
vPTT
+
T
+ OG
Ours:
Pi + pj. 7 + T
o R ( (n- Pln P. (n-1)PT
NOO VT
V (Teft i==
pi
o
Ei PiT:
+o oa
12 7 7=
11
Nonconvex-Coneet System Setting
Poet:/ooonnneeeenene-o--o----- Convergence Rate
(NC-IPC): (Theorem 2, Remark 5)
Sharma et al. (2022) with P = n: O
+ +
[nr)
(TPT)TA
VT
P: = Vi E [n]
a-P VOG 1-1 PT
1/4
+
+VOL
(PT
1/4
+
Tj = T, iE [x]]
Ours with P<
< m:
o
(rp/1/4 23/4
p-P
-1/4
+ (G + o
n-1
T574
1/4
1/1
n- P
n-1
maxi pi PT
VOL
Tea
Li=1
p 1Ip1
Ours:
Pi * Pj. o #
+0
(Fotp)1/1 T3/4
+ P
TTell Li=1 7:
22 + Teff n-P
n-1 max; pi)
-1/4)
F = >E= Ti
+0
1
of.
Σ
i=
P:Ti
(G + og max, 2
73/4
72
In Table 2, we specialize the bound in (4) to SGDA-based local updates. We compare the bound under two cases: Case 1: equally-weighted clients (p. = 1/n, for all f), all running t = local updates; and Case 2: unequally weighted clients (px * pU), running unequal local updates (T, # Ty)- The setting in Case has previously been considered in Sharma et al. (2022) (under full participation) and Yang et al. (2022a)*. Compared lo Sharma et al. (2022), our bound has a smaller local-updales error term. This results in improved communication cost (see Corollary 1.2). The additional factors going from Case 1 to the more general Case 2 are highlighted in blue. The following insights can be drawn from Table 2.
Partial Client Participation Error: O [G the most significunt component of convergence error. (PT)
Unlike the other two errors, does not docrease with increasing local updates Tef- Consequently, we do not observe communication savings by performing multiple local updates at the clients. It remains an open problem to achieve speedup in terms of local updates in partial participation settings.
Unequal client weights: the clients are weighted disparately, we observe an increase in the stochastic d.vRpp. + (nnP))nilpll> + VPraa
gradient complexity. To see this, let TÜ = r. The resulting bound is O (GG
(n-1)PT
Since || |Ipll2 < 1, in the worst case (when only one of the clients has all the weight), the , +o
"The condition number x dependence not explicitly stated in the results in Yang et (2022a).
9

---

Published in Transactions on Machine Learning Research (12/2023)
complexity is worse by factor of This happens because the client sampling is not done in proportion to their weights. Rather, the server first samples the clients uniformly, and then scales their updates to get an unbiased estimator (3). We leave exploring non-uniform WOR sampling further as future direction.
Corollary 1.2 (Improved Communication Cost). Suppose all the clients are weighted equally (ps =1/n for all i), with each carrying oul local sleps of SGDA. Further, assume o is bounded from below. Then, to reach x such that [ e,
Under full participation, the per-client gradient complecity of Fad-Norm-SGDA TT O ((cc)) The number of communiication rounds required is T 0 /e²).
Under portial participalion, the per-client gradient complexity of Fed-NNrmm-SGAA is OO* ((=))) In general, running maltiple local updates does not. yield any communication savings. However, in the special case when inter-client data heterogeneity oG = 0, the communiictiin cost is O(x²/e")
The gradient complexity in Corollary 1.2 is optimal in and achieves lincar speedup in the nunber of participating clients. The communication complexity improves the corresponding results in Deng & Mahdavi (2021); Sharma et al. (2022). We match the communication cost in the recent work Yang et al. (2022a). addition, our work considers a more general FL setting with unequally weighted clients (pi # p;), running unequal local updates (7, ry), using distinct local solvers (a, * aa)).
Remark 2.
Extending the Results to Nonconvex-PL Functions
Assumption 6. A function f satisfies p-PL condition in y (μ > 0), if for any fixed x: 1) maxy f(x,y') has nonempty solution set; and 2) for all y
I fxx, 2 2u(max ((x,y) f(x,
Remark 3. If Assumptions 1, 2, 3, 4 hold, and the global function F' satisfies Assumption 6, then for appropriately chosen learning rates (Appendix B.5), the bound in Theorem 1 holds.
5.2 Con-convex-Concav (NC-C) Case
In this subsection, we consider smooth nonconvex functions which satisfy the following assumptions. Assumption 7 (Concavity). The function f is concave in if for fixed x E Rdi, for all y,y' e Rd,
((x,y) S f(x,y' + (V,I(x,))) (Vnl))+(VVW,x,trX,"
Assumption (Lipschitz continuity in x). Given function f, there exists constant Gx, such that for each y E Rd,, and all x, e Rd,
1 x) S Gx ||x x'1.
The envelope function (xx) maxy y( used so far, may no longer be smooth in the absence of a unique maximizer. However, +(-) weakly convex (Lin et al., 2020a, Lemma 4.7). Therefore, we use the alternate definition stationarity, proposed in Davis Drusvyatskly (2019), utilizing the Moreau envelope Φ.
Definition 4 (Moreau Envelope). The function Φx is the A-Moreau envelope of 6, for A 0, if for all e Rd,
xx = min (xx) + 2X
||x' x||
Drusvyatskiy & Paquette (2019) showed that a small [ indicates the existence of some point x in the vicinity of x, that is nearly stationary for áb Hence, in our case, we focus minimizing [x)](
10

---

Published in Transactions on Machine Learning Research (12/2023)
Proposed Algorithm. For nonconvex-coneare functions, we Fed-Norm-SGDA+ The x-updates are identical to Fod-Norm-SGDA, For the updates however, the clients compute stochastic gradients Vyli( .Y. (1,8), g( {((.k)) keeping the x-component fixed at X(*) for S communication rounds. This trick, :si
originally proposed in Deng & Mahdavi (2021), gives the analytical benefit of double-loop algorithm (which updates y several times before updating once) while also updating simultancously.
Theorem 2. Suppose the local loss functions {fi} satisfy Assumptions 1, 2, 3, 4, 7, 8, the y iterates are bounded, and the server selects |ct0| - P clients for all t. With appropriate client and server learning rates, (nh, ny)) and (12,7 vy) respectively (see Appendiz C.2), the iterates of Fed-Norm-SGDA+ satisfy
F. min E. 1/2L, (x10)| so ( n A (E[T]
(
1/1 +
Cuof. + + t
+0
72/3/4
Partial participation error
Local updates crvor
(6)
(( TTglT VI+
Ano Au
1/4
A A- (R)
Taf
1/4
+ O
+
T3/4
Aw
Tall n-1 E5
Error with full symchroniaation
where 11/21, is the Moreau envelope of 4, and D Aw, Cw, D, Ewy T, Teff defined in Theorem and Fw
11/21, (xo) minx T 11/22, The constants
m(n-P)
P(n-1) Ei=1 W².
See Appendix C for the proof. Theorem 2 states convergence for surrogate objective F. Next, we see convergence for the true objective F.
Corollary 2.1 (Convergence in terms of F). Given envelope functions (xx) & maxy F(x,y), T(x) maxy y)x under the conditions of Theorem 2,
8L;
V 1 (x S copt + KE
-T-1 |x(00 x00
min
T
where 1//21 is the Moreau envelope of t x(1 & arg min + + -x00==(000))) x(1) mig (T(x') +
L/||x' - x(') for all t, Eopt is the error bound in (6).
Similar to Corollary 1.1, if we replace {we} with {p:} for all i E [n] in the server updates Algorithm 1, then F= F, and x and x(1) are identical for all t. Consequently, Theorem 2 gives convergence in terms of the true objective F. For the rest of this subsection, we assume wy P; for all i e [n].
Remark 4. Some existing works do not require Assumption for NC-C functions, and also improve the convergence rate. However, these methods either have double-loop structure Rafique et al. (2021); Zhang et al. (2022), or work with deterministic problems Xu et al. (2020); Zhang et al. (2020). Proposing single-loop method for stochastic NC-C problems with the same advantages is an open problem.
Again, in Table 2, we specialize the bound in (6) to SGDA+ based local updates. As in the last section
Partial client participation is the most significent source of convergence error.
Unequal client weights (p: A P,) can increase the stochastic gradient complexity, due to the presence of /IIpll.c. n ||p|22 factors.
Corollary 2.2 (Improved Communication Cost). Suppose all the clients are weighted equally (ps = 1/n for all i), with each carrying out local steps of SGDA Further, assume that & 11/22, is bounded from below. Then, to reach x such that 1 (x)l S,
Under full participation, the per-client gradient complesity of Fel-Norm-SGDA. is TT T ((1((n6))) The ramber of communicatton rounds required is T O(1fe).
Under partial participation, the per-client gradient complerity of Fed-Norm-SGDA+ (()((P))). In general, running multiple local updates does not yield any communication savings. However, in the special case when inter-client data heterogeneity aG = 0, the communication cost is O(1/et).
11

---

Published in Transactions on Machine Learning Research (12/2023)
In terms of communication requirements, achieve massive savings (compared to O(1/e²) in Sharma et al. (2022)). Our gradient complexity results achieve linear speedup in the number of participating clients. Further, as stated earlier, our work considers a more general FL setting with unequally weighted clients (pi # PJ), running uncqual local updates (T, # Tj), using distinct local solvers (a; + az).
Extending the Results to observed in SGD dynamics during neural network training Li & Yuan (2017); Kleinberg et al. (2018).
Functions. One-poinl-convexity has been
Assumption (Onn-point-Coneavity in y). The function f is said to be one-point-concave in y if fixing Rd, for all y E Rd,
( y $ f(x,)) y(x,y'xx))
where (x) E arg maxy y).
It turns out, Theorem 2 holds for the more general class of ronconvex-one-point-ooom (NC-1PC) functions. See Appendix C.4 for more details.
Remark 5. Suppose Assumptions 1, 3, 2, 4, 8 hold. Suppose for all all the fi's satisfy Assumption 9 at a common global minimizer (x).. Then, the bound Theorem holds.
Remark 6. Hence, we settle the conjecture posed in Sharma et al. (2022) that linear speedup can be achieved for NC-1PC functions. As intermediate step in proof, we show convergence of Local SGD for one-point-convex functions. This extends the convex result for Local SGD to larger class of functions.
6 Experiments
In this section, we evaluate the empirical performance of the proposed algorithms. We consider a robust neural training problem Sinha et al. (2017); Nouiched et al. (2019), and a fair classification problem Mohri et al. (2019); Deng et al. (2020). Due to space constraints, additional details of our experiments, and some additional results are included in Appendix D. Our experiments were run on a network of 15 clients, each equipped with an NVIDIA TitanX GPU, We model data heterogeneity across clients using Dirichlet. distribution Wang et al. (2019) with parameter a, (a), Small = higher heterogeneity across clients.
Robust NN training.
We consider the following robust neural network (NN) training problem.
min max S1
l (a b),,,))
where x denotes the NN parameters, (a,, by) denote the feature and label of the i-th sample, denotes the adversarially added feature perturbation, and by denotes the NN output.
Impact of system heterogeneity. In Figure 3, compare the effect of heterogeneous number of local updates across clients, on the performance of our proposed Fed-Norm--SGAA- We compare with Local SGDA+ Deng & Mahdavi (2021), and Local SGDA+ with momentum Sharma et al. (2022). Clients sample the number of epochs they run locally via uniform sampling over the set 12...,E) i.e., ~ Unif(2 E). We observe that Fed-Norm-SGDA adapts well to system heterogeneity and outperforms both existing methods.
Impact of partial participation and heterogeneity. Next, compare the impact of different levels of partial client participation on performance. We compare the full participation sctting (n = 15) with P= 5, 10. Clients sample the number of epochs they run locally via ~ [2, We plot the results for two different values of the data heterogeneity parameter a = 0.1, 1.0. As seen in all our theoretical results where partial participation was the most significant component of convergence error, smaller values of P result in performance loss. Further, higher inter-client heterogeneity (modeled by smaller values of a) results in worse performance. We further explore the impact of performance in Appendix D.
12

---

Published in Transactions on Machine Learning Research (12/2023)
60
Test Accuracy
50
40
30
Local SGDA+
Local SGDA (M)
Fed-Norm SGDA+
125
150
175
Number of Communications
Figure 3: Comparison of the effect of heterogeneous number of local updates {T,} the performance of
Fed- SSGd (Algorithm 1), Local SGDA+, and Local SGDA+ with momentum, while solving (7) CIFAR10 dataset, with VGG11 model. The solid (dashed) curves are for E = 5 (E = 7), and = 0.1.
Accuraay
30
(P=5)
20
PCP (P=10)
10
FCP (n=15)
0
0
50
100
150
200
250
300
350
400
Number of Communications
Figure 4: Comparison the effects of partial client participation (PCP) on the performance of Fed-Norm- SGDA+, for the robust NN training problem on the CIFAR10 dataset, with the VGG11 model. The figure shows the robust test accuracy. The solid (dashed) curves for 0.1 (a 1.0).
Test Accuracy
30-
10
LocalSCDA
LocaiSCaDA (M)
Fed Norm SEDA
20
40
60
80
100
120
140
Number of Communications
Figure 5: Comparison of Local SGDA, Local SGDA with momentum, and Fod-Norm-SGDA, for the fair classification task on the CIFAR10 dataset, with the VGGII model. The solid (dashed) curves are for E 5 (E 7), a = 0.1.
Fair Classification. Nouiehed et al. (2019).
We consider minimax formulation of the fair classification problem Mohri et al. (2019);
min max
Σ
F.FF(x)
A |y|
(8)
x yEar
c=)
13

---

Published in Transactions on Machine Learning Research (12/2023)
where x denotes the parameters of the NN, {Fe]a= denote the loss corresponding to class c, and Ac is the C-dimensional probability simplex. In Figure 5, we plot the worst distributtin test accuracy achieved by Local SGDA Deng & Mahdavi (2021) and Local SGDA with momentum Sharma et al. (2022). As in Figure 3, clients sample T; ~ each case. Again, Fed-Norm-SGDA outperforms existing methods.
We plot the test accuracy on the worst distribution in
7 Conclusion
In this work, we considered nonconvex minimax problems the federated setting, where in addition to inter-client data heterogeneity and partial client participation, there is system heterogeneity as well. Clients may run unquual number of local update steps, using different local solvers. In such settings, we observed that existing methods, such as Local SGDA, might converge to the stationary point of an objective quite different from the original intended objective. We showed that normalizing individual client contributions solves this problem. Using generalized framework, we analyzed several classes of nonconvex minimax functions and significantly improved existing computation and communication complexity results. Potential future directions include analyzing foderated systems with unprodictable client presence Yang et al. (2022b).
Acknowledgments
This work was supported in part by NSF grants CCF 2045694, CNS-2112471, CPS-2111751, and ONR N00014-23-1- 2149. Jiarui Li helped with plotting figures for some experiments.
References
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Alcksandr Beznosikov, Peter Richtárik, Michael Diskin, Max Ryabinin, and Alexander Gasnikov. Distributed methods with compressed communication for solving variational inequalities, with theoretical guarantees. arXiv preprint orXiv:211000394 2021a.
Aleksandr Beznosikov, Alexander Rogozin, Dmitry Kovalev, and Alexander Gasnikov. Near-optimal decen- tralized algorithms for saddle point problems over time-varying networks. In International Conference on Optimization and Applications, pp. 146-257. Springer, 2021b.
Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Distributed saddle- point problems under similarity. In Advances in Neural Information Processing Systems, volume 34, 2021c.
Aleksandr Beznosikov, Vadim Sushko, Abdurakhmon Sadiev, and Alexander Gasnikov. Decentralized personalized federated min-max problems. arXiv preprint arXiv:2106.0720 2021d.
Mingzhe Chen, Nir Shlezinger, H Vincent Poor, Yonina C Eldar, and Shuguang Cui. Commuication--fffccatt federated learning. Proceedings of the National Academy of Sciences, 118(17)=22044789118, 2021.
Ziyi Chen, Yi Zhou, Tengyu Xu, and Yingbin Liang. Proximal gradient descent-ascent: Variable convergence under kt geometry. In International Conference Learning Representations, 2020.
Hanseul Cho and Chulhee Yun. Sgda with shuffling: faster convergence for nonconvex-p (VL) minimax optimization. arXiv preprint arXiv:2210. 05995, 2022.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29172207,2339 2019.
Yuyang Deng and Mchrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intelligence and Statistics, pp. 1387-1395. PMI.R, 2021.
14

---

Published in Transactions on Machine Learning Research (12/2023)
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging.
In Advances in Neural Information. Processing Systems, volume 33, pp. 15111-15122, 2020.
Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178(1):5033-)) 2019.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing syslems, volume 27, 2014.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. Advances in Neural Information Processing Systems, 32:11082 11094, 2019.
Jenny Hamer, Mchryar Mohri, and Ananda Theertha Suresh. Fedboost: A communictiion-offiienn algorithm for federated learning. In International Conference on Machine Learning, pp. 3973 3983. PMLR, 2020.
Charlie Hou, Kiran K Thekumparampil, Giulia Fanti, and Sewoong Oh. Efficient algorithms for federated saddle point optimization. arviv preprinl 0e::2102.0330 06333333, 2021.
Divyansh Jhunjhunwala, Pranay Sharma, Aushim Nagarkatti, and Gauri Joshi. FedVARP: Tackling the variance due to partial client participation federated learning. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
Chi Jin, Pranccth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonooncan minimax optimization? In International Conference on Machine Learning, pp. 4880-4889. PMLR, 2020.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiu:1912.04977 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Dalabases, pp. 795 811. Springer, 2016.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519-4529. PMLR, 2020.
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? In International Conference on Machine Learning, pp. 2698 2707. PMLR, 2018.
Anastasia Koloskova, Nicolas Loizou, Sadra Borciri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pp. 5381 5393. PMLR, 2020.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. Xiv preprint ar arXiv:1610.02.0 2016.
Suchcol Lee and Donghwan Kim. Fast extra gradient mothods for smooth structured mmnconvx--noncoccnn minimax problems. In Advances in Neural Information Processing Systems, volume 34, 2021.
Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, pp. 3175-6186, PMLR, 2021.
Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaic. Complexity lower bounds for nonconvex- strongly-concave min-max optimization. In Advonces in Neural Information Processing Systems, volume 34, 2021.
15

---

Published in Transactions on Machine Learning Research (12/2023)
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-00) 60, 2020.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, volume 30, 2017.
Luofeng Liao, Li Shen, Jia Duan, Mladen Kolar, and Dacheng Tao. Local adagrad-tppe algorithm for stochastic convex-concane minimax problems. arXiv preprint arXiv:2106. 10022, 2021.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent. ascent for nonconvex-concet minimax problems. In International Conference on Machine Learning, pp. 6083-6093. PMLR, 2020a.
Tianyi Lin, Chi Jin, and Michael I Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pp. 2738 2779. PMLR, 2020b.
Weijie Liu, Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil, Zebang Shen, and Nenggan Zheng. A decentralized proximal point-type method for saddle point problems. Xixiv preprinl 1rX00:1910.1 14380, 2019.
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block succossive approximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions Signal Processing, 68:3676-366 3691, 2020.
Luo Luo and Cheng Chen. Finding second-order stationary point for nonconvex-strongyy-conaaa minimax problem. arXiv preprint vrXiv:2110.04 2021.
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex- www.uuewwsssttoooooneeeeooo minimax problems. In Advonces in Neural Information Processing Systems, volume 33, pp. 20566-20577, 2020.
Luo Luo, Guangzeng Xie, Tong Zhang, and Zhihua Zhang. Near optimal stochastic algorithms for finite-sum unbalanced convex-concave minimax optimization. arXiv preprint arXiv:2106.01761, 2021.
David Madras, Elliol Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pp. 3384-3393. PMLR, 2018
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt,, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient. learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pp- 1273 1282. PMLR, 2017.
Dmitriy Metelev, Alexander Rogozin, Alexander Gasnikov, and Dmitry Kovalev. Decentralized saddlo-point problems with different constants of strong convexity and strong concavily. arXiv preprint urXiv:2206.000 000900 2022.
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34: 14606-14613 2021.
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171 (1):115 166, 2018
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference Machine Learning, pp. PMLR, 2019.
16

---

Published in Transactions on Machine Learning Research (12/2023)
Hongscok Namkoong and John C Duchi. Stochastic gradient methods for distribationally robust optimization with Edivergences. In Advances in Newral Information. Processing Systems, volume 29, 2016.
Yurii Nesterov. Lectures on conver optimization, volume 137. Springer, 2018.
Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class non-convex min-max games using iterative first order methods. In Advances in Neural Information 2019.
Processing Systems, volume 32, pp.
Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 185(1):1-33) 35, 2021.
Shuang Qiu, Zhuoran Yang, Xiaohan Wei, Jieping Ye, and Zhaoran Wang. Single-timescale stochastic nonconvex-concave optimization for smooth nonlinear TD learning. ar preprint ar wXXw:2208.101033 2020.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex conelly-covex--coccaee concave min max optimization: provable algorithms and applications machine learning. Oplimizalion Methods and Software,, pp. 1-35, 2021.
Amirhosscin Reisizadch, Farzan Farnia, Ramtin Podarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. In Advonces in Neural Information Processing Systems, volume 33, pp. 21554-215500 2020.
Amirhossein Reisizadeh, Isidoros Tziotis, Hamed Hassani, Aryan Mokhtari, and Ramtin Pedarsani. Straggler- resilient federated learning: Leveraging the interplay between statistical accuracy and system hoterogeneity. IEEE Journal on Selecled Areas in Information Theory, 2022.
Alexander Rogozin, Alexander Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. arXiv preprint arXiv:2102.07758, 2021.
Maziar Sanjabi, Jimmy Ba, Mcisam Razaviyayn, and Jason D Lec. On the convergence and robustness of training gans with regularized optimal transport. Advances in Neurul Information Processing Systems, 31, 2018.
Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Robust and communication- efficient federated learning from non-iid data. IEEE transactions on neural networks and learning systems, 31 (9):34400 3413, 2019.
Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning, pp. 19683 19730. PMLR, 2022.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2017.
Sebastian U Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2018.
Zhenyu Sun and Ermin Wei. A communication--ffiiien algorithm with linear convergence for federated minimax learning, arXiv preprint arXiv:2206.01 132, 2022.
Kiran Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. In Advances in Neural Information Processing Systems, volume 32, 2019.
Quoe Tran-Dinh, Deyi Liu, and Lam M Nguyen. Hybrid varianco-reduced sgd algorithms for minimax problems with nonconvex-lined function. In Advonces in Neural Information Processing Systems, volume 33, pp. 11096 11096-11107 11107, 2020.
17

---

Published in Transactions on Machine Learning Research (12/2023)
Isidoros Tziotis, Zebang Shen, Ramtin Pedarsani, Hamed Hassani, and Aryan Mokhtari. Straggler-resilennt personalized lederated learning. arXiv preprinl or Xiv:22006 02078, 2022.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailioponlos, and Yasaman Khazaeni. Federated learning with matched averaging. In International Conference Learning Representations, 2019.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of local-update sgd algorithms. Journal of Machine Learning Research, 22(213):1 50, 2021.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent, Poor. Tackling the objective inconsistency problem in heterogencous federated optimization. In Advances in Neural Information Processing Systems, volume 33, pp. 7611-7623, 2020.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, el al. A field guide to federated optimization. arXiv preprint Xrx::2107.00000 07906117, 2021.
Yuanhao Wang and Jian Li. Improved algorithms for convex-concave minimax optimization. In Advances in Neural Information Processing Systems, volume 33, pp. 4800-4810, 2020.
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heterogencous distributed learning. Advances in Neural Information Processing Systems, 33:6281 6292, 2020.
Guangzeng Xie, Luo Luo, Yijiang Lian, and Zhihua Zhang. Lower complexity bounds for finito-sum convex-concave minimax optimization problems. In International Conference on Machine Learning, pp. 10504-10513. PMLR, 2020.
Jiahao Xie, Chao Zhang, Yunsong Zhang, Zebang Shen, and Hui Qian. A federated learning framework for nonconvex-pl minimax problems. arXie preprint orxi:21005.14116 14216, 2021.
Eric Xing, Qirong Ho, Pengtao Xie, and Dai Wei. Strategies and principles of distributed machine learning on big data. Engineering, 2(2):179 195, 2016.
Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projection algo- rithm for nonconvex-concave and convex-oncconcave minimax problems. orXiv preprint arXiv:2006.0000 2020.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving lincar speedup with partial worker participation in non-iid federated learning. In International Conference on Learning Representations, 2021.
Haibo Yang, Zhuqing Liu, Xin Zhang, and Jia Liu. Sagda: Achieving ((c-2) communication complexity in federated mix-max learning. arXiv preprint or 2rXiv22210.00111, 2022a.
Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning. In International Conference on Machine Learning, pp. 25331-25363. PMLR, 2022b.
Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A catalyst framework for minimax optimization. In Advances in Neural Information Processing Systems, volume 33, pp. 3667-5678, 2020.
Junchi Yang, Antonio Orvicto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax oplimization without strong concavity. In International Conference on Artificial Intelligence and Stalistics, pp. 5485-5517. PMLR, 2022c.
TaeHo Yoon and Ernest K Ryu. Accelerated algorithms for smooth convex-concave minimax problems with o (1/k²2) rate on squared gradient norm. In International Conference on Machine Learning, pp. 12098-12109. PMLR, 2021.
Hao Yu, Rong Jin, and Sen Yang. On the lincar speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In International Conference on Machine Learning, pp. 7184-7193. PMIRR, 2019.
18

---

Published in Transactions on Machine Learning Research (12/2023)
Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local sgd with shuffling: Tight convergence bounds and beyond. In International Conference on Learning Regresenlations, 2022.
Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhiquan Luo. A single-loop smoothed gradient descent- ascent algorithm for nonconvex-concave min-max problems. In Advances in Neural Information Processing Systems, volume 33, pp. 7377-7389, 2020.
Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex- strongly-coneave minimax optimization. In Conference on Uncertainty in Artificial Intelligence, pp. 482-492. PMLR, 2021.
Xuan Zhang, Needet Serhat Aybat, and Mert Gurbuzbalaban. Sapd+: An accelerated stochastic method for nonconvex-concav minimax problems. orXiv preprint arXiv:2205. 15084, 2022.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. Xixiv preprint Xrv: 2005022,, 2018.
19

---

Published in Transactions on Machine Learning Research (12/2023)
Contents
1 Introduction
1
2 Related Work
3
2.1 Single-client minimax
3
2.2 Distributed/Foddratta Minimax
3
3
Preliminaries
4
4 Algorithm for Heterogeneous Federated Minimax Optimization
5
Limitations of Local SGDA
5
4.2 Proposed Normalized Federated Minimax Algorithm
5
Convergence Results
8
5.1 SoocoooveeSStroglyyyCccree (NC-SC) Case
8
5.2 Non-convex-Concave (NC-C) Case
10
6 Experiments
12
7 Conclusion
14
A Background
21
A.1 Gradient Aggregation with Different Solvers at Clients
21
A.2 Auxiliary Results
22
B Convergence of Fed-Norm-SGDA for Conconves-StrongyyCCorvee Functions (Theo-
rem 1)
23
B.1 Intermediate Lemmas
24
B.2 Proof of Theorem 1
25
B.3 Proofs of the Intermediate Lemmas
28
B.4 Auxiliary Lemmas
38
B.5 Convergence under Polyak Lojasiewicz (PL) Condition
39
C Convergence of Fed-Norm-SGDA4 for Nonconvex Concave Functions (Theorem
39
C.1 Intermediate Lemmas
40
C.2 Proof of Theorem 2.
42
C.3 Proofs of the Intermediate Lemmas
46
C.4 Extending the result for Nonconvex One-Point-Conce (NC-IPC) Functions
D Additional Experiments
51
20

---

: ell))) (t,k) (t.8), ((..k) Published in Transactions on Machine Learning Research (12/2023)
Appendix
The appendix are organized follows. In Section we mention some basic mathematical results and inequalities which are used throughout the paper. In Appendix B we prove the non-asymptotic convergence of Fed-Norm-SGDA. (Algorithm 1) for smooth woneonvee--trrongyyyoom and derive gradient complexity and communication cost of the algorithm to achieve an e-stationary point. In Appendix C, we prove the non-asympoolic convergence of Fed-Norm-SGDAA+ (Algorithm 1) for smooth senconvex-concayy and nonconvex-onee point- concave functions. Finally, in Appendix D we provide the details of the additional experiments we performed.
(and nonconvex-PPe functions,
A Background
A.1 Gradient Aggregation with Different Solvers at Clients
eff = r for all i E [n], t E [7]. Also, (1.b) for all e [r],t. Then, the local iterate updates in Algorithm Nored--oor-SG reduce to (the updates for Fed-NormnSGDDA+ are analogous)
Local SGDA. Suppose Ti = (t)
(1,+1) (1,k)
xi n V (xx (1.b)
.y. ((a),
(1,+1)) (1,k) My V (x( y (1
for k E {O...., }} and the gradient aggregate vectors (gx. (t) are simply the average of individual gradients
Σ K=0
Vali(x (1,0) (1,0),
(x
(1.)) yy (
8x.1
k=
Note that these are precisely the iterates of LocalSGDA proposed in Deng & Mahdavi (2021); Sharma et al. (2022), with the only difference that in LocalSGDA, the clients communicate the iterates {x] (t.r) (t.r) to
the server, which averages them to compute (x(++2), ((+2))) While here, the clients communicate (gx.0 Sy.jJ* Also, in Fed-Norm-SGID the clients and server separate learning rates, which results in tighter bounds on the local-updates error.
(t)
With Momentum in Local Updates. (4) - 1}
Suppose each local client uses momentum buffer with momentum
scale p. Then, for
xi 11.+1 = p. + V Vzf((x( (t,k) (1.))
yi e(lit),,
(1,b),
x; (e.+1) = xx
n d 1++1
1.+ = p. ik + V (xx
(1,8) (1.b),
yi :c) c(())),
y(1x+1)) ((((,))
+ m/ d p f.++1
y,
Simple calculations show that the coefficient of (xf((x) gradient aggregate vectors (0) (1)
(1.))
.y
((:)) ; ((.k)) and V (x. (t.b) , e (lt))) in the
By.i)
(4)
1 - p (4)
=1 p ... tt -1-k
1 P
J2
Therefore, the aggregation vector is a; I-p
(1)
1
1
p²:
(0)
1 p/:
(8)
...., p), and
① k
(1) p (T()))
11 = Σ
p
1 -
1 -
1 -
k=0
21

---

Published in Transactions on Machine Learning Research (12/2023)
A.2 Auxiliary Results
Remark 7 (Impact of heterogeneily ag even with 7 -= 1). Consider two simple minimization problems:
(P1):
fx)
and (P2): min f(x).
n
(P1) is a simple distributed minimization problem, with clients, which we solve using synchronous distributed SGD, At iteration t, each client computes stochastic gradient (x((x))) e and sends it to the server, which averages these, and takes a step in the direction n E ; (.)). On the other hand, (P1) is centralized minimization problem, where at each iteration 1, the agent computes a stochastic gradient estimator with batch-size n, - ((((();e!")) We compare the variance of the global gradient estimators as follows.
(P1)
(P2)
E
Ei=1
fi(x (1) ( )))
E
EE
V
ff(x -5 (1)) V
n
i=
of + 3 V. 17
VS
E fx -.,0) v
EE
n²
n²
22 82
Bh V +08
o Ei E (x ||²
Since almost all the existing works consider the local variance bound (Assumption 3) with 8g = 0, the global gradient estimator in both synchronous distributed SGD (P1) and singlo-agent minibatch SGD (P2) have the same n
22 variance bound. Therefore, in most existing federated works on minimization Wang et al. (2020); Yang et al. (2021) and minimax problems Sharma al. (2022), the full synchronization error only depends on the local variance o.. However, et al. (2020), which considers similar local variance assumption as ours for minimization problems, also show similar dependence on heterogeneity og.
above, for 8z 0, this apparent equivelence breaks down. Koloskova
Lemma A.1 (Young's inequality). Given two same-dimensiona vectors u, v E Rd, the Euclidean inner product can be bounded as follows:
|u| 2 27
7
l|vl| 2
(u, v) <
+
for every constant 7>> > 0.
Lemma A.2 (Strong Concavity). A function g X x y is strongly concove in y, if there evists consland > 0, such that for all x E X, and for all y. E y, the following inequality holds.
y) S y(x,y')+)))))) + (V Vyg(x,'') -)) - lly 1111.
14
Lemma A.3 (Jensen's inequality). Given conver function f and random variable X, the following holds. f (E(X)) S E[f(x).
Lemma A.4 (Sum of squares). For a positive integer K, and a set of vectors xI,..., the following holds:
X
K
|xx
k=1
Lemma A.5 (Qaadratic growth condition Karini et al. (2016)). If function satisfies Assumptions 1, 5, then for all x, the following conditions holds
g(x) min ((z)g(z))))) 2 X, x||
[[g(x)]]= 2 24 (g(x) - min g(2))
22

---

Published in Transactions on Machine Learning Research (12/2023)
Lemma A.6. For L-smooth, convez function 9, the following inequality holds
E V Vg(x)]] 2 2L [o(y) g(x) Vg(x) (x)]
(9)
Lemma A.7 (Proposition 6 in Cho & Yun (2022)). For L-smooth function g which is bounded below by g", the following inequality holds for all x
E [ S 2L -
(10)
B Convergence of Bed-Norm-SGDA for Manconvex-Strongyy-Coom Functions (Theorem 1)
We organize this section follows. First, in Appendix B.1 we present some intermediate results, which we use to prove the main theorem. Next, in Appendix B.2, we present the proof of Theorem 1, which is followed by the proofs of the intermediate results in Appendix B.3. Appendix B.4 contains some auxiliary results. Finally, in Appendix B.5 we discuss the convergence result for nonconvex-Pi PL functions.
The problem we solve
F(x,y) Σ wi urfi(xxy))
min max y
We define T(x) f maxy y( y) and (x) arg maxy y(x,y). y). Since F(x,:) )) is p-strongly concave, y*(x) is unique. In Fed-Norm-SSIDA (Algorithm 1), the client updates are given by
(t.)) x(( 1/
Σ
5-0
(11)
k-1
y (1,h) = y() + 1
Σ
(
(5)
4.
1-0
where 1 &
These client updates are then aggregated to compute
{ gy.1
(t) (0)
1
(Tr) sf (x:t)) .i. (
(L.))
<lux)); h = aail
Vz)) (x: (1,)) (x("")))("" y!(
8x,1
|a:
1
(k) (T.)
(t.) y ((ak), cl(a)):: cl(b)e (1)
(1) (T) (x(( yy s((i))
By,
|a.
x5
|a.ll
k=0
k=
Remark 8. Note that have made explicit, the dependence & in ( above. This omitted in the main paper to avoid tedious notation. However, for some local optimizers, such as local momentum at the clients (Appendix A.1), the coefficients (k) change with k. We assume in our subsequent analysis that (1) (k) S for all j E {0, 1,.... 1} and for all k E (1, We also use the notation ||a,|| 2 ||aa(TT))] d
At iteration i, the server samples |C00| clients without replacement (WOR) uniformly at random. While aggregating at the server, client update weighed by w,n/[C()). The aggregates (gl). (()) computed at the server are of the form
(t)
wige such that Egco (g)) Eows
I(i E C
(8) )()))
Σ
(t) wigx
gx
(EC(+)
(12)
(t) By (EC())
Σ
mu such that Egco [8(1) Eew Σ T(i E c( (()))
(8)
Σ
wi
23

---

Published in Transactions on Machine Learning Research (12/2023)
For simplicity of analysis, unless stated otherwise, assume that (c(t) - for all t. Finally, server updates the x,y variables as
= x()) Tear
y(++1) = y(t) + Ten
We define by F(t') the o-algebra generated by ((x!1)) 3 1 Throughout, we denote the conditional expectation B[)]F(()] by the shorthand [:]]]-
(1.) (1.))
B.1 Intermediate Lemmas
We begin with the following result from Nouiched et al. (2019) about the smoothness of ((-).
Lemma B.1. If a function f(.-)) satisfies Assumptions 1, 5 (Ly-smoothness and p-strong concavity in y), then (.) A maxy y( is La-smooth with La kL, /2 + L,, where k = Lg/ is the condition number. Lemma B.2. Suppose the local client loss functions {fi} satisfy Assumptions 1, 4, and the stochastic oracles for the local functions satisfy Assumption S. Suppose the server selects P clients in each round. Then the iterates generated by Fed-Norm-SGDA (Algorithm 1) satisfy
Eg
8x
E
Σ
(EC()
P
n2
(k) (T.)) of. 37, V fi( (1,20
(13)
Ex
Wi
h
la
P
P
n(n- P)
2L
a
W
T
(
(1..) x.y
(i) + (max wi) 2 38 Fx y(t))) |1 + o8 }
2
11
P
|ai 11
+ lly! (1( 1p] the iterate drift for client i, at local iteration le in 112 (0.k) (i) 2 E, (|x((()) - where, Axy
the t-th commumication round.
Lemma B.3. Suppose the local client loss functions {fi} satisfy Assumeptions 1, 4, 5, and the stochas- tic oracles for the local functions satisfy Assumption 3. Also, the server learning rate 7h satis- B fies 64T BL & & (max, w;lla:113 /
113 1, Lo w:) (H=P) max 1} 1, and
8T 8T B3 P (maxix waa (K) (T:)/|aas11 S 1. Then the ilerates generated by Algorithm 1 salisfy
E, (++)) - {(x{1))
s 7r
v)(x 1²
Tef (1
n(P 1) P(n - Te
Er
w h (t)
16
2
+ 7 Tett 13
5
Wi
(8) (T
(c. x.y
(i)
I (x((()) Fxx(1))
.((1)] ((xx))),((0))
(14)
aail
4fa
k=0
2o ral n
L n
of.
w
a:
2
+
oz
2(max wx)
n-
n-1 + 2,3 max
ws wi|la:112 11:
2
P
|a
||a:1 2
Remark. The bound in Equation (14) looks very similar to the corresponding one-step decay bound for simple smooth minimization problems. The major difference is the presence of (xx(0) (x(11), y(t))
which quantifies the inaccuracy of y(()) in solving the mar problem maxy Fyx().y). The term (k) (t.k) (i) is the client drift and is bounded in Lemma B.4 below.
Eis ||a.|h Ex 1 a; (T)
Lemma B.4. Suppose the local loss functions {ft) satisfy Assumptions 1, 4, 5, and the stochastic oracles for the local functions satisfy Assumption 3. Further, in Algorithm 1, we choose learning rates vfa nf, such Then, the iterates {x() ()(")) generated by Fod-NNormSSGDA
that maxtnf. n 5 (myx, (a.ll)) (oll))2((110)))
24

---

Published in Transactions on Machine Learning Research (12/2023)
(Algorithm 1) satisfy
3 Σ Wi
a (T)
( 2 + +11]1) 1.307. Σ ||a. + +T.34aa (122) + +11g)) 0e
a lll
1=1
k=0
+ Ma,
|
+ 8. ,8 (2k(/a) + [mg]3) (o(x(0) - F(xe(t) y((t))
where Ma., max; (1ai,-111 1
Lemma B.5. Suppose the local loss functions (Ji) salisfy Assumplions 1, 4, 5, and the stochastic oracles for the local functions satisfy Assumption 3. The server learning rates r N satisfy the following conditions:
n T max 87. max
wi willa, l1
n P
1
7g
WA
S
S
|aill
64
8LK2
n n- P Sy max n
max wi, B7. max wid; (Ti)
(k)
<
|aill
The client learning rates Tha Fy satisfy my L S 16 and nh , S the iterates generated by Aod-Norm-SGLLn (Algorithm 1) satisfy
respectively. Then
64kg
E (xx ((x((),y(0)))
(x(())) - Fxx(10) .(()
T-1
4T Log n(P- -
n m
V (x) +
(t)
<
TofTiGHTT
12 T
P(n -11 1)
x,1
1=
+ 8T 71
02 Σ
||:1|
+ 20
n1 - P
max wi + B2 max
wa willa,11
||a:11
i=1
+ 8kLy ([riI2 + 1ng11)
of Σ
w |a..-1122 20%
(15)
Remark 9. The proof of Lemma B.5 differs from similar results in the existing literature Sharma et al. (2022); Yang et al. (2022a). As in these works, if all the clients are running the same number of local steps (7, T, for all i), we can define virtual sequences of average iterates (t.kk) = p Eiecio x! (t,K)
y(th)) = } Eiecis y, y (1.k)
for all k E [0, 1),t. Define F'(1, k) as the o-algebra generated by
(4.h) (1 DED U ((x) F'(1K)) A o {(x] (1.t) x
(1)) x3 (1)))) }=)
Since, conditioned on kt, xh++! 1 (Vff(xx yt :s simplifies the analysis. However, with 7; * Tj, the virtual sequences (xllitt, y((k)) can no longer be defined for all k. Hence, we need an alternate proof strategy.
((.)) (4.))
((A),
(
ر using fx((t.0) y(ttt))))))) considerably
B.2 Proof of Theorem 1
For the sake of completeness, we first state the full statement of Theorem here.
Thcorem. Suppose the local loss functions (fi)s satisfy Assumptions 1, 3, 4, 5. Suppose the server selects clients using without-rephe rethouut--plccement sampling scheme (WOR). Also, the server learning rates ri n0 and the client learning rates ofe nfy salisfy the conditions specified in Lemma B.5. Then the ilerates generated by
25

---

Published in Transactions on Machine Learning Research (12/2023)
Fed-Norm-SGDA (Algorithm 1) satisfy
min 11
E
V
(x)
/|
-
1
T-1
Σ
E
(xxx)))
AT TefriiT
+
Pighs P
Of + Bewlod))
T
t=0
Error with full synchronization
R² 2 - P
- P g Bengoo
O
(k² (1m + [n [c + Do +0
n n-
P
Ervor due to local updates
Partial Partscipation Brror
where Lg/p is the condition number, (xx) maxy F(x,y) y) is the envelope function, Aū - ((x(0)) minx T(x), Aw - nTeff Ei=1 wil|a.113
[alll B _ nFeff max;
willa:1l
Cw - E wi w:(lla:122 - [a (1,77 1))), D -
| TT for all i and Ew & max, Wi.
max; ||a, |ai.- ||a,-113). 1), where a & la, ai
(1)
Using 7i -
(V TurhesT An (Bu =- Bop
and nff S n 0 ((TTTT) where F + Ti
in the bounds above, we get
min E (
0o
12 121
A + BwiBg.g A-
R²
P
Eu PT
+0 R Cwoz + DoG
PTofff
n-
T2T
Local updates error
Error full synchronization
Partial participation error
Proof.
Using Lemina B.3, and substituting in the bound on iterates' drift from Lemma B.4, can bound
E2 ((x((+1)) - ((xx(0)
7T
Tetr
n(P - 1) (1-
Toff 7 Lo
B
wy h
16
2
P(n 1)
x,
9T
(xx(1)) - Fxx(1), y.(0)]
4p
Teft hi La
wfl
a 12
1- P
willa.12
+ -66
2(max wi)
9- + 2,32 max
|| ?
|aa:1
n oi Σ
Ta (Inil + (ng]?) 13
wi |laa,-1ll u 20
10 L. 38 [n
\/( ,,, (2x(n + [ng]t) (x(xx(0) (00))F(( (260),(0)))
(16)
Summing (16) over 0, .., - substituting the bound E (xx(1)) F(x(0), y(o)) from Lemma B.5, and rearranging the terms, we get
x A
& n n
o7.
wf |a:
+00
n P
n max w; + 53. max
willa:113
la.11 ))
TannT
P
||a:11
+ O h2 ((n5) + (n T.3
o. Σ
72
wi (1a:112
(a! (a(::==1113) + o max (1a.,-11 33 lai 11..)11)))) 1) (17)
i=1
Consequently, using constants Awi, Bwo Cwn D, Ew. (17) can be simplified to
(A²
A
TēT.
(Amo? + (Bus + n n-P En 02 oz)l)
50
+
Ta
n-
26

---

Published in Transactions on Machine Learning Research (12/2023)
0 (x²2 (ITE) + [mg])) L3 [Cuol Doã)),
which completes the proof.
Convergence in terms of F
Proof of Corollary 1.1. According to the definition of F(x) and F(x), we have
VΦ(x)= V = Σ
w,
(xr arg maxy F(x,
Σ Pi Vofi(x (x)]
Σ (p. - wx) yx
i=1
-VxP(xx, (x)) vxf(x, (x)
P:
wi
V (x))
V
Taking norm, using smoothness and applying Cauchy- Schwarz inequality, we get
v - vQ(x)
|| 21 (ly - (x)] +2
(ps w;)2
Σ w.
5x
Wi
< 21 (x) - (x)]1 + 2xp
18 |
/|
+ +
where the last inequality Assumption 4. Next, note that
1| 12 +2 [T(x)
|V((x)] <2 V vo(x)
Therefore, we obtain
(x))
|
T-1
(x(
min T
-
T
T Σ
1 T-1 x + 1
2
2
w
88
+ 1
T
1
(1) l|?
+ +
2
1x
-x()
1=
2 22
2ppp
w og +
1
Copt + 4
2 o + L2
where Eopt. denotes the optimization error in the right hand side of (4) in Theorem 1.
Proof of Corollary 1.2. If clients are weighted equally (w, = = 1/n for all i), with each carrying out 7 steps of local SGDA, from (4) we get
()))))) <0 E
min
P PROGG VPT
x2 0z 1 110G
of T02
/PTT
7T
For full client participation, this reduces to
( 7)
v 20
min
VnrT +
To reach an e-stationary point, assuming nt < T, the per-client gradient complexity is TT =
net
Since S T/n, the minimum number of communication rounds required is T 0 k²
27

---

Published in Transactions on Machine Learning Research (12/2023)
For partial participation, o( ((1=7)))) oGy PT is the dominant term, and we do not get any convergence benefit of multiple local updates. Consequently, per-g graddentdnntt client complexity and number of communication rounds are both TT O Pet for O(1) However, if the data across clients comes from identical distributions (og 0), then we recover per-client gradient complexity of x+ and number of communication rounds = O Pet
B.3 Proofs of the Intermediate Lemmas
Proof of Lemma B.2.
E
(t)
E2
Σ
Wi
8x
(1)
h
x,
(4)
h (8) x,1
(EC())
(a)
E2
Σ
Th
8x,
+ Et
Σ
W; x,
(EC(s)
(EC())
E,
xx
h
E2
Σ
h
(t)
(:: Be (9)
-h for all clients E c())
(EC())
RECO
P
11
W
TD
8x,
(0)
h
2,1
(1)
2
+ E2
Σ
W
h
x,
(::0; win/P and P(i P(i E c(t) = P/n)
t=1
RECO
2
TC-
Σ
la
(b)
(T.)1²
oz B8
[ax((x
(1.8)
.y. /1)
BB, Σ
wit i
(18)
REC1O
Here, (a) follows from the following reasoning.
E2
Σ
Bx.j n n22)
(8)
(JCC
E,
(h (2)
8x.i
-n2
F(t), c(o) + Σ w.ú E
(n gx.j hn F(t), c(9)
(9)
(EC()
(Assumption 3; independence of stochastic gradients across clients)
E,
Σ
WfE
x.i
(t) (1)
8x,
-n
(0)
c(t),
(EC())
E,
?
T--1T--1
Σ
Σ
a
(Ta) ) (T.)a
(Vrfi (x((iA)
.y ((.)) e((.))))) Vali (x((1)) ( -.(t))))
1
(EC())
k= 1=0
Vafi (x((x)) (x((a)),(((11)) ) [(1)
Tー- Σ 0=
W
10
(8)
(T))]
[=f(((((t))) (((tt) g((t)))
V
f( (( (1)) (((0)) [(((
|a;
?
(ec())
28

---

Published in Transactions on Machine Learning Research (12/2023)
V= , -y((رbi) ) c(0)
+ 14 (T.)a: (T.)
(8)
( [z 19: " ,( ((()))) - Vzzi(x
(t,1) (1.1)
(c,k) y (((ii)))) x (()ا)) y; -لبرر
4i
jck
Vefi(x(())) .y! [1)
= 0.
(: Assumption 3)
The last inequality in (18) follows from Assumption 1 and 3. Further, we can bound the second term in (18) as follows.
E
Σ iecon
W. h
Wy h
+
wyhx
(1)
E,
Wc h x,
+ E
Σ
T(i E ((0))
10 b0 (0)
Σ
we h (t)
x
(WOR) sampling)
i=1
E,
1 h
Σ E
[uui E ((0))) (())) + w
211(i c()))
|n 27
1=1
+ Σ
E,
(I(i E c(t)
w/ wi)h C2 (I() E cw))o - w, ( )
ii C (120|
E,
wc h
+ Σ Es
1=1
(I( E )(t)
Illjj E cl وāū - lljj E c(())) w;; I(i E c( + wiws) (1 (0)
Er
n
P ( - -1) (n22 12)) n
E,
Wc: h
x,
(1)
P
Σ E2
wF
Er
WiWj
p
n
n
P
Ex
n
wi
+ n n
P n
w F4
|1
(19)
n
P n
Next, we bound the second term in (19).
Σ
wf
1 - (x((((())
(1) (())) ()())
+ vxf((x()), ,(()) |
1=1
?
(k) (Tx) (T.) x. (1) + 2 (max wi) 38 v (xF(x()) y())) 12 + +2²)
<
2
(20)
[all
k=0
using Assumption 4. (t.k) (i) E,
|xx (t.b) - x 2 + llx (t.b) - -01] Substituting (20) in (19), and using
the resulting bound in (18) we get the bound in (13).
Proof of Lemma B.S. Since the local functions (f.) satisfy Assumption 5, -xx,)) is p-SC for any x. In the proof, we use the quadratic growth property of J-SC function F(x, :), i.e., for any given x
2 Ily - yx)xl S (xxx)((x)) F(x,y), for all y,
(21)
29

---

Published in Transactions on Machine Learning Research (12/2023)
where (xx = arg maxy, y(x,y'). Using Lo-smoothness of Φ(.).
Eg ((x(++))) I [x(((111)
Es
v (1)
Ter
Σ
(t)
Telt
L
By
8x
2
tEC())
Tetl [Tm)
2
Lo
= =xx B
v Σ
Wy
(1)
Et
g(
(using Assumption 3 and (3))
2
27
= )
Toffi
|
/|
+ B2
W (1)
+
Toff 10
E,
vx(x100) -
>
w
(
2
1=1
+ Totrl [/] Lup
Be
Bx
(1)
(22)
2
The last term is bounded in Lemma B.2. Next, we bound the third term above.
v (1) - Σ
we
1=1
n
Ex
W/
Vali(x(), + Vali(x(), y()))
(1) x,1
i=1
(since ÿ (x) arg
arggma,, maxy. F(x, y')
I 21 15 -
-x(10// 2E,,
n Σ Wi
V=fi(x("), y(1))
(k) (Ti Vafi (x((.b) (1.00)
laill
km
(L smoothhnessss: Young's inequality)
413 T (1)) F(x((1),)) y(00)
12
(xx)) y()) (x (h. .y ((a))) |²
+ Σ
Σ
(2) (T.) V (x
w.
|aill
i=1
k=
(Quadratic growth of PCSC functions (21): Jensen's inequality)
41
((x(1)) F(x((1) y()))] 2 Σ
Wi
(k) (T:)
|| - (x)))
2 || + || y())
a
11
|a:
k=
(L (Ly-smothhness)
4T?
((x(10) ((se(0),y,(0)) + +2L3} Σ
Wi 11
(2) (
(23)
|a
where (t.k) (
- B.
| - x210
(()
y(00
Further, the term containing
[xx((x( (1.))
in (13) is bounded in Lemma B.7. Substituting the bounds from (23), (13) and Lemma B.7 into (22), we get
E,
(
Teft < 5)
| 10 2 R
/12
w: h
2
4L2
+
Tefl?
T (xx (1) - (x (1) ((()))
+ 223
W/
(T))AA)) (1.b) (i)
2
11
[a: k=0
+
Teff
hna) L.
n
P 1
E,
(8) we x.
+ P n 2L
P
a
(k) (T)) (1)
2
P
n 1
| |ll
1=1
k=
2
Li no
a w
2
22
Lip n
n P
82 V (x) (1) y(0)) 1| + +02
+
2(max wi)
2
P
|a
2
P n - 1
30

---

Published in Transactions on Machine Learning Research (12/2023)
+
2-
2
L. n
P 1%
2
W
[a (T:)) 2 (4.0)
(1) + 208
max will willa::1 12
2
||a||| 11
x,Y
1|a:1l
1=1
k=0
+
Tefl 1m
La n
BLAB2
max
Wi
2T
(((x(t) (1) - -xxx ,x((1))
+ v 2 (3)) 1|2
2
p
||aili
S ((x(1))
Tett12
1
P
P
Tell
Er
Σ
n
w
(0)
16
2
n
n-
+
( - F(x(1)) |l(o)]
+ 5
Team
Wi
1
(2. (t)
4/
4
||a:||
i=1
k=0
+
T lmm La
2
n
P
n w 12
| 1
+
oō
2(mmxx wi)
12 P
1 +
2,3
max
w/ walla,18 11
||::1 ?
where, the coefficietss are simplified, using assumptions on the learning rate 7i=
Tetth La
(maxws) w/)
12 P (pP)) 12 - 1
+
32
max 2
w.as
(M)
(T,)
I
P
||::11
4n
Tett Lip
(max i
n
11 1-
+ B2
max.
wil a 112 ||a. ?
32,3,,i n
P
This finishes the proof.
Proof of Lemma B.4. We use the client update equations for individual iterates (11). To bound (t.b) (i),
first we bound a single component term Eg | - x00| For 1 < k S Tr
k-1
E2
x3
(1,b)
x00
= [
Σ dj (K) (aai (x: (x(1)) .y ,(,0) Vafi (x((0) ,.(())) + Vali (x(())))? .y ((.)))
= 2
E+
7 0. (k)
1-1
(v ((1-))) .y [(,0) Vafi (x((x)) )(())))
+ +E
Σ a ( (x(tt)) .y s((s))
(using unbiasedness in Assumption 3)
= 2
Σ 10 (K))'E Vali (x((t)),{(+))) [+++) vafi (x .y (())))
|| +E
d ( fi (z (1.)) .y (1)))
(B))2 of + f. V=li(x(' ",,"""")"","" )/(0))1()= + [ (B)
Σ (+)E, V.Ji (x(
(15)) || (24)
< 2
31

---

Published in Transactions on Machine Learning Research (12/2023)
where the last incquality follows from Jensen's inequality (Lemma A.3). Next, note that
T
(K)2= = 7.-
(1)
(Ta)
(
(b))²
T0
10 (A)]
la:12 - [a (a.
1) (T:)1,
|a:l11
K=0
k=
k-1 (k)
T-2
[a:ll
1
(T.)
(A) = Σ
4
(1)) - ||a:11, - 1a,0001-11 1) (T.)],
K=0
j
K=
K=
1-1
T--
00
(+)]²
(T)
Σ
[a (b)P
S a.
Σ (T)).
|a;111
a
3 0
k=0
1) (25)
where af (k) S a for all j. We define ||a.,-112 for the sake of brevity, Using (25), we bound the individual terms in (24).
112 - ||
| 11 (T: (T:))
||aa,, 11 - ||.1|:
- |a (1)
(T:)
k-1
Σ
(M)
(T:)
Σ
la
(3
V=fi(( yy (1))))
laill1
R=
5=
s 228
Σ
1a
(b)A + +252 a 11.2 Vafi(x(), x(00)/
(26)
5=0
Similarly,
1
1
(Ti)
Σ C (k)
Σ
1 (K)
Vafi
(xx"")),((")) s(.5))) |
|a
1 k=0
1=0
$
7-1
(1)) (Ti)
Σ
T
oi (b)
Σ
(+)
2 (A)
[13243 + Vali(elo |10001000,000011
||:l11
k=0
1=0
1=0
2
$2||a; 1111 L3 Σ
d
+2|1a, -19
(27)
j=0
Substituting (26), (27) in (24), we get
5-1
a 0
(T.)
x (2,b) x x00|²
< Inoloo |1.-112++ 2[n (1aa,-1l1 + B7,a)
Σ
(k)
(T))
a
1aill
k=0
+ +2 (la.. 11 + B2 ||..- 12)) (V.1((x(0,,(01))
(28)
Similarly, we can bound the y error
TC-1
( | - y00l 11(())
s Po |a.--112 + 2[n L3 (11a)-1ll1 + ;2a)
Σ
a.
(k)
(T.)
(T.)
(1)
|a:1
R=
+ +2|ng] (10.--112 + 33 ||a.- 11:) Vof((x(!)) ,,0)/
(29)
Combining the two bounds in (28) and (29), we get
(4) (, || | (t,k)
x(00|| + | (1)( -y00]]]] < (Ina) + [(g]1) oî ||a.-111"
|a
1-1 1
+2 ((n0)2 + [ng 1 l|ail (lla;, + +Baa)
Σ d
(k)
(T)) (1)
||a:l|
0=0
32

---

Published in Transactions on Machine Learning Research (12/2023)
+ (la.- 112 BL 1a..-11.1) [ma] Vali (x(), y(0)) + Ing]] || y(0) )1
(30)
Define Am _ 2 ([n + [ng]et max; |aill (11a,-1l1 + Maa. Rearranging the terms in (30), and taking the weighted sum over agents, get
3 |aill
(8) (T))
([ + [ng]²) 1 2
Wi 1|
A-Am
+ 1 - Am i=1
212
Σ Wi
(1aa
+B2 [|aa,,-11 11a,,
[mal] || (x(0) (x(), 1|² + [[gg V (x(0) ((())))) )1
(1161 + (mg]2) I.?
213
ws Vafa (x(1) s111)))))) /|
Σ
Wi |a
[no)?
Σ
+ oā
1 Am
1 Am
i=1
1=1
2L 2
Σ w; V yf (xl0) (000)))0))
-
+ 1 Am
+ +0%
(31)
where (31) follows from Assumption 4, and we define Ma., max, (laa,-111 + 332 ||a_- We bounded
/ F (x(1), || in Lemma B.6. Similarly, can bound V/ F' (x()),((t)) follows.
V F x )1) Vyy x(),)(1)) V,F (x1() (x())))(((())) S 22g (xx(1)) y(()))
||
(: arrg maxy y')
(32)
using smottheesss and concavity of F(x,.) .) (Lemma A.6). Also, for the choice of ne mh we get Am S 1/2. Consoquently, substituting the two bounds (31), we complete the proof.
Proof of Lemma B.5. First we see that
E, (11)+ (x+1)) (tt) (tt)))
= Es (x+((+)))) - ((x{ + - (())), + E, [F( - -F(x(t+1) -((t)))]
-
(33)
E2 ((x(++1)) { is already bounded in Lemma B.3. We bound E, F((x(t) - =(x((+1), y,(())))))))))
follows. Using the notation 2(1) = (x())) and using sysoothhnssss (Assumption 1) of F(,)),
-F(2((+1)) S (((((0)) V (z()))))) 2 - -2(0)++ L,
(((+1) - =2(0
2
--((2(0)- (v (x(()) ,))(()))))())))))) -y(1))
L,
|(++1) - -y(0)//
+
2
(x(F(x(()) ,(()) ((+1) x(0)
T,
[((+1] - x(()) /2
2
+
2
-E F(x((t)), (((((t))),((++1)) < -x((x(()
(7,F(E (1))
Σ w. w.hh (1)
T 11 Ls
(1)
+
E,
gy
2
+ B. (x((
wit (t)
+
-. 1x:0]
2
E,
(t()
2
33

---

Published in Transactions on Machine Learning Research (12/2023)
Rearranging the terms bit, we get
E F F(x((+1), (
2
27
S
Toftl L R.
2
((F(((t).y)) /// +
Σ
1
h (8)
y.3
V Fxx(1)) , y(t))
Σ
Wy h (1)
v.3
Tell rg L.
2
2
F.p
By
(1)
2
2
27
Teft E,
|=F((
(t)
(xF(x(1) ,5())
n
(0)
Tefl 1
2
L
(1)
2
+
00
x.3
wPh
x,1
+
2
E2
gx
(34)
Next, we bound the individual terms in (34). Using quadratic growth of μ-SC functions (Lemina A.5),
V (x!" /0) (0))""")"')'
2 2p (((((t) F(x F(x(0, y(0))
To bound v Fx((1)) y(t)) - Ei= wi
(t)
we use similar reasoning as in (23).
V 22
Σ
w. h
( y,
Σ 10
(v ,y(t)) - h..))
7
S
13
wi
a (T) x.
(
(35)
|a.
1
1=1
k=
Substituting the bounds in (35) and Lemma B.6 into (34) we get
Eg (1) ,,((t)) - F(x((+1) (++1) ((x(tt))),.((
S =ToAfling (1-
2
( F(x(1) y(1))
Tett
EE,
Σ
Wi h (1)
2
y.
+ Tetti
V /|/
Tatt1
E,
w. h (t)
Tel Ls 2
[_]]
gg( 2
+ 1,,
2
7 2
n
Wi
TC-1
(4)
(T))
(36)
a
E. Ex|18<22
11 2
is already bounded in Lemma B.2. We further substitute the bound on E, V fix (t.k)
(1.A)
from Lemma B.7 to get
E,
g
(8)
2
n( P
E
Σ
W.
(0)
+
o n
1a
1
(n(n - P) 208
max wi
P(n - 1)
x,
P
P
n-
:
1=1
In n
2T²
(K) (T:)
2 (L.))
(1) + 4,88
max
will
willa,ll
1
V. (x)0))
/|
P
||
||a;
2
1=1
k=0
+ 87 n
wille willa;112
2
max
o0 +
L
()) F(x(()) ,(x(0),,(11))] y(:)]]]
P
||ail
+ nnn- P) 2L
m
T
(k) (T, $2. (1)
n -
P
[a Il
k=
+ n(nn - P)
2 P
((x(+)) - (ixx0,,(00) +2 V. V x((00)
max Wi
4L
34

---

Published in Transactions on Machine Learning Research (12/2023)
n(P- 1)
Be
Σ
W:
(1) x,1
+ nh
wil
22
+
2nog
P
max wi + 37. max
wi a 2 || 1
P(n- 1)
||al1
2
P
n n-1 1
+
n1 P
max W/ + 88
max 5
wid
(k) (Tx)
2
5
n
W
ai (Ti) (T.) (1)
(8)
11 1
|| |ailla
P
aill1 k=0
4m
n1 P
willaill
|
V (xxxx || ||
max wi + 8 max
P
11
|ailli
8n 8ng8Lr
(n-P P
we ||: 112
n n- max wi + 87 max
(x(x(t) - F(x!1) x100]
(37)
P
||: 1
Similarly, we can bound E,
|gy
(2) |
to get
E
By
n(P- - 1)
P(n - 1)
R2
y,
(2)
P
n
|a:1
a
11
20
P
n - P
n - 1
max w; + 32 max willa: 11
|a 1
1=1
+ 1- P
max wi + BL
max
(k)
(Tx)
2
wi
a
(1)
(T. (T.)
(1,b) (1)
11 1
i
|ailla
P
0
111
k=
488.T.m + P
P
max wi + 82 max
wallall2
1
(o(x{()) - Fxx(1) -(x(0, ,y))),,(0)))
(38)
π1
||a:1|
Substituting (37), (38) in (36), and again substituting the resulting bound in (33), we get
Er (xx - (xx1) y((t1))]
(g)
- Totting
11-
1
x2
+ 9
Toftie7
An P
n n-P P
max wi + B8 max
wel [tllaa]] 12:112
(x(x(0) - -(0))),(0)))
4
n n- 1
|| 1|
9
2n
(n- P
max W/ + 537 max willa:112
/ ||
+ Toll
Tatt I 17
16
P
n - 1
i
||ail2
Teff (xii]
Lo n
n
w3l
||
1211
n n- P
1 + +25% max willa,1?
2
+ o6
2(mmax w/)
2
||all/
2
||:11] ?
Te (1yg11 + [n211t
oinn
n
w
wu?[|a]]]
2
2nog
n - P
wi aa 12 | 1
max wi + B8 max
2
P
lla:1?
n 7- 1
7eft 12
/ 11)
n(P 1)
(1
1
Tell Lo
P(n 1) T
E.
W h
2
P(n 1)
1=1
Teff
2
1
(PP - 1)
P(n - 1) Tettgblss)
Er
Σ
wi h (1)
y,
3/2 2
3rd
33
W4
(1) (T.) x.y (1)
(1)
Toff
[a:|]
|||
x.y
1=1
k=
1
Tetting
1-
2
+
9
Tattir An.BLbs
(n-P P
1 1 max wi + 88 max
we willa:112
))
(a(x(() 5(x)00,y(0)
|| 1
9
2n,88
P
max W7 + ot max willa:11]
1a.11 )) |
Tarr
16
p
n 1
Tea 1:0) n(P - 1)
(Lo + L,)EE,
Σ
wi
(0) x,i
2 P(n - 1)
1=1
35

---

Published in Transactions on Machine Learning Research (12/2023)
7eff 1x
1
n(P - 1)
Teff
Lg
Et
Σ
Wi
h
(0) y,
2
P(n- 1)
7/
Toft 2 Lo
n1
w
||
a
12
1- P
walla;1 1
2 10
00
2(max wi)
2 max
2
||
71
|a:1li
i=1
TapLs
oi
|a
2no
- P
wi aa 12
(hall (T213)
max wi 8i max
P
||:111
11
la:1l
+ TottTy (172)3 + +[ngg?)
13 Σ
Wi
aa.-
1112 ( Ma ([72)3 + [nn]] o
- Tamriy Ma |n
/ ||
+8L3 B (2x[n]] (ng]3) [x(x()) F(x(0, x000,,
(39)
where (a) follows since
(k) (Ts) n2 1
P
waa;
Tell 17
n max wi + 3 max
i
|a:
P 4
and (b) follows by using the bound in Lemma B.4. Next, we simplify the coefficients of different terms in (39).
Coefficient of E -
can be simplified to - F(x(1), y(t))
1 (1- TeRling 1
1
222700 17
Tentiny 4n18... P
max wi + 83 max
w/ aa 112 wi|laall
Yg
4
12 1
||a:1|
+ T
38 (2x(Ta]) + Ing]3)
T
$ 1
4
using 7/- S
75 1
T a max {8r max;
ws wi/|a:11 n-P [a.l] n-1 max; wi wi) S 61 KI 12
and B S 1
Coefficient of E Σn with (1) 2 can be simplified to
Teft 22
(Lo L,) n(P-npp 1 1) S har
n(P - 1) P(n - 1)
(: L & T.a)
2
P(n 1)
/
Coefficient of E
can be simplified to
9
2n,82 P
n P
wi willa; 1|2 )) ||a ||
TeftT 8
+
Teft
Ly
=
n1 max wi + 82 max
+ 881
16
9
4
Tefti 64x²
< Teff
+
+
16
64x
Toff
2 <
1
48x²
81
using 7 <
81x#
7/
n L
BG S /
and T n max { n--P
{ n-1 max, wi S2 max, willa,l1 }
la:1l?
} 5
36

---

Published in Transactions on Machine Learning Research (12/2023)
Coefficient of oz can be simplified to
Toff Tal
2
2
Lo
n P
w a 2
reff
2
(hgl [1al3)
2
lalli
2
P
a
+ Tattl
2 (1na) + (mg]²)
wi ||, -1;.-1112 112
$ Fof (17)) + (b))
11 P
we
|a:ll
+ 2T (bral + [ng] 1 72
Σ
a 1
w;
a
?
Coefficient of o can be simplified to
r n
2(max ws) n-
wi|laill
+ 259 max
2
P
12
i
|ail?
+
Le
(1?01?= + 1n:11,)
2n
n
max wA + B2 max
w. [a||a:1] 11 || 1
2
P
+ Toth 1.. (1101 + [m)]])
2n
n P
wi willa:l3 ||a;
Ly s Tal ( +
| La)
max wz + 89. max
+ 4ramy (h2)) + +1ggt) Ma.
p
n 1
Substituting these simplified coofficients in (39), and rearranging the terms, we get
Er ((x((++1))- - F(x((+1)) y(+)))))))())))))))
1 Testiil) (o(xx(0) - (3x10,y(0))
+
Tof
48
/|
L
n(P 1)
P(n - 1) E,
w
h (1)
x,1
wf
20 - P
max we 88 max will willasll 112
ran (1r5) T.p + 1T:]3T,0))
of
|a;1i |
||a:1|
i=1
2 (In)) + (ng]?) L3
2
Wi
aa.- 1 112+ G.
Ma
(40)
Summing both sides of (40) over t t= O,...., T 1 and rearranging the terms, we get
T Σ E (t)
Fxx(1),,)) ,((0)]
E ((x(T) - F(x(T), y(()))
((x(1))
F [xx (0) (0))
Σ
vi(x
Tattigu
T
T
12 2 T
t=0
Lod n(P - 1)
+
E
w. h (4)
+ 8KLL (In.] + 1n513)
of.
wi
||a.
+
20
20
Tifke
P(n 1)
w!?
P
willa;1? 1
+ 1 p
2
20 2
max wA + 89 max
(41)
|a
n
||a,11?
where, we use bi 2
Loo. This concludes the proof.
37

---

Published in Transactions on Machine Learning Research (12/2023)
B.4 Auxiliary Lemmas
Lemma B.6. If the local client function (x(x,)) salisfy Assumptions 1, 5 (In (ly-smoothness and p-strong concavity in y), then the function F satisfies
+ 4L3 ((xx) F(x,y)
V F(x.
2
s 2 vă(x)|
Proof.
2
2
V F (x, - vo(x) /
V=F(x,y
22
44 x)
+
22
44
x
21 y (x) yyl
(Ly-smoothness (Assumption 1))
4L2
2 (
+ P
x(x) - F(x,y)
(Assumption 5)
Lemma B.7. If the local client function f((x,)) .) satisfy Assumptions 1, 4 and 5, then the iterates
{x] (t,b) (t.b) y, (i,(,)) generated by Algorithm 1 satisfy
(Te) Vxxi .y: "y(
aa k=0
wel (alla:l]
(Ti (m)) (c.1) (1) + 20
max
|a:li 1l k=0
||a 11
maxx willa; 1
)
1 (x(x(1) - F(x(1), ((1)) + v 1²/
2T
+ 438
||all? ?
Proof.
n
5i-1
Σ
a
(1)
(T)
V (xx
(((1 ,
(1,b) .y!
= vxf((x((),
a
1
k=
< 2
w
(T))²13B
| x + | x2o1l"]
+2 +
af
E
V
(x(()) y(())
a 1 km
|aall
(Ly-mmothness)
<
n
W
T
la
(m) +2
max
Wil wa||a |
|a, ?
88 / y(1)|
+ oo
(Assumption 4)
Using Lemma B.6 gives the result.
Lemma B.8. If the local client function f((x, -) satisfy Assumptions 1, 4 and 5, then the iterates
{x] (x(" yi (e,(e,8) generated by Algorithm 1 satisfy
(1,b)
(1,k)
n
??
(4) (T.)
(1,)) .y, )12 1
laill
<
2
a
(t.)) +2 (T.
(1)
max
wi wi|la;
[06 + 23 (ō(x10) - F(x(0), y(0))
|
? k=
||a 1|?
38

---

Published in Transactions on Machine Learning Research (12/2023)
Proof. Following closely the proof of Lemma B.7,
(1.k) _y!1.)) = V Viri(x((") .r(0) p2 (x(0)((),xx00))
V Voli(x =
E
|
0=
2
19) (T))
(())) - x(01|²
| scolp?]
+ > w a:
2 B
V Uul (x((1)
|
12
||::1
i
1
(L (Ly-smothhness)
l0 ( (1) + 2
max
mc a
88 1T x|10)|
+ +00
|a
1
2
| 1
1=1
k=
(Assumption 4)
2
18) la (T)) x. (1) +
la
wa [ail|a]] max
2
[oc- + 28 (5(x(() - F(x(0,y()) y()))
||a
where the final inequality follows from smoothness and concavity of F in
B.5 Convergence under Polyak tojasiewicz (PL) Condition
In case the global function satisfies Assumption 6, the results in this section follow with minor modifications.
The crucial difference is that Lemma A.6 no longer holds. Lemma B.2 and Lemma B.3 follow exactly. The statement of Lemma B.4 needs some modification, since we use Lemma A.6 in the proof.
Lemma B.9. Suppose the local loss functions {fi] satisfy Assumptions 1, 4, 6, and the stochastic oracles
for the local functions satisfy Assumption 3. Under the conditions of Lemma B.9, the iterates {x] generated by Algorithm 1 satisfy
Yi .
(6) (0)
13
Pt
ps a -112 + ML (Iral + [ng]3) oā (k) (Ti) (t, (i) < 2 (Imll + [ng]]) L307 Ep,
k=
+ 8T, M
8 1 V {)) 2 + 8.I. Ma B8 (2/12)2 + (bg))) E [x(x(0)
F(xe1)) y(1)]
where Ma.
max; (1a,--1l + 3.. 1121| 112)
The bound in Lemma B.8 also changes to
V .y! )1
Ja
+2 max pillas 2 (k) (Tx) (T)) (1.8) +2
(oè + B. (5(x(()) - -F -(x))),()))
2
|a
a
k=0
The same bound in Lemma B.5 holds, but with more stringent conditions on learning rates, namely ||a.l|
B S Mo and T 18 f max (n87 max; ||a.l]] 1 S 64. Consequently, the bounds in Theorem 1 hold, under slightly more stringent conditions on the learning rates.
C Convergence of Fed-Norm-SGDA4 for Nonconvex Concave Functions (Theorem 2)
We organize this section as follows. First, in Appendix C.1 we present some intermediate results, which we use in the proof of Theorem 2. Next, in Appendix C.2, we present the proof of Theorem 2, which is followed by the proofs of the intermediate results in Appendix C.3. Finally, we discuss the extension of our results to nonconve-on---iinnconeee functions in Appendix C.4.
39

---

Published in Transactions on Machine Learning Research (12/2023)
The problem solve is
"
y(x,y) & wi wu.f(xx))) Σ i=1
min max x
y
We define (xx) maxy y) and (x) E arg maxy F(x. y). Since F(x,) .) is no longer strongly concave, y" (x) need not be unique. In Algorithm I-Fed-Norm-SGID SGDA+ the client updates are given by
=x =x (1) m x (L,k)
n V (1)) (.5) (1
(42)
(1,)) = (1)) + B/
( (k) D f((()) ,y)")) ((
where 1 1 k S Ty. The server updates are given by
(((-1) xx(0) Temigkk
((+1) y(0)) + Ten
(43)
(t) (0) where gx gy are defined in (3). The normalized (stochastic) gradient vectors are defined as
(1)
(1) (Ts) Vali
x :y; ( ((thi)):: h
(L.) (t.A),
(1) Vadss (x, .y;
(t.)) (..i))
8x
ai
a
|a.
k=
(44)
T
71
(1)
(k) a
(T: Vysi (/))) n
(k) a (T,)
Vyfi (x y(.i))
By.
ll
||:ll|
C.1 Intermediate Lemmas
As discussed in Section 5.2, we analyze the convergence of the smoothed envelope function T1 1/225- We begin with a bound on the one-step decay of this function.
Lemma C.1 (One-step decay of Smoothed- -.velope-- Suppose the local loss functions {fi} satisfy Assump- tions 1, 3, 7, and 8. Then, the iterates generated by Algorithm 1-Fed Norm--ooDaaaa satisfy
E o 1/22,, (x((+1)))
< SE
+ 2 Lj
w willaill (ol (2 + G
P P
n2
P
|aill?
n
1
n
12
+ 2Terr
17 Σ
Wi
(2) (T) (1) + L (xx(1)) - (1xx"),x(00)
Tofti
E
V
V
(x(1))
|a.1 I
8
(t.h) where Ax. (i)
= E.
111 + (ty( - yp is the drift of cliend E [n], at the k-th local step of [|x (1.b))
epoch t.
Between two successive synchronization time instants (for example, 1, l + 1), the clients drift apart due to local descent/ascent steps, resulting in the ( (1) terms. Also, E ((((()) - F(x()) y(())) quantifies the error of the inner maximization. the subsequent lemmas, we bound both these error terms.
Lemma C.2 (Consensus Error). Suppose the local loss functions {.fc) satisfy Assumptions 1, 4, 7, and 8. The stochastic oracles for the local functions satisfy Assumption 3. Further, in Algorithm 1-Fed- F-Fed-Norm-S Morm-SGDA- (t)
we choose the client learning rate nf, such that nf S (max, ||a: ) mix(1, Then, the iterates {x y
generated by Algorithm 1- ..eee--Norm-SGAAA satisfy
To -1
2
Wi
(4)
y (T. (1.0 (1) < (lng)2 + +mgg)) L30 Σ w; ||a + +417 (Ini)322 + -mn]1
a
0=0
40

---

Published in Transactions on Machine Learning Research (12/2023)
+ 8[1 L3 S8 -)x(()))- ( -((el)),))))
where Ma.. max, (Ia, +3,
Note that consensus error depends on the difference E[ F(x!") )) This is different from the term [x)(x(() - F(x(*) y(t)] in Lemma C.1. Since in Algorithm
the x-component stays fixed at ( for S communication rounds while updating y y,",A, the difference
(6+1)8-1
Σ E t=
(1(8()))(0)) -
can be interpreted as the optimization error, when maximizing the concave function F(x(+),) over S communication rounds. Next, we bound this error. The following result essentially extends the analysis of FedNova (Wang et al. (2020)) to concave maxinization (analogously, convex minimization) problems. We also generalize the corresponding analyses in Khaled et al. (2020); Koloskova et al. (2020) to heterogeneous local updates.
Lemma C.3 (Local SG updates for Concave Maximization). Suppose the local functions satisfy Assumplions 1, 4 and 7. Further, let (1x I R for all t. We run Algorithm
with client step-size
my such that 64[ng] Ma.; 1.p0G P 11. Further, the server step-size y satisfies
2Te max l1 max {ot
{ ot max
w. walla
n P
max Wi
|a
2n I.f n
l max
P -
L
82 max
|aill1
(k) (Ti)
10
Then the iterates generated by Algorithm Cei-NNoo--SDAAA satisfy
(8+1)8-1
E
((((+))
F(x(() _y00
S
4R
Teo n
w a 12
+ +200
n P
max wi + 87 max
wi a; 12
Terri
|a:11
n- 1
|| 2
+ 4L, + {
W/ ||a,-11 112 1/2+ 2Ma (G2 + oGa
o
i=1
where Ma max; 11 + 89, ||a..
Remark 10. It is worth noting that the proof of Lemma C.3 does not require global concavity of local functions. Rather, given x, we only need concavity of local functions {fr} at some point y" (x). This is preciscly the onc-pont-cconcavity assumption (Assumption 9) discussed carlier in Deng & Mahdavi (2021); Sharma et al. (2022). Therefore, Lemma C.3 for a much larger class of functions. Further, the bound in Lemma C.3 improves the corresponding bounds derived in existing work. As we discuss in Appendix C.4, this helps us achieve improve complexity results for nonconvex.onc--oont-coom
(NC-1PC) functions.
Next, we bound the difference E (xxx)) ((x())y(0)
Lemma C.4. Suppose the local functions salisfy Assumplions 1, 3, 4, 8. Then the ilerates generaled by Algorithm I-Fed-Norm- SeattNoom--D...... satisfy
T-1
T/S-1 (++1)8-1
(xx(0) ((xe(0))(0)) x T
Σ
Σ
E ( - -((((0) y((0)]
T
1=U
==0
tm
2T Gx 1) n
(o + 53 G2
P P-1
n1 - P
w?
41

---

Published in Transactions on Machine Learning Research (12/2023)
C.2 Proof of Theorem 2
For the sake of completeness, we first state the full statement of Theorem 2 here.
Theorem 3. Suppose the local loss functions {fi} satisfy Assumptions 3, 4, 8. Further, let || < R for all t. We run Algoritim 1-Fed-Norma-SGD.. with client step-size my such that 64[ng]2MM Ma_, 1, max 1) 1. Further, the server slep-size Ty satisfies
willaill
12
n-2 P
1
2T p max max
8z max
n max wi
| |1
8"
P
waa (Ti)
2T 2f L max
1 max aaill
Then the ilerales generated by Algoritim 1- 1-Fed- -.ee--Norm-SGDAA- salisfy
T-1
E
V 1/21,
(x(0))]== 00
(x
AS Tem
Aw (o2 (02+ + Gx PTeff
(n(P-1)
[n(P- 1)
Fw ))
T
P(n 1)
t=0
Aw
-1) + Fuo)
+0
Gx -1)
(o + (g, +
PT
P(n -
LiR
Tgl
A o6 Telf n1 n
+0
T E + Bin
Tarniis
P
n
+0 ((12)2 + (ng)3) 1.2 [Cro + D) (G2 + +o))))
where 11/2L, (x) minx (xx)) + Lef ||x - x|I² is the envelope Junction, AT T2/221 (xo) minx क $1/21, (x),
Aw - NTff Σi=1
w "o 11 B - max, willa.1lă Ew & n max; Wi, Cw - Σ.= wi wi([|al1 la (,, 1
aalli
and D max;(||a; 1
B2 |a |1.)) F A n(n
P) Em w/. With the following parameter values:
P(n-1)
( p1/4
p3/4
T TeOP
1/ = - = = LF773/8 , ,=== =
Y/ =
(Tof
S= A
where 1 ni Ei= T&e we can further simplify
min E 10 [1 so (E|T]
Eu (
1/1
+0 Cwo + D(G I aZ)
n
F213/1
Partiol participation
Local updates
+ +
AggiAn Aw
V1+
1/4
+
(1
Teyl
1/4
TTgPT
73/4
Au + Telf n Pan
R-P
Error with full symchronsaattin
Proof. We sum the bound in Lemma C.1 over 0 to T and rearrange the terms to get
(x(
E
V
1/21,
T
<
R
1/22, (x(0) , (x(+
TTT
- STamY
n
w |a Σ
(o + 37,02) + +6²
P-1 n P
+
Σ w
P
||
n 1
n
42

---

Published in Transactions on Machine Learning Research (12/2023)
161 T 1=0
T-1 Σ
E ((x(()) F(x((0, x(10)]
16
T/S-
Σ
(++1)8-1
13 Σ
T--1
Σ
a (Ti) A x.y
(8)
(1)
|0:11
tms8
k=0
8
$ 11/21, (x(10)
$ 12222, (x(7))
8TAM7 I.f n
w wFlla:1l
(ol + (/ + +
P-1
+ n
Σ
up
TearET
P
n 1
n
32 (I79)² + [(ng1)) 73
Wy
|a 12 + 6413,Ma (Iaa)e + Ingl303
(From Lemma C.2)
T/8- (++1)5-1
128
L2 G0T
1
Σ
E ())())) - -s(s(()) y(())]
1611, f T 1=U
Σ
E
((x()))
7(xx0,,100)
T
84g
w a;
P P-1
P n
<
8TaH1 I.j
(o) ( + G
+ n
Σ
T
||: ||
n n-
(where A3 - $ 1/22,, (xv) minx $ 11/21, (x)
n TT Σ
33 (17 + +ng]1) L2
W/ ||as.-113
+ 2Ma.. (ox + oy)
n 32 Gx v1
a
(o + (9.03 +
P 1
12 71
P
u?
P
laill
n
1=1
(From Lemma C.4)
18Ls
4R
+ Tamp nn
o Σ
n
wflla
||
1
208
n1 1 max w; + 32 max
P
wi willa;112
Teangs
||:11
||all?
(From Lemma C.3; using Am S min 1637 })
+ 1.
Ws a o Σ 1=1
|a.-
20 Ma
2
(45)
We can simplify the notation using the constants Aw - noeh Ei=1
"?[|a: B & Tean (max; mig ||a: 1 |ia l
|a.
Ey _ n max; Wi, Cn A Ei wa 1| D A Ma Fw a n 2 w/ and drop the numerical constants, for simplicity, to get
p
V T 1/2L, (2
E
T
t=0
A
Aw PToff
(oi.+ RA + G [(P-1) - 1)
+ (n- P)
(n-1) Fm)) ]
(n-P)
+ TottiaLyg
T
P(n 1)
Aw (07, + +. + +G
(n(P-1) - 1)
[n(P
(n (n- P)
+ G 11V
+
(n- - 1) Fw
Preit
P(n - 1)
L
(Aw + 06 Telf n1
(Ten" P
Eu + BubB)) + (118)2 + (nn]1) DD +o0)
+
Terrys
P
A
TT
R
+ Ter
p + +, Gx 1)T,
TTATT
F
+ ([ni]2 + ( 1 Cooo + D(G + oz)l,
(46)
where in (46), to simplify notation, we have defined I₁ 2 Au
PTan ( + G
(n(P-1)
P(z- + (x-1) F
Ig a f BB + Talt a-P Fo
43

---

Published in Transactions on Machine Learning Research (12/2023)
Next, optimize the algorithm parameters S, 72: 7/. My. my to achieve tight bound on (46). If R 0, we Substituting this in (46), get
let S 5=1. 1. Else, let S
V ait 25ngGiz
R
V 12, [x
Ab Tamr
+ T + Po G
+LiV
7
(IEA) + (n]]9) 1. Cmo + D(G2 aG)
(47)
Next, we focus on the terms in (47) containing T5. Lg To
RI %
To optimize these, we choose
2/3
(R G Substituting in (47), we get
7v =
22
Σ V 1/21, /x
AS
+ L + L, (7 (p
1/3
x Ten
+ (Ind) + (nd]t) Li [C + D(G + oG)
(48)
A- FWn b ( Ry GxIz 1/3
Finally, focus the terms in (48) containing -
We ignore the higher
3
(4 (GZI)) -1/4 and absorbing numerical constants inside O()
order linear term With 2 =
FarlLiT)
get,
V 1/21, (2
T t=
(Z 1/4
(ARTanP)1/4
I?
+
1p
+ +0
((17)) +0
+ [n 1 [Cwot D(G +o)))
(Tof PTYJ/4
T3/1
(I/I2)1/4
1/4
G2 + Fw Teff n- P E Euo 1/4
x G2(1 + Fw) Fu) Amo
0
+0
(TotPPT) 1/4
(TonPT))
(AgTeRP)IA
G2 1+ u- (I+
Fw
+0
+ O ((1g))+ + +mn])) 12 [Cwot + D(G + +o)))
(49)
T3/4
1/4
(An + Tott a- Em
Lastly, we spocify the algorithm parameters in terms of n, T, Tatts 7.
2 = 0 (
P1/4
2/ - 0 0 p3/4
(( S=
T
TeaP
Finally, choosing the client. learning rates ni " L,rr3/7; get the result.
Convergence in terms of F
Proof of Corollary 2.1. Following Lin et al. (2020a), we define
11/21, (x) A miny { (x(x') Ly ||x' x||
a arg min ((x') + Ly ||x' x
(50)
T 1 (x) A ming (xxx)) Ly ||x' x|1
x e arg min
(((x)) + Ly ||x' xx|?
44

---

Published in Transactions on Machine Learning Research (12/2023)
Also, it follows from Lemma 2.2 in Davis & Drusvyatskiy (2019) that 2 (x) 2L,(x x) and 101/22, (x) = fx x). Therefore,
| $2 V 1/11122, (x) - 1/2,, (x))
+ 2 V 101122, (x)|
= 813 || x1|² + V V 2
Consequently, we obtain
min T
v 1/22, (x(11)
||
-
T-1 Σ
4 1 (x((1))
T
2 T-
VΦ 101/22, (x(0)/] + 41.33 x x00
(51)
T
where X09 x(1) follow the same definition in (50), with replaced with x(1)
7
Proof of Corollary 2.2. If clients are weighted equally (w, p; 1/n for all i), with each carrying out steps of local SGDA+, then (6) reduces to
min E 1 [x] s00 ( (GPT)I + 73/4 AE|T]
(TP)1/4
0f + + +
)
+ (((m=p PT) ) )
n-
+ +0
r/3/4
For full client participation, this reduces to
1/21, (x())] (x/1)((((0))) 20( (mzz)iz +
(rn)1/4 73/4
min E (E|T]
To reach an e-stationary point, assuming nt S the per-client gradient complexity is TT = O (nee
(
Since < T/n, the minimum number of communication rounds required is 7 = O (1))
For partial participation, (("-- 1
PT ( -("
is the dominant term, and we do not get any convergence benefit of multiple local updates. Consequently, per- per-gradient client complexity and number of communication rounds are both Tr = O (p()), for - ((1). However, if the data across clients comes from identical distributions (ag 0), then we recover per-client gradient complexity of P and number of communication rounds = O (+)
Special Cases
Centralized, deterministic case (az = og = 0,3g = Tar = n== 1): in this case An B.s = 1, Cu D= 0. Also, I₁ = Gx / 3y
+ 1,I22 = 0. The bound in (45) reduces to
-
Σ t=
E V
)1 0
- T
+
L
+ 1)+ 87 +1
+ L
(52)
For Br, 0, (52) yields the convergence result in Lin et al. (2020a).
Single node, stochastic case (0g = 0, 0,3g = Te = n = 1): in this case An = B, = 1, Cw, = D =
Also, I = Vo + (3) + 1) I= oz. The bound in (45) reduces to
1 T 1
A T
T
1 (x /// 5
+
( + (8 + 1)G2) + )
0=
45

---

Published in Transactions on Machine Learning Research (12/2023)
+0 +0(4, Lr 1) (8,, , 1)
R
(53)
7
Again, for 3r. 0, (53) yields the convergence result in Lin et al. (2020a).
Multiple equally weighted (w, 1/n, V e [n]) clients, full client participation, stochastic case with synchronous client updates (Teff = 1): in this case A I, By 1, Cv D (45) reduces to
The bound in
(x( 50
( Ax YTT + وoايا
G2 o2 + +R
E
V 1
/21.)
n
(o T (oî 2z3l) Gx(S
of + B9G G2 + 1)
RIg 7
+ θ
(54)
n
Note that unlike existing analyses of synchronous update algorithms Woodworth al. (2020); Yun et al. (2022); Sharma et al. (2022), the bound in (54) depends on the inter-client heterogeneity og. This is due to the more general noise assumption (Assumption 3). In the existing works, 8%, is assumed zero, in which case, the bound in (54) is also independent of og See Appendix A.2 for a more detailed explanation.
Multiple, equally weighted (w: = 1/n, V i [n]) clients, full client participation, multiple, but equal number of client updates (T, = Teff = 7,4 i E [n]). In this case An B C, = 1, (r - 1)(r 1 + (2). The bound in (45) then reduces to
-=
or + +
1o + KLaE)
V (x()) B
+ mobs
G2
(55)
TYT
no
n
1=0
+
Ly T/ - 11/1 G2
o + B.C2
R
+ + 1) (112)= + (ns) レ3 O + 11 G2
nt
TTSS
For Br = 3G 0, this setting reduces to the considered in Sharma et al. (2022). However, stated earlier, our bound on the local update error is tighter.
C.3 Proofs of the Intermediate Lemmas
Proof of Lemma C.1. Using the definition in (50) (() arg min σ(x) Tyg x x(0 Also, note that
T 1/2L, (x((+1)) < ((((0) L, (x(1) x((1))
(56)
Using the updates in (43),
E x x (++1)
|2 = E x (()
+
T
wigx
(1)
sec(s)
= E (z(() x(0||
+ ret 12
Σ
(t)
+ 2T
((1) (1()
Wi x,
kEC())
< E (z(1) (+)) ||
+ 2 (1(1) (1)
V (x((() ,(())) + 1
(1)
w
1Ee())
+ EB
L
x (1) (1)
2
+
2
Σ
W;
T--1
a (7x) (v (vxf((x)
(k)
(c.k) (.(()))) vaf((x(!) (x(00))
2
L
|a
k=0
46

---

Published in Transactions on Machine Learning Research (12/2023)
E x((0
x0012 + T
Σ
gxg
(1)
(57)
(EC()
L x(1)
x100
W
M (T) ( +2(x0) V (1(1))
+ 12
+ 2
2
a
k=0
(58)
where (58) follows from smoothhesss (Assumption 1) and Jensen's inequality, From (18), (19), we can (t))
bound E
Σ Eie rx:gx. as follows.
E
Σ
S
(k) (a
(T:
oZ + 8EB V (x (1:))
a
k=0
n
P
+ n1 n P - Σ w |1
+
E
Wi h x,3
P
n wa 2
+ n(P - 1) 02 +
n(n P)
G n
(of + B3,G2
Σ w/
(59)
P
|a.1|
P(n (
P(n - 1)
where the final inequality by using Assumption 8. Next, we bound the inner product term in (58). Using Ly-smoothness of F (Assumption 1):
E (x(1))
x (0)
V (+) y())))))))))))))))) E (18",,y00) - F(x10,
-Fx) y( Ls
x(10_ -100 x(0]|]]
T (x) + L, | -x--x" x(01]] - 1F ,,1))
Li
x((1 - -x(1)) 2
E
E
2
E
6(x ()x + 1, 1-000-x-000 x0]1²]
-FF(x(1) y,,0)
Li
x(1) - x00 2
(by definition of x())
2
L1 |x(00 - xx(1) xx(0| ||]
E
((x10) F(x(1), y(t))
(60)
2
Substituting the bounds from (58) and (60) into (56), get
E T 1/22,, (x
< E
( (0) + L,, |x - 1x000
(P-1 n P Σ wi!
- L
n
(o + +2 + +02
+
P
n n
n
Tell L
- L
Wi
(T,
(1.A) xy
(i) 2Tam L B (xx(1)) - Exx!0 |(00]]
E
xx10 x(0
|ai l1
2
P-1
P n
<
E
1/22,, (x
+ T
Lj
(oz + B + 22
+
|a
n n-
n
+ 2T
1 Σ
1
Wi
71
(1) + E, ((x(0)) F(x((), [xx(0)y(00]]
Terr E
V 1/21, (x((1)))
|a;ll
k=0
where we use V 101/21, (x) 2T xx from (50).
47

---

Published in Transactions on Machine Learning Research (12/2023)
Proof of Lemma C.2. We use the client update equations for individual iterates in (42). To bound 4 (2.b) (i),
first we bound the x-error E
x ((.k)
x(o||" Starting from (24), using Assumption 8, for 1 S k S T6
1 0hh (T) |alll
Σ k=
-x
-
1ng
(1) (T.)
Σ
R-1
a
th (b)) (o2 + ( +
Σ
3 (k)
Σ
(
|a:11 k=0
1=0
y=0
- In]] oz ||a + Gx
(Ia + 22 ||a, 111
(61)
where we use (25). Next, we bound E (((())) - -y(1)) || using the bound from (29), to get
?
12) a
(1 (1.) - y00 s ong + 2,
+
(llas,1ll, + f2aa
Σ ai 12)
(T)))))))))
[a.
k=
k=
+ 2[n (11a, + S8 || (3) E
(62)
(c. (i). Taking a weighted Compared to (29), the difference is the presence of A (1 (i) in (62), rather than A sum over agents in (62), we get
+ 0g )
2 (k) (T) s 1
wi ||a; ||,,-1112+ + 2Ma
{8 V F(( (1) "
L
a
k=
(63)
where, we choose ny such that Am A 213 (nA? max, ||a:]] (laa.- + 82a) S 1/2 and define Ma
max; (Ia, + 88. ||a -11)). Next, it follows from sysoohhhsssss (Assumption 1) and Lemma A.7 that
E V F 2200) (x ( )( 2 ( - F(xle),
Subsequently, combining (61) and (63), we get
L
Wi
(T.) (1) < 2 (nna2 + (ngg't 1302 Σ
wi ||a; 112 + + (Ini2 + +ln]302))
k=
-=1
+ 811g) M2 ,
E
(x(()) - (18(0),y000)
which finishes the proof.
Proof of Lemma C.S. We define y (x((s)) E arg max, (((()),)) y). Then,
E y (x()))
y
(43) E (t + T
y ( |
= =E| yx())))
+ -
(ل6" 2
+ 2T y010) yx((()) Σ w. h (1)
(64)
(1) 2
Ei winl????
E
gy
is bounded in (38). We only need to further bound E
E
(t) y,
E
[a
(k) (T:)) (v (y()) Vyl((R()), ((0)) + v V8l(( ((())))))))))) )(1)))
aall
0mm
< 2
n
Wi
[a (T.) (1.2) (1) +2 ( ((0)) |2
(k)
(Jenscn's incquality)
f
|a:l] 1|
k=
48

---

Published in Transactions on Machine Learning Research (12/2023)
2 n
Σ
Wi
+ 4L, (T))4 (1)
( (3()(0) ( - (((8)),,(00)
(65)
a 11
k=
Next, we bound the third term in (64)-
E
y(0
y" (2)))
we h y,
= E
(x(0) - -y Σ
Wi Σ
[a (T:) Vi)8))))))))))))) (.!t))
la:l1
k=
Ui
la! (1) (T:) ((x(0) (y(())-,, -y,( V v2 ,y( )(((b)) + (t((ta)) - -x((²) Vyfi(2 {((,))
a
n
Wi
[0
(8) (T:)]BB f1(2((), y()) - f1(8 yy (1) + I's
(,10 - yy p
(L smoothheess
a
2
+ +1(2 ((())) - y (x(00)))
(Concavity in y)
1 n
W4
(1) la (T, 14 y (1) - ( F(x x(00]
(1)
(66)
=
2
|
k=0
Substituting (38), (65); (66) in (64), we get
E y((tt) - y ( |
]
S E (0(0 (8(1)))
+ h:
0
2
12
20
n- P
max w; + 83 max
w: willa: 1/2
|a
p
n
|| 11
- 2T
2Tarr 112rarmiTs T.s n
1
P - 1
+
P
max wi + 88 max
wi willa:ll 2
E
()()()))
F(8)())
p
n1
n1
||a:1l ||
+ La
+ 2T L
P 1
P
max w. + 87 max
w.a (1)
(Ti)
Σ
wi
la
(T.)
(1.00 (1),
p
n 1
n 1
i.k
|| aaill
|aall1
x
A=
(67)
since
A (t.k)
<
A (t,k)
x.
(t.k) Using the bound on A x.y from Lemma C.2,
n
Σ
Wi
(1) (T) ( < 2 ([ri22 + [n) of Σ wi ||a.-1112 + 4Ma. (1E + [1g)208)
a
k=0
i=1
+ + 1 BB (((()) - F()( .
(68)
We substitute (68) in (67), and simplify the terms using the choice of y ny to get
E y((tt) - ( (
< E |500 - y ( ||
+ 2
2212
on n
n w a
2
2
20
n - P
max w. + 3 max
wi 00 12
P
|a.11 2
p
||a:1] 1
- - ( -
+ 4
tr + (1 [ng13)
o Σ
wi |a -1,.-112 + 2Ma.. (G² + 0z)
1=1
using nÿ n that satisly
n2 P
n-1 + n1 P
waa (Tr)
2TH
max wi + 88
max
1
1
1,k
[a:1 1|
49

---

Published in Transactions on Machine Learning Research (12/2023)
P
n P
willagli
Wil |aalll 112
2n 19 I,f
+ 8
max wy + f8 max
p
n 1
n 1
||a:l1
4'
p T 21
2 Ma 1
4
p
Then the coefficient of E (()()))) )(()))
can we bounded by -TAM Consequently, by rearranging the terms and summing over t, we get the result.
18+1)8-1
Σ
-
y(0)
5
B Bl|yos (+(()))
+ Tetly n
2
w
|a a
2
+200
n - P
max w; + 187 max
wi milla: 12 ||a: |l
Teargs
u
0
||::l
n - 1
1=1
+ (.T,,(11)2 + [bg]3)
2
W/ ||a 11/ + 1aMa,1(3 +
L
1=1
Proof of Lemma C.4. Let t = sS, sS $ +1,..., (s 1)5 1, where k is positive integer. Let x(9) is the latest snapshot iterate for the y-update in Algorithm Fodd-Norm-SGDA+ Then
E (x) (x!1 |
E F(x (t), y (x ()) F(X()) ,x((0))) + yy - F(x(9) y(t) + F(x()), - F(x(0),(00) -
< E F(x y (x () - F((()) y'xx'""(x) (x) + E (S21 y (x(*)) F( ,())) y()) + GxE [x() - -x00
s 2G xx1)) 200 + ( - F(E(*)) y y())]
(69)
where, (-) E arg maxy F(. and (69) follows from Gx-Lipschitz continuity of F(,y) (Assumption 8). Next, we see that
E ( - x(0)| S v E [2(00) - x(1
(Jensen's incquality)
(43)
Teft v Σ
W Tixx
== SEC
S Teft?
-S-1) 1)
E
W. W.xx.
(P)
P'=sS
RECO''
wf a
P -
+ n P
< T5 - 1)1/
2
(oī
(3G3) -
w? (from (59))
P
|a.11
2
Using this bound in (69), and summing over t, we get
(++1) 1js
(++1)5-1
Σ E (x) - (x) (xx00)))00)) )00
E (x(+)) ,((0)),)(00))
S S
S
2Tart Gx(S 1)//
π
(o + G
+ G
P-1
n P
P
|
n-1
71
Finally, summing over 0 to T/S we get the result.
50

---

Published in Transactions on Machine Learning Research (12/2023)
C.4 Extending the result for Nonconvex PieePPoit--Coneeee (NC-1PC) Functions
Carefully revisting the proof of Theorem 2, notice that Lemma C.I and Lemma C.2 do not rely the concavity assumption. Lemma C.3 does use concavity of local functions {ft}. However, it is only needed to derive (66). Further, this only requires concavity of local functions at a global point y ()((())). Therefore, as mentioned earlier in Remark 10, it holds even for NC-1PC functions. This is an independent result in itself, since we have extended the existing convergence result of local stochastic gradient method for convex minimization (concave maximization) problems, to a much more general one-point-comue one-point-convex maximization) problem. Therefore, we restate it here for the more general case.
minimization (or
Lemma C.5 (Local SG updates for One-Point-Concan Maximization), Suppose the local loss functions (fi) satisfy Assumplions 1, 3, 4, 8. Suppose for all all the J salisfy Assumplion 9 al common global minimizer (x),, and that ||y" I R for all t. If we run Trd-Norm-SGDA+ with the same conditions on the client and server step-sizes ny. Ty respectively, as in Lemma C.3, then the iterates generated by Fed-Norm-SGDA+ also satisfy the bound in Lemma C.3.
Next, Lemma C.4 also holds irrespective of concavity. Therefore, the resulting convergence result in Theorem 2 for nonconvex-concary minimax problems holds for much larger class of functions. We restate the modified theorem statement briefly.
Theorem. Suppose the local loss functions {ft] satisfy Assumptions 1, 3, 4, 8. Suppose for all x, all the fi 's satisfy Assumption 9 at common global minimizer y" (x), and that ||x( s R for all t. If we run Algorithm -Fea--Norm-SGDA wilh the same condilions on the client and server slep-sizes rl. 7 respeclively, as in Theorem 3, then the iterates generated by Algorithm -.ed-Norm-SSGA- also satisfy the bound in Theorem 3.
Remark 11. Again, choosing client weights {w;} the same as in the original global objective {pil, we get convergence in terms of the original objective F.
Additional Experiments
For communicating parameters and related information amongst the clients, ethernet connections were used.
Our algorithm was implemented using parallel training tools in PyTorch 1.0.0 and Python 3.6.3.
For both robust NN Training and fair classification experiments, we use batch-size of 32 in all the algorithms. Momentum parameter 0.9 is used only in Momentum Local SGDA(+).
Robust NN Training. Here we further explore performance of Fod-Norm-SGDA+ on the robust NN training problem. We use VGG-11 model to classify CIFAR10 dataset, In Figure 6, we show the training loss curves corresponding to the results Figure 3 on varying number of local steps. Similarly, in Figure 6, we show the training loss curves corresponding Figure 4 on the effect of partial participation. In Figure 7, we demonstrate the effect of increasing data heterogeneity across clients, whle in Figure 9 we show the advantage of using multiple clients for the federated minimax problem. With k-fold increase in n, observe an almost. f-fold drop in the number of communication rounds needed to reach target test accuracy (70% here.).
We use batch-size of 32. Momentum parameter 0.9 is used only in Local SGDA+(M),
Table 3: Parameter values for experiments in robust NN training experiments.
Communication rounds
1-100
101-200
>200
Client Learning Rate (ng)
0.02
2 x 10-3
2 10-7
Client Learning Rate (ng)
0.016
1.6 x 10-3
1.6 x 10-4
Server Learning Rate (2 --=-0 7/)
1
1
Fair Classification We also demonstrate the impact of partial client participation in the fair classification problem. Figure 10 complements Figure 10 in the main paper, evaluating fairness of VGG11 model on
51

---

Published in Transactions on Machine Learning Research (12/2023)
2.4
Local SGDA+
2.2
Local SGDA+ (M)
2.0
Fed Norm-SGDA
1.8
1.6
1.2
1.0
0.8
25
50
75
100
125
150
175
200
Number Communications
Figure 6: Comparison of the effect of heterogeneous number of local updates {T,} the performance of Fed- SSrd-Nom-- (Algorithm 1), Local SGDA+, and Local SGDA+ with momentum, while solving (7) CIFAR10 dataset, with VGG11 model. The solid (dashed) curves are for E = 5 (E = 7), and = 0.1.
2.4
PCP (P-5)
2.2
PCP (P-10)
2.0
[n=15)
1.8
1.2
1.0
0.8
50
100
150
200
250
300 350 400
Number Communications
Figure 7: Comparison of the effects of partial client participation (PCP) the performance of Fed-Norm- SGDA+, for the robust NN training problem the CIFAR10 dataset, with the VGG11 model. The figure shows the robust test accuracy. The solid (dashed) curves are for = 0.1 (a = 1.0).
CIFAR10 dataset. We have plotted the lest accuracy of the model over the worst distribution. With an increasing number of participating clients, the performance consistently improves.
Batch-size of is used. Momentum parameter 0.9 is used only in Local SGDA (M).
Table 4: Parameter values for experiments in fair classification experiments.
Client Learning Rate (ng)
0.02
Client Learning Rate (n
0.016
Server Learning Rate (o = +)
52

---

Published in Transactions on Machine Learning Research (12/2023)
Vanying Heteregenetty
actuney
Ding .01)
Ding(0.055
Dirg
Ding (0.5)
Dindll
Din 0.00
distribution
23
52
75
200
:25 150 175 200
No. comm.
Figure 8: Effect of inter-client data heterogeneity (quantified by a) on the performance of Fed-Norm-SGDA+ in a robust NN training task.
Speedup
2.2
26
Number of clients
Figure 9: Effect of increasing client-set on the performance of Fed-Norm-SGDA+ in robust NN training task.
50
P-15
P-20
40
Test Accuracy
30
20-
10-
20
40
80
100
Number of Communications
Figure 10: Effect of partial client. participation on the performance of Fed-Norm-SGDA in a fair image classification task.
53


Reviews:
[{"review_id": "fLHYFuADpq", "reviewer": "Reviewer_E6s9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper proposes a simple yet effective algorithm that simultaneously tackles inter-client data heterogeneity, partial client participation, and system heterogeneity issues in federated nonconvex minimax optimization-- making it very practical. The proposed algorithm also enjoys provable convergence rates for NC-SC/PL and NC-C/1PC objectives, and improves/mathces upon known results in terms of communication complexity. The paper nicely discusses the results in the context of existing literature and the analysis looks sound as far as I checked. Overall, the paper is well-written in most aspects (except minor edits that can be fixed with a careful proofreading– see below for some examples). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers optimizing a nonconvex minimax objective in a federated setting where the data distributions and system capabilities vary among participating data holders.  The authors propose a general communication efficient (via periodic averaging) method that facilitates an unequal number of local steps among clients and establish convergence under different assumptions on the loss functions. The proposed method, a simple normalization tweak incorporated into standard Local SGDA,  subsumes existing literature on Local SGDA as a special case and obtained rates improve upon known results in terms of communication complexity. \n\nThe key observation is that in the presence of heterogeneous local updates, the Local SGDA converges to a different objective where the components (local empirical losses) are weighted differently, as a result by proposer normalization it is guaranteed to converge to the original empirical loss. The theoretical results are complemented by empirical results on robust neural training and fair classification problems. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In the experiments, it is not clear what learning rates used both in client and server sides. In Lemma B.5, the server side learning rate for x is $O(\\kappa^2)$ times smaller than y, and I was wondering if this is the case in real experiments as well. \n\n- The reduction in Eq 2, reminded of analysis of networked distributed optimization over a star network and I was left wondering how the proof techniques here (specifically handling different number of local updates) compares to the analysis methods in that context, e.g., the paper below:\n\nKoloskova, Anastasia, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, an Sebastian Stich. \"A unified theory of decentralized sgd with changing topology and local updates.\" In International Conference on Machine Learning, pp. 5381-5393. PMLR, 2020.\n\n\n-- Minor --\n\nSome examples below (there are many more, and the authors are encouraged to proofread carefully)\n\n- Page 5: the equation right after paragraph starting ‘Generalized Local SGDA Update Rule.’, both updates are ascent, for x it should be decent\n- Page 2: Section 5.1, 5.2 → Sections\n- Eq 2 needs alignment\n- Lemma A.4 & A.5, these should be vectors and bold faced\n- …\n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oSyicixilS", "reviewer": "Reviewer_2XcN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n\n1. It achieves state-of-the-art gradient complexities in both NC-SC and NC-C settings. \n \n2. The improvement in the communication cost is evident in theory. In NC-SC setting, it improves from $O(\\epsilon^{-3})$ to $O(\\epsilon^{-2})$. In NC-C setting, it improves from  $O(\\epsilon^{-7})$ to $O(\\epsilon^{-4})$. \n\n3. In the full participation setting, a linear speedup is achieved, which is reasonable. \n\n## Weakness and questions\n\n1. I think it does not really consider different optimizers for each client. In Algorithm 1, each client only utilizes a stochastic gradient descent/ascent type update, differing solely in the stepsize employed. In this case, the introduction of the more general SGDA update rule on Page 5 appears unnecessary.\n\n2. The derivation of Corollary 1.2 is unclear. In equation (4), the first term incorporates $\\sqrt{\\frac{n-P}{n-1}}$, but in the proof of Corollary 1.2 on Page 26, the square root for this term is absent in the first equation. Additionally, in the second equation of this proof, when full client participation is assumed, it seems that the second term should be $1/\\tau T$ rather than $1/T$.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on federated learning in the context of minimax optimization, with the primary objective of reducing communication costs while preserving the optimal convergence rate. The key contribution lies in considering two settings: nonconvex-PL (including nonconvex-strongly-concave as a specific case) and nonconvex-one-point-concave (including nonconvex-concave as a special case). \n\nIn comparison to previous works, this research offers two generalizations within the settings:\n\na. System Heterogeneity: The approach accounts for scenarios where each client performs a distinct number of local steps.\n\nb. Weighted Component Functions\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some other minor comments:\n\n1. The definition and usage of $w_i$ and $p_i$ are confusing. In (2), $w_i$ is initially defined, but later, in the line above (3) and Corollary 1.1, it seems that we have the ability to set $w_i$. I recommend improving the clarity surrounding this aspect, although it is currently understandable.\n\n2. Typo in (2): $G_i^t$ should be $G_{x, i}^t$.\n\n3. Typo in the equation of (8): $y^{\\prime}$ should be corrected.\n\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hMOnIoiE14", "reviewer": "Reviewer_YTqc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall this is a very good paper and I'm supportive of it appearing in TMLR. The topics addressed in the paper are certainly of interest to the federated learning community. The paper is generally well-written and the results appear to be both sound and a substantial improvement in rates over the previous literature. By properly addressing issues like partial client participation and systems heterogeneity, this paper reduces the gap between federated minimax optimization algorithms/analyses and federated learning systems in practice.\n\nNo significant weaknesses noted. Rather than be repetitive, I mention the few suggested changes I have in the next section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers federated minimax problems, motivated by applications such as robust/adversarial training and fair classification. The paper studies variants of the stochastic gradient descent-ascent algorithm with local updates, while also accounting for challenges such as partial client participation and \"systems heterogeneity,\" realized as different clients running different numbers of local updates per round. In this sense, the paper can be seen as an extension of the FedNova method to minimax problems. Theoretical analysis in several relevant scenarios shows that the proposed methods achieve superior convergence rates than prior work. Experiments validate the theory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The notion of stochastic gradient complexity in Definition 2 is only well-defined and meaningful if all clients perform the same number of local steps and participate in exactly the same number of rounds during training. I suggest updating it to reflect the more general scenario considered in the paper.\n\n2. Davis & Drusvyatskiy (2019) study the Moreau envelope in the context of non-smooth weakly convex minimization. It may be worth mentioning if any of the assumptions (Assumption 1 or 7) imply that $\\Phi$ is weakly convex. Is an additional assumption needed for $\\Phi$ to be bounded below?\n\n3. In the experiments, in addition to showing test accuracy please also include training accuracy, since this is the quantity the algorithm is actually optimizing.\n\n4. Nit: In Theorems 1 and 2, please clarify what are \"appropriate\" learning rates. In particular, which parameters of the problem do they depend on?", "broader_impact_concerns": "None noted", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers recommended acceptance. The authors should implement the changes and the corrections they have promised in their discussion with the reviewers. Regarding the discussion about the learning rates for Theorems 1 and 2, please at least include explicit pointers in the appendix for their definitions if you do not include them explicitly in the main paper.
Decision: Accept (poster)