Mixed Federated Learning: Joint Decentralized and Centralized Learning
Authors: Sean Augenstein
Andrew Hard
Lin Ning
Karan Singhal
Satyen Kale
Kurt Partridge
Rajiv Mathews
Venue: Submitted to ICLR 2023 (2023)
Keywords: federated learning
decentralized learning
privacy
security
distribution shift
distribution skew
mobile computing

Abstract: Federated learning (FL) enables learning from decentralized privacy-sensitive data, with computations on raw data confined to take place at edge clients.  This paper introduces mixed FL, which incorporates an additional loss term calculated at the coordinating server (while maintaining FL’s private data restrictions). For example, additional datacenter data can be leveraged to jointly learn from centralized (datacenter) and decentralized (federated) training data and better match an expected inference data distribution.Mixed FL also enables offloading some intensive computations (e.g., embedding regularization) to the server, greatly reducing communication and client computation load.  For these and other mixed FL use cases, we present three algorithms: PARALLEL TRAINING, 1-WAY GRADIENT TRANSFER, and 2-WAY GRADIENT TRANSFER.  We perform extensive experiments of the algorithms on three tasks, demonstrating that mixed FL can blend training data to achieve an oracle’s accuracy on an inference distribution, and can reduce communication and computation overhead by more than 90%. Finally, we state convergence bounds for all algorithms, and give intuition on the mixed FL problems best suited to each. The theory confirms our empirical observations of how the algorithms perform under different mixed FL problem settings.

