Fair Resource Allocation in Federated Learning
Authors: Tian Li
Maziar Sanjabi
Ahmad Beirami
Virginia Smith
Venue:  (2020)
Keywords: federated learning
fairness
distributed optimization

Abstract: Federated learning involves training statistical models in massive, heterogeneous networks. Naively minimizing an aggregate loss function in such a network may disproportionately advantage or disadvantage some of the devices. In this work, we propose q-Fair Federated Learning (q-FFL), a novel optimization objective inspired by fair resource allocation in wireless networks that encourages a more fair (specifically, a more uniform) accuracy distribution across devices in federated networks. To solve q-FFL, we devise a communication-efficient method, q-FedAvg, that is suited to federated networks. We validate both the effectiveness of q-FFL and the efficiency of q-FedAvg on a suite of federated datasets with both convex and non-convex models, and show that q-FFL (along with q-FedAvg) outperforms existing baselines in terms of the resulting fairness, flexibility, and efficiency.

Published as a conference paper at ICLR 2020
FAIR RESOURCE ALLOCATION IN FEDERATED LEARNING
Tian Li CMU
Maziar Sanjabi
Ahmad Beirami Facebook AI beirami @ fb.com
Virginia Smith CMU
Facebook Al maziars @ fb.com
tianli@cmu.ed,
smithy Sarch@@cmu.ddu
ABSTRACT
Federated learning involves training statistical models in massive, heterogencous networks. Naively minimizing aggregate loss function in such network may disproportionately advantage or disadvantage some of the devices. In this work, we propose q-Fair Federated Learning (g-FFL), novel optimization objective inspired by fair resource allocation in wireless networks that encourages a more fair (specifically, more uniform) accuracy distribution across devices in federated net- works. To solve q-FFL, we devise a communication-effiienn method, q-F eddvg, that is suited federated networks. We validate both the effectiveness of Q-FFL and the efficiency of q-Fe on a suite of federated datasets with both convex and non-convex models, and show that Q-FFI, (along with q-FedAvg) outperforms existing baselines in terms of the resulting fairness, flexibility, and efficiency.
INTRODUCTION
Federated learning is an attractive paradigm for fitting a model to data generated by, and residing on, network of remote devices (McMahan al. 2017 Unfortumately, naively minimizing an aggregate loss in a large network may disproportionately advantage or disadvantage the model performance on some of the devices. For example, although the accuracy may be high on average, there is no accuracy guarantee for individual devices in the network. This is exacerbated by the fact that the data are often heterogeneous in federated networks both in terms of size and distribution, and model performance can thus vary widely. In this work, we therefore ask: Can we devise an efficient federated optimization method encourage more fair (i.e., more uniform) distribution of the model performance across devices in federated networks?
There has been tremendous recent interest in developing fair methods for machine learning (see, e.g., Cotter et al. 2019 Dwork et al.) 2012).. However, current approaches do not adequately address concerns in the federated setting. For example, common definition in the fairness literature is to enforce accuracy parity between protected g Zafarr et al. 2017a). For devices in massive federated networks, however, it does not make sense for the accuracy to be identical on each device given the significant variability of data in the network. Recent work has taken step towards addressing this by introducing good-intent fairness, in which the goal is instead to ensure that the training procedure does not overfit a model to any one device the expense of another (Mohri et al., 2019). However, the proposed objective rigid in the sense that only maximizes the performance of the worst performing device/group. and has only be tested in small networks (for 2-3 devices). In realistic federated learning applications, it is natural to instead seek methods that can flexibly trade off between overall performance and fairness in the network, and can be implemented scale across hundreds to millions of devices.
In this work, we propose q-FFL, novel optimization objective that addresses faireess issues in federated learning. Inspired by work in fair resource allocation for wireless networks, G-FFL minimizes an aggregate reweighted loss parameterized by g such that the devices with higher loss are given higher relative weight. We show that this objective encourages device-level definition
'hiie faimess is typically concerned with performance between "groups", we define faimess in the federated setting at more granular scale in terms of the devices in the network. We note that devices may naturally combine form groups, and thus use these terms interchangeahly in the context of prior work.

---

Published as a conference paper at ICLR 2020
of fairness in the federated setting, which generalizes standard accuracy parity by measuring the degree of uniformity in performance across devices. As a motivating example, we examine the test accuracy distribution of a model trained via a baseline approach (FedAvg) vs. q-FFL in Figure [ Due to the variation in the data across devices, the model accuracy is quite poor on some devices. By using q-FFL, we can maintain the same overall average accuracy while ensuring more fair/uniform quality of service across the network. Adaptively minimizing our q-FFL objec- tive results in flexible framework that can be tuned depending on the desired amount of fairness.
12
Baseline: FedAvg
Proposed: q-FFL
10-
# Devices
8
Increasing the accuracy of the
worst-performing devices
4
d.c
02
6.4
0.8
1/
To solve q-FFI. in massive federated networks, we ad- ditionally propose a lightweight and scalable distributed method, g-FedAvg. Our method carefully accounts for important characteristics of the federated setting such and low participation of devices (Bonawitz et al.] 2019 McMahan et al. (0177) The method also reduces the overhead of tuning the hy- perparameter q in q-FFL. by dynamically estimating the step-sizes associated with different values of q.
Testing accuracy
Figure 1: Model performance (e.g.. test accuracy) in federated networks can vary widely across devices. Our objec- tive, q-FFL, aims to increase the fair- ness/uniformity of model performance while maintaining average performance.
communication-efficin
Through extensive experiments on federated datasets with both convex and non-convex models, we demonstrate the fairness and flexibility of q-FFL and the efficiency of q-FedAvg compared with existing baselines. In terms of fairness, Q-FFL is able to reduce the variance of accuracies across devices by 45% on average while maintaining the same overall average accuracy. terms of efficiency, our distributed method, q-F e-Fe,,,, is capable of solving the proposed objective orders-of- magnitude more quickly than other baselines. Finally, while we consider our approaches primarily in the context of federated learning, we also demonstrate that q-FFL, can be applied to other related problems such as meta-lcarning, helping to produce fair initializations across multiple tasks.
2 RELATED WORK
Fairness in Resource Allocation. Fair resource allocation has been extensively studied in fields such as network management (Fe & Bajesy| 2004 Hahne 1991 Kelly et al.) 1998 Neely et al., 2008 and wireless communications (Eryilmaz & Srikant 2006 Nandagopal et al.) 2000 (anjaaii al. 2014) Shi et al.) 2014). In these contexts, the problem is defined as allocating a scarce shared resource, e.g.. communication time or power, among many users. In these cases, directly maximizing utilities such as total throughput may lead to unfair allocations where some users receive poor service. As a service provider, it is important to improve the quality of service for all users while maintaining overall throughput. For this reason, several popular fairness measurements have been proposed to balance between fairness and total throughput, including Jain's 's index (Jain et al. 1984), entropy (Rényi et al. 1961), max-min/min-mal fairness (Radunovic & Le Boudec 2007), and proportional fairness (Kelly 1997). ). A unified framework is captured through a-fairness (Lan et al. 2010 Mo & Walrand 2000). in which the network manager can tune the emphasis on fairness by changing a single parameter, a.
To draw an analogy between federated learning and the problem of resource allocation, one can think of the global model as a resource that meant serve the users (or devices). In this sense, is natural to ask similar questions about the faimess of the service that users receive and use similar tools to promote fairness. Despite this, we are unaware of any works that use a-fairnsss from resource allocation to modify objectives in machine learning. Inspired by the a-fairness metric, we propose a similarly modified objective, q-Fair Federated I Learning (g-FFI.), to encourage a more fair accuracy distribution across devices in the context of federated training. Similar the a-fairness metric, q-FFL objective is flexible enough to enable trade-offs between fairness and other traditional metrics such accuracy by changing the parameter q. In Section 4 we show empirically that the of Q-FFL as an objective in federated learning enables a more uniform accuracy distribution across srrices-sinnificatly reducing variance while maintaining the average accuracy.
Fairness in Machine Learning. Fairness is a broad topic that has received much attention in the machine learning community, though the goals often differ from that described in this work. Indeed,
2

---

