Year: 2021

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 realworld 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.

heading: 1 INTRODUCTION
text: 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 et al., 2020). In these scenarios, data belonging to a subset of classes constitute a great proportion of the population while data from the minority classes, generated by uncommon events, are scarce (He & Garcia, 2009). Having a 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 of mistreating the minority class can be catastrophic (Van Hulse et al., 2007) 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 a majority class globally. Moreover, for the purpose of privacy protection in FL, one should tackle the class-imbalance problem in an agnostic manner, i.e. the proposed algorithms should not require the minority class to be identified.
In the centralized training setting, techniques like balanced sampling, loss re-weighting, and gradient 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 explicit identification of the minority class do not directly apply. While research along this line is quite limited, a commonly used heuristic is 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 corresponding to different classes (Wang et al., 2021a; Yang et al., 2020). A key drawback of (Wang et al., 2021a) is that a subset of the client’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 minority 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 a minority user, the corresponding minority data could occupy a 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 handle the class imbalance issue in FL while accounting for both heterogeneity and privacy. In brief, we impose constraints on the standard FL formulation so that the empirical loss on 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 effect 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 are threefold: First, in contrast to previous arts which usually rely on some heuristics to reweight the loss functions for different classses, our approach is 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 is less likely to leak the private information of the clients. Third, from our extensive 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.
• Problem Formulation: To address the challenge of class imbalance in FL with data heterogeneity, 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).
• Meta-Algorithm: We solve our constrained optimization problem via a primal-dual approach. For a fixed dual variable, the corresponding Lagrangian function enjoys a similar structure as the standard FL loss, but with non-uniform weights on the local objectives. Accordingly, we propose an efficient (meta-) algorithm called CLIMB that can use any FL optimization method as a subroutine, with nearly negligible communication overhead. Furthermore, we analyze the convergence properties of CLIMB under certain oracle assumptions.
• Accuracy Improvement in the minority class: On benchmark datasets, CLIMB with Fed-Avg as base solver achieves significant enhancement of the accuracy in the minority class without compromising the overall accuracy under various data heterogeneity and class imbalance scenarios.

heading: 2 RELATED WORKS
text: 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., 2002; Guo & Viktor, 2004). Both methods seek to generate an artificial uniform distribution of data (Buda et al., 2018; Pouyanfar 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., 2019; 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-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 (Anand et al., 1993) showing faster rates of convergence in the class imbalance setting.
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 minority classes are often difficult to identify Li et al. (2020); 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 proportional 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-Loss, a class-wise re-weighted version of the standard cross entropy loss. We note that to define the Ratio-Loss, 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, Yang 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 Astraea which introduces extra virtual components called mediators between the FL server and clients (Duan et al., 2019). The mediator is assumed to have access to the local data distributions 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 balanced 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 composition as the optimization progresses. Works along this research line usually rely on client selection to mitigate the effects of class imbalances. In (Goetz et al., 2019), to address the class imbalance problem, there will a 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 selection policy to balance the gradients (Xia et al., 2020). Other arts leverage Q-learning techniques to select clients in order to minimize the overall loss Wang et al. (2020a). However, we believe in the most practical setting of FL, clients that are available per communication round is incoercible and hence these strategies have limited applicability.
Comparison with Previous Works. Our method significantly differs from the above strategies in the following ways: (1) 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 preserves clients’ privacy. Such a 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 clientwise re-weighting 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.

heading: 3 FEDERATED LEARNING WITH EMPIRICAL LOSS CONSTRAINTS
text: We consider the problem of multi-class classification. Let x ∈ X ⊆ Rd be the input and use y ∈ Y = {1, . . . , C} to denote the target label, where C is the total number of classes. In the context of FL, we assume to have N clients, each of which posses its own private data distribution pi(x, y). Here, pi(x, y) is a joint probability distribution of the input x and the output label y. One can decompose pi(x, y) as pi(x, y) = p(x|y)pi(y), where p(x|y) is the conditional distribution of the input x given class y and pi(y) is the marginal distribution of class y on client i. We assume that the conditional distribution p(x|y) is identical on all devices, but the marginal distribution pi(y) can vary significantly due to the heterogeneity of the data configuration.
LetH = {φ : X ×Θ→ RC} be a family of parameterized predictors with parameter θ ∈ Θ ⊆ RQ. Let ` : RC ×Y → R+ be the loss function, then the local objective function of client i is defined as
fi(θ) = E(x,y)∼pi [`(φ(x, θ), y)]. (1) For multi-class classification, ` is often chosen to be the cross entropy loss. In the standard formulation of FL, the goal is to minimize the global average of local objectives
min θ∈Θ
f̄(θ) := 1
N N∑ i=1 fi(θ). (2)
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 phenomenon for a concrete class imbalance setting. More importantly, such a setting will also motivate our constrained FL formulation. We emphasize that the following setting is just used as a motivating example to showcase our claims, and our results apply generally to any FL setting.
Motivating Example. Let u be the uniform distribution over the classes, i.e. for y ∼ u, Pr(y = c) = 1C ,∀c ∈ Y and let δc be the Dirac distribution of class c. We assume for some small but fixed α ∈ [0, 1], the local class distribution of the client i is a mixture of the uniform distribution over all classes and the Dirac distribution of a fixed class ci, i.e. pi = αu+ (1−α)δci . We use Nc to denote the number clients with ci = c. Note that in the limit setting when α = 0, the aforementioned configuration captures the most heterogeneous setting: clients only have data from a single class. We consider an 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 1 to be the minority class with N1 = 1. We define gi(θ) := Ex∼p(x|y=i)[`(φ(x, θ), i)] as the loss of the predictor φ(·, θ) on the data with y = i. We can calculate that
f̄(θ) =
( α
2 + 1− α N
) g1(θ) + ( α
2 + (1− α)(N − 1) N
) g2(θ). (3)
Clearly, when α, the portion of data with uniform label distribution, is small, e.g. α = 0, 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 a 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.

heading: 3.1 CONSTRAINED FL FORMULATION
text: In our work, to address the class imbalance challenge, we propose to minimize the following constrained FL (CFL) formulation
P ∗ = min θ∈Θ
f̄(θ) := 1
N N∑ i=1 fi(θ) (CFL)
s.t. fi(θ)− f̄(θ) ≤ , ∀i ∈ [1, . . . , N ]. Here, is 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 by encoding it in the subscript. As a motivation, we show that the constraint in our formulation (CFL) can be translated to a 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.e. is close to zero. WLOG, we assume that the first device is the one that has ci = 1. Recall the definition of gi above Eq.(3). One can compute that
f1(θ)− f̄(θ) = (1− α)(N − 1)
N (g1(θ)− g2(θ)) ≤ ⇐⇒ g1(θ)− g2(θ) ≤
N
(1− α)(N − 1) .
Therefore, our formulation (CFL) enjoys a clear class-balancing interpretation in the highly heterogeneous 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.
Algorithm 1 CLIMB: CLass IMBalance Federated Learning 1: Input: initial model θ0, a subroutine ClientUpdate, dual step size ηD, maximum round T ; 2: Initialize the dual variables λ = [0, . . . , 0]; 3: for t = 1, 2, . . . , T do 4: Compute weights: ∀i ∈ [N ], wi = 1 + λi − λ̄, with λ̄ = 1N ∑N i=1 λi;
5: Primal Update: θt+1 ← ClientUpdate({wi}Ni=1, θt); 6: Dual Update: ∀i ∈ [N ], λi ← [λi + ηD(fi(θt+1)− f̄(θt+1)− )]+, with f̄ = 1N ∑N i=1 fi; 7: end for 8: Output: model θT+1
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, or 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 an equivalent Lagrangian formulation.

heading: 3.2 ALGORITHM CONSTRUCTION
text: In order to solve problem (CFL), we resort to the method of Lagrange multipliers. By introducing the dual variables λ = [λ1, . . . , λN ] ∈ RN+ , we define the Lagrangian function as,
L(θ,λ) = 1 N N∑ i=1 fi(θ) + λi fi(θ)− 1 N N∑ j=1 fj(θ)−  (4) = 1
N N∑ i=1 (1 + λi − λ̄)fi(θ)− λi , with λ̄ = 1 N N∑ i=1 λi. (5)
With this in hand, we can construct a lower bound of the above constrained optimization problem using the Lagrangian L(θ,λ) as follows:
D∗ = max λ∈RN+ min θ∈Θ L(θ,λ) ≤ min θ∈Θ max λ∈RN+ L(θ,λ) = P ∗ ,
where we often refer to D∗ as the dual problem. To solve the dual problem, we propose CLIMB, a method described in Algorithm 1, which is discussed in detail as follows. CLIMB proceeds by alternatingly optimizing over the primal variable θ and the dual variable λ. Primal Update. For a fixed λ, the minimization of Lwith respect to θ is equivalent to a re-weighted version of the standard unconstrained FL objective (2):
min θ∈Θ L(θ,λ)⇐⇒ min θ∈Θ
1
N N∑ i=1 (1 + λi − λ̄)fi(θ). (6)
Importantly, this simple and canonical form allows us to perform the update on θ using any FL 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 θ as the subroutine ClientUpdate({wi}Ni=1, θt) → θt+1. Such a subroutine takes the non-uniform weights {wi}Ni=1 on the local objectives and the current consensus model θt as inputs, and returns an updated model θt+1. Note that every call to ClientUpdate may consists of multiple communication rounds. Dual Update. Once we have obtained the new consensus model θt+1, we perform dual update on λ by taking a single dual ascent step of the following equivalent objective (given some fixed θ),
max λ∈RN+ L(θ,λ)⇐⇒ max λ∈RN+
1
N N∑ i=1 λi fi(θ)− 1 N N∑ j=1 fj(θ)−  . (7) To evaluate the gradient of L with respect to λ, we need to first broadcast the consensus model θt+1 and then aggregate the function values f(θt+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, is to transmit the functional value, which is negligible.

heading: 3.3 THEORETICAL GUARANTEES
text: Based on the recent progress in constrained learning (Chamon et al., 2021), we show that under the following 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 classH. Assumption 3.1 The loss function ` in the definition of the local objective (1) is L-Lipschitz, i.e.‖`(x, ·)− `(z, ·)‖ ≤ L‖x− z‖, and bounded by B.
Assumption 3.2 The conditional distribution p(x|y) is non-atomic for all y ∈ RC .
While usually the local data distribution is discrete, we can always augment it by randomly perturbing the data points with white noise, this is often used as data augmentation in vision tasks.
Assumption 3.3 There exists a convex hypothesis class Ĥ such that H ⊆ Ĥ, and there exists a constant ξ > 0 such that ∀φ̂ ∈ Ĥ, there exists θ ∈ Θ such that supx∈X ‖φ̂(x)− φ(x, θ)‖ ≤ ξ.
A simple strategy to construct Ĥ is to take the convex hull of H. When H is sufficiently rich, ξ can be expected to be small. Notice that this bound can be decreased by increasing the richness of the function classH. All the proofs can be found in the Appendix.
Theorem 3.1 (Near Zero Duality Gap) Under Assumptions 3.1, 3.2,3.3, and the Contrained Federated Learning problem is feasible in Ĥ with constraint −2Lξ, the Constrained Federated Learning problem has near zero-duality gap,
P ∗ −D∗ ≤ (2|λ∗ −2Lξ|1 + 1)Lξ, (8)
where λ∗ −2Lξ is the optimal dual variable associated with the Constrained Federated Learning problem equation CFL with constraints − 2Lξ over the space of functions Ĥ.
Theorem 3.1 establishes an upper bound on the duality gap of the Constrained Federated Learning Problem CFL. 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 − 2Lξ. In the case of the cross-entropy loss, as long as − 2Lξ > 0, 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.
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 λ ∈ RN+ , and precision δ > 0 there exists an oracle approximate solution θλ such that L(θλ,λ) ≤ minθ∈RQ L(θ,λ) + δ.
Theorem 3.2 (Convergence) Define the dual function d(λ) = minθ∈Θ L(θ,λ). Under Assumptions 3.1 to 3.4, for a fixed tolerance r > 0, the iterates generated by Algorithm 1, achieve a neighborhood of the dual problem D∗ in at most Tr = O(1/r) steps, i.e.,
d(λTr ) ≥ D∗ − δ − ηD 2 B2 − r, (9)
Due to space limitation, a detailed discussion of the convergence theorem is deferred to the appendix.

heading: 4 EXPERIMENTS
text: In this section, we evaluate our formulation (CFL) 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 is a significant mismatch between local and global imbalance. To ensure a fair comparison, we adopt the same base optimizer, Fed-Avg
in the current experiment1, for all formulations: the standard FL objective in Eq.(2), the proposed formulation in Eq.(CFL), Ratio-Loss (Wang et al., 2021a), and Focal-Loss (Lin et al., 2017). We emphasize that the novelty of our work lies in the new constrained FL formulation (CFL) and is orthogonal to the research of how the formulation is solved. In the following, we describe the datasets and models used in our experiments where more details are provided in the Appendix A. Datasets Two benchmark datasets are used in our experiments with the default train/test splits, which are MNIST (LeCun et al., 1998) and CIFAR10 (Krizhevsky et al., 2009). Heterogeneity. We generate heterogeneity in the local data distributions according to the strategy from (Karimireddy et al., 2020; Hsu et al., 2019): Let α ∈ [0, 1] be some constant that determines
1We are aware of the recent techniques, e.g. SCAFFOLD (Karimireddy et al., 2020) and FedDyn (Acar et al., 2020), designed to tackle the heterogeneity in local data. However, surprisingly, our experiments show that in the extreme case where every device has only one class, these methods have inferior performance than the classic Fed-Avg method.
the level of heterogeneity. For a fixed α, we divide the dataset among N = 100 (moderate) or N = 500 (massive) clients as follows: for we allocate to each client a portion of α i.i.d. data and the remaining portion of (1− α) by sorting according to label. Data Imbalance. We simulate the phenomenon of class imbalance by removing data belong to the minority classes: Observe that the datasets included in our experiments both have 10 perfectly balanced classes. For the minority class(es), we retain only 1/ρ portion of the corresponding data. Here, ρ ≥ 1 the ratio between the numbers of data in the majority class and in the minority class 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, we consider the setting of 1 or 3 minority classes and we take ρ = 5, 10, 20. Models We follow the choice of model architectures in (Acar et al., 2020; McMahan et al., 2017). Specifically, we use a 2 hidden layer fully-connected neural network for MNIST, where the numbers of neurons are (128, 128). For CIFAR10, we use a CNN model consisting of 2 convolutional layers with 64 5 × 5 filters followed by 2 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.

heading: 4.1 RESULTS SUMMARY
text: To evaluate the effectiveness of an approach against the challenge of class imbalance, one 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 CIFAR10 and 1000 rounds for MNIST) under various experiment settings in Tables 1 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 a large margin. Imbalance Ratio and Number of Minority Classes. The imbalance ratio ρ and the number of minority classes are two important quantities to measure the difficulty of a 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 a rare merit when addressing the class imbalance problem. In fact, methods like Ratio-Lossis able to improve the testing accuracy on the minority class, but it also sacrifices the performance on the rest classes, leading to an inferior average testing accuracy. Level of Heterogeneity. We test the performance of CLIMB under different levels of heterogeneity 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, α = 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→ ρ = 5→ MNIST→ 3 minority classes→ α = 0. Moderate vs. Large Number of Devices An important goal of FL is to exploit the computational resources of the IoT devices. Hence, the scalability to a large number of devices is a critical property of an FL method. We hence test CLIMB on both moderate (N = 100, see Table 2) and massive devices (N = 500, see Table 1) settings. To make things more practical, we instantiate the subroutine ClientUpdate using Fed-Avg with the partial-participation scheme in the massive device setting. Specifically, 100 devices participate model training after every Fed-Avg global communication 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 procedure we enforced the performance to be similar in all clients, thus accounting for the class imbalances. In terms of privacy protection, our formulation requires no further information than the standard FL objective to be collected in the server and it 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.

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

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.

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: 1. Proposes a new algorithm solving the non-iid issue in federated learning which only adds constraints on local losses, without sacrificing local data privacy; 2. Utilizes a primal-dual optimization mechanism to solve the problem, provides theoretical guarantees on convergence; 3. Based on the experiments, there is a significant performance increase compared to FedAvg.