A Lightweight Method for Tackling Unknown Participation Statistics in Federated Averaging
Authors: Shiqiang Wang
Mingyue Ji
Venue: ICLR 2024 spotlight (2024)
Keywords: federated learning
partial client participation
adaptation
aggregation weights
Primary area: optimization
TL;DR: We present the FedAU algorithm and its analysis, which improves federated averaging (FedAvg) by adaptively weighting the client updates, based on online estimates of the optimal weights without knowing the statistics of client participation.

Abstract: In federated learning (FL), clients usually have diverse participation statistics that are unknown a priori, which can significantly harm the performance of FL if not handled properly. Existing works aiming at addressing this problem are usually based on global variance reduction, which requires a substantial amount of additional memory in a multiplicative factor equal to the total number of clients. An important open problem is to find a lightweight method for FL in the presence of clients with unknown participation rates. In this paper, we address this problem by adapting the aggregation weights in federated averaging (FedAvg) based on the participation history of each client. We first show that, with heterogeneous participation statistics, FedAvg with non-optimal aggregation weights can diverge from the optimal solution of the original FL objective, indicating the need of finding optimal aggregation weights. However, it is difficult to compute the optimal weights when the participation statistics are unknown. To address this problem, we present a new algorithm called FedAU, which improves FedAvg by adaptively weighting the client updates based on online estimates of the optimal weights without knowing the statistics of client participation. We provide a theoretical convergence analysis of FedAU using a novel methodology to connect the estimation error and convergence. Our theoretical results reveal important and interesting insights, while showing that FedAU converges to an optimal solution of the original objective and has desirable properties such as linear speedup. Our experimental results also verify the advantage of FedAU over baseline methods with various participation patterns.

Published as a conference paper at ICLR 2024
A LIGHTWEIGHT METHOD FOR TACKLING UNKNOWN PARTICIPATION STATISTICS IN FEDERATED AVERAGING
Shiqiang Wang
Mingyue Ji
IBM Watson Research Center Yorktown Heights, NY 10598 wangshi qêus 1.m. com
Department of ECE, University of Utah Salt Lake City, UT 84112 mingyue. jeeitttuuaill @utah.edu
ABSTRACT
federated learning (FL), clients usually have diverse participation statistics that are unknown priori, which can significantly harm the performance of FL if not handled properly. Existing works aiming at addressing this problem are usually based global variance reduction, which requires a substantial amount of additional memory in a multiplicative factor equal to the total number of clients. An important open problem find lightweight method for FL in the presence of clients with unknown participation rates. In this paper, we address this problem by adapting the aggregation weights federated averaging (FedAvg) based on the participation history of each client. We first show that, with heterogeneous participation statistics, FedAvg with non-optimal aggregation weights can diverge from the optimal solution of the original FL objective, indicating the need of finding optimal aggregation weights. However, it difficult to compute the optimal weights when the participation statisties are unknown. To address this problem, we present new algorithm called FedAU, which improves FedAvg by adaptively weighting the client updates based online estimates of the optimal weights without knowing the statistics of client participation. We provide a theoretical convergence analysis of FedAU using a novel methodology to connect the estimation error and convergence. Our theoretical results reveal important and interesting insights, while showing that FedAU converges to an optimal solution of the original objective and has desirable properties such as linear speedup. Our experimental results also verify the advantage of FedAU over baseline methods with various participation patterns.
INTRODUCTION
We consider the problem of finding x E RRd that minimizes the distributed finite-sum objective:
f(x) = EN Fx(x),
where each individual (local) objective F, (x) is only computable at the client This problem often arises in the context of federated learning (FL) (Kairouz et al. 2021 Li et al.) 2020a Yang et al. 2019), where Fn (x) defined on client n's local dataset, f(x) is the global objective, and the parameter vector of the model being trained. Each client keeps its local dataset to itself, which is not shared with other clients or the server. coefficients multiplied to each F,, (x),, but for simplicity, we consider such coefficients to be included {Fa (x) : Vn) (see Appendix A. and do not write them out.
possible to extend (I) to weighted average with positive
Federated averaging (FedAvg) is commonly used algorithm for minimizing T1. which alternates between local updates each client and parameter aggregation among multiple clients with the help of server [McMahan et al. 2017). However, there are several challenges in FedAvg, including data heterogeneity and partial participation of clients, which can cause performance degradation and even non-convergence if the FedAvg algorithm is improperly configured.
Unknown, Uncontrollable, and Heterogeneous Participation of Clients. Most existing works on FL with partial client participation assume that the clients participate according known or controllable random process (Chen et al.) 2022 Fraboni et al. 2021a Karimireddy et al.; 2020 Li
al. 2020ble e
Yang et al. 2021). In practice, however, it is common for clients to have heterogeneous

---

Published as a conference paper at ICLR 2024
and time- varying computation power and network bandwidth, which depend on both the inherent characteristics of each client and other tasks that concurrently run in the system. This generally leads to heterogeneous participation statistics across clients, which are difficult to know a priori due to their complex dependeney on various factors in the system (Wang et al. 2021). It is also generally impossible to fully control the participation statistics, due to the randomness of whether client can successfully complete a round of model updates (Bonawitz et al. 2019).
The problem of having heterogeneous and unknown participation statistics is that it may cause the result of FL to be biased towards certain local objectives, which diverges from the optimum of the original objective in [T. In FL, data heterogeneity across clients is a common phenomenon, resulting in diverse local objectives {x)) The participation heterogeneity is often correlated with data heterogeneity, because the characteristies of different user populations may be correlated with how powerful their devices are. Intuitively, when some clients participate more frequently than others, the final FL result will be benefiting the local objectives of those frequently participating clients, causing possible discrimination for clients that participate less frequently.
A few recent works aiming at addressing this problem are based on the idea of global variance reduction by saving the most recent updates of all the clients, which requires substantial amount of additional memory in the order of Nd, i.c., the total number of clients times the dimension of the model parameter vector (Gu et al. 202T Jhunjhunwala et al. 2022 Yan et al., 2020 Yang et al., 2022). This additional memory consumption is either incurred at the server or evenly distributed to all the clients. For practical FL systems with many clients, this causes unnecessary memory usage that affects the overall capability and performance of the system. Therefore, we ask the following important question in this paper:
Is there a lightweight method that provably minimizes the original objective in ① when the participation statistics of clients are unknown, uncontrollable, and heterogeneous?
We leverage the insight that we can apply different weights to different clients' updates in the parameter aggregation stage of FedAvg. If this is done properly, the effect of heterogencous participation can be canceled out so that we can minimize (T) as shown in existing works that assume known participation statistics (Chen et al., 2022; Fraboni et al.) 2021a Li al. 2020b c). However, in our setting, we do not know the participation statistics priori, which makes it challenging to compute (estimate) the optimal aggregation weights. is also non-trivial to quantify the impact of estimation error on convergence.
Our Contributions. We thoroughly analyze this problem and make the following novel contributions.
To motivate the need for adaptive weighting in parameter aggregation, we show that FedAvg with non-optimal weights minimizes different objective (defined in (2) instead of (
2. We propose a lightweight procedure for estimating the optimal aggregation weight at each client n as part of the overall FL process, based on client n's s's participation history. We name this new algorithm FedAU, which stands for FedAvg with adaptive weighting to support unknown participation statistics.
3. We analyze the convergence upper bound of FedAU, using novel method that first obtains a weight error term in the convergence bound and then further bounds the weight error term via bias-variance decomposition approach. Our result shows that FedAU converges to an optimal solution of the original objective (I). In addition, desirable linear speedup of convergence with respect to the number of clients is achieved when the number of FL rounds large enough.
4. We verify the advantage of FedAU in experiments with several datasets and baselines, with a variety of participation patterns including those that are independent, Markovian, and cyclic.
Related Work. Earlier works on FedAvg considered the convergence analysis with full client
participation (Gorbunov et al., 2021 Haddadpour et al. 2019 Lin et al., 2020 Malinovsky et al. 2023, [ttchh 2019: Wang & (0shi:[0019 2021 Yu et al. 2019). which do not capture the fact that only a subset of clients participates in each round in practical FL systems. Recently, partial client participation has came to attention. Some works analyzed the convergence of FedAvg where the statistics or patterns of client participation are known or controllable (Chen et al.) 2022 Cho et al. 2023; Fraboni et al. 2021a Karimireddy et al.] 2020 Li et al. 2020b ej Rizk al. 2022 Wang & 2i]20 Yang et al. 2021). However, as pointed out by Bonawitz et al. (2019): Wang et al. (2021), the participation of clients in FL can have complex dependencies on the underlying system characteristics,
2

---

Published as a conference paper at ICLR 2024
which makes it difficult to know control each client's behavior a priori. A recent work analyzed the convergence for a re- weighted objective (Patel et al. 2022). where the re- re-weighting is essentially arbitrary for unknown participation distributions. Some recent works (Gu et al. 2022]] Jhunjhunwala et al. 2022, Yan et al. 2020; Yang et al.] 2022) aimed at addressing this problem using variance reduction, by including the most recent local update of each client in the global update, even if they do not participate in the current round. These methods require a substantial amount of additional memory to store the clients' local updates. In contrast, our work focuses on developing lightweight algorithm that has virtually the same memory requirement as the standard FedAvg algorithm.
related area adaptive FL algorithms, where adaptive gradients (Reddi et al. 2021] Wang et al. c and adaptive local updates (Ruan et al.) [202]] Wang et al. (2020) were studied. Some recent
works viewed the adaptation of aggregation weights from different perspectives (Tan et al. 2022 Wang et al., 2022a; Wu & Wang 202T), which do not address the problem of unknown participation statistics. All these methods are orthogonal to our work and can potentially work together with our algorithm. To the best of our knowledge, prior work has studied weight adaptation in the presence of unknown participation statistics with provable convergence guarantees.
A uniqueness in our problem is that the statistics related to participation need to be collected across multiple FL rounds. Although Wang & Ji (022)) aimed at extracting a certiiipaaion-sseecii term in the convergence bound, that approach still requires the aggregation weights in each round to sum to one (thus coordinated participation); it also requires an amplification procedure over multiple rounds for the bound to hold, making it difficult to tune the hyperparameters. In contrast, this paper considers uncontrolled and uncoordinated participation without sophisticated amplification mechanisms.
FEDAVG WITH PLUGGABLE AGGREGATION WEIGHTS
We begin by describing a generic FedAvg algorithm that includes a separate oracle for computing the aggregation weights, as shown in Algorithm|| [ In this algorithm, there are a total of 7 rounds, where each round includes steps of local stochastic gradient descent (SGD) at participating client. For simplicity, we consider I to be the same for all the clients, while noting that our algorithm and results can be extended to more general cases. We use 7 > O and 7 > 0 to denote the local and global step sizes, respectively. The variable xo is the initial model parameter, I, is an identity function that is equal to one if client n participates in round / and zero otherwise, and ga (-) is the stochastic gradient of the local objective (-)-) for each client n.
Algorithm 1: FedAvg with pluggable
aggregation weights
Input: 7, 1). Xu. /; Output: (x, Vi);
1 Initialize to + 0, u 50:; O:
2 for 0, T - 177-100 do
3
for n = 1,
N in parallel do
Sample 1, from an unknown process;
if II" = 1 then
yř, + Xxi
for i = 0, .......
do
L y Vf,+11 + Vi, - 7B (y?,);
A + y -Xi
else
11
A + O;
12 W + Computeeeiiggttttteeoooee ((]) <t);
N wf
13 Xt+1 + X, + N
The main steps of Algorithm [ are similar to those of standard FedAvg, but with a few notable items as follows. 1) In Line we clearly state that we do not have prior knowledge of the sampling process of client participation. 2) Line T2 calls a separate oracle to compute the aggregation weight w/ (W, > 0) for client n in round t. This computation is done on each client n alone, without coordinating with other clients. We do not need to save the full sequence of participation record {1,, r < 1). because it is sufficient to save an aggregated metric of the participation record for weight computation. In Section 3 we will see that we use the average participation interval for weight computation in FedAU, where the average can be computed in an online manner. We also note that we do not include D, in the current round t for computing the weight, which is needed for the convergence analysis so that witl is independent of the local parameter y?; when the initial parameter of round t (i.e., x,) is given. 3) The parameter aggregation is weighted by w/ for each client in Line 13
Objective Inconsistency with Improper Aggregation Weights. We first show that without weight adaptation, FedAvg minimizes an alternative objective that is generally different from ①T).
3

---

