FedShuffle:  Recipes for Better Use of Local Work in Federated Learning
Authors: Samuel Horváth
Maziar Sanjabi
Lin Xiao
Peter Richtárik
Michael Rabbat
Venue: Accepted by TMLR ()

Abstract: The practice of applying several local updates before aggregation across clients has been empirically shown to be a successful approach to overcoming the communication bottleneck in Federated Learning (FL). Such methods are usually implemented by having clients perform one or more epochs of local training per round while randomly reshuffling their finite dataset in each epoch. Data imbalance, where clients have different numbers of local training samples, is ubiquitous in FL applications, resulting in different clients performing different numbers of local updates in each round. In this work, we propose a general recipe, FedShuffle, that better utilizes the local updates in FL, especially in this regime encompassing random reshuffling and heterogeneity. FedShuffle is the first local update method with theoretical convergence guarantees that incorporates random reshuffling, data imbalance, and client sampling — features that are essential in large-scale cross-device FL. We present a comprehensive theoretical analysis of FedShuffle and show, both theoretically and empirically, that it does not suffer from the objective function mismatch that is present in FL methods that assume homogeneous updates in heterogeneous FL setups, such as FedAvg (McMahan et al., 2017). In addition, by combining the ingredients above, FedShuffle improves upon FedNova (Wang et al., 2020), which was previously proposed to solve this mismatch. Similar to Mime (Karimireddy et al., 2020), we show that FedShuffle with momentum variance reduction (Cutkosky & Orabona, 2019) improves upon non-local methods under a Hessian similarity assumption.

Published in Transactions on Machine Learning Research (09/2022)
FEDSHUFFLE: Recipes for Better Use of Local Work in Federated Learning
Samuel Horváth MBZUAP
somue.horvath@mmauui.coom
Maziar Sanjabi Meta AI
maziars com
Lin Xiao
linn@ff.coo com
Meta AT
Peter Richtárik
richtorik@gmail.com
KAUST
Michael Rabbat.
mikerabbat@@f.. com
META AT
Reviewed on OpenReview: https: http///eeeeeeeee//ee/eeeeeeeeeee
net forum? id- Lds5p11010000
Abstract
The practice of applying several local updates before aggregation across clients has been empirically shown to be successful approach to overcoming the communication bottleneck in Foderated Learning (FL). Such methods usually implemented by having clients perform more epochs of local training per round, while randomly reshuflling their finite dataset in each epoch. Data imbalance, where clients have different numbers of local training samples, is ubiquitous in FL applications, resulting in different clients performing different numbers of local updates in each round. In this work, we propose a general recipe, FEDSHUFFLEF that better utilizes the local updates in FI., especially this regime encompassing random reshuffling and heterogeneity. FEDSHUFFFE the first local update method with theoretical convergence guarantees that incorporates random reshuffling, data imbalance, and client sampling features that essential in large-scale cross-device FL. We present a comprchensive theoretical analysis of FEDSHUFFLE and show, both theoretically and empirically, that it does not suffer from the objective function mismatch that is present FL methods that assume homogeneous updates in heterogeneous FL setups, such as FEDAVG (McMahan et al., 2017). In addition, by combining the ingredients above, FEDSHUFFLE improves upon FEDNOVA (Wang al., 2020), which was previously proposed solve this mismatch. Similar to MIME (Karimireddy el. al., 2020), we show that FEDSHUFFLE with momentum variance reduction (Cutkosky & Orabona, 2019) improves upon non-local methods under Hessian similarity assumption.
1 Introduction
Federated learning (FL) aims to train models in decentralized manner, preserving the privacy of client data by leveraging edgo-device computational capabilities. Clicnts' data never leaves their devices; instead, the clients coordinate with a server to train global model. Due to such advantages and promises, FL is now deployed a variety of applications (Hard et al., 2018; Apple, 2019).
MMajority of work completed during an internship Meta.

---

Published in Transactions on Machine Learning Research (09/2022)
In this paper, we consider the standard FL problem formulation of solving an empirical risk minimization problem over the data available from all devices; i.e.,
Ipd
min acRd
f(x)
def
Σ wifi (x)i(z))
where Vi E (l....,m). fa def
D (z)
(1)
Here fiy corresponds to the loss of model with parameters I evaluated on the j-th data point of the i-th client. The weight wy assigned to device i's empirical risk is w; (P:1/1a) where [Di] is the size of the training dataset at device i and [D] > [D:]. This choice of weights w; places equal weight all training data."
To solve (1), optimization methods must contend with several challenges that are unique to FL: heterogeneity with respect to data and compute capabilities of each device, data imbalance across devices, and limited device availability, Moreover, in cross-device FL, the number of participating devices n can be on the order of millions. At this scale, cliend sumpling (using a subset of clients for each update) is a necessily since is impractical for all devices to participate in every round. Furthermore, each device may only participate once or few times during the entire training process, so stateless methods (those which do not rely on cach client maintaining and updating local state throughout training) are of particular interest.
The most widely studied and used methods in this challenging setting have devices perform multiple steps on their data locally, before communcctinn updates to the server (i.c., local update methods a la local SGD/ FEDAvG) (Kairouz et al.; 2019). Most existing analyses of local update methods assume that all participating clients perform the same number of local steps each round, and that clients sample new, independent gradients at every local step. In contrast, most practical implementations, going back to the original description of FEDAVG (McMahan et al., 2017), have devices perform their finite training dataset, while randomly reshuffling the data at each epoch. The number of training samples per device may vary by many orders of magnitude (Kairouz et al., 2019). Thus, performing local epochs results in different clients performing differing numbers of local steps per round.
more local epochs over
Although it is now well-understood that random reshufflig has a variance-reducing effect in centralized training, provably obtaining this benefit in fodcrated training has been challenging bocause of the dependence induced by random reshuflligg. In the next section, we provide detailed discussion on random reshuflling as part of related work. Mishchenko et al. (2021), Yun et al. (2021) and Malinovsky et al. (2021) analyze random reshuffling in the context of FL, while assuming that all devices have the same number of training samples and all devices participate in every round (i.e., no client sampling). Previous work of Wang et al. (2020) identified that performing different numbers of local steps per device per round in FEDAVG leads to the objective inconsistency problem effectively minimizing a different objective than (1), where terms are reweighted by the number of samples per device. Wang et al. (2020) propose the FEDNOVA method to address this by rescaling updates during aggregation. FEDLIN (Mitra et. al., 2021) addresses objective inconsistency by scaling local learning rates, while assuming full participation (all devices participate in every round) which is not practical for cross-device FL. Neither FEDNOVA nor FEDLIN incorporate reshuffling of device data. Improved convergence rates for FL optimization have been achieved by Karimireddy et al. (2020) by combining a Hessian similarity assumption with momenturn variance reduction (Cutkosky & Orabona, 2019), but without accounting for random reshuffling or data imbalance.
In this paper we aim to provide a unified view of local update methods while accounting for random reshuffling, data imbalance (through non-identical numbers of local steps), and client subsampling. Furthermore, we obtain faster convergence by incorporating momentum variance reduction. Table summarizes the key differences mentioned above.
Contributions.
We make the following contributions in this paper:
New algorithm:
FEDSHUFFLE, an improved way to remove objective inconsistency. In Section 4 we introduce and analyze FEDSHUFFLE to account for random reshuffling, client sampling,
1 Although we focus the sctting with weights w; PP: that the overall objective is equivalent to standard, centralized empirical risk minimization problem using the data from all devices, this is essential our analysis, which could accommodate any choice wy. Of course, using different choice of us will change the solution.
2

---

Published in Transactions on Machine Learning Research (09/2022)
Table 1: Comparison of characteristics considered in previous work and the methods analyzed in this paper. Notation: HD Heterogencous Data, CS Client Sampling, RR = Random Reshuffling, NL = Non-identical Local Steps, VR = Variance Reduction, GM Global Momentum, SS = Server Step Size. The bottom four methods are proposed and/or analyzed in this paper.
HD
RR
NL
FRDNOVA (Wang et al., 2020)
FEBLIN (Mitra al., 2021)
MIME (Karimireddy et al., 2020)
x /
FEDRR (Mishchenko et al., 2021) LOCALRR (Yun et al., 2021)
x
(Contributions in this work)
FEDAVGRR
x
FERNOVARR
FEDSHUPFLE
FEDSHUPPLEMVR
WWtth NI, FEDAvORR optimizes the wrong objective.
and address the objective inconsistency problem. FEDSHUPPLE fixes the objective inconsistency problem by adjusting the local step size for each client and redesigning the aggregation step, enabling a larger thcorctical step size than either FEDAVG or FEDNOVA, while also benefiting from lower
variance from random reshufflig.
New algorithm: FRDSHUPFLEMVRR, beating non-local methods. In Section 5.1 extend the results of (Karimireddy et al., 2020) by accounting for random reshuffling and data imbalance. Under a Hessian similarity assumption, we show that incorporating momentum variance reduction (MVR) with FEDSHUPFLE leads to better convergence rates than the lower bounds for methods that do not use local updates.
General framework: FedShuffleGen. The above results are obtained by first considering a general framework (see Algorithm in Appendix E.4) that accounts for data heterogeneity, different numbers of local updates per device, arbitrary client sampling, different local learning rates, and heterogeneity in the aggregation weights. To the best of our knowledge, this work is the first to tackle the challenge of random reshuffling in FI. at this level of generality. Similar to Wang et al. (2020), our analysis reveals how heterogeneity in the number of local updates can lead to objective inconsistency. Within this framework, we obtain the first analysis of FEDAVG² and FEDNOVA with random reshuflling (EERAveRR and FEDNOVARR respectively in Table 1).
Theoretical analysis. To our knowledge, we are the first to analyze a very general setup, where we consider all the standard components that are commonly used in practical implementations of FL. Furthermore, our results are tight compared to the best-known guarantees for components analyzed in isolation. The main challenge of our analysis comes especially from combining biased random reshuffling (RR) with other techniques. On top of that, our analysis is simpler when compared to the state-of-the-art analysis of FEDAVG (Karimireddy et al., 2019a) as it does not require to upper bound local client drift using recursive estimates. Finally, our general variance bound (see Appendix E.4) is the first result that allows the incorporation of non-deterministic aggregation rules based on client sampling. To our knowledge, such results are impossible to obtain with any previously known analysis, despite this being standard practice for FEDAVG, where the update of each client is scaled by w./(Ejes W;), e.g., the default way to aggregate in Tensorflow Federated and other frameworks.
Experiments. Finally, our theoretical results and insights are corroborated by experiments, both in a controlled setting with synthetic data, and using commonly-used real datasets for benchmarking and comparison with other mothods from the literature.
We acknowledge the earlier work of Malinovsky et al. (2021), which analyzes random reshuffling of local data in the context of foderated learning, with a specific focus the role of client and server stepsises. Our main results were obtained independently in early Fall 2021, and that time we also learned about the results of Malinovsky al. (2021) through personal communication, which were obtained somewhat earlier, but were available online that time. S httpps: http::://wwwwt/e/ee tensorf www.orrllooooooooo www.orggfedertteer
3

---

Published in Transactions on Machine Learning Research (09/2022)
2 Related Work
Federated optimization and local update methods. As we mentioned earlier local update methods are at the heart of FL. As a result, many prior works have analyzed various aspects of local updale methods, e.g. (Wang& & Joshi, 2021; Stich, 2018; Zhou & Cong, 2017; Yu et al., 2019; Li et al., 2019; Haddadpour & Mahdavi, 2019; Haddadpour et al., 2019a;b; Khaled et al., 2020; Stich & Karimireddy, 2020; Wang & Joshi, 2019; Woodworth al., 2020; Koloskova et al., 2020; Khaled et al., 2019; Woodworth et al., 2018; Xie et al., 2019; Lin et al., 2018). These analyses are done under the assumption that every client performs the same number of local updates in each round. However this is usually not the case in practice, due to the heterogencity of the data and system in FL; note that practical FL algorithms run fixed number of epochs (not steps) per device. Moreover, forcing the fast and slow devices to run the same number of iterations would slow-down the training. This problem was also noted by (Wang et al., 2020), where it is shown that having a heterogencous number of updates, which is inevitable in FL, leads to an inconsistency between the target loss (1) and the loss that the methods optimize. Moreover, as shown in (Wang et al., 2020), other approaches such as FEDPROX (Li et al., 2020), VRLSGD (Tiang et al., 2019) and SCAFFOLD (Karinireddy et al., 2019a) that are designed for heterogeneous data can partially alleviate the problem but not completely climinate it.
In this work, we propose FRDSHUFFLE, a method that combines update weighting and learning rate adjustments to deal with this issue. Our approach is more general than FEDNOVA (Wang et al., 2020), which only uses update weighting, 4 and we show both analytically and experimentally that it outperforms FEDNOVA and does not slow down the convergence of FEDAVG.
Random reshufflng. A particularly successful technique to optimize the empirical risk minimization objective is randomly permule (i.e., reshuille) the training data at the beginning of every epoch (Bottou, 2012) instead of randomly sampling a data point (or subset of data points) with replacement at each step, as in the standard analysis of SGD. This process is repeated several times and the resulting mothod is usually referred to as Random Reshuffling (RR). RR is often observed to exhibit faster convergence than sampling with replacement, which can be intuitively attributed to the fact that RR is guaranteed to process each training sample exactly once every epoch, while with-replacement sampling needs more steps than the equivalent of one epoch to see every sample with high probability. Properly understanding the random reshuffling trick, and why it works, has been a challenging open problem (Bottou, 2009; Ahn & Sra, 2020; Gürbüzbalaban et al., 2021) until recent advances in Mishchenko et al. (2020) introduced significant simplification of the convergence analysis technique.
The difficulty of analysing RR stems from the fact that step-to-step dependence results in biased gradient estimates, unlike with-roplacement sampling. Apart from this, RR in FL involves an additional challenge: imbalance in number of samples that leads to the heterogeneity in number of local updates. To the best of our knowledge, analyzing R.R in FL and local update methods remains largely unexplored in the literature despite RR being the default implementation used in simulations and practical deployments of FL; e.g., it is a default option in TensorPlow Federated.
We are only aware of two previous papers analyzing RR for FL (Mishchenko et al., 2021; Yun et al., 2021) and both of these works rely on two assumptions that are usually violated in cross-device FL: (i) that all clients participate in every round, and (ii) that all clients have the same number of training samples. In addition, Mishchenko et al. (2021) only analyze the (strongly) convex setting and Yun et al. (2021) require the Loyasieio condition to hold for the global function. In this work, building on shoulders of the recent advances (Mishchenko et al., 2020), we address all the challenges that come from applying R.R. for FL.
3 Notation and Assumptions
Firstly, recall that the portion of the loss function that belongs to client i is composed of single losses (x)( where j corresponds to j-th data point, and x is a parameter we aim to optimize. We assume that client
We note that the analysis of Wang al. (2020) could potentially accommodate clients using differeut learning rates (in their notation, balancing {[]a:]li) instead of aggregation weights). Still, this an obvious extension of the FRDNOVA analysis and it has been neither considered nor analyzed in theory or practice in previous work.
4

