Federated Reconstruction: Partially Local Federated Learning
Authors: Karan Singhal
Hakim Sidahmed
Zachary Garrett
Shanshan Wu
J Keith Rush
Sushant Prakash
Venue: NeurIPS 2021 Poster (2021)
Keywords: federated learning
distributed computing

Abstract: Personalization methods in federated learning aim to balance the benefits of federated and local training for data availability, communication cost, and robustness to client heterogeneity. Approaches that require clients to communicate all model parameters can be undesirable due to privacy and communication constraints. Other approaches require always-available or stateful clients, impractical in large-scale cross-device settings. We introduce Federated Reconstruction, the first model-agnostic framework for partially local federated learning suitable for training and inference at scale. We motivate the framework via a connection to model-agnostic meta learning, empirically demonstrate its performance over existing approaches for collaborative filtering and next word prediction, and release an open-source library for evaluating approaches in this setting. We also describe the successful deployment of this approach at scale for federated collaborative filtering in a mobile keyboard application.

Federated Reconstruction: Partially Local Federated Learning
Karan Singhal Google Research taransinghaa@ggogll..
Hakim Sidahmed
Zachary Garrett Google Research zachgarrett@google. com
Google Research heiidahmed@google.coo
Shanshan Wu
Keith Rush
Sushant Prakash Google Research sush@google. com
Google Research
Google Research
shanshanv@google. com
krush@google.com com
Abstract
Personalization methods in federated learning aim to balance the benefits of feder- ated and local training for data availability, communication cost, and robustness to client heterogeneity. Approaches that require clients to communicate all model parameters be undesirable due to privacy and communication constraints. Other approaches require always-available or stateful clients, impractical in large-scale cross-device settings. We introduce Federated Reconstruction, the first model- agnostic framework for partially local federated learning suitable for training and inference at scale. We motivate the framework via connection to aggostic meta learning, empirically demonstrate its performance over existing approaches for collaborative filtering and next word prediction, and release an open- open-source library for evaluating approaches in this setting. We also describe the successful deployment of this approach scale for federated collaborative filtering in mobile keyboard application.
1 Introduction
Federated learning is a machine learning setting in which distributed clients solve a learning objective on sensitive data via communication with coordinating server [44]. Typically, clients collaborate train a single global model under an objective that combines heterogeneous local client objectives. For example, clients may collaborate to train next word prediction model for mobile keyboard application without sharing sensitive typing data with other clients or a centralized server [28]. This paradigm has been scaled production and deployed in cross-device settings [3, 28, 56] and cross-silo settings [11. 13].
However, training fully global federated model may not always be ideal due to heterogeneity in clients' data distributions. Yu et al. [58] show that global models can perform worse than purely local (non-federated) models for many clients (e.g., those with many training examples). Moreover, in some settings privacy constraints completely prohibit fully global federated training. For instance, for models with user-specific embeddings, such matrix factorization models for collaborative filtering [37], naively training a global federated model involves sending updates to user embeddings on the server, directly revealing potentially sensitive individual preferences [21, 47].
To address this, we explore partially local federated learning. this setting, models are partitioned into global and local parameters such that local parameters never leave client devices. This enables training on sensitive user-specific parameters as in the collaborative filtering setting, and we show also improve robustness to client data heterogeneity and communication cost for other settings,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Server
Client t
Reconstruct
g
git)
((c)
gt
1(4)
g
g
Updatee
Comb ine
Figure 1: Schematic of Federated Reconstruction. Model variables partitioned into global and local variables. For every round t, each participating client is sent the current global variables, uses them reconstruct its own local variables, and then updates its copy of the global variables. The server aggregates updates to only the global variables across clients.
since we are effectively interpolating between local and federated training. Previous works have looked similar settings [4, 41]. Importantly, these approaches cannot realistically be applied at scale in cross-device settings because they assume clients are stateful or always-available: in practice, clients are sampled from an enormous population with unreliable availability, so approaches that rely repeated sampling of the same stateful clients are impractical (Kairouz et al. [34] [Table IJ). Other work has demonstrated that stateful federated algorithms partial participation regimes can perform worse than stateless algorithms due the state becoming "stale" [48]. Previous methods also do not enable inference on new clients unseen during training, preventing worldworld deployment.
These limitations motivate new method for partially local federated learning, balancing the benefits of federated aggregation and local training. This approach should be:
1. Model-agnostic: works with any model.
2. Scalable: compatible with large-scale cross-device training with partial participation.
3. Practical for inference: new clients can perform inference.
4. Fast: clients can quickly adapt local parameters their personal data.
In this work, we propose combining federated training of global parameters with reconstruction of local parameters (see Figure 1). We show that method relaxes the statefulness requirement of previous work and enables fast personalization for unseen clients without additional communication, for models without user-specific emheddings.
Our contributions: We make the following key contributions:
Introduce model-agnostic framework for training partially local and partially global models, satisfying the above criteria. We propose practical algorithm instantiating this framework (FEDRECON).
Justify the algorithm via connection to model-agnostic meta learning (see Section 4.2), showing that FEDRECON naturally leads to fast reconstruction at test time (see Table 1).
Demonstrate FEDRECON's 's empirical performance over existing approaches for applications in collaborative filtering and next word prediction, showing that our method outperforms standard centralized and federated training in performance on unseen clients (see Table 1), enables fast adaptation to clients' personal data (see Figure 3), and matches the performance of other federated personalization techniques with less communication (see Figure 2).
Release open-source source library for evaluating algorithms across tasks in this setting."
Describe the successful deployment of this approach scale for collaborative filtering real-world mobile keyboard application (see Section 7).
2 Related Work
Previous works have explored personalization of federated models via finetuning [52, 58], meta learning / bi-level optimization [10, 16, 18, 33), and model interpolation [14, 27, 43]. Some works aim improve training convergence with heterogeneous client gradient updates [35, 39], while
htcp::///gt...bbteeertdd...

---

others address client resource heterogeneity [15, 49]. All of these approaches require communicating all client parameters during training, which can be unreasonable due to privacy and communication constraints for some models (discussed further in Section 3), which motivates methods that aggregate only part of a model as in our work.
Arivazhagan et al. [4] and Liang et al. [41] aggregate part of a model, but these approaches do not meet the criteria from Section Similar to other works proposing local parameters [22, 31, 40], both approaches require clients to maintain local models across rounds, which is problematic when sampling clients from large populations (criterion 2). Arivazhagan et al. [4] assumes that all clients are available for training at all times and do not propose method for performing inference on new clients (criterion 3). Liang et al. [41] requires new inference clients to be able to ensemble the outputs of all other clients' local models to evaluate on new data, which is unrealistic in practice due to communication and privacy constraints (criterion 3). These constraints are crucial: with previous methods most clients do not have a practical way to perform inference. Previous methods were also proposed for specific model types (criterion 1): Arivazhagan et al. [4] explores personalization layers after shared base layers and Liang et al. [41] learns personal representations of local data. Finally, as we discuss in Section 4.2, our method optimizes a meta learning objective for training global parameters that lead to fast reconstruction (criterion 4).
Federated Collaborative Filtering: We evaluate our approach on collaborative filtering [37] in Section 5.1.1. Prior work has explored federated matrix factorization: Ammad-Ud Ud-Din et al. [2] avoids sending the user matrix the server by storing locally, aggregating only the item matrix globally. Chai et al. [9] applies homomorphic encryption to aggregation of the item matrix. Flanagan et al. [20] studies federated collaborative filtering as a multi-view learning problem. Each approach requires clients to maintain state, unlike our method. Ammad-Ud-Din also do not address the problem of inference on unseen users.
Ud-Din et al. [2] and Chai et al. [9]
Federated Meta Learning: Our approach is motivated by a connection to meta learning, described in Section 4.2. Other federated learning works have also established connections to meta learning: Jiang et al. [33] observed that training global federated model that can be easily personalized via finetuning can be studied in the model-agnostic meta learning (MAML) framework [19], and FEDAVG is performing the distributed version of the REPTILE meta learning algorithm presented by Nichol et al. [46]. Chen et al. [10], Fallah al. [18], and Lin et al. [42] apply the MA algorithm and variants in federated settings. Khodak et al. [36] aims to improve upon these methods by learning
client similarities adaptively. These methods do not address the partially local federated learning
setting, where some parameters are not aggregated globally.
3 Partially Local Federated Learning
Typically, federated learning of a global model optimizes: min
F(x) [x))
XER
where fx) EgED, [x), is the local objective for client i, x is the d-dimensional model parameter vector, P is the distribution of clients, and { is a data sample drawn from client i's data Dj- In practical drosse settings, fx( may be highly heterogeneous for different i, and the number of available clients may be large and constantly changing due to partial availability. Only a relatively small fraction of clients may be sampled for training.
To motivate partially local federated learning, we begin by considering models that can be partitioned into user-specific parameters and non-user-specific parameters. An example is matrix factorization in the collaborative filtering setting [30, 37]: in this scenario, a ratings matrix R E R / representing user preferences is factorized into user matrix P E U and an items matrix Q E R K such that ~e PQ" where U is the number of users and is the number of items. For each user u, this approach yields K Kddimensional user-specific embedding P..
To train this type of model in the federated setting, we cannot naively use the popular FEDAVG algorithm [44] or other (personalized) algorithms that involving aggregation of all model parameters. simple application of global learning algorithms might require every client to be sent every other client's personal parameters, which is clearly unreasonable for both privacy and communication. more sophisticated approach might be to have each client communicate only their own personal parameters with the server. In this case, the server still has access to individual user parameters,
3

---

Algorithm 1 Federated Reconstruction Training
set global parameters G. set of local parameters L, dataset split function S, reconstruction algorithm R, client update algorithm U
Input:
Server executes:
g00) < (initialize G)
ClientUpdate:
for each round do
(D.,. Dog)) t S(D,)
((0) +- (randomly sample m clients)
(00) + R(D r, L. (
for each client s(t) in parallel do
(t) + U UD (Di,g 1, ,g(())
(A!) ..) + ClientUpdate((,, (d g
9;
A t Di
(1)
(t)
end for
n = =Eiest) n4:
n4 t IDiggl
return A n4 to the server
g((+1) + (0) + 1/4 EiEso n A
end for
which in this setting can be trivially used to recover sensitive user-item affinities, negating the privacy benefit of not centralizing the data (again unreasonable).
Thus a practical federated learning algorithm for this setting should be partially local: it should enable clients to train a subset of parameters entirely on-device. However, approaches that involve stateful clients storing their local parameters across rounds are undesirable in large-scale cross-device settings since clients are unlikely to be sampled repeatedly, causing state to be infrequently available and become stale, degrading performance (Reddi et al. [48] [Sec. 5.1]). Additionally, since only a fraction of clients participate in training, all other clients will be left without trained local parameters, preventing them from performing inference using the model. In a large population setting with hundreds of millions of clients as described in Section 7, this can mean 99%+ of clients do not have complete model, preventing practical deployment. Thus an algorithm for this setting ideally should not depend on stateful clients and should provide way to perform inference unseen clients.
Though we have motivated partially local federated learning via setting that contains privacy- sensitive user-specific parameters, we will later show that this paradigm can also improve robustness to heterogeneity in fx) and reduce communication cost, even for models without user-specific parameters. In this case, the partition between local and global parameters is determined by the use-case and communication limitations. As an example, Section 5.1.2 we motivate a next word prediction use-case, where having partially local model can be useful for handling diverse client inputs while reducing communication.
Achieving partially local federated learning in a practical cross-device setting with large, changing client distribution P and stateless clients one of the key contributions of our work.
4 Federated Reconstruction
We now introduce the Federated Reconstruction framework. One the key insights of our approach is that we can relax the requirement for clients to maintain local parameters across rounds by reconstructing local parameters whenever needed, running a reconstruction algorithm to recover them. Once client is finished participating in round, it can discard its reconstructed local parameters. An overview is presented in Figure
Federated Reconstruction training is presented in Algorithm 1. Training proceeds as follows: for each round f, the server sends the current global parameters gf* to each selected client. Selected clients split their local data D; into a support set D.,, and a query set D..q. Each client uses its support set Di, and (*) as inputs to reconstruction algorithm R to produce its local parameters 1(0) Then each
client then uses its query set Di.q. its local parameters r(() and the global parameters (()) as inputs to update algorithm U to produce updated global parameters (²) Finally, the server aggregates updates to global parameters across clients. We describe key steps in further detail below.
Dataset Split Step: Clients apply dataset split function S to their datasets D, to produce support set Dr,s used for reconstruction and a query set Di,g used for updating global parameters. Typically these sets are disjoint to maximize the mntaa-eenrallzzation ability of the model (see Section 4.2), but

---

in Appendix D we show that this assumption may be relaxed if clients don't have sufficient data to partition.
Client Reconstruction Step: Reconstruction of local parameters is performed by algorithm R. Though this algorithm can take other forms, in this work we instantiate R as performing k, local gradient descent steps on initialized local parameters with the global parameters frozen, using the support set a.... We show in Section 4.2 this naturally optimizes a well-motivated meta learning ob- jective, Interestingly, this approach is related to gradient-based alternating minimization, a historically successful method for training factored models [26, 32].
A potential concern with reconstruction is that this may lead to additional client computation cost compared storing local parameters clients. However, since clients unlikely to be reached repeatedly by large-scale cross-device training. in practice this cost similar to the cost of initializing these local parameters and training them with stateful clients. Additionally, reconstruction provides natural way for new clients unseen during training to produce their own partially local models offline (see Section -wtthuut this step, the vast majority of clients would not be able to use the model. Finally, in Section 4.2 we argue and in Section 5.2 we empirically demonstrate that with our approach just one local gradient descent step can yield successful reconstruction because global parameters being trained for fast reconstruction of local parameters.
Client Update Step: Client updates of global parameters are performed by update algorithm U. In this work we instantiate U as performing ky local gradient descent steps on the global parameters, using the query set Di.g-
Server Update Step: We build on the generalized FEDAVG formulation proposed by Reddi et al. [48], treating aggregated global parameter updates as an "antigradient" that can be input into different server optimizers (SGD is shown in Algorithm 1). Note that the server update operates on a weighted average of client updates in McMahan et al. [44], weighted by n, = -D.pl-
We refer to the instantiation of this framework outlined here as FEDRECON below, We address frequently asked questions about FEDRECON and partially local federated learning in Appendix A.
4.1 Evaluation and Inference
To make predictions with global variables g learned using Algorithm 1, clients can naturally recon- struct their local models just they do during training, by using R, g. and Di,- produce local parameters 1. Then and / combined make up a fully trained partially local model, which can be evaluated on Di.-- We refer this evaluation approach RECONEVAT. below. Note that this be applied to clients unseen during training (most clients in large-scale settings), enabling inference for these clients.?
Reconstruction for inference is performed offline, independently of any federated process, so clients can perform reconstruction once and store local parameters for repeated use, optionally refreshing them periodically if they have new local data.
4.2 Connection to Meta Learning
Our framework is naturally motivated via meta learning. Given that RECONEVAL involves clients do- ing (gradient-based) reconstruction using global parameters, we ask: Can we train global parameters conducive to fast reconstruction of local parameters?
We can easily formulate this question in the language of model-agnostic meta learning [19]. The heterogeneous client distribution P corresponds the heterogeneous distribution of tasks; each round (episode) we sample a batch of clients in the hope of meta- geetaageneralziing to unseen clients. Each client has a support dataset for reconstruction and query dataset for global parameter updates. Our meta- parameters are g and our task-specific parameters are 1, for client i. We want to find minimizing the objective:
EnpP filg (44) Eqpp filg R(D L.9)
In this work we focus on new clients that have some local data for reconstruction; our method can be easily extended to learn a global default for the local parameters. We also show that skipping reconstruction can be reasonable for some tasks in Section 5.2.
5

---

where 9 || 4 denotes the concatenation of g and 4 and
BgED.,, [filg 44,
In Appendix B show that the instantiation of our framework where R performs k, 2 steps of gradient descent on initialized local parameters using Di.s and U performs K. = 1 step of gradient descent using Di.g y is already minimizing the first-order terms in this objective (ie.. this version of FEDRECON is performing first-order meta learning). Intuitively, reconstruction corresponds to the MAML "inner loop" and the global parameter update corresponds the "outer loop"; we test the same way we train (via reconstruction), a common pattern in meta learning.
Thus FEDRECON trains global parameters g for fast reconstruction of local parameters I, enabling partially local federated learning without requiring clients to maintain state. In Section 5.2 we observe that our method empirically produces g more conducive fast, performant reconstruction unseen clients than standard centralized or federated training (e.g., see S RECONNEAL vs. FEDRECON in Table 1). We see in Figure 3 that just one reconstruction step is sufficient to recover the majority of performance.
Experimental Evaluation
5.1 Tasks and Methods
We next describe experiments validating FEDRECON on matrix factorization and next word prediction. We aim to determine whether reconstruction can enable practical partially local federated learning with fast personalization for new clients, including in settings without user-specific embeddings.
5.1.1 Matrix Factorization
We evaluate on federated matrix factorization using the popular MovieLens IM collaborative filtering dataset [29]. We perform two kinds of evaluation:
1. STANDARDEVAL on seen users, those users who participated in at least one round of federated training. We split each user's ratings into 80% train, 10% validation, and 10% test by timestamp. We train on all users' train ratings, and report results on users test ratings.
2. RECONEVAL on wnseen users, those users who did not participate at all during federated training. We split the users randomly into 80% train, 10% validation, and 10% test; we train with the train users and report results on test users.
The model learns P and Q such that R R PQT as discussed in Section 3, with embedding dimen- sionality K 50. We apply FEDRECON with local user embeddings P, and global item matrix Q. We report coot-mean-squar-onnee training. FEDAVG, and FEDRECON Table See also Appendix C. for more details on the dataset, model, and hyperparameter choices.
(RMSE) and rating prediction accuracy. We compare centralized
5.1.2 Next Word Prediction
We also aim to determine whether Federated Reconstruction can be successfully applied in settings without user-specific embeddings to improve robustness to client heterogeneity and communication cost, since our approach agnostic to which parameters are chosen as local/global. We apply FEDRECON to next word prediction because the task provides natural motivation for personalization: different clients often have highly heterogeneous data, e.g,, they use different slang, but language models typically have fixed vocabulary. We propose improving the ability of a language model to capture diverse inputs using local vocabulayy (OOV) embeddings. OOV embeddings are a common application of the hashing trick [54] in deep learning; combining them with FEDRECON enables language models to effectively allow for personal input vocabularies for different clients. For example, if client frequently uses OOV token t, and client uses OOV token f,, each client's ss corresponding local OOV embedding can learn to reflect this (even if the OOV embeddings collide). So adding local OOV embeddings with the core global vocabulary fixed can lead to improved personalization without more communication per round; we will also show that we can reduce the size of the core model (reducing communication) and get further benefits.
We perform next word prediction with the federated Stack Overflow dataset introduced TensorFlow [51]. We use an LSTM model and process data similarly to Reddi et al. [48], comparing to their best

---

Table 1: Movielens matrix factorization squt-ee error (lower is better) and rating prediction accuracy (higher better). STANDARDEVAL is on seen users, RECONEVAL, on held-out users. Results within 2% of best for each metric are in bold.
RMSE + ACCURACY 1
CENTRALIZED STANDARD EVAL
.933
43.2
CENTRALIZED + RECONEVAL FEDAVG STANDARD EVAL
1.36
40.8
.939
41.5
FEDAVG RECONEVAL
.934
40.0
FEDRECON (OURS)
.907
43.3
Table 2: Stack Overflow next word prediction accuracy and communication per round, per client. FEDYOGI and OOV/FULL FINETUNING require communication of all model parameters, FE- DRECON does not (see Figure 2). Results within 2% of best for each vocabulary size are bold.
VOCAB. SIZE
1K
5K
10K
COMMUNICATION
FEDYOGI
24.3
26.3
26.7
2/4
+ 2
FEDRECON (I (OV)
24.1
26.2
26.4
2 gg
FEDRECON (500 OOV)
29.6
28.1
27.7
2
OOV FINETUNING (500 OOV)
30.0
28.1
27.9
2/1
2/g
FULL FINETUNING (500 OOV)
30.8
29.2
28.8
2/
FEDRECON+ (500 OOV)
30.7
28.9
28.6
2g
FEDYOGT result. To demonstrate that reconstruction can be used to reduce model size, we describe experiments with vocabulary sizes [1000, 5000, 10,000). See Appendix C.2 for details on the dataset, model, and hyperparameter choices.
5.2 Results and Discussion
In Tables and we present results for matrix factorization and next word prediction for FEDRECON and baselines. We call out several key comparisons below: more results can be found in Appendix D.
For the MovieLens task FEDRECON able match the performance of CENTRALIZED STANDARD EVAL despite performing a more difficult task: as described in Section 5.1.1, FEDRECON is using RECONEVAL to evaluate evaluating. As is typical for server server-trained matrix factorization models, CENTRALIZED + STANDARD EVAL is only being evaluated on held-out ratings for seen users. Note that would not be able to evaluate on unseen users since they do not have trained user embeddings (randomly initializing them embeddings for unseen
held-out users, reconstructing
embeddings for them and then
produces garbage results). If reconstruct in CENTRALIZED + RECONEVAL (we argue this is a fairer comparison with FEDRECON), we see that performance significantly worse than FEDRECON and server-evaluation on seen users. One interesting finding was that the results of this seemed to vary widely across different users, with some users reconstructing embeddings no better than random initialization, while most others reconstructed better embeddings." We see a similar result with FEDAVG for the MovieLens task, where FEDAVG with standard evaluation on seen users" performs bit worse than CENTRALIZED STANDARD EVAL, and performance for RECONEVAL indicates that FEDRECON is doing better job of training global parameters so they can reconstruct local parameters than other approaches, motivated in Section 4.2. Moreover, FEDRECON is doing this despite not having direct access the data or the user-speeific parameters-enabling this approach in settings where centralized training FEDAVG is impossible.
and then evaluate as
unseen users is significantly worse than FEDRECON, This
'For this experiment, we repeat 500 times: sample 50 clients each time and perform RECONEVAL, reporting average metrics. Across runs, we observe large standard deviations of 1.7% accuracy (absolute) and 0.53 RMSE. *Note that this task, FEDAYG equivalent result the stateful FEDPER approach Arivazhagan [4], since each client only updates its own user embedding. The user embeddings are stored on the server here, but this does not affect the result. Performance reduction may be caused by user embeddings getting "stale" across rounds which may occur when stateful algorithms are applied in cross-device FL, Appendix A.
7

---

0.30
0.25
0.20
Accurscy
FedRacon Finetune
0.10
Pedikecon (Durs) 300 OUV
Full Pinetuning 500 OCV
2.05
Fiscturing DOV
PedYogt
100
200
500
400
500
Total Parameters Communicated (in billions)
Figure 2: Accuracy as a function of total parameters communicated across all clients for FEDRECON and baselines for Stack Overflow next word prediction.
Relative Accuracy
Relative Accuracy
MovieLens
0.9
SlackOverflow 1K Vocab
0.25
SlackOverflow 5K Vocab
StackOverflow 10K Vacab
0.00
4
10
0
2
10
Reconstruction Steps
Client Update Steps
Figure 3: Accuracy compared to base FEDRECON when varying the number of reconstruction steps for local parameters (left plot) and client update steps for global parameters (right plot).
In the first section of the Stack Overflow results in Table 2, we compare FEDYOGI (an adaptive variant of FEDAVG introduced by Reddi al. [48] with FEDRECON, showing that enabling FEDRECON with 500 local OOV embeddings significantly boosts accuracy for every vocabulary size. Interestingly, observe that accuracy actually improves for smaller vocabulary sizes for FEDRECON (500 OOV), whereas the reverse holds for FEDYOGI and FEDRECON (1 OOV). We posit that this is because decreasing the vocabulary size effectively increases the amount of "training data" available for the local part of the model, since OOV embeddings are only used (and trained) when tokens are out-of- vocabulary: this is useful only when the local part of the model has sufficient capacity via the number of OOV embeddings. This hypothesis is consistent with vocabulary coverage: 10K vocabulary covers 86.9% of the tokens the dataset, a 5K vocabulary covers 80. %, and 1K vocabulary covers 49.2%; we see that difference in results for FEDRECON (500 OOV) is greater between IK and 5K than between 5K and 10K. We caution that reducing vocabulary size may undesirable in some cases: reducing the size of the vocabulary also restricts the output tokens of the model.
Comparing with Finetuning: In Table we compare FEDRECON with FINETUNING [52, 58] to study whether reconstruction can provide similar benefits as global personalization methods. In our implementation we train a fully global model using FEDYOGI, perform local gradient steps to finetune part of the model using the support set, and then evaluate on the query set (same sets as used for FEDRECON). For OOV FINETUNING, the OOV parameters only are finetuned using the support set (comparable to FEDRECON), and for FULL FINETUNING all parameters are finetuned. Comparing FEDRECON (500 OOV) and OOV FINETUNING, we see that reconstructing local embeddings performs similarly to finetuning pre-trained OOV embeddings, despite FEDRECON not communicating the local parameters / to the server. FULL FINETUNING from Table 2 achieves better accuracy since all parameters are finetuned. To compare this fairly with reconstruction, we perform FEDRECON+ BEDRRECO+FFIETUNNE where the support set is used first to reconstruct local parameters and then to finetune global parameters before evaluation. We also see that can get comparable results, indicating that reconstruction can enable personalization on (potentially privacy -sessiive))) local parameters while reducing communication. See Figure for comparison of different approaches by the total number of parameters communicated-ve we see an advantage for FEDRECON, particularly for lower total communication.
Varying Reconstruction Steps: Section 4.2 we described connection between our framework and MAML [19], which has been a successful paradigm for fast adaptation to tasks with few steps. In Figure 3 we perform FEDRECON for varying numbers of reconstruction steps k,, E [0. 2, 5, 10) and plot the accuracy as fraction of accuracy across tasks from Tables and 2. We see that

---

for zero reconstruction steps (an ablation skipping reconstruction), MovieLens accuracy is 0.0, as expected (all user embeddings are randomly initialized). Relative accuracy for Stack Overflow NWP settings remains above 90%, suggesting that for this task clients can still perform inference with FEDRECON-trainee model even without any data to reconstruct. Importantly, just one reconstruction step is required to recover the majority of remaining performance across both tasks, indicating that FEDRECON learns global parameters conducive to fast reconstruction.
Varying Client Update Steps: In Section 4.2 we showed that gradient-based FEDRECON, involving k, 2 reconstruction steps and l. 1 client update steps, is minimizing a first-order meta learning objective for training global parameters that yield good reconstructions. In Figure 3 we perform FEDRECON with ky [1. 5, 10] and compute relative accuracy as fraction of accuracy across tasks from Tables 1 and 2. For each experiment we run for a fixed number of rounds. We see that 1 step recovers almost all of the accuracy and adding more steps gradually increases accuracy further. Interestingly, we observe that for k, = 1 training proceeds significantly slower than for other values such that performance is still slightly increasing after the fixed number of rounds. This analogous to the difference between FEDAVG and FEDSGD [44]. While FEDSGD is optimizing the original learning objective, FEDAVG often achieves similar performance significantly fewer rounds by adding multiple gradient steps aggregated parameters.
We present further baselines and ablations in Appendix D.
6 Open-Source Library
We are releasing a code framework for expressing and evaluating practical partially local federated models built on the popular TensorFlow Federated library [50]. The code is released under Apache License 2.0. In addition to allowing for easy reproduction of our experiments, the framework provides flexible, well-documented interface for researchers and modelers to run simulations in this setting with models and tasks of their choice. Users can take any existing Keras model and plug it into this framework with just few lines of code. We provide libraries for training and evaluation for MovieLens matrix factorization and Stack Overflow next word prediction, which can be easily extended for new tasks. We hope that the release of this framework spurs further research and lowers the barrier to more practical applications.
7 Deployment in a Mobile Keyboard Application
key differentiator of our method is that it scales to practical training and inference in cross-device settings with large populations. To validate this, we deployed FEDRECON to a mobile keyboard application with hundreds of millions of federated learning clients. We used a system similar to Bonawitz et al. [7] to deploy FEDRECON for training. Note that the system does not support stateful clients given the issues with large-scale stateful training described in Section 4, stateless approach was necessary for deployment.
Users of the mobile keyboard application often use expressions (GIFs, stickers) to communicate with others in egg., chat applications. Different users are highly heterogeneous in the style of expressions they use, which makes the problem natural fit for collaborative filtering to predict new expressions user might want to share. We trained matrix factorization models as described in Section 5.1.1, where the number of items ranged from hundreds to tens of thousands depending on the type of expression.
Training in production brought challenges due to data sparsity. Depending on the task, some clients had very few examples, if e.g., they didn't 't commonly share stickers via the keyboard application. To ensure clients with just one example weren't it just adding noise to the training process by participating. we oversampled clients and filtered out the contributions of clients without at least some number of examples. We reused examples between the support and query sets as described in Appendix D to ensure all examples were used for both reconstruction and global updates.
Another practical challenge we faced was orthogonal to our method and commonly faced in real- world federated learning applications: heterogeneity in client resources and availability meant that some participating clients would drop out before sending updates to the server. We found that the simple strategy of oversampling clients and neglecting updates from dropped-out clients appeared to

---

perform well, but we believe studying the faimess implications of this is valuable area for future work.
After successful training, the resulting model was deployed for inference in predicting potential new expressions
might share, which led to increase of 29.3% in expression recommendations. We hope that this successful deployment of FEDRECON demonstrates the practicality of our approach and leads the way for further real-world applications.
for
8 Conclusion
We introduced Federated Reconstruction, model-agnostic framework for fast partially local federated learning suitable for training and inference at scale. We justified FEDRECON via a connection to meta learning and empirically validated the algorithm for collaborative filtering and next message prediction, showing that can improve performance on unseen clients and enable fast personalization with less communication. We also released an spen-source library for partially local federated learning and described successful production deployment. Future work may explore the optimal balance of local and global parameters and the application of differential privacy to global parameters (see Appendix E).
Acknowledgments and Disclosure of Funding
We thank Brendan McMahan, Lin Ning, Zachary Charles, Warren Morningstar, Daniel Ramage, Jakub Konečný, Blaise Agūera y Arcas, and Jay Yagnik from Google Research for their helpful comments and discussions. We also thank Wei Li, Matt Newton, and Yang Lu for their collaboration towards deployment.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. 2016. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 308-318.
[2] Muhammad Ammad-Ud-Din, Elena Ivannikova, Suleiman A Khan, Were Oyomno, Qiang Fu, Kuan Eeik Tan, and Adrian Flanagan. 2019. Federated Collaborative Filtering for Privacy- Preserving Personalized Recommendation System. arXiv preprint
(2019).
[3] Apple. 2019. Designing for Privacy (video and slide deck). Apple WWDC, https:
//developer.apppepeeeoo apple. httpleeccm/vvieos wwwddddsspla//wwwcccce hptp:///ccl//1////////0/0
[4] Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. 2019. Federated learning with personalization layers. arXiv preprint 1912v:992.0008 (2019).
[5] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. 2019. Private Stochastic Convex Optimization with Optimal Rates. CoRR 0tbs/1908.0999 (2019). 10XXvv1908.0999 http://arxiv orgooog////o att///bss//90// 09970
[6] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. 2014. Private Empirical Risk Min- imization, Revisited. CoRR abs/1403 405.7085 (2014). arXiv:1405.77 http://arxiv.ct org/ abs/1405.7088
[7] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp. Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, H Brendan McMahan, et al. 2019. Towards federated learning at scale: System design. arXiv preprint arXiv: 1902.01044 (2019).
[8] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2017. Practical secure aggregation for
machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 1175-1191.
[9] Di Chai, Leye Wang, Kai Chen, and Qiang Yang. 2020. Secure federated matrix factorization. IEEE Intelligent Systems (2020).
10

---

[10] Fei Chen, Mi Luo, Zhenhua Dong, Zhenguo Li, and Xiuqiang He. 2018. Federated meta-
learning with fast convergence and efficient communication. arXiv preprint arXiv:1802.0787 (2018).
[11] NVIDIA Clara. 2019. The Clara Training Framework Authors. nvidia. com/ clara
https://devveloerr:
[12] Creative Commons. 2002.
Attrbution-ShareAlikk 3.0 Unported.
https://
creativecommons. org /ww./esee//yysa//3....
[13] Walter de Brouwer. 2019. The Federated Future is ready for shipping. https://doc.aii ai/
blog/federated-tune future reader saaeddy-hippingg..
[14] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi, 2020. Adaptive Personalized Federated Learning. arXiv preprint arXiv:2003.13460 (2020).
[15] Enmao Diao, Jie Ding, and Vahid Tarokh. 2020. HeteroFL:
Computation and communication efficient federated learning for heterogeneous clients. arXiv preprint arXiv:2010.01 (2020).
[16] Canh T Dinh, Nguyen H Tran, and Tuan Dung Nguyen. 2020. Personalized federated learning with Moreau envelopes. arXiv preprint arXiv:2006. 08848 (2020).
[17] Cynthia Dwork, Aaron Roth, al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science 9, 3-4 (2014), 211-407.
[18] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar 2020. Personalized federated learning: meta-learning approach. arXiv preprint (/XXi::0002.0748 (2020).
[19] Chelsea Finn, Pieter Abbeel, and Sergey Levine. 2017. Model-agnostic meta-learning for fast adaptation of deep networks, arXiv preprint
(2017).
[20] Adrian Flanagan, Were Oyomno, Alexander Grigorievskiy, Kuan Eeik Tan, Suleiman A Khan, and Muhammad Ammad-Ud-Din 2020. Federated Multi-view Matrix Factorization for Person- alized Recommendations. arXiv preprint arXiv:2004.0m 24424220000042256 (2020).
[21] Dashan Gao, Ben Tan, Ju, Vincent W Zheng, and Qiang Yang. 2020. Privacy Threats Against Federated Matrix Factorization. arXiv preprint arXiv:2007.01587 (2020).
[22] Suyu Ge, Fangzhao Wu, Chuhan Wu, Tao Qi, Yongfeng Huang, and Xing Xie. 2020. Fedner: Privacy-preserving medical named entity recognition with federated learning, arXiv preprint arXiv:2003.09288 (2020).
[23] Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. 2020. In- verting Gradients- How easy is it to break privacy in federated learning? arXiv preprint arXiv:2003. 14053 (2020).
[24] Robin C Geyer, Tassilo Klein, and Moin Nabi. 2017. Differentially private federated learning: A client level perspective. arXiv preprint arXiv:/7/2.07555 (2017).
[25] GroupLenns 2015. MovieLens 1M License. https://files. http:s///tlees.groppleessss org datasetas
movielens/me mm// 1mmmmmm-mmmmmm--mmm-----------m- Sem.-REEEEEEE... txt
[26] Asela Gunawardana, William Byrne, and Michael Jordan. 2005. Convergence Theorems for Generalized Alternating Minimization Procedures. Journal of machine learning research 6, 12 (2005).
[27] Filip Hanzely and Peter Richtárik. 2020. Federated learning of mixture of global and local models. arXiv preprint XXXv:2002.05516 (2020).
[28] Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. 2018. Federated learning for mobile keyboard prediction. arXiv preprint 18/ 1.03604 (2018).
[29] Maxwell Harper and Joseph Konstan. 2015. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis) 5, 4 (2015), 1-19.
11

---

[30] Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative filtering for implicit feedback datasets. 2008 Eighth IEEE International Conference on Data Mining. Icee, 263-272.
[31]
Yutao Huang, Lingyang Chu, Zirui Zhou, Lanjun Wang. Jiangehuan Liu, Jian Pei, and Yong Zhang. 2021. Personalized cross-silo federated learning on non-iid data. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 7865-7873.
[32] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. 2013. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth anmual ACM symposium on Theory of computing. 665-674.
[33] Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. 2019. Improving federated learning personalization via model agnostic meta learning. arXiv preprint arXiv: 1909. 12488 (2019).
[34] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. 2019. Advances and open problems federated learning. arXiv preprint 1rXiv:1912.04997 (2019).
[35] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. 2020. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning. PMLR, 5132-5143.
[36] Mikhail Khodak, Maria-Florina F Balcan, and Ameet S Talwalkar. 2019. Adaptive gradient- based meta-learning methods. Advances Neural Information Processing Systems. 5917- 5928.
[37] Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix factorization techniques for recommender systems. Computer 42, 8 (2009), 30-37.
[38] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. 2020. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine 37, 3 (2020), 50-60.
[39] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. 2018. Federated optimization heterogeneous networks. arXiv preprint 1rXiv:1812.06127 (2018).
[40] Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. 2021. Fedbn: Federated learning non-iid features via local batch normalization. arXiv preprint arX1v:2102.07623 (2021).
[41] Paul Pu Liang, Terrance Liu, Liu Ziyin, Ruslan Salakhutdinov, and Louis-Philippe Morency. 2020. Think locally, act globally: Federated learning with local and global representations. arXiv preprini 2rXiv:2001.0052: (2020).
[42] Yujie Lin, Pengjie Ren, Zhumin Chen, Zhaochun Ren, Dongxiao Yu, Jun Ma, Maarten de Rijke, and Xiuzhen Cheng. 2020. Meta Matrix Factorization for Federated Rating Predictions. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. 981-990.
[43] Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. 2020. Three approaches for personalization with applications to federated learning. arXiv preprint arXiv:2002. 10619 (2020).
[44] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017. Communication--ffiiien learning of deep networks from decentralized data. In Artificial Intelligence and Statistics. PMLR, 1273-1282.
[45] Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. 2017. Learning differen- tially private recurrent language models. arXiv preprint arXiv: 171.::171000066 (2017).
12

---

[46] Alex Nichol, Joshua Achiam, and John Schulman. 2018. On first-order meta-leaminn algorithms. arXiv preprint arXiv: ww...0003.0000 02999 (2018).
[47] Valeria Nikolaenko, Stratis loannidis, Udi Weinsberg, Mare Joye, Nina Taft, and Dan Boneh. 2013. Privacy-preserving matrix factorization. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 801-812.
[48] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. 2020. Adaptive Federated Optimization. arXiv preprint a0X2v (2020).
[49] Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. 2017. Federated multi-task learning. arXiv preprint 1rXiv:1705. (2017).
[50]
TensorFlow. 2019. TensorFlow Federated. http:///wwwwteeorooooooooo
[51] TensorFlow. 2019. TensorFlow Federated Stack Overflow Dataset.
https:
wwwgfederatee..eeooooooooo http:///...//ooooooo/////a//aaaa stactoverflor/load_dd
[52] Kangkang Wang. Rajiv Mathews, Chloé Kiddon, Hubert Eichner, Françoise Beaufays, and Daniel Ramage. 2019. Federated evaluation of on-device personalization. arXiv preprint arXiv: 10252 (2019).
[53] Wenqi Wei, Ling Liu, Margaret Loper, Ka-Ho Chow, Mehmet Emre Gursoy, Stacey Truex, and Yanzhao Wu. 2020. framework for evaluating gradient leakage attacks in federated learning. arXiv preprint 2Xhv:2004.1033 (2020).
[54] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. 2009. Feature hashing for large scale multitask learning. Proceedings of the 26th annual interna- tional conference machine learning. 1113-1120.
[55] Xi Wu, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey F. Naughton. 2016. Differ- entially Private Stochastic Gradient Descent for In-DDMMS Analytics. CoRR abs/1606.00722 (2016). arXiv:1606.04777 http://arxiv.
org/ abwaaaas/b00 04722
[56] Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. 2018. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXiv: 023200203 (2018).
[57] Hongxu Yin, Arun Mallya, Arash Vahdat, Jose M Alvarez, Jan Kautz, and Pavlo Molchanov. 2021. See through Gradients: Image Batch Recovery via GradInversion. arXiv preprint w.Xiv:2104007588 (2021).
[58] Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. 2020. Salvaging federated learning by local adaptation. arXiv preprint arXhv:2002.04758 (2020).
[59] Ligeng Zhu and Song Han. 2020. Deep leakage from gradients. In Federated Learning. Springer, 17-31.
13


Reviews:
[{"review_id": "u04lMmme0LY", "reviewer": "Reviewer_TSbD", "summary": "- This work proposed FedRecon, a method that splits the client model into local and global parameters to enable stateless federated learning\n- During training, the client trains the local and the global model using separate splits of the client dataset, but only transmit the global data for aggregation\n- Clients with no local parameters trained (clients not seen during the training), can reconstruct/train their local parameters after fetching the global parameters from the server using the local training data. Similarly, other clients which might have either stale local parameters or might have lost/forgotten the local parameters can reconstruct them too\n- This makes the method stateless since the clients need not store the global parameters (sever stores them) and the local parameters (since they can be reconstructed)\n- The authors show good empirical performance on matrix factorization and next word prediction task. Additionally, the authors also the practical utility and scalability of the method through the deployment of the method in a real-life scenario.", "questions": "", "limitations": "", "rating": 7, "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": "**Strengths**\n\n- The proposed method is a simple extension of the standard federated learning setup, with the difference being only in how the local model is trained. Experiments show good performance with a wide range of hyperparameters (support and query data splits, local update steps, etc), and the method is applicable to a wide array of models.\n- I also appreciate the authors providing the prior submission review. It helped me understand how the paper has evolved over multiple submission cycles.\n- Open-sourcing of code through the TensorFlow Federated Library for future experimentation and practical use is a good contribution. However, it might be my ignorance of the framework but I would like to understand how is it different from someone open-sourcing the code for any other submission to the conference. Is the open-sourced code the same used by authors to run their experiments, or they modified it especially to release it as a separate framework?\n- The deployment to a mobile application proves the practical applicability of the method and is a good contribution. However, the authors mention in the Submission History section that \"[practical deployment results are] rare in FL papers which typically achieve only simulation results\". I would disagree with this comment. Results on simulated settings do not necessarily mean inapplicability to practical deployments. Recent datasets do have clients in the order of hundreds of thousands, which mimics the practical setting to a certain extent. Additionally, very few researchers have the resources to deploy to millions of devices, and while these results are good to have in the paper, their absence should by no means be negatively looked at.\n\n\n**Clarifications and Improvements**\n\n- Table 1: What is the Server + Standard Eval and Server + ReconEval training setup? Can the authors describe this somewhere in the paper or refer to a prior work that utilizes this setup?\n- Table 1, 2: FedRecon for matrix factorization is trained for 50 gradient steps each for the local and global params, and for NWP it's trained for 100 gradient steps each. How many gradient steps were the baselines trained for? Can the authors please provide the hyperparameters used to train the baselines as well?\n- Lines 263 - 265: The authors mention that the results for Server+ReconEval varied widely across users. Since they ran 500 iterations of the experiment, can the authors please provide the standard error numbers along with the reported mean accuracy to help better understand the variation amongst clients, and compare this variation with FedRecon\n- I felt that the experiment section was informative but was slightly convoluted to follow and understand. For a future version of the paper, the authors might consider refactoring the section to make it more readable.\n\n\n\nOverall, I felt this work:\n\n- tackles a relevant problem in federated learning, \n- proposes a simple, widely applicable to solve the problem, and\n- empirically shows good performance in simulated and practical scenarios.\n\nThus, I would vote for its acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "aw9WNIZTu4", "reviewer": "Reviewer_fqwY", "summary": "This paper introduces a partially local federated learning method named FEDRECON based on federated reconstruction.  The experimental results demonstrate the effectiveness of FEDRECON. The authors also deploy this approach in a real-world mobile keyboard application.", "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": "Pros:\n1. This paper is well written and easy to follow.\n2. The proposed approach is interesting.\n3. The authors provide a nice code library.\n\nCons:\n1. The contributions of this work over other partially local federated learning methods are not clearly explained.\n2. The motivation of reconstruction is not clarified.\n3. Some related works are not cited nor compared.\n\nDetailed comments:\n1. The technical contributions of this work are not well elaborated. Partially local federated learning is a widely studied problem [1-5], especially in the recommendation field. In these methods, each client locally learns a user embedding while item embeddings are global parameters. The authors' discussions in Appendix A do not clarify why this setting is not optimal. \n2. The motivation of reconstruction is also not clarified. For example, in federated recommender systems, why personalized parameters can be generated from shared global ones? What is the intuition?\n3. Some related works are not cited nor compared. The authors need to compare the methods in the recommendation field that locally keep personalized parameters. In addition, the authors may consider comparing some meta-learning based federated learning methods like [2] to better support the key statements.\n\n[1] Chai, Di, et al. \"Secure federated matrix factorization.\" IEEE Intelligent Systems (2020).\n[2] Lin, Yujie, et al. \"Meta Matrix Factorization for Federated Rating Predictions.\" SIGIR 2020.\n[3] Ge, Suyu, et al. \"Fedner: Privacy-preserving medical named entity recognition with federated learning.\" arXiv preprint arXiv:2003.09288 (2020).\n[4] Ammad-Ud-Din, Muhammad, et al. \"Federated collaborative filtering for privacy-preserving personalized recommendation system.\" arXiv preprint arXiv:1901.09888 (2019).\n[5] Wu, Chuhan, et al. \"Fedgnn: Federated graph neural network for privacy-preserving recommendation.\" arXiv preprint arXiv:2102.04925 (2021). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the privacy-related issues of the proposed approach and related limitations in the appendix. However, it is encouraged to include some discussions in the main content.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "OfXVv3E_P9W", "reviewer": "Reviewer_fiWt", "summary": "In this paper, the authors proposed a new FL framework to address data privacy, communication cost, and non-iid data distribution issues in FL. In the proposed method, clients only send and receives partial models to cloud and reconstruct the other half from the clients' own data. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "I have the following major concerns about the paper. \n\n1. What does the model agnostics refer to? Do the authors mean the clients can have different models or the framework can handle different tasks? Please clarify.\n\n2. For the tasks, I agree the task like matrix factorization is suitable for the proposed method. However, for other tasks where each client trains a deep model and aggregates all the clients' models on the cloud, I don't think only compare with FedYogi is enough. FedYogi is an extension from FedAvg which in general only produces a global model and is not suitable for personalization. In my opinion, the authors should compare at least of the SOTA personalized FL methods for their performance, such as \n\na. FedBN: Federated Learning on Non-IID Features via Local Batch Normalization\n\nb. Personalized Cross-Silo Federated Learning on Non-IID Data\n\nc. Federated Optimization in Heterogeneous Networks\n\nd. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning\n\ne. Adaptive Personalized Federated Learning\n\nf. Federated learning ´of a mixture of global and local models\n\n3. The proposed method is a heuristic method without any theoretical convergence guarantee. \n\n4. I also wonder whether this framework works if the local model is a complex and large model. In addition, how does the partition size affect the proposed framework? Especially, a large model is needed.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "1gUVa2wQjQZ", "reviewer": "Reviewer_3vKL", "summary": "The authors propose a new approach to partially local federated learning. In contrast to previous works their approach does not require agents to maintain state (i.e. store the local parameters of the model). Instead, they reconstruct the personalized parts of the model on the fly from local data.  Such a state-less approach is crucial for any practical deployment of FL at scale since is enables new clients that have not yet trained their local parameters to participate in training and to perform inference.\nTheir approach (FedRecon) is inspired by model-agnostic meta learning, where fast reconstruction at test-time is a key design criteria. \n\nEmpirically the performance of FedRecon is evaluated along different axis. The authors show that their approach trains global parameter that are particularly well suited for reconstruction, the approach achieves performance comparable to personalization through fine-tuning of a global model, and they study the qualitative behavior of their method wrt several hyperparameters. \nIn addition the authors report on a successful real-world deployment of the method across hundreds of millions of clients and discuss the practical challenge of data sparsity. \n\nThe code for reconstructing the experiments is packaged as a library to allow users to seamlessly integrate other tasks and algorithms. \n", "questions": "", "limitations": "", "rating": 7, "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": "The paper extends partially local federated learning to settings where agent can not maintain state. This scenario seems well motivated from a practical perspective and the authors give several good application examples. The core idea of using a local reconstruction algorithm to obtain the local parts of the model is simple but interesting and to the best of my knowledge it is novel in this context. \n\nMy main criticism is the presentation of the empirical results in Section 5. The baselines are not well introduced and the goal of the individual comparisons is not clear a priori. This makes it hard to follow (in particular the first part in 5.2, Table 1/2) and as a result your baselines seem a bit constructed at a first glance. \n\nI think it would help if you make clear from the beginning that a direct comparison to existing methods is not possible because there is no other state-less approach that keeps parts of the model parameters entirely local. Then, you could one-by-one outline what aspect of your method you want to study and then introduce the baselines for this purpose. For example, the ReconEval evaluation scheme for Table 1 would make more sense to the reader if they knew that you aim to show that your method learns global parameters that are particularly well suited for reconstruction later on, in comparison to other methods of obtaining these global parameters. \n\nIn this context, a comparison to a global only model might also be interesting, i.e., a model where you ignore the private features completely. This would help clarify the need for local steps in the ReconEval procedure that you introduce. \n\nIn 263 you mention that results vary a lot across users. Could you elaborate more on this? Showing the distribution over accuracy values of users for the different methods (instead of only RMSE) would be useful here and provide more insights into this interesting finding.\n\nIt is nice to see that you actually deployed this federated learning method in a real application. You mentioned that data sparsity was an issue and prevented the naïve implementation of your method.  Were there any other practical challenges you were facing? You mention a 29.3% increase in CTR, this claim is not particularly useful without a reference. What method was used in the previous system?  \n\nOverall, I think the authors adequately addressed the concerns of the meta-review from the previous review round. If the authors are willing to make an effort to address my concerns about the presentation of the empirical results, I will recommend acceptance. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I have carefully read all reviews, rebuttals and subsequent discussion. The proposed methodology relies on a sequence of intuitive shortcuts, reformulations and claims, which in totality make intuitive sense, but are not supported by any theory, and as such, the approach remains a heuristic. For example, the original cross device FL formulation is not well motivated, despite the fact that it is used in nearly every paper on the topic. This is not a particular issue with the current paper - this is an issue with all works in this area.  The authors rightfully claim that statelessness can be a problem in practical deployments of FL in the cross device setting. However, statefulness, when present, has a clear purpose: well designed stateful methods can achieve superior theoretical guarantees, and this is the main reason why states are useful. If the authors tested again stateful methods in the regime when states are useful (e.g., states in SCAFFOLD help to reduce client drift, which leads to better theoretical rates in certain regimes; there are dozens of examples like this), I doubt their stateless approach could win. Of course, once a method is applied outside of the scope in which it is theoretically shown to be better than competing approaches, all bets are off, and the empirical behavior can go both ways. I appreciate though that in the setting considered by the authors, storing states is not practical. The authors then proceed to a reformulation of the cross device FL problem in the form of (2), but do not make any attempt to explain what is lost by using this reformulation. Clearly, solving (1) and (2) are two very different tasks. The connection provided between (2) and (1) is intuitive only. I believe one can think of simple counterexamples that show that by solving (2), one does not approach the solution of (1) in any reasonable way. In this sense, their reformulation is a heuristic again. It may work in some regimes, but it is not clear what regimes these are. Some theory is sorely needed here. In totality, the authors provide a heuristic which may or may not work, depending on the problem being solved. This reduces its usefulness / applicability in regimes/applications beyond the ones studied in the paper. Having said that, the approach seems to be useful for the application at hand. The connection of (2) to MAML is helpful. However, outlining this connection alone does not mean that by solving (2) one gets any close to solving (1). In that sense, the authors could have well just started by saying that what they want to solve is (2) to start with. However, why should one formalize a FL problem in the form (2)? Say we can solve this problem exactly. What does it say about the generalization properties of the model we learn that way? Why does this formulation have any connection to generalization in the first place?

In summary, I believe this is a solid empirical work, proposing a certain heuristic approach to address certain practicality issues encountered in cross device FL models of a certain type (while clearly the approach is model-agnostic, it is not clear at all it makes sense to use it for any model type - some models might not be well trainable using alternating minimization steps). 

I think this paper should be seen as borderline. I tend to accept it as the reviews are largely positive. But at the same time, I am very familiar with the related literature, and my own reading of the paper would lead to a score of 5. I will leave the final decision to SAC.

AC
Decision: Accept (Poster)