Under review as a conference paper at ICLR 2023
MIXED FEDERATED LEARNING: JOINT DECENTRALIZED AND CENTRALIZED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) enables learning from decentralized privacy-sensitive data, with computations on raw data confined to take place at edge clients. This pa- per introduces mixed FL, which incorporates an additional loss term calculated the coordinating server (while maintaining FL.'s private data restrictions). For example, additional datacenter data can be leveraged to jointly learn from central- ized (datacenter) and decentralized (federated) training data and better match an expected inference data distribution. Mixed FL also enables offloading some inten- sive computations (e.g., embedding regularization) to the server, greatly reducing communication and client computation load. For these and other mixed FL use cases, we present three algorithms: PARALLEL TRAINING, 1-WAY GRADIENT TRANSFER, and 2-WAY GRADIENT TRANSFER. We perform extensive experi- ments of the algorithms on three tasks, demonstrating that mixed FL. can blend training data achieve an oracle's s accuracy on an inference distribution, and can reduce communication and computation overhead by more than 90%. Finally, we state convergence bounds for all algorithms, and give intuition on the mixed FL problems best suited to each. The theory confirms our empirical observations of how the algorithms perform under different mixed FL problem settings.
INTRODUCTION
Federated learning (FL) (McMahan 2017) is a machine learning setting where multiple 'clients' (e.g., mobile phones) collaborate to train a model under coordination of a central server. Clients' raw data are never transferred. Instead. focused updates intended for immediate aggregation are used to achieve the learning objective (Kairouz. et al.) 2019). FL. typically delivers model quality improvements because training examples gathered in sifu by clients reflect actual inference serving requests. For example, a mobile keyboard next-word prediction model can be trained from actual SMS messages, yielding higher accuracy than a model trained on a proxy document corpus. Because of the benefits, FL has been used to train production models for many applications (Hard et al. 2018 Ramaswamy et al. 2019; Apple 2019 Ramaswamy et al. 2020
Hartmann 2021 Hard et al. 2022)
Building on FL, can gain significant benefits from 'mixed FL': jointly training with additional
centralized objective in conjunction with the decentralized objective of FL.. Let x be model parameters to be optimized. Let denote mixed loss, sum?] of a federated loss and centralized loss fc:
f(z) f((x) fc(x)
Mixed loss might be a more useful training objective than for many reasons, including:
Mitigating Distribution Shift by Adding Centralized Data to FL While FL helps with reducing train vs. inference distribution skew, it may not remove it completely. Examples include: training device populations that subsets of inference device populations (e.g.. training high-end phones, for eventual use also on low-end phones), label-biased example retention on edge clients (c.g.. only retaining positive examples of binary classification task), and infrequent safety-critical example
We use joint'' to distinguish our work from sequential 'central-thent then-FLL use cases, c.g. transfer learning. "To simplify we subsume any relative weights into loss terms, i.e. this can he f(x) (w.ff))))))()(()))

---

Under review as a conference paper at ICLR 2023
events with outsized importance (e.g., automotive hard hard-braking events needed train a self-driving AI) [Anonymous] a). The benefits of FL can be achieved while overcoming remaining distribution skew by incorporating data from an additional datacenter dataset, via mixed FL. This affords composite set of training data that better matches the inference distribution.
Reducing Client Computation and Communication In representation learning, negative exam- ples are used to push dissimilar items apart in a latent embedding space while keeping positive examples closer together (Oord et al. 2018). In federated settings, clients' caches may have lim- ited local negative examples, and recent work (Anonymous) b) showed this significantly degrades performance compared centralized learning. This work also showed that using an additional loss (a regularization) to push representations apart, instead of negative examples, can resolve this performance gap. However, if done naively this requires communicating and computing over large embedding table, introducing massive overhead for large-scale tasks. Applying mixed FL, where federated loss fr is the primary 'affinity' loss and centralized loss fe is the 'spreadout' regularization, avoids communicating the entire embedding table to clients and greatly reduces client computation.
Though mixed FL can clearly be useful, an actual process to minimize f is not trivial. FL requires that clients' data stay device, they contain private information that possibly reveals personal identity. Moreover, centralized loss/data is expected to differ significantly from client loss/data.
Contributions
We motivate the mixed FL problem and present three algorithms for addressing it: PARALLEL TRAINING (PT), 1-WAY GRADIENT TRANSFER (1-w GT), and 2-WAY GRADIENT TRANSFER (2-w GT). These algorithms maintain the data privacy protections inherent in FL.. [Section]] 2
We experiment with facial attribute classification and language modeling, demonstrating that our algorithms overcome distribution shift. We match the accuracy of hypothetical 'oracle' scenarios where the entire inference distribution was colocated for training. [Section 4
We experiment with user-embedding based movie recommendation, reducing communication overhead by 93.9% and client computation by 99.9% with no degradation in quality. [Section
We state convergence bounds for each algorithm (in strongly, general, and non-convex settings), providing theoretical explanations for convergence behaviors we observe in the experiments. This indicates how the algorithms will perform mixed FL tasks. [Section 5
2 ALGORIHTMM
In FL., the loss function fi is an average of client loss functions f. The client loss fi is an expectation over batches of data examples B; on client
fi(x)) 1
N Σ f(()), f((x)= Eg, [f((;;; B.)
FEDAVG (McMahan et al. 2017) is a ubiquitous, hcuristic FL method designed to minimize Equation 2 w.r.t. model in manner that allows all client data (B3)) to remain at respective clients i. Providing strong privacy protection is a major motivation for FL. Storing raw data locally on clients rather than replicating it servers decreases the attack surface of the system. Also, using focused ephemeral updates and early aggregation follows principles of data minimization (White House Report 2013
While training with loss Jr via FEDAVG can yield effective model æ. this paper shows there scenarios where 'mixing' in an additional 'centralized" loss fe proves beneficial to the training of æ. Such loss term can make use of batches of centralized data examples B,, from datacenter dataset:
fc(x) Es, [f BB)
(3)
A Weee they not differ, could centralized compute node as an additional client in standard FI., and simply make use of an established FI. algorithm like FEDAVG for training æ.
*Even stronger privacy properties are possible when is combined with technologies such differential privacy (DP) and secure multiparty computation (SMPC) (Wagg et al. 2027.
2

---

Under review as a conference paper at ICLR 2023
The centralized loss fe will differ from the federated loss fr (else it would not be useful). This can be
a difference in the distributions that B3 and B, are drawn from, and/or in the functional forms of fo and ft. We will present an expression that quantifies the difference between fo and fi in Section 5
We now state our mixed FL algorithms (Algorithms D and 2 Appendix has a few practical details.
PARALLEL TRAINING performs round of FEDAVG (minimizing fi) in parallel with steps of centralized training (minimizing fo), merges (e.g., averages) the respective updates, and repeats. Green in Algorithm
I lindicates added steps beyond FEDAVG for PARALLEL TRAINING.
1-WAY GRADIENT TRANSFER starts a round by calculating a gradient of fc- It sent to participating clients and summed with clients' gradients of fi during client optimization. Blue in Algorithm 2 indiiaaes added steps beyond FEDAVG for 1-WAY GRADIENT TRANSFER.
2-WAY GRADIENT TRANSFER is PARALLEL TRAINING with gradient sharing. Two gradients are now used, one based on fo and sent clients (like 1-w GT). one based on fr and applied centrally. Purple in Algorithm
D is added steps beyond PT for 2- 2-WAY GRADIENT TRANSFER.
Algorithm 1: PARALLEL TRAINING and 2-WAY GRADIENT TRANSFER
(FEDAVG with added steps for PARALLEL TRAINING and further steps for 2- WAY GRADIENT TRANSFER)
Input: Initial model (0);; CLIENTÖPTMIZERR SERVEROPTIMIZER, CENTRALOFTINIZER, MERGEOFTIMIZER with respective
learning 11, 1b. Thst central loss function fe initial sugmenting centralizeedfooderteed gradients, o 9r
(0) (zcroed)
for e {0, ..... T
1} do
Initialize central model (t.00) = ax())
for central step .,..., K. do
Sumple centralized batch compute stochastic gradient (n. (,,k),6))8)) ())) of fa(a((t)))
Perform central update an! (1) CENTRALOPTIMZESR(" (1.,k.) (aff (1,8) B,(()) > .).
Compute contral model dolta A = x! ((.) (1)
Sample subset g(t) of clients; for client E g(t) in parallel do ( Pj CLIENTUPDATE (*) o HENTOPTMMZERR v).
Aggregate client changes (4) Eicsti) PiA!!) / Exc((t) pi
Compute federated model m (1) SERVEROFTMIZAA( -A0 (..)
Compute federated model delta A mn (2)
Aggregate central model federated model A (t) A(t)) A
Update global model a (1++)) MFAGROPTTMIZER (1)) (1) -aa
Update augmenting centralized gradient o. (1-1)
A." (() (1)
Update augmenting federated gradient 0) ((-1) Eies(e) 4/90(nn Exes() K;) - g (see Appondis
CLIENTUPDATE:
Input: Initial client model (2.10) (1.0), (pussible) augmenting gradient O CLIENTOPTIMIEER, learning vy round 4; client loss f.
Initialize client weight p; =0
for client step O K,
Sample batch (()); compute stochastic gradient gi (ar (4,), (())) ) fa fo
(f+5) updatte client weight p: ps + (18(+)
Perform client update (c,++1) CLIETÖPTIMIZER( (1.A) (rr () ((())) 359) .).t)
Compute client changes (4) (t.))) m! (L.0) and return a. (9) Pp
Algorithm 2: 1-WAY GRADIENT TRANSFER (FEDAvG (MeMahan et al. 2017) with added steps)
Input: Initial model a (0) CLIENTÖPTIIIDRR SERVEROPTIMIZIR with respective learning rates 1). nis contral loss function f for (0,1,.... Sample butch 88() compute stochastic gradient g.(w (0; ((C) fa (t)
()) set augmentngg gradient g! g. (0) (())
Sample a subset (()) clients: client i E S(G parallel do
A/4 (4) P. CLIENTUPDATE (1), 700) CLIENTOPTMMIERR v) (CLIENTUPDATE, fuinnniiooTT.funciioon function defined in Algoridhm
Aggregate client changes A (t) Eies(h p.A(0)/5
/ Exes(i) Ps Update global model a (t++1) = SURVIROPTIMIRDR( (00 (h.
3 RELATED WORK
There are parallels between GRADIENT TRANSFER and algorithms addressing inter-client data heterogeneity in FL. like SCAFFOLD (Kariiiredyy et al. 2020b) or Mime (Karimireddy et al. 2020a). Those algorithms calculate a gradient reflective of the entire federated population and transmit it to clients to reduce update variance, improving optimization on non-IID client data. GRADIENT TR TRANSFER calculates gradient reflective of centralized data/loss, to augment client computations
3

---

Under review as a conference paper at ICLR 2023
of decentralized data/loss (in 2-w GT, also the converse). However, SCAFFOLD requires keeping state at the server (control variates) for each participating client, impractical in real large-scale FL systems (Kairouz et al., 2019). 2-w GT only requires state (augmenting gradients) for two entities, and so is easily implemented.
Another instance of non-IID client approach (Zhao al., 2018 influencing mixed FL is the EXAMPLE TRANSFER algorithm (Anonymous) a). Here, centralized examples are sent to federated clients, instead of gradients. This is typically precluded in real FL applications. The data volume needed to transfer may be excessive, and in general EXAMPLE TRANSFER does not offer solutions for one of the main motivations of this work, reducing client computation and communication.
'Transfer learning' also involves two different training datasets, but has different purpose. Transfer learning pretrains a model on distribution (c.g., centralized data in a datacenter), then fine-tunes it on the actual distribution of interest (e.g., decentralized data via FL). It is desirable as a way to quickly train on the latter distribution (e.g., as in Ro et al. (2022)) But its sequential approach results in catastrophic forgget (McCloskey & Cohen 1989 Ratcliff 1990; French) [999); accuracy on pretraining data is lost as the model learns to fit fine-tuning data instead. mixed FL, we desire good inference performance on all data distributions trained on. See Appendix B.4.5 for more.
In differentially private (DP) optimization, a line of work has aimed to improve privacy/utility tradeoff's by utilizing additional non-private data. One way is use non-private data to pretrain (Abadi et al. 2016). Another avenue is to use non non-private data to learn the gradient geometry (Zhou
et al. 2020 Amid al. 2021: Asi al. 2021: Kairouz al., 2021a Li al., 2022), , improving accuracy by enabling tighter, non-isotropic gradient noise during DP optimization. Amid et al.) (2021) and Li al. (2022) consider the FL use case As in transfer learning, additional data is used only to
improve performance on single distribution, and retaining accuracy on other distributions is non- goal (in contrast to mixed FL). Also, the non-private data used generally matching (in distribution) to the private data, whereas in mixed FL we typically explicitly leverage distinct distributions.
few recent works (Yu al. 2020: Elbir al. 2021; Jeong al. 2021) present instances of mixed FL problems; they shift computations to the server that are intensive or impossible at the clients. These works do not address distribution shift or present more general mixed FL algorithms.
4 EXPERIMENTS
We now present experiments on three tasks (Table showing a range of problems for which mixed FL is useful. They also show the comparative performance of each algorithm described in Section 2
Table 1: Experiments summary. For training byperparameters and further details, see Appendix B
SMILE CLASSIFICATION
LANGUAGE MODELING
MOVIE RECOMMEND.
MODEL ARCH. TYPE
RNN
DUAL ENCODER
FEDERATED DATA
CELEBA (SMILING)
STACK OVERELOW CATEGORICAL C.E. 0.75
MOVIBLENS
FED. CLIENT LOSS (f+)
BINARY C.E. 0.5
HINGE
FED. WEIGHT (wx)
0.5
CENTRALIZED DATA
CELEBA (NON-SMILING)
WIKIPEDIA
CENT. Loss (fe) CENT. WEIGHT (w))
BINARY C.E.
CATEGORICAL C.E.
SPREADOUT (REG.)
0.5
0.25
0.5
4.1 ADDRESS LABEL IMBALANCE IN TRAIN DATA (SMILE CLASSIFIER; CELEBA)
Earlier work (nnnyymous motivated mixed FL with the example problem of training 'smiling'- vs.- - "s-'mmnmilingg classifier via FL with mobile phones, with the challenge that the phones' camera application (by the nature of its usage) tends to only persist images of smiling faces. A solution
An interesting similarity between PDA-DPMD (Amid et al. 2021) and our work: in first order approximation of mirror descent is used, where the server model update is calculated weighted sum of private (federateed and public loss terms, just as in PARALLLEI. TRAINING or 2-WAY GRADIENT TRANSFER.
for FL,
4

---

Under review as a conference paper at ICLR 2023
.65
90
.60
.85
(oracle)
2-way GT (only FL)
(oracle)
1-way
2-way GT
1-way GT
1000
2000
3000
4
1030
2000
3000
4000
(a) Smile Classifier: Eval. AUC (ROC) Round.
(b) Language Model: Evaluation Accuracy Round.
Figure 1: Mixed FL resolves distribution shift, enabling accuracy equal to if data were colocated and centrally trained ('oracle"). The smile classifier reaches an oracle's evaluation AUC of ROC of over 0.95. The language model reaches an oracle's evaluation accuracy of over 0.66. Evaluation is over all data (i.e., smiling and non-smiling faces; Stack Overflow and Wikipedia). Plots show 95% conf.
0.7
1.6
(oracle)
1-way GT
0.6
PT
2-way GT
(oaacle)
2-way GT (only FL)
PT
1 1-way GT
2000
3000
(a) Smile Classifier: Eval. Loss Round.
(b) Language Model: Eval. Loss Round.
Figure 2: Comparative convergence differs; (a) shows PT converging worse than 1-w GT or 2-W GT, while (b) shows all algorithms converging the same. See Section 5.3 for theoretical explanation.
for this severe label imbalance is to apply mixed FL, utilizing an additional datacenter dataset of unsmiling faces to train capable classifier. To experiment, CelebA date d al. 2015 Caldas
et al. 2018) is split into federated 'smiling' dataset and centralized 'unsmiling' dataset.
Figures Th and 22 show the AUC and loss convergence of our three algorithms when applied to this problem. Empirically, we observe GRADIENT TRANSFER converge faster than PARALLEL TRAINING. Section will provide a theoretical explanation for this behavior.
4.2 MITIGATE BIAS IN TRAIN DATA (LANGUAGE MODEL; STACK OVERFLOW, WIKIPEDIA)
Consider the problem of learning a language model like a RNN-based next character prediction model, used make typing suggestions to user in a mobile keyboard application. Because the ultimate inference application is on mobile phones, it is natural to train this model via FL., leveraging cached SMS text content highly reflective of inference time usage (at least for some users).
However, the mobile phones participating in the federated learning of the model might be only subset of the mobile phones for which we desire deploy for inference. Higher-end mobile phones can disproportionately participate in FL, as their larger memory and faster processors allow them to complete client training faster. But do well at inference, a model should make accurate predictions for users of lower-end phones as well. A purely FL approach can do an inadequate job of learning these users' usage patterns. (See Kairouz et al. (009) for more on aspects of fairness and bias in FI..)
Mixed FL. overcomes this problem, by training model jointly on federated data (representative of users of higher-end phones) and a datacenter dataset (representative of users of lower-end phones). We simulate this scenario using two large public datasets: the Stack Overflow datase ? (Kaggle) for federated data, and the Wikipedia [ (Wikimedia Foundation) for datacenter data. Figure Ip shows results. The 'only FL' scenario leams Stack Overflow (but not Wikipedia) patterns of character usage, and so has reduced accuracy (~~ 0.60) when evaluated on examples from both datasets. The
"CelebA federated data available via open source FL. software TFF CclebA documentation 2022
"Stack Overflow federated data available via open source (TFF StackOverflow documentation "Wikipedia data available via open source TFDS Wikipedia (20201201.cm documentation
2022
2022
5

---

Under review as a conference paper at ICLR 2023
Table 2: Movie recommendation: computation
(COMP.) and communication (COMM.) overhead per client. The baseline scenario computes every- thing clients. See Appendix B.3 for analysis.
10.8
baseline
1-way GT
10.4 PT
2-way GT
10.0
COMP. (MFLOP)
COMM. (KB)
1000
1500
BASELINE PT
125.16
494
Figure 3: Movie prediction, Eval. Loss vs. Round. We see that mixed FL results in similar loss as the more expensive baseline scenario (see Table 2
0.025
20
I-w GT
0.025
30
2-W GT
0.025
30
mixed FL algorithms demonstrate learning both: they all achieve an evaluation accuracy (~ 0.66)
comparable to an imagined 'oracle' that could centrally train on the combination of datasets.
Unlike the smile classification experiment, here PARALLEI TRAINING converges about as fast as GRADIENT TRANSFER. SectionS]wi will provide a theoretical explanation for this behavior.
4.3 REGULARIZE EMBEDDINGS AT SERVER (MOVIE RECOMMENDATION, MOVIELENS)
The third task we study, movie recommendation,
one with an embedding regularization term as described in Section [ As Table [ shows, a key difference from the previous two mixed FL experimental scenarios is that here we are mixing losses with different functional forms (instead of mixing different datacenter and federated data distributions). We study this scenario by training dual encoder representation learning model (Covington al. 2016) for next movie prediction on the
MovieLens dataset (Harper & Konstan 2015: GroupLens).
As described Section limited negative examples can degrade representation learning performance. Previous work (Anonymous) b) proposed using losses insensitive to local client negatives to improve federated model performance. They observed significantly improved performance by using a two-part loss: (1) hinge loss to pull embeddings for similar movies together, and (2) spreadout regularization (Zhang et al. 2017) to push embeddings for unrelated movies apart. For clients to calculate (2), the server must communicate all movie embeddings to each client, and clients must perform matrix multiplication over the entire embedding table. This introduces enormous computation and communication overhead when the number of movies large.
Mixed FL can alleviate this communication and computation overhead. Instead of computing both loss terms on clients, clients calculate only the hinge loss and the server calculates the expensive regularization, avoiding costly computation on each client. Also, computing the hinge loss only requires the embeddings of movies client's local dataset. Federated select (Charles al. (022) enables only those embeddings to be sent to that client, saving communication and on-client memory.
Experiments show all mixed FL algorithms achieve model performance (around comparable to the baseline scenario where everything is computed on the clients. Moreover, mixed FL eliminates more than 99.9% of client computation and more than 93.9% of communication (see Table 2). For computation and communication analysis, Appendix [ Note that real-world models can be much larger than this movie recommendation mode 9 Without mixed FL., communicating such large models to clients and computing regularization would be impractical in large-scale settings. PARALLEL TRAINING converges slightly slower than either GRADIENT TRANSFER algorithm (Figure but reaches the same evaluation loss around 1500 rounds.
recall 10)
CONVERGENCE
5.1
PRELIMINARIES
We now describe convergence properties for each mixed FL algorithm from Section 2 We assume mixed loss f has a finite minimizer (i.e., 3 xx s.t. f(x) 2 f(x") x).. We assume client losses fi
F.gg. g., for URL prediction task with millions of URLs the embedding table size can reach gigahytes.

---

Under review as a conference paper at ICLR 2023
and centralized loss are B-smooth. If fi are 3-smooth, federated loss fi is also For some results. we assume ft and fo are p-convex (possibly strongly convex, μ > 0). If fi are p-convex, fi is alsd
f() to denote the full gradient of fa (i.c., over all data on client of t). Similarly, fi(=) and V (()) denote full gradients of ft and fc at æ. We use 9: (z) to denote
For parameter vector
an unbiased stochastic gradient of fi. calculated
random batch B, of examples
client i.
We focus on the impact to convergence when differences exist between the federated and centralized losses/data. As such, we make the following homogeneity assumption about the federated data, which simplifies the analysis and brings out the key differences. Our analysis can be easily extended to heterogeneous clients by assuming bound variance of the client gradients.
Assumption 5.1. The federated clients have homogeneous data distributions (i.e., with examples that are drawn IID from a common data distribution), and their stochastic gradients have bounded variance. Specifically, for some 0, we have for all clients i and parameter vectors a::
E [x)) = V f((x), E (1)
f((x))l & o².
(4)
Under such conditions, FEDAVG convergence can match SGD (Table 2, Karimireddy et al. (2020b))
Let Or denote unbiased stochastic gradient of federated loss ft. formed by randomly sampling a cohort of S (out of N total) clients, randomly sampling a batch B, of client data examples, and averaging the respective client stochastic gradients. Given Assumption 5.
we bound variance of gri
gr(x))
1 (a),, B [lg((())) S
Vf(()) E
11 IES
(.( - Vi((a)
1 S 502 (5)
Let (x) denote a stochastic gradient of the centralized loss fe at æ, calculated on a randomly sampled batch B& of centralized examples (from a datacenter dataset), with variance bounded by of:
E llg. (a) fc())) s o.
66)
Summarizing Equations 4 a client's stochastic gradient (:()) has variance bounded by o2, the federated cohort's stochastic gradient gr(xz) has variance bounded by o²/s, and the centralized stochastic gradient gx(x) has variance bounded by o². Increasing client batch size [.] reduces variance of gi (ax) and g+(x), increasing cohort size S reduces variance of gr(x), and increasing central batch size [B,] reduces variance of gx
Note that ' only bounds variance within the federated data distribution, and o only bounds variance within the central data distribution. To say something about variance across the two data distributions, we adapt the notion of 'bounded gradient dissimilarity' (or 'BGD') introduced in Karimireddy et al. (2020b) (Definition A1), and apply it to the mixed FI. scenario here.
Definition 5.2 (mixed FL B))GD), There exist constants G 2 0 and B > such that Væ:
V
fi( +
V(((#)
G2
+ B² [V](2)]1
Wr
we
W/
We
In the definition, my and w. are proportions of influence (wy+ w. 1) of the federated and centralized objectives on the overall mixed optimization. (The simplest setting is wy we 1/2.)
5.2
BOUNDS
We can now state upper bounds on convergence (to an error in mixed loss smaller than e) for the respec- tive mixed FL. algorithms. For ease of comparison, the convergence bounds are summarized in Table
3 The Theorems and Proofs of these convergence bounds are given in Appendix C As mentioned
By its definition in Equation 2 combined with the triangle incquality.
By its definition in Equation it convex combination fi-
12 Note: V f((=)) is useful for theoretical convergence analysis, but cannot he practically computed in real cross-device Fl. setting. In contrast, f(()) can be computed.
7

---

Under review as a conference paper at ICLR 2023
Table 3: Order of number of rounds required be within of optimal mixed loss, for different mixing
strategies. See Appendix C o² as in ( of as in (6. G and B as in Def. 5.2 with = W. = 1/2. B smoothness (Def. [.I). ja is convexity bound (Def. D.4). K client local steps taken (2 2). is
client cohort size (per round). D and F are initial distances/loss emrors, described in Appendix C
PARALLEI TRAINING
1-w GT
2-W GT
R-CONVEX
(x2+50))
KSue + GvB (a D
+ B'8 log(
(a² K
+ 2 (og(())
[a (
KSue + log(
uve
KSpe
GvB B
(o o
DDa
(o (o"+S0")
KSe + DD
CONVEX
KSe (o² (o²+ K82
KSe
GVB
+ B²BF
(o Ko²)K
BF
(6 +80
+ OF
NONCONVEX
KS2
KSc
previously, the analysis extends in straightforward manner the setting of heterogeneous clients assuming a bound on the variance of client gradients: for all æ. E> [V/[(a)) - [((()))] x of for some of 2 O. Under this assumption, the bounds in Table 3 change by an additional Kož term in the expression involving o² and of in the parenthesis the numerator of the leading term. The derivation of these more general bounds follows on the same lines, so we omit it for brevity.
Analyzing Table 3 there are several implications to be drawn.
Significant (G,D)-BGD impedes PARALLEL TRAINING The convergence bounds for PARAL-
LEL TRAINING show a dependence on the G and parameters from Definition 5.2, If mixed FL problem involves large amount of dissimilarity between the federated and centralized gradients (i.e., G > B > 1), then PARALLEL TRAINING will be slower to converge than alternatives.
Significant of impedes 1-WAY GRADIENT TRANSFER 1-WAY GRADIENT TRANSFER is more sensitive to central variance o?- Unlike the other algorithms, the impact of o² on convergence scales with the number of steps K. 1-WAY GRADIENT TRANSFER requires central batch size |B,] that is K times larger to achieve the same impact on convergence. Intuitively, this makes sense; in a round, PARALLEL TRAINING and 2-WAY GRADIENT TRANSFER sample K fresh batches during centralized optimization, while 1-WAY GRADIENT TRANSFER only samples a single central batch.
2-WAY GRADIENT TRANSFER should always converge at least as well as others The conver- gence bound for 2-WAY GRADIENT TRANSFER is unaffected by gradient dissimilarity (i.e., G >>>>> 0 or B > 1), unlike PARALLEL TRAINING. Also, the bound for 2-WAY GRADIENT TRANSFER is less sensitive to of than the bound for 1-WAY GRADIENT TRANSFER (as described above).
5.3 ANALYSIS OF EXPERIMENTS
PARALLEL TRAINING has a convergence bound substantially different than the GRADIENT TRANS- FER algorithms; the dependence on the BGD parameters and B indicates there are mixed FL problems where PARALIEEI. TRAINING is slower to converge than GRADIENT TRANSFER (in either form). How can we know if a particular problem is one where PARALLEL TRAINING will have slower convergence? It would be useful to know G and B, but they cannot be exactly measured. G and B (Definition 5.2) are upper bounds holding Yz, and the entire space of x cannot realistically be empirically estimate these upper bounds.
checked. Instead, introduce sampled approximations
Let (+) be the global model at start of round t. Let fic. Vos. V be approximations of federated, centralized, total gradients round t. Considering Definition 5.2 we define Ge sampled
approximation of G assuming B 1, and B, as a sampled approximation of B assuming G 0:
Σ (
V V=== =.(aa"))
Vl. = J,l. =
+ V
V
3
= &F
1
1
المرار
-
الللة
B =
1
V
virl'' |
+ 1
| (") /
km
8

---

Under review as a conference paper at ICLR 2023
Table 4: Sampled approximations of (G.B)-BGD. (See Appendix B.1 for details.)
SMILE CLASSIFICATION LANGUAGE MODELING
MOVIE RECOMMEND.
max1ogeg100 Of 49.04
0.03
0.03
maX1ogeg100 B? 1.26
1.34
1.50
Table states maximums of C2 and B3 for the experiments of Section 4 This provides some theoretical explanation for empirical observations made during the experiments.
Smile Classification (4.1) As discussed, PARALLEL TRAINING is at disadvantage when G >> or B >> 1, and Table 4 (left column) shows that G, is significantly large in smile classification. This aligns with our empirical observation Figure 2 PARALLEL TRAINING converging slower than either GRADIENT TRANSFER algorithm.
Language Modeling (4.2) Table 4 (center column) shows language modeling with more trivial gradient dissimilarity: G2 and B, 1. PARALLEL TRAINING should be competitive. Figure 2p empirically confirms this to be true; all algorithms converge roughly equivalently.
CONCLUSION
This paper has introduced mixed FL, including motivation, algorithms and their convergence proper- ties, and intuition for when a given algorithm will be useful for a given problem. Our experiments indicate mixed FL can improve accuracy and reduce communication and computation across tasks.
This work focused on jointly learning from a single decentralized client population and a centralized entity, as illuminates the key aspects of the mixed FL problem. Note that mixed FL and the associated properties we define in this paper (like mixed FI. (G, B)-BGD) are easily expanded to work with multiple (> 1) distinct client populations participating. E.g., population of mobile phones and a separate population of smart speakers, mobile phones separated into populations with distinct capabilities/usage (high-end vs. low-end, or by country/language) Also, there need not be a centralized entity; mixing can be solely between distinct federated datasets.
interesting to reflect on the bounds of Table 3 and what they indicate about the benefits of separating single decentralized client population into multiple populations for mixed FL purposes. The bounds are in terms of o² (representing within population 'variability') and and B (representing cross-population 'variability'). Splitting population based traits will likely decrease a² (each population is now more homogeneous) but introduce or increase G and B (populations are now distinctive). This might indicate scenarios where GRADIENT TRANSFER methods (only bounded by o²) become more useful and PARALLEL TRAINING (also bound by G and B)) becomes less useful.
The limits of our convergence bounds should be noted. First, they are 'loose': practical performance in particular algorithmic scenarios could be better, and thus comparisons between algorithms could differ. Second, our bounds assume IID federated data, which is invalid in practice; convergence properties differ on non-IID data. While our analysis, extended to handle non-lID data, shows that the bounds do not materially change,
still a place where theory and practice slightly diverge.
It is important to note that mixed FL is orthogonal to the choice of algorithm for federated training. For simplicity, this paper described mixed FL with FEDAVG used for federated training. However, one could use DV-FedAvg (McMahan et al. (2018)) or DP-FTRI. (Kairouz et al. (2021b)) with mixed FI. to ensure that DP protections are applied to the federated data. Similarly, an adaptive SERVEROPTIMIZER like FEDADAM (Reddi et al. 2020) could be used in the federated portion of training (preliminary mixed FL results with FEDADAM are given in Appendix [B.4.4].
In principle, mixed FL techniques expected to have positive societal impacts insofar as they further develop the toolkit for FL (which has security and privacy benefits to users) and improve accuracy on final inference distributions. Also, we've shown (Section 4.2) how mixed FL can address participation biases that arise in FL. However, the addition of server- based data to federated optimization raises the possibility that biases in large public corpora find their way into applications of FL..

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In 23rd ACM Conference on Computer and Communications Security (ACM CCS), 2016.
Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song. Thomas Steinke, Vinith Suriyakumar, Om Thakkar, and Abhradcep Thakurta. Public data-assisted mirror descent for private model training. arXiv preprint arXiv:21 2021.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping, Advances in Neural Information Processing Systems, 34:17455 17466, 2021.
Anonymous.
Anonymized for iclr submission review., a.
Anonymous. Anonymized for iclr submission review., b.
Apple. Designing for privacy (video and slide deck). Apple WWDC, https::
apple. httpl//eecc///teeee///aaa///////
2019.
Hilal Asi. John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In International Conference on Machine Learning, pp. 383-392. PMLR, 2021.
Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint 1rXiv:1812.010%%
2018.
Zachary Charles, Kallista Bonawitz, Stanislav Chiknavaryan, Brendan McMahan, et al. Federated select: A primitive for communication and memory-efficienn federated learning. arXiv preprint wrXi::2208.09432 2022.
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In Proceedings of the 10th ACM conference on recommender systems, pp. 191-198, 2016.
Ahmet M Elbir, Sinem Coleri, and Kumar Vijay Mishra. Hybrid federated and centralized learning. In 202/ 29th European Signal Processing Conference (EUSIPCO), pp. 1541-1545. IEEE, 2021.
Robert French. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences, 3: 128-135, 05 1999. doi: 10. 1el.111661166444 166136611611119999992222
GroupLens.
Movielens
1m dataset.
URL httpps//grroppleess.rrr/ggttaee
movielens/Im/
Andrew Hard, Kanishka Rao, Rajiv Mathews, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv: /8/ 1.36004 2018.
Andrew Hard, Kurt Partridge. Neng Chen, Sean Augenstein, Aishanee Shah, Hyun Jin Park, Alex Park. Sara Ng. Jessica Nguyen, Ignacio Lopez Moreno, et al. Production federated keyword spotting via distillation, filtering, and joint federated-centralliedd training. arXiv preprint TrXiv:220400622. 2022.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (täs), 5(4):1-19, 2015.
Florian Hartmann. Predicting text selections with federated leariing, Google Al Blog https: /ai
gpogleblee httpa//w...........e.eeeeeaaaaaa
html 2021.
Wonyong Jeong, Jaehong Yoon, Eunho Yang, and Sung Ju Hwang. Federated semi-supereised learning with inter-client consistency & disjoint learning. In International Conference Learning Representations (ICLR) 2021. International Conference on Learning Representations (ICLR), 2021.
10

---

Under review as a conference paper at ICLR 2023
Kaggle.
Stack overflow
data.
URL https://www. httpss//ww...aglle..c///daaaaaaa
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. arXiv preprini
2019.
Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (nearly) dimension independent private erm with adagrad rates
via publicly estimated subspaces. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning mlr
Research, pp. 2717-2746. PMLR, 15-19 Aug 2021a. URL
press/v1 v1h//v134//66 rouz21a html
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling shuffling. In International Conference on Machine Learning, pp. 5213-5225, PMLR, 2021b.
Sai Pranecth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03600 2020a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. International Conference on Machine Learning (ICML), 2020b.
Tian Li, Manzil Zaheer, Sashank J Reddi, and Virginia Smith. Private adaptive optimization with side information. arXiv preprint arXiv:2202.0544 2022.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Michael McCloskey and Neal J. Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. Psychology of Learning and Motivation, 24:109-16: 165, 1989.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efiinn learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1273-1282, 2017. Initial version posted arXiv in February 2016.
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations (ICLR), 2018.
Nicole Mitchell, Johannes Ballé, Zachary Charles, and Jakub Konečný. Optimizing the communication-accuracyy trade-off federated learning with rate-distortion theory. arXiv preprint vwXiv:2201.02664 2022.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03746. 2018.
Swaroop Ramaswamy, Rajiv Mathews, Kanishka Rao, and Françoise Beaufays. Federated learning for emoji prediction mobile keyboard. arXiv preprint arXiv: 19kiv:99000000 04329, 2019.
Swaroop Ramaswamy, Om Thakkar, Rajiv Mathews, Galen Andrew, H. Brendan McMahan, and Françoise Beaufays. Training production language models without memorizing user data. arXiv preprint arXiv:2009. 10031, 2020.
Roger Ratcliff. Connectionist models of recognition memory: constraints imposed by learning and forgetting functions. Psychological review, 97 2:285-308, 1990.
Sashank Reddi, Zachary Charles, Manzil Zaheer. Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.0m 00295. 2020.
11

---

Under review as a conference paper at ICLR 2023
Jae Hun Ro, Theresa Breiner, Lara McConnaughey, Mingqing Chen, Ananda Theertha Suresh, Shankar Kumar, and Rajiv Mathews. Scaling language model size in cross-device federated learning. In ACL 2022 Workshop Federated Learning for Natural Language Processing, 2022.
URL hhtt:s:://ppnrevveeeet net net/fonee/ootooo forum? d=ShNG2 SEEESNNNGGG-GG-- 9KGF-C)
Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint arXiv:1907.04232, 2019.
TFDS Wikipedia (20201201.en) documentation. Tensorflow datasets (tfds) wilpplidddddddddodduddddaataiiia 2022. URL
wikipedaa22211201er http:///w///.ttoooooooooooooatts
TFF CelebA documentation. [ff.shaaaaariooooottttteeeeeeeed umentation, 2022. http:///ss.waaaaaaoorooooooooo/a ortp:://ffffiiiaaaoooaaaaaaaaaad
doc-
TFF StackOverflow htt.://m............ooooooooooa.
data data
documentation, 2022. URL /ttp:////////////aoooo//////////
Jianyu Wang. Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Agüera y Arcas, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, et al. A field guide to federated optimization. arXiv preprint arXiv:2107.06917 2021.
White House Report. Consumer data privacy in networked world: A framework for protect- ing privacy and promoting innovation in the global digital economy. Journal of Privacy and Confidentiality, 2013.
Wikimedia Foundation. Wikimedia downloads. URL http://ddumms.iiiiieeiia.a..aa..
Felix Yu, Ankit Singh Rawat, Aditya Krishna Menon, and Sanjiv Kumar. Federated learning with only positive labels. 2020.
Xu Zhang, Felix X Yu, Sanjiv Kumar, and Shih-Fu Chang. Learning spread-out local feature descriptors. In Proceedings of the IEEE international conference on computer vision, pp. 4595- 4603, 2017.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated 2018.
learning with non-iid data. arXiv preprint
Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. arXiv preprint arXiv:2007.03811, 2020.
12

---

Under review as a conference paper at ICLR 2023
A PRACTICAL IMPLEMENTATION DETAILS
A.1 DOWNLOAD SIZE
GRADIENT TRANSFER (either 1-WAY 2- 2-WAY) requires sending additional data part of the communication from server to clients at the start of federated round. Apart from the usual model checkpoint weights, with GRADIENT TRANSFER we must now also transmit "augmenting" gradients of the model weights w.r.t centralized data as well. Naively, this doubles the download size as the gradient is the same size as the model. However, the augmenting gradients should be amenable to compression, e.g. using an approach such as Mitchell et al. (2022).
A.2 UPLOAD SIZE
With PARALLEL TRAINING and 1- 1-WAY GRADIENT TRANSFER, no client gradient information is used outside of the clients themselves, so there is no additional information (apart from the model deltas and aggregation weights) to upload to the server. With 2- 2-WAY GRADIENT TRANSFER, client gradient information is used in centralized training, needs to be conveyed to the server somehow.
When the FL client optimization is SGD, the average client gradient in a round (over all clients participating, over all steps) can be determined from the model deltas and aggregation weights that are already being sent back to the server, meaning no additional upload bandwidth necessary. Apart from bandwidth considerations, this also means there is additional vector for private data leakage. The algorithm to do this is as follows.
Each client transmits to the server local model change A and an aggregation weight p; that is related to number steps taken K,. The average total gradient applied at client during round t is:
g0 = nk₁
(8)
The average client gradient (i.e., w.r.t. just client data) at client is:
1 K
10 - -9!0
(9)
where g. is the augmenting centralized gradient that was calculated from centralized data and used round l. The average (across the cohort) of average client gradients, weighted by K4, is:
1 K.
(4) Σ A ge
g
(10)
KG
This average client gradient (() is in the spirit of SCAFFOLD Karimireddy et al. 2020b) Equation 4, Option II. It will be used as the augmenting federated gradient of (1+1)) in the subsequent round t L, to augment centralized optimization. See Algorithm
A.3 DEBUGGING AND HYPERPARAMETER INTUITION VIA K=1
As these algorithms each involve different hyperparameters. validating that software implementa- tions" are behaving as expected is non-trivial. Something that proved useful for debugging purposes, as well as provided practical experience in understanding equivalences between the algorithms, was to perform test cases with the number of local steps K set to algorithms are effectively identical and should make equivalent progress during training.
this setting, the three mixed FL.
Note that the convergence bounds Table hoold for K 2 2, so this takes us outside the operating regime where the bounds predict performance. It also takes us outside an operating regime that is typically useful (FL use cases generally find multiple steps per round to be beneficial). But does serve purpose when debugging.
An open-source mixed FL. code repository will he shared with the public version of the paper.
13

---

Under review as a conference paper at ICLR 2023
2.0
Smile Classification
1.8
Language Modeling
10
Smile Classification
1.6
Movie Recommend.
Language Modeling
10
Movie Recommend.
10-3
10-2
40
100
60
G2 Round
(b) B2
Round
Figure 4: Sampled approximations of mixed FI. (G, B)-BGD, for the three experiments in Section
B EXPERIMENTS: ADDITIONAL INFORMATION AND RESULTS
B.1 G. AND BG METRICS PLOTS
Table iis an informative comparison of the mixed FL optimization landscape of the three respective experiments conducted in Section 4 It includes maximum values for the metrics G2 and Bg (the sampled approximations of the parameters defined in (G, B)-BGD (Definition 5.2). Here we provide some additional information.
Figure plots these sampled approximation metrics over the first 100 rounds of training. We ran simulations per experiment and took the maximum at each round across simulations. We used the same hyperparameters as described below (in Subsection B except taking only a single step per round (K 1).
B.2 ADDITIONAL DETAILS FOR EXPERIMENTS IN SECTION
General Notes on Hyperparameter Selection For the various experiments in Section we empirically determined good hyperparameter settings (as documented in Tables 50) Our general approach for each task was to leave server learning rate 7), 1, select number of steps K that made the most use of the examples in each client's cache, and then do a sweep of client learning rates 1) to determine setting that was fast but didn't 't diverge. For PARALLEL TRAINING and 2- B-WAY GRADIENT TRANSFER, which involve central optimization and merging, rate 7m to be I, and set the central learning rate 7) as the product of client and server learning rates: 77 7777s (and since 17s 1, this meant client and central learning rates were equal).
set the merging learning
General Notes Comparing Algorithms We generally kept hyperparameters equivalent when comparing the algorithms. For example, we aimed to set batch sizes for all algorithms such that central and client gradient variances a² and a have equivalent impact on convergence (meaning [B&]| = B for PT and 2-w GT, and [B& = KSJB, for 1-w GT). In the case of language model training with 1-WAY GRADIENT TRANSFER, following this rubric would have meant central batch size [3, of 12800; we reduced this in half for practical computation reasons. For a given task, we also generally kept learning rates the same for all algorithms. Interestingly, we observed that as (and %e if applicable) is increased for given task, the 2- 2-WAY GRADIENT TRANSFER algorithm is the first of the three to diverge, and so we had to adjust, e.g., in the language modeling experiment we used lower 7) for 2-W GT than for PT and 1- GT.
B.2.1 CELEBA SMILE CLASSIFICATION
Datasets The CelebA federated dataset consists of 9,343 raw clients, which can be broken into train/evaluation splits of 8,408/935 clients, respectively (TFF CelebA documentation 2022). The raw clients have average cache size of ~ 21 face images. The images are about equally split between smiling and unsmiling faces. In order enlarge cache size, group three raw clients together into one composite client, so our federated training data involves 2,802 clients with caches of (on average) 63 face images (and about half that when limit the clients to only have smiling faces).
14

---

Under review as a conference paper at ICLR 2023
Table Smile classifier training, federated hyperparameters.
Table 6: Smile classifier training, centralized and overall hyperparameters.
(all)
(1-w GT) [8c
(PT and
2-W
GT)
(all)
S
13
K
1]
%
[B
K
T/c
7m
Wr
Wic
100
5
2
0.01
1.0
1000
500
2
1
1.0
0.5
0.5
Table 7: Language model training, federated hyperparameters.
Table 8: Language model training. centralized and overall hyperparameters.
(all)
(I-w GT)
(PT and 2-w GT)
(all)
S
[8
7
Y
[Bdl
[3
K
1]c
We
100
8
16
2.0 (2-W GT:
1.0
6400
800
16
11
1.0
0.75
0.25
Table 9: Movie recommender training, federated hyperparameters.
Table 10: Movie recommender training. centralized and overall hyperparameters.
(all)
(I-w GT) Bel
(PT and 2-w GT)
(all)
S
[8|
K
77
1/s
K
1]c
1/m
Wi
W/
100
16
10
0.5
1.0
10
1.0
0.5
0.5
Our evaluation data consists of both smiling and unsmiling faces, and meant stand in for the inference distribution (where accurate classification of both smiling and unsmiling inputs is necessary). Note that as CelebA contains smiling and unsmiling faces in nearly equal amounts, high evaluation accuracy cannot come the expense of one particular label being poorly classified.
Model Architecture
The architecture used is very basic fully- cally-connected neural network with single hidden layer of 64 neurons with ReLU activations.
14
Hyperparameter Settings The settings used in mixed FL training are shown in Tables 5 and 6 SGD was used for all optimizers: CLIENTOPTIMIZER and SERVERÖPTIMIZER, and (if PT or 2-W GT) CENTRALOPTIMIZER and MERGBOPTIMIZER.
B.2.2 STACK OVERFLOW/WIKIPERR LANGUAGE MODELING
Datasets The Stack Overflow dataset is large-scale federated dataset. consisting of 342,477 training clients and 204,088 evaluation clients (TFF StackOverflow documentation [022]. The training clients have average cache size of ~ 400 examples, and evaluation clients have average cache size of 6,210,1 10 examples (TFDS Wikipedia (20201201 .en) documentation) 2022). which we partition by designating the first 5,000,000 examples for training and the remainder for evaluation. All raw text data is processed into sequences of 100 characters.
examples. The Wikipedia dataset (wi pedi a /2000122 201 en) consists of
Our evaluation data a combined dataset consisting of randomly shuffled examples drawn from Stack Overflow evaluation clients and the Wikipedia dataset. After accounting for raw examples dis- carded during processing, the evaluation dataset comprised of approximately 75% Stack Overflow and 25% Wikipedia. Hence, used this weighting proportion when performing mixed FL training in the language modeling problem (Table
Addpttdd from online tutorial involving CelebA binary attribute classification: Optimization Example Using CelebA Datase!"
"TensorFlow Constrained
15

---

Under review as a conference paper at ICLR 2023
0.7
2 way GT
1-way GT
(only FL)
2- way
0.4
1-way GT
tonly FL)
0.50
1000
2000
3000
4000
1030
2000
3000
4000
(a) Evaluation Accuracy Stack Overflow vs. Round.
(b) Evaluation Accuracy Wikipedia vs. Round.
Figure 5: Language model accuracy, evaluated on only decentralized (left) or centralized (right) data.
Model Architecture The architecture used is recurrent neural network (RNN with an embed- ding dimension of 256 and 1024 GRU units.
Hyperparameter Settings The settings used in mixed FL training are shown in Tables and Note that in this experiment we also found clipping the norm of gradients (both federated and centralized) to be beneficial, for all mixed FL algorithms. We used adaptive clipping for the federated gradients (via the method described in Andrew al. (202T). without noise addition) and a fixed clip value of 0.2 for the centralized gradients. SGD was used for all optimizers: CLIENTOPTIMIZER and SERVERON EROPIMIER,,, and (if PT or 2-w GT) CENTRALOPTIMIZES and MERGEOPTIMIZER.
Evaluation Accuracy on Individual Data Splits Figure 5 shows the accuracy of models (trained either via mixed FL pure FL) when evaluated only federated data (Stack Overflow) only cen- tralized data (Wikipedia) individually. Confirming what we expect, the various mixed FL algorithms do good job of achieving accuracy both datasets. But if train only via FL (without mixing), then we do a good job of learning the federated data (Stack Overflow) character sequences, but aren't nearly accurate predicting the next character in centralized data (Wikipedia) sequences.
B.2.3 MOVIELENS MOVIE RECOMMENDATION
Dataset The MovieLens 1M dataset (GroupLens) contains approximately million ratings from 6,040 users on 3,952 movies. Examples are grouped by user, forming a natural data partitioning across clients. For all mixed FL algorithms we study, we keep examples from 20% of users (randomly selecting 20% of users and shuffling the examples of these users) as the datacenter data, and use examples from the remaining 80% users as client data. With this data splitting strategy, the server data won't 't include the same individual client distributions but will still be sampled from the same meta distribution of clients. We then split the clients data into the train and test sets, resulting in 3,865 train, 483 validation, and 483 test users. The average cache size of each client is 160 examples.
Model Architecture The architecture used the tation learning model with bag-of-word encoder for the left tower (which takes in list of movies a user has seen) and simple embedding lookup encoder for the right tower (which takes in the next movie a user sees).
Anonymous (b), dual encoder represen-
Hyperparameter Settings The settings used in mixed FL training are shown in Tables and 10 In Subsection 4.3) SGD was used for all optimizers: CLIENTOPTIMIZER and SERVEROPTIMIZER and (if PT or 2-w GT) CENTRALOPTIMIES additional experiment where ADAM used as the SERVEROPTIMIZER in 1-W GT.
and MERGEOPTIMIZER See Appendix [B..4| for an
Recall 10 As mentioned in Subsection 4.3 all mixed FL algorithms achieved similar global recall @ 10 compared to the baseline. Figure shows evaluation recall @ 10 over 2000 training rounds.
'Adapted from online tutorial involving character prediction: "Text generation with RNN"
16

---

Under review as a conference paper at ICLR 2023
0.100
0.075
Recall@
0.050
baseline
1-way GT
2-way GT
0.000
500
1000
1500
2000
Training Round
Figure 6: Next movie prediction performance (recall 10).
Table 11: Computation and communication overheads for Movie Recommendation task.
baseline
PARALLEL TRAINING
1-w GT
2-W GT
Comp.
(K N2 d)/2
dN22 2.n.d
(2/
(N2 d2/2
Comm.
2.N.C
3.
3
B.3 COMPUTATION AND COMMUNICATION SAVINGS FOR MOVIE RECOMMENDATION
This section provides a detailed analysis of the computation and communication savings brought by mixed FL in the movie recommendation task.
For movie recommendation, both the input feature and the label are movie IDs with vocabulary size of N. They share the same embedding table, with embedding dimension of d. The input features and label embedding layers account for most of the model parameters in dual encoder. Therefore, we use the total size of the feature and label embeddings to approximate the model size: M = (N + .) d. Batch size is B; and local steps per round is K. Let the averaged number of movies in each client's local dataset for each training round be n, smaller than B, K.
Computation As shown the second row of Table 11 the amount computation for regulariza- tion term is (K. N2, d)/2 if calculating on-device (baseline). When computing the regularization term on the server (mixed FL), the complexity is (N2 d2/2. The total computation saving with mixed FL is ((K 1) N d2/2. We use (N'2 d)/2 2 instead of N2 d for regularization term computation which is more accurate for an optimized implementation.
The total computation complexity of the forward pass is O(B,d (,B.d+B,d&+- + B3d), where the three items are for the bag-of-word encoder, the context hidden layer, and similarity calculation. The hinge loss and spreadout computation is O(B)) + (0,,5 The gradient computation is O(2B,d 2B3 d) for network backward pass and O(B,) + ((Nd) for hinge and spreadout. Therefore, when computing the regularization term the server with mixed FL, the computation savings for each client 1 - (B,d dB, + 38 + 2B;) + 3B,d² + 3B d + 28, + 0.5.V + Nd), which is 99.98% for all mixed FL algorithms.
The communication overheads of each algorithm are presented in the last row of Table For the baseline, the server and each client need to communicate the full embedding table and the gradients, so the communication overhead the server and each client only communicate movie embeddings and the gradients corresponding to movies that client's 's local datasets. Thus the communication traffic is reduced to 2 n or 20KB. GRADIENT TRANSFER requires the server to send both the movie embeddings and gradients each client. The communication overhead then becomes 3 n or 30KB. Overall, mixed FL can save more than 93.9% communication overhead than the baseline.
Communication
N or 494KB. With PARALLEL TRAINING,
17

---

Under review as a conference paper at ICLR 2023
0.8
10:1=5
|A:=2550
0.7
[0,|=25
|6,|=1000
.0
[0,|=100
.85
|8:=5
|8|
|6,|=5
11000
0.4
[A|=100
0.3g
500
1000
1500
2000
500
1000
1500
2000
(a) Eval. Loss Round.
(b) Eval. AUC (ROC) Round.
Figure 7: Smile classifier training, 1-W GT with various central batch sizes |B&e].
0.8
18:1=5
[6,/=125 |6,|=500
.95
0.6
|8:1=50
.90
0.5
[6||=125
=5,
[6,|=500
0.3
.75
(a) Eval. Loss Round.
(b) Eval. AUC (ROC) vs. Round.
Figure 8: Smile classifier training, 2-W GT with various central batch sizes [B&g].
B.4 ADDITIONAL. OBSERVATIONS AND EXPERIMENTS
B.4.1 EFFECT OF of ON CONVERGENCE
Table 3 shows that the theoretical bounds rounds to convergence directly proportional to the client variance bound x² and central variance bound of Also, as discussed Subsection 5.2 1-WAY GRADIENT TRANSFER is sensitive high central variance than the other algorithms. Whereas in the other algorithms the impact of o² on convergence scales with cohort size S, in 1-WAY GRADIENT TRANSFER scales with cohort size S and steps taken per round K.
To observe the effect of of in practice, and compare its effect on 1-WAY GRADIENT TRANSFER vs. 2-WAY GRADIENT TRANSFER, we ran sweeps of CelebA smile classification training, varying the central batch size [B The plots of evaluation loss and evaluation AUC of ROC are shown in Figures (1-w GT) and (2-w GT). For each central batch size setting, we ran 10 trials; the plots show the means of each setting's 's trials, with corresponding 95% confidence bounds.
Figure 7 confirms the sensitivity of 1-WAY GRADIENT TRANSFER to central variance, with ex- periments using larger central batches B, converging faster than experiments using smaller central batches. However, least the case of this task, the benefits of lower variance disappear quickly. The convergence of AUC of ROC did not appreciably improve for central batch sizes larger than 25. Presumably there is little effect at these larger central batch sizes because these cases the convergence is dominated by client variance (i.e., further convergence improvements would come from increasing client batch size [B.)).
Comparing Figure g with Figure 7 empirically observe that 2- 2-Y GRADIENT TRANSFER has lower sensitivity than 1-WAY GRADIENT TRANSFER to central batch size/central variance.
B.4.2 TRADING Bj FOR K
The convergence bounds of Table have an additional implication, in regards to the trade off between client learning rate 77 (and central learning rate 7)) and number of local steps taken K.
It's better to reduce 17 and 1e and increase K, but there are limits The convergence bounds are not related to client or central learning rate (n or n7), but are inversely related to local steps K. In general, it's best to take many steps as possible, and if necessary reduce learning rates accordingly. But there are limits to how large K can be. First, clients have finite caches of data, and K will always be limited by cache size divided by batch size. Second, in the of 1-WAY GRADIENT TRANSFER,
18

---

Under review as a conference paper at ICLR 2023
0.7
PT (n=0.01, K=2)
PT (n=0.0067, K=
90
.55
In=0.01. K=2)
(n= 0.0067, K=3)
0.3
500
1000
1500
2000
500
1000
1500
2000
(a) Eval. Loss Round (PT).
(b) Eval. AUC (ROC) vs. Round (PT).
0.7
wawa (m=0.01, 2=
.95
0.6
1-way GT (n=0.0067, K=3)
.90
0.5
0.4
800
1-way GT 0m=0.01, K-2)
1-way GT 0n=000067, K=3)
.75
1000
1000
1500
(c) Eval. Loss vs. Round (1-w GT).
(d) Eval. AUC (ROC) vs. Round (1-W GT).
2-way GT (n=0.01, K=2)
.95
2-way (n=0.0067, K=3)
0.5
.85
0.4
.80
2-way GT 0n=0.01. K=2)
2-way GT (n- (n=0.0067, K=3)
0.3
500
1000
1500
2000
500
1000
1500
2000
(c) Eval. Loss vs. Round (2-w w GT).
(f) Eval. AUC (ROC) vs. Round (2-W GT).
Figure 9: Smile classifier training with different 77 and K settings (for each mixed FL algorithm).
any increase in K means that central variance of must be proportionally reduced (as mentioned above), necessitating even larger central batch sizes (which at some point is infeasible).
We empirically observed this relationship by running smile classification (Figure 9 and language modeling (Figure I0) experiments where client learning rate 1) (and central learning rate me) are inversely proportionally varied with K. For each hyperparameter configuration we ran trials; the figures include 95% confidence intervals. The results confirm that reducing these learning rates, and making a corresponding increase in the number of steps, beneficial. never hurts convergence, and often helps.
B.4.3 DIFFERENCES IN EFFECTIVE STEP SIZE
Table 12 in Appendix C shows that in order to yield the convergence bounds stated in this paper, each algorithm makes different assumptions of maximum effective step size. From this draw final implication in regards to comparing the mixed FL algorithms.
For given 7/, maximum K varies by algorithm, or, for given K, maximum 7) varies by algorithm Consider just effective federated step size 177,, K for the moment. Assume that server learning rate 7 held constant. Then each mixed FL algorithm has a different theoretical upper bound on the product of client learning rate 1 and local steps per round K. If using common y), the theoretical upper limit on K varies by mixed FL algorithm. Alternatively if using a common K, the theoretical upper limit on 77 varies by mixed FL algorithm.
The maximum effective step sizes of Table 12 immll that 2- WAY GRADIENT TRANSFER has narrower limits than 1- 1-WAY GRADIENT TRANSFER on the allowable ranges of n and K. It also indicates that for PARALLEL TRAINING the allowable range of n,, Me, and depends on the B parameter from mixed FL (G, BGD (Definition 5.2).
Some of this behavior has been observed empirically, when hyperparameter tuning our experiments (discussed in Subsection B.2 For example, for the language modeling experiment, assuming
19

---

Under review as a conference paper at ICLR 2023
1.6
PT (g=2.0, K=8)
.65
1.5
PT (n=1.0, K=16)
600
1.4
(n=2.0.
PT 110, K-16)
500
1000
1500
2000
4
500
1000
1500
2000
(a) Eval. Loss Round (PT).
(b) Eval. Accuracy Round (PT).
1-way GT (n=2.0, K=8)
1 1-way GT (n=1.0, K=16)
.55
1.3
1-way GT (g=2.0, K-8)
.50
1-way GT (r=1100. K-16)
1.2
45
1000
(c) Eval. Loss vs. Round (1-w GT).
(d) Eval. Accuracy vs. Round (1-w GT).
1.6
2-way GT (1=2.0, K=8)
.65
1.5
2-way GT (n=1.0, K=16)
1.4
1.3
2-way GT (n=2.0, K=8)
1.2
.50
2-way GT (n=1.0, K-16)
500
1000
1500
2000
445
500
1000
1500
2000
(c) Eval. Loss vs. Round (2-w w GT).
(f) Eval. Accuracy vs. Round (2-w GT).
Figure 10: Language model training with different 1 and K settings (for each mixed FL algorithm).
1.6
PT (.0))
.65
1.5
1-way GT (n=
1.4
2-way (n= 1.0)
(n 3.0)
1.3
1-way (n 3.0)
1.2
.50
2-way GT (n = 1.0)
1000
2000
3000
45%
1000
2000
3000
(a) Evaluation Loss vs. Round.
(b) Evaluation Accuracy vs. Round.
Figure 11: Language model training, with higher 7) for PT and 1-w GT (K 16 for all). The increased learning rate boosts progress on evaluation loss and accuracy early in optimization, but does not change the number of rounds ultimately required for convergence. All three algorithms have reached similar loss and accuracy by round 3000, and are still converging.
constant number of steps K 16. 2-WAY GRADIENT TRANSFER tends to diverge when learning rate 77 was increased beyond 1.0, whereas 1-WAY GRADIENT TRANSFER is observed to converge even with learning rate 1) of 5.0. (PARALLEL. TRAINING is in-between; still converges with learning rate 77 of 3.0, but diverges when learning rate 17 is 5.0.) An interesting characteristic to note is that using different 7j in different algorithms does not really impact comparative convergence. Figure []] shows convergence in the language modeling experiment, when 2-WAY GRADIENT TRANSFER uses 7 = 1.0 1.0 and J-WYY GRADIENT TRANSFER and PARALLEL TRAINING both use v = 3.0 (in all cases, with K 16). The higher learning rate of 1-w GT and PT helps a little early, but does not impact the number rounds to convergence. This holds with the theoretical convergence bounds of Table 3 which show relationship with steps K but not learning rates (as also discussed above).
20

---

Under review as a conference paper at ICLR 2023
baseline adam
1-way GT adam 1-way sgd
sqd
Evaluation Loss
10.4
10.2
10.0
500
1000
1500
Training Round
0.100
Recalle
0.050
0.025
baseline ne adam
1 1-way GT adam
baseline sgd
1-way GT sgd
0.000
500
1000
1500
2000
Training Round
Figure 12: Next movie prediction performance when training with adaptive optimizer (client opti- mizer: SGD, server optimizer: ADAM).
B.4.4 1-w GT WITH ADAPTIVE OPTIMIZATION
We briefly studied the performance of 1 1-WAY GRADIENT TRANSFER when using ADAM in place
of SGD as the server optimizer, i..., FEDADAM (Reddi et al., 2020 Note that the server adaptive optimizer requires smaller learning rate perform well. Figure
reports the results of using
ADAM as the server optimizer with a server learning rate of 0.01. All the other hyperparameters are the same in Tables 9 and TO We observe that (1) ADAM works better than SGD, leading to better convergence, and (2) TAW GRADIENT TRANSFER performs almost the same as the baseline when using ADAM. We will extend our investigation of mixed FL with adaptive optimization in the future. This will include studying methods for applying adaptive optimization to PARALLEL TRAINING and 2-WAY GRADIENT TRANSFER; these algorithms are more complicated since they involve additional optimizers (CENTRALOPTIMIZER and MERGEOFTIMIZER)
B.4.5 COMPARISON WITH TRANSFER LEARNING
Section discussed how transfer learning is ill-suited for mixed FL. Here we show why.
Recall the bias mitigation mixing task of Section 4.2 The end goal a single trained language model that performs well both for high-end and low-end mobile phone users. We use Stack Overflow and Wikipedia datasets as respective experimental stand-ins, as they model the problem well. They are in the same domain (Latin alphabet) and same language (English) but with distinct usage distributions.
Transfer learning sequentially trains the language model, first 'pretraining' on one dataset and then switching to 'fine-tune' on the other. One could first centrally pretrain (with Wikipedia), then switch to federated fine-tuning (with Stack Overflow), or the converse. Figure 13 shows what happens. The switches take place at 250 rounds. We also show PARALLEL TRAINING point of comparison.
Figure shows that in transfer learning, catastrophic forgetting the pretraining task occurs after switching to the fine-tuning task. The centralized pretraining case precipitously drops its evaluation accuracy on datacenter data (Wikipedia). The federated pretraining case does the same with federated data (Stack Overflow). Figure 13 shows that PARALLEL TRAINING achieves superior evaluation accuracy on the stand-in for the desired inference distribution (i.e. the combined Stack Overflow and Wikipedia datasets).
21

---

Under review as a conference paper at ICLR 2023
0.6
0.4
Centralized Pretraining Federated Pretraining Parallel Training
0.2
100
200
300
500
600
(a) Eval. Accuracy on All Data vs. Round.
0.6
0.6
Centralized Pretraining
Centralized Pretraining
Federated Pretraining
Federated Pretraining
0.2
Parallel Training
Parallel Training
100
200
300
400
500
600
100
200
300
400
500
600
(b) Eval. Accuracy on Stack Overflow vs. Round.
(c) Eval. Accuracy on Wikipedia vs. Round.
Figure 13: Mixed FL endeavors to learn both data distributions, but transfer learning fails to retain knowledge the pretraining task. When the pretraining-to coaiiinng---ff------ to-fine-tuning switch happens at round 250, the transfer learning cases fit the new distribution and 'forget' the previous distribution they were pretrained on. PARALLEI TRAINING does not suffer from this problem as it sees data from both distributions throughout training.
To simplify Figure 13 we don't show GRADIENT TRANSFER results, but they would match PARALLEL TRAINING (e.g., as shown Figures D and (p). Because the PARALLEL TRAINING and GRADIENT TRANSFER algorithms presented in this paper jointly train both data distributions in parallel (as opposed to sequentially), they avoid catastrophic forgetting.
22

---

Under review as a conference paper at ICLR 2023
Table 12: Maximum effective federated step size, f) myK, for convergence bounds in Appendix C and Table 3 When applicable (PT, 2-w GT) the effective centralized step size, R,K, shares the same maximum (and assume that merging learning rate 7/m 1). , is the smoothness bound (Def. D.1
PT
1-w GT
2-W GT
J-CCOVEX
min
6[1 B1}+
83
813 15p
CONVEX
1
6(1 B-)3
8,
8133
NONCONVEX
6[1 13)3
18
24/9
Table 13: Assumptions merging or server learning rates, for convergence bounds in Appendix C and Table
PT
1-w GT
2-w GT
(ASSumES)
7m 2
1
1/s 2 VS
7m 2 1
C
CONVERGENCE THEOREMS
The three subsections that follow state theorems for convergence (to an error smaller than <) for the respective mixed FL algorithms. The convergence bounds are summarized in Table in Section 5 Tables 12 and convey some supporting aspects of the convergence bounds, about limits on effective step size 1) and assumptions on learning rates.
C.I PARALLEL TRAINING
Given Assumption 5.1 one can view PARALLEL TRAINING as a 'meta-FEDAvG" involving two 'meta-clients'. One meta-client the population of IID federated clients (collectively having loss fi), and the other meta-client is the centralized data at the datacenter (having loss fc). As such, we can take the convergence theorem for FEDAVG derived in Karimireddy et al. (2020b) (Section 3, Theorem I) and observe that it applies to the number of rounds T to reach convergence in the PARALLEL TRAINING scenario.
Theorem C.1. For PARALLEL TRAINING, where the federated data is IID (Assumption 5.1 for 3-smooth functions fy and fo which satisfy Definition 5.2 the number of rounds to reach an expected error smaller than is:
Jt-Strongly convex:
T Ō
(o"+8o") KSpc
GVB
log(t) nv4
#
General convex:
==0
(u24802)D2
GV3 .
+ B²
KSc
Non-convex:
==
(o (o²+8o2)8F
GV3
B²DF
RS.
where f(x(()) ) - f(x"), 12 12-101100 -2-0 - x=1.
Conditions for above: 1jm 2 1; 777, S 6(14#2)aK
Proof. The analysis is exactly along the lines of the analysis in Karimireddy et al. (020b), Appendix D.2, in the context FEDAVG. Effectively, the analysis applies to the imeta-FEDAve problem of PARALLEL TRAINING, with two 'meta-clients, one being the central loss/data (with stochastic gradients with variance of af) and the other being the federated loss/data. The homogeneity of the clients and the averaging gradients to o² o²/s. The analysis follows in straightforward manner by accounting for the variance in appropriate places. We omit the details for brevity.
the sampled clients effectively reduces the variance of the stochastic
23

---

Under review as a conference paper at ICLR 2023
C.2 1-WAY GRADIENT TRANSFER
We now provide convergence bounds for the 1-WAY GRADIENT TRANSFER scenario. Unlike PARALLEL TRAINING, which could be thought of 'meta' version of existing FL algorithm (FEDAVG), 1-WAY GRADIENT TRANSFER is an entirely new FL algorithm. As such, we must formulate novel proof (Appendix D of its convergence bounds.
Given Assumption 5.1 the following Theorem gives the number of rounds to reach a given expected emror
Theorem C.2. For 1-WAY GRADIENT TRANSFER, where the federated data is IID (Assumption 5. for fnnctioon fi and fo. the number of rounds T to reach an expected error smaller than
p-Stroonly corvex:
T =
(n (K
2 (og(
when v 188 S
KSpe (a (a²+KSo2)D
85Km
General corvex:
T =
OD2
when 1}s V /38.1 1 8
KS
Non-convex:
T T
(o2+KS02)08
BF
when f3s 2 v S 18
KSe
where F' f(xx f(x"). 112
(0) x="
Proof. Detailed proof given in Appendix D
C.3 2-WAY GRADIENT TRANSFER
Given Assumption 5.1 one can view 2-WAY GRADIENT TRANSFER as 'meta-SCAFFOLD' involving two 'meta-clients' (analogous to the view of PARALLEL TRAINING as 'meta-FEDAvG" in Subsection C.I) As such, we can take the convergence theorem for SCAFFOLD derived in Karimireddy et al. (2020b) (Section 5, Theorem III) and observe that it applies to the number of rounds 7' to reach convergence in the 2-WAY GRADIENT TRANSFER scenario.
Theorem C.3. For 2-WAY GRADIENT TRANSFER, where the federated data IID (Assumption 5.7. for 3-smooth functions f and fo. the number of rounds T to reach an expected error smaller than
JtStrrnnly convex:
T
(o2 (o2-So?)
+
log( (
when Yie 2 1; 1/8/ & min 813K 16p
KSpu
General convex:
T 0
(0 S0=
AD2
when The 1:7k, 117, S sInK
K8e
Non-convex: T-
when Th 2 1;7,, mp1 S 24
KSCt
where F f(xx())) f(x'), D2 (z) xx
Proof. The analysis is exactly along the lines of the analysis in Karimireddy et al. (2020b), Appendix E, in the context of SCAFFOLD. Effectively, the analysis applies to the CSFFOO problem of 2-WAY GRADIENT TRANSFER, with two 'meta-clients', one being the central loss/data (with
stochastic gradients with variance of o?) and the other being the federated loss/data. The homogeneity of the clients and the averaging over the sampled clients effectively reduces the variance of the
stochastic gradients to ///s. The analysis follows in straightforward manner by accounting for the variance in appropriate places. We omit the details for brevity.
24

---

Under review as a conference paper at ICLR 2023
D CONVERGENCE PROOFS FOR 1-WAY GRADIENT TRANSFER
We will prove the convergence rate I-WAY GRADIENT TRANSFER for 3 different cases: strongly convex, general convex, and non-convex. While these proof' are influenced by those for SCAFFOLD in Karimireddy et al. (020b), we note some additional technical challenges we face with 1-WAY GRADIENT TRANSFER. First, the name indicates, gradient information only flows way (in SCAFFOLD, gradient information flows from and to all clients). Second, we only sample a batch of centralized data once per round (whereas SCAFFOLD can draw multiple batches during a round). The result is that (as described in Subsection 5.2). -WYY GRADIENT TRANSFER works out to be more sensitive to central variance of and number of steps K than 2- WWW GRADIENT TRANSFER.
We will first state number of definitions and lemmas in Subsection D.I that are needed in proving convergence rate of 1-WAY GRADIENT TRANSFER, before proceeding the actual proof's in Subsection D.2
D.1 ADDITIONAL DEFINITIONS AND LEMMAS
Note that some of the lemmas below are restatements lemmas given in Karimireddy et (2020b). We opt to restate here (versus referencing the relevant lemma in Karimireddy et al. (2020b) each time) due to the volume of usage of the lemmas, to ease the burden on the reader.
We will first present the subset of definitions and lemmas which don't make any assumptions of convexity (Subsection D.I.Ip, followed by the subset that assume convexity (Subsection D.1.2)
D.1.1 GENERAL DEFINITIONS AND LEMMAS
Definition D.1 (8-Smoothness). A function h is 3-smooth if it satisfies:
VV(zz) Vh(y)) || S 3 || yll, for any æ,
This implies the following quadratic upper bound on h:
(V(()) y - x) (((z)) h(y) + 2 || - 21() for any æ,
Lemma D.2 (Relaxed triangle inequality). Let {ul, ......., 1r be vectors in Rd. Then for any a > 0:
||e + uyll s (1 1|=/1 + 1 1
|,y]1
Also:
|1
Proof. The first statement for any follows from the identity:
l0 + 1| (1 + 1u..11 + 1 1
||,/11 |aae
1 Uy
Va
The second statement follows from the convexity of v + ||ua|2 and Jensen's inequality:
|o,1"
Lemma D.3 (Separating mean and variance). Let [ ..... ......,, E,} be J random variables in Rd which are not necessarily independent. First suppose that their mean is E[E.] = E, and variance is bounded as E|||E, - = < o². Then:
E
+
i=1
25

---

Under review as a conference paper at ICLR 2023
Now instead suppose that their conditional mean is E ..]] E.. i.e. the variables
{ - Es} form a martingale difference sequence, and the variance is bounded same as above. Then
can show the tighter bound:
E
Σ
S 2E
Σ
&
+
2To²
Proof. For any random variable X, _[X²]
B[X]]) + (E[x))) implying:
Σ
Σ [ - Ev)
E
&
+
E
Expanding the last term of the above expression using relaxed triangle inequality (Lemma proves the first claim:
|
Σ [ ())
S ST <
s.IPp] s T0002
For the second statement, & is deterministic and depends Ei E1. Hence have resort to the cruder relaxed triangle inequality to claim:
(.) 17
E
Σ
E
2E
Σ
&
2E
Σ ( (E.
Then we use the tighter expansion of the second term:
||
-
4)) so)
E
Σ [
B -6,5, -5))
Σ E |E E/1²
S ra²
The cross terms in the above expression have zero mean since {E, {.} form a martingale difference sequence.
D.1.2 DEFINITIONS AND LEMMAS ASSUMING CONVEXITY
Definition D.4 (p-Convexity). A function h is p-convex for μ 2 0 if it satisfies:
(Vh(z), x) S (h(z) h(y) 1 x - for any x, y
When > O, we have strong convexity, a quadratic lower bound on h.
Proposition D.5 (Convexity and smoothness). If client losses fr and centralized loss fe are each 3-smooth (Definition D.I,, and x" is optimum of the overall loss f (as defined in Equation 7 then the following holds true:
N
s fzxx (V='')))
Vfc(a')12
23
Proof. Define the functions f((x) f((x) (Vf((*)), for all clients i, and the function fc(z) == fc(x) (V.f.x")),) (,), Since f. and fa are convex and 3-smooth, are fo and for and furthermore their gradients vanish at æ"; hence, x" a common minimizer for f.. fo and f. Using 3-smoothness f, and fc. we have
1
v 21 < f.(x) f((x)) and
// [v)(()) < Fc(x) - Fc(x).
28
23
Note that + >>
f. + = since + E
V.(xx')) Vfc(=*)= vf(x*) = The claimed
==
bound then follows from the above two facts.
26

---

Under review as a conference paper at ICLR 2023
Proposition D.6 (Convex bound gradient of overall loss). If client losses fs and centralized loss fe are each p-convex (Definition D.4) and B-smooth (Definition D.Iy, and x" is an optimum of the overall loss (as defined in Equation D.. then the expected norm of the gradient of overall loss is bounded as:
E E[VS(=)) <48B(5(2) f(xx)]
Proof.
E [|V]
( - [==")|
E
(Vf(())) -f( +
vfc((*))
N
Applying the relaxed triangle inequality (Lemma D.2 twice:
N
E Vf(x)
2E
(V((())) - vf((z'))
+ +E Vi((2)) Vfc(2*)]1
N
1
S 2E
[(Vf(()) v + 2E vf((=))1
N
S 2E
V vf((=*))1
N
Applying Proposition D.5
E [>>))
- -(a I 45E - f(x*)]
Lemma D.7 (Perturbed strong convexity). The following holds for any 8-smooth and p-strongly- function h, and any x, y. z in the domain of h:
(Vh(z), yt 2 h(2)) h(y) + 11 y =11 B || x01?
Proof. Given any x, y. and get the following two inequalities using smoothness (Definition D.I and strong convexity (Definition) D.4] h:
(Vh(z), x x) 2h(z) h(xx)
2 || x ||
zh(x) - h(y) +
1/ 2 2
2
Further, applying the relaxed triangle inequality (Lemmaa D.2) gives:
f Il x=|
/ 1ly 2||
1 2
|| z 1
2
4
Combining all the inequalities together have:
(Vh(z), z y) 2 h(2) h(y)
11
4 l1
2112
B
3+1
|| x=1
The lemma follows since ,3 2 μ.
Lemma D.8 (Contractive mapping). For any 3-smooth and u-strongly convex function h, values æ and y in the domain of h. and slep-size (learning rate) 1 73 the following holds true:
- 1))()) - + vh(y))1 < (1 - nm) || - y1
27

---

Under review as a conference paper at ICLR 2023
Proof. Expanding terms, and applying smoothness (Definition D.I.
| 1æ-vvii -V/(()) ~/V((y))
y + n/ [[V/(()) Vh(y))1
Vh(aa Vh(y), ) - y
S || y12 (11² 2n) (Vh(z=) Vh(y), y)
step-size such that - 3. then: Finally, for j--trong convexity (Definition D.4) of we have:
(n 2n) (Vh(z) Vhly). y) S Vh((>) Vh(g), y)
(V Vh y) S u | y|1
D.2 PROOFS OF THEEOREM
We will now prove the rates of convergence stated in Theorem C.2 for 1-WAY GRADIENT TRANSFER. Subsection D proves the convergence rates for strongly convex and general convex cases, and Subsection D.2.2 proves the convergence rates for the non-convex case.
Let S be the cardinality of the cohort of clients S participating in round of training. Let the server and client optimizers be SGD. Let the clients all take an equal number of steps K, and let ij be the "effective step-size', equal KπT.. With W-WAY GRADIENT TRANSFER, the server update of the global model at round & can be written as:
K (ol(a((ik)) + 90 (c(2((1))
(++1) (1)
1j
KS
iES
Amml
(11)
K
x (t+1) x())
-xig((x::1))
1
((((((())))
KS
iES
Rm
Henceforth, let [-] denote expectation conditioned on x (1), As in Karimireddy et al. (020b), we Ill define client local 'drift' term in round as:
N
K
g())
E
x
(t,k)
x 2000
(12)
KN
1=1
k=1
Lemma D.9 (Bound on variance of server update). The variance of the server update is bounded as:
E
- [1a(tt))=00001
< 4it g + 2np
KS 0² + oo? + 2r (()))())))
||
Proof. Let S denote the set of clients sampled in round t. For brevity, will use Ax refer to (t--)) (t),
Ep.
Ax 2
Ejp
(1+1)
=01019
E5
(o((((()))) g6(
KS
():(a((())) -((((()))()(((((t))) (VSi(z(())) g (c(
< Ep
KS
k=1
28

---

Under review as a conference paper at ICLR 2023
We separate terms by applying the relaxed triangle inequality (Lemma D.2):
K
|1 [[ + 20 9c( 13
Bi |xxl S 1ee
V 11((0(0))
+ 2n Eip
KS
ES
k=1
In term A. we separate mean and variance for the client stochastic gradients Is, using Lemma D.3 and Equation 4
K
11
4if
A Ei
Virl(a
V(((a())
KS
KS
JES
1=1
We apply the relaxed triangle inequality (Lemma convert it to an expression in terms of drift g(:);
D.2
followed by smoothness (Definition D.1 to
N
K
477²02
V VV((ac ((.)) - //i(o(0))
A
E
KN
KS
E=1
4ff
| -0(11 200111]]
4jj302
E
KN
KS
1=1
k=
4fj²0²
s g((
KS
In term we have a full gradient of the federated loss f and a stochastic gradient of the centralized loss Gc. We use Lemma D.3 to separate the stochastic gradient into a full gradient of the centralized loss fc and variance term, allowing us to express terms of full gradient of the overall loss f.
V (i((z((0) c<( [|]
B B= B=2ij 2 E2p
Vf((z((t) Vz((((( (1) 11²)
<21i
21j²
Ep
((0 +27700
Combining A and B back together:
E Axx 2 < 32)
+21
(
0² + 02
0²
B |
KS
D.2.1 CONVEX CASES
We will state two lemmas, one (Lemma D.10 related the progress in round towards reaching st. and the other (Lemma D.11 bounding the federated clients 'drift in round g()) We then combine the two lemmas together to give the proofs of convergence rate for the strongly convex (μ > 0) and general convex (μ 0) cases.
29

---

Under review as a conference paper at ICLR 2023
Lemma D.10 (One round progress). Suppose our functions satisfy bounded variance o², fı-convexity (Definition D.4, and B-smoothness (Definition D.I. if S3 the updates of 1-WAY GRADIENT
TRANSFER sattsfy:
B [ - 2-1 -
34m 2
||
|
x:1 2²12 - -i(((( (f(x(0)-((x*)) + g()
16
+ 21²²
K 0² + +o?
Proof. The expected server update, with N total clients in the federated population, is:
N
K E 9.(2
((+1)) z1()] = -n (c(2(())]
KN
The distance from optimal x parameter space at round ||a:(0) x=" 11 The expected distance
from optimal at round + 1, conditioned on (1) and earlier rounds, is:
-0 [+tttt)) x- =01
Ep x (1+ x²)) + x -2-11
x-1; 201?]
x (1) - xz I1 +2 2E x((+1) x(1) ,0((1) x²) +1i | - x 200
For clarity, we now focus on individual terms, beginning with C:
= [E (0+1))
-x.(1)
,0000 xx"
N
=2
Mi (c(()(11)
(.(aa(1))))) xx(1 x
KN
i=
k=1
N
K
27 ((((((())) -x (1))
2m
fi(x: (t.)) ), x1
KN
We can use convexity (Definition D.4) bound C1, with (t), and y = x=:
C1 < 2n fc((x()) fc(x=) + x0 x x01()
We apply perturbed convexity (Lemma D.7 to bound C2, with x xzj
(t.A) xx, and (1);
N
K
2î
fi(x*) - f((x + + +331a01 (1,b)
2000|
11
(1()) x= x111"
C2 <
KN
4
k=1
((((:(t)) - fi(xx* + 1 (o(()) 2x" 11) +
2,9
K
(e.k) o (0
< 22j
x.
KN
d= k=
< 2- ((((a())) f((2=" 11 (1) x²" 1²) + (3
30

---

Under review as a conference paper at ICLR 2023
Combining C1 and C2 back together:
S -2 (s(a())) f(x=)
3/4
|010) x* =²1(') + 2,T7
Now we turn to term D, which is the variance of the server update (from Lemma D.9h:
D = Es -
2001- - B +27²
( ( 0 + 0. + B KS
2
We can leverage Proposition D.6 to replace the norm squared of the gradient of the overall loss:
D = Eie =000 < g( + 2n² K + +o?) + 878 Bl [(() - -(x))))))xx))
Returning to our equation for the expected distance from optimal x" in parameter space, and making use of the bounds we established for C and D:
E | - x- =010 = -|x0) - x¹1'" -001'-l +2 +2
x (++1)
x(11]
xx(1) x²)
+ E
(t+1)) x 10/
D
(1) x'11" 27 (f(x(1)-f(az) ff(')=((x)))))
3/ x(1) - -001(²))
2
+ 2877 44j 277
08 to?
+ SE [f(=(() f(x0)]
1 3um
2 |00(0) x=* 1
+ (87 B 27) (1(z(()) - f(x0))
+ +27 (1 + 275) g(t) + 277² ( 0² + +0?
Assuming that ; < 33:
E 1 - x011"
340
| x²
10 (f(x()))((x))
_ E(1
<
2
16
2 KS
2n²²
+ +o?
Lemma D.11 (Bounded drift). Suppose our functions satisfy bounded variance, ju-convexity (Defini- tion D.4), and B-smoothness (Definition) D.I). Then the drift is bounded as:
f(x²)) + +3K2 (1 K
g(t) 1 3E (()(())
+ +o?
31

---

Under review as a conference paper at ICLR 2023
Proof. We begin with the summand of the drift term, looking at the drift of a particular client at local step k. Expanding this summand out:
(1,R) B 2;
(1)) 10 = 1 (t.k-1) - (x) (1(b-11) + (=(()())) - x =000|"
= jr x ((. x(() ng. (x) (x((()-1))) (000
Separating mean and variance of the client gradient, then using the relaxed triangle inequality (Lemma D.2 further separate out terms:
(t.1) 1 a
2011/² S Ryc
(=.(t(-1)) x:(1) 1/ Si(2r.
(( - ng. (x/)) //((((/
+ 12202
Bie x (1abb-11))) - x!(1) -1) -
+ + a1+ n² ((((=!)) + (<()(()) /| + n2a02
Term F is bounded via the contractive mapping lemma (Lemma D.8 provided that v) S 1. g²
(1- | [=((t--1) 2001|² = Bip - ((( 2001|2
Putting back into the bound drift on client i at local step k and letting a = K:
E, a0 (1,b)
K+1 Bie
|o (os(k-11) c00 +KKn / V[(((00))+ + )c((e())) t170².
Unrolling the recursion:
E 1
x
(t,A)
x
s 2Kn² (00(==00)))()))))) 112
Σ
1=0
< 2Kn v)(((( (1) + (00
+1200
(2K)
4k2, Vi((" + 2 (x)
+2K
The second inequality above uses the following bound:
k-1
-
< 2K.
1=
Now separating mean and variance of the central gradient:
(t,K) x
x0())
1K2, V (((( + Vi(((e()))'
+ +2K2n200" + 2K
< 2 (0x /|² 2k??
_ K
+
Finally, we apply Proposition D.6
32

---

Under review as a conference paper at ICLR 2023
80 I 422 (1) 22
K OK + to?)
1
1 + ORO²+0?)
$ 16K2 3 ((((0)) + -2K277
Assuming that 1j 5
8/
1/2 (1 + 0² + to?
(()) S 2 _ Bir f(((10) -((("1))(((0)) 1/
T/e K
Proofs of Theorem C.2 for Convex Cases Adding the statements of Lemmas D.10 and
D.11 and
assuming that 1/s >
S. n
80kn so that 7j = 83 we get:
(141)
x= 111
3pm
|0(00
x² x01?"
112 - -n (f(o())) -f(x*)
5
B1 [(xx(0) -(aaa)
+2 72 (1
00²0 + t
+ 16
75
1/3
+ 27j
KS 0² + 0!
|0000) x² x11 1|
- ()(( -
(((o()))((xa)) f(x*))
2
+ 1
5
BBr
(((z(1)) =f(x")
2
172
(5 (5
+
0²
+ 27 o²
Knp
KS
8 n
3p0
| xx"
S
/50²
- --((((a) n [((x10)
+ 30? ip2
+
S
KS
We can now remove the conditioning over x (() by taking expectation on both sides over (t), to get a recurrence relation of the same form.
For the case of strong convexity (μ > 0), we can use lemmas (e.g.. Lemma 1 in Karimireddy et al. (2020b), Lemma 2 in Stich (2019) which establish a linear convergence rate for such recursions. This results in the following bound for T 2
88
3n
E [( - f(x'((())))))))))) δ
02 + KSo?
+2*KSo?
10 (0) x=
2
-3pT
#KST
exp
168
where i (T)) is a weighted average of ())) (2)) (2)
(T+1) with geometrically decreasing weights
(1 2
30d 1 for (r), ,r),r r = 1,2,..., T
This yields an expression for the number of rounds T to reach error
T= Ō (0² (
KSo?
+
log
KSue
16The Ô notation hides dependence logarithmie terms which be removed hy using varying step-sizes.
33

---

Under review as a conference paper at ICLR 2023
For the case of general convexity 0), use lemmas (e.g.. Lemma 2 in Karimireddy et al. (2020b). Lemma in Stich] which establish sublinear convergence rate for such recursions. In this case get the following bound:
E [ - 1(x²)= -
-
5 5
S
883 (0) xx"
20 12K x x=" VKS(T+ +1)
T
where x (7)
T+I T++ x (1)
This yields an expression for the number of rounds T to reach an error e:
(o² KSo D2
BD
T ==
KS
In the above expression, 2 a distance in parameter space at initialization, ||x:10) x
D.2.2 NON-CONVEX CASE
We will now prove the rate of convergence stated in Theorem C.2 for the non-convex case for 1-WAY GRADIENT TRANSFER. We will state lemmas, one (Lemma D.12) establishing the progress made in each round, and one (Lemma D.13) bounding how much the federated clients 'drift' in round during the course local training. We then combine the two lemmas together give the proof of convergence rate for the non-convex case.
Lemma D.12 (Non-convex one round progress). The progress made in round can be bounded as:
Bip [( s f(x(0))
4
g(0)
2 0² + to? gip KS
Proof. We begin by using the smoothness of f to get the following bound on the expectation of (()(++)) conditioned on (*);
Bip [(((()1))] s ER ((x(()) + ( (z(1)))))()))===(()))))
-z(1))
3
2 x (t+1)
x0(1) 2 (++1)
(01
S f(x(0)) + E (v)(= x((+1) - x((1)
+ Bip
Substituting in the definition of the 1-WAY GRADIENT TRANSFER update (Equation and using Assumption 5.1 for the expectation of the client stochastic gradient:
Es [[x((t+1))] (zx(t) + B/
V (z)
gi(we(td)) + g6 (c(cx(1))
KS
iES
k=1
3
(1+1) - 2000l1
+ 2 Eye
x
$ (()
()()( 1
Vii(m
(((l)) V(c(a((1))
KN
3
(1+1) x000
+
Eje
Next, make of the fact that -ab [(b a)2 x² - 12) 3 (bb a)2:
34

---

Under review as a conference paper at ICLR 2023
B1 [[(altti))] s {(x(0-
- 1
) /|
2
2
N K
Viila, ( + Vf((a())) - vf((o(t))
+
2
KN
k=1
8
R,
x
((+1)
x 20001
2
7
{)))
2
N
K
v V(((o - )
KN
1=1
8
2 E
x
x 20() | ()))
((+1)
S (0)
2
V
|
K
17
1
B1 Vir(an - -V
2
KN
i=1 k=1
2
8
x (++1)
x 2001
Next, we use smoothness (Definition D.I. and the definition of client drift (Equation 12
Bp [[(((411))] S f(x(()))
17
V
((
2
2
7,82
N
K
(1.b) 20
+
B1e
x
KN
k=1
8
(++1) c0(1)) ||2
Ei
x
2
$ fzx
|f(=
1| //2
+
n192
2 E(1
2
En
x (t(++)
2
The last term is the variance of the server update, for which we can substitute the bound from Lemma D.9
E1 [[alltt))]]
S (1x(())
17
V (()))) /|²
1732
-
+
2
2
+
8
4nj2 g(0)
+ 227
K + +o?
2
+ +212BB \T(= )1²)
2
S {)x(
(
|
||²
2
+
1182
+ 21/2 83 g()
2
2
2 02 + oZ
+ 7
KS
Assuming a bound on effective step-size ñ S 183.
E [s(a(tti)]] s s((x()) - 47 [((a(())
||
8 g0))
+ ( x + +0²) Bip.
+
9
27
35

---

Under review as a conference paper at ICLR 2023
Lemma D.13 (Non-convex bounded drift). Suppose our functions satisfy bounded variance and B-smoothness (Definition D.I. Then the drift is bounded as:
(() - 9.3n?
4rj
E
V ()))
2n
1 0² + 402 )
K
Proof. We begin with the summand of the drift term, looking at the drift of a particular client at local step k. Expanding this summand out:
(t,k) E 8i
(t())
||= = E
x (t.k-1) 1] (a) (1))))))) + ge se(2xl()) - -xx
E (t.k-1) - (t) ng: (x0 (1) (10(
Separating mean and variance of the client gradient:
E 1 (t.k)
=000 s E
L [t.kk (²)) V f((z; (1) (x)()(())
||] +17002
Next relaxed triangle inequality (Lemma D.2 to further separate terms:
(t,k)
=013
< 1 1 a
11
Di
æi
fi(a (c 1) + (() 1
+ (1 a) 2
V
+120²
11 E z ((A-11) - (t) 12
+ +(++a) 2 ( (V (()))) v)((e(())) + - + (
+120²
(t,k-1) _ (1( 1
1 a
E xz
Vfi(2 (1--)))-- () 12 a(1+a) ( (1)
+ (1 a) 2n
H
+ (1 + a) 4n (x)() Vi(((0(0))
/|
+1/002
In the above inequality, term H can be converted via smoothness (Definition D.I and term I is the variance of the centralized stochastic gradient (Equation 6). Letting a K, have:
(t.k) x
2000
S
K K
+ +2
E o (1--1) - 20001² - 4K (
+ +4K1²0² + 11220²
Unrolling the above recurrence, we get:
1-1
E x
(1,N)
=200//²=
5 [K
(((a()))
+ 4K17 0 + 1200²
Σ
K
+ 2k
K
1=0
41² Krp
18
+
7
1 K
2
+ 40
Σ
K +1
2 82 5 KT
Kiz
36

---

Under review as a conference paper at ICLR 2023
Assuming 7/5 2 1, and 1j S 18,3 we have K+1 + 28
S +
163
and hence
oo
162K
R-1
K+1 K
28 K
[1
163 162K
) (1 +
163
K
1)
162K
1
(e
163
1)K 2K.
162K
163
==
j=0
E
(1)bb)
x
10
2πj 933Kgg
E
1 + 2K
Kig
Adding back the summation terms over and k, the bound on client drift is:
g(o <
4n
E \)(
2 ||
2nj² ns
( + 402
1 K
9.8m
Proofs of Theorem C.2 for Non-Convex Case and assuming 1/2 2 VS, we get:
Adding the statements of Lemmas D.12 and D.13
b [( s f(x(1))
40
V
fz (1))
||
2
+
0² + +02 Bin
9
4m
||
1
21j²
1
+
E
(((((()))
+
0² + 40?
27
9,3m
mh
K
((x(0)
3
(z)))))
(1))
1
+
3
0²
+ 20 Bi²
With the above, we have a recursive bound on the loss after round / + 1. We can use lemmas (e.g.. Lemma 2 in Karimireddy al. (2020b), Lemma 4 in /tich (2019) which establish sub-linear
convergence rate for such recursions. Assuming 7 S 183 and n3s 2 VS. we get:
543F 6v 02 + 202) 3F 1 T+1
min (E.1..... T+1)
+T+1
In the above expressions, F is the error at initialization, f(x f(x').
This yields an expression for the number of rounds T to reach an error e:
[0 + KSo 3F
3F
T=o
KSe²
E
37


Reviews:
[{"review_id": "es_VM_wZc9", "reviewer": "Reviewer_oANg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose algorithms for federated learning (decentralized data) alongside the presence of a centralized dataset (termed \"mixed federated learning\"). The paper presents 3 algorithms based on gradient exchange between the clients and the server, benchmarks the corresponding performance on 3 tasks (simple classification, language modeling, movie recommendation) and theoretically analyzes the convergence properties. The benefits of the proposed methods are in terms of improved predictive power (due to the centralized data complementing the decentralized) and in terms of computation and communication efficiency (due to offloading intensive computations to the server side).", "summary_of_the_review": "The paper is overall promising but requires a substantial amount of improvements mainly in terms of clarity and evaluation.\nThe novelty is limited but that is not an issue if the approach is clearly described and shown to be improving the state of the art. The paper would be substantially better in the presence of a convergence analysis that does not assume iid data (e.g., based on bounded dissimilarity assumptions).\n\nThe overall recommendation is a weak reject given the weaknesses of the work that are only partly addressable (given the necessary effort) with high confidence.", "strength_and_weaknesses": "### Strengths\n\n- The problem of distribution shift across federated learning clients is very important. The idea of tackling it by combining decentralized with centralized training is both practical and promising.\n\n- The authors perform an empirical evaluation comparison based on 3 tasks with applications on federated learning.\n\n- The authors discuss the convergence of the proposed solutions.\n\n### Weaknesses\n\n- The paper needs improvement in terms of clarity (see detailed review below).\n\n- The convergence analysis assumes unbiased gradients (and thus iid distribution which is an invalid assumption on the federated learning setup). The authors also acknowledge this fact on their conclusion.\n\n- The proposed methods require additional hyperparameters (ηc, ηm).\n\n- The evaluation doesn't employ any baseline for the task of employing the centralized data (e.g., based on transfer learning).\n\n- The use case of bias mitigation (section 4.2) is interesting; however there is a questionable (in terms of practicality) assumption on the existence of a non-private representative dataset for a subset of the clients.\n\n- The paper does not assess the performance of the proposed methods in the presence of noise necessary to ensure differential privacy guarantees (given that federated learning on its own is not sufficient to provide strong privacy guarantees).\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "T778KTfEWM", "reviewer": "Reviewer_vzaj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a joint (mixed) FL strategy that jointly trains using a combination of centralized and federated models without transferring any data across server or client and vice versa. \n", "summary_of_the_review": "Overall, the proposed approach, mixedFL sounds decent, however, the presentation can be improved further and also, the comparison with the state-of-the-art FL algorithms might help position the paper better as to how the proposed modifications benefit w.r.t the more adanced FL optimization algorithms.", "strength_and_weaknesses": "# Pros:\n\n- The paper is well-written, easy to understand and follow along, however, I must admit that I did not pay an in depth attention to some of the theoretical analysis presented in section 5.\n\n- Literature is covered adequately and the proposed paper is presented amongst the body of knowledge while it also contributes to extend the existing knowledge in the domain.\n\n# Cons:\n\n- Where are the references to the works in literature that showed the techniques such as using some portion of data at server to train the server model after aggregation, next another work that showed the linear combination of server and client models. Of course they fall under the category of “sequential central-then-FL” category as opposed to the joint FL in this paper.\n\n- On page 2, “... large embedding table” is mentioned, does not make sense as to what it refers to at this point, it only makes sense after reading the contributions as one of the bullets talks about recommender systems. \n\n- Also, the footnote 1 is actually the real difference from the so called sequential FL coined here vs the joint FL proposed, make this clear from the abstract itself rather than undermining it in the footnote.\n\n- The notations in Algorithm 1 and 2 are never described but left for the reader to interpret. \n\n- After looking at the results in Fig 1 and Fig 2, what is the point of having three variations especially all the three proposed algorithms more or less converge to the same accuracies in most of the cases.\n\n- How movie recommendation embeddings are regularized is still unclear, please provide a formula on how this is done especially given the FL settings, even if the regularizations are there in literature. Maybe some reference to appendix also should make the concepts clear and how they play out in mixed FL.\n\n- The way the paper presentation flows is a bit odd from the regular style of paper writing or formatting. For example, section 2 (algorithms) comes first and then section 3 (related work), then section 5 (convergence) comes after experiments, why not swap section 2 and 3 then place 5 as 4 and then experiments and so on.\n\n- The empirical explanations in section 5.3 does not sound all that convincing, especially the trends of the Language modeling and movie recommendations are similar compared to the smile classification. The general common sense points to the fact that the celebA is custom partitioned and that probably is something to do with the observations in the paper. Did you rule that aspect out (or similar simple perspectives), before trying to prove the observations with such a complex empirical analysis?\n\n- The FL settings such as the number of clients, the generation of non-IID distributions, optimizers user, etc are not explained.\n\n- Also, the results show curves over a certain number of rounds that compare w.r.t the oracle. Obviously oracle has a single number, why not compare the end of training results with the oracle as well as the other state-of-the-art FL algorithms.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PuwKyxZYzTV", "reviewer": "Reviewer_nSLv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper focuses on a federated learning setting where there is a form of potentially high bias on the client-side (I use the work bias in the basic sense (i.e., favored towards to) instead of the pure statistical sense). These biases are exemplified by the datasets used by the paper, which come in the form of unbalanced labeling on client devices, and differences in the specification of client devices (i.e., high-end phones vs low-end phones). For these biases, the paper proposes to mix the datasets between the server (or datacenter) and the clients. Specifically, the paper uses two datasets:\n\n* CelebA: the dataset is partitioned into people who are \"smiling\" and who are \"not smiling.\" The claim is that the majority of pictures on people's phone are smiling. Here, the server contains the non-smiling pictures and the clients contain smiling pictures and the task is to predict smiling or not smiling.\n\n* StackOverflow and Wikipedia: the StackOverflow dataset is used for clients, and the Wikipedia dataset is used for the server.\n\nThe paper also proposes a mixed loss function, which is the sum of the loss on server data and the loss on client data.\n\n", "summary_of_the_review": "The proposed idea and presentation require more work.\n\nUpdate: Thank you to the authors for their reply. I will maintain my review.", "strength_and_weaknesses": "In Section 2 Algorithms, it would be more helpful to explain the notation used and the various components in the two algorithms in this section rather than relegating details to the appendix. Additionally, it is not clear to me what the components ClientOptimizer, ServerOptimizer, CentralOptimizer, and MergerOptimizer in this context are, what each performs (they appear to be blackbox functions), how they relate to equation (1), and how they connect to Section 5.\n\nThe rationale on the StackOverflow and Wikipedia (and the allocation of 25% server, 75% client) dataset as it pertains to client devices is not thoroughly explained in the experimental section.\n\nSection 4.3 as it pertains to \"mixing different loss\" and to the focus of the paper is not clear to me.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "GAI-H74xSuA", "reviewer": "Reviewer_YiaD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "To mitigate distribution shift and improve FL performance in inference scenarios, the paper proposes the Mixed FL, which adds centralized data to the server and co-trains a powerful and robust global model between clients and the server. And the 1/2-way gradient transfer could work to alleviate the influence caused by non-iid data. Thus, the model could perform better facing unfamiliar datasets with different distributions compared with clients' local datasets. Many experiments have been conducted to validate their algorithms in different domain tasks. Related theoretical explanations are provided for the convergence. \n", "summary_of_the_review": "Overall, this work constructs a well-established algorithm for mixed FL. But some of its ideas are not very novel. This algorithm is more like integrating some existing technologies, such as compute offloading and gradient transferring. However, the experimental part is fully carried out, which can reflect the effectiveness of the algorithm. Moreover, the related theoretical proof is also relatively solid, although there are still some limitations. Again, further revisions are still required in the organization and presentation of some paragraphs.\n", "strength_and_weaknesses": "Strengths:\n1. The general algorithm of Mixed FL is well constructed and seems valid.\n2. The relevant experiments are relatively sufficient and able to reflect the effectiveness of proposed algorithm.\n\nWeakness:\n1.In 2-WAY GRADIENT TRANSFER, the client's gradient information will be passed to the server. However, issues related to data privacy during gradient tranmission do not appear to be explored in the paper.\n2. Some technique behind the algorithm may not be that novel, such as computation offloading and gradient augmentation.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject