Communication-Efficient Federated Group Distributionally Robust Optimization
Authors: Zhishuai Guo
Tianbao Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: Federated Learning
Group Distributional Robust Optimization
Communication Efficiency
Primary area: optimization

Abstract: Federated learning faces challenges due to the heterogeneity in data volumes and distributions at different clients, which can compromise model generalization ability to various distributions. 
Existing approaches to address this issue based on group distributionally robust optimization (GDRO) often lead to high communication and sample complexity.
To this end, this work introduces algorithms tailored for communication-efficient Federated Group Distributionally Robust Optimization (FGDRO). Our contributions are threefold: Firstly, we introduce the FGDRO-CVaR algorithm, which optimizes the average top-K losses while reducing communication complexity to $O(1/\epsilon^4)$, where $\epsilon$ denotes the desired precision level. Secondly, our FGDRO-KL algorithm is crafted to optimize KL regularized FGDRO, cutting communication complexity to $O(1/\epsilon^3)$. Lastly, we propose FGDRO-KL-Adam to utilize Adam-type local updates in FGDRO-KL, which not only maintains a communication cost of $O(1/\epsilon^3)$ but also shows potential to surpass SGD-type local steps in practical applications.
The effectiveness of our algorithms has been demonstrated on a variety of real-world tasks, including natural language processing and computer vision.

