# Advances and Open Problems in Federated Learning

Peter Kairouz, Brendan H. Mcmahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.

► To cite this version:

Peter Kairouz, Brendan H. Mcmahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, et al. Advances and Open Problems in Federated Learning. Foundations and Trends in Machine Learning, 2021, 14 (1-2), pp.1-210. hal-02406503v2

HAL Id: hal-02406503

https://inria.hal.science/hal-02406503v2

Submitted on 4 May 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
Advances and Open Problems in Federated Learning

Peter Kairouz<sup>7*</sup>      H. Brendan McMahan<sup>7*</sup>      Brendan Avent<sup>21</sup>      Aurélien Bellet<sup>9</sup>
Mehdi Bennis<sup>19</sup>    Arjun Nitin Bhagoji<sup>13</sup>    Kallista Bonawitz<sup>7</sup>    Zachary Charles<sup>7</sup>
Graham Cormode<sup>23</sup>  Rachel Cummings<sup>6</sup>      Rafael G.L. D'Oliveira<sup>14</sup>
Hubert Eichner<sup>7</sup>   Salim El Rouayheb<sup>14</sup>    David Evans<sup>22</sup>      Josh Gardner<sup>24</sup>
Zachary Garrett<sup>7</sup>  Adrià Gascón<sup>7</sup>        Badih Ghazi<sup>7</sup>      Phillip B. Gibbons<sup>2</sup>
Marco Gruteser<sup>7,14</sup> Zaid Harchaoui<sup>24</sup>    Chaoyang He<sup>21</sup>      Lie He<sup>4</sup>
Zhouyuan Huo<sup>20</sup>    Ben Hutchinson<sup>7</sup>      Justin Hsu<sup>25</sup>      Martin Jaggi<sup>4</sup>      Tara Javidi<sup>17</sup>
Gauri Joshi<sup>2</sup>     Mikhail Khodak<sup>2</sup>      Jakub Konečný<sup>7</sup>    Aleksandra Korolova<sup>21</sup>
Farinaz Koushanfar<sup>17</sup> Sanmi Koyejo<sup>7,18</sup>    Tancrède Lepoint<sup>7</sup>    Yang Liu<sup>12</sup>
Prateek Mittal<sup>13</sup>  Mehryar Mohri<sup>7</sup>      Richard Nock<sup>1</sup>      Ayfer Özgür<sup>15</sup>
Rasmus Pagh<sup>7,10</sup>    Hang Qi<sup>7</sup>           Daniel Ramage<sup>7</sup>    Ramesh Raskar<sup>11</sup>
Mariana Raykova<sup>7</sup>  Dawn Song<sup>16</sup>        Weikang Song<sup>7</sup>    Sebastian U. Stich<sup>4</sup>
Ziteng Sun<sup>3</sup>      Ananda Theertha Suresh<sup>7</sup> Florian Tramèr<sup>15</sup> Praneeth Vepakomma<sup>11</sup>
Jianyu Wang<sup>2</sup>      Li Xiong<sup>5</sup>          Zheng Xu<sup>7</sup>      Qiang Yang<sup>8</sup>      Felix X. Yu<sup>7</sup>      Han Yu<sup>12</sup>
Sen Zhao<sup>7</sup>

<sup>1</sup>Australian National University, <sup>2</sup>Carnegie Mellon University, <sup>3</sup>Cornell University,
<sup>4</sup>École Polytechnique Fédérale de Lausanne, <sup>5</sup>Emory University, <sup>6</sup>Georgia Institute of Technology,
<sup>7</sup>Google Research, <sup>8</sup>Hong Kong University of Science and Technology, <sup>9</sup>INRIA, <sup>10</sup>IT University of Copenhagen,
<sup>11</sup>Massachusetts Institute of Technology, <sup>12</sup>Nanyang Technological University, <sup>13</sup>Princeton University,
<sup>14</sup>Rutgers University, <sup>15</sup>Stanford University, <sup>16</sup>University of California Berkeley,
<sup>17</sup>University of California San Diego, <sup>18</sup>University of Illinois Urbana-Champaign, <sup>19</sup>University of Oulu,
<sup>20</sup>University of Pittsburgh, <sup>21</sup>University of Southern California, <sup>22</sup>University of Virginia,
<sup>23</sup>University of Warwick, <sup>24</sup>University of Washington, <sup>25</sup>University of Wisconsin–Madison

Abstract

Federated learning (FL) is a machine learning setting where many clients (e.g. mobile devices or
whole organizations) collaboratively train a model under the orchestration of a central server (e.g. service
provider), while keeping the training data decentralized. FL embodies the principles of focused data
collection and minimization, and can mitigate many of the systemic privacy risks and costs resulting
from traditional, centralized machine learning and data science approaches. Motivated by the explosive
growth in FL research, this paper discusses recent advances and presents an extensive collection of open
problems and challenges.

<footnote>*Peter Kairouz and H. Brendan McMahan conceived, coordinated, and edited this work. Correspondence to kairouz@
google.com and mcmahan@google.com.</footnote>
# Contents

<table><tr><td>1</td><td>Introduction</td><td>4</td></tr><tr><td>1.1</td><td>The Cross-Device Federated Learning Setting</td><td>5</td></tr><tr><td>1.1.1</td><td>The Lifecycle of a Model in Federated Learning</td><td>7</td></tr><tr><td>1.1.2</td><td>A Typical Federated Training Process</td><td>8</td></tr><tr><td>1.2</td><td>Federated Learning Research</td><td>9</td></tr><tr><td>1.3</td><td>Organization</td><td>10</td></tr><tr><td>2</td><td>Relaxing the Core FL Assumptions: Applications to Emerging Settings and Scenarios</td><td>11</td></tr><tr><td>2.1</td><td>Fully Decentralized / Peer-to-Peer Distributed Learning</td><td>11</td></tr><tr><td>2.1.1</td><td>Algorithmic Challenges</td><td>12</td></tr><tr><td>2.1.2</td><td>Practical Challenges</td><td>14</td></tr><tr><td>2.2</td><td>Cross-Silo Federated Learning</td><td>14</td></tr><tr><td>2.3</td><td>Split Learning</td><td>16</td></tr><tr><td>2.4</td><td>Executive summary</td><td>17</td></tr><tr><td>3</td><td>Improving Efficiency and Effectiveness</td><td>18</td></tr><tr><td>3.1</td><td>Non-IID Data in Federated Learning</td><td>18</td></tr><tr><td>3.1.1</td><td>Strategies for Dealing with Non-IID Data</td><td>19</td></tr><tr><td>3.2</td><td>Optimization Algorithms for Federated Learning</td><td>20</td></tr><tr><td>3.2.1</td><td>Optimization Algorithms and Convergence Rates for IID Datasets</td><td>21</td></tr><tr><td>3.2.2</td><td>Optimization Algorithms and Convergence Rates for Non-IID Datasets</td><td>25</td></tr><tr><td>3.3</td><td>Multi-Task Learning, Personalization, and Meta-Learning</td><td>28</td></tr><tr><td>3.3.1</td><td>Personalization via Featurization</td><td>28</td></tr><tr><td>3.3.2</td><td>Multi-Task Learning</td><td>28</td></tr><tr><td>3.3.3</td><td>Local Fine Tuning and Meta-Learning</td><td>29</td></tr><tr><td>3.3.4</td><td>When is a Global FL-trained Model Better?</td><td>30</td></tr><tr><td>3.4</td><td>Adapting ML Workflows for Federated Learning</td><td>30</td></tr><tr><td>3.4.1</td><td>Hyperparameter Tuning</td><td>31</td></tr><tr><td>3.4.2</td><td>Neural Architecture Design</td><td>31</td></tr><tr><td>3.4.3</td><td>Debugging and Interpretability for FL</td><td>32</td></tr><tr><td>3.5</td><td>Communication and Compression</td><td>32</td></tr><tr><td>3.6</td><td>Application To More Types of Machine Learning Problems and Models</td><td>34</td></tr><tr><td>3.7</td><td>Executive summary</td><td>34</td></tr><tr><td>4</td><td>Preserving the Privacy of User Data</td><td>36</td></tr><tr><td>4.1</td><td>Actors, Threat Models, and Privacy in Depth</td><td>37</td></tr><tr><td>4.2</td><td>Tools and Technologies</td><td>38</td></tr><tr><td>4.2.1</td><td>Secure Computations</td><td>40</td></tr><tr><td>4.2.2</td><td>Privacy-Preserving Disclosures</td><td>44</td></tr><tr><td>4.2.3</td><td>Verifiability</td><td>46</td></tr><tr><td>4.3</td><td>Protections Against External Malicious Actors</td><td>48</td></tr><tr><td>4.3.1</td><td>Auditing the Iterates and Final Model</td><td>49</td></tr><tr><td>4.3.2</td><td>Training with Central Differential Privacy</td><td>49</td></tr><tr><td>4.3.3</td><td>Concealing the Iterates</td><td>51</td></tr><tr><td>4.3.4</td><td>Repeated Analyses over Evolving Data</td><td>52</td></tr><tr><td>4.3.5</td><td>Preventing Model Theft and Misuse</td><td>52</td></tr><tr><td>4.4</td><td>Protections Against an Adversarial Server</td><td>53</td></tr><tr><td>4.4.1</td><td>Challenges: Communication Channels, Sybil Attacks, and Selection</td><td>53</td></tr><tr><td>4.4.2</td><td>Limitations of Existing Solutions</td><td>54</td></tr><tr><td>4.4.3</td><td>Training with Distributed Differential Privacy</td><td>55</td></tr><tr><td>4.4.4</td><td>Preserving Privacy While Training Sub-Models</td><td>58</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>4.5 User Perception</td>
      <td>59</td>
    </tr>
    <tr>
      <td>4.5.1 Understanding Privacy Needs for Particular Analysis Tasks</td>
      <td>59</td>
    </tr>
    <tr>
      <td>4.5.2 Behavioral Research to Elicit Privacy Preferences</td>
      <td>60</td>
    </tr>
    <tr>
      <td>4.6 Executive Summary</td>
      <td>60</td>
    </tr>
    <tr>
      <td><b>5 Defending Against Attacks and Failures</b></td>
      <td><b>62</b></td>
    </tr>
    <tr>
      <td>5.1 Adversarial Attacks on Model Performance</td>
      <td>62</td>
    </tr>
    <tr>
      <td>5.1.1 Goals and Capabilities of an Adversary</td>
      <td>63</td>
    </tr>
    <tr>
      <td>5.1.2 Model Update Poisoning</td>
      <td>66</td>
    </tr>
    <tr>
      <td>5.1.3 Data Poisoning Attacks</td>
      <td>67</td>
    </tr>
    <tr>
      <td>5.1.4 Inference-Time Evasion Attacks</td>
      <td>69</td>
    </tr>
    <tr>
      <td>5.1.5 Defensive Capabilities from Privacy Guarantees</td>
      <td>70</td>
    </tr>
    <tr>
      <td>5.2 Non-Malicious Failure Modes</td>
      <td>71</td>
    </tr>
    <tr>
      <td>5.3 Exploring the Tension between Privacy and Robustness</td>
      <td>73</td>
    </tr>
    <tr>
      <td>5.4 Executive Summary</td>
      <td>73</td>
    </tr>
    <tr>
      <td><b>6 Ensuring Fairness and Addressing Sources of Bias</b></td>
      <td><b>75</b></td>
    </tr>
    <tr>
      <td>6.1 Bias in Training Data</td>
      <td>75</td>
    </tr>
    <tr>
      <td>6.2 Fairness Without Access to Sensitive Attributes</td>
      <td>76</td>
    </tr>
    <tr>
      <td>6.3 Fairness, Privacy, and Robustness</td>
      <td>77</td>
    </tr>
    <tr>
      <td>6.4 Leveraging Federation to Improve Model Diversity</td>
      <td>78</td>
    </tr>
    <tr>
      <td>6.5 Federated Fairness: New Opportunities and Challenges</td>
      <td>79</td>
    </tr>
    <tr>
      <td>6.6 Executive Summary</td>
      <td>79</td>
    </tr>
    <tr>
      <td><b>7 Addressing System Challenges</b></td>
      <td><b>81</b></td>
    </tr>
    <tr>
      <td>7.1 Platform Development and Deployment Challenges</td>
      <td>81</td>
    </tr>
    <tr>
      <td>7.2 System Induced Bias</td>
      <td>82</td>
    </tr>
    <tr>
      <td>7.2.1 Device Availability Profiles</td>
      <td>82</td>
    </tr>
    <tr>
      <td>7.2.2 Examples of System Induced Bias</td>
      <td>83</td>
    </tr>
    <tr>
      <td>7.2.3 Open Challenges in Quantifying and Mitigating System Induced Bias</td>
      <td>84</td>
    </tr>
    <tr>
      <td>7.3 System Parameter Tuning</td>
      <td>85</td>
    </tr>
    <tr>
      <td>7.4 On-Device Runtime</td>
      <td>86</td>
    </tr>
    <tr>
      <td>7.5 The Cross-Silo Setting</td>
      <td>87</td>
    </tr>
    <tr>
      <td>7.6 Executive Summary</td>
      <td>88</td>
    </tr>
    <tr>
      <td><b>8 Concluding Remarks</b></td>
      <td><b>89</b></td>
    </tr>
    <tr>
      <td><b>A Software and Datasets for Federated Learning</b></td>
      <td><b>119</b></td>
    </tr>
  </tbody>
</table>
# 1 Introduction

Federated learning (FL) is a machine learning setting where many clients (e.g. mobile devices or whole organizations) collaboratively train a model under the orchestration of a central server (e.g. service provider), while keeping the training data decentralized. It embodies the principles of focused collection and data minimization, and can mitigate many of the systemic privacy risks and costs resulting from traditional, centralized machine learning. This area has received significant interest recently, both from research and applied perspectives. This paper describes the defining characteristics and challenges of the federated learning setting, highlights important practical constraints and considerations, and then enumerates a range of valuable research directions. The goals of this work are to highlight research problems that are of significant theoretical and practical interest, and to encourage research on problems that could have significant real-world impact.

The term federated learning was introduced in 2016 by McMahan et al. [337]: “We term our approach Federated Learning, since the learning task is solved by a loose federation of participating devices (which we refer to as clients) which are coordinated by a central server.” An unbalanced and non-IID (identically and independently distributed) data partitioning across a massive number of unreliable devices with limited communication bandwidth was introduced as the defining set of challenges.

Significant related work predates the introduction of the term federated learning. A longstanding goal pursued by many research communities (including cryptography, databases, and machine learning) is to analyze and learn from data distributed among many owners without exposing that data. Cryptographic methods for computing on encrypted data were developed starting in the early 1980s [396, 492], and Agrawal and Srikant [11] and Vaidya et al. [457] are early examples of work that sought to learn from local data using a centralized server while preserving privacy. Conversely, even since the introduction of the term federated learning, we are aware of no single work that directly addresses the full set of FL challenges. Thus, the term federated learning provides a convenient shorthand for a set of characteristics, constraints, and challenges that often co-occur in applied ML problems on decentralized data where privacy is paramount.

This paper originated at the Workshop on Federated Learning and Analytics held June 17–18th, 2019, hosted at Google’s Seattle office. During the course of this two-day event, the need for a broad paper surveying the many open challenges in the area of federated learning became clear.<fnref n="1" />

A key property of many of the problems discussed is that they are inherently interdisciplinary — solving them likely requires not just machine learning, but techniques from distributed optimization, cryptography, security, differential privacy, fairness, compressed sensing, systems, information theory, statistics, and more. Many of the hardest problems are at the intersections of these areas, and so we believe collaboration will be essential to ongoing progress. One of the goals of this work is to highlight the ways in which techniques from these fields can potentially be combined, raising both interesting possibilities as well as new challenges.

Since the term federated learning was initially introduced with an emphasis on mobile and edge device applications [337, 334], interest in applying FL to other applications has greatly increased, including some which might involve only a small number of relatively reliable clients, for example multiple organizations collaborating to train a model. We term these two federated learning settings “cross-device” and “cross-silo” respectively. Given these variations, we propose a somewhat broader definition of federated learning:

> Federated learning is a machine learning setting where multiple entities (clients) collaborate in solving a machine learning problem, under the coordination of a central server or service provider. Each client's raw data is stored locally and not exchanged or transferred; instead,

<footnote n="1">¹During the preparation of this work, Li et al. [301] independently released an excellent but less comprehensive survey.</footnote>
focused updates intended for immediate aggregation are used to achieve the learning objective.

Focused updates are updates narrowly scoped to contain the minimum information necessary for the specific
learning task at hand; aggregation is performed as early as possible in the service of data minimization. We
note that this definition distinguishes federated learning from fully decentralized (peer-to-peer) learning
techniques as discussed in Section 2.1.

Although privacy-preserving data analysis has been studied for more than 50 years, only in the past decade have solutions been widely deployed at scale (e.g. [177, 154]). Cross-device federated learning and federated data analysis are now being applied in consumer digital products. Google makes extensive use of federated learning in the Gboard mobile keyboard [376, 222, 491, 112, 383], as well as in features on Pixel phones [14] and in Android Messages [439]. While Google has pioneered cross-device FL, interest in this setting is now much broader, for example: Apple is using cross-device FL in iOS 13 [25], for applications like the QuickType keyboard and the vocal classifier for “Hey Siri” [26]; doc.ai is developing cross-device FL solutions for medical research [149], and Snips has explored cross-device FL for hotword detection [298].

Cross-silo applications have also been proposed or described in myriad domains including finance risk
prediction for reinsurance [476], pharmaceuticals discovery [179], electronic health records mining [184],
medical data segmentation [15, 139], and smart manufacturing [354].

The growing demand for federated learning technology has resulted in a number of tools and frameworks becoming available. These include TensorFlow Federated [38], Federated AI Technology Enabler [33], PySyft [399], Leaf [35], PaddleFL [36] and Clara Training Framework [125]; more details in Appendix A. Commercial data platforms incorporating federated learning are in development from established technology companies as well as smaller start-ups.

Table 1 contrasts both cross-device and cross-silo federated learning with traditional single-datacenter distributed learning across a range of axes. These characteristics establish many of the constraints that practical federated learning systems must typically satisfy, and hence serve to both motivate and inform the open challenges in federated learning. They will be discussed at length in the sections that follow.

These two FL variants are called out as representative and important examples, but different FL settings
may have different combinations of these characteristics. For the remainder of this paper, we consider the
cross-device FL setting unless otherwise noted, though many of the problems apply to other FL settings as
well. Section 2 specifically addresses some of the many other variations and applications.

Next, we consider cross-device federated learning in more detail, focusing on practical aspects common to a typical large-scale deployment of the technology; Bonawitz et al. [81] provides even more detail for a particular production system, including a discussion of specific architectural choices and considerations.

## 1.1 The Cross-Device Federated Learning Setting

