An Agnostic Approach to Federated Learning with Class Imbalance
Authors: Zebang Shen
Juan Cervino
Hamed Hassani
Alejandro Ribeiro
Venue: ICLR 2022 Poster (2022)
Keywords: Federated Learning
Class Imbalance

Abstract: Federated Learning (FL) has emerged as the tool of choice for training deep models over heterogeneous and decentralized datasets. 
As a reflection of the experiences from different clients, severe class imbalance issues are observed in real-world FL problems.
Moreover, there exists a drastic mismatch between the imbalances from the local and global perspectives, i.e. a local majority class can be the minority of the population. Additionally, the privacy requirement of FL poses an extra challenge, as one should handle class imbalance without identifying the minority class. In this paper we propose a novel agnostic constrained learning formulation to tackle the class imbalance problem in FL, without requiring further information beyond the standard FL objective. A meta algorithm, CLIMB, is designed to solve the target optimization problem, with its convergence property analyzed under certain oracle assumptions. Through an extensive empirical study over various data heterogeneity and class imbalance configurations, we showcase that CLIMB considerably improves the performance in the minority class without compromising the overall accuracy of the classifier, which significantly outperforms previous arts. 
In fact, we observe the greatest performance boost in the most difficult scenario where every client only holds data from one class. The code can be found here https://github.com/shenzebang/Federated-Learning-Pytorch.

Published as a conference paper at ICLR 2022
AN AGNOSTIC APPROACH TO FEDERATED LEARNING WITH CLASS IMBALANCE
Zebang Shen, Juan Cervino, Hamed Hassani, Alejandro Ribeiro Department of Electrical and Systems Engineering University of Pennsylvania
Philadelphia, PA 19104, USA
{zebang, jcervino, hassani, aribeiro upenn edu
ABSTRACT
Federated Learning (FL.) has emerged as the tool of choice for training deep mod- els over heterogeneous and decentralized datascts. As reflection of the experi- ences from different clients, severe class imbalance issues are observed real- world FL problems. Moreover, there exists drastic mismatch between the im- balances from the local and global perspectives, i.e. a local majority class can be the minority of the population. Additionally, the privacy requirement of FL poses an extra challenge, as one should handle class imbalance without identifying the minority class. In this paper propose novel agnostic constrained learning formulation to tackle the class imbalance problem in FL without requiring fur- ther information beyond the standard FL objective. A meta algorithm, CLIMB, designed to solve the target optimization problem, with its convergence property analyzed under certain oracle assumptions. Through an extensive empirical study over various data heterogeneity and class imbalance configurations, we showcase that CLIMB considerably improves the performance in the minority class without compromising the overall accuracy of the classifier, which significantly outper- forms previous arts. In fact, we observe the greatest performance boost in the most difficult scenario where every client only holds data from one class. The code can be found here!
INTRODUCTION
Class imbalance is ubiquitous in real world supervised learning problems. Examples span from medical applications (Lee & Shin 2020; Roy et al. 2019) Choudhury et al. 2019), fraud detection Yang et al. 2019 Chan et al. 1999), to consumer based applications (Wang et al. 2021b Wu et al.) 2020 Long al. 2020). In these scenarios, data belonging subset of classes constitute great proportion of the population while data from the minority classes, generated by uncommon events, scarce (He & Garcial 2009).. Having non-uniform number of samples per class deteriorates the performance of the classifier in the minority class (Huang et al. 2016). resulting in low training and testing accuracy. More importantly, unintended consequences mistreating the minority class can be catastrophic (Van Hulse et al., (207)) if the problem is not handled appropriately.
From the perspectives of data heterogeneity and privacy, the issue of class imbalance is even more significant in the setting of Federated Learning (FL). Due to the heterogeneity of the local data distributions, there can be a significant mismatch between the local and global imbalance, i.e. the class that is a minority locally can actually be majority class globally. Moreover, for the purpose of privacy protection FI., one should tackle the class-imbalance problem in an agnostic manner, i.c. the proposed algorithms should not require the minority class be identified.
In the centralized training setting, techniques like balanced sampling, loss re-weighting, and gra- dient tuning have achieved many successes (Johnson & Khoshgoftaar 2019). However, due to the extra difficulty of handling the class imbalance problem in FL, previous arts that rely on the ex- plicit identification of the minority class do not directly apply. While research along this line is quite limited, a commonly used heuristic to estimate the portion of a class using the norm of the gradient per class. When used as proxies, these quantities are then utilized to reweight the losses

---

Published as a conference paper at ICLR 2022
corresponding to different classes /Wang al.) 2021a a Yang et al. 2020). A key drawback of WWang ct al., aa is that a subset of the client's 's local dataset needs to be shared, which is not ideal for privacy preserving purposes. Moreover, the effectiveness of such approaches degrades when there is a notable mismatch between the local imbalance and the global imbalance (Wang et al. 2021a).
In this work, we target the most difficult yet possibly most interesting setting in FL., where there is a significant mismatch between the local and global imbalance. Concretely, on certain clients, a mi- nority class from a global perspective is in the majority locally. Practitioners often encounters such a mismatch due to the highly heterogeneous data configuration in FL and the principle of locality (Wang et al., 2021a). For example, when the local data are produced by minority user, the corre- sponding minority data could occupy large portion of the local distribution. In this scenario, due to the scarceness of the minority data from a global perspective, the corresponding underrepresented client will usually experience poor service quality from the trained model, giving rise to potentially severe fairness issue.
To overcome the aforementioned challenges, we propose a constrained learning formulation to han- dle the class imbalance issue in FL while accounting for both heterogeneily and privacy. In brief, we impose constraints on the standard FL formulation so that the empirical loss every client should not overly exceed the average empirical loss. Such constraints are shown to force the classifier to account for all classes equally and hence mitigate the detrimental effeet of class imbalance, under a type of heterogeneous data configuration that captures the mismatch between the local and global imbalance. The advantages of our formulation threefold: First, in contrast previous arts which usually rely on some heuristics to reweight the loss functions for different classses, our approach principled, yielding a simple optimization interpretation. Second, unlike existing methods, our formulation requires no additional information compared to the original FL formulation and it treats data from different classes agnostically, and hence less likely to leak the private information of the clients. Third, from our exiensive empirical study, our formulation can significantly improve the testing accuracy on the minority class, without compromising the overall performance.
Contribution. We summarize our contributions as follows.
1. Problem Formulation: To address the challenge of class imbalance in FL with data hetero- geneity, we propose a novel constrained FL formulation with explicit enforcement on the similarity between the local empirical losses. Using only information from the standard FL objective, our approach is completely agnostic to class distribution of the client data and its proxies, as opposed to the existing literature (which mostly violate privacy requirements of FL).
2. Mega-Algori We solve our constrained optimization problem via a primal-dual approach. For fixed dual variable, the corresponding Lagrangian function enjoys similar structure as the standard FL loss, but with non- non-uniform weights on the local objectives. Accordingly, we propose an efficient (meta-) algorithm called CL. that use any FL optimization method as a subrou- tine, with nearly negligible communication overhead. Furthermore, we analyze the convergence properties of CLIMB under certain oracle assumptions.
On benchmark datasets, CLIMB with Fed-Avg as base solver achieves significant enhancement of the accuracy in the minority class without com- promising the overall accuracy under various data heterogeneity and class imbalance scenarios.
Accuracy Improvement in the minority class:
2 RELATED WORKS
Class Imbalance in Centralized Setting. In the centralized learning setting, the number of samples per class is known. We categorize existing solutions that exploit such information as follows. Balanced sampling. In order to balance the data used for gradient calculation, the most common approaches are either to under sample from the majority classes (Liu et al.) 2008). or to augment the minority class (Chawla et al. 22022 Guo Viktor 2004). Both methods seek to generate an artificial uniform distribution of data (Buda et al. 2018 PPuyyafar et al.] 2018).
Loss reweighting. Methods in this category focus on re-weighting the loss functions for different classes, with extra emphases on the mistakes made in the minority class (Cui et al. [001 Ling & Sheng 2008 Sun et al.) 2007: Wang et al.] 2016). There also exist works like (Lin et al.] 2017) that
adjust the scale of the loss sample-wie wise, without exploiting the global data distribution.
Gradient tuning. In the context of neural networks, some other works focus on tuning the gradient per class Annnd et al. 1993) showing faster rates of convergence in the class imbalance setting.
2

