Monsieur Pierre Geneves

Machine Learning models are increasingly used in our daily life. For instance, these models can be used for content recommendation during a purchase or to help doctors while making medical decisions,etc. However, to obtain accurate and useful models, we generally need to train the models with large amount of data. Therefore, several entities with limited datasets may want to collaborate in order to improve their local model accuracy. In traditional machine learning, such collaboration requires to first store all entities' data on a centralized server before training the model on it. Such data centralization might be problematic when the data are sensitive and data privacy is required. Instead of sharing the training data, Federated Learning shares the model parameters between a server, which plays the role of aggregator, and the participating entities. More specifically, the server sends at each round the global model to some participants (downstream). These participants then update the received model with their local data and sends back the updated gradients' vector to the server (upstream). The server then aggregates all the participants' updates to obtain the new global model. This operation is repeated until the global model converges. Although Federated Learning improves both the privacy and the accuracy, it is not perfect. In fact, sharing gradients computed by individual parties can leak information about their private training data. Several recent attacks have demonstrated that a sufficiently skilled adversary, who can capture the model updates (gradients) sent by individual parties, can infer whether a specific record or a group property is present in the dataset of a specific party. Moreover, complete training samples can also be reconstructed purely from the captured gradients. Furthermore, Federated Learning is not only vulnerable to privacy attacks, it is also vulnerable to poisoning attacks which can drastically decrease the model accuracy. Finally, Federated Learning incurs large communication costs during upstream/downstream exchanges between the server and the parties. This can be problematic for applications based on bandwidth and energy-constrained devices, as it is the case for mobile systems, for instance. In this thesis, we first propose three bandwidth efficient schemes to reduce the bandwidth costs up to 99.9%. We then propose differentially private extensions of these schemes which are robust against honest-butcurious adversaries (server or participants) and protect the complete dataset of each participant (participant-level privacy). Moreover, our private solutions outperform standard privacy-preserving Federated Learning schemes in terms of accuracy and/or bandwidth efficiency. Finally, we investigate the robustness of our schemes against security attacks performed by malicious participants and discuss a possible privacy-robustness tradeoff which may spur further research.

6.6

In-backdoor attack on FL-SIGN, FL-CS, FL-TOP and FL-STD with the CIFAR dataset, η Adv is set to 7, 4, 2 for 10%, 20%, 40% respectively. The table depicts the global accuracy convergence and the accuracy of the label "airplane" which is under attack. We choose the compression ratio r for FL-CS and FL-TOP such that each scheme reaches the same accuracy as FL-STD on the same settings but without the attack. Therefore, r is set to 60% and 20%, respectively. Note also, that we do not use boosting with FL-CS to not impact the sparsity of the model's update. . . . . . . . . . . . . . . . . . . . . . . . . . .

6.7

Out-backdoors attack on FL-SIGN, FL-CS, FL-TOP and FL-STD with the MNIST dataset. η Adv is set to 1 (no boosting). The table displays the global model accuracy as well as the model's prediction rate to misclassify the out-backdoor class "0" to the targeted class "1" (attack accuracy). We choose the compression ratio r for FL-CS and FL-TOP such that each scheme reaches the same accuracy as FL-STD on the same settings but without the attack. Therefore, r is set to 5% and 0.5%, respectively. . . . . . . . . . . . . . . . . . .

6.8

Out-backdoors attack on FL-SIGN and FL-STD with the CIFAR dataset. η Adv is set to 1 (no boosting). The table displays the global model accuracy as well as the model's prediction rate to misclassify the out-backdoor class "airplane" to the targeted class "ship" (attack accuracy). We choose the compression ratio r for FL-CS and FL-TOP such that each scheme reaches the same accuracy as FL-STD on the same settings but without the attack. Therefore, r is set to 60% and 20%, respectively. . . . . . . . . . . . . . . . . . . . . . . 6.9

In-backdoor attack on FL-SIGN-DP and FL-SIGN with MNIST dataset. The table depicts the global accuracy convergence and the accuracy of the label "5" which is under attack. 6.10 In-backdoor attack on FL-SIGN and FL-SIGN-DP with Fashion-MNIST dataset. The table depicts the global accuracy convergence and the accuracy of the label "Sandal" which is under attack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.11 Out-backdoors attack on FL-SIGN-DP and FL-SIGN with MNIST dataset. The table displays the global model accuracy as well as the model's prediction rate to misclassify the out-backdoor class "0" to the targeted class "1" (attack accuracy). . . . . . . . . . . . 6.12 Out-backdoors attack on FL-SIGN-DP and FL-SIGN with Fashion-MNIST dataset. The table displays the global model accuracy as well as the model's prediction rate to misclassify the out-backdoor class "T-shirt/Top" to the targeted class "Trouser" (attack accuracy). . .

8.1

Common environment and configuration of FL-SIGN, FL-CS, FL-TOP and FL-STD. γ = 0.001.

8.2

Common environment of the privacy part. γ = 0.005 and T cl = 200. For FL-STD-DP, S is set to 1. 73 Sensitivity S used for each scheme and for different compression ratio r on Fashion-MNIST.

List of Figures

5.1

Distributions of the Top-K weight values (after convergence) for both FL-TOP and FL-STD schemes with the Fashion-MNIST dataset (left) and the medical dataset (right). . . . . .

6.1

In-backdoor attack on FL-SIGN and FL-STD with the MNIST dataset, η Adv = 7. The figure displays the global accuracy convergence and the accuracy of the label "5" which is under attack. 10% of the nodes are malicious. . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2

In-backdoor attack on FL-SIGN and FL-STD with CIFAR dataset, η Adv = 7. The figure displays the global accuracy convergence and the accuracy of the label "airplane" which is under attack. 10% of the nodes are malicious. . . . . . . . . . . . . . . . . . . . . . . .

ix x

Acknowledgement

I take this opportunity to thank people and organizations without whom this dissertation would not be possible.

First, I would like to express my profound gratitude to my supervisors Claude Castelluccia and Pierre Genevès for their unwavering support, valuable advice and for offering me the flexibility to pursue my own research interests. I was very lucky to have them as supervisors. I would also like to thank Massih-Reza Amini, Emiliano De Cristofaro, Reza Shokri, Marc Tommasi and Aurélien Bellet for taking time to be part of my thesis committee.

I also want to thank the Grenoble Alpes Data Institute in the framework of the WP5 "Data Governance, Data Protection and Privacy" for awarding me fellowships to support my PhD.

I am very fortunate to have had the opportunity to collaborate with Gergely Ács with whom I learned and progressed a lot. Thank you very much for your availability, help and support.

I would also like to thank Mérouane Debbah who made me love the research world and who remains a model for me to follow. Thank you for everything you have done for me.

I would also like to thank the members of the Magnet team at Inria Lille, who hosted me at the beginning of my PhD to work on their decentralized architecture.

I am thankful to several people I met in the course of my PhD. Many thanks to Nabil Layaïda, Vincent Roca, Théodore Christakis, Cédric Lauradoux, Thomas Calmant, Mathieu Thiery, Supriya Sreekant Adhatarao, Belkacem Teibi, Coline Boniface, Amela Fejza, Muideen Adekunle Lawal, Sarah Chlyah, Laurent Carcone, Cécile Roisin for their many productive discussions and advise. I also acknowledge each and every member of the Privatics team, Tyrex team and the Chair on the Legal and Regulatory Implications of Artificial Intelligence. It has been such a great honour working alongside every one of you! I would like to thank Microsoft for inviting me to present my research at the -Data Science Law Forum 3.0: "Operationalizing Responsible AI".

I would also like to thank my family and especially my parents, my brother, my sister, my aunt Fazia for their unconditional love and support. I owe a great deal to my family for providing me with lots of love and moral support.

I would like to thank my dear and loving wife Amira, who has given me much love and support during this adventure. You have shown patience and understanding and I will be forever indebted to you. You also gave me the most beautiful gift by giving birth to our little princess Léa whom we love so much.

Finally, I would like to thank my friends and everyone who helped me in one way or the other during my study. This achievement would not have been viable without all of you. " AI is a tool. The choice about how it gets deployed is ours.

-Oren Etzioni (Professor of Computer Science, and CEO of the Allen Institute for Artificial Intelligence.)

Motivation and Problem Statement

During the last decade, Artificial Intelligence (AI) has gained in popularity and was used in various applications (e.g. medicine/HealthCare [START_REF] Malik Amisha | Overview of artificial intelligence in medicine[END_REF], ecology [START_REF]Harnessing Artificial Intelligence for the Earth (Fourth Industrial Revolution for the Earth Series)[END_REF], agriculture [START_REF] Simon | Artificial Intelligence (AI) in Agriculture[END_REF], finance [START_REF] Cao | AI in Finance: A Review[END_REF]). In HealthCare, AI can be used, for example, to predict if a patient is more likely to be transferred to Intensive Care Unit or to die during his hospital stay. Such models are used by doctors to take better care of certain patients or to plan for enough patient beds per unit. Indeed, a recent study has shown a significant correlation between the availability of hospital resources (particularly ICU beds) and patient mortality during the early weeks of the COVID-19 pandemic [START_REF]Lack of ICU beds tied to thousands of excess COVID-19 deaths, study finds[END_REF]. Therefore, doctors can save more patients' lives if they anticipate their influx per unit via those models.

Model training requires generally the availability of large datasets. In fact, there is often a correlation between the accuracy of the model and the data size. Professor Andrew Ng declared that "It's not who has the best algorithm that wins. It's who has the most data.". However, some data holder may not have enough data. For instance, rural hospitals have much less data than non-rural ones because they treat less patients.

Collaboration between users might be a solution to address this problem. In Machine Learning, different entities may want to collaborate in order to improve their local model accuracy. In traditional machine learning, such collaboration requires to first store all entities' data on a centralized server and then to train a model on it. However, data centralization is a problem when data are sensitive and privacy is required.

After the Facebook-Cambridge Analytica data scandal [Wik] where the British consulting firm Cambridge Analytica obtained and used the personal data of millions of Facebook users without their consent for political advertising, people have become more aware about the risk behind the use of their personal data. Fortunately, the European Union took the problem seriously long before this scandal. Indeed, it promulgated the General Data Protection Regulation (aka. GDPR [START_REF]On the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF]) a regulation in EU law on data protection and privacy in the European Union (EU) and the European Economic Area (EEA) to set the general rules for the use of sensitive and private data. Moreover, the specific characteristics of AI (e.g. opacity, complexity, dependency on data) which can negatively affect the fundamental rights defined in the EU Charter of Fundamental Rights [START_REF]The European Union[END_REF], has pushed the European Union to come up with a new proposal [PC21]. This proposal aims at enhancing and promoting the protection of the rights protected by the Charter, including respect for private life and protection of personal data (Articles 7 and 8 in [START_REF]The European Union[END_REF]).

In order to mitigate the privacy risk of data centralization, Federated Learning, which allows different entities to learn collaboratively a common model without sharing their data, was introduced [SS15; MMRHA16]. Instead of sharing the training data, Federated Learning shares the model parameters between a server, which plays the role of aggregator, and the participating entities. Therefore, it delegates the learning to the users from which data originate. Federated Learning has been gaining popularity and considered to train shared models for many applications such as input text prediction, ad selection1 , drug discovery2 , or various medical applications [START_REF] Choudhury | Differential Privacy-enabled Federated Learning for Sensitive Health Data[END_REF] over the confidential data of many entities.

Although Federated Learning improves privacy, model parameters can still leak information about the training data. Indeed, [ZLH19; ZMB20; GBDM20] presented some attacks that allow an adversary to reconstruct parts of the training data of some participating entities. [NSH19; MSDS19] define membership attacks that allow one to infer if a particular record is included in the data of a specific entity. Similarly, [START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF] describes an attack which aims at inferring if a subgroup of people with a specific property, like for example skin color or ethnicity, is included in the dataset of a particular participating entity. Also, the property inference attack relates to properties that are uncorrelated to the main task.

A solution to prevent these attacks and provide theoretical guarantees is to use a privacy model called Differential Privacy [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF]. Differential Privacy has been applied to federated learning in order to protect either each record included in the dataset of any entity (record-level guarantee), or the whole dataset of any entity (client-level guarantee). Unfortunately, it is well-known that Differential Privacy drastically degrades model accuracy as it requires adding random noise to the gradients (record-level) or to the updates (client-level) of each client.

Besides that, Federated Learning may be vulnerable against Poisoning attacks which includes Data Poisoning [BNL12; Rub+09; MZ15] or Model poisoning [START_REF] Blanchard | Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent[END_REF][START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF]. Data and Model poisoning attacks aim at reducing the model accuracy by altering respectively the training data or the learning process. Also, Poisoning attacks may either impact the global accuracy of the model (untargeted) or the accuracy of a specific class (targeted). Different solutions were proposed to be more robust against such attacks but they generally implies the access to each individual update. However, access to each individual update means that we can not use the secure aggregation protocol which allows to access only the aggregate update.

Finally, the communication cost between the server and the clients is another drawback of Federated Learning. Indeed, knowing that a model has on average millions of parameters, each of them encoded with 32 bits and each round requires an upstream and downstream communication cost, the total cost may be problematic. Therefore, some energy-constrained devices may suffer a lot during the training.

Medical and health datasets are considered as sensitive data. Indeed, Electronic Health Records datasets, for example, contains private information about different patients. Such private information may be harmful to the patient. An employer can decide to dismiss his employee if he knows that he is seriously ill, or, an insurance company may decide to increase the costs of the sick patient's insurance. On the other hand, these datasets are important and their benefits indisputable since they can help us analyzing and understanding interesting patterns. Various AI models are used for proactive healthcare management, disease mapping, finding effective medicines for diseases that are still not cured [START_REF] Daley | EXAMPLES OF ARTIFICIAL INTELLIGENCE SHAKING UP[END_REF][START_REF] Inc | [END_REF]. The main objective of this thesis is to design, implement and evaluate privacy-preserving Federated-learning algorithms. Another objective is to design robust solutions against state-of-the-art security attacks. Finally, the solutions should be bandwidth efficient and accurate for better usability and usefulness.

Contributions

In this section, we present our solutions and contributions that address the drawbacks of federated learning presented above.

Bandwidth Efficient Federated Learning

The first drawback of the federated learning scheme is the large communication costs incurred by upstream/downstream exchanges. We explored two different approaches: update compression and model compression. Update compression consists in compressing the size of the updates that are sent by the participants to the server. We proposed two "update compression" solutions, namely FL-SIGN and FL-CS. FL-SIGN is a quantization-based solution. It sends only a single bit per model parameter for aggregation. This extreme quantization reduces the required updates' bandwidth by a factor of 32, while still providing similar performance to the standard federated learning approach.

FL-CS for its part leverages the sparsity of the model updates and relies on the compressive sensing theory [Don06; CT06; CRT06] which enables to reconstruct a complete sparse data (ie,. image or signal) from few sampled points in it. More specifically, it loosely compresses the sparse model updates in federated learning using a slightly modified version of compressive sensing. Indeed, our protocol allows to save bandwidth and reduce communication costs by transferring only the low frequency components of the gradient vector to the server (instead of some random frequency components like in traditional compressive sensing). The server can reconstruct the approximated sparse gradient vector by efficiently solving a convex quadratic optimization problem. This approach provides more accurate reconstruction than simply applying the inverse Fourier transform on the low frequency components. Our approach is also scalable to large gradient vectors and is almost as accurate as the vanilla federated learning protocol, referred to FL-STD, without any compression, still incurring much smaller communication cost (up to 95% less).

Model compression consists in compressing the size of the model in order to reduce the number of element in the update vectors. We developed a solution, called FL-TOP, that harnesses the ability of the model to converge and to reach good accuracy under constraint. Indeed, in FL-TOP only some weights are updated while keeping all the remaining ones constant (defined as constraint). As all participants always update the same set of weights and transfer them, communication costs in both upstream and downstream are reduced. Our results show it also reduces the upstream and downstream bandwidth by a factor of 1000 compared to standard federated learning, which makes it particularly adapted to applications based on energy-constrained devices as it is the case for mobile systems.

Differentially Private and Bandwidth Efficient Federated Learning

We extended the aforementioned bandwidth efficient schemes to provide theoretical privacy guarantees. We proposed FL-SIGN-DP a privacy-preserving extension which provides client-level Differential Privacy (DP). Specifically, it hides any information that is unique to a client's training data, regardless whether it is about a single or multiple records, but still allows learning about characteristics that are common among multiple clients' training data. Our DP learning protocol, whose convergence rate is also computed analytically, produces models with an accuracy comparable to its non-private counterpart, even with stringent privacy guarantees (e.g., ε = 1). In order to diminish the communication costs of our DP algorithm, we proposed a novel discretized and distributed version of the Gaussian Mechanism. In particular, as opposed to the standard Gaussian Mechanism [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF], the noise values come from a discretized domain and are tightly concentrated around its mean depending on the desired privacy guarantee ε. As a result, these values can be encoded with fewer bits than if they came from a continuous Gaussian distribution. Also, participants inject Gaussian noise in a distributed manner so that the sum of the noisy compressed vectors is differentially private. In addition, secure aggregation guarantees that the server (or any other third party) can only learn the noisy compressed aggregate.

The private extension of the standard federated learning scheme (FL-STD-DP) uses the full model which often has a high sensitivity. Unfortunately, the noise required by DP is proportional to its sensitivity. Furthermore, the accuracy of the model is inversely proportional to the added noise. Therefore, reducing sensitivity via bandwidth-efficient schemes can greatly improve model performance. The FL-CS-DP and FL-TOP-DP schemes reduce the sensitivity via compression and enable to add less noise, which improves the accuracy of the model compared to FL-STD-DP scheme.

The differentially private extension of FL-CS called FL-CS-DP adds Gaussian noise to the compressed gradients. In FL-CS-DP and similarly to FL-SIGN-DP, participants inject Gaussian noise in a distributed manner owing to the linear compression scheme. Reconstructing the approximated gradients is an instance of Basis Pursuit Denoising (or LASSO), which can be solved with efficient solvers that provide large accuracy despite the added Gaussian noise. We show that FL-CS-DP produces more accurate models than FL-STD-DP, that is, the differentially private variant of the vanilla federated learning protocol without any compression. Therefore, compression boosts the accuracy of differentially private federated learning and also reduces bandwidth cost by more than 60% with early stopping [START_REF] Chollet | Keras Early Stopping[END_REF].

Also, we proposed a novel differentially private federated learning solution as an extension of FL-TOP called FL-TOP-DP that improves the model accuracy. The proposed scheme provides theoretical privacy guarantees, as it is based on Differential Privacy. Furthermore, it optimizes the model accuracy by constraining the model learning phase on a few selected weights. As all participants always update the same set of weights and transfer them to the server for aggregation, the proposal can be easily integrated with secure aggregation [START_REF] Bonawitz | Practical Secure Aggregation for Federated Learning on User-Held Data[END_REF], exactly as for FL-SIGN-DP and FL-CS-DP, which allows parties to add less noise than other decentralized perturbation approaches such as randomized response [START_REF] Erlingsson | RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response[END_REF] used in local differential privacy. Finally, we noticed that, compression (bandwidth efficiency) which reduces the sensitivity of the models in FL-CS-DP and FL-TOP-DP seems to be compatible with differential privacy. Indeed, the two combined improve the utility of the private model.

Finally, in FL-CS-DP and FL-TOP-DP, we add the noise to specific coordinates that often have much larger update values than others. The objective is to increase the value-to-noise ratio to achieve better performance. In FL-CS-DP, the noise is added to the first coefficients. Indeed, due to the large energy compaction property of DCT, the first coefficients, which correspond to the low frequency components of the update vector, tend to have the largest magnitude and hence convey the most information about the model update. Similarly, the constraint defined in FL-TOP-DP by updating only the Top-K weights, leads to the increase of update values of those weights. Therefore, adding the noise to the updates of the Top-K weights leads to increase the value-to-noise level.

Secure and Bandwidth Efficient Federated Learning

The concept of "curse of dimensionality" was introduced in [START_REF] Chang | Cronus: Robust and heterogeneous collaborative learning with black-box knowledge transfer[END_REF]. The authors claim that large models are more vulnerable to privacy and security attacks. Therefore, reducing the model size (or its update) should make the model more robust against such attacks.

To validate this assumption, we experimentally evaluated the robustness of our bandwidth efficient schemes by implementing and testing several State-of-the-Art security attacks, such as model degradation (where the adversary aims at reducing the global model accuracy) or backdoor inclusion attacks (where the adversary aims at inserting hidden backdoors). We showed that, FL-SIGN, is more resilient to these attacks than the other scheme thanks to: (1) the quantization which limits the adversarial impact on the aggregate as it requires to bound each parameter's update with +1/-1. Therefore, the boosting which is commonly used by an adversary to surpass the updates of honest participants can be easily detected. (2) the majority vote (by taking the median) makes also our approach more robust against poisoning attacks. Indeed, if we assume that we have more honest participants than malicious ones, we are more likely to update the weights correctly.

Although, FL-SIGN is robust against security attacks and may suggest a possible compatibility between compression and robustness to security attacks, both FL-CS and FL-TOP are vulnerable against poisoning attacks. Therefore, compression does not necessarily imply robustness against security attacks.

Finally, we decided to evaluate the robustness of FL-SIGN-DP against poisoning attacks. Although FL-SIGN is robust against various attacks, its differentially private variant FL-SIGN-DP however turns out to be more vulnerable to the security attacks. Indeed, the attacks are inherently concealed by the noise which is introduced to guarantee Differential Privacy. Our result suggests a possible privacy-security tradeoff.

Thesis Structure

The thesis is structured as follows. Section 2 details the preliminaries including the basic Federated Learning algorithm (FL-STD) and Differential Privacy (DP). Section 3 introduces related work. To address the large bandwidth costs drawback of Federated Learning, we define in Chapter 4 three bandwidth efficient schemes, namely FL-SIGN, FL-CS and FL-TOP which are as accurate FL-STD. We therefore propose in Chapter 5 to extend theses schemes in order to obtain differential private guarantees and defined as FL-SIGN-DP, FL-CS-DP and FL-TOP-DP, respectively, as a solution to privacy issues in FL-STD. In Chapter 6 we investigate the robustness of the proposed schemes on state-of-theart security attacks, and finally Section 7 provides a summary and additional discussions about the proposed algorithms and future works. It is also robust against state-of-the-art backdoor as well as model degradation attacks even when a large proportion of the participant nodes are malicious. We propose a practical differentially private extension of this scheme which protects the whole dataset of participating entities. We show that this extension performs as efficiently as the non-private but robust scheme, even with stringent privacy requirements but are less robust against model degradation and backdoor attacks. This suggests a possible fundamental trade-off between Differential Privacy and robustness.

Publications

Part I

State-of-the-Art Each client k submits the update ∆w k t = w k t -w k t-1 to the server, which then updates the common model as follows:

wt = wt-1 + k∈K |D k | j |D j | ∆w k t ,
where |D k | is known to the server for all k (a client's update is weighted with the size of its training data). The server stops training after a fixed number of rounds T cl , or when the performance of the common model does not improve on a held-out data.

Note that each D k may be generated from different distributions (i.e., Non-IID case), that is, any client's local dataset may not be representative of the population distribution [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]. This can happen, for example, when not all output classes are represented in every client's training data. The federated learning of neural networks is summarized in Alg. 1. In the sequel, each client is assumed to use the same model architecture.

12 w k t = SGD(D k , w k t-1 , T gd ) Output: Model update (w k t -w k t-1 )
The motivation of federated learning is three-fold: first, it aims to provide confidentiality of each participant's training data by sharing only model updates instead of potentially sensitive training data. Second, in order to decrease communication costs, clients can perform multiple local SGD iterations before sending their update back to the server. Third, at each round, only a few clients are required to perform local training of the common model, which further decreases communication costs and makes the approach especially appealing with large number of clients. There is different types of federated learning schemes which can be classified based on the distributions of data features and data samples among participants [START_REF] Yang | Federated machine learning: Concept and applications[END_REF]. The most used is the horizontally federated learning (HFL) which assumes that participants share similar features but they differ in users' records [KC04; SS15; MMRHA16]. The second approach is called vertically federated learning (VFL) and it assumes that participants share the same users' records but with different features [START_REF] Vaidya | Privacy preserving association rule mining in vertically partitioned data[END_REF]. Federated transfer learning (FTL) is another approach where participants have little overlap in both users' records and features [START_REF] Yang | Federated machine learning: Concept and applications[END_REF]. Similarly, federated learning can be classified based on the model architectures among participants. Generally, we assume that all participants train models with the same architecture and it is defined as Federated Learning with Homogeneous Architectures. However, in federated learning with Heterogeneous Architectures each participant can use a unique model architecture over the training process [START_REF] Li | Fedmd: Heterogenous federated learning via model distillation[END_REF].

Standard Federated Learning requires a single server which aggregates the received models/updates from participants. However, in Decentralized Federated Learning, each participant may play the role of the server at a given round [YLCT19; Lyu+19; LYY20]. Therefore, the number of possible server during the training process can be equal to the number of participants.

Differential Privacy

Differential privacy allows a party to privately release information about a dataset: a function of an input dataset is perturbed, so that any information which can differentiate a record from the rest of the dataset is bounded [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF]. Intuitively, this guarantees that an adversary, provided with the output of A, can draw almost the same conclusions (up to ε with probability larger than 1 -δ) about any record no matter if it is included in the input of A or not [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF]. That is, for any record owner, a privacy breach is unlikely to be due to its participation in the dataset.

Definition 1 (Privacy loss). Let A be a privacy mechanism which assigns a value

Moments Accountant. Differential privacy maintains composition; the privacy guarantee of the kfold adaptive composition of A 1:k = A1, . . . , A k can be computed using the moments accountant method [START_REF] Abadi | Deep Learning with Differential Privacy[END_REF]. In particular, it follows from Markov's inequality that Pr (A,D,D ,O))]/ exp(λε) for any output O ∈ Range(A) and λ > 0. This implies that A is (ε, δ)-DP with δ = min λ exp(αA(λ)-λε), where αA(λ

[P(A, D, D , O) ≥ ε] ≤ E[exp(λP
) = max D,D log E O∼A(D) [exp(λP(A, D, D , O))]
is the log of the moment generating function of the privacy loss. The privacy guarantee of the composite mechanism A 1:k can be computed using that αA

1:k (λ) ≤ k i=1 αA i (λ) [Aba+16].
Gaussian Mechanism. There are a few ways to achieve DP, including the Gaussian mechanism [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF]. A fundamental concept of all of them is the global sensitivity of a function [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF]. The Gaussian Mechanism [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF] consists of adding Gaussian noise to the true output of a function. In particular, for any function f : D → R n , the Gaussian mechanism is defined as adding i.i.d Gaussian noise with variance (∆2f • σ) 2 and zero mean to each coordinate value of f (D). Recall that the pdf of the Gaussian distribution with mean µ and variance ξ 2 is

Definition 3 (Global Lp-sensitivity).

pdf G(µ,ξ) (x) = 1 √ 2πξ exp - (x -µ) 2 2ξ 2 (2.1)
In fact, the Gaussian mechanism draws vector values from a multivariate spherical (or isotropic) Gaussian distribution which is described by random variable G(f (D), ∆2f • σIn), where n is omitted if it's unambiguous in the given context.

Compressive Sensing

Compressive Sensing (CS) [Don06; CT06; CRT06] aims to reconstruct the original signal from significantly fewer samples (or measurements) than other traditional sampling techniques, which are based on the Nyquist-Shannon theorem, by exploiting the sparsity of the signal.

Consider a signal x ∈ R n which admits a sparse representation s ∈ R n , that is, there exists a sparsity orthonormal basis with matrix Ψ ∈ R n×n such that:

x = Ψs (2.2)
Here, s is U -sparse if s 0 = U. Ψ can denote any linear transformation, such as Discrete Fourier/Cosine or Wavelet Transform, which renders the original signal x sparse. If x is already sparse, then Ψ can be the identity matrix which corresponds to the canonical sparsity basis.

In CS, x is reconstructed from some of its linear measurements. For m measurements, the signal is "sampled" in m values yj = φj, x (1 ≤ j ≤ m), where the vectors φj ∈ R n constitute the sensing basis matrix Φ = (φ1, φ2, . . . , φm) ∈ R m×n . Here, m = r × n, where r is the compression ratio. Therefore, the compression operator C is defined as:

C(x, m) = y = Φx = ΦΨs = Θs (2.3)
where Θ is the sparsity sensing matrix. There are several options to select the sensing matrix Φ. When Φ is a random matrix (e.g., each element of Φ is an iid sample from G(0, 1/m)), then Ψ works well with an arbitrary sparsity basis [START_REF] Jacques | Compressed sensing: When sparsity meets sampling[END_REF]. On the other hand, the numerical reconstruction of x in that case has a complexity of O(mn) which can be very large (recall that n is the model size in the order of 10 6 ). Another (faster) option for the sensing matrix Φ is when it is composed of random m rows of the matrix of the (real) Discrete Fourier/Cosine Transform. Then, matrix multiplication can be executed with the Fast Fourier Transform (FFT) in O(n ln n), but such sensing matrix provides accurate reconstruction if Ψ is the identity matrix, i.e. x is already sparse [START_REF] Jacques | Compressed sensing: When sparsity meets sampling[END_REF]. Fortunately, this usually holds for gradient vectors (or can be made as such by sparsification without significantly affecting convergence) and hence we will use this option in this dissertation.

In order to recover s from y, one has to solve a system of linear equations with m equations and n unknowns. Although this system seems underdetermined because m < n, CS exploits the U -sparsity of s for the reconstruction. It aims to reconstruct the sparse vector s from y = Θs given the sparsity sensing basis Θ by solving the following optimization problem: Eq. (2.4) defines our decompression operator and is an instance of convex quadratic programming.

arg
In this paper, we use the Orthant-Wise Limited-memory Quasi-Newton (OWL-QN) algorithm [AG07; Tay20], an extension of Limited-memory BFGS, which is a numerical scalable optimization procedure that can efficiently solve Eq. (2.4). When λ → 0, the problem in Eq. (2.4) becomes BP because λ s 1 tends to 0. In the case of non-noisy sensing measurements, a BP decoder is more adapted to reconstruct the sparse signal s. Otherwise, BPDN is more suited. This has particular importance in our case when the compressed vector (measurements) are noised to guarantee Differential Privacy, i.e., y = Θs+z where z ∼ N (0, SIσ) (see Section 5.3.1). Approximate signal reconstruction from noisy measurements have been theoretically justified in [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF] from the Restricted Isometry Property of Θ.

Definition 4 (Restricted Isometry Property (RIP) [START_REF] Emmanuel | Decoding by linear programming[END_REF]). The U -restricted isometry constant 0 ≤ δU < 1 of a matrix Θ ∈ R m×n is defined as the smallest number such that:

(1 -δU ) s 2 2 ≤ Θs 2 2 ≤ (1 + δU ) s 2 2
for all U -sparse vector s ∈ R n and we say that the matrix Θ obeys the Restricted Isometry Property (or RIP(U ,δU )) of order U < m.

Theorem 1 (Reconstruction error of BPDN [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF]).

If Θ is RIP(2U, δU ) and δU < √ 2 -1, then ||s -R(y, κ)||2 ≤ Cκ + (D/ √ K)||s -sK ||1
, where C and D are constants and sK is a vector with all but the K-largest entries of s set to zero1 .

Finally, notice that the compression operator C in Eq. (2.3) is linear, which means that:

i C(xi, m) = C i xi, m and therefore D i C(xi, m) ≈ i xi
This linearity allows to combine secure aggregation and compressive sensing described in Section 5.3.1.

Error Propagation

Biased estimation of the gradients may prevent model convergence unless the approximation error introduced by lossy compression techniques, such as compressive sensing, sketching, or quantization, is accumulated and re-injected in every optimization round [START_REF] Sai | Error Feedback Fixes SignSGD and other Gradient Compression Schemes[END_REF] The corrected direction pt is obtained by adding the error et-1 accumulated over all iterations to gt (see Alg. 2 in [START_REF] Sai | Error Feedback Fixes SignSGD and other Gradient Compression Schemes[END_REF] for more details). Here, the error is calculated based on the biased estimation of the update given by D(C(pt)).

Related Work

Machine Learning and Privacy

Inference Attacks

There exists a few inference attacks specifically designed against federated learning schemes. In property inference attack [START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF], the adversary's goal is to infer whether records with a specific property are included in the training dataset of the other participants (called batch property inference). The authors demonstrate the attack by inferring whether black people are included in any of the training datasets, where the common model is trained for gender classification (i.e., the inferred property is independent of the learning objective). The attack assumes the participation of all the participants at each round including the adversary. Therefore, the adversary can retrieve the aggregated update of honest participants by first computing the difference between the received model at round t and t -1 and then by subtracting his update sent to the server at round t -1. It can also be passive or active. In passive mode, the adversary locally "emulate" the collaborative training process by sampling data with and without the property, calculate the aggregate of honest updates and train a binary classifier to distinguish between the aggregates which includes an update based on the data with and without the property. However, the attack is more powerful when the adversary is active and use multi-task learning to simultaneously optimize the main task and recognize batch properties. As a result, the malicious update will lead the global model to learn a separable representation of the gradients generated by using data with and without the property and therefore enabling the adversary to decide whether the training data has the property.

An adversary who has a black-box access to a classifier model (has a view only on the outputs of the last layer), can use model inversion attacks [START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF] to infer features which are specific to each class. Each reconstructed sample looks like an averaged record over a class and can be considered as the representative of it. Similarly, an adversary who participates actively in the learning process as it is the case in federated learning can use GAN [START_REF] Goodfellow | Generative Adversarial Nets[END_REF] to reconstruct the representatives of the classes [START_REF] Hitaj | Deep models under the GAN: information leakage from collaborative deep learning[END_REF]. And in the special case where all the records belonging to the same class represent the same person or thing then both inversion attack and GAN attack can reconstruct samples which are similar to training inputs. Recent reconstruction attacks [ZLH19; ZMB20; GBDM20] show that the complete training samples including their labels can also be reconstructed only from the captured gradients. However, the reconstruction accuracy is inversely proportional to the batch size which is used to compute those gradients. Indeed, the received gradients on which the attack is based is the average gradients over a batch and more we increase the size of the batch, more we dilute the effect of any individual record, thus becoming harder to reconstruct it.

In [START_REF] Nasr | Comprehensive Privacy Analysis of Deep Learning: Passive and Active White-box Inference Attacks against Centralized and Federated Learning[END_REF], the proposed attack infers if a specific person is included in the training dataset of the participants (aka, Membership inference). The adversary extracts the following features from every snapshot of the common model, which is a neural network: output value, hidden layers, loss values, and the gradient of the loss with respect to the parameters of each layer. These features are used to train a membership inference model, which is a convolutional neural network. The attack is more powerful when the adversary is the server and therefore has access to each individual update and when it is active.

Privacy-Preserving Machine Learning

Differentially Private machine learning models are obtained by adding a calibrated amount of noise during the learning process. More, specifically the noise is added on: (1) the objective function (objective perturbation) [CMS11; JT14; PWWD16; PWD17; Iye+19; JKT12; CM09; ZZXYW12], (2) the gradients at each iteration (gradient perturbation) [SS15; ZWZZC19; SCS13], (3) the final model obtained after the training (output perturbation) [CMS11; JT14; CM09; PRR10; HCB16; Wu+17], (4) input perturbation [START_REF] John C Duchi | Local privacy and statistical minimax rates[END_REF] and (5) label perturbation via teachers-student ensemble [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF]. However, the output and objective perturbation methods are often not applicable to non-convex settings as it is the case in deep learning. Generally, gradient perturbation is widely used for differentially private deep learning [SS15; ZWZZC19; Aba+16] and requires to manually clipping the gradients norm at each iteration as we are not able to have a prior estimate of the real bound in deep learning. Clipping the norm and therefore bounding the gradients' sensitivity is required to generate the noise in differential privacy [START_REF] Abadi | Deep Learning with Differential Privacy[END_REF][START_REF] Jayaraman | Evaluating differentially private machine learning in practice[END_REF].

The concept of Client-based Differential Privacy has been introduced in [START_REF] Mcmahan | Learning Differentially Private Recurrent Language Models[END_REF] and [START_REF] Geyer | Differentially Private Federated Learning: A Client Level Perspective[END_REF], where the goal is to hide any information that is specific to a single client's training data. These algorithms noise the contribution of a single client instead of a single record in the client's dataset. The noise is drawn from continuous distributions and added by the server, hence, unlike our solution, these works assume that the server is trusted. However, a noise drawn from continuous distributions may impact negatively the differential privacy guarantees [START_REF] Mironov | On Significance of the Least Significant Bits for Differential Privacy[END_REF]. In fact, the vulnerability is based on irregularities of floating-point implementations of the privacy-preserving mechanism. Therefore, a better solution would be to sample noise from discrete distributions instead [START_REF] Mironov | On Significance of the Least Significant Bits for Differential Privacy[END_REF][START_REF] Clément L Canonne | The Discrete Gaussian for Differential Privacy[END_REF]. The use of Discrete Gaussian has been proposed in [START_REF] Clément L Canonne | The Discrete Gaussian for Differential Privacy[END_REF], however it requires to add the discrete noise on integer values. Fortunately, our discrete Gaussian mechanism proposed in Section 5.2.2 is more general as the noise can be added even to real numbers. Moreover, the privacy guarantee of the distributed generation of discrete Gaussian noise has not been analyzed earlier (e.g., in federated learning).

Recently, [START_REF] Liu | FedSel: Federated SGD Under Local Differential Privacy with Top-k Dimension Selection[END_REF] proposed to add noise only to the K largest update1 à la local-DP. In local-DP, each client adds larger noise that what is necessary to guarantee DP for the aggregated model update without using secure aggregation. Therefore, the common model is less accurate than with our scheme (aka. FL-TOP-DP and defined in Section 5.4.1). In addition, [START_REF] Liu | FedSel: Federated SGD Under Local Differential Privacy with Top-k Dimension Selection[END_REF] uses two epsilon budgets; one for selecting Top-K parameters per client, and the second for perturbing these selected Top-K parameters. By contrast, in FL-TOP-DP, we select the Top-K parameters via public data without sacrificing any privacy budget. Finally, their solution is also less bandwidth efficient than ours: as the Top-K parameters differ for each client and at each round, the client cannot send only the Top-K parameters values because the server will not be able to identify which value corresponds to which Top-K parameter. For this reason, the client has to send a sparse vector with only Top-K perturbed values and all remaining parameters set to 0. Therefore, the quantization of the non-Top-K parameters is performed only during the upstream (from client to server) without compressing any downstream traffic. As opposed to this, in our solution, only the weights/updates of the Top-K parameters are transferred downstream/upstream.

In [START_REF] Jin | Stochastic-Sign SGD for Federated Learning with Theoretical Guarantees[END_REF], a private extension of SignSGD protocol defined in [START_REF] Bernstein | signSGD: Compressed Optimisation for Non-Convex Problems[END_REF] was proposed. The authors used local DP to guarantee client-level-DP. Their proposal is more bandwidth efficient than our private protocol called FL-SIGN-DP and presented in Section 5.2 as they send only one bit per parameter, however, it is widely accepted that the large perturbation provided by local DP degrades accuracy: the aggregation of the DP updates increases the noise variance. Our private proposals add noise in a distributed manner such that the final noise after the aggregation corresponds to the minimum noise needed to ensure DP. This is made thanks to a secure aggregation protocol. Regarding the Byzantine resilience of their protocol, only the attack where each adversary sends the opposite sign of its gradients is considered while we consider the gradient ascent and the random update attacks. Furthermore, we consider backdoor attacks, and more powerful adversaries which collude by sharing their data and agree on the same poisoning updates.

In [START_REF] Naseri | Toward Robustness and Privacy in Federated Learning: Experimenting with Local and Central Differential Privacy[END_REF], the authors show how DP variants (Local or Central DP) defend against backdoor attacks. However, the adversaries in this approach either faithfully follows the DP protocol and do not deviate from it (under Local DP settings) or in case of Central DP the server is trusted and it takes care of adding the noise. In our case, we make the opposite observations if the adversaries decide to send their non-noisy, boosted and polluted updates.

Compressive Sensing (CS) [Don06; CT06; CRT06; JV10] was used with DP in [START_REF] Li | Compressive Mechanism: Utilizing Sparse Representation in Differential Privacy[END_REF]. The authors show that the amount of noise is reduced from

O( √ n) to O(log(n))
, when the noise is added on the sampled coefficients instead of the original database.

Cronus uses adversarial regularization techniques [START_REF] Nasr | Machine learning with membership privacy using adversarial regularization[END_REF] to be more robust against active and passive membership attacks. However, using local DP to have a theoretical privacy-preserving guarantee degrades the model accuracy of the global model such that each single participant's model (without collaboration) is more accurate.

The authors in [START_REF] Mo | PPFL: Privacy-Preserving Federated Learning with Trusted Execution Environments[END_REF] proposed to use hardware-based Trusted Execution Environments (TEEs) in Federated Learning settings. Indeed, TEEs allow to securely store data and execute code on an untrusted device. This proposed approach is an alternative to solutions which incur significant computational overhead as it is the case when we use multi-party computation or fully homomorphic encryption [START_REF] Naehrig | Can Homomorphic Encryption Be Practical?[END_REF]20]. However, even if the results are promising it still introduces increase in 15% CPU time, 18% memory usage and 21% energy consumption overhead in the client-side. Moreover, creating large TEEs is considered to be a bad practice as it has proven to significantly increase the attack surface. Therefore, the TEE size must be as small as possible. As a consequence, deep neural networks, which have generally large size, cannot be trained. As a solution, the author proposed to train each layer or block of a layer one after the other based via greedy layer-wise training [BLPL07; LBLL09]. In [START_REF] Yu | Salvaging federated learning by local adaptation[END_REF] authors decided to investigate the utility of being a participant during the federated learning process. As a result, the authors have shown that some participants have local models which are more accurate on their data than the global model. Moreover, the use of robust aggregation or differential privacy increases this gap. Finally, they evaluate three well-known techniques: fine-tuning, multi-task learning, and knowledge distillation for local adaptation of federated models. Therefore, the local adapation of federated models yields to outperform all local models.

Bandwidth Efficient Machine Learning

Different quantization methods have been proposed to save the bandwidth and reduce the communication costs in federated learning. They can be divided into two main groups: unbiased and biased methods. The unbiased approximation techniques use probabilistic quantization schemes to compress the stochastic gradient and attempt to approximate the true gradient value as much as possible [AGLTV17; Wen+17; Wan+18; Kon+16]. However, biased approximations of the stochastic gradient can still guarantee convergence both in theory and practice [BWAA18; LHMWD18; SFDLY14]. SignSGD [START_REF] Bernstein | signSGD: Compressed Optimisation for Non-Convex Problems[END_REF] protocol uses quantization to reduce the number of required bits per weight/update value during downstream and upstream exchanges between the server and the clients but requires the use of all the clients at each round which is not realistic in the context of federated settings because each client is available only during few rounds [START_REF] Kairouz | Advances and open problems in federated learning[END_REF].

A different line of works exploit the sparsity of model updates to compress model updates. Our work presented in Section 4.1.4 belongs to this line. The authors in [START_REF] Mamaghanian | Compressed sensing for real-time energy-efficient ECG compression on wireless body sensor nodes[END_REF] use CS for lowcomplexity energy-efficient ECG compression. Although compressed sensing was primarily designed for compression [START_REF] Emmanuel | Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] David | Compressed sensing[END_REF], it can be used for the purpose of denoising [START_REF] Christopher A Metzler | From denoising to compressed sensing[END_REF][START_REF] Tavakoli | Image denoising based on compressed sensing[END_REF]. In [START_REF] Yu | A compressed sensing based AI learning paradigm for crude oil price forecasting[END_REF], compressed sensing based denoising and certain artificial intelligence are combined to improve the prediction performance.

Similarly to our solutions presented in Section 4.1.4, authors in [AG19; AG20] proposed to use compressive sensing for federated learning in order to compress model updates. However, their solutions are non-private and assume that all clients participate in each round (as they maintain an error accumulation vector at each client due to the compression scheme), but as discussed in [START_REF] Kairouz | Advances and open problems in federated learning[END_REF] this assumption is not always realistic. Recently in [START_REF] Jeon | A Compressive Sensing Approach for Federated Learning Over Massive MIMO Communication Systems[END_REF] another compressive sensing algorithm was proposed for denoising purpose in federated learning context, where the added noise is due to the network transmission.

Sketching was adapted to federated learning for the purpose of compressing model updates in [START_REF] Ivkin | Communicationefficient distributed sgd with sketching[END_REF]. The authors proposed to use Count-Sketch [START_REF] Charikar | Finding frequent items in data streams[END_REF] to retrieve the largest weights in the update vector on the server side. After that, the server uses two additional communication rounds to inform the clients about what gradient values they need to send back to the server. The server then takes the average of the received gradients and zeros-out the others before updating the model. The error due to the compression is maintained at each client, and the participation of all clients are required in each round which, as per [START_REF] Kairouz | Advances and open problems in federated learning[END_REF] and as discussed above, is not practical to federated learning. In [START_REF] Rothchild | FetchSGD: Communication-Efficient Federated Learning with Sketching[END_REF], the aforementioned scheme is improved further by directly retrieving the most updated gradient values without asking for their positions in the update vector. This makes the scheme more efficient as it needs fewer communication rounds. Similarly to our approach called FL-CS and presented in Section 4.1.4, the error vector is also maintained on the server side instead of the client side, which is clearly a better fit for federated learning.

Constraining the weights to have a specific distribution has already been studied. In [START_REF] Han | DSD: Dense-Sparse-Dense Training for Deep Neural Networks[END_REF], for example, the authors use pruning techniques to create a sparse model at the end of the training. After each SGD iteration, the authors zero-out all the weights with an absolute value smaller than a threshold. Iterating the process leads to a sparse model with only some absolute weight values larger than 0. Similarly, [START_REF] Courbariaux | Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1[END_REF] aim to create a model with binary weights such that at the end of the training all the weights are close to 1 or -1. After each SGD update, the authors take the sign of the weights before the next update. After some iterations, the weight values become close to the interval limits -1 and 1.

In [START_REF] Frankle | The Lottery Ticket Hypothesis: Training Pruned Neural Networks[END_REF], a new hypothesis claims that we can extract a sub-neural networks from a model which, if trained, can achieve similar performance. To find such a sub-network, one has to follow a simple iterative procedure: train the complete network, prune the smallest weights, and then reinitialize the remaining weights to their original values. These steps are repeated iteratively. This approach was extended to federated learning in [START_REF] Li | LotteryFL: Personalized and Communication-Efficient Federated Learning with Lottery Ticket Hypothesis on Non-IID Datasets[END_REF].

Machine Learning and Security

In this section, we focus on the poisoning attacks against Federated learning as it is the most studied attacks in federated context. We also investigate the potential defenses against such attacks in literature.

Poisoning Attacks

