Exp-$\alpha$: Beyond Proportional Aggregation in Federated Learning
Authors: Junjiao Tian
Xiaoliang Dai
Chih-Yao Ma
Zecheng He
Yen-Cheng Liu
Sayan Ghosh
Peter Vajda
Anqi Wu
Zsolt Kira
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning

Abstract: Federated Learning (FL) is a distributed learning paradigm, which computes gradients of a model locally on different clients and aggregates the updates to construct a new model collectively. Typically, the updates from local clients are aggregated with weights proportional to the size of clients' local datasets. In practice, clients have different local datasets suffering from data heterogeneity, such as imbalance. Although proportional aggregation still theoretically converges to the global optimum, it is provably slower when non-IID data is present (under convexity assumptions), the effect of which is exacerbated in practice. We posit that this analysis ignores convergence rate, which is especially important under such settings in the more realistic non-convex real world.  To account for this, we analyze a generic and time-varying aggregation strategy to reveal a surprising trade-off between convergence rate and convergence error under convexity assumptions. Inspired by the theory, we propose a new aggregation strategy, Exp-$\alpha$, which weights clients differently based on their severity of data heterogeneity. It achieves stronger convergence rates at the theoretical cost of a non-vanishing convergence error. Through a series of controlled experiments, we empirically demonstrate the superior convergence behavior (both in terms of rate and, in practice, even error) of the proposed aggregation on three types of data heterogeneity: imbalance, label-flipping, and domain shift when combined with existing FL algorithms. For example, on our imbalance benchmark, Exp-$\alpha$, combined with FedAvg, achieves a relative $12\%$ increase in convergence rate and a relative $3\%$ reduction in error across four FL communication settings. 

