Maximizing Global Model Appeal in Federated Learning
Authors: Yae Jee Cho
Divyansh Jhunjhunwala
Tian Li
Virginia Smith
Gauri Joshi
Venue: Accepted by TMLR ()

Abstract: Federated learning (FL) aims to collaboratively train a global model using local data from a network of clients. To warrant collaborative training, each federated client may expect the resulting global model to satisfy some individual requirement, such as achieving a certain loss threshold on their local data. However, in real FL scenarios, the global model may not satisfy the requirements of all clients in the network due to the data heterogeneity across clients. In this work, we explore the problem of global model appeal in FL, which we define as the total number of clients that find that the global model satisfies their individual requirements. We discover that global models trained using traditional FL approaches can result in a significant number of clients unsatisfied with the model based on their local requirements. As a consequence, we show that global model appeal can directly impact how clients participate in training and how the model performs on new clients at inference time. Our work proposes MaxFL, which maximizes the number of clients that find the global model appealing. MaxFL achieves a $22$-$40\%$ and $18$-$50\%$ improvement in the test accuracy of training clients and (unseen) test clients respectively, compared to a wide range of FL approaches that tackle data heterogeneity, aim to incentivize clients, and learn personalized/fair models.

Published in Transactions on Machine Learning Research (03/2024)
Maximizing Global Model Appeal in Federated Learning
Yac Jee Cho
yuejeec www.ewwwwwmm.oommmmoommmmm. edu
Carnegie Mellon Universily
Divyansh Jhunjhunwala
Carnegic Mellon Universily
Tian Li
lition wwwndreanddddanneeo cmaL edu
Carnegie Mellon University University of Chicago
Virginia Smith Cornegie Mellon University
smithv@cmmu.ck edu
Gauri Joshi Carnegie Mellon Universily
gourtj@andree..cm edu.
Reviewed on OpenReview: https: // openreview. net/ forum? id= 8BI1SXqJBk
Abstract
Federated learning (FL) aims to collaboratively train global model using local data from network of clients. To warrant collaborative training, each federated client may expect the resulting global model to satisfy some individual requirement, such as achieving a certain loss threshold on their local data. However, in real FL scenarios, the global model may not satisfy the requirements of all clients in the network due to the data heterogeneily across clients. In this work, we explore the problem of global model oppeal in FL, which we define as the fotal number of clients that find that the global model satísfies their individual requirements. We discover that global models trained using traditional FL approaches significant. number of clients unsatisfied with the model based on their local requirements. As a consequence, we show that global model appeal can directly impact how clients participate in training and how the model performs on new clients at inference time. Our work proposes MAXFL, which maximizes the number of clients that find the global model appealing. MAXFL achieves a 22-40% and 18-50% improvement in the test accuracy of training clients and (unseen) test clients respectively, compared wide range of FL approaches that tackle data heterogeneity, aim to incentivize clients, and learn personalized/ fair models.
result in
1 Introduction
Federated learning (FL) is distributed learning framework that considers training machine learning model using a network of clients (c.g., mobile phones, hospitals), without directly sharing client data with central server (McMahan et al., 2017). FL is typically performed by aggregating clients' updates over multiple communication rounds to produce global model (Kairouz et al.) 2019). In turn, each client may have its own requirement that expects be met by the resulting global model under different scttings such as inference or with some fine-tuning. For example, clients such as hospitals or edge devices may expect that the global model performs at least better than local model trained in isolation the client's 's limited local data

---

Published in Transactions on Machine Learning Research (03/2024)
before contributing to FL training. Unfortunately, due to data heterogencity across the clients, the global model may fail to meet the requirements of all clients (Yu et al. 2020).
Previously, a plethora of works in FL on techniques such variance reduction (Karimireddy et al. 2019
personalization (Fallah et al. 2020 Dinh et al. 2020), and fairness (Li et al.) 2019) have proposed to train a global model or several personalized models that can better cater to the needs of the clients or the server. However, prior work has not directly focused on the total number of clients that are satisfied with the single global model based on their individual requirements, and has not explored how this may affect the training of the global model from the server's perspective when clients have the autonomy to freely join or leave the federation. Recent closely related works focus on clients' incentives from a game-theoretas lens (Hu al.) Kang et al., 2019 Zhang et al.. 2021 and establish useful insights for simple linear tasks, but it is difficult to extend these to practical non-convex machine learning problems. Other related works design strategies specifically to prevent client dropout (Wang& & Xu 2022 Gu et al. 2021), but these algorithms are stateful, i.., they require saving the gradient information from previously participating clients for the current updates, making them impractical to implement in cross-device settings (Kairouz et al., 2019). Moreover, these works only provide convergence guarantoes to the global minimum with respect to the standard FedAvg objective (McMahan et al., 2017), lacking theoretical ifstitication that their objectives can yield solutions that guarantee more participating clients compared to other classic FL objectives, even in simplified settings; we provide such guarantees for our proposed objective for mean estimation problems, which helps to shed light on our strong empirical performance (Section 2.2
2023
Proposing a new and formal metric to evaluate FL systems, we define that a global model is appealing to client if it satisfies the client's specified require- ment, such as incurring at most some max training loss. Subsequently, we define the number of clients which find the global model appealing as global model
80
80
80
80
Test Accorscy
Accurscy GM-Appeal
Tost Accuracy (%)
GMM-Appeal
60
GiM-App Appeal (%)
Test Accuracy
GM- And-Apppal
40-
40-
-00
appeal (GM-APPRAL; formalized in Definition [].
20
20
20
20
We show that having a high global model appeal is critical for the server to maintain a large pool of clients to select from for training, and for gathering additional willingly participating clients. This is es- pecially true in the light of clients possibly opting out of FL, due to the significant costs associated with training (e.g., computational overhead, privacy risks, logistical challenges), which is a practical concern not typically considered in prior work. With larger pool of clients to select from, a server can not only improve privacy-utility trade-offs (McMahan et al., 2018), but can also improve test accuracy on par- ticipating clients, and produce a global model that generalizes better at inference to new unseen clients (see Fig. and Table
0-
FodAvg FedProx MaxFL
FodAvg FedProx MaxFL
(a) Seen Clients
(b) Unseen Clients
Figure 1: model for FMNIST. A higher GM-Appeal results in a higher test accuracy for both the seen clients that have participated during training and unseen clients that have not, due to the server having a larger pool of clients to select from. MAXFL, which aims to maximize GM- Appeal, results in the highest test accuracy compared to the other baselines that do not consider GM-Appeal.
Test acc. and GM-Appeal of the global
In this work, we seek to understand: (1) What benefits exist when maximizing global model appeal relative to other common federated modeling approaches, and (2) What strategies exist to maximize global model appeal in federated settings. Our key contributions are summarized as follows:
We introduce the notion of global model appeal (referred to as GM-APPEAL) the fraction of clients that have their local requirements met by the global model. We then propose MAXFL, an objective that directly maximizos global model appeal, and show that having a high global model appeal can load to better test accuracy on training clients, as well as better generalization to unseen clients at inference time.
We theoretically show for mean estimation that the MAXFL objective yields a solution that guarantees higher GP-APPEAL than standard FL objectives and provide convergence guarantees for our MAXFL solver which allows partial client participation, is applicable to non-convex objectives, and is stateless (does not require clients to maintain local parameters during training).
2

---

Published in Transactions on Machine Learning Research (03/2024)
We empirically evaluate the performance of MAXFL to thoroughly understand the benefits of maximizing GM-APPRAL, with experiments where i) clients can flexibly opt-out of training, ii) there are new incoming (unseen) clients, and iii) clients perform personalization via local fine-tuning with the global model.
We show that MAXFL significantly improves the global model appeal in practice, leading to a 22-40% and 18-50% test accuracy improvement for the seen clients and unseen clients respectively, compared to wide range of FL methods, including those that tackle data heterogeneity, aim for variance reduction incentivizing clients, or provide personalization or fairness.
Overall, our goal in comparing MAXFL with a variety of other FL methods that have varying goals is not necessarily to compele against these methods, but rather understand and demonstrate the potential benefits of our proposed notion of global model appeal relative to other objectives under different scenarios, such as with flexible client participation or new incoming clients. As global model appeal has not been studied previously in FL, our work is the first to explore its possible implications, and then propose an objective to train a global model that can maximize the number of clients whose individual requirements are satisfied. We hope our proposed perspective of viewing and evaluating FL systems can inspire future works in different FL scenarios and applications where client participation is not necessarily taken for granted, and can potentially be used in conjunction with prior approaches in FL (e.g., see Section D.2]. We provide a more detailed review of prior work and related areas of fairness, personalization and client incentives in Section
2 Problem Formulation
Setting, We consider a setup where M clients are connected to a central server to collaboratively train a global model. For each client & e [M], its true loss function is given by fa(w) = BE-DDI[(w, E)] where Dy is the true data distribution of client k and f(w, c) is the composite loss function for the model w E Rd for data sample ç. In practice, each client. only has access to its local training dalaset BR with [Bx] No data samples sampled from Dr. Client k's empirical loss function is F&(w) [8 Eses, E). While some of the lake-aways of our work (e.g., improving performance on unseen clients) may be more specific to cross-device applications, our general setup and method are applicable to both cross-device and cross-silo FL.
Defining Global Model Appeal. Each client's 's natural aim is to find a model that minimizes ils true local loss fw(w). Clients can have different thresholds of how small this loss should be, and we denote such self-defined threshold for each client as Pk: 1 E [M]. For instance, each client can perform solo training on its local dataset B₁ to obtain an approximate local model WE and have its threshold to be the true loss from this local model, i.e., Pk = fA (w Based on these client requirements, we provide the formal definition of global model appeal below:
Definition 1 (Global Model Appeal). A global model w is said to be appealing to client k E [M] if fx(w)= < Pk: i.e., the global model w yields a smaller local true loss than the self- delf-defined threshold of the client. Accordingly. we defone the fraction of clients to which the global model is appealing as global model appeal (GM-APPEAL) with I being the indicator function:
M [(fa(w) < pp)
GM-APPEAL 1 M.
(1)
Our GM-APPEAL metric measures the exact fraction of clients that find the global model appealing by focusing on whether the global model satisfies the clients' requirements not instead of looking at the gap between f& (w) and Pk. Another variation of T could be to measure the margin Σe max{pk - f& (w). 0}, but this does not capture the motivation behind our work which is to understand how the number of clients that find the global model appcaling affects the global model performance.
Why Explore GM-Appeal in FL? GM-APPEAL. measures how many clients have their requirements satisfied by the global model. Thus, it can gauge important characteristics of the server's global model such as i) how many clients are likely to dropout with the current global model or ii) how many new incoming
The client can have held-out data used for calculating the true loss fx(+) or its training data as proxy. We explain in more detail of defining Pa Section g
3

---

Published in Transactions on Machine Learning Research (03/2024)
clients that do not have the capacity for additional training will likely be satisfied with the current global model without any additional training to the model. Ultimately, a high global model appeal can lead to a larger pool of clients for the server to select from. The standard FL objective (McMahan et al. 2017] or its popular variants (Karimiroddy et al.) 2019 Li et al. 2020; Fallah et al.) 2020) docs not consider whether the global model satisfies the clients' requirements, and implicitly assumes that the server will have a large number of clients select from. However, this may not necessarily be true clients are allowed to dropout when they find the global model unappealing. We show that acquiring a larger pool of clients by improving global model appeal is useful for improving the global model for both the seen clients at training as well as the unseen clients at inference (see Fig. | and Table D. In fact, we find that other baselines such as those that aim to tackle data heterogeneity, improve fairness, or provide personalization have low GM-Appeal, leading to a large number of clients opling out. Due to this, the global model is trained on just a few limited data points, resulting in poor performance. Our work explores a new notion of global model appeal, showing its significance FL.
2.1 Proposed MaxFL Objective
In this section, we first introduce MAXFL whose aim is to train a global model that maximizes GM-APPEAL. A naive approach can be to directly maximize GM-APPEAL defined in (1) as follows:
argmax GM-APPEAL argmin Σ (f (w) pk).
(2)
where sign(z) = if 2 O and heewieee.. There are two immediate difficulties in minimizing 2 First, clients may not know their true data distribution Dj to compute fx (w) -w)-AP -p- Second, the sign function makes the objective nondifferentiable and limits the use of common gradient- methods. We resolve these issues by proposing a "proxy" for (2 with the following relaxations.
i) Replacing the Sign function with the Sigmoid function o()): Replacing the non-differentiabu 0-1 loss with a smooth differentiable loss is a standard tool used in optimization (Nguyen & Sanner) 2013
Masnadi-shirazi & Vasconcelos) 2008). Given the many candidates (e.g. hinge loss, ReLU, sigmoid), we find that using the sigmoid function essential for our objective to faithfully approximate the true objective in
2 We further discuss the theoretical implications of using the sigmoid loss Section 2.2
ii) Replacing (w( with F& (w): As clients do not have access to their true distribution Da to compute fi(.) we propose to use an empirical estimate o (FF((w)-PH pk). This is again similar to what is done in standard FL where we minimize F&(w) instead of fx( at client k. Note that the global model w is trained on the data of all clients, making it unlikely to overfit to the local data of any particular client, leading to Sk(W) x (w), which we also show empirically in Appendix D.2
With the two relaxations above, we present our proposed MAXFL objective:
M
1
MAXFL Obj:: min F(w) = min
(ww,, where F((w) := oFF((() ps). M
(3)
Before presenting our proposed solver for the MAXFL objective, we first present motivating toy example with mean estimation which shows that MAXFL's objective leads to different solution that has higher GM-APPEAL compared to the solution obtained from the classic FL objective.
2.2 Toy Example: Maximizing GM-Appeal in Mean Estimation
We consider a toy setup with M = 2 clients where the true loss function at each client is given by fe(w) = (w - 0z)2. In practice, clients only have N₂ samples drawn from the distribution given by ekij ~ No 2). Vj [Nx]. We further assume that the empirical loss function at each client is given by Fx(w) = (w 02) + (6. 6,)² where 0g is the empirical mean, 0. = प.. Σnn CR.j- It is easy to see that the
minimizer of (w) is the empirical mcan 0z. Thus, we set the solo-traincd model at cach client as T = o and the loss threshold requirement at client Pk Fs (wxx)) (ō. 0z)
4

---

Published in Transactions on Machine Learning Research (03/2024)
GM-Appeal for Standard FL Model Decreases Exponentially with Heterogeneity. For simplicity let us assume N1 N2 = N where 72 = /N is the variance of the local empirical means and n = ((0) - 02) > 0 is the measure of heterogeneity between the true means. The standard FL objective will always set the FL model to be the average of the local empirical means (i.e. (01 + 02) and does not take into account the heterogeneity among the clients. As a result, the GM-Appeal of the global model decreases exponentially as n increases.
Lemma 2.1. The expected G---ppeal of the standard FL model is upper bounded by 2xx (-72/(572)), where the expectation is taken over the randomness in the local datasets B2
Maximizing GM-Appeal with Relaxed Objective. We now maximize the GM-Appeal for this setting by solving a relaxed version of the objective in (2 as proposed earlier. We replace the true loss fx(() with the empirical loss (.(+)) and replace the 0-1 (sign) loss with a differentiable approximation h(-). We first show that setting ht-) to be standard convex surrogate for the 0-1 loss (e.g. log loss, exponential loss, ReLU) leads to our new objective behaving the same the standard FL objective.
Lemma 2.2. Let h be ony function that conver, twice differentiable, and strictly increasing in oo).
Then our relared objective is strictly conver and has a unique minimizer at w² = =(1 + 02)
MaxFL Objective Leads to Increased GM-Appeal. Based on Lemma 2.2 we see that we need nonconvexity in h(.) for the objective to behave differently than standard FL. We set h(x) = o(x) = exp(=)/1+ + exp(x), as proposed in our MAXFL objective (3) and find that the MAXFI. objective adopts the empirical heterogeneity parameter % = (02 - 02/2)2. If % < (small data heterogeneity), the objective encourages collaboration by setting the global model to be the average of the local models. Conversely, if 28 > 2 (large data heterogeneity), the objective encourages seperation by setting the global model close to the local model of either client (see Fig. below). Based on this observation, we have the following theorem.
Theorem 2.1.
Let w be a local minima of the MAXFL objective. The expected GM-Appeal using w lower bounded by exp (-x-2)/ /16 where the expectation is over the local datasets B1, B2.
Observe that even with r > O, MAXFL will keep satisfying the requirement of at least one client by adapting its objective accordingly. We show the behavior of MAXFL in a 3-client setup which further highlights the non con-trivialness of our proposed MAXFL's formulation in Appendix A along with the simulation details for
Fig. 2
Details of our proof in this section can be found in Appendix B
FedAvg
(w))
Fl(w)
0.6
MaxFl (R)LU)
Loss (Objective)
(a()))
Loss (Objeetive)
Fe(w)
GM-Appeal
MaxF1
F(wi)
F(w)
0.4
0.2
01
0
4
0.0
0
5
10
-5
5
10
Data Heterogeneity (18)
W
w
(a)
(b) Smaller 00 = 1/4
(c) Larger 0e =4 4
Figure 2: (a): GM-APPEAL for FedAvg decays exponentially while GM-Appeal for MAXFL is lower bounded. Replacing the sigmoid approximation with ReLU in MAXFL leads to the same solution as FedAvg. (b-c): MAXFL adapts to the heterogeneity of the problem for small heterogeneity it encourages collaboration by having single global minima, for large heterogeneity it encourages separation by having far away local minimas.
3 Proposed MaxFL Solver
In this section, we present our MAXFL objective's solver. The MAXFL algorithm enjoys the following properties: i) uses the same local SGD procedure as in standard Fed, ii) allows partial client participation,
5

---

Published in Transactions on Machine Learning Research (03/2024)
and tii) is stateless. By stateless, we mean that clients do not carry varying local parameters throughout
training rounds, preventing issues from stale parameters (Wang et al. 2021p. With the sigmoid approximation
of sign loss and for differentiable F& (w), our objective F(w) in (3) is differentiable and can be minimized
with gradient descent and its variants. Its gradient is given by:
M
VF(w)=
1 M
Σ
(F Vfk(w).
(4)
aggregating weight:=q:(w
Observe that VF(w) is a weighted aggregate of the gradients of the clients' empirical losses, similar in spirit to the gradient FF(w) in standard FL. The key difference is that in MAXFL, the weights qu g&(w) ==
(1 - F& depend on how much the global model appeals to the clients and are dynamically updated based on the current model w, as we discuss below.
Behavior of the Aggregation Weights. For a given w, the aggregation weights gı (w) depend on the GM-APPEAL Gap, Fo(w)-ps (see Fig. 3 When F&(W) < Pk: the global model w
More Appealing
Less Appealing
Aggregating Weight
sufficiently meets the client's requirement. Therefore, MAXFL
0.2
sets 9& (w) RJ 0 focus on the updates of other clients. Sim- ilarly, if Fi (w) >> Pk, MAXFL sets qu (w) A O. This is because Fe(w)= >> Pk implies that the current model w is incompatible with the requirement of client k and hence it is better to avoid optimizing for this client at the risk of sacrificing other clients' requirements. MAXFI, gives the highest weight. to clients for which the global model performs similarly to the clients' require- ments since this allows to increase the GM-APPEAL without sabotaging other clients' requirements.
0.1
0.0
-10
0
10
GM-Appeal Gap F& (w(w) - Pk
Figure 3: Aggregating weight qk (W) versus the GM-APPEAL gap defined as Fx(w) Pk: for any client k E [M].
A Practical MaxFL Solver. Directly minimizing the MAXFL objective using gradient descent can be slow to converge and impractical, as it requires all clients to be available for training, Instead, we propose a practical MAXFL algorithm, which uses multiple local updates at each client to speed up convergence as done in standard FL (McMahan et al. 2017) and allow partial client participation. We use the superscript (t, r) to denote the communication round and the local iteration index r. In each round t, the server selects a new set of clients g(t.0) uniformly at random and sends the most recent global model w-(t.0) to the clients in g(t,0), Clients in S(t,0) perform 7 local iterations with learning rate ni to calculate their updates w (f,++1) = w(( mggw/ (org( ,4% c((."))) E (O,..., - 11 where g( (t.r)
(t.r).
B(w ,. c(f.r)) = Eece(t.)) V.[(w (((w( .g) is
the stochastic gradient computed using a mini-batch <((rr) of size b that is randomly sampled from client k's local dataset Bg. The weight qu (w(w(.)) can be computed at each client by calculating the loss over its training data with wh which is a simple inference step. Clients in S(+.0) then send their local updates Aw (t,0) w (t,r) we
(1.0) and weights qe( ue(w((.)) back to the server, which updates the global model
Dg Exeetco) (w(()))))+ is the adaptive server learning rate with global learning rate my and e O. We discuss the reasoning for such a learning rate below. The pseudo-code for our MAXFL solver can be found in Algorithm
(++1.00) = (t.0) na
(r,0) ExEstso) 9A ((.())))))) (t.0) where Th
(t.0)
Adaptive Server Learning Rate for MaxFL. With Le continuous and L. smooth Fs(w), Ak [M]] (sce Assumption 3.1 the objective F(w) is L, smooth where L, = hi Ex=19(()) + Le
4 (sce Appendix C Hence, the optimal learning rate î for the MAXFL is given by, î = 1/L.- MM/ (E* (x(w) + +)), where
7 7= + is the optimal learning rate for standard FL and ML. > 0 is a constant. The denominator of the 4L, optimal îj is proportional to the sum of the aggregation weights (w) and acts as a dynamic normalizing (t.0) (E qu (w((.0)) + +c)
factor. Therefore, we propose using an adaptive global learning rate n/ with hyperparameters Ng. 6.
Setting Pk as Fe( for MaxFL. One intuitive way to set Pk for each client to set it as the training loss value FR(WE) where We is client local model that is solo-trained with few warm-up local SGD steps
6

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm Our Proposed MAXFI. Solver
1:
Input: mini-batch size b, local iteration steps T, client requirement Pk: & E [M]
Output: Global model w(T:0)
Initialize: Global model w((..))
4: For 1 0,... communication rounds do:
5: Global server do:
6: Select m clients for S(t,0) uniformly at random and send w/(,00 to clients in S(,,0)
7: Clients h E S(t,0) in parallel do:
8: Set W (t.0) w(t.0), and calculate gs (w( (())) - (F&((w ((.)) pk)
9:
For r r= -..,.., -- local iterations do:
Update w (t,+1) <- wh (f.r) mig( (f,r)
10:
11: Send AwA (4.0) w (t.0) w (1,T) and aggregation weight qx (w((..)) to the server
12: Global server do:
Update global model with ((+1100) = w(t.0) - 1lg
(t.0) EkESu.. qu (w((.))) (1.0)
13:
on its local data. The loss value only needs to be computed once and saved as a constant beforehand at each client. How to train the local model Wx, such as deciding the number of steps of training or whether to add regularization, is dependent on the personal resources and requirements of the clients. Therefore, the quality of the local model (such as whether it has overfitted or underfitted) is not explicitly controlled by MAXFL. Nevertheless, we do provide an ablation study on the number of local SGD steps we take for training the local trained model and provide the results in Appendix D.2 which shows that MAXFL performance is in fact robust. to the number of local SGD steps we take and the performance does not vary much on this number. In the essence, Pk is client-dependent parameter that the client can choose, and our proposed MAXFL is a more general framework that can be used for any client-defined Pk. One might. raise concerns that adversarial clients can send arbitrarily small Pk in the hope to get high weights, but as Fig. clearly shows this will in fact make the client get smaller weights Further, we add experiments with byzantine clients in Section in Appendix D.2 and show that MAXFL robust to these specific attack scenarios.
A Appeal-based Flexible Client Participation. It may appear that our MAXFL solver requires clients to always participate in FL if selected even when the global model does not appeal to them. However, our algorithm is easily modified to allow clients to participate flexibly during training depending on whether they find the global model appealing or not. For such appeal-based flexible client participation, we assume that clients are available for training if selected only during few initial training rounds. After these rounds, clients are included in the pool of clients where the server can select the clients from only if they find the global model appealing. We demonstrate this extension of MAXFL with appeal-based flexible client participation in Table D The experiment shows that with ficxible client participation, retaining a high global model is even more imperalive for the server to achieve good Lest accuracy and generalization performance. We also show that even after we allow clients to participate flexibly, MAXFI. retains significantly higher number of clients that find the global model appealing compared to the other baselines.
3.1 Convergence Properties of MaxFL
In this section, we show the convergence guarantees of MAXFL in Algorithm | shows that the gradient norm of our global model goes to zero, and therefore we converge to a stationary point of our objective F(w). First, we introduce the assumptions and definitions below.
Our convergence analysis
Assumption 3.1 (Continuity & Smoothness of Fs(w), V k). The local objective functions F1 [W), ..., F.. (w), are To--continuous and T.g-shooth for any w.
Assumption 3.2 (Unbiased Stochastic Gradient with Bounded Variance for Fw(w,, k). For mini-batch & uniformly sampled at random from Bg, the resulting stochastic gradient unbiased, i.e., (Wg.(We.&Co Ex)l = (Ff(W)), and its variance is bounded: E[lgg:(w Ex) FFF((w)) $ og.
Assumption 3.3 (Bounded Dissimilarity of F(w)). There erists B² 2 1, x2 2 0 such that # EM [FF 1 DM (F](2)]22 R2 for any w.
7

---

Published in Transactions on Machine Learning Research (03/2024)
Assumption 3.1
3.3 are standard assumptions used in the optimization literature (Stich 2019
Karimireddy
et al. 2019
Bistritz et al. 2020 Wang et al. 2020), including the l:c-ooninuity assumption (Shalev-Shwartz
et al. 2009
Riis al. 2.21p. Note that we do not assume anything for proposed objective function F(w)
and only have assumptions over the standard objective function F(w) to prove the convergence of MAXFL
over F(w) in Theorem 3.1
Theorem 3.1 (Convergence to the MAXFL Objective F(w)). Under Assumption 3.1 3.3 suppose the
server uniformly selects m out of M clients without replacement in each round of Algorillm 7 With
m VT+ 72 VTm, for total communication rounds T of the MAXFL solver in Algorithm we have:
( so (
T (mrTT)
09 Tt
B
min E
+0
+0
+0
(5)
(T
VTm
T
where O subsumes all constants (inckuding L, and L.).
Theorem 3.1 shows that with a sufficiently large number of communication rounds T' we reach a stationary where we also show a version of
point of our objective function F(w). The proof is deferred to Appendix C this theorem that contains the learning rates fl and rp with the constants.
4 Related Work
To the best of our knowledge, the notion of GM-APPEAL and the proposal to maximize it while considering flexible client participation have not appeared before in the previous literature. Previons works have focused on the notion of satisfying clients' personal requirements from a game-theorelic lens or designing stralegies specifically to prevent client dropout, including the use of personalization, which have their limitations, as we discuss below.
4.1 Incentivizing Clients and Preventing drop-out
A recent line of work in game theory models FL as a coalition of self-interested agents and studies how clients can optimally satisfy their individual incentives defined differently from our goal. Instead of training a single global model, Donahue & Kleinberg 22021a b) consider the problem where each client tries to find the best possible coalition clients to federate with to minimize its own error. Blum et al. (2021) consider an orthogonal setting where each client aims to satisfy its constraint of low expected error while simultaneously trying to minimize the number of samples it contributes to FL. While these works establish useful insights for simple linear tasks, it is difficult to extend these to practical non-convex machine learning tasks. In contrast to these works, in MAXFL we aim to directly maximize the number of satisfied clients using a global model. Concurrent work (Huang et al.) 2023) has evaluated the diverse data contributions in FL where the tension between the server and the clients modcled as a utility-cost function to analyze the optimal behavior of clients in FL and propose a mechanisam lo incentivize agents to give contribution to FL using the Stackelberg game to maximize the total utility. Another concurrent similar line of work (Dorner et al., 2023) has investigated how to incentivize "honesty" across clients in FL where honesty implies clients sending local updates that are true to their local data and non-malicious. This perspective alleviates some of the analysis complexities occurring in game-theoretic formulations and allows us to consider general non-convex objective functions.
A separate line of work looks at how to prevent and deal with client drop-out in FL. Wang & Xu 2022 introduce a notion of 'friendship' among clients and proposes to use friends' local update as a substitute for the update of dropped-out clients. Gu et al. (2021) propose to use previous updates of dropped-out clients as a substitute for their current updates. Both algorithms are stateful. Another line of work (Han al. 2022. Kang al. 2019 Zhang et al.] (021) aims to incentivize clients to contribute resources for FL and promote long-term participation by providing monetary compensation for their contributions, determined using game-theoretic tools. These techniques are orthogonal to MAXFL's formulation and can be combined if needed to further incentivize clients.
4.2 Personalized and Fair Federated Learning
Personalized federated learning (PFL) methods aim to increase performance by training multiple related models across the wetwork (e.g.. Smith al. 2017). Tn contrast to PFT, MAXFI. focuses on the challenging goal of
8

---

Published in Transactions on Machine Learning Research (03/2024)
training stngle global model that can maximize the number of clients for which the global model outperforms their local model. Unlike PFI. which may require additional training new clients for personalization,
MAXFL's global model can be used by new clients without additional training (see Table 2 Also, MAXFL is stateless, in that clients do not carry varying local paramoters throughout training rounds as in many popular personalized FL methods (Smith et al. 2017: Dinh et al., 2020 Fallah et al. 2020 Li et al. 2021), preventing parameter staleness problems which can be exacerbated by partial client participation (Wang et al. 2021 p.
Furthermore, MAXFL is orthogonal to and can be combined with PFL methods. We demonstrate this in
Table 3 where we show results for MAXFL jointly used with personalization via fine-tuning (Jiang et al., We compare MAXFT. + +Fine-tuning with another well known PFT. method PerFedAvg (Fallah et al. 2020 and show that MAXFL appeals to a significantly higher number of clients than the baseline.
2019
Finally, another related area is fair FL, where common goal is to train a global model whose accuracy has less variance across the client population than standard FedAvg (Li et al. 2019 Mohri et al. 2019). A side benefit of these methods is that they can improve global model appeal for the worst performing clients. However, the downside is that the performance of the global model may be degraded for the best performing clients, thus making it unappcaling for them to participate. We show in Appendix D.2 that fair FL. methods are indeed not effective in increasing GM-APPEAL.
5 Experiments
In this section we evaluate MAXFL for a number of different datasets while comparing with a wide range of baselines to show that maximizing GM- APPEA,,,L, ie., training a global model that can appeal to a larger number of clients, provide many benefits for FL including: i) the server gaining more participating clients to select clients from for training better global model for the seen clients, ii) the global model having a higher chance to have good performance on unseen clients, and iii) clients gaining better performance with the global model when they combine MAXFL. with local fine-tuning.
Datasets and Model. We evaluate MAXFL in three different settings: image classification for non-iid partitioned (i) FMNIST (Xiao et al., 2017) (ii) EMNIST with 62 labels (Cohen et al., 2017), and (iii) sentiment analysis for (iv) 140 (Go et al. 2009hwith MLP. For FMNIST, EMNIST, and 1e dalaset, we consider 100, 500, and 308 clients in total that are used for training where we select 5 and 10 clients uniformly at random per round for FMNIST and EMNIST, S4nt respectively. These clients are active at some point in training the global model and we call them 'seen clients'. We also sample the 'unseen clients' from the same distribution from which we generate the seen clients, with 619 clients for Sent140, 100 clients for FMNIST, and 500 for EMNIST. These unseen clients represent new incoming clients that have not been seen before during the training rounds of FL to evaluate the generalization performance at inference. Further details of the experimental settings are deferred to Appendix D.1
Baselines. We compare MAXFL with numerous well-known FL algorithms such as standard FedAvg McMa han et al. ireddy et al. 2019) which aims for variance-reduction PerFed (Fallah et al. 2020), pFedme (Dinh el al. 2020) which facilitates personalization; MW-Fee (Blum et al. 2021) which incentivizes client participation; and qFLL which facilitates fairness [Li ct al. 2019). For all algorithms, we set Ps: to be the same, i.c., Pk = (W)), where We is obtained by running a lew warm-up local SGD steps on client k's data as outlined in Section 3 to ensure a fair comparison across baselines. We perform grid search for hyperparameter tuning for all baselines and choose the best performing ones.
2017); FedProx (Sahu et al. 2020) which aims to tackle data heterogeneity; SCAFFOLD Karim-
Evaluation Metrics: GM-Appeal, Average Test Accuracy, and Preferred-model Test Accuracy.
We evaluate MAXFL and other methods with three key metrics: 1) GM-APPEAL, defined in ( 2) average test accuracy (avg. test acc.) across clients, and a new metric that we propose called 3) proferred-model test accuracy. Preferred-modee (est accuracy is the average of the clients' test accuracies computed on either the global model w or their solo-trained local model WE, whichever one satisfies the client's requirement. We belive that average test accuracy is a more server-oriented metric as assumess that clients will use the global model by default. On the other hand, moder test accuracy is a more client-centric metric that allows clients to select the model which works best, thereby better reflecting their actual satisfaction.
9

---

Published in Transactions on Machine Learning Research (03/2024)
Seen Clients
Unseen Clients
FMNIST
EMNIST
FMNIST
EMNIST
Test Acc.
Test Acc.
AMPAPPELL
Test Acc.
GM-APPEAL.
Test Acc. GM-APPEAL.
FedAvg
43.70(10.02)
35.15(10.51) 0.04(10.0)
43.14(=0.23) (.02
(.0001))0
0.06(40.0) (7.14
FedProx
14.59(+1.94)
0.05(+0.01)
0.004(+0.0) 34))
43.80(=1.67)
(=00
36.82(+0.22)
0.008(=0.0)
Scaffold
39.90(40.09)
0.0
34.78(4-2.05)
39.24 0.0(+b.0)
0.01
14.19(+1.25)
0.004
Pvr
46.62(11.0)
0.05(20.0)
34.78(11.05)
0.003(10.0)
46.00
0.07(40.0)
36.92
0.008
PRedme
31.06
(#2.06)
0.0 (+0.0)
9.78 (#2.13)
0.0 (#0.0)
20.11 (#3.4)
0.0 (#0.0) 7.05 (#1.03)
0.0 (+0.0)
FFFL.
29.92(+3.13)
0.0(20.0)
15.95(+3.02)
0.0(20.0)
19.63(=2.17)
0.0(
(_4
0.0(20.0)
MW-Fed (422(+2.38))
0.0
30.04++3.07)
13.16(=2.15) (=01
(.06
36.51(#0.40)
(.01
MAXFL 70.86(12.16) (.37 67.34(214))
0. (.2.03) /4.53/=0.50
(000)) 55. (20.8)) 0-31(=0.03))
Table 1: Avg. test accuracy and GM-Appeal where we train for 200 communication rounds. At the 10th communication round, we let clients flexibly opt-out opt-in depending on whether the global model has met their requirements. We report the final avg. test accuracy and GM-Appeal at the 200th comm. round.
Preforrdd- Preforod-Modd]] Test Asc.
09.3
06
FedAvg
Preferred Model Tel Tel Acc.
FodAvg
GM--Appaal
0.4
09.2
GMd-Appeal
FedProx
MW-Fee
MW-Fer Fed
FedFrox
FedAvg FedProx
PodAvg
MaxFL
0.2
99.3
FedProx
07
MW-Fed
MW-FFal
MaxFt
99.
MaxFl.
20
40
60
100
21
50 10
100
100 Communication Rounds
50
150
20
60
100
Commamication Rounds
Commmmication Rounds
Communication Rounds
(a) FMNIST
(b) Scm1140
Figure 4: GM-APPEAL and refferred-modd test accuracy for the seen clients significantly higher for
MAXFL. Therefore, clients can also benefit from choosing either the local or global model for best performance, while the server also gains large number of clients to select from.
Note that the preferred-model test accuracy is a complementary novel metric we propose to gauge the satisfaction of the clients when they can choose between the global and local models. For instance, if we have a high preferred-mode test accuracy but a low GM-Appoal where all clients are not interested in the global model, then the primary objective of MAXFL has not been achieved. However, in our results we show that in fact MAXFT. has the complementary effect of not only being able to maximize the GM-Appeal, but also have higher proeerred-model test accuracy. This is because MAXFL is able to find the global model that can perform better than a prefixed threshold for as many clients as possible, and therefore compared to the other global models trained from different baselines, the test accuracy for those clients who chose the global model is higher.
5.1 Experiment Results
Average Test Accuracy of Seen Clients & Unseen Clients. We first show that we improve the GM-APPEAL and thus the average test accuracy performance for the 'seen clients' used during the training of the global model. In Table [ we show the average test accuracy across clients where we let clients flexibly whether the global model is appealing after 5% of communication rounds of
join drop-out depending mandatory participation. We show that MAXFL achieves the highest GM-APPEAL than other basclines for both FMNIST and EMNIST by 0.32-0.39 and 0.23-0.31 improvement, respectively. Since MAXFL is able to retain a larger pool clients due to having a higher GM-APPEAL, it therefore trains from selecting from a more larger client pool, leading to the highest average test accuracy compared to the baselines by 22-40% and 18-50% improvement respectively for the seen and unscen clients. Since the other baselines do not consider the notion of GM-APPEA entirely, it fails in preventing client dropouts leading to poor performance. Note
10

---

Published in Transactions on Machine Learning Research (03/2024)
that we do not use any of the 'unseen clients' during training and only calculate the GM-APPEAL and test accuracy via inference with the global model trained with the 'seen clients'.
Prederred-model Test Accuracy: Clients' Perspective. Recall that a high preferred- model test accuracy implics that the client has a higher chance of satisfying its requirement by choosing between the global or solo-trained lo- cal model, whichever performs better. In Fig. 4 we show that as the GM-APPEAL increases across the communication round, preferred- model test accuracy also increases. MAXFL achieves the highest final GM-APPEAL and preferred-model test accuracy indicating that it provides a win-win case for both the server and clients, since the clients have the highest, accuracy by choosing the better model between the global model w and the local model Wk; and the server has the highest fraction of participating clients. Similarly, in Table 2 MAXFL achieves the highest GM-A PPEALL and preferred-model Lest accuracy. Although the preferred-model test accuracy improvement compared to the other baselines may appear small, showing that MAXFL is able to maintain a high preferred-mose test accuracy while also achieving a high GM-APPEAL implics that it does not sabotage the benefit of clients while also bringing the server more clients to select from.
GM-APPEAL
Preferred-Modde Test Acc.
FMNIST Sent140
FMNIST
14 57.05(=144)
FedAvg 0.08 (.37(= 98 53(40.13)
FedProx 0.07(#a.01) (.37 98, (8.42())
57.07(=1.42)
Scaffold 0.02 01) 0.03 05) 98 08.26(10.20) 51.59(
04) 0.17(=0.03) 98.32(110.15)
55.57(=1.28)
MAXFT 0.55(=0.0) 0.43 98 (8.83))0.06)) 57.16(21.35)
Table 2: GM-APPEAL and preferred-model test accuracy of the final global models for the unseen clients. MAXFL improves the GM-APPEAL by at least 47% for FMNIST, and 6% for 140 and achieves the same or higher preferred- model test accuracy.
Local Tuning for Personalization. Per- sonalized FL methods can be used to fine-tune the global model at cach client before compar- ing it with the client's locally trained model. MAXFL can be combined with these methods by simply allowing clients to perform some fine- tuning iterations before computing the aggre- gation weights in Step 7 of Algorithm [ Both for clients that are active during training and unseen test clients, we show in Table 3 that MAXFL increases the GM- APPEAL by at least 10% compared to all baselinos. For FMNIST and Semt140, the improvement in GM-APPEAL over other methods is up to 27%, 28% respec- tively for active clients and 17%, 4% respec- tivoly for unseen clients.
Seen Clients
Unseen Clients
FMNIST
Sent140 FMNIST
Sent140
Fed 0.38(20.06) 0.25 09) 0.39(20.06) 0.42(220.05
0.26(10.09) (=0007) (.43 FedProx 0.40(=0.07)
Scaffold 0.02(=0.02) 0.16 0.03 0.07(:0.01)
PerFedAvg 0.45(=0.05) 0.24( 10) 0.46;=0.06) 0.47
--
MW-Fed 0.28(=0.07) 0.08(=0.01) (.39 (.20
MAXFL (.55 0::66::00.000.5666:00000000
Table 3: GM-APPEAL of locally-tuned models with 5 local steps from the final global models for seen clients and unseen clients. Both for clients that are active during training and unseen test clients, MAXFL increases the fraction of clients that find the global model appealing by at least 10% compared to all baselines.
6 Limitations and Concluding Remarks
In this work we explore the notion of global model appeal by proposing to train a global model that maximizes the number of clicnts whose local requirements are satisfied. We show that when participating clients drop out or clients do not join due to a low global model appeal, the test accuracy for the current clients and generalization performance to the new unseen clients can suffer significantly. Through extensive experiments as well as theoretical insights and guarantees, we show that MAXFL can help to retain clients for training and thus achieve high average test accuracy across both participating clients and new incoming clients.
We note that our proposed metric GM- and MAXFL objective have some limitations. For instance, it is possible to train global model that sacrifices the performance of few clients to maximize GM-APPEAL, potentially reducing fairness. However, we expect that MAXFL could potentially be altered by modulating the Pk value to cover such limitations such as setting Pk to constant that retains fairness. Another limitation
11

---

Published in Transactions on Machine Learning Research (03/2024)
in MAXFL is that it does not currently consider specific incentive mechanisms for various settings such what cost we can set for the new incoming clients that wants to use the global model at inference without participating in training. Without setting this cost, one may raise the concern of free-rider problems. Neverthcless, our work presents a first step towards maximizing the set of clients that are interested in the global model; how design the cost of using global model would be an interesting, orthogonal direction of future work. As similar notion of global model appeal has not been thoroughly examined previously, we hope our work can open up new research directions in understanding the role played by the server prevent. client dropout and recruit new clients by finding a global model that serves many clients possible.
Broader Impact Statement
Our work proposes a new objective to maximize global model appeal in federated learning, which can incentivize more clients to participate and prevent clients from dropping out, and improve generalization performance unseen clients. Despite these benefits, it is worth acknowledging the potential negative effects of the proposed objective and algorithm in terms of other metrics, such as unfairness (e.g.. increased performance gap) between different sub-populations. Here, we note that (1) Our MAXFL framework is general in the sense that it could be adjusted to trade off fairness caannnss//tllyy /uiliity by setting the local requirement parameters Ps appropriately for specific sub-populations, arriving at a fairer model that reduces the number of clients suffering from inferior performance; and (2) Our results demonstrate that MAXFL is in fact more robust to specific Byzantine clients that adversarially send high GM-APPEAL. gap than competitors due to its dynamic reweighting scheme (see Table 4h. In general, however, it remains critical to carefully consider trade-offs between issues such as model appeal, fairness, and robustness for the application at hand. The goal of this work is to explore the implications of MAXFL both theoretically and empirically so that we can understand various benefits and limitations of GM-APPEAL in different sconarios. We hope practitioners and researchers can thus appropriately adjust the framework and/or combine it with other learning schemes depending on the application of interest, weighing potential benefits of the approach relative existing methods in terms of achieving higher accuracy, broader participation, and increased fairness or robustness.
12

---

Published in Transactions on Machine Learning Research (03/2024)
References
1. Bistritz, A. J. Mann, and N. Bambos. Distributed distillation for on-device learning. In Advances in Neural Information Processing Systems, 2020.
Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. In International Conference on Machine Learning, 2021.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. EMNIST: an extension of MNIST to handwritten letters. arXiv preprint 1rXii:1702.0539 2017.
Canh T. Dinh, Nguten H. Tran, and Tuan Dung Nguyen. Personalized federated learning with morean envelopes. In Advances in Neural Information Processing Systems, 2020.
Kate Donahue and Jon Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. In The Fiith AAAI Conference on Artificial Intelligence (AAA1-21), 2021a.
Kate Donahue and Jon Kleinberg. Optimality and stability in federated learning: A game-theoretic approach. In Advances in Newral Information Processing Systems, 2021b.
Florian F. Dorner, Nikola Konstantinov, Georgi Pashaliev, and Martin Vechev. Incentiviving honesty among competitors in collaborative learning and optimization. In Advonces in Neurol Information Processing Systems, volume 36, pp. 7659 7696, 2023.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. In Advances in Neural Information Processing Systems, 2020.
Alec Go, Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervision. CS224N Project Report, Stanford, 2009. URL luttps://www- cs. wt..sssoorr.doooo/o wtt.staaffr....ceeppppeeeeeeeeee httpp/ppppp//aaalcg///appssee TrL.tenDissarttSpprriiisooooppp
Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning in the presence of
arbitrary device unavailability. Advances in Neural Information Processing Systems, 34:12052 12064, 2021.
Jingoo Han, Ahmad Faraz Khan, Syed Zawad, Ali Anwar, Nathalie Baracaldo Angel, Yi Zhou, Feng Yan, and Ali R. Butt. Tokenized incentive for federated learning. In Proceedings of the Federated Learning Workshop at the Association for the Advancement of Artificial Intelligence (AAAI) Conference, 2022.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Malti Picus, Stephan Hoyer, Marten Н. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Garard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825) September 2020. doi: 10.1038/ 0411586-02002-49--4 URL htttps://doi..ooo 1038/ 841586-020- 2649-
Tzu- Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. In International Workshop on Federated Learning for User Privacy and Dala Confidentialily in Conjunction with NewrIPS 2019 (PL-NeurIPS'19)) December 2019.
Shengyuan Hu, Dung Daniel Ngo, Shuran Zheng, Virginia Smith, and Zhiwei Steven Wu. Federated learning network elfects game. ArXiv, February 2023. URL httpps///arxv.oorr//////22..... 08533
Baihe Huang, Sai Praneeth Karimireddy, and Michael I. Jordan. Evaluating and incentivizing diverse data contributions in collaborative learning, 2023.
Divyansh Jhunjhunwala, Pranay Sharma, Aushim Nagarkatti, and Gauri Joshi. Fedvarp: Tackling the variance due to partial client participation in federated learning. arvi 2022.
13

---

Published in Transactions on Machine Learning Research (03/2024)
Yihan Jiang, Jakub Koneeny, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning. arXiv 1909.12488 12488, 2019.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adria Gascon, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecny, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrode Lepoint, Yang Liu, Prateck Mittal, Mchryar Mohri, Richard Nock, Ayfer Ozgur, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. arXiv preprint arXiv: 1912.04977 2019.
Jiawen Kang, Zehui Xiong, Dusit Niyalo, Han Yu, Bing-Chang Liang, and Dong In Kim. Incentive design for efficient federated learning in mobile networks: A contract theory approach. In 2019 IEEE VTS Asia Pacific Wireless Communications Symposium (APWCS), pp. 1-5, 2019. doi: 10.1099/VTS-AWWOS WwT.:/CSS..0..... 2019.8851649.
Sai Pranceth Karimiroddy, Satyen Kale, Mchryar Mohri, Sashank J Reddi, Scbastian U Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastie controlled averaging for on-device federated learning. arXiv preprint XrXit:1910.0633 2019.
Yúsaku Komatu. Elementary inequalities for mills' ratio. Reports of Statistical Application Research (Union of Japanese Scientific Engineers), 4:69 4:69-70, 70, 1955.
Tian Li, Maziar Sanjabi, and Virginia Smith. Fair resource allocation in federated learning. orXiv preprint MXX::1905.10499 2019.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In Proceedings of the 38th International Conference on Machine Learning, 2021.
URL httph: htapps:://axiv..../ wwtpexiiv.orgaaie wtgg/bbs///00/ 2tts//211..444 04221
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang, On the convergence of fedavg non-iid data. In International Conference on Learning Representations (ICLR), July 2020. URL
https://arxiv. https://arxaw.orr/bb//////
Hamed Masnadi-shirazi and Nuno Vasconcelos. On the design of loss functions for classification: theory, robustness to outliers, and savageboost. In Advances in Neural Information Processing Systems 2008.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agoura y Arcas. Communication- Efficient Learning of Deep Networks from Decentralized Data. International Conference on Artificial Intelligenece and Statistics (AISTATS), April 2017. URL http:: org/ abtp//22..11//e//// 05629
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent. language models. International Conference Learning Representations, 2018
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (cds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4615 4625, Long Beach, California, USA, 09 15 Jun 2019. PMLR.
Tan T. Nguyen and Scott Sanner. Algorithms for direct 0-1 loss optimization in binary classification. In Proceedings of the 30th International Conference on Machine Learning, volume 28, 2013.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word repre- sentation. In Empirical Methods in Natural Language Processing (EMNLP), pp. 1542-1543, 2014. URL acwweb. http://www.ccleeb..or///aaoooa//
14

---

Published in Transactions on Machine Learning Research (03/2024)
Erlend S. Riis, Matthias J. Ehrhardt, G. R. W. Quispel, and Carola-Bibiane Bibiane Schönlieb. A geometric integration approach to nonsmooth, nonconvex optimisation. Foundations of Compulalional Mathemalics, 2021.
Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. Federated optimization for heterogeneous networks. In Proceedings of the 3rd MLSys Conference, January 2020.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, 2009.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. In Advances in Neural Information Processing Systems, pp. 4424 4434. 2017. URL http: htttt://papers...t .nips -oapee//000-eeeeeratee-mtiii
learning. pdf
Sebastian U Stich. Local SGD converges fast and communicates little. In International Conference Learning Represenlations (ICLR), 2019.
Pauli Virtanen, Ralf Gommers, Travis Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261-272, 2020.
Heqiang Wang and Jie Xu. Friends to help: Saving federated learning from client dropout. ar preprint arXiv:2205. 13222, 2022.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the Objective Inconsistty Problem in Heterogeneous Federated Optimization. preprinl, May 2020. URL https::/arxxiv.org//
2707.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprint arXiv:2107.063 06911,, 2021.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking aug 2017.
machine learning algorithms. https://orrtt.rr//////////0....
Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging federated learning by local adaptation. arXiv preprint Xix:20002.. 04758, 2020.
Meng Zhang, Ermin Wei, and Randall Berry. Faithful edge federated learning: Scalability and privacy. IEEE Journal on Selected Areas in Communications, 39(12):3790 3804,, 2021. doi: 10.110//5AA.222233111222
15

---

Published in Transactions on Machine Learning Research (03/2024)
A Further Results and Details for Our Motivating Toy Example
F((W) F2(w)
Fi(w)
Fi (w)
F2(w)
F2(w))
Fy(w)
Fs(w)
Fz(w)
F(w)
F(w)
F(w)
-5
5
0
10
20
10
w
w (c)
(a)
(b)
Figure 5: Results for the three client mean estimation; (a): case 1 when the true mean across clients are close amongst each other where MAXFL's optimal solution identical to that of FodAvg: (b): case when the true mean across clients are all different from each other where MAXFL's optimal solution ensures that least one of the clients will be satisfied with MAXFL's global model (unlike Fed:v (c) case when two clients' true means are close to each other while the other client has different mean. MAXFL in this case, is able to ensure that the two clients satisfied while FedAvg is not able to make any client satisfied.
Mean Estimation with 3 Clients with MaxFL. We further examine the property of MAXFL to satisfy clients with 3 clients toy example which is an extension from what we have shown for 2 clients. Reusing the notation from the 2 client example, where 0; is the true mean at client i and 0, ~ (V,, is the empirical mean of a client, our analysis can be divided into the following cases for the client example (also depicted in Fig. 5):
Case 1: 0 = 02 R 0g: This case captures the setting where the data at the clients is almost i.idd In this case, it makes sense for clients to collaborate together and therefore MAXFL's optimal solution will be the average of local empirical means (same as FedAvg).
Case 2: 01 + 0g # 0y: This case captures the setting where the data at clients is completely disparate. In this case, none of the clients benefit from collaborating and therefore MAXFL's optimal solution will be the local model of one of the clients. This ensures at least one of the clients will still be satisfied with the MAXFL global model unlike FedAvg.
Case 3: 0, 02 # 0g: The most interesting case happens when data at two of the clients is similar but the data at the third client is different. Without loss of generality assume that data at clients and 2 is similar and client 3 is different. In this case, although client and 2 benefit from federating, FedAvg is unable to leverage that due to the heterogeneity at client 3. MAXFL, on the other hand, will set the optimal solution to be the average of the local models of just client 1 and client 2. This ensures clients and 2 are satisfied with the global model, thus maximizing the GM-APPEAL.
Simulation Details for Fig. 2 For the mean estimation simulation for Fig. aaa,, we set the true means for the two clients as 0, = 0, 02 = 2Ya where Ta E [0, 20). The simulation was perfomed using NumPy (arris et al. 2020) and SciPy (Virtanen et al. 2020). The empirical means 0 and 02 sampled from the distribution (0,, 1) and (02, 1) respectively where the number of samples are assumed to be identical for simplicity. For local training we assume clients set their local models as their local empirical means which is analogous to clients performing a large number of local SGD steps to obtain the local minima of their empirical loss. For the global objective (standard FI,, MAXFL (RcLU), MAXFL) a local minima found using the scipy. ccipy.optiine optimize function in the SciPy package. For each r8 E [0, v20), the average GM-Appeal is caleulated over 10000 runs for each global objective.
16

---

Published in Transactions on Machine Learning Research (03/2024)
B Proof for Theoretical Analysis in Section 2.2
We additionally define the following quantities
1²
(0
01 2
70
(6)
N
Note that the distribution of the empirical means itself follows normal distribution following the linear additivity of independent normal random variables.
0. ~ ~((1,))) ~2(2,
(- 12
Lemma A.1 The expected GM- of the standard FL model is upper bounded by 2 exp the expectation is taken over the randomness in the local datasets B2
where
Proof.
0. and therefore the expected GM-Appeal is, The standard FL model is given by,
[(w 01)2
(01 01)) + +[[( 02) < (02 02)
E
(8)
2
P
(w 01)3 (01 01)²)
+ IP (Iw -2) (02 02)²
(9)
Ti
Next we bound Ti and T2.
Ti = P
(w - 02) < (0, -11)2)
(10)
2
0 + 02
= P
01
< (0) 01)2
(11)
2
02
2
02 0
+
(0) 01) <0 <0)
(12)
2
2
2
02
01
+ 2
02 0
(0) 01) <
n { 02 01}
2
2
2
P
02 0
+2
02 01
(0 01) <0 =0
n 200ntt8
s {b1}
(13)
2
02 01
0(00 8.1
IP
20
0
7
02 0
2
0z 0
)
0z s 61)
P
+2 2
(0r 01)
0
(14)
17

---

Published in Transactions on Machine Learning Research (03/2024)
82 01
S P
+2 01) -0)=== + +P(00
(02 01 50)
(15)
2
where 21 N (To.gT² 72 ~ N (27G,
5
P (Z
0)
(22 50
(16)
18
1 ?2
exp
+ +exp
(17)
572
< 2exp
(18)
572
where 113 uses P (AA = PAAnB) + P [An Bº).
15
uses ( & P(A), (16 uses
7 and lincar
additivity of independent normal random variables,
uses a Chernoff bound.
(-29 (-
We can similarly bound T2 to get T2 5 2xp model upper bounded by exp
Thus the expected GM-Appeal of the standard FL 5422
12
5-
Lemma A.2 Let h be any function that is conver, twice differentiable, and strictly increasing in [O, oc).
Then relaxed objective is strictly conver and has unique minimizer at wt 0: +02 Proof.
Let us denote our relaxed objective by v(w). Then v(w) can be written as,
1 [h (Fi(w) F()))) h (F2(w) F( 1 h ((w - 8112) + 2 ((w 01)² v(w) =
(19)
2
vi(w
22(w)
(20)
We first prove that U1 (w) is strictly convex. Let A E (0, 1) and (w) be any pair of points in R² such that w1 * W2. We have,
"1 (Aw1 + (1- A)we))
(A(w) - 0,) + -))(w3 0,))²)
(21)
2
-0)2 2 h (X(w) - 2 + (1 --)(w2 - -1132)
1
(22)
X
- >, (ww2 0,)2) (ww) 0.13)) +
(23)
2
2
Ao (wi) + (1 - X-u (w2)
(24)
follows from the strict convexity of f (w) = u² and the fact that h(w) is strictly increasing in the range 00, oc), 23 follows from the convexity of h(w).
where (22
This completes the proof that (w) is strictly convex. We similarly prove that un (w) is stricly convex and hence uww) is strictly convex since summation of strictly convex functions is strictly convex.
Also note that,
Vo(w) Vh ((w - 01)2) (w- (w + vh ( (w 02)
(25)
It is easy to see that Vo(w) at w will be a unique global minimizer. This completes the proof.
0 Since v(w) is strictly convex this implies that w
2
18

---

Published in Transactions on Machine Learning Research (03/2024)
Proof of Theorem A.1
Before stating the proof of Theorem A.1 we first state some intermediate results that will be used in the proof.
The MAXFL objective can be written as,
1 20 (ww 82)2) v(w) 2 (lw-01y +
1
(26)
where a(w) = 1/(1 + exp(-w)).
We additionally define the following quantities,
== argmin (0i.03] j j: argmax 02: 3a 0 0:
(27)
Let q(w) = (1 - (w)). The gradient of v(w) is given as,
Vo(w) (ww- ()))) (wr 01) + a ((w- (w0-02)²) (w 02)
02)3)
(28)
Lemma A.3 For 9a > 2, w
will be local mazima of the MAXFL objective.
will always be stationary point of Vu(w). Our goal is to determine whether it will be local minima local maxima. To do so, calculate the hessian of v(w) follows. Let f(w) (wv) - (w))(( - (w)). Then,
It is easy to that +02 2
v'u(w)= = f (ww- - 8.)))(())))) (w 0.) + ((w (ww-81()) -1))) + ((w ((w-02)²) (w 02) + (ww - -2))²
(29)
(ww)
(w(
Note that h2 (w) = (w) for w = (0++02)
Hence it suffices to focus on the condition for which hı h1(w) < 0
at w 8: 8.+02) ). We have,
(01 f(22)n + (62)
(30)
(2(1 - 20(72) + 1)
(31)
for 9o 1.022
(32)
where the last inequality follows from the fact that ((w) > 0 for all E R and 2(1 - 20 + 0 for w 2 1.022. Thus for Ro > 2, w
(0++0, will be local maxima of the MAXFL objective.
Lemma A.4 For 9a > 0, any local minima of v(w) lies in the range -20
Firstly note that since 9a > 0 we have 0, > 0, Secondly note that since (ww) > 0 for all w E R, Vo(w) < 0
for all 0 and Vr(w) > 0 for all 0,. Therefore any root of the function Ve(w) must lie in the range (0,, Q)).
Case 1: 0 < 56 2 2.
19

---

Published in Transactions on Machine Learning Research (03/2024)
In this case, the lemma is trivially satisified since (0, c
-20,]]
Case 2: 90 > 2.
-0--; 8g and g(z) = g(x))x. We can write Ve(w) as, Vu(O; + 2) - g(x) - g(26cc - z). It can be seen that for x > 2, g(x) is a decreasing function. For x E (G) we have x > 29G - x which implies g(x) > g22gg- - x). Therefore Vu(0, + +) > 0 for E (2, 9c). Also Vo(0, + 2na -x) -VvvO + x) and therefore Vu(0, x) < for z E 25g.25c 2). Vo(0, + Ro) but this will be a local maxima for 9G 2 as shown in Lemma A.3. Thus there exists no local minima of v(w) for w E (0, + 2. 2)
Let 2 = ----- w-
Combining both cases we see that any local minima of v(w) lies in the range { (0. 0. + 2 2 - 2, 200,)
Theorem A.1 Let w be a local minima of the MAXFT. objective. The expected GM-Appeal using w is lower
bounded by 16
1 exp (- where the expectation is over the randomness in the local dataset B,, B2.
Proof.
The GM-Appeal can be written as,
1 P (w- <0) 01)3) P ((w 0,) (0, 1 2
(33)
We focus on the case where 02 * 0, implying 0, 0, (02 0 is a zero-probability event and does not affect our proof). Let w be any local minima of the MAXFL objective. From Lemma A.4 we know that will lic in the range (0,, 02 2| u (0, 2,0,)
Case 1: w E (0,, 0g + 22]
P (w 0.)2 < (0: -0)3)
= PP (w 0.)2 + 2(w 0.) - 0.) < <0)
(34)
P
(w - 0.) + +2 - 0.) <0)
(35)
(2-2 - 0.) < 0)
2 P
(36)
= P (0.-0) <-1
(37)
2 P ((0 < {b n { {00- - 01)) < -1])
(38)
P
0 0,2
P 00 -0-04 <
110 < <0,)
(39)
2
P
0
< 022
P (0, 8 < <11
(40)
P
00
< 0z)
(Z > 1/7) where ~ NO,
(41)
1
1
8
exp
(42)
35
uses the fact that (w - 0.) > 0, 366 uses (w 0.) < 2,
38
uses P (AA) 2 (AA B) and definition
of i. 40 uses the following argument. If 01 1 2 0g then P
01 01 < 1101 < <8²) 1. If fg < 0g
then 0, 01 < -100 < 02) P 00 01 -1) /IP 0 < 02)
00, - 01 < <-1). 41 uses 0, 01
P
N(O,, 22), 42 uses IP (0, 0,) 2 1/2 and (Z 2 x) N
2exp( /2)
> 1 expp(2z) where Z NO
/2
Komatu 1955
20

---

Published in Transactions on Machine Learning Research (03/2024)
In the case where w E (0) 2, 0,] a similar technique can be used to lower bound (ww 0,) < <0,--00 01)3)
Thus the GM-Appeal of any local minima of the MAXFL objective lower bounded by 16 exp (- 42
C Convergence Proof
C.1 Preliminaries
First, we introduce the key lemmas used for the convergence analysis.
Lemma C.1 (Bounded Dissimilarity for F(w)). With Assumption 9.1 and Assumption 3.3 we have the bounded dissimslarily with respect to F(w) us:
M
1
D R²a
(43)
M
where = x22 = 4. x²
Proof. One can casily show that
M
M VV <
M
vP(()))
Σ
M Σ [V](()]]
(44)
M
M
due to (:(w)= S 1. Hence we have from Assumption 3.3 and Cauchy-Schwarz inequality that
VF;(w)]1
(45)
(w)ll
(46)
S (
(47)
We bound the first term in
47 as
M
qi(w))
FV((w)
V2(w)
VF((w)
(48)
M
1
[1(1
V F: VF (w)
(49)
M
M
2
[FF(w))
S 2T
(50)
M
where in 50 we use q: (w) < 1, Vi E [M] and Assumption
3.1
Then from 47
we have
25 23
n²2 +
(51)
M
completing the proof.
Lemma C.2 (Smoothness of F(w)). If Assumption 3.1 is satisfied we have that the local objectives, (i(w, ... (w),)) are also smoothott for any where T.g 1.2/4 q:(w) Toy.
21

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. Recall the definitions of F(w) below:
F(w)= 1 M Σ F.w),, (F
(52)
Let lllp denote the spectral norm of matrix. Accordingly, with the model parameter vector w Rd we have the spectral norm of the Hessian of F:(w), Vi E [M] as:
(w))lo llop
(53)
(VV
(())) V2 (W](wll
where q:(w) = (F( - F. (w;)) and VF((w) E _dx1 is the gradient vector for the local objective (i()) and (2):(w) E Raxd is the Hessian of (w). We can bound the RHS of (53) as follows
| olopp = (11:((w)
d: (FV F(
(54)
1lop
(55)
(w) - (o
llop
(56)
= (w) (w) 1
(57)
L2 L
+
(58)
4
where we use triangle inequality in 55 and use ||xy llp
| |yll in
57
and use q. (w) S 1 along with
La Assumption 3.1 in 58 Since the norm of the Hessian of (.(w) is bounded by 4 + (w() we complete the proof.
C.2 Proof of Theorem 3.1 Full Client Participation
Theorem C.1 Convergence to the MAXFL Objective F(w) for Full Client Participation). Under As- suppose all M clients participate for each communication round of Algorithm 1 With MM, for total communication rounds T of the MAXFLL solver in Algorithm 1 we have:
sumplion 3.1 3.3,
17
VT- fg
(4L, + L.) (F(W(O.0)) Pmn) + 64 (4L, + La)
min E [
LNVTMT
L.T
(59)
ALL + La)
oLL,OG + L./4)²
TTLe
VTMr
For ease of writing, we define the following auxiliary variables for any client i i [M]:
Weighted Stochastic Gradient: h,"h (t.0) == q:(w(()))
Σ g(w
(tar) (((r))).
(60)
r=0
Weighted Gradient: h (1,0)
q: (w(()))
V FF (fr))
(61)
Normalized Global Learning Rate: v (l.0) /g/
Σ Em(w((0)) +e
(62)
where is constant added to the denominator to prevent the denominator from being O. From Algorithm
with full client participation, our proposed algorithm has the following effective update rule for the global
model at the server:
M
w (1+1,0) = (1.0) -1g
(1.0)
m
k
(t.0)
(63)
22

---

Published in Transactions on Machine Learning Research (03/2024)
With the update rule in 63 defining 7/t.0)) "1
(1.0) THT M and using Lemma C.2
we have
M
E [(w((+100))]
F(w(t.0))
- 1
(l(w
h
(t,0)
MT
(64)
Lg (7
(0,0)
E
h
2
MT
= -
M
M
MT Σ
h
(t,0)
h
(1.00)
7
(F(w
(1.0)
h;
(1,0)
MT
1=1
(65)
M
(t,0)
E
2
MT
17(--0)
(w(((t)))) /²
M
hg
(t.0)
+
17(5.0)
E
M
h
(1.0)
MT
2
MT
(66)
(7 22222
E
Σ
h
(t,0)
For the last term in 666 we can bound it
E
Σ h
(c.0)
I. (7
Σ
h
(1.00) h 11
Lg (7
E
Σ h
M
(2.0)
(67)
2M272
2
2272
(7
L. (7(4.,00)3 E
2 E
a:(
Σ
(g(w! (trr)
<((err) V (w ((r)
Σ
h;
(t.0)
M272
M272
(68)
(7 M
Σ
q: (W((110))
Σ
T-1
E
[g((w (l((((t))
(trr) e(((.r) (A:1)--AALL V.((((()))) ((-r))
27
L. (7(
Σ
M
h
(1.0)
27
(69)
M
M2
==1
I. M
q: (w.00))) 70 + 1.(771.00)3
M
27
M272 Σ
E
Σ
h
(1,0)
(70)
M2y2
1.(7710011802 MT + (77000)))
M MT
1
(1.0)
(71)
where 67 is due to the Cauchy-Schwarte inequality and
70 is due to Assumption 3.2 and
71
is due
(w()) I. e [M]. Merging (11 into
66 we have
77 7)t1,0)
(7,)
EE [(w((+100)]] F(w(t.0) <
v (F((((r0)
E
VF(
(1.0)
MT
(72)
L. 17((
77(0.0)
h (t.0)
F
MT
2
Mr
23

---

Published in Transactions on Machine Learning Research (03/2024)
Now we aim bounding the second term in the RHS of
72 as follows:
(
M
27
E
V F( ( ((.0)
h
(1.0)
(73)
2
MT
1=1
M
M
E
qe ((wlt.0))
FFj(w((.)) FF
V
Σ 2i (i (1.)
V.F(WW (1:7)
(74)
2
M
MT
77(--0)
M
E
2: (:( (10)
V (P(( -F
(75)
2
MT
$
17(4.0)
M
li( (w(w(.00)
(2.0))
Σ
[F(( V.i(W: (1:7) |1"
(76)
2M
1=
1277000)
M
w - 1 11
Σ
9i (w((1.0)))
R
(77)
2M
where 76 is due to Jensen's 's inequality and (7 is due to Lemma
C.2
We can bound the difference of the
global model and local model for any client E M] as follows:
E
w (1.0)
w.! 1
Tf
Σ g(w: (1.))
(78)
-5 <((()) VF((w! 17
Σ g w (1.1)
+2nfBB
(79)
$ 2m 02 + 2
(W
(80)
where 79
is due to Cauchy-Schward inequality and 80 is due to Assumption
3.2
We bound the last term
in 80
as follows:
V (W (1
Sr >EEB
E
VFF(W
ST
Σ
E
V (
(81)
1=0
< 2r
Σ
1-1
(VF((W(tl))
27
V VFF(WW ( c.0) |19
(82)
1=0
< 2
E w (t.))
[P]
2T
(83)
where 88 is due to Jensen's inequality, and (82 is due to Cauchy-Schwarz inequality, and 83 is due to Combining
Lemma C.2
with (80) we have that
((.0 (t.r)
2nf + 4L3mL+ T
Σ E [(1)) w [(
4n ?
VE (Wtis
(84)
Reorganizing 84 and (aking the summation
E [r] on both sides we have,
(1 -
E
w((.00 -oft0)l w
< 2m o
2
Σ + 14 33
V VF (c.0)) VFi(m(c.0)
(85)
np 00
4n 33
VFF (w/c
(86)
24

---

Published in Transactions on Machine Learning Research (03/2024)
With m 1/)2222 we have that 1/(1 - =2) S 2 and hence can further bound (86 as
w. ((())) 27
E
S 2njo + 8n8
(87)
r=0
Finally, plugging in 87
to
77
we have
7)(000)
2 E
VF(w
MT Σ h
M
(.00)
(88)
L.7 M
Σ (w((oo))
2n og + sni
V
2MT
i=1
M
12 ri og + 2 (1.7 1
(F((w((0)))
E
(89)
M
2 oz + 2 (1,0) (8²
V F (w || n²?))
(90)
where
89
uses (w) S 1, Vi E [M] and
90 uses Lemma
C.1
Merging
90 to 72
we have
E P( (+t
(w
S 71c.0)
1 2 VF \F/()( t77(00 (Tith:011
E
h
(1,0)
(91)
2)
MT
L. (7 1/1100 L o3 + 17(( 7 2 V
WF(
+ 477tt.0)
mp L3,
Mr
With 71gg S 1/(47 I.g) we have that 7/c,.0) T. - - S -144 and thus can further simplify
91 to
E P(w(tt1100)] - F(w(1.0) 5
7)1000)
v (tt ||
1 4,,1000 2 8
V (F(
(92)
I, (7(000))) Po
+ 7 Linio'z + 47 (1,00 n² L3
Mr I. (7i00)
= -711000 (Ani
1 WF(m
+ -,..00 13 + 47 1.00 " 1
(93)
Mr
With local learning rate m S min(11(4TLo)) 1/(4 ( we have that
E F [(w((t110))] - F(w(t.0)) < g/t.00
V Wfo +
+ 1 (1t000 1317003
4
Mr
(94)
+47 (1.0) 2 7 13,
and we use the property of :jtt,0) that Mrmmn M+e
S ipt(.00 <
Mrnnng to get
E (( - F(w((h0)) <
M MTnhng
VF (w (1ot)/
||=
T. T.mninng
+
4(M +c)
22
(95)
M ng
c
Taking the average across all rounds on both sides of
95
get
Σ E [IVF(wii)))))
4(M + é)
F(w Fint)
L +
Mrnni T
(96)
4L +
AomLoo 2 (M +e)
22
25

---

Published in Transactions on Machine Learning Research (03/2024)
and prove
4(M + +&) (F(wl0.0)) - Fint)
1 T-1
Σ 1=
min E 1E121
E
T
Mrning
(97)
16n r L2 13 +c)
AL tc) +
of cc)
Further, using L, La Σke the (w)+ + 4 and in 97 to be
MLa 21.
from the optimal learning rate we have the bound
(4L, + LO) (f(wl0.0)) Fins) +
G4nR + Lc)
/F(
V VVF(W((t
min E eE
LOTMINTT
Le
(98)
4T
Iic)
B (T,
T.c/4)2
+
Le
ML3
By setting the global and local learning rate as f7 as
VTM and m VTa we can further optimize the bound
(4T, + Le) (F(w(0.0)) inn)
min E [l
12]
64L3,6 (AL. + Lc)
+
LoVTMr
L.T
(99)
oL + Le)
64L.0g(Lo + Lo/4)²
TThe
VTMT
completing the full client participation proof of Theorem
C.3 Proof of Theorem 3.1 Partial Client Participation
Thcorem C.2 (Convergence the MAXFL Objective F(w) for Partial Client Participation). Under
A Assumplion 3.3.
3.3. suppose m clients are selected by the server uniformly al random without replacement oul VTm,
of M total clients for participation for each commanication round of Algorithm 1 With m /T7' Bg
for total communication rounds T of the MAXFL solver in Algorithm
we have:
4 (F(w(0.0)) - -Fan)) 402
40
80
min E E
(1.)
VTTm
VT
3TT
(100)
80L2
48v M - -m)
T
VTm
We present the convergence guarantees of MAXFT, for partical client participation in this section. With partical client participation, we have the update rule in
63) changed to
w (t+1,0) (1.0)
(t.0)
(t.0) m
Σ
h
(101)
KES(A)))
where the m clients are sampled uniformly at random without replacement for S(t,0) at each communication
round t by the server and 1ig (t.0)
-milg/ (Eresi.o; Iee (w(((t)))) + + for positive constant Then with the
update rule in 101 and Lemma C.2 defining ()(,,)) nh
(2.0)
mmm we have
E
F(w(++20))]
F(w((10)) $
E (1)00
(F(w(..)))
h
(t.0)
mT
rESt..0)
(102)
L, (7t1.003
(c,00
+E
h
TITT
iESU1.)
26

---

Published in Transactions on Machine Learning Research (03/2024)
For the first term in the RHS of (102) we have that due to the uniform sampling of clients (see Lemma in Jhunjhunwala et al. (202)) ) it becomes analogous to the derivation for full client participation. Hence, with
the property of arril < 77 (7.0) < mrnal and using the previous bounds in 900 we result in the final bound
for the first term in the RHS of 102 as below:
)
E - t/1.0))
VF(w(((1))
Σ
h
(((00)
4n A 12 Agm
[w((00))))
|
TIT
(ES(..0)
m. +
6 A mi mmgg R
(103)
For the second term in the RHS of 1022. with C = [mmmnngg///) we have the following:
L (7
E
h (t,0)
S CE
(h (t.0)
h
(1.0)
2
MT
M1T
(ES(C,))
(ES(
(104)
(1.0)
+CE
MT
iESt..)
C'
h
(1.0) (1.0) 2
h;
CE
1
Σ
h
(4.0)
(105)
2
MIT
SES
C
E
h;
(t.0)
5.
(1,0) 27
+ CEE
1
Σ
h
(t.0)
(106)
2
2
1=1
(ES(t.0)
Co + CE
Σ
h
(1.0)
(107)
(ES(..))
where 106 follows due to, again, the uniform sampling of clients and the rest follows identical steps for full client participation in the derivation for 67 Note that
L
M (w))) + (mrring/e)2 S (L, + In (mmrnngee
Le
C
(108)
M
4
kml
For the second term in
107
we have that
E
h;
(t.0)
= E
h
(1,00
vi((w((.))) + VF. V.:(w(()))))
VES(1.))
(ESU..)
(109)
VF(w((.0)) + +1 VF((((0)))
27
< 3E
h
(t.0)
VF (w((())))
+ B
1 Σ FF(((((.)) v (F(
MTT
m
(ES(..))
ie
(110)
A
Aa
V F (w
+ 3E
27

---

Published in Transactions on Machine Learning Research (03/2024)
First bound A in 110 as follows:
[
3E
1
h
(t.0)
VF. FF:(w (10)))
31
Σ gi (w((L))))
(F:(w
Vli(w(())))
VITT
MIT
VES(1.))
iESiC.0)
M
3
E
Σ
VF((w!")) - VF((w(t.)))
3
ΣΣ
E
(F(((("))
( (00) [|]
mT
MT
iEStt,,0 r=o
=1
(111)
3
M
--1
w((.0) w! (
E
(112)
MT
where 111
is due to Jensen's inequality, (:()) S 1, and uniform sampling of clients, and 112 is due to 72 we have already derived, bound (112) further to:
Assumption
3.1
Using
2R
M E
3E
h (1)00
V F/
(((((())))))
S 66..210
(113)
mt
M
:E.S...0)
S 61,3120
+AI. 7
(2.00 + x!2)
(114)
where 114 due to Lemma
Next bound A2 follows:
3
E
Σ
VF((w(t.))) v FF((1.0))
-2
m
VES(L.)
(115)
3(M ml
Σ
V (W(((0)))) (F(w(.0)))
(M - 1)
3(M - m))
Σ
V (i(
9: (:w0((.))) FF((w((.0)) M
1
(116)
72mM (M 1)
1=1
6(M - m))
Σ
q: (((w Σ VFF((w(t.0)
(117)
MM 1)
M
12(M - m2
(118)
-2m(M-1
where 115 is due to the variance under uniform sampling without replacement (see Lemma 4 in Jhunjhuwaaa
et al. 2022 and 117 is due the Cauchy-Schwan inequality and (118) due to Assumption 3.1
Mering the bounds for A and A2 to 110 we have that
E
h (.0)
2
MT
VES(t.))
(119)
12(M m2
1 | F
+24L 2
3IE
72((M 1)
12(M m)
2
|VF(w((10))))
n r 4Tk'2)
(120)
mm 1)
28

---

Published in Transactions on Machine Learning Research (03/2024)
Then can plug in (200) back to 107 and plugging in 103
102
we can derive the bound in
102
F F(w((+100)]]
F(w(c.0))
m
4n no TT 2
o + + (TRTI))))))) (2 23 + 33 VF (w(to))))) + (TTMA)
(121)
m +
6
met
(LL 4TK²2) + 12(M - m) L2
72m(M - + m Li
+ (rmmng)>
where v = Los + Lo/4. With Vi S 11/48TTLs c= m, and T/ S Drw we can further bound above as
o Vv 7 VF (F((w(..))) (Fnmng²
- F((((100) [F((((+10))]
mit
(122)
+ 4TK²2) ) + 12(M m)L2
6LL3NTT0O + (
+ 4L3 m n + L23 F nin
m2 -
Taking the average across all rounds on both sides of 122 and rearranging the terms we get
(F(w(00.)) Fint)
Σ | (10)))1)]))
+ +407m1
11 m
213
3 + L3T
TIMoT
(123)
80L
72
48 m)
3
TM(M 1)
With the small enough learning rate mn = 1/(VTT) and ng = vT one can prove that
11 <
4 F(wl0.0)) Fiut)
+
40
20
80
min E
F
+
eE[T]
VTrm
VT
37T
(124)
80L
48v(M M- L2
T
vTm
n2
VT
O
+
O
+ 0
(125)
TTm
TT
T
Tmm
completing the proof for Theorem 3.1 for partial client participation.
Experiment Details and Additional Results
All experiments are conducted on clusters equipped with one NVIDIA TitanX GPU. The algorithms are implemented in PyTorrh 11. 0. All experiments are run with 3 different random seeds and the average performance with the standard deviation shown. The code used for all experiments is included in the supplementary material.
D.1 Experiment Details
For FMNIST, for the results in Fig. Table 2 and Table the data is partitioned into clusters where 2 labels are assigned for cach cluster with no labels overlapping across clusters. For the other FMNIST results and EMNIST, we use the Dirichlet distribution (Hsu et al. 2019) to partition the data with a 0.5, 0.05 respectively. Clients are randomly assigned to each cluster, and within each cluster, clients are homogeneously distributed with the assigned labels. For the Scnt140 dataset, clients are naturally partitioned with their twitter IDs. The data of each client is partitioned to 60% 40% for training and test data ratio unless mentioned otherwise.
29

---

Published in Transactions on Machine Learning Research (03/2024)
Seen Clients
FMNIST
EMNIST
Byz=0.1
Byz=0.05
Byz=0.1
By2=0.05
Test Acc.
GM-APPEAL Test Acc.
GM-APPEAL Test Acc. GM-APPEAL Test Acc. GM-APPEAL
MWdFee 17.24 (4:2355)
0.01 (#0.0) 21.28 (=1.79) 0.02 (#0.0) 15.83 (#1.52) 0.004 (#0.0) 22.22 (10.63) 0.008 (20.001)
MAXFL 69.42 (+2.87) 0.35 (#0.03) 70.60 (+2.78) 0.42 (*0.03) 52.74 (+0.44) 0.20 (+0.01) 56.10 (40.77) 0.23 (+0.01)
Unseen Clients
FMNIST
EMNIST
Byz=0.1
Byz=0.05
Byz=0.1
By2=0.05
Test Acc. GM-APPEAL Test Acc.
GM-APPEAL Test Acc. GM-APPEAL Test Acc. GM- APPAAPEAL
MW-Fed 18.45 (#2.81) 0.01 (#0.0)
21.91 (=3.81) 0.01 (=0.0) 17.03 (#0.21) 0.005 (#0.0) 22.23 (20.63) 0.003 (#0.0)
MAXFL, 69.75 (#3.66) 0.39 (+0.01) 71.11 (+1.47) 0.46 (=0.D1) 53.82 (#0.09) 0.26 (#0.02) 55.10 (+0.78) 0.28 (=0.01)
Table 4: Byzantine clients are included in the total clients where they artificially report large losses to the server and add noise to their gradients. The ratio of the Byzantine clients is denoted as 'Byz'. We report the final avg. test accuracy and GM-Appeal across the seen and unseen clients where we train for 200 communication rounds. At the 10th round, clients flexibly opt-out or opt-in depending on whether the global model has met their requirements.
Obtaining W, E [M] for MaxFL Results in Section 5 In MAXFL, we use Wi, E [M] to caleulate the aggregating weights (see Algorithm D For all experiments with MAXFL, we obtain W,, E [M] at each client by each client taking 100 local SGD steps on its local dataset with its own separate local model before
starting federated training. We use the same batch-size and learning rate used for the local training at clients done after we start the federated training (line 8-9 in Algorithm []. The specific values are mentioned in the next paragraph.
Local Training and Hyperparameters. For all experiments, we do a grid search over the required hyperparamcters to find the best performing ones. Specifically, we do a grid scarch over the learning rate: Til E (0.1, 0.05, 0.01, 0.005, 0.001}, batchsize: b E {32, 64, 128), and local iterations: T E {10, 30, 50} to find the uyper-parameters with the highest test accuracy for each benchmark. For all benchmarks we use the best hyper-parameter for each benchmark after doing grid search over feasible parameters referring to their source codes that are open-sourced. For fair comparison across all benchmarks we do not use any learning rate decay or momentum.
DNN Experiments. For FMNIST and EMNIST, we train deep multi-layer perceptron network with 2 hidden layers of units (64, with dropout after the first hidden layer where the input is the normalized flattened image and the outpul is consisted of 10 unils each of one of the 0-9 labels. For Sent140, we train a deep multi-layer perceptron network with 3 hidden layers of units [128, 86,30) with pre-trained 200D average-pooled GloVe embedding (Pennington et al. 2014). The input is the embedded 200D vector and the output is a binary classifier determining whether the tweet sentiment is positive or negative with labels 0 and respectively. All clients have at least 50 data samples. To demonst further heterogeneity across clients' data we perform label flipping to 30% of the clients that are uniformly sampled without replacement from the entire number of clients.
D.2 Additional Experimental Results
Robustness of MaxFL Against Byzantine Clients. One may think that MAXFL may be perceptible to specific attacks from Byzantine clients that intentionally send a greater GM-APPEAL gap to the server to gain a higher aggregation weight. To show MAXFL's robustness against such attacks we show in Table 4 the performance of MAXFL with Byzantine clients attacks which send higher losses to gain higher weights and then send Gaussian noise mixed gradients to the server. We compare with MW-Fed (Blum et al., (021) which aims for incentivizing client participation by clients sending higher weights to the server and performing
30

---

Published in Transactions on Machine Learning Research (03/2024)
2,50
12
2.25
2,00
1.0
1.50
0.8
Ed, fe(W)/A
1.25
Fe(w)/M
2e-1 Fk(w)MM
20
40
60
SO
100
0
50
100
150
Communication Rounds
Communication Rounds
(a) FMNIST
(b) Sent140
Figure 6: Comparison of the average of the true local losses across all clients (Ei,, fx(w)/M) and the empirical local
losses across all clients M (w)) where the former calculated on the test set and the latter is calculated on the training set for the global model w. We show that the average of the true local losses is nearly identical to the average empirical local loss across clients empirically validating our relaxation of replacing fs(w) with Fl (w).
GM-APPEAL
Preferred-Modee Test Acc.
50
100
7 150
71 50
7: 100
7i 150
FedAvg 0.01 (40.01))
0.01 (+0.0)
0.01 (+0.0)
98.56 (40.08)
98.72 (+1.022)
98.75 (+1.28)
FedProx 0.01 (10.0)
0.01 (10.0)
0.01 (10.01)
98.56 (11.115)
98. (4:1.08)
98. 75 (1:1.5)
MAXFL 0.55 (#0.0) 0.55 (+0.0)
0.55 (=U.D)
98.64 (+1.03) 98.77 (+1.01)
98.77 (+1.01)
Table 5: GM-APPEAL and preferred-model test accuracy for varying number of local steps to obtain Wa, E [M]
where = 200 is the total number of communication rounds for training the global model.
more local updates. In Table 4 we see that for both high and low byzantine client ratios, MAXFL achieves only 1-5% lower test accuracy for seen and unseen clients compared to the case where there are no Byzantine clients in Table 1 This is due to our objective giving lower weight to those clients that give a too high GM-APPRAL. gap (see Fig. 3p. Hence MAXFI, disregards these clients that send artificially high PPEAL. gaps. Note that it is indeed possible that attackers can devise different attacks, and in our work we consider one of them to show MAXFL's robustncss. Specifically, our focus is the case when some attackers try to modify their loss values in order to get higher weights for their updates.
Ablation Study on S&(W) Re F& (w). One of the two key relaxations we use for MAXFL (see Section 2.1 is that we replace fiwWw) - fa(WWx with F&(w)- Fx(W)). In other words, we replace the true loss fx (w) De=D,[l(w, {)] with the empirical loss F& (w) = B EeEs, f(w,E) for all clients & E [M]. We have used the likely conjecture that the global model w is trained on the data of all clients, making it unlikely to overfit. to the local data of any particular client, leading to fx (w) R Fs(w). We show in Fig, G that this is indeed the case. For all DNN experiments, we show that the average true local loss across all clients, iee, EM fo (w)M is nearly identical to the average empirical local loss across all clients, i.e, Σ F& (w)MM given the training of the global model w throughout the communication rounds. This empirically validates our relaxation of the true local losses to the empirical local losses.
A Ablation Study on the Number of Local Steps π. to train We. k E [M]. We conduct an additional ablation study where we vary the number of local steps to obtain Wx. & E [M] for clients as shown in Appendix D.2 Despile that a smaller number of local sleps can lead to underfitting and a larger number of local steps can lead to overfitting, we show that all methods' GM-Appeals do not vary much by the different number of local steps used for training.
Proferred-model Test Accuracy for the Local-Tuning Results in Table 3 In Table 3 we have shown how MAXFL can largely increase the GM-APPEAL compared to the other baselines even when jointly used with local-tuning. In Table 6 we show the corresponding preferred model test accuracies. We show that for the seen clients that were active during training. MAXFL achieves at least the same or higher preferred-mode test accuracy than the other methods for all the different datasets. Hence, the clients are able to also gain from MAXFL by achieving the highest accuracy in average with their preferred models (either
31

---

Published in Transactions on Machine Learning Research (03/2024)
Seen Clients
Unseen Clients
FMNIST
Sent140
FMNIST
Sent 140
FedAvg
99.37 (#0.24) 55.71 (40.46) 99.50 (#0.02) 58.79 (+0.67)
FedProx
99.35 (2.0233
55.75 (1:0.80)
99.55 55 (20.09)
58.82 (1:0.2)
PerFedAvg
99.20 (=0.25)
55.74
(#0.80)
98.98 (=0.55)
58.82 (#0072)
MW-Fee
99.27 (#00339)
55.06
(4:0.35)
99.47 (#0008)
57.36 (400711
MAXFL 99.40 (1:033) 55.82
(=00882
99.50 (=0.02) 58.88 (10.77)
Table 6: Preferred-modee test accuracy with the locally-tuned models with local steps from the final global model for seen clients' and unseen clients' test data (the corresponding GM-Appeal is in Table 3
GM-APPEAL
Preferred- Test Acc.
FMNIST
Sent140
FMNIST
S4nt140
F-F.L. (g- = 1) 0.03 (#0.01) 0.09 (#0.06) 99.24 (#0.05) 53.10 (#2.63)
q FFL (g = 10) 0.0 (#0.0) 0.09 (=0.0) 98.90 (#0.01)
52.71 (#1.40)
MAXFL.
0.55 (=0.0) 0.41 (=0.07) 99.29 (#0.03) 53.93 (=1.87)
Table 7: GM-APPEAL, and preferred-model test accuracy for the seen clients' test data with the final global models trained via MAXFL and q-FFT, (Li et al. 2019) which aims in improving fairness. The baseline q-FFL with large g, e.g. q= 10, emulates the behavior of another well-known algorithm named AFL (Mohri et al. 2019).
global model or solo-trained local model). For the unseen clients with FMNIST, FedProx achieves a slightly higher preferred-model test accuracy (+0.05) than MAXFL but with a much lower GM-Appeal of 0.46 (see Table 3) as MAXFL's GM-Appeal 0.56, For the other datasets with unseen clients, MAXFL achieves at least the same or higher preferred-mode test accuracy than the other mothods. This demonstrates that MAXFL consistently largely improves the GM-Appeal compared to the other methods while losing very little, if any, in terms of the model test accuracy.
Comparison with Algorithms for Fairness Fair FL methods (Li et al. 2019 Mohri et al. 2019) aim in training a global model that yields small variance across the clients' test accuracies. These methods may satisfy the worst performing clients, but potentially best performing clients. We show in Table 7 that the common fair FL methods are indeed not effective in improving the overall clients' GM-APPEAL. We see that the fair FL methods achieve a GM-APPEAL. lower than 0.01 for all datasets while MAXFL achieves at least 0.40 for all datasets. Moreover, the preferred-model test accuracy is also higher for MAXFL compared to the fair FL methods. This underwelming performance of fair FL methods in GM-APPEAL can be due to the fact that fair FL methods try to find the global model that performs well, in overall, over all clients which results in failing to satisfy any client.
the cost of causing dissatisfaction from the
MaxFL's Theoretical Learning Rate Behavior for Fig. (b). Here, we provide plot of MAXFL's theorctical learning rate for the mean estimation example in Fig. 1(b) in Fig. 7 to show how the learning rale changes for proof of concept on the adaptive learning rate we discuss in Section 4. For the sigmoid function which is used for our MAXFL objective, using a global notion of smoothness can cause gradient descent to be too slow since global smoothness determined by behavior at wo 0 where w the model. In this case, it is better to use local estimate of smoothness in the flat regions where |uo| >> O. Recall that (ww) and therefore setting
10
different regions of the model. We show this plot
fgg
5
0
5
10
W
Figure 7: Behavior of The- oretical Learning Rate of MAXFLL for the mean estima- tion example in Fig. 1(b). As expected from the theoretical learning rate formula, higher learning rate in regions where the function is flat.
Vor(w) = a (1-)))1))())L11) (1 -2o(w) < <z( the learning rate proportional to [[w)[1o(w]] can increase the learning rate in flat regions where aw) is close to 1 or Following a similar argument, can show that the learning rate in our objective should be proportional to 1/ (MM (FF(w)) - (1 - ((F(w))) F.()))))
see
32


Reviews:
[{"review_id": "AQP0lkLewT", "reviewer": "Reviewer_E382", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nS1. The proposed formulation is new and shows good performance in simple experiments.\n\nS2. Numerical results show that MaxFL works well even when some clients decide to leave/join.\n\n### Weaknesses\n\nW1. The benefits of considering GM-Appeal maximization are not formalized and not justified theoretically. The authors explain the intuition and motivation behind the proposed formulation but do not show formal benefits of its consideration.\n\nW2. The authors do not provide a formal result on how problems (2) and (3) are related.\n\nW3. Theorem 3.1 relies on many assumptions. In particular, the authors assume Lipschitzness and smoothness of $F_k$. Typically, for the analysis of optimization methods and, in particular, FL algorithms it is sufficient to assume either Lipschitzness or smoothness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose the so-called Global Model Appeal (GM-Appeal) as an alternative to the standard FL objective. This quantity measures the ratio of clients finding the current global model $w$ \"appealing\", i.e., the ratio of clients such that the value of true loss function $f_k(w)$ of client $k$ is smaller than some predefined threshold $\\rho_k$. The authors also provide a smooth relaxation of the proposed formulation (via replacing the indicator function with a sigmoid and the true loss with an empirical one) and design a new algorithm (called MaxFL) for minimizing the resulting objective. This algorithm can be seen as FedAvg for the relaxed GM-Appeal minimization with a stepsize that adapts to the weights of aggregation. The authors also analyze the proposed method for non-convex problems with smooth, Lipschitz-continuous objective under bounded variance and bounded gradient dissimilarity assumptions. MaxFL was also tested in numerical experiments and showed better GM-Appeal and test accuracy than competitors on image classification tasks (FMNIST, EMNIST, Sent140).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Questions and suggestions for improvement\n\n1. Can the benefits of maximizing GM-Appeal be formalized and justified theoretically? For example, one can try to come up with an example when GM-Appeal maximization is provably beneficial in the case when new clients join with a data similar to the seen clients. If it is problematic to show theoretical benefits of GM-Appeal maximization, then more substantial numerical justification is required.\n\n2. How well does problem (3) approximate problem (2)?\n\n3. In the toy example, $\\rho_k$ requires knowing $\\theta_k$. In this case, the mean is already known for each client.\n\n4. The experiment with Byzantine attackers is confusing. In this experiment, the authors assume that Byzantine workers send too large GM-Appeal gap. However, it is unclear why it is the worst possible scenario. For example, Byzantine workers can send zero as a \"gap\" and send arbitrary vectors as $\\Delta w_k^{(t,0)}$, e.g., these vectors can have arbitrary large norms. In this case, MaxFL can be broken by Byzantines in 1 communication round. Therefore, in the current shape the algorithm cannot resist Byzantine attacks.\n\n5. On page 6, the authors claim that MaxFL allows \"partial client availability\". This statement is inaccurate since the authors use uniform client sampling, which implicitly relies on the fact that all clients are available at any time (since every client can be sampled with non-zero probability).\n\n6. The pseudocode of the method should be provided in the main part of the paper. Otherwise, it is hard to understand how the method works and what are some of the quantities stand for (in particular, it is mentioned only in the pseudocode that $T$ stands for the number of communication rounds).\n\n7. On page, the authors mention that the optimal learning rate for MaxFL is $\\widetilde{\\eta} = 1/\\widetilde{L}_s$. Is there any proof of optimality of this stepsize? Did the authors try to use other stepsizes (e.g., constant ones, without weights) in MaxFL for the experiments?\n\n8. There is no complete formulation of Theorem 3.1 in the appendix (though the authors claim that they provide it in the appendix). In particular, complete formulas for stepsizes are required together with the requirements on $T$, i.e., how large $T$ should be? Moreover, the current formula for $\\eta_l$ and the third and fourth terms in RHS of (5) have issues with a physical dimension: $\\eta_l$ should have the same physical dimension as $1/L_s$ while $T,\\tau,m$ have void physical dimension.\n\n9. Why does the inequality for $\\widetilde{\\eta}^{(t,0)}$ between formulas (95) and (96) hold?\n\n## Minor comments\n\n1. Definition 1: the notation for GM-Appeal does not reflect the fact that it depends on $w$ and $\\rho_k$. I suggest to replace GM-Appeal with GM-appeal($w, \\lbrace\\rho_k\\rbrace_{k\\in [M]}$).\n\n2. Formula (2): usually $\\text{sign}(x)$ denotes a sign of $x \\in \\mathbb{R}$, i.e., $-1,0,+1$. The function that authors denote as $\\text{sign}(x)$ is usually denoted as $[x]_+$.\n\n3. Page 6: wrong sign in the definition of $\\Delta w_k^{(t,0)}$.\n\n4. I think there is a typo in (55) in the calculation of the Hessian, though starting from (58) the derivation is correct.\n\n5. In the derivation of (91), the authors use (47) + (49) + (52) instead of just the statement of Lemma C.1. So, it is better to adjust the statement of Lemma C.1.\n\n6. The first line of page 26: should be $\\eta_l \\eta_g \\leq 1 / (4\\tau M L_s)$.", "broader_impact_concerns": "The authors provide enough details on a broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EssBAIbH8m", "reviewer": "Reviewer_xZWJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1) The proposed metric is well-motivated and has real world application potentials. This proposed new framework can inspire the community to rethink about the traditional global loss minimization objective.\n2) Extensive numerical validation are provided from various aspects to show effectiveness of the proposed method.\n3) Theoretical analysis are provided for the method.\n\nWeakness:\n1) Since the proposed objective resembles a \"hard\" variation of q-FFL, I suggest the author provide more discussion to compare between q-FFL and the proposed GM-Appeal.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduce a novel objective called Global Model Appeal (GM-Appeal), which aims at training a global model that can satisfy the requirements of the most number of local clients. To maximize the proposed GM-Appeal, the author propose a framework called MaxFL, which are shown to be able to perform well in the new objective. In addition, convergence analysis are provided for the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the \"weakness\" section.", "broader_impact_concerns": "Broader impact is properly addressed", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "elUhmxk7Be", "reviewer": "Reviewer_DCmo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed metric of global model appeal is intuitive and practically useful, especially in problems in which the clients may opt out of the federation. It also provides a fresh perspective as to the goal of federated learning.\n- Based on the proposed definition of global model appeal, the paper also applies natural relaxation of the definition, which leads to a natural algorithm which is able to efficiently maximize the objective of global model appeal.\n- Although the toy example is very simple, it does allow for formalizing a number of interesting insights about the proposed global model appeal.\n- The experimental results indeed show the empirical advantage of the proposed method.\n\nWeaknesses:\n- In your main experiments (such as Figure 1 and Table 1), do you consider the possibility of agents opting out of the federation? If yes, then this is different from the common experimental setting in federated learning, and needs to be clearly specified. Also, if you have indeed allowed the agents to opt out, how is this done exactly? An agent would opt out as long as its requirement is not satisfied in any iteration? In addition, if the answer is yes, have you tested the performance of the algorithm in the standard FL setting (no agents opting out)?\n- In the toy example in Section 2.2, in the definition of $F_k(w)$, why is the second term $(\\hat{\\theta}_k - \\theta_k)^2$ needed?\n- The interpretation of the aggregated gradient in Section 3 is very interesting and provides insights and intuitions as to how the proposed algorithm works. However, I find the behavior of the algorithm when $F_k(\\mathbf{w}) \\gg \\rho_k$ concerning. More specifically, the discussion at the top of page 6 suggests that in this case, the algorithm will simply \"abandon\" those agents for whom there is little hope to satisfy their requirements, i.e., give up helping them satisfy their requirements. I think this is likely to create problems regarding fairness. So, I think mitigation methods should be proposed or this issue should be given sufficient discussions.\n- The theoretical results in Section 3.1 can be presented better. For example, I think it would be helpful to clearly discuss what are the insights drawn from the theoretical results, and what how do these theoretical results differ from those of classical FedAvg.\n- On page 9, it is mentioned that \"We perform grid search for hyperparameter tuning for all baselines and choose the best performing ones\". Is this a common practice? I imagine in practice, it may make more sense to use a single set of hyperparameters in all new applications, or to use a validation set to select hyperparameters and then test the results using a separate test set. \n- In the experiments of \"Local Tuning for Personalization\", have you compared the performance using local fine-tuning with the performance without it (no personalization)?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a novel objective in federated learning, i.e., to maximize the total number of clients whose requirements are satisfied by the global model. The paper firstly proposes the novel metric of global model appeal, which measures the proportion of clients whose requirements are satisfied by the global model. Then, the proposed objective is relaxed in order to derive a practical objective and optimization algorithm to maximize the global model appeal. The convergence of the method is analyzed, and extensive experiments are performed to assess the advantage of the proposed metric and method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Most of the required changes are discussed under Weaknesses above. In addition, \n- Theorem 2.1, should the $\\gamma$ be $\\gamma_G$?", "broader_impact_concerns": "As I mentioned in the third point under Weaknesses above, the proposed method may cause fairness issues.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new objective for federated learning, which is to optimize a notion of "global model appeal" to the clients rather than the average loss over clients. This idea is new, significantly different from previous proposals of alternative objective functions, and resonates with the need of providing incentives to convince clients to join an FL process.

The proposed formulation is validated by some theoretical and empirical results. While I agree with reviewer E382 that these results could be improved/broadened, I side with the other two reviewers that the current results are sufficient to validate the usefulness of the proposed idea, which I believe has the potential to be refined in subsequent work.

For these reasons, I recommend the paper to be accepted with minor revision. The requested changes are as follows:
- The claim that the proposed approach is "robust to Byzantine clients", while not central to the paper, is not supported by sufficient evidence, as highlighted by reviewer E382. Indeed, Byzantine clients can behave arbitrarily, hence such a robustness property must be formally established. What the authors provide is evidence that their approach is robust to a particular attack (but better attacks may exist). I thus ask the authors to tone down their claim, e.g., by stating that their approach exhibits better robustness to some attacks.
- In his/her last message, reviewer E382 asked for clarifications about Theorem 3.1 and its proof. Please make sure you add these details.
Decision: Accept (poster)