Published as a conference paper at ICLR 2020
fairness in machine learning is typically defined the protection of some specific attribute(s). Two common approaches are to preprocess the data to remove information about the protected attribute, or to post-process the model by adjusting the prediction threshold after classifiers are trained (Feldman 2015 Hardt et al. 2016, Calmon et al. 2017). Another set of works optimize an objective subject to some fairness constraints during training time (Agarwal al., 2018)) Cotter al.. 2019 Haahimoto
ct al. 20188] Woodworth et al.) 2017, Baharlouci et al.) 2020] Zafar ct al. 201 7a
b Dwork et al. 2012).
define fairness as the uniformity of the accuracy distribution across devices in federated learning (Section 3). as opposed to the protection of a specific attribute. Although some works define accuracy parity to enforce equal error rates among specific groups notion of fairness (Zafar et al. 201 Cotter et al. 2019), devices in federated networks may not be partitioned by protected attributes, and our goal is not to optimize for identical accuracy across all devices. Cotter et al. (2019) use notion of 'minimum accuracy', which is conceptually similar to our goal. However, it requires one optimization constraint for each device, which would result in hundreds to millions of constraints in federated networks.
Our work also enforces fairness during training, although
In federated settings, Mohri et al. (2019) recently proposed a minimax optimization scheme, Agnostic Federated Learning (AFL), which optimizes for the performance of the single worst device. This method has only been applied at small scales (for a handful of devices). Compared to AFL, our proposed objective is more flexible as it can be tuned based the desired amount of fairnsss; AFL can in fact be seen as a special case of our objective, q-FFI, with large enough q. In Section 4 we demonstrate that the flexibility of our objective results in more favorable accuracy vs. fairness trade-offss than AF and that q-F F can also be solved at scale more efficiently.
Federated Optimization. Federated learning faces challenges such expensive communication, variability in systems enviromments in terms of hardware or network connection, and non-identically distributed data across devices (Li et al., (019).. In order to reduce communication and tolerate het- erogeneity, optimization methods must be developed to allow for local updating and low participation among devices (McMahan et al.] 2017 |mmith et al., 2017). We incorporate these key ingredients when designing methods to solve our FIFFI. objective efficiently in the federated setting (Section 3.3)
3 FAIR FEDERATED LEARNING
In this section, we first formally define the classical federated learning objective and methods, and introduce proposed notion of fairness (Section (.T). We then introduce q-FFL., novel objective that encourages a more fair (uniform) accuracy distribution across all devices (Section 3.2). Finally, in Section 3.3] we describe q-F e-Fed,vg an efficient distributed method to solve the Q-FFL objective in federated settings.
3.1 PRELIMINARIES: FEDERATED LEARNING, FEDAVG, AND FAIRNESS
Federated learning algorithms involve hundreds millions of remote devices learning locally on their device-generated data and communicating with central server periodically to reach global consensus. particular, the goal is typically to solve:
min ((w)
Σ ph FR(w), 1=1
where is the total number of devices, pk 2 0, and Σ E. Pk = The local objective Fe's can be
defined by empirical risks over local data, i.e., (w) az In 1i, (w), where n4 is the number of samples available locally. We can set pk to be Bk where n >x n& the total number of samples to fit a traditional empirical risk minimization-type objective over the entire dataset.
Most prior work solves T by sampling a subset of devices with probabilities pk at each round, and then running an optimizer such stochastic gradient descent (SGD) for a variable number of iterations locally on each device. These local updating methods enable flexible and efficient communication compared to traditional mini-batch methods, which would simply calculate sub- set of the gradients (Stich 2019 Wang & Joshi 2018: Woodworth et al. 2018 Yu et al., 2019). FedAvg (McMahan et al. 2017). summarized in Algorithm BS in Appendix C.I is one of the leading methods to solve (I) in non-convex settings. The method runs simply by having each selected device apply F: epochs of SGD locally and then averaging the resulting local models.
3

---

Published as a conference paper at ICLR 2020
Unfortunately, solving problem (T) in this manner can implicitly introduce highly variable perfor- mance between different devices. For instance, the learned model may be biased towards devices with larger numbers of data points, or (if weighting devices equally), to commonly occurring devices. More formally, we define our desired fairness criteria for federated learning below.
Definition (Fairness of performance distribution). For trained models w and ú. we informally say that model t provides more fair solution to the federated learning objective (1) than model úö if the performance of model w on the m devices, {01,.... ... Om is more uniform than the performance of model i on the m devices.
In this work, we take 'performance', Og, to be the testing accuracy of applying the trained model w on the test data for device k. There are many ways to mathematically evaluate the uniformity of the performance. In this work, we mainly use the variance of the performance distribution as a measure of uniformity. However, we also explore other uniformity metrics, both empirically and theoretically, in Appendix [. We note that a tension exists between the fairesss/uiformiyy of the final testing accuracy and the average testing accuracy across devices. In general, our goal is to impose more fuimmss/uniformitty while maintaining the same (or similar) average accuracy.
Remark 2 (Connections to other fairness definitions). Definition I targets device-level fairness, which has finer granularity than the classical attribute-level fairness such as accuracy parity (Zafar er al. 2017ap. We note that in certain cases where devices can be naturally clustered into groups with specific attributes, our definition can be seen as a relaxed version of accuracy parity, in that we optimize for similar but not necessarily identical performance across devices.
3.2 THE OBJECTIVE: G-FAIR FEDERATED LEARNING (q-FFL)
A natural idea to achieve fairnsss as defined in (T) would be to reweight the objective abjscnive-assigning higher weights to devices with poor performance, so that the distribution of accuracies in the network shifts towards more uniformity. Note that this reweighting must be done dynamically, as the performance of the devices depends on the model being trained, which cannot be evaluated priori. Drawing inspiration from a-faiiness, utility function used in fair resource allocation in wireless networks, we propose the following objective. For given local non-negative cost functions F3 and parameter q > 0, we define the q-Fair Federated Learning (q-FFI.) objective as:
min fa(w)
Pk
F
(w),
(2)
where F2 (.) denotes (.) to the power of (1+ Here, q is a parameter that tunes the amount of fairness we wish impose. Setting q = 0 does not encourage fairness beyond the classical federated learning objective [ A larger means that we emphasize devices with higher local empirical losses, (w),), thus imposing more uniformity to the training accuracy distribution and potentially inducing faimess in accordance with Definition] ! Setting (w( with a large enough reduces to classical minimax fairness (Mohri al.. 2019). as the device with the worst performance (largest loss) will dominate the objective. We note that while the (q+1) term in the denominator in (2) may be absorbed Pk. we include it as it standard in the a-fairnsss literature and helps to ease notation. For completeness, we provide additional background on o-fairnsss in Appendix B
As mentioned previously, Q- generalizes prior work in fair federated learning (AFL) Mohri et al., 2019), allowing for a flexible trade-off between fairness and accuracy as parameterized by In our theoretical analysis (Appendix A we provide generalization bounds of g-FFL. that generalize the learning bounds of the AFL objective. Moreover, based on fairness definition (Definition] [ theoretically explore how Q-FFL results in more uniform accuracy distributions with increasing q. Our results suggest that Q-FFL is able to impose 'uniformity' of the test accuracy distribution in terms of various metrics such as variance and other geometric and information-thent
measures.
In our experiments (Section 4.2 both convex and non-convex models, show that using the Q-FFL objective, we can obtain lairer/more uniform solutions for federated datasets in terms of both the training and testing accuracy distributions.
4

---

Published as a conference paper at ICLR 2020
3.3 THE SOLVER: FEDAVG-STYLE Q-FAIR FEDERATED LEARNING (q-FEDAVG)
In developing a functional approach for fair federated learning, it is critical to consider not only what objective to solve but also how solve such an objective efficiently in massive distributed network. In this section, we provide methods to solve q-FFL. We start with a simpler method, q-F FdddsG to illustrate our main techniques. We then provide a more efficient counterpart, q-FedAvg, by considering local updating schemes. Our proposed methods closely mirror traditional distributed optimization methods methods-mini-bant mini-bbtch SGD and federated averaging (FedAvg) butt with step-sizes and subproblems carefully chosen in accordance with the Q-FFL, problem
Achieving variable levels of fairness: tuning 9. In devising a method to solve q-FFL ( we begin by noting that it is crucial to first determine how to set q. In practice, q can be tuned based on the desired amount of fairness (with larger y inducing more fairness). As we describe in our experiments (Section 4.2 it is therefore common to train a family of objectives for different q values so that practitioner can explore the trade-off between accuracy and fairness for the application at hand.
One concern with solving such a family of objectives is that it requires step-size tuning for every value of q. In particular, in gradient- based methods, the step-size inversely depends on the Lipschitz constant of the function's ' gradient, which will change search space to explode. To overcome this issue, we propose estimating the local Lipschitz constant for the family of Q-FFL objectives by using the Lipschitz constant we infer by tuning the step-size (via grid search) on just one (e.g. = 0). This allows us to dynamically adjust the step-size of our gradient-based optimization method for the q-FFL objective, avoiding manual tuning for each q. In Lemma 3 below we formalize the relation between the Lipschitz constant, L, for = 0 and >> O.
change q. This quickly cause the
Lemma 3. If the non-negative function f()) has a Lipschitz gradient with constant L, then for any q 2 0 and at any point w,
- = Lf(")" +
(3)
is an upper-bound for the local Lipschitz constant of the gradient of 1 (.+)()) at point w.
g+I
Proof. At any point w, we can compute the Hessian 7 (w+) as:
2 got (w)) = (w) (w) V[
+ (
V2 f(w)
(4)
3LXI
As result, v
1 f1+1 (w)llz S (w( = g+b
A first approach: q-FedSGD. Our first fair federated learning method, q-FedSGD, is an exten- sion of the well-known federated mini-batch SGD (FedSGD) method (McMahan et al. 2017). q-FedSGD uses dynamic step-size instead of the normal fixed step-size of FedSGD. Based on Lemma 3 for each local device k, the upper-bound of the local Lipschitz constant is In each step of q-FedSGD, FFF and F₂ on each selected
(F + "IV device k are computed at the current iterate and communicated to the central node. This information used compute the step-sizes (weights) for combining the updates from each device. The details are summarized in Algorithm [ Note that g-FedSGD is reduced to FedSGD when q = O. It is also important to note that to run q-FedDGD with different values of q. we only need to estimate once by tuning the step-size on g = 0 and can then reuse it for all values of O.
g-FedAvg. federated settings, communication-effiee schemes using local stochastic solvers (such as FedAvg) have been shown to significantly improve convergence speed (McMahan et al. 2017 However, when y 0, the r term is not an empirical average of the loss over all local samples due to the q + exponent, preventing the use of local SGD in FedAvg. To address this. we propose to generalize FedAvg for q > 0 using a more sophisticated dynamic weighted averaging scheme. The weights (step-sizes) are inferred from the upper bound of the local Lipschitz constants of the gradients of F similar to q- edSGD. To extend the local updating technique of FedAvg to the Q-FFL objective (2). we propose heuristic where we replace the gradient FF, in the FeFDDD steps with the local updates that are obtained by running SGD locally on device k. Similarly, g-FedA is reduced to FedAvg when g 0. We
Improving communication-effiiee
5

---

Published as a conference paper at ICLR 2020
Algorithm 1 q-FedSGD
Input: K, 9, L, w. Pk. ,,
2: for = 0,....................... .T do
3: Server selects subset S, of K devices random (each device & chosen with prob. Pt.)
4: Server sends w² to all selected devices
5: Each selected device computes:
A V
h4 q (w' FI LFF
6: Each selected device kt sends A and hy back to the server
7:
Server updates w++1 as:
Eres, 4 EREst h
w ++ = w'
8: end for
Algorithm 2 q-FedAvg
1: Input: K, E. (... L/L, 77, w. Pk. h =,, ,,
2: for = 0,... , , do
3: Server selects subset St of K devices random (each device k is chosen with prob. p&)
4: Server sends w² to all selected devices
5: Each selected device k updates w' for E epochs of SGD Fa with step-size y) to obtain wf+1
6: Each selected device computes:
Aw L(w 1
A (2("") Aw')
h = (P--1((") Auf + (F)("0)
7: Each selected device sends Aj. and h back to the server
8: Server updates w++1 as:
w++1 w' EkEs, 4 EkES, hig
9: end for
provide additional details on q-FedAvg in Algorithm 2 solve Q-FFL objective much more efficiently than q-FedSCD due to the local updating heuristic. Finally, recall that as + oo the q-FFL objective recovers that of the AFL. However, we empirically notice that q-F g-FedAvg has more favorable convergence speed compared to AFL while resulting in similar performance across devices (see Figure Inn in the appendix).
As we will see empirically, q-FedAv can
4 EVALUATION
We now present empirical results the proposed objective, q-FFL, and proposed methods, q-FedAvg and F-FDG We describe our experimental setup in Section[4.] We then demonstrate the improved
fairness q-FFL in Section 4.2] and compare q-FFL with several baseline faimess objectives in Sec-
tion 4.3, Finally, we show the efficiency of g-FedAvg compared with g-FedSGD in Section 4.4 All
code, data, and experiments are publicly available allgithub. 1 wttp:/tttoocc///////// fair fatrrffeerrrr
4.1 EXPERIMENTAL SETUP
Federated datasets. We explore suite of federated datasets using both convex and non-convex models our experiments. The datasets are curated from prior work in federated learning (McMahan) al.] 2017 Smith al.) 2017 Li et al. 2020 Mohri et al. 2019) as well as recent federated learning benchmarks (Caldas et al., 2018).
particular, we study: (I) a synthetic dataset using a linear regression classifie, (2) Vehiele dataset collected from distributed sensor network (Duarte & Hu 2004) with linear SVM for binary classification, (3) tweet data curated from Sentiment1400 (Go al. 2009) (Sent140) with an LSTM classifier for text sentiment analysis, and (4) text data built

---

Published as a conference paper at ICLR 2020
from The Complete Works of William Shakespeare (McMahan al. 2017) and an RNN to predict the next character. When comparing with AFL, we use the two small benchmark datasets (Fashion MNIST (Xiao et al. 2017) and Adult (Blake 1998)) studied in Mohri et al. (2019). When applying
g-FFL to meta-learning, we use the common meta-learning benchmark dataset Omniglot (Lake et al.
2013 Full dataset details given in Appendix [.I]]
Implementation. We implement all code in Tensorflow (Abadi et al. 2016), simulating a federated network with one server and devices, where m is the total number of devices in the dataset (Appendix D.I. We provide full details (including all hyperparameter values) in Appendix D.2
4.2 FAIRNESS OF Q-FFL
In our first experiments, we verify that the proposed objective q-FFLL leads more fair solutions (Definition D for federated data. In Figure 2 we compare the final testing accuracy distributions of two objectives (g and a tuned value q > 0) averaged across random shuffles of each dataset. We observe that while the average testing accuracy remains fairly consistent, the objectives with q > 0 result in more centered (i.e., fair) testing accuracy distributions with lower variance. In particular, while maintaining roughly the same average accuracy, g- g-FFL reduces the variance of accuracies across all devices by 45% on average. We further report the worst and best 10% testing accuracies and the variance of the final accuracy distributions in Table [I] Comparing q 0 and O, see that the average testing accuracy remains almost unchanged with the proposed objective despite significant reductions in variance. We report full results all uniformity measurements (including variance) in Table in the appendix, and show that Q-FFL, encourages more uniform accuracies under other metries as well. We observe similar results on training accuracy distributions in Figure 6 and Table 6 Appendix E In Table the average accuracy is with respect to all data points, not all devices; however, we observe similar results with respect to devices, as shown in Table Appendix
Synthotic
Vehicla
Sent140
Shalaspeare
200
Devices
20
Desttom
Devicos
5.0
100
8.0
0.25
0.50
0.75
1.00
800
0.25
0.50
0.75
1.00
800
0.25
0.50
0.75
1.00
8.00
0.25
0.50
0.75
1.00
Teeting accuraty
Testing sccuracy
Testing sccurary
Testing sccuracy
Figure 2: Q-FFL leads fairer test accuracy distributions. While the average accuracy remains almost identical (see Table TT. by setting 0, the distributions shift towards the center as low accuracies increase at the cost of potentially decreasing high accuracies on some devices. Setting q 0 corresponds to the original objective ( 'he selected values for > O on the four datasets, as well as distribution statistics, are also shown in Table T
Table 1: Statistics of the test accuracy distribution for q-FFL. By setting > O. the accuracy of the worst 10% devices increased at the cost of possibly decreasing the accuracy of the best 10% devices. While the average accuracy remains similar, the variance of the final accuracy distribution decreases significantly. We provide full results of other uniformity measurements (including variance) in Table 5 Appendix and show that F-FFL encourages more uniform distributions under all metrics.
Average (%)
Worst 10% (%)
Best 10% (%)
Variance
Dataset
Objective
q 0
80.8 9
18.8 5.0
100.0 +: 0.0
724
Synthetic
g = 1
79.0 + 1.2
31.1 + 1.8
100.0 + n.0
472 + 14
q = 0
87.3 =
43.0 + 1.0
95.7 1.0
291 +
Vehicle
g 5
87.7 1
69.9
94.0 1.
48
g = 0 q = 1 { = 0
65.1 4.88
15.9 4.99
100.0 + 0.0
697 + 132
Sent140
66.5 .2
23.0
100.0 0.0
509 1::
51.1 =
39.7 + 2.8
72.9 6.7
82 + 41
Shakespeare
q .001
52.1 +
42.1 +: 2.1
69.0 4.4
54 +
7

---

Published as a conference paper at ICLR 2020
Choosing 9. As discussed in Section 3.3
natural question is to determine how q should be tuned in
the q-FFL objective. Our framework is flexible in that it allows one to choose q to tradeoff between fairnsssummiformity and average accuracy. We empirically show that there are family of q's that can result in variable levels of fairness (and accuracy) on synthetic data in Table [T] Appendix H In general, this value can be tuned based the data/application hand and the desired amount of fairness. Another reasonable approach in practice would be to run Algorithm 2 with multiple g's in parallel to obtain multiple final global models, and then select amongst these based on performance (e.g., accuracy) on the validation data. Rather than using just one optimal q for all devices, for example, each device could pick a device-specific model based on their validation data. We show additional performance improvements with this levice-specific strategy in Table T2 in Appendix Finally, we note that one potential issue is that increasing the value y may slow the speed of convergence. However, for values of y that result in more fair results on our datasets, we do not observe significant decrease in the convergence speed, as shown in Figure g Appendix E
4.3 COMPARISON WITH OTHER OBJECTIVES
Next, we compare QLF with other objectives that are likely to impose fairness in federated networks. One heuristic is to weight each data point equally, which reduces to the original objective in (1) (i.e.. Q-FFL with q = 0) and has been investigated in Section 4.2] We additionally compare with two alternatives: weighting devices equally when sampling devices, and weighting devices adversarially, namely, optimizing for the perfo-nerf device, as proposed in Mohri et al. (2019).
Weighting devices equally. We compare q-FFL with uniform sampling schemes and report testing accuracy in Figure 3 A table with the final accuracies and three fairness metrics is given in the appendix in Table While the 'weighting each device equally' heuristic tends to outperform our method in training accuracy distributions (Figure 7 and Table in Appendix D. we see that our method produces more fair solutions in terms of testing accuracies. One explanation for this is that uniform sampling is a static method and can easily overfit to devices with very few data points, whereas q-FFL will put less weight on device once its loss becomes small, potentially providing better generalization performance due to its dynamic nature.
Synthetic uniform exo
Vahicla
Sent1
Shakaspeare
200
7.5
Deviess
20
Devines
Deviess
800
0.25 Testing accuracy
0.50
0.25
1.00
800
0.25
0.50
0.75
1.00
8.00
0.25
0.50
0.75
1.00
8.00
0.25
0.50
0.75
1.00
Testing accuracy
Testing accuracy
Testing accuracy
Figure 3: q-FFL (q > 0) compared with uniform sampling. In terms of testing accuracy, our objective produces more fair solutions than uniform sampling. Distribution statistics are provided in Table 9 in the appendix. Q-FFL achieves similar average accuracies and more fair solutions.
Weighting devices adversarially. We further compare with AFL (Mohri et al. 2019), which is the only work we are aware of that aims to address faimess issues in federated learning. We implement a non-stochastic version of AFL where all devices are selected and updated each round, and perform grid search on the AFL hyperparameters, Two and 7x- In order to devise a setup that is as favorable to AFL as possible, we modify Algorithm [2) by sampling all devices and letting each of them run gradient descent at each round. We use the same small datasets (Adult (Blake) 1998) and subsampled Fashion MNIST (iaao et al. 2017)) and the same logistic regression model as in Mohri et al. (2019). Full details of the implementation and hyperparameters (e.g., values of qı and q2) are provided in Appendix D.2.3 We note that, as opposed to AF L, F-FFL is flexible depending on the amount of fairness desired, with larger y leading to more accuracy uniformity. As discussed, g-FFL generalizes AFL in this regard, as AFL is equivalent to Q-FFL with a large enough q. In Table 2 we observe that q-FFL can in fact achieve higher testing accuracy than AFL on the device with the worst performance (i.e.. the problem that the APL was designed to solve) with appropriate q. This also indicates that G-FFL. obtains the most fair solutions in certain cases. We also observe that F-FFI, converges faster
8

---

Published as a conference paper at ICLR 2020
in terms of communication rounds compared with AFL to obtain similar performance (Appendix which we speculate is due to the con-smoothness of the AFL objective.
Table 2:
Our objective compared with weighing devices adversarially (AFL MMorr et al. 2019) In order to be favorable to AFL, we use the two small, well-behaved datasets studied in (Mohri et al. 2019). q-FFL > 0) outperforms AFL the worst testing aceuracy of both datasets. The tunable parameter y controls how much fairness we would like to achieve- q induces less variance. Each accuracy is averaged across 5 runs with different random initializations.
Adult
Fashion MNIST
Objectives
average (%)
PhD (%)
non-PhD
average (%)
shirt (%)
pullover
T-shirt
(%)
(%)
(%)
Q-FFL, 0=0 AFL
83.2 i 69.9 4
83.3 1.1
78.8
66.0 1.3
84.5 4
85.9
82.5 s 73.0 1:22
82.6 5
77.8 1.2
71.4 4:2
81.0 133
82.1 1:39
q-FFL, 91>0
82.6 +1 74.1 6
82.7 1
77.8
74.2
78.9
80.4 4
Q-FFL, 92>91
82.3 +
74.4 9
82.4
77.1 #
74.7 #
77.9 #
78.7 #
4.4 EFFICIENCY OF THE METHOD Q-FRDAVG
In this section, we show the efficiency of our proposed distributed solver, g-FedAvg, by comparing Algorithm 2 with its con-local-updating baseline q-F e-DDD (Algorithm[]) to solve the same objective (same as in Table At each communication round, we have each method perform the same amount of computation, with g-FedAvg running one epoch of local updates on each selected device while q-F edGGD runs gradient descent with the local training data. In Figure q-FedAvg converges faster than g-FedSGD in terms of communication rounds in most cases due to its local updating scheme. The slower convergence of q-F FedAvg compared with q-FedSGD may be due to the fact that when local data distributions are highly heterogeneous, local updating schemes may allow local models move too far away from the initial global model, potentially hurting convergence; see Figure 10 in Appendix for more details.
the synthetic dataset
Synthetic
Vehide
Sent140
a.
Texting acsurecy
Sooume 93
icao
Fod/vg Fed56D
Teating
300
1000
1500
2000
200
cio
500
3000
1500
2000
Rounds
$ Rounds
Rounds
A Rouudd
Figure 4: For a fixed objective (i.e., F-FFL with the same q), the convergence of q-FedAvg (Alg e-FDD (Alg(] and FedSGD. For edAvg and q-FedSGD, we tune a best step-size q = and apply that step-size to solve F-FFL with q >> For q-FedSGD, we tune the step-size directly. We observe that (1) g-FedAvg converges faster in terms of communication rounds; (2) our proposed q-FedSGD solver with a dynamic step-size achieves similar convergence behavior compared with a best-tuned FedSGD.
To demonstrate the optimality of our dynamic step-size strategy in terms of solving I-FFL, we also compare our solver q-FedSGD with FedsGD with best-tuned step-size. For q-FedSGD, we tune a step-size on = 0 and apply that step-size to solve Q-FFL with q > 0. q-FeddGG has similar performance with FedSGD, which indicates that (the inverse of) our estimated Lipschitz constant on q > 0 is as good as a best tuned fixed step-size. We can reuse this estimation for different q instead of manually re- re-tuning when q changes. We show the full results other datasets in Appendix E We note that both proposed methods q-FedAvg and q-Fed can be easily integrated into existing implementations of federated learning algorithms such as TensorFlow Federated (TFF)

---

Published as a conference paper at ICLR 2020
4.5 BEYOND FEDERATED LEARNING: APPLYING q-FFL TO META-LEARNING
obeeteeee to other learning tasks beyond federated learning. One natural extension is apply g-FFL to meta-learning, where each task can be viewed as device in federated networks. The goal of meta-lcarning is to learn a model initialization such that it can be quickly adapted to tasks using limited training samples. However, the new tasks can be heterogeneous, the performance distribution of the final personalized models may also be non-uniform. Therefore, aim learn better initialization such that quickly solve unseen tasks in a fair manner, i.e., reduce the variance of the accuracy distribution of the personalized models.
Finally, we generalize the proposed q-FFL objective
Omaiigiot
qFu
15-
q".1
Table 3: Statistics of the accuracy distribution of personalized models using q-MAML. The method with q = 0 corresponds to MAML. Similarly, we see that the variance is reduced while the accuracy of the worst 10% devices is increased.
Takks
0.4 Testing accurascy
Average (%)
Worst 10%
Best 10%
Variance
Dataset
Objective
(%)
(%)
Figure 5: Q-FFL, results in fairer (more centered) ini- tializations for meta-learning tasks.
Omniglot
q =
79.1 9.8
61.2 # 3.2
94.0 +
93 2
= .1
79.3 9.6
62.5 # 5.3
93.8 +
86 + 28
To achieve this goal, we propose new method, q-MAMI, by combining q-FFL, with the popular meta- learning method MAML (Finn et al. 2017). In particular, instead of updating the global model in the way described in MAML, we update the global parameters using the gradients of the q-FFL objective q+I F (w). with weights inferred from Lemma 3 Similarly, 9-MAMI with g = 0 reduces to MAMI, and q-MAML with q + oo corresponds to MAML with a most 'fair' initialization and a potentially lower average accuracy. The detailed algorithm is summarized in Algorithm 4 in Appendix C22 We sample 10 tasks at each round during meta-training, and train for iterations of (mini-batch) SGD for personalization on meta-testing tasks. We report test accuracy of personalized models on meta-testing tasks. From Figure 5 and Table above, we observe that g-MAML is able to learn initializations which result in fairer personalized models with lower variance.
CONCLUSION
In this work, propose Q-FFL, novel optimization objective inspired by fair resource allocation in wireless networks that encourages fairer (more uniform) accuracy distributions across devices in federated learning. We devise scalable method, q-F (-FedAvg, solve this objective in massive networks. Our empirical evaluation on a suite of federated datasets demonstrates the resulting fairness and flexibility of Q-FFL, as well as the efficiency of g-FedAvg compared with existing baselines. We show that our framework is useful not only for federated learning tasks, but also for other learning paradigms such as meta-learning.
ACKNOWLEDGMENTS
We thank Sebastian Caldas, Chen Dan, Neel Guha, Anit Kumar Sahu, Eric Tan, and Samuel Yeom for their helpful discussions and comments. The work of TL and VS was supported in part by the National Science Foundation grant IIS NIS188801, a Google Faculty Award, a Carnegie Bosch Institute Research Award, and the CONIX Research Center. Any opinions, findings, and conclusions or recommendations expressed in this material are those the author(s) and do not necessarily reflect the National Science Foundation any other funding ageney.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Tensorflow federated: Machine learning on decentralized data.
URL
https: //Www www
Eensorflow frg//ederteed
Martín Abadi, Paul Barham, Jiammin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large-scale machine learning. In Operating Systems Design and Implementation, 2016.
Alckh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. In International Conference on Machine Learning, 2018.
Sina Baharlouci, Maher Nouiched, Ahmad Beirami, and Meisam Razaviyayn. Rényi fair inference. In International Conference on Learning Representations, 2020.
Ahmad Beirami, Robert Calderbank, Mark M Christiansen, Ken R Duffy, and Muriel Médard. A characterization of guesswork on swiftly tilting curves. IEEE Transactions on Information Theory,
65(5):2850-2877 2871, 2019.
Catherine L Blake,
Uci repository http://wwww.css.cc..dddd// http:/sii...eeammmmmmeeeeeeeeeee
machine
learning
databases.
1998.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselande. Towards federated learning scale: System design. In Conference on Machine Learning and Systems, 2019.
Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv: 1812.0097, 2018.
Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre-processing for discrimination prevention. In Advances in Neural Information Processing Systems, 2017.
Andrew Cotter, Heinrich Jiang, Serena Wang, Taman Narayan, Maya Gupta, Seungil You, and Karthik Sridharan. Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals. Journal of Machine Learning Research, 2019.
Mina Dashti, Paeiz Azmi, and Keivan Navaie. Harmonic mean rate faimess for cognitive radio networks with heterogeneous traffic. Transactions on Emerging Telecommunications Technologies, 2013.
Marco F Duarte and Yu Hen Hu. Vehicle classification in distributed sensor networks. Journal of Parallel and Distributed Computing, 2004.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science, 2012.
Cheng Tien Ee and Ruzena Bajesy, Congestion control and fairness for many-to-one routing in sensor networks. In International Conference on Embedded Networked Sensor Systems, 2004.
Atilla Eryilmaz and R Srikant. Joint congestion control, routing, and mac for stability and faimesss in wireless networks. IEEE Journal on Selected Areas in Communications, 2006.
Michael Feldman. Computational fairness: Preventing machine-learned discrimination. 2015.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. International Conference on Machine Learning, 2017.
Alec Go, Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervision. Stanford CS224N Project Report, 2009.
11

---

Published as a conference paper at ICLR 2020
Ellen L. Hahne. Round-robin scheduling for max-min fairness in data networks. IEEE Journal Selected Areas in communications, 1991.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, 2016.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang, Fairness without demographics in repeated loss minimization. In International Conference Machine Learning, 2018.
Rajendra K Jain, Dah-Ming W Chiu, and William R Hawe. A quantitative measure of faimess and discrimination. Eastern Research Laboratory, Digital Equipment Corporation, 1984.
Frank Kelly, Charging and rate control for elastic traffic. European Transactions on Telecommunica- tions, 1997.
Frank P Kelly, Aman K Maulloo, and David KH Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society, 1998.
Brenden Lake, Ruslan Salakhutdinov, and Joshua Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 2015.
Tian Lan, David Kao, Mung Chiang, and Ashutosh Sabharwal. An axiomatic theory of fairness in network resource allocation. In Conference on Information Communications, 2010.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. arXiv preprint urXiv:1908.07880 07873, 2019.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Conference on Machine Learning and Systems, 2020.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Communication-efficcai learning of deep networks from decentralized data. International Conference Artificial Intelligence and Statistics, 2017.
Jeonghoon Mo and Jean Walrand. Fair end-to-end window-based congestion control. JEEE/ACM Transactions on Networking, 2000.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- tional Conference on Machine Learning, 2019.
Thyagarajan Nandagopal, Tae-Eun Kim, Xia Gao, and Vaduvur Bharghavan. Achieving mac layer faimess in wireless packet networks, In International Conference Mobile Computing and Networking, 2000.
Michael J Neely, Eytan Modiano, and Chih-Ping Li. Fairness and optimal stochastic control for heterogencous networks. IEEE/ACM Transactions On Networking, 2008
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing, 2014.
Bozidar Radunovic and Jean-Yves Le Boudec. unified framework for max-mi max-min and min-max faimnsss with applications. IEEE/ACM Transactions on Networking, 2007.
Alfréd Rényi al. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1961.
Maziar Sanjabi, Meisam Razaviyayn, and Zhi-Quan Luo. Optimal joint base station assignment and beamforming for heterogeneous networks. IEEE Transactions on Signal Processing, 2014.
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-efficii distributed optimization using approximate newton-type method. In International Conference Machine Learning, 2014.
12

---

Published as a conference paper at ICLR 2020
Huaizhou Shi, R Venkatesha Prasad, Ertan Onur, and IGMM Niemegeers. Faimess in wireless networks: Issues, measures and challenges. IEEE Communications Surveys and Tutorials, 2014.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. In Advances in Neural Information Processing Systems, 2017.
Virginia Smith, Simone Forte, Ma Chenxin, Martin Takáč, Michael Jordan, and Martin Jaggi. Cocoa: A general framework for communication-effcceen distributed optimization. Journal of Machine Learning Research, 2018.
Sebastian Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2019.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiienn sgd algorithms. arXiv preprint arXiv:1808.000 07576, 2018.
Blake Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, and Nathan Srebro. Learning non- discriminatory predictors. Conference on Learning Theory, 2017.
Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in Neural Information Processing Systems, 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07744 2017.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd for non-convex optimization with faster convergence and less communication. In AAAI Conference on Artificial Intelligence, 2019.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fair- ness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In International Conference World Wide Web, 2017a.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fair- ness constraints: Mechanisms for fair classification. In International Conference on Artificial Intelligence and Statisties, 2017b.
13

---

Published as a conference paper at ICLR 2020
A THEORETICAL ANALYSIS OF THE PROPOSED OBJECTIVE Q-FFL
A. UNIFORMITY INDUCED BY Q-FFL
In this section, we theoretically justify that the q-FFL objective can impose more uniformity of the performance/accuracy distribution. As discussed in Section [.2] q-FFL can encourage more fair solutions terms of several metries, including (1) the variance of accuracy distribution (smaller variance), (2) the cosine similarity between the accuracy distribution and the all-ones vector 1 (larger similarity), and (3) the entropy of the accuracy distribution (larger entropy). We begin by formally defining these fairness notions.
Definition 4 (Uniformity Variance of the performance distribution). We say that the performance distribution of m devices {F) ..... [m[[]] is more uniform under solution than w' if
Var (.m.).....())))) (m]))) < Var Var(Fi (F.(())..... (w)))))
(5)
Definition (Uniformity Cosine similarity between the performance distribution and 1). We say that the performance distribution of m devices (F), F' [m]] is more uniform under solution w than w' if the cosine similarity between {Fi (F],,,,.... Fm (w)) and is larger than that between {Fi(w'), (w)).... Fm (nww") and 1, i.c.
1 DE FA(W)
E Fa(w')
(6)
1 ER F((w)
1 E F((w")
Definition 6 (Uniformity 3: Entropy of performance distribution). We say that the performance distribution of m devices {Fi(w), Fm(()) is more uniform under solution than w/ if
(F(()) H(F(w'))
where (FW))) is the entropy of the stochastic vector obtained by normalizing (Fi(w),.... Fm (w),, defined as
m Fw log [FF(w))
F& (w) Ek= P((w))
(8)
Ei (w
To enforce uniformity/fairness (defined in Definition and 6 we propose the q-FFL objective to impose more weights on the devices with worse performance. Throughout the proof, for the ease of mathematical exposition, we consider similar unweighted objective:
RFT
min W
fww))
FR
(w)
771
and we denote w as the global optimal solution of min fq(w))
We first investigate the special case of q and show that q = results in more fair solutions than
0 based on Definition and Definition 5
Lemma 7. q leads to more fair solution (smaller variance of the model performance distribu- tion) Ihan 0, i.e., Var Fi
Fm.( < Var (FrFF (F (w))..., Fm Fm(w)) (w))).
Proof. Use the fact that wi is the optimal solution of min, fi(w), and wy is the optimal solution of min fo(w), we get
2
2
Σ 1=1 (ww))
m
M
F((wo))
m k=
F (((w))
1
(u(
Fr
m
m
m
m
Σ Em 1=
F F2(W))
1
Fa Fa(
(9)
1=1
14

---

Published as a conference paper at ICLR 2020
Lemma 8. 9= leads more fair solution (larger cosine similarity between the performance distribution and 1) than q = 0, i.e.
m E FR(Wi))
m DE Pe(w))
(w0
V m (1
Proof. As Σx= directly follows that
(x(wi)
2 +.
m Ex= (w( and 1 Ex= (2(wF)
2 1 - FR(w)),
1 Σ k= Fx(w1)
1 D Fa(wH))
(w))
(2
We next provide results based on Definition 6 states that for arbitrary g 2 0. by increasing g for a small amount, we can get more uniform performance distributions defined over higher-orders of the performance.
Lemma 9. Let F(w) be twice differentiable in w with V F(w) > 0 (positive definite). The derivative of (FF((w))) with respect to the variable p evaluated at the point p q is non-negative, i.e.,
H(F
2 0,
Op
p=q
where (1F)) is defined in equation
S
Proof.
(FF())
θ
Σ
F (1)))
In
Fg (w(g))
(10)
Öp
0p
Σx Fil (2)
Σn Fi ((wg))
p=q
0
Σ
F1 (wp) Σ. Fil (wF)
In (F%
0p
pm
ln
F
(w
(1I)
0p
N
p=q
Op
w
w (wgg))
Σ
p=q
In (F)
Σn F2l F2(10))
Op "
V (l(
F (w
(12)
F2 (wi))
(1
(w
Up "
p=q
(In (F) + +1).
(13)
Σx (10
k
Now, let us examine derivative with respect to p. we have
== 0p " p==
We know that Ee ve by definition. Taking the
i
Σ VV
Op w + Σ (In 1) V.
(14)
Invoking implicit function theorem,
0 Op
[VZF((w3))
Σ (In (R + +1) F(
(15)
P
15

---

Published as a conference paper at ICLR 2020
Plugging öp u
into (13). we get that Öp ((F())))) p=y
2 completing the proof.
p=y
Lemma states that for any p. the performance distribution of (FI ..... Fi x+e)) is guaranteed be more uniform based Definition than that of {FF (wp).... ...................... F2 (wF)) for small
enough e, Note that Lemma is different from the existing results on the monotonicity of entropy under the tilt operation, which would imply that 2 (009 Lemma 11)).
s 0 for all 2 0 (see Beirami et al.
9 implying that the distribution {FT (wp+e).... Fa (w (w)+)) is more uniform than {FT (w (w)).. ...... F2 (w2) }} for any p. q and small
Ideally, we would like to prove result more general than Lemma
enough E. We prove this result for the special case of m = 2 in the following.
Lemma 10. Let F(w) be twice differentiable in w with V F2F(w) > (positive definite). If m = for any q E R the derivative of H (F" (w,)) with respect to the variable p is non non-negative, i.e.,
① Op
H (w 2
where (wF))) is defined in equation 8
Proof. First, we invoke Lemma 9 to obtain that
i
il (1
20.
(16)
Dp
p=g
Let
(g(w) (w) (w)
(17)
Without loss of generality assume that (2=,))
(0. 20.2] can relabel F1 and F2 otherwise. Then, given that m 2, we conclude from equation [6 allnnong with the monotonicity of the binary entropy function in (0, ž] that
0 Pp
og (w)))
2 0,
(18)
p=y
which in conjunction with equation 17 Iimplis that
a Fi (w
9
2 0.
(19)
Op
Fa(w;)
p=g
Given the monotonicity of x" with respect for all q sufficient to imply that for any q > 0,
0, it can be observed that the above is
0 Fi (wz)
8
2 0.
(20)
Op
F2 (2w)
Going all of the steps back we would obtain that for all p 0
a (FT) 2 0.
(21)
This completes the proof of the lemma.
We conjecture that the statement of Lemma 9 true for all q R+, which would be equivalent the statement of Lemma holding true for all m N.
Thus far, we provided results that showed that 4-FFL promotes faimess in three different senses. Next, we further provide a result on equivalence between the geometric and information-theoreii notions of fairness.
16

---

Published as a conference paper at ICLR 2020
Lemma 11 (Equivalence between uniformity in entropy and cosine distance). Q-FFL encourages more uniform performance distributions in the cosine distance sense (Definition 5 if any only if is
encourages more uniform performance distributions in the entropy sense (Definition 6 i.e., (a) holds if and only if holds where (a) for any p. 9 RR the derivative of ((F))) with respect to p is non-negative, (b) for any S ts sts
{e(w 2 {((
I-(w))
I+(w))
Proof. Definition 6 is a special case of ((F() with y = 1. If (F*(( increases with p for any P. then We are guaranteed to get more fair solutions based on Definition
6 Similarly,
Definition 5 is a special case of fe(w")
f-(w:() with & 0,r 1. If f.(w() increases with u for any S r. f-(w(.)
Q-FFL FI can also obtain more fair solutions under Definition 5
Next, we show that (a) and (b) equivalent measures of fairness.
For any r 2 t 2 0, and any a 2 2 O,
fe(wi)) (r(w))
f((w;)
In fe(w
- In f((wt)
2
20 0
(22)
(r(w))
Jr [w( (r(wg)
n 0 In Se(w")
dr 2 0
(23)
0r
(w(
In fe(up)
2 0, for any 0
(24)
0p
fr(w;)
i
In (r(
In (, < 0, for any p 2 0
(25)
Öp
Op
I. Öpdq
0² In fy f1 - 0 for any p. 2 0
(26)
8²
In fy(wx)) S 0, for any q 2 0
(27)
Opdq
i ((F 2 0, for any p, 2
(28)
Op
The last inequality is obtained using the fact that by taking the derivative of In fo (wz)) with respect to q. we get HH(FH(PP P9 (w))).
Discussions. We give geometrie (Definition 5) and information-theome (Definition 6 interpretations of our uniformity/fairnes: notion and provide uniformity guarantees under the q-FFL objective in some cases (Lemma 7, Lemma 8 and Lemma 99. We reveal interesting relations between the geometric and information-theorett interpretations in Lemma TT Future work would be to gain further understandings for more general cases indicated in Lemma
A.2 GENERALIZATION BOUNDS
In this section, we first describe the setup we consider in more detail, and then provide generalization bounds of q-FFL. One benefit of q-FFL that it allows for a flexible trade-off between fairness and accuracy, which generalizes AFL (a special case of q-FFL with q -> oc). We also provide learning bounds that generalize the bounds of the AFL objective, as described below.
Suppose the service provider is interested in minimizing the loss over distributed network of devices, with possibly unknown weights on each device:
m
(h(h)= = Σ AL A=
(29)
where A is in a probability simplex A, m is the total number of devices, D& is the local data distribution for device k., h is the hypothesis function, and / is the loss. We use î. (h) denote the empirical
17

---

Published as a conference paper at ICLR 2020
loss:
As
7kk (h(2)1)) Mk.)),
(h
(30)
Th
j=1
where ne is the number of local samples on device and (Ik.j, ~ DR.
We consider slightly different, unweighted version of q-FFL:
m
min fw(
(w)
(31)
m
which is equivalent to minimizing the empirical loss
Lg(h)
(k((zg)).
(32)
Tkk
where 1 q+I -1
Lemma 12 (Generalization bounds of Q-FF for specific X). Assume that the loss is bounded by M >> O and the numbers of local samples are (n,,... ,Tmm). Then, for any 5 O, with probability at
least 1 - 8, the following holds for any E A, h H:
m
Lx(h) S (g())L
max Lx(h) EA(A)) + M hEH
log
(33)
2nk
where AA(A) | and 1/p + 1/(g + 1.
Proof. Similar to the proof in Mohri et al. (211)). for any O, the following inequality holds with probability least 1 for any À E A, h H:
(h) < (A( + E max (1) - La(h)) + M,
log
(34)
REH
2nh
Denote the empirical loss on device
Σラ ((h((r))))))))) (ess)) as FR. From Hölder's inequality, we
ne
have
m
m
m
(b) = Σ PpP
Σ
X2
Σ
(gg())
a+l 1.
Plugging (A( & (A( into
34
yields the results.
Theorem (Generalization bounds of Q-FFL any A). Assume that the loss is bounded by M > O and the number of local samples is (nI,... .mm). Then, for any 8 >> O, with probability at least 8, the following holds for any A, h H:
max Lx(h) ES(A) + M heHf
X 2n
(h) < max (Ag(A) (b) AEA
max AEA
E
Σ km
log
(35)
where (2) = 1 and 1/p +1)
Proof. This directly follows from Lemma 12 by taking the maximum over all possible X's A.
Discussions. From Lemma 12 letting À (_.... ....... and y co, recover the generalization
bounds in AFL (Mohri et al. 2019). In that sense, our generalization results extend those of AFL In addition, it is not straightlorward to derive optimal q with the tightest generalization bound from Lemma 12 and Theorem [3 In practice, our proposed method q-F q-FedAvg allows us to tune a family of q by re-using the step-sizes.
18

---

Published as a conference paper at ICLR 2020
B Q-FAIRNESS AND Q-FEL
As discussed in Section 2 while it is natural to consider the a-fairness framework for machine learning, we are unaware of any work that uses a-fairness to modify machine learning training objectíves. We provide additional details on the framework below; for further background on a- fairness and faimess in resource allocation more generally, we defer the reader to Shi et al. (2014);
Mo & Walrand (2000).
a-fairness Lann al. 2010: Mo Walrand 2000 is a popular fairness metric widely-used in resource allocation problems. The framework defines a family of overall utility functions that can be derived by summing up the following function of the individual utilities of the users the network:
In In(x); Ua(2)= = T
if
if 2 0
Here (x) represents the individual utility of some specific user given x allocated resources (e.g., bandwidth). The goal is to find a resource allocation strategy to maximize the sum of the individual utilities. This family of functions includes a wide range popular fair resource allocation strategies. In particular, the above function represents zero fairness with fairness (Kelly) 1997) with a 1. harmonic mean fairness (Dashti et al. 2013) with 2, and max-min faimess (Radunovic & Le Boudec 2007) with +00.
0, proportional
Note that federated learning, we are dealing with costs and not utilities. Thus, max-min in resource allocation corresponds to min-max in our setting. With this analogy, it is clear that in our proposed objective q-FFL (2), the case where q = +o0 corresponds to min-max fairness since is optimizing for the perrr-eeffoming device, similar to what was proposed in Mohri et al. (219)) Also, q = 0 corresponds to zero fairness, which reduces to the original FedAvg objective resource allocation problems,
In be tuned for trade-offs between fairness and system efficiency. In federated settings, g can be tuned based on the desired level of fairness (e.g., desired variance of accuracy distributions) and other performance metrics such as the overall accuracy. For instance, in Table 2 in Section 4.3, we demonstrate on two datasets that as q increases, the overall average accuracy decreases slightly while the worst accuracies are increased significantly and the variance of the accuracy distribution decreases.
19

---

Published as a conference paper at ICLR 2020
C PSEUDO-CODE OF ALGORITHMS
C.1 THE FEDAVG ALGORITHM
Algorithm 3 Federated Averaging McMahan al. (0177) (FedAvg)
Input: K, T, 7/ E, w N, Pk. k = , fort 0, 0..... T
1 do
Server randomly chooses a subset St of K devices (each device is chosen with probability pk)
Server sends w² all chosen devices
Each device k updates w² for E epochs of SGD on F& with step-size vy to obtain wek" ++1
Each chosen device k sends w back to the server Server aggregates the w's as w Ekes, w/ 1+1
end for
C.2 THE q-MAML ALGORITHM
Algorithm 4 q-FFL applied to MAML: 9-MAML
1: Input: K, T, 7), w N, Pk. k 1,..,, N
2: for 0,- 0,....
do
3: Sample batch of Se ([S, K)) tasks randomly (each task k is chosen with probability pk)
4: Send w' to all sampled tasks
5: Each task & E S. samples data Dj from the training set and D/ from the testing set, and computes updated parameters on D: wf = w v Fu(w") 6: Each task E S, computes the gradients (F on D
7: Each task k E S, computes:
A F (w) VF
h 9F% (w))
FF LF
8: w1 is updated as:
w1+1 w² Σ EkES, 4 EnES, 11
9: end for
20

---

Published as a conference paper at ICLR 2020
D EXPERIMENTAL DETAILS
D.1 DATASETS AND MODELS
We provide full details on the datasets and models used in our experiments. The statistics of four federated datasets used in federated learning (as opposed to meta-leaminn) experiments are summarized in T We report the total number of devices, the total number of samples, and mean and deviation in the sizes of total data points on each device. Additional details on the datasets and models are described below.
Synthetic: We follow similar set up as that Shamir al. (2014) and impose additional heterogeneity. The model is y = argmax(softmax (W x))6)), I E IR W E R R10x60 6 E 10 and the goal learn a global W and b. Samples (X₂, Yx) and local models on each device & satisfies W₂ M(ug 1), by ~ N (ug. 1), 24 ~ (O,, 1); diagonal with Σj =j j 3-1.2 Each element in 24 is drawn from W(B, : 1), B, (O, 1). There are 100 devices in total and the number of samples on each devices follows a power law.
Nuk, E), where the covariance matrix E
Vehicle We use the same Vehicle Sensor (Vchicle) dataset as Smith et al. 2017). modelling each sensor as a device. This dataset consists of acoustic, seismic, and infrared sensor data collected from distributed network of 23 sensors Duarte & Hu (2004). Each sample has 100-dimension feature and a binary label. We train a linear SVM to predict between AVV-type and DW-type vehicles. We tune the hyperparameters in SVM and report the best configuration.
Sent140: This dataset is a collection of tweets curated from 1,101 accounts from Senti- 40 (Go et al., 2009) (Sent140) where each Twitter account corresponds to a device. The task is text sentiment analysis which we model as a binary classification problem. The model takes input 25-word sequence. embeds each word into a 300-dimensional space using pre- trained Glove [Pennington et al. 2014), and outputs a binary label after two LSTM layers and one densely-connected layer.
Shakespeare:
This dataset is built from The Complete Works of William Shakespeare (McMahan et al. 2017). Each speaking role in the plays is associated with device. We subsample 31 speaking roles to train a deep language model for next character prediction. The model takes as input an 80-character sequence, embeds each character into learnt 8-dimensional space, and outputs one character after two LSTM layers and one densely-connected layer.
The Omniglot dataset (Lake et al. 2015) consists of 1,623 characters from 50 different alphabets. We create 300 meta-training tasks from the first 1, 1,200 characters, and 100 meta-testing tasks from the last 423 characters. Each task is 5-class classification problem where each character forms a class. The model is a convolutional neural network with two convolution layers and two fully-comnected layers.
Omniglot:
Table 4: Statistics of federated datasets
Dataset
Devices Samples Samples/device
mean
stdev
Synthetic
100
12,697
127
73
Vehicle
23
43,695
1,899
349
Sent140
1.101
58,170
53
32
Shakespeare
116,214
3,749
6,912
D.2 IMPLEMENTATION DETAILS
D.2.1 MACHINES
We simulate the federated setting (one server and m devices) on server with 2 Intel Xeon E5-2650 v4 CPUs and 8 NVidia 1080Ti GPUs.
http:/ /www. ecs. umass ama.secll/mmiiarrt///aavveee.e
21

---

Published as a conference paper at ICLR 2020
D.2.2 SOFTWARE
We implement all code in TensorFlow (Abadi et al.) 2016) Version 1.10.1. Please see github.
for full details.
D.2.3 HYPERPARAMETERS
We randomly split data on each local device into 80% training set, 10% testing set, and 10% validation set. We tune best q from {0.001, 0.01, 0.1, 0.5, 1,2,5, 10, 15} the validation set and report accuracy distributions on the testing set. We pick up the q value where the variance decreases the most, while the overall average accuracy change (compared with the For each dataset, we repeat this process for five randomly selected train/test/validttinn splits, and report the mean and standard deviation across these five runs where applicable. For Synthetic, Vehicle, 140, and Shakespeare, optimal values are 1, 5, 1, and 0.001, respectively. For all datasets, we randomly sample 10 devices each round. We the learning rate and batch size on FedAvg and use the same learning rate and batch size for all g-FedAvg experiments of that dataset. The learning rates for Synthetic, Vehicle, Sent 40, and Shakespeare are 0.1, 0.01, 0.03, and 0.8, respectively. The batch sizes for Synthetic, Vehicle, Sent 140, and Shakespeare 10. 64, 32, and 10. The number of local epochs is fixed to for both F FedAvg and q-FedAvg regardless of the values q.
case) within 1%.
In comparing q- q-ved efficiency with q-FedSGD, also tune best learning rate for q-FSSGGD methods on 9 O. For each comparison, we fix devices selected and mini-batch orders across all We stop training when the training loss F(w) does not decrease for 10 rounds. When running AFL methods, we search for a best "he and 7 such that AFL achieves the highest testing accuracy on the device with the highest loss within fixed number of rounds. For Adult,
You 0.1 and T> = 0.1; for Fashion MNIST, we use T = 0.001 and 72 = 0.01. We use the same T as step-sizes for q-Feddvg on Adult and Fashion MNIST. In Table 91 0.01, q2 for q-FFL on Adult and 5, = 15 for Q-FFL on Fashion MNIST. Similarly, the number of local epochs is fixed to whenever we perform local updates.
22

---

Published as a conference paper at ICLR 2020
E FULL EXPERIMENTS
E.1 FULL RESULTS OF PREVIOUS EXPERIMENTS
Fairness of Q-FFL under all uniformity metrics. We demonstrate the fairness of q-FFL in Table in terms of variance. Here, we report similar results in terms of other uniformity measures (the last two columns).
Table 5: Full statistics of the test accuracy distribution for q-FFL. Q-FFL increases the accuracy of
the worst 10% devices without decreasing the average accuracies. We see that g-FFL encourages
more uniform distributions under all uniformity metrics defined in Appendix A.2 (1) the variance of the accuracy distribution (Definition 4, (2) the cosine similarity/geometrie angle between the
accuracy distribution and the all-ones vector (Definition 5). and (3) the KL-divergence between the
normalized accuracy vector and the uniform distribution u, which can be directly translated to the
entropy (Definition 6
Average (%)
Worst 10%
Best 10% (%)
Variance
Angle (9)
KL(allu)
Dataset
Objective
(%)
Synthetic
q =
80.8 9
18,8 5.00
100.0 0.0
724 =
19.5 = 1.1
.083 = 0013
q 1
79.0 = 1.2
31.1 1.8
100.0 0.0
472
16.0 # .049 .00
q = 0
87.3
43.0 =
95.7 = 1.
291 18
11.3 #
.031 008
Vehicle
Q 5
87.7
69.9
94.0+0
48 =
4.6
.003
Q = 0 Q =
65.1 + 4.8
15.9 +
100.0 0.0
697 + 132
22.4 3.3
.104 034
Sent140
66.5 22
23.0 + 1.4
100.0 0.0
509 30
18.8 4.5
.067 : .06
Q 0 q .001
51.1
39.7
4: 2.8
72.9
82
9.8 2.7
.014
Shakespeare
52.1 1.3
42.1
2.1
69.0 1 4.4
54 2:
7.9 2.3
.009 1: .05
Fairness of Q-FFL with respect to training accuracy. The empirical results in Section 4 are with respect testing accuracy. As sanity check, we show that F-FFL also results in more fair training accuracy distributions Figure 6 and Table
Synthetic
Shakesspare
and
100
20
A
and
Diviqs
8.0
8.00
8.0
8.50
3.00
Training
Figure 6: Q-FFL (g > 0) results in more centered (i.e., fair) training accuracy distributions across devices without sacrificing the average accuracy.
Table 6: Q-FFL results more fair training accuracy distributions terms of all uniformity measurements-Gaa (a) the accuracy variance, (b) the cosine similarity (i.e., angle) between the ac- curacy distribution and the all-ones vector 1, and (c) the KL divergence between the normalized accuracy and uniform distribution u.
Average (%)
Worst 10% (%)
Best 10% %
Variance
Angle (*)
KL(allu)
Dataset
Objective
(%)
Synthetic
q
81.7 +.3
23.6 =
100.0
597 i
17.5 4.3 .061 .002
78,9 +
41.8 1.0
96,8 +
292 11
12.5 #.2 .027 + 0011
Vehicle
q =
87.5 4.2
49.5 + 10.2
94.9 +.7
237 4:97
10.2 #24 .025 + 0111
87.8 +
71.3 #22
93.1 1.4
37 +
4.0 2.7 .003 0011
69.8 #
36.9 #31
94.4 +
278 #4
13.6 = 1.1
.032 006
Sent140
Q
68.2
46.0
88.8
143 4
10.0
.017 .000
Shakespeare
Q
72.7 +.8
46.4
79.7
116 4
9.9 =
.015 001
Q .001
66.7 - 1.2
48.0 +
71.2 + 1.9
56 -
+
.008 + 001
23

---

Published as a conference paper at ICLR 2020
show that q-FFL leads to more fair accuracy distributions while maintaining approximately the same testing accuracies. Note that report average testing accuracy with respect to all data points in Table observe similar results on average accuracy with respect to all devices between = 0 and > objectives, shown in Table This indicates that q-FFL, reduce the variance of the accuracy distribution without sacrificing the average accuracy over devices or over data points.
Average testing accuracy with respect devices. In Section 4.2
| However,
Table 7: Average testing accuracy under Q-FFL objectives. We show that the resulting solutions of = 0 and q > 0 objectives have approximately the same average accuracies both with respect to all data points and with respect to all devices.
Accuracy w.r.t. Data Points (%)
Accuracy w.r.t. Devices
Dataset
Objective
(%)
Synthetic
g = 1
80.8
77.3 +
79.0 = 1.2
76.3 + 1.7
Vehicle
y g 5 Q =
87.3 1:5
85.6 4
87.7 #
86.5 #
65.1 1 4.8
64.6 4.5
Sent140
Q
66.5
66.2 2
Shakespeare = 0 q .001
51.1 #
61.4 2.7
52.1
60.0 +
Comparison with uniform sampling. In Figure and Table g we show that in terms of training accuracies, the uniform sampling heuristic may outperform Q-FFL (as opposed to the testing accuracy results in Section 4). We suspect that this because the uniform sampling baseline is a static method and is likely to overfit to those devices with few samples. In additional to Figure Ji Section 4.3 also report the average testing accuracy with respect to data points, best 10%, worst 10% accuracies, and the variance (along with two other uniformity measures) Table 9
30
Synthetic uniform
Vehidle
Senti 60
Shakespeare
100
Devces
a0
Devicas
Devian
10
800
800
800
8.00
1.00
Figure 7: Q-FFL (q > 0) compared with uniform sampling in training accuracy. We see that on some datasets uniform sampling has higher (and more fair) training accuracies due to the fact that is overfitting to devices with few samples.
Table 8: More statistics comparing the uniform sampling objective with Q-FFL in terms of training accuracies. We observe that uniform sampling could result in more fair training accuracy distributions with smaller variance in some cases.
Average (%)
Worst 10%
Best 10%
Variance
Angle
KL(allu)
Dataset
Objective
(%)
(%)
uniform
83.5 +
42.6 + 1.4
100.0
366 +
13.4 + .031 .02
Synthetic
q =
78.9 + 2
41.8 + 1.0
96.8 + 5
292 + II
12.5 +.2 .027 = .011
uniform
87.3 4.3
46.6
94.8 4.5
261 + 10
10.7
.027 =
Vehicle
5
87.8 +
71.3 + 2.2
93.1 + 1.4
37 + 12
4,0 +
.003 + .011
uniform
69.1 1.5
42.2 1.1
91.0
188 + 19
11.3 4.5
.022 + .002
Sent140
-=1
68.2 1.6
46.0 1:3
88.8 8.8
143 1:4
10.0 1.1 .017 1: .00
Shakespeare
uniform
57.7 1.5
54.1 1.7
72.4 1 3.2
32 .177
5.2 1
.004
:: .011
== .001
66.7 1:2
48.0 1.44
71.2
56 .1.9
7.1 1
.008 1:
24

---

Published as a conference paper at ICLR 2020
Table More statistics showing more fair solutions induced by q-FFL compared with the uniform sampling baseline in terms of test accuracies. Again, we observe that under q-FFL, the testing accuracy of the worst 10% devices tends to increase compared with uniform sampling, and the variance of the final testing accuracies is smaller. Similarly, q-FFL is also more fair than uniform sampling in terms of other uniformity metrics.
Average (%)
Worst 10%
Best 10%
Variance
Angle (*)
KL(allu)
Dataset
Objective
(%)
(%)
uniform
82.2 +: 1.1
30.0 = 4
100.0 : .0
525 47
15.6 + .048 + 007
Synthetic
q 1
79.0 +: 1.2
31.1 1.8
100.0 0.00
472 14
16.0 + .049 003
uniform
86.8
45,4 #
95,4
267 #
10,8 =.1 .028 = .011
Vehicle
g == 5
87.7 0.7
69.9
94.0 +
48 =
4.6
.003 000
uniform g ==1
66.6 + 2.6
21.1 + 1.9
100.0 0.0
560 =
19.8 = .076 006
Sent140
66.5 = 22
23.0 + 1.4
100.0 0.0
509 30
18.8 = .067 = 006
uniform
50.9
41.0 3.7
70.6
7
9.1 2.8
.012 = 006
Shakespeare
.001
52.1 =
42.1 2.1
69.0 4.4
54 27
7.9 +
.009 = .05
E.2
ADDITIONAL EXPERIMENTS
Effects of data heterogeneity and the number of devices on unfairness. To study how data heterogeneity and the total number of devices affect unfairness more direct way, we investigate into a set of synthetic datasets where we can quantify the degree of heterogeneity. The results are shown in Table below. We generate three synthetic datasetss following the process described in Appendix D.I but with different parameters to control heterogeneity. In particular, we generate an IID data Synthetic (IID) by setting the same W and on devices and setting the samples Th ~ (0, 1) for any device k. We instantiate two non-identically distributed datasets (Synthetic (I, 1) and Synthetic (2, 2)) from Synthetic (a, (3) where dg ~ NO, a:) and B₃ ~ ~N(0, 3). Recall that 8 allows precisely manipulate the degree of heterogeneity with larger a, 3 values indicating more statistical heterogeneity. Therefore, from top to bottom in Table TO data are more heterogeneous. For each dataset, we further create variants with different number of participating devices. We see that as data become more heterogeneous and as the number of devices in the network increases, the accuracy distribution tends to be less uniform.
Table 10: Effects of data heterogeneity and the number of devices on unfairness. For a fixed number of devices, as data heterogeneity increases from top to bottom, the accuracy distributions become less uniform (with larger variance) for both & = 0 and & > Within each dataset, the decreasing number of devices results in more uniform accuracy distribution. In all scenarios (except on IID data), setting > helps to encourage more fair solutions.
Dataset
Objective
Average
Worst 10 %
Best 10 %
Variance
89.2
70.9 1
100.0
85
100 devices
89.0 =.5 5
70.3 +
100.0 =
88 = 19
Synthetic (IID)
50 devices
q
87.1 1.5
66.5 4
100.0 :0
107
86.8 + 0.8
66.5 +
100.0 =0
109 1
100 devices
q
83.0 9
36.8 =
100.0
452
82.7 1.3
43.5 5
100.0 1:0
362 58
Synthetic (1, 1)
50 devices
q
84.5
43.3 1:2
100.0
370 1
85.1 .
47.3 +
100.0
317 =41
100 devices
Q =
82.6 + 1.1
25.5 4
100.0 =0
618 + 117
82.2 0.7
31.9 6
100.0 =0
484 79
Synthetic (2, 2)
50 devices
=
85,9 + 1.0
36.8 47
100.0 40
421
= 85
q 85.9 1.4
39.1 6
100.0.0
396 76
A family of g's results in variable levels of fairness. In Table we show the accuracy distribu-
tion statistics using a family of q's on synthetic data. Our objective and methods are not sensitive to any particular since all q 0 values can lead to more fair solutions compared with q 0. In our experiments in Section 4 we report the results using the values selected following the protocol
described in Appendix D.2.3
25

---

Published as a conference paper at ICLR 2020
Table 11:
Test accuracy statistics of using a family of q's on synthetic data. We show results with q's selected from our candidate set {0.001, 0.01, 0.1, 1, 2, 5, 10, 15). q-FFL allows for more flexible trade-off between fairness and accuracy. but potentially lower accuracy. Similarly, a larger q imposes more uniformity in terms of other metries- (a) the cosine similarity/angle between the accuracy distribution and the all-ones vector 1, and (b) the KL divergence between the normalized accuracy a and a uniform distribution
larger q results in more fairesss (smaller variance),
Dataset
Objective
Average (%)
Worst 10%
Best 10%
Variance
Angle (*)
KL(allu)
(%)
(%)
9=0
80.8 +
18.8 5.0
100.0
724
19.5 + 1.1 .083 +
q= 0.1
81.1 0.8
22.1 + 8
100.0 = 00
666 = 56
18.4 =
.070 + .009
Synthetic
9=1
79.0 1.2
31.1
100.0 0:0
472 =
16.0 =5
.049 +
q=2
74.7 +
32.2 2.1
99.9 =
410 23
15.6 +
.044 + .005
9=5
67.2
30.0 4.8
94.3 = 1.4
369 51
16.3 + 122 .048 + .010
Device-specific q- In these experiments, we explore a device-specific strategy for selecting @ in Q-FFL. We solve q-FFL with q {0, 0.001, 0.01, 0.1, 1, 10} in parallel. After training, each device selects the best resulting model based on the validation data and tests the performance of the model using the testing set. We report the results in terms of testing accuracy in Table [2] Interestingly, using this device-specific strategy the average accuracy in fact increases while the variance of accuracies is reduced, in comparison with q = O. We note that this strategy does induce more local computation and additional communication load at each round. However, it does not increase the number of communication rounds if run in parallel.
Table 12: Effects of rumning Q-FFL with several g's in parallel. We train multiple global models (corresponding to different q's) independently in the network. After the training finishes, each device picks up best, device-specifie model based the performance (accuracy) the validation data. While this adds additional local computation and more communication load per round, the device-specific strategy has the added benefit of increasing the accuracies of devices with the worst 10% accuracies and devices with the best 10% accuracies simultaneously. This strategy is built upon the proposed primitive Algorithm 2 and in practice, people can develop other heuristics to improve the performance (similar to what we explore here), based on the method of adaptively averaging model updates proposed in Algorithm 2
Dataset
Objective
Average (%)
Worst 10%
Best 10% (%)
Variance
Angle (9)
KL(allu)
(%)
9=0
87.3 =.5 5
43.0 + 1.0
95.7 + 1.0
291 + 18
11.3 +.3
.031 + .003
Vehicle
9=5
87.7 2
69.9 2.6
94.0 +
48 =
4.6 4.2
.003 + .000
multiple
88.5 .3
70.0 2.0
95.8 + 66
52 17
4.7 4.3.
.004 1: 000
-=0
51.1 :33
39.7 22
72.9 6.7
82 411
9.8=27
.014 + 000
Shakespeare
9=.001
52.1 23
42.1 2.1
69.0 4.4
54 2.27
7.9 2.
.009 1: .05
multiple q
52.0 +: 1.5
41.0 1 4.3
72.0 4.8
1:32
10.1 1.7 .017 +: .000
Convergence speed of q-FFL. Since q-FFL (g 0) is more difficult to optimize, natural
question one might ask is: will the q-FFL >> 0 objectives slow the convergence compared with FedAvg? We empirically investigate this on the four datasets. We use q-FedAvg to solve g-FFL,
and compare it with FedAvg (i.e., solving F-FFL with 0). As demonstrated in Figure 8 the values that result in more fair solutions also do not significantly slow down convergence.
Figure 8: The convergence speed of q-FFL, compared with FedAvg. We plot the distance to the highest accuracy achieved versus communication rounds. Although q-FFL with q>0 is a more difficult optimization problem, for the q values we choose that could lead to more fair results, the convergence speed is comparable to that of O.
26

---

Published as a conference paper at ICLR 2020
Efficiency of q-FFL compared with AFL. One added benefit of q-FFL is that it leads to faster convergence than AFL even when we use amn-loal-updatingg methods for both objectives. In Figure show with respect the final testing accuracy for the single worst device (i.e., the objective that AFL is trying to optimize), q-FFL, converges faster than AFL. As the number of devices increases (from Fashion MNIST to Vehicle), the performance gap between AFL and q-FFI. becomes larger because AFL introduces larger variance.
9
Fashion MNISTT
Vehicle
Device with lowest accu.
0.70
9.6
Shirt
0.85
0.4
0.55
AFL QIFL q=5
AFL QFFL
2000
4000
6000
100
Rounds
Rounds
Figure 9: Q-FFL is more efficient than AFL. With the worst device achieving the same final testing accuracy, Q-FFL converges faster than L. For Vehicle (with 23 devices) as opposed to Fashion MNIST (with 3 devices), we that the performance gap larger. We run full gradient descent at each round for both methods.
Efficiency of q-FedAvg under different data heterogeneity. As mentioned in Appendix E.1 one potential cause for the slower convergence of g-FedAvg the synthetic dataset may be that local updating schemes could hurt convergence when local data distributions are highly heterogeneous. Although it has been shown that applying updates locally results in significantly faster convergence in terms of communication rounds (McMahan et al.) 2017: Smith et al., 2018). which is consistent with our observation on most datasets, we note that when data is highly heterogeneous, local updating may hurt convergence. We validate this by creating an IID synthetic dataset (Synthetic-III) where local data on each device follow the same global distribution. We call the synthetic dataset used We also create hybrid dataset (Synthetic-Hybrid) where half of
in Section 4 Synthetic-Non-IIl the total devices are assigned IID data from the same distribution, and half of the total devices are assigned data from different distributions. We observe that if data is perfectly IID, q-FedAvq is more efficient than q-F y-FedSGD. As data become more heterogeneous, g-FedAvg converges more slowly than q-FedSGD in terms of communication rounds. For all three synthetic datasets, we repeat the process of tuning a best constant step-size for FedSGD and observe similar results as before our dynamic solver q-F g-FedSGD behaves similarly (or even outperforms) best hand-tuned FedSGD.
Synthetic-Non-ID
Synthetic-Hybrid
Synthetic-IID
Testing accuracy
sisstine accurany
9.6
Testing accurapy
0.8
0.6
0.5-
0.4
q-FedAvg
q-FedSGD
0.2
best tuned FedsGD
2-
2000
1000
1500
2000
Rounds
Rounds
# Rounds
Figure 10: Convergence of q-FedAvg compared with F-GDD under different data heterogeneity. When data distributions are heterogeneous, it is possible that q-FedAvg converges more slowly than q-FedSGD. Again, the proposed dynamic solver q-FedSGD performs similarly (or better) than a best tuned fixed-step-size FedSGD.
27


Reviews:
[{"review_id": "rJeNTLRhFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a new optimization objective for fair resource allocation. Furthermore, a new algorithm, q-FedAvg, based on the vanilla federated learning, is proposed to solve the new optimization in massive and heterogeneous networks. The paper is well written. Theoretical analysis is also provided to support the effectiveness of the proposed methods. The experiments show good performance.\nIn overall, I think this paper solves an important problem in federated learning, and I vote for acceptance.\nHowever, since my knowledge in fairness is very limitted, I think my review is an educated guess. If the other reviews vote for rejection, I will not champion this paper.\n\nI have question to the authors:\n\nIs the proposed algorithm robust to the estimation of the Lipschitz constant? In my opinion, the proposed algorithm highly relies on $L_q(w)$. Thus, the estimation of L will be very essential. It will be better if the authors can show some results where different estimations of L  is used, and compare these results to show the sensitivity to the estimation of L.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SJxeQHzEqH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The problem of fairness in federated learning (FL) is important given the popularity of the topic and its immediate impact on the society. Vanilla FL approaches may be subject to poor performance for clients whose data is under-represented across all participants. This paper proposes a new algorithm for federated learning to reduce variance in performance across clients. The inspiration for the algorithm comes from the problem of uniform  resource allocation in wireless networks.\n\nWhile the problem and the motivation for the algorithm are interesting on the high level, I think this paper does not deliver the key ideas in sufficient detail and clarity.\n\nOn the algorithms side, I am still unclear on how the Lipschitz constant L is estimated on the first run with q=0. Are the results for q=0 in the experiments reported for this run or is it repeated with the learned L? Further, this procedure suggests that the number of communication rounds is at least doubled for the end-to-end training. Tuning q, which seems to be necessary, may require even more communication rounds.\n\nWhile there are a lot of experiments in the paper (across main text and supplementary), none seem to be carried out sufficiently well. Understanding the complete experimental setup for at least one of them is also quite hard due to numerous supplementary references throughout the experiments section. I would recommend to focus on fewer experiments, but present more thorough results. Below are some suggestions.\n\nThe importance of resource allocation in FL appears to me to be directly related to the key FL aspects such as degree of data heterogeneity and number of clients. This submission is lacking experiments comparing FedAvg to the proposed method under these settings (which can be simulated using available datasets). To argue in favor of the proposed approach it is important to demonstrate failure modes of the existing algorithms under some realistic scenarios and present a solution using new algorithm.\n\nAccuracies in Fashion MNIST and Shakespeare experiments seem quite poor suggesting some problems with the setup. FedAvg paper reports 54% on Shakespeare, whereas this paper reports 52%. It also appears that the number of considered \"devices\" on Shakespeare is significantly smaller than in the FedAvg paper (31 vs 1146) - what is the reason for this?\nOn Fashion MNIST, AFL paper reports 80%+ accuracy while achieving 90%+ on the combined dataset seems relative easy based on the results mentioned on the Github repository of the dataset. This paper reports 78% for the proposed method and AFL. Why is there a discrepancy with AFL paper and what is the performance of FedAvg on this dataset (assuming some suitable CNN architecture)? Is there a reason to believe that this dataset is much harder for federated learning than MNIST, where FedAvg roughly matches full data training?\n\nThis statement is ambiguous \"uniform sampling is a static method and can easily overfit to devices with very few data points, whereas q-FFL has better generalization properties due to its dynamic nature.\" If there is a device with very few data points it is easy to overfit to it and q-FFL will essentially ignore that device since the loss on this device is very small. Why does this not lead to more severe overfitting behavior?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJg7OyyM9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary]\nThe authors propose a protocol to encourage a more fair distribution of the performance across devices in a federated setting. In contrast with previous work, which protects a specific attribute, this paper aims to achieve the uniformity of the accuracy distribution.\n\n[Key Comments]\nThe paper is well-organized and clearly written. The claims are well-supported by theoretical analysis and experimental results. However, my main concern is that the paper offers an incremental improvement over the early work FedAvg (McMahan et al., 2017). It would be helpful for the authors to summarize their contributions if space permits.\n\n[Details]\n[Pro 1] This paper provides insights into fairness (a more uniform accuracy distribution) in federated learning, which appears to be well-motivated.\n\n[Pro 2] This paper provides an instructive method to estimate the upper-bound of the Lipschitz constants for ??? the local objective function (the objective function with clients' data) ???. It is an interesting idea to choose dynamic step-size depending on the global Lipschitz constants and fairness parameter q.\n\n[Pro 3] The evaluation fully considers various uniformity metrics, sampling strategies, and the chosen of q.\n\n[Con 1] I am confused about the difference between the proposed method and Newton's method. It would be helpful for the authors to clarify the limitation of the objective function (for example, the objective function should be second-order derivable).\n\n[Con 2] The authors note that \"It is not straightforward to simply apply FedAvg to problem (2) when q>0, as the F_{k}^{q+1} term prevents the use of local SGD.\" I found it difficult for me to follow this argument. Is it relevant to the parameter q? Given the communication-efficiency improvement in Section 3.3, few explanations are provided for the main improvement over previous work. Is it because of the local updating? Otherwise, more details about the convergence rate will strengthen the submission.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript proposes and analyzes a federated learning procedure with more uniform performance across devices, motivated as resulting in a fairer performance distribution. The resulting algorithm is tunable in terms of the fairness-performance tradeoff and is evaluated on a variety of datasets.

The reviewers and AC agree that the problem studied is timely and interesting, as there is limited work on fairness in federated learning. However, this manuscript also received quite divergent reviews, resulting from differences in opinion about the novelty and clarity of the conceptual and empirical results. In reviews and discussion, the reviewers noted insufficient justification of the approach and results, particularly in terms of broad empirical evaluation, and sensitivity of the results to misestimation of various constants. In the opinion of the AC, while the paper can be much improved, it seems to be technically correct, and the results are of sufficiently broad interest to consider publication.
Decision: Accept (Poster)