This section takes an applied perspective, and unlike the previous section, does not attempt to be definitional. Rather, the goal is to describe some of the practical issues in cross-device FL and how they might fit into a broader machine learning development and deployment ecosystem. The hope is to provide useful context and motivation for the open problems that follow, as well as to aid researchers in estimating how straightforward it would be to deploy a particular new approach in a real-world system. We begin by sketching the lifecycle of a model before considering a FL training process.
<table><caption>Table 1: Typical characteristics of federated learning settings vs. distributed learning in the datacenter (e.g. [150]). Cross-device and cross-silo federated learning are two examples of FL domains, but are not intended to be exhaustive. The primary defining characteristics of FL are highlighted in bold, but the other characteristics are also critical in determining which techniques are applicable.</caption><thead><tr><th></th><th>Datacenter distributed learning</th><th>Cross-silo federated learning</th><th>Cross-device federated learning</th></tr></thead><tbody><tr><td>Setting</td><td>Training a model on a large but "flat" dataset. Clients are compute nodes in a single cluster or datacenter.</td><td>Training a model on siloed data. Clients are different organizations (e.g. medical or financial) or geo-distributed datacenters.</td><td>The clients are a very large number of mobile or IoT devices.</td></tr><tr><td>Data distribution</td><td>Data is centrally stored and can be shuffled and balanced across clients. Any client can read any part of the dataset.</td><td>Data is generated locally and remains decentralized. Each client stores its own data and cannot read the data of other clients. Data is not independently or identically distributed.</td><td></td></tr><tr><td>Orchestration</td><td>Centrally orchestrated.</td><td>A central orchestration server/service organizes the training, but never sees raw data.</td><td></td></tr><tr><td>Wide-area communication</td><td>None (fully connected clients in one datacenter/cluster).</td><td>Typically a hub-and-spoke topology, with the hub representing a coordinating service provider (typically without data) and the spokes connecting to clients.</td><td></td></tr><tr><td>Data availability</td><td>— All clients are almost always available. —</td><td></td><td>Only a fraction of clients are available at any one time, often with diurnal or other variations.</td></tr><tr><td>Distribution scale</td><td>Typically 1 - 1000 clients.</td><td>Typically 2 - 100 clients.</td><td>Massively parallel, up to 10<sup>10</sup> clients.</td></tr><tr><td>Primary bottleneck</td><td>Computation is more often the bottleneck in the datacenter, where very fast networks can be assumed.</td><td>Might be computation or communication.</td><td>Communication is often the primary bottleneck, though it depends on the task. Generally, cross-device federated computations use wi-fi or slower connections.</td></tr><tr><td>Addressability</td><td>Each client has an identity or name that allows the system to access it specifically.</td><td></td><td>Clients cannot be indexed directly (i.e., no use of client identifiers).</td></tr><tr><td>Client statefulness</td><td>Stateful — each client may participate in each round of the computation, carrying state from round to round.</td><td></td><td>Stateless — each client will likely participate only once in a task, so generally a fresh sample of never-before-seen clients in each round of computation is assumed.</td></tr><tr><td>Client reliability</td><td>— Relatively few failures. —</td><td></td><td>Highly unreliable — 5% or more of the clients participating in a round of computation are expected to fail or drop out (e.g. because the device becomes ineligible when battery, network, or idleness requirements are violated).</td></tr><tr><td>Data partition axis</td><td>Data can be partitioned / re-partitioned arbitrarily across clients.</td><td>Partition is fixed. Could be example-partitioned (horizontal) or feature-partitioned (vertical).</td><td>Fixed partitioning by example (horizontal).</td></tr></tbody></table>
<figure><img src="image_1.png" /><figcaption>Figure 1: The lifecycle of an FL-trained model and the various actors in a federated learning system. This figure is revisited in Section 4 from a threat models perspective.</figcaption></figure>

1.1.1 The Lifecycle of a Model in Federated Learning

The FL process is typically driven by a model engineer developing a model for a particular application. For example, a domain expert in natural language processing may develop a next word prediction model for use in a virtual keyboard. Figure 1 shows the primary components and actors. At a high level, a typical workflow is:

1. Problem identification: The model engineer identifies a problem to be solved with FL.

2. Client instrumentation: If needed, the clients (e.g. an app running on mobile phones) are instrumented to store locally (with limits on time and quantity) the necessary training data. In many cases, the app already will have stored this data (e.g. a text messaging app must store text messages, a photo management app already stores photos). However, in some cases additional data or metadata might need to be maintained, e.g. user interaction data to provide labels for a supervised learning task.

3. Simulation prototyping (optional): The model engineer may prototype model architectures and test learning hyperparameters in an FL simulation using a proxy dataset.

4. Federated model training: Multiple federated training tasks are started to train different variations of the model, or use different optimization hyperparameters.

5. (Federated) model evaluation: After the tasks have trained sufficiently (typically a few days, see below), the models are analyzed and good candidates selected. Analysis may include metrics computed on standard datasets in the datacenter, or federated evaluation wherein the models are pushed to held-out clients for evaluation on local client data.

6. **Deployment**: Finally, once a good model is selected, it goes through a standard model launch process, including manual quality assurance, live A/B testing (usually by using the new model on some devices and the previous generation model on other devices to compare their in-vivo performance), and a
<table><caption>Table 2: Order-of-magnitude sizes for typical cross-device federated learning applications.</caption><tr><td>Total population size</td><td>10<sup>6</sup>–10<sup>10</sup> devices</td></tr><tr><td>Devices selected for one round of training</td><td>50 – 5000</td></tr><tr><td>Total devices that participate in training one model</td><td>10<sup>5</sup>–10<sup>7</sup></td></tr><tr><td>Number of rounds for model convergence</td><td>500 – 10000</td></tr><tr><td>Wall-clock training time</td><td>1 – 10 days</td></tr></table>

staged rollout (so that poor behavior can be discovered and rolled back before affecting too many users). The specific launch process for a model is set by the owner of the application and is usually independent of how the model is trained. In other words, this step would apply equally to a model trained with federated learning or with a traditional datacenter approach.

One of the primary practical challenges an FL system faces is making the above workflow as straightforward as possible, ideally approaching the ease-of-use achieved by ML systems for centralized training. While much of this paper concerns federated training specifically, there are many other components including federated analytics tasks like model evaluation and debugging. Improving these is the focus of Section 3.4. For now, we consider in more detail the training of a single FL model (Step 4 above).

### 1.1.2 A Typical Federated Training Process

We now consider a template for FL training that encompasses the Federated Averaging algorithm of McMan- han et al. [337] and many others; again, variations are possible, but this gives a common starting point.

A server (service provider) orchestrates the training process, by repeating the following steps until training is stopped (at the discretion of the model engineer who is monitoring the training process):

1. **Client selection:** The server samples from a set of clients meeting eligibility requirements. For example, mobile phones might only check in to the server if they are plugged in, on an unmetered wi-fi connection, and idle, in order to avoid impacting the user of the device.

2. **Broadcast:** The selected clients download the current model weights and a training program (e.g. a TensorFlow graph [2]) from the server.

3. **Client computation:** Each selected device locally computes an update to the model by executing the training program, which might for example run SGD on the local data (as in Federated Averaging).

4. **Aggregation:** The server collects an aggregate of the device updates. For efficiency, stragglers might be dropped at this point once a sufficient number of devices have reported results. This stage is also the integration point for many other techniques which will be discussed later, possibly including: secure aggregation for added privacy, lossy compression of aggregates for communication efficiency, and noise addition and update clipping for differential privacy.

5. **Model update:** The server locally updates the shared model based on the aggregated update computed from the clients that participated in the current round.

Table 2 gives typical order-of-magnitude sizes for the quantities involved in a typical federated learning application on mobile devices.
The separation of the client computation, aggregation, and model update phases is not a strict require-
ment of federated learning, and it indeed excludes certain classes of algorithms, for example asynchronous
SGD where each client's update is immediately applied to the model, before any aggregation with updates
from other clients. Such asynchronous approaches may simplify some aspects of system design, and also
be beneficial from an optimization perspective (though this point can be debated). However, the approach
presented above has a substantial advantage in affording a separation of concerns between different lines of
research: advances in compression, differential privacy, and secure multi-party computation can be devel-
oped for standard primitives like computing sums or means over decentralized updates, and then composed
with arbitrary optimization or analytics algorithms, so long as those algorithms are expressed in terms of
aggregation primitives.

It is also worth emphasizing that in two respects, the FL training process should not impact the user
experience. First, as outlined above, even though model parameters are typically sent to some devices
during the broadcast phase of each round of federated training, these models are an ephemeral part of the
training process, and not used to make “live” predictions shown to the user. This is crucial, because training
ML models is challenging, and a misconfiguration of hyperparameters can produce a model that makes bad
predictions. Instead, user-visible use of the model is deferred to a rollout process as detailed above in Step 6
of the model lifecycle. Second, the training itself is intended to be invisible to the user — as described
under client selection, training does not slow the device or drain the battery because it only executes when
the device is idle and connected to power. However, the limited availability these constraints introduce
leads directly to open research challenges which will be discussed subsequently, such as semi-cyclic data
availability and the potential for bias in client selection.

1.2 Federated Learning Research

The remainder of this paper surveys many open problems that are motivated by the constraints and chal-
lenges of real-world federated learning settings, from training models on medical data from a hospital sys-
tem to training using hundreds of millions of mobile devices. Needless to say, most researchers working on
federated learning problems will likely not be deploying production FL systems, nor have access to fleets of
millions of real-world devices. This leads to a key distinction between the practical settings that motivate the
work and experiments conducted in simulation which provide evidence of the suitability of a given approach
to the motivating problem.

This makes FL research somewhat different than other ML fields from an experimental perspective, lead-
ing to additional considerations in conducting FL research. In particular, when highlighting open problems,
we have attempted, when possible, to also indicate relevant performance metrics which can be measured
in simulation, the characteristics of datasets which will make them more representative of real-world per-
formance, etc. The need for simulation also has ramifications for the presentation of FL research. While
not intended to be authoritative or absolute, we make the following modest suggestions for presenting FL
research that addresses the open problems we describe:

* As shown in Table 1, the FL setting can encompass a wide range of problems. Compared to fields where the setting and goals are well-established, it is important to precisely describe the details of the particular FL setting of interest, particularly when the proposed approach makes assumptions that may not be appropriate in all settings (e.g. stateful clients that participate in all rounds).

* Of course, details of any simulations should be presented in order to make the research reproducible. But it is also important to explain which aspects of the real-world setting the simulation is designed to capture (and which it is not), in order to effectively make the case that success on the simulated
problem implies useful progress on the real-world objective. We hope that the guidance in this paper
will help with this.

* Privacy and communication efficiency are always first-order concerns in FL, even if the experiments are simulations running on a single machine using public data. More so than with other types of ML, for any proposed approach it is important to be unambiguous about *where computation happens* as well as *what is communicated*.

Software libraries for federated learning simulation as well as standard datasets can help ease the chal-
lenges of conducting effective FL research; Appendix A summarizes some of the currently available options.
Developing standard evaluation metrics and establishing standard benchmark datasets for different federated
learning settings (cross-device and cross-silo) remain highly important directions for ongoing work.

1.3 Organization

Section 2 builds on the ideas in Table 1, exploring other FL settings and problems beyond the original focus on cross-device settings. Section 3 then turns to core questions around improving the efficiency and effectiveness of federated learning. Section 4 undertakes a careful consideration of threat models and considers a range of technologies toward the goal of achieving rigorous privacy protections. As with all machine learning systems, in federated learning applications there may be incentives to manipulate the models being trained, and failures of various kinds are inevitable; these challenges are discussed in Section 5. Finally, we address the important challenges of providing fair and unbiased models in Section 6.
# 2 Relaxing the Core FL Assumptions: Applications to Emerging Settings and Scenarios

In this section, we will discuss areas of research related to the topics discussed in the previous section. Even though not being the main focus of the remainder of the paper, progress in these areas could motivate design of the next generation of production systems.

## 2.1 Fully Decentralized / Peer-to-Peer Distributed Learning

In federated learning, a central server orchestrates the training process and receives the contributions of all clients. The server is thus a central player which also potentially represents a single point of failure. While large companies or organizations can play this role in some application scenarios, a reliable and powerful central server may not always be available or desirable in more collaborative learning scenarios [459]. Furthermore, the server may even become a bottleneck when the number of clients is very large, as demonstrated by Lian et al. [305] (though this can be mitigated by careful system design, e.g. [81]).

The key idea of fully decentralized learning is to replace communication with the server by peer-to-peer communication between individual clients. The communication topology is represented as a connected graph in which nodes are the clients and an edge indicates a communication channel between two clients. The network graph is typically chosen to be sparse with small maximum degree so that each node only needs to send/receive messages to/from a small number of peers; this is in contrast to the star graph of the server-client architecture. In fully decentralized algorithms, a round corresponds to each client performing a local update and exchanging information with their neighbors in the graph<fnref n="2" />. In the context of machine learning, the local update is typically a local (stochastic) gradient step and the communication consists in averaging one's local model parameters with the neighbors. Note that there is no longer a global state of the model as in standard federated learning, but the process can be designed such that all local models converge to the desired global solution, i.e., the individual models gradually reach consensus. While multi-agent optimization has a long history in the control community, fully decentralized variants of SGD and other optimization algorithms have recently been considered in machine learning both for improved scalability in datacenters [29] as well as for decentralized networks of devices [127, 459, 443, 59, 278, 291, 173]. They consider undirected network graphs, although the case of directed networks (encoding unidirectional channels which may arise in real-world scenarios such as social networks or data markets) has also been studied in [29, 226].

It is worth noting that even in the decentralized setting outlined above, a central authority may still be in charge of setting up the learning task. Consider for instance the following questions: Who decides what is the model to be trained in the decentralized setting? What algorithm to use? What hyperparameters? Who is responsible for debugging when something does not work as expected? A certain degree of trust of the participating clients in a central authority would still be needed to answer these questions. Alternatively, the decisions could be taken by the client who proposes the learning task, or collaboratively through a consensus scheme (see Section 2.1.2).

Table 3 provides a comparison between federated and peer-to-peer learning. While the architectural assumptions of decentralized learning are distinct from those of federated learning, it can often be applied to similar problem domains, many of the same challenges arise, and there is significant overlap in the research communities. Thus, we consider decentralized learning in this paper as well; in this section challenges

<footnote n="2">²Note, however, that the notion of a round does not need to even make sense in this setting. See for instance the discussion on clock models in [85].</footnote>
<table><caption>Table 3: A comparison of the key distinctions between federated learning and fully decentralized learning. Note that as with FL, decentralized learning can be further divided into different use-cases, with distinctions similar to those made in Table 1 comparing cross-silo and cross-device FL.</caption><thead><tr><th></th><th>Federated learning</th><th>Fully decentralized (peer-to-peer) learning</th></tr></thead><tbody><tr><td>Orchestration</td><td>A central orchestration server or service organizes the training, but never sees raw data.</td><td>No centralized orchestration.</td></tr><tr><td>Wide-area communication</td><td>Typically a hub-and-spoke topology, with the hub representing a coordinating service provider (typically without data) and the spokes connecting to clients.</td><td>Peer-to-peer topology, with a possibly dynamic connectivity graph.</td></tr></tbody></table>

specific to the decentralized approach are explicitly considered, but many of the open problems in other sections also arise in the decentralized case.

### 2.1.1 Algorithmic Challenges

A large number of important algorithmic questions remain open on the topic of real-world usability of decentralized schemes for machine learning. Some questions are analogous to the special case of federated learning with a central server, and other challenges come as an additional side-effect of being fully decentralized or trust-less. We outline some particular areas in the following.

**Effect of network topology and asynchrony on decentralized SGD** Fully decentralized algorithms for learning should be robust to the limited availability of the clients (with clients temporarily unavailable, dropping out or joining during the execution) and limited reliability of the network (with possible message drops). While for the special case of generalized linear models, schemes using the duality structure could enable some of these desired robustness properties [231], for the case of deep learning and SGD this remains an open question. When the network graph is complete but messages have a fixed probability to be dropped, Yu et al. [498] show that one can achieve convergence rates that are comparable to the case of a reliable network. Additional open research questions concern non-IID data distributions, update frequencies, efficient communication patterns and practical convergence time [443], as we outline in more detail below.

Well-connected or denser networks encourage faster consensus and give better theoretical convergence rates, which depend on the spectral gap of the network graph. However, when data is IID, sparser topologies do not necessarily hurt the convergence in practice: this was analyzed theoretically in [357]. Denser networks typically incur communication delays which increase with the node degrees. Most of optimization-theory works do not explicitly consider how the topology affects the runtime, that is, wall-clock time required to complete each SGD iteration. Wang et al. [469] propose MATCHA, a decentralized SGD method based on matching decomposition sampling, that reduces the communication delay per iteration for any given node topology while maintaining the same error convergence speed. The key idea is to decompose the graph topology into matchings consisting of disjoint communication links that can operate in parallel, and carefully choose a subset of these matchings in each iteration. This sequence of subgraphs results in more
frequent communication over connectivity-critical links (ensuring fast error convergence) and less frequent communication over other links (saving communication delays).

The setting of decentralized SGD also naturally lends itself to asynchronous algorithms in which each client becomes active independently at random times, removing the need for global synchronization and potentially improving scalability [126, 448, 461, 469].

### Local-update decentralized SGD
The theoretical analysis of schemes which perform several local update steps before a communication round is significantly more challenging than those using a single SGD step, as in mini-batch SGD. While this will also be discussed later in Section 3.2, the same also holds more generally in the fully decentralized setting of interest here. Schemes relying on a single local update step are typically proven to converge in the case of non-IID local datasets [278, 279]. For the case with several local update steps, [467, 280] recently provided convergence analysis. Further, [469] provides a convergence analysis for the non-IID data case, but for the specific scheme based on matching decomposition sampling described above. In general, however, understanding the convergence under non-IID data distributions and how to design a model averaging policy that achieves the fastest convergence remains an open problem.

### Personalization, and trust mechanisms
Similarly to the cross-device FL setting, an important task for the fully decentralized scenario under the non-IID data distributions available to individual clients is to design algorithms for learning collections of personalized models. The work of [459, 59] introduces fully decentralized algorithms to collaboratively learn a personalized model for each client by smoothing model parameters across clients that have similar tasks (i.e., similar data distributions). Zantedeschi et al. [504] further learn the similarity graph together with the personalized models. One of the key unique challenges in the decentralized setting remains the robustness of such schemes to malicious actors or contribution of unreliable data or labels. The use of incentives or mechanism design in combination with decentralized learning is an emerging and important goal, which may be harder to achieve in the setting without a trusted central server.

### Gradient compression and quantization methods
In potential applications, the clients would often be limited in terms of communication bandwidth available and energy usage permitted. Translating and generalizing some of the existing compressed communication schemes from the centralized orchestrator-facilitated setting (see Section 3.5) to the fully decentralized setting, without negatively impacting the convergence is an active research direction [278, 391, 444, 279]. A complementary idea is to design decentralized optimization algorithms which naturally give rise to sparse updates [504].

### Privacy
An important challenge in fully decentralized learning is to prevent any client from reconstructing the private data of another client from its shared updates while maintaining a good level of utility for the learned models. Differential privacy (see Section 4) is the standard approach to mitigate such privacy risks. In decentralized federated learning, this can be achieved by having each client add noise locally, as done in [239, 59]. Unfortunately, such local privacy approaches often come at a large cost in utility. Furthermore, distributed methods based on secure aggregation or secure shuffling that are designed to improve the privacy-utility trade-off in the standard FL setting (see Section 4.4.3) do not easily integrate with fully decentralized algorithms. A possible direction to achieve better trade-offs between privacy and utility in fully decentralized algorithms is to rely on decentralization itself to amplify differential privacy guarantees, for instance by considering appropriate relaxations of local differential privacy [146].
### 2.1.2 Practical Challenges

An orthogonal question for fully decentralized learning is how it can be practically realized. This section outlines a family of related ideas based on the idea of a distributed ledger, but other approaches remain unexplored.

A blockchain is a distributed ledger shared among disparate users, making possible digital transactions, including transactions of cryptocurrency, without a central authority. In particular, smart contracts allow execution of arbitrary code on top of the blockchain, essentially a massively replicated eventually-consistent state machine. In terms of federated learning, use of the technology could enable decentralization of the global server by using smart contracts to do model aggregation, where the participating clients executing the smart contracts could be different companies or cloud services.

However, on today's blockchain platforms such as Ethereum [478], data on the blockchains is publicly available by default, this could discourage users from participating in the decentralized federated learning protocol, as the protection of the data is typically the primary motivating factor for FL. To address such concerns, it might be possible to modify the existing privacy-preserving techniques to fit into the scenario of decentralized federated learning. First of all, to prevent the participating nodes from exploiting individually submitted model updates, existing secure aggregation protocols could be used. A practical secure aggregation protocol already used in cross-device FL was proposed by Bonawitz et al. [80], effectively handling dropping out participants at the cost of complexity of the protocol. An alternative system would be to have each client stake a deposit of cryptocurrency on blockchain, and get penalized if they drop out during the execution. Without the need of handling dropouts, the secure aggregation protocol could be significantly simplified. Another way of achieving secure aggregation is to use confidential smart contract such as what is enabled by the Oasis Protocol [119] which runs inside secure enclaves. With this, each client could simply submit an encrypted local model update, knowing that the model will be decrypted and aggregated inside the secure hardware through remote attestation (though see discussion of privacy-in-depth in Section 4.1).

In order to prevent any client from trying to reconstruct the private data of another client by exploiting the global model, client-level differential privacy [338] has been proposed for FL. Client-level differential privacy is achieved by adding random Gaussian noise on the aggregated global model that is enough to hide any single client's update. In the context of blockchain, each client could locally add a certain amount of Gaussian noise after local gradient descent steps and submit the model to blockchain. The local noise scale should be calculated such that the aggregated noise on blockchain is able to achieve the same client-level differential privacy as in [338]. Finally, the aggregated global model on blockchain could be encrypted and only the participating clients hold the decryption key, which protects the model from the public.

## 2.2 Cross-Silo Federated Learning

In contrast with the characteristics of cross-device federated learning, see Table 1, cross-silo federated learning admits more flexibility in certain aspects of the overall design, but at the same time presents a setting where achieving other properties can be harder. This section discusses some of these differences.

The cross-silo setting can be relevant where a number of companies or organizations share incentive to train a model based on all of their data, but cannot share their data directly. This could be due to constraints imposed by confidentiality or due to legal constraints, or even within a single company when they cannot centralize their data between different geographical regions. These cross-silo applications have attracted substantial attention.
**Data partitioning** In the cross-device setting the data is assumed to be partitioned by examples. In the cross-silo setting, in addition to partitioning by examples, partitioning by features is of practical relevance. An example could be when two companies in different businesses have the same or overlapping set of customers, such as a local bank and a local retail company in the same city. This difference has been also referred to as horizontal and vertical federated learning by Yang et al. [490].

Cross-silo FL with data partitioned by features, employs a very different training architecture compared to the setting with data partitioned by example. It may or may not involve a central server as a neutral party, and based on specifics of the training algorithm, clients exchange specific intermediate results rather than model parameters, to assist other parties' gradient calculations; see for instance [490, Section 2.4.2]. In this setting, application of techniques such as secure multi-party computation or homomorphic encryption have been proposed in order to limit the amount of information other participants can infer from observing the training process. The downside of this approach is that the training algorithm is typically dependent on the type of machine learning objective being pursued. Currently proposed algorithms include trees [118], linear and logistic regression [490, 224, 316], and neural networks [317]. Local updates similar to Federated Average (see Section 3.2) has been proposed to address the communication challenges of feature-partitioned systems [316], and [238, 318] study the security and privacy related challenges inherent in such systems.

Federated transfer learning [490] is another concept that considers challenging scenarios in which data parties share only a partial overlap in the user space or the feature space, and leverage existing transfer learning techniques [365] to build models collaboratively. The existing formulation is limited to the case of 2 clients.

Partitioning by examples is usually relevant in cross-silo FL when a single company cannot centralize their data due to legal constraints, or when organizations with similar objectives want to collaboratively improve their models. For instance, different banks can collaboratively train classification or anomaly detection models for fraud detection [476], hospitals can build better diagnostic models [139], and so on.

An open-source platform supporting the above outlined applications is currently available as *Federated AI Technology Enabler (FATE)* [33]. At the same time, the IEEE P3652.1 Federated Machine Learning Working Group is focusing on standard-setting for the Federated AI Technology Framework. Other platforms include [125] focused on a range of medical applications and [321] for enterprise use cases. See Appendix A for more details.

**Incentive mechanisms** In addition to developing new algorithmic techniques for FL, incentive mechanism design for honest participation is an important practical research question. This need may arise in cross-device settings (e.g. [261, 260]), but is particularly relevant in the cross-silo setting, where participants may at the same time also be business competitors. The incentive can be in the form of monetary payout [499] or final models with different levels of performance [324]. The option to deliver models with performance commensurate to the contributions of each client is especially relevant in collaborative learning situations in which competitions exist among FL participants. Clients might worry that contributing their data to training federated learning models will benefit their competitors, who do not contribute as much but receive the same final model nonetheless (i.e. the free-rider problem). Related objectives include how to divide earnings generated by the federated learning model among contributing data owners in order to sustain long-term participation, and also how to link the incentives with decisions on defending against adversarial data owners to enhance system security, optimizing the participation of data owners to enhance system efficiency.
**Differential privacy** The discussion of actors and threat models in Section 4.1 is largely relevant also for the cross-silo FL. However, protecting against different actors might have different priorities. For example, in many practical scenarios, the final trained model would be released only to those who participate in the training, which makes the concerns about “the rest of the world” less important.

On the other hand, for a practically persuasive claim, we would usually need a notion of local differential privacy, as the potential threat from other clients is likely to be more important. In cases when the clients are not considered a significant threat, each client could control the data from a number of their respective users, and a formal privacy guarantee might be needed on such user-level basis. Depending on application, other objectives could be worth pursuing. This area has not been systematically explored.

**Tensor factorization** Several works have also studied cross-silo federated tensor factorization where multiple sites (each having a set of data with the same feature, i.e. horizontally partitioned) jointly perform tensor factorization by only sharing intermediate factors with the coordination server while keeping data private at each site. Among the existing works, [272] used an alternating direction method of multipliers (ADMM) based approach and [325] improved the efficiency with the elastic averaging SGD (EASGD) algorithm and further ensures differential privacy for the intermediate factors.

## 2.3 Split Learning

In contrast with the previous settings which focus on data partitioning and communication patterns, the key idea behind split learning [215, 460]$^3$ is to split the execution of a model on a per-layer basis between the clients and the server. This can be done for both training and inference.

In the simplest configuration of split learning, each client computes the forward pass through a deep network up to a specific layer referred to as the *cut layer*. The outputs at the cut layer, referred to as *smashed data*, are sent to another entity (either the server or another client), which completes the rest of the computation. This completes a round of forward propagation without sharing the raw data. The gradients can then be back propagated from its last layer until the cut layer in a similar fashion. The gradients at the cut layer – and only these gradients – are sent back to the clients, where the rest of back propagation is completed. This process is continued until convergence, without having clients directly access each others raw data. This setup is shown in Figure 2(a) and a variant of this setup where labels are also not shared along with raw data is shown in Figure 2(b). Split learning approaches for data partitioned by features have been studied in [101].

In several settings, the overall communication requirements of split learning and federated learning were compared in [421]. Split learning brings in another dimension of parallelism in the training, parallelization among parts of a model, e.g. client and server. The ideas in [245, 240], where the authors break the dependencies between partial networks and reduced total centralized training time by parallelizing the computations in different parts, can be relevant here as well. However, it is still an open question to explore such parallelization of split learning on edge devices. Split learning also enables matching client-side model components with the best server-side model components for automating model selection as shown in the ExpertMatcher [413].

The values communicated can nevertheless, in general, reveal information about the underlying data. How much, and whether this is acceptable, is likely going to be application and configuration specific. A variation of split learning called NoPeek SplitNN [462] reduces the potential leakage via communicated activations, by reducing their distance correlation [461, 442] with the raw data, while maintaining good model

<footnote>$^3$See also split learning project website - https://splitlearning.github.io/.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 2: Split learning configurations showing raw data is not transferred in the vanilla setting and that raw data as well as labels are not transferred between the client and server entities in the U-shaped split learning setting.</figcaption></figure>

performance via categorical cross-entropy. The key idea is to minimize the distance correlation between the raw data points and communicated smashed data. The objects communicated could otherwise contain information highly correlated with the input data if used without NoPeek SplitNN, the use of which also enables the split to be made relatively early-on given the decorrelation it provides. One other engineering driven approach to minimize the amount of information communicated in split learning has been via a specifically learnt pruning of channels present in the client side activations [422]. Overall, much of the discussion in Section 4 is relevant here as well, and analysis providing formal privacy guarantees specifically for split learning is still an open problem.

## 2.4 Executive summary

The motivation for federated learning is relevant for a number of related areas of research.

* Fully decentralized learning (Section 2.1) removes the need for a central server coordinating the overall computation. Apart from algorithmic challenges, open problems are in practical realization of the idea and in understanding of what form of trusted central authority is needed to set up the task.

* Cross-silo federated learning (Section 2.2) admits problems with different kinds of modelling constraints, such as data partitioned by examples and/or features, and faces different set of concerns when formulating formal privacy guarantees or incentive mechanisms for clients to participate.

* Split learning (Section 2.3) is an approach to partition the execution of a model between the clients and the server. It can deliver different options for overall communication constraints, but detailed analysis of when the communicated values reveal sensitive information is still missing.
# 3 Improving Efficiency and Effectiveness

In this section we explore a variety of techniques and open questions that address the challenge of making federated learning more efficient and effective. This encompasses a myriad of possible approaches, including: developing better optimization algorithms; providing different models to different clients; making ML tasks like hyperparameter search, architecture search, and debugging easier in the FL context; improving communication efficiency; and more.

One of the fundamental challenges in addressing these goals is the presence of non-IID data, so we begin by surveying this issue and highlighting potential mitigations.

## 3.1 Non-IID Data in Federated Learning

While the meaning of IID is generally clear, data can be non-IID in many ways. In this section, we provide a taxonomy of non-IID data regimes that may arise for any client-partitioned dataset. The most common sources of dependence and non-identicalness are due to each client corresponding to a particular user, a particular geographic location, and/or a particular time window. This taxonomy has a close mapping to notions of dataset shift [353, 380], which studies differences between the training distribution and testing distribution; here, we consider differences in the data distribution on each client.

For the following, consider a supervised task with features $x$ and labels $y$. A statistical model of federated learning involves two levels of sampling: accessing a datapoint requires first sampling a client $i \sim Q$, the distribution over available clients, and then drawing an example $(x, y) \sim P_i(x, y)$ from that client's local data distribution.

When non-IID data in federated learning is referenced, this typically refers to differences between $P_i$ and $P_j$ for different clients $i$ and $j$. However, it is also important to note that the distribution $Q$ and $P_i$ may change over time, introducing another dimension of “non-IIDness”.

For completeness, we note that even considering the dataset on a single device, if the data is in an insufficiently-random order, e.g. ordered by time, then independence is violated locally as well. For example, consecutive frames in a video are highly correlated. Sources of intra-client correlation can generally be resolved by local shuffling.

**Non-identical client distributions** We first survey some common ways in which data tend to deviate from being identically distributed, that is $P_i \neq P_j$ for different clients $i$ and $j$. Rewriting $P_i(x, y)$ as $P_i(y|x)P_i(x)$ and $P_i(x|y)P_i(y)$ allows us to characterize the differences more precisely.

* *Feature distribution skew (covariate shift):* The marginal distributions $P_i(x)$ may vary across clients, even if $P(y|x)$ is shared.<fnref n="4" /> For example, in a handwriting recognition domain, users who write the same words might still have different stroke width, slant, etc.

* *Label distribution skew (prior probability shift):* The marginal distributions $P_i(y)$ may vary across clients, even if $P(x|y)$ is the same. For example, when clients are tied to particular geo-regions, the distribution of labels varies across clients — kangaroos are only in Australia or zoos; a person's face is only in a few locations worldwide; for mobile device keyboards, certain emoji are used by one demographic but not others.

<footnote n="4">⁴We write “$P(y|x)$ is shared” as shorthand for $P_i(y|x) = P_j(y|x)$ for all clients $i$ and $j$.</footnote>
* *Same label, different features (concept drift)*: The conditional distributions $P_i(x|y)$ may vary across clients even if $P(y)$ is shared. The same label $y$ can have very different features $x$ for different clients, e.g. due to cultural differences, weather effects, standards of living, etc. For example, images of homes can vary dramatically around the world and items of clothing vary widely. Even within the U.S., images of parked cars in the winter will be snow-covered only in certain parts of the country. The same label can also look very different at different times, and at different time scales: day vs. night, seasonal effects, natural disasters, fashion and design trends, etc.

* *Same features, different label (concept shift)*: The conditional distribution $P_i(y|x)$ may vary across clients, even if $P(x)$ is the same. Because of personal preferences, the same feature vectors in a training data item can have different labels. For example, labels that reflect sentiment or next word predictors have personal and regional variation.

* *Quantity skew or unbalancedness*: Different clients can hold vastly different amounts of data.

Real-world federated learning datasets likely contain a mixture of these effects, and the characterization of cross-client differences in real-world partitioned datasets is an important open question. Most empirical work on synthetic non-IID datasets (e.g. [337, 236]) have focused on label distribution skew, where a non-IID dataset is formed by partitioning a “flat” existing dataset based on the labels. A better understanding of the nature of real-world non-IID datasets will allow for the construction of controlled but realistic non-IID datasets for testing algorithms and assessing their resilience to different degrees of client heterogeneity.

Further, different non-IID regimes may require the development of different mitigation strategies. For example, under feature-distribution skew, because $P(y|x)$ is assumed to be common, the problem is at least in principle well specified, and training a single global model that learns $P(y|x)$ may be appropriate. When the same features map to different labels on different clients, some form of personalization (Section 3.3) may be essential to learning the true labeling functions.

**Violations of independence** Violations of independence are introduced any time the distribution $Q$ changes over the course of training; a prominent example is in cross-device FL, where devices typically need to meet eligibility requirements in order to participate in training (see Section 1.1.2). Devices typically meet those requirements at night local time (when they are more likely to be charging, on free wi-fi, and idle), and so there may be significant diurnal patterns in device availability. Further, because local time of day corresponds directly to longitude, this introduces a strong geographic bias in the source of the data. Eichner et al. [171] described this issue and some mitigation strategies, but many open questions remain.

**Dataset shift** Finally, we note that the temporal dependence of the distributions $Q$ and $P$ may introduce dataset shift in the classic sense (differences between the train and test distributions). Furthermore, other criteria may make the set of clients eligible to train a federated model different from the set of clients where that model will be deployed. For example, training may require devices with more memory than is needed for inference. These issues are explored in more depth in Section 6. Adapting techniques for handling dataset shift to federated learning is another interesting open question.

### 3.1.1 Strategies for Dealing with Non-IID Data

The original goal of federated learning, training a single global model on the union of client datasets, becomes harder with non-IID data. One natural approach is to modify existing algorithms (e.g. through
different hyperparameter choices) or develop new ones in order to more effectively achieve this objective.
This approach is considered in Section 3.2.2.

For some applications, it may be possible to augment data in order to make the data across clients more similar. One approach is to create a small dataset which can be shared globally. This dataset may originate from a publicly available proxy data source, a separate dataset from the clients' data which is not privacy sensitive, or perhaps a distillation of the raw data following Wang et al. [473].

The heterogeneity of client objective functions gives additional importance to the question of how to craft the objective function — it is no-longer clear that treating all examples equally makes sense. Alternatives include limiting the contributions of the data from any one user (which is also important for privacy, see Section 4) and introducing other notions of fairness among the clients; see discussion in Section 6.

But if we have the capability to run training on the local data on each device (which is necessary for federated learning of a global model), is training a single global model even the right goal? There are many cases where having a single model is to be preferred, e.g. in order to provide a model to clients with no data, or to allow manual validation and quality assurance before deployment. Nevertheless, since local training is possible, it becomes feasible for each client to have a customized model. This approach can turn the non-IID problem from a bug to a feature, almost literally — since each client has its own model, the client's identity effectively parameterizes the model, rendering some pathological but degenerate non-IID distributions trivial. For example, if for each i, $P_i(y)$ has support on only a single label, finding a high-accuracy global model may be very challenging (especially if x is relatively uninformative), but training a high-accuracy local model is trivial (only a constant prediction is needed). Such multi-model approaches are considered in depth in Section 3.3. In addition to addressing non-identical client distributions, using a plurality of models can also address violations of independence stemming from changes in client availability. For example, the approach of Eichner et al. [171] uses a single training run but averages different iterates in order to provide different models for inference based on the timezone / longitude of clients.

## 3.2 Optimization Algorithms for Federated Learning

In prototypical federated learning tasks, the goal is to learn a single global model that minimizes the empirical risk function over the entire training dataset, that is, the union of the data across all the clients. The main difference between federated optimization algorithms and standard distributed training methods is the need to address the characteristics of Table 1 — for optimization, non-IID and unbalanced data, limited communication bandwidth, and unreliable and limited device availability are particularly salient.

FL settings where the total number of devices is huge (e.g. across mobile devices) necessitate algorithms that only require a handful of clients to participate per round (client sampling). Further, each device is likely to participate no more than once in the training of a given model, so stateless algorithms are necessary. This rules out the direct application of a variety of approaches that are quite effective in the datacenter context, for example stateful optimization algorithms like ADMM, and stateful compression strategies that modify updates based on residual compression errors from previous rounds.

Another important practical consideration for federated learning algorithms is composability with other techniques. Optimization algorithms do not run in isolation in a production deployment, but need to be combined with other techniques like cryptographic secure aggregation protocols (Section 4.2.1), differential privacy (DP) (Section 4.2.2), and model and update compression (Section 3.5). As noted in Section 1.1.2, many of these techniques can be applied to primitives like “sum over selected clients” and “broadcast to selected clients”, and so expressing optimization algorithms in terms of these primitives provides a valuable separation of concerns, but may also exclude certain techniques such as ap-
<table><caption>Table 4: Notation for the discussion of FL algorithms including Federated Averaging.</caption><tr><td>N</td><td>Total number of clients</td></tr><tr><td>M</td><td>Clients per round</td></tr><tr><td>T</td><td>Total communication rounds</td></tr><tr><td>K</td><td>Local steps per round.</td></tr></table>

**Server executes:**
initialize $x_0$
**for** each round $t = 1, 2, \dots, T$ **do**
  $S_t$ ← (random set of $M$ clients)
  **for** each client $i \in S_t$ **in parallel do**
    $x_{t+1}^i$ ← ClientUpdate($i, x_t$)
    $x_{t+1}$ ← $\sum_{k=1}^M \frac{1}{M} x_{t+1}^k$

**ClientUpdate**($i, x$):
**for** local step $j = 1, \dots, K$ **do**
  $x$ ← $x - \eta \nabla f(x; z)$ for $z \sim P_i$
  return $x$ to server

Algorithm 1: Federated Averaging (local SGD), when all clients have the same amount of data.

plying updates asynchronously.

One of the most common approaches to optimization for federated learning is the Federated Averaging algorithm [337], an adaption of local-update or parallel SGD.<fnref n="5" /> Here, each client runs some number of SGD steps locally, and then the updated local models are averaged to form the updated global model on the coordinating server. Pseudocode is given in Algorithm 1.

Performing local updates and communicating less frequently with the central server addresses the core challenges of respecting data locality constraints and of the limited communication capabilities of mobile device clients. However, this family of algorithms also poses several new algorithmic challenges from an optimization theory point of view. In Section 3.2, we discuss recent advances and open challenges in federated optimization algorithms for the cases of IID and non-IID data distribution across the clients respectively. The development of new algorithms that specifically target the characteristics of the federated learning setting remains an important open problem.

### 3.2.1 Optimization Algorithms and Convergence Rates for IID Datasets

While a variety of different assumptions can be made on the per-client functions being optimized, the most basic split is between assuming IID and non-IID data. Formally, having IID data at the clients means that each mini-batch of data used for a client's local update is statistically identical to a uniformly drawn sample (with replacement) from the entire training dataset (the union of all local datasets at the clients). Since the clients independently collect their own training data which vary in both size and distribution, and these data are not shared with other clients or the central node, the IID assumption clearly almost never holds in practice. However, this assumption greatly simplifies theoretical convergence analysis of federated optimization algorithms, as well as establishes a baseline that can be used to understand the impact of non-IID data on optimization rates. Thus, a natural first step is to obtain an understanding of the landscape of optimization algorithms for the IID data case.

<footnote n="5">⁵Federated Averaging applies local SGD to a randomly sampled subset of clients on each round, and proposes a specific update weighting scheme.</footnote>
Formally, for the IID setting let us standardize the stochastic optimization problem

$$ \min_{x \in \mathbb{R}^m} F(x) := \mathbb{E}_{z \sim \mathcal{P}} [f(x; z)]. $$

We assume an intermittent communication model as in e.g. Woodworth et al. [480, Sec. 4.4], where $M$ stateless clients participate in each of $T$ rounds, and during each round, each client can compute gradients for $K$ samples (e.g. minibatches) $z_1, \dots, z_K$ sampled IID from $\mathcal{P}$ (possibly using these to take sequential steps). In the IID-data setting clients are interchangeable, and we can without loss of generality assume $M = N$. Table 4 summarizes the notation used in this section.

Different assumptions on $f$ will produce different guarantees. We will first discuss the convex setting and later review results for non-convex problems.

**Baselines and state-of-the-art for convex problems** In this section we review convergence results for $H$-smooth, convex (but not necessarily strongly convex) functions under the assumption that the variance of the stochastic gradients is bounded by $\sigma^2$. More formally, by $H$-smooth we mean that for all $z, f(\cdot; z)$ is differentiable and has a $H$-Lipschitz gradient, that is, for all choices of $x, y$

$$ \|\nabla f(x, z) - \nabla f(y, z)\| \le H \|x - y\|. $$

We also assume that for all $x$, the stochastic gradient $\nabla_x f(x; z)$ satisfies

$$ \mathbb{E}_{z \sim \mathcal{P}} \| \nabla_x f(x; z) - \nabla f(x) \| \le \sigma^2. $$

When analyzing the convergence rate of an algorithm with output $x_T$ after $T$ iterations, we consider the term

$$ \mathbb{E}[F(x_T)] - F(x^*) \quad (1) $$

where $x^* = \arg \min_x F(x)$. All convergence rates discussed herein are upper bounds on this term. A summary of convergence results for such functions is given in Table 5.

Federated averaging (a.k.a. parallel SGD/local SGD) competes with two natural baselines: First, we may keep $x$ fixed in local updates during each round, and compute a total of $KM$ gradients at the current $x$, in order to run accelerated minibatch SGD. Let $\bar{x}$ denote the average of $T$ iterations of this algorithm. We then have the upper bound

$$ \mathcal{O}\left(\frac{H}{T^2} + \frac{\sigma}{\sqrt{TKM}}\right) $$

for convex objectives [294, 137, 151]. Note that the first expectation is taken with respect to the randomness of $z$ in the training procedure as well.

A second natural baseline is to ignore all but 1 of the $M$ active clients, which allows (accelerated) sequential SGD to execute for $KT$ steps. Applying the same general bounds cited above, this approach offers an upper bound of

$$ \mathcal{O}\left(\frac{H}{(TK)^2} + \frac{\sigma}{\sqrt{TK}}\right). $$

Comparing these two results, we see that minibatch SGD attains the optimal ‘statistical’ term $(\sigma/\sqrt{TKM})$, whilst SGD on a single device (ignoring the updates of the other devices) achieves the optimal ‘optimization’ term $(H/(TK)^2)$.

The convergence analysis of local-update SGD methods is an active current area of research [434, 310, 500, 467, 390, 371, 269, 481]. The first convergence results for local-update SGD methods were derived
<table><thead><tr><th>Method</th><th>Comments</th><th>Convergence</th></tr></thead><tbody><tr><td colspan="3"><strong>Baselines</strong></td></tr><tr><td>mini-batch SGD</td><td>batch size KM</td><td>O (<sup>H</sup>/<sub>T</sub> + <sup>σ</sup>/<sub>√TKM</sub>)</td></tr><tr><td>SGD</td><td>(on 1 worker, no communication)</td><td>O (<sup>H</sup>/<sub>TK</sub> + <sup>σ</sup>/<sub>√TK</sub>)</td></tr><tr><td colspan="3"><strong>Baselines with acceleration<sup>a</sup></strong></td></tr><tr><td>A-mini-batch SGD [294, 137]</td><td>batch size KM</td><td>O (<sup>H</sup>/<sub>T<sup>2</sup></sub> + <sup>σ</sup>/<sub>√TKM</sub>)</td></tr><tr><td>A-SGD [294]</td><td>(on 1 worker, no communication)</td><td>O (<sup>H</sup>/<sub>(TK)<sup>2</sup></sub> + <sup>σ</sup>/<sub>√TK</sub>)</td></tr><tr><td colspan="3"><strong>Parallel SGD / Fed-Avg / Local SGD</strong></td></tr><tr><td>Yu et al. [500]<sup>b</sup>, Stich [434]<sup>c</sup></td><td>gradient norm bounded by G</td><td>O (<sup>HKM</sup>/<sub>T</sub> <sup>G<sup>2</sup></sup>/<sub>σ<sup>2</sup></sub> + <sup>σ</sup>/<sub>√TKM</sub>)</td></tr><tr><td>Wang and Joshi [467]<sup>b</sup>, Stich and Karimireddy [435]</td><td></td><td>O (<sup>HM</sup>/<sub>T</sub> + <sup>σ</sup>/<sub>√TKM</sub>)</td></tr><tr><td colspan="3"><strong>Other algorithms</strong></td></tr><tr><td>SCAFFOLD [265]</td><td>control variates and two stepsizes</td><td>O (<sup>H</sup>/<sub>T</sub> + <sup>σ</sup>/<sub>√TKM</sub>)</td></tr></tbody></table>

<caption>Table 5: Convergence rates for a (non-comprehensive) set of distributed optimization algorithms in the IID-data setting. We assume *M* devices participate in each iterations, and the loss functions are *H*-smooth, convex, and we have access to stochastic gradients with variance at most *σ*². All rates are upper bounds on (1) after *T* iterations (potentially with some iterate averaging scheme).</caption>

under the bounded gradient norm assumption in Stich [434] for strongly-convex and in Yu et al. [500] for non-convex objective functions. These analyses could attain the desired $\sigma/\sqrt{TKM}$ statistical term with suboptimal optimization term (in Table 5 we summarize these results for the middle ground of convex functions).

By removing the bounded gradient assumption, Wang and Joshi [467] and Stich and Karimireddy [435] could further improve the optimization term to $HM/T$. These result show that if the number of local steps *K* is smaller than $T/M^3$ then the (optimal) statistical term is dominating the rate. However, for typical cross-device applications we might have $T = 10^6$ and $M = 100$ (Table 2), implying $K = 1$.

Often in the literature the convergence bounds are accompanied by a discussion on how large *K* may be chosen in order to reach asymptotically the same statistical term as the convergence rate of mini-batch SGD. For strongly convex functions, this bound was improved by Khaled et al. [269] and further in Stich and Karimireddy [435].

For non-convex objectives, Yu et al. [500] showed that local SGD can achieve asymptotically an error bound $1/\sqrt{TKM}$ if the number of local updates *K* are smaller than $T^{1/3}/M$. This convergence guarantee was further improved by Wang and Joshi [467] who removed the bounded gradient norm assumption and showed that the number of local updates can be as large as $T/M^3$. The analysis in [467] can also be applied to other algorithms with local updates, and thus yields the first convergence guarantee for decentralized SGD with local updates (or periodic decentralized SGD) and elastic averaging SGD [505]. Haddadpour et al. [216] improves the bounds in Wang and Joshi [467] for functions satisfying the Polyak-Lojasiewicz

<footnote><sup>a</sup>There are no accelerated fed-avg/local SGD variants so far</footnote>

<footnote><sup>b</sup>This paper considers the smooth non-convex setting, we adapt here the results for our setting.</footnote>

<footnote><sup>c</sup>This paper considers the smooth strongly convex setting, we adapt here the results for our setting.</footnote>
(PL) condition [262], a generalization of strong convexity. In particular, Haddadpour et al. [216] show that for PL functions, $T^2/M$ local updates per round leads to a $O(1/TKM)$ convergence.

While the above works focus on convergence as a function of the number of iterations performed, practitioners often care about wall-clock convergence speed. Assessing this must take into account the effect of the design parameters on the time spent per iteration based on the relative cost of communication and local computation. Viewed in this light, the focus on seeing how large $K$ can be while maintaining the statistical rate may not be the primary concern in federated learning, where one may assume almost infinite datasets (very large $N$). The costs (at least in wall-clock time) are small for increasing $M$, and so it may be more natural to increase $M$ sufficiently to match the optimization term, and then tune $K$ to maximize wall-clock optimization performance. How then to choose $K$? Performing more local updates at the clients will increase the divergence between the resulting local models at the clients, before they are averaged. As a result, the error convergence in terms of training loss versus the total number of sequential SGD steps $TK$ is slower. However, performing more local updates saves significant communication cost and reduces the time spent per iteration. The optimal number of local updates strikes a balance between these two phenomena and achieves the fastest error versus wallclock time convergence. Wang and Joshi [468] propose an adaptive communication strategy that adapts $K$ according to the training loss at regular intervals during the training.

Another important design parameter in federated learning is the model aggregation method used to update the global model using the updates made by the selected clients. In the original federated learning paper, McMahan et al. [337] proposes taking a weighted average of the local models, in proportion to the size of local datasets. For IID data, where each client is assumed to have a infinitely large dataset, this reduces to taking a simple average of the local models. However, it is unclear whether this aggregation method will result in the fastest error convergence.

There are many open questions in federated optimization, even with IID data. Woodworth et al. [480] highlights several gaps between upper and lower bounds for optimization relevant to the federated learning setting, particularly for “intermittent communication graphs”, which captures local SGD approaches, but convergence rates for such approaches are not known to match the corresponding lower bounds. In Table 5 we highlight convergence results for the convex setting. Whilst most schemes are able to reach the asymptotically dominant statistical term, none are able to match the convergence rate of accelerated mini-batch SGD. It is an open problem if federated averaging algorithms can close this gap.

Local-update SGD methods where all $M$ clients perform the same number of local updates may suffer from a common scalability issue—they can be bottlenecked if any one client unpredictably slows down or fails. Several approaches for dealing with this are possible, but it is far from clear which are optimal, especially when the potential for bias is considered (see Section 6). Bonawitz et al. [81] propose overprovisioning clients (e.g., request updates from $1.3M$ clients), and then accepting the first $M$ updates received and rejecting updates from stragglers. A slightly more sophisticated solution is to fix a time window and allow clients to perform as many local updates $K_i$ as possible within this time, after which their models are averaged by a central server. Wang et al. [471] analyzed the computational heterogeneity introduced by this approach in theory. An alternative method to overcome the problem of straggling clients is to fix the number of local updates at $\tau$, but allow clients to update the global model in an asynchronous or lock-free fashion. Although some previous works [505, 306, 163] have proposed similar methods, the error convergence analysis is an open and challenging problem. A larger challenge in the FL setting, however, is that as discussed at the beginning of Section 3.2, asynchronous approaches may be difficult to combine with complimentary techniques like differential privacy or secure aggregation.

Besides the number of local updates, the choice of the size of the set of clients selected per training round presents a similar trade-off as the number of local updates. Updating and averaging a larger number of client models per training round yields better convergence, but it makes the training vulnerable to slowdown due
to unpredictable tail delays in computation/communication at/with the clients.

The analysis of local SGD / Federated Averaging in the non-IID setting is even more challenging; results and open questions related to this are considered in the next section, along with specialized algorithms which directly address the non-IID problem.

### 3.2.2 Optimization Algorithms and Convergence Rates for Non-IID Datasets

In contrast to well-shuffled mini-batches consisting of independent and identically distributed (IID) examples in centralized learning, federated learning uses local data from end user devices, leading to many varieties of non-IID data (Section 3.1).

In this setting, each of $N$ clients has a local data distribution $\mathcal{P}_i$ and a local objective function

$$f_i(x) = \mathbb{E}_{z \sim \mathcal{P}_i} [f(x; z)]$$

where we recall that $f(x; z)$ is the loss of a model $x$ at an example $z$. We typically wish to minimize

$$F(x) = \frac{1}{N} \sum_{i=1}^{N} f_i(x). \qquad (2)$$

Note that we recover the IID setting when each $\mathcal{P}_i$ is identical. We will let $F^*$ denote the minimum value of $F$, obtained the point $x^*$. Analogously, we will let $f_i^*$ denote the minimum value of $f_i$.

As in the IID setting, we assume an intermittent communication model (e.g. Woodworth et al. [480, Sec. 4.4]), where $M$ stateless clients participate in each of $T$ rounds, and during each round, each client can compute gradients for $K$ samples (e.g. minibatches). The difference here is that the samples $z_{i,1}, \dots, z_{i,K}$ sampled at client $i$ are drawn from the client's local distribution $\mathcal{P}_i$. Unlike the IID setting, we cannot necessarily assume $M = N$, as the client distributions are not all equal. In the following, if an algorithm relies on $M = N$, we will omit $M$ and simply write $N$. We note that while such an assumption may be compatible with the cross-silo federated setting in Table 1, it is generally infeasible in the cross-device setting.

While [434, 500, 467, 435] mainly focused on the IID case, the analysis technique can be extended to the non-IID case by adding an assumption on data dissimilarities, for example by constraining the difference between client gradients and the global gradient [305, 300, 304, 469, 471] or the difference between client and global optimum values [303, 268]. Under this assumption, Yu et al. [501] showed that the error bound of local SGD in the non-IID case becomes worse. In order to achieve the rate of $1/\sqrt{TKN}$ (under non-convex objectives), the number of local updates $K$ should be smaller than $T^{1/3}/N$, instead of $T/N^3$ as in the IID case [467]. Li et al. [300] proposed to add a proximal term in each local objective function so as to make the algorithm be more robust to the heterogeneity across local objectives. The proposed FedProx algorithm empirically improves the performance of federated averaging. Khaled et al. [268] assumes all clients participate, and uses batch gradient descent on clients, which can potentially converge faster than stochastic gradients on clients.

Recently, a number of works have made progress in relaxing the assumptions necessary for analysis so as to better apply to practical uses of Federated Averaging. For example, Li et al. [303] studied the convergence of Federated Averaging in a more realistic setting where only a subset of clients are involved in each round. In order to guarantee the convergence, they assumed that the clients are selected either uniformly at random or with probabilities that are in proportion to the sizes of local datasets. Nonetheless, in practice the server may not be able to sample clients in these idealized ways — in particular, in cross-device settings only
## Non-IID assumptions

<table><thead><tr><th>Symbol</th><th>Full name</th><th>Explanation</th></tr></thead><tbody><tr><td>BCGV</td><td>bounded inter-client gradient variance</td><td>E<sub>i</sub> ||∇f<sub>i</sub>(x) − ∇F(x)||<sup>2</sup> ≤ η<sup>2</sup></td></tr><tr><td>BOBD</td><td>bounded optimal objective difference</td><td>F* − E<sub>i</sub>[f<sub>i</sub>]<sup>*</sup> ≤ η<sup>2</sup></td></tr><tr><td>BOGV</td><td>bounded optimal gradient variance</td><td>E<sub>i</sub> ||∇f<sub>i</sub>(x*)||<sup>2</sup> ≤ η<sup>2</sup></td></tr><tr><td>BGV</td><td>bounded gradient dissimilarity</td><td>E<sub>i</sub> ||∇f<sub>i</sub>(x)||<sup>2</sup>/||∇F(x)||<sup>2</sup> ≤ η<sup>2</sup></td></tr></tbody></table>

## Other assumptions and variants

<table><thead><tr><th>Symbol</th><th>Explanation</th></tr></thead><tbody><tr><td>CVX</td><td>Each client function f<sub>i</sub>(x) is convex.</td></tr><tr><td>SCVX</td><td>Each client function f<sub>i</sub>(x) is μ-strongly convex.</td></tr><tr><td>BNCVX</td><td>Each client function has bounded nonconvexity with ∇<sup>2</sup>f<sub>i</sub>(x) ≃ −μI.</td></tr><tr><td>BLGV</td><td>The variance of stochastic gradients on local clients is bounded.</td></tr><tr><td>BLGN</td><td>The norm of any local gradient is bounded.</td></tr><tr><td>LBG</td><td>Clients use the full batch of local samples to compute updates.</td></tr><tr><td>Dec</td><td>Decentralized setting, assumes the connectivity of network is good.</td></tr><tr><td>AC</td><td>All clients participate in each round.</td></tr><tr><td>1step</td><td>One local update is performed on clients in each round.</td></tr><tr><td>Prox</td><td>Use proximal gradient steps on clients.</td></tr><tr><td>VR</td><td>Variance reduction which needs to track the state.</td></tr></tbody></table>

## Convergence rates

<table><caption>Table 6: Convergence rates for a (non-comprehensive) set of federated optimization methods in non-IID settings. We summarize the key assumptions for non-IID data, local functions on each client, and other assumptions. We also present the variant of the algorithm comparing to Federated Averaging and the convergence rates that eliminate constant.</caption><thead><tr><th>Method</th><th>Non-IID</th><th>Other assumptions</th><th>Variant</th><th>Rate</th></tr></thead><tbody><tr><td>Lian et al. [305]</td><td>BCGV</td><td>BLGV</td><td>Dec; AC; 1step</td><td>O(1/T) + O(1/√NT)</td></tr><tr><td>PD-SGD [304]</td><td>BCGV</td><td>BLGV</td><td>Dec; AC</td><td>O(N/T) + O(1/√NT)</td></tr><tr><td>MATCHA [469]</td><td>BCGV</td><td>BLGV</td><td>Dec</td><td>O(1/√TKM) + O(M/KT)</td></tr><tr><td>Khaled et al. [268]</td><td>BOGV</td><td>CVX</td><td>AC; LBG</td><td>O(N/T) + O(1/√NT)</td></tr><tr><td>Li et al. [303]</td><td>BOBD</td><td>SCVX; BLGV; BLGN</td><td>-</td><td>O(K/T)</td></tr><tr><td>FedProx [300]</td><td>BGV</td><td>BNCVX</td><td>Prox</td><td>O(1/√T)</td></tr><tr><td>SCAFFOLD [265]</td><td>-</td><td>SCVX; BLGV</td><td>VR</td><td>O(1/TKM) + O(e<sup>-T</sup>)</td></tr></tbody></table>
devices that meet strict eligibility requirements (e.g. charging, idle, free WiFi) will be selected to participate
in the computation. At different times within a day, the clients characteristics can vary significantly. Eichner
et al. [171] formulated this problem and studied the convergence of semi-cyclic SGD, where multiple blocks
of clients with different characteristics are sampled from following a regular cyclic pattern (e.g. diurnal).
Clients can perform different local steps because of heterogeneity in their computing capacities. Wang
et al. [471] proves that FedAvg and many other federated learning algorithms will converge to the stationary
points of a mismatched objective function in the presence of heterogeneous local steps. They refer to this
problem as *objective inconsistency* and propose a simple technique to eliminate the inconsistency problem
from federated learning algorithms.

We summarize recent theoretical results in Table 6. All the methods in Table 6 assume smoothness or Lipschitz gradients for the local functions on clients. The error bound is measured by optimal objective (1) for convex functions and norm of gradient for nonconvex functions. For each method, we present the key non-IID assumption, assumptions on each client function $f_i(x)$, and other auxiliary assumptions. We also briefly describe each method as a variant of the federated averaging algorithm, and show the simplified convergence rate eliminating constants. Assuming the client functions are strongly convex could help the convergence rate [303, 265]. Bounded gradient variance, which is a widely used assumption to analyze stochastic gradient methods, is often used when clients use stochastic local updates [305, 303, 304, 469, 265]. Li et al. [303] directly analyzes the Federated Averaging algorithm, which applies $K$ steps of local updates on randomly sampled $M$ clients in each round, and presents a rate that suggests local updates ($K > 1$) could slow down the convergence. Clarifying the regimes where $K > 1$ may hurt or help convergence is an important open problem.

**Connections to decentralized optimization** The objective function of federated optimization has been studied for many years in the decentralized optimization community. As first shown in Wang and Joshi [467], the convergence analysis of decentralized SGD can be applied to or combined with local SGD with a proper setting of the network topology matrix (mixing matrix). In order to reduce the communication overhead, Wang and Joshi [467] proposed periodic decentralized SGD (PD-SGD) which allows decentralized SGD to have multiple local updates as Federated Averaging. This algorithm is extended by Li et al. [304] to the non-IID case. MATCHA [469] further improves the performance of PD-SGD by randomly sampling clients for computation and communication, and provides a convergence analysis showing that local updates can accelerate convergence.

**Acceleration, variance reduction and adaptivity** Momentum, variance-reduction, and adaptive learning rates are all promising techniques to improve convergence and generalization of first-order methods. However, there is no single manner in which to incorporate these techniques into FedAvg. SCAFFOLD [265] models the difference in client updates using control variates to perform variance reduction. Notably, this allows convergence results not relying on bounding the amount of heterogeneity among clients. As for momentum, Yu et al. [501] propose allowing each client to maintain a local momentum buffer and average the local buffers and the local model parameters at each communication round. Although this method empirically improves the final accuracy of local SGD, this doubles the per-round communication cost. A similar scheme is used by Xie et al. [485] to design a variant of local SGD in which clients locally perform Adagrad [335, 161]. Reddi et al. [389] instead proposes using adaptive learning rates at the server-level, developing federated versions of adaptive optimization methods with the same communication cost as FedAvg. This framework generalizes the server momentum framework proposed by Hsu et al. [237], Wang et al. [470], which allows momentum without increasing communication costs. While both [501, 470] showed that the momentum variants of local SGD can converge to stationary points of non-convex objective
functions at the same rate as synchronous mini-batch SGD, it is challenging to prove momentum accelerates
the convergence rate in the federated learning setting. Recently, Karimireddy et al. [264] proposed a general
approach for adapting centralized optimization algorithms to the heterogeneous federated setting (MIME
framework and algorithms).

## 3.3 Multi-Task Learning, Personalization, and Meta-Learning

In this section we consider a variety of “multi-model” approaches — techniques that result in effectively using different models for different clients at inference time. These techniques are particularly relevant when faced with non-IID data (Section 3.1), since they may outperform even the best possible shared global model. We note that personalization has also been studied in the fully decentralized setting [459, 59, 504, 19], where training individual models is particularly natural.

### 3.3.1 Personalization via Featurization

The remainder of this section specifically considers techniques that result in different users running inference with different model parameters (weights). However, in some applications similar benefits can be achieved by simply adding user and context features to the model. For example, consider a language model for next-word-prediction in a mobile keyboard as in Hard et al. [222]. Different clients are likely to use language differently, and in fact on-device personalization of model parameters has yielded significant improvements for this problem [472]. However, a complimentary approach may be to train a federated model that takes as input not only the words the user has typed so far, but a variety of other user and context features— What words does this user frequently use? What app are they currently using? If they are chatting, what messages have they sent to this person before? Suitably featurized, such inputs can allow a shared global model to produce highly personalized predictions. However, largely because few public datasets contain such auxiliary features, developing model architectures that can effectively incorporate context information for different tasks remains an important open problem with the potential to greatly increase the utility of FL-trained models.

### 3.3.2 Multi-Task Learning

If one considers each client's local problem (the learning problem on the local dataset) as a separate task (rather than as a shard of a single partitioned dataset), then techniques from multi-task learning [506] immediately become relevant. Notably, Smith et al. [424] introduced the MOCHA algorithm for multi-task federated learning, directly tackling challenges of communication efficiency, stragglers, and fault tolerance. In multi-task learning, the result of the training process is one model per task. Thus, most multi-task learning algorithms assume all clients (tasks) participate in each training round, and also require stateful clients since each client is training an individual model. This makes such techniques relevant for cross-silo FL applications, but harder to apply in cross-device scenarios.

Another approach is to reconsider the relationship between clients (local datasets) and learning tasks (models to be trained), observing that there are points on a spectrum between a single global model and different models for every client. For example, it may be possible to apply techniques from multi-task learning (as well as other approaches like personalization, discussed next), where we take the “task” to be a subset of the clients, perhaps chosen explicitly (e.g. based on geographic region, or characteristics of the device or user), or perhaps based on clustering [331] or the connected components of a learned graph over the clients [504]. The development of such algorithms is an important open problem. See Section 4.4.4
for a discussion of how sparse federated learning problems, such as those arising naturally in this type of multi-task problem, might be approached without revealing to which client subset (task) each client belongs.

### 3.3.3 Local Fine Tuning and Meta-Learning

By local fine tuning, we refer to techniques which begin with the federated training of a single model, and then deploy that model to all clients, where it is personalized by additional training on the local dataset before use in inference. This approach integrates naturally into the typical lifecycle of a model in federated learning (Section 1.1.1). Training of the global model can still proceed using only small samples of clients on each round (e.g. 100s); the broadcast of the global model to all clients (e.g. many millions) only happens once, when the model is deployed. The only difference is that before the model is used to make live predictions on the client, a final training process occurs, personalizing the model to the local dataset.

Given a global model that performs reasonably well, what is the best way to personalize it? In non-federated learning, researchers often use fine-tuning, transfer learning, domain adaptation [329, 132, 61, 332, 133], or interpolation with a personal local model. Of course, the precise technique used for such interpolations is key and it is important to determine its corresponding learning guarantees in the context of federated learning. Further, these techniques often assume only a pair of domains (source and target), and so some of the richer structure of federated learning may be lost.

One approach for studying personalization and non-IID data is via a connection to *meta-learning*, which has emerged as a popular setting for model adaptation. In the standard learning-to-learn (LTL) setup [56], one has a meta-distribution over tasks, samples from which are used to learn a learning algorithm, for example by finding a good restriction of the hypothesis space. This is in fact a good match for the statistical setting discussed in Section 3.1, where we sample a client (task) $i \sim Q$, and then sample data for that client (task) from $P_i$.

Recently, a class of algorithms referred to as *model-agnostic meta-learning (MAML)* have been developed that meta-learn a global model, which can be used as a starting point for learning a good model adapted to a given task, using only a few local gradient steps [187]. Most notably, the training phase of the popular Reptile algorithm [358] is closely related to Federated Averaging [337] — Reptile allows for a server learning rate and assumes all clients have the same amount of data, but is otherwise the same. Khodak et al. [270] and Jiang et al. [250] explore the connection between FL and MAML, and show how the MAML setting is a relevant framework to model the personalization objectives for FL. Chai Sim et al. [102] applied local fine tuning to personalize speech recognition models in federated learning. Fallah et al. [181] developed a new algorithm called Personalized FedAvg by connecting MAML instead of Reptile to federated learning. Additional connections with differential privacy were studied in [299].

The general direction of combining ideas from FL and MAML is relatively new, with many open questions:

* The evaluation of MAML algorithms for supervised tasks is largely focused on synthetic image classification problems [290, 386] in which infinite artificial tasks can be constructed by subsampling from classes of images. FL problems, modeled by existing datasets used for simulated FL experiments (Appendix A), can serve as realistic benchmark problems for MAML algorithms.

* In addition to an empirical study, or optimization results, it would be useful to analyze the theoretical guarantees of MAML-type techniques and study under what assumptions they can be successful, as this will further elucidate the set of FL domains to which they may apply.

* The observed gap between the global and personalized accuracy [250] creates a good argument
that personalization should be of central importance to FL. However, none of the existing works clearly formulates what would be comprehensive metrics for measuring personalized performance; for instance, is a small improvement for every client preferable to a larger improvement for a subset of clients? See Section 6 for a related discussion.

* Jiang et al. [250] highlighted the fact that models of the same structure and performance, but trained differently, can have very different capacity to personalize. In particular, it appears that training models with the goal of maximizing global performance might actually hurt the model's capacity for subsequent personalization. Understanding the underlying reasons for this is a question relevant for both FL and the broader ML community.

* Several challenging FL topics including personalization and privacy have begun to be studied in this multi-task/LTL framework [270, 250, 299]. Is it possible for other issues such as concept drift to also be analyzed in this way, for example as a problem in lifelong learning [420]?

* Can non-parameter transfer LTL algorithms, such as ProtoNets [425], be of use for FL?

### 3.3.4 When is a Global FL-trained Model Better?

What can federated learning do for you that local training on one device cannot? When local datasets are small and the data is IID, FL clearly has an edge, and indeed, real-world applications of federated learning [491, 222, 112] benefit from training a single model across devices. On the other hand, given pathologically non-IID distributions (e.g. $P_i(y|x)$ directly disagree across clients), local models will do much better. Thus, a natural theoretical question is to determine under what conditions the shared global model is better than independent per-device models. Suppose we train a model $h_k$ for each client $k$, using the sample of size $m_k$ available from that client. Can we guarantee that the model $h_{FL}$ learned via federated learning is at least as accurate as $h_k$ when used for client $k$? Can we quantify how much improvement can be expected via federated learning? And can we develop personalization strategies with theoretical guarantees that at least match the performance of both natural baselines ($h_k$ and $h_{FL}$)?

Several of these problems relate to previous work on multiple-source adaptation and agnostic federated learning [329, 330, 234, 352]. The hardness of these questions depends on how the data is distributed among parties. For example, if data is vertically partitioned, each party maintaining private records of different feature sets about common entities, these problems may require addressing record linkage [124] within the federated learning task. Independently of the eventual technical levy of carrying out record linkage privately [407], the task itself happens to be substantially noise prone in the real world [406] and only sparse results have addressed its impact on training models [224]. Techniques for robustness and privacy can make local models relatively stronger, particularly for non-typical clients [502]. Loss factorization tricks can be used in supervised learning to alleviate up to the vertical partition assumption itself, but the practical benefits depend on the distribution of data and the number of parties [373].

## 3.4 Adapting ML Workflows for Federated Learning

Many challenges arise when adapting standard machine learning workflows and pipelines (including data augmentation, feature engineering, neural architecture design, model selection, hyperparameter optimization, and debugging) to decentralized datasets and resource-constrained mobile devices. We discuss several of these challenges below.
### 3.4.1 Hyperparameter Tuning

Running many rounds of training with different hyperparameters on resource-constrained mobile devices may be restrictive. For small device populations, this might result in the over-use of limited communication and compute resources. However, recent deep neural networks crucially depend on a wide range of hyperparameter choices regarding the neural network's architecture, regularization, and optimization. Evaluations can be expensive for large models and large-scale on-device datasets. Hyperparameter optimization (HPO) has a long history under the framework of AutoML [395, 273, 277], but it mainly concerns how to improve the model accuracy [64, 426, 374, 180] rather than communication and computing efficacy for mobile devices. Therefore, we expect that further research should consider developing solutions for efficient hyperparameter optimization in the context of federated learning.

In addition to general-purpose approaches to the hyperparameter optimization problem, in the training space specifically the development of easy-to-tune optimization algorithms is a major open area. Centralized training already requires tuning parameters like learning rate, momentum, batch size, and regularization. Federated learning adds potentially more hyperparameters — separate tuning of the aggregation / global model update rule and local client optimizer, number of clients selected per round, number of local steps per round, configuration of update compression algorithms, and more. Such hyperparameters can be crucial to obtaining a good trade-off between accuracy and convergence, and may actually impact the quality of the learned model [106]. In addition to a higher-dimensional search space, federated learning often also requires longer wall-clock training times and limited compute resources. These challenges could be addressed by optimization algorithms that are robust to hyperparameter settings (the same hyperparameter values work for many different real world datasets and architectures), as well as adaptive or self-tuning algorithms [446, 82].

### 3.4.2 Neural Architecture Design

Neural architecture search (NAS) in the federated learning setting is motivated by the drawbacks of the current practice of applying predefined deep learning models: the predefined architecture of a deep learning model may not be the optimal design choice when the data generated by users are invisible to model developers. For example, the neural architecture may have some redundant component for a specific dataset, which may lead to unnecessary computing on devices; there may be a better architectural design for the non-IID data distribution. The approaches to personalization discussed in Section 3.3 still share the same model architecture among all clients. The recent progress in NAS [230, 387, 175, 388, 60, 375, 313, 488, 175, 323] provides a potential way to address these drawbacks. There are three major methods for NAS, which utilize evolutionary algorithms, reinforcement learning, or gradient descent to search for optimal architectures for a specific task on a specific dataset. Among these, the gradient-based method leverages efficient gradient back-propagation with weight sharing, reducing the architecture search process from over 3000 GPU days to only 1 GPU day. Another interesting paper recently published, involving Weight Agnostic Neural Networks [192], claims that neural network architectures alone, without learning any weight parameters, may encode solutions for a given task. If this technique further develops and reaches widespread use, it may be applied to the federated learning without collaborative training among devices. Although these methods have not been developed for distributed settings such as federated learning, they are all feasible to be transferred to the federated setting. Neural Architecture Search (NAS) for a global or personalized model in the federated learning setting is promising, and early exploration has been made in [228].
### 3.4.3 Debugging and Interpretability for FL

While substantial progress has been made on the federated training of models, this is only part of a complete ML workflow. Experienced modelers often directly inspect subsets of the data for tasks including basic sanity checking, debugging misclassifications, discovering outliers, manually labeling examples, or detecting bias in the training set. Developing privacy-preserving techniques to answer such questions on decentralized data is a major open problem. Recently, Augenstein et al. [31] proposed the use of differentially private generative models (including GANs), trained with federated learning, to answer some questions of this type. However, many open questions remain (see discussion in [31]), in particular the development of algorithms that improve the fidelity of FL DP generative models.

## 3.5 Communication and Compression

It is now well-understood that communication can be a primary bottleneck for federated learning since wireless links and other end-user internet connections typically operate at lower rates than intra- or inter-datacenter links and can be potentially expensive and unreliable. This has led to significant recent interest in reducing the communication bandwidth of federated learning. Methods combining Federated Averaging with sparsification and/or quantization of model updates to a small number of bits have demonstrated significant reductions in communication cost with minimal impact on training accuracy [282]. However, it remains unclear if communication cost can be further reduced, and whether any of these methods or their combinations can come close to providing optimal trade-offs between communication and accuracy in federated learning. Characterizing such fundamental trade-offs between accuracy and communication has been of recent interest in theoretical statistics [507, 89, 221, 7, 49, 444, 50]. These works characterize the optimal minimax rates for distributed statistical estimation and learning under communication constraints. However, it is difficult to deduce concrete insights from these theoretical works for communication bandwidth reduction in practice as they typically ignore the impact of the optimization algorithm. It remains an open direction to leverage such statistical approaches to inform practical training methods.

**Compression objectives** Motivated by the limited resources of current devices in terms of compute, memory and communication, there are several different compression objectives of practical value.

(a) *Gradient compression*<fnref n="6" /> – reduce the size of the object communicated from clients to server, which is used to update the global model.

(b) *Model broadcast compression* – reduce the size of the model broadcast from server to clients, from which the clients start local training.

(c) *Local computation reduction* – any modification to the overall training algorithm such that the local training procedure is computationally more efficient.

These objectives are in most cases complementary. Among them, (a) has the potential for the most significant practical impact in terms of total runtime. This is both because clients' connections generally have slower upload than download bandwidth<fnref n="7" /> – and thus there is more to be gained, compared to (b) – and because the effects of averaging across many clients can enable more aggressive lossy compression schemes. Usually, (c) could be realized jointly with (a) and (b) by specific methods.

<footnote n="6">⁶In this section, we use “gradient compression” to include compression applied to any model update, such as the updates produced by Federated Averaging when clients take multiple gradient steps.</footnote>

<footnote n="7">⁷See for instance https://www.speedtest.net/reports/</footnote>
Much of the existing literature applies to the objective (a) [282, 440, 281, 17, 235, 55]. The impact of (b) on convergence in general has not been studied until very recently; an analysis is presented in [123]. Very few methods intend to address all of (a), (b) and (c) jointly. Caldas et al. [95] proposed a practical method by constraining the desired model update such that only particular submatrices of model variables are necessary to be available on clients; Hamer et al. [219] proposed a communication-efficient federated algorithm for learning mixture weights on an ensemble of pre-trained models, based on communicating only a subset of the models to any one device; He et al. [227] utilizes bidirectional and alternative knowledge distillation method to transfer knowledge from many compact DNNs to a dense server DNN, which can reduce the local computational burden at the edge devices.

In cross-device FL, algorithms generally cannot assume any state is preserved on the clients (Table 1). However, this constraint would typically not be present in the cross-silo FL setting, where the same clients participate repeatedly. Consequently, a wider set of ideas related to error-correction such as [311, 405, 463, 444, 263, 435] are relevant in this setting, many of which could address both (a) and (b).

An additional objective is to modify the training procedure such that the *final* model is more compact, or efficient for inference. This topic has received a lot of attention in the broader ML community [220, 138, 509, 309, 362, 74], but these methods either do not have a straightforward mapping to federated learning, or make the training process more complex which makes it difficult to adopt. Research that simultaneously yields a compact final model, while also addressing the three objectives above, has significant potential for practical impact.

For gradient compression, some existing works [440] are developed in the minimax sense to characterize the worst case scenario. However usually in information theory, the compression guarantees are instance specific and depend on the *entropy* of the underlying distribution [140]. In other words, if the data is easily compressible, they are provably compressed heavily. It would be interesting to see if similar instance specific results can be obtained for gradient compression. Similarly, recent works show that learning a compression scheme in a data-dependent fashion can lead to significantly better compression ratio for the case of data compression [482] as well as gradient compression. It is therefore worthwhile to evaluate these data-dependent compression schemes in the federated settings [193].

**Compatibility with differential privacy and secure aggregation** Many algorithms used in federated learning such as Secure Aggregation [79] and mechanisms of adding noise to achieve differential privacy [3, 338] are not designed to work with compressed or quantized communications. For example, straightforward application of the Secure Aggregation protocol of Bonawitz et al. [80], Bell et al. [58] requires an additional $O(\log M)$ bits of communication for each scalar, where $M$ is the number of clients being summed over, and this may render ineffective the aggressive quantization of updates when $M$ is large (though see [82] for a more efficient approach). Existing noise addition mechanisms assume adding real-valued Gaussian or Laplacian noise on each client, and this is not compatible with standard quantization methods used to reduce communication. We note that several recent works allow biased estimators and would work nicely with Laplacian noise [435], however those would not give differential privacy, as they break independence between rounds. There is some work on adding discrete noise [9], but there is no notion whether such methods are optimal. Joint design of compression methods that are compatible with Secure Aggregation, or for which differential privacy guarantees can be obtained, is thus a valuable open problem.

**Wireless-FL co-design** The existing literature in federated learning usually neglects the impact of wireless channel dynamics during model training, which potentially undermines both training latency and thus reliability of the entire production system. In particular, wireless interference, noisy channels and channel
fluctuations can significantly hinder the information exchange between the server and clients (or directly
between individual clients, as in the fully decentralized case, see Section 2.1). This represents a major
challenge for mission-critical applications, rooted in latency reduction and reliability enhancements. Poten-
tial solutions to address this challenge include federated distillation (FD), in which workers exchange their
model output parameters (logs) as opposed to the model parameters (gradients and/weights), and optimiz-
ing workers' scheduling policy with appropriate communication and computing resources [248, 368, 402].
Another solution is to leverage the unique characteristics of wireless channels (e.g. broadcast and superposi-
tion) as natural data aggregators, in which the simultaneously transmitted analog-waves by different workers
are superposed at the server and weighed by the wireless channel coefficients [4]. This yields faster model
aggregation at the server, and faster training by a factor up to the number of workers. This is in sharp con-
trast with the traditional orthogonal frequency division multiplexing (OFDM) paradigm, whereby workers
upload their models over orthogonal frequencies whose performance degrades with increasing number of
workers [174].

**3.6 Application To More Types of Machine Learning Problems and Models**

To date, federated learning has primarily considered supervised learning tasks where labels are naturally available on each client. Extending FL to other ML paradigms, including reinforcement learning, semi-supervised and unsupervised learning, active learning, and online learning [226, 508] all present interesting and open challenges.

Another important class of models, highly relevant to FL, are those that can characterize the uncer-
tainty in their predictions. Most modern deep learning models cannot represent their uncertainty nor allow
for a probability interpretation of parametric learning. This has motivated recent developments of tools
and techniques combining Bayesian models with deep learning. From a probability theory perspective, it
is unjustifiable to use single point-estimates for classification. Bayesian neural networks [419] have been
proposed and shown to be far more robust to over-fitting, and can easily learn from small datasets. The
Bayesian approach further offers uncertainty estimates via its parameters in form of probability distribu-
tions, thus preventing over-fitting. Moreover, appealing to probabilistic reasoning, one can predict how the
uncertainty can decrease, allowing the decisions made by the network to become more deterministic as the
data size grows.

Since Bayesian methods gave us tools to reason about deep models’ confidence and also achieve state-of-
the-art performance on many tasks, one expects Bayesian methods to provide a conceptual improvement to
the classical federated learning. In fact, preliminary work from Lalitha et al. [292] shows that incorporating
Bayesian methods allows for model aggregation across non-IID data and heterogeneous platforms. However,
many questions regarding scalability and computational feasibility have to be addressed.

**3.7 Executive summary**

Efficient and effective federated learning algorithms face different challenges compared to centralized training in a datacenter.

* Non-IID data due to non-identical client distributions, violation of independence, and dataset drift (Section 3.1) pose a key challenge. Though various methods have been surveyed and discussed in this section, defining and dealing with non-IID data remains an open problem and one of the most active research topics in federated learning.
* Optimization algorithms for federated learning are analyzed in Section 3.2 under different settings, e.g., convex and nonconvex functions, IID and non-IID data. Theoretical analysis has proven difficult for the parallel local updates commonly used in federated optimization, and often strict assumptions have to be made to constrain the client heterogeneity. Currently, known convergence rates do not fully explain the empirically-observed effectiveness of the Federated Averaging algorithm over methods such as mini-batch SGD [481].

* Client-side personalization and “multi-model” approaches (Section 3.3) can address data heterogeneity and give hope of surpassing the performance of the best fixed global model. Simple personalization methods like fine-tuning can be effective, and offer intrinsic privacy advantages. However, many theoretical and empirical questions remain open: when is a global model better? How many models are necessary? Which federated optimization algorithms combine best with local fine-tuning?

* Adapting centralized training workflows such as hyper-parameter tuning, neural architecture design, debugging, and interpretability tasks to the federated learning setting (Section 3.4) present roadblocks to the widespread adoption of FL in practical settings, and hence constitute important open problems.

* While there has been significant work on communication efficiency and compression for FL (Section 3.5), it remains an important and active area. In particular, fully automating the process of enabling compression without impacting convergence for a wide class of models is an important practical goal. Relatively new directions on the theoretical study of communication, compatibility with privacy methods, and co-design with wireless infrastructure are discussed.

* There are many open questions in extending federated learning from supervised tasks to other machine learning paradigms including reinforcement learning, semi-supervised and unsupervised learning, active learning, and online learning (Section 3.6).
# 4 Preserving the Privacy of User Data

Machine learning workflows involve many actors functioning in disparate capacities. For example, users may generate training data through interactions with their devices, a machine learning training procedure extracts cross-population patterns from this data (e.g. in the form of trained model parameters), the machine learning engineer or analyst may assess the quality of this trained model, and eventually the model may be deployed to end users in order to support specific user experiences (see Figure 1 below).

In an ideal world, each actor in the system would learn nothing more than the information needed to play their role. For example, if an analyst only needs to determine whether a particular quality metric exceeds a desired threshold in order to authorize deploying the model to end users, then in an idealized world, that is the only bit of information that would be available to the analyst; such an analyst would need access to neither the training data nor the model parameters, for instance. Similarly, end users enjoying the user experiences powered by the trained model might only require predictions from the model and nothing else.

Furthermore, in an ideal world every participant in the system would be able to reason easily and accurately about what personal information about themselves and others might be revealed by their participation in the system, and participants would be able to use this understanding to make informed choices about how and whether to participate at all.

Producing a system with all of the above ideal privacy properties would be a daunting feat on its own, and even more so while also guaranteeing other desirable properties such as ease of use for all participants, the quality and fairness of the end user experiences (and the models that power them), the judicious use of communication and computation resources, resilience against attacks and failures, and so on.

Rather than allowing perfect to be the enemy of good, we advocate a strategy wherein the overall system is composed of modular units which can be studied and improved relatively independently, while also reminding ourselves that we must, in the end, measure the privacy properties of the complete system against our ideal privacy goals set out above. The open questions raised throughout this section will highlight areas

<figure><img src="image_3.png" /><figcaption>Figure 1: The lifecycle of an FL-trained model and the various actors in a federated learning system. (repeated from Page 7)</figcaption></figure>
wherein we do not yet understand how to simultaneously achieve all of our goals, either for an individual module or for the system as a whole.

Federated learning provides an attractive structure for decomposing the overall machine learning work-
flow into the approachable modular units we desire. One of the primary attractions of the federated learning
model is that it can provide a level of privacy to participating users through data minimization: the raw
user data never leaves the device, and only updates to models (e.g., gradient updates) are sent to the central
server. These model updates are more focused on the learning task at hand than is the raw data (i.e. they
contain strictly no additional information about the user, and typically significantly less, compared to the
raw data), and the individual updates only need to be held ephemerally by the server.

While these features can offer significant practical privacy improvements over centralizing all the training data, there is still no formal guarantee of privacy in this baseline federated learning model. For instance, it is possible to construct scenarios in which information about the raw data is leaked from a client to the server, such as a scenario where knowing the previous model and the gradient update from a user would allow one to infer a training example held by that user. Therefore, this section surveys existing results and outlines open challenges towards designing federated learning systems that can offer rigorous privacy guarantees. We focus on questions specific to the federated learning and analytics setting and leave aside questions that also arise in more general machine learning settings as surveyed in [344].

Beyond attacks targeting user privacy, there are also other classes of attacks on federated learning; for example, an adversary might attempt to prevent a model from being learned at all, or they might attempt to bias the model to produce inferences that are preferable to the adversary. We defer consideration of these types of attacks to Section 5.

The remainder of this section is organized as follows. Section 4.1 discusses various threat models against which we wish to give protections. Section 4.2 lays out a set of core tools and technologies that can be used towards providing rigorous protections against the threat models discussed in Section 4.1. Section 4.3 assumes the existence of a trusted server and discusses the open problems and challenges in providing protections against adversarial clients and/or analysts. Section 4.4 discusses the open problems and challenges in the absence of a fully trusted server. Finally, Section 4.5 discusses open questions around user perception.

## 4.1 Actors, Threat Models, and Privacy in Depth

A formal treatment of privacy risks in FL calls for a holistic and interdisciplinary approach. While some of the risks can be mapped to technical privacy definitions and mitigated with existing technologies, others are more complex and require cross-disciplinary efforts.

Privacy is not a binary quantity, or even a scalar one. This first step towards such formal treatment is a careful characterization of the different actors (see Figure 1 from Section 1, repeated on page 36 for convenience) and their roles to ultimately define relevant threat models (see Table 7). Thus, for instance, it is desirable to distinguish the view of the server administrator from the view of the analysts that consume the learned models, as it is conceivable that a system that is designed to offer strong privacy guarantees against a malicious analyst may not provide any guarantees with respect to a malicious server. These actors map well onto the threat models discussed elsewhere in the literature; for example, in Bittau et al. [73, Sec 3.1], where the “encoder” corresponds to the client, the “shuffler” generally corresponds to the server, the “analyzer” may correspond to the server or post-processing done by the analyst.
As an example, a particular system might offer a differential privacy<fnref n="8" /> guarantee with a particular pa-
rameter $\epsilon$ to the view of the server administrator, while the results observed by analysts might have a higher
protection $\epsilon' < \epsilon$.

Furthermore, it is possible that this guarantee holds only against adversaries with particular limits on
their capabilities, e.g. an adversary that can observe everything that happens on the server (but cannot
influence the server's behavior) while simultaneously controlling up to a fraction $\gamma$ of the clients (observing
everything they see and influencing their behavior in arbitrary ways); the adversary might also be assumed
to be unable to break cryptographic mechanisms instantiated at a particular security level $\sigma$. Against an
adversary whose strength *exceeds* these limits, the view of the server administrator might still have some
differential privacy, but at weaker level $\epsilon_0 > \epsilon$.

As we see in this example, precisely specifying the assumptions and privacy goals of a system can
easily implicate concrete instantiations of several parameters ($\epsilon, \epsilon', \epsilon_0, \gamma, \sigma$, etc.) as well as concepts such
as differential privacy and honest-but-curious security.

Achieving all the desired privacy properties for federated learning will typically require composing many
of the tools and technologies described below into an end-to-end system, potentially both layering multiple
strategies to protect the same part of the system (e.g. running portions of a Secure Multi-Party Compu-
tation (MPC) protocol inside a Trusted Execution Environment (TEE) to make it harder for an adversary
to sufficiently compromise that component) as well as using different strategies to protect different parts
of the system (e.g. using MPC to protect the aggregation of model updates, then using Private Disclosure
techniques before sharing the aggregate updates beyond the server).

As such, we advocate for building federated systems wherein the privacy properties degrade as gracefully as possible in cases where one technique or another fails to provide its intended privacy contribution. For example, running the server component of an MPC protocol inside a TEE might allow privacy to be maintained even in the case where either (but not both) of the TEE security or MPC security assumptions fails to hold in practice. As another example, requiring clients to send raw training examples to a server-side TEE would be strongly dispreferred to having clients send gradient updates to a server-side TEE, as the latter's privacy expectations degrade much more gracefully if the TEE's security were to fail. We refer to this principle of graceful degradation as "Privacy in Depth," in analogy to the well-established network security principle of defense in depth [361].

## 4.2 Tools and Technologies

Generally speaking, the goal of an FL computation is for the analyst or engineer requesting the computation to obtain the result, which can be thought of as the evaluation of a function *f* on a distributed client dataset (commonly an ML model training algorithm, but possibly something simpler such as a basic statistic). There are three privacy aspects that need to be addressed.

First, we need to consider *how f* is computed and what is the information flow of intermediate results
in the process, which primarily influences the susceptibility to malicious client, server, and admin actors. In
addition to designing the flow of information in the system (e.g. early data minimization), techniques from
secure computation including Secure Multi-Party Computation (MPC) and Trusted Execution Environments
(TEEs) are of particular relevance to addressing these concerns. These technologies will be discussed in
detail in Section 4.2.1.

<footnote n="8">⁸Differential privacy will be formally introduced in Section 4.2.2. For now, it suffices to know that lower $\epsilon$ corresponds with higher privacy.</footnote>
<table><caption>Table 7: Various threat models for different adversarial actors.</caption><thead><tr><td>Data/Access Point</td><td>Actor</td><td>Threat Model</td></tr></thead><tbody><tr><td>Clients</td><td>Someone who has root access to the client device, either by design or by compromising the device</td><td>Malicious clients can inspect all messages received from the server (including the model iterates) in the rounds they participate in and can tamper with the training process. An honest-but-curious client can inspect all messages received from the server but cannot tamper with the training process. In some cases, technologies such as secure enclaves/TEEs may be able to limit the influence and visibility of such an attacker, representing a meaningfully weaker threat model.</td></tr><tr><td>Server</td><td>Someone who has root access to the server, either by design or by compromising the device</td><td>A malicious server can inspect all messages sent to the server (including the gradient updates) in all rounds and can tamper with the training process. An honest-but-curious server can inspect all messages sent to the server but cannot tamper with the training process. In some cases, technologies such as secure enclaves/TEEs may be able to limit the influence and visibility of such an attacker, representing a meaningfully weaker threat model.</td></tr><tr><td>Output Models</td><td>Engineers & analysts</td><td>A malicious analyst or model engineer may have access to multiple outputs from the system, e.g. sequences of model iterates from multiple training runs with different hyperparameters. Exactly what information is released to this actor is an important system design question.</td></tr><tr><td>Deployed Models</td><td>The rest of the world</td><td>In cross-device FL, the final model may be deployed to hundreds of millions of devices. A partially compromised device can have black-box access to the learned model, and a fully compromised device can have a white-box access to the learned model.</td></tr></tbody></table>
Second, we have to consider *what* is computed. In other words, how much information about a participating client is revealed to the analyst and world actors by the result of *f* itself. Here, techniques for privacy-preserving disclosure, particularly differential privacy (DP), are highly relevant and will be discussed in detail in Section 4.2.2.

Finally, there is the problem of *verifiability*, which pertains to the ability of a client or the server to prove to others in the system that they have executed the desired behavior faithfully, without revealing the potentially private data upon which they were acting. Techniques for verifiability, including remote attestation and zero-knowledge proofs, will be discussed in Section 4.2.3.

### 4.2.1 Secure Computations

The goal of secure computation is to evaluate functions on distributed inputs in a way that only reveals the result of the computation to the intended parties, without revealing any additional information (e.g. the parties' inputs or any intermediate results).

**Secure multi-party computation** Secure Multi-Party Computation (MPC) is a subfield of cryptography concerned with the problem of having a set of parties compute an agreed-upon function of their private inputs in a way that only reveals the intended output to each of the parties. This area was kicked off in the 1980's by Yao [493]. Thanks to both theoretical and engineering breakthroughs, the field has moved from being of a purely theoretical interest to a deployed technology in industry [78, 77, 295, 27, 191, 242, 243]. It is important to remark that MPC defines a set of technologies, and should be regarded more as a field, or a general notion of security in secure computation, than a technology *per se*. Some of the recent advances in MPC can be attributed to breakthroughs in lower level primitives, such as oblivious transfer protocols [244] and encryption schemes with homomorphic properties (as described below).

A common aspect of cryptographic solutions is that operations are often done on a finite field (e.g. integers modulo a prime *p*), which poses difficulties when representing real numbers. A common approach has been to adapt ML models and their training procedures to ensure that (over)underflows are controlled, by operating on normalized quantities and relying on careful quantization [194, 10, 206, 84].

It has been known for several decades that any function can be securely computed, even in the presence of malicious adversaries [208]. While generic solutions exist, their performance characteristics often render them inapplicable in practical settings. As such a noticeable trend in research has consisted in designing custom protocols for applications such as linear and logistic regression [359, 194, 351] and neural network training and inference [351, 10, 48]. These works are typically in the cross-silo setting, or the variant where computation is delegated to a small group of computing servers that do not collude with each other. Porting these protocols to the cross-device setting is not straightforward, as they require a significant amount of communication.

*Homomorphic encryption* Homomorphic encryption (HE) schemes allow certain mathematical operations to be performed directly on ciphertexts, without prior decryption. Homomorphic encryption can be a powerful tool for enabling MPC by enabling a participant to compute functions on values while keeping the values hidden.

Different flavours of HE exist, ranging from general fully homomorphic encryption (FHE) [197] to the more efficient leveled variants [87, 182, 88, 129], for which several implementations exist [233, 409, 364, 415, 1]. Also of practical relevance are the so-called partially homomorphic schemes, including for example ElGamal and Paillier, allowing either homomorphic addition or multiplication. Additive HE has been used
<table><caption>Table 8: Various technologies along with their characteristics.</caption><thead><tr><td>Technology</td><td>Characteristics</td></tr></thead><tbody><tr><td>Differential Privacy (local, central, shuffled, aggregated, and hybrid models)</td><td>A quantification of how much information could be learned about an individual from the output of an analysis on a dataset that includes the user. Algorithms with differential privacy necessarily incorporate some amount of randomness or noise, which can be tuned to mask the influence of the user on the output.</td></tr><tr><td>Secure Multi-Party Computation</td><td>Two or more participants collaborate to simulate, though cryptography, a fully trusted third party who can:<ul><li>Compute a function of inputs provided by all the participants;</li><li>Reveal the computed value to a chosen subset of the participants, with no party learning anything further.</li></ul></td></tr><tr><td>Homomorphic Encryption</td><td>Enables a party to compute functions of data to which they do not have plain-text access, by allowing mathematical operations to be performed on ciphertexts without decrypting them. Arbitrarily complicated functions of the data can be computed this way ("Fully Homomorphic Encryption") though at greater computational cost.</td></tr><tr><td>Trusted Execution Environments (secure enclaves)</td><td>TEEs provide the ability to trustably run code on a remote machine, even if you do not trust the machine's owner/administrator. This is achieved by limiting the capabilities of any party, including the administrator. In particular, TEEs may provide the following properties [437]:<ul><li>Confidentiality: The state of the code's execution remains secret, unless the code explicitly publishes a message;</li><li>Integrity: The code's execution cannot be affected, except by the code explicitly receiving an input;</li><li>Measurement/Attestation: The TEE can prove to a remote party what code (binary) is executing and what its starting state was, defining the initial conditions for confidentiality and integrity.</li></ul></td></tr></tbody></table>
as an ingredient in MPC protocols in the cross-silo setting [359, 224]. A review of some homomorphic encryption software libraries along with brief explanations of criteria/features to be considered in choosing a library is surveyed in [404].

When considering the use of HE in the FL setting, questions immediately arise about who holds the secret key of the scheme. While the idea of every client encrypting their data and sending it to the server to compute homomorphically on it is appealing, the server should not be able to decrypt a single client contribution. A trivial way of overcoming this issue would be relying on a non-colluding external party that holds the secret key and decrypts the result of the computation. However, most HE schemes require that the secret keys be renewed often (due to e.g. susceptibility to chosen ciphertext attacks [117]). Moreover, the availability of a trusted non-colluding party is not standard in the FL setting.

Another way around this issue is relying on distributed (or threshold) encryption schemes, where the secret key is distributed among the parties. Reyzin et al. [392] and Roth et al. [398] propose such solutions for computing summation in the cross-device setting. Their protocols make use of additively homomorphic schemes (variants of ElGamal and lattice-based schemes, respectively).

**Trusted execution environments** Trusted execution environments (TEEs, also referred to as secure enclaves) may provide opportunities to move part of the federated learning process into a trusted environment in the cloud, whose code can be attested and verified.

TEEs can provide several crucial facilities for establishing trust that a unit of code has been executed faithfully and privately [437]:

* Confidentiality: The state of the code's execution remains secret, unless the code explicitly publishes a message.

* Integrity: The code's execution cannot be affected, except by the code explicitly receiving an input.

* Measurement/Attestation: The TEE can prove to a remote party what code (binary) is executing and what its starting state was, defining the initial conditions for confidentiality and integrity.

TEEs have been instantiated in many forms, including Intel's SGX-enabled CPUs [241, 134], Arm's TrustZone [28, 22], and Sanctum on RISC-V [135], each varying in its ability to systematically offer the above facilities.

Current secure enclaves are limited in terms of memory and provide access only to CPU resources, that is they do not allow processing on GPUs or machine learning processors (Tramèr and Boneh [447] explore how to combine TEEs with GPUs for machine learning inference). Moreover, it is challenging for TEEs (especially those operating on shared microprocessors) to fully exclude all types of side channel attacks [458].

While secure enclaves provide protections for all code running inside them, there are additional concerns that must be addressed in practice. For example, it is often necessary to structure the code running in the enclave as a data oblivious procedure, such that its runtime and memory access patterns do not reveal information about the data upon which it is computing (see for example [73]). Furthermore, measurement/attestation typically only proves that a particular binary is running; it is up to the system architect to provide a means for proving that that binary has the desired privacy properties, potentially requiring the binary to be built using a reproducible process from open source code.

It remains an open question how to partition federated learning functions across secure enclaves, cloud computing resources, and client devices. For example, secure enclaves could execute key functions such as
secure aggregation or shuffling to limit the server's access to raw client contributions while keeping most of
the federated learning logic outside this trusted computing base.

**Secure computation problems of interest** While secure multi-party computation and trusted execution environments offer general solutions to the problem of privately computing any function on distributed private data, many optimizations are possible when focusing on specific functionalities. This is the case for the tasks described next.

*Secure aggregation*

Secure aggregation is a functionality for *n* clients and a server. It enables each client to submit a value (often a vector or tensor in the FL setting), such that the server learns just an aggregate function of the clients' values, typically the sum.

There is a rich literature exploring secure aggregation in both the single-server setting (via additive masking [8, 213, 80, 58, 428], via threshold homomorphic encryption [417, 218, 103], and via generic secure multi-party computation [94]) as well as in the multiple non-colluding servers setting [78, 27, 130]. Secure aggregation can also be approached using trusted execution environments (introduced above), as in [308].

*Secure shuffling*

Secure shuffling is a functionality for *n* clients and a server. It enables each client to submit one or more messages, such that the server learns just an unordered collection (multiset) of the messages from all clients and nothing more. Specifically, the server has no ability to link any message to its sender beyond the information contained in the message itself. Secure shuffling can be considered an instance of Secure Aggregation where the values are multiset-singletons and the aggregation operation is multiset-sum, though it is often the case that very different implementations provide the best performance in the typical operating regimes for secure shuffling and secure aggregation.

Secure shufflers have been studied in the context of secure multi-party computation [107, 288], often under the heading of mix networks. They have also been studied in the context of trusted computing [73]. Mix networks have found large scale deployment in the form of the Tor network [157].

*Private information retrieval*

Private information retrieval (PIR) is a functionality for one client and one server. It enables the client to download an entry from a server-hosted database such that the server gains zero information about which entry the client requested.

MPC approaches to PIR break down into two main categories: *computational PIR* (cPIR), in which a single party can execute the entire server side of the protocol [286], and *information theoretic PIR* (itPIR), in which multiple non-colluding parties are required to execute the server side of the protocol [121].

The main roadblocks to the applicability of PIR have been the following: cPIR has high computational cost [423], while the non-colluding parties setting has been difficult to achieve convincingly in industrial scenarios. Recent results on PIR have shown dramatic reductions in the computational cost through the use of lattice-based cryptosystems [12, 363, 13, 23, 198]. The computational cost can be traded for more communication; we refer the reader to Ali et al. [16] to better understand the communication and computation trade-offs offered by cPIR. Additionally, it has been shown how to construct communication-efficient PIR on a single-server by leveraging side information available to the user [251], for example via client local state. Patel et al. [372] presented and implemented a practical hybrid (computational and information theoretic) PIR scheme on a single server assuming client state. Corrigan-Gibbs and Kogan [131] present theoretical constructions for PIR with sublinear *online* time by working in an offline/online model where,
during an offline phase, clients fetch information from the server(s) independent on the future query to be performed.

Further work has explored the connection between PIR and secret sharing [479], with recent connections to PIR on coded data [159] and communication efficient PIR [72]. A variant of PIR, called PIR-with-Default, enable clients to retrieve a default value if the index queried is not in the database, and can output additive secret shares of items which can serve as input to any MPC protocol [297]. PIR has also been studied in the context of ON-OFF privacy, in which a client is permitted to switch off their privacy guards in exchange for better utility or performance [355, 494].

### 4.2.2 Privacy-Preserving Disclosures

The state-of-the-art model for quantifying and limiting information disclosure about individuals is *differen- tial privacy* (DP) [167, 164, 165], which aims to introduce a level of uncertainty into the released model sufficient to mask the contribution of any individual user. Differential privacy is quantified by privacy loss parameters $(\epsilon, \delta)$, where smaller $(\epsilon, \delta)$ corresponds to increased privacy. More formally, a randomized al- gorithm $\mathcal{A}$ is $(\epsilon, \delta)$-differentially private if for all $S \subseteq \text{Range}(\mathcal{A})$, and for all adjacent datasets $D$ and $D'$:

$$P(\mathcal{A}(D) \in S) \leq e^{\epsilon} P(\mathcal{A}(D') \in S) + \delta. \quad (3)$$

In the context of FL, $D$ and $D'$ correspond to decentralized datasets that are adjacent if $D'$ can be obtained from $D$ by adding or subtracting all the records of a single client (user) [338]. This notion of differential privacy is referred to as user-level differential privacy. It is stronger than the typically used notion of ad- jacency where $D$ and $D'$ differ by only one record [165], since in general one user may contribute many records (e.g. training examples) to the dataset.

Over the last decade, an extensive set of techniques has been developed for differentially private data analysis, particularly under the assumption of a centralized setting, where the raw data is collected by a trusted party prior to applying perturbations necessary to achieve privacy. In federated learning, typically the orchestrating server would serve as the trusted implementer of the DP mechanism, ensuring only privatized outputs are released to the model engineer or analyst.

However, when possible we often wish to reduce the need for a trusted party. Several approaches for reducing the need for trust in a data curator have been considered in recent years.

**Local differential privacy** Differential privacy can be achieved without requiring trust in a centralized server by having each client apply a differentially private transformation to their data prior to sharing it with the server. That is, we apply Equation (3) to a mechanism $\mathcal{A}$ that processes a single user's local dataset $D$, with the guarantee holding with respect to *any* possible other local dataset $D'$. This model is referred to as the *local model of differential privacy* (LDP) [475, 266]. LDP has been deployed effectively to gather statistics on popular items across large userbases by Google, Apple and Microsoft [177, 154, 155]. It has also been used in federated settings for spam classifier training by Snap [378]. These LDP deployments all involve large numbers of clients and reports, even up to a billion in the case of Snap, which stands in stark contrast to centralized instantiations of DP which can provide high utility from much smaller datasets. Unfortunately, as we will discuss in Section 4.4.2, achieving LDP while maintaining utility can be difficult [266, 455]. Thus, there is a need for a model of differential privacy that interpolates between purely central and purely local DP. This can be achieved through distributed differential privacy, or the hybrid model, as discussed below.
**Distributed differential privacy**
In order to recover some of the utility of central DP without having to rely on a trustworthy central server, one can instead use a *distributed differential privacy model* [166, 417, 73, 120]. Under this model, the clients first compute and encode a minimal (application specific) focused report, and then send the encoded reports to a secure computation function, whose output is available to the central server, with the intention that this output already satisfies differential privacy requirements by the time the server is able to inspect it. The encoding is done to help maintain privacy on the clients, and could for example include LDP. The secure computation function can have a variety of incarnations. It could be an MPC protocol, a standard computation done on a TEE, or even a combination of the two. Each of these choices comes with different assumptions and threat models.

It is important to remark that distributed differential privacy and local differential privacy yield different guarantees from several perspectives: while the distributed DP framework can produce more accurate statistics for the same level of differential privacy as LDP, it relies on different setups and typically makes stronger assumptions, such as access to MPC protocols. Below, we outline two possible approaches to distributed differential privacy, relying on secure aggregation and secure shuffling. We stress that there are many other methods that could be used, see for instance [400] for an approach based on exchanging correlated Gaussian noise across secure channels.

*Distributed DP via secure aggregation*
One promising tool for achieving distributed DP in FL is secure aggregation, discussed above in Section 4.2.1. Secure aggregation can be used to ensure that the central server obtains the aggregated result, while guaranteeing that intermediate parameters of individual devices and participants are not revealed to the central server. To further ensure the aggregated result does not reveal additional information to the server, we can use local differential privacy (e.g. with moderate $\varepsilon$ level). For example, each device could perturb its own model parameter before the secure aggregation in order to achieve local differential privacy. By designing the noise correctly, we may ensure that the noise in the aggregated result matches the noise that would have otherwise been added centrally by a trusted server (e.g. with a low $\varepsilon$ / high privacy level) [7, 385, 204, 417, 213].

*Distributed DP via secure shuffling*
Another distributed differential privacy model is the shuffling model, which was kicked off by the recently introduced Encode-Shuffle-Analyze (ESA) framework [73] (illustrated in Figure 3). In the simplest version of this framework, each client runs an LDP protocol (e.g. with a moderate $\varepsilon$ level) on its data and provides its output to a secure shuffler. The shuffler randomly per-mutes the reports and sends the collection of shuffled reports (without any identifying information) to the server for final analysis. Intuitively, the interposition of this secure compute function makes it harder for the server to learn anything about the participants and supports a differential privacy analysis (e.g. with a low $\varepsilon$ / high privacy level). In the more general multi-message shuffled framework, each user can possibly send more than one message to the shuffler. The shuffler can either be implemented directly as a trusted entity, independent of the server and devoted solely to shuffling, or via more complex cryptographic primitives as discussed above.

Bittau et al. [73] proposed the Prochlo system as a way to implement the ESA framework. The system takes a holistic approach to privacy that takes into account secure computation aspects (addressed using TEEs), private disclosure aspects (addressed by means of differential privacy), and verifiability aspects (mitigated using secure enclave attestation capabilities).

More generally, shuffling models of differential privacy can use broader classes of local randomizers, and can even select these local randomizers adaptively [178]. This can enable differentially private protocols with far smaller error than what is possible in the local model, while relying on weaker trust assumptions
<figure><img src="image_4.png" /><figcaption>Figure 3: The Encode-Shuffle-Analyze (ESA) framework, illustrated here for 4 players.</figcaption></figure>

than in the central model, e.g., [120, 178, 45, 201, 204, 200, 202, 203, 110].

**Hybrid differential privacy** Another promising approach is hybrid differential privacy [40], which combines multiple trust models by partitioning users based on their trust model preference (e.g. trust or lack of trust in the curator). Prior to the hybrid model, there were two natural choices. The first was to use the least-trusting model, which typically provides the lowest utility, and conservatively apply it uniformly over the entire userbase. The second was to use the most-trusting model, which typically provides the highest utility, but only apply it over the most-trusting users. By allowing multiple models to coexist, hybrid model mechanisms can achieve more utility from a given userbase, compared to purely local or central DP mechanisms. For instance, [40] describes a system in which most users contribute their data in the local model of privacy, and a small fraction of users opt-in to contributing their data in the central DP model. This enables the design of a mechanism which, in some circumstances, outperforms both the conservative local DP mechanism applied across all users as well as the central DP mechanism applied only across the small fraction of opt-in users. Recent work by [57] further demonstrates that a combination of multiple trust models can become part of a promising toolkit for designing and implementing differential privacy. This construction can be directly applied in the federated learning setting; however, the general concept of combining trust models or computational models may also inspire similar but new approaches for federated learning.

### 4.2.3 Verifiability

An important notion that is orthogonal to the above privacy techniques is that of verifiability. Generally speaking, verifiable computation will enable one party to prove to another party that it has executed the desired behavior on its data faithfully, without compromising the potential secrecy of the data. The concept of verifiable computation dates back to Babai et al. [42] and has been studied under various terms in the literature: checking computations [42], certified computation [343], delegating computations [210], as well as verifiable computing [195].

In the context of FL, verifiability can be used for two purposes. First, it would enable the server to prove to the clients that it executed the intended behavior (e.g., aggregating inputs, shuffling of the input messages, or adding noise for differential privacy) faithfully. Second, it would enable the clients to prove to the server that their inputs and behavior follow that of the protocol specification (e.g., the input belongs to a certain
range, or the data is a correctly generated ciphertext).

Multiple techniques can be useful to provide verifiability: zero-knowledge proofs (ZKPs), trusted execution environments (TEEs), or remote attestation. Among these ZKPs provide formal cryptographic security guarantees based on mathematical hardness, while others make rely on assumption about the security of trusted hardware.

**Zero-knowledge proofs (ZKPs)** Zero knowledge (ZK) proofs are a cryptographic primitive that enables one party (called the *prover*) to prove statements to another party (called the *verifier*), that depend on secret information known to the prover, called witness, without revealing those secrets to the verifier. The notion of zero-knowledge was introduced in the late 1980’s by Goldwasser et al. [209]. It provides a solution for the verifiability question on private data. While there had been a large body of work on ZK construction, the first work that brought ZKPs and verifiable computation for general functionalities in the realm of practicality was the work of Parno et al. [369] which introduces the first optimized construction and implementation for succinct ZK. Nowadays, ZKP protocols can achieve proof sizes of hundred of bytes and verifications of the order of milliseconds regardless of the size of the statement being proved.

A ZKP has three salient properties: *completeness* (if the statement is true and the prover and verifier follow the protocol, the verifier will accept the proof), *soundness* (if the statement is false and the verifier follows the protocol, the verifier will refuse the proof), and *zero-knowledge* (if the statement is true and the prover follows the protocol, the verifier will only learn that the statement is true and will not learn any confidential information from the interaction).

Beyond these common properties, there are different types of zero-knowledge constructions in terms of supported language for the proofs, setup requirements, prover and verifier computational efficiency, interactivity, succinctness, and underlying hardness assumptions. There are many ZK constructions that support specific classes of statements, Schnorr proofs [408] and Sigma protocols [147] are examples of such widely used protocols. While such protocols have numerous uses in specific settings, general ZK systems that can support any functionality provide a much more broadly applicable tool (including in the context of FL), and thus we focus on such constructions for the rest of the discussion.

A major distinguishing feature between different constructions is the need for *trusted* setup. Some ZKPs rely on a common reference string (CRS), which is computed using secrets that should remain hidden in order to guarantee the soundness properties of the proofs. The computation of such a CRS is referred to as a trusted setup. While this requirement is a disadvantage for such systems, the existing ZKP constructions that achieve most succinct proofs and verifier's efficiency require trusted setup.

Another significant property that affects the applicability in different scenarios is whether generating the proof requires interaction between the prover and the verifier, and here we distinguish non-interactive zero-knowledge proofs (NIZKs) that enable the prover to send a single message to the verifier and require no further communication. Often we can convert interactive to non-interactive proofs by making stronger assumptions about ideal functionality of hash functions (i.e., that hash functions behave as random oracles).

Additionally, there are different measurements for efficiency of a ZKP system one must be aware of, such as the length of the proof and the computation complexity of the prover and verifier. The ideal prover's complexity should be linear in the execution time for the evaluated functionality but many existing ZKPs introduce additional (sometimes significant) overhead for the prover. The most efficient verification complexity requires computation at least linear in the size of the inputs for the evaluated functionality, and in the setting of proofs for the work of the FL server this input size will be significant.

Succinct non-interactive zero-knowledge proofs (SNARKs) [71] are a type of ZKP that provides constant
proof size and verification that depends only on the input size, linearly. These attractive efficiency properties
do come at the price of stronger assumptions, which is mostly inherent, and trusted setup in all existing
scheme. Most existing SNARK constructions leverage quadratic arithmetic programs [196, 369, 136] and
are now available in open-source libraries, such as libsnark [307], and deployed in cryptocurrencies, such
as Zcash [62]. Note that SNARK systems usually require overhead on the part of the prover; in particular,
the prover computation needs to be superlinear in the size of the circuit for the statement being proven.
Recently, Xie et al. [489] presented Libra, a ZKP system that achieves linear prover complexity but with
increased proof size and verification time.

If we relax the requirements for succinctness or non-interactiveness for the construction, there is a large
body of constructions that achieve a wide range of efficiency trade-offs, avoid the trusted setup requirement
and use more standard cryptographic assumptions [92, 463, 20, 63].

In the recent years, an increasing numbers of practical applications have been using non-interactive
zero-knowledge proofs, primarily motivated by blockchains. Using interactive ZKP systems and NIZKs
efficiently in the context of FL remains a challenging open question. In such a setting, NIZKs may enable
to prove to the server properties about the client's inputs. In the setting where the verifier is the client, it
will be challenging to create a trustworthy statement to verify as it involves input from other clients. Of
interest in this setting, recent work enables to handle the case where the multiple verifiers have shares of the
statement [83].

**Trusted execution environment and remote attestation** We discussed TEEs in Section 4.2.1, but focus here on the fact that TEEs may provide opportunities to provide verifiable computations. Indeed, TEEs enable to attest and verify the code (binary) running in its environment. In particular, when the verifier knows (or can reproduce) which binary should run in the secure enclaves, TEEs will be able to provide a notion of *integrity* (the code execution cannot be affected, except by the inputs), and an *attestation* (the TEE can prove that a specific binary is executing and what is starting state was) [437, 451]. More generally, remote attestation allows a verifier to securely measure the internal state of a remote hardware platform, and can be used to establish a static or dynamic root of trust. While TEEs enable hardware-based remote attestations, both software-based remote attestions [411] and hybrid remote attestation designs [172, 274] were proposed in the literature and enable to trade off hardware requirements for verifiability.

In a federated learning setting, TEEs and remote attestations may be particularly helpful for clients to be
able to efficiently verify key functions running on the server. For example, secure aggregation or shuffling
could run in TEEs and would provide differential privacy guarantees on their outputs. Therefore, the post-
processing logic subsequently applied by the server on the differentially private data could run on the server
and remain oblivious to the clients. Note that such a system design requires the clients to know and trust
the exact code (binary) for the key functions to be applied in the enclaves. Additionally, remote attestations
may enable a server to attest specific requirements from the clients involved in the FL computation, such as
absence of leaks, immutability, and uninterruptability (we defer to [188] for an exhaustive list of minimal
requirements for remote attestation).

**4.3 Protections Against External Malicious Actors**

In this section, we assume the existence of a trusted server and discuss various challenges and open problems
towards achieving rigorous privacy guarantees against external malicious actors (e.g. adversarial clients,
adversarial analysts, adversarial devices that consume the learned model, or any combination thereof).

As discussed in Table 7, malicious clients can inspect all messages received from the server (including
the model iterates) in the rounds they participate in, malicious analysts can inspect sequences of model iter-
ates from multiple training runs with different hyperparameters, and in cross-device FL, malicious devices
can have either white-box or black-box access to the final model. Therefore, to give rigorous protections
against external adversaries, it is important to first consider what can be learned from the intermediate iter-
ates and final model.

4.3.1 Auditing the Iterates and Final Model

To better understand what can be learned from the intermediate iterates or final model, we propose quan-
tifying federated learning models’ susceptibility towards specific attacks. This is a particularly interesting
problem in the federated learning context. On the one hand, adversaries receive direct access to the model
from the server, which widens the attack surface. On the other hand, the server determines which specific
stages of the training process the adversary will receive access to the model, and additionally controls the
adversary’s influence over the model at each of the stages.

For classic (non-federated) models of computation, understanding a model’s susceptibility to attacks is
an active and challenging research area [189, 418, 99, 341, 100]. The most common method of quanti-
fying a model’s susceptibility to an attack is to simulate the attack on the model using a proxy (auditing)
dataset similar to the dataset expected in practice. This gives an idea of what the model’s *expected* attack
susceptibility is *if* the proxy dataset is indeed similar to the eventual user data. A safer method would
be to determine a worst-case upper-bound on the model’s attack susceptibility. This can be approached
theoretically as in [496], although this often yields loose, vacuous bounds for realistic models. Empirical
approaches may be able to provide tighter bounds, but for many types of attacks and models, this endeavour
may be intractable. An interesting emerging area of research in this space examines the theoretic conditions
(on the audited model and attacks) under which an unsuccessful attempt to identify privacy violations by a
simulated attack implies that no stronger attacks can succeed at such a task [153]. However, this area is still
nascent and more work needs to be done to better understand the fundamental requirements under which
auditing (via simulated attacks) is sufficient.

The federated learning framework provides a unique setting not only for attacks, but also for attack quantification and defense. Specifically, due to the server's control over when each user can access and influence the model during the training process, it may be possible to design new tractable methods for quantifying a model's average-case or worst-case attack susceptibility. Such methods would enable the development of new adaptive defenses, which can be applied on-the-fly to preempt significant adversarial influence while maximizing utility.

4.3.2 Training with Central Differential Privacy

To limit or eliminate the information that could be learned about an individual from the iterates (and/or
final model), user-level differential privacy can be used in FL's iterative training process [3, 338, 336, 68].
With this technique, the server clips the $l_2$ norm of individual updates, aggregates the clipped updates, and
then adds Gaussian noise to the aggregate. This ensures that the iterates do not overfit to any individual
user's update. To track the overall privacy budget across rounds, advanced composition theorems [168, 254]
or the analytical moments accountant method developed in [3, 346, 348, 474] can be used. The moments
accountant method works particularly well with the uniformly subsampled Gaussian mechanism. For mod-
erate privacy budgets and in the absence of a sufficiently large dataset [384], the noise introduced by this
process can lead to a large decrease in model accuracy. Prior work has explored a number of avenues to
mitigate this trade-off between privacy and accuracy, including collecting more private data [338], designing
privacy-friendly model architectures [367], or leveraging priors on the private data domain [449].

In cross-device FL, the number of training examples can vary drastically from one device to the other. Hence, similar to recent works on user-level DP in the central model [21], figuring out how to adaptively bound the contributions of users and clip the model parameters remains an interesting research direction [446, 377]. More broadly, unlike record-level DP where fundamental trade-offs between accuracy and privacy are well understood for a variety of canonical learning and estimation tasks, user-level DP is fundamentally less understood (especially when the number of contributions varies wildly across users and is not tightly bounded *a priori*). Thus, more work needs to be done to better understand the fundamental trade-offs in this emerging setting of DP. Recently, [320] made progress on this front by characterizing the trade-offs between accuracy and privacy for learning discrete distributions under user-level DP.

In addition to the above, it is important to draw a distinction between malicious clients that may be able to see (some of) the intermediate iterates during training and malicious analysts (or deployments) that can only see the final model. Even though central DP provides protections against both threat models, a careful theoretical analysis can reveal that for a specific implementation of the above Gaussian mechanism (or any other differentially private mechanism), we may get different privacy parameters for these two threat models. Naturally, we should get stronger differential privacy guarantees with respect to malicious analysts than we do with respect to malicious clients (because malicious clients may have access to far more information than malicious analysts). This “privacy amplification via iteration” setting has been recently studied by Feldman et al. [185] for convex optimization problems. However, it is unclear whether or not the results in [185] can be carried over to the non-convex setting.

**Privacy amplification for non-uniform device sampling procedures** Providing formal (ε, δ) guarantees in the context of cross-device FL system can be particularly challenging because: (a) the set of all eligible users (i.e. underlying database) is dynamic and not known in advance, and (b) users participating in federate computations may drop out at any point in the protocol. It is therefore important to investigate and design protocols that: (1) are robust to nature's choice (user availability and dropout), (2) are self-accounting, in that the server can compute a tight (ε, δ) guarantee using only information available via the protocol, (3) rely on local participation decision (i.e. do not assume that the server knows which users are online and has the ability to sample from them), and (4) achieve good privacy-utility trade-offs. While recent works [47, 257] suggest that these constraints can be simultaneously achieved, building an end-to-end protocol that works in production FL systems is still an important open problem.

**Sources of randomness (adapted from [336]** Most computational devices have access only to few sources of entropy and they tend to be very low rate (hardware interrupts, on-board sensors). It is standard—and theoretically well justified—to use the entropy to seed a cryptographically secure pseudo-random number generator (PRNG) and use the PRNG’s output as needed. Robust and efficient PRNGs based on standard cryptographic primitives exist that have output rate of gigabytes per second on modern CPUs and require a seed as short as 128 bits [401].

The output distribution of a randomized algorithm $\mathcal{A}$ with access to a PRNG is indistinguishable from the output distribution of $\mathcal{A}$ with access to a true source of entropy as long as the distinguisher is computationally bounded. Compare it with the guarantee of differential privacy which holds against any adversary, no matter how powerful. As such, virtually all implementations of differential privacy satisfy only (variants of) computational differential privacy introduced by [347]. On the positive side, a computationally-bounded adversary cannot tell the difference, which allows us to avoid being overly pedantic about this point.

A training procedure may have multiple sources of non-determinism (e.g., dropout layers or an input of a
generative model) but only those that are reflected in the privacy ledger must come from a cryptographically
secure PRNG. In particular, the device sampling procedure and the additive Gaussian noise must be drawn
from a cryptographically secure PRNG for the trained model to satisfy computational differential privacy.

**Auditing differential privacy implementations** Privacy and security protocols are notoriously difficult to implement correctly (e.g., [345, 217] for differential privacy). What techniques can be used for testing FL-implementations for correctness? Since the techniques will often be deployed by organizations who may opt not to open-source code, what are the possibilities for black-box testing? Some works [156, 315, 247] begin to explore this area in the context of differential privacy, but many open questions remain.

4.3.3 Concealing the Iterates

In typical federated learning systems, the model iterates (i.e., the newly updated versions of the model after each round of training) are assumed to be visible to multiple actors in the system, including the server and the clients that are chosen to participate in each round. However, it may be possible to use tools from Section 4.2 to keep the iterates concealed from these actors.

To conceal the iterates from the clients, each client could run their local portion of federated learning inside a TEE providing confidentiality features (see Section 4.2.1). The server would validate that the expected federated learning code is running in the TEE (relying on the TEE’s attestation and integrity features), then transmit an encrypted model iterate to the device such that it can only be decrypted inside the TEE. Finally the model updates would be encrypted inside the TEE before being returned to the server, using keys only known inside the enclave and on the server. Unfortunately, TEEs may not be generally available across clients, especially when those clients are end-user devices such as smartphones. Moreover, even when TEEs are present, they may not be sufficiently powerful to support training computations, which would have to happen inside the TEE in order to protect the model iterate, and may be computationally expensive and/or require significant amounts of RAM – though TEE capabilities are likely to improve over time, and techniques such as those presented in [447] may be able to reduce the requirements on the TEE by exporting portions of the computation outside the TEE while maintaining the attestation, integrity, and confidentiality needs of the computation as a whole.

Similar protections can be achieved under the MPC model [351, 10]. For example, the server could encrypt the iterate's model parameters under a homomorphic encryption scheme before sending it to the client, using keys known only to the server. The client could then compute the encrypted model update using the homomorphic properties of the cryptosystem, without needing to decrypt the model parameters. The encrypted model update could then be returned to the server for aggregation. A key challenge here will be to force aggregation on the server before decryption, as otherwise the server may be able to learn a client's model update. Another challenging open problem here is improving performance, as even state-of-the-art systems can require quite significant computational resources to complete a single round of training in a deep neural network. Progress here could be made both by algorithmic advances as well as through the development of more efficient hardware accelerators for MPC [393].

Additional challenges arise if the model iterates should also be concealed from the server. Under the TEE model, the server portion of federated learning could run inside a TEE, with all parties (i.e., clients and analyst) verifying that the server TEE will only release the final model after the appropriate training criteria have been met. Under the MPC model, an encryption key could protect the model iterates, with the key held by the analyst, distributed in shares among the clients, or held by a trusted third party; in this setup, the key holder(s) would be required to engage in the decryption of the model parameters, and could thereby ensure
that this process happens only once.

### 4.3.4 Repeated Analyses over Evolving Data

For many applications of federated learning, the analyst wishes to analyze data that arrive in a streaming fashion, and must also provide dynamically-updated learned models that are (1) correct on the data seen thus far, and (2) accurately predict future data arrivals. In the absence of privacy concerns, the analyst could simply re-train the learned model once new data arrive, to ensure maximum accuracy at all times. However, since privacy guarantees degrade as additional information is published about the same data [167, 168], these updates must be less frequent to still preserve both privacy and accuracy of the overall analysis.

Recent advances in differential privacy for dynamic databases and time series data [143, 142, 97] have all assumed the existence of a trusted curator who can see raw data as they arrive online, and publish dynamically updated statistics. An open question is how these algorithmic techniques can be extended to the federated setting, to enable private federated learning on time series data or other dynamically evolving databases.

Specific open questions include:

* How should an analyst privately update an FL model in the presence of new data? Alternatively, how well would a model that was learned privately with FL on a dataset *D* extend to a dataset *D'* that was guaranteed to be similar to *D* in a given closeness measure? Since FL already occurs on samples that arrive online and does not overfit to the data it sees, it is likely that such a model would still continue to perform well on a new database *D'*. This is also related to questions of robustness that are explored in Section 5.

* One way around the issue of privacy composition is by producing synthetic data [165, 5], which can then be used indefinitely without incurring additional privacy loss. This follows from the post-processing guarantees of differential privacy [167]. Augenstein et al. [31] explore the generation of synthetic data in a federated fashion. In the dynamic data setting, synthetic data can be used repeatedly until it has become “outdated” with respect to new data, and must be updated. Even after generating data in a federated fashion, it must also be updated privately and federatedly.

* Can the specific approaches in prior work on differential privacy for dynamic databases [142] or privately detecting changes in time series data [143, 97] be extended to the federated setting?

* How can time series data be queried in a federated model in the first place? By design, the same users are not regularly queried multiple times for updated data points, so it is difficult to collect true within-subject estimates of an individuals’ data evolution over time. Common tools for statistical sampling of time series data may be brought to bear here, but must be used in conjunction with tools for privacy and tools for federation. Other approaches include reformulating the queries such that each within-subject subquery can be answered entirely on device.

### 4.3.5 Preventing Model Theft and Misuse

In some cases, the actor or organization developing an ML model may be motivated to restrict the ability to inspect, misuse or steal the model. For example, restricting access to the model’s parameters may make it more difficult for an adversary to search for vulnerabilities, such as inputs that produce unanticipated model outputs.
Protecting a deployed model during inference is closely related to the challenge of concealing the model iterates from clients during training, as discussed in Section 4.3.3. Again, both TEEs and MPC may be used. Under the TEE model, the model parameters are only accessible to a TEE on the device, as in Section 4.3.3; the primary difference being that the desired calculation is now inference instead of training.

It is harder to adapt MPC strategies to this use case without forgoing the advantages offered by on-device inference: if the user data, model parameters, and inference results are all intended to be on-device, then it is unclear what additional party is participating in the multi-party computation. For example, naïvely attempting to use homomorphic encryption would require the decryption keys to be on device where the inferences are to be used, thereby undermining the value of the encryption in the first place. Solutions where the analyst is required to participate (e.g. holding either the encryption keys or the model parameters themselves) imply additional inference latency, bandwidth costs, and connectivity requirements for the end user (e.g. the inferences would no longer be available for a device in airplane mode).

It is crucial to note that even if the model parameters themselves are successfully hidden, research has shown that in many cases they can be reconstructed by an adversary who only has access to an inference/prediction API based on those parameters [450]. It is an open question what additional protections would need to be put into place to protect from these kinds of issues in the context of a model residing on millions or billions of end user devices.

## 4.4 Protections Against an Adversarial Server

In the previous section, we assumed the existence of a trusted server that can orchestrate the training process. In this section we discuss the more desirable scenario of protecting against an adversarial server. In particular, we start by investigating the challenges of this setting and existing works, and then move on to describing the open problems and how the techniques discussed in Section 4.2 can be used to address these challenges.

### 4.4.1 Challenges: Communication Channels, Sybil Attacks, and Selection

In the cross-device FL setting, we have a server with significant computational resources and a large number of clients that (i) can only communicate with the server (as in a star network topology), and (ii) may be limited in connectivity and bandwidth. This poses very concrete requirements when enforcing a given trust model. In particular, clients do not have a clear way of establishing secure channels among themselves independent of the server. This suggests, as shown by Reyzin et al. [392] for practical settings, that assuming honest (or at least semi-honest) behaviour by the server in a key distribution phase (as done in [80, 58]) is required in scenarios where private channels among clients are needed. This includes cryptographic solutions based on MPC techniques. An alternative to this assumption would be incorporating an additional party or a public bulletin board (see, e.g., [398]) into the model that is known to the clients and trusted to not collude with the server.

Beyond trusting the server to facilitate private communication channels, the participants in cross-device FL must also trust the server to form cohorts of clients in a fair and honest manner. An actively malicious adversary controlling the server could simulate a large number of fake client devices (a "Sybil attack" [160]) or could preferentially select previously compromised devices from the pool of available devices. Either way, the adversary could control far more participants in a round of FL than would be expected simply from a base rate of adversarial devices in the population. This would make it far easier to break the common assumption in MPC that at least a certain fraction of the devices are honest, thereby undermining the security of the protocol. Even if the security of protocol itself remains intact (for example, if its security is rooted
in a different source of trust, such as a secure enclave), there is a risk that if a large number of adversarial clients' model updates are known to or controlled by the adversary, then the privacy of the remaining clients' updates may be undermined. Note that these concerns can also apply in the context of TEEs. For example, a TEE-based shuffler can also be subject to a Sybil attack; if a single honest user's input is shuffled with known inputs from fake users, it will be straight forward for the adversary to identify the honest user's value in the shuffled output.

Note that in some cases, it may be possible to establish proof among the clients in a round that they are all executing the correct protocol, such as if secure enclaves are available on client devices and the clients are able to remotely attest one another. In these cases, it may be possible to establish privacy for all honest participants in the round (e.g., by attesting that secure multi-party computation protocols were followed accurately, that distributed differential privacy contributions were added secretly and correctly, etc.) even if the model updates themselves are known to or controlled by the adversary.

### 4.4.2 Limitations of Existing Solutions

Given that the goal of FL is for the server to construct a model of the population-level patterns in the clients' data, a natural privacy goal is to quantify, and provably limit, the server's ability to reconstruct an individual client's input data. This involves formally defining (a) what is the view of the clients data revealed to the server as a result of an FL execution, and (b) what is the privacy leakage of such a view. In FL, we are particularly interested in guaranteeing that the server can aggregate reports from the clients, while somehow masking the contributions of each individual client. As discussed in Section 4.2.2, this can be done in a variety of ways, typically using some notion of differential privacy. There are a wide variety of such methods, each with their own weaknesses, especially in FL. For example, as already discussed, central DP suffers from the need to have access to a trusted central server. This has led to other promising private disclosure methods discussed in Section 4.2.2. Here, we outline some of the weaknesses of these methods.

**Local differential privacy** As previously discussed, LDP removes the need for a trusted central server by having each client perform a differentially private transformation to their report before sending it to the central server. LDP assumes that a user's privacy comes solely from that user's addition of their own randomness; thus, a user's privacy guarantee is independent of the additional randomness incorporated by all other users. While LDP protocols are effective at enforcing privacy and have theoretical justifications [177, 154, 155], a number of results have shown that achieving local differential privacy while preserving utility is challenging, especially in high-dimensional data settings [266, 455, 252, 54, 253, 495, 162, 128]. Part of this difficulty is attributed to the fact that the magnitude of the random noise introduced must be comparable to the magnitude of the signal in the data, which may require combining reports between clients. Therefore, obtaining utility with LDP comparable to that in the central setting requires a relatively larger userbase or larger choice of $\varepsilon$ parameter [445].

**Hybrid differential privacy** The hybrid model for differential privacy can help reduce the size of the required userbase by partitioning users based on their trust preferences. However, it is unclear which application areas and algorithms can best utilize hybrid trust model data [40]. Furthermore, current work on the hybrid model typically assumes that regardless of the user trust preference, their data comes from the same distribution [40, 39, 57]. Relaxing this assumption is critical for FL in particular, as the relationship between the trust preference and actual user data may be non-trivial.