Communication-fficien Federated Group Distributionally Robust Optimization
Zhishuai Guo, Tianbao Yang"
Department of Computer Science and Engineering Texas A&M University
zhi zhishhuu@tamu.ed edu, Alaanba--yag@tten edu
Abstract
Federated learning faces challenges due to the heterogeneity in data volumes and distributions different clientss, which can compromise model generalization ability to various distributions. Existing approaches to address this issue based on group distributionally robust optimization (GDRO) often lead high communication and sample complexity. To this end, this work introduces algorithms tailored for communication-effiiiee Federated Group Distributionally Robust Optimization (FGDRO). Our contributions are threefold: Firstly, we introduce the FGDRO-CVV CVRR algorithm, which optimizes the average top-K losses losees while reducing communication complexity to (11/²), where denotes the desired precision level. Secondly, our FGDRO-KL algorithm crafted optimize KL regularized FGDRO, cutting communication complexity to O(1/c²). Lastly. we propose FGDRO-KL-Adam to utilize Adam-type local updates in FGDRO-KL, which not only maintains a communication cost of (11/2²) but also shows potential to surpass SGD-type local steps in practical applications. The effectiveness of our algorithms has been demonstrated a variety of real-world tasks, including natural language processing and computer vision.
Introduction
Federated learning enables effective model training without the need share raw data [3 48 is essential in contexts where data privacy and ownership are paramount, such as in inter-hospital collaborations [54] and mobile device networks [0). However, clients often have data of varying volumes and distinct distributions, which poses notable challenges in maintaining generalization behavior (50, 27). Generalization here refers to model's s ability to perform consistently across
different clients, including those that have not participated in the training [3 79].
In this study, we tackle the issue using federated group distributionally robust optimization (FGDRO), formulated as follows:
min F(w)
max PEAN
(.(((w) Ao(p).
Here, w denotes a machine learning model, and N represents the number of clients. For each client i, D; represents its local data distribution, and f<(w) Ea-DD,(w;; ((w;z) represents the loss calculated from that local distribution. An denotes a N N-dimensional simplex, which constrains Σ, P: = 1. The vector p [p..... .... pv] comprises the weights assigned to each of the clients. The function d(p) acts as a regularization term, with À > being an adjustable parameter. This framework aims to assign higher weights to machines with greater losses while discouraging substantial deviations of these weights from specified distribution.
*Corresponding Author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Our study concentrates on two particular forms of the regularization term o, which are well-established regularization techniques [T] 39] each suited to different tasks and data distributions. Specifically, CVaR is defined as ((P) [(o.//<((P) In this scenario, ((P) is set to O if each weight p. falls within the range of [0. 1/K], and is infinite otherwise. FGDRO-CVaR focuses on optimizing for worst-case scenarios or the average of the worst-case losses, making particularly effective in high-stakes applications like healthcare and finance, where avoiding extreme losses is crucial. However, it can be sensitive to outliers or malicious client attacks. FGDRO-KL -L, on the other hand, uses Kullback Leibler (KL) divergence,
N as ((p) = Σ P, log(P..). This version of Φ penalizes deviations of the weight distribution p from uniform distribution. Fundamentally, when @(p) is strongly convex, as in the case of KI. divergence, F(w) can enjoy a smoothness property, while non-strongly convex <(p) would result in non-smooth F(w) [6] In contrast to CVaR,, KL a softer regularizer to promote smoother and more stable learning. Thus, can beneficial in scenarios where robustness to outliers or malicious clients is needed. FGDRO-KL- KL-Adam further enhances FGDRO-KL by incorporating Adam-type updates.
Table 1: Comparison of communication cost and sample complexity on each machine to achieve e-stationary point or near to <-stationary point, where e-stationary point has a (sub-)gradien [[OF(w)]l& I 22. NDP-SONT denotes the naive deployment of the SONT algorithm [2 in federated environment, communicating in all iterations.
FGDRO with CVaR constraint Sample Complexity
FGDRO with KL regularization
Communication Complexity
Communication Complexity
Sample
Complexity
DRFA
0 (
0
0
(
DR-DSGD
((+))
((2)
30
NDP-SONT
(#))
0 (+)
0 (+)
0 (1)
22
This Work
(#)
0
0 (+)
0 (+))
Previous research addressing these optimization problems in federated learning has struggled with high communication and sample complexity issues, which are basically due to inefficient updates of p on local machines. For example, Deng et al. [I]] examined a particular case of the general formula (1) using CVaR constraint with K- = 1, and developed an algorithm for KL regularization as well. They update p only in global communication rounds, while local steps only optimize the local loss function using stochastic gradient descent (SGD). To achieve a e-stationary point or a point
near to e-stationary point, where e-stationary point has a (sub)gradient [[@F(w)] ||2 < e², their methods required a communication cost of (2) and a sample complexity of O(1/c15) (6) on each client. For FGDRO with KL regularization, [3) achieves communication cost of O(1/e)), but it requires the use of large data batches in local update steps in order to get good approximation for the surrogate of p. resulting in total sample complexity of ((1/c²) per machine.
To overcome these limitations, this paper presents specialized algorithms FGDRO-CVaR and FGDRO- KL for FGDRO with CVaR constraint and KL regularization, respectively. Instead of dealing with the constrained primal-dus formulation in ( we consider their equivalent forms with a compositional structure that get rid of the high-dimensional constrained variable p. We summarize the complexity results in [
For FGDRO with CVaR constraint, we are the first to consider constraint-free equivalent form and develop communication-efficiiee algorithm for it, significantly reducing communication costs, as shown in Table 1. In addition to sharing machine learning models, we only introduce an additional scalar threshold to select participants in each round, minimizing additional costs. The equivalent compositional form is a non-smooth two-level compositional function with one auxiliary variable s, which works as threshold. Only machines whose local losses are greater than s are supposed to contribute to updating the model. In this way, we can simply update the constraint-free scalar variable s locally in each client and average 8 in communication rounds. However, we do face challenges with non-smooth compositional optimization problems. Our first algorithm FGDRO-C CVaR effectively

---

addresses this issues and achieves a communication cost of O(1/et) and a sample complexity of O(1/e)) on each machine.
For FGDRO with KL regularization, while previous literature has explored constraint-free compo- sitional reformulations, they often require large batch sizes on each machine to estimate gradients, making this approach impractical and leading to high sample complexity. In contrast, we utilize moving averages that can work with smaller data batches while still providing accurate gradient estimates, enhancing the efficiency of our method. The equivalent compositional form we consider a smooth three-level compositional function. In this case, the weights for the clients depend on both local loss functions and global loss functions. We use moving average estimators of these statisties and update the estimators locally. In communication rounds, in addition to averaging the model w, the machines will average the estimator of the global loss function. We have reduced the communication cost and the computation cost compared to the literature as presented in Table [
To further enhance our approach, we have developed an adaptive algorithm for solving FGDRO with KL regularization, named FGDRO-KL-Adam. Stochastic adaptive methods apply variable step sizes for each coordinate based on historical gradient information, often yielding better results than non-adaptive techniques, as evidenced by wealth of research [13 36
49 69] In federated learning, while Reddi et al. [59] have developed a federated adaptive algorithm and shown its effectiveness in various tasks. However, limits adaptive steps to global updates on the server, with local updates relying on standard SGD, which may lead to suboptimal results. Moreover, their method is primarily designed for Empirical Risk Minimization (ERM) and is not applicable to address compositional optimization problems. Our (GDRO-KL-Adam allows local updates to use Adam-type updates, which introduces the challenge of handling unbiased gradients, further complicated by the use and updating of the second-order moment. To this end, we update the first-order momentum and second- order momentum locally and then average them globally during communication rounds. Moreover, our analysis carefully manages the moving estimates of the first and second-order moments, ensuring that the solution provably converges.
enables local updates with Adam typee methods, which raises the challenge of maintaining unbiased gradients, especially with the adjustment of the second-order moment. Our analysis meticulously handles the moving estimates of both first and second-orde moments to guarantee provable convergence. The first-order momentum and second-order momentum are updated locally and then averaged during communication rounds.
Our FGDRO-KL-LAA
In summary, our paper contributes in three main areas. First, our FGDRO-CVal algorithm greatly reduces both communication costs and sample complexity for FGDRO with CvaR constraint problems. Second, our FGDRO-KL algorithm achieves a better sample complexity while maintaining the same communication costs as the existing results. Third, our FGDRO-KL-Adan integrates adaptive step sizes with Adam-type updates, which has the potential surpass the performance of conventional SGD-base approaches. Extensive testing on diverse real-world datasets has shown that our approach achieves superior performance while substantially reducing communication overhead.
2 Related Work
Federated learning has gained significant attention due to its potential to train machine learning
models using data from various sources while ensuring data privacy [38
48
54
Two central
challenges to this field are communication cost and client heterogeneity. which have been extensively
explored in the literature [63 76 77 73 62 34 64 2 31 68 33
35| 71
70
34
[8].
This section
will dive into the body of literature that focuses on these specific challenges.
Non Clients in Federated Learning (FL) One of the key challenges in Federated Learning (FL) is managing client heterogeneity, particularly the issue of non-III (nonindependently and identically distributed) data across client networks. Efforts to overcome the negative implications of data diversity have led to the development of model personalization techniques [47 10
44 82 45)
75, 19 41. However, these approaches face challenges when dealing with data from unseen or unidentifiable groups. For comprehensive examination of the challenges and strategies concerning
non-lID clients in federated learning, the readers are directed to 27
Federated Group Distributionally Robust Optimization Since Group Distributionally Robust Optimization has shown effectivenss in addressing non-iid data in centralized setting 14 12, 56).
3

---

previous research has investigated Federated Group Distributionally Robust Optimization (FGDRO)
address the challenges posed by non- clients in federated settings [50 I.. The DRFA algorithm
11 focuses on a specific instance of ( applying CVaR constraint on p with K = 1. It samples machines based on updated probabilities to allow local updates, reducing the need for communication, with these probabilities managed by central server. However, this approach results in significant communication costs of ((1/e²)) and sample complexity of (1))e1b) per machine to achieve an e-stationary point. Recent developments in [22] introduced algorithms for handling Group DRO with a CV&R constraint in centralized settings, but adapting these to federated learning entails substantial communication overheads of ( Moreover, [7 introduced the SCAFF-PD algorithm, which is only applicable in convex scenarios and requires the use of the complete dataset in each training round. Regarding KL regularization, [30] achieved communication cost of O(1/e"), but required the use of large data batches, resulting in a total sample complexity of ((1/e") per machine. (80] has studied
FGDRO with KI. regularization in a decentralized setting, which would incur a communication cost. of O(1/e) if directly applied to centralized federated learning setting.
Federated Adaptive Algorithm Stochastic adaptive methods for minimization in non-convex stochastic optimization have garnered significant interest in recent years [13 36 49
69 42 84 [65]
46 25 16 8T. These methods, known for assigning unique step sizes to each coordinate, often outperform their non-adaptive counterparts. In federated learning, Reddi et al. (59 have advanced the field with an adaptive algorithm. However, their methodology predominantly applies adaptive steps at the global server level, with local updates still dependent on SGD. This could lead to suboptimal performance. Furthermore, their approach was tailored for Empirical Risk Minimization (ERM) problems and could not be applied for problems considered in this work.
3 Preliminaries
A function f is C-Lipschitz if f(x) f(y) S C||x- -yll A differentiable function f is L-smooth
if f - V f(y]] S L||x yll, where V fx) denotes the gradient. For a non-differentiable function f. its subdifferential 0f(x) is defined
set of all subgradients as 0f = fy) > x. When the context is clear, we also overload the notation (x) to denote one subgradient from the subdifferential set. We use fx(; or 0f z) to represent an unbiased estimator of gradient or subgradient with randomly drawn sample z. Additionally, a function f p-weakly convex if (x) 2 f(y) + (af(y).y
f(x + (v.y- - x) + o(lly- - -xl)) as
fly -
For smooth function f(x), is c-stationary point if [ < 2 For non-smooth functions, x is an e-stationary point if (0, (x))( < e², where dist(x, S) = minxes ||x x x'I22 measures the distance between a point and set S. For non-smooth functions, since is usually difficult or even impossible to find an e-stationary point, we instead seek an e-near stationary point.
Definition 3.1. x is an c-near stationary point of f(-) if Ex' such that ||x x'112 S and dist(O, (x)) S c.
4 FGDRO-CVaR
In this section, we present our algorithm designed to tackle Federated Group Distributionally Robust Optimization (FGDRO) with CVaR constraint. This problem poses substantial challenges due to the complexity of both CVaR and simplex constraints. Typically, during local updates, individual machines do not have access to adequate information to appropriately adjust the weight vector p. Prior approaches, such as the one proposed by [T, mitigate this issue by updating p during global communication rounds, but results in slower convergence rates. To this end, we reformulate the problem into an equivalent two-level compositional optimization problem without constraints:
K min min F(w, s) = N Σ f(a((w) -s) N
(2)
where f(-) = (+)+ and g:(w) = E.ZD, ((w, w, 2) is a local loss and s is intended to serve as a threshold > [(]:(w) 8') + K'', only the K clients with the highest losses will have losses greater than 8 83). During the training phase, K clients with the highest losses expected to predominantly influence the optimization process.
value. With arg min, N
,

---

The formulation (2) replaces the constrained high- -ihensninniin vector with single unconstrained scalar variable s. However, this adjustment introduces new challenges due the compositional structure and the non-smooth nature of the outer function f. As result, it is biased to estimate subgradient 0 (g( - 8) V) (w) using batch of samples. To address this, it common practice
to create an accurate estimate of Ds (w) 667 24
22
66
32
55 57] Specifically, we employ moving
average u as our accurate estimate:
- (1 31) - + Sz((w:
And then the estimators for sub- soth-gradient of w and 8, namely m, v are computed using u. is notable that for it is updated locally using local data and averaged between clients in communication rounds. It will converge alongside w an e-near stationaty point. This is a fundamental reason why our method achieves lower communication complexity compared to [Л], as the latter can only update the weight variables at the server node in the communication rounds.
Algorithm 1 FGDRO-CVAR
1: Initialization: w', s' = 0, un, = 0,
2: for 1.... R do
p-1 3: Wh. = w", % = 8", who0 1
4: for = 1,.... / do
5: Each machine samples data z,,,
6:
o = (1 - 1/
31 E 1 [.,))
7:
of = - - ./,--1 1) + N and 8 S 72
8:
m 0f sT,--1 17
(4,-1\4/ w i _.,)) and w!, = w 7/1 m
9:
end for
10:
W
N Σ W gr N
end for
12: Output: w
Σ
Whps where r' and are sampled from [1, R] and [1, I], respectively.
We present the formalization of our FGDRO-CVaR method in Algorithm D Next, we show the convergence results of FGDRO-CVaR We make the following assumptions regarding problem (
Assumption 4.1. (1) vi and Vz E D,, ((-, 2) is Cg Lipschitz and Ly-smooth. (2) EZED, V[(w;z)
Vg((w)]l < o², EzED, || (w:z) gi(w)]l < 2².
Remark. The first assumption about Lipschitz continuity and smoothness of gi is standard in
compositional optimization [22 66 67.. The second assumption of bounded variance is also common. Assumption 4.1 leads to F(w, (w.)) 8) being weakly convex, which is key step in the analysis as shown in Appendix A.2
The behavior of the estimator u is examined through the following lemma.
Lemma 4.2. Under Assumption 4.1 by setting 1) (1) 31 = (1/R), O(R).
Algorithm Tnsures that
BI 9.(w)) 12 < (1 1- B.)E g. (w 233 + 382m 2 + _.
5
Coll, w.-1112.
31
The convergence result of FGDRO-CVaR is given in the following theorem.
Theorem 4.3. Under Assumption 4.1 by setting 17 = (1/(R))8/2, 31 O (L/R), O(R) and
2.. the Algorithm I ensures that for the output (w, 8). there exists (w', 8¹) that
[dist(O, F(w', ((w's'))11 & 1/p(( w'll 2
s <'1BB) < 0
(4)
R1/2
Remark. The analysis has utilized Moreau envelop to address the nonsmooth issue 52 9 To
achieve an e-near stationary point of F(.), we need set ((1/e)) and / 0(1/e), and thus the sample complexity each machine is RI O(1/e)). The total sample complexity of O(n/e9)
5

---

by [22] is achieved by the STORM estimator [8] which incurs additional memory and computational costs due to the requirement of computing gradients using two models at each iteration. Without the STORM estimator, [22] would exhibit total sample complexity of (nn/e)). When deployed in a federated setting, the complexity for each machine would be 0(1/c), aligning with our results and demonstrating that our approach achieves a linear speed-up in terms of number of machines. Additionally, although we aggregate certain scalar variables (in FGDRO-CVale the scalar variable s; in FGDRO-KK KL and FGDRO-KL-AR KL-mdmm to be presented later, the scalar variable v), similar to the technique in the Remark 3.1 of [I,, we can aggregate these variables using homomorphic encryption, ensuring that their exact values remain confidential.
5 FGDRO-KL
In this section, we present our FGDRO-KL algorithm for solving problem T with KL regularizaatin. Unlike the CVaR constraints that focus on the top K clients, KL regularization takes into account all clients, assigning them varying weights. Additionally, FGDRO with KL regularization is smooth, and strongly concave with respect to p. Nevertheless, it is subject to the simplex constraint on To address this, we use an equivalent form derived from the KKT conditions, as referenced in [56
min F(w) = A Alog( w
exp(RxxD, ((w:))/A))
(5)
N
This formulation eliminates the constrained vector p. and F(w) smooth since KL regularization is strongly concave [6). However, this formulation has three-level composition structure and thus, using a batch of data in three-level composition can result in biased gradient estimation. Furthermore, the gradients on one machine are depend on other machines.
Specifically, we denote (w) =
(w: and 9(w) = Σ (((,,, with f(w; D2) =
ExED, Z(w then, the gradient of F(w) in 55) is given by:
1 N
g. w V((w; D:).
VF(w)=
(6)
It is crucial to recognize that the gradient for machine i, i... Vl(w; D:), is scaled by 9: (w)/s(w) This scaling indicates that machines experiencing larger loss functions exert more influence over the training process. To mitigate the biased gradient estimation, we approximate g:(w) and g(w) based on moving average estimators u and v. On each machine, u serves as a moving average estimator for the local loss function E(w; D:), with exp(u",,/ (X) providing a local approximation of (w). is updated and maintained locally without need for averaging during communication rounds. estimates the global statistic g(w). and is updated locally but averaged during global communication rounds. Subsequently, a moving average estimator of the gradient, denoted as m constructed using and v. For specific update rules, please refer to Algorithm 2
For analysis, we make the following assumptions regarding problem (I with a KL regularization: Assumption 5.1. (1) Vi and Vz E Di, ge(-) is -yp-isschitz and -s-ooooth. (2) EzED, / (V;;))))) Vl(w: 12 < -² EE EZED, [((wz) z) f(w: D.) < o². (3) f is CLipsschittzz and -mooth. (4) Vi and Vz E D, 0 < ((:i)) < Co. e(-) is Cr-Lipschitz and Ly-soh.h.
The behavior of the u and u estimators be bounded similar to the previous section and shown in Appendix B The estimator m for gradient can be bounded as
Lemma 5.2. Under Assumption 5.1 with proper constants C₁ and G. by setting 17 = O (TTT
81 = 0 ( (vrr) ) the Algorithm ensures that
Bg 2 ||m] VF(W))]1 <
1 N Σ
VP(WLIII+&BCCC ||m_1
e(W[-:;
+BC1Lo - (/ B3C2 0² +2,

---

Algorithm 2 FGDRO-KL
1: Initialization: w¹, u 0², m
2: for L..., R do
3: W = W., m m. 40-0 = u 11,0 = 1
4: for = 1.... / do
5: Each machine samples data _
6:
=h, (1 B1 B [ and iiz = (1 (1-32)uf,,
32)0 + B2 exp(ut,/A)
7:
h = exp(uf,a)
the V ),,,), and m = (1 (1- 1--33)mm ( + B3b
8:
W = -hi--1 -
9:
end for
N Σ
N
10: w
N
Σ
w i, o++1
N
u n and m
N Σ m
11: end for
12: Output: w- NV
whe i,y where r' and 1' are sampled from [1, and [1, /]. respectively,
Algorithm 3 FGDRO-KL-Adaa
1: Initialization: w|
0 1, 0__ mimmmna
2: for L.... R do
3: W = w", = m. 4: q", u¹,00 - and v0 or
4: for / = 1,... / do
5:
Each machine samples data -
6:
ui, = (1 -1--8p ) B1 (l (. and v/ = -(1 32)u + Bo exp(uf,/A)
exp(
7:
Ve( (
8:
m = (1-3g) (1-33)mmf,--0 + B3 Bsh and प. = -1- + (h
m
9:
W W 17 +r
end for
N
N Σ m and q = N Σ di
N
11:
w t. gr+1 =
N Σ
n++
N
N
end for
13:
Output: W
N Σ
whp where r' and are sampled from [1, R] and [1, Л1 respectively.
The precisions of the u, v, m estimators depend on each other. The idea get E Il - 1.) B o( w() 1|3, |m [F(T)] and /E[V/((W) jointly converge, and then we finally have the following theorem to guarantee the convergence:
Theorem 5.3. Under Assumption 5.1 by setting = ( B1 = - I = R1/3
Algorithm 2 ennures that
1 12/3
F 00
(7)
Remark. To achieve an e-stationary point, i.e., [F (1) e2, we need set R 0(1/e)), O(1/c), = O(c²) and 81 O(2²). Compared to B30 our approach maintains communication complexity of ((1/2), but significantly reduces the sample complexity on each machine from ( from O(1/ct,, requiring only batch size of O(1) rather than a large batch size of (11/²). Our results match the communication and sample complexity [7,, which tackles a simpler two- level compositional problem and achieved sample complexity of O(1/et) per machine. Considering that the sample complexity for two-level compositional problem in centralized setting would be Onn/e²) (66), our approach realizes linear speed-up proportional to the number of machines.
7

---

6 FGDRO-KL-Adam
In this section, we introduce an adaptive algorithm, FGDRO-KL-ADE to address the problem (5) with KL regularization, detailed in Algorithm 3 This algorithm incorporates Adam-type updates at local steps, which have been shown to outperform SGD in centralized settings. While previous studies [59] in federated settings have implemented Adam-type updates the global step but retained SGD for local updates, which may be sub-optimal.
Similar to Algorithm 2, and v are used to estimate the local loss and the global function ((w). respectively. The variables and m are updated in a manner consistent with Algorithm 2 Under Assumption 5.T the behavior of the v, m estimators is addressed as previously discussed.
The primary distinction Algorithm 3 lies in its adaptive updates for the local model w Here, m serves a role akin to the first-order momentum in Adam, and we introduce q to estimate the second-order momentum:
d. (1 - 34 - S. Subsequently, the local models are updated udaptively using the formula:
(8)
m
w 1 W
(9)
where both the square root and division are performed element-wise.
key step in the analysis is to address the coordinate-wiss update, as in the following lemma.
Lemma 6.1. Using L-smooth of F, for some proper constants C and G, by setling 1J = O VRT
31 = -0 (Viar. we have
( F(W,) S F(w, IVF(W,)) - "=300 2(G + +T) /F(
(10)
Finally, we show that FGDRO-KL-AdE has same convergence rate as FGDRO-KL.
Theorem 6.2. Under Assumption 5.1 by setting of 11 = 0 ( (vaa)) B O ( (VRl and I = R1/3,
Algorithm 3 achieves:
V F |1 0 R2/3
(11)
[VF(w]| S e,, we just need to set = 011ee), I O(1/e), (ce2) and 31 OE))). The communication and sample complexities are the same as in Theorem 5.3 Our analysis, following the framework (16), requires /q, + r to be both upper and lower bounded.
Remark. To achieve an e-stationary point, i.e.,
achieved by the upper bound assumption and choice of r, ensuring < G + 7, which is utilized similarly in [59]. However, Guo et al. [16 did not cover
S V9, + the federated learning scenario or the compositional problems. It is important to note that we have developed an Adam-type variant for FGDRO-CVaR. This is due the need for accurate gradient estimation in the analysis of Adam-type typp updates, which is achieved using the moving estimator m. But in CVaR variant, the nonsmooth nature renders moving average for subgradient aF(w) not provably accurate.
7 Experiments
Datasets and Neural Networks We use Pile 15 CivilComments 51, Camelyon17 [I] iWild- Cam2020 [3], and Poverty (74). For Pile, we preprocess it as [72], for the others, we use the preprocessed version by [37. We utilized natural data splits where data from the same hospital, web source, location, or demographic group were placed on the same client machine. These experiments have involved with highly imbalanced number of data clients. Data statistics are presented in the Appendix E. Additiona experiments on Cifar with Dirichlet distributions over 100 clients are reported in Appendix G

---

The Pile data set is a large language data set. We use the uncopyrighted version 22 which has 17 domains, and each domain is allocated to one machines. We use the GPT2 model [58] as implemented by [28] with 12 hidden layers, 12 attention heads, and 768 embeddings and hidden states. We measure the performance using worst log-perplexity and average log- log-perplexity of testing groups. CivilComments is a toxicity classification of the online comment task in diversified demographic identities. We train on four groups based on the presence of 'Black' and toxicity labels, deploying each on separate machine, and use the ERT base-uncased model [60] to predict toxicity. We measure the performance using worst group accuracy and average accuracy of testing groups. Camelyon17 focuses tumor detection from lymph node images [I] with data from five hospitals split into training (3), validation (1), and testing (1) sets. Training uses three machines, each processing data from one hospital, using DenseNet-12 121 [26]. The iWildCam2020 dataset consists of wildlife images from various camera traps [3, the dataset is split into training, validation, and testing segments. We use ResNet50 [21] across all datasets and measure performance via Macro F1 score. The Poverty dataset contains geographic data aimed at predicting regional poverty levels [74]. We use ResNet50 (21] for our models and evaluate performance using both the Pearson correlation the porst-performing region and the average across regions.
Table 2: Experiments on Natural Language Task, PPL is abbrevation of perplexity.
Datasets
Pile
CivilComments
Metric
Worst Log-PPL.
Average Log-PPI.
Worst Acc
Average Acc
FedAvg
8.005()0.0012)
6.785 (.7.5000.0033 (+0.0020)
0.6415 (=0.0007
0.7635 0=1.)
SCAFFOLD
7.975 (=0.0024)
6,901 (t0000031)
0,6436 (=.0016)
0.7633 (0:))0
FedProx
8.079 (+000038)
6.724 (+-0.006))
0.6430 (= 0.0002)
0.7692 (++0.0025)
FedAdam
7.242 (#:00008)
6.479 (=:0.0037
0.6567 (=.00233)
0.7664 (=E0.000)
DRFA
8.014 (+-0.0053)
6.702 (++0.0062)
0.6327 (=0.0019)
0.7413 (+-0.0022)
DR-DSGD
8.023 (+00.0033)
6.693 (#F0.0030)
0.6272
0.0006)
0.7523 (1F0.0011)
FGDRO-CVaR
8.145 (#0.0039
6.907 (#0.0046)
0.6693
(=0.0015)
0.7571 (=F0.0122)
FGDRO-KL
7.932 (10.0048)
6.664 (1.0.055))
0.6921
(=.00)
0.7734 (110.0020)
TGDRO-KL-Adan
3.608 (10.0052)
2.653 (100.0040)
0.6628 (=0.0007)
0.7614 (1.0.0005)
Table 3: Experiments on Image Classification Task
Datasets
Camelyon17
iWildCam2020
PovertyMap
Metric
Acc
Macro F1
Worst Pearson
Average Pearson
FedAvg
0.8723 (+00077))
0.4964 (+000125)
0.7301 (++0.004))
0.7782 (+-0.0077)
SCAFFOLD
0.8851
(=0.0063)
0.4527 0..0311)
0.7229 000099
0.7814 (#0.004
FedProx
0.8703 (+-0.017))
0.3925 (+-0.0228)
0.7305
(++0.0063)
0.7641
(+-0.0770)
FedAdam
0.9493 (=:.0122)
0.3570 (=000003)
0.7294 (+:0.0058)
0.8273
(1000041)
DRFA
0.8301 (#0.0174)
0.4200 (#0.0149)
0.7071(#0.0026)
0.7665
(+0000)
DR-DSGD
0.9270 (+-0.0955)
0.3157 (+-0.022))
0.7155 (+.0.0063)
0.7770
(+-000059)
FGDRO-CVaR
0.8667 (=000110)
0,5080 (=0.0174)
0.7443
(+0.0052)
0.7977
(+0.0051)
FGDRO-KL
0.9243 (#000129)
0.5201 (=0.0233)
0.7254 (+000066)
0.7829
(+0.0062)
TGDRO-KL-Adam
0.9399 (10.0154)
0.4485(10.0205)
0.7827 (100.071)
0.8225 (L0.0060)
Baselines We compare our algorithms FGDRO-CVaR, FGDRO-KL, and TGDRO-KL-Adan with
four baselines: FedAvg [48) SCAFFOLD 34 FedProx 40), FedAdam (59] DRFA [I] and DR- DSGD (30
We tune the initial step size in [lc-4, Ic-3, 1c-2, 1e-1]. All algorithms set the communication interval I = 32 unless otherwise specified. The local mini-batch sizes are set to 32. Experiments run for 20K local iterations except for Pile, which runs for 200K iterations. The / parameters of FGDRO-KL KL. and FGDRO-KL-Adam are tuned in [0.01, 0.1, 0.2, 0.5). For each algorithm, we repeat the experiments 3 times with different random seeds and report the averaged performance. Following [22, our FGDRO algorithms for Pile initially train for 20K iterations to obtain domain weights, which are then fixed during subsequent training phases.
Results We report the experimental results for natural language processing in Table and those for computer vision in Table 3 We can see that our methods outperform the basclines in most tasks. Our

---

approaches improve worst-case performance without hurting average case performance. Furthermore, Addm has demonstrated superior performance compared FGDRO-KL in most cases.
Ablation Studies Here present some ablation study to examine some aspects of our algorithm design. First, in Figure [[]] we vary the communication interval / in experiments on the Camelyon dataset. We can that both our FGDRO-CVal and (GDRO-KL-Adaa algorithms can tolerate skipping a large number of communications without degrading the performance.
To demonstrate the effect of the local adaptive updates. We develop LocalAdan algorithm (see Appendix D), which optimizes ERM using our design of using Adam steps in local updates. The results are plotted in Figure T(b) We can see that the LocalAdam algorithm outperforms FedAdam, which uses SGD in local steps and only uses adaptive steps global communication rounds.
1.00
Camelyon FGDRO-CVaR
Camelyon FGDRO-EE -lamd
Pile
Pile
1-8
1w52 1n5
Feciddom
Fededam
Yoeining Lose
6.300
1n
1n
Tie elecim
Testing Average Lop-
5.75
1=32
1e64
Training
Tramnin
2200
1200
Iterations (IKi
800
Iterations
iterations (-10k)
30
Iterations (*10k)
Varying I
(b) Effectiveness of Local Adam Steps
Figure Ablation Experiments
Conclusions
Our algorithm provides a significant advantage addressing federated group distributionally robust optimization while maintaining low communication and computational complexity. Furthermore, incorporating local adaptive steps has the potential to accelerate the training process beyond the capabilities of traditional approaches that employ SGD in local steps. Various experiments on natural lanugage processing and computer vision have confirmed our theoretical results and underscored the effectiveness of our algorithms. It remains to develop a provable adaptive algorithm for FGDRO- CVaR, which currently absent due the non-smoothness and compositional problem structure.
Impact Statements
This paper is meant advance the field of federated machine learning. We do not see noticeable negative impact.
Acknowledgments and Disclosure of Funding
We appreciate the feedback provided by the anonymous reviewers. This work was partially supported by the National Science Foundation Career Award 2246753, the National Science Foundation Award 2246757, 2246756 and 2306572.
References
[1] P. Bandi, O. Geessink, Q Manson, M. Van Dijk, M. Balkenhol, M. Hermsen, B. E. Bejnordi, B. Lee, K. Paeng, A. Zhong, et al. From detection of individual metastases to classification of lymph node status at the patient level: the camelyon17 challenge. IEEE transactions on medical imaging, 38(2):550-560) 2018
[2] D. Basu, D. Data, C. Karakus, and S. Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations. Advances Neural Information Processing Systems, 32, 2019.
10

---

[3] S. Beery, A. Agarwal, E. Cole, and V. Birodkar. The iwildcam 2021 competition dataset. arXiv preprint arXiv:2105.03494 2021.
[4] Bernstein, Y.-X. Wang, K. Azizzadenesheli, and A. Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning. pages 560-569. PMLR, 2018.
[5] D. Borkan, L. Dixon, J. Sorensen, N. Thain, and L. Vasserman. Nuanced metrics for measuring unintended bias with real data for text classification. In Companion proceedings of the 2019 world wide web conference, pages 491-500, 2019.
[6] S. P. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[7] Chen, D. Zhou, Y. Tang, 7.. Yang, Y. Cao, and Q. Gu. Closing the generalization gap of adaptive gradient methods training deep neural networks. In Proceedings of the Twenty-Ninth International Joint Conference Artificial Intelligence (IJCAI), pages 3267-3275, 2020.
[8] A. Cutkosky and F. Orabona. Momentum-baand based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
[9] D. Davis and D. Drusvyatskiy. Stochastic wwwoodell-bssse minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-233 2019.
[10] Y. Deng, M. M. Kamani, and M. Mahdavi. Adaptive personalized federated learning. arXiv preprint arXiv:2003. 13461, 2020.
[11] Y. Deng, M. M. Kamani, and M. Mahdavi. Distributionally robust federated averaging. Advances in neural information processing systems, 33:15111-15122 2020.
[12] J. Duchi and H. Namkoong. Variance-based regularization with convex objectives. Journal of Machine Learning Research, 20(68): 2019.
[13] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120u1):211-2215, 2011.
[14] Y. Fan, S. Lyu, Y. Ying, and Hu. Learning with average top-k loss. Advances neural information processing systems, 30, 2017.
[15] L. Gao, S. Biderman, S. Black, L. Golding, T. Hoppe, C. Foster, J. Phang, H. He, A. Thite, N. Nabeshima, et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2101.0000
2020.
[16] Z. Guo, Y. Xu, W. Yin, R. Jin, and T. Yang. A novel convergence analysis for algorithms the adam family and beyond. arXiv preprint arXiv:2104. 14840, 2021.
[17] Z. Guo, R. Jin, J. Luo, and T. Yang. Fedxl: provable federated learning for deep x-risk optimization. In International Conference on Machine Learning, pages 11934-11966. PMLR, 2023.
[18] Haddadpour, M. M. Kamani, M. Mahdavi, and V. Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. Advances in Neural Information Processing Systems, 32, 2019.
[19] Hanzely, S. Hanzely, S. Horváth, and P. Richtárik. Lower bounds and optimal algorithms for personalized federated learning, Advances in Neural Information Processing Systems, 33: 2304-2315, 2020.
[20] A. Hard, K. Rao, R. Mathews, S. Ramaswamy, F. Beaufays, S. Augenstein, H. Eichner, C. Kid- don, and D. Ramage. Federated learning for mobile keyboard prediction. arXiv preprint 1rXiv:1811.03600 2018.
[21] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
11

---

[22] Q. Hu, D. Zhu, and T. Yang. Non-smooth weakly-conver finite-sum coupled compositional optimization. arXiv preprint arXiv:2310.03254, 2023.
[23] X. Hu, S. Li, and Y. Liu. Generalization bounds for federated learning: Fast rates, unpartici- pating clients and unbounded losses. In The Eleventh International Conference on Learning Representations, 2023.
[24] Y. Hu, S. Zhang. X. Chen, and N. He. Biased stochastic gradient descent for conditional stochastic optimization. arXiv preprint 2077090002. 2020.
[25] F. Huang, J. Li, and H. Huang. Super-adam: Faster and universal framework of adaptive gradients. arXiv preprint vrXiv:2106.083)) 08208, 2021.
[26] G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4708, 2017.
[27] W. Huang, M. Ye, Z. Shi, G. Wan, H. Li, Du, and Q. Yang. Federated learning for generalization, robustness, faimess: A survey and benchmark. arXiv preprint 1.X65023 2023.
[28] Huggingface. Open ai gpt2 by huggingface, howpublished = /ntps::/muggingffce. docs/ otoo////so/ommmrsmmommololo/oo/
[29]
Huggingface. pile-uncopyrighheed h -ttp:://nnggiigaae..c//aaaasssse
[30] C. B. Issaid, A. Elgabli, and M. Bennis. Dr-dsgd: A distributionally robust decentralized learning algorithm over graphs. arXiv preprint arXiv:2208. 13810, 2022.
[31] P. Jiang and G. Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. Advances in Neural Information Processing Systems, 31, 2018.
[32] W. Jiang, G. Li, Y. Wang, L. Zhang, and T. Yang. Multi-block- Multi-block-siggle-preee single--reeeeeeeeeeeeeee variance reduced estimator for coupled compositional optimization. In NeurlPS, 2022.
[33] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems federated learning. Foundations and Trends@ in Machine Learning, (4(1-2):1-211 2021.
[34] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning. pages 5132-5143. PMLR, 2020.
[35] A. Khaled, K. Mishchenko, and P. Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519-4529 PMLR, 2020.
[36] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In Y. Bengio and LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http! //arxiv. www./ogg/////oooooooe//.ooeeee/e
6980
[37] P. W. Koh, Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Ya- sunaga, R. L.. Phillips, I. Gao, et al. Wilds: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021.
[38] J. Konečný, H. B. McMahan, D. Ramage, and Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv: 2016.
[39] G. Lan and Z. Zhang. Optimal methods for convex risk-averse distributed optimization. SIAM Journal on Optimization, 1318))1518-155) 2023.
[40] Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429-4500 2020.
12

---

[41] T. Li, S. Hu, A. Beirami, and V. Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning. pages 3357-6368. PMLR, 2021.
[42] X. Li and F. Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 983-992,44 2019.
[43] Z. Li, H. Zhao, B. Li, and Y. Chi. Soteriafl: A unified framework for private federated learning with communication compression. Advances in Neural Information Processing Systems, 35: 4285 4300, 2022.
[44] P. Liang. T. Liu, L. Ziyin, N. B. Allen, R. P. Auerbach, D. Brent, R. Salakhutdinov, and L.-P. Morency. Think locally, act globally: Federated learning with local and global representations. arXiv preprint arXiv:2001.01523, 2020.
[45] G. Long, M. Xie, T. Shen, T. Zhou, X. Wang, and J. Jiang. Multi-center federated learning: clients clustering for better personalization. World Wide Web, 26(1):481-500, 2023.
[46] L. Luo, Y. Xiong, Y. Liu, and X. Sun. Adaptive gradient methods with dynamic bound of learning rate. In 7th International Conference on Learning Representations (ICLR), 2019.
[47] Y. Mansour, M. Mohri, J. Ro, and A. T. Suresh. Three approaches for personalization with applications to federated learning. arXiv preprint arXiv: 10619, 2020.
[48] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Arcas. Communication--eficienn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[49] H. B. McMahan and A. Blum. Online geometric optimization in the bandit setting against an adaptive adversary. In Proceedings of the 17th Annual Conference on Learning Theory (COLT), pages 109-123, 2004.
[50] M. Mohri, G. Sivek, and A. T. Suresh. Agnostic federated learning. In International Conference on Machine Learning, pages 4615-4625. PMLR, 2019.
[51] H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust optimiza- tion with f-divergences. Advances neural information processing systems, 29, 2016.
[52] Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical programming, 140(1):125-161, 2013.
[53] W. Ogryczak and A. Tamir. Minimizing the sum of the k largest functions in linear time. Information Processing Letters, 85(3):117-122, 2003.
[54] S. Pati, U. Baid, B. Edwards, M. Sheller, S.-H. Wang, G. A. Reina, P. Foley, A. Gruzdev, D. Karkada, C. Davatzikos, al. Federated learning enables big data for rare cancer boundary detection. Nature communications, 13(1):7346, 2022.
[55] Q. Qi, J. Lyu, K.-S. Chan, E.-W. Bai, and T. Yang. Stochastic constrained dro with a complexity independent of sample size. Transactions on Machine Learning Research.
[56] Q. Qi, Z. Guo, Y. Xu, R. Jin, and T. Yang. An online method for a class of distributionally robust optimization with non-convex objectives. Advances in Neural Information Processing Syslems, 34: 1006--00000, 2021.
[57] Q Qi Y. Xu, W. Yin, R. Jin, and T. Yang. Attentional-biant biased stochastic gradient descent. Transactions on Machine Learning Research, 2022.
[58] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[59] Reddi, Z. Charles, M. Zaheer, 7. Garrett, K. Rush, J. Konečný, Kumar, and B. McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.0000 2020.
13

---

[60] V. Sanh, L. Debut, J. Chaumond, and T. Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.0/ 108, 2019.
[61] Z. Shen, J. Cervino, H. Hassani, and A. Ribeiro. An agnostic approach to federated learning with class imbalance. In International Conference Learning Representations, 2021.
[62] V. Smith, S. Forte, M. Chenxin, M. Takáč, M. Jordan, and M. Jaggi. Cocoa: general framework for communication-efficcenn distributed optimization. Journal of Machine Learning Research, 18:230, 2018.
[63] S. U. Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2018.
[64] S. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified sgd with memory. Advances in Neural Information Processing Systems, 31, 2018.
[65] T. Tieleman and G. Hinton. Lecture 6.5-rmsprop. coursera: Neural networks for machine learning. University of Toronto, Technical Report, 2012.
[66] B. Wang and T. Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. arXiv preprint 123.::22002.133966 2022.
[67] M. Wang, E. X. Fang, and H. Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Math. Program., 161(1-2):419-49, 2017.
[68] Wangni, J. Wang. J. Liu, and Zhang. Gradient sparsification for cew.muuniicaiio-fffcciieee distributed optimization. Advances in Neural Information Processing Systems, 31, 2018.
[69] R. Ward, X. Wu, and L.. Bottou. AdaGrad stepsizes: Sharp convergence nonconvex landscapes. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 6677-6686, 2019.
[70] B. Woodworth, K. K. Patel, S. Stich, Z. Dai, B. Bullins, B. Memahan, O. Shamir, and N. Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10343. PMLR, 2020.
[71] B. E. Woodworth, K. K. Patel, and N. Srebro. Minibatch vs local sgd for heterogencous distributed learning. Advances in Neural Information Processing Systems, 33:6281-622 62292, 2020.
[72] S. M. Xie, H. Pham, X. Dong, N. Du, H. Liu, Y. Lu, Liang, Q. V. Le, T. Ma, and A. W. Yu. Doremi: Optimizing data mixtures speeds up language model pretraining. arXiv preprini arXiv:2305.10429, 2023.
[73] Yang. Trading computation for communication: Distributed stochastic dual coordinate ascent. Advances in Neural Information Processing Systems, 26, 2013.
[74] C. Yeh, A. Perez, A. Driscoll, G. Azzari, Z. Tang, D. Lobell, S. Ermon, and M. Burke. Using publicly available satellite imagery and deep learning to understand economic well-being in africa. Nature communications, (1))::2583, 2020.
[75] K. Yi, L. Condat, and P. Richtárík, Explicit personalization and local training: Double commu- nication acceleration in federated learning. arXiv preprint 23Xi::2305.13170, 2023.
[76] H. Yu, R. Jin, and S. Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages
PMLR, 2019.
[77] H. Yu, S. Yang. and Zhu. Parallel restarted sgd with faster convergence and less communica- tion: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5693-5700, 2019.
[78] Y. Yu, S. Karimireddy, Y. Ma, and M. Jordan. Scaff-pd: Communication efficient fair and robust federated learning. arXiv preprint 2331: 2023.
14

---

[79] H. Yuan, W. Morningstar, L. Ning, and K. Singhal. What do we mean by generalization in federated learning? arXiv preprint 14.212110.14216,.22 2021.
[80] M. Zecchin, M. Kountouris, and D. Gesbert. Communication-effiienn distributionally robust decentralized learning, arXiv preprint arXiv:2205.15614. 2022.
[81] J. Zhang, S. P. Karimireddy, A. Veit, S. Kim, S. J. Reddi, S. Kumar, and S. Sra. Why adam beats sgd for attention models. 2019.
[82] M. Zhang, K. Sapra, S. Fidler, S. Yeung, and J. M. Alvarez. Personalized federated learning with first order model optimization. arXiv preprint arXiv:2012.08565. 2020.
[83] D. Zhu, Li, B. Wang, X. Wu, and T. Yang. When auc meets dro: Optimizing partial auc for deep learning with non-conver convergence guarantee. In International Conference on Machine Learning, pages 27548- 27573.. PMLR, 2022.
[84] Zou and Shen. On the convergence of adagrad with momentum for training deep neural networks. arXiv preprint 180.::1808.033: 2(3):5, 2018.
15

---

A Analysis of FGDRO-CVaR
For non-smooth functions, since it is usually difficult even impossible find e-stationary point, we are interested in finding an c-near stationary point. Following a common technique for finding an e-near stationary point for weakly convex function, we use the Moreau envelope of a general non-smooth p-weakly-convex F(x) [9]. defined as
12/0) (x) - =min(F(()))) + - 1 - -
By the properties of Moreau envelop [52 9. we have that if p = 2p, then (1)a()) is smooth and an e-stationary point of /1)) is an e-near stationary point of F(-).
Since F(w,s) is non-smooth, we investigate its Moreau envelop, which is
5 ((lww - wwl + I|s - s|]
(1yn)(w,)) s) = min F(w', s') + 2 w'."
A.1 Proof of Lemma 4.2
Proof. By updating rule, we have
Blluf, 9:(w;)) ||2 E [1(1 BLe -9: (w/)))
E (1 1+
31 2
2
|1(1 B1) + 3: 2 ( (1 +
Blll: (w(
31
(12)
where
[] - B1 30) +
- 9:(W111)1?
s B1](1 - (1)(uH,.-1 (:(W(())) (1(((W 25,)) (w B1 (((W,, - ((W,1,225.1)
$ (1 + 31 [BI((1 -B:) - (w/))) ( -
2
+ (1 +
),8111( -0))((w;.-.,2...) - 1(W/11 1,,1
31
31
B B1 ( (1
=(1
TE|((1 B:)
(1)((((,111 9:(w (1
2 18811((W,
+ (1 +
1(W 25
31
(13)
where the last equality uses E. [(( z[,)) 9: (w(w))) = 0.
Since f(, z) and g(- z) are Lipschitz and smooth, we know || < C2. We also have
N
|| l - w = ll(w"
m -(w"- Σ
m )11
N
1=1
#=1
(14)
2
mf e 12 + 2|
m we 11 < 1
i=1 #=1
Therefore,
E El|u,, - < (1- 3,) -
g((W(1))1
+ 02 + 4,8 1/ WT wh + (1+ 2
3/ [[9) - [W
(15)
2370² 43,17 T2 + 3
< (1 1
c w/-1l?
3
16

---

A.2 Proof of Theorem 4.3
Proof. Since f()) is I-Lipschitz, convex and monitonically nondecreasing, while {(:,2) is Cg- Lipschitz and Lm-smooth, we know that F(w, 8) is pF := Lg-weakly convex by
[(((w), 2 [(g((") 2 f(g(w'), + (V + () 5')
(. -g((g))) (V (, 88)
w') Lg ww
(16)
where the first inequality uses the convexity of f(-), and the second inequality uses that 0f(-) 2- 0 and the -moootttsssss of g(-).
With أ = max 2pr, 1, we define
min [F(w' + [(1 -w,ll + ||s - -1
((1/)) (w) min
(17)
and
(WI, arg min [F(w', ./) + P 2 ((l w|ll2 + ||s 1111,
(18)
then we have the following 9
|| w/ 12 || 57]1
Va/a (W], (w,, 57)11.
(19)
Then
B(v1/2 WT, 87)
E min w'.s'
F(w', + 2 ((ww- w|ll + 1|s 27 $/]13)
F(W ( + ! [1/ w/ll2 -118/- - -
E2
1 N
1
E
P(W 15 ( + 2
<1/w[_1 - ( - N
Σ
m ||1 + |155_1
(86 1/
Σ
131
1=1
F(w 15 1 + p
< E
(1 - w/-1112 + -| - 1
N
EE nWW wL11 N +
Σ
mi,)) + 17(8/_1 - - N
Σ
vi1e) - Cg.
1=1
1=1
(20)
where used || < Cg. Denote mf
Σ
Ouf (1 of
Σ O.f (uf 8/,-1):: where the sub-differential Onf ((,-1)) and 0,f [u] s/ are se-
17

---

lected the same in m and uh respectively. Thus,
/ [:)
F( 1, 82_1) + !
$ E
2 211 -w + +181 - 5 113)
+ P
[W w mm) + n -5 of))
+ PE
[W/1 11 m -m,) + 17(88 - 1: (fg)
+ +mp c2
F F( 87-1) 1)+ + P
6 (11W/- w 1| + || - 5. 1133)
E
2
+ p
[W/[1 -w mm,) + 1 55 o5/)
1 + 2 |w/-1 - -w,-1l' + "
||ا - - 112 112 + "
| m
+
17
+ pmp²
2
2
2
(21)
Since f is convex, 0uf 2 0 and is pg = we-wly convex, we have
(w,( f(u,, 1)1
2 Ouf(u,, 8 (9.
vhi,) + 0ff 57 56 1%,,-1)
2 O.f(u -
gi (W(W-1) 1) uh, + (V9.( Wi-1 - -W[-))
Pe
W[_1
w/-111
2
+ +0,f(uh -1) 1))
(22)
Noting 0,f < 1, 22 yields
(m, W wi-1) + (0 - 1/11)
( WI-1) + 1 51 - ,
N
Ouf(ul -l- uF,el] + Pg
$ N
W -w, w
2
(23)
Putting
21 and 23
together, we obtain
E B/v1/0
nP
ne
nd 2
nĀ
< Bl11// W 1-11 +
-w;_,112
11
- 1/
|m
m
|| 56
2
2
N + +mp + npp Σ
E
vi,el
+ Ps W - w,_,i 1
-Ely1/0 [W[11 11 32-1) + n1p
ne
|15
1/-1112 2|
np
jm
m 2 ne ller
2
2
2
N
+ + + np N
Σ
E
- f(
+
- f(ut (1)1))))))
s
- (u, S (he - -Vh,el + Pg || - w/-11? 11
2
(24)
18

---

Since (()) s) is Pe-wwekll convex in w, f(g((w),)) s) + ([wlw [[[ + +|ss -3--113)) is
I - sr-stonyy convex in w, s. Therefore, we get
f(a((W)))) 5[-1)
-[(()((W] 2 (11 w/-1l1² 1181-11111 [[-11
- -f 1), -11) + [11W/-1 w/ + -|s
(25)
GIIVE w6-1l 11 - || 1 - |12)
| 3/211
2
2
PF -)([I=T]1 W/_1 || + || - 8 113) + "/
11 1/1111
2
2
PF -1-111 1
16-1133) ( + pF 11,,1111111111 -5--112
Thus,
B|V1/2 (w),))
11
2 | - -ww
nP |5 - 11
n
|m m nP
I /01/0(W W/ 11,, +
2
2
2
O + n10 N
Σ
f(g: (W::(W(-1) 1): s6
+ fla of.11) - f(u s
- S 199 - -1,,l++ + Pg
||w - w/-1113
2
S (1 3/-1) + n | w. 112
nd || 1--11
7P
nd ||05 of
|m
m
2
2
2
N
+ 0g + np( PF
- [) - w/-11
1|5 3 113) + no(p + pF)
1
|
|
-
2
N
1=1
- + npC, Σ [1o:(w]]1) - nh,,ll + - w/_111
(26)
follows that
E El0r 3])
S 1h1/a 1.
4 n w/-112 11//2+100 +118/11 - 112)
+ + +npC, Σ (l/1( uT,1|l + n
112 + n
| m
100
1/-11
2
2
S //1/0 (Wi-1; 5/1) | /1V W 31113 + pm 2n
1 +no N
Σ
(lo:(w])1) uf,,1l + - C2
(27)
R
E (011)100111361111
RT
(28)
v /1 (
+ np0
ΣΣΣ
Blla(w[])) - uf,ell + 172 C
NRİ
19

---

Hence, taking telescoping sum over Lemma 4.2
sum we have
N
- (0:1-1-9(([[-)))
RIN
(29)
N Bil
o
c
22
B1 RIN
3
Thus,
R
V 3)1 (0
E
(w,
1/R + + B1R1
+
B1 + m/ +
7
RI
31
(30)
With
P [[| w/p2 + ||s/ =1|?)]
(w, arg min [F(w', 8') w .
(31)
2
We also have that || 2| + || - a||2 = // 3)|| 1 (F(ww8))
// 3) [9. We can conclude by setting parameters as in the theorem.
B Analysis of FGDRO-KL
B.1
Lemmas
The behavior u, which is an estimator of (w''s'ss, is given in the following lemma.
Lemma B.1. Under Assumption 5.1 with some constant G, by setting n = O (v Br
0
Algorithm 2 ensures that
VRI
81 Elluu - [(W 33,
Ellu5, [(w]: (()]: & (1
(32)
+ 12 123,
B m 3702 o² +
B CE
3
The behavior of v, which is an estimator of 1 N Σ, gi (w), is given in the following lemma.
Lemma B.2. Under Assumption 5.1 with some constant C1. by setting = O ( (v)h)) ). B1
Algorithm
ensures that
VRI
0 g(w,))l
& (1-1111110 B2) g( g(W(-))11
1
(33)
+3,2
CE ((w: + B2 C,Bll ?
N
20

---

B.2 Proof of Lemma B.1
N
Proof. Denoting w = N
1
Σ
W we have = r.m and
1=1
Bl|ug, -
B1 - 31),,,, +
- <(W]; D.)1
13]1 - 31)( [[ + - + (e(W]_1;D.) -
81
s E
1
11(1 ((1-81)(ufr-11 - -(((-;;PP(( +
-
2
+ IR
(1+
2
[1(w[_1: D.) - -.)
B1
$1
1 +
- -11(( - [(W]- D.)) +
-
2
3
+ + D.) -(WW :::)==
C. W ww/l?
31
(
1+ 31
[1 - (1) (
111 D,) - ((W)1;::)))1
3
+ 1. (1,111) ((WT.-1:D.)) D:)1 + 31
- w/ll
(1 1+ 2
B1
3 (WW]::::)11 + (1+ 2
(1 -
Di) [(w]_1: -e((w D.))
31
+ 1,300² +
B1
(34)
where (a) holds due to the fact that E,-1l((([,; [(W.,,; Dj)] = 0. Moreover, we have
E El(((w,,-1i D.)
< C w/ - - 11-111
< 2C W w/12 + +CC/Fl/ - w 1|
N
(35)
< 207
m 20
mf, 12
N
< 4C7r121
m m1|l
6C
E 11
and
E [lmm",
2 =E E
Σ (1 -1 13-
gl
V Ve( - (1 - BBs) 3
1
N
2
Σ
(1 (1-Bs))-1 -1
g V Vl(Ww. V + (1- 3B) m.
3sm_mb
N
1
< 2E
Bz)== -1 88g or
g
V V )1
N
+ 2E
(1 3a 3 - B3
k=1
ket
(36)
21

---

which yields
E
|
m
< 2t
83
[1|
==1
N
2/
33
1=1
k=1
< 881
[8]
V((
- ( D.)1
( ; + :::
+ N
S 1612 $161283071 17
Ci).
(37)
with C1 = exp(Co//) A). Thus,
B1
Ellui,, (.W:: s (1
[Bllur - -11-
((w + 3
2
(38)
+ -123,031 2
Σ
B| 3|
23:00000+000- +
3 C2n"El|mn
B
with C2 = 288(C29((02 + 07))
B.3
Proof of Lemma B.2
Proof. We have
1o0 - (( 11(1
-(( 12)0//1 + B2 N
exp(x),/A)- 2(w
= =I|1-Ba)6 - (2)(T[_1
,(W[_1)) 83
exp(uf,,/X) o(WE-1) -9(w)) + g(W(_1))
N
1+
B2
1-)( - g(W[_1]) + 32
(1
exp(ul,e/ 9(w(-1)
2
+
1+
(lo(w)) 9(W211)11
82
1 B2
(1 (1-1))
B2) 16 a(w[_)))
+1+
1+
2
32
1
Σ
exp((x,,/ (((1))
Br
N
+
C W/ -w_
32
N Σ - -((; +
< (1 -2) M(w] 1)12 117++30 3,3
cll - -W_,11?
N
Br
(39)
where C = exx:\((o//)
22

---

B.4 Proof of Lemma 5.2
Proof. Here we analyze the m, which the moving average estimator of the gradient.
N
m VF(W))12 = (1 (1- Ba)mi B3
1
g(u
- VF(w:)
1
< (1 (m) VF(W Ba(
exp(u
-
+ VF(W:-1) - vF(w:))
(+ 83
1
(1 1- + 8a(
-
2
N
1=1
(A)
1+ 2
|VF(W[-))- VFF(:)]
33
(40)
where
(A)
(1 - --sBBss -
N Σ
+ 83
(Ap(ut,/A)V((
N
N
N
+ 30
Σ
cxppuu,.-/A/VV(((
Σ
N
1
N
1/22
i=1
i=1
+ 83
exp(t(W/ (.) [
N
N
+ A3
exp(((<=:22))))<((< D2)
N
-VF((() -
+ 83
i=1
+ 83
(1 -
2
N
N Σ
1
+ 83
exp( /
exp( expput,--/AVV///...1111
N
N i=1
1=1
1 N
+ 83
Σ
1
exp (1 /XVV
exp :,p(((
N
Fm1
i=1
NN
+ A3
Σ
of
T
1=1
N
+ 83
VF(W,_))
N
t=1
N
N
+ (1 +
)8²
cxplut,/A)VV((W
3x
N 1=1
N
1
(41)
23

---

which is followed by
8g)
(A) -
(1- 1- -VF(Wi=1))
2
83
1
exp(uu,,_ /
1
N
N
1
+ A8
<pp((w
N
N
38
1
cxp((wW.:D.//))VVWWW.. -VP
VF(wL_))
-1:
N
o
+ +(1+
1+
83
83
1
1
e D.)
N
(1+
),8
(42)
Then leads to
m
(W(WD)
Ba
(1 (a) - VF(WF_1)
1
1
8g
exp(1 exp(o/.-/AAVV<((....33
N
N
+ 8
Σ
Σ
1
e.p( - 2
+ +.8g
N
Ba 2
N
+ +(1+ +
exp(u
exp
Di)
1 N
+
32
exp(u /V
Σ
B3
N
N
(1
+
+
[VF(WL)) - -FF(?))1
By
(43)
24

---

Thus, it follows that
B3
VF(W))11
1
- vF(
(1-
2
Σ
1 /
N Σ
3
83
N
33
N
33
33
33
N
8
1
1
1
Σ
exp(u(,,-/A)V
4
N
N
8
1
1
1
33
33
N
J/1
2
+
1
-
B3
(44)
We address each term as follows. ! can be bounded as
N
N
E
83
exp
D.)
N
N
1/
83
- ([W[1;::))]
(45)
2
can be bounded
N
8,3
Σ
D,)
1
$ E
1633
N
1
1
1
E
16,3
N
N
b
<163,C8C9//
w|ll
+ 1633
-
$ 2
163
Σ
N
(46)
25

---

can be bounded as
N
8/3
16,3
/ppp D.)
g W
i=1
+
E
1683
N g(w[)
N
g(w])
N
1
16
163
- w
|
N
(0)
32 g(w))
3233
||]l
+ 64
- 960
(47)
where (a) follows from 335 can be bounded
N
N
exp(uf, Di)
N
1=1
83 N2
E
expputt-:/AVVWW.....
exp(w explvl,--/AAV(( Di))
1=1
< 8 02
N
(48)
machines independent conditioned on iteration 1.
can be bounded as
N
N
E
833
N
N
1=1
<
E
8,3
-
E
24,9g
N
N
+
IE
24
C2
N
1=1
1
+E
243
|explot /
N
1=1
1
< <4830030002 +E
243a
< 488,033002 + 24
(49)
where the first inequality uses vf. 2 1 as E(.) 2 0.
26

---

F(w) is LF := و + smmothh With n S (3L G can be bounded as
1
2
B1 BIIF V < - L3
3 B3 w/l
E||
3/
$ n/ [m m + + 7
V F +- +n
$ 3/ mi
-m 112 31/ i
(50)
< 3n 3n(483 -
1, 488CC +0²)) +04))
VF((
+ 1 +
< 1 VV-WW-FF V|
where (a) uses
E m
m -1-111==11111 11|
Ba)m; + +B3
g(u Vel -m
N
(51)
< 220 + 2
Σ
g
N
Thus,
VFF()) 5 ( | - + N Σ Gf - - Di)]
N N
+ +633 + 163g
c - 5ا
323, g(w]) + 323, 990 " mil?
E||m,111 + 3300 o²
+ 6107n112 Σ
| - 96C
+ +883, 243 243,17
+ 4n m - (F(WW-))
+ +
(52)
We conclude the proof by setting the parameters in the Lemma.
Proof of Theorem 5.3 Using Lemma 5.2 with 33 = 0(3s), we have
1
m VF(w
1122
E
m
VF(W;))2
+25 + + N
RI
RI
R
1
E 1
VF(W 12
nEl|VF(W[ 2) +8702)
RKN
RI
(53)
27

---

Using Lm-smooth of F, we have
F(W)) S F(WL)) (WE -w + LF ww w/-1l?
= - - - ii + LF
2 ?
S F(([ -/F (m) +
+ (
(54)
S -/W.
VFF(LL))
4 ([lm; VF-VFFFWWW )| [VF(W,
S F(W[-1)- " "IV )1
31 | I VF(W1_1))
Therefore,
R
<0
+ 3100 + 831 + nLP) (55)
E V[F
E
VF (
RI
n/I
We conclude the proof by setting the parameters as the theorem.
C Analysis of FGDRO-KL-AAdm
Proof of Theorem 6.2
Lemma
B.1
Lemma
B.2 and Lemma
5.2 still hold. Specifically, denoting
w W we have
El - e(W;; D
n +880²
< 11-1i)ll,,0-1
C2lm; VFF(W)) (56)
31
72 CIVF
3
where (a) holds due to the fact that Ee-r(((w[, e(w7,;; D.)] 0.
And we have
|oo - ((w)))l2511 (1-B)]le 9(w[-1]11 3,3 Σ
-
- =(W;
B2 Clll w7_1l1
(57)
where C₁ = exp(Co/A).
Moreover, have
1
E
m VF(W))12
+25 + σ²
i VF(W[,)11 = 0o
RI
RI
N
R
1
E U -
VF(W!))
nEI|FF(W 2)12 -8000)
RKN
RI
(58)
28

---

Using smoohh of F, we have
L
F(W[) S PF( VP(()))))))))))))) -w(1)
1w; w.-1l?
FF(W;))) VF(W. () (ip: m;)
I.
1177 о mm
L
F(([-1)) マ vh (VF(W -m
Il 11 1
11 m / 5llv
2
$ <F(W(-1) + 7
W m m
7
[VF( 1112
1/2/T²
n/(G/ + r)
n/
|m
2T
2(G +T)
2
S F((W[[)) + リ VF( m. 1 1| !
m -m,
m
VF 1)12
2(++T)
S F ? VF((W_)) m - C
VF(([-)))1
2
(59)
Therefore,
E
ΣΣ
R
VF
DI?
<
1 0o
+ + B + nLcC)
1RT [ 3102
(60)
RT
P=
We conclude the proof by setting the parameters as the theorem.
D LocalAdam Algorithm
In this section, we present Algorithm which uses Adam type updates in local steps to solve an
ERM problem.
Algorithm 4 LocalAdam
Initialization: w/, m
2: for r = 1.... R do
3: who
m m 9. = q"
4: for = 1..... do
5: Each machine samples data z
6:
h,, V((w x.,))
7:
m = (1- Bg "s) . m
+ Bah q. = -11 (1-8a)qf,,1 + (b
8:
W = w /r
9:
end for
N
wi+1 N Σ w m r+1
N Σ
m
and qr
Σ E
N
i=1
11: end for
E Statistics of Datasets
Table 4 summarizes the sizes of the datasets used. Table summarrzess the client imbalance ratio and the class imbalance ratio. The client imbalance ratio represents the ratio between the number of training samples the client with the most data and the client with the least data, and the class imbalance ratio reflects the ratio of training data in the largest to the smallest classes in classification tasks.
F Running Time
Running time is reported in Tabel 6. Each algorithm was run on high performance cluster where each machine uses a NVIDIA A100 GPU.
29

---

Table 4: Number of data for each split, with the number of training domains in the brackets. Number of training clients in the last column, with data from the same training domain to be on the same client.
Train
Validation
Test
Num of Clients
Pile
192,912,246 (17)
193,105 (17)
193,105 (17)
17
Civilcomments
269,038 (4)
45,180 (16)
133,782 (16)
Map
9,792 (13)
3,936 (5)
3,968 (5)
13
iWildsCam
129,809 (243)
7,314 (243)
8,154 (243)
Camelyon
302,436 (3)
34,904 (1)
85,054 (1)
Table 5: Imbalance Ratio
Datasets
Pile
CivilComments
Camelyon17
iWildCam2020
PovertyMap
Client Imbalance Ratio
258
36.2
1.7
5.9
Class Imbalance Ratio
N/A
4.6
4802
N/A
G Experiments on Cifar 10
We create an imbalance dataset by reducing the data of 5 classes by 80% and then distributed the data across 100 clients according to two different Dirichlet distributions: Dirichlet (0.3) and Dirichlet (10), using code released by [61]. We use two layer CNN as the model. Results of algorithms are summarized in Table Figure and Figure illlustrate the communication complexity of each method by comparing the worst-case testing accuracy against the number of local updates and the communicated data sizes.
Imbalanced Cifar10, Dirichlet(0.3)
Imbalanced Cifar10, Dirichlet(O.32 Imbalanced Cifar10, (irichlet(0.3)
Werst Accuracy
Werst Accuracy
Worst Accuracy
0.4
0.3
0.8
0.30
Tadtig
Tedkdem
025
Pading
N02R0 CLAdem
014503
01
61
0.0
10 Iterations (*1))
100
15n
10
XC
40
50
Communicated Size (MB)
Communicated Size (MB)
(a)
(b)
(c)
Figure 2: Convergence Imbalanced Cifar 10 with Dirichlet(O.3)
H On the Statistical Significance of Proposed Algorithms
In Table 9 and 10 we evaluate the statistical significance of our algorithmss' advantages over the baselines. In each cell, the three letters (representing FGDRO-CVaR, FGDRO-KL, and FGDRO-KL- Adam, respectively) indicate whether each our algorithms has outperformed the corresponding baseline in that row with confidence level greater than 95% (p-value less than 0.05). 'Y' indicates Yes, and 'N' indicates No.
30

---

Table 6: Average running time of federated algorithms. We report running (in hours) for each algorithm to finish (200K iterations for Pile data and 20K for others).
Pile
CivilComments
Camelyon17
iWildCam2020
Mov
FedAvg
29.77
3.05
4.59
12.90
1.77
FedAdam
35.39
3.13
6.01
12.91
3.22
DRFA
34.12
3.27
4.94
12.95
2.25
DR-DSGD
25.26
4.01
6.26
13.02
4.71
FGDRO-CVAR
34.07
4.03
7.19
13.01
5.02
FGDRO-KL
34.92
3.65
7.23
14.57
5.42
KGDRO-KL-Adan
35.98
3.80
7.54
14.82
5.50
Table 7: Imbalanced Cifarl0, data alloacted clients accoring Dirichlet distributions
Datasets
Cifar10, (irichlet(0.3)
Cifar10, Dirichlet(10)
Metric
Worst Acc
Average Acc
Worst Acc
Average Acc
FedAvg
0.3140 (+0.0027)
0.6236 (+0.0019)
0.3620 (+0.0032)
0.6742 (+0.0020)
SCAFFOLD
0.3245 (.002)
0.6337 0,0038)
0,3821 (=0.0022)
0.6816 (+0. 0025) (.000025)
FedProx
0.3 (10.0027)
0.6189
(=3.))36)
0.3757 (1:0.004))
0.6925 (10.0053)
FedAdam
0.4860 (+0.0047)
0.7147 (+0.0058)
0.4460 (+0.0039)
0.7042 (+0.0043)
DRFA
0.3215 (10.0119)
0.6381 (=0,0131)
0.3752 (+00.0053)
0.6739 (+0000048)
DR-DSGG
0.3277 (#:0.0074)
0.6403 (+:00058)
0.3700 (+:000633
0.6792 (+-0.0888)
FGDRO-CVaR
0.4100 (1:0.0032)
0.6606
(1:0.0039)
0.4010 (1:0.0022)
0.6882 (1:0.0027)
FGDRO-KO KL
0.3560 (=0.0018)
0.6369
0009)
0,4110 (=000085)
0.6951 (#0.0042)
0.5280 (+00.001)
0.7057 (+00.033)
0.5110 (1.0.0072)
0.7286 (1-0.0063)
Imbalanced Cifar10, Dirichlet(10)
Imbalanced Cifar10, Dirichlet(10)
0.4 Imbalanced Cifar10, Dirichlet(10)
Worst Accuracy
0.45
Worst Accuracy
Worst Accuracy
0.40
0.4
0.10
0.55
0.30
Tedinng
rCoRo ONR POOnO-L
Pedidem
0.25
Pottag
cnna
0.20
10
15
01
50
100
150
0:00
20
40
Iterations (1K0)
Communicated Size (MB)
Communicated Size (MB)
(b)
Figure 3: Convergence on Imbalanced Cifarl0 with Dirichlet(10)
Table Statistical Confidence on Imbalanced Cifar10
Datasets
Cifar10, (003chlet(0.3)
Cifar10, Dirichlet(10)
Metric
Worst Ace
Average Acc
Worst Ace
Average Acc
FedAvg
VIYIY
YIVIY
YIVIY
YIVIY
SCAFFOLD
VIVIY
YINI
YIVIY
YIVTY
FedProx
YIYTY
YIYIY
YIYIY
NINIY
FedAdam
NINIY
NININ
NINIY
NINIY
DRFA
YIYTY
YINIY
YIYTY
YIYIY
DR-DSGD
VIYIY
YINIY
YIYIY
YIVIY
Table 9: Statistical Confidence on Piles and CivilComments
Datasets
Pile
CivilComments
Metric
Worst Log-PP Log-PPL.
Average Log- Tog-PPI.
Worst Acc
Average Acc
FedAvg
NIYTY
NIYIY
YIYTY
NIYIN
SCAFFOLD
NIYTY
NIYIY
YIYIY
NIYIN
FedProx
NIYTY
NIVIY
YIYIY
NIYIY
FedAdam
NINIY
NINIY
YIYTY
NIYIN
DRFA
NIYTY
NIYIY
VIVIY
YIVIY
DR-DSGD
NIYIY
NIYIY
YIYIY
YIYTY
31

---

Table 10: Statistical Confidence Camelyon17. 7, IWildCam2020, and Mav
Datasets
Camelyon17
iWildCam2020
CivilComments
Metric
Acc
Macro F1
Worst Pearson
Average Pearson
FedAvg
NIYIY
YIYIN
YINYY
YIYTY
SCAFFOLD
NIYIY
YIYIN
YINYY
YINIY
FedProx
NIYIY
YIYIY
YINIY
YIYTY
FedAdam
NININ
YIYIY
YINIY
NININ
DRFA
YIYIY
YIYIY
YIYIY
YIYIY
DR-DSGD
YIYIY
YIYIY
YIYIY
YIYIY
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction are accurate summary of the paper and well supported by other sections the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
33

---

Justification:
Assumptions are discussed in Section 4
Theorems are presented in Proofs are shown in details Appendix
Section 45
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The setting and parameter tuning scope are discussed in Section
7
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
34

---

Answer:
[No]
Justification:
All used data are publicly available. Code will be released later.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/ddeeeeee Cooeeeoodeesssseeeeee //nips.com / cassiicyncccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
These details are shown in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Experiments repeated for multiple times with different random seed, and error bars are reported in experimental results in Section 7
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
35

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computing resource and time of execution are reported in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
This paper conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The broader impacts have been discussed in Section 9
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
36

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not release any new data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The assets use are all publicly available and properly credited.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
37

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: No new assets introduced in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "Ugjo5WqF4y", "reviewer": "Reviewer_rzqA", "summary": "This paper aims to improve the efficiency of existing federated group distributionally robust optimization (FGDRO) when considering two specific types of regularization, condition value at risk and KL divergence. To address the first type of problem, the authors propose FGDRO-CVaR that reduces the sample complexity and communication costs simultaneously. For KL conditions, the proposed FGDRO-KL reduces the sample complexity while retaining the same communication costs. Moreover, the authors integrate the notion of Adam into FGDRO-KL, yielding FGDRO-KL-Adam and achieving better convergence speed.", "questions": "1. The datasets considered in this paper do not seem common in the existing literature. Could the authors report numbers on datasets like CIFAR-10/100 or EMNIST? Why did the authors choose the datasets in the paper?", "limitations": "Yes, the authors have discussed the limitations in the paper.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper is well-written, though some background information is missing.\n2. The problem is well-motivated. The sample and communication efficiency is a pivotal problem in federated learning, though the benefits are not fully analyzed in the experiments.\n3. The proposed method is grounded and improves over prior baselines.", "weaknesses": "1. The background can be more thoroughly explained. The authors are encouraged to provide additional context to address the following questions, which will greatly enhance the paper's completeness. Why is federated group distributionally robust optimization (FGDRO) an important problem or technique? What are the sources of the additional communication costs? Why is it necessary to consider two different types of regularization? Are these types of regularization relevant to different applications?\n\n2. My major concerns lie in the experiments and their settings. \n\n    - **Data Splits.** While FGDRO's main advantage appears to be its ability to address non-IID optimization, the experimental setup concerning data splits lacks clarity. An analysis of the non-IID levels, such as those derived from different Dirichlet-distributed data splits with varying $\\lambda$ values, is missing. Including more representative baselines, such as SCAFFOLD and FedProx, which are also designed for non-IID optimization, could further enhance the analyses.\n\n    - **Performance.** The proposed method performs similarly to the baselines in most experiments. For example, in Tables 2 and 3, apart from the Adam variant, the proposed method is comparable to the baselines. This would be acceptable if the proposed method demonstrated improved efficiency; however, relevant analyses on this aspect are absent from the experiments.\n\n    - **Communication or Sample Complexity Analysis.** An empirical analysis comparing complexity versus utility would be beneficial and highlight the advantages of the proposed method. For instance, the experiment in Figure 1 can be extended to a comparison among different baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! We address your questions as below and will include the discussion in the revision. \n\n***Q1: Why is FGDRO an important problem or technique?***\n\n***A:*** In federated learning, data is distributed across multiple clients, each with its own unique data distribution. FGDRO is crucial because it addresses the heterogeneity of these distributions, ensuring that models are fair across different clients and also robust to distributional shifts.\n\n***Q2: What are the sources of the additional communication costs?***\n\n***A:***\nFor FGDRO-CVaR, the only additional communication involves a scalar variable $s$, which is negligible compared to the large size of the deep learning model that needs to be shared in federated learning algorithms. For FGDRO-KL, the primary source of additional communication cost is the sharing of $m$, a moving average estimator of the gradient, which is the same size as the model itself. For FGDRO-KL-Adam, the additional communication cost arises from sharing both $m$ and $q$, which are estimators of the first and second order moments of gradients, respectively.\n\n***Q3: Why is it necessary to consider two different types of regularization?***\n\n***A:***\nFGDRO-CVaR and FGDRO-KL employ well-established regularization techniques [Deng et al., 2020; Lan & Zhang, 2023], each suited to different tasks and data distributions. __FGDRO-CVaR__ focuses on optimizing for worst-case scenarios or the average of the worst-case losses, making it particularly effective in high-stakes applications like healthcare and finance, where avoiding extreme losses is crucial. However, it can be sensitive to outliers or malicious client attacks.\n__FGDRO-KL__, on the other hand, uses KL divergence as a softer regularizer to promote smoother and more stable learning. Thus, it can be beneficial in scenarios where robustness to outliers or malicious clients is needed.\n__FGDRO-KL-Adam__ further enhances FGDRO-KL by incorporating Adam-type updates.\n\n[Deng et. al., 2020] Distributionally Robust Federated Averaging.\n\n[Lan & Zhang, 2023] Optimal Methods for Convex Risk Averse Distributed Optimization\n\n***Q4: Data Splits. The experimental setup concerning data splits lacks clarity. An analysis of the non-IID levels, such as those derived from different Dirichlet-distributed data splits is missing.***\n\n***A:*** In our previously submitted experiments, we used a natural data split, where data from the same hospital, web source, location, or demographic group were assigned to the same machine, with up to 17 clients in total. The following table summarizes key statistics of the data, including the Client Imbalance Ratio, which represents the ratio between the number of training samples on the client with the most data and the client with the least data, and the Class Imbalance Ratio, which reflects the ratio of training data in the largest to the smallest classes in classification tasks.\n|Datasets |__Pile__| __CivilComments__| __Camelyon17__|__iWildCam2020__| __PovertyMap__|\n|-|-|-|-|-|-| \n|Client Imbalance Ratio | 258 | 36.2 | 1 | 1.7 |  5.9  |\n|Class Imbalance Ratio | N/A | 4.6 | 1 | 48021 | N/A |\n\nWe conducted additional experiments using the Cifar10 dataset, where we created an imbalance dataset by reducing the data of 5 classes by 80%, and then distributed the data across 100 clients using two different Dirichlet distributions: Dirichlet (0.3) and Dirichlet (10). Results are summarized as below (detailed table at Section 2 of https://anonymous.4open.science/r/NeurIPS_11919-3402).\n\n|Datasets |  Dirichlet(0.3) |  Dirichlet(10) |\n|-|-|-|\n|Metric  | Worst Acc, Average Acc |  Worst Acc, Average Acc |\n|FedAvg |0.3140, 0.6236 | 0.3620, 0.6742 |\n|SCAFFOLD|0.3245, 0.6337| 0.3821, 0.6816|\n|FedProx | 0.3102, 0.6189 | 0.3757, 0.6925|\n|FedAdam| 0.4860, __0.7147__ | 0.4460, 0.7042| \n|DRFA | 0.3215, 0.6381 | 0.3752, 0.6739 |\n|DR-DSGD | 0.3277, 0.6403 | 0.3700, 0.6792 |\n|FGDRO-CVaR | 0.4100, 0.6606 | 0.4010, 0.6882|\n|FGDRO-KL| 0.3560, 0.6369| 0.4110, 0.6951|\n|FGDRO-KL-Adam | __0.5280__, 0.7057 | __0.5110__, __0.7286__|\n\n***Q5: Including more baselines, such as SCAFFOLD and FedProx, which are also designed for non-IID optimization, could further enhance the analyses.***\n\n***A:*** \nWe have included SCAFFOLD and FedProx as baselines (see Section 2 and 4 of https://anonymous.4open.science/r/NeurIPS_11919-3402). However, it's important to highlight some fundamental differences between these methods and our FGDRO algorithms. SCAFFOLD and FedProx optimize the average loss, whereas our FGDRO algorithms focus on prioritizing clients with poorer performance, thereby enhancing robustness and generalization.\n\n***Q6: The proposed method performs similarly to the baselines in most experiments. This would be acceptable if the proposed method demonstrated improved efficiency. An empirical analysis comparing complexity versus utility would be beneficial.***\n\n***A:***\nWe would like to highlight that our algorithms statistically significantly outperform the baselines in most tasks, as shown by the p-values in Section 4 of https://anonymous.4open.science/r/NeurIPS_11919-3402. \n\nWe include additional figures that illustrate the complexity comparison of methods. Specifically, we compare the worst-case testing accuracy against the number of local iterations, and the worst-case testing accuracy against the size of communicated data. These figures can be found at Section 1 of https://anonymous.4open.science/r/NeurIPS_11919-3402.\n\n***Q7: The datasets considered in this paper do not seem common in the existing literature.*** \n\n***A:***\nThe datasets we used were chosen because they naturally contain groups that reflect real-world scenarios, such as data from the different hospitals, web sources, locations, or demographics. These natural splits make them particularly relevant for studying group distributionally robust optimization [11, 66]. Additionally, we have conducted experiments on the Cifar10 dataset as mentioned earlier.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yfyKmhjgGU", "reviewer": "Reviewer_sEsv", "summary": "The paper presents three methods for Federated Learning Group Distributionally Robust Optimization: (i) one tailored to reduce the CVaR which optimizes the top K-losses, (ii) another one tailored to tackle the KL divergence, and finally (iii) one that uses Adam locally. The paper is well written and the ideas are presented. To the best of my knowledge, the proofs are correct. My main concerns are regarding the relevance and importance of the subject, the lack of experiments, and the lack of empirical studies on communication efficiency.", "questions": "[Q1] Why should be designed solutions that are distributional robust? And, at what cost? If we compare a method that simply maximizes/minimizes the FL problem, what is the overall loss? I believe the overall loss should be smaller, given that being distributionally robust is a particular case, and therefore, the unconstrained problem achieves a smaller minimum.", "limitations": "See weaknesses.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "[S1] The paper is well-written, and the ideas are presented. \n\n[S2] The theoretical results are correct, to the best of my knowledge.", "weaknesses": "[W1] The relevance of the subject is not entirely addressed. See [Q1]\n\n[W2] The experiment section is limited. In particular, the paper does not present any intuition on the problems they are solving. They do not consider the number of samples per server for example. I believe the authors should include a class imbalance problem [AN AGNOSTIC APPROACH TO FEDERATED LEARNING WITH CLASS IMBALANCE - Shen et al, ICLR 22].\n\n[W3] Communication efficiency is not properly addressed by the authors. The authors show the number of communication rounds required, but they do not take into account how much is communicated. The authors claim that this method is more efficient in terms of communication, and they show it theoretically, but in the experiment section, there is no evidence of communication efficiency. I suggest the authors reveal the communication cost associated with each method, measured in the amount of data shared between servers. \n\n[W4] Privacy is an important subject of Federated Learning, but in this paper, there is no analysis of the privacy aspect. Can the authors elaborate on the privacy aspect of this work? \n\n[W5] Federated learning is a technique used to train on a set of machines. The idea is that the number of machines that participate is large. It appears to me that the largest number of servers is 17. This seems to me insufficient for a distributed learning problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time to review! Below we address your concerns and suggestions.\n\n***Q1: Why should be designed solutions that are distributional robust? And, at what cost? If we compare a method that simply maximizes/minimizes the FL problem, what is the overall loss?***\n\n***A:*** Designing distributionally robust solutions in federated learning is essential for two reasons:  __1)Robustness__: It effectively manages distributional shifts, making models more reliable in real-world scenarios. In high-stakes applications like healthcare and finance, where failure in extreme cases can be costly, distributional robustness is crucial for minimizing risks. __2) Fairness__: By upweighting the group that has lower performance, it aims to not only perform good on average but on every subpopulations equitably.\n\nFocusing on distributional robustness may result in a potential reduction in average performance for the majority in the observed distribution. However, this trade-off is necessary to achieve the broader goal of creating models that are both robust to distributional shifts during testing and fair across all data groups.\n\n***Q2: In particular, the paper does not present any intuition on the problems they are solving. They do not consider the number of samples per server for example. I believe the authors should include a class imbalance problem [AN AGNOSTIC APPROACH TO FEDERATED LEARNING WITH CLASS IMBALANCE - Shen et al, ICLR 22].*** \n\n***A:*** In our previous submitted experiments, we utilized natural data splits where data from the same hospital, web source, locations, or demographic groups were placed on the same machine. These experiments have involved with highly imbalanced number of data on servers. The following table summarizes key statistics of the data, including the Client Imbalance Ratio, which represents the ratio between the number of training samples on the client with the most data and the client with the least data, and the Class Imbalance Ratio, which reflects the ratio of training data in the largest to the smallest classes in classification tasks. \n\n|Datasets |__Pile__ |  __CivilComments__ |  __Camelyon17__ | __iWildCam2020__ |  __PovertyMap__ |\n|------|-------|-------|------|----|-------| \n|Client Imbalance Ratio | 258 | 36.2 | 1 | 1.7 |  5.9  |\n|Class Imbalance Ratio | N/A | 4.6 | 1 | 48021 | N/A |\n\nTo further address this concern, we have conducted additional experiments using the Cifar10 dataset. We create an imbalance dataset by reducing the data of 5 classes by 80\\% and then distributed the data across 100 clients according to two different Dirichlet distributions: Dirichlet (0.3) and Dirichlet (10), using code released by [Shen et al, ICLR 22]. Results are summarized as below (detailed table at Section 2 of https://anonymous.4open.science/r/NeurIPS_11919-3402).\n\n|Datasets |  Dirichlet(0.3) |  Dirichlet(10) |\n|-----------------|-----------------|-----------------|\n|Metric  | Worst Acc, Average Acc |  Worst Acc, Average Acc |\n|FedAvg |0.3140, 0.6236 | 0.3620, 0.6742 |\n|SCAFFOLD|0.3245, 0.6337| 0.3821, 0.6816|\n|FedProx | 0.3102, 0.6189 | 0.3757, 0.6925|\n|FedAdam| 0.4860, __0.7147__ | 0.4460, 0.7042| \n|DRFA | 0.3215, 0.6381 | 0.3752, 0.6739 |\n|DR-DSGD | 0.3277, 0.6403 | 0.3700, 0.6792 |\n|FGDRO-CVaR | 0.4100, 0.6606 | 0.4010, 0.6882|\n|FGDRO-KL| 0.3560, 0.6369| 0.4110, 0.6951|\n|FGDRO-KL-Adam | __0.5280__, 0.7057 | __0.5110__, __0.7286__|\n\n***Q3: Communication efficiency is not properly addressed by the authors. I suggest the authors reveal the communication cost associated with each method, measured in the amount of data shared between servers.***\n\n***A:*** We have expanded our analysis to better address communication efficiency. Specifically, we now include figures that illustrate the communication complexity of each method by comparing the worst-case testing accuracy against the number of local updates and the communicated data sizes. You can find the figures at Section 1 of https://anonymous.4open.science/r/NeurIPS_11919-3402.\n\n***Q4: Privacy is an important subject of Federated Learning, but in this paper, there is no analysis of the privacy aspect. Can the authors elaborate on the privacy aspect of this work?***\n\n***A:***\nThank you for your comment. In our work, models and estimates of gradients are shared, both of which have been extensively studied in the privacy literature. The techniques developed in these studies can be integrated with our algorithms and applied within our framework.\n\nAdditionally, we aggregate certain scalar variables (in FGDRO-CVaR, the scalar variable s; in FGDRO-KL and FGDRO-KL-Adam, the scalar variable v). Borrowing the technique from the Remark 3.1 of [Shen et al., ICLR 2022], these variables can be aggregated using Homomorphic Encryption, ensuring that their exact values remain confidential. We appreciate the reviewer for bringing this literature to our attention.\n\nIn summary, while we acknowledge the importance of privacy in federated learning, we believe that our algorithms do not introduce significant new challenges in this area. We will included an elaborated discussion on this matter in the revision. \n\n***Q5: Federated learning is a technique used to train on a set of machines. The idea is that the number of machines that participate is large. It appears to me that the largest number of servers is 17.*** \n\n***A:*** In our new experiments on Cifar10, we have scaled up the number of clients to 100. Please check the results presented in Section 1 and 2 of https://anonymous.4open.science/r/NeurIPS_11919-3402.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "68maMn64i8", "reviewer": "Reviewer_f6MF", "summary": "This paper addresses the challenge of reducing communication costs and sample complexity in Federated Group Distributionally Robust Optimization (FGDRO). The authors present the FGDRO-CVaR algorithm and the FGDRO-KL algorithm to address different constraints. Subsequently, they conduct extensive experiments across various real-world tasks, including NLP and CV tasks. The corresponding empirical results confirm the effectiveness of their proposed methods.", "questions": "1. The introduction's treatment of the concept of generalization appears incomplete. It is evident that there are two levels of generalization in Federated Learning, as delineated in [1] and [2].\n\n2. As highlighted in the aforementioned weaknesses, the authors should provide additional clarification regarding the contributions and novelty of this paper. Overall, it appears that the proposed method is primarily a direct combination of existing methods.\n\n3. Similarly, the authors should delineate the challenges and innovations intrinsic to their theoretical analysis. Specifically, they should underscore the complexities involved in analyzing federated adaptive algorithms when applied in federated group DRO.\n\n4. On line 154 of Page 4, what is the relationship between the \"accurate estimate\" and the \"moving average\" in the subsequent sentence?\n\n5. Some minor points to address. The authors might consider offering more empirical results on convergence analysis in the experimental section. Additionally, they should further consider the statistical significance of these convergence analyses.\n\n[1] Hu X, Li S, Liu Y. Generalization bounds for federated learning: Fast rates, unparticipating clients and unbounded losses[C]//The Eleventh International Conference on Learning Representations. 2023.\n\n[2] Yuan H, Morningstar W, Ning L, et al. What do we mean by generalization in federated learning?[J]. arxiv preprint arxiv:2110.14216, 2021.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The exploration of reducing communication costs for federated group DRO is a rarely-studied topic within the FL community.\n\n2. The theoretical convergence analysis for the proposed algorithms is somewhat solid.\n\n3. The authors conduct comprehensive experiments to validate the effectiveness of the devised algorithms.", "weaknesses": "1. The contributions and novelties of this paper are unclear. It appears that the authors have directly combined existing federated adaptive algorithms with pre-existing federated group DRO methods in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! We address your suggestions and concerns as follows.\n\n***Q1: The introduction's treatment of the concept of generalization appears incomplete. It is evident that there are two levels of generalization in Federated Learning, as delineated in two literature.***\n\n***A:***\nThank you for bringing to our attention the literature that discusses the two levels of generalization in federated learning. In our work, we are referring to generalization at the participant level, where the goal is to develop robust models that perform well across both participating and non-participating clients. Based on the insights from the mentioned literature, we have revised the first paragraph of our introduction as follows:\n\n_\"... Generalization here refers to the model's ability to perform consistently across different clients, including those that have not participated in the training [Hu et al., 2023, Yuan et al., 2021].\"_\n\n***Q2: It appears that the authors have directly combined existing federated adaptive algorithms with pre-existing federated group DRO methods in this paper.***\n\n***A:*** \nFirst, our federated adaptive algorithms differ from those in the existing literature in terms of both algorithm design and analysis, such as [Reddi et al., 2020], as we employ Adam-type updates at every step while  [Reddi et al., 2020] uses SGD updates on local steps and only apply Adam at global steps. Second, our approach to federated group DRO is distinct from previous works. By considering constraint-free equivalent forms of federated group DRO problems and focusing on dedicated algorithm design and analysis, we have achieved lower communication and sample complexity, with or without adaptive components, compared to the literature.\n\n***Q3: The authors should delineate the challenges and innovations intrinsic to their theoretical analysis.***\n\n***A:***\nFor FGDRO-CVaR, we are the first to consider a constraint-free equivalent form and develop a communication-efficient algorithm for it, significantly reducing communication costs, as evidenced in Table 1. In addition to sharing machine learning models, we propose introducing only an additional scalar threshold to select participants in each round, minimizing additional costs. The new formulation, being a nonsmooth and compositional problem, introduces challenges that are uncommon in federated learning literature. We addressed these by carefully designing the use of moving average estimators to handle client drift and achieve linear speedup.\n\nFor FGDRO-KL, although previous literature has considered constraint-free compositional reformulations, they typically require large batch sizes on each machine to estimate gradients. This approach is impractical and incurs high sample complexity. Instead, we employ moving averages that only require small data batches while still providing accurate gradient estimations, making our method more efficient.\n\nFor FGDRO-KL-Adam, we allow local updates using Adam-type updates, which introduces the challenge of handling unbiased gradients, further complicated by the use and updating of the second-order moment. Our analysis carefully manages the moving estimates of the first and second-order moments, ensuring that the solution provably converges.\n\n***Q4: On line 154 of Page 4, what is the relationship between the \"accurate estimate\" and the \"moving average\" in the subsequent sentence?***\n\n***A:*** The \"moving average\" is what we refer to as our \"accurate estimate.\" To clarify this relationship, we have restated the sentences as follows: _\"To address this, it is common practice to create an accurate estimate of \n$g_i(w)$ [23, 22, 60, 61, 31]. Specifically, we employ a moving average $u$ as our accurate estimate.\"_\n\n***Q5: Some minor points to address. The authors might consider offering more empirical results on convergence analysis in the experimental section. Additionally, they should further consider the statistical significance of these convergence analyses.***\n\n***A:*** We conducted additional experiments using the Cifar10 dataset, where we created an imbalance dataset by reducing the data of 5 classes by 80%, and then distributed the data across 100 clients using two different Dirichlet distributions: Dirichlet (0.3) and Dirichlet (10). Results are summarized as below (detailed table at Section 2 of https://anonymous.4open.science/r/NeurIPS_11919-3402).\n\n|Datasets |  Dirichlet(0.3) |  Dirichlet(10) |\n|-----------------|-----------------|-----------------|\n|Metric  | Worst Acc, Average Acc |  Worst Acc, Average Acc |\n|FedAvg |0.3140, 0.6236 | 0.3620, 0.6742 |\n|SCAFFOLD|0.3245, 0.6337| 0.3821, 0.6816|\n|FedProx | 0.3102, 0.6189 | 0.3757, 0.6925|\n|FedAdam| 0.4860, __0.7147__ | 0.4460, 0.7042| \n|DRFA | 0.3215, 0.6381 | 0.3752, 0.6739 |\n|DR-DSGD | 0.3277, 0.6403 | 0.3700, 0.6792 |\n|FGDRO-CVaR | 0.4100, 0.6606 | 0.4010, 0.6882|\n|FGDRO-KL| 0.3560, 0.6369| 0.4110, 0.6951|\n|FGDRO-KL-Adam | __0.5280__, 0.7057 | __0.5110__, __0.7286__|\n\nWe have expanded our analysis to better address communication efficiency. Specifically, we now include figures that illustrate the communication complexity of each method by comparing the worst-case testing accuracy against the number of local updates and the communicated data sizes. You can find the figures at Section 1 of https://anonymous.4open.science/r/NeurIPS_11919-3402.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c03X5TCVcJ", "reviewer": "Reviewer_tWjT", "summary": "This work introduces three algorithms for communication-efficient Federated Group Distributionally Robust Optimization. The effectiveness of the proposed algorithms are verified through both theoretical and experimental results.", "questions": "1) Missing reference: How about the comparison with this work [1]?\n\n[1] Communication-Efficient Distributionally Robust Decentralized Learning https://arxiv.org/pdf/2205.15614\n\n2) What are the experimental setups for the number of clients and non-IID?\n\n3) In experimental results (Tables 2 and 3), FGDRO-CVaR seems to have no advantages in both task; why do we need this algorithm? Besides, it is better to highlight the best-performance results in Tables 2 and 3.\n\n4) Intuitively, using Adam optimizer can bring training speedup and is supposed to outperform other algorithms. But why do the results show that sometimes FGDRO-KL is better than FGDRO-KL-Adam?\n\n5) In proof, is an assumption of bounded gradient needed? If I don't misunderstand, Line 550 indicates such an assumption.\n\n6) If the loss function assumes to be convex, analyzing the optimal distance between the loss value the minimum loss should be better in Theorem 6.2.", "limitations": "See weakness.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) This work studies an important problem of federated group distributionally robust optimization.\n2) The theoretical results show the advantages of the proposed algorithms.", "weaknesses": "1) This work proposes three algorithms, including FGDRO-CVaR, FGDRO-KL, and FGDRO-KL-Adam. There lacks a comparison between these algorithms. For example, what are the connections and differences between these algorithms?\n2) The analysis for FGDRO-CVaR assumes the loss function to be rho-weakly convex, which is missing from the main context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! We believe we can address your concerns as follows. \n\n***Q1: There lacks a comparison between the three proposed algorithms. What are the connections and differences between these algorithms?***\n\n***A:*** FGDRO-CVaR and FGDRO-KL employ well-established regularization techniques [Deng et al., 2020; Lan & Zhang, 2023], each suited to different tasks and data distributions.\n\n__FGDRO-CVaR__ focuses on optimizing for worst-case scenarios or the average of the worst-case losses, making it particularly effective in high-stakes applications like healthcare and finance, where avoiding extreme losses is crucial. However, it can be sensitive to outliers or malicious client attacks.\n__FGDRO-KL__, on the other hand, uses KL divergence as a softer regularizer to promote smoother and more stable learning. Thus it can be beneficial in scenarios where robustness to outliers or malicious clients is needed.\n__FGDRO-KL-Adam__ further enhances FGDRO-KL by incorporating Adam-type updates.\n\n[Deng et. al., 2020] Distributionally Robust Federated Averaging. \n\n[Lan & Zhang, 2023] Optimal Methods for Convex Risk Averse Distributed Optimization\n\n***Q2: The analysis for FGDRO assumes the loss function to be $\\rho$-weakly convex, which is missing from the main context.***\n\n***A:*** This property can indeed be deduced from Assumption 4.1, as demonstrated in equation (16) of the appendix. In the revised version, we will ensure that this assumption is clearly articulated within the main body.\n\n***Q3: Missing reference \"Communication-Efficient Distributionally Robust Decentralized Learning\"***\n\n***A:*** Thank you for bringing this literature to our attention. While this literature addresses similar problem to ours, it is tailored for decentralized federated learning. It would incur high communication cost if directly applied to a centralized federated learning framework because it requires communication at every iteration. Additionally, the approach discussed is not applicable to scenarios involving a CVaR regularizer. We will include a discussion of this literature in our revision.\n\n***Q4: What are the experimental setups for the number of clients and non-IID?***\n\n***A:***\nIn our previously submitted experiments, we used a natural data split, where data from the same hospital, web source, location, or demographic group were assigned to the same machine, with up to 17 clients in total. The following table summarizes key statistics of the data, including the Client Imbalance Ratio, which represents the ratio between the number of training samples on the client with the most data and the client with the least data, and the Class Imbalance Ratio, which reflects the ratio of training data in the largest to the smallest classes in classification tasks. \n|Datasets |__Pile__ |  __CivilComments__ |  __Camelyon17__ | __iWildCam2020__ |  __PovertyMap__ |\n|------|-------|-------|------|----|-------| \n|Client Imbalance Ratio | 258 | 36.2 | 1 | 1.7 |  5.9  |\n|Class Imbalance Ratio | N/A | 4.6 | 1 | 48021 | N/A |\n\nTo further explore non-IID scenarios, we conducted additional experiments using the Cifar10 dataset, where we created an imbalance by reducing the representation of 5 classes by 80%, and then distributed the data across 100 clients using two different Dirichlet distributions: Dirichlet (0.3) and Dirichlet (10). Results are summarized as below (detailed table at Section 2 of https://anonymous.4open.science/r/NeurIPS_11919-3402).\n\n|Datasets |  Dirichlet(0.3) |  Dirichlet(10) |\n|--|--|-|\n|Metric  | Worst Acc, Average Acc |  Worst Acc, Average Acc |\n|FedAvg |0.3140, 0.6236 | 0.3620, 0.6742 |\n|SCAFFOLD|0.3245, 0.6337| 0.3821, 0.6816|\n|FedProx | 0.3102, 0.6189 | 0.3757, 0.6925|\n|FedAdam| 0.4860, __0.7147__ | 0.4460, 0.7042| \n|DRFA | 0.3215, 0.6381 | 0.3752, 0.6739 |\n|DR-DSGD | 0.3277, 0.6403 | 0.3700, 0.6792 |\n|FGDRO-CVaR | 0.4100, 0.6606 | 0.4010, 0.6882|\n|FGDRO-KL| 0.3560, 0.6369| 0.4110, 0.6951|\n|FGDRO-KL-Adam | __0.5280__, 0.7057 | __0.5110__, __0.7286__|\n\n***Q5: FGDRO-CVaR seems to have no advantages in both tasks; why do we need this algorithm? Besides, it is better to highlight the best-performance results in Tables 2 and 3.*** \n\n***A:***\nOn the CivilComments, iWildCam2020, PovertyMap and newly added Cifar10 datasets, FGDRO-CVaR outperforms previous baselines. Specifically, on PovertyMap, it surpasses FGDRO-KL, although it performs worse than FGDRO-KL-Adam. The primary reason for this is that FGDRO-CVaR does not implement Adam-type local updates. This is due to the current limitations in developing provable algorithms for FGDRO-CVaR with Adam-type updates, given the nonsmoothness of the problem. This is an area we plan to explore in future research. We will also highlight the best-performing results in the tables in our revision. Thank you for the suggestion. \n\n***Q6: Why do the results show that sometimes FGDRO-KL is better than FGDRO-KL-Adam?***\n***A:*** It is not unusual for SGD updates to occasionally outperform Adam in specific scenarios. Although Adam is generally more robust, it comes with additional hyperparameters that require careful tuning. We believe the observed result where FGDRO-KL-Adam underperforms compared to FGDRO-KL could be improved through an extensive hyperparameter search.\n\n***Q7: In proof, is an assumption of bounded gradient needed?***\n\n***A:*** Yes, an assumption of bounded gradients is necessary. This requirement is implicitly addressed in Assumptions 4.1 and 5.1 of the main text, where we assume that the functions are Lipschitz continuous. That implies the bounded gradients. We will explicitly address this point in the main text of our upcoming revision.\n\n***Q8: If the loss function assumes to be convex, analyzing the optimal distance between the loss value the minimum loss should be better in Theorem 6.2.***\n\n***A:*** While this is a valuable suggestion, our work does not assume convexity in the loss function, as the focus of this paper is on the nonconvex regime.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Authors propose algorithms for federated distributionally robust optimization (DRO). DRO is claimed to be particularly relevant in federated setting because of the potential for non-IID data on client. They argue that existing methods have higher communication and sample complexity and provide 3 algorithms to address CVaR and KL regularized DRO frameworks, and analyze their communication complexities. They show that the algorithms have different theoretical goals and strengths. Finally authors provide multiple experimental results showing the robustness of their algorithms when compared to other federated baselines. Reviewers raised multiple concerns including lack of experimental details, lack of baselines and comparison to past literature, confusion about experimental details, unclear delineation of technical and algorithmic novelty, lack of statistical uncertainty in experiment, and too strong assumptions. Authors were able to address most of these concerns during the rebuttal phase. AC notes that paper lacks any comparison to non federated (centralized) learning methods. This is particularly important to understand the performance gap between centralized and federated setting. AC highly encourage the authors to add this baseline in the next revision.
Decision: Accept (poster)