---

Published as a conference paper at ICLR 2022
To do this, the gradient is reshaped in order to have an equal magnitude when projected to all the gradients per class, while keeping the same norm as the original gradient.
Class Imbalance in Federated Learning. Combating with the issue of class imbalance is more challenging in FL. since the data composition in such a setting is generally unknown and the minor- ity classes often difficult to identify Li al. 20200; [Wang et al. (2020b). While research in this direction are quite limited, to the best of our knowledge, we classify them into the following two classes based on whether a proxy of the data composition is explicitly built.
[
(i A common strategy in existing methods is to explicitly build proxies of the data composition based on some heuristics. These proxies are dynamically adjusted during the learning procedure and allow the aforementioned three techniques, balanced sampling, loss re-weighting and gradient tuning, to be utilized in the FL setting: Wang et al. (2021a) suggests that there exists a propor- tional relation between the magnitude of the gradients the corresponds to the last layer of the neural network and the sample quantity. Based on such observation, the proposed the Ratio- Losss, s, class-wise re-weighted version of the standard cross entropy loss. We note that to define the Rat Lo-Los, one needs to collect a subset of client data as "auxiliary data", which may not be ideal in the setting of FL. On the same vein. (Yngg et al. (2020) argues that the gradient per class can be used as a proxy to infer the imbalances in the distributions of the clients, and thus clients should be selected according to how uniform the magnitude of gradient per class is. We also notice the work Ast raea which introduces extra virtual components called mediators between the FL server and clients (Duan al. 2019). The mediator is assumed to have access to the local data distribu- tions of the clients so that client rescheduling and data augmentation can be carried out accordingly. Through the prepossessing on the mediator, the gradients communicated to the server are made bal- anced class-wise. However, when privacy is taken into consideration, methods like Astraea may not be appropriate as in essence it is directly built on the global data distribution.
(ii) Without explicitly constructing an estimation of the data composition, there are works that resort to techniques like active learning and reinforcement learning to implicitly learn the data composi- tion as the optimization progresses. Works along this research line usually rely client selection to mitigate the effects of class imbalances. In (Goetz et al.] 2019). to address the class imbalance problem, there will higher probability to sampling clients that posses the global minority class. Other works, leverage client selection as a multi-armed bandit problem, and design a client selec- tion policy balance the gradients (Xia al., (020). Other arts leverage Q-learning techniques to select clients in order to minimize the overall loss Wang el al. (2020a). However, we believe in the most practical setting of FL, clients that are available per communication round incoercible and hence these strategies have limited applicability.
Comparison with Previous Works. Our method significantly differs from the above strategies in the following ways: (I) Our method requires no knowledge of the data composition, nor any proxy of such information. Consequently, our approach is agnostic to the minority class and better pre- serves clients' privacy. Such property draws clear distinction between our work and the works listed in class (i) above. (2) As will be more clear in the following section, we only perform client- wise re- weightttingg as opposed to the class-wise re-weighting schemes used in previous works, which further emphasize the agnostic nature of our approach. (3) In contrast to the methods in class (ii) above, our approach does not require active client selection, enjoying a broader applicability in the most practical and interesting settings.
3 FEDERATED LEARNING WITH EMPIRICAL LOss CONSTRAINTS
We consider the problem of multi-class classification. Let x E X' C Rd be the input and use y E {1, (1,...,C C} to denote the target label, where C is the total number of classes. In the context of FI., we assume to have N clients, each of which posses its own private data distribution p((x,g). v). Here, (1 3) is a joint probability distribution of the input x and the output label y. One can decompose Ps (I, 3) as Px(I, y) = p( (()))))(()). where p(zly) is the conditional distribution of the input x given class y and p.(y) the marginal distribution of class y on client We assume that the conditional distribution p(x is identical on all devices, but the marginal distribution (v() can vary significantly due to the heterogeneity of the data configuration.
Let H = { X' x θ + RC be a family of parameterized predictors with parameter 0 E e C R Let l: RRC x y - R.+ be the loss function, then the local objective function of client defined as
f0) (x..)) [[((( 0), v)].
(I)
3

---

Published as a conference paper at ICLR 2022
For multi-clase class classification, l is often chosen to be the cross entropy loss. In the standard formu- lation of FL, the goal is to minimize the global average of local objectives
min f(0) == Σ f((0). BEB
While it is well known that, in the presence of class imbalance, the above vanilla formulation will produce models that perform poorly on the minority data, we consider the following configuration of heterogeneous local class distributions in order to make a quantitative analysis of such a phe- nomenon for concrete class imbalance setting. More importantly, such setting will also motivate our constrained FL formulation. We emphasize that the following setting is just used as motivating example to showcase our claims, and our results apply generally to any FL setting.
Motivating Example. Let be the uniform distribution over the classes, i.c. for y u, Pr(y c) = Vc E y and let de be the Dirac distribution of class c. We assume for some small but fixed E 1]. the local class distribution of the client i is mixture of the uniform distribution over all classes and the Dirac distribution of a fixed class C, i.e. = ou + (1 - ) We use N₂ to denote the number clients with C; = c. Note that in the limit setting when a O, the aforementioned configuration captures the most heterogeneous setting: clients only have data from a single class. We consider extreme case of class imbalance under the above configuration. Without loss of generality, we consider the binary classification problem, i.e. C = 2. and we assume class I to be the minority class with N1 1. We define (:))) ;= Ex=-pxll==)](((0
0), i)] as the loss of the
predictor ob 0) on the data with y We can calculate that
a (0) +
(1 (1- aN -
f(0)
92
(3)
N
2
N
Clearly, when a, the portion of data with uniform label distribution, is small, e.g. a and N, the total number of clients, is large, the loss of the predictor on class 1 has negligible weight, which often leads to the poor performance on the minority class in the trained classifier as the majority classes dominate the gradient. Moreover, observe that when is small, there is significant mismatch between the local and global class imbalance: the global minority class 1 is in the majority on the corresponding client locally. Such phenomenon is pertinent to the FL setting due to the data heterogeneity and poses a great challenge for tackling the issue of class imbalance in FL.
3.1 CONSTRAINED FL FORMULATION
In our work, to address the class imbalance challenge, we propose to minimize the following con- strained FL (CFL) formulation
N
P min f(0) 1 f((0)
(CFL)
8EB
N
s.t. ((
S e, vi E [l,,,,
Here, e css a tolerance constant that controls the enforced closeness in the training loss among clients, and we emphasize the dependence of the optimal value P. on e by encoding motivation, we show that the constraint in our formulation CFL can be translated to constraint on the performance of the minority class, under the above class imbalance setting: Consider the setting where the tolerance constant is very small, i.c. is close to zero. WLOG, assume that the first device is the one that has e; = Recall the definition of g; above Eq. One can compute that
the subscript. As
- - F(0) (1 - (N -
Ne
(g1 (0) 92(0)) < + 91 (1) 92 (2( (1-a)
N
Therefore, our formulation CCF..) enjoys a clear class-balancing interpretation the highly hetero- geneous setting when is small and N is large. Note that this is achieved without the identification of the minority class and server collects no additional information compared to the vanilla FL.
While the above nice interpretation of the proposed constraint may not hold exactly for general class imbalance settings, in spirit, we want the resulting classifier from our algorithm to perform similarly on every class, in other words to account for the minority class and majority class equally. In the following section, we discuss how to solve the proposed formulation by alternating the primal and dual updates of equivalent Lagrangian formulation.
4

---

Published as a conference paper at ICLR 2022
Algorithm CLIMB: CLass IMBalance Federated Learning
1: Input: initial model 0º a subroutine ClientUpdate, dual step size T/D, maximum round T;
2: Initialize the dual variables À - [O....,.)
3: for ( 1,2, do
4: Compute weights: Vi E [N], w, = Xa X, with Ā= Nv Ei= dzi
5: Primal Update: 0t+1 +- (ffentUpdate((w::] :
6: Dual Update: Vi E [N], [} (f( f(00+1) c)]_ with f N Ei= fü;
7: end for
8: Output: model gT+1
3.2 ALGORITHM CONSTRUCTION
In order to solve problem
CFL
we resort the method of Lagrange multipliers. By introducing AN] E R we define the Lagrangian function as,
the dual variables X X1,
N
N Σ j=1
((0,)) = N
f((0) + X
f1(0)
(0)
-
(4)
N
N Σ (1+A-1)):00 - XAe, 1=1
N Σ
with Ā
A
(5)
With this in hand, construct lower bound of the above constrained optimization problem using the Lagrangian L( A) as follows:
D max min C(O, A) S min max C(O, = AER BE@
BEB XERS
where we often refer to D as the dual problem. To solve the dual problem, we propose CLIMB, method described in Algorithm which discussed in detail as follows.
CLIMB proceeds by alternatingly optimizing over the primal variable 0 and the dual variable X.
Primal Update. For a fixed X, the minimization of with respect to is equivalent to a re-whighted version of the standard unconstrained FL objective (2)
min L(0, A) EEB
min BEB N -1 ())((O)
Σ 1=1
(6)
Importantly, this simple and canonical form allows solver as the base optimizer. For flexibility, we do not explicitly choose the base optimizer in our algorithm description, but refer to the update on the subroutine ClientUpdatee w; )= (*) gt-1, Such subroutine takes the non- non-uniform weights {w: the local objectives and the current consensus model df as inputs, and returns an updated model gi-1. Note that every call to ClientUpdate may consists of multiple communication rounds.
perform the update 0 using any FL.
Dual Update. Once we have obtained the new consensus model gr+1, we perform dual update on by taking single dual ascent step of the following equivalent objective (given fixed 0).
N Σ f
max C(O,A)+ -
max AERN
d
f((0)
1 N 1=1
f1(0- -c -
XERN
N
To evaluate the gradient of L with respect to A, we need to first broadcast the consensus model gt-1 and then aggregate the function values f(8++1). Since the broadcast model can be used for the next round of primal update, the only overhead of CLIMB compared to the standard FL solver ClientUpdate, to transmit the functional value, which is negligible.
We emphasize that CLIMB can be implemented in privacy-preserving manner: A client can carry out its update locally given the access to the global average of the dual variables and the global average of the loss functions f()). These quantities can be computed via the standard FL technique of Homomorphic Encryption without revealing the exact value of the dual variable X and local loss fc(0) to the server, elaborated in Appendix 1)
Remark 3.1
5

---

Published as a conference paper at ICLR 2022
3.3 THEORETICAL GUARANTEES
Based on the recent progress in constrained learning (Chamon et al. 2021), we show that under mild regularity conditions, the duality gap between the dual problem D. and the primal problem P can be controlled by some quantity that describes the capability of the parametric function class H.
Assumption 3.1 The loss function & in the definition of the local objective ① is L-Lipschitz. i.e. Le.](((z,-)) [(z, ) & L || - 2|I. and bounded by B.
Assumption 3.2 The conditional distribution p(zly) non-atome non-atomic for all y RC
While usually the local data distribution is discrete, we can always augment it by randomly per- turbing the data points with white noise, this is often used data augmentation in vision tasks.
Assumption 3.3 There exists a convex hypothesis class H. such that H C H. and there exists constant { > 0 such that Vé H. there exists 0 E ④ such that supzex (1ő(z) - 6xx,0)] S.
A simple strategy to construct H to take the convex hull of H. When is sufficiently rich, & can be expected to be small. Notice that this bound can be decreased by increasing the richness of the function class H. All the proofs can be found in the Appendix.
Theorem 3.1 (Near Zero Duality Gap) Under Assumptions 3. 3.2 and the Contrained Fed- erated Learning problem is feasible in H with constraint e 2LE, the Constrained Federated Learn- ing problem has near zero-duality gap,
P - D. S (21X + 1)
(8)
where -2LE is the optimal dual variable associated with the Constrained Federated Learning with constraints 2LC over the space of fanctions H.
problem CFL)
Theorem establishes an upper bound on the duality gap of the Constrained Federated Learning The gap depends on the Lipschitz constant of the loss function L, the richness of the function class ç. and the optimal dual variable of a more restrictive problem. Note that we required the Constrained Federated Learning problem to be feasible for constraint 2T... In the case of the cross-entropy loss, as long as c 2T. > O, this can be satisfied by a classifier that assigns a uniform label for every sample, as each individual loss will be equal to each other.
Problem CFL
Since the minimization of the Lagrangian function L is non-convex, to show the convergence of CLIMB, we need an additional oracle assumption as follows.
Assumption 3.4 (Approximate Solution) For every dual variable X E R.Y, and precision ò there exists an oracle approximate solution 0* such that L(0>, X) S millgRee L(0, X) +
Theorem 3.2 (Convergence) Define the dual function d(A) minøge L(0, Under Assump- tions 3.7 to 3.4 for a fixed tolerance > O, the iterates generated by Algorithm 7 converge to neighborhoud of the dual problem D in at most T, =((1/r steps, iee.
d(x 2 Do
11 B2 -,
2
EXPERIMENTS
In this section, we evaluate our formulation (CLL) against the competitors on various FL scenarios at the presence of class imbalance. Our results highlight the benefits of our approach especially when the local data distributions are severely heterogeneous and there significant mismatch between local and global imbalance. To ensure a fair comparison, we use Fed-Avg as the base optimizer in the current experiment for all formulations: the standard FL objective in Eq. ( the proposed formulation in (FL).. datio-Loss (Wang et al. 202 and Focal -oos (Lin) et al. 2017). We emphasize that the novelty of our work lies in the new constrained FL formulation (CLL) and orthogonal how the formulation is solved. We now describe the datasets and models used in our experiments with more details provided in Appendix A
Datasets Three benchmark datasets used in experiments with the default train/test splits,

---

Published as a conference paper at ICLR 2022
Imbalance ratio
Level of heterogeneity
Baseline (Fq.22)
CLIMB (this work)
Dataset
Ratio-Loss
Pocal-loss
minority class out of T0 total classes
0.0532
0.2080
0,1140
0.0450
a 0.1
(0.6754)
(0.6829)
(0.6727)
(0.6445)
CIFARIO
0.137
0.3230
0.1790
0.0430
0.2
(0.7121)
(0.7121)
(0.7037)
(0.6914)
minority classes out of 10 total classes
/ 20
0.2810
0
0
a 0.1
(0.5669)
(0.6031)
(0.5746)
(0.6565)
0.1279
0.3240
0.1790
0.0552
0.2
(0.7098)
(0.7167)
(0.7054)
(0.6905)
minority class out of TO total classes
0.6889
0.8552
0.8472
0.6186
a a= 0.1
(0.9375)
(0.9556)
(0.9544)
(0.9278)
MNIST
0.7925
0.8748
0.8052
0.7784
0.2
(0.9540)
(0.9616)
(0.9555)
(0.9479)
minority classes out of 10 total classes
0.3425
0.6987
0.4134
0.1944
0.1
(0.8260)
(0.9158)
(0.8484)
(0.7938)
0.4720
0.7290
0.6717
0,4602
0.2
(0.8596)
(0.9153)
(0.9063)
(0.8654)
minority class out of 10 total classes
0.2058
0.3629
0.2164
0.0414
0.1
(0.6841)
(0.7041)
(0.6839)
(0.6543)
CIFAR1O
0.1813
0.3743
0.2657
0.1347
0.2
(0.7113)
(0.7312)
(0.7083)
(0.6911)
minority classes out of TO total classes
-000
0.0492
0.2280
0.0315
0
0.1
(0.5933)
(0.6358)
(0.5825)
(0.5548)
0.1064
0.2734
0,0993
0.0298
a
(0.6380)
(0.6696)
(0.6211)
(0.5982)
minority class of TO total classes
0.8473
0.9305
0.8851
0.8469
0.1
(0.9534)
(0.9584)
(0.9558)
(0.9470)
MNIST
0.8962
0.9239
0.8798
0,8953
a
(0.9634)
(0.9657)
(0.9615)
(0.9586)
minority classes
10 total classes
0.6045
0.8084
0.6981
0.4690
0.1
(0.8906)
(0.9356)
(0.9119)
(0.8670)
0.7272
0.8195
0.7663
0.6961
a
(0.9190)
(0.9392)
(0.9320)
(0.9099)
Table 1: The minority class testing accuracy and the overall testing accuracy (the quantity in the parentheses) after 5000 communication rounds. If there are multiple minority classes, we report the worst of them. Here N, the number of devices, is 500. The base FL solver is Fed-Avg with purtial-participation 100 devices participate every communication round.
which are MNIST
LeCun et al. 1998). CIFARIO (Krizhessky et al. 2009) and Fashion-MNIST
Xiao al. 2017). The results the last dataset are deferred to the appendix due space limitation. Heterogemedy: We generate heterogeneity in the local data distributions according to the strategy from (Karimireddy et al. 2020; Hsu al. 2011): Let the level of heterogeneity. For fixed a, we divide the dataset among N = 100 (moderate) or N 500 (massive) clients as follows: for we allocate each client portion of a i.i.d. data and the remaining portion of (1 a.) by sorting according to label. In our appendix, we also consider the Dirichlet type heterogeneous data allocation scheme which wildly used the literature of Federated Learning, for example (Hsu al. 2019 Acar et al. 2020).
[0, 1] be some constant that determines
Data Imbalance. We simulate the phenomenon of class imbalance by removing data belong to the minority classes: Observe that the datasets included in experiments both have 10 perfectly balanced classes. For the minority class(es), we retain only 1/p portion of the corresponding data. Here, 2 1 the ratio between the numbers of data in the majority class and in the minority class

---

Published as a conference paper at ICLR 2022
and is termed the imbalance ratio. For example, when there are 3 minority classes with 10,
90% of the data belong to classes 0, 1, 2 (without loss of generality) are manually removed. In our experiments, consider the setting of or 3 minority classes and we take p 5, 10, 20. Models We follow the choice of model architectures in (Acar et al.) 2020; McMahan et al. 2017) Specifically, we use a hidden layer fully-connected neural network for MNIST, where the numbers of neurons are (128, 128). For CIFARIO, 10, we use CNN model consisting of 2 convolutional layers with 64 5 5 filters followed by fully connected layers with 394 and 192 neurons. We note that higher testing accuracy on the included datasets can be obtain by using models with high capacity, but is orthogonal to our research.
4.1 RESULTS SUMMARY
To evaluate the effectiveness of approach against the challenge of class imbalance, needs to take into consideration both the performance on the minority class(es) and the average performance on all the classes. We report both quantities after sufficient communication rounds (5000 rounds for CIFARIO and 1000 rounds for MNIST) under various experiment settings in Tables [ and 2 In every cell of these tables, the quantity above denote the minority class testing accuracy and the quantity in the parentheses is the average performance on all the classes. We also considered the case where there are multiple minority classes and we report the worst accuracy among the minority classes. Our approach outperforms previous arts in all cases, often by large margin.
Imbalance Ratio and Number of Minority Classes. The imbalance ratio p and the number of minority classes are two important quantities to measure the difficulty of class imbalance problem. Under all the included choices, CLIMB consistently beats previous arts in both minority class testing accuracy and average performance on all the classes. Therefore, we conclude that CLIMB is able to boost the performance on the minority class without compromising the performance on the other classes. This is rare merit when addressing the class imbalance problem. In fact, methods like Rossoss able to improve the testing accuracy on the minority class, but it also sacrifices the performance on the rest classes, leading to inferior average testing accuracy.
Level of Heterogeneity. We test the performance of CLIMB under different levels of heterogene- ity and observe that CLIMB outperforms the included methods considerably in all settings, It has the biggest advantage over the competitors in the most heterogeneous setting, a = 0. There are situations that existing methods completely fail in the minority class with less than 10% accuracy, but CLIMB is still able to correctly classify most of the minority data, e.g. see Table 2 MNIST 3 minority classes-> a = O.
5
Moderate vs. Large Number of Devices An important goal of FL. is to exploit the computational resources of the loT devices. Hence, the scalability to a large number of devices is a critical prop- erty of an FL method. We hence test CLIMB on both moderate (N = 100, see Table ( and massive devices (N = 500, see Table T settings. To make things more practical, we instantiate the sub- routine ClientUpdate using Fed-Avg with the prrtial-partcccpattion scheme in the massive device setting. Specifically, 100 devices participate model training after every Fed-Avg global communica- tion round. We clearly observe the advantage of CLIMB in all of these setups.
CONCLUSION
In this paper we proposed a novel agnostic constrained learning formulation to tackle the problem of class imbalance in the Federated Learning setting. By introducing constraints in the learning be similar in all clients, thus accounting for the class
procedure we enforced the performance imbalances. In terms of privacy protection, our formulation requires no further information than the standard FL objective to be collected in the server and never estimates the data composition as opposed to all previous approaches. Moreover, compared with previous arts which are usually heuristic based, our approach is principled as it is purely optimization based and can be efficiently solved via the proposed meta-algorithm CLIMB, yielding major practical benefits. Our extensive empirical study showcases the superiority of proposed constrained formulation over previous arts.
ACKNOWLEDGMENTS
This research is supported by AFOSR Award 19RT0726, NSF HDR TRIPODS award 1934876, NSF award CPS- 113723,,,,3, NSF award CIF-1910056, NSF CAREER award CIF- 1943064, and NSF award CCF-21 12665.
8

---

Published as a conference paper at ICLR 2022
Imbalance ratio
Level of heterogeneity
Baseline (Eq.22)
CLIMB (this work)
Dataset
Rat latio-Loss
Pocal-Lose
minority class out 10 total classes
0.0229
0.3575
0
0.0
(0.5734)
(0.6076)
(0.4836)
(0.4205)
0.2753
0.5054
0.2929
0.2284
CIFARIO
a = 0.1
(0.7143)
(0.7246)
(0.6951)
(0.6860)
0.2988
0.4689
0.3825
0.2618
0.2
0.7348
(0.7511)
(0.7329)
0.7249
minority classes out of 10 total classes
0,0402
0.2756
0
0
0.0
(0.5534)
(0.5598)
(0.4678)
(0.4527)
0.1316
0.3399
0.0690
0.0408
0.1
(0.6189)
(0.6637)
(0.615)
(0.5976)
0.2566
0.3292
0.1916
0.1213
a 0.2
(0.6659)
(0.6983)
(0.6504)
(0.6346)
== 10
minority class out total classes
0.3092
0.9175
0.4650
0,3078
(0.8630)
(0.9341)
(0.8630)
(0.8556)
0.8597
0.9428
0.9189
0,8348
MNIST
0.1
(0.9586)
(0.9675)
(0.9648)
(0.9529)
0.8750
0.9377
0.9283
0,8882
0.2
(0.9640)
(0.9715)
(0.9706)
(0.9631)
minority classes out of T0 total classes
0.0153
0.8029
0.0631
0.0717
0.0
(0.7133)
(0.9115)
0.7222
0.7401
0.7263
0,8828
0.7870
0.6674
0.1
(0.9189)
(0.9522)
(0.9341)
(0.9069)
0.7950
0.8004
0.7801
0.7785
0.2
(0.9352)
(0.9416)
(0.9364)
(0.9274)
minority class out 10 total classes
0.2892
0,5987
0.0942
0.1491
(0.6382)
(0.6468)
(0.5506)
(0.5631)
0.4101
0.6075
0.40TT
0.3558
CIFARIO
a= 0.1
(0.7186)
(0.7351)
(0.7008)
(0.6994)
0.5335
0.6063
0.5054
0.4359
0.2
(0.7536)
(0.7556)
(0.7427)
(0.7380)
minority classes out of TO total classes
0.0313
0.3813
0.0512
0
0.0
(0.4742)
(0.5639)
(0.5108)
(0.4514)
0,5135
0.6420
0.4600
0,4213
0.1
(0.6636)
(0.6977)
(0.6632)
(0.6384)
0.5251
0.6328
0.5751
0.5311
0.2
(0.6960)
(0.7202)
(0.6883)
(0.6749)
5
minority class out TO total classes
0.7245
0.9154
0.8020
0.7429
(0.8953)
(0.9224)
(0.9016)
(0.8992)
0.9378
0,9582
0,9286
0.9408
MNIST
0.1
(0.9666)
(0.9693)
(0.9651)
(0.9624)
0,9448
0.9670
0.9561
0,9481
0.2
(0.9711)
(0.9734)
(0.9733)
(0.9686)
minority classes out of 10 total classes
0.0160
0.8744
0.0544
0.0
(0.7722)
(0.9137)
(0.7370)
(0.7826)
0.8294
0.9217
0.8520
0.7987
(0.9422)
(0.9606)
(0.9501)
(0.9361)
0.8557
0.8818
0.8730
0.8321
0.2
(0.9536)
(0.9595)
(0.9536)
(0.9442)
Table 2: The minority class testing accuracy and the overall testing accuracy (the quantity in the parentheses) after sufficiently many communication rounds. If there are multiple minority classes, report the worst of them. Here N, the number of devices, is 100. The base FL solver is Fed-Avg fillpplll-ariiiiiaattto: all devices participate in every communication round.

---

Published as a conference paper at ICLR 2022
REFERENCES
Durmus Alp Emre Acar, Yue Zhao. Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Con- ference on Learning Representations, 2020.
Rangachari Anand, Kishan G Mehrotra, Chilukuri K Mohan, and Sanjay Ranka. An improved algorithm for neural network classification of imbalanced training sets. IEEE Transactions on Neural Networks, 4(6):962-969) 1993.
Dimitri Bertsekas. Convex optimization theory. Athena Scientific, 2009.
Dimitri Bertsekas. Convex optimization algorithms. Athena Scientific, 2015.
Stephen Boyd and Almir Mutapcic. Subgradient methods.
Stephen Boyd and Lieven Vandenberghe. Corvex optimization. Cambridge university press, 2004.
Mateusz Buda, Atsuto Maki, and Maciej Mazurowski. systematic study of the class imbalance problem in convolutional neural networks. Neural Networks, 106:249 2018.
Luiz Chamon and Alejandro Ribeiro. Probably approximately correct constrained learning. Ad- vances Neural Information Processing Systems, 33, 2020.
Luiz FO Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained learning with non-convex losses. arXiv preprini arXiv: 103.05510 2021.
Philip K Chan, Wei Fan, Andreas L Prodromidis, and Salvatore Stolfo. Distributed data mining in credit card fraud detection. IEEE Intelligent Systems and Their Applications, 14(6):67-74, 1999.
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-357 2002.
Olivia Choudhury, Yoonyoung Park, Theodoros Salonidis, Aris Sikoulalas-Divanis, Issa Sylla, et al. Predicting adverse drug reactions distributed health data using federated learning. AM An- nual symposium proceedings, volume 2019, pp. 313, American Medical Informatics Association, 2019.
Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number samples. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9268-9277, 2019.
Moming Duan, Duo Liu, Xianzhang Chen, Yujuan Tan, Jinting Ren. Lei Qiao, and Liang Liang. Astraca: Self-balancing federated learning for improving classification accuracy of mobile deep learning applications. 2019 IEEE 37th international conference on computer design (ICCD), pp. 246-254. IEEE, 2019.
Jack Goetz, Kshitiz Malik, Due Bui, Seungwhan Moon, Honglei Liu, and Anuj Kumar. Active federated learning. arXiv preprint arXiv:1909 124441, 2019.
Hongyu Guo and Herna L Viktor. Learning from imbalanced data sets with boosting and data generation: the databoost-im approach. ACM Sigkdd Explorations Newsletter, 6(1):30-39, 2004.
Haibo He and Edwardo A Gareia. Learning from imbalanced data, IEEE Transactions on knowledge and data engineering, 1263-1244,,,4,, 2009.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint (00i::/9000063355 2019.
Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning deep representation for imbalanced classification. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 5375-5384, 2016.
Justin M Johnson and Taghi M Khoshgoftaar. Survey on deep learning with class imbalance. Journal of Big Data, 6(1):1-54, 2019.
10

---

Published as a conference paper at ICLR 2022
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. arXiv preprint arXiv: 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143. PMLR, 2020.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86( 1):2278-2324, 1998.
Geun Hyeong Lee and Soo- Yong Shin. Federated learning on clinical benchmark data: Performance assessment. Med Internet Res, 22(10))e2089,, Oct 2020. ISSN 1438-8871. doi: 10.2196/20891. URL httpthtpp//w/tt
i or httpi/rrrrg/2220/////22520
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data, 2020.
Tsung-Y Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference computer vision, pp. 2980-2988, 2017.
Charles X Ling and Victor S Sheng. Cost-sensitive learning and the class imbalance problem. Encyclopedia of machine learning, 2011:231-235, 2008.
Xu- Yu-Ying Liu, Jianxin Wu, and Zui-Hua Zhou. Exploratory undersampling for class-imbalance learn- ing. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 39(2):539-550, 2008.
Guodong Long, Yue Tan, Jing Jiang, and Chengqi Zhang. Federated Learning for Open Banking, pp. 240-254. Springer International Publishing. Cham, 2020. ISBN 978-3-030-
63076-8. doi: (000000978-3000063300 978 03000300000--0-
17. URL
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Ar- cas. Communicatinn-Efiiiennn Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu (eds.), Proceedingg of the 20th International Conference Artifi- cial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. PMLR, 20-22 Apr 2017. URL nommahan 7a 1atttam11.....1
mlr wtwppp/sss//////e
Samira Pouyanfar, Yudong Tao, Anup Mohan, Haiman Tian, Ahmed S Kaseb, Kent Gauen, Ryan Dailey, Sarah Aghajanzadeh, Yung-Hsiang Lu, Shu-Ching Chen, et al. Dynamic sampling in convolutional neural networks for imbalanced data classification. In 2018 IEFE conference on multimedia information processing and retrieval (MIPR), pp. 112-117. IEEE, 2018.
Alejandro Ribeiro. Optimal resource allocation in wireless communication and networking.
EURASIP Journal on Wireless Commaiccatinns and Networking. 2012(1):1-19, 2012.
Abhijit Guha Roy, Shayan Siddiqui, Sebastian Pölsterl, Nassir Navab, and Christian Wachinger. Braintorrent: A peer-to-peer environment for decentralized federated learning. arXiv preprint arXiv:1905.0673/ 2019.
Yanmin Sun, Mohamed S Kamel, Andrew KC Wong, and Yang Wang. Cost-sensitive boosting for classification imbalanced data. Pattern recognition, 40(12):3358-33) 2007.
Fabio Tardella. A new proof of the Iyapunov convexity theorem. SIAM journal on control and optimization, 28(2):478-485 1990.
Jason Van Hulse, Taghi M Khoshgoftaar, and Amri Napolitano. Experimental perspectives leam- ing from imbalanced data. Proceedings of the 24th international conference on Machine leamn ing, pp. 935-942, 2007.

---

Published as a conference paper at ICLR 2022
Hao Wang. Zakhary Kaplan, Di Niu, and Baochun Li. Optimizing federated learning non-iid data with reinforcement learning. In IEEE INFOCOM 2020-IEEE Conference on Computer Commu- nications. pp. (698-1707. IEEE, 2020a.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization, 2020b.
Lixu Wang, Shichao Xu, Xiao Wang, and Qi Zhu. Addressing class imbalance in federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10165-10173, 2021a.
Shoujin Wang, Wei Liu, Jia Wu, Longbing Cao, Qinxue Meng, and Paul J Kennedy. Training deep neural networks on imbalanced data sets. In 2016 international joint conference on neural networks (IJCNN), pp. 4368 4374. IEEE, 2016.
Yi Wang, Imane Lahmam Bennani, Xiufeng Liu, Mingyang Sun, and Yao Zhou. Electricity con- sumer characteristics identification: A federated learning approach. IEEE Transactions on Smart Grid, 12(4):3637-364) 2021b. doi: 10. 1109/TSG.002..30666
Qiong Wu, Xu Chen, Zhi Zhou, and Junshan Zhang. Fedhome: Cloud-edge based personalized federated learning for in-home health monitoring. IEEE Transactions on Mobile Computing, pp- 1-1, 2020. doi: 10.1 109/TMC..002.334536600
Wenchao Xia, Tony QS Quek, Kun Guo, Wanli Wen, Howard H Yang, and Hongbo Zhu. Multi- armed bandit-based client scheduling for federated learning. IEEE Transactions Wireless Com- 2020.
mumications, 19(1
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mniss a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Miao Yang, Akitanoshou Wong, Hongbin Zhu, Haifeng Wang, and Hua Qian. Federated learning with class imbalance reduction, 2020.
Wensi Yang, Yuhang Zhang, Kejiang Ye, Li Li, and Cheng-Zhong Xu. Ffd: A federated learning based method for credit card fraud detection. In Keke Chen, Sangeetha Seshadri, and Liang-Jie Zhang (eds.), Big Data BigData 2019, pp. 18-32, Cham, 2019. Springer International Publish- ing. ISBN 978 778-3-030-23551-4
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. Interna- tional Conference on Machine Learning, pp. 7252-7261. PMLR, 2019.
Xinwei Zhang, Mingyi Hong. Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005. 14418, 2020.
12


Reviews:
[{"review_id": "Z5Z37kEGYRa", "reviewer": "Reviewer_u6Lr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is well written, with sufficient background and motivating examples on the problem under consideration. There exists some minor grammatical issues in Section 2 which needs to be carefully reviewed.\nThe empirical results clearly shows benefits of the solution setup. However, there are 3 suggestions to improve the paper: (1) Use of more complex datasets, (2) Comparison with other FL algorithms mentioned in the paper, even under additional settings such as active learning, MAB etc. (3) Need for ablation study on alpha.\n\nThough MNIST and CIFAR10 is typically used as a standard dataset in literature, there exists more complex image datasets where the proposed method may struggle. From the current description, the limitations of the methods are not clear. Where does the method not work? If it works, why does it work? Here, comparison with existing techniques may aid in showing reasons for enhanced model performance. Finally, it would be interesting to see how variation in alpha affects model performance. If alpha=0.5, would the model still work relative to its baseline? When deploying the model in practice, alpha may not be known.\n\nIt is also not clear on how training and deployment of the algorithm work in practice. If a new client is added to the federated system, how does that affect model performance when shift in global data imbalance change? It would be good to discuss future work and how its applicability to multiclass classification would affect computational performance.", "summary_of_the_paper": "The paper describes an agnostic constraint learning method for handling class imbalance in a federated learning setting. Here, a client may have a minority class which is globally (across clients) a majority class. By setting up the constraint learning using Lagrange multipliers, the theoretical solution and convergence guarantees is shown, along with empirical evidence of the methods superiority.", "summary_of_the_review": "The paper provides good theoretical and empirical justification of a unique problem of addressing extreme local imbalance in a federated data system while maintaining data privacy. However, additional supporting material and stronger empirical support may be required to justify strong conclusions in the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "R2RQ4UtvLSp", "reviewer": "Reviewer_Mp3G", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The problem is clearly stated and the algorithm is well-organised, theoretical analysis is provided;\n2. The problem itself is interesting, non-iid and imbalance is a key challenge in federated learning and real-world setting;\n3. The proposed algorithm is simple but efficient, since it does need sharing local data, privacy of local clients is also kept. Also, no prior knowledge required matches the real-world setting;\n4. The way of partitioning the data is reasonable;\n5. The experiments are mostly sound and comprehensive. Code is provided in the material, thus it should be easy to repeat the experiments and utilize the algorithm;\n\nWeaknesses:\n1. More citations on non-iid/imbalanced federated learning should be cited or taken into consideration as baselines. For example, [1][2][3];\n2. Some minor written issues need to be taken care of. For example, g(\\theta) needs to be defined before using it;\n3. In the paper, the authors stated that \"in the extreme case where every device has only one class, these methods have inferior performance than the classic Fed-Avg method,\" it would be good if the authors can provide the results in appendix. Also, in some non-extreme settings, if some of those algorithms perform better than FedAvg, it should be considered as a baseline;\n4. The experiments are good, but would be better if results of experiments on other datasets, for example, synthetic dataset, fashion-MNIST are provided.\n\n\n\n[1] Tackling the objective inconsistency problem in heterogeneous federated optimization. J Wang, Q Liu, H Liang, G Joshi, HV Poor - arXiv preprint arXiv:2007.07481, 2020\n\n[2] H. Wang, Z. Kaplan, D. Niu and B. Li, \"Optimizing Federated Learning on Non-IID Data with Reinforcement Learning,\" IEEE INFOCOM 2020 - IEEE Conference on Computer Communications, 2020, pp. 1698-1707, doi: 10.1109/INFOCOM41043.2020.9155494.\n\n[3] On the convergence of fedavg on non-iid data. X Li, K Huang, W Yang, S Wang, Z Zhang - arXiv preprint arXiv:1907.02189, 2019", "summary_of_the_paper": "This paper focuses on an interesting and challenging setting in federated learning, where number of classes and samples are imbalanced across different local workers. Compared to other methods which might require subset of local data or prior knowledge of the minor classes, the algorithm proposed in this paper does not need neither local data nor prior knowledge, which maintains the privacy principle in federated learning and aligned to real-world settings. The main contributions are:\n1. Proposes a new algorithm solving the non-iid issue in federated learning which only adds constraints on local losses, without sacrificing local data privacy;\n2. Utilizes a primal-dual optimization mechanism to solve the problem, provides theoretical guarantees on convergence;\n3. Based on the experiments, there is a significant performance increase compared to FedAvg.", "summary_of_the_review": "This paper proposes a new algorithm on imbalanced setting in federated learning. It enjoys the advantages of not leaking local data and no need of prior knowledge and overall the algorithm based on primal-dual optimization is easy to understand and be utilized. It is a good paper after minor revisions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "L3DrAEUPc5d", "reviewer": "Reviewer_obo5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main concern about the paper is the presentation of CLIMB as the method counteracting the issue of class imbalance. The method itself directly optimizes a problem that imposes small differences in classification performance among the clients. This certainly improves the fairness of the trained model, but it does not help when data is imbalanced. The authors demonstrate that CLIMB improves performance on minority classes in the imbalanced setting; however, it seems that it is only because the authors distribute the data across the clients in a special manner. Concretely, the dataset of selected clients contains a lot of minority examples, to the extent that locally the minority class has much more examples than majority classes. Therefore, a method that looks for a fair model (similar performance for each client) naturally also improves for imbalanced classes. However, it is difficult to say to what extent such particular data distribution occurs in practice. Moreover, the approach seems not to handle class imbalance in any way if the data is not distributed in such a particular way.\n\nThe second concern is about privacy. The approach seems to require sending lambda values for each client to the server, which are directly related to the difference between average performance among the clients and the client's performance. Therefore, by observing the value of lambda, one can deduce if the performance on client's data is good. Since the classifier usually better recognizes majority classes (particularly during training), the high lambda value possibly indicates clients with many minority class data? Have the authors considered this issue? \n\n", "summary_of_the_paper": "The paper proposes an interesting new federated learning approach called CLIMB that leverages a special formulation of the FL problem as optimization with constraints. The approach aims to improve the classification performance of FL method on class imbalanced data.\n", "summary_of_the_review": "In general, the paper is well written, and the algorithm presentation is clear. The experimental evaluation is, in my opinion, insufficient if we interpret CLIMB as an imbalanced learning method (see the second paragraph of the review). For instance, more different ways of distributing data among the clients should be investigated. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3as-Cj3yMw", "reviewer": "Reviewer_8nbc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n1. Their method is agnostic to class distribution of the client data, which satisfies the privacy requirements of FL.\n\n2. There is no need for active client selection in their method which is more practical than other similar work.\n\nWeaknesses:\n1. My first concern is about the Assumption 3.4. It seems too strong to me. Can you provide more FL literature which support this assumptions? I also hope you could provide a simple example which satisfies this assumption.\n\n2. I am quite confused with the Theorem 3.2. What is the relationship between Theorem 3.2 and convergence of FL algorithms? Maybe you could combine it with Theorem 3.1 and add more detailed explanations to them.\n\n3. The settings of  the experiments is ambiguous. In the caption of Table 1&2, what does “sufficiently many communication rounds” means? \nI recommend the authors should add some “Accuracy and Epoch” figures to show how fast the accuracy increases in their method and other baselines.\n\n4. The results in Table 2 show that their method can achieve a better performance than Table 1. I think the authors should provide some theoretical analysis to explain this phenomenon.\n\n5. In the section of introduction, the authors mention that a drawback of Yang et al., 2020 is that “a subset of the client’s local data need to be shared”. Why? \n\n6. Minor typos. “they will a higher probability to”->\"there will ...\"\n", "summary_of_the_paper": "The authors design a method, CLIMB, to solve the severe class imbalance issues in FL problem. In their method, they propose a constrained FL formulation (CFL) and adopt the method of Lagrange multipliers to solve this problem. They present some theoretical and experimental results to prove that their method is effective.", "summary_of_the_review": "Although reducing the class imbalance in FL is an interesting topic and the method in this paper is new, I still think their method are not well-supported by theories and experiments according to the above discussion. Therefore, I think it is marginally below the acceptance threshold and needs further improvements.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a method to handle class imbalance in federated learning, while accounting for data heterogeneity and privacy. The key idea is to solve a constrained optimization problem where the difference between the global and local objective values has to be less than some parameter $\epsilon$. The paper proposes a primal-dual optimization algorithm called CLIMB to solve this constrained FL problem. The paper presents a theoretical analysis of the algorithm, as well as experimental results. 

All the reviewers found the formulation interesting and novel and gave a positive assessment of the paper. Reviewer obo5 had some concerns about whether the optimization problem is improving fairness and getting reduced class imbalance as a side benefit or whether it is directly addressing class imbalance. After discussion with the authors, their concerns were partially addressed. Reviewer 8nbc had concerns about the assumptions and theoretical analysis. Their concerns were also mostly addressed by the authors during the discussion phase. I suggest the authors to also address Reviewer u6Lr and Reviewer Mp3G's concerns about experimental results and citing related work respectively when they revise the paper.

Overall, I recommend acceptance of the paper, and strongly encourage the authors to take the reviewers' suggestions about 1) fairness connections, 2) privacy connections, 3) theoretical analysis, 4) experimental results, and 5) prior work into account when revising it.
Decision: Accept (Poster)