---

Published in Transactions on Machine Learning Research (09/2022)
has access to oracle that takes ().2) imput and returns the gradient (zy(2) output. In order to provide convergence guarantees, we make the following standard assumptions and will discuss how they relate to other commonly used assumptions in the literature. We provide convergence guarantees for three common classes of smooth objectives: strongly-convex, general convex, and non-convex. Assumption 3.1. The functions { are p-convex for 2 0; i.e, for any i,
(Viis(z) - x) - - (fi((z) - (1)(1) + - - u1l²)
(2)
We say that fij is p-strongly convex if μ. > 0, and otherwise fij is (general) convex. Assumption 3.2. The functions } are L-smooth; i.e. there is an L > 0 such that for any i, 2,
[1) Viy((o)l & L|l yll
(3)
Next, we state two standard assumptions which quantify heterogeneily. The first bounds the gradient dissimilarity among local functions {fft} at different clients, and the second controls the variance of local gradients at each client. The same or more restrictive versions of these assumptions appeared in (Karimireddy et al., 2019b; 2020; Wang et al., 2020; Mitra et al., 2021).
Assumption 3.3 (Gradient Similarity). The local gradients (V are (G, bobundd i.., for all x R
n
(4)
If [fr] are convex, then we can relax the assumption to
i [V([= < G² +LLB - f).
(5)
Assumption 3.4 (Bounded Variance). The local stochastic gradients (Vii)) have (o,, P.)-buudded vari- ance, i.e., for all x e Rdd
DJ Σ
v +
(6)
D
Note that we do not require gradient norms to be bounded by constant. Morcover, we do not require the global or local variance to be bounded by constants either, but we allow them to be proportional to the gradient norms. In stochastic optimization, these assumptions are referred to as relaxed growth condition (Botton et al., 2018). Furthermore, one can show that for smooth and convex [fijh these are not actually assumptions, but rather properties (Stich, 2019). While for non-convex functions, these are critical assumptions to show convergence under partial participation.
Following (Karimireddy al., 2020), we also characterize the variance in the Hessian. This an important assumption that helps to understand and showcase the benefits of local steps.
Assumption 3.5 (Hessian Similarity). The local gradients {V have 8- H-Hessian similarity, i.e., for all Rd and E [n], (II-II represents spectral norm for matrices)
| (2)))
(7)
Note that if (fi} are L-smooth then it must hold that |V* S L for all for all x E Rdd and E [m]] and, therefore, Assumption 3.5 is satisfied with 5 < 2L. In realistic examples, one might expect the clients to be similar and hence could happen that < L.
We work with fixed arbitrary participation framework (Horváth & Richtárik, 2020), where one assumes that the subset of participating clients is determined by arbitrary random set-valued mapping S (a "sampling")
5

---

Published in Transactions on Machine Learning Research (09/2022)
Algorithm FEDSHUFFLE
1: Input: initial global model x0, global and local step sizes Vg. ve' proper distribution S for each round r O...., R do server broadcasts to all clients S
for each client E S" (in parallel) do
5: initialize local model y/ + x
6: for e e ,,..., E' do
7: Sample permutation (Tl,,... 11 p. of (I,...,;P)) [Di]}
8: for j = -..... [Dy] do
update yı + y/4 10: end for
of D.
V Vin
11: end for
12: send A; V/- to server
13: end for
14: server computes = Eies ai A;
15: server updates global model I + x 1/A
16: end for
with values in 2mm), sampling S is uniquely defined by assigning probabilities to all 2" subsets [n]. With each sampling S we associate a probabilily matric P E RR defined by P.j def Pr [[1,]] S S). The probability vector associated with S the vector composed of the diagonal entries of P: p (P. .p....., Pn)) R", where
Pe def Pr (i E S). We say that S is proper if p; > 0 for all i. It is easy to show that b def [|[[]] Trace (P) E Pi, and hence b can be seen as the expected number of clients participating in cach communication round. We associate every proper sampling with a vector [st....,8n] for which it holds
P P-pp I Diag(pis $1, P282: ...,. ..Sp))
which is a quantity that appears the convergence rate. For instance, one can show that uniform sampling with participating clients admits 8; (n-b)/(n-1) and full participation allows to set 8; = as P all ones matrix, see (Horváth & Richtárik, 2019) for details. Finally, we note that a fixed arbitrary participation framework is only for case of exposition and our framework can handle non-fixed distributions with minimal adjustments in the analysis.
4 The FEDSHUFFLE Algorithm
We now formally introduce our FEDSHCFFLE method. Its pseudocode is provided in Algorithm 1 (simple) and Algorithm (precise). The main inspiration for FEDSHUFFLE is the default optimization strategy used in Federated Learning: FED As described in McMahan et al. (2017), in FEDAVG one starts each communication round by sampling b clients uniformly at random to participate. These clients then receive the global model from the server and update it by training the model for E epochs on their local data. The model updates are communicated back to the server, which aggregates them and updates the global model before proceeding to the next round. We provide the pseudocode for this procedure in Algorithm 2 in the Appendix.
Unfortunately, we show that FEDAVG (as implemented in practice) does not converge the exact solution due to inconsistency caused by unbalanced local steps and biased aggregation. We discuss each of these issues in details in Sections 4.1 and 4.2, respectively. Therefore, propose new Seoorithm-FDSSUUSE address These limitations of local methods. It involves two modifications compared to FEDAVG: we scale the local step size by p. and we also adjust the aggregation step. In addition, our analysis allows each client to run different number of epochs {E,}, in that case, the local step size scaled proportionally to 1 E. see
to
Section E in the Appendix.

---

Published in Transactions on Machine Learning Research (09/2022)
4.1 Heterogeneity in the Number of Local Updates
We introduce the first adjustment: step size scaling. We consider the samne example Wang el al. (2020), the quadratic minimization problem
[
1
min aERd
Σ x eall.
(9)
D
[P] are given vectors. Clearly, this is a strongly convex objective with the unique minimizer D E C₁. For simplicity, let us assume that we solve this objective using standard FEDAVG with local shuffling and full client participation, i.e., b= [D] Since each local function has only one element, this is equivalent to running Gradient Descent (GD), and therefore for small enough step size this algorithm converges linearly to the optimal solution x². Now, suppose instead that only {e are unique and cach client i has [Dy] copies of et locally. Then, we can write the objective
where {ei
min WER
n
DDi D
f((z); where fi(x)) def
[D.
x e.l..
(10)
D
Applying AvG with local shufling is equivalent to running FEDAVG with E|D; local steps since all the local data are the same. Similarly to Wang et al. (2020), we show that FEDAVG with unbalanced the optimized objective and converges linearly to the
E|D; local steps introduces bias/ stas/inconsistecyy sub-optimal solution = ,//E_,, (id1a) [e:_]// for sufficiently small step size dp (this statement is a direct consequence of Theorem F.1 that can be found in Appendix F). We note that one can choose ([Di]} and { arbitrarily; thus, the difference between ž and x* can be arbitrary large. To tackle this first issue that causes the objective inconsistency, we propose to scale the step size proportionally to 1/D,,1, which removes the aforementioned inconsistency.
In fact, Appendix E contains more general results. We introduce and analyze a general shuffling algorithu PEDSHUPPLEGEN, that encapsulates FEDAVG, FEDNOVA and our FEDSHUPFLE as special cases due to its general parametrization by local and global step sizes, step size normalization, aggregation weights and the nggregation normalization constants; see Algorithm 4 in the appendix. As byproduct, we obtain detailed theoretical comparison of FEDNOVA and FEDSHUPFLE. In nutshell, we show that FEDSHUFFLE balances the progress made by each client and keeps the aggregation weights unaffected while FEDNNVV diminishes the weights for the client that makes the most progress. As a consequence, FEEDSHUFFLE allows larger theoretical local step sizes than both FEDAVG and FEDNOVA while preserving the worst-case convergence rate. We refer the reader to Appendix E,, particularly Section E.2, for the extended discussion and a detailed comparison of all three methods.
Lastly, one might fix the inconsistencies in the FEDAVG by running the same number of local steps K at each client. Note that universally choosing fixed number of steps for all clients is not straightforward. We will compare heuristics based on fixed number K of steps with our proposed approaches in the experiments. To be comparable to other baselines, we use two heuristics to select K :: (1) Set K based on the client with minimum number of data points in the round (FEDAvGMIN), which ensures that such a round will not result in any additional stragglers compared to other baselines. As we will see, AVGANG does not result great performance as it does not utilize all the data on most of the clients. (2) Set K to be the average number of steps that the selected clients would have taken in that round if they were rumning other baselines (F AvEDAN)))))). This makes sure that the total number of local steps for all clients is the same across all basclines. Note that FEDAVGMIN and FEDAAGMEAN are not practical since they require additional coordination among the selected clients to determine the number of local steps to take; we consider them as a heuristic to show the difficulty of choosing a fixed number of local steps for all clients. As we will see, AeeMAn under-performs FEDSHUFFFE and even in some cases FEDAVG, especially in terms of test accuracy in heterogeneous settings.
4.2 Removing Bias in Aggregation
The second algorithmic change compared to FEDAVG has been, to the best of our knowledge, overlooked and it is related to the aggregation step. The original aggregation that is widely used in practice, see Algorithm 2
7

---

Published in Transactions on Machine Learning Research (09/2022)
for FEDAVG practical implementation, contains the step (line 15) where the local weights from the client i E S are normalized to sum to one by "r/Ees myy we refer to this as the Sum One (SO) aggregation. Such aggregation can lead to a biased contribution from workers and therefore to an inconsistent solution that optimizes a different objective as we show in the following example.
Suppose that there are three clients and they hold, respectively. 1, 2 and data points. In each round, we sample two clients uniformly at random. Then, the expected contribution from client i is E, [w//a.], where A, A.=X Ejes s.t. iES Wj. It is easy to verify that this is equal to 7/36, 16/45 and 9/20, respectively. One note that this is not proportional to the weights {w;} of the objective (1). Furthermore, this proposed aggregation cannot be simply fixed by changing the client sampling scheme, e.g., by sampling clients with probability proportional to the number of examples they hold, since one can always find a simple counterexample. The problem of the aggregation scheme is the sample dependent normalization Eies Wi that makes sampling biased in the presence of non-uniformity with respect to the number of data samples per client. To solve this issue, we use "i/p, in the scaling step, where p; is the probability that client is selected. This a very standard aggregation scheme (Wang el. al., 2018; Wangni al., 2018; Horváth & Richtárik, 2019) that results in unbiased aggregation with respect to the worker contribution since E, [M*//x]] wy It is easy to see that if {p;} are proportional to {wy}} then the aggregation step would be simply taking sum. This can be achieved by each client being sampled independently using probability proportional to its weight W/, i.e., its dataset size if the central server has access to this information." 5 If not all clients are available at all times, one can use Approximate Independent Sampling (Horváth & Richtárik, 2019) that leads to the same effect.
4.3 Extensions
As mentioned previously, we introduce FEDSHUFFLEGEN (Algorithm 4) in Appendix E which encapsulates FEDAVG, FEDNOVA and FEdSHUFFLE as special cases and unifies the convergence analysis of these three methods. As an advantage, we use this unified framework to show that it is better to handle objective inconsistency by scaling the step sizes rather than scaling the updates, i.c., it is better to run FEDSHUFFLE rather than FEDNOVA as FEDSHUPFLE allows for larger theoretical step sizes, see Remark E.2 for details.
In addition, our general analysis allows for different extensions such as each client running different arbitrary number of local epochs. FEDSHUFFLEGEN also allows us to run and analyze hybrid approaches of mixing stop size scaling with update scaling to overcome the objective inconsistency. These hybrid approaches would be efficient when applying step size scaling only, i.e. FEDSHUFFLE, might not overcome objective inconsistency due to system challenges. For example, such scenario could happen when some clients cannot finish their predefined number of epochs due to time-out, e.g., large variance in computing time, random drop-off, or ion during local training. In such scenarios, FEDSHUPPLEGEN allows additional adjustments through update scaling.
5 Convergence guarantees
In the theorem below, we establish the convergence guarantees for Algorithm Before proceeding with the theorem, we define several quantities derived from the constants that appear in Assumptions 3.3 and 3.4
def M max (E(m)
2 wi
p2 def
p2
def
Σ of
def 1+ (1+ MB²,
max 1EIN
D
D
iE(M)
and the ones that reflect the quality of the initial solution D def ||20 =
12 --
and F def f(x²) - ft.
Theorem 5.1. Suppose that the Assumptions 3.2-3.4 & hold. Then, in each of the following cases, there exist def ij Eng such that for any ni def
weights {vr}, local step sizes vif def m and effective step sizes ip" the output of FEDSHUFFLE (Algorithm 1)
"lg 2
x" with probability
for T (0, ......... R-13
(11)
Σ, U7
iI may be possible for the server to know the number samples per client because privacy constraints, which case one can always default uniform sampling scheme with pt- = 1/n.
8

---

Published in Transactions on Machine Learning Research (09/2022)
satisfies
Strongly convex: {ft} satisfy (2) for μ > 0, i 1
R
49L then
43L
E [f(x*) - f(x'){ s <0 (MG²
<O(MG
uR + (E² + +
+ DD2 exp
11
)
H 1
88L
General convex: {fe}} satisfy (2) for μ 4= =0
VDMG
+ D2/3 + G2) + 02)//3
LD3
E [[((=)) 50
+
VR
R2/3 2/3 E2/3
R
Non-convez: n
40L then
VFMLG
13 + G2 002 +
LF3 R
|F SO
VR
Re/3 2/3 F2/3
Let us discuss the obtained rates. First, note that for a sufficiently large number of communicttion rounds, the first term is the leading term. This term together with the last term correspond to the rate of Distributed GD with partial participation, where each sampled client returns its gradient as the update. If each client participates then M = 0 and the first term vanishes. The second term comes from local steps using random reshuffling, Note here that the dependency of the noise term a² on the number of communication rounds is R² and R2/3, respectivcly, while for local steps with unbiased stochastic gradients, this would be R and R1/3, This shows that the variance is decreased when one employs random reshuflling instead of with-replacement sampling. We further note that the middle term can be completely removed in the limit where 7g - co, and the local variance o² vanishes when E' + co. We note that such property was not observed for FEDNOVA. The limit Mg - so implics y - and thus FEDSHUFFLE reduces to GD with partial participation. To analyze the effect of the cohort size b (number of sampled clients) on the convergence rate, we look at the special case where each client sampled independently with probability pt = bw, (assume bw; S for simplicity) for all E [n]. We refer to this sampling importance sampling it is casy to see that the M term is minimized for this sampling (Horváth & Richtárik, 2019). In this particular case, M (1-min(w:))/4 and, thus, we obtain theoretical linear speed with respect to the expected cohort size b.
Lastly, we note that the obtained rates do not asymptotically improve upon distributed GD with partial participation, but this the case for every local method with local steps based only on the local dataset, i.e., no global information exploited.
5.1 Improving upon Non-Local Methods
Contrary to the relatively negative worst-case results presented in the previous section, local methods have been observed to perform significantly better in practice (McMahan et al., 2017) when compared to non-local (i.e., one local step) methods. To overcome this issue, Karimireddy et al. (2019b) proposed to use Hessian similarity assumption (Arjevani & Shamir, 2015), and they showed that local steps bring improvement when the objective is quadratic, all clients participate in each round and the local steps are corrected using SAGA-like variance reduction (Defazio et al., 2014). Later, Karimireddy et al. (2020) proposed MIMEMVR that uses the Momentum Variance Reduction (MVR) technique (Cutkosky & Orabona, 2019; Tran-Dinh et al., 2019) and extended the prior results to smooth non-convex functions with uniform partial participation. In our work, we build upon these results and show that FEDSHUFPLE can also improve in terms of communication rounds complexity. To achieve this, we introduce FEDSHUFFLEMVR, a FEDSHUFFLE type algorithm that is extended with MIMEMVR's momentum technique. Each local update of FEDSHUFFLEMVI has the following form
m
Vhe = Vieej-1
di di.ed-1.
(12)
[D.
9

---

Published in Transactions on Machine Learning Research (09/2022)
where
di aV Jam, (Whes) ) (1-a)mi + - (0))"+((-)VVarr, (Key)
Viny (x"))
(13)
where the momentum term m² is updated at the beginning of each communication round
m =
Σ Wi (1- + -a) VES Ps
wi Σ WES Pi
(Vfi(z') v(((x-11))
(14)
For the notation details, refer the reader to Algorithm 3 in the Appendix. The above equations be seen as the standard momentum (first two terms) with an extra correction term (the last term). For a detailed explanation about the motivation behind this momentum technique, we refer the reader to Cutkosky & Orabona (2019). Note that the momentum term is only updated once in cach commuicattion round, this reduce the local drift as proposed by Karimireddy et al. (2020). A convergence guarantee of FEDSHUFFLEMVR in the non-convex regime follows.
Theorem 5.2. Let us run FEDSHUFFLEMVR with step sizes ri TOE min (
1(1"))1- 1/3 " 1,
(G*
momenbum porameler a max m1x211 h), and local epochs E 4/2 Then, given that Assumplions 3.2- 3.5 hold with P, 0 for all i [n], 1, and one client is sampled with probabilities {wi}. we have
R- Æ-1
[P s 00 (
182132// GG2 +02)118
8F + G2 GF2 +
E
V
RE
R2/3
R
Note that our rate is independent L and only depends on the Hessian similarity constant d. Because S L, this rate improves upon the rate of the centralized MVR ((22)))2/1) We note that the improvement is only for the number of communication rounds, and the number of gradient calls is least the same as for the non-local centralized MVR since E8 < L, but main concern here is the communication efficiency. It is worth noting that our results qualitatively similar to those provided by MIMEMVR Karimireddy et al. (2020), but in our work, we consider a more challenging and practical setting. Namely, FEDSHUFFLEMVI does not require that all clients perform the same number of local updates, and each client runs local epochs using random reshuffling. Therefore, we work with biased gradients, and, in addition, we allow for heterogeneity the number of samples per client, which brings another challenge that needs to be adequately addressed in the analysis to avoid objective inconsistency. Lastly, we note that our step size scaling is essential in the provided FEDSHUFFLEMVR convergence theory as it requires balancing the progress made by each client. Therefore, it is not clear whether combination of FEDNOVA and MVR can lead to similar improvement.
6 Experimental Evaluation
For the experimental evaluation, compare three methods FEDAVG, FEDNOVA, and our FEDSHUFFLE with different extensions such as random reshuffling or momentum. We run two sets of experiments. In the first, we perform an ablation study on a simple distributed quadratic problem to verify the improvements predicted by our thcory. In the second part, we compare all of the methods for training deep neural networks on the CIFAR100 and Shakespeare datasets. Details of the experimental setup can be found Appendix F. As expected, our findings are that FEDSHUFFLE consistently outperforms other baselines. Moreover, global momentum leads to improved performance of all methods predicted by our theory.
6.1 Results on quadratic functions
In this section, we verify our thcoretical findings on convex quadratic objective; see (36) in the appendix for details. Figure 1 summarizes the results. The left-most plot showcases the comparison of FEDAVG. FEDAvG with reshuffling (FRDAvGRR), FEDNOVA analyzed in (Wang al., 2020) (with sampling), FEDNOVA
10

---

Published in Transactions on Machine Learning Research (09/2022)
1311
1071
10:1
PedShaffe Fed
FedShulta FerSin
12'2
10'1
Bo
Fesllygitt
TodAegiti
Pedloggin
Indeaciionn
Fecloophese
13"2 Fndtruffle
Fodhona
20
Puchicus
10
Peetibuffe
comm INCAFIO POUNSOS
communication murdds
communication IOUnDS
communication rourdss
Figure 1: Quadratic objective as defined in (36). Each client runs local epoch. Left: A comparison of FEDAvG, FEDAVG with reshufflng AvGRR), FEDNOVA and FEDNOVA with reshuflling (FEDNOVA RR) and FEDSHUFFLE with full participation. Middle Left: the same baselines with the global momentum 0.9. Middle Right: FEDSHUFFLE w/ Sum One and plain FEDSHUFFLE with partial participation (two clients sampled uniformly at random). Right: FEDSHUFFLE with uniform sampling and importance sampling (IS) with partial participation (one client per round).
Table 2: Shakespeare dataset.
Table 3: CIFAR100 dataset.
Accuracy
No Momentum
With Momentum
Accuracy
No Momentum
With Momentum
FEDAVGMIN
35.79 + 0.28
51.13 = 0.27
FEDAVGMIN
48.49 = 0.28
63.62 = 0.20
0.20
FEDAvGMEAN
36.95 0.55
55.38 1. 0.27
AVGMAN
49.24 1: 0.92
64.75 1 0.20
FEDAVG
48.61
64.64 0.10
FEDANG
50.29 1: 0.31
63.04 0.511
FEDNOVA
43.29 0.40
61.65 0.06
FEDNOVA
50.63 = 0.66
62.83 = 0.19
FEDSHUPFLE
59.57 = 0.14
67.63 = 0.35
FEDSHUPFLE
51.97 + 0.20
64.52 + 0.48
with reshuffling (FenNovARR) analyze it in Appendix E, and FEDSHUFFLE. All clients participate in each round and run one local epoch with batch size 1.
As expected, FEDAvGRR saturates at higher loss, since it optimizes the wrong objective, see Appendix E. AVGMIN fixes the objective inconsistency of the AVG, but it is still dominated by other baselines due to decreased amount of local work per client. FEDNOVA provides a better performance since does not contain any inconsistency by construction, but its performance later dominated by noise coming from stochastic gradients. The same holds for FEDAVCMEAN As predicted by our theory, random reshuffling decreases the stochastic noise and FEDNOVARR improves upon the performance of FEDNOVA. FEDSHUFFLE dominates all the baselines since it does not have any objective inconsistency, it uses superior method to remove inconsistencies compared to FEDNOVA, and it also incorporates random reshuffling which itself provides some variance reduction.
In the second plot, we use the same baselines but include global momentum as defined in (13) and (14). We can see that this technique helps FEDAVG to reduce its objective inconsistency since the uoment (14) is unbiased. For other methods, we can see that momentum has a beneficial variance reduction effect expected, and observe convergence to a solution with higher precision. Note that FEDSHUFFLE still performs the best as predicted by our theory.
In the third plot, we analyse the difference between the default implementation of the aggregation step, that is denoted as "sum one" (FEDSHUFFLE w/ SO) since the sum of weights during aggregation is normalized to be one, and our unbiased version, where the weights are scaled by the probability of sampling the given client. We sample two clients in cach step uniformly at random and each client runs one local epoch. As was discussed in Section 4, we observe that FEDSHUFFLE w/ SO converges to worse solution due to objective inconsistency resulting from the biased aggregation.
Finally, we compare FEDSHUFFLE with uniform and importance sampling, where we sample one client per round and the sampled client runs one local epoch. For importance sampling (IS), each client is sampled proportionally to its dataset size. To better showcase the effect of importance sampling, we use a slightly different objective, where d 10, the first client holds 8 data points, and other two clients hold one. As predicted by our theory (decrease of the M term in Theorem 5.1), importance sampling leads to a substantial improvement.
11

---

Published in Transactions on Machine Learning Research (09/2022)
Fastught n.
Taddip
50.3
64
40
Fedlught:
Feclughht
Too
1032
Festughht
8
Fackig
Feelv))
PosMacttoon
Folliee
Fachtza
Fadifono
20
comimniiation rounds
Communccasion rounds
Communication rourds
communcatioon rounds
(a) Shakespeare w/ LSTM
(b) CIFAR1O0 (TFF Split) w/ ResNett18
Figure 2: Comparison of FEDANNMIN, FEDAVG, FEDNOVA, FEDSHUFFLE on real-world datasets. Partial participation: each round 16 client sampled uniformly at random. All methods use random reshuffling. For Shakespeare, number of local epochs is 2 and for CIFAR100, it is 2 5 sampled uniformly at random at each communication round for each client. Left: Plain methods, without momentum. Right: Global momentum 0.9.
6.2 Training Deep Neural Networks
In the next experiments, we evaluate the same methods on the CIFAR100 Krizhevsky et al. (2009) and Shakespeare McMahan et al. (2017) datasets. The results already showcased theoretically (see Sections 4 and Appendix E) and empirically in the previous experiments that reshuffling leads to substantial improvement over random sampling with replacement. Therefore, in these experiments we focus on other aspects of FEDSHUFFLE and show its superiority over other methods that use random reshufiling. To do that, we only consider random reshuffing methods in this section; thus FEDNOVA, FEDAVG, FEDAVGMIN and FEDAvGMEAN refer to AVDRRR FEDNOVARR, AEDAVGMIN and FEDAVGMEAN with (partial) random reshuffling, respectively. For each task, we run 1000 rounds and we sample 16 clients in cach round. For Shakespeare, each client runs two local epochs. For CIFARI00, all clients have the same number of data points. Thus, we follow (Wang al., 2020) to create heterogeneity and test FEDSHUFFLEGEN framework we assume each client runs 2 to 5 epochs uniformly at random. We investigate which method performs the best and, furthermore, we look at the effects of the momentum. and importance sampling. where the description of the used importance sampling strategy can be found in (Horváth & Richtárík, 2019, Section 2.3). We report the test accuracies in Figure 2 and Tables 2 and 3. We observe that FEDSHUFFLE outperforms all the basolines, for the Shakespeare dataset with a large margin. With respect to the global fixed momentum, we can see that this technique helps all the methods and substantially improves their performance. We note that AVGMAAN and FVDAVGMIN perform exceptionally well for CIFAR100 (w/ momentum) but not for the Shakespeare dataset. We conjecture this is due to the significant heterogeneity of the Shakespeare dataset in terms of samples per client. In this setting, FED does not utilize most of the data on clients with larger data-sets, while AvGMEAN over-uses the data on clients with smaller data-size. Note that for CIFAR100, this is not the case as we use an equal-sized split. For completeness, we include the train loss corresponding to Figure in Section in the appendix.
7 Conclusion
This paper introduces and analyzes FEDSHUPFLEF which incorporates the practice of running local epochs with reshuffling in common FL implementations while also accounting for data imbalance across clients, and correcting for the resulting objective inconsistency problem that arises in FED mothods. FEDSHUPFLE: involves adjusting local learning rates based on the amount of local data, in addition to modified aggregation weights compared to prior work like FEDAVG or FEDNOVA. Under an additional Hessian amoothnes: assumption, incorporating momentum variance reduction leads order-optimal rates, in the sense of matching the lower bounds achieved by non-local-update methods. The theoretical contributions of this work are verified in controlled experiments using quadratic functions, and the superiority of FEDSHUFFLE is also demonstrated in experiments training deep neural networks on standard FL benchmark problems.
Promising directions for future work include generalizing the analysis FEDSHUFFLE to cover asynchronous exccution (Huba et al., 2022; Nguyen et al., 2022), incorporating compression mochanisms to reduce commu- nication overhead (Karimireddy et al., 2019c; Mishchenko et al., 2019), and to account for computational and communication heterogeneity across clients (Caldas et al., 2018b; Diao et al., 2020; Horváth et al., 2021).
12

---

Published in Transactions on Machine Learning Research (09/2022)
References
Kwangjun Ahn and Suvrit Sra. On tight convergence rates of without--eplacemmnt SGD. arXiv preprint arXiv:2004.08637, 2020.
Apple. Designing for privacy (vidco and slide dock). Apple WWDC, http://sp//vvebpg...pppaaaa///aa play/wadd2019/700, 2019.
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Xixiv preprint aixi 150.0199000 2015.
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium learning and data science, Paris, volume 8, pp. 2624-2633, 2009.
Leon Bottou. Stochastic gradient descent tricks, volume 7700 of lecture notes in computer science (Inos), 2012.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for largo-scale machine learning. Siam Review, 60(2):223 311, 2018.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.01009 2018a.
Sebastian Caldas, Jakub Konečny, H Brendan McMahan, and Ameet Talwalkar. Expanding the reach of federated learning by reducing client resource requirements. arXiv preprint arXiv:1812.072110 2018b.
Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for foderated learning. arXiv preprinl arXiv:2010. 13723, 2020.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex SGD. arXie preprinl arxiv:1905 10018, 2019.
Aaron Delazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogeneous clients. arXiv preprint arXiv:2010.00 001::2000.11.4 2020.
Mert Gürbüzzaalaaan Asu Ozlaglar, and Pablo A Parrilo. Why random reshuflling beats stochastic gradient descent. Mathemoticol Programming, 186(1):49-88) 84, 2021.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint ar Xi:: 19100. 14425, 2019.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redun- dancy for communication: Speoding up distributed SGD for non-convex optimization. In International Conference on Machine Learning, pp. 2545 2554. PMLR, 2019a.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck R Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. arXiv preprint 1xXiv:1910.1855 2019b.
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Danicl Ramage. Federated learning for mobile kcyboard prediction. arXiv preprint arxiv:1811 (at:181110360,, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEFE conference on computer vision and paltern recognition, pp. 2016.
13

---

Published in Transactions on Machine Learning Research (09/2022)
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735-178) 1997.
Samuel Horváth and Peter Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. In International Conference on Machine Learning, pp. 2781-2789. PMLR, 2019.
Samuel Horváth and Peter Richtárik. A better alternative to error feedback for communication-effcieett distributed learning. arXiv preprint arXiv:2006. 1 10777, 2020.
Samuel Horváth, Stefanos Laskaridis, Mario Almeida, llaas Leontiadis, Stylianos Venieris, and Nicholas Donald Lane. FjORD: Fair and accurate federated learning under heterogencous targets with ordered dropout. In A. Beygekimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:
eT.
Kevin Hsich, Amar Phanishayec, Onur Mutlu, and Phillip B. Gibbons. The Non-IID Data Quagmire of Decentralized Machine Learning. In Proc. of ICML, volume 119, pp. 4387 4398. PMLR, 2020.
Dzmitry Huba, John Nguyen, Kshitiz Malik, Ruiyu Zhu, Mike Rabbat, Ashkan Yousefpour, Carole-Jean Wu, Hongyuan Zhan, Pavel Ustinov, Harish Srinivas, et al. Papaya: Practical, privale, and scalable federated learning. Proceedings of Mochine Learning and Systems, 4:814 802,8322--21 2022.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Xii preprint orXiv:1912.04 049777777 2019.
Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms federated learning. arXiv preprint 200: 03600, 2020.
Sai Pranceth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for ou-device federated learning. 2019a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. arXio e-prints, pp. arXiv-1910, 2019b.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In International Conference on Machine Learning, pp. PMLR, 2019c.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local GD on heterogeneous data. arXiv preprint arXiv:1909.00 04715, 2019.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519 4529. PMLR, 2020.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning, pp. 5381-5393. PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Amoct Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429 2:429-450, 2020.
Wei Li and Andrew McCallum. Pachinko allocation: Dag-structured mixture models of topic correlations. Proceedings of the 23rd international conference Machine learning, pp. 577-584 584, 2006.
14

---

Published in Transactions on Machine Learning Research (09/2022)
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. orXiv preprinl arxiv: 01.1199770288.. 2019.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local SGD with lower communication complexity. arXiv preprint Xiv: 12844, 2019.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local SGD. arXiv preprint arXiv:1808. 072117 2018.
Grigory Malinovsky, Konstantin Mishchenko, and Peter Richtárik. Server-side stepsizes and sampling without replacement provably help in federated optimization. arXiv preprint 221::2221111006 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-
efficient learning of deep networks from decentralized data. In International Conference Artificial Intelligence and Stalislics, pp.
PMLR, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáë, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.00 09269, 2019.
Konstantin Mishchenko, Ahmed Khaled Ragab Bayoumi, and Peter Richtárik. Random reshufiling: Simple analysis with vast improvements. Advances in Newral Information Processing Systems, 33, 2020.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Proximal and federated random reshufiling. arXiv preprint arxix:1002000 06704, 2021.
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Achieving linear convergence in federatod learning under objective and systems heterogeneity. arXiv preprint arXiv:2102.0700 2021.
Yurii Nesterov et al. Lectures on conver optimization, volume 137. Springer, 2018.
John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In International Conference on Artificial Intelligence and Statistics, pp. 3581-3607. PMLR, 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca. Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alhcé-Bue, E. Fox, and R. Garnett (eds.), Advances in Newral Informa- tion Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL http:
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Koncčný, Sanjiv Kumar, and H Brendan McMahan, Adaptive federated optimization. arXiv preprint arXiu:2003.00295, 2020.
Sebastian U Stich. Local SGD converges fast and communicates little. orXiv preprint arXiu:1805.09767, 2018.
Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. ar preprint wrXiv:1907.02222 2019.
Scbastian U Stich and Sai Pranceth Karimireddy. The crror-feodback framework: Better rates for SGD with delayed gradients and compressed updates. Journal of Machine Learning Research, 21:1-36, 2020.
TFF. Tensorflow federated datasets. 2021. URL httppp///wssstaeerroooooo/ereeep python//tff/simlation/// /atiiiinnndtttstss..
Quoe Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint arxi 005.05920, 2019.
15

---

Published in Transactions on Machine Learning Research (09/2022)
Hongyi Wang, Scott Sievert, Zachary Charles, Shengehao Liu, Stephen Wright, and Dimitris Papailiopoulos. 1 No:1806.dr 006.04090, 2018.
Atomo: Communication-elfcientt learning via atomic sparsification. or preprint or Xin:
Jianyu Wang and Gauri Joshi. Adaptive communication strategies achieve the best error-runtime trade-off in local-update SGD. Proceedings of Machine Learning and Systems, 1:212-223 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 Learning Research, 22(213):1 50, 2021.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. arXiv preprint orXiv:2007.07481, 2020.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication-effcienn distributed optimization. In Advances in Newral Information Processing Systems, pp. 1299-1309, 2018.
Blake Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nathan Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Xi preprint arXiv:1805. 10222, 2018.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In International Conference on Machine Learning, pp. 10334-10344 PMLR, 2020.
Cong Xie, Oluwasanmi Koyejo, Indranil Gupta, and Haibin Lin. Local AdaAlter: Communication-effcient stochastic gradient descent with adaptive learning rates. arXiv preprint arxiv:1911. ST::::911.000333 1001000, 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 Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 1693--5700 2019.
Chullee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuflligg: Tight convergence bounds and beyond. arXiv preprint orXiv.2110100322, 2021.
Fan Zhou and Guojing Cong. On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization. arXio preprint Xrx: 708.01012 2017.
16

---

Published in Transactions on Machine Learning Research (09/2022)
Appendix
A FEDAVG with Random Reshuffling
Algorithm FEDAVG with RR
Input: initial global model æ0, global and local step sizes Vig oi
for each round 0,..., R -2-1 do
server broadcasts x² to all clients i e S [n|] sampled uniformly at random with |S*] = b
4: for each client i E S" (in parallel) do
5: initialize local model Vi x"
6: for e l,...., E do
7: Sample permutation {1lF 11 11.1111111 of [l,....|P.I]
8: for j = L.... [Di] do
9: update Vie.. = Veaj- 1i V Vinr - (V
10: end for
11: e+,1+ = DPil
12: end for
13: send A V F.I.D x² to server
14: end for
15: server computes A' = neer di
Eies W;Ai
16: server updates global model r1+1 = x²' - 113 Ar
17:
end for
B Technicalities
B.1 Convex Smooth Functions
We first state some implications of Assumption 3.2. It implies the following quadratic upper bound on fúj
fu(() s (o( (V) x) L x112.
(15)
In addition, if the functions {fij] are convex and xt optimum of f, then
1
Σ (V)((()) {f -*
(16)
2L
Further, if fij is twvice-differentiabl,, then Assumption 3.2 implics that (VT s L for all x see, c.g., (Nesterov et al., 2018, Theorem 2.1.5), where ||:|| refers here to the spectral norm.
Next, include lemma that is useful to provide bounds for any smooth and strongly-convex functions. It can be seen a generalization of the standard strong convexity inequality (2), but this bound can handle gradients computed at slightly perturbed points using smoothness assumption. This lemma turns out to be especially useful for local methods and was also used in the analysis of FedAVG in (Karimireddy et al., 2019b).
Lemma B.1 (perturbed strong convexity). The following holds for any L-smooth and p-strongly conver function h, and any x, y, z in the domain of h:
(Vh()), - y) 2 h(2) h(y) + 11y =112 L|[e x
17

---

Published in Transactions on Machine Learning Research (09/2022)
Proof. Given any æ, ys and 2, one gets the following two inequalities using smoothness and strong convexity of the function h:
L
(Vh(z), 2- z) 2 h(z) h(x)
- 12
1
2
(Vh(x), h(x) h(v)
"
2 11y
Further, applying the relaxed triangle inequality gives
5 ~ 11 1 fly 2112 | =11²
Combining all the inequalities logether we have
(Vh(z), - v) 2 h(2) h(v) + 411 1l - 211²
+ 1
1 - x1
2
The lemma follows since it has to hold 7, 2 n.
B.2 Convergence Derivations
In this section, we cover some technical lemmas which are useful to unroll recursions and derive convergence rates. computations later on. The provided Lemmas correspond Lemma and in (Karimireddy al., 2019b).
Lemma B.2 (linear convergence rate). For every non-negative sequence {dy-1lr21 and any parameters μ >> 0, Mmax E (0, 1/14, c2 0, R 2 2mmazst there crists a constant step size 1j S Tmmx and weights Or (1 (17)) ' such that for VR
def
def R+1
- Ur
1
Ur (1 (m)) d,-1 n
d, cmpr)) ( = (xdo (M1paxx R)
VR
VR
pR)
Proof. By substituting the value of er, we observe that we end up with a telescoping sum and estimate
R+1
R+1
dp V R + cn.
RR
(w--id=-1 vrdr) +
Ur
VRR
VR
1 When R2 2nm (1 -n) < expl 1 Rn < 3. For such an R, can lower bound 1/VR using
1/ 17(1 pn) R > (1 pm)" n11 pm) n (1 - um)
1
(1 -mm)
pm
3/
This proves that for all R 2 2wn'
MR < 3udo un) + en S 3udo exp(-umR) + en.
The lemma now follows by carefully tuning 7, Consider the following two cases depending on the magnitude of R and Imax:
log(maax(1 p Rdg/e)) Then we can choose 1) = 7/max
Suppose ZnR S Mmax
uR
V V & 3pdo exp 1- R + CMmax S 3pdd exp [- [-pmmaax R +
C
18

---

Published in Transactions on Machine Learning Research (09/2022)
log(max((1.g Rdo/e)) u.h
we pick log(max(1,p (ido///))) uuh
Instead if Mmax
to claim that
VR S 3udo exp [- lmaxx 1 Rdo/c)) + +0 +
P.R
M.R.R.
Lemma B.3 (sub linerr convergence rate). For every non-negative sequence {dr-1)r21 and any parameters
Mhuax 2 0, 2 0, R 2 0, there cwists a constant step size S Qmma and weights U, = 1 such that,
def
Σ
R+1
dy-1
d cin + xan+) Tmmx (R+1)
do
2/cido VR+1 +
do
RR
R+1
1
R+
Proof. Unrolling the sum, we can simplify
do + +.n + + c202 n(R +
V R S
Similar the strongly convex case (Lemma B.2), we distinguish the following cases:
When R R+15
dg Ninax
and R+1S de co Namaax
we pick = Mmax to claim
dg + Umax + C2
do
Vci0o
do
V mmx R + 1)
7max
R)
VR+ +1+1
In the other case, have T/
dg (R+T
1/axxx
dg cx
We choose
min V (R(+1))
do : V (R(++1)
to prove
do
d2ez
V n 5
+ 0n
+2
2
() + 1)
V R
+1
(R+1)
B.3
Variance bounds
In this section, provide bounds that useful to bound the variance of the gradient estimators used in this work. We first introduce standard variance decomposition and then state two lemmas.
For random variable X and any Rd, the variance can be decomposed as
E [ X - E X = [||X - y - E X - y
(17)
The first lemmn captures bounds for the variance of unbiased estimator with arbitrary proper sampling. This lemma is adapted from (Chen al., 2020) originally introduced in (Horváth & Richtárik, 2019).
Lemma B.4. Let S1, C2,..., Sn be vectors in Idd and W1, W2,... ... Wn be non-negative real numbers such that E wi 1. Define & def Σn wiGs- Let S be proper sampling. If 8 Ra is such that
P- P-ppT 3 Diag(p15) P2,2,, ... Pn)
(18)
then
E
Σ iES
WiCi
2 8; |call p,
(19)
Pi
1=1
where the expectation is laken over S.
19

---

Published in Transactions on Machine Learning Research (09/2022)
Proof. Let Lies 1 if 8 and Lies 0 otherwise. Likewise, let Lijes if i,j E S and lijes = 0 wili; otherwise. Note that E [Iies] Pt and E [1,ess] Pij. Next, let us compute the mean of X def Eies Pt
wiCi
wi Pi
wii E
X =
E
lies =
[ies] = Σ
wiGi =
Pi
Pj
LEES
1=1
Let A .a..... an] Rdxa, where a; = بككس and let e be the vector of all ones in R" We now write the variance of in form which will be convenient to establish bound:
|||X - E
E
[
[
Wi<i
E
- 1|Š1
Pi
iES
E
wiSi
wiii
lijEs
-15111
Pi
Pj
(20)
WaGh Wrli
Σ
w.wysi Sj
Pij
Pt
Pj
Σ
(Pij P.P;) )o, aj
i
((P pp ATA)...
Since, by assumption, we have P pp = Diag(pos) s)), we can further bound
( pp ) A A)e S T (Diag(p os A A)e Σ pis:|la:l1?
The second lemma bounds the variance of the estimator obtained using the sampling without replacement. The provided lemma is adopted from (Mishchenko et al., 2020).
Lemma B.5. Let Ch...., Sn E Rd be fixed vectors,
12
def
Ce
be their average and
13
2 def
|c 2112
11
be the population variance. Fix any le E {l...., n), let Smi.... Sax be sampled uniformly without replacement from (G....,Sn) and Ek be their average. Then, the sample average and variance are given by
E |
n k 2
(21)
E
k 1)
Proof. The first claim follows by lincarity of expectation and uniformity of sampling:
k = k
h -
E
[
Σ
k
i=1
1=1
20

---

Published in Transactions on Machine Learning Research (09/2022)
To prove the second claim, let first establish that the identity cov(ST.: Indeed,
o² n-
holds for any # j.
n
cov(S Sn2) E [(Gr E,, - 23 n(n 1)
(Gi
C. Cm 2)
1=1 m=1,mpf
{S1 E, Sm -2) -
Σ 1s-
nnn
1)
n(n 1)
1=1 m=1
1=1
1
n
n
0²
(Ci S. Σ
(Gm - ()
n(n 1)
11. 1
0²
This identity helps us to establish the formula for sample variance:
E
Cov cov(S Sxy)
122
k
k
E
IST. 211
+
cov ST,
k22
1=1
i=1 i=1 j=1.fi
0²
n k
koz
k(k: - 1)
k(n - 1) 0².
1
n1
B.4 Technical Lemmas
Next, state a relaxed triangle inequality for the squared l norm.
Lemma B.6 (relaxed triangle inequality). Let (ui,..., 1. be vectors in Rd. Then the following are true
||0 0/11 s (1 a)1 + (1 1+ :) ||u,11 for any a >
(22)
and
|u: |0:1?
(23)
Proof. The proof of the first statement for any >> 0 follows from the identity:
|| + u,11 (1 a) + [ 2) |00 1|
Vao,
1
vo
2/
For the second inequality, we use the convexity of x + ||/|| and Jensen's inequality
21
E
21

---

Published in Transactions on Machine Learning Research (09/2022)
Algorithm FEDSHUFFLE
Input: initial global model x0, global and local step sizes Vg. vi' proper distribution S for each round r O...., R do server broadcasts x' all clients i 8
for each client E S" (in parallel) do
5: initialize local model Vi x²
6: for e e L,..., E' do
7: Sample permutation {II 1.e,0 I 1,,,I.,1-13 of fI,...,12 |Dil]
for j L...., | do update Vig. Kea-i 1i/1p, - (1 10: end for
11: e1,++ = V.,e,.Dal
12: end for
13: send A V.D.I x² to server
14: end for
15: server computes A = = S P:
A
16: server updates global model x +1 x² - 11 '
17:
end for
C
Algorithm 3: Convergence Analysis (Proof of Theorem 5.1)
The style of our proof technique is related to the analysis of FEDAVG of (Karimireddy et al., 2019b). We start with proof for convex functions. By E, [.] we denote the expectation conditioned on the all history prior to communication round r. We first establish the bound on the progress in a single communication round.
Lemma C.1. (one round progress) Suppose Assumptions 3.1 3.4 hold. For any constant step sizes Tn and of def yn satisfying m S (I+MB"JLLT, and effective step size ñj def Eng the updates of FEDSHUFFLE satisfy
pij 2
E || - 2' 2²133 S
x² x²1 EE [f(x"-1) s41 + 3L MG?
where& & is the drift caused by the local updates on the clients defined to be
E
5"
def
Σ
Σ
E,
E,
[IVV x- 113]
D
==
and M def maxie|n)
si siws
Proof. For better readability of the proofs in round progress, drop the superscript that represents the current completed communication round - 1.
By the definition in Algorithm 3, the update A can be written as
E
D.
wi A.
A = Tl iES
v fmi.a- (Whee-1)).
Pi
D
p:
iES ==
We adopt the convention that summation Eiem,ss (M is either [n] or S) refers to the summations def Van (Wiej-1). Using
Σiem EP2
[Pd unless otherwise stated. Furthermore, denote Pies
22

---

Published in Transactions on Machine Learning Research (09/2022)
above, proceed as
E, || + A x²11²] || 1|---' 1--
-2E-1
D
ij
Σ :ES,e.)
pi
(gie.j
x2)) 2t
+ E
BlDi
iES,e.) pi 9i
To bound the term A1, we apply Lemma B.1 to each term of the summation with h fij. I = Vi.e.j-1. = x", and z =x. x. Therefore,
A = E,
2
Σ (ES.e.)
1
- - x²))
D
Pi
< Ex-1
2îj
Σ
(=') falleng- (x) + Ll - 2012
P.
4 1| - x =²)²)
E|D
iES.e.)
= ((x)
[(x))
1 | 1| x1)) 2LTE.
For the second term A2, we have
A2 = Er
Dien
E
iES,e,j
(17)
E D12
17
E
E-
Σ
Pi
- Dies
E
ghed
+
Σ
gi,e.
iES.c.j
tE(n),es
iE|ni,e,
27
(19)
D
17
E
Σ
Ps
Σ
gi,o.j
+
Σ
Diee.
sE/n|
c.j
iE|n|.a.
(23)
27
E,-1
E
Σ
Σ ed
Di.c.
V Vill
+ 2
E 2
Ps
Pi
sEin
ie(n]
2/j
+
D
E,-1
Σ
Dioo.
V V
+ 2 V [
(E(n),e
(23)
21j
E
8;
w. alleegess V (ill...-
+ 217
8;
w f+))1
D
Pi
Pi
iEin).e.
sEin|
+ 27j²
E
[|ains
Vill + 207 1 [
E
iE(n],e.
2 maxx 1
8i
L + 27
max
-
Σ wi [
pi
iE(n]
pi
sE/n
+ 21j L2E E + 2n²
V fx)))
(4)
K 2
1 + max
81
Wi
1/2 L2 27j
max
8;
G² + 27
1
max iE(n]
8;
- wi
B2 [V((2)1
1E(n]
p;
(16)
<
2
1 +
max
$1 W/
1P + 2
W4
62 + ALi²
1+ max 1E(m)
S
B2 (F(x) -f))
(c(m]
Di
pi
pi
23

---

Published in Transactions on Machine Learning Research (09/2022)
Recall M def max { e w/ ). therefore by plugging back the bounds on A1 and A2.
E I + A - 2²11 (1- fi || 4 +
+1+ (1+ M)LL)2LA + 21j MG?.
The lemma now follows by observing that 4LM + +1) s 1 and that B 2 1.
The next step is to bound client drift caused by the heterogeneity of clients' data. Unlike (Karimireddy et al., 2019b), we do not upper bound local client drift using recursive estimates, but we directly exploit smoothness combined with the relaxed triangle inequality.
Lemma C.2. (bounded drift) Suppose Assumptions 3.2 - 3.4 hold. Then the updates of FEDSHUFFLE for any step size salisfying &h S ( have bounded drift:
3L S ((f(=²) - 8)+ + E ((E² - p²)G² +
10
where p2 def pa
maxie(s] T..
o²
def
3/D]
Eie(n) of and M def maxie|n]
{ ( [
Proof. We adopt the same convention for the previous proof, i.e., dropping superscripts, simplifying sum def
notation and having Ji,o.j - Therefore,
<
Σ
E
11 -
E
ic sein]ii
n
c-1 Dj
Σ
Σ Si.ec
gidee +
[
Dip2
iE nl)e.
1=0 c=1
(22)
2nf
6-1 D ΣΣ
E
2
E,-1
Dille
(e- (x((x) Σ Di.cc
Vill..... (x)
sE(n]eed
fn
1
+
E,-1
E
(e-1)).
+
v filla (z)
[
Next, upper bound each term separately. For the first term, we have
27
2
D.
D2 E, E,-1
Σ
Ii.l.c - -e- 1)D.. +
Σ Di,ec - Will (z)
1=0 c=1
(23)
2m
((e - 1) + j)
E,
ΣΣ
gidee V.l. (z))|2 + Σ
gr. V V ae (z))
E
12,12
vE(n]ee
1=0 c=l
2m T.2
24

---

Published in Transactions on Machine Learning Research (09/2022)
For the second term we obtain
2m
E
(e (e- (e-1)DD(VA(t)) +
V V (iT
D
E
D2j
2
se(n]eed
(17)
2nf
E E,
|[(ee + {
V ( (2)
|D|E
Di12
iE|nl
2nf
+ j(12, -)
D.
[ic(() -
|D|E
1Di22
(12,1 -1) [D]
iE|n]ie.j
2
2nj
1
((c-1))//++)
((c
j(D. 1)
(0² + P -
|D|E
Di12
(1D 11 1)
(E(n]iej
2m
Dil
E
E(D, + 1D
(o + P(IV)(
D
F
[D=] 2
1
iE(n)
? +
of
2n
E²
Vf((x)]]++
3 E2
3
iE|n
Combining the upper bounds
{ S L -1 + +
Since 27 < | and ALB / E (1 + P2) v お therefore
3Lg S 9 [((()) (r) + 97m ((F² + G2) + +²²)
10
which concludes the proof.
Adding the statements of the above Lemmas C.1 and C.2, we get
E [| - x²1 1-1
1
jm
E ||x0111
x11
x²1
ñ E,
[f(x* 1f(x"-1--f" 8 [ 27 MG² +
9
((F2 + p2) +00)
2
10
E
1
um
E |||0
2=1
n
E - ff] + 2n² MGG+ + 2n
9î ((E2 + p2) +
2
10
Moving the (f(x"-1) f(*))) term and dividing both sides by #. get the following bound for any
i 1+(F4T)++MB1)141
E,- [f 11
f*1 s f (1 1
10
jm 2
201 + 207 MG² + 9n E ||
+ +0))
En
If μ 0 (weakly-convex), we can directly apply Lemma B.3. Otherwise, by averaging using weights
e, = (1- - and using the same weights to pick output R
simplify the above recursive bound
(see proof of Lem. B.2) to prove that for any satisfying aR क S [H(P4114MBB)1L
E - < 1011. 11 u eep (-2UR) + (4MG))
18 E ((E2+ G2
der
def
det
C2
Now, the choice of îj = min log(maax(1,pp Rd/cs))
([P+1)B+MBB)JL yields the desired rate.
25

---

Published in Transactions on Machine Learning Research (09/2022)
For the non-convex case, one first exploits the smoothness assumption (Assumption 3.2) (extra smoothness term I in the first term in the convergence guarantee) and the rest of the proof follows essentially in the same steps as the provided analysis. The only difference is that distance to an optimal solution is replaced by functional difference, i.., |2 - x=112 f(x²) - f The final convergence bound also relies on Lemma B.3. For completeness, we provide the proof below.
We adapt the same notation simplification as for the prior cases, see proof of Lemma C.I. Since {f() are L-smooth then is also L smooth. Therefore,
8.-1ff(2 f(t)) (V L
E,
[|A||]
= f(x) - -E,-1 ( (F(C))
giees )
f
Lii E +
E
Diee,
D
2
E
iE
iE(u]ie,t
iES,e.)
(22
7
2 f(x)
2
+ 2
E1
E|D
gr...
V Vfa .el
(z)
iE vE(n),eu
27
Lii
+
Ex-1
Σ gises
2
E|D
ieS.c.)
(3)+ $ f(z)
"
712
Laj²
1
+ 2
5
E
Li
ps
gh,e.t
iES,o,
We upper-bount the last term using the bound of A2 in the proof of Lemma C.I (note that this proof does not rely the convexity assumption). Thus, we have
E--1 A) f()) 37 [[f[())]
ΩL 2 f +
The bound on the step size i <
M+(+41)B+MB))44 implies
E [f(x + A]] & f(x) - - Vf(x)] +
3
Next, we reuse the partial result of Lemma C.2 that does not require convexity, i.e. we replace f(x) l with 1 ZI [f Therefore,
E,-1 [ʃ(x {()) - -
97L (E 1 p2)G2 +o?) + MRL
4n
By adding f*r both sides, reordering. dividing by n and taking full expoctation, we obtain
E |V
_ (E|((>)) - S E rr] *MMM -
F (( + G2 -0²
18L
Applying Lemma B.3 concludes the proof.
26

---

Published in Transactions on Machine Learning Research (09/2022)
D FEDSHUTFLEMVE: Convergence Analysis (Proof of Theorem 5.2)
The style of our proof technique is related to the convergence analysis of MIMELITEMMR (Karimireddy et al,, 2020) and non-convex Random Reshuflligg (Mishchenko et al., 2020). By E, [-], we denote the expectation conditioned on the all history prior to communication round r. For the sake of notation, we drop the superscript that represents the communication round in the proofs. Furthermore, we use superscripts and to denote r+1 and r-1, rospectively.
def Firstly, we analyse a single local epoch. For the ease of presentation, we denote Vi,e.0 Vi and
[Dd
gi.e
(24)
D
and
die def (V.i(v))))+ + a)m + (1 -Vii-a)VVVVi. V(((z)).
(25)
In the first lemma,, we investigate how gi.e update differs from the full local gradient update.
Lemma D.1. Suppose Assumptions 3.2-3.4 hold with 0 for all i [n] and B and only one client is sampled. Then, for m
Es |Ilo.. VSi(un))1 s 2n L of [Dj + m I Iddreel.
(26)
Proof. By definition,
D2
E
I1gr. Vf((ue))) E.
1
V
fall (11 - V - (
[D:
(16),(23) L
D2
Eg
Viee.j-1 - vi.el?
[D,
Ø=1
Let us now analyze
1iinnj-1 -viell
D.1
vi.ell
Σ
j(1 - (m-
Σ v fall (Whee
12i12 5=1
(23) 2nk
D. 1-1
fall,o. (25.e.)) V f (Vie)
1D,
R=0
2
j(1 (mm +
fa (Wiie)
D 12
D21 j-1
(16)
2n L
11e, - - vh.el?
1212
j=1 0=0
[D
2m
+
j(1 a) vf((2)) +
f San (Wie)
12
k=
[D_]
ni L
|1,,,j11 1
2nf
+
j(1 - (m vf((z)) +
fill. (Wiee
|D,12
j=1
0
27

---

Published in Transactions on Machine Learning Research (09/2022)
By nu 21. have
D2
8mj
[2d]]
1-1
E
Σ
Mii,e.j11 Ucell
S
E
(1 - (1-a)
a) vf((x)))
V fill. (31,e)
k=
[D:
(21).(6) 8 -
- o. (111)a011)
3|D; ?
(1D -1
< 2n of + ví Dilll
Combining this bound with the previous results concludes the proof.
Next, we examine the variance our update in each local epoch di.e.
Lemma D.2. For the client update (13), given Assumption 3.5 and assuming that one client is sampled, the following holds for any a E [0. 1], where def m f(x)):
||dr,e =f( + 38 z11² (V)((()(( vf(2)]]?
(27)
Proof. Starting from the client update (13), we can rewrite as
di Vs((io)) (1 a)h
(V.ii Vf((z) Vf((ie)) Vf(x))
+ (V((f(( - Vf(z)).
We can use the relaxed triangle inequality Lemma B.6 to claim
lide, (S(ri,)) = - 12)?
+ +. Vf(x)) - Vs((ic) Vf(a))
+ 30 (z(()) vf(i)1
2 3(1 1 + 36
z11² 3a -
It remains to use that (1 (1-60 a)² < since [0.
In the following lemma, we introduce a bound that controls the distance moved by a client in each step during the client. update.
Lemma D.3. For the client update updates (13) with S min{ TEO + and given Assumptions 3.2, 3.4 and 3.5 with P. = for all i E [n] and one client is sampled, the following holds
E 1
E D
E
lutee - x||?
<
16E2
m
E
e=0
(28)
3/1111 + 3a 3a ([) 2 + +1 1121 I? o,
+ 16E 17
[D,
28

---

Published in Transactions on Machine Learning Research (09/2022)
Proof. Starting from the FEDSHUFFLEMVR update (13),
E
E
E
Bi.e
x=1²]
= n
E
Σ D
dis--1
1 Σ E
Σ d1
v(((e))) + Vf((ic))
(gi, vf((va,))))
0
(23)
E ||d.e (((( + E [V [Ilon. vfllone)))))
S 3m
E-1
< 2F 1/1
E |lds, v (Vnt,)))
+ E [
+ [Ilor v(si((t)))))
em0
(26)
I 2E m
E ||di, - vf(eee))))
+ E V fur )11
+ 222 L2
o, D
+ ri I [Idhall))
6=0
(23)
T2 of |D:
4E
m
E |ld..e
+ E [VS( )|
where the last inequality also uses the step size bound
S
1 22.
By exploiting (27), we can further bound
E- 1
E
E-1
E
llvee
2|1?
< 12E
Σ
E
llvie
x1| + 4E
E
| f((nc)))
==
==
e=0
+ nf of
+ 12
12F of V/
|Dal
m S 1 implies that 12E mf 1288
< 3 therefore
4F8
E Σ
E
Iike - x=12]
S 16F.2 of
E
V
0=0
e=0
- - + I of [D.
+ 16E mp
3|111| + 3a
We compute the error of the server momentum m defined as h def m Vs(x). Its expected norm can be bounded as follows.
Lemma D.4. For the momentum update (14), given that Assumptions 3.2-3.5 with P. = 0 for all E [n] and
B B=1 1 hold and one client is sampled, the following holds for any m S ( 408 } and 1 2 a 2 1152E ;
E 11]] < (1-
23a
|14| +
3a²E
[V
{(+))(
24
(29)
of
+ 16
8
E [V
[D.
Proof. Starting from the momentum update (14),
+ = (1 a)h
=11-a) - v
-
29

---

Published in Transactions on Machine Learning Research (09/2022)
Now, the first term does not have any information from current round and hence is statistically independent of the rest of the terms. Further, the rest of the terms have mean 0. Hence, we can separate out the zero mean noise terms from the h and then the relaxed triangle inequality Lemma B.6 to claim
[1 + 11 = (1 - E E [|A]
+ 2( a) || Vf(((t) vf(x)) V((=+)+++
+ 2a
[V]((z> - |
2 (1 ' [|]]|]]]] + 2 a)) || x||²] + 2a E [V(x)) vf(=))]
Finally, note that (1 - a)² V (1 a) S 1 for E [0, 11. Therefore,
h 12] S (1 a) || + E [| - ==17]] + E [
We can continue upper bounding E [|| - x=|?].
D.
E [| - x=|3] = 1i²B E
dg e--l
D
E
Σ (d.c- f((().))) (gi.e (y(ee)
(23)
S 211
E-1
E [ldd,c V[(,))))) + I1gt,
V (i((s))))
(26)
F-1
o²
2 2m
E
Σ
E
ldb.e - V(((i)))1 + +2n
+ ni L2 lIdi 1
[D.]
(23)
of [D.]
F-
F
3 4m E L2
4n E Σ E lldiee- - V + A L2 +
E
| [V(())))
e=0
e=0
(27)
of
I 4nh E L
12m E 11111
12 E² (V vf(x)]
[D,
E-1 Σ
E-1
+ 12n E8²
- x||?
+ 4n L2
V [().
e=0
e=0
(28)
< En (1 48 22) o²
D
12n 2 (1 + 48 2 8²) ||11| 12nj 2 (1 48 -f(x))²
+ -4/ + 4882
Σ E V((
(28)
of |Da
x E2
+ 24m E² 1111
-
E
4n E
E
vf(kne)11
V
30

---

Published in Transactions on Machine Learning Research (09/2022)
where the last inequality uses the upper bound on the step size mp- Plugging this back to previous bound yields
E |1 11 - ( a1 E20 E
+
3
3a
Vf((t) - {(()))
+ 167 E2 o
E E
[D] + 8mi 8 8
E
The last step used the bound on the momentum parameter that 2 2 1152n 88 8 E?, Note that m S 105E ensures that this set non-empty.
Now we can compute the overall progress.
Lemma D.5. For any client update step with step size m min { a To , az 1152n7 E² and given that Assumptions 3.2-3.5 hold with P. = 0 for all i E [n] and B = 1 and one client is sampled with probabilities [wi), we have
R-1 E-1
5
( =
S
+ 25 L202 255a
(30)
RE
Th RF
where vor def (f(x*) 1+)
288m 23a
Fllm" [(x'))] and の² def
D Li=1 of.
Proof. The assumption that L-smooth implies quadratic upper bound (15).
Eg [f(,)ett)] - f(nne) Em Vf(vie),
D.
1
D
di
d
)
Luf E
D2g
1
D
d
--1
j=1
[D
=- 2
V f((c)))
11
(1 - L.
1
d
di 5-1
2
[Del
[D.
+
171 E. 2
di.e.j-1 (((iee))
[D:] 1=1
V f(i.e) ) 12 + E
T I(dde Vf(((.e) - - - ((((ss))))1)
S
2
2
(23)
1
(B(ree))l + mlldd.e vf(M,e))l +nE |Ilo.e - vi(
2
(26)
1
(f(r,e))
mmlld.ee - - +m L2 o?
+ ni L L3lld
2
[D.1
1
(1 An/ L Vf((ne))) 22plldi. - v + 2m 1 o?
2
[D,
1 (1 -m7 T.² [[((,,))
of 2n 1 |Di
2
+ 6m [lAb||2 + 52 52llvi,e x12 [ vf()))))
The first equality used the fact that for any a, 2(a, b) ||a -0ll ||a||2 first equality can be removed since nn +-
|1612.
The second term in the
31

---

Published in Transactions on Machine Learning Research (09/2022)
Applying this incquality recursively with full expectation over the current comminication round
E-1 [ + E
of [Di
E
E [[(xt]] f(x) - 111 (1 4n
6n.
Vive 2:12
+ 6Em ||A||2 a2 [V.((())) -V(())²²
(28) 1
(1 47, 1927/ 28 E-1
V VVy, )1( + 2m L2 + 828) of
Σ
2
[Di
+ 6. (1 + 192nt E² 6² (1111] + a² d(((V - V)(+))²)
E-1
V f(y..))))) )1 4n 222 o.
+ 12Em (11112 +V v((W)))). -V()))
D2
Adding an extra term 12F
|1+ term results to
23a
E f(xx) + 12E
24Th
|1n
1|
f(x)
(29)
S
111
1 104
E2
E-1
Vf( + [4 208 E²22
Em
L2 of DD.
23a
4
a
241
+ 12F
+ (12mia² + 39maa) - |1A112
23a
E-1
fV,,e))) + 5Em L2 of
111
5 6=0
[Di
24m
+ 12E
|||ll + 51maaE -
23a
Taking the full expectation including the client selection step yields
F-1
E E
w) 2
E
[IV + 25n L²o² + 255aG²
E e=
Applying this inequality recursively with the fact v 2 0 leads to the desired result.
Equipped with Lemma D.5, we have
R-IE-1 Σ ==0
5
E
211 |
mRE + 25m L2o2 + +
RE
where to del (f(x9) f*)
288mL 23a
E.
Fl
11.
Further, we need to control ||m - )| Cutkosky & Orabona (2019) show that by using time-varying step sizes, it is possible to directly control this error. Alternatively, Tran-Dinh et al. (2019) use large initial accumulation for the um term. For the sake of simplicity, we will follow the latter approach similarly to the work of Karimireddy et al. (2020). Extension to the time-varying step size case is straightforward Suppose that we run the algorithm for 2R communication rounds wherein for the first R rounds, we simply compute m = R R (x"). With this, we have ||mm - vf(=")) = G² round r =
R Thus, we have for the first
Th = (1(x9) - 1*) + 288m
Elmm O - 22 (f(x") <)(())) 1*) + 288m EG
23a
23aR
Torether, this gives
1 R-1E-1
ΣΣ E | [|1]] 3(f(x') f³)
63G
+ 25m 2 L2 293760G
RE
EiER
aR?
32

---

Published in Transactions on Machine Learning Research (09/2022)
The above equation holds for any choice of min( 4r. ) and momentum parameter 2 1152E282 Set the momentum parameter
400
= max 11522 7
With this choice, can simplify the rate of convergence
5(f(x")- f
318G²
+ 225L220 + 293760E
BER
R
Now let us pick
1/3
"R min 1
f(x)) - 8r
4L, 405E'
E R(5875200 G² + 50 L2
E²
For this combination of step size yn and a, the rate simplifies to
(f(z²) - ()
+ + Bx)
1/3 13)
318G2
20 + () - -1-
+ 390
+
R
R²
ER
Since E then 12 E
82 and L S Eδ, which concludes the proof.
D.1 Discussion on Theoretical Assumptions
Note that in Theorem 5.2, we assume that P: = for all E [n] and B = These are not necessary assumptions, but we rather introduce these more restrictive requirements to match the assumptions that were used obtain previous results. Furthermore, note that we require only one client be samplod in each round. Unfortunately, our results cannot be simply extended to the case with multiple clients sampled in each round. The problem is the aggregation step (line 15 in Algorithm 1) which involves averaging. For analysis and all the previous works that show the improvement over non-local methods in the non-convex setting to work, one would need to assume that the average model performs not worse than the average output of the sampled client. Such a property was empirically observed in (McMahan et al., 2017); thus, is reasonable to assume. Another possibility to replace the averaging by randomly selecting model from one of the sampled clients. We note that while the second option might be preferable in theory as it does not require an extra assumption, might affect the client privacy and therefore not applicable in practice.
33

---

Published in Transactions on Machine Learning Research (09/2022)
Algorithm FEDSHHFFFEEGNN (c, w)
1: Input: initial global model z²: global and local step sizes Vg ni, proper distribution S do
2: for each round r = 0,...,
3: server broadcasts x" to all clients i E S for each client E S (in parallel) do initialize local model vi..0 + x² for = l..... E, do 7: Sample permutation (...0.... .... II 1e. of (I,..../P.I)
for j = ..... [Di] do
local step size vi, ni/e,
10:
update Vie.. Kaa-- ni, V full,...- (W1..--) end for
11:
12:
0 1.0 = Vi,e, end for
13:
14: send A = E., - x² to server
15: end for
16:
Mi AE computes A"= Eies
g." 17: server updates global model x111 x²' - A"
18: end for
E FEDSHUFFLEGEN: General Shuffling Method
In this section, we introduce and analyze FEDSHUPPLEGEN, FEDSHUPFLEGEN a class of algorithms parametrized by local and global step sizes {nī [ where each of its element is the step size normalization for client i, aggregation weights {úu ) and the aggregation normalization constants { {98 1ses.s>>s
R-1 and [m]] step size normalization = {c
Note that we allow the aggregation normalization constants to be non-deterministic. To our knowledge, such results are impossible to obtain with any known analysis, despite this boing standard practice for FEDAVG (where the update of cach client scaled by wa/(E, (Ejs (EjesW))) wy)), e.g., the default way to aggregate in Tensorflow Federated and other frameworks. We include the pseudocode in Algorithm 4. Later in this section, we show that FRDSHUFFLeGen with its parametrization covers wide variety of the FL algorithms in the form as they are implemented in practice.
E.1 Convergence Analysis
We start with the convergence analysis of FEDSHUFFLEGEN, We first introduce the function f(x), which we show is the true objective optimized by Algorithm 4:
fxx def wif((x), where w; del te D. with 1
D
Es lis and W
(31)
Wq.c, 4i
o
C6C;
RE[x]
We denote 8* to be an optimal solution of and f to be its functional value.
Furthermore, FEDSHUPFLEGEN allows the normalization to depend on the sampled clients (line 16 of A Algorithm 4, which requires more general notion of variance. For this purpose, we introduce a n X matrix H. where its elements H., Es
9:9; 1i,jes and h is its diagonal with h, Es ( lies We further of
define vector _ to be such vector that holds
H ce
Diag(h 82, h282, ... hn)
34

---

Published in Transactions on Machine Learning Research (09/2022)
where IR is all ones vector. Note that this is not an assumption as such upper-bound always exists due to Gershgorin circle theorem, e-g., for 8; for all E [n] this holds. Equipped with these extra quantities, we proceed with the convergence guarantees for (strongly-)cones convexx and non-convex functions.
Theorem E.1. Suppose that the Assumptions 3.2-3.4 holds. Then, in each of the following cases, there crist def
def
weights {ur} and local step sizes of in such that for any ni ng 2 1 the output of FEDSHUPFLEGEN (Algorithm 4)
===x' with probability
Cr 0r for r E {0, ......, R- 13.
(32)
En Ur
satisfies
Strongly convex: {fes} satisfy (2) for μ 0, 17
R
4BL and c D,) then
48L
P
E -((=") < s (MiGG2 + (1+p2) G² +o²
DD exp( 8BT. R?)
1R
n R
General convex: {frj} satisfy (2) for = 0, m S
1_ R 2 1 and e, 2 E.(l then 43Lmg
VDMG
12 G2) + 02)1//3
LDB
[( -((")))(($*)) 5o
VR
12/3 119
2/3
R
Non-convex: mn S
1 43Lmg"
R R21 and ai 2 D then
E [[VF{EB>))] 0o
VFMLLG
F2/3 + p2) + 002/1/3
LF3
+
VR
R2/3ng 2/3
R.
where 3 def
1 + M2 + (1 P)B MBB2, p2 def max 3
P.
0² def Eie(n ú1
o7 W.DD. 13
def
Mi
maxiejn] (h:8;0s), M2 def (Eietn) FEE F.(l maxiel)) W }.
1100
x IP? and F def f(x0)= 8
The above rate is generalization of results presented in Section and we refer the reader to this section for the detailed discussion.
E.2
Special Cases
In this section, show how FRDSHUFFLEGEN captures not only our proposed FEDSHUFFLE, but also both FEDAVG and FEDNOVA with hetcrogencous data, arbitrary client sampling, random reshuffling, non-identical local steps, stateless clients and server and local step sizes. To the best of our knowledge, our work is the first to provide such comprehensive analysis.
We start with the FEDAVG algorithm. Algorithm contains a detailed pscudocode of how it is usually implemented practice. is easy to verily that FEDSHUFFLEGEN covers this implementation with the following selection of parameters
① = w, c= max max and d
w'
sE|n]
JEST
Unfortunately, it is not guaranteed that f f. For instance, when all clients participate in each round, cach client runs E local epochs and weight of each client is proportional to its dataset size, i.e. = IP.l//p), then a = /P.1"/ Eet ID,I", which means that the objective that we end up optimizing favours clients with larger amount of data. This inconsistency is partially removed when client sampling is introduced, since the clients with the larger number of data points are average normalized with larger numbers, i.c. qi grows. The inconsistency is only fully removed when only one client is sampled uniformly at random, which does not.
35

---

Published in Transactions on Machine Learning Research (09/2022)
reflect standard FL systems where reasonably large number of clients is selected to participate in each round.
FEDNOVA tackles the objective inconsistency issue by re-weighting the local updates during the aggregation step. For the same example as before with the full participation, FEDNOVA uses the same parameters as FEDAVG with a difference that = s/n that leads to f f- Aarr from full participation, Wang et al. (2020) analyze a client sampling scheme with one client per communication round sampled with probability IP.l/DD)
In our work, apart from providing general theory for shuffligg methods in FL, we introduce FEDSHUFFLE that is motivated by insights obtained from our general theory provided in Theorem F.1. FEDSHUFFLE preserves the original objective aggregation weights, i.e, w = w, it uses unbiased normalization weights during the aggregation slep and it sets G = Ej[Di|- Such parameters choice guaranlees that f= Remark E.2 (FEDSUUFFLE is better than F'EDNOA).. FEDSHUFFFE preserves the original objective aggre- gation weights, i.c., 1 = w. and it uses unbiased normalization weights during the aggregation step. In addition, contrary to FEDAVG and FEDNOVA, FEDSHUFFLE uses q; = E.|D;] (FEDAvG and FEDNOVA require G = maxje(n] [ (D,1), which implies that it allows larger local step sizes than both FEDAVG and FEDNOVA, but it does not introduce any inconsistency as it still holds that f= as for FEDNOVA. Differently from FEDNOVA, FEDSHUPFLE does not degrade the local progress made by clients by diminishing their contribution via decreased weights in the aggregation step. Still, it achieves the objective consistency by balancing the clients' progress at each step while preserving the worst-case convergence rate that can't be further improved Woodworth et al. (2020); Arjevani Shamir (2015).
E.3 Proof of Theorem E.1
By E, I], we denote the expectation conditioned on the all history prior to commuicatiin round r. Lemma E.3. (one round progress) Suppose Assumptions 3.1 3.4 hold. For any constant step sizes Tf def TI and of def Ti satisfying mi S MM and effective step size ij def Wngm,, the updates of FEDSHUFFLEMVR satisfy
E [1|²- 1111 S (1 (1-
[1))
|
1-1 E [ pr] + 3LA + M
M2
2
where& &, is the drift caused by the local updates on the clients defined to be
def
n
E.
W
E,-1
- x 11
qEes
Mi def max (hesp0:) and M2 def (Eietn) Fs Fo(D:l) maxie())
Wasee
Proof. For better readability of the proofs in round progress, drop the superscript that represents the current completed communication round r r-
By the definition in Algorithm 4, the update A can be written as
W Vin (Hree--))
A
11g
4
W
o
We adopt the convention that summation Σiem,e (M is either [n]] or 5) refers to the summations ΣiEM Σe= unless otherwise stated. Furthermore, denote Ite. above, proceed as
def Vallays (Wiej-1)) Using
Wh (gre,,
E, || + 2 = || 12 -2E,-1
W
of
8²)
+ +
E
W
cf
Diec.j
seS,ed
iES
A
36

---

Published in Transactions on Machine Learning Research (09/2022)
To bound the term A1, we apply Lemma B.1 to each term of the summation with h fij. Vi.e,j-1 y fi, and = Therefore,
A1 = E
2
7
Σ
Vi (the. -²)
W
Th
iES.ej
E,-1
1)
of (Jaliaoss (8*) - Salleos- (x) + Ll - -x|/2 //4 11 x 113)
W
iES.e,)
= -2 ((x) - fo + 11
+ 2L1g..
For the second term A2, we have
vi
A2 = 7/ E,-1
Pioe
W
Li
iES
2
27
(17)
1
wi
1
Wi
Wi
S 17 E
Pi
Pins
+
Fi.c.j
W
T: Ci
W
W
qici
VES,eN
(E(m)],.
(31) 2
W2
E E
Σ
hisp0?
P.
Σ
fins e,j
+
Gits
W
Dirr.j
kE|m]
KE(N),ey
(23) 277
has G.
172
h2 1. DD
E
Σ
Σ gies Vill....-1 (2))
+
[Vf(())]
W/2
W22
iE|m]
ie/m]
+
27j2
E,-1
[gi.s Wi qic,
V Ffll..o-
+ 2n fz)) (z)
W
kE(n),es
(23)
27
E,-1
Wu E. Dil
| - Vimnes (x))
+ 2
772
h DD
[()())]
W22
22
W2
Fe
jE(m).ng
<E(r)
Σ
Ee|Di)
277
E [1ohhe. - Vaaliees (x) + 277
v((x)]
+
W2
ieInl.e.j
2M I22g + + M1 Σ
27 20²² Vf(t>)
ic(n
2(M2+
G2 227 2
[+ \
+ M, B3) B1
(16)
S 2(M2 + M3 1.2 + M + A1.7 (1 M13 -r)
By plugging back the bounds on An and A2
E,-1 || + A - 1-12 < (1- 14)
2 ||-- 1-112 -20) + 1))((()) - -p
+ (1 + (Mi + M2) 27 0²
The lemma now follows by observing that 4T5 B² + M2 + 1) < and that B 2 1.
37

---

Published in Transactions on Machine Learning Research (09/2022)
3.4 hold. Then the updates of FEDSHUPFLEMIE Lemma E.4. (bounded drift) Suppose Assumptions 3.2 3.4 for any step size salisfying mn (I+M=+(+ Ba))Abn, and Gi 2 F2]D; for all i E [r]] have bounded drift:
3 1 10 1 f() 9 oi
(1+P2) +
where p2 maxie[n] ".
p
o² Eigln] Wh الح
o²
and Mi def
maxxelm (1an.;;)
Proof. We adopt the same convention as for the previous proof, i.e., dropping superscripts, simplifying sum def
notation and having Di,e.i (Wies-)) Thcrefore,
5
wi E,
-2"
W
iE(n].i.j
D.
gidle
Ii...
W
9:
iE [n] ..ar
1=0
(22)
2rp
Wi
Σ Si..e (1-1) Vf((z) + Σ Diee. Vill...-_ (x)
c-1 D.
VE [..))
1=0
2n
W
(e- (c--))D/Vf((=++ + fil. (x)
kEin),e,j
Next, we upper bound cach term separately. For the first term, we have
2n
W
D
W
Dil.e (e - 1/),.
Fie.
(x)
Se [n].cg
1=0 c=l
(23)
@i((
D.l + j)
c-1 D. ΣΣ
late Villa (x)]12
Σ
geeec V (illaoo- (00))()
W
q007
ie jE)
1=0 c=l
(3)
S 2m L2g
38

---

Published in Transactions on Machine Learning Research (09/2022)
For the second term,
2n
E
(e - L)) + Σ
V fm -.-- (x)
W
e
(17)
2
Wi
Em
([(e-1)] [[(e-1)DD| +
Vmm (x)
(E(n)en
2
Wi
+ +)
j(1D,1 -j)
(12;1 1) [Di] Σ [Vic(()) V((2))
D:
W
iE(n),c.
2
j(DA) - 1) (0 + + (1P,1-
((e-1))p
W
[D
D; 11)
S 2m Σ
dz [+(( 2
1. + P(IV)(()))
6o²
iE[m]
p?
o?
< 2m
Σ
w V
+ 0
3(; F?
iE|n]
2 AL (1
(2)
Combining the upper bounds
S 2n + (1 (( 24) P2)
Since 23 and 4LB² of (1 + P2) 1 + therefore
9 (((((()) (o) gine ((1+
3T
+1++P0 G2 +
10
which concludes the proof.
Adding the statements of the above Lemmas E.3 and E.4, we get
E ||x0 - 10 5
- 201 01|a=-1-
7 E,
[|( - - + 27 M2
977 ((1+P)) +
2
10
1/2
1
E [||0-11 ++1
7 E, [1 - pr] + 20² MiG² +
((1 +
+ +1)+
2
10
2n
Moving the (f(x--1)- - (x*)) term and dividing both sides by i. we get the following bound for any
ñ S (PMM B2))4T
10
9n 2ng
((1 + P2) + P2) +o2)
E E [| |r] <
E 11x0
1-1 207 M2 +
x²
If 0 (weakly-conves)) we can directly apply Lemma B.3. Otherwise, by averaging using weights
= (1 - and using the same weights to pick output z can simplify the above recursive bound
(see proof of Lemma B.2) to prove that for any ñ satisfying μ
1 < ñ < (1+Ma+ M, B-JJ4L
E [[('")] - f(x*)] < 101120 101 pexp(=") 7 (R) 71(4M)
+ tt
18
((1 P2 P2) + 02)
d
01
def 0g
39

---

Published in Transactions on Machine Learning Research (09/2022)
Now, the choice of ij = min log(max((1,) Rd/es))
(1+1)) Ba)aaz yields the desired rate.
pit
For the non-convex case, one first exploits the smoothness assumption (Assumption 3.2) (extra smoothness term L in the first term in the convergence guarantoe) and the rest of the proof follows essentially in the same steps as the provided analysis. The only difference is that distance to an optimal solution is replaced by functional difference, ie., |20 - 1=12 + ((z))-f+ The final convergence bound also relies on Lemma B.3. For completeness, we provide the proof below.
We adapt the same notation simplification as for the prior cases, see proof of Lemma E.3. Since {fr} } are T-smooth then f is also I smooth. Therefore,
E, [ [((++))]/]) A0] S {s(x)
+ EI- (VV(o))
+
- E.-1
||||i]
2
= f(x) - -1 |
(V((o)
n
W
Li
gised
+
E,
Free
W
qies
2
W
g C2
iE(n]iew
iES,c,J
(22)
1/ V f( (z))
||
+ "
w
I f(x)
2
E
W
qics
(h
fall, (x))
-..-
ie
27
Lij
E
Σ
gi.e.j
2
W
g: cs
iES.e.)
(2)))2))
2
Lij
1
((0)
Mag
+
E
2
W
c4
iES.e.j
We upper-bound the last term using the bound of Ag in the proof of Lemma C.1 (note that this proof does not rely on the convexity assumption). Thus, we have
E,- [[]++ s f(x) - (())
TT2 M&t (M1 + MMG (|
The bound on the step size ザ S (L+M+++++ij++MBBBB B.))44 implies
E. E- fz) 7 [V((2))
3ÿL2 4 +
Next, we reuse the partial result of Lemma C.2 that does not require convexily, i.e., we replace f(x) f with 2. fxx)). Therefore,
1 I1 ) E, [( + +2) s f(x))
97 4ng
+
(1+ +o²) + M.L.L
By adding for both sides, reordering, dividing by ń and taking full expectation, we obtain
18L E V 17 < - E [(x") |r] - x+) + G
1 ((1 + G2 +
Applying Lemma B.3 concludes the proof.
40

---

Published in Transactions on Machine Learning Research (09/2022)
E.4 General Variance Bound
In this section, we provide more general version of Lemma B.4. We recall the definition of the indicator function used in the proof of the aforementioned lemma, where lies = 1 if E S and Lies = otherwise i,j E S and lijes = otherwisc. Further, let be n x n matrix, where 9:9 lijes and h is its diagonal with h; = Es (nff) lies). We are ready to procoed with the a5
and, likewiso, Lijes
of
H, = Es
lemma.
Lemma E.5. Let S1. S2..... Sn be vectors in Rd and Wi, Wa, Wn be non-negative real numbers such that
E wi = 1. Define Ç del Lim1 th Sr. Let be proper sampling. If s E 12 such that
ee z Diag(h1s2 82, h282........................ ..... Sn),
(33)
then
3
n
wi
E
h;s
(34)
iES
i=1
where the expectation is taken over S and is the vector of all ones in TR..
Proof. Let us first compute the mean of X def Eies
wiGe
q.
WiCi
wiGi g
E
E
E
lies
lies
Ç.
qi
Let A ( an.] E IRdxn, where ai
wilt,
We now write the variance of X in a form which will be
2
convenient to establish a bound:
E [ E
[X]]I = E [] [X]]
E
S
1K
T
iES
E
W/
W
1ijes
11211
(35)
H WiGi WyGi
WiST Wisj
Σ
qb
4j
qi
qi
1.
i.j
Σ (Hij - -1)a aj
ee -T(((- [ee--ee] A A)e.
Since, by assumption, we have H eeT = Diag(h o s), we can further bound
(HH ee A A)e < T (Diag(h o 08) AT ATA)e
Σ has: kasilla.1??
41

---

Published in Transactions on Machine Learning Research (09/2022)
Table 4: Baselines. W/ or W/O Replacement
Local Steps/ Epochs
Pseudocode
Gradient Sampling"
FEDAvGRR
Epochs
W/O
Algorithm 2
Reddi al. (2020)
FRDAVGMIN
Steps
W/
Algorithm with K K min
Reddi et al. (2020)
FEDAVGMEAN
Steps
W/
Algorithm with K K mean
FEDNOVA
Epochs
W/
Wang et al. (2020)
Algorithm 4
FEDNOVARR
Epochs
W/O
with FEDNOVA aggregation
FEDSHUFFLE
Epochs
W/O
Algorithm 1
For real-world datascts, as commonly implemented practice, all mothods use without replacement sampling, i.c,
random reshuffligg
K Kmin corresponds to the minimal number of steps acroes clients for FEDAVRRR.
K Kmean corresponds to the average number of steps across clients for FEDAvGRR, i.., FEDAVGMEAN and FEDAvGRR
perform the same total computation.
F Experimental Setup and Extra Experiments
As mentioned in the previous section, we compare three algorithms FEDAVG, FEDNOVA, and our FED- SHUFFLE. For FEDAVG, include an extra baseline that fixes objective inconsistency by running the same number of local steps per each client. To avoid extra computational burden on clients, ie., to avoid stragglers, select the number of local steps to be the minimal number of steps across clients. We refer to this baseline as FEDAVGMIN, Another FEDAVG-type baseline that we compare to is FEDAvGMEAN. Similarly to MVNANGMIN, AvGMEE runs the same number of local steps per each device with a difference that the number of steps is selected such that the total computation performed by FEDAVGMEAN is equal to FVD with local epochs. We include this thcoretical baseline to see the effect of heterogeneity in local steps and whether it is beneficial to run full epochs. We consider three extensions: (i) random reshuftlig for FEDAvG, and F FEDNOVA, since those methods were not originally analysed using biased random reshuffling but rather with unbiased stochastic gradients obtained by sampling with replacement, (ii) global momentum. Our implementation of FEDAVG and FEDNOVA follows (Reddi et al., 2020) and (Wang et al., 2020), respectively. In all of the experiments, the reported performance is average with one standard deviation over 3 runs with fixed seeds across methods for a fair comparison.
Hyperparameters. The server learning rate for all methods is kept its default value of 1. For all momentum methods, we pick momentum 0.9. The rest of the parameters for the simple quadratic objective are selected based the thcoretical values for all the methods. For the other experiments (Shakespeare and CIFAR100), the local learning rate is tuned by searching over grid {0.1, 0.01, 0.000.00000) and we use a standard learning schedule, where the step size is decreased by 10 at 50% and 75% of all communccation rounds. We note that FEDSHUFFLE uses different local step sizes for each client nf = ni/ D,I. For a fair comparison, we take the local learning rate for FEDSHUFFLE to be the local learning rate for the client with the largest number of local steps as this follows directly from the theory. The global momentum as defined in (13) and (14) is only used in this form for the toy experiment. For the real-word experiments, we ignore the last term and we approximate ff((")) EYp.ly, A to avoid extra communication and computation. Note that for both FEDNOVA and FEDSHUFFLE, the estimator of ff(=") is proportional to A and, therefore, the server directly update the global momentum using only this update. For FEDAVG, this is not the case and it is closely related to the objective inconsistency issuc. Despite this fact, we provide FEDAVG with the proper momentum estimator that improves its performance as it reduces the objective inconsistency. Lastly, for neural network experiments we allow each method to benefit from the weight decay (0, le 4} and the gradient clipping {5, oo), i.c., we do a grid search over all the combinations of step sizes, weight decays and gradient clippings. For the toy experiment, the batch size is 1 and for neural nets, we select batch size to be 32.
42

---

Published in Transactions on Machine Learning Research (09/2022)
4.0
Felfestoon
FedtayMoon
Festorptoon
35
Fezdeg
1.5
Fadlez
Peskig
Fediiva
2.3
Fechooa
110
Fachfooa
2.5
Fuchove
2.5
FedS
222
FerSturte
2.5
FedSttute
2.0
Fectouute
2.40
3.5
10
300
commun cation nounds
communicttion rounds
communiar on rounds
communication rounds
Shakespeare w/ LSTM
(b) CIFARI00 (TFF Split) w/ ResNet18
Figure: 3: Comparison of the moving average with slide 20 of the train data loss on FEDAVGMIN, AEDAVG, FEDNOVA, FEDSHUFFLE on real-world datasets. Partial participation: in each round 16 client is sampled uniformly at random. All methods use random reshuffling. For Shakespeare, number of local epochs is 2 and for CIFAR100, is 2 to 5 sampled uniformly at random at each communication round for cach client. Left: Plain methods. Right: Global momentum 0.9. Note that the displayed loss is only for the truin data, and it does not include the 12 penalty; therefore, its informative value is limited.
10-1
FedNovoRR
FedShuffle FedShuffleGen
1012
10-3
10-4
0
200
600 800
1000
communication rounds
Figure 4: Quadratic objective as defined in (36). Each client runs one local epoch. A comparison of FEDNOVa with reshuflling (FEDNOVA RR) and FEDSHUPFLE and FEDSHUPFLE with FEDNoVA-like aggregation weights to remove objective inconsistency caused by unfinished local rounds (FEDSHUFFLEGEN) with full participation.
Datasets and models. We run experiments on three datasets with three corresponding models. First, we consider a simple quadratic objective
6 Σ1 |r e;11 i=1
min ZE 12
(36)
where is the canonical basis vector with at i-th coordinate and 0 elsewhere. We partition data into 3 clients, where the first client owns the first data point, the second is assigned eq and es and the rest belongs to the third client.
For the second task, we evaluate a next character prediction model on the Shakespeare dataset (Caldas et al., 2018a). This dataset consists of 715 users (characters of Shakespearc plays). where cach example corresponds to contiguous set of lines spoken by the character in given play. For the model, an input character is first transformed into 8-dimensional vector using embedding layer, and this is followed by LSTM (Hochreiter & Schmidhuber, 1997) with two hidden layers and 512-dimensional hidden state.
Last, we consider an image classification task on the CIFAR100 dataset (Krizhevsky et al., 2009) with a ResNet18 model (He et al., 2016), where we replace batch normalization layers with group normalization following (Hsich et al., 2020). The data partitioned across 500 clients, where each client owns 100 data points using a hicrarchical Latent Dirichlet Allocation (LDA) process (Li & McCallum, 2006). We use equivalent splits to those provided in TensorFlow Federated datasets (TFF, 2021).
43

---

Published in Transactions on Machine Learning Research (09/2022)
Our implementation is in PyTorch (Paszke et al., 2019).
For the first experiment, we only consider performance on the train set (i.e., training loss), while for the real-world datasets we report performance on the corresponding validation datasets (validation accuracy).
Baselines. For the experimental evaluation, we compare three methods FedAvg, FedNova, and our FedShuffle- with different extensions such as random reshuffling or momentum
F.1 Hybrid approach to tackle system challenges
As discussed in Section 4.3, FEDSHUFFLEGEN allows us to run and analyze hybrid approaches of mixing step size scaling with update scaling to overcome the objective inconsistency caused by system challenges. In this example, we assume that each client does not finish the last iteration of the local training. To fix this issue, employ FEDSHUPFLE and FEDNoVA-like aggregation that fixes objective inconsistency (we refer to this method as FEDSHUFFLEGEN since it is its special case); see (31) for the selection of weights, We use the quadratic objective as introduced above with full participation, and each client runs one local epoch. As it can be seen from Figure 4, as expected, FEDSHUPFLE suffers from objective inconsistency since some clients do not finish the prodefined number of local steps. However, our FEDSHUFFLEGEN based technique fixes objective consistency caused by system challenges while providing superior performance when compared the plain FEDNOVA method with reshuffling (FEDNOVA RR).
44


Reviews:
[{"review_id": "WkJb7z9g08", "reviewer": "Reviewer_5ooG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Very comprehensive analyses are provided for the framework and the algorithms. These analyses could be of interest for future research.\n2. Random reshuffling is commonly used in practice while less attention is spent on it in federated learning research. This work fills the gap in the area.\n\nWeaknesses:\n1. The new algorithm is an ensemble of commonly used techniques and is a straight forward design, I assume some practitioners might have been already using it. Thus the algorithm design is less interesting itself.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies using random reshuffling in federated learning algorithms, along with other techniques coping with data heterogeneity and client sampling. A general algorithmic framework is proposed and convergence analyses are provided. Some new algorithms using random reshuffling are proposed and experiments show these algorithms have good performance.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Current version looks good to me. A  few suggestions are 1) adding more insights discussion on random reshuffling since this is the main difference that separate this work with existing works 2) add more experiments comparing algorithms with and without random reshuffling to provide readers an idea on how much random reshuffling could help. \n\n", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9kLe5GXUBo", "reviewer": "Reviewer_y9tc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The paper presents a generalization of FedAvg and FedNova and FedAvg with momentum variance reduction, including convergence results for this general algorithm.\n- The paper presents a range of convergence rate results.\n\nWeaknesses:\n- The main motivation for FedShuffle is that FedAvg would sample data with replacement and that reshuffling is beneficial. Yet, it seems the convergence analysis in this paper (appendix C) assumes gradients are drawn iid.\n- How can the objective function of FedAvg with drawing data with replacement be wrong, when there are convergence results for this setup (e.g., [1], or [2] with a similar gradient similarity assumption)?\n- The claim that FedAvg does not perform reshuffling is false. In the original paper, local data is partitioned into batches in each epoch (cf. Algo 1 in [3]) and reshuffling is a common practice in most implementations.\n- the authors claim that fixing a number of update steps or epochs between communication rounds is hard, mainly because determining it requires sending local dataset sizes, which might infringe privacy. This claim seems unsubstantiated, since standard FedAvg requires sending local dataset sizes to normalize updates, anyways. Moreover, many practical implementations (including the original FedAvg) perform a fixed number of updates between communication rounds. \n- The scaling of local learning rates is unnecessary if local dataset sizes are roughly equal, so their main use should be when local dataset sizes vary greatly. In this scenario, choosing a normal learning rate means that the effective local learning rate (i.e., chosen learning rate divided by local dataset size) is miniscule for clients with larger datasets. Choosing a large learning rate instead (so that for clients with large local datasets the effective learning rate is normal) means that for clients with small local datasets the learning rates will be enormous. Since learning rates in non-convex optimization - in particular deep learning - impact the minima that are found, this could deteriorate the model quality substantially (even if it does not impact the convergence rate). \n\n[1] Li, Xiang, et al. \"On the Convergence of FedAvg on Non-IID Data.\" International Conference on Learning Representations. 2020.\n\n[2] Yu, Hao, Sen Yang, and Shenghuo Zhu. \"Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.\n\n[3] McMahan, Brendan, et al. \"Communication-efficient learning of deep networks from decentralized data.\" Artificial intelligence and statistics. PMLR, 2017.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper analyzes the convergence of federated learning for heterogeneous local data, in particular when reshuffling local data in each epoch and rescaling local learning rates by dataset size. Moreover, the paper proposes to use momentum and variance reduction in local updates to improve convergence. It then derives a general form of these approaches that also is a generalization of classical FedAvg and FedNOVA. It provides convergence rates for these approaches, as well as the general version.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Critical:\n- Clarify the issues of existing methods and how this paper overcomes them, in particular wrt. to their original description. Claiming that (i) FedAvg would not perform reshuffling and that this is a major issue, (ii) choosing a fixed number of updates between communication rounds is hard, and (iii) communicating local dataset sizes is problematic without substantiating these claims runs the risk of being a strawman argument.\n- Clarify whether the convergence analysis assumes reshuffling or for drawing gradients iid. The proof in the appendix even does not mention reshuffling, but rather seems to analyse the convergence of FedAvg. \n- relate convergence results to existing ones: explain the differences in assumptions and proof techniques and differences in the rates to existing convergence rate results. This includes discussing the novelty over the proof in Karimireddy et al., 2019b.\n- analyze the impact of learning rate rescaling on model quality in deep learning\n- please discuss the assumption of gradient similarity / Hessian similarity to the non-iid setting. Since this work is mainly motivated by the problems of FedAvg under heterogeneous local data, assuming gradient similarity seems counter-intuitive.\n\nNon-critical:\n- in the example computation in 4.2, I got $\\frac{10}{36}$ for $i=1$ instead of  $\\frac{7}{36}$, but I might have made a mistake. Please provide the computation, e.g., in the appendix.\n\n", "broader_impact_concerns": "I do not have concerns on the ethical implications of this work and thus do not see a requirement for a broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "afX36c3Ssl", "reviewer": "Reviewer_T6NJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Careful theoretical analysis of important ingredients of federated learning, including heterogeneous local steps, random reshuffling and momentum variance reduction.\n2. This work proposes several algorithms, FedShuffle, FedShuffleMVR and FedShuffleGen. Convergence analysis of each algorithm is given.\n3. Experiments on CIFAR100 and Shakespeare, which show the improvement of FedShuffle over baseline algorithms.\n4. Good literature survey of recent related work.\n\n\nWeaknesses:\n1. Although I appreciate the detailed convergence analysis of FedShuffle, the main algorithm seems like a direct combination of many tricks used for FL, which makes the work sounds a bit incremental. In fact, as shown in Table 1, all of the tricks have appeared in previous works, including FedNova, FedLin, Mime and FedRR. This work seems like a chowder of these various tricks. \n2. Some notations are not clear for non-experts. (See the next section)\n3. Some paragraphs are not clearly written and further motivations/explanations are needed. (See the next section)\n4. In the experimental section, the comparison wrt the baselines is limited. More related algorithms are needed for demonstrating the effectiveness of FedShuffle.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides detailed convergence analysis for FedShuffle, which includes several ingredients commonly used in federated learning but not rigorously analyzed, including random reshuffling, heterogeneous data, non-identical local steps, global momentum, etc.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Page 2, 4th paragraph: Why do we suddenly talk about random reshuffling? Could you add some motivation for this technique? \n2. Page 2 before contributions: why would you say \"a unified view\"? Accounting for all these tricks does not sound like a unified view but more like a simple composition.\n3. Typo: Page 4, 3rd paragraph: \"in  Mishchenko\"\n4. Section 3, Assumption 3.1: maybe it's worthwhile to (re)introduce $(j, x)$.\n5. Assumptions 3.3, 3.4: is it a well-known assumption in the field? If so please add relevant references.\n6. Page 5 typo: $s_i = n - b/n - 1$\n7. Page 5: \"Finally, we note that a fixed arbitrary participation framework is only for an ease of exposition and our framework can handle non-fixed distributions with minimal adjustments in the analysis.\" Could you explain how the minimal adjustments can be made?\n8. Page 5: what is the meaning of the vector $s$?\n9. Section 4.1, eq. (9): this example is adapted from FedNova and some reference needs to be made.\n10. Before Sec 4.2: this paragraph should be moved to the experimental section;\n11. Sec 4.2 2nd paragraph: the derivation is not quite straightforward. The authors might want to explain the example separately and show the details;\n12. Sec 4.2: \"This is a very standard aggregation scheme\". Any reference?\n13. Question: Which algorithm do you recommend the most, FedShuffle, FedShuffleMVR or FedShuffleGen? Any theoretical comparison on the convergence rates?\n14. Sec 5, before Thm 5.1: (re)explain $s_i, p_i, P_i, B$.\n15. Page 9, line 1: why would $M = 0$ will full participation?\n16. Page 9 line 5: how can we have $\\eta_g \\to \\infty$? This is not practical.\n17. Page 9: the terminology \"importance sampling\" has its special meaning. Is your method the same as the standard terminology?\n18. Page 9: Before Theorem 5.2: (typo) we \"refer reader to\"\n19. General typo: \\citet vs. \\citep: Page 2 (Karimireddy et al., 2020); Page 4: (Mishchenko et al, 2021), (Yun et al., 2021)\n20. Sec 6.1 typo: see (36) in appendix; due to decreased amount\n21. Baseline comparison in Table 2/3: \"FedAvgMin\" and \"FedAvgMean\" are from the current paper and may not be regarded as strong baselines. The authors should implement FedLin, Mime, FedRR, FedProx, VRLSGD and SCAFFOLD that are mentioned in the related work.\n22. Large blanks in the appendix: Page 20; page 23.\n\n\n", "broader_impact_concerns": "The authors did not discuss the broader impact. This is okay as it is a theoretical paper, but general discussion on federated learning might be good.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide a unified theoretical analysis of a few implementation practices in federated learning (FL), including random shuffling (widely used but rarely analyzed until lately), client sampling, adaptive step size, momentum and variance reduction. While this work built on some results from previous works, I believe its analysis on random shuffling and more general subsampling in FL is timely and interesting. The authors also carefully compared to other recent baselines and showed some improvements. A few confusions were clarified during the discussion, thanks to the authors' efforts. As the authors acknowledged, the proposed algorithms are perhaps not too surprising from a practical perspective, but the simplified and unified analysis (which is the focus here) may still prove useful and inspiring to researchers in FL. Overall, we conclude that the presented results are great additions to FL.

Please consider making the following changes in the final version: 
- Abstract in the submitted pdf differs from the one on openreview.
- The analysis of the example in Section 4.1 is deferred to Appendix E but it is not clear where this analysis can be found. If the argument is not long, I'd suggest moving the details to the main body. Comparing to $E=\infty$ on this example would also be interesting. $N$ in Eq (9) should be $n$?
- Is it possible to measure Hessian similarity during the iterations? This empirical quantity might provide more insights on the experimental results.
- As the reviewers suggested, it may be beneficial to explicitly point out the novelties in the proof against existing work. The statement in the contribution list is a bit too high level while the appendix (where proofs are) did not highlight the key parts. 

Decision: Accept (poster)