During the training, the poisoning attacks can be performed on the model (model poisoning) [START_REF] Blanchard | Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent[END_REF][START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF] or on the data (data poisoning) [BNL12; Rub+09; MZ15; Xia+15; KL17; CLLLS17; Jag+18; STS16 ;[START_REF] Fung | Mitigating sybils in federated learning poisoning[END_REF]. In what follows, we will first describe the difference between Model Poisoning and Data Poisoning and therefore we explain the goal behind such attacks (targeted/untargeted).

Model Poisoning vs Data Poisoning

With data poisoning attacks only the data are modified by the adversary while the learning process remains unchanged [START_REF] Tolpegin | Data poisoning attacks against federated learning systems[END_REF]. By contrast, the adversary in model poisoning attacks, modifies its learning process instead of its data to generate adversarial updates. However, both can be combined to reach the adversarial objective [BCMC19; BVHES18]. Although both are effective, data poisoning is much more practical than model poisoning and it requires much less expertise from the adversary [START_REF] Tolpegin | Data poisoning attacks against federated learning systems[END_REF].

Data poisoning attacks largely fall in two categories: clean-label[Sha+18; Muñ+17; KL17] and dirty-label [GDG17; CLLLS17; Liu+18]. The first one assumes that the adversary cannot change the label of any training data due to a process which certifies that data are belonging to the correct class and the poisoning of data samples has to be imperceptible. In contrast, with dirty-label attacks the adversary can modify the labels of some training data samples to miss-classify them to the desired targeted label in order to generalize this behavior on the testing data. Dirty-labels attacks includes backdoor attacks which are performed during the training phase either by label-flipping attack which modifies the label of a specific class to targeted class's label, or by modifying specific features of some samples to insert a timestamp or a trigger before to change their labels to desired class's label as with label-flipping. After that if the trigger is available on some testing data then the model will behave according to the adversary's target by predicting the targeted class. Note, that in comparison with the phenomenon of adversarial examples [CW17; Sze+13] which aims to modify only the inputs of the testing data to carry out a miss-classification, with dirty-label we aim at modifying the testing data according to the training data. So, we insert for example a trigger in the testing data only because it was present in the training data.

Targeted vs Untargeted poisoning attacks

The poisoning attack can be either targeted where the goal of the adversary is to cause the misclassification of specific class in the global model while maintaining a good accuracy on the nontargeted classes (Backdoors attacks [BCMC19; BVHES18]); or untargeted where it aims to decrease the accuracy of the global model without distinction between the classes [HJNRT11; LYY20; BEGS17]. The first backdoor attack designed for a federated learning environment was proposed in [START_REF] Bagdasaryan | How To Backdoor Federated Learning[END_REF]. Here, the adversary scales up its update in order to surpass the contributions of other honest participants after aggregation. The goal of the attack is to alter the common model so that it exhibits some adversarial behaviour (e.g., targeted misclassification). However, these attacks are effective only in later rounds, when the global model has converged. Indeed, the attack exploits the fact that when the global model has converged, the updates of other honest clients will be smaller and then are more easier to surpass. In contrast, the adversary in [START_REF] Arjun | Analyzing federated learning through an adversarial lens[END_REF] boosts its update enough to surpass the contributions of honest clients from the very first rounds even when the global model has not converged. The papers [START_REF] Arjun | Analyzing federated learning through an adversarial lens[END_REF][START_REF] Bagdasaryan | How To Backdoor Federated Learning[END_REF] show how to bypass detection and carry out a stealthy model poisoning. Indeed, in [START_REF] Bagdasaryan | How To Backdoor Federated Learning[END_REF] the adversary adds a specific term to the loss function such that it can optimize the model for the backdoor task while it remains close enough from the non-backdoor model to avoid detection. In [START_REF] Arjun | Analyzing federated learning through an adversarial lens[END_REF], an additional term is added to ensure the minimum degradation on the accuracy of the global model in order to evade accuracy-based detection. Moreover, the authors alternate between the minimization of the stealth and the adversarial loss which separates one from the other for a finer control over relative effect of the two objectives. The authors claim that the alternating minimization strategy increases the targeted objective while it increases the ability of the attacker to evade detection.

The resilience of distributed implementations of Stochastic Gradient Descent (SGD) against Byzantine failures is studied in [START_REF] Blanchard | Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent[END_REF]. Each Byzantine worker (among a set of workers) sends a random vector drawn from a Gaussian distribution. The results show that only a single Byzantine worker can prevent the traditional federated schemes such as FL-STD from converging. Note that this attack can be adapted to SignSGD scheme, where an adversary sends the sign of the random value instead [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF].

Although label flipping is often used as targeted class to insert a backdoor [BCMC19; TTGL20], however, it can also be used as untargeted attack if the adversary decide to flip all the labels of her local training data randomly and without distinction between classes [Jag+18; Muñ+17].

In Table 3.1 we classify the studied poisoning attacks used in our Security Analysis in Chapter 6.1.

Defenses

KRUM a Byzantine-resilient algorithm is proposed in [START_REF] Blanchard | Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent[END_REF] as an aggregation rule to select one honest update per round in an adversarial environment. In [START_REF] Yin | Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates[END_REF] two distributed gradient descent algorithms were proposed: the first one is based on the simple coordinate-wise median operation while the second is based on the coordinate-wise trimmed mean operation where for each coordinate, only participants with value smaller or larger than a constant are taken into account to compute the mean value. The original version of the trimmed mean operation for collaborative learning was introduced in [START_REF] El | The Hidden Vulnerability of Distributed Learning in Byzantium[END_REF] where the author introduced a hybrid aggregation rule called Bulyan which combines both KRUM and the trimmed mean operations to be more efficient. Another version of the trimmed mean is presented in [START_REF] Xie | Generalized byzantine-tolerant sgd[END_REF]. In [START_REF] Fung | Mitigating sybils in federated learning poisoning[END_REF], a solution was proposed to defend against backdoors in federated learning. Same, paper [START_REF] Tolpegin | Data poisoning attacks against federated learning systems[END_REF] proposes a clustering-based solution to detect malicious participants and then to defend against backdoor attacks (Label Flipping). Indeed, the insight behind this solution is that the updates of malicious and honest participants are distinguishable. Therefore, by using PCA clustering on the weights of the last layer's nodes, the server can separate the two groups of participants. Neural Cleanse [START_REF] Wang | Neural cleanse: Identifying and mitigating backdoor attacks in neural networks[END_REF] is a technique which aims at detecting and removing backdoors in deep neural networks. This technique assumes that the clusters of the source and target classes are close in the representation space under backdoor attacks. [START_REF] Shen | Auror: Defending against poisoning attacks in collaborative deep learning systems[END_REF] demonstrates how to circumvent backdoor attacks on distributed learning by using a variant of Trimmed Mean which is based on K-mean clustering. In [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF], the authors study the robustness and the tolerance of signSGD/SIGNUM [START_REF] Bernstein | signSGD: Compressed Optimisation for Non-Convex Problems[END_REF] with majority vote against network faults and adversarial clients, where SIGNUM is the momentum equivalent of signSGD (i.e., each client maintains a momentum and transmits the sign momentum to the server at each iteration). In [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF], the authors show that signSGD is robust against sign inversion attack, when each malicious client inverts the sign of the computed gradient. The authors argue that this is the best possible attack in a non-adaptive setting (i.e., when the adversary performs the attack independently of the gradients it computed). In Section 6, we experimentally show that FL-SIGN is also robust against other adaptive attacks like various backdoor attacks [START_REF] Arjun | Analyzing federated learning through an adversarial lens[END_REF]. Multiplicative weight update (MWU) technique [AHK12; FS97; PST95; Li+14; GK07] defines a set of weighted aggregation rules which are robust against poisoning attacks. The intuition behind MWU-based aggregations is to reduce the impact of malicious participants on the weighted aggregated update by reducing their weights. Finally, Cronus [CSSH19] is a robust defense scheme against poisoning attacks. The scheme use knowledge transfer through distillation between the server and different parties. This implies that the only information shared between them is their prediction on a public dataset. Moreover, the server replace the naive aggregation rules commonly used in federated learning scheme (mean, averaged mean) with the robust mean estimation proposed in [START_REF] Diakonikolas | Being Robust (in High Dimensions) Can Be Practical[END_REF]. Cronus outperforms most of the aforementioned defense schemes such as Median [START_REF] Yin | Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates[END_REF], Bulyan [START_REF] El | The Hidden Vulnerability of Distributed Learning in Byzantium[END_REF], Krum [START_REF] Blanchard | Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent[END_REF], MWU with mean aggregation and MWU with optimization [START_REF] Li | Resolving conflicts in heterogeneous data by truth discovery and source reliability estimation[END_REF].

How effective are they?

Although different defenses were proposed to detect or cancel-out such attacks, however, recent works show that an adversary is able to bypass and evade numerous of them. Indeed, [START_REF] Baruch | A Little Is Enough: Circumventing Defenses For Distributed Learning[END_REF] shows that by carefully crafting the byzantine values, an adversary which controls some participants can defeat most of the state-of-the-art defenses including: Krum, Trimmed Mean and Bulyan. Two attacks was proposed: the first one aims to prevent the convergence while the second aims to backdoor the model. Moreover, the paper clearly shows that the assumption which is made by most existing defenses for distributed learning [BEGS17; EGR18; XKG18; YCKB18] that if each value from the adversary update is upper-bounded by the variance of the honest workers' values then the attack fails, is not correct. Indeed, even by choosing those values from that range, it is possible to succeed in the attack. In fact, those defenses use statistical methods to remove all the updates with large changes to prevent the attacks. Similarly, the solution proposed in [START_REF] Shen | Auror: Defending against poisoning attacks in collaborative deep learning systems[END_REF] to circumvent backdoor attacks on distributed learning was successfully evades it by the backdoor attack introduced in [START_REF] Baruch | A Little Is Enough: Circumventing Defenses For Distributed Learning[END_REF]. Note also, that the KRUM and the coordinate-wise median protocols are not effective against the backdoor attack used in [START_REF] Arjun | Analyzing federated learning through an adversarial lens[END_REF].

Finally, except for signSGD, all the other defenses aforementioned assume to have access to each individual update in order to remove measure and perform the statistics-based methods to remove potential adversaries. Therefore, secure aggregation can not be used as it allows to access only to the aggregation while each individual update is encrypted.

Part II Contributions

Toward Bandwidth Efficient Federated Learning Schemes

Federated Learning is bandwidth hungry and not adapted to applications that use limited bandwidth devices, such as IoT devices. Indeed, it is generally used to train deep neural networks with millions of parameters and each parameter is encoded on 32 bits. Also, it requires more than one round to converge. Moreover, the communication exchanges between the server and the clients in both directions (upstream and downstream), increase drastically the energy consumption. Therefore, Federated Learning is not practical for applications which are based on energy-constrained devices.

To make it more practical, it is useful to study and propose some federated schemes which are adapted to energy and bandwidth-constrained devices.

To address this issue, we studied two approaches namely update compression and model compression, and proposed three bandwidth efficient schemes:

• FL-SIGN is a scheme based on biased quantization of the updates and enables to reduce the number of bits per weight's update from 32 bits to 1 bit.

• FL-CS for its part relies on the compressive sensing theory which enables to reconstruct a complete sparse data (ie,. image or signal) from few sampled points in it. Analogously, starting by some points sampled from the update, FL-CS leverages its sparsity in order to reconstruct it accurately. Therefore, the model's update is compressed by up to 95%.

• FL-TOP harnesses the ability of the model to converge and reach good accuracy under constraint. Indeed, in FL-TOP only some weights are updated while keeping all the remaining ones constant. As a result, only the few updated weights have to be exchanged between the server and the clients. FL-TOP enables to reduce the model size up to 99.9% in both downstream and upstream directions which makes it particularly adapted to applications based on energy-constrained devices as it is the case for mobile systems.

All the proposed solutions obtained similar accuracy to the standard Federated Learning scheme in spite of their bandwidth efficiency.

Reducing Bandwidth by Compressing the updates

Update compression consists in compressing the size of the updates that are sent by the participants to the server. We proposed two "update compression" solutions, namely FL-SIGN and FL-CS.

FL-SIGN: Bandwidth-Efficient Federated Learning via Quantization

The FL-SIGN Protocol Algorithm 3: FL-SIGN: Sign Federated Learning

12 w k t = SGD(D k , w k t-1 , T gd ) Output: Model update sign(w k t -w k t-1 )
We propose to reduce the bandwidth costs by quantizing the model weights as in [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF]. More specifically, in the new scheme, referred to as FL-SIGN in the rest of this dissertation, each client sends only the sign of every coordinate value in its parameter update vector. The server takes the sign of the sum of signs per coordinate and scales down the result with a fixed constant γ (which is in the order of 10 -3 in practice) in order to limit the contribution of each client and adjust convergence. This scaled aggregated updates are added to the global model.

More specifically, FL-SIGN (see Alg. 3) differs from the standard federated scheme FL-STD (see Alg. 1) as follows:

1. Each client returns s k t = sign(ww k t-1 ) instead of (ww k t-1 ), where sign : R n → {-1, 1} n returns the sign of each coordinate value of the input vector if it is non-zero and a sign chosen uniformly at random otherwise.

2. The server sums the sign vectors s k t sent by each client k and computes the sign vector of this sum as sign k s k t . This is equivalent to take the median of all clients' signs at every position of the update vectors. Unlike in Alg. 1, the update s k t is not weighted with client k's data size |D k |, since that would require the client to send |D k | to the server which would enable the adversary to maliciously scale up its sign vector by sending a fabricated size of its training data.

The extreme quantization performed by FL-SIGN reduces the communication costs of federated learning by a factor of 32 (since only one bit is sent per parameter instead of 32 bits), and also, as we will demonstrate later (in Chapter 6), improves its robustness against different attacks aiming to maliciously manipulate the common model through the updates. Note also that, if the quantized update vector is sparse, other compression techniques can further improve communication efficiency [START_REF] Jakub Konecný | Federated Learning: Strategies for Improving Communication Efficiency[END_REF].

In signSGD [START_REF] Bernstein | signSGD: Compressed Optimisation for Non-Convex Problems[END_REF], all the clients calculate the stochastic gradient based on a single mini-batch and then send the sign vector of this gradient to the server. The server calculates the aggregated sign vector by taking the median (majority vote) and sends the signs of the aggregated signs back to each client.

The main differences between our scheme (FL-SIGN) and signSGD are as follows:

• FL-SIGN aims to train a common model that is distributed to a random subset of all clients in every round. However, in signSGD, all clients start with the same initialized common model and the server sends the same aggregated model update to every client at each round. Selecting only a random subset of clients in each round has at least three benefits. First, FL-SIGN becomes more robust against temporary node failures. Second, FL-SIGN reduces the communication costs upstream to the server. Finally, sampling boosts privacy due to the uncertainty that a specific user's or client's data is used for training or not.

• In FL-SIGN, each client can perform multiple SGD iterations locally using multiple mini-batches before computing the model update. On the contrary, signSGD always performs one local SGD iteration with a single mini-batch at every client.

• As all the clients participate at each round in signSGD, the server only transfers the sign of the aggregated signs to the clients in every round. Therefore, only a single bit is transferred per parameter downstream to the clients. In FL-SIGN, the whole model is transferred but only to a random subset of clients.

Experimental Set-up

This section describes the experimental set-up that are used to evaluate the accuracy, security and privacy of our proposals in the rest of the paper. The following datasets were used: MNIST, Fashion-MNIST, IMDB, LFW and CIFAR which is augmented from 50,000 images to 500,000 (See Appendix 8.3 for more details)

The description of the datasets and model architectures can be found in Section 8.3 of the Appendix. For FL-SIGN, γ, the learning rate, was set to 0.001 for all datasets1 . N , the total number of participant clients, was set to 1000. C, the percentage of selected clients at each round, was set to 0.1. |D k | is the training data size of client k. |B|, the batch size, was set to 50 with CIFAR dataset, 25 with IMDB, 10 for MNIST and Fashion-MNIST datasets. T gd , the local gradient descent iterations per round and per client, was set to 30, 30, 5 and 50 for MNIST, Fashion-MNIST, IMDB and CIFAR, respectively. T cl , the number of rounds, was set to 100 for the MNIST, Fashion-MNIST, IMDB datasets, and 400 for CIFAR. We use two optimizers: the stochastic gradient descent (SGD) [START_REF] Chollet | Keras optimizers[END_REF] with a learning rate (η) set to 0.215 and the adaptive moment estimation (Adam) [START_REF] Diederik | Adam: A Method for Stochastic Optimization[END_REF] [Cho+15d] with a learning rate set to 0.001. Table 8.1 summarizes the different parameter values that were used for the different datasets.

Performance Evaluation

In this section, we compare the performance of FL-SIGN and FL-STD using the same configuration. The global model accuracy of FL-STD and FL-SIGN on the CIFAR, MNIST, Fashion-MNIST, IMDB datasets are compared in Table 4.1. The bandwidth consumption is calculated by measuring the average number of bits sent by a client to the server. This is computed as (C× round × n) for FL-SIGN, and (32 × C× round × n) for FL-STD, where n is the model's size and round represents the round when we get the best accuracy over T cl rounds. Similarly, we present the best accuracy over T cl rounds.

The results show that the accuracy performance of both schemes over the five datasets are very similar despite the severe parameter quantization. Indeed, the difference between FL-STD and FL-SIGN in terms of accuracy is between 0.01 and 0.03. However, FL-SIGN is much more bandwidth efficient and consumes up to 59 times less bandwidth than FL-STD.

Dataset

w k t = SGD(D k , w k t-1 , T gd ) 18 ∆w k t = w k t -w k t-1 Output: Model update C(∆w k t , m)
CS assumes the sparsity of the reconstructed signal in a specific basis domain Ψ as explained in Section 2.3. We assume the model update (as a signal) to be already sparse in the time domain, that is, Ψ is canonical sparsity basis (i.e., Ψ = I), and therefore, the compression operator is C(∆w, m) = Φ∆w, where Φ is composed of the first m rows of the matrix of the Discrete Cosine Transform (DCT) [START_REF] Ahmed | Discrete cosine transform[END_REF][START_REF] Nasir | How I came up with the discrete cosine transform[END_REF]. Indeed, due to the large energy compaction property of DCT, the first coefficients, which correspond to the low frequency components of ∆w, tend to have the largest magnitude and hence convey the most information about the model update [START_REF] Rao | Discrete cosine transform: algorithms, advantages, applications[END_REF]. In fact, for a canonical sparsity basis Ψ = I, Θ = Φ is RIP with overwhelming probability as soon as

m = O(U ln 4 n) if ∆w is U -sparse [CT06]
. Therefore, reconstruction is possible according to Theorem 1.

The decompression operator D is defined Eq. (2.4). Note that the compression operator can be computed in O(n ln n) with FFT and the decompression (or reconstruction) operator is implemented with the OWL-QN algorithm [START_REF] Andrew | Scalable training of L 1-regularized log-linear models[END_REF] which makes our approach reasonably fast in practice. FL-CS is described in Alg. 4. A client first computes its update ∆w k t with SGD, and then transfers the compressed update C(∆w k t , m), which consists of the first m DCT coefficients of the update (Line 18). The server takes the average of the client's updates (Line 8), updates the momentum (Line 9), and computes the error et (Line 10-12) due to compression following the error propagation technique described in Section 2.3.1. This error is accumulated over all federated rounds and added to the model (Line 13) to compensate its negative effect on convergence. The server uses OWL-QN [AG07; Tay20] to reconstruct the error-compensated aggregated model update st ∈ R n . Finally, the server updates the global model as wt = wt-1 + st before re-distributing the updated model to a new set of clients K.

Notice that the error et, the averaged model update yt, as well as the momentum are maintained in the compressed domain and have a size of m instead of n. Moreover, all of them are maintained at the server side instead of at each client side. This is possible due to the linearity of the compression scheme which is detailed in Section 2.3.

Scalable Reconstruction:

Although OWL-QN is reasonably fast in practice, its computational overhead may not be tolerated with very large models. A scalable reconstruction is proposed as follows. On the client side, the update vector ∆wt is shuffled and then splitted into P equally-sized chunks. Then, the compression operator C is applied on each individual chunk. Finally, the compressed chunks are transferred to the server. On the server side, each chunk is reconstructed independently using OWL-QN. The decompressed chunks are concatenated, and the resulted vector with size n is reshuffled to obtain st by inverting the client-side shuffling.

Shuffling is performed by each client identically which guarantees that the compressed chunks can still be aggregated by the server. In practice, this can be implemented by sharing a common random seed among all participants to initialize the shuffler. As the server also knows this seed, it can invert this shuffling and reconstruct the aggregated model updates. Note that shuffling is also performed identically over all the rounds to maintain the error.

Notice that, instead of reconstructing the complete update vector at once, the server performs reconstruction on smaller chunks which makes decompression faster. In addition, shuffling guarantees that the sparsity of the chunks is proportional to the sparsity of the whole update vector (i.e., if the update vector is U -sparse then all its chunks are U/P -sparse). Hence, the same compression operator C(•, m/P ) can be applied on every chunk without increasing the compression ratio (i.e., the compressed update still has a size of m). Moreover, each chunk can be reconstructed independently in parallel which can significantly speed up decompression.

Experimental Set-up

This section describes the experimental set-up that are used to evaluate the accuracy of our proposal. We used the Fashion-MNIST and the Medical dataset and their respective models described in Section 8.3.

For both datasets, we tune η from 0.01 to 0.5 with an increment value of 0.005. As in [START_REF] Ivkin | Communicationefficient distributed sgd with sketching[END_REF], we fix the momentum parameter ρ to 0.9 and we tuned the global learning rate ηG from 0.05 to 2.0 with an increment value of 0.05. The number of chunks used is P = 200. The hyperparameters used by each of the considered schemes are summarized in Table 8.4 and Table 8.5 in the Appendix for Fashion-MNIST and the medical dataset, respectively.

We aim at evaluating the performance of FL-CS with different levels of compression and comparing them with the performance of the following learning protocols:

• FL-STD: It is described in Section 2.1 (see Alg. 1).

• SignSGD: It is descibed in Section 4.1.1.

• FL-RND: This baseline follows the algorithm of FL-STD except that a random subset of the update vector with size m ≤ n is sent to the server instead of the complete update of size n. Each client selects the same random subset of coordinates from the update vector, but a different subset in every round. The server then averages the received updates before updating only the corresponding m weights. Note that if m = n, FL-RND is equivalent to FL-STD (see Alg. 5).

• FL-FREQ: In this baseline, a client transforms the model update to the frequency domain by using DCT [ANR74; Ahm91], and then the first m coefficients (low frequency components) are extracted and sent to the server as in FL-CS. However, as opposed to FL-CS, the server reconstructs the aggregated update vector by applying the inverse DCT on the aggregated compressed vectors where the last n -m coefficients are zeroed out (see Alg. 6). This baseline corresponds to a low-pass filter applied on the update vector. Φ in Alg. 6 is composed of the first m rows of the matrix of the DCT.

Performance Evaluation

Table 4.2 represents the best accuracy over 200 rounds for each scheme on the Fashion-Mnist dataset. Round corresponds to the round when the best accuracy is reached and Cost is the average bandwidth consumption calculated as: r × n × 32 × Round × C, where 32 is the number of bits necessary to represent a float value, n is the uncompressed model size, r = m n , m is the compressed model size, C is the sampling probability of a client, and Round is the round when we get the the best accuracy.

Table 4.3 represents the best balanced accuracy over 100 rounds for each scheme on the Medical dataset. AUROC (area under the receiver operating characteristic curve [START_REF] Narkhede | Understanding AUC -ROC Curve[END_REF]) corresponds to the AUROC value when the best balanced accuracy is reached, round is also the round when we get the best balanced accuracy, and finally, Cost is the average bandwidth consumption calculated as for the Fashion-MNIST dataset described above. Without DP, notice that our FL-CS scheme outperforms FL-RND and FL-FREQ whatever the considered compression ratio or the dataset are. Also, compared to FL-STD, our scheme started to reach the same accuracy from a compression ratio r being equal or greater than 0.1 for both datasets, although the differences between FL-CS and FL-STD for a compression ratio of 0.05 are only of 6%2 and 1%3 for the Fashion-Mnist and the medical datasets, respectively. However, FL-STD consumes much more bandwidth than FL-CS. Indeed, FL-CS reduces the bandwidth cost by 95% compared to FL-STD with a compression ratio of 0.05 for both datasets, while the bandwidth cost is reduced to 80% and 85% with a compression ratio of 0.2 for Fashion-MNIST and the medical data, respectively.

17 w k t = SGD(D k , w k t-1 , T gd ) 18 ∆w k t = w k t -w k t-1 19 Generates a random set G = {x ∈ {1, •
SignSGD for its part, also reaches similar accuracy than FL-STD. The bandwidth cost, SignSGD consumes less bandwidth than FL-STD with the Medical dataset as it reaches the best accuracy earlier than FL-STD. However, for the Fashion-MNIST dataset, FL-STD is more bandwidth efficient than SignSGD. It can be explained by the fact that only a small proportion of available clients are selected at each round in FL-STD, while in SignSGD all the clients are selected at each round. Notice, that our bandwidth efficient schemes outperform SignSGD in term of bandwidth efficiency irrespective of the considered dataset.

Reducing Bandwidth by Compressing the Model

Model compression consists in compressing the size of the model in order to reduce the number of element in the update vectors. We developed a scheme, called FL-TOP, that harnesses the ability of the model to converge and reach good accuracy under constraint.

FL-TOP: Bandwidth-Efficient Federated Learning via Constraint

In the standard federated learning scheme (FL-STD, in Section 2.1), the server sends the latest updated model to a randomly selected set of clients (downstream), and each client sends back its complete model update after local training to the server (upstream) at each round. Knowing that a model has on average millions of parameters (each is a floating point value represented on 32 bits), the network can suffer from large traffic both upstream and downstream.

Our solution, called FL-TOP, aims to reduce the large amount of network traffic by reducing both downstream and upstream traffic. In what follows, we describe the non-private scheme FL-TOP. 14

w k t = SGD(D k , w k t-1 , T gd ) 15 ∆w k t = w k t -w k t-

FL-TOP: Federated Pruning for Compression

FL-TOP is inspired by the pruning techniques proposed in [START_REF] Han | DSD: Dense-Sparse-Dense Training for Deep Neural Networks[END_REF] (see Section 3.2 in the Related Work for more details), and it aims to reduce the amount of parameters exchanged downstream (from the server to the participating entities) and upstream (from the participating entities to the server). In our scheme, each client updates only a small subset, Top-K, of the model parameters (weights) at each round. Only the K weight values of these Top-K parameters are updated during training, and neither the clients nor the server need to transfer the values of the remaining n -K parameters, where n is the total number of parameters. The set of Top-K parameters do not change over the whole training and are identical for all clients. We experimentally show in Section 5.4.5 that, if these K parameters are chosen carefully, the performance penalty is negligible even if K = 0.005 • n, that is, 99.5% of the model parameters are pruned. Notice that unlike standard pruning techniques, where the set of pruned weights are re-selected after each SGD iteration [START_REF] Han | DSD: Dense-Sparse-Dense Training for Deep Neural Networks[END_REF], our scheme always updates the same K parameters. These Top-K parameters are selected by the server at the beginning of the protocol. More specifically, the server initializes the model and trains that with some public data that have a similar distribution as the clients' training data. After a few SGD iterations, the server selects the K parameters which values changed the most. FL-TOP is described in Alg. 7. First, the server uses public data to identify the set T of the Top-K parameters (K = |T|), before starting federated learning. In particular, starting from a public model w0, it accumulates the absolute value of gradients per parameter over Tinit SGD iterations, and selects the K parameters with the largest accumulated gradients. After that, the values/updates4 of these parameters are the only ones exchanged during the rest of the training between the server and the clients.

w k t-1 [i] = ŵk t-1 [j] 22 j = j + 1 23 end 24 w k t = Top k SGD(D k , w k t-1 , w 0 , T gd , T) Output: Model update C(w k t -w k t-1 , T) Algorithm
At each round, each selected client k uses the K updated weights ŵt-1 received from the server to create a new weight vector w k t-1 of size n, such that w k t-1 is composed from the compressed vector ŵk t-1 of size K ≤ n (with coordinates in T) and n -K weights from the initialization vector w0. w0 is identical for all participants and can be generated from a shared seed. Note that when K = |T| = n, the scheme is equivalent to FL-STD. The weight vector w k t-1 is used to train the client's model. However, only the weights in T are updated while the remaining ones are kept fixed. To do that, the weights not in T are reinitialized after each SGD iteration to w0. The server receives only the values from w k t -w k t-1 at coordinates T, denoted by C(w k t -w k t-1 ) for short, from every client k, and updates the common model wt with the average of these compressed updates (in Line 12).

Experimental Set-up

The goal of this section is to evaluate the performance of our proposed schemes FL-TOP on a benchmark dataset and a realistic in-hospital mortality prediction scenario. We aim at evaluating their performance with different levels of compression and comparing them with the performance of the following learning protocols5 :

• FL-STD: The Standard Federated Learning scheme as described in Section 2.1 (see Alg. 1).

• FL-BASIC: A Federated Learning scheme that updates a random subset of parameters instead of the Top-K parameters at each SGD iteration. This subset is re-selected at the beginning of each new round. The n -k non-selected parameters are still reinitialized after each SGD update as in FL-TOP.

• FL-CS: Our Federated Learning scheme that uses Compressive sensing (CS) to compress model updates from Section 4.1.4. See Section 2.3 for more details.

• FL-SIGN: Our sign-based Federated Learning scheme that uses quantization to compress model updates from Section 4.1.1.

Note that all compression operators in the baselines are linear, and hence they can also be used with secure aggregation.

We evaluate the above learning algorithms on the well-known Fashion-MNIST dataset and on the Premier Healthcare Database, described in Section 8.3.

Recall that the Top-K weights are selected before starting the federated learning process using public data. For Fashion-MNIST, we randomly select a batch with size 10 from MNIST dataset described in Section 8.3. For the medical dataset, we did not find any public dataset with the same features as ours, and for this reason, we selected randomly from the dataset a batch of 356 patients6 . This set is used only by the server and never by any client. Afterwards, the server performs Tinit SGD iterations starting from the model parameters w0 on the same batch to identify the Top-K weights. We experimentally show later that even these small batches are enough for the server to find a good set of Top-K weights.

More information about the hyper-parameter selection can be found in Tables 8.8,8.9, 8.10 in the Appendix. For FL-SIGN, γ is set to 0.001.

Performance Evaluation

Table 4.4 represents the best accuracy over 200 rounds for each scheme on the Fashion-MNIST dataset. Round corresponds to the round when the best accuracy is reached and Cost is the average bandwidth consumption calculated as: r × n × 32 × Round × C, where 32 is the number of bits necessary to represent a float value, n is the uncompressed model size, r = |T| n , |T| is the compressed model size, C is the sampling probability of a client, and Round is the round when we get the the best accuracy.

Table 4.5 represents the best balanced accuracy over 100 rounds for each scheme on the Medical dataset. AU ROC (area under the receiver operating characteristic curve -see Section 8.4.2 for more details) corresponds to the AU ROC value when the best balanced accuracy is reached.

These tables show that the proposed non-private scheme FL-TOP has similar accuracy than the standard scheme FL-STD but reduces the bandwidth cost significantly. For example, with the Fashion-MNIST dataset, the FL-TOP accuracy reaches 0.85 when the compression ratio r = 10%. In comparison, the standard FL-STD scheme reaches an accuracy of 0.86% but consumes 10 times more bandwidth. Furthermore, although FL-CS reaches the same accuracy than FL-TOP and consumes slightly less bandwidth upstream (9% less), its required downstream bandwidth is about 10 times larger (See Table 4.4 for more details). The results on the medical dataset are quite similar. In fact, FL-TOP achieves its best balanced accuracy (0.74) and AUROC (0.82) when r = 10% while the FL-STD scheme obtains similar performance but required about 11 times more upsteam and downstream bandwidth cost. FL-CS achieves similarly accuracy at r = 10% as FL-TOP but its downstream required bandwidth is about 11 times larger (see Table 4.5 for more details).

Although, FL-SIGN reaches the same accuracy (0.84) on Fashion-MNIST than FL-TOP (at r=0.5%) and with less upstream costs (38% less), however, its required downstream bandwidth is about 20 times more than FL-TOP. Similarly, on the medical dataset, FL-SIGN reaches the same accuracy compared to FL-TOP at r = 0.5% and with less downstream bandwidth but much more upstream bandwidth (see

Conclusion

In this Chapter, we have shown that it is possible to have bandwidth efficient Federated Learning solutions which are as accurate as the standard Federated Learning scheme (FL-STD). Indeed, we have proposed two approaches which compress either the updates or the model.

The approach of reducing bandwidth by compressing the updates includes two schemes: 1) FL-SIGN is based on quantization and is almost as accurate as FL-STD but incurs less communication overhead by reducing the number of bits per float value from 32 bits to 1 bit during upstream step (from the clients to the server); 2) FL-CS allows to reduce the upstream bandwidth cost by up to 95% by exploiting the sparsity of the model updates via Compressive Sensing theory.

The approach of reducing bandwidth by reducing the model includes one scheme called FL-TOP, which reduces both upstream and downstream bandwidth costs up to 99.9%. Therefore, it is particularly adapted to bandwidth and energy constrained applications as it is the case for mobile systems.

Designing Private and Bandwidth Efficient Federated Learning Schemes

Although Federated Learning improves privacy, model parameters can leak information about the training data. Indeed, [ZLH19; ZMB20; GBDM20] presented some attacks that allow an adversary to reconstruct pieces of the training data of some entities. [NSH19; MSDS19] define a membership attack that allows to infer if a particular record is included in the data of a specific entity. Similarly, [START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF] define an attack which aims at inferring if a subgroup of people with a specific property, like for instance the skin color or ethnicity, is included in the dataset of a particular participating entity. A solution to prevent these attacks and provide theoretical guarantees is to use a privacy model called Differential Privacy [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF].

We propose differentially private extensions of the three schemes proposed in Chapter 4, namely FL-SIGN-DP, FL-CS-DP and FL-TOP-DP. For each proposed scheme, we follow an approach where clients themselves add noise in a distributed manner so that the aggregated updates are sufficiently noised to have meaningful differential privacy. To this end, individual noisy updates are encrypted with a simple and efficient encryption scheme taken from [ÁC11].

• FL-SIGN-DP: In order to diminish the communication costs of our DP algorithm, we propose a novel discretized and distributed version of the Gaussian Mechanism. In particular, as opposed to the standard Gaussian Mechanism [14], the noise values come from a discretized domain and are tightly concentrated around its mean depending on the desired privacy guarantee . As a result, these values can be encoded with fewer bits than if they came from a continuous Gaussian distribution.

• FL-CS-DP reduces the added Gaussian noise by reducing the sensitivity of the model via compression. Indeed, it adds the noise only to the first coefficients of the discrete cosine transform of each update. Because of the large energy compaction property of DCT, the first coefficients, which correspond to the low frequency components of the update, tend to have the largest magnitude and hence convey most information about the model update. This leads to larger value-to-noise level and therefore better performance. Also, reconstructing the approximated gradients is an instance of Basis Pursuit Denoising (or LASSO), which can be solved with efficient solvers that provide large accuracy despite the added Gaussian noise. Finally, we show that FL-CS-DP produces more accurate and bandwidth efficient models than FL-STD-DP, that is, the differentially private variant of the vanilla Federated Learning protocol without any compression.

• FL-TOP-DP updates for its part only few weights during the whole training process while keeping the remaining ones constant (defined as a constraint). As a result, it reduces the sensitivity of the model. Moreover, we observed experimentally that the constraint leads to greater importance of the updated weights by increasing their values. This result is important when differential privacy is used as it leads to larger value-to-noise level and hence better performance.

Notice that the secure aggregation protocol can be used only with linear compression schemes such as the ones we propose.

Privacy Model

We consider an adversary, or a set of colluding adversaries, who can access any update vector sent by the server or any clients at each round of the protocol. A plausible adversary is a participating entity, i.e. a malicious client or server, that wants to infer the training data used by other participants. The adversary is passive (i.e., honest-but-curious), that is, it follows the learning protocol faithfully.

Different privacy requirements can be considered depending on what information the adversary aims to infer. In general, private information can be inferred about:

• any record (user) in any dataset of any client (record-level privacy),

• any client/party (client-level privacy).

To illustrate the above requirements, suppose that several banks build a common model to predict the creditworthiness of their customers. A bank certainly does not want other banks to learn the financial status of any of their customers (record privacy) and perhaps not even the average income of all their customers (client privacy).

Record-level privacy is a standard requirement used in the privacy literature and is usually weaker than client-level privacy. Indeed, client-level privacy requires to hide any information which is unique to a client including perhaps all its training data.

FL-SIGN-DP: Private and Bandwidth-Efficient Federated Learning via Quantization

In FL-SIGN, a participant only sends the signs of its updates, as opposed to their actual value, hence it intuitively reveals less information about the client's dataset than the original FL-STD scheme. In order to experimentally validate this intuition, we implemented the inference attack described in [START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF] on FL-STD and FL-SIGN1 . The results clearly validated our intuition (the attack accuracy dropped from 92% for FL-STD to 50% for FL-SIGN). Although these results are very promising and might confirm that privacy is preserved in practice, it does not provide any provable privacy-preserving guarantees. In order to obtain theoretically, backed and proven private schemes, we extend FL-SIGN with Differential Privacy. Our goal is to design differentially private schemes that are efficient in terms of accuracy and bandwidth (even for small ε values).

Operation

We aim at developing a solution that provides client-level privacy and is also bandwidth efficient. For example, in the scenario of collaborating banks, we aim at protecting any information that is unique to each single bank's training data. The adversary should not be able to learn from the received model or its updates whether any client's data is involved in the federated run (up to ε and δ). We believe that this adversarial model is reasonable in many practical applications when the confidential information spans over multiple samples in the training data of a single client (e.g., the presence of a group a samples, such as people from a certain race). Differential Privacy guarantees plausible deniability not only to any groups of samples of a client but also to any client in the federated run. Therefore, any negative privacy impact on a party (or its training samples) cannot be attributed to their involvement in the protocol run.

To guarantee differential privacy per client, every client should add enough noise to its update locally such that the server cannot learn any client-specific information from the noisy update. However, this approach (aka, local differential privacy [START_REF] Erlingsson | RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response[END_REF]) requires so much perturbation that it is impractical if the number of clients is limited. Instead, likewise [START_REF] Truex | A Hybrid Approach to Privacy-Preserving Federated Learning[END_REF], we follow a different approach where clients themselves add noise in a distributed manner so that the aggregated updates are sufficiently noised to have meaningful differential privacy. To this end, individual noisy updates are encrypted with a simple and efficient encryption scheme taken from [START_REF] Ács | I Have a DREAM! (DiffeRentially privatE smArt Metering)[END_REF][START_REF] Bonawitz | Practical Secure Aggregation for Federated Learning on User-Held Data[END_REF]. The purpose of this encryption is to prevent the adversary from accessing the individual (and weakly-noised) update per client but only their sum over all clients which is in turn sufficiently noised to guarantee DP for any client.

Specifically, each client k first computes the gradient update ∆w k t (in Line 12 of Alg. 9) and then takes the sign vector of this update. Then, a random noise share ρ k is added to the sign vector sign(∆w k t ) so that k∈K sign(∆w k t ) + ρ k satisfies differential privacy. A simple solution is that ρi ∼ G(0, √ nσI/ |K|), which means that k∈K sign(∆w k t ) + k∈K ρ k = k∈K sign(∆w k t ) + G(0, √ nIσ) as the sum of Gaussian random variables also follows Gaussian distribution 2 . Indeed, the variance of the Gaussian noise has to be proportional to the L2-sensitivity of the sign vector which is no more than √ n, where n is the number of parameters. However, recall that the adversary can access sign(∆w k t ) + ρ k , which means that, if |K| is too large, ρ k is likely to be small allowing the adversary to learn sign(∆w k t ) + ρ k very accurately. For this reason, each client k encrypts sign(∆w k t ) + ρ k and sends the encrypted result to the aggregator. After summing all the encrypted values, the server obtains k EncK k (sign( [START_REF] Bonawitz | Practical Secure Aggregation for Federated Learning on User-Held Data[END_REF] for details). Here, modulo is taken element-wise and m = 2 log 2 (max k ||1+ρ k ||∞|K|) . Therefore, the server can only access the aggregate which is sufficiently noised to guarantee differential privacy; any client-specific information that could be learnt from the noisy aggregate is quantified by the moments accountant described in Section 2.2. To make learning more resilient to perturbation, the server takes the sign of the sum of updates and scales the result with γ < 1 which is crucial to achieve convergence in practice especially if √ nσ is large. Unfortunately, the above simple approach is not bandwidth efficient; adding noise from the continuous domain requires each noisy update sign(∆w k t ) + ρ k to be encoded as a floating-point number 3 (represented by at least 32 bits on a commodity hardware) no matter that sign(∆w k t ) would need only 1 bit per coordinate. Therefore, the noisy update needs at least 32 times more data to be transferred from a client to the server than with FL-SIGN (in Alg. 3).

∆w k t ) + ρ k ) = k sign(∆w k t ) + G 0, √ nσI where EncK k (sign(∆w k t ) + ρ k ) = sign(∆w k t ) + ρ k + K k mod m and k K k = 0 (see [ÁC11;
To alleviate the above bandwidth problem, each client k generates a random integer from a discrete Gaussian distribution with mean sign(∆w k t ), encrypts this random integer, and sends the result for aggregation. Since the discrete Gaussian random variable has an integer value and is concentrated around its mean, its value can be encoded with fewer bits than a floating-point number. The new learning algorithm, called FL-SIGN-DP, guarantees differential privacy for any client and is summarized in Alg. 9.

In what follows, we first describe the Discrete Gaussian Mechanism (DGM), which is used in FL-SIGN-DP, and prove that it practically provides the same privacy guarantee as the continuous Gaussian Mechanism (GM) if its variance is sufficiently large. This allows us to precisely quantify the privacy guarantee of FL-SIGN-DP. Finally, we show that using DGM instead of (continuous) GM in FL-SIGN-DP reduces the communication overhead by roughly 40%.

Discrete Gaussian Mechanism (DGM)

The discrete Gaussian distribution has probability mass function

pmf DG(µ,ξ) (x) = Z -1 exp(-(x -µ) 2 /2ξ 2 ) (5.1)
where Z = x∈Z exp(-(x -µ) 2 /2ξ 2 ). Note that µ ∈ R but the support of DG is always Z. Although Z is infeasible to compute, there are several efficient techniques to sample from the discrete Gaussian distribution [START_REF] Micciancio | Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time[END_REF].

The next lemma shows that the pmf of the discrete Gaussian distribution can be almost perfectly approximated by its continuous counterpart if ξ is large enough. Lemma 1. Let pmf DG(µ,ξ) (x) and pdf G(µ,ξ) (x) be as defined in Eq. (5.1) and Eq. (2.1), respectively, and

κ(ξ) = 2e -2π 2 ξ 2 1-e -6π 2 ξ 2 . Then, 1 -κ(ξ) ≤ pdf G(µ,ξ) (x)
pmf DG(µ,ξ) (x) ≤ 1 + κ(ξ) for x ∈ Z. The proof can be found in Appendix 8.1.1. The multivariate spherical version of DG can be defined analogously to the spherical Gaussian distribution, that is, if z ∼ DG(µ, ξ), then zi ∼ DG(µi, ξ) independently for each i.

The Discrete Gaussian Mechanism (DGM) is defined analogously to the (continuous) Gaussian Mechanism except that it uses discrete Gaussian noise instead of its continuous counterpart for perturbation. The next theorem shows that the moments of DGM can be tightly upper bounded by that of the continuous Gaussian mechanism if ξ is large enough, and hence the privacy guarantee of DGM can be efficiently and accurately approximated.

Let

η G 0 (x|ξ) = pdf G(0,ξ) (x) and η G 1 (x|ξ) = (1 -C)pdf G(0,ξ) (x) + Cpdf G(1,ξ) (x)
where C is the sampling probability of a single client in a single round. Let αG(λ|C) = log max(E1(λ, ξ, C), E2(λ, ξ, C))

(5.2)

where

E1(λ, ξ, C) = R η G 0 (x|ξ, C)• η G 0 (x|ξ,C) η G 1 (x|ξ,C) λ dx and E2(λ, ξ, C) = R η G 1 (x|ξ, C)• η G 1 (x|ξ,C) η G 0 (x|ξ,C) λ dx.
αDG(λ|C) is defined analogously to αG(λ|C).

Theorem 2 (Privacy of DGM). αDG(λ|C) ≤ αG(λ|C) + log (1+κ(ξ)) λ

(1-κ(ξ)) λ+1

for any C, where κ(ξ) is defined in Lemma 1. Therefore, DGM is (min λ ( αG(λ|C) + log (1+κ(ξ)) λ

(1-κ(ξ)) λ+1

log δ)/λ, δ)-DP.

The proof can be found in Appendix 8.1.2. Given a fixed value of δ, ε is computed numerically as in [START_REF] Abadi | Deep Learning with Differential Privacy[END_REF][START_REF] Mironov | Rényi Differential Privacy of the Sampled Gaussian Mechanism[END_REF].

Notice that, in [START_REF] Clément L Canonne | The Discrete Gaussian for Differential Privacy[END_REF], the privacy bound of the proposed Discrete Gaussian Mechanism is same as the one of its continuous counterpart. However, to obtain this result, they considered a Discrete Gaussian Mechanism with an integer mean. Therefore, their mechanism can only be used with integer values, which is not always the case in practice. Hence, our result is more general and can even be used with float values.

Privacy of FL-SIGN-DP

As shown in Alg. 9, each client k generates a random integer vector z k ∼ DG(sign(∆w k t ), √ nσI/ |K|) in FL-SIGN-DP. Then, every client sends the encrypted result EncK k (z k ) to the aggregator. After summing all the encrypted integers, the server obtains

k EncK k (z k ) = k z k = k DG(

Communication Overhead

The domain of z in Eq. (5.3) is the support of DG which is still unbounded. This means that the size of the encrypted text can be very large though with exponentially small probability. Indeed, ||z k ||∞ is unbounded and hence modulo m = 2 log 2 (max k ||z k ||∞|K|) has to be large. To overcome this problem, we choose modulo m to be so large that the probability that 2 log 2 (max k ||z k ||∞|K|) is larger than m is negligible. For this purpose, we rely on the following concentration inequality of the discrete Gaussian distribution.

Lemma 2 ([MW17], Lemma 2.2). For any ν > 0, ξ > ln(2 + 2/ν)/2π 2 , and t > 0, Pr

x∼DG(µ,ξ) [|x - µ| ≥ t • ξ] ≤ 2e -t 2 /2 • 1+ν 1-ν .
Lemma bits in total to the aggregator. For example, if |K| = 100, max k ||µ k ||∞ = 1, σ = 1 (i.e., ε ≈ 0.2), then log 2 m = 22. By contrast, if noise was generated from the continuous domain, then log 2 m = 32 which means that DGM reduces the communication overhead by roughly 32%.

Notice that if ε or δ is smaller (i.e., there is stronger privacy guarantee), then σ is larger which implies that m also increases, and hence more bits need to be transferred to the server per parameter. This results in a trade-off between Differential Privacy and bandwidth efficiency.

11 w k t-1 = w 12 ∆w k t = SGD(D k , w k t-1 , T gd ) -w k t-1 13 ∆ ŵk t = ∆w k t / max 1, ||∆w k t || 2 S Output: Enc K k (G(∆ ŵk t , SIσ/ |K|))

Robustness of FL-SIGN-DP Against non-adversarial Client Failures

If any client fails to add its noise share to the model update for any reason, the aggregate will not have sufficient amount of noise to guarantee differential privacy. A straightforward countermeasure is to increase the variance of the added noise so that even if r clients fail, the sum of CN -r noise shares are still enough for differential privacy. In particular, each client k sends EncK k (DG(sign(∆w k t ),

√ nσI/ √ CN -r))
to the server for aggregation. Obviously, if less than r nodes fail, the aggregate will have larger noise than what is necessary for differential privacy.

Experimental Set-up

The performance of FL-SIGN-DP is compared with FL-STD-DP in Table 5.1 and 5.2. FL-STD-DP is an extension of FL-STD to provide client-level differential privacy. Specifically, in FL-STD-DP, the randomly selected clients first clip their model update vector to have a bounded L2-norm 4 , add continuous Gaussian noise to the clipped update vector, and then transfer the non-quantized noisy model update to the server (see Alg. 10 for more details). The configurations of these protocols are summarized in Table 8.2.

Performance Evaluation

Table 5.1 and 5.2 show the best model accuracy observed over 200 rounds with each algorithm on the MNIST and Fashion-MNIST datasets, respectively. FL-STD-DP provides the best accuracy; for MNIST, it is 86-93%, and for Fashion-MNIST, it is 61-78% depending on the privacy parameter ε. The performance degradation of FL-SIGN-DP compared to FL-STD-DP is at most 0.02 on MNIST and 0.07 on Fashion-MNIST. In fact, FL-SIGN-DP outperforms FL-STD-DP for small privacy budget (i.e., ε = 1). As expected, weaker privacy requirement (i.e., larger ε) needs smaller noise magnitude and hence better accuracy for all algorithms.

The communication cost of FL-SIGN-DP is 66% of that of FL-STD-DP. Specifically, while FL-STD-DP needs 32 bits per parameter, FL-SIGN-DP requires 21-22 bits depending on the value of ε 5 . If ε is smaller, the variance of the noise is larger, and hence more bits are necessary to encode the noisy signs.

The convergence rates of FL-SIGN and FL-SIGN-DP are

O 1 √ T cl CN and O 1 √ T cl CN + √ 3nσ √ T cl CN , respectively, supposing that γ = O(1/ √ T cl ), T gd = 1, |B| = T cl (see Appendix 8.1.4 for the proofs).
Therefore, the "cost of privacy" in convergence rate is

O √ 3nσ √ T cl CN
which is due to the added noise. Tab. 5.2: Model accuracy and communication cost with Fashion-MNIST dataset using FL-SIGN-DP. We give the communication cost per parameter value (bits/parameter) for any value of ε.

ε = 1 ε = 2 ε = 4 Acc Cost Acc

FL-CS-DP: Private and Bandwidth-Efficient Federated Learning via Compressive Sensing

FL-CS-DP is the private extension of FL-CS described in Section 4.1.4. It provides the same guarantee as FL-SIGN-DP and considers the same Privacy model (see Section 5.1 and Section 5.2.1 for more details). Therefore, it aims at preserving the privacy of each client instead of each record (client-level privacy). In what follows, we first describe the operation required to reach this guarantee and then we evaluate our private scheme on both: accuracy and bandwidth efficiency aspects.

Operation

∼ G(0, SσI/ √ K) is added to ĉk t such that k∈K (ĉ k t + z k ) = k∈K ĉk t + G(0, SσI)
as the sum of Gaussian random variables also follows Gaussian distribution 6 and then differential privacy is satisfied where ε and δ can be computed using the moments accountant described in Section 2.2. 5 It is computed from log 2 2 log 2 ((12

√ nσ+max k ||µ k ||∞ )|K|)
where σ is obtained from ε and δ = 10 -5 using the moments accountant. This ensures that the magnitude of the noisy update per model parameter is less than the modulus n with probability at most 2 -80 (see Section 5.2.4). 6 More precisely,

i G(νi, ξi) = G( i νi, i ξ 2 i )
However, as the noise is inversely proportional to √ K, z k is likely to be small if |K| is too large. Therefore, the adversary accessing an individual update ĉk t + z k can almost learn a non-noisy update since z k is small. Hence, each client uses secure aggregation to encrypt its individual update before sending it to the server. Upon reception, the server sums the encrypted updates as:

k∈K y k t = k∈K EncK k (ĉ k t + z k ) = k∈K ĉk t + k∈K z k = k∈K ĉk t + G(0, SσI) (5.4)
where EncK k (ĉ k t +z k ) = ĉk t +z k +K k mod p and k K k = 0 (see [START_REF] Ács | I Have a DREAM! (DiffeRentially privatE smArt Metering)[END_REF][START_REF] Bonawitz | Practical Secure Aggregation for Federated Learning on User-Held Data[END_REF] for details). Here the modulo is taken element-wise and p = 2 log 2 (max k ||ĉ k t +z k ||∞|K|) . Let γ k t = 1/ max 1,

||c k t || 2 S .
Then,

k∈K ĉk t = k∈K γ k t c k t = k∈K γ k t C(∆w k t , m) = C( k∈K γ k t ∆w k t , m) (5.5)
where the last equality comes from the linearity of the compression operation (see Section 2.3). Plugging Eq. (5.5) into Eq. (5.4). we get that k∈K

y k t = C( k∈K γ k t ∆w k t , m) + G(0, SσI)
This is an instance of BPDN (see Section 2.3), and therefore the direct reconstruction of k∈K y k t would be an approximation of k∈K γ k t ∆w k t . However, analogously to FL-CS, the server applies error propagation and computes the (noisy) error et from yt = (1/|K|) k∈K y k t (in Line 10), and decompresses et into st by using OWL-QN. Recall that the reconstruction algorithm solves the BPDN problem, where a sparse vector s is reconstructed from m noisy measurements of the form Θs + z, where the noise z ∈ R m is assumed to be identically and independently distributed over its elements with a Gaussian distribution [JV10; CDS01]. Since z ∼ G(0, SIσ) in our case, the reconstruction algorithm is therefore optimized to reconstruct the differentially private compressed vectors (see Theorem 1).

Privacy of FL-CS-DP

Privacy Analysis

The server can only access the noisy aggregate which is sufficiently perturbed to ensure differential privacy; any client-specific information that could be inferred from the noisy aggregate is tracked and quantified by the moments accountant, described in Section 2.2, as follows.

Let

η0(x|ξ) = pdf G(0,ξ) (x) and η1(x|ξ) = (1 -C)pdf G(0,ξ) (x) + Cpdf G(1,ξ) (x)
where C is the sampling probability of a single client in a single round. Let

α(λ|C) = log max(E1(λ, ξ, C), E2(λ, ξ, C)) (5.6) where E1(λ, ξ, C) = R η0(x|ξ, C) • η 0 (x|ξ,C) η 1 (x|ξ,C) λ dx and E2(λ, ξ, C) = R η1(x|ξ, C) • η 1 (x|ξ,C) η 0 (x|ξ,C) λ dx.

Theorem 4 (Privacy of FL-CS-DP). FL-CS-DP is (min

λ (T cl • α(λ|C) -log δ)/λ, δ)-DP.
Given a fixed value of δ, ε is computed numerically as in [START_REF] Abadi | Deep Learning with Differential Privacy[END_REF][START_REF] Mironov | Rényi Differential Privacy of the Sampled Gaussian Mechanism[END_REF]. The magnitude of the added Gaussian noise is proportional to the sensitivity S, which is in turn often proportional to the model size n [START_REF] Zhu | Voting-based Approaches For Differentially Private Federated Learning[END_REF]. Hence, when n becomes large, SGD often fails to converge due to the perturbation error caused by the added noise [START_REF] Zhu | Voting-based Approaches For Differentially Private Federated Learning[END_REF]. In our approach, the perturbation error is less since Gaussian noise is added to the compressed vector with size m < n. On the other hand, compression also induces some reconstruction error owing to its lossy nature. The total error is the sum of the reconstruction and the perturbation error and is quantified in Theorem 1. Finding the right trade-off between these two errors is the key to achieve good model quality. 17

w k t = SGD(D k , w k t-1 , T gd ) 18 ∆w k t = w k t -w k t-1 19 c k t = C(∆w k t , m) 20 ĉk t = c k t / max 1, ||c k t || 2 S Output: Enc K k (G(ĉ k t , SIσ/ |K|))

Robustness of FL-CS-DP Against non-adversarial Client Failures

If any client fails to add its noise share to the model update for any reason, the aggregate will not have sufficient amount of noise to guarantee differential privacy. A straightforward countermeasure is to increase the variance of the added noise so that even if l clients fail, the sum of |K| -l noise shares are still enough for differential privacy. In particular, each client k sends EncK k (G(ĉ k t , SIσ/ |K| -l)) to the server for aggregation. Obviously, if less than r nodes fail, the aggregate will have larger noise than what is necessary for differential privacy.

Experimental Set-up

To evaluate our private scheme FL-CS-DP, we use exactly the same settings and datasets used to evaluate its non-private version FL-CS described above in Section 4.1.5. Note that, FL-STD-DP, FL-RND-DP and FL-FREQ-DP (see Alg 10,12,13 for more details) are the private extension of FL-STD, FL-RND and FL-FREQ, respectively.

The sensitivity S is selected during an initialization round for each scheme by taking the median value over N L2-norm values. We also noticed that the sensitivity of FL-CS-DP, FL-RND-DP and FL-FREQ-DP are nearly equivalent for the same level of compression. For this reason, the same sensitivity value is used for each compressed scheme and for the same compression ratio. Table 8.4 and Table 8.5 show the selected clipping threshold (i.e., sensitivity S) for each dataset and according to each compression ratio.

Results

Table 5.3 represents the best accuracy over 200 rounds for each scheme on the Fashion-Mnist dataset. Round corresponds to the round when the best accuracy is reached and Cost is the average bandwidth consumption calculated as: r × n × 32 × Round × C, where 32 is the number of bits necessary to represent a float value, n is the uncompressed model size, r = m n , m is the compressed

17 w k t = SGD(D k , w k t-1 , T gd ) 18 ∆w k t = w k t -w k t-1 19 Generates a random set G = {x ∈ {1, •
∆ w k t = ∆ w k t / max 1, || ∆ w k t || 2 S Output: Enc K k (G( ∆ w k t , SIσ/ |K|))
model size, C is the sampling probability of a client, and Round is the round when we get the the best accuracy. Table 5.4 represents the best balanced accuracy over 100 rounds for each scheme on the Medical dataset. AUROC (area under the receiver operating characteristic curve [START_REF] Narkhede | Understanding AUC -ROC Curve[END_REF]) corresponds to the AUROC value when the best balanced accuracy is reached, round is also the round when we get the best balanced accuracy, and finally, Cost is the average bandwidth consumption calculated as for the Fashion-MNIST dataset described above.

Surprisingly, for the smallest compression ratio 5%, FL-CS-DP performs as well as FL-RND-DP or FL-FREQ-DP in terms of accuracy and much better in terms of bandwidth consumption. Indeed, FL-CS-DP with a compression ratio of 5% reached 0.78 of accuracy on Fashion-MNIST, however, our baseline FL-RND-DP needs a compression ratio of 10% to reach a similar result (0.77) and 20% to have slightly better result (0.80). The same holds for the medical dataset, where FL-CS-DP reached 0.69 and 0.76 of balanced accuracy and AUROC, respectively. However, our other baseline FL-FREQ-DP needs a compression ratio of 20% to reach the same performance. FL-CS-DP performs better for a small compression ratio. Indeed, FL-CS-DP reaches 0.78, 0.73 and 0.66 for 5%, 10% and 20% of accuracy, respectively, on Fashion-MNIST. The accuracy degradation with DP can be explained by the fact increasing the compression ratio r also increases the sensitivity S which has a direct impact on the additive Gaussian noise as explained in Section 5.3.1. Indeed, the standard deviation of the normal distribution is σ × S.

On both datasets, FL-STD-DP suffers from the noise due to the large sensitivity which is the largest one in Table 8.4 and Table 8.5 for a compression ratio of 1.0 (uncompressed model). Even for FL-RND and FL-FREQ, the gap between the non-private and the private version is larger when the compression ratio increases for both datasets. As the noise proportional to S and is added to every coordinate, the norm of the added noise increases with the model size n. This has negative impact on model convergence for a large n as discussed in [START_REF] Zhu | Voting-based Approaches For Differentially Private Federated Learning[END_REF]. By decreasing n, compression helps reach better utility.

On Fashion-MNIST, FL-CS-DP with a compression ratio of 0.05 outperforms FL-STD-DP on both utility and bandwidth preservation. However, and even though FL-CS-DP reduces the bandwidth cost 14

w k t = SGD(D k , w k t-1 , T gd ) 15 ∆w k t = w k t -w k t-1 16 ∆ w k t = Φ∆w k t / max 1, ||C( ∆ w k t ,m)|| 2 S Output: Enc K k (G( ∆ w k t , SIσ/ |K|))
by 95% which is not negligible, they have both comparable accuracy on the medical data. It can be explained by the reduction of the noise due to the reduction of S and σ (see Table 8.5 and Table 8.4: Indeed, for FL-STD-DP, S*sigma=0.46 with the medical data, and it is 3.31 with Fashion-MNIST.) needed to reach an value of at most 1 after T cl rounds. In order to validate our assumption, we have decided to run two more experiments: (1) We increased sigma from 1.49 to 5 (epsilon=0.39), which will result in a (balanced) accuracy of 0.65 and an AUROC value of 0.70 for FL-CS-DP (r=0.05), and only 0.63 (Balanced accuracy) and 0.68 (AUROC) for FL-STD-DP.

(2) We have decided to run an experiment on another dataset, and we chose the well-known MNIST dataset. In this case the accuracy of FL-CS-DP (r=0.05, S=0.39) is equal to 0.93 and the accuracy of the FL-STD-DP (S=1.8) is 0.85. Once again, the results show the positive impact of compressive sensing on the quality of predictions as measured by AUROC, Balanced accuracy or Accuracy; under privacy-preserving settings.

There is a possible tradeoff between the privacy, communication cost, and utility. Indeed, having a small (better privacy) results in a reduction of the communication costs while it decreases accuracy. FL-STD-DP, for example, converges to the best accuracy (61%) after only 25 rounds with early stopping, which results in high privacy ( =0.69) and low communication cost (only 22.18 Megabit). However, the accuracy degradation is more important (about 30% which is the worst accuracy degradation indicated in Table 5.3). Indeed, the large amount of added noise impacts the convergence of the model which can not achieve an accuracy larger than 61%.

Finally, we highlight a trade-off for FL-CS-DP. As mentioned above, FL-CS-DP performs better when the smallest compression ratio r is used, as the sensitivity for this level of compression is the smallest one. On the other hand, the compression ratio cannot be decreased arbitrarily as it will result in large reconstruction error. Therefore, one has to find the smallest compression ratio that is small enough to reduce the perturbation error but large enough to induce small reconstruction error. Finally, we note that increasing the number of local SGD iterations T gd performed by each client reduces the sparsity of its updates. This can make the reconstruction of the aggregate at the server side less accurate or even impossible.

FL-TOP-DP: Private and Bandwidth-Efficient Federated Learning via Constraint

FL-TOP-DP is the private extension of FL-TOP described in Section 4.2.1. It provides the same guarantee as FL-SIGN-DP and FL-CS-DP and considers the same Privacy model (see Section 5.1 and Section 5.2.1 for more details). Therefore, it aims at preserving the privacy of each client instead of each record (client-level privacy). In what follows, we first describe the operation required to reach this guarantee and then we evaluate our private scheme on both: accuracy and bandwidth efficiency aspects.

Operation

FL-TOP-DP is described in Alg. 14 is very similar to FL-TOP except that each client adds Gaussian noise to its Top-K model updates to guarantee client-level DP, and applies secure aggregation allowing the server to learn only the aggregated (and noisy) model update. More specifically, each client first calculates its compressed model update ∆w k t = C(w k t -w k t-1 ) (in Line 25) which is then clipped (in Line 26) to obtain ∆ ŵk t with L2-norm at most S. After that, random noise z k ∼ G(0, SσI/ √ K) is added to ∆ ŵk t such that the sum k∈K (∆ ŵk t + z k ) = k∈K ∆ ŵk t + G(0, SσI) as the sum of Gaussian random variables also follows Gaussian distribution 7 and then differential privacy is satisfied where ε and δ can be computed using the moments accountant described in Section 2.2. Recall that the Top-K coordinates in T are selected and distributed by the server, which is honest-but-curious by assumption.

However, as the noise is inversely proportional to √ K, z k is likely to be small if |K| is too large. Therefore, the adversary accessing an individual update ∆ ŵk t + z k can almost learn a non-noisy update since z k is small. Hence, each client uses secure aggregation to encrypt its individual update before sending it to the server. Upon reception, the server sums the encrypted updates as: . Then,

k∈K c k t = k∈K EncK k (∆ ŵk t + z k ) = k∈K ∆ ŵk t + k∈K z k = k∈K ∆ ŵk t + G(0, SσI) (5.7) 7 More precisely, i G(νi, ξi) = G( i νi, i ξ 2 i ) 5.4 FL-
k∈K ∆ ŵk t = k∈K γ k t ∆w k t = k∈K γ k t C(w k t -w k t-1 , T) = C( k∈K γ k t (w k t -w k t-1 ), T) (5.8)
where the last equality comes from the linearity of the compression operation. Indeed, recall that each client selects the values of the same Top-K coordinates from T. Plugging Eq. (5.8) into Eq. (5.7). we get that

k∈K c k t = C( k∈K γ k t (w k t -w k t-1 ), T) + G(0, SσI)

Privacy of FL-TOP-DP

Privacy analysis: The server can only access the noisy aggregate which is sufficiently perturbed to ensure differential privacy; any client-specific information that could be inferred from the noisy aggregate is tracked and quantified by the moments accountant, described in Section 2.2, as follows.

Let

η0(x|ξ) = pdf G(0,ξ) (x) and η1(x|ξ) = (1 -C)pdf G(0,ξ) (x) + Cpdf G(1,ξ) (x)
where C is the sampling probability of a single client in a single round. Let α(λ|C) = log max( E1(λ,ξ,C),E2(λ,ξ,C))

where E1(λ, ξ, C) = R η0(x|ξ, C) • η 0 (x|ξ,C) η 1 (x|ξ,C) λ dx and E2(λ, ξ, C) = R η1(x|ξ, C) • η 1 (x|ξ,C) η 0 (x|ξ,C) λ dx.
Theorem 5 (Privacy of FL-TOP-DP). FL-TOP-DP is

(min λ (T cl • α(λ|C) -log δ)/λ, δ)-DP.
Given a fixed value of δ, ε is computed numerically as in [Aba+16; MTZ19]. 18

w k t-1 = w 0 19 j = 1 20 for each coordinate i in T do 21 w k t-1 [i] = ŵk t-1 [j] 22 j = j + 1 23 end 24 w k t = Top k SGD(D k , w k t-1 , w 0 , T gd , T) 25 ∆w k t = C(w k t -w k t-1 , T) 26 ∆ ŵk t = ∆w k t / max 1, ||∆w k t || 2 S Output: Enc K k (G(∆ ŵk t , SIσ/ |K|))

Remarks

The magnitude of the added Gaussian noise is proportional to the clipping threshold S, which is in turn calibrated to the norm of the model update. However, the norm of the model update increases if the model size increases [START_REF] Zhu | Voting-based Approaches For Differentially Private Federated Learning[END_REF], and hence S should be chosen sufficiently large to guarantee fast convergence with large accuracy. On the other hand, too large S also increases the perturbation error caused by the added noise.

FL-TOP aims to diminish this perturbation error by reducing S via compression which also increases the L2-norm of the compressed update vector. This is illustrated in Figure 5.1, which shows that the norm of the Top-K coordinates with FL-TOP tend to be larger than with FL-STD (i.e., when all coordinates get updated not only the Top-K). Therefore, besides decreasing the magnitude of the added noise, FL-TOP also decreases the relative error on the retained parameters. These together decrease the perturbation error caused by the added noise.

Notice that there exist other alternatives to identify the Top-K coordinates in a privacy-preserving manner than using a public dataset. For example, every client can select the Top-K parameters with the largest magnitude during the first rounds locally, and send them to the server for aggregation. More specifically, each client creates a parameter vector with size n, where the Top-K coordinates are set to 1 while the rest are kept 0. Then, these binary vectors are noised and aggregated by the server like in Section 5.4.1. In the rest of the training, all participants exchange only the updates and weights of the these Top-K parameters like in FL-TOP. However, aside from consuming more privacy budget, this approach also has lower accuracy than our proposal according to our tests. Moreover, it has larger communication cost in the initialization phase when the Top-K parameters are identified and the whole binarized parameter vector is sent for aggregation.

Robustness of FL-TOP-DP Against non-adversarial Client Failures

If any client fails to add its noise share to the model update for any reason, the aggregate will not have sufficient amount of noise to guarantee differential privacy. A straightforward countermeasure is to increase the variance of the added noise so that even if l clients fail, the sum of |K| -l noise shares are still enough for differential privacy. In particular, each client k sends EncK k (G(∆ ŵk t , SIσ/ |K|)) to the server for aggregation. Obviously, if less than r nodes fail, the aggregate will have larger noise than what is necessary for differential privacy.

Experimental Set-up

The goal of this section is to evaluate the performance of our proposed scheme FL-TOP-DP on a benchmark dataset and a realistic in-hospital mortality prediction scenario. We aim at evaluating their performance with different levels of compression and comparing them with the performance of the following learning protocols: FL-STD-DP,FL-BASIC-DP, FL-CS-DP and FL-SIGN-DP which are the private extensions of FL-STD, FL-BASIC, FL-CS and FL-SIGN introduced in Section 2.1, Section 4.2.2, Section 4.1.4 and Section 4.1.18 .

Note that all compression operators in the baselines are linear (just like FL-TOP-DP), and hence they can also be used with secure aggregation. Similarly to FL-TOP-DP, the private extensions (i.e., FL-STD-DP, FL-BASIC-DP, FL-CS-DP and FL-SIGN-DP) also clip and then noise the compressed updates. However, with FL-SIGN-DP we use the Discrete Gaussian Mechanism defined in Section 5.2.2 instead of the continuous.

Similarly to Section 4.2.2, we evaluate the above learning algorithms on the well-known Fashion-MNIST dataset and on the Premier Healthcare Database. More details can be found in Section 8.3. We also fix the Top-K weights before starting the federated learning process using public data: For Fashion-MNIST we use MNIST and for the medical dataset we use a batch from the same dataset (as we did in Section 4.2.2).

In order to select the clipping threshold S, the server executes a single training round locally, which is composed of T gd SGD iterations starting from the model parameters w0, using the batch from the public data. The clipping threshold S is set to the L2-norm of the Top-K weight update obtained for this single training round. For FL-BASIC-DP, the same steps are repeated for 100 times, where a new random set of trainable weights with size K are selected each time, which yields 100 L2-norm values. S is set to the median of these L2-norm values. We think that this approach is more fair, because the set of trainable weights is re-selected at each round in FL-BASIC-DP. The computed values of S can be found in Table 8.9 and Table 8.10 for Fashion-MNIST and Medical dataset, respectively. More information about the model architecture and the hyper-parameter selection can be found in Section 8.3 and Table 8.8 in the Appendix. Tab. 5.5: Summary of results on Fashion-MNIST dataset using the FL-TOP-DP scheme.

Results

Figure 5.1 displays the distribution of the Top-K updated weights for FL-TOP and FL-STD at the end of the training. We select the weights when each scheme reached the best accuracy over 200 and best balanced accuracy9 over 100 rounds for fashion-MNIST and the medical dataset, respectively. We choose the smallest compression ratio r that leads to the best accuracy for the FL-TOP-DP scheme. Table 5.5 shows that FL-TOP-DP reaches the best accuracy, 0.81, when r = 0.5% on fashion-MNIST and reaches the best accuracy, 0.69, when r = 0.1% on the medical dataset. Both figures validate the intuition that by constraining the model to update only a small set K of the total weights, these Top-K become more important and reach larger values. This result is important when differential privacy is used as it leads to larger value-to-noise level and therefore better performance.

Table 5.5 represents the best accuracy over 200 rounds for each scheme on the Fashion-MNIST dataset. Round corresponds to the round when the best accuracy is reached and Cost is the average bandwidth consumption calculated as: r × n × 32 × Round × C, where 32 is the number of bits necessary to represent a float value, n is the uncompressed model size, r = |T| n , |T| is the compressed model size, C is the sampling probability of a client, and Round is the round when we get the the best accuracy.

Table 5.6 represents the best balanced accuracy over 100 rounds for each scheme on the Medical dataset. AU ROC (area under the receiver operating characteristic curve -see Appendix 8.4.2) corresponds to the AU ROC value when the best balanced accuracy is reached. Note that FL-SIGN-DP needs 22 bits to encode each parameter as it is based on the Discrete Gaussian Mechanism (more details can be found in Section 5.2.4).

The results also show that not only our privacy-preserving solution FL-TOP-DP provides strong privacy guarantee (with values smaller than 1) but also that it outperforms the other schemes in terms of accuracy and bandwidth, for both datasets.

For example, with Fashion-MNIST, our scheme achieves an accuracy of 0.81 when r = 0.5% while the baseline scheme, FL-BASIC-DP, achieves an accuracy of 0.79 when r = 10% and requires 189 times more downstream bandwidth and 18 times more upstream bandwidth. Similarly, FL-SIGN-DP is 22% less accurate than FL-TOP-DP and it requires 17 times more upstream bandwidth and 25 times more downstream bandwidth.

With the medical dataset, FL-TOP-DP reaches the best balanced accuracy 0.69 and best AUROC 0.76 for a compression ratio of r = 0.1% while FL-BASIC-DP and FL-CS-DP achieve the same performance at r = 5%. Note that FL-STD-DP performs very poorly as noise has to be added to the all weights of the model and the sensitivity is large (see Table 5.5 and Table 5.6). Finally, FL-SIGN-DP is 9% and 11% less accurate than FL-TOP-DP on the Balanced accuracy and AUROC, respectively, while it requires 1142 times more upstream bandwidth and 785 times more downstream bandwidth.

Conclusion

Differential privacy generally consists of adding noise sampled from a continuous Gaussian distribution to the updates. However, if we add continuous Gaussian noise to the quantized updates of FL-SIGN in order to obtain its private extension called FL-SIGN-DP, we loose the bandwidth efficiency property. We therefore proposed to sample noise from a discrete Gaussian distribution instead. As a result, FL-SIGN-DP is 30-40% more bandwidth efficient than FL-STD and FL-STD-DP.

We also have shown that the utility of the private model can be improved by reducing its sensitivity via compression. Similarly, it can be improved by increasing the value-to-noise either by taking the first frequencies of the discrete cosine transform of the update (FL-CS-DP) or by constraining the model to only update some weights (FL-TOP-DP). Finally, reconstructing the approximated gradients in FL-CS-DP is an instance of Basis Pursuit Denoising (or LASSO), which can be solved with efficient solvers that provide large accuracy despite the added Gaussian noise.

Security Analysis

In this Chapter, we first evaluate the robustness of FL-SIGN, FL-CS and FL-TOP against several stateof-the-art security attacks. More specifically, we investigate the robustness against pollution attacks which includes targeted (backdoors attacks) and untargeted attacks. We noticed that FL-SIGN is particularly robust to such attacks compared to the vanilla federated learning FL-STD, but also to our other compressed schemes, namely FL-CS and FL-TOP. Indeed, we have shown that FL-SIGN prevents the adversary to scale up its update to increase its impact on the global model. Due to the quantized nature of FL-SIGN, the adversary can be easily detected if it sends a value larger than +1 or smaller than -1. Also, the majority vote at the server side also allows the server to be more robust against the attacks.

In the second part of this Chapter, we investigate if FL-SIGN-DP is as robust as its non-private variant FL-SIGN. However, we noticed that FL-SIGN-DP is not robust. Seemingly, there is a possible trade-off between differential privacy and robustness against security attacks.

Security Model

Adversarial model: In this work, we assume that the adversary controls a certain fraction of the participating entities/clients at each round of the training, which means it can access and modify these clients' training data as well as all parameters of their local model. We, however, assume that the server is honest (i.e., it does not manipulate the aggregate nor the update vector sent by any client). The set of all malicious nodes is denoted by M.

We consider two types of adversary. The first one aims at degrading the overall model performance (i.e., increase the average misclassification rate). The second one aims at causing targeted misclassification on some particular classes of samples by injecting backdoors into the model during the training phase. These adversaries are active in the sense that they may not follow the learning protocol faithfully.

Next, we detail the attacks considered.

6.1.1 Overall Model Degradation Attacks (Untargeted Attacks) Adv . Each malicious party selects the noise independently (i.e., they do not collude).

Gradient Ascent Attack

In this attack, malicious clients aim at maximizing the loss by performing gradient ascent instead of descent on their own training data [START_REF] Nasr | Comprehensive Privacy Analysis of Deep Learning: Passive and Active White-box Inference Attacks against Centralized and Federated Learning[END_REF]. In particular, every malicious client k ∈ M updates the model parameters locally as

w k = w k -1 + η Adv ∇f (∪ k∈M D k ; w)
, where η Adv is set in order to suppress the updates of honest clients and to maximize the impact of their own update on the common model. Notice that this attack assumes colluding malicious clients (i.e., every malicious client sends exactly the same update computed on the union of their training data). This attack attempts to maximize the average misclassification rate of the common model, and is more effective if the number of malicious parties is large, or the training data of the malicious and benign nodes come from similar distributions.

We note that Gradient Ascent Attack is equivalent to the Sign Inversion Attack for FL-SIGN, described in [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF], if T gd = 1 (i.e., each client computes its update using a single mini-batch in every round). In Sign Inversion Attack, all malicious clients faithfully compute the sign of their model update, but then send the inverted signs to the server for aggregation.

Backdoor Attacks (Targeted Attacks)

The goal of these attacks is to selectively degrade the accuracy of the common model with respect to only a few tasks. As opposed to the overall model degradation attacks, they generate targeted misclassification while preserving the model convergence as well as a high average prediction accuracy except, of course, for the targeted tasks, called backdoor classes.

We distinguish two types of backdoors: In-backdoors and Out-backdoors.

- To illustrate the difference between in-and out-backdoors, consider a model which recognizes dogs and rabbits in the input photos. If the adversary relabels all photos of dogs as 'rabbit' in its training data, then it is an in-backdoor attack. However, if the adversary adds new photos of frogs to its training data and relabels them as 'dog', then this is an out-backdoor attack.

In
Out-backdoors are more difficult to detect than in-backdoors as they can come from a much larger set of samples, which are potentially unknown to the protocol participants. Hence, out-backdoors are especially severe in security-related applications such as in access control.

As per [START_REF] Arjun | Analyzing federated learning through an adversarial lens[END_REF], the adversary also uses explicit boosting to outbalance the combined effect of benign model updates. For both in-and out-backdoors, the adversary boosts ∆w t Adv at time t by sending η Adv ∆w t Adv (η Adv > 1) in order to suppress the model updates of benign parties. Importantly, η Adv should be large enough in order to achieve misclassification of the backdoor class but also small enough to ensure the convergence of the common model and hence hide the attack.

Security Analysis of FL-SIGN, FL-CS and FL-TOP

In this section, we evaluate the robustness of FL-SIGN, FL-CS and FL-TOP against the security attacks presented previously.

For the Overall Model Degradation attacks, different percentage of malicious nodes are considered, the MNIST and IMDB datasets were used, and the same experimental setting as defined in Table 8.1 is used. The boosting parameter η Adv of the Gradient Ascent Attack is set to 10 with MNIST dataset and 20 with the IMDB dataset (we use the boosting only with FL-STD, FL-CS and FL-TOP1 ). We also do not need to use boosting for the Random Update Attack as σ Adv = 200 generates large noise which prevents the model convergence.

For the Backdoor attacks, the MNIST and CIFAR datasets were used and the experimental setting is shown in Table 8.3. As backdoor attacks, which aim at modifying the prediction of one particular label while maintaining the global accuracy, are more difficult to perform on binary classifiers, we switched to the CIFAR dataset with a multiclass classifier. Furthermore, similarly to [START_REF] Arjun | Analyzing federated learning through an adversarial lens[END_REF], we reduce the total number of clients N from 1000 to 10, we use different percentages of malicious nodes: 10%, 20% and 40%, and all clients report their updates to the server at each round (i.e. C = 1.0). The malicious nodes collude by sharing their data for the training and by sending the same update to the server.

Overall Model Degradation Attacks

6.2.1.1 Random Update Attack Table 6.1 and 6.2 depict the best accuracy of the global model over 100 rounds according to the fraction of malicious nodes in set K. The results show that FL-SIGN is robust against the random update attack even if 20% of all nodes are malicious, while FL-STD, FL-CS and FL-TOP fail to converge even if 1% of all nodes are malicious. Indeed, with 20% of malicious nodes, FL-SIGN reaches an accuracy of 98% and 86% for the MNIST and IMDB datasets, respectively. On the contrary, FL-STD, FL-CS and FL-TOP fail to converge even with one malicious node at each round. In fact, as we show in Appendix 8.1.4, FL-SIGN's convergence rate is O

1 (1-α) √ CN T cl
, where α denotes the fraction of malicious clients. This is in contrast to the sign inversion attack detailed in [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF], which has a convergence rate of O

1 (1-2α) √ CN T cl
, that is, convergence is only possible if less than half of the nodes are malicious. 6.3), FL-SIGN reaches an accuracy of 98% and 79% for 20% and 40% of malicious nodes, respectively, while the other schemes do not converge even if only 10% of the nodes are malicious. For IMDB dataset, FL-SIGN reaches an accuracy of 86% and 72% for 10% and 20% of malicious nodes, respectively, while FL-STD, FL-CS and FL-TOP fail to converge with only 10% of malicious nodes. Indeed, they do not converge even if we have only one malicious node. The reason for this difference is that malicious nodes can scale up their update with η Adv and hence boost its effect on the global model. However, such adversarial boosting does not work with FL-SIGN as the trusted server accepts only the values -1 and +1 in the update vectors. Therefore, a single malicious client does not have larger impact on the global model than any other honest client. To boost its impact, the adversary can only increase the number of the malicious clients, as shown by the experimental results. Since Gradient Ascent is equivalent to Sign Inversion Attack if T gd = 1, the convergence rate of Gradient Ascent in this restricted scenario is O 6.5, 6.6 show the effect of in-backdoor attacks on the MNIST and CIFAR datasets, respectively. In all experiments, there are ten clients, out of which different fraction of malicious nodes are considered. Figure 6.1 depicts the accuracy of the global model for MNIST, when the adversary relabels every image of digit '5' to '7' in its local dataset. The red plots show the accuracy of the global models, while the green ones display the model accuracy only for the images with label '5' (i.e., accuracy on the backdoor class). The results show that FL-SIGN is robust as both global model accuracy and model accuracy on the specific in-backdoor class (digit 5) reach 99% by the end of the training.

1 (1-2α) √ CN T cl as shown in [BZAA18]. 10% 20% 40% 60% FL-STD - - - - FL-CS - - - - FL-TOP - - - -
By contrast, with FL-STD, while the accuracy of the global model converges slowly to 99%, the accuracy of the attacked model oscillates. Similar behaviour can be observed in Figure 6.2 which plots the accuracy on CIFAR dataset, where images of airplanes are re-labelled to 'ship' in the adversary's training data. In these experiments, FL-STD fails to converge on the backdoor class, and its accuracy on CIFAR never exceeds 55%.

The oscillation of accuracy with FL-STD can be explained by the nature of gradient descent and in particular backpropagation: when the malicious client injects the backdoor, it scales its update with η Adv . In the following round, honest clients scale up their gradients on the backdoor samples (i.e., images of digit 5 in MNIST and images of airplanes in CIFAR) in order to "fix" the classification error on the backdoor class. In the next round, when the model is "fixed" (i.e., digit '5' is correctly predicted as '5' again), the adversary's gradients are increased again in order to re-inject the backdoor. This process repeats till the end of the training. By contrast, and similarly to the overall model degradation attacks, a malicious client cannot scale up its update in FL-SIGN as the update vectors must take value from {-1, 1} n . Table 6.5 shows the accuracy of the model on digit class 5 (in-backdoor class) when we consider different percentage of malicious nodes (values are chosen based on the best model accuracy over 40 rounds). The global accuracy of the model over all the classes is 99% and the accuracy on class '5' is 99% independently of the number of malicious nodes and regardless whether FL-STD or FL-SIGN is used. However, the accuracy on class '5' is more impacted when we use FL-CS or FL-TOP. Indeed, with 40% of malicious nodes, the accuracy on class '5' is 74% and 83% for FL-CS and FL-TOP, respectively.

As in the previous table, Table 6.6 shows the accuracy of the model on airplane class (in-backdoor class) when we consider different number of malicious nodes (values are chosen based on the best global accuracy over 100 rounds). FL-SIGN with 20% of malicious nodes reaches a global accuracy of 84%, and an accuracy of 76% on the in-backdoor class. However, FL-STD with the same amount of malicious nodes reaches 80% of global accuracy and 0% for the airplane class. About other schemes, FL-CS reaches a global accuracy of 80% and an accuracy of 71% on the 'airplane' class, whereas, FL-TOP reaches a global accuracy of 81% and an accuracy of 35% on the in-backdoor class. The results validate the robustness of FL-SIGN over the other schemes.

Out-backdoor Attack

The main goal of the out-backdoor attack is to introduce fake information during the training by relabeling a sample, whose true label is not a valid output of the global model. We experimented this attack on MNIST by first excluding all samples with digit '0' in all clients' training datasets. We then choose different fraction of malicious clients and relabeled the samples with '0' to '1'. Similarly, the attack is also implemented using the CIFAR dataset by removing all airplanes from the clients' training data and relabelling all images of an airplane as 'ship' in the malicious clients' datasets 2 . Note that pattern with the CIFAR dataset although the accuracy difference is less significant (66% versus 72%). This can be explained by the inherent bias present in CIFAR. For example, planes are often misclassified as 'bird' or 'ship' even without the attack because of the similar background of these images (i.e., sky is very similar to sea in many images). Indeed, the probability of predicting an airplane as a ship without the attack is 58%, and it only increases to 66% and 72% with FL-SIGN and FL-STD, respectively.

Almost the same remarks can be done on the other schemes FL-TOP and FL-CS. Indeed, with 10% of malicious nodes, the attack accuracy on the MNIST dataset for FL-SIGN is 77% and 61% less than FL-CS and FL-TOP, respectively. On the CIFAR dataset, the attack accuracy with 10% of malicious nodes for FL-SIGN is 8% and 6% less than FL-CS and FL-TOP, respectively.

As for in-backdoor attacks, FL-SIGN mitigates out-backdoor attacks because the adversary cannot scale up its update in order to increase its impact on the global model. In fact, we did not use boosting during Out-backdoor attacks and despite that FL-STD, FL-CS and FL-TOP have been more vulnerable. Therefore, even the use of the majority vote plays also an important role to be more robust. rate to misclassify the out-backdoor class "airplane" to the targeted class "ship" (attack accuracy). We choose the compression ratio r for FL-CS and FL-TOP such that each scheme reaches the same accuracy as FL-STD on the same settings but without the attack. Therefore, r is set to 60% and 20%, respectively.

FL-SIGN-DP Security Analysis

Table 6.9, 6.10, 6.11 and 6.12 depict the accuracy of the in-backdoor class and the misclassification rate of the out-backdoor class (best values are chosen based on the global model accuracy over 200 rounds) when backdoor attacks are launched against FL-SIGN-DP schemes. Indeed, we investigate if FL-SIGN-DP is as robust as its non-private variant called FL-SIGN.

Malicious clients, whose fraction changes between 0.1 and 0.4, omit to add noise to their own updates at each round. Also, malicious clients collude by sharing their data and sending the same adversarial updates to the server. We use the configuration described in Table 8.2 except for γ which is decreased to 0.001. In Fashion-MNIST dataset, at all malicious nodes, all images of 'Sandal' are relabelled to 'Sneaker' for In-backdoor, and all images of 'T-shirt/top' are relabelled to 'Trouser' for Outbackdoor attacks (only the malicious nodes have photos of 'T-shirt/top'). In addition, with FL-SIGN-DP, each malicious node calculates their updates, extracts the signs (sign : R n → {-1, 1} n ) and then uses a boosting parameter η Adv = 5000 to boost their updates before sending them back to the server for aggregation. Indeed, as all honest clients send the noisy update in FL-SIGN-DP, the noise together with encryption can conceal the manipulation of the malicious update vectors.

The results show that FL-SIGN-DP is less robust against backdoor attacks than FL-SIGN. On the MNIST dataset, model accuracy on the in-backdoor class is 0% for FL-SIGN-DP regardless of the number of malicious nodes, and larger than 97% and 95% for FL-SIGN, with 10% and 20% of malicious nodes, respectively. The same tendency holds for Fashion-MNIST. Out-backdoor attacks are especially effective on MNIST (see Table 6.11 and Table 6.12); here, the misclassification rate is more than 98% for FL-SIGN-DP and 0-99% for FL-SIGN. When we consider only 2% of malicious nodes with MNIST, the misclassification rate is 0% for FL-SIGN and 76% for FL-STD (without boosting) with a global model accuracy of 98% for both schemes. Indeed, FL-STD is vulnerable to the out-backdoor attack even if we have only a small number malicious node and without using any boosting. For MNIST and Fashion-MNIST, FL-SIGN is clearly superior to FL-SIGN-DP regarding all attacks.

Finally, random update attack and gradient ascent attack are mounted against FL-SIGN-DP. The same parameters are used as in the previous experiments. Malicious clients still collude and omit to add any noise to their own model updates. Instead, they boost their signs updates with FL-SIGN-DP (η Adv = 5000). The model fails to converge even if only 1% of all selected nodes are malicious at each round.

10% 20% 40%

Conclusion

FL-SIGN is almost as accurate as FL-STD but incurs less communication overhead and has better resiliency against both security and privacy attacks (see Section 4.1.3 and 6.2). FL-TOP and FL-CS are also less robust against poisoning attacks compared to FL-SIGN. In fact, FL-SIGN is more robust due to: (1) the quantization which mitigates the adversarial updates and (2) the majority vote which implies to take a more robust decision regarding how to update of each weight. Notice that, the "Curse of Dimensionality" assumption defined in [START_REF] Chang | Cronus: Robust and heterogeneous collaborative learning with black-box knowledge transfer[END_REF] which claims that large models, with high dimensional parameter vectors are more vulnerable to security attacks, is not always true. Indeed, we have shown in our results that the bandwidth efficient FL-TOP and FL-CS schemes are sometimes less robust than the non-compressed scheme FL-STD (see Table 6.5).

Seemingly, there is a possible trade-off between differential privacy and robustness against security attacks. One possible explanation is that differential privacy requires to randomize every value of the update vector so much that their aggregates become easier to manipulate. As malicious clients omit to add any noise to their own model updates, the attacked DP protocols essentially turn into Random Update Attacks, where honest clients send almost uniformly random signs and malicious clients transfer non-noisy, boosted updates to the aggregator. As FL-SIGN converges with Random Update Attack even with limited number of honest nodes, the malicious nodes in FL-SIGN-DP can also degrade model performance or inject backdoors for the very same reason. The smaller ε is the more uniform every coordinate's distribution will be, and the larger impact a malicious client has on the aggregate.

Conclusion and perspectives

Concluding Remarks

As described in this thesis Federated Learning is a very promising approach but suffers from a high bandwidth cost. Furthermore, although it improves privacy, it does not provide any theoretical privacy-preserving guarantee. This thesis reports some of the works of my Ph.D. studies where we tried to address some of these issues.

The first part of this thesis proposes three bandwidth efficient Federated Learning schemes. The first solution is called FL-SIGN and it is a quantization approach. FL-SIGN reduces the number of bits per parameter by a factor of 32. Therefore, instead of sending 32 bits per parameter, we only have to send 1 bit: +1/-1 to either increase or decrease the weight. The second solution FL-CS leverages the sparsity of the updates which are sent from the client to the server. By using Compressive sensing theory [START_REF] Jacques | Compressed sensing: When sparsity meets sampling[END_REF], which allows to reconstruct a sparse data (i.e., image or signal) from some sampled points in it, we have shown that it is possible to learn a model as accurate as the model learned via standard federated learning. Moreover, FL-CS allows to compress each update up to 95% compared to the standard scheme. FL-TOP for its part harnesses the ability of the model to adapt its weights under constraint. By updating only the weights which are more likely to be updated during the training process, we have shown that it is possible to compress the model until 99.9%. Moreover, our previous proposals FL-SIGN and FL-CS are bandwidth efficient only during upstream traffic (from clients to server), however, FL-TOP is bandwidth efficient in both upstream and downstream directions due to the fact that the same proportion of weights are updated during all the learning process while keeping all the remaining ones constant. Therefore, this protocol seems to be well adapted to an environment with energy-constrained devices as the batteries of such devices are highly sensitive to the network communications.

The second part of this thesis defines Differentially Private versions of FL-SIGN, FL-CS and FL-TOP. The private extension of FL-SIGN called FL-SIGN-DP provides client-level Differential Privacy (DP) and aims at protecting any information that is unique to a client's training data. We show that our DP learning protocol produces models with an accuracy comparable to its non-private version even with stringent privacy guarantees (eg., = 1). The private extension of the federated learning scheme called FL-STD has performance slightly better than FL-SIGN-DP (this difference tends to be reduced as we increase the privacy protection (reducing ).), however the latter has 30-40% less communication cost than FL-STD-DP and FL-STD. The bandwidth efficiency of our DP algorithm is due to the use of a novel discretized and distributed version of the Gaussian Mechanism. Therefore, the noise values are discrete and can be encoded with fewer bits than if they came from a continuous Gaussian distribution.

The utility-privacy trade-off is one of the challenge that we face when we use DP. Having a good privacy guarantee (small ) is often synonymous with high accuracy decrease and vice-versa. To have a differentially private solution, we have to noise the updates. The required noise is generally sampled from a Gaussian distribution with mean 0 and variance S 2 σ 2 . S is the sensitivity of the model and it is generally proportional to its size. By reducing the size of the model we also reduce its sensitivity and therefore the required noise for a differentially private guarantee. This is exactly what FL-CS-DP and FL-TOP-DP leverage in order to improve the utility of the model. Both of them outperform the FL-STD-DP scheme in both accuracy and bandwidth efficiency. Moreover, in FL-CS-DP the noise is added on the first discrete cosine transform frequencies of each update which are generally larger than the other frequencies and only few weights are updated in FL-TOP-DP during the learning process which make their values larger compared to the case when they are trained under the standard learning scheme FL-STD-DP. Therefore, FL-CS-DP and FL-TOP-DP increase the value-to-noise to improve the model's accuracy.

Finally, Chapter 6 evaluates the robustness of the proposed schemes in an adversarial environment. First, we have evaluated the robustness of our non private schemes: FL-SIGN, FL-CS and FL-TOP against poisoning attacks.The poisoning attacks can be either targeted where the adversary aims at reducing the accuracy of the model regarding a specific class, or untargeted and in that case the adversary aims at reducing the global model accuracy without distinction between classes. Our results show that FL-SIGN has better resiliency against both targeted and untargeted attacks compared to FL-CS, FL-TOP and FL-STD even by considering strong adversaries which collude by sharing their data and sending the same updates. FL-SIGN mitigates out-backdoor attacks because the adversary cannot scale up its update in order to increase its impact on the global model. Also, the majority vote allows to take a better decision on how each weight should be updated. This straightforward approach can be also used with secure aggregation which is not the case of most techniques designed to detect the malicious updates or to choose the honest updates. Indeed, they generally require access to each individual participant's update which is therefore incompatible with secure aggregation. After that, we evaluated the robustness of the private extension of FL-SIGN in order to see if it is as robust. However, the results have shown that FL-SIGN-DP is not robust against poisoning attacks due to the added noise requires by the differential privacy scheme. Our result introduces a possible trade-off between differential privacy and robustness against security attacks.

Future Research Directions

• Designing Differentially Private and Secure Federated Learning Scheme. This research indicates that there might exist a robustness/privacy tradeoff and we would like to explore this further. Using Game Theory algorithms might be an interesting direction to investigate. Such algorithms aim at increasing a profit or minimizing a cost. If we consider that our profit is to increase the utility of the model, such algorithms may help the server to select only or at least more often honest participants than malicious ones. For example, we can model the selection of an honest set of clients as a multi-armed bandit problem [ACF02; BF85]. A Multiarmed bandit problem models a casino with a slot machine of k arms, where pulling each arm results in a different and unknown expected payoff. The goal is to sequentially select the optimal sequence of slot machine arms to pull to maximize the expected total reward. Considering each selected set of client K at each round as an arm, that may or may not provide a reward (improve model accuracy for example) when it is used.

• Improving the Utility-Privacy Tradeoff. Using differential privacy has a cost and may highly reduce the utility (accuracy) of the model. To reduce this negative effect of DP on the accuracy, we reduced the sensitivity of the model by reducing its size and we also increased the valueto-noise. However, there is also other possibilities to reduce the noise either by: 1) reducing the number of federated' rounds or 2) reducing the sampling probability of any participant. In Federated Learning, each selected client at a specific round, updates the received model based on his data only during few, limited SGD iterations. Indeed, if the selected clients decide to run an unlimited number of SGD iterations 1 , the aggregated model tends to diverge, due to the fact that each client's update will be highly personalized on its dataset. Therefore, it is interesting to find how we can run the maximum number of SGD iterations at the client side without impacting the convergence of the model after the aggregation. This might speed up the training process and therefore decrease the noise. One possible solution to reduce the sampling probability is to leverage the large amount of public data freely available online. More specifically, we can add some simulated clients with public data in order to reduce the sampling probability and therefore to reduce the noise. However, we should find a way to either make the updates of the simulated clients valuable even if they use public data or limit their impact on the learning process otherwise. Note that this approach remains valid even for the centralized learning scenario with a record-level privacy guarantee.

• Private and Secure Federated Learning Based on New Approaches. Most of the research on federated learning focus on the standard federated learning approach called Horizontally Federated Learning [KC04; SS15; MMRHA16], where the same features are shared between participants, but they differ on their records. However, the security and privacy aspects of the Vertical Federated Learning (VFL) and Federated Transfer Learning (FTL)2 were not studied yet. Therefore, it is interesting to evaluate the different poisoning attacks and inference attacks on the other approaches. Moreover, proper attacks and solutions might be designed for the non-studied approaches. Similarly, It is interesting to study the privacy and robustness of the recent AI approaches like Self-supervised learning and Graph neural networks in federated learning context. Indeed, Self-supervised is a new approach and sub-class of unsupervised learning. According to Professor Yann LeCun and Professor Yoshua Bengio, it will be the future of AI as it may allow machines to develop "common sense" just like humans [21b; 21a]. Graph Neural Networks are also becoming increasingly popular as these allow better explainability of the model's prediction. It is therefore important to study their privacy and security properties in a collaborative learning environment as with Federated Learning.

• Detection of malicious entities. It is interesting to provide some mechanisms to either detect malicious servers or participants, which aims at inferring sensitive information or at degrading the accuracy of the model via poisoning attacks. However, this solution should take into account that a strong adversary can adapt and behave malicious only during some rounds. Therefore, by switching from honest to malicious behaviour, it is really challenging to detect such adversaries.

• Evaluating the contribution of each participant under DP. Different solutions allow to evaluate the contribution of malicious entities under federated learning settings [Pej20; FVL21] to prevent Free-rider Attacks [START_REF] Fraboni | Free-rider Attacks on Model Aggregation in Federated Learning[END_REF]. Indeed, in such attacks, the adversary's goal is to obtain the final aggregated model without actually contributing with any data. However, previous solutions do not consider DP. Therefore, it is interesting to find a way to do it when DP is used. It is particularly challenging because by definition using DP for a client-level differential privacy does not allow distinguishing between clients.

• Evaluating the impact of compression on the model's performance. It is interesting to study the negative impact of the compression on the model's performance. This should include more aspects than only considering the potential loss in average accuracy. In [START_REF] Hooker | What Do Compressed Deep Neural Networks Forget[END_REF], the authors show that compression disproportionately impacts model performance on the underrepresented long-tail of the data distribution. Therefore, it seems that compression has a negative impact on fairness. We should then inverstigate all the possible aspects which may be impacted negatively by compression. Proof. We first show that Z/

√ 2πξ ≤ 1 + 2e -2π 2 ξ 2 1-e -6π 2 ξ 2 , where Z = x∈Z exp(-(x -µ) 2 /2ξ 2 ), which implies the upper bound. From [Sza01], Z = √ 2πξϑ3(πµ, exp(-2π 2 ξ 2 )), where ϑ3(u, r) = 1 + 2 i≥1 r i 2 cos(2iu) is a Jacobi Theta function. Then, 1 + 2 i≥1 r i 2 cos(2iu) ≤ 1 + 2r i≥0 r 3i ≤ 1 + 2r 1 -r 3 if |r| < 1.
The lower bound can be derived similarly using the fact that cos(2iu) ≥ -1.

Proof of Theorem 2

Proof. Without loss of generality, suppose that DG ξ : R → Z n .

We apply the moments accountant [START_REF] Abadi | Deep Learning with Differential Privacy[END_REF] and show that αDG(λ) can be upper bounded efficiently without evaluating the pmf of DG.

Let

η DG 0 (x|ξ) = pmf DG(0,ξ) (x) and η DG 1 (x|ξ) = (1 -q)pmf DG(0,ξ) (x) + qpmf DG(1,ξ) (x) where pmf DG(µ,ξ) (x) = Pr x∼DG(µ,ξ) [x]. Then, αDG(λ) = log max(E 1 (λ, ξ), E 2 (λ, ξ))
where

E 1 (λ, ξ) = ∞ x=-∞ η DG 0 (x|ξ) • η DG 0 (x|ξ) η DG 1 (x|ξ) λ ≤ (1 + κ(ξ)) λ (1 -κ(ξ)) λ+1 ∞ x=-∞ η G 0 (x|ξ) • η G 0 (x|ξ) η G 1 (x|ξ) λ ≤ (1 + κ(ξ)) λ (1 -κ(ξ)) λ+1 R η G 0 (y|ξ) • η G 0 (y|ξ) η G 1 (y|ξ) λ dy = (1 + κ(ξ)) λ (1 -κ(ξ)) λ+1 E1(λ, ξ)
where the first inequality follows from Lemma 1. Using a similar reasoning we obtain that

E 2 (λ, ξ) ≤ (1 + κ(ξ)) λ (1 -κ(ξ)) λ+1 E2(λ, ξ)
The theorem follows from Theorem 2 in [START_REF] Abadi | Deep Learning with Differential Privacy[END_REF].

Proof of Theorem 3

As opposed to the continuous case, the sum of discrete Gaussian random variables i DG(µi, ξi) does not follow the distribution of DG( i µi, i ξ 2 i ), though it is very close to that if ξi is sufficiently large. The exact difference is quantified by the following Lemma from [START_REF] Micciancio | Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time[END_REF].

Lemma 3 ([MW17], Theorem 2.1). If ξi ≥ ln(2 + 2/ν)/π and µi ∈ R n , then 1 -ν 1 + ν ≤ Pr z∼ i DG(µ i ,ξ i ) [z] Pr z∼DG i µ i , i ξ 2 i [z] ≤ 1 + ν 1 -ν for any z ∈ Z n Intuitively, if Z = x∈Z exp(-(x -µ) 2 /2ξ 2 i ) ≈ √ 2πξi then DG(µi, ξi) ≈ G(µi, ξi), in which case i DG(µi, ξi) ≈ i G(µi, ξi) = G(µi, i ξi) ≈ DG(µi, i ξi)
, which follows from Lemma 3. Indeed, it also follows from the proof of Lemma 1 that Z/

√ 2πξi ≤ ϑ3(πµ, exp(-2π 2 ξ 2 i )) ≤ 1 + 2e -2π 2 ξ 2 i 1-e -6π 2 ξ 2 i ≤ 1 + 2 exp(2ξ 2 i π 2 )-1 ≤ 1 + 2 exp(ξ 2 i π 2 )-2 ≤ 1 + ν
which provides some insight into the condition on ξi in Lemma 3.

For example, ν < 10 -4 is satisfied if ξi > 1.

Let DG ξ denote the distributed Gaussian mechanism which returns N k=1 DG(µ k , ξ/ |K|) where µ k ∈ R n . The next lemma, which directly follows from Theorem 2 and Lemma 3, implies Theorem 3.

Lemma 4. If ξ ≥ |K| ln(2 + 2/ν)/π, then α DG (λ|q) ≤ αG(λ|q) + log (1+κ(ξ)) λ (1-κ(ξ)) λ+1 1+ν 1-ν 3 .

Convergence Proofs

All the proofs are simple adaptations of Theorem 2 from [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF]. Here we outline only the main deviations from the proof of that theorem.

Assumptions:

1. Lower bound: For all x and some constant f * , f (x) ≥ f * , where f denotes the loss/objective function.

2. Smoothness: Let g(x) denote the gradient of the objective function f evaluated at x. Then, for all x, y and some non-negative constant L = (L1, L2, . . . , Ln),

|f (y) -[f (x) + g(x) T (y -x)]| ≤ 1/2 i Li(yi -xi) 2
3. Variance bound: Upon receiving query x ∈ R n , the stochastic gradient oracle gives us an independent, unbiased estimate ĝ that has bounded variance per coordinate: E[ĝ(x)] = g(x), E[(ĝ(x)i -g(x)i) 2 ] ≤ τ 2 i for a vector of non-negative constants τ = (τ1, τ2, . . . , τn).

4. Unimodal, symmetric gradient noise: At any given point x, each component of the stochastic gradient vector ĝ(x) has unimodal distribution that is also symmetric about the mean.

Note that adding extra Gaussian noise to each gradient component for the purpose of differential privacy will not violate Assumption 4.

1 T cl T cl -1 t=0 E||gt||1 ≤ 2 √ T cl √ 2||τ ||1 (1 -α) √ CN + ||L||1(f0 -f * )
where α denotes the fraction malicious clients and |gi|/τi ≤ 2/ √ 3 for all 1 ≤ i ≤ n.

For FL-SIGN-DP,

1 T cl T cl -1 t=0 E||gt||1 ≤ 2 √ T cl ||τ ||1 √ CN + √ 3nσ||τ ||1 CN + ||L||1(f0 -f * )
if |gi|/τi ≤ 2/ √ 3 for all 1 ≤ i ≤ n.

Proof. The primary focus of all the proofs is to bound the probability that a client computes the sign of a parameter update correctly. Let M = CN . As in [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF], let Zi ∈ [0, M ] denote the number of correct sign bits received by the aggregator for parameter i, and p denotes the probability that a honest client computes the correct bit. Let ω = p -1 2 .

1. Random Update Attack: Notice that the probability that a sign of any parameter is correct at a malicious client is 1/2, and each client acts independently from each other. Hence, E [Zi] = (1 -α)M p + 1 2 αM and Var [Z] = 1 4 αM + (1 -α)M p(1 -p). The probability that a vote fails for the i th parameter is identical to P [Zi ≤ M/2], which, likewise in [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF], can be bounded as follows.

P [Zi ≤ M/2] = P [E [Zi] -Zi ≥ E [Zi] -M/2] ≤ 1 1 + (E[Z i ]-N/2) 2 Var[Z i ]
(by Cantelli's inequality)

≤ 1 2 Var [Zi] (E [Zi] -M/2) 2
(by 1 + x 2 ≥ 2x)

≤ 1 2 √ M 1 4 α + (1 -α)p(1 -p) (1 -α) 2 (p -1 2 ) 2 ≤ 1 2 √ M 1 4 α (1 -α) 2 (p -1 2 ) 2 + 1 2 √ M p(1 -p) (1 -α)(p -1 2 ) 2 ≤ √ α 4 √ M (1 -α)|ω| + 1 2 √ M 1 4 -ω 2 (1 -α)ω 2 ≤ √ 3ατi 2 √ M (1 -α)|gi| + τi M (1 -α)|gi| (8.1) ≤ τi( √ α + √ 1 -α) √ M (1 -α)|gi| ≤ √ 2τi √ M (1 -α)|gi|
where, in Eq. (8.1), we used that 1 4ω 2 -1 ≤ 4τ 2 i /g 2 i and 1/|ω| ≤ 2 √ 3τi/|gi| for |gi|/τi < 2/ √ 3 based on Lemma 1 in [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF]. The rest of the derivation is identical to the proof of Theorem 2 in [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF].

FL-SIGN-DP:

The Gaussian noise is added to the sum of signs. Let Yi denote the random variable describing the noise added by the clients to Zi. Based on [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF],

P [Zi + Yi ≤ M/2] ≤ 1 2 Var [Zi + Yi] (E [Zi + Yi] -M/2) 2
1 2 Var [Zi] (E [Zi] -M/2) 2 ≤ 1 2 M 1 4 -ω 2 M 2 ω 2 ≤ 1 2 M 4τi/|gi| M 2 ω 2 ≤ τi √ M |gi| (8.3)
Moreover, if |gi|/τi ≤ 2/ √ 3, then 1/ω 2 ≤ 12τ 2 i /g 2 i , and hence

1 2 Var [Yi] (E [Zi] -M/2) 2 ≤ 1 2 nσ 2 M 2 ω 2 ≤ 1 2 12nσ 2 τ 2 i /g 2 i M 2 ≤ √ 3 √ nστi M |gi| (8.4)
Plugging Eq. (8.3) and (8.4) into Eq. (8.2), we obtain that the probability that the noisy vote fails for the i th coordinate is bounded as

P [Zi + Yi ≤ M/2] ≤ τi √ M |gi| + √ 3 √ nστi M |gi| if |gi|/τi ≤ 2/ √ 3.
The claim follows from the proof of Theorem 2 in [START_REF] Bernstein | signSGD with Majority Vote is Communication Efficient And Byzantine Fault Tolerant[END_REF].

Selection of Hyperparameters

Strictly speaking, the selection of hyperparameters in each private schemes, such as batch size |B|, scaling factor γ, or sensitivity S, must also be differentially private. One option is to use public data for this purpose which comes from the same distribution as the clients' private training data. The selection of hyperparameters can also be performed using more sophisticated methods like the one in Appendix D of [START_REF] Abadi | Deep Learning with Differential Privacy[END_REF].

Experimental Set-up

This section describes the experimental set-up that are used to evaluate the accuracy of our proposal. The following datasets were used: MNIST, Fashion-MNIST, IMDB, LFW and CIFAR.

Model Architectures:

• For MNIST and Fashion-MNIST, we use a model [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF] with the following architecture: a convolutional neural network (CNN) with two 5x5 convolution layers (the first with 32 filters, the second with 64, each followed with 2x2 max pooling), a fully connected layer with 512 units and ReLu activation, and a final softmax output layer. This results in 1,663,370 parameters in total.

• The LFW dataset is used with a CNN of three 3x3 convolution layers (32, 64, and 128 filters, each followed with 2x2 max pooling), a fully connected layer with 256 units and ReLU activation, and a final softmax output layer with 2 units. To test the property inference attack from [MSDS19], batch size is set to 32, and the SGD learning rate is 0.01.

• The model that we use for the CIFAR dataset is called "All-CNN-C" in [SDBR15] [START_REF] Labs | How these researchers tried something unconventional to come out with a smaller yet better Image Recognition[END_REF], which consists of a CNN of 3 blocks: the first block has three 3x3 convolutions layers with 96 filters (the last layer has a strides of 2x2 and dropout of 0.5 is applied), the ReLu activation is used per layer. The second block has the same configuration as the previous block, except the filter size which is 192 for each layer. The last block has one 3x3 convolutions layer with 192 filters, followed by two 1x1 convolution layers: the first with 192 filters (Relu activation) and the second with 10 filters. The last layer is connected with a global average pooling layer and uses softmax activation. We use also the Adam optimizer with a learning rate of 0.001. This results in 1,369,738 parameters in total.

• We use the following model for the IMDB dataset: one embedding layer with an output size of 50 (the vocabulary size is set to 5000 and the maximum length input to 400), followed by a convolution layer of one dimension with a kernel size of 5 and 250 filters; and a max pooling layer of size 3; followed by a LSTM layer with an output size set to 70 and an output layer with one unit that uses a sigmoid activation function. We use the Adam optimizer with a learning rate of 0.001. This results in 402,701 parameters in total.

• For our medical dataset, as in [START_REF] Avati | Improving palliative care with deep learning[END_REF], we use a fully connected neural network model with the following architecture: two hidden layers of 200 units, which use a Relu activation function followed by an output layer of 1 unit with sigmoid activation function and a binary cross entropy loss function. A dropout layer with a rate set to 0.5 is used between each hidden layer and between the last hidden layer and the output layer. This results in 1,496,601 parameters in total. We tune η from 0.01 to 0.5 with an increment value of 0.005.

Datasets

The following datasets were used:

• The MNIST database of handwritten digits. It consists of 28 x 28 grayscale images of digit items and has 10 output classes. The training set contains 60,000 data samples while the test/validation set has 10,000 samples [LC10] [START_REF] Chollet | Keras datasets[END_REF].

• The CIFAR-10 dataset consists of 60000 32x32 colour images in 10 classes, with 6000 images per class. There are 50000 training images and 10000 test images. We augment the dataset to 500,000 training images by randomly shifting the original images horizontally and vertically and by randomly flipping the original images horizontally [KNH] [Cho+15b].

• Fashion-MNIST database of fashion articles consists of 60,000 28x28 grayscale images of 10 fashion categories, along with a test set of 10,000 images [XRV17] [START_REF] Chollet | Keras datasets[END_REF].

• IMDB Movie reviews sentiment classification dataset of 25,000 movies reviews, labeled by sentiment (positive/negative) [START_REF] Chollet | Keras datasets[END_REF]. The test set contains also 25,000 movies reviews.

• Labeled Faces in the Wild (LFW) dataset: consists of 13,000 62 • 47 RGB images of faces collected from the web [START_REF] Gary | Labeled Faces in the Wild: A Database for Studying Face Recognition in Unconstrained Environments[END_REF]. The pixel of each image is an unsigned integer in the range between 0 and 255. We rescale themto the range [0,1] instead. And we did exactly the same with MNIST, Fashion-MNIST and CIFAR-10.

• As medical dataset, we used EHR data from the Premier healthcare database1 which is one of the largest clinical databases in the United States, collecting information from millions of patients over a period of 12 months from 415 hospitals in the USA [START_REF] Fejza | Scalable and Interpretable Predictive Models for Electronic Health Records[END_REF]. These hospitals are supposedly representative of the United States hospital experience [START_REF] Fejza | Scalable and Interpretable Predictive Models for Electronic Health Records[END_REF]. Each hospital in the database provides discharge files that are dated records of all billable items (including therapeutic and diagnostic procedures, medication, and laboratory usage) which are all linked to a given patient's admission [START_REF] Fejza | Scalable and Interpretable Predictive Models for Electronic Health Records[END_REF][START_REF] Makadia | Transforming the Premier Perspective® Hospital Database into the Observational Medical Outcomes Partnership (OMOP) Common Data Model[END_REF]. The initial snapshot of the database used in our work (before pre-processing step) comprises the EHR data of 1,271,733 hospital admissions. Electronic Health Record (EHR) is a digital version of a patient's paper chart readily available in hospitals. For developing supervised learning and specifically deep learning models, we focus on a specific set of features from EHR data. The features of interest that capture the patients information are summarized in Table 8.6. There is a total of 24,428 features per patient, mainly due to the variety of drugs possibly served. As in [START_REF] Avati | Improving palliative care with deep learning[END_REF], we also removed all the features which appear on less than 100 patients' records, hence, the number of features was reduced to 7,280 features. The Medication regimen complexity index (MRCI) [START_REF] Mcdonald | Automating the medication regimen complexity index[END_REF] is an aggregate score computed from a total of 65 items, whose purpose is to indicate the complexity of the patient's situation. The minimum MRCI score for a patient is 1.5, which represents a single tablet or capsule taken once a day as needed (single medication). However the maximum is not defined since the number of medications increases the score [START_REF] Mcdonald | Automating the medication regimen complexity index[END_REF]. In our case, after statistical analysis of our dataset, we consider the MRCI score as ranging from 2 to 60. Most real datasets like ours are generally imbalanced with a skewed distribution between the classes. In our case, the positive cases (patients who die during their hospital stay) represent only 3% of all patients. Table 8.7 gives more details about this distribution after the pre-processing step which is discussed in Appendix 8.4.1. To deal with this well-known problem, we have decided to use the downsampling technique [Mor16; HG09], a standard solution used for this purpose.2

The In-hospital Mortality Prediction Scenario: The ability to accurately predict the risks in the patient's perspectives of evolution is a crucial prerequisite in order to adapt the care that certain patients receive [START_REF] Fejza | Scalable and Interpretable Predictive Models for Electronic Health Records[END_REF]. We consider the scenario where several hospitals are collaborating to train models for in-hospital mortality prediction using our Federated Learning schemes. This well-studied real-world problem consists in trying to precisely identify the patients who are at risk of dying from complications during their hospital stay [Ava+18; Ra18; FGLB18]. As commonly found in the literature [START_REF] Fejza | Scalable and Interpretable Predictive Models for Electronic Health Records[END_REF], for such predictions, we focus on hospital admissions of adults hospitalized for at least 3 days, excluding elective admissions.

Using Client-Level differential privacy requires to add more noise than Record-Level differential privacy, because the privacy purposes are not the same as detailled in Section 2.2. To reduce the noise (when is fixed) and then improve the utility, we have to reduce the number of iterations or to reduce the sampling probability which are the parameters used to compute . We therefore have two options to reduce the sampling probability:

-Reducing the number of clients selected at each round |K|. However this option also decreases the amount of data, and hence have a negative impact on the utility. We therefore preferred to use the next option.

-Increasing the total number of clients N : we created more hospitals by splitting randomly the training data over 5011 "virtual" hospitals. We also, took care to have at least one in-hospital dead patient per hospital. Each hospital contains 203 patients except one which has 356 patients. We created 5011 hospitals5 in order to have approximately the same number of patients per hospital, each of them with some in-hospital dead patients.

In practise, Client-Level differential privacy is more adapted to an environment with a large set of clients as explained in [MRTZ18; GKN17].

Medical Data: Performance Metrics

We use the following metrics:

• Balanced accuracy [BOSB10; BDA13] is computed as 1/2•( TP P + TN N ) = TPR +TNR 2 and is mainly used with imbalanced data. True Positive Rate (TPR ) and True Negative Rate (TNR ): TPR = TP P and TNR = TN N , where P and N are the number of positive and negative instances, respectively, and TP and TN are the number of true positive and true negative instances. We note that traditional ("non-balanced") accuracy metrics such as TP +TN P +N can be misleading for very imbalanced data [START_REF] Akosa | Predictive accuracy: a misleading performance measure for highly imbalanced data[END_REF]: in our dataset, the minority class has only 3% of all the training samples (see Table 8.7), which means that a biased (and totally useless) model always predicting the majority class would have a (non-balanced) accuracy of 97%.

• The area under the ROC curve (AUROC ) is also a frequently used accuracy metric. The ROC curve is calculated by varying the prediction threshold from 1 to 0, when TPR and FPR are calculated at each threshold. The area under this curve is then used to measure the quality of the predictions.

A random guess has an AUROC value of 0.5, whereas a perfect prediction has the largest AUROC value of 1.

Evaluation Method.

First, we split randomly the dataset of each hospital into disjoint training and testing data (80% and 20% respectively). An entire federated run is executed with this split, and all the metrics are evaluated in every round on the union of all clients' testing data. All metric values of the round with the best balanced metric are recorded.

  For FL-STD-DP, S is set to 2.40. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.10 Sensitivity S used for each scheme and for different compression ratio r on the medical dataset. For FL-STD-DP, S is set to 1.40. . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.11 Summary of results on Fashion-MNIST dataset. . . . . . . . . . . . . . . . . . . . . . . . 8.12 Summary of results on Medical dataset (Part 1). . . . . . . . . . . . . . . . . . . . . . . vi 8.13 Summary of results on Medical dataset (Part 2). . . . . . . . . . . . . . . . . . . . . . . 86

  Learning (FL-STD) In federated learning [SS15; MMRHA16], multiple parties (clients) build a common machine learning model from the union of their training data without sharing them. At each round of the training, a set of selected clients retrieve the global model from the parameter server, update the global model based on their own training data, and send back their updated model to the server. The server aggregates the received updated models to obtain a global model that is re-distributed to some other parties in the next round. More specifically, a subset K of all N clients are randomly selected at each round to update the global model such that |K| = C × N , where C denotes the fraction of selected clients. At round t, a selected client k ∈ K executes T gd local gradient descent iterations on the common model wt-1 using its own training data D k (D = ∪ k∈K D k ), and obtains the updated model w k t , where the number of weights is denoted by n (i.e., |w k t | = |∆w k t | = n for all k and t).

Algorithm 1 :2

 1 FL-STD: Federated Learning 1 Server: Initialize common model w 0 3 for t = 1 to T cl do 4 Select K clients uniformly at random 5 for each client k in K do 6 ∆w k t = Client k (w t-1 )

Algorithm 2 :

 2 Stochastic Gradient Descent Input: D : training data, T gd : local epochs, w : weights 1 for t = 1 to T gd do 2 Select batch B from D randomly 3 w = w -η∇f (B; w) 4 end Output: Model w

  Range(A) to a dataset D. The privacy loss of A with datasets D and D at output O ∈ Range(A) is a random variable P(A, D, D , O) = log Pr[A(D)=O] Pr[A(D )=O] where the probability is taken on the randomness of A. Definition 2 (( , δ)-Differential Privacy [DR14]). A privacy mechanism A guarantees (ε, δ)-differential privacy if for any database D and D , differing on at most one record, Pr O∼A(D) [P(A, D, D , O) > ε] ≤ δ.

  For any function f : D → R n , the Lp-sensitivity of f is ∆pf = max D,D ||f (D)-f (D )||p, for all D, D differing in at most one record, where ||•||p denotes the Lp-norm.

  as follows: gt = ∇f (B, wt-1) : Computing gradients on batch B pt = ηgt + et-1 : Error feedback (correction) ∆t = D(C(pt)) : Reconstruction of pt wt = wt-1 -∆t : Updating model parameters (weights) et = pt -∆t : Error accumulation

211

  Initialize common model w 0 3 for t = 1 to T cl do 4 Select K clients uniformly at random 5 for each client k in K do 6 s k t = Client k (w t-1 ) Client k (w k t-1 ):

Global model wt 15 16

 15 1 to T cl do 4 Generate a random seed ζ Select K clients uniformly at random 5 for each client k in K do 6 y k t = Client k (w t-1 , ζ) Client k (w k t-1 , ζ):

  1 to T cl do 4 Select K clients uniformly at random 5 for each client k in K do 6 ∆y k t = Client k (w t-1 )

Initialize common model w 0 3 20 for

 020 Select set T of Top-K updated weights' coordinates via public dataset 4 for t = 1 to T cl do 5 Select K clients uniformly at random 6 for each client k in K do 7 c k t = Client k (C(w t-1 , T)) each coordinate i in T do 21

8 :

 8 Top k -Stochastic Gradient Descent Input: D : training data, T gd : local epochs, w : weights, w 0 : first weights' initialization, T : set of Top-K values coordinates . 1 for t = 1 to T gd do 2 Select batch B from D randomly 3 u = -η∇f (B; w) 4 for each coordinate i in T do 5 w[i] = w[i] + u[i]

2

  More precisely, i G(νi, ξi) = G i νi, i ξ 2 i 3 and then as a large integer for encryption 5.2 FL-SIGN-DP: Private and Bandwidth-Efficient Federated Learning via Quantization

Algorithm 10 :

 10 FL-STD-DP: Federated Learning with Client Privacy

Algorithm 11 :2

 11 FL-CS-DP: Private Compressive Sensing Federated Learning 1 Server: Initialize common model w 0 , η G , ρ, ut = 0, et = 0 3 for t = 1 to T cl do 4 Select K clients uniformly at random 5 for each client k in K do 6 y k t = Client k (w t-1 ) t-1 + yt : Momentum 10 et = η G ut + e t-1 : Error Feedback 11 st = D(et, n) : Reconstruction 12 et = et -C(st, m) : Error accumulation 13 wt = w t-1 + st : Update 14 end Output: Global model wt 15 16 Client k (w k t-1 ):

Initialize common model w 0 3 for t = 1 to T cl do 4 16

 34 Generate a random seed ζ Select K clients uniformly at random5 for each client k in K do 6 y k t = Client k (w t-1 , ζ) Client k (w k t-1 , ζ):

Algorithm 14 :Initialize common model w 0 3for t = 1 to T cl do 5 Select K clients uniformly at random 6 for each client k in K do 7 c k t =

 14056t FL-TOP-DP: Federated Learning Select set T of Top-K updated weights' coordinates via public dataset 4 Client k (C(w t-1 , T))

Fig. 5 . 1 :

 51 Fig. 5.1: Distributions of the Top-K weight values (after convergence) for both FL-TOP and FL-STD schemes with the Fashion-MNIST dataset (left) and the medical dataset (right).

  -backdoor Attacks: In-backdoor attacks [BCMC19] are created for a class of samples that exists in the training data of some parties. Specifically, for some training samples Daux ⊆ D k , each adversary uses output labels that are different from their true labels. Let y denote the adversarially chosen label for a training sample (x, y) ∈ Daux, and D aux denotes the set of all relabelled samples (i.e., (x, y ) ∈ D aux ). The new objective is to minimize the loss f ((D k \ Daux) ∪ D aux ; w). -Out-backdoor Attacks: As opposed to in-backdoors, out-backdoors are created from samples that do not exist in the training data of any honest clients and are relabelled to have a class that does exist in their training data. Specifically, let L denote the set of labels that exist in D = ∪ k D k . The adversary creates D aux such that, for each (x, y) ∈ D aux , x / ∈ D and y ∈ L. The new objective is to minimize the loss f (D k ∪ D aux ; w).

Figure 6 .

 6 Figure 6.1, 6.2 and Table6.5, 6.6 show the effect of in-backdoor attacks on the MNIST and CIFAR datasets, respectively. In all experiments, there are ten clients, out of which different fraction of malicious nodes are considered. Figure6.1 depicts the accuracy of the global model for MNIST, when the adversary relabels every image of digit '5' to '7' in its local dataset. The red plots show the accuracy of the global models, while the green ones display the model accuracy only for the images with label '5' (i.e., accuracy on the backdoor class). The results show that FL-SIGN is robust as both global model accuracy and model accuracy on the specific in-backdoor class (digit 5) reach 99% by the end of the training.

Fig. 6. 1 :

 1 Fig. 6.1: In-backdoor attack on FL-SIGN and FL-STD with the MNIST dataset, η Adv = 7. The figure displays the global accuracy convergence and the accuracy of the label "5" which is under attack. 10% of the nodes are malicious.

Appendix 8. 1

 1 Proofs for FL-SIGN and FL-SIGN-DP 8.1.1 Proof of Lemma 1

Theorem 6 .

 6 If |B| = T cl , T gd = 1, and γ = f 0 -f * ||L|| 1 T cl , then 1. For FL-SIGN in the Random Update Attack,

Tab. 8. 1 :

 1 Common environment and configuration of FL-SIGN, FL-CS, FL-TOP and FL-STD. γ = 0.001. |D k | = 60; |D k | = 25; |D k | = 500; |B| = 10; |B| = 25; |B| = 50; T gd = 30; T gd = 5; T gd = 50; T cl = 100; T cl = 100; T cl = 400; SGD ADAM ADAM (η = 0.215) (η = 0.001) (η = 0.001)

  Common environment between the schemes on the Medical dataset. ρ, ηG, λ and P are only used with FL-CS and FL-CS-DP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.6 Descriptions of features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7 Number of instances for our case study. The Medical dataset contains in total 1,271,733 records. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.8 Common environment between the schemes. ρ, ηG and P are only used with FL-CS and FL-CS-DP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.9

and 2.15 for MNIST and Fashion-MNIST, respectively. For FL-SIGN-DP, S is fixed to √ n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Parameter Configuration for the Backdoor Attacks. FL-SIGN is used with the vote aggregation γ = 0.001. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Common environment between the schemes on Fashion-MNIST. ρ, ηG, λ and P are only used with FL-CS and FL-CS-DP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5

  Thank you all! Proofs for FL-SIGN and FL-SIGN-DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.1 Proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.2 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.3 Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.4 Convergence Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Selection of Hyperparameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Experimental Set-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Model Architectures: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Medical Data: Data Pre-Processing & Experimental Set-up Details . . . . . . . . . . . . 8.4.1 Medical Data: Data Pre-Processing . . . . . . . . . . . . . . . . . . . . . . . . 8.4.2 Medical Data: Performance Metrics . . . . . . . . . . . . . . . . . . . . . . . . 8.4.3 Evaluation Method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Computational Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Dedication Introduction	1
		To my dear and lovely little daughter Léa and wife Amira
		To my beloved parents, brother Lyes and sister Doria.
		To my dearest aunt Fazia who is like my second mom.
	xii	xi

xiii Bibliography xvi 8 Appendix 8.1

  My publications written during my thesis are listed below:-"Constrained Differentially Private Federated Learning for Low-bandwidth Devices", Raouf Kerkouche, Gergely Ács, Claude Castelluccia and Pierre Genevès.To appear in the Conference on Uncertainty in Artificial Intelligence (UAI'21),[PDF].Abstract. Federated learning becomes a prominent approach when different entities want to learn collaboratively a common model without sharing their training data. However, Federated learning has two main drawbacks. First, it is quite bandwidth inefficient as it involves a lot of message exchanges between the aggregating server and the participating entities. This bandwidth and corresponding processing costs could be prohibitive if the participating entities are, for example, mobile devices. Furthermore, although federated learning improves privacy by not sharing data, recent attacks have shown that it still leaks information about the training data. This paper presents a novel privacy-preserving federated learning scheme. The proposed scheme provides theoretical privacy guarantees, as it is based on Differential Privacy. Furthermore, it optimizes the model accuracy by constraining the model learning phase on few selected weights. Finally, as shown experimentally, it reduces the upstream and downstream bandwidth by up to 99.9% compared to standard federated learning, making it practical for mobile systems. Our results suggest that strong and provable patient-level privacy can be enforced at the expense of only a moderate loss of prediction accuracy.-"Federated Learning in Adversarial Settings", Raouf Kerkouche, Gergely Ács, Claude Castelluccia. Submitted for publication,[PDF].Abstract. Federated Learning enables entities to collaboratively learn a shared prediction model while keeping their training data locally. It prevents data collection and aggregation and, therefore, mitigates the associated privacy risks. However, it still remains vulnerable to various security attacks where malicious participants aim at degrading the generated model, inserting backdoors, or inferring other participants' training data. This paper presents a new federated learning scheme that provides different trade-offs between robustness, privacy, bandwidth efficiency, and model accuracy.Our scheme uses biased quantization of model updates and hence is bandwidth efficient.

	Abstract. Machine Learning, and in particular Federated Machine Learning, opens
	new perspectives in terms of medical research and patient care. Although Federated
	Machine Learning improves over centralized Machine Learning in terms of privacy,
	it does not provide provable privacy guarantees. Furthermore, Federated Machine
	Learning is quite expensive in terms of bandwidth consumption as it requires participant
	nodes to regularly exchange large updates. This paper proposes a bandwidth-efficient

-"Compression Boosts Differentially Private Federated Learning", Raouf Kerkouche, Gergely Ács, Claude Castelluccia and Pierre Genevès. To appear in the 6th IEEE European Symposium on Security and Privacy (Euro S&P'21),

[PDF]

. Abstract. Federated Learning allows distributed entities to train a common model collaboratively without sharing their own data. Although it prevents data collection and aggregation by exchanging only parameter updates, it remains vulnerable to various inference and reconstruction attacks where a malicious entity can learn private information about the participants' training data from the captured gradients. Differential Privacy is used to obtain theoretically sound privacy guarantees against such inference attacks by noising the exchanged update vectors. However, the added noise is proportional to the model size which can be very large with modern neural networks. This can result in poor model quality. In this paper, compressive sensing is used to reduce the model size and hence increase model quality without sacrificing privacy. We show experimentally, using 2 datasets, that our privacy-preserving proposal can reduce the communication costs by up to 95% with only a negligible performance penalty compared to traditional non-private federated learning schemes.

-"Privacy-Preserving and Bandwidth-Efficient Federated Learning: An Application to

In

-Hospital Mortality Prediction", Raouf Kerkouche, Gergely Ács, Claude Castelluccia and Pierre Genevès. ACM Conference on Health, Inference and Learning (CHIL'21), [PDF]. privacy-preserving Federated Learning that provides theoretical privacy guarantees based on Differential Privacy. We experimentally evaluate our proposal for in-hospital mortality prediction using a real dataset, containing Electronic Health Records of about one million patients.

  min Indeed, the convex L1-norm usually approximates the non-convex L0-norm well, and the relaxed optimization problem can be efficiently solved with any convex optimization technique[START_REF] Jacques | Compressed sensing: When sparsity meets sampling[END_REF] (e.g., with an LP solver).When the measurements y are noisy (i.e., y = Θs + z, where z ∈ R m is the additional bounded iid noise, i.e. z 2 ≤ κ), then the following convex quadratic variant of BP called Basis Pursuit Denoising (BPDN) is rather considered:

	R(y, κ) = arg min s	s 1 s.t.	y -Θs 2 ≤ κ
	and therefore
	D(y, n) = Ψ arg min s	1 2	y -Θs 2 2 + λ s 1 ,	(2.4)
				s	s 0 s.t. y = Θs
	Since this optimization problem is NP-complete [Nat95; JV10], it is further relaxed into the
	following slightly different problem called Basis Pursuit (BP) [CDS01]:
		arg min s	s 1 s.t. y = Θs
					2.3 Compressive Sensing

  Summary of the attacks which are considered in our Security analysis introduced in Chapter 6. The description of all the attacks can be found there.

		Attack Approaches
		Targeted Poisoning Untargeted Poisoning Model Poisoning Data Poisoning
	Attacks	Random Update Ascent Gradient In-Backdoor Out-Backdoor
	Tab. 3.1:

  • • , n}} of m random integer values such that m ≤ n based on the seed ζ

20 ∆ w k t =Sample m elements from ∆w k t by taking each element of G as a coordinate Output: The sampled Model update ∆ w k t

1

  Output:The sampled Model update Φ∆w k

		t
	Compression ratio (r) Algorithms	Performance Accuracy Round Cost (Megabit)
		FL-RND		0.73	192		8.52
	0.05	FL-FREQ	0.73	189		8.38
		FL-CS		0.82	200		8,87
		FL-RND		0.78	200		17.74
	0.1	FL-FREQ	0.78	197		17.48
		FL-CS		0.85	199		17.65
		FL-RND		0.82	200		35,49
	0.2	FL-FREQ	0.82	195		34,60
		FL-CS		0.87	193		34,24
	1.0	FL-STD		0.87	191		169.44
	1.0	Sign-SGD	0.85	200		332.67
	Compression ratio (r) Algorithms	Performance Bal_Acc AUROC Round Cost(Megabit)
		FL-RND		0.60	0.69	99	4.73
	0.05	FL-FREQ		0.69	0.76	100	4.78
		FL-CS		0.73	0.80	100	4.78
		FL-RND		0.66	0.73	100	9.56
	0.1	FL-FREQ		0.71	0.78	100	9.56
		FL-CS		0.73	0.81	87	8.31
		FL-RND		0.69	0.76	100	19.11
	0.2	FL-FREQ		0.72	0.80	100	19.11
		FL-CS		0.73	0.81	74	14.14
	1.0	FL-STD		0.74	0.82	99	94.62
	1.0	Sign-SGD		0.73	0.79	39	58.37

Tab. 4.2: Summary of results on Fashion-MNIST dataset using the FL-CS scheme.

Tab. 4.3: Summary of results on Medical dataset using the FL-CS scheme.

Table 4 .

 4 5).

							Performance
	r		Algorithms	Accuracy Round	Downstream Cost	Upstream Cost
								(Kilobyte)	(Kilobyte)
			FL-BASIC	0.65	193		21402.03	107
	0.5%	FL-CS		0.57	185		20514.9	102.56
			FL-TOP		0.82	200		110.88	110.88
			FL-BASIC	0.78	196		21734.70	1086.73
	5%	FL-CS		0.82	200		22178.27	1108.91
			FL-TOP		0.84	200		1108.91	1108.91
			FL-BASIC	0.81	196		21734.70	2173.47
	10%	FL-CS		0.85	182		20182.22	2018.22
			FL-TOP		0.85	199		2206.74	2206.74
	100%	FL-STD FL-SIGN	0.86 0.84	200 197		22178.27 21845.59	22178.27 682.67
							Performance
	r	Algorithms	Bal_Acc AUROC Round	Downstream Cost	Upstream Cost
								(Kilobyte)	(Kilobyte)
		FL-BASIC		0.51	0.51	99	11829.42	11.82
	0.1%		FL-CS		0.53	0.55	100	11948.91	11.94
			FL-TOP	0.69	0.76	68	8.12	8.12
		FL-BASIC		0.72	0.80	100	11948.91	597.45
	5%		FL-CS		0.73	0.81	98	11709.93	585.5
			FL-TOP	0.72	0.80	95	567.57	567.57
		FL-BASIC		0.74	0.81	100	11948.91	1194.89
	10%		FL-CS		0.74	0.82	100	11948.91	1194.89
			FL-TOP	0.74	0.82	90	1075.40	1075.40
	100%	FL-STD FL-SIGN		0.74 0.72	0.82 0.79	99 68	11829.42 8125.26	11829.42 253.91

Tab. 4.4: Summary of results on Fashion-MNIST dataset using the FL-TOP scheme.

  = 12) then the probability that ||z k -µ k ||∞ cannot be bounded by 12 √ nσ per client is less than 2 -80 even if |K| = 1 and n = 10 7 . Thus, a client needs to transfer n•log 2 2 log 2 ((12 √ nσ+max k ||µ k ||∞)|K|)

	1 Server:
	2	Initialize common model w 0
	3	for t = 1 to T cl do
	4	Select K clients randomly
	5	for each client k in K do
	6 7	end	∆w k t = Client k (w t-1 )
	8	wt = w t-1 + γ • sign	k ∆w k t
	9	end
	10 Client k (w):
	11	w k t-1 = w
	12	∆w k t = SGD(D k , w k t-1 , T gd ) -w k t-1
		Output: Enc K k DG sign ∆w k t ,	√	nIσ/ |K|
	(i.e., t

2 implies that if ξ = √ nσ/ |K| > 3.51 then 1+ν 1-ν < 3 2 and Pr z∼DG(µ, √ nσI/ √ |K|) [||z -µ||∞ ≥ t √ nσ] ≤ 3ne -|K|t 2 /2 after applying the union bound. For example, if m = 2 log 2 (12 √ nσ|K|) Algorithm 9: FL-SIGN-DP: Federated Learning with Client Privacy

  FL-CS-DP is described in Alg. 11. Client-level differential privacy requires each client to add Gaussian noise to the compressed model updates. In particular, each client first calculates c

	k t =
	C(∆w k t , m) (in Line 19), which is then clipped (in Line 20) to obtain ĉk t with L2-norm at most S. Then,
	random noise z k

  • • , n}} of m random integer values such that m ≤ n based on the seed ζ

20

∆ w k t =Sample m elements from ∆w k t by taking each element of G as a coordinate 21

  Summary of results on Fashion-MNIST dataset using the FL-CS-DP scheme.

	Compression ratio (r)	Algorithms	Performance Accuracy Round Cost (Megabit)
			FL-RND-DP	0.73	196		8.69	0.99
	0.05		FL-FREQ-DP	0.72	200		8,87	1
			FL-CS-DP		0.78	197		8.74	1
			FL-RND-DP	0.77	199		17.65	1
	0.1		FL-FREQ-DP	0.76	200		17.74	1
			FL-CS-DP		0.73	101		8,96	0.84
			FL-RND-DP	0.80	199		35.31	1
	0.2		FL-FREQ-DP	0.79	200		35,49	1
			FL-CS-DP		0.66	150		26,61	0.92
	1.0		FL-STD-DP	0.61	25		22.18	0.69
	Tab. 5.3: Compression ratio (r)	Algorithms	Performance Bal_Acc AUROC Round Cost(Megabit)
		FL-RND-DP		0.60	0.69	100	4.78	1
	0.05	FL-FREQ-DP		0.65	0.72	100	4.78	1
			FL-CS-DP		0.69	0.76	100	4.78	1
		FL-RND-DP		0.65	0.72	100	9.56	1
	0.1	FL-FREQ-DP		0.67	0.74	100	9.56	1
			FL-CS-DP		0.69	0.76	99	9.46	1
		FL-RND-DP		0.67	0.74	99	18.92	1
	0.2	FL-FREQ-DP		0.69	0.76	100	19.11	1
			FL-CS-DP		0.68	0.74	64	12.23	0.92
	1.0	FL-STD-DP		0.70	0.77	93	88.88	0.99

Tab. 5.4: Summary of results on Medical dataset using the FL-CS-DP scheme.

  (see[START_REF] Ács | I Have a DREAM! (DiffeRentially privatE smArt Metering)[END_REF][START_REF] Bonawitz | Practical Secure Aggregation for Federated Learning on User-Held Data[END_REF] for details). Here the modulo is taken element-wise and p = 2 log 2 (max k ||∆ ŵk t +z k ||∞|K|) .

	1/ max 1,	||∆w k t || 2 S	Let γ k t =

TOP-DP: Private and Bandwidth-Efficient Federated Learning via Constraint where EncK k (∆ ŵk t + z k ) = ∆ ŵk t + z k + K k mod p and k K k = 0

  Summary of results on Medical dataset using the FL-TOP-DP scheme.

					Performance
	r	Algorithms	Bal_Acc AUROC Round	Downstream Cost	Upstream Cost
						(Kilobyte)	(Kilobyte)
		FL-BASIC-DP	0.50	0.49	100	11948.91	11.94	1
	0.1%	FL-CS-DP	0.51	0.51	99	11829.42	11.82	1
		FL-TOP-DP	0.69	0.76	85	10.15	10.15	0.97
		FL-BASIC-DP	0.69	0.76	100	11948.91	597.45	1
	5%	FL-CS-DP	0.69	0.76	100	11948.91	597.45	1
		FL-TOP-DP	0.68	0.75	23	137.41	137.41	0.79
		FL-BASIC-DP	0.69	0.76	99	11829.42	1182.94	1
	10%	FL-CS-DP	0.69	0.76	96	11470.95	1147.09	0.99
		FL-TOP-DP	0.68	0.74	23	274.82	274.82	0.79
	100%	FL-STD-DP FL-SIGN-DP	0.66 0.63	0.72 0.68	62 97	7408.32 11590,44	7408.32 7968,43	0.91 1.0
		Tab. 5.6:

  6.1.1.1 Random Update Attack In this attack, malicious clients, whose numbers might vary as shown later, use random updates. More specifically, instead of the true model update ∆w k t , each malicious client k generates a random update ∆ ŵk t in all time slots t [BEGS17], where ∆ ŵk t is drawn from an isotropic Gaussian distribution G(0, σ Adv I) with mean zero and variance σ 2

  Random update attack on FL-SIGN, FL-CS, FL-TOP and FL-STD with the MNIST dataset depending on the fraction of malicious nodes. σ Adv = 200. The table represents the best accuracy over 100 rounds. "-" means that the algorithm does not converge. Random update attack on FL-SIGN, FL-CS, FL-TOP and FL-STD with the IMDB dataset depending on the fraction of malicious nodes. σ Adv = 200. The table represents the best accuracy over 100 rounds. "-" means that the algorithm does not converge. Table 6.3 and 6.4 show the best accuracy of the global model over 100 rounds when the adversary aims to degrade the average model performance by performing gradient ascent on its own training data. With the MNIST dataset (in Table

	Tab. 6.2: 10% 20% 40% 60%
	FL-STD	-	-	-	-
	FL-CS	-	-	-	-
	FL-TOP	-	-	-	-
	FL-SIGN 0.86 0.86 0.54	-
	6.2.1.2 Gradient Ascent Attack
	Tab. 6.1: 10% 20% 40% 60%
		FL-STD	-	-	-	-
		FL-CS	-	-	-	-
		FL-TOP	-	-	-	-
		FL-SIGN 0.98 0.98 0.94	-

  Gradient ascent attack on FL-SIGN, FL-CS, FL-TOP and FL-STD with the MNIST dataset. η Adv = 10. The table represents the best accuracy over 100 rounds. "-" means that the algorithm does not converge. Gradient ascent attack on FL-SIGN, FL-CS, FL-TOP and FL-STD with the IMDB dataset. η Adv = 20. The table represents the best accuracy over 100 rounds. "-" means that the algorithm does not converge.

	FL-SIGN 0.98 0.98 0.79	-
	Tab. 6.3: 10% 20% 40% 60%
	FL-STD	-	-	-	-
	FL-CS	-	-	-	-
	FL-TOP	-	-	-	-
	FL-SIGN 0.86 0.72 0.52	-
	Tab. 6.4: 6.2.2 Backdoor Attacks
	6.2.2.1 In-backdoor Attack

  Out-backdoors attack on FL-SIGN, FL-CS, FL-TOP and FL-STD with the MNIST dataset. η Adv is set to 1 (no boosting). The table displays the global model accuracy as well as the model's prediction rate to misclassify the out-backdoor class "0" to the targeted class "1" (attack accuracy). We choose the compression ratio r for FL-CS and FL-TOP such that each scheme reaches the same accuracy as FL-STD on the same settings but without the attack. Therefore, r is set to 5% and 0.5%, respectively. Out-backdoors attack on FL-SIGN and FL-STD with the CIFAR dataset. η Adv is set to 1 (no boosting). The table displays the global model accuracy as well as the model's prediction

		10% 20% 40%
	FL-SIGN	Model accuracy 0.99 0.99 0.99 Attack accuracy 0.19 0.87 0.99
	FL-STD	Model accuracy 0.99 0.99 0.99 Attack accuracy 0.92 0.99 0.99
	FL-CS	Model accuracy 0.99 0.99 0.99 Attack accuracy 0.83 0.95 0.99
	FL-TOP	Model accuracy 0.99 0.99 0.99 Attack accuracy 0.49 0.93 0.99
	Tab. 6.7: 10% 20% 40%
	FL-SIGN	Model accuracy 0.91 0.91 0.92 Attack accuracy 0.66 0.74 0.93
	FL-STD	Model accuracy 0.92 0.92 0.90 Attack accuracy 0.72 0.86 0.95
	FL-CS	Model accuracy 0.90 0.89 0.89 Attack accuracy 0.72 0.80 0.96
	FL-TOP	Model accuracy 0.91 0.92 0.91 Attack accuracy 0.70 0.79 0.95
	Tab. 6.8:

  In-backdoor attack on FL-SIGN-DP and FL-SIGN with MNIST dataset. The table depicts the global accuracy convergence and the accuracy of the label "5" which is under attack. In-backdoor attack on FL-SIGN and FL-SIGN-DP with Fashion-MNIST dataset. The table depicts the global accuracy convergence and the accuracy of the label "Sandal" which is under attack.

	ε = 1	Model accuracy Accuracy on digit class '5'	0.89 0.90 0.90 0 0 0
	ε = 2	Model accuracy Accuracy on digit class '5'	0.89 0.90 0.90 0 0 0
	ε = 4	Model accuracy Accuracy on digit class '5'	0.89 0.90 0.90 0 0 0
	FL-SIGN	Model accuracy Accuracy on digit class '5' 0.97 0.95 0.98 0.98 0.90 0
	Tab. 6.9: 10% 20% 40%
	ε = 1	Model accuracy Accuracy on Sandal class	0.77 0.79 0.80 0 0 0
	ε = 2	Model accuracy Accuracy on Sandal class	0.77 0.79 0.80 0 0 0
	ε = 4	Model accuracy Accuracy on Sandal class	0.77 0.79 0.80 0 0 0
	FL-SIGN	Model accuracy Accuracy on Sandal class 0.90 0.84 0.83 0.84 0.79 0
	Tab. 6.10:

  Out-backdoors attack on FL-SIGN-DP and FL-SIGN with Fashion-MNIST dataset. The table displays the global model accuracy as well as the model's prediction rate to misclassify the out-backdoor class "T-shirt/Top" to the targeted class "Trouser" (attack accuracy).

			2%	10% 20% 40%
	ε = 1	Model accuracy 0.98 0.98 0.99 0.99 Attack accuracy 0.98 0.99 0.99 1
	ε = 2	Model accuracy 0.98 0.98 0.98 0.99 Attack accuracy 0.99 0.98 0.99 0.99
	ε = 4	Model accuracy 0.98 0.98 0.99 0.99 Attack accuracy 0.99 0.99 0.99 0.99
	FL-SIGN	Model accuracy 0.98 0.98 0.98 0.99 Attack accuracy 0 0.97 0.99 0.99
	Tab. 6.11: Out-backdoors attack on FL-SIGN-DP and FL-SIGN with MNIST dataset. The table displays the global
	model accuracy as well as the model's prediction rate to misclassify the out-backdoor class "0" to the
			targeted class "1" (attack accuracy).
			10% 20% 40%
	ε = 1		Model accuracy 0.87 0.88 0.90 Attack accuracy 0.78 0.81 0.87
	ε = 2		Model accuracy 0.88 0.88 0.90 Attack accuracy 0.78 0.82 0.85
	ε = 4		Model accuracy 0.87 0.89 0.90 Attack accuracy 0.78 0.81 0.86
	FL-SIGN	Model accuracy 0.87 0.88 0.90 Attack accuracy 0 0.12 0.83
	Tab. 6.12:

  Summary of results on Fashion-MNIST dataset.

	Compression ratio (r)	Algorithms	Performance Accuracy Round Downstream Cost (Kilobyte) Upstream Cost (Kilobyte)
		FL-BASIC	0.14	111	12308.94	12.31	N/A
		FL-BAS-2	0.16	185	20514.9	20.51	N/A
		FL-BAS-3	0.27	200	22.17	22.17	N/A
		FL-BAS-4	0.17	200	22.17	22.17	N/A
		FL-CS	0.37	200	22178.27	22.17	N/A
		FL-TOPK-BIS	0.59	198	21.95	21.95	N/A
	0.1%	FL-TOP FL-BASIC-DP	0.78 0.14	199 167	22.06 18518.85	22.06 18.51	N/A 0.95
		FL-BAS-2-DP	0.14	124	13750.53	13.75	0.88
		FL-BAS-3-DP	-	-	-	-	-
		FL-BAS-4-DP	0.15	137	15.19	15.19	0.90
		FL-CS-DP	0.36	197	21845.59	21.84	1
		FL-TOPK-BIS-DP	0.59	196	21.73	21.73	0.99
		FL-TOP-DP	0.76	199	22.06	22.06	1
		FL-BASIC	0.65	193	21402.03	107	N/A
		FL-BAS-2	0.46	196	21734.70	108.66	N/A
		FL-BAS-3	0.73	200	110.88	110.88	N/A
		FL-BAS-4	0.41	197	109.22	109.22	N/A
		FL-CS	0.57	185	20514.9	102.56	N/A
		FL-TOPK-BIS	0.76	200	110.88	110.88	N/A
	0.5%	FL-TOP FL-BASIC-DP	0.82 0.59	200 200	110.88 22178.27	110.88 110.88	N/A 1
		FL-BAS-2-DP	0.38	200	22178.27	110.88	1
		FL-BAS-3-DP	0.56	200	110.88	110.88	1
		FL-BAS-4-DP	0.33	200	110.88	110.88	1
		FL-CS-DP	0.53	200	22178.27	110.88	1
		FL-TOPK-BIS-DP	0.68	184	102.01	102.01	0.97
		FL-TOP-DP	0.81	200	110.88	110.88	1
		FL-BASIC	0.71	194	21512.92	215.12	N/A
		FL-BAS-2	0.59	200	22178.27	221.77	N/A
		FL-BAS-3	0.76	200	221.77	221.77	N/A
		FL-BAS-4	0.56	195	216.23	216.23	N/A
		FL-CS	0.69	200	22178.27	221.77	N/A
		FL-TOPK-BIS	0.79	197	218.45	218.45	N/A
	1%	FL-TOP FL-BASIC-DP	0.83 0.65	200 197	221.77 21845.59	221.77 218.45	N/A 1
		FL-BAS-2-DP	0.62	198	21956.48	219.56	1
		FL-BAS-3-DP	0.66	198	219.56	219.56	1
		FL-BAS-4-DP	0.52	198	219.56	219.56	1
		FL-CS-DP	0.66	189	20958.46	209.58	0.98
		FL-TOPK-BIS-DP	0.70	174	192.94	192.94	0.96
		FL-TOP-DP	0.81	183	202.92	202.92	0.97
		FL-BASIC	0.78	196	21734.70	1086.73	N/A
		FL-BAS-2	0.72	199	22067.38	1103.36	N/A
		FL-BAS-3	0.81	199	1103.36	1103.36	N/A
		FL-BAS-4	0.76	196	1086.73	1086.73	N/A
		FL-CS	0.82	200	22178.27	1108.91	N/A
		FL-TOPK-BIS	0.83	196	1086.73	1086.73	N/A
	5%	FL-TOP FL-BASIC-DP	0.84 0.76	200 195	1108.91 21623.81	1108.91 1081.18	N/A 0.99
		FL-BAS-2-DP	0.72	195	21623.81	1081.18	0.99
		FL-BAS-3-DP	0.76	199	1103.36	1103.36	1
		FL-BAS-4-DP	0.75	191	1059.01	1059.01	0.99
		FL-CS-DP	0.78	160	17742.61	887.13	0.94
		FL-TOPK-BIS-DP	0.71	152	842.77	842.77	0.92
		FL-TOP-DP	0.81	152	842.77	842.77	0.92
		FL-BASIC	0.81	196	21734.70	2173.47	N/A
		FL-BAS-2	0.78	199	22067.38	2206.74	N/A
		FL-BAS-3	0.82	195	2162.38	2162.38	N/A
		FL-BAS-4	0.79	200	2217.83	2217.83	N/A
		FL-CS	0.85	182	20182.22	2018.22	N/A
		FL-TOPK-BIS	0.84	196	2173.47	2173.47	N/A
	10%	FL-TOP FL-BASIC-DP	0.85 0.79	199 189	2206.74 20958.46	2206.74 2095.85	N/A 0.98
		FL-BAS-2-DP	0.77	189	20958.46	2095.85	0.98
		FL-BAS-3-DP	0.79	183	2029.31	2029.31	0.97
		FL-BAS-4-DP	0.78	195	2162.38	2162.38	0.99
		FL-CS-DP	0.72	167	18518.85	1851.89	0.95
		FL-TOPK-BIS-DP	0.69	138	1530.30	1530.30	0.90
		FL-TOP-DP	0.80	157	1740.99	1740.99	0.93
	100%	FL-STD FL-STD-DP	0.86 0.56	200 60	22178.27 6653.48	22178.27 6653.48	N/A 0.76
		Tab. 8.11:

https://blog.chromium.org/2019/08/potential-uses-for-privacy-sandbox.html

https://www.melloddy.eu

1.2 Contributions

1.4 Publications

For instance, for δ U = 0.2, C < 4.2 and D < 8.5

Chapter 2 Background

We refer to the model parameters of the K most largest updates as Top-K parameters.

3.2 Bandwidth Efficient Machine Learning

Chapter 3 Related Work

3.3 Machine Learning and Security

We noticed experimentally that γ should be selected between range 0.001 and 0.005. And it should be increased when DP is used.4.1 Reducing Bandwidth by Compressing the updates

4.1 Reducing Bandwidth by Compressing the updates

Based on the accuracy

Based on the balanced accuracy[START_REF] Henning Brodersen | The balanced accuracy and its posterior distribution[END_REF][START_REF] Bekkar | Evaluation measures for models assessment over imbalanced data sets[END_REF]

4.2 Reducing Bandwidth by Compressing the Model

weight values for downstream and update/gradients for upstream traffic

More baselines are considered but due to the lack of space, We have decided to present only those which return the best results. All other results can be found in Tables 8.11,8.12,8.13.

Reduced to 24 patients when we train via downsampling with 12 patients for each class 4.2 Reducing Bandwidth by Compressing the Model

Tab. 4.5: Summary of results on Medical dataset using the FL-TOP scheme.

4.3 Conclusion

A model is trained for gender classification on the LFW dataset. The adversary's goal is to infer from the model updates whether a specific group of individuals in a client's dataset are black.

The sensitivity S = √ n and γ = 0.005 for FL-SIGN-DP. For FL-STD-DP, the server computes the median L2-norm value over N L2-norm values received during an additional initialization round. Hence, S is set to 1.73 and 2.15 for MNIST and Fashion-MNIST, respectively.

5.2 FL-SIGN-DP: Private and Bandwidth-Efficient Federated Learning via Quantization

5.3 FL-CS-DP: Private and Bandwidth-Efficient Federated Learning via Compressive Sensing

More baselines are considered but we have decided to present only those which return the best results. All other results can be found in Tables 8.11,8.12,8.13. 5.4 FL-TOP-DP: Private and Bandwidth-Efficient Federated Learning via Constraint

See Appendix 8.4.2 for more details.

5.5 Conclusion

Chapter 5 Designing Private and Bandwidth Efficient Federated Learning Schemes

Due to quantization, boosting is not possible on FL-SIGN.6.2 Security Analysis of FL-SIGN, FL-CS and FL-TOP

we also removed all birds and trucks from the training data, in order to limit the bias between classes.6.2Security Analysis of FL-SIGN, FL-CS and FL-TOP

6.3 FL-SIGN-DP Security Analysis

6.4 Conclusion

but of course without overfitting on their local testing data

refer to Section 2.1 for details.7.2 Future Research Directions

Bibliography

https://www.premierinc.com/newsroom/education/premier-healthcare-database-whitepaper 8.3 Experimental Set-up

We have also tested weighted loss function and oversampling techniques. Experimentally we observed that downsampling outperforms the other techniques whatever the considered scheme.

https://www.resdac.org/cms-data/variables/claim-inpatient-admission-type-code-ffs

https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.MinMaxScaler.html

We consider 5010 hospitals with FL-TOP and FL-TOP-DP, instead of 5011. The dataset of the non-selected hospital is used as public data to fix the updatable weights at the server side. 8.4 Medical Data: Data Pre-Processing & Experimental Set-up Details

10% 20% 40%

FL-SIGN Model accuracy 0.99 0.99 0.99 Accuracy on digit class '5' 0.99 0.99 0.99

FL-STD

Model accuracy 0.99 0.99 0.99 Accuracy on digit class '5' 0.99 0.99 0.99

FL-CS

Model accuracy 0.99 0.99 0.97 Accuracy on digit class '5' 0.98 0.96 0.74

FL-TOP

Model accuracy 0.99 0.99 0.97 Accuracy on digit class '5' 0.98 0.95 0.83 Tab. 6.5: In-backdoor attack on FL-SIGN, FL-CS, FL-TOP and FL-STD with the MNIST dataset, η Adv is set to 7, 3, 1 for 10%, 20%, 40% respectively. The table depicts the global accuracy convergence and the accuracy of the label "5" which is under attack. We choose the compression ratio r for FL-CS and FL-TOP such that each scheme reaches the same accuracy as FL-STD on the same settings but without the attack. Therefore, r is set to 5% and 0.5%, respectively. Note also, that we do not use boosting with FL-CS to not impact the sparsity of the model's update.

10% 20% 40%

FL-SIGN Model accuracy 0.86 0.84 0.82 Accuracy on airplane class 0.80 0.76 0.57

FL-STD

Model accuracy 0.86 0.80 0.81 Accuracy on airplane class 0.55 0 0

FL-CS

Model accuracy 0.81 0.80 0.74 Accuracy on airplane class 0.81 0.71 0.30

FL-TOP

Model accuracy 0.82 0.81 0.80 Accuracy on airplane class 0.42 0.35 0.18 Tab. 6.6: In-backdoor attack on FL-SIGN, FL-CS, FL-TOP and FL-STD with the CIFAR dataset, η Adv is set to 7, 4, 2 for 10%, 20%, 40% respectively. The table depicts the global accuracy convergence and the accuracy of the label "airplane" which is under attack. We choose the compression ratio r for FL-CS and FL-TOP such that each scheme reaches the same accuracy as FL-STD on the same settings but without the attack. Therefore, r is set to 60% and 20%, respectively. Note also, that we do not use boosting with FL-CS to not impact the sparsity of the model's update.

since only malicious clients have samples from the backdoor class, the detection of this attack is quite challenging. Tables 6.7 and 6.8 display the global model accuracy as well as the model's prediction rate to misclassify the out-backdoor class to the targeted class (attack accuracy) for MNIST and CIFAR, respectively (values are chosen based on the best model accuracy over 100 rounds with MNIST and 300 rounds with CIFAR). We consider different fraction of malicious nodes. The results show that the model accuracy is similar for both datasets and schemes, but FL-SIGN is much more robust against the attacks than other schemes. In fact, with 10% of malicious nodes, the attack accuracy on the MNIST dataset is very low for FL-SIGN (19%) whereas it is quite large for FL-STD (92%). We obtained similar

Medical Data: Data Pre-Processing & Experimental Set-up Details

This section describes the experimental setting which is used to evaluate the accuracy and the privacy of our proposals on the Medical dataset.

Medical Data: Data Pre-Processing

1. Features normalization: we extract from the dataset the values of each feature represented in Table 8.6. For gender, we use one-hot encoding: Male, Female and Unknown. Similarly, for admission type we use 4 features: Emergency, Urgent, Trauma Center, and Unknown 3 . For drugs and ICD9 codes, we extract 24,419 features which correspond to the different drugs (name and dosage), procedures codes and diagnosis codes. As in [START_REF] Avati | Improving palliative care with deep learning[END_REF], we also removed all the features which appear on less than 100 patients' records, hence, the number of features was reduced to 7,280 features. A given patient receives only a few of the possible drugs served, resulting in a very sparse patient's record. We use a MinMax normalization for age and MRCI in order to rescale the values of these features between 0 and 1 (using MinMaxScaler class of scikit-learn 4 ). The labels that we consider are boolean: true means that the patient died during his hospital stay while false means she survived.

Patients filtering:

We consider patient and drug information of the first day at the hospital so that we can make predictions 24 hours after admission (as commonly found in the literature [Ra18; FGLB18]). We filter out the pregnant and new-born patients because the medication types and admission services are not the same for theses two categories of patients. Our model prediction is built without patients' historical medical data. This has the advantage to require minimum patient's information and to work for new patients.

Hospitals filtering:

The dataset contains 415 hospitals for a total size of 1,271,733 records. We split randomly the dataset into disjoint training and testing data (80% and 20% respectively). The final dataset for testing contains 254,347 patients, with 7,882 deceased patients and 246,465 non-deceased patients (see Table 8.7).

Tab. 8.2: Common environment of the privacy part. γ = 0.005 and T cl = 200. For FL-STD-DP, S is set to 1.73 and 2.15 for MNIST and Fashion-MNIST, respectively. For FL-SIGN-DP, S is fixed to √ n.

``````````À

Computational Environment

Our experiments were performed on a server running Ubuntu 18.04 LTS equipped with an Intel(R) Xeon(R) Silver 4114 CPU @ 2.20GHz, 192GB RAM, and two NVIDIA Quadro P5000 GPU card of 16 Go each. We use Keras 2.2.0 [Cho+15a] with a TensorFlow backend 1.12.0 [TensorFlow] and Numpy 1.14.3 [START_REF] Oliphant | A guide to NumPy[END_REF] to implement our models and experiments. We use Python 3.6.5 and our code runs on a Docker container to simplify the reproducibility.

Features Descriptions

Age Value in the range of 15 and 89 Gender Male, Female or Unknown Admission type Emergency, Urgent, Trauma Center: visits to a trauma center/hospital or Unknown MRCI Medication regimen complexity index score (ranging from 2 to 60)

Drugs and ICD9 codes

Drugs given to the patient on the 1 st day of hospitalization. The ICD9 codes [START_REF] Marta | ICD-9-CM: International Classification of Diseases, Ninth Revision, Clinical Modification[END_REF] are composed of procedures and diagnosis codes, the first gives details about the medical procedures performed on the patient and the second about the doctor's diagnosis of the patient. There is a total of 24,419 possible drugs and ICD9 codes.