Under review as a conference paper at ICLR 2023
EXP-o: BEYOND PROPORTIONAL AGGREGATION IN FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Federated Learning (FL) is distributed learning paradigm, which computes gradients of a model locally on different clients and aggregates the updates to construct new model collectively. Typically, the updates from local clients are aggregated with weights proportional to the size of clients' local datasets. In practice, clients have different local datasets suffering from data heterogeneity, such as imbalance. Although proportional aggregation still theoretically con- verges the global optimum. provably slower when non-IID data present (under convexity assumptions), the effect of which is exacerbated in practice. We posit that this analysis ignores convergence rate, which is especially important under such settings in the more realistic non-convex real world. To account for this, we analyze a generic and time-varying aggregation strategy to reveal surprising trude-off' between convergence rate and convergence error under convexity assumptions. Inspired by the theory, we propose a new aggregation strategy, Exp-a, which weights clients differently based their severity of data heterogeneity. achieves stronger convergence rates at the theoretical cost of non-vanishing convergence error. Through series of controlled experiments, we empirically demonstrate the superior convergence behavior (both in terms of rate and, in practice, even error) of the proposed aggregation on three types of data heterogeneity: imbalance, label-flippigg and domain shift when combined with existing FL algorithms. For example, on our imbalance benchmark. Exp-a. combined with FedAvg, achieves relative 12% increase in convergence rate and a relative 3% reduction in error across four FL communication settings.
INTRODUCTION
Federated Learning (FL) (McMahan et al., 2017) a decentralized approach for learning a model on distributed data to preserve data privacy. Because data reside clients and never transmitted to a central server, privacy is preserved. However, data on local clients are often correlated with their demographics and preferences. This makes training data highly non-lllD or heterogeneous, (Wang et al., 2021; Zhang et al., 2021; Kairouz et al., 2021), containing label imbalance, noisy labels (e.g. labei-nlipping,, or domain shift. This can significantly impact model's performance and specifically convergence rates (Zhao et al., 2018; 8 Li et al., 2019). To tackle the issue of data heterogeneity, the majority of federated learning have focused on improving the local optimization (Zhao al., 2018: Shoham et al., 2019; Karimireddy et al., 2020; Zhang et al., 2020; Acar et al., 2021) and the global optimization (Hsu et al., 2019; Reddi et al., 2020) objectives in federated learning pipeline. Few papers have paid attention to the other aspects of federated learning, such as client selection (Cho al., 2020) and model aggregation (Chen al., 2020; Wang et al., 2020).
Most existing methods use proportional aggregation (McMahan et al., 2017), whose aggregation weights are proportional to the size local dataset. Although proportional aggregation still theoret- ically converges when non-lID data is present under convexity assumptions, we posit that this anal- ysis ignores convergence rate, which is especially important under such settings in the real world, because proportional aggregation assumes equal importance of all samples. Intuitively, non-IlI data makes the equal importance property guestionable since imbalanced data can bias predictions towards majority classes, and noise or domain shift slow down convergence.

---

Under review as a conference paper at ICLR 2023
To study this, we start by introducing the proportional aggregation strategy and discussing its mer- its: equal importance and asymptotic convergence. Following prior works (Wang et al., 2021; Rei- sizadeh et al., 2020; Yuan et al., 2021), we define the federated global objective F(W) of the server as a weighted sum of N local objectives F((W) in Eq. 1. F()) denotes generic loss/risk function.
Definition 1
F(W) Σ (WB(W) where ((W Pg [s(W:))
Ei=1 P. = are the aggregation weights, W E Rd denotes the global model and & is a sample from the local data distribution P. Usually in the distributed learning (Stich, 2018) and federated learning (Li et al., 2019) literature, the weights are set to be proportional to the number of samples on client denoted as P: د
E,7' where |E,|" is the size of local dataset E This weighting
scheme has an intuitive interpretation, i.c., the global data can be equivalently seen as the union of local datasets, and the federated global objective is equivalent in expectation what one would optimize centrally if data are sampled randomly from it. Proportional aggregation is then used to compute an unbiased update to Eq. 1. In summary, proportional aggregation is a statistically sound strategy, giving all data points equal importance and providing axymptolic convergence to hypo- thetical centralized objective, i.e., achieving zero-error eventually. However, a recent survey calls these properties into question (Wang et al., 2021). In the real world, the defining characteristics of proportional aggregation, particularly equal importance and asymptotic convergence, can be less well justified. The property of equal importance of all participating data can be less desirable when data heterogeneity is severe. For example, even though the convergence of using proportional ag- gregatoin (with zero-error under convex settings) with non-IID clients is guaranteed, it is provably slower (Li et al., 2019), and with data poisoning (such as label-flipping) it can be even unstable (Xie al., 2019; Jebreel et al., 2022). This is exacerbated by the limited communication rounds in FL, making the asymptotic convergence property less relevant since asymptotic convergence can only be achieved under the assumption of unlimited communication. As a result, two algorithms with comparable asymptotic convergence can perform quite differently in practice ( (Wang et al., 2021).
In this paper, we study generic and time-varying aggregation strategy, En = where o is the weight for client at time I, as opposed to proportional aggregation. A theoretical study of this strategy reveals surprising trade-off between convergence rate and convergence error, allowing us to make more explicit what proportional aggregation favors and to develop new algorithms that make different trade-offs. For example, proportional aggregation, when instantiated in our frame- work as a special case, is shown to favor convergence error at the cost of convergence rate. More specifically, we start from theoretical analysis on the convergence of FedAvg (McMahan et al., 2017), a prototypical FL algorithm, while allowing the aggregation weights to change over time. The resultant convergence bound in this more generic setting reveals a family of aggregation strate- gies that 1) improves convergence rate but 2) leaves a theoretically non- non-vanishing error w.r.t the proportionally weighted federated objective (Eq. 1). Subsequently, we propose a specific aggrega- tion strategy in this family, Exp-a, which weights clients differently based on their severity of data heterogeneity and can achieve stronger convergence rates at the theoretical cost of non- non-shnishing convergence error. Intuitively, this strategy puts larger weights distribution to each other. Empirically, we go beyond theory to test its effectiveness on three major types of local data heterogeneity: imbalance (Zhao al., 201 8), label-flipping (Xie et al., 2019) and domain shift (Li et al., 2021). Our results suggest that an aggregation strategy with faster conver- gence rate be more important in practice than one with theoretically zero-error under the convex assumption; in practice, our method achieves both better rates and better errors, owing to the fact that practical settings are non-convex. For example, on our imbalance benchmark, Exp-ox, combined with FedAvg, achieves a relative 12% increase in convergence rate and a relative 3% reduction in error across four FL communication settings. To sum up, our contributions are:
clients sharing more similar data
We analyze the convergence of FedAvg with generic and time-varying aggregation strat- egy to reveal a trade-off between convergence rate and error under convexity assumptions, and elucidate properties of prior proportional aggregation strategies.
We use the notation| to denote the size of a set.
2

---

Under review as a conference paper at ICLR 2023
We propose new aggregation strategy, Exp-a, that trades convergence rate over emror under convexity assumptions. When applied to several existing FL algorithms in real world experiments, Exp-a demonstrates superior performance in both convergence rate and error over the widely used proportional aggregation on three types of data heterogeneity.
2 BACKGROUND AND RELATED WORKS
Federated learning (FI.) a distributed machine learning paradigm developed to preserve privacy while enabling continual development of an ML model private data (McMahan et al., 2017). FL generally consists of three stages: client selection, client update and server update. Most FL algorithms innovate one component of this algorithm.
Client Selection: At the beginning of round of communication (a global iteration), the current global model W E Rd is distributed to randomly sampled set of N local clients from large pool of candidates N,, sampled from a population distribution C supported on N. If N < [V] then this is called partial-parti pariiialpaatiiiiiiin... Most paper follows uniform client sampling strategy (Li al., 2019). However, a recent work (Cho et al., 2020) shows that a biased strategy can bring pratical improvement FL algorithms.
After receiving the global model, the clients optimize their copies of it indepen- dently on their own local data ç E E; PX(X, Y), where & represents an element in the set of local data E, on client sampled uniformly from the local data distribution P.. for specified E number of steps to arrive at different updated local models W
Client Update:
E E Rd for i E {1,...,N N). This is the most investigated stage in FL research due to its unique non-III (distribution shift) challenge (Zhao et al., 2018; Li et al., 2019). The vanilla FedAvg (McMahan et al., 2017) uses plain SGD updates, which can only handle mild non-IID data. Many followup works design regularization techniques to improve convergence under more severe distribution shift. Please see Appendix A. for an intro- duction to those methods. Our contribution is orthogonal to FL research in this category and can be combined. We will demonstrate this compatibility in our experiments (Sec. 4).
To complete this round of communication, the updated local models are sent back to the central server for aggregation, which yields the next global model. Server update can be split into two steps: aggregation and optimization (Reddi et al., 2020). Our work focuses on the aggregation step in the server update stage. Specifically, aggregation refers to how gradients are combined and optimization refers to how the aggregated gradients are applied. Please see Appendix A.1 for an introduction FL algorithms with different server optimization techniques. Few have studied the aggregation step in server update. FOCUS (Chen et al., 2020) measures the performance of a local model on globally shared dataset and assigns an aggregation weight accordingly. However, the requirement of a global dataset that encompasses unknown local data distributions violates the privacy premise of FL. A recent work (Wang et al., 2020) discovered an implicit bias in aggregation when the number of local updates is different and proposed a mitigation strategy. This problem is orthogonal to our target on non-IID data and therefore, we keep the number of local updates the same on all clients in our experiments. Nonetheless, most existing works use proportional aggregation. Our contribution orthogonal and compatible to other innovations in the optimization step. We will demonstrate this compatibility in the experiment section (Sec. 4).
Server Update:
3 GOING BEYOND PROPORTIONAL AGGREGATION
Existing FL convergence analyses often assume proportional aggregation in their deviation (Li et al., 2019: Khaled et al., 2020). This strategy yields asymptotically zero-error convergence under convex settings. However, as we will show in this section, revisiting the convergence analysis with a generic, time-varying aggregation strategy reveals that by carefully designing the aggregation weights, one can theoretically trade off convergence rate over error. This section is organized as the following. Sec. 3.1 introduces several common assumptions FL convergence analysis and notations neces- sary to understand the theoretical results; Sec. 3.2 presents convergence bound with a generic and varying aggregation strategy; Sec. 3.3 discusses the trade-off between convergence rate and error with derived corollary; Finally, inspired by the corollary, Sec. 3.4 proposes a practical aggre- gation strategy, Exp-a, which demonstrates superior convergence behavior in terms of both rate and error on several benchmarks in Sec. 4.
3

---

Under review as a conference paper at ICLR 2023
Exp-a
"f
Virtual global model
Accessible global model
22
Client local model
t=
2
Client local model
Figure 1: Illustration of our proposed Exp-a (Sec. 3.4) with three local optimization steps, i.c. E = 3. and two clients. In this example, mhnchroizzaioo/commmnnettti steps t 0,3, 6. Exp- a calculates the aggregation weights based on the latest accessible global model and local models.
3.1 TIME- VARYING AGGREGATION: ASSUMPTIONS AND NOTATIONS
We first make common assumptions in FL convergence analysis.
Assumption The local objective functions Fi,...FN are p-sttrongly convex: F((W) F.(V) 2 (W- - VV" + I + -V12 VW, V.
Assumption? 2 The local objective functions, F Fi,..., FN are L-smooth functions: F.(W) - VIW vW, V
F((V) (W -W -VV
V.
Assumption Bounded local gradient variance, let & P, be sampled data point on client The variance of gradients on all devices is bounded: E| Vi("; VF:(W)) s of Vi E
{1, (1...,N). N).
Assumption 4 Bounded local gradients, let &. ~ P. be a sampled data point on client i. The squared norm of gradients on all devices are bounded: E|[ (.W": s G2 Vi E [1....,N]
In addition to the convex Assumption 2, Assumptions 1-4 are fairly common assumptions in non- convex optimization literature (Reddi et al., 2016; Ward al., 2020) and federated learning litera- ture (Li et al., 2019; Cho et al., 2020). There are other FL. works relaxing the above assumptions. For example, FedAdaGrad (Reddi et al., 2020) relaxes the convex assumptions and shows that the expected gradient goes to zero, thus converging to a stationary point with unknown error bound. While it's sufficient to demonstrate the hidden convergence dependency on aggregation weights un- der the current assumptions, extending our subsequent analysis to different FL assumptions can be an interesting future work.
We will utilize the method of virtual sequence (Stich, 2018) for the proof of the main theorem. Let In be the set of anndhronization/commmiiccac steps, such that Ig = {n x Ein = 0, 0,..2, where E. denotes the number of local update iterations. The virtual sequence W++1 is defined as:
W
Σ
N
W++1
where
W
V i
if 1 & IE if 1 E IE
(2)
E
1=1
where pt 2 0 and E ++1 1 is the time-varying aggregation weight, and W W. W V denotes the local model i optimization step t. In reality, we only have access to W when t ++1 E Ig. i.e., time of actual synchronization. When this happens, we write W where E Iz. We provide a graphical illustration of the virtual sequence Fig. 1, which also features our proposed method, Exp-o. Furthermore, let W be the optimal solution to the federated global objective in Eq. ie.. W arg minw F F(W) arg minw ΣN (WF,, and W: be the optimal solution to a client's data distribution, i.e., W = arg minw F.(W).
3.2 TIME-VARYING AGGREGATION: CONSERVATIVE ERROR BOUND
Taking into account of generic and time-varying aggregation weights, p/: present the following theorem for the FedAvg algorithm (McMahan et al., 2017), a prototypical FL algorithm that uses vanilla SGD for local and global updates and proportional aggregation in the original work.
4

---

Under review as a conference paper at ICLR 2023
Theorem Assume Assumptions 1- 4 hold and H, di G be defined therein. Choose y max t and the learning rate 7 u(*+1) and T E Ig. Then FedAvg using SGD with full device participa-
tion and a generic, time-varying aggregation weights
Σ
P
= 1 satisfies
L
2B
L - (T
[[F(WT) P(W") <
Du
+
(T-
7 7
n2a
vansshing
vanishing
where Do | - 1 B = max ( (E (0f ( + 8(B G)G² + 6LΩ, r = max, E EE 1+1 (F.(W') (((W)) and 12 min, Σ (F((") F 2 O.
F.(W
We provide a complete proof of the main theorem A.9. The convergence bound in Thm. has two outstanding components, a vanishing term decreasing over time and a non-vanishing term. The vanishing term goes to zero with time and controls convergence rate; the non-vanishing term does not decrease over time and results in non-zero error after convergence. The convergence result is consistent with convergence bound using proportional aggregation (Li et al., 2019). Specifically, we can show (Appendix A.13) that if p = Pi = د E,l' then 52 = r- = Σ (:(F((
)))))), and the non-vanishing error is zero. This demonstrate that proportional aggregation, special case of our more general analysis, favors convergence error at the cost of convergence rate.
3.3 TIME- VARYING AGGREGATION: TRADE-OFF BETWEEN SPEED AND ERROR
From Thm. 1, we observe that FedAvg with generic varying weighing converges at rate of
N
O 5 T
+ O - Q). where Ω = min
Σ (F((W)) - F(W))))
i=1
The quantity Ω controls the convergence rate and the non-vanishing error. The intuitive way to improve the convergence rate to design strategy which gives a small Ωt Let Upr denote the quantity Ω defined by proportional aggregation, i.e., 2pr - min, E (:FF((W)) - F)(W))), where P: = Σy " Specifically, if the goal to improve over proportional aggregation, then the proposed aggregation strategy should lead to an Z2 smaller than 2pp. Upon close examination of Z in Thm. 1, one can expect that the key lies in choosing the aggregation weight of according the relative magnitude of the quantity 0 & F (W") - F:W);) for all E ... To this end, we provide the following corollary formally justify the intuition. We show that with specific choice
E,
of p 1+1 one can achieve Ω < 0pr-
Corollary 1.1 Assume
NE. E. (F(W') F((W))) are arranged in decreasing order, i.e., NE++
EN E (F(W") R(W:)) Z Ej |,
NE
(FHi(W") F:+1(W:: (Wi+1)) If we choose
N N
NEI ((W:)-F(WV)
V1.
E
|
where U(+) 2 is a non-decreasing function, then Ω S 2pr.
A detailed proof is provided in Appendix A.11. In Corollary 1.1, W is the virtual global model (Eq. 2) at the previous step and W is the optimal local model for client Therefore, the quantity 2 (WW)) - F (W;) captures the performance difference between the closest virtual global model and the optimal local model on client i. Intuitively, one would expect that a client with more severe distribution shift will result in larger Ω since the current virtual global model should not work well on this severely shifted distribution, resulting in larger discrepancy between F; (W) and F.(W;) In other words, the aggregation strategy in Corollary 1.I puts smaller weights on more severely shifted clients based on current performance difference. Consequently, it is reasonable to expect trade off between convergence speed and convergence error depending on how aggressively the algorithm nown-weight shifted clients. In our experiments, to avoid the compound issue of update bias due to unequal number of local updates (Wang et al., 2020), deliberately keep the size of local datasets equal, i.e., | = |Eyl- Therefore NEE
18,1
5

---

Under review as a conference paper at ICLR 2023
3.4 VARYING AGGREGATION: THE EXPONENTIAL FUNCTIONS
One family of functions that satisfies (+() 2 0 and non-decreasing, is the exponential functions. We will use this the paramterization for our empirical investigation. However, at synchronization step T E Zg. according to Thm. I and Corollary 1.1, we need to evaluate F, F((W (WT-I) and (((")) to calculate the aggregation weights. This is not realistic, however; first, we only have access to the virtual global model at f = T E. i.c., the model from the previous synchronization step since the current one has yet to be calculated. Therefore, the closest available global model is W Second, in the most common setting. FL algorithms only optimize a local model for fixed number of epochs and do not train to convergence'. Thus, the closest approximation to F:WW)) is the current local model after E' local updates from the previous synchronization, P: (W""". A graphical illustration is provided in Fig. 1. For subsequent investigation, we use the following approximation,
F((W.) F.(WTEE)
P x exp
Ox
where a is a temperature hyperparameter to control the strength of the proportionality. As a + oo, the strength of proportionality decreases, e.g., in the limit, Pt - 1. Intuitively, a small increases the concentration of p; and a large decreases the concentration and makes the weights more evenly spread. In subsequent sections, we term this family of aggregation strategy as the Exp-a method. We provide a detailed algorithm description of Exp-o and discussion on computation in Appendix A.2.
4 EXPERIMENTS
Overview. In this section, we present experiments to test the capability of the Exp-a strategy be- yond theory. To this end, we surveyed existing literature and identified three dominant data hetero- geneity types: imbalance (Zhao et al., 2018), label-flipping (Xie et al., 2019) and domain shift (Li al., 2021). Each types of heterogeneity brings specific challenge to an aggregation strategy. Specifically, imbalanced clients require the aggregation to be adaptive to the severity of imbalance; label-fipping requires the aggregation to block contributions from label-flipped clients; domain shift requires the aggregation to not disregard any clients since all domains should contribute.
Datasets. To benchmark on different data heterogeneity, we use popular datasets in FL re- search (Zhao et al., 2018; Li et al., 2021; Yuan et al., 2021). For imbalance, we adopt the popular Imbalanced CIFARIO (Cao et al., 2019) setting in the imbalanced classification task. For label- flipping experiments, we use CIFARIO 10 with randomly flipped labels (Xie et al., 2019; Jebreel et al., 2022). For domain shift experiments, following Li et al. (2021), we use Digits (Li et al., 2021), Effice-Clatech10 (Gong et al., 2012), and DomainNet (Peng et al., 2019), each of which consists of a range of different domains with shared labels. Specifically, Digits has five domains, Office- Clatech 10 has four domains, and DomainNet has six domains. Please see Appendix A.4 for details.
We compare different methods using the accuracy achieved at both the halfway and full global training iterations (McMahan et al., 2017). Higher accuracy means lower converged error ing the same number of optimization steps. We also report the global iterations required to achieve X performance (given rithm converges to the same performance using fewer rounds of global communications and has higher convergence rate. We separate datasets into train, validation, and test splits, and report both validation and test accuracy if applicable in our experiments.
Metrics.
"Accæ") (MeMahan al., 2017). Lower "Acca" means that the algo-
Backbone Algorithms. Exp-o an aggregation strategy and can plug into most existing FL meth- ods. We select five representative baselines from different categories as the backbone algorithm: FedAvg (McMahan et al., 2017), FedAvgM (Hsu et al., 2019), FedAdam (Reddi al., 2020), Fed- Prox (Zhao et al., 2018), and FedFor (Tian et al., 2022). Specifically, FedAvgM and FedAdam use different server-side momentum while FedProx and FedFor have different client-side regularization. For domain shift experiments, 2021). 1). For all experiments, we assume a large amount of available clients and sample a fraction of them to participate in each round of communication. This corresponds to the most practical FL setting: cross-device FL with partial participation (Kairouz et al., 2021). For different experiments, use different neural network architectures. Please refer the Appendix A.3 for more details.
include the SOTA personalized FL alogorithm FedBN (Li et al.,
"ome FI. algorithms require exact convergence local model, e.g., FedPD) (Zhang al., 2020).

---

Under review as a conference paper at ICLR 2023
4.1 IMBALANCE EXPERIMENTS
For imbalance experiments, we use the Imbalanced CIFARIO (Cao et al., 2019) dataset created with an artificial exponential imbalance among classes. To create this exponential imbalance, we specify a variable imbalance ratio. For example, an imbalance ratio of 0.01 means that the ratio between the number of samples in the smallest class and the largest class 0.01.
Table I: Compatibility Experiments on Imbalanced CIFAR. Results are averaged over 3 runs. E the number of local iterations and refers to the number of global iterations. A complete table with standard deviation is available at A.5.
E= 20
E
40
5 = 160
Backbone
Stralegyy
= 200
== 400
Todt
apo10]
[/= 100 T
[= 200
Test
= 25
(= 50
Tost 1
FodAvg
Propto.
64.60
55.77
64.25
7.00
63.55
Exp-o
38.00
S8.34
67.19
66.86
19.67
57.20
66.12
65.89
5.33
57.77
66.12
66.09
FedFrox
Propto
47.33
56.53
64.86
64.57
25.00
55.92
63.44
64.98
7.33
55.52
54.06
63
Exp-o
36,00
$7.99
66.74
68.54
22.00
$7.41
66.22
65.83
6.33
56.55
66,05
65.63
FedForr
Propto.
37.67
60:80
69.62
16.33
64.71
74.04
73.25
6.33
57.74
67.02
66.71
Exp-o
34.67
62.15
70.48
70.04
16.67
64.47
74.44
73.90
5.33
69.34
69.06
FedAugM
Propto.
26.67
63.43
71.36
70.72
16.33
62. 03.38
70:55
70.28
8.00
59:25
69.17
68.40
Exp-o
25.00
65.04
72.65
72.21
13.00
64.15
72.69
72.55
6.00
61.08
69.61
69.52
FedAdam
Propto.
Exp-
22.33
18.67
72.67
74.16
79.38
79.69
78.87
14.67
14.33
67.59
69.26
76.41
76.49
76.15
11.33
10.00
55.05
65.37
64.98
65.20
64.32
Compatibility to other FL algorithms. To mimic the real world situation of varying imbalance, sample a batch of 10 clients for each round of communication and each client is created using an imbalance ratio sampled randomly from the set of ratios (1.0, 0.5, 0.1, 0.05, 0.01, 0.005, 0.001} covering gradual increase of severity of imbalance from balanced, moderately imbalanced and extremely imbalanced datasets. At the beginning of each round, we re-sample the clients and their imbalance ratios. We benchmark the performance of Exp-a and proportional aggregation in six FL algorithms under four communication-compee computation configurations with a trade-off between the number of global iterations (denoted as () and local update iterations (denoted as F) in Tab. 1. More local update (larger F)) iterations lead to more severe weight divergence (Li et al., 2019) but with potential global communication savings (smaller t). Here, we report the number of steps to reach 40% accuracy (denoted acc40), half-time, final validation accuracy, and the final test accuracy.
Moreover, we fix the temperature hyperparameter a = 0.2, chosen by a grid search on a validation set using FedAAg and FedAvgM with (t 100, E = 80} and an imbalance ratio of 0.001. Please Appendix A.5 for the details on effects of a. We observe that Exp-o brings improvement to all FL algorithms considered Specifically, most algorithms using Exp-a reach 40% accuracy with fewer rounds of global steps than using proportional aggregation, e.g., 12.3% reduction in number of steps using FedAvg with E- 20. This shows that Exp-a improves convergence rate over proportional aggregation. Furthermore, all algorithm using Exp-a reach higher converged accuracy, thus lower error, than using proportional aggregation. This shows that in real world settings, where function are non-convex, faster convergence speed can potentially lead to lower error, in contrast to the speed and error trade-off in theoretical convergence analysis in convex settings.
Adaptability to Severity of Imbalance. As a dynamic algorithm, Exp-a should weight each sample differently based on the severity of imbalance. To provide more insights into the adaptability to the degree of imbalance, we now use more controlled sampling strategies and imbalance ratios. Instead of sampling clients with random imbalance ratio as in the previous experiment, we designate a few combinations of imbalance configurations. For example, we use the notation (1.0x 4, 0.01 x3, 0.1 x 3} to denote a composition of four balanced clients, three imbalanced clients with an imbalance ratio of 0.01 and three imbalanced clients with an imbalance ratio of 0.1. Specifically, we visualize the aggregation weights of Exp-a and compare its performance against that of the proportional aggregation in four imbalance configurations. Again, we sample ten clients at the beginning of each round however with different imbalance configurations. The hyperparameter a is set to 0.2 and the FL setting {t 400, E 20). As we can see from Fig. 2a, Exp-a adapts to different imbalance configurations. For example, as client becomes less imbalanced, it receives higher
Exp-aa can be applied to other FL algorithms such as SCAFFOLD (Karimireddy et al., 2020), Fed- Dyn (Acar et al., 2021). However, these algorithms not compatible with the current benchmark because they are stateful algorithms and perform poorly in the cross-device setting (Xu et al., 2021).
7

---

Under review as a conference paper at ICLR 2023
292v0)
11. 2x-1
1/5 relo:
cormistien
Expie: 68.11 11
Proport: 02 70
Rap-e: 66.30 Proport:
Exprs 08.44
Exp-e: 24.34
Exp a:: 66.47
weight
weights
Expai Exp-e:
Proport:: 44.52
66.05 Proport: 45.64
Proport:: 50.21
Proport: 58.05
0:32
(a) Imbalance Adaptability Experiments
(b) Flip Adaptability Experiments
Figure 2: We visualize the average aggregate weights and report test accuracy of Exp-a for different imbalance and flip configurations. Exp-a always assigns smaller weight to more shifted clients. Fedavg is used as the backbone FL. algorithm and results are averaged over three runs.
weight. The balanced clients always have the highest aggregation weights. Also, expected, Exp-a shows more performance improvement when imbalance is more severe. In the case, when all clients are balanced, Exp-a assign roughly equal weights to all clients with marginal variation due to stochasticity in sampling. Experiments with IID clients are provided in Appendix A.5. As expected, when clients have balanced datasets, Exp-a performs just well proportional aggregation.
4.2 LABEL FLIPPING EXPERIMENTS
For label flipping experiments, we use CIFARIO as the dataset. To control the extend of label flipping, we define corruption rate and Slip ratio. For example, corruption rate of 1/3 means that with 1 /3 chance, client has flipped labels and flip ratio of 1.0 means that all classes are incorrectly labeled and 0.5 means that half of the classes incorrectly labeled. The number of classes whose labels are flipped is determined by the flip ratio multiplied by the number of classes.
Table 2: Compatibility Experiments on CIFAR with flipped clients. Results are averaged over 3 runs. E is the number of local iterations and & refers to the number of global iterations. complete table with standard deviation is available at A.6.
E 20
E 40
E
160
Backhone
Strategy
scc40)
200
400
Test7
acc40)
100
200
Test"
acc40.
25
50
Test
FodAvg
Propto.
Expro
36.33
58.39
59.55
66.97
67.01
18.33
$7.19
65.78
66.21
5.33
58.34
66.45
66.24
FedProx
Propto.
59.67
52.25
60.08
60.27
33.67
53.03
61.00
60.83
12.33
$1.11
59.71
59.71
Exp-n
34,33
58.95
67.14
66,51
19.67
58.31
66.74
66.75
5,00
58.65
66.71
66.60
Propto.
53.00
9.67
53.32
Exp-o
28.00
62.50
70.89
70.39
15.33
64.50
73.02
72.57
5.33
60.56
70.18
69.70
FodAvgM
Propto.
Exp-o
22.67
39.33
56.11
65.95
64.29
73,82
64.13
73.45
28.00
13.00
64.93
56.95
65.76
73.28
72.40
65.82
10.67
6,00
54.45
62.66
61.40
70.97
61.05
70.62
FedAdam
Propto.
Exp-o
30.00
20.00
61.61
80.17
71.72
71.51
24.33
57.46
77.46
64.37
64.00
18.67
54.22
43.53
57.27
57.07
Compatibility to other FL algorithms. Similar to the imbalance experiments, we benchmark Exp- and proportional aggregation using six different FL backbone algorithms. In this experiment, we keep a = 0.2, chosen by a grid search on a validation set using FedAvg and FedAvgM with a corruption rate of 1/3, a flip ratio of 1.0 and {t = 100, for the effects of a. At the beginning of each round, we sample six clients with different data composition and each client has probability of 1/3 being corrupted with flip ratio of 1.0, meaning that all its labels are incorrect. Therefore, the algorithm is challenged with a different flipping pattern each time. We report the number of global steps to reach 40% accuracy, half-time, final time validation accuracy and final test accuracy across four federated learning configurations in Tab. 2. In all experiments, Exp-a brings significant improvements over proportional aggregation. This demonstrates that 1) label flipping is detrimental to federated learning and 2) Exp-a greatly alleviate its negative affect.
80). Please see Appendix A.6
Adaptability to Severity of Label Flipping. In this experiment, study how Exp-a responds to partially flipped clients. Specifically, we keep a = 0.2 and vary the flip ratio E {1.0, 0.13. meaning corrupted client can either have all labels wrong or just labels for one class incorrect. Furthermore,
8

---

Under review as a conference paper at ICLR 2023
instead of sampling, we use a deterministic corruption rate E 1/33. This means that the beginning of each round of communication, we sample six clients and four or two clients out of the six clients will be corrupted, corresponding to 2/3 or 1/3 comuppiion rate respectively. The hyperparameter a is set to 0.2 and the FI. setting is {t = 400, F = 20). In Fig. 2b, we present four configurations covering the aforementioned variables of interest. We notice that 1) Exp-a outperforms proportional aggregation in all configurations; 2) Exp-a differentiates between clients with different level of label flipping, e.g., assigns higher weights to flipped clients where only single class is incorrect than to those where all classes are incorrect. Furthermore, Exp-a works when the number of flipped clients is majority and minority.
4.3 DOMAIN SHIFT EXPERIMENTS
Table 3: Domain Shift Experiments on Digits, Office-Clatech11 and DomainNet. Results are averaged over 3 runs. Each benchmark has several domains. We use shorthand notation in this table.
etall, 2011)
UfficeCCltechie (Coong
Domannee (Pheg 2019)
Bacitonee
Startgy
MINITT
SVRRX
USPS
SD
[M:M
C
D
W
Arg.
K
S
Q
Agg.
Med//g
Phopoto
Esper
95.64
61.33
61.18
05.38
95.30
81:77
81.82
18.71
75.26
$1.89
39.03
57.47
$1.50
30.51
64.58
65.63
37.40
$6.44
02.83
63.44
72.37
73.44
64.13
68.05
39,08
38.81
70.01
69:57
70.76
09.31
59.23
60.30
6229
63.28
FeIBN
Propeto
93.75
93.79
80,97
73.77
$4.47
72.14
Unlike in the previous two challenges, for domain shift, a federated learning algorithm needs to con- sider all clients despite their data heterogeneity, We benchmark Exp-a and proportional aggregation on three domain shift benchmarks: Digits, Office, and DomainNet. Each benchmark consists of several domains with a shared label space. Specifically, Digits consists of five ligit-like datasets; Office-Caltech10 has four domains and DomainNet has six domains. Please see Appendix A.4 for detailed description. We distribute the data from each domain to a client separately, such that each client has a distinct data distribution with domain shift. FedAvg (McMahan et al., 2017) and FedBN (Li et al., 2021) are used as the backbone FL algorithms. We report test accuracy of each domain and cross-domain average for each benchmark under the FL setting {t = 400, E' = 16) in Tab. 3. Different a has been used for each dataset, chosen by grid search using the validation set. Please see Appendix A.7 for the discussion on effects of a. We observe that Exp-o leads to similar performance as proportional aggregation most cases. This shows that Exp-a incorporates all local data despite the existence of domain shifts among clients. Furthermore, Exp-a even brings noticeable improvement in some cases For example, Exp-a improves FedAvg with proportional aggregation on Office-Clatech10 by a relatively 4% on average across four domains. Upon close examination, the improvement mainly comes from the Webcam (W) domain (relatively 10% im- provement). The Webcam domain is the best performing domain already when using proportional aggregation, indicating that benefits the most from federated learning across the four domains. Exp-a emphasizes it further by assigning the Webcam domain the largest aggregation weight. For this particular experiment, the average aggregation weights over the entire training trajectory for Amazon (A), Caltech (C), DSLR (D) and Webcam (W) are (0.19, 0.26, 0.22, 0.34). While Amazon (A) received the smallest average aggregation weight, this did not deteriorate the performance of Exp-a on this domain but rather improved by a relative 3%.
CONCLUSION
While proportional aggregation enjoys several theoretical advantages, e.g., equal importance and asymptotic convergence, a fixed client weighting is less sensible under non-lll) settings. In this pa- per, we start out by removing the assumption of proportional aggregation and derive a convergence bound using generic and time-varying aggregation strategy. This analysis reveals surprising trade-off between convergence speed and error under convexity assumptions. The analysis moti- vates family of aggregation strategies, which prioritize convergence speed and weight samples dynamically. Consequently, we propose a new aggregation strategy, Exp-a, from this family. Our extensive experiments on three types of data heterogeneity demonstrates its superior performance and robustness, and compatibility to existing algorithm albeit the existence of non-zero error in the- ory. More importantly, the theoretical analysis opens new direction to study aggregation strategy to focus on convergence speed and robustness in future works.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We include a code repository to reproduce the results on imbalanced CIFARIO reported in Tab. 1. Specifically, the codebase includes an implementation of FedAvg (McMahan al., 2017) with the original proportional aggregation and the proposed Exp-a aggregation strategy. Readers can repro- duce results reported in the first row of Tab. The code repository has readme file with necessary instructions to install environment and run experiments. The code is written to run on single GPU.
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. arXiv preprint arXiv:2/ / 11.0466,, 2021.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label-distibutton-awaar margin loss. Advances in neural information processing systems, 32, 2019.
Yiqiang Chen, Xiaodong Yang, Xin Qin, Han Yu, Biao Chen, and Zhiqi Shen. Focus: Dealing with label quality disparity in federated learning. arXiv preprint 1rXiv:2001.11359, 2020.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection federated learning: Convergence analysis and power-of-choice selection strategies. arXiv preprint arXiv:2010.01244; 2020.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference on machine learning, pp. 1180-1189 PMLR, 2015.
Boqing Gong, Yuan Shi, Fei Sha, and Kristen Grauman. Geodesic flow kemel for unsupervised domain adaptation. In 2012 IEEE conference on computer vision and pattern recognition, pp. 2066-2073. IEEE, 2012.
Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. 2007.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint
2019.
Jonathan J. Hull. A database for handwritten text recognition research. IEEE Transactions on pattern analysis and machine intelligence, 16(5):550-554, 1994.
Najeeb Moharram Jebreel, Josep Domingo-Ferrer, David Sánchez, and Alberto Blanco-Justicia. De- fending against the fabe-ffipping attack in federated learning. arXiv preprint arXiv:2207.01982. 2022.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-200, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143, PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identi- cal and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519 4519-4529 4529. PMLR, 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFF, 86(11):227) (11()))228-22444 1998.
10

---

Under review as a conference paper at ICLR 2023
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv: UrXiv:190..02199 2019.
Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. Fedbn: Federated learning non-iid features via local batch normalization. arXiv preprint arXiv:2102.07623, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-cffiionn learning deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 1406-1415, 2019.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabás Póczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pp. 314 323. PMLR, 2016.
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. Advances in Neural Information Processing Sys- tems, 33:21554--21555, 2020.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In European conference on computer vision, pp. 213-226. Springer, 2010.
Neta Shoham, Tomer Avidor, Aviv Keren, Nadav Israel, Daniel Benditkis, Liron Mor- Yosef, and Itai Zeitak. Overcoming forgetting in federated learning on non-iid data. arXiv preprint arXiv:1910.000 2019.
Sebastian U Stich. Local sgd converges fast and communicates little. 1o55077885.09767, 2018
arXiv preprint
Junjiao Tian, James Smith, and Zsolt Kira. Fedfor: Stateless heterogeneous federated learning with first-order regularization. arXiv preprint, 2022.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective
inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:7611-7623, 2020.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan AI-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to feder- ated optimization. arXiv preprint arXiv:2107.06917, 2021.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. The Journal of Machine Learning Research, 21(1):9447-9066 2020.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance. In International Conference on Machine Learning, pp. 6893- 6901. PMIR, 2019.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint arXiv:2 10874, 2021.
Honglin Yuan, Warren Morningstar, Lin Ning, and Karan Singhal. What do we mean by generaliza- tion in federated learning? arXiv preprint arXiv:2 10. 14216, 2021.
Chen Zhang, Yu Xie, Hang Bai, Bin Yu, Weihong Li, and Yuan Gao. survey on federated learning. Knowledge-Baver Systems, 216:106777 106775, 2021.
11

---

Under review as a conference paper at ICLR 2023
Xinwei Zhang, Mingyi Hong. Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005.11412 2020.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv: 00582, 2018.
12

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 EXTENDED RELATED WORKS
Client Update. FedProx (Zhao et al., 2018) adds first order proximal term in the loss function; FedCurv (Shoham et al., 2019) and FedFor (Tian et al., 2022) use a second order and first order gradient regularization respectively; SCAFFOLD (Karimireddy et al., 2020) uses control-variate to align objective functions; FedPD (Zhang al., 2020/FeeDDyn (Acar et al., 2021) propose a dynamic regularization based on gradient consensus among clients.
Server Update. In the aggregation step, updated gradients are averaged in weighted man- ner to generate pseudo-gradients for the global model (Reddi et al., 2020). In the optimiza- tion step, methods differ how the 2017) directly uses SGD-like updates; FedAvgM (Hsu et al., 2019) adds Nesterov momentum and FedAdam/Fed Yogi (Reddi et al., 2020) generalizes more adaptive optimization techniques. Our method specifically tackles the less discussed aggregation step.
are applied. FedAvg (McMahan et al.,
A.2 ALGORITHM DESCRIPTION OF EXP-a
Algorithm 1: Exp-a.
Data: K clients with local data E; for i {I, K} are selected, temperature parameter Result: W
Initialize W
for T E {nE'n = 0... do
for {1 ...,, K) parallel do
F(WT CalculateRisk (E, WT)
W! TT+ ClientUpdatee W
e.g. FedProx FedPrxx Zhao et al. (2018)
F.WW
TTE] +- CaleulateRisk (E,, WT+B) [R(W." -.F:(W"))
Pi
T+E exp
> Eq.
end
VF(WT) Σ ΣK D3
T+E (W W!+E)
of FF
WT+E +- ServerUpdatc( (FT.T(
b c., FedAvgM Hsu et al. (2019)
end
In this section, we describe the Exp-a algorithm (Alg. 1). Exp-w is an aggregation algorithm, so it is compatible with most existing FL algorithms. Following the convention in (Reddi et al., 2020) and to describe the algorithm as general as possible, we abstract the client optimization and global optimization procedures ClieniUpdate and ServerUpdate. The majority of FL. algorithms differ in how they change these two components. Please refer to the related works section (Sec. 2) for brief discussion this. In experiments (Sec. 4), aim to demonstrate generality and compatibility of Exp-a in combination of innovations to these components. In Alg. 1, we implement CalculateRisk function to calculate the risk values. This a simple inference forward pass through the local dataset given specific model. The computation on the client side is fairly cheap, as it only requires two additional inference passes on the local data. During local training, FL algorithm needs to run epochs, each which has many more local iterations while the caleulation of risk only requires a simple forward pass without computing, storing and applying gradients. Therefore, the computation cost of CalculateRisk is only a small fraction the original computation cost.
pass, e.g., computing, storing and applying gradients for multiple
A.3 IMPLEMENTATION DETAILS
For CIFAR experiment in Sec. 4.1 and 4.2, we use ResNet20 (He et al., 2016). Specifically, the proper ResNet implementation for CIFAR10 (He et al., 2016). For Digits experiment Sec. 4.3, use custom CNN provided by Li et al. (2021). For Office and DomainNet experiment in Sec 4.3, we use ResNet18 (He et al., 2016). All models are trained with SGD, with no momentum and weight decays. We constant learning rate, i.e., no learning rate decay: CIFAR, Digits and Office 0.01
13

---

Under review as a conference paper at ICLR 2023
Table 4: Implementation Details for CIFARIO, Digits, Office and DomainNet.
Architecture
Optimizer
Learning
Batch
Steps per Eppcch
CIFAR1O
ResNe120 Tle al. (2016)
SGD
0.01
128
10
Office-Caltceh10
ResNett Ho (2016)
SGD
DomainNet
B Hi al. (2016)
SGD
0.05
64
4
Digits
DigiLModel et al. (2021)
SGD
0.01
64
and DomainNet 0.05. We summarize the statistics in Tab. 4. To avoid the issue of implicit bais due to difference in number of local updates (Wang et al., 2020), we keep the optimization steps per epoch constant on clients one experiment. Therefore, we also report the the number of steps in each local epoch in Tab. 4 for each dataset.
A.4 DATASET STATISTICS
Table 5: Train, validation and test splits for the Office-Caltech10 dataset.
Amazon
Caltech
DSLR
Webcum
Train
536
628
87
165
Val 230
270
38
71
Test 192
225
32
59
Table Train, validation and test splits for the DomainNet dataset.
Clipart
Painting
Infograph
Sketch
Quickdraw
Train
1472
1730
1838
3404
1549
2800
Val
631
742
788
1460
664
1200
Test
526
619
657
1217
554
1000
The Digits benchmark consists of SVHN (Netzer et al., 2011), USPS Hull (Hull, 1994), SynthDig- its (Ganin & Lempitsky, 2015) and MNIST-M (Ganin & Lempitsky, 2015), MNIST (LeCun et al., 1998); the DomainNet benchmark (Peng et al., 2019) has six domains. The Office-Caltech10 dataset (Gong et al., 2012) selects three doamins from Office-31 (Saenko et al., 2010), Amazon, DSLR and Webcam, and one domain from Caltech256 (Griffin al., 2007).
We split datasets into training, validation and test sets. In our experiments we report validation accuracy and test accuracy if applicable. We summarize the number of samples each split for Office, DomainNet and Digits in domain shift experiments in Tab. 5,Tab. and Tab. 7 respectively. For CIFAR 10 experiments, we have the following splits {train 35, 000, validation 15, 000, 10, 0003.
A.5 ADDITIONAL RESULTS FOR IMBALANCE EXPERIMENTS IN SEC 4.1
Effects of Alpha. In this experiment, we fix the imbalance ratio to 0.001, the number of local epochs 2 and the number of global iteration 200, and vary the hyperaparameter in Exp-a. Specifically, we sample different set of ten clients, among which four are balanced and six are imbalanced each time. So the total number available clients the number of rounds of communication multiplied by ten. We compare convergence performance of under different E {0.2, 1.0, 5.0, 25.0, 125.0) using two backbone FL. algorithms: FedAvg (MeMahan et al., 2017) and FedavgM (Hsu al., 2019) in Fig. 3. Compared to proportional aggregation, Exp-a with a proper selection of can consistently improve both convergence speed and converged performance. Specifically in this experiment, we noticed that smaller leads to better performance because smaller makes the weights more concentrated on the balanced clients. We use a = 0.2 the main paper in Sec. 4.1.
Effects of Local Steps and Degree of Heterogeneity. With increasing increasing number of local steps and increasing heterogeneity among clients, smaller a can do better. To demonstrate this present the following experiments. Specifically, At each round of global communication,
14

---

Under review as a conference paper at ICLR 2023
Table Train, validation and test splits for the Digits dataset.
MNIST
SVHN
USPS
SyothDitgits
MNIST-M
Train
892
892
892
892
892
Val
395
595
595
595
595
Test
14000
19858
1860
97791
14000
fedavg with Exp a Proportional Weighding Inibalanced CIFAR10
fedavom Exp and Proportional Weighting Imoolanced
66
6002
8-133.
popelted
120
Communccalion Roundss
Communi Rounds
(a) Fedavg
(b) Fedavgm
Figure 3: Convergence of Fedayg and Fedavgm using Exp-a and proportional aggregation on Im- balance CIFARI0. Results averaged over three runs. Imbalance ratio 0.001.
sample a different set clients, six of which are imbalanced. To show the effects of increasing local steps, run experiments across four communication settings with increasing number of local steps E E (20, 40, 80, 160} and a fixed imbalance ratio of 0.1. For each setting, we sweep a E (0.2, 5, 25, 125) In Tab. 8, show the test accuracy with different for each communication setting. We observe that increasing number of local steps requires smaller a.
To show the effects increasing heterogeneity, vary the imbalance ration in {0.1, 0.2, 0.3, 0.4, 0.5} with smaller number indicating more severe imbalance. Similarly, we sweep a {0.2, 1, 25, 125). Tab. we present test accuracy for each imbalance ratio with different a. We observe that more severe heterogeneity can benefit from smaller a.
fix the number of local steps be E' 160 and
Imbalance Compatibility Table with Standard Deviation. Here, we show the full table of Tab. with standard deviation Tab. 10.
Exp-o in IID Setting, In the main paper, explored Exp-a in non-IID settings, where clients are subject to different degrees imbalance. In this section, we present results comparing FedAvg using Exp-a and proportional aggregation under IID settings, where all clients have balanced data Tab. 11. As expected, Exp-a and proportional aggregation perform similarly.
fodave
Proportional Weighting on Flipped
fodaygm Exp and Proportional Weighting Fllpood
2402
sund
Beet wwildettoonnoo RecurrTy
1:1550 expetted
02
202 Communication
156
201
352
483
156
232
250
350
Communication
(a) Fedavg
(b) Fedavgm
Figure 4: Convergence of Fedavg and Fedavgm using Exp-a and proportional aggregation on Flipped CIFAR10. Results averaged over three Flip ratio 1.0.
15

---

Under review as a conference paper at ICLR 2023
Table 8: Effects of Local Steps with EXP-a. We use a fixed imbalance ratio of 0.1.
0.2
1.0
5.0
25.0
125.0
E=20
66.68
66.63
65.35
66.72
67.13
E=40
66.33
66.54
66.92
66.72
66.81
E=80
65.62
66.61
66.65
66.37
66.34
E= 160
66.50
66.36
65.53
65.53
64.78
Table 9: Effects of Heterogeneity with EXP-a. We sweep different imbalance ratio and use fixed number of local steps E = 160
Imbalance Ratio
0.2
1.0
5.0
25.0
125.0
0.1
66.50
66.36
65.53
65.53
64.78
0.2
67.19
66.83
66.84
66.71
66.22
0.3
67.07
66.38
66.40
66.96
65.85
67.48
68.79
66.64
66.71
0.5
65.75
66.18
66.16
66.63
67.33
A.6 ADDITIONAL RESULTS FOR LABEL FLIPPING EXPERIMENTS SEC. 4.2
Effects of Alpha. In this experiment, we fix the corruption rate to be 1/3, the flip ratio to be 1.0, i.e., all labels on a flipped client are incorrect, and vary the hyperparamter a. Specifically, we randomly sample data from training set to create six balanced clients. However, clients subject to fabel-flipping with a chance of 1/3. We compare convergence performance of under different a E (0.2, 5.0, 25.0, 125.0} using two backbone FL algorithms: fedavg (McMahan al., 2017) and fedavgm (Hsu et al., 2019) in Fig. 4. We notice that Exp-a with small a values provides significant convergence improvement compared proportional aggregation. This because a smaller a forces the aggregation algorithm to focus more on the clean clients. We use = 0.2 in the main paper in Sec. 4.2.
Label Flipping Compatibility Table with Standard Deviation. Here, we show the full table of Tab. with standard deviation Tab. 12.
A.7 ADDITIONAL RESULTS FOR DOMAIN SHIFT EXPERIMENTS SEC. 4.3
range of {0.2, 1, 5, 25, 125) the three domain shift benchmarks: Digits, Office-Caltechh and DomainNet. We report validation accuracy in Tab. 13. While there is not obvious trend which works the best, Exp-a with moderate
Effects of Alpha. In this section, sweep
a 2 outperforms proportional aggregation in most cases.
A.8 LEMMAS
To facilitate the derivation of the main convergence bound, will introduce some lemmas. Specif- ically, we will utilize the method of virtual sequence (Stich, 2018). Let Ig be the set of synchro- nization/communication steps, such that Ig [nEin 0, ..2) where E' denotes the number of local update iterations. We first introduce an intermediate notation denoting the update of a single step SGD update on a client:
V
W - V.:
where é ~ P. is sampled data point on the client at time
Depending on whether the current iteration a synchronization step, the local update on each client can be written the following, for t 0:
if + IE.
(5)
W!+1
ift+el E
(6)
where 1.-1 0 and MN P3 1 is the aggregation weight for client i, and W W
16

---

Under review as a conference paper at ICLR 2023
Table 10: Compatibility Experiments on Imbalanced CIFAR. Results are averaged over runs. E is the number of local iterations and t refers to the number of global iterations.
Baddhone
Straegy
[-
2001
Eu: 800
1
1ce1
100091
1-
1001
<=:
2141
1
Tees!
1 10.
J00
1
25
Teat
PodAng
Expor
36,00
+3.00
1:321
-3.41
58.34
10:36
-40.0
67.19
14:14
14:51
08.96
10.55
19.87
11:53
57.30
11.19
65.12
10.95
65.59
10.75
11.55
12.53
57.24
10.00
66.28
13.45
03:55
63.81
1..99
12.04
10.55
5333
87.77
11.0
66.13
-0.99
13.53
+0.67
66.10
10.08
FeiPoox
Pagai
Expux
62.31
36,00
47.33
-3115
56.33
20.00
65.54
64.50
64.57
003 10
15.55
15.00
22.00
37.41
55.90
1.148
05:44
08.22
64.98
63.83
68
11.53
1.
$7.90
54.97
-1.91
68.33
64.35
00.50
64.05
98.03
10.55
7.53
-0 03
38.30
55.55
86.85
20.4
63.91
63.03
Przso:
31.63
00.80
10.40
06.75
10.77
09.02
13:33
16.33
66.11
74.91
33.24
10.35
10.35
63.01
73.57
73.54
10024
0.51
$7.51
67.00
1846
69.71
1.52
13.17
10:72
10.00
13.35
10.22
10.00
142.6
10.87
10.04
10.55
143.40
Rageo
71.30
03.41
09-32
29.25
05.40
FeldugM
Expor
22,00
15.00
20.20
65884
24.16
72.63
72.21
20.45
13:00
11.00
21.06
64.15
72,99
20382
2107
12.55
11.53
9.30
20102
64.29
12.95
20.95
72.99
51.0
10.00
6,00
61.88
20.13
20096
6961
69.52
24.75
03:77
23.17
10.91
10333
13.38
103.5
11.00
11.24
10.15
21054
12.0
11.12
1:125
Pegio
18.47
1.88
20344
76.8
99.56
30:31
10.19
79
02.31
16.35
20.55
69.36
76886
10.20
20.30
76.49
21.35
18.6
14.00
02194
71.91
20.00
50000
71.0
31.55
11.35
01.28
5473
85.17
65.20
Table 11: Exp-o and Proportional Aggregation IID CIFAR. Results averaged over runs. E is the number of local iterations and refers to the number of global iterations.
Epecke
55
Stareay
Glimal Bor.
x0400
1
Icet
a0240)
[1:0 200
[cer]
80244)
11:0 99.1
190.1
[ 1911
10xt
Fedlig
Propto
Expo
24.55
=307
19:32
=1163
67:30
20.75
=0.58
18:67
211.3
19:75
210.35
67.64
20.34
$3.00
=1.00
9.10
-1.31
=0.75
14.11
20.37
07.50
07.30
=0.54
=5000
5.00
59.26
=1.28
67.45
-1.06
-0.90
65,95
67.68
Then we define virtual sequence
N w
W
In reality, we only have access to W++1 when t 1+1 1 E IE. We provide a graphical illus- tration of virtual sequence with E = 3 and two clients in Fig. 1. The virtual sequence W++ can be viewed as a virtual single step SGD update from W ie, W = W 7)9 where = EeEie of ++1 WWW. {t). Furthermore, the expected gradient is denoted as 9r = E[g]] = IN P (F. Note that Lemma 2 and Lemma 3 are adaptations of lemmas from Li et al. (2019) with the addition of time-varying aggregation weights. Deferred proof of lemmas is in A. 10.
Lemma 1 Results of one-step SGD the virtual sequence. With Assumption I and 2, if aL we can show that
N W < (1 - m//1 W 2 2
W
(+1 (1 W W!
i=1
+ 66 + 2m (T - 91) + n g: g: 11
where I = max EN + (F((*)) - E.())) and Ω = min, EN pt
Lemma Bounded variance. With assumption 3, it follows that
E Elg
1 <
(p 10 < max
Lemma Bounded divergence. With assumption 4, m) is non don-decregsing and mp S 27+ 0, it follows that
Vt 2
n w!I
+1 W
< 4E
17

---

Under review as a conference paper at ICLR 2023
Table 12: Compatibility Experiments on CIFAR with flipped clients. Results are averaged over 3 runs. E is the number of local iterations and t refers to the number of global iterations.
Boathene
Striligg/
[-
2001
9931
BCC
1101
1 2001
12s17
ACC
5
541
106
TeasT
g
1 50.
Too
Fallog
Pagen.
Expor
$3.06
36,33
23.09
22.11
58.39
13152
-0072
66.97
23.01
-2023
67.80
5:208
18.35
25.19
21.11
57.59
210.59
66.78
20.54
20.32
66.23
3:346
10.35
111.00
21.13
58.47
230.45
66.57
210.0
2:305
66.90
2.004
2.1 1.73
210.5
5.33
59.34
252.03
250.70
68-45
26000
=00.9
66.24
Rathox
Pergi
Expar
14.16
39.07
40.58
-0.70
52.25
-0.30
33.28
11.1
58.27
34.53
30.00
-1.50
53003
30.30
61.10
-0.28
14.03
3..00
18.07
51,30 11.56
27.47
311 80
06.15
40.20
00.41
33.05
10.14
331
12.05
1.53
1.00
4.300
20.11
840 00
66.71
99-21
=0.8
50:71
Phopss
51.01
11.51
01.11
51.43
25.07
96.77
06.19
56.49
06.11
9.67
53.52
63.24
Espor
20.0
1330
62.50
0.44
11599
10.50
18,39
1.75
15.35
18.55
0.53
10.17
0.331
11:00
64.21
18.35
76.16
11.5
73.76
13084
11.56
5.33
08.56
11.36
78.15
14.04
69.70
1066
Pogpto
33.19
-0:57
20.35
20.45
29.34
211.5
21.41
22.06
21.16
12.35
22.43
23.33
21
52.14
22.22
Popo
22.06
22,67
65.95
29.19
20.35
7382
20.75
73.45
11.00
13.00
20.37
64333
73.38
20.35
72.40
$.33
24161
64.74
21.30
7306
72.46
25.50
21.00
5,00
20.62
02.66
24.77
7837
2008
7843
PodAdan
Phopos
Expa
24.36
122.5
30.00
-0.31
74.55
61.61
+0.8
1044
71.22
-094
11.51
-041
3306
11.53
26.35
-102
57.46
20.36
10.35
64.37
-100
14.00
-004
22.53
11.00
22.35
52,02
10.11
30.00
+1.32
61.96
10:35
+127
61.55
11.03
25.51
11:55
18.67
42.00
12.04
43.55
$1.27
10201
2:34
20007
=0.75
$1.07
Table 13: EXP-a with Varying a on Digits, Office-Clatechin and DomainNet. Results are averaged over runs. We use two FL algorithms FedAvg (McMahan et al., 2017) and Fedbn (Li et al., 2021). The numbers reported are validation accuracy.
Dataset
| FL Algorihhm
EXP
Pruportional
o 0.2
1.0
5.0
10-20 25.0
- 125.0
Digit (Li et al., 2021)
FedAvg Fedbi
B1.92
78.41
35.10
81.45
85.03
$1.45
85.02
81:79
85.01
81.65
81.64
$4.97
Office-Clitech10 10 (Gong al., 2012)
FedAvg
Feehn
63.09
78.56
$1.85
66.58
30.88
65.58
66.07
80.95
65.34
81.62
79,81
66.10
DomainMer (Pong et 2019)
FodAug
60.50
70.34
69.76
61.18
A.9 PROOF OF THEOREM 1
Here we present the proof of the main theorem using the lemmas from the previous section. It follows closely the method in Li et al. (2019). While we do not claim novelty in the methodology of this derivation, show that there exists an error term due to time-varying weighting, that has been previously ignored.
Let A, B/W 1P From Lemma 1, Lemma 2 and Lemma have that
A++1 < (1 - m1 + BBBBBBBB
where B max, MN (p: 20? 8(E G) 7LΩ 2 (T 2). Following the setting in
n
Li,2019 (Li et al., 2019), set 1):
8 for some 3 > and 7 > 0 such that 77, < aL and
Ne S 2. Let max 8'B
7 We first assume that A, < c+ and prove by induction
Fu-1
that this holds for all By induction,
B
B2
A S (1 TT111)
A. + BB
A. + (t + 7)2
B
(8)
t 1+g"
3
V
B²
1+ - - B10 +
g22
1
+
B
B
1 1+7"
7 7+1
(1 +++ 7)2
7)2
(1+
7)2
1
82
Bp 11
B-
(1+7)²
7)²
(1 + 7)22
V
++++1
By the L-smoothness assumption (Assump. 1).
T. WTI w 2
I
B(F(W')- -F((") -
(9)
2 7 +
18

---

Under review as a conference paper at ICLR 2023
Following Li,2019 (Li al., 2019), choose 3 = 2, 7 max / E} - 1, and let nhe 1 7
show that the learning rate satisfies 1 S 2 Vt 2 0. Then,
B 3p-11 1 740 =
}
B
4B
=
max
Bp 1p-1 + o S n +
(10)
Finally, plugging this in to Eq. 9, we obtain a convergence bound as,
4B
B[F(W*)] -(W))))(())) F(W') <
+
7
(11)
2
+
112
N
L
2
max
(pt P0 +(F 1 1)6² + 6TΩ+
- -(T ?)
+
7
Ao
(7
112
7p
2
1=1
T.
BBB
L (T (T- ②2)
An
+
(7
112
1
where Ao - W 11 B max, Σ i= (o )20 + 8(E 1)G² + 6LΩ, r
max, DESP p
1+1 (FI(W') F (W:)) and S = min, Σ p - (P.(Wt) - -F(W))).
A.10 PROOF OF LEMMAS
Proof of Lemma J.
From the definition of Wi+1 W T]g decompose W
2 as
| 2 = W T(g: W -Trrr + Th:B: 2
(12)
W W 7g 2m.
(
W 7). g:
gt
t g:
8t 12.
A2
In the above expression, E[Ag] 0 only need to bound A
A1 W W > W w 27p W
W B
g
(13)
B3
We first focus on B2. From the L-smooth assumption (Assump. 1), we have that WFF < (W() - F.(W)))
(14)
We now bound B2 as the following.
2
N
By = 7 11 = T/E
p ++1 (F
S TH
p
+1
VF
(15)
1=1
< 2Tmi Σ + (F((W)) -
where the first inequality comes from the convexity of norms and Jensen's inequality for convex functions.
To bound B,, we first split it into two terms by the linearity of inner product as
Bi 22) W W. g.) = 22 W
r
W!
VF:(W))
(16)
N
2mp
W
V. Wi)
+2m
H1 W
W (F((W)
1=1
B1.1
B1
19

---

Under review as a conference paper at ICLR 2023
To bound B,,1, we invoke Cauchy- Seecaa- and AM-GM inequality the following,
B1,1= = (W; - W VE((W))
W (
(17)
7/
$ 17
W
wi mm (F
To bound B1,,, we use the convexity assumption (Assump. 2), which gives
B12== = (W' - W VF((W)) & F((W)) - R.(W;) - II - -.
(18)
Now we plug Eq. 15, 16, 17 and 18 back into A (Eq. 13) as the following,
N
_ [-|We - + n. w [V 7
A I
W
2 S W w + T/ Σ p
N
+ 2th
Σ
pt+1 (F:(W') - F:W))
- I - -
i=1
N
2 + 2m
(+1 (F.(W)) - FF(W))))(W))
=| w01
neP Σ P
will Σ ps (I w!ll)
N
N Σ
+ 2L
2
Σg
P
(+
(FI(W) - F((())
+1 [F(()))
1=1
N
+ 2m Σ
pith (FA(W") - F((W))
(1 (1- m-1) W - -W12 + Σ pf (WW--W!l7
N + 4mmb Σ
++1
-FW)))())))) + 2m Σ p 1+1 (F((W') F.(W!)
p
i=1
20

---

Under review as a conference paper at ICLR 2023
The last inequality uses the convexity of norms, Jensen's inequality and Eq. 14. We rearrange
C.
N
C
Σ
Pi
++ (R(W)) - P.(WT)) + 2T.
Σ
Mi
1+1
(F(WW)) - F((W))
(19)
i=1
==1
N
N
+ 21)
+1 (W:) - 2Th Σ
p 2 R((?)
1=1
i=1
-
Σ
Pi
1+1 (((W)) + 2Th Σ
Pi 41 F((W))
ALTE Σ (F((W)) F(W?))
i=1
+ 217 Σ
F. (W") 2T Σ
Pi F(W))
Pi
N
N
= - -2Lm) Σ
p (F:(()(W))) F(W.)) + 2Tp Σ (F((") - F((W))
+1 (F((W:) ((W'))-4Ln??)
D
where we define "/- = 2m/(1 2b)) and r, = - E (F((') F(W;)).
To bound D, we use first use the convexity assumption (Assump. 2).
N
N
D
=
++1
(WF) = Σ pf
- -F(()))F((W)) + Σ pp. (F(W")) ==1
-
1=1
(20)
N
Σ
H1
( - w. (P.("( Σ of ( -
Pi
1=1
N
Σ
pi
|/V - | w'Ip] Σ p #F F(("))
7h
N
Σ
0:
2Lm(F((W)) - -B((F(())FE(W)))))))))))))))))>)
W w'1p] + Σ p. (F(W")-- -
2 1m1
where the second last inequality uses the AM-GM inequality and the last equality comes from the L-smooth assumption (Assump. 1).
21

---

Under review as a conference paper at ICLR 2023
Therefore,
N
CS 71
1+1
( F((W)) +
1
I w112
(21)
21)
7
Pi
+ (P((W") F((")) (F(W))
4L
pr H+ (UR(W""-F((W))))) + 2tje I - w'))
-
N
(F((W") (((W))>F(W""+BEEE + -(W))) + 4L
1=1
=n(n 1) Σ
P
(FI(W)) - R((T)) + (4LTH + +,)ri
Tt
Pi
++
W - w9]
2M
1=1
$ (T,( 1) min Σ (F( F((W))) +21 max I,
7t
P
W
W/
2m
P20
920
N
=6n - 27/-- - 11 + 2171 r +
W W1
2m
i=1
in LS2 (T (2) + Σ Pi
[
11
i=1
where the second inequality is because Ex" P ( (F((') - -F(W:)) 2 0 and n 1 S 4" and the last inequality is because
Ct. 2np < 1 and 47/ 2 2 O.
Plugging in everything into A₁, we can bound the effect of one-step SGD as
N
|W W 1 < (1 - m/) W W + 2 2
(W'' - w!ll
(22)
1=1
6L + 2mp (T ? + n ll gi 1|
Proof of Lemma 2.
Assume Assumption 3 hold, the variance of gradients all devices is bounded E (WW"; V [I,...N..
VF S of
N E
N (W!)
E g:
gd
f
(W
Σ
p ++1
(23)
N
(pf *1 1
Vl':((': F.(W)) |3]
N <
(p)
< max 10
Σ 2
t
1=1
1=1
where the first inequality comes from the convexity of norms and Jensen's inequality. Proof of Lemma 3.
22

---

Under review as a conference paper at ICLR 2023
Assume Assumption 4 holds, i.e., E| f. (W": < G G² v [I. Let denote synchronization step. This means that a W Because Fl. requires synchronization of every E' step. we have t S E - 1 where is any step between now and the next synchronization step (inclusively). Furthermore, assume the learning rate 7 is non-increasing and To 27/- Then,
N
Pi W
w
E
Pi
I(
W
(W: w!
(24)
E8
E
(w
W - ( - |1?
2 E
Epp
E
Ept
1
W
11 (W(())))))
t-1
E
T
f (W :5:)
I Ept
E
170
V W Ea)
1
i=
S Ept
110
V(((W
S Epr
E
n/b(t to) ||
1=0
< Ept [T6 - 1|G
< 4n 11G2
A.11 PROOF OF COROLLARY 1.1
Assume .EW (F(WW) - F( are arranged in decreasing order, i.e., .EE Σ |S,
Σ E,
F((W))) 2 Σ |1 (F++(W'))
NE
we choose U(*) 2 as a non-decreasing
function, then it follows that,
NEI
N N
(F((W') F((W))) >
(Fi+1 - (Wi.))
1= E
Σ/ [5]
NEA
N E
(F(W;;) - F(WO)) <
(F44 (1) - Fi+1(W))
Σ/= |3
Σ/ |
(Fi(W)) F((W"))
N E (F (F
+u
su
ΣØ=1
Σソ=1 |
Let's define p,t11 x x
NEI
(R(W)) -F((")) have
E E,
N
N|E |3
N NE (B(W") F(W)))
Σ
(R(W") F.(W))
E
E
E,
i=1
where the inequality is direct consequence of the Chebyshev's sum inequality. Then rewrite the equation above as the following,
N
N
Σ
(F((W) - F(WW)) < Σ
(.(F(WW)) - E(W!))
where o+1
N| Σx [E,
p and P: = Σg E.
|5,1"
23

---

Under review as a conference paper at ICLR 2023
Therefore,
N (P.(W) F.())) min Σ (F F.(D))
min
A.12 EXTENSION TO PARTIAL PARTICIPATION
To provide partial participation extension to Thm. 1, need to define some additional notations. Note that the following derivation and notations largely follow the prior work (Li et al., 2019), which provides easy way to extend FL. convergence analysis the partial participation setting.
Stochasticity due to Client Sampling, Now, instead of full participation of N clients, at time t, we assume to sample K clients from the pool of N available clients, forming active of S This new client sampling procedure introduces another level of stochasticity addition to data sampling stochasticity on each client. We use the notation E.[]] and E[|] to denote expectation w.r.t each of the stochasticity respectively.
Assumption 5 The active set St+1 is constructed by sampling client with probabilities {p!+1lē I,...NN} repeatedly for K times with replacement, and the aggregation pattern defined as,
W w
N
where W
=
V++1 R Σ V
ift 1 $ Iæ
ift+ IE S
(25)
The virtual sequence W++1 is different than the virtual sequence W++1 in Eq. when t + 1 E Zg. Therefore, the key to incorporate partial participation characterizing the difference between the two when + 1 Ig.
To facilitate the proof we present the following two lemmas.
Lemma 4 lft+ + E Ig, then
E, [W++]== = W
Lemma 1fL+1 E Ix and th S 2 is non-increasing VI 2 0, then
4 E. W w+
K Th EG
Theorem Assume Assumptions 1-5 hold and T., di, G defined therein. Choose 7 = max 1 and the learning rale 1): कलानग and T E Ir. Then FedAvg using SGD with partial device participation and generic. vary-varying sampling weights Σ P 1 satisfies
22 12
-A00 + 2
L (-
[IF(WT)--F(W)) -
< ( T)
+
manishing
vanishing
where Ag | W B max, Ex (v) 3 +8E 1)62 C &
max, Em
P
(+1 (F(("") - F.WW)), and S = min, EmT,, (+1 -FW:)))
Proof of Lemma 4
K
K
E, (
[
1
Σ
E,
V
Σ
p 44 lv+1 - W
K
K
i=1
1=
24

---

Under review as a conference paper at ICLR 2023
Proof of Lemma 5
K
27
K
[. W
[1 E,
V
W
Eg
-
V
w
K
K2
K
K
$ E,
V++1
- w
1
E,
-
w
K
K
1=1
1=1
1
E.
W+
K
where the first inequality stems from triangle inequality of norms. Now we introduce new notation to = t + 1 E E Ig, which is the most recent aggression moment. Therefore, W is the same
across all clients.
1
|| We W w |P]
- K
1
[|(v -w) (W W wo>l {|]]
E,
K
[|(v
- W E.VV - w' - 1 E,
- ||
E.
K
K
The last inequality stems from the calculation of auto-correlation, i.e., E|[[ [[ = B|r+11 E[r]?. Finally, we have the following,
E. W++1
11] S
V++ w -z)
E
w3)))
p
4+1
E
Σ ا
T V
Σ
E
j=L.
1+1
4nj
Σ
E [
K
1
4 k E12
Σ
pi
H+1
EG²)
A.13 ADDITIONAL PROOF
In the main paper, we claimed equality between Thm. 1 and the convergence bound in a prior work (Li al., 2019) if p Pi
B. E Specifically, we want show that Ω r
EN (F (W:)). In this section, give detailed proof to this statement. The equality holds because
N
Ω min Σ
- -F(W))))))W))) min Σ ps FW Σ
(W;)
N Σ PFFWW" - ΣAR(W,)
N
and,
N EAF(W") Σ P.R(WW))
r max
-
Σ
1=1
25

---

Under review as a conference paper at ICLR 2023
Therefore, the bound in Thm reduces to the following,
- -
L
2B
7 Ao
(7+
122
vonishing
where Ao 1/00- - 11 B E pi + 8(E -(E-1)G 1)G² +
= Ei=IAF((W")
Zi=IPF((W::)
26


Reviews:
[{"review_id": "vBJ6dXA0zJ", "reviewer": "Reviewer_CKau", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "By analyzing the effect of time-varying aggregation weights in FL, the authors obtain a tradeoff between the convergence rate and the convergence error, where FedAvg favors the latter. Further, setting the aggregation weights proportional to the change in local loss after the local steps, the authors obtain a new aggregation strategy, $Exp-\\alpha$. This algorithm outperforms proportional aggregation across several baseline FL algorithms on several FL datasets, in terms of both the convergence rate and the final convergence error.\n", "summary_of_the_review": "See the detailed strength/weakness section ", "strength_and_weaknesses": "Strengths\n- The theoretical analysis using time-varying aggregation weights reveals that setting proportional weights is a suboptimal strategy, especially in terms of the convergence error.\n- Thorough experiments across different datasets and with different types of heterogeneity.\n- The proposed aggregation strategy, $Exp-\\alpha$, is easy to apply in practice and  outperforms baseline proportional aggregation in all scenarios.\n\nWeaknesses \n\n- **Metrics** : I assume that the authors report test accuracy of the global model averaged across clients. This wasn't clarified in the Experiments section or the appendix. Additionally, it would be  interesting to see the performance of the global model only on the heterogeneous clients, i.e., the ones which $Exp-\\alpha$ down-weights during aggregation. Further, robust algorithms perform well under low levels of corruption, so it would be interesting to see the performance of $Exp-\\alpha$ when half of the clients are corrupted.\n\n- **Theoretical results hold only for strongly convex cases** : Since the authors have not adapted proofs for convex or non-convex cases, the exact expression of proportional aggregation might be different in these cases.\n\n- **Domain Shift Experiments**: From Table 3, I could see that $Exp-\\alpha$ performs worse than proportional aggregation on several domains, however, the average accuracy is better. Could the authors provide an explanation for this? I expect that the aggregation weights for clients from these domains should be small but a further analysis of how heterogeneous these domains are, might help.\n\n- **Effects of $\\alpha$, heterogeneity and number of local steps** : Appendix A.5 is difficult to parse, especially Figures 3,4 and 5. (No legend in Figures 3 and 4 and Figure 5 is too small). While the authors do have all these sets of experiments, they do not compare how aggregation differs wrt increasing heterogeneity and number of local steps. I think that the value of $\\alpha$ controls how different the proportional weights are, with lower $\\alpha$ providing larger difference. Using this explanation, increasing heterogeneity among clients or increasing the number of local steps, should increase the deviation between local models and global models and should require a smaller $\\alpha$ to handle it. Could the authors provide more details on this?\n\n\nSuggestions \n- **Explaining Experiments** : The set of experiments are exhaustive, however, some analysis of the experimental results in terms of behavior wrt number of local steps, the value of $\\alpha$ and the cases where proportional aggregation outperforms $Exp-\\alpha$ would greatly benefit the paper.\n\n- **Possible connection to robust aggregation**: Note that several robust aggregation algorithms, for instance Trimmed Mean[1], discard or decrease the weight of clients which differ severely from the average. Here, $Exp-\\alpha$ also gives lower weights to clients which differ a lot from the average iterate and should ideally also provide some \"robustness\" in the aggregation.\n- **$Exp-\\alpha$ for stateful algorithms**: Working out the proof using a baseline stateful algorithm, for instance SCAFFOLD[2], should provide more insights into whether stateful algorithms also suffer from the issue of suboptimal convergence rate with proportional aggregation or not.\n\n\n### Typos --\n- Theorem~1 : What is the max over? and doesn't it require Assumption 1 (Strong Convexity)\n- Figures 3 and 4 in the appendix do not have legends so it is difficult to figure out exactly what is the effect of $\\alpha$.\n\n\n### References --\n\n[1] Yin, D., Chen, Y., Kannan, R. &amp; Bartlett, P.. (2018). Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates. <i>Proceedings of the 35th International Conference on Machine Learning</i>, in <i>Proceedings of Machine Learning Research</i> 80:5650-5659 Available from https://proceedings.mlr.press/v80/yin18a.html.\n\n\n[2] Karimireddy, S.P., Kale, S., Mohri, M., Reddi, S., Stich, S. &amp; Suresh, A.T.. (2020). SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. <i>Proceedings of the 37th International Conference on Machine Learning</i>, in <i>Proceedings of Machine Learning Research</i> 119:5132-5143 Available from https://proceedings.mlr.press/v119/karimireddy20a.html.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UeGXvDuP0bo", "reviewer": "Reviewer_Cggb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considered the impacts of model aggregation in federated learning (FL). The authors first derive the convergence performance of FL with a more general time-varying aggregation scheme for FL. Then by specializing the time-varying convergence result to the conventional proportional aggregation, the authors argued that the conventional proportional aggregation has its limitation in favoring convergence error while sacrificing convergence rate performance. Then, the authors proposed an exponential-type aggregation scheme called Exp-$\\alpha$ and empirically showed that Exp-$\\alpha$ achieves good performance.", "summary_of_the_review": "This paper considered the impacts of model aggregation in FL and proposed a time-varying model aggregation scheme to improve the convergence of FL over the conventional proportional scheme. Although the paper reveals some interesting insights for the proposed time-varying scheme and empirically shows the performance of the Exp-$\\alpha$ scheme, there are some confusions and potential misunderstandings of convergence rate in the theoretical results in this paper. ", "strength_and_weaknesses": "Strengths:\n1. This paper considered model aggregation, which is an important aspect of FL.\n2. The revealed insights based on a more general time-varying aggregation scheme are interesting.\n\nWeaknesses:\n1. Although this paper provides a fresh perspective on model aggregation in FL, the strong convexity (Assumption 1) and bounded local gradients (Assumption 4) are quite restrictive and not very interesting in the state-of-the-art convergence analysis of FL. \n\n2. The main theoretical results in Theorem 1 have not been presented clearly. Specifically, $\\Gamma$ and $\\Omega$, the two most important quantities in Theorem 1, are quite confusing. For a while, it appears to the reviewer that they are asymptotic and independent of $t$. But later in Sec. 3.3, it seems that they are only for finite time $t$. I suggest changing the notations to $\\Gamma_t$ and $\\Omega_t$ to avoid such confusion. Also, the authors seem to have an incorrect understanding of the terminology \"convergence rate,\" which typically characterizes the finite-time error of some convergence metric (gap w.r.t. the optimal value of the problem in Theorem 1) w.r.t. $T$. In Theorem 1, it is unclear how $\\Gamma-\\Omega$ scales w.r.t. $t$ when the proposed time-varying aggregation scheme is used. On the other hand, $\\Gamma-\\Omega = 0$ when the conventional proportional aggregation scheme is used. Thus, it is inaccurate to claim that the time-varying aggregation can achieve an improved convergence rate. In fact, the time-varying scheme may even hurt the convergence rate performance since $\\Gamma_t - \\Omega_t$ could have a convergence rate worse than $O(1/T)$.\n\n3. For the proposed Exp-$\\alpha$ aggregation scheme, the authors also didn't provide any theoretical analysis on its convergence rate in terms of $\\Gamma-\\Omega$. Thus, it is hard to know theoretically how fast the convergence rate performance of the Exp-$\\alpha$ scheme is.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QARtlQFS2S1", "reviewer": "Reviewer_gbV4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The author(s) study the model aggregation strategy in federated learning. The author(s) conduct a theoretial analysis on the impact of the model aggregation strategy. In particular, the author(s) show that the model aggregation can lead to a trade-off between convergence rate and convergence error (a non-vanishing bias term). Experiments on real-world datasets under various settings are conducted to support the proposed method.", "summary_of_the_review": "The paper is well-written and the experiments are thorough and clear to me. My only concern is on the theory side, please see my questions in the \"Strength And Weaknesses\" section. I will raise my score if these questions can be addressed.", "strength_and_weaknesses": "Strengths:\n- The paper is well-motivated and well-writtem, the story line and the theoretical analysis are easy to follow.\n- Experiments are thorough.\n\nWeakness:\n- The theory developed (Theorem 1) is not very strong. The definition of $\\Gamma$ and $\\Omega$ actually depends on $T$, so it is more accurate to write them as $\\Gamma_T$ $\\Omega_T$. As a result, the convergence error (the non-vanishing bias term) depends on $T$, which could potentially goes to 0 as $T \\to \\infity$. The relationship between the bias term and $T$ making the trade-off between convergence rate and convergence error less clear. Please also see my questions below.\n\nQuestions:\n1. Theorem 1 assumes full participation, is it possible to extend it to the parital participation case? This seems to be important because the full participation assumption is too strong for FL.\n2. Consider the proportional aggregation strategy, the bound in Theorem 1 reduces to\n$$\nE[ F(W^t) ] - F(W^*) \\leq \\frac{L}{\\gamma + T} O(1) + \\frac{L}{\\mu} \\min_{t \\in [T]} \\sum_{i=1}^N \\rho_i ( F_i( W^t ) - F_i(W^*) ) \\\\\n\\leq \\frac{L}{\\gamma + T} O(1) + \\frac{L}{\\mu} \\min_{t \\in [T]} \\sum_{i=1}^N ( F(W^t) - F(W^*) )\n$$\nwhich is trivial since $L/\\mu > 1$. This sanity check indicates that the inequality is rather loose. Is it possible to tighten the bound so that we can get a non-trivial bound for proportional aggregation?\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "15fj7ky8JgI", "reviewer": "Reviewer_cWRm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "This paper considers federated learning with non-iid data. Under the non-iid data, standard methods do not work well. For this problem, the authors first consider the effectiveness of proportional aggregation. Then, they find a trade-off between convergence rate and convergence error. Based on this finding, they propose a novel method, called Exp-$\\alpha$, which achieves the stronger convergence rates at the theoretical costs of a non-vanishing convergence error. Through several experiments, the authors confirm the empirical effectiveness.", "summary_of_the_review": "Unfortunately, I am not familiar to this topic and cannot evaluate the significance of this paper. However, the paper is well written, and there is no serious error in mathematical statement .", "strength_and_weaknesses": "The authors consider an intriguing problem in federated learning. Based on a finding on the proportional aggregation, the authors propose insightful framework, analysis, and methods. Unfortunately, I have not studied federated learning and cannot evaluate the significance. However, it seems that the theoretical results are sound, and the authors develop non-trivial methods based the theoretical results. In particular, the idea of time-varying aggregation is outstanding. Overall, I felt that the paper is high-quality and well-written. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject