Science, Faculty of
Computer Science, Department of
DSpace
UBCV
He, Shiqi
Master of Science - MSc
University of British Columbia
Federated learning (FL) is an effective technique to directly involve edge devices in machine learning (ML) training while preserving client privacy. However, the substantial communication overhead of FL makes training challenging when edge devices have limited network bandwidth. Existing work to optimize FL bandwidth overlooks downstream transmission and does not account for FL client sampling. We propose GlueFL, a framework that incorporates new client sampling and model compression algorithms to mitigate low download bandwidths of FL clients. GlueFL prioritizes recently used clients and bounds the number of changed positions in compression masks in each round. We analyse FL convergence under GlueFL’s sticky sampling, and show that our proposed weighted aggregation preserves unbiasedness of updates and convergence. We evaluate GlueFL empirically, and demonstrate downstream bandwidth and training time savings on three public datasets. On average, our evaluation shows that GlueFL spends 29% less training time with a 27% less downstream bandwidth overhead as compared to three state-of-the-art strategies.
GlueFL: Reconciling Client Samplingand Model Masking for BandwidthEfficient Federated LearningbyShiqi HeB.Sc., Hong Kong Polytechnic University, 2020A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)January 2023© Shiqi He 2023The following individuals certify that they have read, and recommend tothe Faculty of Graduate and Postdoctoral Studies for acceptance, the thesisentitled:GlueFL: Reconciling Client Sampling andModel Masking for Band-width Efficient Federated Learningsubmitted by Shiqi He in partial fulfillment of the requirements for thedegree of Master of Science in Computer Science.Examining Committee:Ivan Beschastnikh, Associate Professor, Computer Science, UBCSupervisorMathias Lécuyer, Assistant Professor, Computer Science, UBCSupervisory Committee MemberiiAbstractFederated learning (FL) is an effective technique to directly involve edgedevices in machine learning (ML) training while preserving client privacy.However, the substantial communication overhead of FL makes training chal-lenging when edge devices have limited network bandwidth. Existing workto optimize FL bandwidth overlooks downstream transmission and does notaccount for FL client sampling.We propose GlueFL, a framework that incorporates new client samplingand model compression algorithms to mitigate low download bandwidths ofFL clients. GlueFL prioritizes recently used clients and bounds the numberof changed positions in compression masks in each round.We analyse FL convergence under GlueFL’s sticky sampling, and showthat our proposed weighted aggregation preserves unbiasedness of updatesand convergence.We evaluate GlueFL empirically, and demonstrate downstream band-width and training time savings on three public datasets. On average, ourevaluation shows that GlueFL spends 29% less training time with a 27%less downstream bandwidth overhead as compared to three state-of-the-artstrategies.iiiLay SummaryMachine learning is known as an effective approach to solving predictivetasks by leveraging large volumes of data. Federated learning moves machinelearning training to mobile devices and allows participants to collaborativelytrain a global model without disclosing their local training data. However,since the training may involve thousands to millions of participants, net-work usage becomes a performance bottleneck. Participants that have lowbandwidth act as stragglers and slow down model training.We design GlueFL, a federated learning training framework that op-timizes bandwidth usage. It consists of novel client sampling and modelcompression algorithms. These new mechanisms alleviate the impact ofclient staleness in client sampling and minimize downstream bandwidth. Weempirically demonstrate that GlueFL decreases communication costs whilepreserving model performance on three public datasets. To the best of ourknowledge, this is the first work to combine model masking with client sam-pling to reduce downstream bandwidth.ivPrefaceThis thesis presents the original and unpublished work done by the au-thor, Shiqi He, conducted in the Systopia lab at the Univerisity of BritishColumbia under the supervision of Prof. Ivan Beschastnikh. Chapters 3, 4and 5 are primarily adapted from an unpublished manuscript.This work was performed in collaboration with Qifan Yan, Feijie Wu,Prof. Mathias Lécuyer and Prof. Lanjun Wang. In this work, I developedkey ideas, implemented the proposed algorithms, and conducted most exper-iments. Qifan Yan assisted me with the implementation of sticky samplingdescribed in Chapter 3 and the experiment described in Chapter 5. FeijieWu helped me complete the theorem presented in Chapter 4. Profs. IvanBeschastnikh, Mathias Lécuyer and Lanjun Wang offered suggestions on theframework design and contributed to the manuscript writing.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Propositions . . . . . . . . . . . . . . . . . . . . . . . . . xiList of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . xiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xiii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Motivation and Background . . . . . . . . . . . . . . . . . . . 42.1 Federated Learning (FL) . . . . . . . . . . . . . . . . . . . . . 42.2 Cross-device FL Bandwidth Characteristics . . . . . . . . . . 52.3 Limitations of Existing Masking Strategies . . . . . . . . . . . 62.4 Problem Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 83 GlueFL Framework Design . . . . . . . . . . . . . . . . . . . 93.1 Sticky Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . 93.1.1 Analysis of Sampling Schemes . . . . . . . . . . . . . . 133.2 Mask Shifting . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3 Adapting other Techniques to Work with GlueFL . . . . . . . 17viTable of Contents4 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . 194.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.2 Convergence Result . . . . . . . . . . . . . . . . . . . . . . . . 194.3 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . 204.3.1 Some Useful Lemmas . . . . . . . . . . . . . . . . . . 214.3.2 Progress in one single step . . . . . . . . . . . . . . . . 214.3.3 Final Convergence Result . . . . . . . . . . . . . . . . 244.3.4 Bounded Gap between two successive local updates. . 254.3.5 Bounded gap between two successive global models . . 265 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . 295.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 295.2 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . 305.3 Performance Results . . . . . . . . . . . . . . . . . . . . . . . 325.4 Sensitivity Analysis . . . . . . . . . . . . . . . . . . . . . . . . 325.5 Network Environment . . . . . . . . . . . . . . . . . . . . . . 355.6 Ablation Study . . . . . . . . . . . . . . . . . . . . . . . . . . 355.7 Availability and Stragglers . . . . . . . . . . . . . . . . . . . . 386 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42viiList of Tables2.1 Summary of notation used in this thesis. . . . . . . . . . . . 45.1 Downstream transmission Volume (DV, in ×102 GB) andTotal transmission Volume (TV) for training different mod-els/datasets. We measure Top-1 accuracy for FEMNIST andGoogle Speech, and Top-5 accuracy for OpenImage [19]. Weset the target accuracy to be the highest achievable accuracyby all approaches. Our target accuracies are comparable withprevious work [19, 20]. The best results are in bold. . . . . . 315.2 Download Time (DT, in hours) and Total training Time(TT) for training different models/datasets. The best resultsare in bold. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.3 Downstream transmissionVolume (DV, in×102 GB),DownloadTime (DT, in hours), Total transmission Volume (TV) andTotal training Time (TT) for training ShuffleNet on FEM-NIST with different over-commitment (OC) settings. . . . . . 39viiiList of Figures2.1 (a) The distribution of network bandwidth in North America,June 2022 [25], and (b) the cumulative distribution function(CDF) of network bandwidth in (a). . . . . . . . . . . . . . . 62.2 (a) The downstream and upstream bandwidth usage of STCper round, and (b) the model size a client must downloadwhen being re-sampled after a certain number of rounds. . . . 63.1 Sticky sampling design. . . . . . . . . . . . . . . . . . . . . . 103.2 Mask shifting design with q = 10% and qshr = 9%. . . . . . . 155.1 Effect of aggregation weights νti,s and νti,r: GlueFL (Equal) isbiased (equal weights), while GlueFL is unbiased. . . . . . . 335.2 Effect of sticky group size S. . . . . . . . . . . . . . . . . . . . 335.3 Effect of sticky sampling parameter C. . . . . . . . . . . . . 345.4 Effect of shared mask ratio qshr. . . . . . . . . . . . . . . . . 345.5 Average share of time spent per round downloading (grey),uploading (red) and computing (blue). . . . . . . . . . . . . 365.6 Effect of shared mask regeneration. . . . . . . . . . . . . . . 375.7 Effect of error-compensation. . . . . . . . . . . . . . . . . . . 37ixList of Theorems1 Theorem (Unbiased Aggregation) . . . . . . . . . . . . . . . . 122 Theorem (Convergence) . . . . . . . . . . . . . . . . . . . . . 19xList of Propositions1 Proposition (Uniform Sampling) . . . . . . . . . . . . . . . . 132 Proposition (Sticky Sampling) . . . . . . . . . . . . . . . . . . 13xiList of Algorithms1 Sparse Ternary Compression (STC) . . . . . . . . . . . . . . . 72 Sticky Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . 113 GlueFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16xiiAcknowledgementsThis research was funded by the Natural Science and Engineering ResearchCouncil of Canada (NSERC) Discovery Grant (RGPIN-2020- 05203), as wellas Huawei Technologies Co. and the Data Science Institute (DSI) at theUniversity of British Columbia.First, I would like to express my deepest appreciation to my supervi-sor, Prof. Ivan Beschastnikh, who encouraged me to follow my interestsand guided me throughout this work. Without his constant support andinvaluable guidance, this work would not have achieved its present form.I would like to further thank Profs. Mathias Lécuyer and Lanjun Wangfor their contributions. They provided numerous insightful suggestions andmotivated me to work smarter. I am also grateful to my collaborators QifanYan and Feijie Wu, who spent countless nights with me on this work. It hasbeen a great pleasure working with you all.In addition, I want to give special thanks to Prof. Frank Wood and hisProgramming Languages for Artificial Intelligence (PLAI) research group.They offered GPU resources for me to conduct the experiments in this work.I also want to thank my friends in Hong Kong and Vancouver: Yutong Yang,Jiahui Huang, Jincheng Chen, Xindong Lin, Ruochen Qin, and many morewho helped me release stress during the pandemic period.Lastly, I would like to extend my thanks to my parents and my fiancée,Xinyu Ma, for their unconditional love and company. Thank you for makingmy life wonderful.xiiiChapter 1IntroductionFederated learning (FL) moves machine learning (ML) training to the edge.In FL, edge clients communicate with a central server to collaborativelytrain a global model, while keeping client training data local. We focus oncross-device FL, in which there are many clients that are end-user devices.For example, companies like Google and Intel use cross-device FL for com-puter vision and natural language processing model training across customerdevices [11, 12, 45].One downside of FL is its network usage. This is especially problematic incross-device FL, which relies on lower-bandwidth mobile or IoT devices [16].For example, Google Keyboard (Gboard), a virtual keyboard with over 1billion installs, selects clients from millions of mobile devices to enhance itssearch query suggestions [45]. In this type of application, clients usuallyhave a diversity of device-to-server (upstream) and server-to-device (down-stream) bandwidth. Clients that have either slow upstream or downstreambandwidth act as stragglers and slow down model training.This heterogeneous bandwidth setting has attracted significant research,with a focus on reducing the communication cost of FL training [7, 24, 30, 32,36]. One important strategy is client sampling, which limits the number ofclients that perform training in each round [23, 24]. Client sampling reducesboth upstream and downstream bandwidth. However, a client that is notsampled gradually becomes stale: its local state diverges from the stateof clients that have been sampled. The next time this client is sampled,the central server must therefore send a larger state update, increasing thedownstream transmission overhead.Another approach to reducing FL bandwidth usage is to apply a maskto the client gradients, such as a sparsification mask [32, 38] or a parameterfreezing mask [5, 7]. In traditional masking schemes, clients apply a maskto their local gradients and only transfer significant gradients to the server.This saves upstream bandwidth. Since each client generates the mask locallyand independently, however, the entire model is usually updated at the endof a round and needs to be fully synchronized. In server masking schemes,such as Sparse Ternary Compression (STC) [32] and Adaptive Parameter1Chapter 1. IntroductionFreezing (APF) [7],the server uses a mask to compute the final model update. Since theserver only partially updates the model, only a part of the model needs tobe sent back to clients; this saves downstream bandwidth.User sampling and masking approaches are typically considered as or-thogonal, compatible approaches [7, 32]. Though existing masking strategiesare indeed empirically effective in full participation FL, we show that whenclient sampling is used they fail to decrease downstream bandwidth (§2). Forexample, with a 0.01 sample ratio and a masking compression ratio of 10%,a single client needs to download 75% of the global model on average.The reason downstream bandwidth increases is because of the stalenessof local state at the clients. To see why, let us first consider the full participa-tion case. Intuitively, since the global model is only partially updated by theserver under masking, a client only needs to download this partial updateand apply it to its local version of the model, saved from the previous round.With client sampling however, a typical client skips multiple rounds by notbeing sampled, and its local model state becomes stale. When the clientis later sampled, it needs to download the new value of all parameters up-dated in the skipped rounds, which amounts to a large fraction of the model.This effect increases downstream bandwidth usage, voiding the benefits ofserver masking, and slowing down training when edge devices have limiteddownload capacity [1].To resolve the incompatibility between masking and client sampling, wepropose GlueFL, a new FL training framework specifically designed to retainthe benefits of masking when using client sampling. This compatibility isparticularly important in cross-device FL deployments, which require bothclient sampling (full participation is impractical) and bandwidth savings dueto mobile or IoT clients. To the best of our knowledge, GlueFL is the firstmasking design to address the downstream bandwidth bottleneck in cross-device FL with client sampling.We design GlueFL with two new mechanisms to alleviate client stalenessand to optimize downstream bandwidth requirements. First, we introducesticky sampling (§3.1) to prioritize the most recently used clients, therebyreducing the number of stale clients in each update. Since recently selectedclients have an up-to-date view of model parameters, they need to downloadsmaller updates. We combine sticky sampling with a weighted central aggre-gation scheme to ensure that model updates remain unbiased, a requirementfor convergence (§4). Sticky sampling is especially important in practicalimplementations that sample a small fraction of clients in each round [45].Second, we propose a gradual mask shifting strategy (§3.2), to ensure2Chapter 1. Introductionthat consecutive central model updates share a large number of changedparameters, while empirically preserving model convergence. This way, anewly selected client only has to synchronize a subset of the model, evenafter several rounds of not being sampled.To sum up, we make three contributions:⋆ We present an FL design called GlueFL, which is based on sticky sam-pling and mask shifting. These two new mechanisms alleviate the im-pact of client staleness in client sampling. Both techniques minimizedownstream bandwidth in cross-device FL. To the best of our knowl-edge, this is the first work to combine masking with client sampling toreduce downstream bandwidth.⋆ We analyse FL convergence under GlueFL’s sticky sampling, and showthat our proposed weighted aggregation preserves unbiasedness of up-dates and convergence.⋆ We evaluate GlueFL empirically, and demonstrate downstream band-width and training time savings on three public datasets. On average,our evaluation shows that GlueFL spends 29% less training time with a27% less downstream bandwidth overhead as compared to FedAvg [24],STC [32] and APF [7].3Chapter 2Motivation and BackgroundWe start by reviewing standard FL with client sampling. Then we introducea state of the art masking strategy called STC [32], and discuss its limita-tions. Finally, we formalize the problem that we set out to solve in the restof the thesis. Table 2.1 overviews our notation.Table 2.1: Summary of notation used in this thesis.N , N, i set, total number, index of clientsK,K set, number of sampled clientsT, t number, index of communication roundsE, e number, index of local update stepswt server model in round twt,ei ,gt,ei model, gradients of client i in round t and step eS, S set, size of sticky groupC, C set, number of clients sampled from SR, R set, number of clients sampled from N \ Sνi,s, νi,r aggregation weight of client i in C, Rq, qshr total, shared mask ratio2.1 Federated Learning (FL)Consider a system with N clients, coordinated by a central server. Eachclient i has a local data distribution Di. Let us denote the weight of clienti as pi such that∑Ni=1 pi = 1. The weight pi is given by the server andrepresents the importance of the i-th client’s local loss function. Under thenon-convex settings, our target is formulated asminw∈RdF (w)△=N∑i=1piFi(w) (2.1)where Fi(w) = 1|Di|∑ξ∈Di ℓ(w, ξ), and ℓ(w, ξ) is the empirical loss on modelw and sample ξ. In practice, Fi(w) is generally estimated with a ran-42.2. Cross-device FL Bandwidth Characteristicsdom realization ξi drawn from Di, which is assumed to be unbiased, i.e.,Eξi∼Diℓ(w, ξi) = Fi(w). Let F∗ is the minimum value of the global objec-tive, i.e., F (w) ≥ F∗ for any w ∈ Rd.FedAvg [24] is a standard algorithm to solve Equation (2.1). To improvecommunication efficiency, clients are selected uniformly at random in eachround. The FedAvg algorithm with client sampling looks as follows:1. At the beginning of round t, the server uniformly at random samplesa subset of clients (i.e., K) and broadcasts the latest global model wtto these sampled clients.2. Each sampled client i ∈ K receives the model wt (= wt,0i ) and runs Elocal SGD iterations to compute a local update ∆ti = −γ∑E−1e=0 gt,ei ,where γ is the client learning rate. In each iteration, the client com-putes the gradient as gt,ei = ∇ℓ(wt,ei , ξt,ei ) where ξt,ei is drawn fromDi.3. The server receives updates ∆ti from all sampled clients and aggregatesthem to compute the new global model [22]wt+1 = wt +NK∑i∈Kpi∆ti (2.2)In expectation, the steps above realize an update form EK[wt+1]= wt+∑Ni=1 pi∆ti in each round. To ensure that the global loss approaches theoptimal one, FedAvg repeats the process for T rounds. FedAvg achieves aconvergence rate of O(√EKT)[17, 44] under partial worker participation.2.2 Cross-device FL Bandwidth CharacteristicsThe cross-device FL setting relies on a large number of clients. In this case,some clients are likely to have an unreliable or slow network. For exam-ple, Figure 2.1 shows the bandwidth distribution estimated by measurementlab [25]. We observe that around 20% of devices have a download bandwidthof at most 10Mbps. These devices can take at least 20s to download a typicalmodel like ShuffleNet_V2 [46], which is specially designed for mobile devicesand contains 5 million model parameters.52.3. Limitations of Existing Masking Strategies100 101 102 103Download (Mbps)100101102103Upload (Mbps)(a)100 101 102 103Bandwidth (Mbps)0.00.20.40.60.81.0Cumulative probability UploadDownload(b)Figure 2.1: (a) The distribution of network bandwidth in North America,June 2022 [25], and (b) the cumulative distribution function (CDF) of net-work bandwidth in (a).0 10 20 30 40 50 60 70 80 90Communication Rounds0100200300400500600700800MB Down (q=20%)Down (q=10%)Up (q=20%)Up (q=10%)(a)0 5 10 15 20 25 30 35 40 45Communication Rounds051015202530MBDown (q=20%)Down (q=10%)(b)Figure 2.2: (a) The downstream and upstream bandwidth usage of STC perround, and (b) the model size a client must download when being re-sampledafter a certain number of rounds.2.3 Limitations of Existing Masking StrategiesPrior work has proposed several masking strategies to reduce the amountof transferred data and alleviate low bandwidth issues [5, 7, 32, 38]. Todemonstrate how masking fails to optimize downstream bandwidth in FLwith client sampling, we use STC [32], a popular server masking strategy, asa representative technique.STC builds on top-k sparsification [34], a masking approach that selectsand uploads the largest q (e.g., 10%) absolute values in a client’s local gra-62.3. Limitations of Existing Masking StrategiesAlgorithm 1: Sparse Ternary Compression (STC)Output: wT1 for t← 1 to T do2 /* Server:client sampling */3 Generate set of sampled clients K ;4 Broadcast wt to K ;5 /* Client:local training */6 for i ∈ K in parallel do7 wt,0i ← wt ;8 for e← 0 to E − 1 do9 wt,e+1i ← wt,ei − γgt,ei ;10 end11 /* Client:sparsification */12 ∆˜ti ← topq(wt,Ei −wt,0i ) ;13 end14 /* Server:aggregation */15 Receive ∆˜ti from worker i ∈ K ;16 /* Server:sparsification */17 ∆˜t ← topq(∑i∈K piNK ∆˜ti) ;18 wt+1 ← wt + ∆˜t;19 enddients. In STC, this top-k sparsification technique is applied to both clients’gradients and server updates1. Algorithm 1 shows this masking-only ver-sion of STC. For a single client sampled in both the current and last round,STC only has to update the weights covered by the server mask (line 17).However, note that a client that has not been sampled recently may have toupdate the entire model, as their local view of the model is stale. The reasonis that server masks change in each round, and the client has to synchronizeall updated model parameters since it last participated.To measure the impact of model staleness on downstream bandwidth, weapply STC to FedAvg and conduct experiments on FEMNIST, using N =2, 800 clients and a client sample size of K = 30. We try compression ratios1For simplicity, we only consider the masking part of STC. STC also includes quanti-zation, an orthogonal technique that can be combined with sparsification [2, 15] and willnot change our conclusion, as quantization compresses both downstream and upstreamcommunication.72.4. Problem Setupof 10% and 20%2. We examine both downstream and upstream bandwidthusage in each round. The results in Figure 2.2 show that upstream bandwidthis reduced when using a smaller compression ratio, as expected. However, aclient still needs to download 70% of the global model on average. Clientswith 10Mbps download bandwidth (§2.2) will take at least 14s to receivethese changes. This imposes a high downstream bandwidth requirementson participating clients. In general, the more rounds that a client skips,the more updated model state it needs to download (Figure 2.2(b)). Asa result, the training bottleneck shifts to downstream communication. Weexpect these results to hold for other masking strategies as they similarlyupdate different parts of the global model in each communication round.For example, in APF [7], model parameters are frozen in some rounds butwill then be updated again after the freezing period ends. The downstreambottleneck is therefore a general limitation across masking strategies.2.4 Problem SetupOur goal in GlueFL is to minimize the total expected downstream bandwidthof training, while retaining a low upstream bandwidth, and ensuring that theexpected global training loss F (wT ) converges to a local minimum value,where wT is the aggregated global model after T rounds.2Smaller values led STC to require an unacceptable number of rounds to converge witha noticeable drop in convergence accuracy.8Chapter 3GlueFL Framework DesignGlueFL includes two components to decrease the downstream bandwidthduring FL training: sticky sampling (Figure 3.1) and mask shifting (Fig-ure 3.2). The newly designed sampling scheme allows some clients to bere-sampled in a short term and mask shifting restricts the mask from chang-ing too fast. We elaborate on the design of each of these components in §3.1and §3.2, before describing how to adapt other existing mechanisms in §3.3.3.1 Sticky SamplingClient sampling is the process of selecting K out of N clients in each round,to participate in computing the model update. With uniform sampling,each client participates in each round with a probability of K/N . Thus, aclient is expected to participate in training every N/K rounds on average(See Proposition 1 in Appendix 3.1.1). In cross-device FL systems, thevalue of N is often large, and K is small. For example, Gboard samplesK = 100 clients in each round while there are millions of devices [45]. Thisproduces a low probability of participation in each round, which means thaton average clients skip a large number of training rounds before being selectedagain. As we saw in §2.3, these long skips are responsible for local statestaleness. Clients’ state must therefore be re-synchronized when they areselected, reducing the benefits of masking on downstream bandwidth.GlueFL introduces sticky sampling to ensure that clients with an up-to-date local state are more likely to be selected. Figure 3.1 illustrates stickysampling and Algorithm 2 details it. The server maintains a smaller stickygroup of clients S with size S, while the remaining clients form a non-stickygroup, N \ S. We randomly select S clients to initialize S in the beginningof training, and allow S to evolve over time.Figure 3.1 (step 1) illustrates how in each FL training round, the serverconstructs its sampled set of clients K from two sources; K = C ∪ R. Itsamples C clients to construct C by sampling from the current sticky groupS. It samples (K−C) clients to constructR by sampling from the non-sticky93.1. Sticky SamplingKSampledclientsSSticky clientsN-SNon-sticky clientsCK-CKK-CStep 1: Sample clients for trainingStep 2: Rebalance non-sticky and sticky groups with sampled clientsNon-sticky clients Sticky clientsSampledclientsFigure 3.1: Sticky sampling design.group, without replacement. All sampled clients K participate in one roundof training (Algorithm 2 line 5).At the end of the round (Figure 3.1 (step 2)), the server randomly selects(K − C) clients from S \ C (the set of clients in the sticky group that didnot participate in the latest round) and removes these clients from the stickygroup (Algorithm 2 line 20). The server replaces these clients with (K −C)clients that were not sampled from the sticky group and that participatedin the last update (R in Algorithm 2).Just as with uniform client sampling, sticky client sampling requiresN/Krounds to re-sample a client on average (see Proposition 2 for details). How-ever, a client selected with sticky sampling will join the sticky group andthen have a higher probability of being selected in the next round than un-der uniform sampling, as long as CS >KN . Since a client that exits the stickygroup (by not being selected in the current round) is less likely to be se-lected than under uniform sampling (K−CN−S <KN whenCS >KN ), we need toensure that a sticky client has a higher expectation of being included duringthe next several rounds. This is because after several missed rounds, thewhole model needs to be synchronized (see Figure 2.2(b)). Proposition 2 inAppendix 3.1.1 shows the probability for a client in the sticky group to be103.1. Sticky SamplingAlgorithm 2: Sticky SamplingOutput: wT1 for t← 1 to T do2 /* Server:sample clients */3 Randomly select |C| = C clients from S;4 Randomly select |R| = K − C clients from N \ S;5 Set of sampled clients K ← C ∪R;6 Broadcast wt to K;7 /* Client:local training */8 for i ∈ K in parallel do9 wt,0i ← wt ;10 for e← 0 to E − 1 do11 wt,e+1i ← wt,ei − γgt,ei ;12 end13 ∆ti ← wt,Ei −wt,0i ;14 end15 /* Server:aggregation */16 Receive ∆ti from worker i ∈ K;17 ∆t ←∑i∈C νti,s∆ti +∑i∈R νti,r∆ti ;18 wt+1 ← wt +∆t;19 /* Server:rebalance non-sticky and sticky groups */20 Randomly remove K − C clients in S \ C ;21 S ← S ∪R ;22 endselected after r rounds. We use this formula to select S and C to ensure thatthis probability is higher than that of uniform sampling for a high enoughvalue of r.Case Study. Consider a training run on FEMNIST with N = 2, 800clients, K = 30, S = 120, and C = 24 (our default experimental setup in§5.2). In this case, using the Proposition 1 and Proposition 2 in Appendix,we can compute the probability of client inclusion over the next 6 rounds fora client starting in the sticky group: 20.0%, 15.0%, 11.2%, 8.5%, 6.4%, 4.8%.By contrast, uniform sampling re-samples clients with a probability of around1.1%.With sticky sampling, clients that just participated in a round, and thushave an up-to-date state, are more likely to participate again in the shortterm. Such clients will therefore download smaller model updates. This113.1. Sticky Samplingsynergizes with masking approaches that reduce the size of an update ineach round. We show in §5 that for cross-device FL, where a large N and asmall K are typical, masking approaches with sticky sampling significantlyreduce downstream bandwidth usage.However, sticky sampling also introduces new challenges during aggre-gation. As discussed in §2, the global update should provide appropriaterepresentation for every client in expectation [26, 37, 40]. Formally, the up-date should be an unbiased estimate of the FedAvg update computed onevery client in round t. That is: EK[∆t] =∑Ni=1 pi∆ti. Under the FedAvgaggregation function (Equation (2.2)), since sticky clients are selected withhigher probability, they would have a larger weight then non-sticky clients.To correct for this bias, GlueFL uses an inverse propensity weighted ag-gregation function. It assigns a different weight to updates from clients ofdifferent groups, corresponding to their importance parameter re-weightedby the inverse probability of selection. Updates from sticky group clientsuse the weight νti,s =SC pi, while non-sticky group clients use the weightνti,r =N−SK−C pi. The model update rule then becomes:wt+1 ← wt +∑i∈Cνti,s ·∆ti +∑i∈Rνti,r ·∆ti︸ ︷︷ ︸∆t(3.1)This is shown in lines 17 and 18 of Algorithm 2.With this reweighting scheme in place, we can show that sticky samplingudpates are unbiased:Theorem 1 (Unbiased Aggregation). Let K = C ∪ R be the set of sampledclients in sticky sampling. The update ∆t computed in Equation (3.1) isunbiased. That is:EK[∆t] =N∑i=1pi∆ti (3.2)Proof. We can rewrite the update as a sum over all the data, where the123.1. Sticky Samplingprobability of inclusion cancels out with the aggregation weight:EK[∆t] = EK[∑i∈CSCpi∆ti +∑i∈RN − SK − Cpi∆ti]= EK∑i∈S1{i∈C}SCpi∆ti +∑i∈N\S1{i∈R}N − SK − Cpi∆ti=∑i∈SCSSCpi∆ti +∑i∈N\SK − CN − SN − SK − Cpi∆ti=N∑i=1pi∆tiwhere 1{predictate} is the indicator function with value 1 when the predicateis true, and 0 otherwise.§ 4.3 shows that estimating unbiased updates is key to analyzing theconvergence of GlueFL, following proof techniques from [8, 9].3.1.1 Analysis of Sampling SchemesIn this section, we provide a comparison between uniform sampling andsticky sampling to demonstrate the advantage of sticky sampling. We firstanalyze the probability that a client is re-sampled after r rounds and thengive the expected number of rounds for a client to be re-sampled.Proposition 1 (Uniform Sampling). Suppose a client is sampled at the cur-rent round. With uniform sampling, there is a probability of KN (1 − KN )r−1that the client is sampled after r rounds. On average, a client is sampledevery N/K rounds.Proof. The client is sampled with a probability of KN . The client has not beenselected for the first (r − 1) rounds. Thus, this happens with a probabilityof KN (1 − KN )r−1. Furthermore, the value of averaged sampled rounds is∑∞r=1KN (1− KN )r−1 · r = N/K.Proposition 2 (Sticky Sampling). Suppose a client is sampled at the currentround. Using sticky sampling, the client in the sticky group is sampled with aprobability of 1(N−S)K−(K−C)S (K(NC−SK)S (1−KS )r−1+(K−C)2(1−K−CN−S )r−1)after r rounds. As expected, the client trains a model every N/K rounds.133.2. Mask ShiftingProof. In the sticky group, a client is sampled or moved to the non-stickygroup with the probability of CS andK−CS , respectively. And, a client issampled from the non-sticky group with probability K−CN−S .There are two strategies to sample a client that has participated in modeltraining. First, it is sampled from the sticky group, where the probabilityis CS (S−KS )r−1 after r rounds. Second, it is sampled from the non-stickygroup, indicating the client is moved out of the sticky group in the middle.Therefore, the probability is∑r−1i=1 (1−K−CN−S )i−1 ·K−CN−S ·(S−KS )r−i−1 ·(K−CS ) =(K−C)2(N−S)K−(K−C)S ((1−K−CN−S )r−1−(S−KS )r−1). By summing up these two prob-abilities, we can obtain the desired result. Furthermore, similar to Proposi-tion 1, we can calculate the value of averaged sampled rounds.Discussion According to the proof of Proposition 2, the probability of aclient in the sticky group being sampled after r rounds is greater or equal toCS (S−KS )r−1, which is the probability that it is still sampled from the stickygroup. Then, for r ∈ {1, . . . , 1 +⌊(log CNSK)/(log S(N−K)N(S−K))⌋}, CS (S−KS )r−1is greater or equal to KN (1− KN )r−1, the probability that a client is sampledafter r rounds in uniform sampling (Proposition 1).3.2 Mask ShiftingSticky sampling allows clients in a sticky group to be sampled more fre-quently. However, sticky sampling alone is insufficient. As we have seen inFigure 2.2, a client re-sampled after 10 rounds still needs to download around50%-80% of the global model on average. This is because the masked updatesof two successive rounds (e.g., ∆˜t and ∆˜t+1) have little overlap.We solve this issue by designing a gradual mask shifting strategy, thatprevents the mask from changing too quickly while ensuring that the totalcompression ratio is maintained. Figure 3.2 illustrates our mask shiftingdesign. We construct a shared mask with compression ratio qshr (with qshr <q), which is represented using a bitmap shared with selected clients in M t ∈Bd in round t. Clients send their update for parameters in M t, as well as aq− qshr proportion of locally important parameters. The server will use M tas well as locally important parameters to calculate the model update, and toshift M t to obtain M t+1, while keeping a large overlap between consecutivemasks.Algorithm 3 details the mechanism, with sticky sampling from Algo-rithm 2 used to select clients in lines 5 and 28. The server first synchronizes143.2. Mask Shifting(b) Clients send their local masks and masked model updates to server(a) Server sends shared mask andlatest model state to clientsLocal client 1 maskServerLocal client K mask …Shared mask global modelShared maskShared mask global model…Clients Client 1 maskedparam gradientsClient K maskedparam gradients……Compute Sparse Update global modelComputeTop - Aggregation<latexit sha1_base64="4mSRiAOC1HPbUsbyd7QN48T yFAA=">[binary] MH4xeNAQ==</latexit>t global model<latexit sha1_base64="bucQ6NxnLtyaZoxy51aSK5G1WG8=">[binary]</latexit>t+ 1RoundRound<latexit sha1_base64="2FjbS9aJBtfFwfZmOb7VFl30648=">[binary]</latexit>qshr = 9%Roundshared mask<latexit sha1_base64="bucQ6NxnLtyaZoxy51aSK5G1WG8=">[binary]</latexit>t+ 1<latexit sha1_base64="2FjbS9aJBtfFwfZmOb7VFl30648=">AAAB9HicbVBNS [binary]</latexit>qshr = 9%<latexit sha1_base64="wBc4tLnXxZJb9MT6yqB5dNohsyo=">[binary]</latexit>q  qshr = 1%<latexit sha1_base64="wBc4tLnXxZJb9MT6yqB5dNohsyo=">[binary]</latexit>q  qshr = 1%<latexit sha1_base64="2FjbS9aJBtfFwfZmOb7VFl30648=">AAAB9HicbVBNS [binary]</latexit>qshr = 9%<latexit sha1_base64="2FjbS9aJBtfFwfZmOb7VFl30648=">AAAB9HicbVBNS [binary]</latexit>qshr = 9%<latexit sha1_base64="4mSRiAOC1HPbUsbyd7QN48T yFAA=">[binary] MH4xeNAQ==</latexit>tRound<latexit sha1_base64="4mSRiAOC1HPbUsbyd7QN48TyFAA=">AAAB6HicbVBNS8NAEJ3Ur1q/qh69LBbBU0mkq [binary]</latexit>tRound<latexit sha1_base64="V6YgtPOEOEtppgFPiPpF5fwEIRY=">[binary]</latexit>qshrFigure 3.2: Mask shifting design with q = 10% and qshr = 9%.the global modelwt with sampled clients and distributesM t to them (line 7).In line 16, the client i calculates the shared local gradient ∆˜ti,shr as Mt⊙ ∆˜ti,where ⊙ sets those positions that are not covered by the masks to zero. Next,the algorithm computes unique local gradients ∆˜ti,uni by selecting a (q−qshr)proportion of the largest values in other (previously masked) positions, toprovide more local information to the server (line 17). Finally, client i sends∆˜ti,shr and ∆˜ti,uni to the server.During aggregation, the central server uses sticky sampling importanceweights νti,s, νti,r given in §3.1. The server first computes the shared update∆˜tshr based on all client (weighted) updates, and the update based on uniquelocal information by selecting the (q − qshr) proportion of largest overall(weighted) gradients (line 23). Formally, each quantity is computed as:∆˜tshr ←∑i∈Cνti,s∆˜ti,shr +∑i∈Rνti,r∆˜ti,shr (3.3)∆˜tuni ← top(q−qshr)(∑i∈Cνti,s∆˜ti,uni +∑i∈Rνti,r∆˜ti,uni)(3.4)These updates are combined and update the global model (line 24). Finally,the shared mask is updated by selecting a share qshr of parameters with thelargest update values in the combined update (line 26). Since the new maskM t+1 will be used to compute ∆˜t+1, the overlap of two successive modelupdates ∆˜t and ∆˜t+1 is at least qshr.153.2. Mask ShiftingAlgorithm 3: GlueFLOutput: wT1 for t← 1 to T do2 /* Server:sticky sampling */3 Randomly select |C| = C clients from S;4 Randomly select |R| = K − C clients from N \ S;5 Set of sampled clients K ← C ∪R ;6 Synchronize wt with K by sending model updates;7 Send shared mask M t to i ∈ K;8 /* Client:local training */9 for i ∈ K in parallel do10 wt,0i ← wt ;11 for e← 0 to E − 1 do12 wt,e+1i ← wt,ei − γgt,ei ;13 end14 /* Client:masking */15 ∆ti ← wt,Ei −wt,0i ;16 ∆˜ti,shr ←M t ⊙∆ti ;17 ∆˜ti,uni ← top(q−qshr)(¬M t ⊙∆ti) ;18 end19 /* Server:aggregation */20 Receive ∆˜ti,shr, ∆˜ti,uni from worker i ∈ K ;21 Compute ∆˜tshr via Equation (3.3) ;22 Compute ∆˜tuni via Equation (3.4) ;23 ∆˜t ← ∆˜tshr + ∆˜tuni;24 wt+1 ← wt + ∆˜t;25 /* Server:update shared mask */26 M t+1 ← topqshr(∆˜tshr + ∆˜tuni) ;27 /* Server:update sticky group S */28 Randomly remove K − C clients in S \ C ;29 S ← S ∪R ;30 end163.3. Adapting other Techniques to Work with GlueFL3.3 Adapting other Techniques to Work withGlueFLWe further improve the performance of GlueFL by adapting common FLtechniques to sticky sampling and mask shifting [7, 10, 29, 33, 35, 42].Shared Mask Regeneration Previous work [7, 10] showed that modelparameters converge at different rates. Meanwhile, a parameter that hasconverged may become unstable in later rounds. For example, according to[7], it is possible that some 10% of parameters are unstable in both round tand t+1, while another 5% parameters are only unstable in round t+1. Inthis case, a small (q − qshr) (e.g., 2%) value will slow down convergence, asthe shared mask fails to cover the gradients of the unstable 5% of parametersand a large (q − qshr) (e.g., 10%) value incurs more bandwidth cost.To address this, we use a small (q − qshr) value while re-generating theentire shared mask M t every I rounds. To regenerate, we set qshr = 0 andupdate M t as topqshr(∆˜tuni) (Algorithm 3, line 26). Although this processintroduces more downstream overhead in the next few rounds, it speeds uptraining and reduces overall bandwidth.Error-Compensation Compression methods, such as quantization andsparsification, slow down model convergence due to the loss of informationin client updates [29, 35, 42]. Error-compensation is a technique to alleviatethis problem, first proposed to accelerate convergence in 1-bit SGD [33].The key idea is for clients to (1) remember their local compression error(the difference between their true update and what is actually sent to theserver), and (2) add it into the next round’s computed local gradient beforecompression. In GlueFL, we apply error compensation as:∆ti ← ∆ti +νφ(t)iνti· hφ(t)i (3.5)where νti is the aggregation weight applied at step t for client i (i.e., νti,s ifthey are in the sticky group, νti,r otherwise; their exact values are definedin §3.1), φ(t) indicates the step-index when client i was last selected, andhφ(t)i the compensation vector for client i in round φ(t). After that, theclient computes ∆˜ti,shr and ∆˜ti,uni (Algorithm 3, lines 16-17). Then, thecompensation vector is calculated as hti = ∆ti − (∆˜ti,shr + ∆˜ti,uni).The reason for scaling with hφ(t)i in Equation (3.5) is to ensure that clienti’s compensation is consistent with the aggregation in sticky sampling. As173.3. Adapting other Techniques to Work with GlueFLthe compensation only applies to a client’s local gradient before masking, thisoptimization does not introduce extra bandwidth and improves convergenceperformance.18Chapter 4Convergence AnalysisFrom a theoretical perspective, we show that GlueFL without masking canachieve convergence at a rate of O(1/√T ) for smooth non-convex functionsunder two assumptions (§4.1). §4.2 states our result and their interpretation,with details in §4.3.4.1 AssumptionsWe make a standard assumption that clients sample a mini-batch in eachlocal update such that the computed gradient is equal to the true gradientin expectation [17, 22, 37, 41, 44]. That is, Eξi∼Di∇fi(w, ξi) = ∇Fi(w) forall workers i ∈ {1, . . . , N} and the model w ∈ Rd, where ξi and Di representthe mini-batch and the local training set, respectively.We make two more assumptions:Assumption 1 (Bounded Local Variance). There exists a constant σ > 0,such that the variance of each local gradient estimator is bounded by,Eξi∼Di∥∇fi(w, ξi)−∇Fi(w)∥ ≤ σ2, ∀i ∈ [N ].We also assume that the local objective functions (i.e., F1, . . . , FN ) andtheir derivatives are Lipschitz continuous.Assumption 2 (Continuity and Smoothness). The local objective functionsare Lc-continuous and Ls-smooth.4.2 Convergence ResultHere we analyze the convergence rate of sticky sampling (Algorithm 2) onnon-convex local objective functions. See §4.3 for the complete proof.194.3. Proof of Theorem 2Theorem 2 (Convergence). Suppose Assumptions 1 and 2 hold, and set theaggregation weights as νti,s =SC pi and νti,r =N−SK−C pi. Let the learning rate beγ =√1E(σ2 + E)· KTA(4.1)Algorithm 2 is such that:mint∈{1,...,T}∥∥∇F (wt)∥∥22= O(√(1 +σ2E)· AKT)+O(KTA)(4.2)where A = KN(S2C +(N−S)2K−C)(∑Ni=1 p2i). We treat Ls, Lc, and F (w1)− F ∗as constants.This result gives a convergence rate for reaching a fixed point duringmodel training.Comparison with FedAvg. If all clients have equal weights, (i.e.,pi =1N for all workers i ∈ {1, . . . , N}), and the sticky group does not exist(i.e., S = 0), the algorithm reduces to FedAvg, and A = 1. As we cansee, when we set the number of local updates E ≥ σ2 and T is sufficientlylarge, the convergence result is led by O(√1KT). This is comparable to thestate-of-the-art works on convergence of FedAvg as described in §2.1. Sticky-sampling introduces a variance cost (the S2C +(N−S)2K−C term in A) to remainunbiased under non-uniform client sampling. Next, we show empirically thatthis is a favorable trade-off given the bandwidth savings enabled by stickysampling (§5).4.3 Proof of Theorem 2In this section, we theoretically analyze the convergence rate of sticky-sampling in GlueFL on non-convex functions, under Assumptions 1 and 2.The conclusion has been mentioned in Theorem 2. The proof follows thesame template as those of [4, 17, 37, 44], and proceeds as follows: (1) we useLemma 1 to bound the expected progress in each step (§4.3.2) by a sum oftwo terms. (2) We bound the first term through a bound on local updates(§ 4.3.4) and our unbiased aggregation. (3) We bound the second term byadapting a bound on the norm between two consecutive models to accountfor our aggregation weights (§4.3.5). (4) We use the bound on the expected204.3. Proof of Theorem 2progress in each step in a telescopic sum to bound the overall progress overtraining (§4.3.3).We first present steps (1) and (4) in § 4.3.2 and 4.3.3, which represent thehigh level articulation of the proof, before presenting the lower level resultsfor steps (2) and (3) in § 4.3.4 and 4.3.5.4.3.1 Some Useful LemmasIn this section, we provide two useful lemmas, which will apply to our sub-sequent analysis in §4.3. Lemma 1 is used to present the progress in onesingle step in FL (§4.3.2) and Lemma 2 is used to bound the gap betweentwo successive global models (Lemma 4).Lemma 1 ([4]). Suppose a function H is Lc-continuous and Ls-smooth. Forany w, v ∈ Rd, the following inequality holds for H:∥∇H(w)∥2 ≤ Lc; H(w) ≤ H(v) + ⟨∇H(v), w − v⟩+ Ls2∥w − v∥22Lemma 2 (Lemma 4 in [17]). Let ε = {ε1, . . . , εa} be a random variables inRd, which are not assumed to be independent. If E [εi] = ei, and the varianceis bounded by E[∥εi − ei∥22]≤ σ2, we have:E∥∥∥∥∥a∑i=1εi∥∥∥∥∥22 ≤ ∥∥∥∥∥a∑i=1ei∥∥∥∥∥22+ a2σ2If we further suppose that E [εi|εi−1, . . . , ε1] = ei, in which case the {εi −ei} form a martingale difference sequence, and the bound of the varianceE[∥εi − ei∥22]≤ σ2 holds, we have the following, tighter bound:E∥∥∥∥∥a∑i=1εi∥∥∥∥∥22 ≤ 2 ∥∥∥∥∥a∑i=1ei∥∥∥∥∥22+ 2aσ24.3.2 Progress in one single stepWe first bound the expected progress after one step of the model update.By definition, wt+1 = wt − γ∑i∈Kt νti∑E−1e=0 ·gt,ei , where νti can be eitherνti,s or νti,r depending on the client’s membership. Since all local objective214.3. Proof of Theorem 2functions are Ls-smooth, the global objective F is Ls-smooth as well. Thus,according to Lemma 1, we have:Et+1|t[F(wt+1) ]− F (wt) ≤ Et+1|t 〈∇F (wt),wt+1 −wt〉︸ ︷︷ ︸Q1(4.3)+Ls2Et+1|t∥∥wt+1 −wt∥∥22︸ ︷︷ ︸Q2(4.4)where Et+1|t means the expected value at round (t+ 1), condition on allinformation at round t, including the model wt and the participants Kt−1.The expectation is over the randomness of client selection (Kt) and batchselection at the client’s (ξi ∼ Di from § 2.1).We first provide the upper bound analysis for term Q1. Intuitively,our unbiased aggregation combines with a technical client local drift boundadapted from previous work (§ 4.3.4) to decompose this term. Rememberthat as Theorem 1 indicates, our weighted update is an unbiased estimateof the true update over all clients. That is:Et+1|t[wt+1 −wt]= Et+1|t[∆t]=N∑i=1piEξi∼Di[∆ti], (4.5)where we decomposed Et+1|t in the randomness over client sampling,and local updates. The expectation in the right-hand side is over the lo-cal training steps of each client. Based on the form of local updates, wehave that Eξi∼Di[wt,Ei − wt]= −γ∑E−1e=0 Eξi∼Di[gt,ei ]. Considering theunbiased estimation assumption mentioned in Section 2.1, we have that∀e, i : Eξi∼Di[gt,ei]= −∇Fi(wt,ei )]. Therefore, the term Q1 above canbe bounded as follows:224.3. Proof of Theorem 2Q1 = Et+1|t〈∇F (wt),wt+1 −wt〉 (4.6)=〈∇F (wt),−γN∑i=1pi ·(E−1∑e=0Eξi∼Di[gt,ei])〉(4.7)= −γE ·〈N∑i=1pi∇Fi(wt),N∑i=1E−1∑e=0piEEξi∼Di[∇fi (wt,ei ) ]〉(4.8)= −γE2· ∥∥∇F (wt)∥∥22− γE2∥∥∥∥∥N∑i=1E−1∑e=0piE∇Fi(wt,ei)∥∥∥∥∥22(4.9)+γE2∥∥∥∥∥N∑i=1E−1∑e=0piEEξi∼Di[∇fi(wt)−∇fi (wt,ei ) ]∥∥∥∥∥22(4.10)≤ −γE2· ∥∥∇F (wt)∥∥22− γ2E∥∥∥∥∥N∑i=1E−1∑e=0pi∇Fi(wt,ei)∥∥∥∥∥22(4.11)+γE2·N∑i=1E−1∑e=0piEEξi∼Di[ ∥∥∥∇fi(wt)−∇fi (wt,ei )∥∥∥22](4.12)≤ −γE2· ∥∥∇F (wt)∥∥22− γ2E∥∥∥∥∥N∑i=1E−1∑e=0pi∇Fi(wt,ei)∥∥∥∥∥22(4.13)+γL2s2·N∑i=1E−1∑e=0piEξi∼Di[ ∥∥∥wt −wt,ei ∥∥∥22](4.14)where the last equality follows from the fact that ⟨a, b⟩ = 12a2+ 12b2− 12(a−b)2 and the assumption we make in § 4.1 that Eξi∼Di[∇fi(w, ξi)] = ∇Fi(w);the first inequality follows from Jensen’s Inequality because∑Ni=1∑E−1e=0piE =1; and the next inequality from the Ls-smoothness assumption.Plugging Lemma 3 into the above bound for Q1, and using Lemma 4 to234.3. Proof of Theorem 2bound Q2, we have that:Et+1|t(F(wt+1))− F (wt) (4.15)≤− γE2∥∇F (wt)∥22 +3γ3E2L2s2(ELc + σ2) (4.16)+Lsγ22· E(∑i∈CtS2C2p2i +∑i∈Rt(N − SK − C)2p2i)Eσ2 (4.17)+Lsγ22E2L2c∑i∈StSCp2i +∑i∈N\StN − SK − Cp2i (4.18)−(γ2E− Lsγ22)∥∥∥∥∥N∑i=1E−1∑e=0pi∇Fi(wt,ei)∥∥∥∥∥22(4.19)4.3.3 Final Convergence ResultLet γ ≤ 1ELs . By averaging the above inequality over t from 1 to T , we have:1TT∑t=1Et+1|t(F (wt+1)− F (wt)) (4.20)≤ −γE2T∥∇F (wt)∥22 +3γ3E2L2s2(ELc + σ2) (4.21)+Lsγ2Eσ22TT∑t=1E(∑i∈CtS2C2p2i +∑i∈Rt(N − SK − C)2p2i)(4.22)+Lsγ2E2L2c2TT∑t=1∑i∈StSCp2i +∑i∈N\StN − SK − Cp2i (4.23)= −γE2T∥∇F (wt)∥22 +3γ3E2L2s2(ELc + σ2) (4.24)+Lsγ2E(σ2 + EL2c)2TT∑t=1(N∑i=1S2CNp2i +N∑i=1(N − S)2N(K − C)p2i)(4.25)where the last equation follows that (i) a client in the sticky group andthe non-sticky group with the probability of SN andN−SN , respectively; (ii)a client is sampled from the sticky group and the non-sticky group with the244.3. Proof of Theorem 2probability of CS andK−CN−S , respectively. Therefore, the convergence rate is1TT∑t=1∥∇F (wt)∥22 ≤2(F (w1)− F∗)γET+ 3γ2EL2s(ELc + σ2) (4.26)+Lsγ(σ2 + EL2c)N(S2C+(N − S)2K − C) N∑i=1p2i (4.27)By setting the learning rate as devised in Theorem 2, we can obtain thedesired result.4.3.4 Bounded Gap between two successive local updates.Lemma 3. Suppose, for all i ∈ {1, . . . , N}, the local objective function Fi isLc-continuous and Ls-smooth. Then, for all e ∈ {0, . . . , E − 1}, we haveE∥wt,ei −wt∥22 ≤ 3E(Eγ2L2c + γ2σ2)(4.28)Proof. As we know, the recurrence formula for wt,ei = wt,e−1i − γgt,e−1i .Through this relationship, we can bound for E∥∥∥wt,ei −wt∥∥∥22,E∥wt,ei −wt∥22 = E∥wt,e−1i − γgt,e−1i −wt∥22 (4.29)(a)= E∥wt,e−1i −wt − γ∇Fi(wt,e−1i )∥22 (4.30)+ γ2 · E∥∥∥gt,e−1i −∇Fi(wt,e−1i )∥∥∥22(4.31)(b)≤(1 +1E − 1)· E∥wt,e−1i −wt∥22 (4.32)+ Eγ2 · E∥∇Fi(wt,e−1i )∥22 (4.33)+ γ2 · E∥∥∥gt,e−1i −∇Fi(wt,e−1i )∥∥∥22(4.34)(c)≤(1 +1E − 1)· E∥wt,e−1i −wt∥22 + Eγ2L2c + γ2σ2 (4.35)≤e−1∑φ=0(1 +1E − 1)φ· (Eγ2L2c + γ2σ2) (4.36)≤ 3E (Eγ2L2c + γ2σ2) (4.37)In the above proof, equation (a) separates the mean and the variance, thefirst inequality (b) uses (a+ b)2 ≤ (1 + α)a2 + (1 + 1α)b2, and the inequality(c) follows Assumptions 1 and 2.254.3. Proof of Theorem 24.3.5 Bounded gap between two successive global modelsInspired by the proof of Theorem 2 in [44], we derive the following lemmato bound Q2 accounting for GlueFL reweighted aggregation in Algorithm 2:Lemma 4. Suppose Assumption 1 and 2 hold. With Algorithm 2 by settingthe weights νti,s =SC pi and νti,r =N−SK−C pi mentioned in Section 3.1, let αi =pi∑E−1e=0 ∇Fi(wt,ei ), the bound for two successive models should beEt+1|t∥∥wt+1 −wt∥∥22(4.38)≤γ2Eσ2Et+1|t(∑i∈Ct(SCpi)2+∑i∈Rt(N − SK − Cpi)2)+ γ2Et+1|tSC∑i∈Stp2iE2L2c +N − SK − C∑i∈N\Stp2iE2L2c +∥∥∥∥∥N∑i=1αi∥∥∥∥∥22(4.39)Proof. As we know, the relationship between two successive models isEt+1|t∥∥wt+1 −wt∥∥22(4.40)= γ2 · Et+1|t∥∥∥∥∥∑i∈Ctνti,sE−1∑e=0gt,ei +∑i∈Rtνti,rE−1∑e=0gt,ei∥∥∥∥∥22(4.41)≤ γ2Et+1|t(∑i∈Ct(νti,s)2 +∑i∈Rt(νti,r)2)· Eσ2 (4.42)+ γ2Et+1|t∥∥∥∥∥∑i∈Ctνti,sE−1∑e=0∇Fi(wt,ei ) +∑i∈Rtνti,rE−1∑e=0∇Fi(wt,ei )∥∥∥∥∥22(4.43)where the inequality is based on Lemma 2. Next, we ignore the coefficientand find the bound for the second term of Equation (4.43) by plain expandingthe term as proposed in [44]: Let αi = pi∑E−1e=0 ∇Fi(wt,ei ), and since νti,s =264.3. Proof of Theorem 2SC pi and νti,r =N−SK−C pi, we haveEt+1|t∥∥∥∥∥∑i∈Ctνti,sE−1∑e=0∇Fi(wt,ei ) +∑i∈Rtνti,rE−1∑e=0∇Fi(wt,ei )∥∥∥∥∥22(4.44)= Et+1|t∥∥∥∥∥∑i∈CtSCαi +∑i∈RtN − SK − Cαi∥∥∥∥∥22(4.45)= Et+1|t∑i∈Ct∥∥∥∥SCαi∥∥∥∥22︸ ︷︷ ︸C terms+∑i∈Rt∥∥∥∥N − SK − Cαi∥∥∥∥22︸ ︷︷ ︸(K − C) terms+∑i ̸=j,i,j∈Ct(SC)2⟨αi, αj⟩︸ ︷︷ ︸C(C − 1) terms+∑i ̸=j,i,j∈Rt(N − SK − C)2⟨αi, αj⟩︸ ︷︷ ︸(K − C)(K − C − 1) terms+2∑i∈Ct,j∈Rt(SC)(N − SK − C)⟨αi, αj⟩︸ ︷︷ ︸C(K − C) terms(4.46)Before analyzing the bound of Equation (4.46), we provide the constantresults for the following expectations:E ∥αi∥22 =1S∑s∈St∥αs∥22 , for i ∈ St (4.47)E ∥αi∥22 =1N − S∑r∈N\St∥αr∥22 , for i ∈ N \ St (4.48)E ⟨αi, αj⟩ = 1S2∑s1,s2∈St⟨αs1 , αs2⟩ , for i, j ∈ St (4.49)E ⟨αi, αj⟩ = 1(N − S)2∑r1,r2∈N\St⟨αr1 , αr2⟩ , for i, j ∈ N \ St (4.50)E ⟨αi, αj⟩ = 1S(N − S)∑s∈St,r∈N\St⟨αs, αr⟩ , for i ∈ St, j ∈ N \ St (4.51)274.3. Proof of Theorem 2Therefore, the bound of Equation (4.46) is analyzed as follows:Et+1|t∥∥∥∥∥∑i∈CtSCαi +∑i∈RtN − SK − Cαi∥∥∥∥∥22(4.52)= Et+1|tCS·(SC)2∑i∈St∥αi∥22 +K − CN − S(N − SK − C)2 ∑i∈N\St∥αi∥22 (4.53)+C(C − 1)S2(SC)2 ∑i,j∈St⟨αi, αj⟩ (4.54)+(K − C)(K − C − 1)(N − S)2(N − SK − C)2 ∑i,j∈N\St⟨αi, αj⟩ (4.55)+2(K − C)C(N − S)S(SC)(N − SK − C) ∑i∈St,j∈N\St⟨αi, αj⟩ (4.56)= Et+1|tCS·(SC)2∑i∈St∥αi∥22 +K − CN − S(N − SK − C)2 ∑i∈N\St∥αi∥22 (4.57)+C(C − 1)S2(SC)2 ∥∥∥∥∥∑i∈Stαi∥∥∥∥∥22(4.58)+(K − C)(K − C − 1)(N − S)2(N − SK − C)2 ∥∥∥∥∥∥∑i∈N\Stαi∥∥∥∥∥∥22(4.59)+2(K − C)C(N − S)S(SC)(N − SK − C) ∑i∈St,j∈N\St⟨αi, αj⟩ (4.60)≤ Et+1|tSC∑i∈St∥αi∥22 +N − SK − C∑i∈N\St∥αi∥22 +∥∥∥∥∥N∑i=1αi∥∥∥∥∥22 (4.61)≤ Et+1|tSC∑i∈Stp2iE2L2c +N − SK − C∑i∈N\Stp2iE2L2c +∥∥∥∥∥N∑i=1αi∥∥∥∥∥22 (4.62)where the first equation is due to the independent client sampling with re-placement in both groups, and the last inequality follows Assumption 2.Therefore, with the result from Equation (4.62), we can obtain the desiredresult based on Equation (4.43).28Chapter 5Experimental EvaluationWe evaluate GlueFL across several datasets and network distributions. Ourgoal is to answer three questions:1. What model accuracy does GlueFL achieve?2. How does GlueFL impact bandwidth usage?3. How quickly does the model converge with GlueFL?5.1 ImplementationWe build GlueFL on top of FedScale, a scalable and extensible open-sourceFL library [19]. We implemented sticky sampling in ClientManager. Wealso customized the Aggregator and Client to implement mask shifting.While mask shifting introduces extra overheads to transmit sparse vectors,we take care to minimize these overheads using coding strategies from pre-vious work [32, 43]. For example, we communicate the sparse vector usingabsolute positions or bitmaps.Aggregation for Batch Normalization layers A Batch Normalization(BN) layer contains five parameters:• Trainable parameters: weight, bias• Non-trainable summary statistics: running_mean, running_var, andnum_batches_trackedWhile GlueFL updates trainable parameters as all model parameters (Al-gorithm 3), non-trainable parameters need to be treated differently. Weperform the aggregation of these non-trainable parameters v as follows:∆ti ← vt,Ei − vt,0i (5.1)vt+1 ← vt + 1K∑i∈K∆ti (5.2)295.2. Experimental Setupwhere∆ti represents the local change of vt on client i in round t. Note that wedo not perform re-weighting on∆ti as this produces the best empirical results.This aggregation rule is consistent with the FedScale implementation [19].5.2 Experimental SetupWe deployed GlueFL on a set of VMs in one data-center with a total of14 NVIDIA Tesla V100 GPUs. To reproduce real-world heterogeneous clientperformance, we use FedScale’s client behavior trace and the NDT dataset [25]to simulate the availability pattern and bandwidth capacity of clients, re-spectively. To mitigate stragglers and offline clients, FedScale introduces anover-commitment (OC) variable [3] which we set to 1.3 in all experiments.That is, we sample 1.3×K clients in each round and use the first K uploadedupdates.Datasets and Models We use three datasets: FEMNIST [6], OpenIm-age [18], Google Speech [39]. The first two datasets are frequently used forimage classification and consist of 640K and 1.3M colored images, respec-tively. Google Speech is a dataset with 105K speech samples. We partitionthe data using FedScale’s real-world non-iid client-data mapping [19] andremove those clients that have fewer than 22 samples as the default set-ting in FedScale. In total, we use 2, 800, 10, 625, and 2, 066 clients in ourexperiments, respectively. The models we use are ShuffleNet [46] and Mo-bileNet [31] for both FEMNIST and OpenImage, and ResNet-34 [13] forGoogle Speech. We set the number of sampled clients K = 30, 100, and 30for FEMNIST, OpenImage, and Google Speech, respectively.Baselines We compare GlueFL with FedAvg [24], the most widely used FLalgorithm with no model compression methods. We also compare GlueFLwith STC [32] and APF [7], which are the state-of-the-art sparsification andparameter freezing strategies, respectively.Metrics We measure the total data volume and total training time toaddress Q2 and Q3, respectively. We also analyze the downstream bandwidthand download time. For download time, we pick the slowest client in eachround and sum up their download time. To address Q1, similar to Oort [20],we average the test accuracy over 5 rounds and report the results when theaveraged accuracy first reaches the target accuracy.305.2. Experimental SetupTable 5.1: Downstream transmission Volume (DV, in ×102 GB) and Totaltransmission Volume (TV) for training different models/datasets. We mea-sure Top-1 accuracy for FEMNIST and Google Speech, and Top-5 accuracyfor OpenImage [19]. We set the target accuracy to be the highest achievableaccuracy by all approaches. Our target accuracies are comparable with pre-vious work [19, 20]. The best results are in bold.Dataset # Clients TargetAcc. ModelFedAvg STC APF GlueFLDV (TV) DV (TV) DV (TV) DV (TV)FEMNIST 2,800 73.3%ShuffleNet 2.6 (4.6) 2.6 (3.4) 2.3 (3.2) 2.2 (3.1)MobileNet 1.2 (2.1) 1.5 (1.9) 1.5 (2.0) 0.9 (1.4)OpenImage 10,625 66.8%ShuffleNet 25.2 (45.0) 33.9 (50.0) 27.1 (43.1) 21.3(31.4)MobileNet17.4 (31.1) 16.7 (24.5) 20.3 (30.9) 14.9(22.1)Google Speech 2,066 61.2% ResNet-34 12.8 (23.0) 13.5 (18.5) 15.8 (21.9) 7.2 (12.5)Table 5.2: Download Time (DT, in hours) and Total training Time (TT)for training different models/datasets. The best results are in bold.Dataset # Clients TargetAcc. ModelFedAvg STC APF GlueFLDT (TT) DT (TT) DT (TT) DT (TT)FEMNIST 2,800 73.3%ShuffleNet 2.7 (7.6) 2.7 (5.7) 2.3 (5.7) 2.2 (5.3)MobileNet 1.5 (4.6) 1.7 (3.9) 1.6 (4.5) 0.8 (3.3)OpenImage 10,625 66.8%ShuffleNet 11.2 (28.8) 14.8 (29.9) 12.3 (29.8) 8.0 (19.2)MobileNet 7.1 (22.4) 7.1 (19.1) 8.8 (21.0) 5.8 (14.4)Google Speech 2,066 61.2% ResNet-34 20.1 (60.9) 16.0 (42.3) 19.1 (54.1) 12.1(27.8)Training Parameters Clients perform 10 local updates per round. Weuse PyTorch’s SGD optimizer with a momentum factor of 0.9 for all tasks.For FEMNIST, OpenImage, and Google Speech, the initial learning rate isset to 0.01, 0.05, and 0.01, respectively, with a decay factor of 0.98 every 10rounds. To obtain the best performance, we set the total mask ratio q = 20%for ShuffleNet, and q = 30% for MobileNet and ResNet-34 in STC. For APF,we set the threshold for effective perturbation, which reflects the compressionratio, to 0.1 for all tasks. The remaining STC and APF parameters are set totheir optimal values [7, 32]. For GlueFL, the default sticky group parameters315.3. Performance Resultsare S = 4K and C = 4K/5. For ShuffleNet, the default mask shiftingparameters are q = 20% and qshr = 16%. For MobileNet and ResNet-34,we set q = 30% and qshr = 24%. We use I = 10 to regenerate the sharedmask every 10 rounds. We choose these values as they produce the bestperformance across most tasks.5.3 Performance ResultsCommunication costs Tables 5.1 and 5.2 list the data volume and train-ing time for FedAvg (baseline), STC, APF, and GlueFL (our framework). Itshows that STC and APF outperform FedAvg as they require less bandwidthto reach the target accuracy, reducing volume by 8% on average. However,STC and APF consume substantial downstream bandwidth. For example,when training MobileNet on FEMNIST, STC only takes 40 GB to uploadgradients but uses 150 GB for downstream synchronization. GlueFL reducesdownstream bandwidth (Table 5.1): for OpenImage, GlueFL provides a sav-ing of 15% compared with FedAvg, while for Google Speech GlueFL saves42%. We further compare the performance of GlueFL with STC and APF.In each case, while consuming nearly the same amount of upstream band-width (note upstream bandwidth volume = TV-DV in Table 5.1), GlueFLuses the least downstream bandwidth across all three datasets. For example,when training MobileNet on OpenImage, APF, STC, and GlueFL all con-sume around 900 GB to upload gradients. However GlueFL lowers downloadbandwidth by 11% and 26% as compared with STC and APF, respectively.This is because STC and APF do not bound the changes of masks in acommunication round and the update size rapidly increases.Wall-clock Time Table 5.2 indicates that downstream bandwidth is thebottleneck. For example, when training MobileNet on FEMNIST, FedAvguses 32% of its total training time for model synchronization while STC uses43%. GlueFL reduces total training time by reducing downstream bandwidthand saving download time, which speeds up the training by 15% and 26% ascompared with STC and APF.5.4 Sensitivity AnalysisWe evaluate the influence of GlueFL parameters on training performanceon FEMNIST with ShuffleNet and Google Speech with ResNet-34. Similarto §5.3, we use K = 30. When evaluating one parameter, we use defaults325.4. Sensitivity Analysis1.0 1.5 2.0 2.5 3.0Cumulative Downstream Bandwidth (×102GB)5560657075Test AccuracyFedAvgSTCAPFGlueFL (Equal)GlueFL(a) ShuffleNet (FEMNIST)2 3 4 5 6 7 8 9 10Cumulative Downstream Bandwidth (×102GB)404550556065Test AccuracyFedAvgSTCAPFGlueFL (Equal)GlueFL(b) ResNet-34 (Google Speech)Figure 5.1: Effect of aggregation weights νti,s and νti,r: GlueFL (Equal) isbiased (equal weights), while GlueFL is unbiased.1.0 1.5 2.0 2.5 3.0Cumulative Downstream Bandwidth (×102GB)5560657075Test AccuracyFedAvgGlueFL (S=30)GlueFL (S=60)GlueFL (S=120)GlueFL (S=240)(a) ShuffleNet (FEMNIST)2 3 4 5 6 7 8 9 10Cumulative Downstream Bandwidth (×102GB)404550556065Test AccuracyFedAvgGlueFL (S=30)GlueFL (S=60)GlueFL (S=120)GlueFL (S=240)(b) ResNet-34 (Google Speech)Figure 5.2: Effect of sticky group size S.for the others (see §5.2). For each setting, we run GlueFL for 1,000 roundsand report the average test accuracy over 20 rounds with respect to thecumulative downstream bandwidth.Effect of aggregation weights νti,s and νti,r Figure 5.1 demonstratesthe impact of two settings of aggregation weights on training performance:equal (i.e., νti,s = νti,r = 1/K) and unbiased (see §3.1). Overall, unbiasedaggregation weights lead to similar or better convergence speed for the sameamount of cumulative downstream bandwidth usage. In the case of GoogleSpeech, unbiased aggregation was able to achieve convergence while saving41% of downstream bandwidth.335.4. Sensitivity Analysis1.0 1.5 2.0 2.5 3.0Cumulative Downstream Bandwidth (×102GB)5560657075Test AccuracyFedAvgGlueFL (C=24)GlueFL (C=18)GlueFL (C=6)(a) ShuffleNet (FEMNIST)2 3 4 5 6 7 8 9 10Cumulative Downstream Bandwidth (×102GB)404550556065Test AccuracyFedAvgGlueFL (C=24)GlueFL (C=18)GlueFL (C=6)(b) ResNet-34 (Google Speech)Figure 5.3: Effect of sticky sampling parameter C.1.0 1.5 2.0 2.5 3.0Cumulative Downstream Bandwidth (×102GB)5560657075Test AccuracyFedAvgGlueFL (qshr=4%)GlueFL (qshr=8%)GlueFL (qshr=16%)(a) ShuffleNet (FEMNIST)2 3 4 5 6 7 8 9 10Cumulative Downstream Bandwidth (×102GB)404550556065Test AccuracyFedAvgGlueFL (qshr=6%)GlueFL (qshr=12%)GlueFL (qshr=24%)(b) ResNet-34 (Google Speech)Figure 5.4: Effect of shared mask ratio qshr.Sticky sampling parameters S and C Figure 5.2 shows the impact ofsticky group size S on training performance. Typically, a larger sticky groupsize means more diverse training data for the sticky clients and indirectlybetter accuracy at the cost of more communication. It follows that choos-ing an appropriately large S is important for optimizing performance. Forinstance, the S = 120 setting for Google Speech reached the target accuracywith almost 20% less downstream communication compared with S = 60.However, the same S is unable to help GlueFL achieve a speedup for FEM-NIST.Next, we evaluate the impact of the sticky sampling parameter C (Fig-ure 5.3). C clients in the sticky group are sampled and (K − C) clients arereplaced by clients from the non-sticky group. Across C = 6, 18, and 24 in345.5. Network EnvironmentFigure 5.3, we do not observe a large improvement in accuracy for smallerC. By contrast, C = 6 adds 76% download bandwidth in each round asGlueFL is unable to capitalize on the savings from sticky sampling due tomore new clients. This indicates that a large C does not harm accuracy andsaves more bandwidth.Mask shifting parameter qshr Figure 5.4 shows the effect of the sharedmask ratio qshr on performance. On average, a higher value (qshr = 16%)does not cause accuracy to drop substantially and is preferable as GlueFLuses the least downstream bandwidth to reach the convergence accuracy ofFedAvg. This is because GlueFL optimizes mask shifting with shared maskregeneration and error compensation.5.5 Network EnvironmentTo further test our framework on high-throughput environments, we repeatedthe experiment in Tables 5.1 and 5.2 on commercial 5G [28] and GoogleCloud [27] with the default settings for GlueFL (see §5.2). Figure 5.5 showsthe total share of download, upload, and computation time for the threeenvironments.According to Figure 5.5(a), transmission time remains a bottleneck in theend-user edge devices environment as shown in Table 5.2. We attribute thisto low-bandwidth clients. The ratio of download to upload time increasesas we introduce compression. Since clients usually download faster thanupload [1, 25]: new clients in FedAvg spend 70% more time uploading thandownloading the same-sized update. However, for STC and APF, downloadtime takes on average 8% longer than upload, confirming the discussion in§2.3. To address this limitation, GlueFL saves downstream bandwidth andreduces download time by at least 42% as compared with other approaches.This is because clients in the sticky group are required to download lessupdates and are therefore less likely to become stragglers.In 5G and intra-datacenter networks, computation dominates the per-round training time. Yet, straggler clients still exist and they ultimatelydetermine the end-to-end training time.5.6 Ablation StudyWe described two optimization techniques in §3.3: shared mask regenerationand error-compensation. The first technique regenerates the shared mask355.6. Ablation StudyFedAvg STC APF GlueFL0306090120Training Time / Round (s) Download TimeUpload TimeComputation Time(a) End-user device networkFedAvg STC APF GlueFL0510152025Training Time / Round (s) Download TimeUpload TimeComputation Time(b) Commercial 5G networkFedAvg STC APF GlueFL0510152025Training Time / Round (s) Download TimeUpload TimeComputation Time(c) Google Cloud datacenter networkFigure 5.5: Average share of time spent per round downloading (grey), up-loading (red) and computing (blue).M t every I rounds and the second technique adds a re-scaled compensation365.6. Ablation Study1.0 1.5 2.0 2.5 3.0Cumulative Downstream Bandwidth (×102GB)5560657075Test AccuracyFedAvgGlueFL (I=10)GlueFL (I=20)GlueFL (I=∞)(a) ShuffleNet (FEMNIST)2 3 4 5 6 7 8 9 10Cumulative Downstream Bandwidth (×102GB)404550556065Test AccuracyFedAvgGlueFL (I=10)GlueFL (I=20)GlueFL (I=∞)(b) ResNet-34 (Google Speech)Figure 5.6: Effect of shared mask regeneration.1.0 1.5 2.0 2.5 3.0Cumulative Downstream Bandwidth (×102GB)5560657075Test AccuracyFedAvgGlueFL (None)GlueFL (EC)GlueFL (REC)(a) ShuffleNet (FEMNIST)2 3 4 5 6 7 8 9 10Cumulative Downstream Bandwidth (×102GB)404550556065Test AccuracyFedAvgGlueFL (None)GlueFL (EC)GlueFL (REC)(b) ResNet-34 (Google Speech)Figure 5.7: Effect of error-compensation.vector hφ(t)i to local updates ∆ti. In this section, we conduct ablation studiesto evaluate the effect of these techniques.We run GlueFL on FEMNIST with ShuffleNet and Google Speech withResNet-34. In each round, the server samples 30 clients out of 2,800 clients(for FEMNIST) and 30 clients out of 2,066 clients (for Google Speech). Foreach experiment, we run 1,000 rounds and measure the downstream band-width and test accuracy. While GlueFL consists of both sticky sampling andmask shifting, we only change the corresponding part in mask shifting andkeep other training settings the same as §5.2.Shared Mask Regeneration As described in §3.3, we set qshr = 0 andregenerate the shared mask as M t ← topqshr(∆˜tuni) every I rounds. A larger375.7. Availability and StragglersI value indicates that M t will be regenerated less frequently. We do notregenerate M t when I =∞.In Figures 5.6(a) and 5.6(b), we plot results for three I values: 10, 20,∞.Both figures show that setting I = 10 achieves the best overall performance,saving around 22% downstream bandwidth at the target accuracy for GoogleSpeech. The impact of I on FEMNIST training in Figure 5.6(a) is lesspronounced but the I = 10 setting still has the best accuracy. Thus, inpractice, we need to set an appropriate I value (e.g., 10) to avoid a drop inaccuracy.Error-Compensation In §3.3 we noted that error compensation can beused to accelerate convergence when applying compression methods in FLtraining. GlueFL re-scales the compensation vector hφ(t)i , following Equa-tion (3.5), to make it compatible with sticky sampling. In this section,we report on experiments for three error compensation settings: no com-pensation (None), compensation without re-scaling (EC), compensationwith re-scaling (REC). The convergence results are shown in Figures 5.7(a)and 5.7(b). Both figures show that removing re-scaling from error compen-sation immediately breaks GlueFL and harms the convergence performance.This demonstrates that it is necessary to apply re-scaling with error com-pensation.5.7 Availability and StragglersIn §5.2 we discussed a default value of 1.3 for over-commitment. This meansthat GlueFL will sample 0.3×K additional clients to mitigate stragglers andclients that might become unavailable (e.g., go offline). In this section, weexplore different values and strategies in over-commitment for GlueFL.In GlueFL’s default setting, the over-commitment applies to both stickygroup S and non-sticky group N \S. The server will sample 0.3×K×(C/K)and 0.3×K× (1− (C/K)) additional clients from S and N \S, respectively.However, as GlueFL only includes the fastest K − C clients in all samplednon-sticky clients to S in each round, clients in S are less likely to becomestragglers. It follows that we can improve the over-commitment strategy bysampling fewer additional clients in S while sampling more additional clientsfrom N \ S.Table 5.3(a) presents the results from using four over-commitment strate-gies for training ShuffleNet on FEMNIST. Similar to previous tasks: we select30 clients out of 2,800 clients in each round and we choose another 9 (i.e.,385.7. Availability and StragglersTable 5.3: Downstream transmission Volume (DV, in ×102 GB),DownloadTime (DT, in hours), Total transmission Volume (TV) and Total train-ing Time (TT) for training ShuffleNet on FEMNIST with different over-commitment (OC) settings.(a) Results of different over-commitment strategies with a constantover-commit value (1.3)OC Strategy (S : N \ S) DV TV DT TT10% 1 : 8 2.1 3.1 0.6 2.730% 3 : 6 2.2 3.0 0.9 3.150% 5 : 4 2.1 2.9 1.3 3.8C/K (Default) 7 : 2 2.2 3.1 2.2 5.3(b) Results for different over-commitment valueswith a constant strategy (row 1 in Table 5.3(a))OC Value DV TV DT TT1.0 1.5 2.3 32.0 67.81.1 2.2 3.1 3.5 10.71.2 2.2 3.0 1.0 3.91.3 2.1 3.1 0.6 2.71.4 2.9 3.7 0.5 2.61.5 3.1 4.0 0.5 2.40.3 × 30) clients for over-commitment. We report transmission volume andtraining time when the model reaches the target test accuracy of 73.3%. Inthe table, the OC strategy row of 10% means that 1 (i.e., 0.3×30×10%), and8 (i.e., 0.3×30×(1−10%)) additional clients are sampled from S and N \S,respectively. The results show that by choosing fewer additional clients fromthe sticky group, GlueFL consumes less training time without increasing thedownstream bandwidth volume.Next, we use the best setting of 10% (from Table 5.3(a)) to evaluatedifferent OC values. Table 5.3(b) shows the results for OC values of 1.0to 1.5. With increasing OC values, we find that training time decreasesfaster than downstream volume increases. As an example, when OC value ischanged from 1.0 to 1.3, training time is decreased by 96% and downstreamvolume increases by 40%. However, increasing the OC value from 1.3 to1.5 only reduces 11% training time while consuming 47% more downstreamvolume. In practice, one should set the OC value carefully to balance thetrade-off between bandwidth and training time.39Chapter 6Related WorkThe synchronization bottleneck is an established problem in FL. Existingsolutions fall into roughly two categories: (1) use client sampling to constrainthe number of clients in each round; and, (2) compress model data withstrategies like sparsification and parameter freezing.Client sampling. FedAvg proposed a uniform sampling of clients toparticipate in each round. Uniform sampling has been shown to be biased,and multinomial distribution (MD) sampling was proposed to address thisissue [21]. Clustered sampling [9] reduced the variance of client update ag-gregation by improving client representation. Oort [20] introduced a practi-cal client selection algorithm, which considers both data utility and clientsspeed.Sparsification. The idea of sparsification is to send only the most in-formative gradients. Gaia [14] transfers gradients whose absolute or relativevalues are larger than a given threshold. Stich et al. [34] proposed Top-Kthat, given a compression ratio, selects a fraction of gradients based on theirabsolute values to meet the ratio. STC [32] extended Top-K to FL trainingand also uses server-side compression.Parameter freezing. Parameter freezing reduces bandwidth by freez-ing the gradients that converged. Brock et al. [5] proposed FreezeOut, whichgradually froze the first few layers of a deep neural network that were ob-served to converge first. However, it has a coarse layer-based granularity andit degrades accuracy. APF [7] improves on FreezeOut by freezing at a finegranularity and achieves a communication speed-up while preserving modelconvergence.Our goal with GlueFL is to coherently combine client sampling withmodel compression. To our knowledge, we are the first to propose a com-bination that is unbiased, achieves high accuracy, and lowers downstreambandwidth usage.40Chapter 7ConclusionsWe proposed GlueFL, a framework to optimize downstream bandwidth incross-device FL. GlueFL uses sticky sampling for client selection and maskshifting for model compression to mitigate the low download bandwidth ofFL clients. We also provide a theoretical convergence guarantee for GlueFL.In comparison with FedAvg, GlueFL achieves similar accuracy while decreas-ing total training time by 36% and uses 22% less downstream bandwidth.GlueFL also outperforms STC [32] and APF [7].41Bibliography[1] Speedtest global index. https://www.speedtest.net/global-index,2022.[2] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-SGD: Distributed SGD with quantization, sparsification and localcomputations. In Advances in Neural Information Processing Systems(NeurIPS), 2019.[3] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba,Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečny`, Ste-fano Mazzocchi, Brendan McMahan, et al. Towards federated learningat scale: System design. In Proceedings of Machine Learning and Sys-tems (MLSys), 2019.[4] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methodsfor large-scale machine learning. Siam Review, 60(2):223–311, 2018.[5] Andrew Brock, Theodore Lim, James M Ritchie, and Nick Weston.Freezeout: Accelerate Training by Progressively Freezing Layers. InNIPS Workshop on Optimization for Machine Learning (OPTML),2017.[6] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li,Jakub Konečny`, H Brendan McMahan, Virginia Smith, and Ameet Tal-walkar. LEAF: A Benchmark for Federated Settings. arXiv preprintarXiv:1812.01097, 2018.[7] Chen Chen, Hong Xu, Wei Wang, Baochun Li, Bo Li, Li Chen, andGong Zhang. Communication-Efficient Federated Learning With Adap-tive Parameter Freezing. In International Conference on DistributedComputing Systems (ICDCS), 2021.[8] Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal ClientSampling for Federated Learning. arXiv preprint arXiv:2010.13723,2020.42Bibliography[9] Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi.Clustered Sampling: Low-Variance and Improved Representativity forClients Selection in Federated Learning. In International Conference onMachine Learning (ICML), 2021.[10] Pengchao Han, Shiqiang Wang, and Kin K Leung. Adaptive GradientSparsification for Efficient Federated Learning: An Online Learning Ap-proach. In International Conference on Distributed Computing Systems(ICDCS), 2020.[11] Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy,Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon,and Daniel Ramage. Federated Learning for Mobile Keyboard Predic-tion. arXiv preprint arXiv:1811.03604, 2018.[12] Florian Hartmann, Sunah Suh, Arkadiusz Komarzewski, Tim D Smith,and Ilana Segall. Federated Learning for Ranking Browser History Sug-gestions. arXiv preprint arXiv:1911.11807, 2019.[13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Resid-ual Learning for Image Recognition. In IEEE Conference on ComputerVision and Pattern Recognition (CVPR), 2016.[14] Kevin Hsieh, Aaron Harlap, Nandita Vijaykumar, Dimitris Konomis,Gregory R Ganger, Phillip B Gibbons, and Onur Mutlu. Gaia: Geo-Distributed Machine Learning Approaching LAN Speeds. In USENIXSymposium on Networked Systems Design and Implementation (NSDI),2017.[15] Peng Jiang and Gagan Agrawal. A Linear Speedup Analysis of Dis-tributed Deep Learning With Sparse and Quantized Communication. InAdvances in Neural Information Processing Systems (NeurIPS), 2018.[16] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bel-let, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, ZacharyCharles, Graham Cormode, Rachel Cummings, et al. Advances andOpen Problems in Federated Learning. Foundations and Trends® inMachine Learning, 14(1–2):1–210, 2021.[17] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, SashankReddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD:Stochastic Controlled Averaging for Federated Learning. In Interna-tional Conference on Machine Learning (ICML), 2020.43Bibliography[18] Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, IvanKrasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Mal-loci, Alexander Kolesnikov, Tom Duerig, and Vittorio Ferrari. The OpenImages Dataset V4: Unified Image Classification, Object Detection, andVisual Relationship Detection at Scale. IJCV, 2020.[19] Fan Lai, Yinwei Dai, Sanjay S. Singapuram, Jiachen Liu, XiangfengZhu, Harsha V. Madhyastha, and Mosharaf Chowdhury. FedScale:Benchmarking Model and System Performance of Federated Learningat Scale. In International Conference on Machine Learning (ICML),2022.[20] Fan Lai, Xiangfeng Zhu, Harsha V. Madhyastha, and Mosharaf Chowd-hury. Oort: Efficient Federated Learning via Guided Participant Selec-tion. In USENIX Symposium on Operating Systems Design and Imple-mentation (OSDI), 2021.[21] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Tal-walkar, and Virginia Smith. Federated Optimization in HeterogeneousNetworks. In Proceedings of Machine Learning and Systems (MLSys),2020.[22] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and ZhihuaZhang. On the Convergence of FedAvg on Non-iid Data. In InternationalConference on Learning Representations (ICLR), 2020.[23] Bing Luo, Wenli Xiao, Shiqiang Wang, Jianwei Huang, and LeandrosTassiulas. Tackling System and Statistical Heterogeneity for FederatedLearning with Adaptive Client Sampling. In IEEE Conference on Com-puter Communications (INFOCOM), 2022.[24] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, andBlaise Aguera y Arcas. Communication-Efficient Learning of Deep Net-works From Decentralized Data. In International Conference on Artifi-cial Intelligence and Statistics (AISTATS), 2017.[25] Measurement Lab. The M-Lab NDT data set. https://measurementlab.net/tests/ndt, (2022-06-01 – 2022-07-01).[26] Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani.Linear convergence in federated learning: Tackling client heterogeneityand sparse gradients. In Advances in Neural Information ProcessingSystems (NeurIPS), 2021.44Bibliography[27] Ricky KPMok, Hongyu Zou, Rui Yang, Tom Koch, Ethan Katz-Bassett,and Kimberly C Claffy. Measuring the Network Performance of GoogleCloud Platform. In Internet Measurement Conference (IMC), 2021.[28] Arvind Narayanan, Xumiao Zhang, Ruiyang Zhu, Ahmad Hassan,Shuowei Jin, Xiao Zhu, Xiaoxuan Zhang, Denis Rybkin, ZhengxuanYang, Zhuoqing Morley Mao, et al. A Variegated Look at 5G in theWild: Performance, Power, and Qoe Implications. In ACM Special In-terest Group on Data Communication (SIGCOMM), 2021.[29] Xun Qian, Peter Richtárik, and Tong Zhang. Error Compensated Dis-tributed SGD Can Be Accelerated. In Advances in Neural InformationProcessing Systems (NeurIPS), 2021.[30] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jad-babaie, and Ramtin Pedarsani. FedPAQ: A Communication-EfficientFederated Learning Method With Periodic Averaging and Quantiza-tion. In International Conference on Artificial Intelligence and Statistics(AISTATS), 2020.[31] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov,and Liang-Chieh Chen. MobileNetV2: Inverted Residuals and LinearBottlenecks. In IEEE Conference on Computer Vision and PatternRecognition (CVPR), 2018.[32] Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and WojciechSamek. Robust and Communication-Efficient Federated Learning FromNon-iid Data. IEEE transactions on neural networks and learning sys-tems, 31(9):3400–3413, 2019.[33] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-BitStochastic Gradient Descent and Its Application to Data-Parallel Dis-tributed Training of Speech DNNs. In International Speech Communi-cation Association (ISCA), 2014.[34] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsi-fied SGD with Memory. In Advances in Neural Information ProcessingSystems (NeurIPS), 2018.[35] Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Dou-bleSqueeze: Parallel Stochastic Gradient Descent With Double-PassError-Compensated Compression. In International Conference on Ma-chine Learning (ICML), 2019.45Bibliography[36] Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson,Yaniv Ben Itzhak, and Michael Mitzenmacher. Eden: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learn-ing. In International Conference on Machine Learning (ICML), 2022.[37] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H VincentPoor. Tackling the objective inconsistency problem in heterogeneousfederated optimization. In Advances in Neural Information ProcessingSystems (NeurIPS), 2020.[38] Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient Spar-sification for Communication-Efficient Distributed Optimization. In Ad-vances in Neural Information Processing Systems (NeurIPS), 2018.[39] Pete Warden. Speech Commands: A Dataset for Limited-VocabularySpeech Recognition. arXiv preprint arXiv:1804.03209, 2018.[40] Feijie Wu, Song Guo, Haozhao Wang, Zhihao Qu, Haobo Zhang, JieZhang, and Ziming Liu. From Deterioration to Acceleration: A Cal-ibration Approach to Rehabilitating Step Asynchronism in FederatedOptimization. arXiv preprint arXiv:2112.09355, 2021.[41] Feijie Wu, Shiqi He, Song Guo, Zhihao Qu, Haozhao Wang, WeihuaZhuang, and Jie Zhang. Sign Bit is Enough: A Learning SynchronizationFramework for Multi-Hop All-Reduce with Ultimate Compression. InACM/IEEE Design Automation Conference (DAC), 2022.[42] Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. ErrorCompensated Quantized SGD and Its Applications to Large-Scale Dis-tributed Optimization. In International Conference on Machine Learn-ing (ICML), 2018.[43] Hang Xu, Chen-Yu Ho, Ahmed M Abdelmoniem, Aritra Dutta,El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, andPanos Kalnis. Grace: A Compressed Communication Framework forDistributed Machine Learning. In International Conference on Dis-tributed Computing Systems (ICDCS), 2021.[44] Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedupwith partial worker participation in non-iid federated learning. arXivpreprint arXiv:2101.11203, 2021.46Bibliography[45] Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, WeiLi, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. AppliedFederated Learning: Improving Google Keyboard Query Suggestions.arXiv preprint arXiv:1812.02903, 2018.[46] Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. ShuffleNet:An Extremely Efficient Convolutional Neural Network for Mobile De-vices. In IEEE Conference on Computer Vision and Pattern Recognition(CVPR), 2018.47
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Beschastnikh, Ivan
GlueFL : reconciling client sampling and model masking for bandwidth efficient federated learning
Text