Published as a conference paper at ICLR 2024
Theorem 1 (Objective minimized convergence, informal). When 1 weights are time- constant, i.e., wh = Wn but generally wn may not be equal to way (n +n+ n'), with
Bernoulli(px) and the
property chosen learning rates y and ni and some other assumptions. Algorithm 7 minimizes the following objective:
h(x) := 7 E (nP
(2)
where : =>=> WnPa.
formal version of the theorem is given in Appendix B.4 Theorem shows that, even in the special case where each client participates according to a Bermoulli distribution with probability Pn. choosing a constant aggregation weight such as Wn = 1, Vn as in standard FedAvg causes the algorithm converge to different objective that is weighted by Pv. As mentioned earlier, this implicit weighting discriminates clients that participate less frequently. In addition, since the participation statistics (here, the probabilities (px}) of clients are unknown, the exact objective being minimized is also unknown, and it is generally unreasonable to minimize an unknown objective. This means that it is important to design an adaptive method to find the aggregation weights, so that we can minimize ① even when the participation statistics are unknown, which is our focus in this paper.
The full proofs of all mathematical claims are in Appendix B
FEDAU: ESTIMATION OF OPTIMAL AGGREGATION WEIGHTS
In this section, we describe the computation of aggregation weights {w:] based on the participation history observed at each client, which is the core of our FedAU algorithm that extends FedAvg. Our goal is to choose {w.] } to minimize the original objective
T as close as possible.
Intuition. We build from the intuition in Theorem D and design an aggregation weight adaptation algorithm that works for general participation patterns, i.c., not limited to the Bernoulli distribution considered in Theorem ! From (2) we see that if we can choose w,, = 1/p.. the objective being minimized is the same ④. We note that pn. 7 ET= 1 for each client when T is large, due to ergodicity of the Bernoulli distribution considered in Theorem [ Extending to general participation not limited to the Bernoulli distribution, intuitively, we would like to choose the
patterns that weight on to be inversely proportional to the average frequency of participation. In this way, the bias caused by lower participation frequency is "canceled out" by the higher weight used in aggregation. Based on this intuition, our goal of aggregation weight estimation is as follows.
Problem (Goal of Weight Estimation, informal). Choose {wf) so that its long-term average (i.e., for large T) + E wt is close to + p.. for each n.
Some previous works have discovered this need of debiasing the skewness of client participation (Li et al. 2020c Perazzone et al., 2022) designing the client sampling scheme to ensure that the updates are unbiased (Fraboni et al. 2021a la Li et al. 2020b). However, in our work, we consider the more realistic case where the participation statistics unknown, uncontrollable, and heterogeneous. In this case, we are unable to directly find the optimal aggregation weights because we do not know the participation statistics a priori.
Technical Challenge. If we were to know the participation pattern for all the T rounds, an immediate solution to Problem T is choose wi (for each client nı) be equal to T divided by the number of rounds where client participates. We can see that this solution is equal to the average interval between every two adjacent participating rounds, assuming that the first interval starts right before the first round / = 0. However, since we do not know the future participation pattern or statistics in each round I, we cannot directly apply this solution. In other words, every round I, we need to perform an online estimation of the weight w, based on the participation history up to round f 1.
challenge in this online setting is that the estimation accuracy is related to the number of times each client n has participated until round t - 1. When / is small and client n has not yet participated in any of the preceding rounds, we do not have any information about how to choose w/- For an intermediate value of t where client has participated only in few rounds, we have limited information about the choice of w." In this case, if we directly use the average participation interval up to the (t - 1)-th round, the resulting w/ can be far from its optimal value, i.e., the estimation has high variance if
4

---

Published as a conference paper at ICLR 2024
the client participation follows random process. This is problematic especially when there exists a long interval between two rounds (both before the (t- - 1)-th round) where the client participates. Although the probability of the occurrence of such long interval is usually low, when it occurs, it results in a long average interval for the first l. rounds when / is relatively small, and using this long average interval as the value of wi may cause instability to the training process.
Key Idea. To overcome this challenge, we define a positive integer K as a "cutoff" interval length. If client has not participated for K rounds, we consider K to be a participation interval that we sample and start a new interval thereafter. In this way, we can limit the length of each interval by adjusting K. By setting w,"" to be the average of this possibly cutoff participation interval, we overcome the aforemmentioed challenge. From a theoretical perspective, we note that wp will be a biased estimation when K < 00 and the bias will be larger when K is smaller. In contrast, smaller K leads to a smaller variance of wi,, because we collect more samples in the computation of w"" with smaller K. Therefore, an insight here is that K' controls the bias- variance tradeoff of the aggregation weight wp. In Section 4 we will formally show this property and obtain desirable convergence properties of the weight error term and the overall objective function ① by properly choosing K in the theoretical analysis. Our experimental results in Section 5 also confirm that choosing an appropriate value of K < oo improves the performance in most cases.
Online Algorithm. Based on the above insight, we describe the procedure of computing the aggregation weights {wā',, ). as shown in Algorithm The computation is independent for each client n. In this algorithm, the variable M,, denotes the number of (possibly cutoff) participation intervals that have been collected, and 5 denotes the the length of the last interval that is being computed. We compute the interval by incrementing 5% by one in every round, until the condition in Line 5 holds. When this condition holds, Sn the actual length of the latest participation interval with possible cutoff. As explained above, we always start a new interval when 5% reaches K. Also note that we consider I-= instead of I in this condition and start 3 to align with the requirement in Algorithm that the weights are computed from the participation records before (not including) the current round f. For = 0, we always use w/f = 1. In Line 7 we compute the weight using an online averaging method, which is equivalent to averaging over all the participation intervals that have been observed until each round t. With this method, we do not need to save all the previous participation intervals. Essentially, the computation in each round & only requires three state variables that are scalars, including Mn, 5% and the previous round's weight w w²-1- This makes this algorithm extremely memory efficient.
Algorithm 2: Weight computation FedAU
Input: K, {1] Vt, n): Output: {wp : Vt, n): 1 for n = 1...., .N in parallel do
2
Initialize M,. t 0, St. +- 0, wii t- 1;
3
for ( = 1,...: T
do
5% Sn 1;
if [ = or Sh = K then
Sn & S // final interval computed
Sn,
if Mn = 0 if M, 2 1
w/ Ma +Sa M.+1
5% is
M, +- Mn + 1;
9
5% < 0;
10
else
w/ +- 1
the loop from t = 1 in Line
In the full FedAU algorithm, we plug in the result of w for each round obtained from Algorithm into Line 12 of Algorithm [1] In other words, Computeweight in Algorithm I calls one step of update that includes Lines 4 Il of Algorithm 2
Compatibility with Privacy-Preserving Mechanisms. In our FedAU algorithm, the aggregation weight computation (Algorithm 2 is done individually at each client, which only uses the client's s participation states and does not use the training dataset or the model. When using these aggregation weights as part of FedAvg in Algorithm T the weight w/ can be multiplied with the parameter update A at each client n (and in each round 7) before the update is transmitted to the server. In this way, methods such as secure aggregation (Bonawitz et al. (2017) can be applied directly, since the server only needs to compute a sum of the participating clients' updates. Differentially private FedAvg methods (Andrew al. 202 McMahan al., 2018) can be applied in a similar way.
Note that we focus on the aggregation weights here, which is different from classical concept of the bias-variance tradeoff of the model.
5

---

Published as a conference paper at ICLR 2024
Practical Implementation. We will see from our experimental results in Section chosen value of K gives a reasonably good performance in practice, which means that we do not need to fine-tune K. There also other engincering tweaks that can be made in practice, such as using an exponentially weighted average in Line Algorithm{2) 2o put more emphasis on the recent participation characteristics of clients. In extreme case where each client participates only once, possible solution is to group clients that have similar computation power (c.g., same brand/model of devices) and are in similar geographical locations together. They may share the same state variables Mn, Sü, and w used for weight computation in Algorithm [ We note that according to the lower bound derived by Yang et al. (2022). if each client participates only once, it is impossible have an algorithm to converge to the original objective without sharing additional information.
that that coarsely
4 CONVERGENCE ANALYSIS
Assumption 1. The local objective functions are L-smooth, such that (x) VE)(y)) s L ||x -yll y,
(3)
Assumption 2.
The local stochastic gradients and unbiased with bounded variance, such that
E g (x) and E [lg)
x so² Vx,
(4)
In addition, the stochastic gradient noise gn (x) F (x) is independent across different rounds (indexed by t), clients (indexed by n), and local update steps (indexed by i).
Assumption 3. The divergence between local and global gradients is bounded, such that
(((x)l S 2,,,vx, Vx
(5)
Assumption 4. The client participation random variable DN is independent across different t and n. It is also independent of the stochastic gradient noise. For each client n. we define Pn such that [T]]] Pn. ie., 122 Bernoulli(p.). where the value of Pr. is unknown to the system a priori.
Assumptions 1+3 commonly used in the literature for the convergence analysis of FL algorithms (Cho et al. 2023 Wang & Ji. 2022 Yang et al. 202T). Our consideration of independent participation across clients in Assumption is more realistic than the conventional setting of sampling among all the clients with or without replacement (Li et al. 2020c] Yang et al. 202I). because it is difficult to coordinate the participation across large number of clients in practical FL systems.
Challenge in Analyzing Time-Dependent Participation. Regarding the assumption on the independence of I across time (round) t in Assumption 4 the challenge in analyzing the more general time-dependent participation is due to the complex interplay between the randomness in stochastic gradient noise, participation identities {1"), and estimated aggregation weights { J. In particular, the first step in our proof of the general descent lemma (see Appendix B.3 the specific step is in (B.366) would not hold if D² is dependent on the past, because the past information is contained in X, and {w[" } that are conditions of the expectation. We emphasize that this is purely theoretical limitation, and this time-independence of client participation has been assumed in the majority of works on FI. with client sampling (Fraboni et al. 2021 Karimireddy et al. 2020 Li cct al. 2020b c Yang et al.) D.. The novelty in our analysis is that we consider the true values of {Pn} to be unknown the system. Our experimental results in Section Show show that FedAU provides performance gains also for Markovian and cyclic participation patterns that are both time-dependent.
Assumption 5. We assume that either of the following holds and define Ve accordingly.
Option I: Nearly optimal weights. Under the assumption that N EN (prwl -1)² S 8I
for all I, we define Va
Option 2: Bounded global gradient. Under the assumption that [Vx < G2 for any we define V = ?
Assumption i only needed for Theorem (stated below) and not for Theorem |
Here, the bounded
global gradient assumption is a relaxed variant of the bounded stochastic gradient assumption commonly used in adaptive gradient algorithms (Reddi al. 2021: WWag al. 2022b c). Although

---

Published as a conference paper at ICLR 2024
focusing very different problems, our FedAU method shares some similarities with adaptive gradient methods in the sense that we both adapt the weights used in model updates, where the adaptation is dependent see Appendix A.2 for some further discussion. For the nearly optimal weights assumption, we can that it holds if 8/9p.. wit < 10/op.. which means toleration of relative error of 1/o 11% from the optimal weight 1/p.. Theorem holds under either of these two additional assumptions.
some parameters that progressively change during the training process;
Main Results. We now present our main results, starting with the convergence of Algorithm I with arbitrary (but given) weights {wa] with respect to (w.r.t.) the original objective function in
NN Theorem 2 (Convergence error w.n.t. ①.. Let T S Av15LI and mm S min { ą 54LTQ }. where
Q = max (0 I -1 N
En= Pm )n( When Assumptions 5 hold, the result {xe} obtained
from Algorithm 7
satiifies:
T E E [()(())
(6)
0O
F
VG +
T-1 N ΣΣ
B (pri (p 11}
MLQ +02) -2a)
+
MIT
NT
N
where F == f(xo) f", and f == min fxx is the truly minimum value of the objective in
The proof of Theorem 2 includes a novel step to obtain NY Et= E E
(prar" - = (ignoring
the other constants), referred to as the weight error term, that characterizes how the aggregation weights } affect the convergence. Next, we focus on {wF') obtained from Algorithm 2
Theorem (Bounding the weight error term). For {wf} obtained from Algorithm
2 when T 2 2,
T-I
N
(Pnifl - 1)9] x
logT T
1
Σ n=1
N
(1-Phh
11
)2
NT
N
t=
The proof of Theorem is based on analyzing the unique statistical properties of the possibly cutoff participation interval Sn obtained in Algorithm[2 The first term of the bound in (7) is related to the variance of w/. This term increases linearly K, because when K gets larger, the minimum number of samples of S, that are used for computing wi" gets smaller, thus the variance upper bound becomes larger. The second term the bound in (7) is related to the bias wi which measures how far E [w]"] departs from the desired quantity of 1/pm. Since 0 < Pn. < 1, this term decreases exponentially in K. This result confirms the bias-variance tradeoff of wil that we mentioned earlier.
Corollary 4 (Convergence of FedAU). Let K = [log, T with c := 1/0 min, p., 7 1
FN LIVT' 4V15L] j. and choose n such that 7T7 min V Q(14+02)LIT ALI 54LIQ When T 2 2, the result {x,) obtained from Algorithm Tahat uses {wf)
min
obtained from Algorithm satisfies
1 ET E [
0o TVTFQ SVLFQ +
(Va +2 + at R LF(1 ②) 82 +) +
+
(8)
VNIT
VNT
T
T
where Q and a are defined in Theorem and = 1/10ge.
The result in Corollary is the convergence upper bound of the full FedAU algorithm. Its proof involves further bounding 7 in Theorem 3 when choosing K log, T. and plugging back the result along with the values of 7 and v) into Theorem 2 It shows that, with properly estimated aggregation weights {wI") } using Algorithm 2 the error approaches zero as T + oo, although the actual participation statistics are unknown. The first two terms of the bound in (8) dominate when T large enough, which are related to the stochastic gradient variance o² and gradient divergence 8². The error caused by the fact that {p.} } is unknown is captured by the third term of the bound in (8). which has an order of O log" T/r). We also see that, as long as we maintain T to be large enough so that the first two terms of the bound in (8) dominate, we can achieve the desirable property of linear speedup in N. This means that we can keep the same convergence error by increasing the number of clients (N) and decreasing the number of rounds (I), to the extent that T remains large enough. Our result also recovers existing convergence bounds for FedAvg in the case of known participation Appendix A.3 for details.
probabilities (Karimireddy et al. 2020 Yang al. 2021
7

---

Published as a conference paper at ICLR 2024
5 EXPERIMENTS
We evaluate the performance of FedAU experiments. More experimental setup details, including the link to the code, and results are in Appendices C CandD respectively.
Datasets, Models, and System. We consider four image classification tasks, with datasets including SVHN (Netzer et al. 201T), CIFAR-I0 10 (Krizhevsky & Hinton 2009), CIFAR- 100 (Krizhevsky & Hinton 2009). and CINIC-1O (Darlow et al. 2018). where CIFAR- 100 has 100 classes (labels) while the other datasets have 10 classes. We
FL train convolutional neural network (CNN) models of slightly different architectures for these tasks. We simulate an FL system that includes a total of N 250 clients, where each has its own participation pattern.
Heterogeneity. Similar to existing works (Hsu et al. 2019; Reddi et al. 2021 we use a Dirichlet distribution with parameter oa 0.1 to generate the class distribution of each client's data, for a setup with non-III) data across clients. Here, Pg specifies the degree of data heterogeneity, where a smaller aa indicates a more heterogeneous data distribution. In addition, to simulate the correlation between data distribution and client participation frequency as motivated in Section [] we generate a class-widk participation probability distribution that follows a Dirichlet distribution with parameter Op 0.1. Here, Op specifies the degree of participation heterogeneity, where a smaller Cpp indicates more heterogeneous participation across clients. We generate client participation patterns following a random process that is either Bernoulli (independent), Markovian, or cyclic, and study the performance of these types of participation patterns different experiments. The participation patterns have a stationary probability Pn. for each client that is generated according to a combination of the two aforementioned Dirichlet distributions, and the details are explained in Appendix C.6 We enforce the minimum Pa. Vn, to be 0.02 in the main experiments, which is relaxed later. This generative approach creates an experimental scenario with non-IID client participation, while our FedAU algorithm and most baselines still do not know the actual participation statistics.
Baselines. We compare our FedAU algorithm with several baselines. The first set of baselines includes algorithms that compute average of parameters over either all the participating clients (average participating) or all the clients (average all) in the aggregation stage of cach round, where the latter case includes updates of non-participating clients that are equal to zero as part of averaging. These two baselines encompass most existing FedAvg implementations (e.g., McMahan et al. 20 Patel jet al. (2022); Yang et al, (2021) that do not address the bias caused by heterogeneous participation statistics. They do not require additional memory or knowledge, thus they work under the same
Table Accuracy results (in %) on training and test data
Participation pattern
Dataset
SVHN
CIFAR-10
CIFAR-IOV 100
CINIC-10
Method/ / Metric
Train
Test
Train
Test
Train
Test
Train
Test
FedAU (ours, + oc)
90.4+0.
89.
85.4
+7.4
63.4466
52.3-0.4
65.2+to.5
61.5+004
FodAU (ours, K 50)
90.6.104
89.6104
86.0:005
77.31:03
6388103
52.1
66.7:10.3
62.7:002
Average participating
89.140.3
87.24-03
83.540.9
74.1
59.34044
48.8-07
61.14:23
$6.6+22
Beroulli
Average all
88.5405
87
81.0+499
72.74-99
58.2404
47.9-0.5
60.5++23
56.++2
FodVarp (250x memory)
89.6105
88
84.210.3
77.9002
57.2109
49.2
64,4110
020100.5
MIFA (250x memory)
09.4.0.3
88.7 18.74:02
83.5
77.3 4-03
$5.8
48.4=00.7
63.8
0..5
Known participation statistics
89.240.
88.44-05
4.0.
77.0+-0.5
59.4++00
50.6++0.44
63.2++00.
60.54-0.5
FedAU (ours, K - 06)
90.51004
89.3
05.3:10.3
77.11:033
63.2:105
01.8
64.9:10.3
61.2100
FedAU (ours, K 50)
90.6:20.3
89.5
05.9
77.2+t0.3
63.5
51.7-003
66.3+:0.4
62.3-.0.2
Average participating
89.0=203
87.1
83.4.0.
74.24:0.
59.2400
48.6-0.
61.5+22.
56.921.9
Markovian
Average all
684106
86.810.7
1..8
72.5
$7.8.09
47.7=0.
59.91228
55.71222
FedVarp (250x memoryy
89.6403
88.6-0022
84.0:2033
17.8=0.2
56.4411.
48.820.5
64.61:04
62.1420.4
MIFA (250x memory)
20.
88.42:0
83.0=04
77.2+:04
15.1
63.5
61.22006
Knowa participation statistics
89.5+002
88.6+-0.2
84.5 4-0.4
76.9+-0.3
59.74-0.5
50.34+..
63.5+-09
60.7+-0.6
FedAU (ours, K - oc)
89.8
88.71:06
84.21088
76.3-1077
60:9106
50.6=003
63.5::10
60.02:08
FodAU (ours, K = 50)
89.910.6
88.81006
84.8:10.6
76.61:0.4
61.3310088
51.0
64.5:10.9
6..9
Average participating
87
85.5
8.2
73.3
58.111-1.0
4..
58.94:2.1
55.0
Cyclic
Average
89. 12
87.41:08
1..1
73.8-:03
59.74:3
48.8=0.4
6..9+117
57.621.5
FedVarp (250x memory)
84.3105
83.9106
79.710.9
75.31077
50.9005
45.9204
60.4:10.7
58.51006
MIFA (250x memory)
78.6111.
7..41:1.
7..0.11.
70.6.11.1
44.8.1066
01.1
51.2.1100
50.2::099
Known participation statistics
89.9-07
88.7=006
83.62007
16.5
60
60.2100
50.8.104
62.62088
59.8
Note to the tuble. The top part of the sub-table for each participation pattern includes our method and basclines in the same setting. The bottom part of each sub-table includes baselines that require either additional memory or known participation statistics. For each column, the best values the and bottom parts highlighted with bold and undertine, respectively. The total number of rounds is 000 for SVIIN; 10, 000 for CIFAR-10 and CINIC- 10, 20, 000 for CIFAR-IO0 100. The mean and standard deviation values shown in the table are computed over experiments with different random seeds, for the average accuracy over the 200 rounds (meassured an interval of 10 rounds).
8

---

Published as a conference paper at ICLR 2024
system assumptions FedAU, The second set of baselines has algorithms that require extra resources or information, including FedVarp (Jhunjbunwala et al. (022) and MIFA (Gu et al. 2021). which require N 250 times of memory, and idealized baseline that assumes known participation
statistics and weighs the clients' contributions using the reciprocal of the stationary participation probability. For each baseline, we performed separate grid search to find the best y and 17-
Results. The main results are shown in Table [ where we choose K = 50 for FedAU with finite K based on a simple rule-of-thumb without detailed search. Our general observation is that FedAU provides the highesl accuracy compared to almost all the baselines, including those that require additional memory and known participation statistics, except for the test accuracy on the CIFAR-10 dataset where Fed Varp performs the best. Choosing K = 50 generally gives a better performance than choosing K - oo for FedAU, which aligns with our discussion in Section 3
The reason that FedAU can perform better than VedVarp and MIFA is that these baselines keep historical local updates, which may be outdated when some clients participate infrequently. Updating the global model parameter with outdated local updates can lead to slow convergence, which is similar to the consequence of having stale updates in asynchronous SGD (Recht et al. (001)) T). In contrast, at the beginning of each round, participating clients in FedAU always start with the latest global parameter obtained from the server. This avoids stale updates. and we compensate heterogencous participation statistics by adapting the aggregation weights, which is fundamentally different and more efficient method compared to tracking historical updates as in Ved and MIFA.
It is surprising that FedAU even performs better than the case with known participation statistics. participation
To understand this phenomenon, we point out that in the case of Bermoulli-distribul with very low probability (e.g.. P.. 0.02), the empirical probability of a sample path of client's participation can diverge significantly from pa. For T = 10, 000 rounds, the standard deviation of the total number of participated rounds is o' ;= /Tp,
Pa) = 0.0196 = 14 while the mean is n' : Tpp 200. Considering the range within 2o', we know that the optimal participation weight when seen on the empirical probability ranges from L/(u" + 20') = 43.9 to 2 21/(x' 2a') z 58.1, while the optimal weight computed on the model-based probability is 1/p_ = 50. Our FedAU algorithm computes the aggregation weights from the actual participation sample path of each client, which captures the actual client behavior and empirically performs better than using 1/2n even if pa. is known. Some experimental results that further explain this phenomenon are in Appendix D.4
As mentioned earlier, we lower-bounded Pa. Vn, by 0.02 for the main results. Next, we consider different lower bounds of Pr. where a smaller lower bound of pr, means that there exist clients that participate less frequently. The performance of FedAU with different choices of K and different lower bounds of pr. is shown in Figure 1 We observe that choosing K = 50 always gives the best performance; the performance remains similar even when the lower bound of Pn is small and there exist some clients that participate very infrequently. However. choosing large K (c.g., K > 500) significantly deteriorates the performance when the lower bound of Pr is small. This means that having finite cutoff interval K of an intermediate value (i.e., K = 50 in our experiments) for aggregation weight estimation, which is uniqueness of FedAU, is essential especially when very infrequently participating clients exist.
0.001
2: 2.00
0.0
P. 0.005
0.8
Thel acomay
0.6
0.4
0.2
10¹
10"
10"
FedAU with different K (CIFAR-10 with Bernoulli participation).
Figure 1:
CONCLUSION
In this paper, we have studied the challenging practical FL scenario of having unknown participation statistics of clients. To address this problem, we have considered the adaptation of aggregation weights based on the participation history observed at each individual client. Using a new consideration of the bias-varianc tradeoff of the aggregation weight, we have obtained the FedAU algorithm. Our analytical methodology includes a unique decomposition which yields a separate weight error term that is further bounded to obtain the convergence upper bound of FedAU. Experimental results have confirmed the advantage of FedAU with several client participation patterns. Future work can study the convergence analysis of FedAU with more general participation processes and the incorporation of aggregation weight adaptation into other types of FL algorithms.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENT
The work of M. Ji was supported by the National Science Foundation (NSF) CAREER Award 2145835.
REFERENCES
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:
17455-17466, 2021.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 119111191, 2017.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp. Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konečný. Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design. In Proceedings of Machine Learning and Systems, volume 1, pp. 374-388, 2019.
Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learning. Transactions on Machine Learning Research, 2022. ISSN 2835-8856.
Yae Jee Cho, Pranay Sharma, Gauri Joshi, Zheng Xu, Satyen Kale, and Tong Zhang. On the convergence of federated averaging with cyclic client participation. arXiv preprint arXiv:2302.03109 2023.
Luke N Darlow, Elliot J Crowley, Antreas Antoniou, and Amos Storkey. CINIC-10 is not Imagenet or CIFAR-10, arXiv preprint arXiv::810003330 2018.
Yucheng Ding, Chaoyue NIu, Yikai Yan, Zhenzhe Zheng, Fan Wu, Guihai Chen, Shaojie Tang, and Rongfei Jia. Distributed optimization over block-cyclic data. arXiv preprint arXiv:2002.07455 2020.
Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi-cyclic stochastic gradient descent. In International Conference on Machine Learning, pp. 1764-1773. PMLR, 2019.
Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. Clustered sampling: Low-variance and improved representativity for clients selection in federated learning. In International Conference on Machine Learning, volume 139, pp.
PMLR, Jul. 2021a.
Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. On the impact of client sampling on federated learning convergence. arXiv preprint arXiv:2107.12211, 2021b.
Eduard Gorbunov, Filip Hanzely, and Peter Richtarik. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, volume 130 of PMLR. pp. 3556-3564, 2021.
Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning in the presence of arbitrary device unavailability. In Advances in Neural Information Processing Systems, 2021.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, 2019.
Tzu- PrngMing Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint /rX9v:/909.066 2019.
10

---

Published as a conference paper at ICLR 2024
Divyansh Jhunjhunwala, Pranay Sharma, Aushim Nagarkatti, and Gauri Joshi. FedVARP: Tackling the variance due to partial client participation in federated learning. In Uncertainty Artificial Intelligence, pp. 906 906-916. PMLR, 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. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLDD Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143, PMLR, 2020.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020b.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-IID data. In International Conference on Learning Representations, 2020c.
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local SGD. In International Conference on Learning Representations, 2020.
Grigory Malinovsky, Samuel Horváth, Konstantin Burlachenko, and Peter Richtárik. Federated learning with regularized client participation. arXiv preprint arXiv:2302.03662 2023.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. coammuunicatioo-fffcceeeee learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pp. 1273-1282. PMLR, 2017.
H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representationss 2018.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. In NeurIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Kumar Kshitij Patel, Lingxiao Wang, Blake Woodworth, Brian Bullins, and Nathan Srebro. Towards optimal communication complexity distributed non-convex optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Jake Perazzone, Shiqiang Wang, Mingyue Ji, and Kevin S Chan. Communication-efficiess device scheduling for federated learning using stochastic optimization. IEEE Conference on Computer Communications, pp. 1449-14558 2022.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: lock-free approach to parallelizing stochastic gradient descent. Advances in neural information processing systems, 24, 2011.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference Learning Representations, 2021.
Elsa Rizk, Stefan Vlaski, and Ali H Sayed. Federated learning under importance sampling. IEEE Transactions Signal Processing, 70:5381-5399 2022.

---

Published as a conference paper at ICLR 2024
Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe- Wong. Towards flexible device participation in federated learning. In International Conference on Artificial Intelligence and Staristics, pp. 3403-3411. PMLR, 2021.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Reprexentations, 2019.
Lei Tan, Xiaoxi Zhang, Yipeng Zhou, Xinkai Che, Miao Hu, Xu Chen, and Di Wu. Adafed: Optimizing participation-awer federated learning with adaptive aggregation weights. IEEE Transactions Network Science and Engineering, 9(4):2708- 2022.
Janny Wang and Gauri Joshi. Adaptive communication strategies achieve the best error-runtime trade-off in local-update SGD. In Proceedings of Machine Learning and Systems, volume 1, pp. 212 229, 2019.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of local-update SGD algorithms. Journal of Machine Learming Research, 22(213):1-500 2021.
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 Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprini arXiv: 2tl.::2077.6999 107.06917, 2021.
Qiyuan Wang, Qianqian Yang. Shibo He, Zhiguo Shi, and Jiming Chen. AsyncFedED: Asynchronous federated learning with euclidean distance based adaptive weight aggregation. arXiv preprint arXiv:2205. 13797, 2022a.
Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client participation. In Advances in Neural Information Processing Systems, volume 35, 2022.
Yujia Wang, Lu Lin, and Jinghui Chen. Communication adaptive federated learning. In International Conference on Machine Learning, pp. 22802-22838. PMLR, 2022b.
Yujia Wang, Lu Lin, and Jinghui Chen. conmuuiccationcoomp..cc adaptive gradient method for distributed nonconvex optimization. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2022c
Hongda Wu and Ping Wang. Fast-convergent federated learning with adaptive weighting. IEEE Transactions on Cognitive Communications and Networking, 144):1078-1088, 2021.
Yikai Yan, Chaoyue Niu, Yucheng Ding, Zhenzhe Zheng, Fan Wu, Guihai Chen, Shaojie Tang, and Zhihua Wu. Distributed non-convex optimization with sublinear speedup under intermittent client availability. arXiv preprint arXiv:2002.07338 2020.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-lII federated learning. In International Conference on Learning Representations, 2021.
Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu, Anarchic federated learning. In International Conference Machine Learning, pp.
PMLR, 2022.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):12, 2019.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In AAAI Conference on Artificial Intelligence, pp. 5693-5700, 2019.
12

---

Published as a conference paper at ICLR 2024
Appendix
Additional Discussion
14
A.1
Extending Objective (1) to Weighted Average
14
Assumption Bounded Global Gradient
14
A.3
Comparison with Existing Convergence Bounds for FedAvg
14
Proofs
16
Preliminaries
16
B.2
Equivalent Formulation of Algorithm]
16
B.3
General Descent Lemma
17
B
4
Formal Version and Proof of Theorem
23
B 5
Proof of Theorem
24
B.6 6 Proof of Theorem
25
B.7 Proof of Corollary
28
Additional Setup Details of Experiments
30
C.I Code
30
Datasets
30
Models
30
Hyperparameters/
30
C.5
Computation Resources
31
C.6
Heterogeneous Participation Across Clients
31
D Additional Results from Experiments
34
D.i Results with Different Participation Heterogeneity
34
D.2 Loss and Accuracy Plots
34
D.3
Client-wise Distributions Loss and Accuracy
................................
35
D.4
Aggregation Weights
36
D.5
Choice of different K
37
D.6
Low Participation Rates
39
13

---

Published as a conference paper at ICLR 2024
A ADDITIONAL DISCUSSION
A.1 EXTENDING OBJECTIVE
I TO WEIGHTED AVERAGE
We note that our objective ① can be easily extended to a weighted average of per-client empirical risk (i.c., average of sample losses), with arbitrary weights {9n Vn). To this, let Fn (x) denote the (local) empirical risk of client n, and let r == Σm= In. We can define the local objective of client n as (x) = Ln F (x), which gives us the global objective of
T
N N
N Σ
1
f(x)
F
S (x).
(A.1.1)
This objective is in a standard form seen most FL papers. The extension allows us give different importance to different clients, if needed. For simplicity, we do not write out the weights {gn) in the main paper, because this extension to arbitrary weights {qa} is straightforward, and such simplification has also been made in various other works such Jhunjhunwala et al. (2022);
Karimireddy et al. (2020); Reddi et al. (2021); Wang Ji (2022).
A.2 ASSUMPTION ON BOUNDED GLOBAL GRADIENT
As stated in Theorem our convergence result holds when either of the "bounded global gradient" assumption or the "nearly optimal weights" assumption holds. When the aggregation weights {w[") are nearly optimal satisfying N Σn = (prw) 1)² we do not need the bounded gradient assumption.
For the bounded gradient assumption itself, stronger assumption of bounded stochastic gradient is used related works on adaptive gradient algorithms (Reddi et al.] 202T] Wang et al.) [2022b c) which implies upper bound on the per-sample gradient. Compared to these works, only require an upper bound on the global gradient, i.e., average of per-sample gradients, in our work. Although focusing on very different problems, our FedAU method shares some similarities with adaptive gradient methods in the sense that we both adapt the weights used in model updates, where the adaptation is dependent on some parameters that progressively change during the training process. The difference, however, is that our weight adaptation is based on each client's ' participation history, while adaptive gradient methods adapt the element-win wise weights based on the historical model update vector. Nevertheless, the similarity in both methods leads to technical (mathematical) step of bounding a "weight error" in the proofs, which where the bounded gradient assumption needed especially when the "weight error" itself cannot be bounded. In work, this step is done in the proof of Theorem (in Appendix [B.5). In adaptive gradient methods, as an example, this step is on page 14 until Equation (4) in Reddi et al. (2021).
Again, we note that the bounded gradient assumption is only needed when the aggregation weights estimated and the estimation error is large. This is seen in the two choices in Assumption [ the convergence bound holds when either of these two conditions hold. Intuitively, this aligns with the reasoning of the need for bounding the "weight error".
A.3 COMPARISON WITH EXISTING CONVERGENCE BOUNDS FOR FEDAVG
We compare our result in Corollary 4 with existing FedAvg convergence results, where the latter assumes known participation probabilities. Since most existing results consider equiprobable sampling of certain number (denoted by S here) of clients out of all the N clients, we first convert our bound to the same setting so that comparable with existing results. We note that our convergence bound includes the parameter Q that is defined as Q == ma... N Σ Pa ( in Theorem When we know the participation probabilities and choose w/ p..
"1 for all t. we have
Q = N m= Further, for equiprobable sampling of S clients out of total of N clients, we have Pm. N
N. and thus Q = S. Therefore, when T is large and ignoring the other constants, our upper bound in Corollary becomes O VNT
S
O
14

---

Published as a conference paper at ICLR 2024
Considering existing results of FedAvg with partial participation where the probabilities are both homogeneous and known, Theorem in Karimireddy et al. (2020) gives the same convergence bound of O VT
for non-convex objectives, and Corollary in Yang et al. (2021 gives
covergence bound of O VSS Here, we note that Karimireddy et (2020) express the bound on communication rounds while give the bound on the square gradient norm, but the two types of matches with Theorem in
bounds are directly convertible to each other. Our bound of O
SS
Karimireddy et al. (2220) and improves over Corollary in Yang et a.. (202T). We also note that, in this special case, our result shows linear speedup with respect to the number of participating clients,
ie., S, which the same as the existing results in Karimireddy al. (2020); Yang al. (202T).
The uniqueness of our work compared to Karimireddy et al. (020)): Yang et al. (2021) and most other existing works is that we consider heterogeneous and unknown participation statistics (probabilities), where each client has its own participation probability Pn. that can be different from other clients.
In contrast, Karimireddy et al. (2020); Yang et al. (2021) assume uniformly sampled clients where fixed (and known) number of clients participate in each round. Our setup is more general where the number of clients that participate in each round can vary over time. Because of this generality, we cannot define fixed value of S in convergence bound that holds for this general setup, use Q to capture the statistical characteristics of client participation. When the overall probability distribution of client participation remains the same, increasing the total number of clients (N) has the same effect as increasing the number of participating clients (S), as we have shown above.
As side note, when choosing wi" = J. the weight error term [F - 1)²] becomes zero and the third term in 8 in Corollary 4 will not exist, i.c., it becomes zero. See the proof in Appendix B.7 for why the third term in (8) related the weight error.
15

---

Published as a conference paper at ICLR 2024
B PROOFS
B. PRELIMINARIES
We first note the following preliminary inequalities that we will use the proofs without explaining them further.
have
M
M
M
M
1
Σ
Zo
Zm
and
Zy
S
M
Zm
(B.1.1)
M
M
m=1
m==1
m==
m=1
for any Zm
Rd with m {1,
M) which is direct consequence of Jensen's inequality.
We also have
p p|
1z
(21, z2) -
(B.1.2)
2
2p
for any E RR and > O, which is known (the generalized version of) Young's 's inequality and also Peter-Paul inequality. direct consequence of B.1.2
1 + z2 2
b)+ + + 7)
1z2ll
(B.1.3)
for some constant 6 O.
We also the variance relation follows:
E
[|]]"]]
| [z] 11 + [|2 E [=]1]]]
(B.1.4)
for any E Rd, while noting that (B.1.4) also holds when all the expectations are conditioned on the same variable(s).
In addition, use E, b] to denote E [x),, (w[") in short. We also assume that Assumptions 1 hold throughout our analysis.
B.2 EQUIVALENT FORMULATION OF ALGORITHM
For the purpose of analysis, similar to Wang & Ji 2022 we consider an equivalent formulation of the original Algorithm 1 as shown in Algorithm B.2. In this algorithm, we assume that all the clients compute their local updates in Lines 5 This is logically equivalent to the practical setting where the clients that do not participate have computation. because their computed update Aü has no effect Line 10 if D = 0, thus Algorithm and Algorithm B give the same output sequence {x, Vt). Our proofs in the following sections consider the logically equivalent Algorithm B.2. for analysis and also use the notations defined in this algorithm.
Algorithm B.2.1: A logically equivalent version of Algorithm
Input: 7, 7) Xg. I
Output: {x, Vt}
Initialize to 0, 4 0:
2 for O..... 1 do
for n 1, ...... in parallel do
Sample 1 from an unknown stochastic process;
yi,0 <- Xt;
for = O,..., I-1 do
1h.+1 yi, 7g (y%,); In practice, computation if 1.
A + yi, Xti
with Computeweii ght (I) f));
10
X441 f- X + N "N'A
16

---

Published as a conference paper at ICLR 2024
B.3 GENERAL DESCENT LEMMA
To prove the general descent lemma that is used to derive both Theorems and 2 we first define the following generally weighted loss function.
Definition B.3.1. Define
N
f(x) = Σ
pn Fx))
(B.3.1)
nml
where Pn 2 0 for all and En Pn 1.
In B.3.1 choosing Pn + gives original objective of [xx. Note that we consider the updates in Algortthm B.2.1 to be still without weighting by Pn. which allows us to quantify the convergence different objective when the aggregation weights are not properly chosen.
Lemma B.3.1. Define 8 25, we have
-Fx(x)vV((x)) 8,,
(B.3.2)
Proof. From Assumption 3 have
(x,())) - (f+xxx-v(xx))
(F, + + V.((x) vixx /
s 2 (x) - V +2 VS(x) - V
2 (x) - V/())1 +2 Σ pm (VS(x) v.2
n=1
(0)
2 ( Vx(x)11 +2
Σ Pn [Vf(x) (F)
< 482
where we use the Jensen's inequality in (a). The final result follows due to 82 := 482.
Lemma B.3.2. When 7 V3017'
E2 ||x x 17] (o2 6789) + +3072 VJ
(B.3.3)
Proof. This lemma has the same form in Yang et al. (002
Lemma 2) and Reddi et al. 22021
Lemma 3), but we present it here for a single client n instead of average over multiple clients.
F {0, 1,2, I 1}, have
E, ||yT,et - x; x/11]
Eg ||y", - x; - (y,,()
= E, []lv2: - -x, - ( VF..y + VF.(y?.) - VF,(x.) + (F,(x;)
-vf(xi) vf(xx)
(4) E, |1 -F.
+ 2E, Ee ((( V v..(y.)) -i - VEE.
-f(x)) vf(x)) /
yE.s x
+ E, yi. x, - - (VRr,y).) - (F,(x,) + VF,(x,) - vf(x,) {((x)))
17

---

Published as a conference paper at ICLR 2024
( E2 |1> Bn -V
+ +2E (E, (B( -V (v - ( M
yi, X, xx - -AN-
82, x (VEN())))) VF vi(x)) vf(x)) ||
+ E,
E2
(Bn (xT,)) - VEGCE)
yh, x > (VRDO) - (VE -V) + -V(()))Vv())>>))))))))))()))))() - f(xi)) 1²
+ E0
E2
|17 (y
(1+ 27 27-1) Er -I>x,;-x111? x.11?
+ 2TT, 1 (VF.)))) (x,) (x,) vf(x.) + v
1+ 21 - - E+ [[IxX's=xx/ xx1²]
< Be [1> (s.))) -
(VF.((())) -V(xx)) 12]
+ +,T., (VF vx.( 67R,
+67 | |
(e)
S 3700² +
(1+
21 -11
1
Ee |Ixx. -x|1") + +61721213
|1x2. x1||²] + 617782
/ fx(x))) ||
+ +
11 -(1+ 21 21-1 6172 L2
1
xxl1= Es ||xx, - - x=|1"+++* +720² + +61-282 + +617
v f((x))
(B.3.4)
where (a) follows from expanding the squared norm above and applying the law of total expectation on the second term, (b) is because the second part of the inner product has no randomness when y?, and x, given, (c) is because the inner product is zero due to the unbiasedness of stochastic gradient, (d) follows from expanding the second term and applying the Peter-Paul inequality, (e) uses gradient variance bound, Lipschitz gradient, and gradient divergence bound.
Because y S V30L1' we have
1
21 +61-212 <
21 - 1 51
21
1
1
T
Continuing from (B3.4). we have
E. [|lv..11 x.
||]
< 1 (
1
Ee E. [1yT - x x.11²] -x,
+720² + + +6
[i(xi)]
By unrolling the recursion, we obtain
E, [1ye 2 xx| |2]
72022 -602+611882-00 661-28+617 +61 7
1 + 1
) (186 + +07228 + 11(
1
-1 -1
(1-1) 1 (N00² + 617 + + 4 v(xx))1
18

---

Published as a conference paper at ICLR 2024
1-2 (1 (1+ 1- 2 -
2/2
-1 1 1 2) (180² +61,28 + +07 [
1 + 1 1
(4)
V3e -1 1| (1- 1) (100² + 6I7282
+ (1'07+00088 +702++61288-
-17² /
I 517 (o² + 6182) + y0 ? |
where (a) uses (1 + 2)²² s for any 2 and 1
1-2 33
Lemma B.3.3 (General descent lemma). When y 4v15L1
and mm
aLI we have
1
E. [[(x+t)
- f(xx)) +
3YMNN
15L217202
278²
N Σ
Pnw
2
ipn
2
8
N
n=1
+ 2
(0²
+ )
+ 7
17a²
27102
Σ
N
Pr P2(
N2
16
8
n=1
81N
N
2
LI
1
+ 7ml
16
N
9n
+ 13 +
8N2
Pm (wx²)
n=1
n=
(B.3.5)
Proof. Due to Assumption
(ttpppiiionnoosooooooo (L-smoothness)) we have
I
)
Es [(xx+1)] s f(x.) - -
(i(x)),
1
I w
Σ
N
TT .Ee
N
Bn (Yrr))
2
N
= -(xx)= - -T ( v((x)):
1
NN
I-1
(
Pr
N
n=1
1=0
2212L
E,
gn (vi.))
(B.3.6)
2
N
R=1
where the last equality is due to E, [[]] = Pr, and the unbiasedness of the stochastic gradient giving E, [E (v?,)) yT.]] = E, [VF, (v7.)] (for simplicity, we will not write out this total expectation
in subsequent steps of this proof).
Expanding the second term of (B.3.6), we have
N
1-1
)
f((x),,
1
Σ
Σ
N
n=1
=
Vf((x)),
1
Prww
VF.
Σ pn
Σ (v..)
N
==1
i=0
N
IVf(xi) + [V |
P
N
Σ Pm Σ (Fn(y..))) )
N
1-1
= =mm
vf(u))
1
Σ
Vy..)..)
N
0=0
n=1
1=0
19

---

Published as a conference paper at ICLR 2024
N
T-1 Σ
Vy,() -1V())))))))) )1 - m ||/1>)
V (x,,), Σ
pn
n=1
==0
N
VF, (y )
=-M
77 B. I
1 fx1()
Σ
N
n=1
1=0
I-1
V
M Et
(x)()
Pn
Σ
VFn (y2,))
771
V f(xi)) |
1
(4)
ml
|f(xx) /| + $1
V
17 Et
PMW!
Σ (y,.)"
pn
4
2 11
7 Ex
Σ Pn Σ (yP.))
-FF(()))
2
21
1 ml |
M Et
Σ PPn Σ
V
(y2.))
21
n=1
i=0
2 21-1
S N
Σ
Pnin
8n
Σ 0=0
Ex [IVP
N
N
T-1
70
V - (x))) 19]
+ 2
P
E1
R=1
i=0
[]
M Er
Σ
N
Pn Σ
1-1
VLn (vt,))
|(xx ||
21
R=
i=0
S N
N
Poii
Pn
21-1
Σ
E. [IVPR
+ MOL
Σ
N
pp
1-1
Ex
[|xx",
- x
x0l²]
N
2
n=1
i=0
1m0
M Ex
Σ
N
Pn
1-1
VF
[
vyl
|
(B.3.7)
21
4
1=
where we use (a, b)
1
(Ila
+ b1l2 ||a||2 - [[b||]]
to expand the second term in (a).
Expanding the third term of [...6). we have
7212L L
E2
Σ Rn (v
2
2282 E,
1
Σ
(g (y2)) v.r())))
Σ W
Σ
v
1=0
1 N
5 ST222 LE,
Σ
(yt,) - VF()E))
N
==0
N
+ L.
V Fr (ytt))
N
1=0
(0) 2
N
1-1
E2
(g (y -F
N2
2=0
20

---

Published as a conference paper at ICLR 2024
1 Σ C Pn + pm WW
+ + LE,
Pr (y
(b) 2 2
N
N
27
Pr (w ) + 721 LIEt
4E pn)w Σ
V (yf.))
N
1
+ 2 LBB,
V F
==
( 121 LIo²
2
Pro Pr( (2x)))
+
I Pm Y0
V Fr (y
N
N2
==1
n=1
==0
N
Paii N
+ LB,
-Pn + pn
F (y
n=
2=0
(d)
N
P
N
Pr (w/))
+
Σ
Pr (1 - Pm. (wF)
Fy
N2
N2
n=1
n=1
N
1-1
27
N
+ +2
Σ
(y
+ 12 LIE,
Σ Pm Σ
v Fr (ytt))
N
1=0
1=0
72 N
2
N
1-1
(2
+
Pr Bn(wF!) )2
Es
N2
N2
n=1
1=0
2 21-1 Σ
+ 227211 LIN
Pnayy
Pn
E,
[|| (v 12]
N
1=0
+ +2 T.E,
Pn
Fn (y
(B.3.8)
where we note that D,¹ follows Berouuli distribution with probability pa, thus E [1]]] Var [4"]] = (n - Pn), yielding the relation in (d). We also use the independence across different n and for the stochastic gradients and the independence across n for the client participation random variable I,, as well as the fact that I, and the stochastic gradients are independent of each other, so the local updates (progression of y².) are independent of I,," according the logically equivalent algorithm formulation in Algorithm B. 1.2.1 The independence yields some inner product terms to be zero, giving the results in (a), (b), and (c).
Pn. and
[|| F that exists in both B.3.7 and B.3.8 we note that
For E,
| F., (y [P]
E,
-E, (y (x,( + (x, - vf(x,) + vi(x,) 11]
[VV.)) - (x || +3 VF,(x)))) - vi(x))) +3 v ?
S 3E,
< 3L E [|>TT xx 11| +3² +3 /
151 1512 + +6122 38 + (90 +3) [f(xx)]
(B.3.9)
21

---

Published as a conference paper at ICLR 2024
Combining (B.377,
(B3.8),
(B.39)
gives
-m
V
(x())
N N
P
m
V
)
22122
E2
Σ u
Σ
8n (y
27
2
n=1
k=U
N Σ
1-11
S //n//
4p
Er
[ 11
[1]
E2
||> - -x,1=xx''' xx11?]
N
2
n=1
1=0
1=0
?9 Re 21
N
T-1
V (y
M
||
4
n=1
1=0
TTp2T.T02 N2
N
N
Pr (2u))) +
Σ
(2
Σ
E,
[1VF
N2
1=0
21
+ +2 2 LIN
Pauf
Σ Th
[|VFF)(>7:]]
12]
Pn
N
1=0
N
I-1 Σ
Pn
1=0
N
21-1
+ +
N
E2
VF
N
n=1
1=0
N
Σ
|1x - -x,l1]
+
4n
E2
2
n=1
i=0
22 2 2
N
21 N
Pr (2x)))
+
Σ
(2(
E2
(x2,))1
N²
N²
1=0
27
2 /
||
21 22)2)2L.) E.
Σ Pn Σ
(y..))
4
(a)
S mm + 2mLI) N
Priuf
pp
21-1
Σ
E.
[|
N
N
1-1
Σ
||x;" - x=|1"]
+
E2
2
1=
i=0
2222LI02
N
Pn (2TT) + 22
Σ
N
pn(wp))
1-1
E2,
[|
- Iia
4 | ||
N2
N²
n=1
1=0
N
Prif
2
151.21 + +6882) + 38 + (901.3227² +3) | | 1"]
7 (1 + 2m
N
(pn) N
|
+
5172(02 + 6182) + +31222
2
LIO?
N
Pn (2
N2
n=1
2222
N Σ
(
15 +6189 + 38 + (90121272+
N2
n=1
|
4
22

---

Published as a conference paper at ICLR 2024
(e)
N
PnWy
-Pn)
(n) )²
15200
+
270²
+
27
[xxx))
|
2
N
8
8
n=1
1
(072 + +6187) + +3002,²
2
I
Σ Pn(uft) +
N
T.12
Σ n=1
Pr (2
0²
278²
27
V
N²
N²
161
8
4
3YMIN
151.277002
2782
N
Puit
2
fn
2
8
N
57 122
22
1702
27182
(o 6188) )+
+
+
Σ Pm(wB)²
N2
16
8
+ ty/l
81N
16
N
Prinf
N
Pn
+
15L
27
8N2
Σ Pn(wF))
N
1
(xxx))
n=
(B.3.10)
where (a) uses yn S 4 (b) uses Lemma B.3.2 and (B3.9
and (c) uses messmms
m S 41.1 and y S 1vI5LI
The final result is obtained by plugging (B.3.10) into (B.366).
B.4 FORMAL VERSION AND PROOF OF THEOREM
We first state the formal version of Theorem D as follows.
Theorem B.4.1 (Objective minimized convergence, formal). Define an alternative objective function as
1 h(x) = P WnPaFa(X)
(B.4.1)
where ;:=) EN WnPn. Under Assumptions when w/ = with some > for all and n, choosing 7 S and n that ym) - for some constants c, d' there exists a sufficiently
large T so that the result {xx} obtained from Algorithm satisfies ETD E [[Vh(x))]]] Se for any > 0.
the result remains the same when we replace 17 and w/ (thus w()) with 7 and an, respectively, while keeping the product ījā = TWn. We choose ān = W.,N N and i nP N. satisfies Em Ph = 1, so Lemma B.3. holds after replacing 7 and wi" in the lemma with ij and an.
Proof. According to Algorithm B.2.1
P
Then, we choose p.n WaPe Pach in Lemma B.3.3 We can that this choice
N
respectively, and f(x) in Lemma B.3.3 is equal to h(x) defined in Theorem B.4.1 with this choice of Pn. Therefore,
P2
17a²
2718²
N
E, [h(xx+1)] < h(xx))))+))))))))()))))))) +
(02 +618) + N2
+
16
8
n=1
2I N
+ r/! 12
8N2 Σ
[1
(B.4.2)
n=1
Because 7 < VT and 7
v
"
there exists sufficiently large T that 15,
27-11L
ΣN Pr, 2 In this case, after taking the total expectation of (B..22 and rearranging,
8N2
23

---

Published as a conference paper at ICLR 2024
have
[1V((x))1) 8 (E [x(x)]] (x((x++)))
8yûL
1702
27182
N
+2002213T(0= + +678)) +
+
Pr Pn.
N
16
8
(B.4.3)
Then, summing up over T rounds and dividing by T. we have
T
8H. & MIT + 2002 6182) +
8
17o²
2718²
N
E ||V
+
Pn.
T t=
N²
16
n=1
(B.4.4)
where : l(xx) - h with ht == minx hxx) as the truly minimum value.
Since 7 /T and yn TT. we can see that the upper bound above converges to zero as T + co. Thus, there exists sufficiently large T to achieve upper bound of an arbitrarily positive value of 2
B.5 PROOF OF THEOREM 2
We first present the following variant of the descent lemma for the original objective defined in Lemma B.5.1 (Descent lemma for original objective). Under the same conditions as Lemmal B.3.3
E, [x(x++1)
3yml
278² +
5/2 (0² + 616
S f(x)) +
1522
Σ
(Wnil - 1)2 + 2
2N
8
1702
27182
N
+ N2
Σ
Pa (n())
16
8
n=1
+ +
81
(prw" - 1)2 + 151.2
27 N
Σ n=l
Pm(wf)) 1
[VS(x)))
16N
8N2
4
(B.5.1)
Proof. The result can immediately obtained from Lemma B.3.3 by choosing Pr. N in (B.3.T) and noting that gradient divergence bound holds for 5 with this choice of pn according Assumption B
Proof Theorem Consider the last term in Lemma B.5.1 as specified in the theorem, have 15L3 I To and
Due to 7 S 4vI5L7 and
m S min
ALT X
27mLl EN Pm. (w S 16 8N2
Case 1: When assuming [V((x)) G2 we have
81
N
27mLL N 8N2
Σ pn (w))2 1 -[V[((x))l
mm
(prw) 1)2 15L21232
16N
SlymIGa
N
(paw) - 1)2 In 8
(B.5.2)
16N
Plugging back into Lemma B.5.1 after taking total expectation and rearranging, we obtain
E
[xx
24

---

Published as a conference paper at ICLR 2024
[[E])(x)) - -E [f(x(+1)])
12
27(6² + Ga)
N
151.214202 +
Prrws 1)2
InI
N
8
n=
+ 20072 + +678% + ML
17o
+ 2718²
Σ
N
Pr Pn(w))?
(B.5.3)
N2
2
n=1
Case 2: When assuming 1 E (Prleff - -1)² 2 81 we have
81
N
(prin - 1)2 15231222 27mLL 8N2
N Σ R=1
1 -[[5((x)]1*
mml
Pr (w())
-
16N
n=1
[xx()))
(B.5.4)
16
Plugging back into Lemma B.5.1 after taking total expectation and rearranging, we obtain
[[V](())))
24 [[xx] - E [f((+))))))
2782
N (pris - 1)²
+ 1 +
Σ
mi
N
8
n=1
N
+ 40, + 616
N2 (170² + +41822
(wx))
(B.5.5)
The final result is obtained by summing up either BB5.3 choosing Va accordingly for each case, and absorbing the constants in O-)) notation.
B.5.5 over T rounds and dividing by T.
B.6 PROOF OF THEOREM 3
We start by analyzing the statistical properties of the possibly cutoff participation interval S,, Because in every round, each client participates according Bernoulli distribution with probability Pa. the random variable S, has the following probability distribution:
Pm. p-, iflsk<h
Pr(S. ( -11-ppm k-1 -
(B.6.1)
k
which is "cutoff" geometric distribution with maximum value of K. We will refer to this probability distribution as K-cutoff geometric distribution. We can see that when K + co, this distribution becomes the same as the geometric distribution, but we consider the general case with an arbitrary K that is specified later. We also recall that the actual value of pr. is unknown to the system, which is why we need to compute (w," } using the estimation procedure Algorithm ?
Lemma B.6.1. Equation B defines probability distribution, and the mean and variance of Sn. are
(1 pn)
1 Pn.
(2K 1)(1 - Pp)
(1 22
2K
E
[S
Var [Sa] =
Pn
Pn
ph
Pn
Ph
(B.6.2)
Proof. We first show that (B.6.l defines probability distribution. According the definition in (B.6.T). we have ΣK Pr(S, k) 1 for any K. We prove this by induction. Let S, and Sy denote the random variables following K K-cutoff and (K + 1)-cutoff geometric distributions, respectively. For K 2, have ΣX Pr(S, k) P.. (1 pn) 1. Therefore, we can assume that Σk_ Pr(S, = k] = holds for a certain value of K. For (K + 1)-cutoff distribution, first note that according (B.6.I.
Pr(S, = =), Pn Pr(S, K}.
5 k < K
Pr(S, k)
K
(1 - pa) Pr(S, = K}. K +
25

---

Published as a conference paper at ICLR 2024
Therefore,
K+1
K-1 =k}
Σ
Pr(S
Σ
Pr[S,, kk Pr: Pr(S, K} + (1 (p)))) Pr(S, =K}
K Pr(S,= = k}
k=1
1
This shows that Pr(S,- = }} defined in (B.6.1 is probability distribution.
In the following, we derive the mean and variance of Sn, where we use to denote the derivative of y with respect x.
dy de
We have
K --1
E [m
=
Σ
kpn(1 - paa) + K(1 - -Pn)
k=
d
K-1
Σ (1 -Pa)*)) )
+ +K(1 - pr)) K-
Pn
dpn
k=1
(1 Pn) ((1 - Pni) pp))-1- 11 )) + K[11 k1
d
Pn
dpn
Pr.
d
((1 (1-Pa) 1 Pn
K[1 *K(1-pp) -Pn)
Pn
dpm
Pn
d
(1 (1-Pn) Pn.) K
Pn
+ 1
+ KK(1 - pm)
dpm
Pn
Pn
K(1 - Pr.) K 1--p + (1 Pm) K
Pn
+ pd
1
+ K(1 pmn)
Pr.)
(B.6.3)
Pn
Pn
which gives the expression for the expected value. To compute the variance, we note that
(Sn - -1)]
K-1
Σ
kik
KK(K--IKKKKIIPP -P.))-
k=1
d
K-1
(ke - 1)((1 -p(() )]
Σ
K(K -1)(1 K1
Pn
dpn
k=1
K-1
-(1 - (1))
(k: - 1)(1 -pa)
+ KK(K- -1)(1 - (p)) k-1
Pn
dpn
1=1
)² d
K-1
Pr
-(1 pn)
Σ (1 pm)
+ K(K - 11)(1 ppn) K-1
dpm
dpn
k=1
d
pn)) d 11 (1
pm) Ka
))
+K(K ((-))))
Pr.
dpn
dpn
Pn
Pn
d
(1-pa)
(K 1)(1 prn) K K-2
Pn
1+ (1 - Pm --1)
+ KK(K -1)(1 - pp.) > K-1
dpm
p2
(K (K-1)(1- - Pm)
(1 - Pa)
K+1
- (1-pm)2) )
+ K(K- - 1)(1 - K
=Pr
dpm
Pn
p?
26

---

Published as a conference paper at ICLR 2024
K(K 11)1-1)11- pn))-11 K-
Pn + (K 1)(1 -Pr))
Pr
pr.
(K + +1(1 -pr) pr + 2(1 pn.) 1
Pn
2(1 - pn)p 10m)-p))i-
+ 2(11 pm
+
+ +K(K - 1)((1 Pro) pmo
(K- 1)(1 - Ppn)
(K + 1)(1 - Pn) 2(1 - pm) k+1
2(1 2(1-PH Pn)
2(1 Pn)2
+
Dn
Pn
Pn
ph
2K(1 - pm))*
2(1 - Pm)(1 -Pa) + 2(1 - -Pr))
Pn
D
Phc
2K(1 - pn))
2(1 pm)K
2(1 pm)
2(1 Pm)
Pn
ph
Pn
ph
2(K 1)(1 Pr.)*
2(1
pr. K
2(1 Pn.)
(B.6.4)
Pn
P7
P
Thus,
[ = E [S, - 1)] + E [S,)
2(K 1)(1 Pm.
2(1 Pm)) )*)*
2(1 Pm))
1
(1
-
Pm Pb)
+
Pn
1
ph
Pn
Pn.
(2K 1)(1 pn)
2(1 Pa.) )K
2 Pm
(B.6.5)
Pn
ph
Therefore,
Var [Sm] = [S E [S,]²
(2K- 1)(1 pr.)
2(1 Pn)
Pn
(1
Pn)
2
+
Pa
1h
Ph
Pn
Pr.
(2K- 1)(1 pm))
2(1 - Pn )
Pn.
2(1
Pu. p
(1 -
Pm 2K
+
+
Pa )
PM
ph
ph
ph
ph
(2K- 1)(1
pr.)
1 Pu
(1 - Pr
)2K
+
(B.6.6)
Pn which gives the final variance result.
ph
pr
Now, we are ready to obtain an upper bound of the weight error term.
Proof of Theorem
Case I: According to Algorithm 2 we have wit = 1 in the initial rounds before the first participation has occurred. This includes at least one round (t 0) and at most K rounds. In these initial rounds, we have
E (prw 1)²] <
(B.6.7)
Case 2: For all the other rounds, wit is estimated based on at least one sample of S,. Therefore, using the mean and variance expressions from Lemma B.6. [ we have the following for these rounds:
E [Prcct - 1)²] = 2E
(1-
-1-p))) pm)
)
(1 - Px 27
w/
Pr.
Pn
Pr.
(a) )pn) 2
w/
(1 - --PP)) )
27
+ (1 - 2K 2K
Pn.
Pn.
27

---

Published as a conference paper at ICLR 2024
(6)
Var [Sm]
- (pm)²
max { + (1 Pr)2
Var [Sp]
S (pn)² 2
pn) )
t ( 2K Po) t + - pm)
(B.6.8)
where (a) is because the inner product term is zero since the mean of w/ is equal to (1-p.) (b) is due to the definition of variance, the fact that we consider the computation w/ to be based on at least one sample of Sn, and for any round there are at least
Pn Pn
L samples of S₁ due to the cutoff interval of length K; (c) uses the upper bound of Var [S,]] Pn Vi.
We note that the bound (.6.7) in Case always applies for = O, because we always have w/" = 1 for & 0 according Algorithm 2 For rounds 0 < K, either the bound (B.6.7) in Case 1 or the bound (B.6.8) in Case 2 applies, thus E (Prw" 1)² is upper bounded by the sum of both bounds these rounds. Then, for 2 K, the bound (B.6.8) in Case applies. According to this fact, summing up the bounds for each round and dividing by T gives
Σ
(pro 1) S
1 T
K+ (T 1)(1 Pv)) 2K + 2K(1 Pr.
T
K 2K(1 - (P)) (log T + (1 pm)22
T
3K + 2K log T
(1 pmi
(B.6.9)
T
where we use the relation that Σ1 T 7 S log T 1 for T 2 2, and the logarithm based on e.
The final result is obtained by averaging (B.69 over all n.
B.7 PROOF OF COROLLARY 4
We first prove the upper bound of the weight error term in the following lemma.
Lemma B.7.1. Choosing K [log, T1, where c (1-p) and p min, Pn. Define R
log
When T 2 2, the aggregation weights {wf) obtained from Algorithm 2 satisfies
T-1
N
(praf - -1) 0o
R Rlog" T
(B.7.1)
NT
T
Proof. Let K
flog, T7, we have
log, T
N
(1 Pn) 22 < (1-p) = (1 (1-p)a[log, 27 - (1-11)1 2)2 T
N
1 1-p
8=1
1
log 2 T
(B.7.2)
log. T
T
This shows that by choosing
= [log T where T 2 2, the RHS in 7 of Theorem is upper
3
bounded by O
2
log21 T
R Rlog T
which proves the result.
Tloge T
=
Proof of Corollary 4
We note that
1 LIVT
7 = min
LIVT 4V15L1
28

---

Published as a conference paper at ICLR 2024
FN Q (162 02) LIT LIT
N
FN
7 = min
ALI
54LIQ 54LIQ
Q (182 + +z0) LIT
QU1 LIT ;ALI; N
(182 + 0²² LIT
54LIQ
= max
4LT +
FN
FN
N
The result follows by plugging these upper bounds of y7, and 1 and the result in Lemma B.7.1
59
into Theorem
2 where we note that VT8 + o² I vTō + a since 152 + 0² I 18 + +V/Tvo to
(vío+o).
29

---

Published as a conference paper at ICLR 2024
C
ADDITIONAL SETUP DETAILS OF EXPERIMENTS
C.I CODE
The code for reproducing our experiments is available via the following link: wang/code/fedeeeeeoooooooooo
C.2 DATASETS
The SVHN dataset has a citation requirement Netzer et al. (2011). Its license is for non-commercial use only. It includes 32 x 32 color images with real-world house numbers of 10 different digits, containing 73, 257 training data samples and 26, 032 test data samples.
The CIFAR-10 dataset only has citation requirement Krizhevsky & Hinton (2009). It includes 32 x 32 color images of 10 different types of real-world objects, containing 50, 000 training data samples and 10, 000 test data samples.
The CIFAR- 100 dataset only has a citation requirement Krizhevsky & Hinton (2009). includes 32 32 color images of 100 different types of real-world objects, containing 50, 000 training data samples and 10, 000 test data samples.
The CINIC-10 dataset Darlow al. (2018) has MIT license. It includes 32 32 color images of 10 different types of real-world objects, containing 90, 000 training data samples and 90, 000 test data samples.
We have cited all the references in the main paper and conformed to all the license terms.
We applied some basic data augmentation techniques to these datasets during the training stage. For SVHN, we applied random cropping. For CIFAR-10 and CINIC-10, we applied both random cropping and random horizontal flipping- For CIFAR-100, applied combination of random sharpness adjustment, color jitter, random posterization, random equalization, random cropping, and random horizontal flipping.
C.3 MODELS
All the models include two convolutional layers with kernel size 3, filter size of 32, and ReLU activation, where each convolutional layer is followed by a max-pool layer. The model for the SVHN dataset has two fully connected layers, while the models for the CIFAR-10/100 and CINIC-10 datasets have three fully connected layers. All the fully connected layers use ReLU activation, except for the last layer that connected to softmax output. For CIFAR- 100 and CINIC-10 datasets, dropout layer (with dropout probability Kaiming initialization for weights. See the code for further details on model definition (the model class files are located inside the "model/" 1"" subfolder).
0.2) is applied before each fully connected layer. We use
C.4 HYPERPARAMETERS
For each dataset and algorithm, we conducted a grid search on the learning rates and separately.
The grid for the local step size y {10-2, 210-2,10-1.77 10-1.7 10-1.5 the grid for the global step size 17 is {10", 100:25 10 0.7.7 10 10 (01.22,100-- 10 To reduce the complexity of the search, we first search for the value of y with = 1, and then search for while fixing y the value found in the first search. We consider the training loss 500 rounds for determining the best y and 7. The hyperparameters found from this search and used in our experiments are shown in Table C.4.I
10-1.25 10-1 10 00.75 10-0.5) and
Learning Rate Decay for CIFAR-100 Dataset. Only for the CIFAR-106 100 dataset, we decay the local learning rate 7 by half every 1, 000 rounds, starting from the 10, 000-th round.
30

---

Published as a conference paper at ICLR 2024
Table C.4.1: Values of hyperparameters 7 and 77, where we use 10-1.25 0.0316, 100.25 x 1.78
0.0562, 10-1.5
Dataset
SVHN
CIFAR-I0
CIFAR-100
CINIC-10
Method Hyperparameter
Y
7
Y
7
7
77
Y
7
FedAU (ours, K + 00)
0.1
1.0
0.1
1.0
0.0562
1.78
0.1
1.0
FedAU (ours, K 50)
0.1
1.0
0.1
1.0
0.0562
1.78
0.1
1.0
Average participating
0.0562
1.78
0.0562
1.78
0.0316
1.78
0.0562
1.78
Average all
0.1
10.0
0.1
10.0
0.0562
10.0
0.1
10.0
VedVarp (250x memory)
0.1
1.0
0.0562
1.0
0.0316
1.78
0.0562
1.0
MIFA (250x memory)
0.1
1.0
0.0562
0.0316
1.78
0.0562
Known participation statistics
0.1
1.0
0.0562
1.0
0.0316
1.78
0.0562
1.0
C.5 COMPUTATION RESOURCES
The experiments were split between a desktop machine with RTX 3070 GPU and an internal GPU cluster. In our experiments, the total number of rounds 000 for SVHN, 10, 000 for CIFAR- 10 and CINIC-10, and 20, 000 for CIFAR-100. Each experiment with 10, 000 rounds took approximately 4 hours to complete, for one random seed on RTX 3070 GPU. The time taken for experiments with other number of rounds scales accordingly. We ran experiments with 5 different random seeds for each dataset and algorithm. It was possible to run multiple experiments simultancously on the same GPU while not exceeding the GPU memory.
C.6 HETEROGENEOUS PARTICIPATION ACROSS CLIENTS
C.6.1 GENERATING PARTICIPATION PATTERNS
In each experiment with a specific simulation seed, we take only one sample of this Dirichlet distribution with parameter Op, which gives probability vector q ~ Dir(a,) that has dimension equal the total number of classes in the dataset The participation probability pn. for each client is obtained by computing an inner product between and the class distribution vector of the data at client n. and then dividing by normalization factor. The rationale behind this approach is that the elements in indicate how different classes contribute to the participation probability. For example, if the first element of q large, it means that clients with a lot of data samples in the first class will have a high participation probability, and vice versa. Since the participation probabilities {P,) generated using this approach are random variables, the normalization ensures a certain mean participation probability, i.e., E [p.]]. of any client which is set to 0.1 in our experiments. We further cap the minimum value of any pn to be 0.02.
Among the three participation patterns in experiments, i.e., Bernoulli, Markovian, and cyclic, maintain the same stationary participation probabilities {p,} for the clients, so the difference is in the temporal distribution of when a client participates, which is summarized follows.
For Bernoulli participation, every round i, each client n decides whether or not to participate according to a Bernoulli distribution with probability Pn- This decision is independent across time, i.c., independent across different rounds.
For Markovian participation, each client participates according two-state Markov chain, where the motivation is similar to cyclic participation (see next item below) but includes more randomness. We set the maximum transition probability of client transitioning from not participating to participating to 0.05. The initial state of the Markov chain is determined by random sampling according the stationary probability Pa, and the transition probabilities are determined in a way so that the same stationary probability is maintained across all the subsequent rounds.
For cyclic participation, each client participates eyclically, i.e., it participates for a certain number of rounds and does not participate in the other rounds of a cycle. This setup has
We use Dir(ap) denote Dir(a,) with all the elements the vector On equal to Cp.
31

---

Published as a conference paper at ICLR 2024
been used in existing works simulate periodic behavior of client devices being charged (c.g., at night) (Cho et al. 2023] Ding et al., 2020; Eichner et al.) 2019 Wang & Ji] (022). We set each cycle to be 100 rounds. We apply random initial offset to the cycle for each client, to simulate stationary random process for each client's participation pattern.
Figure C.6.1 shows examples these three types of participation patterns.
(line-independent)
Markovian
Oydlc
Partspation
100
200
300
400
100
200
300
400
100
204
300
400
Number of Duanin rourda
Namber Eraaning sounds
Numbbrr traning rounds
Figure C. Illustration of different participation patterns, in the first 400 rounds a single client with 52.7% mean participation rate.
C.6.2 ILLUSTRATION OF DATA AND PARTICIPATION HETEROGENBITY
As described in Section 5 and Appendix C.6.1 we generate the data and participation heterogeneity with two separate Dirichlet distributions with parameters a. and O'p, respectively. the following. we illustrate the result of this generation for specific random instance. In Figure (iguueeC.6.2) the class-wise data distribution of each client is drawn from Dir( For computing the participation probability, we draw vector q from Dir(a,), which gave the following result in our random trial:
[0.02, 0.05, 0.12, 0.00, 0.00, 0.78, 0.00, 0.00, 0.02, 0.00).
Then, the participation probability is set the inner product of q and the class distribution of each client's data, divided by normalization factor. For the above q, the 6-th element has the highest value, which means that clients with a larger proportion of data in the 6-th class (label) will have a higher participation probability. This is confirmed by comparing the class distributions and the participation probabilities in Figure C.6.2
Class wise data distribution
Participation Probability
10
20
0.02
0.08
0.1
15
0.02
0:50
0.04
0.07
0.02
0.02
0.31
0.02
0.02
0.21
Proportion classes
Figure C.6.2: Illustration of data and participation heterogeneity, for an example with 20 clients.
In this procedure, q is kept the same for all the clients, to simulate consistent correlation between participation probability and class distribution across all the clients. However, the value of q changes with the random seed, which means that have different q for different experiments. We ran
32

---

Published as a conference paper at ICLR 2024
experiments with 5 different random seeds for each setting, which allows to observe the general behavior.
More precisely, let Kn Dir( denote the class distribution of client n's data. The participation probability Pa of each client n computed as
Pn (ke 9)
(C.6.1)
where is the normalization factor ensure that E [p.]] is equal to some target μ., because pn is random quantity when using this randomized generation procedure. In our experiments, we set y 0.1. Let C' denote the total number of classes (labels). From the mean of Dirichlet distribution and the fact that and are independent, we know that IE ( q) {E [k..] E [q]) :. Therefore, to ensure that E [po] = μ., according to (C.6.I), the normalization factor chosen as
We emphasize again that this procedure is only used for simulating experimental setup with both data and participation heterogeneity. Our FedAU algorithm still does not know the actual values of {pn)-
33

---

Published as a conference paper at ICLR 2024
D ADDITIONAL RESULTS FROM EXPERIMENTS
D.1 RESULTS WITH DIFFERENT PARTICIPATION HETEROGENEITY
We present the results with different participation heterogeneity (characterized by the Dirichlet parameter ap) on the CIFAR-I0 10 dataset in Table T.I. for the case of Bernoulli participation. The main observations remain consistent with those Section [ We also see that the difference between different methods becomes larger when the heterogeneity is higher (i.e., smaller ap), which aligns with intuition. For all degrees of heterogeneity. our FedAU algorithm performs the best among the algorithms that work under the same setting, i.e., the top part of Table D.I.I
Table D.I.I: Accuracy results (in %) on training and test data of CIFAR-10, with different participation heterogeneity (Bernoulli participation)
Participation beterugeneity
ap
4p
0.05
0.5
Method/ / Metric
Train
Test
Train
Test
Train
Test
Train
TTst
Train
Test
FedAU (ours, K + oo)
83.74008
76.24..7
84.3-40..8
76.6++0.5
85.4:10.4
77.1=40.4
87,3++0,5
77.8-+0.2
88. 14007
78.1-40.2
FedAtf (ours, K 50)
84.720.6
76.920.6
85.1
27.3
86.020.5
77.320.3
87.6
07.8
08.2
78.02002
Average participating
1..6.:12
72.32117
81.5::111
72.62:1.4
83.52009
74.1:208
85.9220.7
78.7200
87.0.1.0
76.8:006
Average
76.9+22.
69.5++2.7
78.5++1.77
70.6++1.8
81.0=10.9
72.7=40.9
83.6++1.4
74.6-+0.8
84.9++1.2
75.9-+1.0
FedVarp x memory)
82.5
27.34:03
83.0:10.4
27.5++0.4
84.2:00.3
77.94:02
85.4:10.5
78.1
78.54:0.3 06.4.1077
MIFA (250x memoryy
82.1:10.8
77.0:10.7
82.6:10.3
77.3-10.4
83.5
77.5:10.3
84.9..0.5
77.9:10.3
78.0:10.4 85.4..0.4
Known participation statisties
83.1
76.3-20.6
83.6
76.7200
84.3+0.
77.0=005
86.1
77.7
86.8+09
77.9-00.
Note to the table. The same note in Table D
also applies to this table.
D.2 LOSS AND ACCURACY PLOTS
For Bernoulii participation, we plot the loss and accuracy results in different rounds for the four datasets, as shown in Figures D.2.] In these plots, the curves show the mean values and the shaded areas show the standard deviation. We applied moving average with window size equal to 3% of the total number of rounds, and the mean and standard deviation are computed across samples from all experiments (with 5 different random seeds) within each moving average window.
The main conclusions from Figures(D..IJ D.2.4Jare similar to what we have seen from the final-round results shown in Table in the main paper. We can see that our FedAU algorithm performs the best in the vast majority of cases and across most rounds. Only for the CIFAR-10 10 dataset, FedAU gives slightly worse test accuracy compared to FedVarp and MIFA, which aligns with the results in Table T However, FedAU still gives the highest training accuracy on CIFAR-10. This implics that Varp/M/FIF gives slightly better generalization on the CIFAR-10 dataset, where the reasons worth further investigation. We emphasize again that FedVarp and MIFA both require a substantial amount of additional memory than FedAU, thus they do not work under the same system assumptions as FedAU, For the CIFAR- 100 dataset, there is jump around the 10, 000-th round due to the learning rate decay schedule, mentioned in Section
FedAU (X
FedAU (K= 50)
Avg. part.
Aug. all
Fedvarp
MIFA
Known part. prob.
0.92
0.0024
0.90
0.0022
0.90
aocuray
0.88
0.0020
Test socuracy
Trahing
0.0018
0.88
0.88
0.0016
0.86
0.0014
0.84
0.82
0.0012
0.0010
0.82
0.80
500
1000
1500
2000
500
1000
1500
2000
500
1030
1500
2000
Training rounds
Training rounds
Training rounds
Figure D.2.1: Results SVHN dataset (Bernoulli participation).
34

---

Published as a conference paper at ICLR 2024
(K
FedAU (K 50)
Avg. part.
Aug.
FecVarp
MIFA
Known part. prob.
0.0040
0.78
0.0035
0.76-
0.80
0.0030
Traiiin
Thaning
0.75
0.72
0.0025
0.70
0.0020
0.70
0.88
0.0015
0.65
Training rounds
Training rounds
Training rounds
Figure D.2.2: Results on CIFAR-10 10 dataset (Bernoulli participation).
FedAU (K++))
FedAU (K
Avg. part.
Avg. all
FecVarp
MIFA
Known part. prob.
0.0080
0.65
0.52
0.0085
0.60
0.50
0.0080
0.0075
0.55
0.48
0.0070
Tranning
0.46
0.0085
0.50
Test
0.44
0.0060
0.42
0.45
0.0055
0.40
0.0050
0.40
0:38
5000
10000
19000
20000
5000
10000
15000
20000
5000
10000
15000
20000
rounds
Training rounds
Training
Figure D.2.3: Results CIFAR-100 dataset (Bernoulli participation).
FedAU (K+
FadAUi 50)
Aug. part.
Aug.
Fackarp
Known
0.625
0.65
0.0055
0.800
0.60
0.575
0.0050
Traring
0.550
0.0065
Traiking
0.55
0.50
0.0035
0.45
2500
7600
10000
5000
7500
10000
5000
7500
10000
Training rounds
Training rounds
Training rounds
Figure D.2.4: Results on CINIC-10 dataset (Bernoulli participation).
D.3 CLIENT-WISE DISTRIBUTIONS OF LOSS AND ACCURACY
We plot the loss and accuracy value distributions among all the clients in Figure D.3.1 where consider Bernoulli participation and compare with baselines that do not require extra resources or information.
35

---

Published as a conference paper at ICLR 2024
1.0
FodAU Jours. K)+
Fadill (oum, K-
0.8
FodAU
Average partoipttnn
0.-
Auwraga partidpeetin
FedAll tours.
0.6
Average
Avcrage
FedAU (ouns, K-+ -]]
0.4
04-
Average perkidpwing
0.0
Averape al
6.0
00
0.
Traniig accuracy diantt
accurecy
Figure D.3.1: Client-wise distributions of loss value, training aceuracy, and test accuracy, CIFAR-I0 dataset with Bernoulli participation. The distribution is expressed as empirical cumulative distribution function (CDF).
We can see that compared to the wverac-paatticpatin and average-all baselines that use the same amount of memory as FedAU, the spread the loss and accuracy with FedAU is smaller. This also seen in the standard deviation of all the clients' loss and accuracy values in Table Table where only include the standard deviation values because the mean values are the same as those Table
Table D.3.1: Client-wise statistics of loss and accuracy (CIFAR-10 dataset with Bernoulli participation)
Method
Client-wise std. dev. of loss
Client-wise std. dev. of training accuracy
Client-wise std. dev. of test accuracy
FedAU (ours, K + oo)
0.017
9.9%
11.7%
FedAU (ours, K = 50)
0.016
9,5%
11.2%
Average participating
0.031
13.3%
11.6%
Average
0.030
13.3%
12.2%
This shows that FedAU (especially with K = 50) reduces the bias among clients compared to the two baselines, which aligns with our motivation mentioned in Section about reducing discrimination.
D.4 AGGREGATION WEIGHTS
As shown in Figure D.4.1 with Bernoulli participation, the computed weights be quite different from 1/p.. especially when the participation probability is low (in Subfigures D. 1.4. In contrast, see in Figure D.4.2) that with cyclic participation the weights computed by FedAU and the known participation statistics baseline are more similar. This aligns with the fact that the accuracies in the case of cyclic participation also more similar compared to the case of Bernoulli participation, as seen in Table []
Note that K for FedAU in both Figure D.4.1 and Figure D.4.2
36

---

Published as a conference paper at ICLR 2024
Average a200ogatoon wwgght
2.2
Known
Aggrapetin weight
2.00
FadAU (ours)
1.75
1.50
10
Known part. ssal.
1.25
FedAU (ouns)
1.00
5000
10000
10000
traming
naaning
(b)
50
50
100
Known part stat.
Agg aggroottoon woght
65-
FedNU (ours)
80
www.oo..... 200y
Aggropatoon
35
30-
30
80
Known
Known FocAU (ours)
FesNU (ours)
5000
10000
5000
10000
5000
10000
Number training rounds
Number of triiing rounds
Number of training rounds
(c)
(d)
(c)
Figure D.4.1: Aggregation weights with Bernoulli participation, (a) average aggregation weights over all clients, (b) aggregation weights of a single client with a high mean participation rate of 52.7%, (c)-(e) aggregation weights of three individual clients with a low mean participation rate of 2%.
27
FodMU jours)
2.0
1.0
1.6
FedRU
2000
5000
7500
10000
2000
5000
7000
10000
Number of training rounds
Number Indiring rounds
(a)
(b)
45
Apprpttion gh
40
$2.5
-00
60.0
20-
47.54
45.0
Known part 93M
(oun)
42.
FedAll (su))
(oon))
2500
5000
7500
10200
40.0
7500
2500
5000
7900
10000
Numbeer buiniing ronns
Number
Sumber maining rounds
(e)
Figure D.4.2: Aggregation weights with cyclic participation, (a) average aggregation weights over all clients, (b) aggregation weights of a single client with high mean participation 52.7%. (c)-(e aggregation weights of three individual clients with a low mean participation rate of 2%.
D.5 CHOICE OF DIFFERENT K
We study the effect of the cutoff interval length K by considering the performance of FedAU under different minimum participation probabilities. The distributions participation probabilities {p.) for all the clients with different lower bounds are shown in F.5.I) where that smaller lower bound value corresponds to having more clients with very small participation probabilities. The full set of plots complementing Figure is shown in Figure D.5.2
37

---

Published as a conference paper at ICLR 2024
Pa 2 0.02
2 0.01
Pr 2 0.005
z 0.001
0.75
0.75
0.75
0.75
0.50
0.50
0.50
3
0.50
0.25
0.25
0.00
10
10
10
10
10
10
10
10
10
10"
Particiaation probabiity
Paridiation probability
Partictaation
0.0
1.00
0.00
0.00
10
Participation probabllty
Figure D.5.1: Distributions of participation probabilities {Pn} at clients, with different lower bound values of these probabilities. The distribution is expressed as empirical cumulative distribution function (CDF) with logarithmic scale on the z-axis.
0.02
0.01
0.005
0.001
0.0
0.8
0.008
Trahing actunecy
Teat eozuraty
0.6
0.006
0.5
0.4
0.4
0.004
0.3
0.2
10
10
10'
10"
K
K
(a) Full plots
Re
Pn
0.005
Px
0.0040
0.78
0.0006
Training accurasy
0.80
Teat Rocuracy
0.74
0.0030
Training
0.72
0.75
0.0025
0.0020
0.70
0.68
0.0015
0.85
16
10'
10
10
10
10
K
K
(b) Flots with enlarged y-axis
Figure D.5.2: Results of FedAU with different K, on CIFAR-10 dataset with Bernoulli participation. The loss is NaN for K 10th with p., 2 0.0.
38

---

Published as a conference paper at ICLR 2024
D.6 Low PARTICIPATION RATES
To further study the performance of FedAU in the presence of clients with low participation rates, set the lower bound of participation probabilities 0.0 (i.e., we do not impose specific lower bound; see Appendix CC.. Appendix D.3 for details) and compare the performance of FedAU with K 50 the bascline algorithms. We consider settings with different mean participation probabilities E [pr., while following the same procedure of generating heterogeneous participation patterns as described in Appendix [.66 to capture the effect of different overall participation rates of clients. The resulting distributions of [Pr. with different E [Pn] are shown in Figure D.6.1
F[pp]= =01
#[Pa] =1Pa==0.00
FlP,] = 0.001
1.00
1.00
1.00
0.75
0.50
0.50
0.50
0.25
0.00
0.00
0.00
10"
10"
10"
10"
10'
Particlpation probabillyy Pr.
Participatio probability
Participation probabilly P.
Figure D.6.1: Distributions of participation probabilities {p,} at clients, with different values of E [n)] The distribution is expressed as empirical cumulative distribution function (CDF) with logarithmic scale on the a-axis.
Table D. Accuracy results (in %) on training and test data of CIFAR-1O, with different mean participation probabilities E [p.] of clients (Bernoulli participation) and no minimum cap of p.,
Mean participation probability
E Elpo] =
E [pm]
0.01
E [p.]
0.001
Method / /etric
Train
Test
Train
Test
Train
Test
FedAU (ours, K 50)
84.1 10.6
75.9
71.5+11
67.7+1.
45.9
45,6212
Average participating
81.6207
72.5
60.2
57.9415
26.7+1x
26.8
Average all
79.5 +-.
71,5+09
61.8 4:2
60.0+
33,0+18
33.5
FedVarp x250x memory)
61.5
59.5
10.0+a.
10.0+a0
12.7434
12.8435
MIFA (250x memory)
14.8
72.5
10.010.
10.0
10.0100
10.0
Known participation statistics
15.0=100
14.9
10.0+0.
10.0
10.0100
10.0
Note to table. Total number rounds is 10, 000. We do not enforce a minimum participation probability in these results, i.c., we allow any pr. 2 0.0. We use the hyperparameters listed in Table C.4.1 for all the experiments. The same note in Table also applies to this table.
Key Observations. The accuracy results are presented in Table D.6.1 from experiments with the CIFAR-I0 dataset and 10, 000 rounds of FL. As expected, the performance of the majority of algorithms decreases as E [p,.] decreases, where the minor increase of Fed FedVarp's performance from the case of E [p.] = 0.01 E [p.] = 0.001 is due randomness in the experiments. We summarize the key findings from Table D. in the following.
is interesting to see that the baseline algorithms that require additional memory or other information actually perform very poorly when the clients' participation rates are low, where we note that an accuracy of 10% corresponds random guess for the CIFAR-10 dataset that has 10 classes of images. The reason is that Ved and MIFA both perform variance reduction based on previous updates of clients. When clients participate rarely, is likely that the saved updates are outdated, causing more distortion than benefit to parameter updates. For the case of known participation statistics, the aggregation weight of each client n is chosen as 1/p.. When pr, is very small, the aggregation weight becomes very large, which causes instability to the model training process.
The average participating and average all baselines perform better than the FedVarp, MIFA, and known participation statistics baselines, because the aggregation weights used by the average participating
39

---

Published as a conference paper at ICLR 2024
and average all algorithms do not have much variation, which provides more stability in the case of low client participation rates.
FedAU (with K 50) gives the best performance, because the cutoff interval of length K ensures that the aggregation weights are not too large, which provides stability in the training process. At the same time, clients that participate frequently still have lower aggregation weights, which balances the contributions clients with different participation rates.
Further Discussion. We further note that all the results in Table D.6. are from experiments using the hyperparameters listed in Table
C.4.1 These near-optimal hyperparametens were found from grid search (see Appendix C.4) when the clients participate according Bernoulli distribution with statistics described in Appendix C.6 For the baseline methods that give random guess (or close to random guess) accuracies, it possible that their performance can be slightly improved by choosing much smaller learning rate, which may alleviate the impact of stale updates (for Fed and MIFA) or excessively large aggregation weights (for known participation statistics) when the client participation rate is low. However, it is impractical to fine tune the learning rates depending on participation rates, especially when the participation rates are unknown a priori. In addition, using very small learning rates generally slows down the convergence, although the algorithm may converge in the end after large number of rounds. The fact that FedAU gives the best performance compared to the baselines for wide range of client participation rates, while keeping the learning rates unchanged (i.e., using the values in Table C.4.I confirms its stability and usefulness in practice.
40


Reviews:
[{"review_id": "qmvl5S5HIv", "reviewer": "Reviewer_dwXt", "summary": "The article tackles the problem of Federated Learning under heterogeneous client participation. The authors propose a correction of FedAvg algorithm which handles heterogeneous participation through estimation of optimal aggregation weights based on client participation history, in a new algorithm called FedAU. Theoretical results are derived, which highlight sub-optimality of classical FedAvg algorithm in this setting, as well as convergence analysis of FedAU. Numerical experiments illustrate the theoretical findings.\n\nI have read the authors response, which thoroughly answered my questions. In this regard, I think the paper is very strong and updated my score accordingmy.", "questions": "- In practice, what is the order of magnitude of the lowest participation rate that can be estimated? \n- Related question, did you perform any experiments to understand at what point the weights might explode (in the case where K is very large) ?\n- It is also likely that clients participation rate pn actually vary over time, while remaining independent across t. Do you think your theoretical results could easily be adapted to such cases ?\n- Concerning the theoretical results, using your proof techniques, do you recover existing results in the particular case where pn are homogeneous/known ?", "limitations": "", "rating": 10, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper tackles an important practical limitation on existing FL algorithms, which often depend on a known, homogeneous client's participation rate. \n- The proposed algorithm is original as it tackles client participation heterogeneity using novel methodologies quite different from existing litterature mostly based on variance reduction techniques. In addition, the proposed algorithm enjoys favourable computational complexity compared to existing works.\n- The proof techniques are also original and could be reused in other settings\n- The paper is very clear and well-written, the problematic, related work and contributions are clearly highlighted, and scientific methodology is easy to follow. In particular, the authors made the effort of stating intuitive results and presenting formal theorems in a user-friendly manner.", "weaknesses": "- The authors mention that the proof techniques, but I didn't find any sketch of the proof in the main text, which is a shame because it could help readers understand the novelty, and maybe reuse proof techniques.\n- The numerical experiments are a bit disappointing in the sense that they do not really highlight how much of the theoretical results are observed in practice, but only that FedAU improves over FedAvg on the proposed use cases. It would have been interesting to see experiments highlighting convergence error for varying values of K or ground truth average participation rates (even on simple simulations)", "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": "", "extra_scores": {}}, {"review_id": "e3Zh8Hp2kh", "reviewer": "Reviewer_p8tC", "summary": "This paper studies the FedAvg algorithm with unknown participation statistics. It first proves that FedAvg with non-optimal aggregation weights can diverge from the optimal solution of the original FL objective. Next, it proposes an adaptive method to estimate the participation weight and come up with the FedAU algorithm that can converge to the desired solution even under the unknown participation statistics. Numerical experiments validate the theoretical findings.", "questions": "1. Please clarify why does your linear speedup term is O(1/sqrt{N*I*T}) not O(1/sqrt{S*I*T}) as shown in reference [R1] with partial client sampling. I think O(1/sqrt{S*I*T}) makes more sense since only a subset of S participates in data sampling and model update per iteration.\n\n2. Why do you need both bounded variance assumption in (4) and bounded global gradient assumption in Theorem 2? The bounded gradient assumption is typically very restrictive and are not used in literature such as in [R1]. Can the bounded global gradient assumption be removed?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. It shows that, with unknown participation statistics, FedAvg with non-optimal weight will diverge from the optimal solution of the original FL objective.\n\n2. It proposes an interesting online Algorithm 2 to estimate the unknown participation weight.\n\n3. It proposes FedAU algorithm that can converge to the desired solution even with unknown participation weight.", "weaknesses": "The linear speedup term in Eq.(8) seems unreasonable. According to the FedAvg result in reference [R1] (see Table 2), when only a subset of clients (say S clients) participate in the FedAvg, the linear speedup term should be O(1/sqrt{S*I*T}), not O(1/sqrt{N*I*T}).  I believe O(1/sqrt{S*I*T}) makes more sense since only S clients sample data and participate in algorithm update per iteration.\n\n[R1] Karimireddy et.al., SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, ICML 2020.", "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": "", "extra_scores": {}}, {"review_id": "PVbr6qgiHg", "reviewer": "Reviewer_X6kq", "summary": "This paper studies the problem of partial participation in federated learning. More specifically, the authors consider the FedAvg algorithm and assume that each client $m$ will participate with some unknow probability $p_m$. The authors show that if we are aiming to optimize the objective in equation (1), the non-adaptive aggregation weight in FedAvg will lead to a solution of optimizing another objective. In addition, the authors propose a new method that can compute the adaptive aggregation weight efficiently, and provide the corresponding convergence rate.", "questions": "I have the following questions regarding the current paper:\n1. What are the other baseline algorithms and their corresponding convergence rates?\n2. According to Theorem 1, when we have full participation, i.e., $p_n=1$ and $w_n=1$, the objective in (2) will reduce to the objective in (1). Therefore, whether your results will recover the convergence rate of FedAvg with full participation? In addition, when we have partial participation with $p_n=p<1$ and $w_n=1$, the objective in (2) will also reduce to the objective in (1). How will your result look like compared to the existing results?\n3. What is the expression on $\\Psi_G$ in your theorems?\n4. In Corollary 4, what do you mean by sufficient large $T$? Do you mean the results hold only asymptotically?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strengths of the paper:\n1. The authors provide a result to show that non-adaptive aggregation weight in FedAvg is bad for optimizing the objective in equation (1).\n2. The authors develop an efficient method to estimate the adaptive aggregation weight that can be used in FedAvg.\n3. The authors establish the convergence rate of the proposed method which demonstrates the effectiveness of the proposed method.", "weaknesses": "The weaknesses of the paper:\n1. There is no (theoretical) comparison with existing baselines.\n2. Several conditions in the established results are unclear.", "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": "", "extra_scores": {}}, {"review_id": "tpoZg1WuQU", "reviewer": "Reviewer_ByHL", "summary": "The paper addresses a critical issue in federated learning (FL) where clients have varying and unknown participation rates, which can hinder FL's performance. Existing solutions often rely on global variance reduction, which consumes substantial memory resources. The paper introduces a lightweight method called FedAU, which adapts aggregation weights in FedAvg based on each client's participation history. FedAU resolves this problem by adaptively weighting client updates using online estimates of optimal weights, even without knowledge of participation statistics. Theoretical analysis shows that FedAU converges to the original objective's optimal solution with desirable properties such as linear speedup, and experimental results support its advantages over baseline methods in various participation scenarios.", "questions": "see above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strengths of this paper's contributions are as follows:\n\n1. The authors introduce a lightweight procedure named FedAU for estimating optimal aggregation weights for each client based on their participation history. This approach supports FL even when participation statistics are unknown, making it highly practical.\n\n2. The paper provides a novel and thorough analysis of the convergence upper bound for FedAU. It employs a unique method to handle weight error in the convergence bound and shows that FedAU converges to the optimal solution of the original objective. Furthermore, it achieves desirable linear speedup in convergence when the number of FL rounds is sufficiently large.\n\n3. Experimental results validate the advantages of FedAU over various datasets and baseline methods, particularly in scenarios with diverse participation patterns, including independent, Markovian, and cyclic patterns. This demonstrates the robustness and effectiveness of the proposed approach.", "weaknesses": "1. The theoretical results in the paper are founded on the assumption of a Bernoulli distribution for client participation. It does introduce an extra layer of specificity that might not hold universally. It would be beneficial for the authors to explicitly state this assumption within the paper, as the current presentation of the four assumptions largely omits this fact.\n\n2. I wonder if there is a potential limitation in scenarios where clients rarely participate in the training process, as seen in cases like cross-device federated learning. In such instances, the online estimation of the aggregation weights (w_t) could be challenging or, at best, very inaccurate.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)