Yann Fraboni

Richard Vidal

Laetitia Kameni

Marco Lorenzi

Sequential Informed Federated Unlearning: Efficient and Provable Client Unlearning in Federated Optimization

The aim of Machine Unlearning (MU) is to provide theoretical guarantees on the removal of the contribution of a given data point from a training procedure. Federated Unlearning (FU) consists in extending MU to unlearn a given client's contribution from a federated training routine. Current FU approaches are generally not scalable, and do not come with sound theoretical quantification of the effectiveness of unlearning. In this work we present Informed Federated Unlearning (IFU), a novel efficient and quantifiable FU approach. Upon unlearning request from a given client, IFU identifies the optimal FL iteration from which FL has to be reinitialized, with unlearning guarantees obtained through a randomized perturbation mechanism. The theory of IFU is also extended to account for sequential unlearning requests. Experimental results on different tasks and dataset show that IFU leads to more efficient unlearning procedures as compared to basic re-training and state-of-the-art FU approaches.

Introduction

With the emergence of new data regulations, such as the EU General Data Protection Regulation (GDPR) [START_REF] Voigt | The eu general data protection regulation (gdpr). A Practical Guide[END_REF] and the California Consumer Privacy Act (CCPA) [START_REF] Harding | Understanding the scope and impact of the california consumer privacy act of 2018[END_REF], the storage and processing of sensitive personal data is often subject of strict constraints and restrictions. In particular, the "right to be forgotten" states that personal data must be erased upon request from the concerned individuals, with subsequent potential implications on machine learning models trained by using this data. Machine Unlearning (MU) is an emerging discipline that studies methods to ideally remove the contribution of a given data instance used to train a machine learning model. Current MU approaches are essentially based on routines that modify the model weights in order to guarantee the "forgetting" of a given data point, i.e. to obtain a model equivalent to an hypothetical one trained without this data point [START_REF] Cao | Towards making systems forget with machine unlearning[END_REF][START_REF] Bourtoule | Machine unlearning[END_REF].

Motivated by data governance and confidentiality concerns, Federated learning (FL) has gained popularity in the last years to allow data owners to collaboratively learn a model without sharing their respective data. Among the different FL approaches, federated averaging (FEDAVG) has emerged as the most popular optimization scheme [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]. An optimization round of FEDAVG requires data owners, also called clients, to receive from the server the current global model which they update before sending it back to the server. The new global model is then created as the weighted average of the client updates, according to their data ratio. FL communication design guarantees to clients that their data is solely used to compute their model update, while theoretical work guarantees FL convergence to a stationary point of the clients' joint optimization problem [START_REF] Wang | Tackling the objective inconsistency problem in heterogeneous federated optimization[END_REF][START_REF] Li | On the convergence of fedavg on non-iid data[END_REF].

With the current deployments of FL in the real-world, it is of crucial importance to extend MU to guarantee the unlearning of clients wishing to opt-out from a collaborative training routine. This is not straightforward, since current MU schemes have been proposed essentially in the centralized learning setting, and cannot be seamlessly applied to the federated one. For example, several MU methods require the estimation of the Hessian of the loss function [START_REF] Guo | Certified data removal from machine learning models[END_REF][START_REF] Izzo | Approximate data deletion from machine learning models[END_REF]Golatkar et al., 2020aGolatkar et al., ,b, 2021)), an operation which is notoriously computationally heavy and intractable for high dimensional models. Moreover, sharing the Hessian would require clients to share with the server additional information about their data, thus exposing the federated setting to information leakage and attacks, for example under the form of model inversion [START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF]. Alternative MU methods draw from the concept of differential privacy [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] and are based on a Gaussian noise perturbation of the trained model [START_REF] Neel | Descent-to-delete: Gradient-based methods for machine unlearning[END_REF][START_REF] Guo | Certified data removal from machine learning models[END_REF][START_REF] Gupta | Adaptive machine unlearning[END_REF]. The magnitude of the noise perturbation should be estimated directly from the clients data, which is by construction inaccessible to the server in the FL regime. We also note that while recent federated unlearning (FU) methods have been proposed to unlearn a client from the global FL model [START_REF] Liu | Federaser: Enabling efficient client-level data removal from federated learning models[END_REF][START_REF] Wang | Federated unlearning via class-discriminative pruning[END_REF][START_REF] Halimi | Federated unlearning: How to efficiently erase a client in fl?[END_REF][START_REF] Wu | Federated unlearning with knowledge distillation[END_REF], these approaches do not come with theoretical guarantees on the effectiveness of the unlearning.

The main contribution of this work consists in Informed Federated Unlearning (IFU), a novel efficient FU approach to unlearn a client's contribution with quantifiable unlearning guarantees. IFU requires minimal additional computations to the server in a standard FEDAVG procedure. Specifically, the server quantifies at every optimization round each client's contribution to the global model. Upon receiving an unlearning request from a client, the server identifies in the FL training history the optimal FL iteration and associated intermediate global model from which re-initializing the unlearning procedure. Unlearning guarantees are provided by introducing a novel randomized mechanism to perturb the selected intermediate model with client-specific noise. We also extend IFU to Sequential Informed Federated Unlearning (SIFU), to account for realistic unlearning scenarios where the server receives sequential unlearning requests from one or more clients at different times [START_REF] Neel | Descent-to-delete: Gradient-based methods for machine unlearning[END_REF][START_REF] Gupta | Adaptive machine unlearning[END_REF]. This manuscript is structured as follows. In Section 2, we provide formal definitions for MU, FL, and FU, and introduce the randomized mechanism with associated unlearning guarantees. In Section 3, we introduce sufficient conditions for IFU to unlearn a client from the FL routine (Theorem 2). In Section 4, we extend IFU to the sequential unlearning setting with Sequential IFU (SIFU). Finally, in Section 5, we experimentally demonstrate on different tasks and datasets that SIFU leads to more efficient unlearning procedures as compared to basic re-training and state-of-the-art FU approaches.

Background and Related Work

In Section 2.1, we introduce the state-of-the art behind Machine Unlearning, while in Section 2.2, we introduce FL and FEDAVG. Finally, we introduce Federated Unlearning (FU) in Section 2.3.

Machine Unlearning

Let us consider a dataset D composed of two disjoint datasets: D f , the cohort of data samples on which unlearning must be applied after FL training, and D k , the remaining data samples. Hence, we have D = D f ∪ D k . We also consider M(D), the ML model parameters resulting from training with optimization scheme M on dataset D. We introduce in this section the different unlearning baselines and methods currently used to unlearn D f from the trained model M(D).

MU through retraining. Within this setting, a new training is performed from scratch with only D k as training data. As the initial model contains no information from D f , the new trained model M(D k ) also contains no information from D f . We note however that this procedure wastes the contribution of D k already available by training originally on D. Hence, this method is considered sub-optimal, and represents a basic baseline for unlearning approaches.

MU through fine-tuning. Fine-tuning on the remaining data D k has been proposed as a practical approach to unlearn the specificities of D f . However, fine-tuning does not provide guarantees about the effectiveness of the unlearning. We provide an example of this issue in Appendix A.

MU through model scrubbing. Another unlearning approach consists in applying a "scrubbing" transformation h to the model M(D) such that the resulting model is as close as possible to the one that would be trained with only D k , i.e. h(M(D)) ≈ M(D k ) [START_REF] Ginart | Making ai forget you: Data deletion in machine learning[END_REF]. To define a scrubbing method h, existing work mostly relies on the following Assumption 1, which considers a quadratic approximation of the loss function.

Assumption 1. For model parameters θ and ϕ, the gradient of the loss function of a given data point

D x satisfies ∇f Dx (ϕ) = ∇f Dx (θ) + H Dx (θ)(ϕ -θ), (1)
where H Dx (θ) is positive semi-definite.

The scrubbed model is the new optimum obtained when unlearning data samples in D f . Hence, under Assumption 1, the new optimum can be obtained by setting

∇f D k (h D k (θ)) = 0, which gives h D k (θ) = θ -H -1 D k (θ)∇f D k (θ). (2)
With equation ( 2), h reduces to performing a Newton step, and has been derived in previous MU works [START_REF] Guo | Certified data removal from machine learning models[END_REF][START_REF] Izzo | Approximate data deletion from machine learning models[END_REF]Golatkar et al., 2020aGolatkar et al., ,b, 2021;;Mahadevan and Mathioudakis, 2021a) under different theoretical assumptions that can be generalized with Assumption 1.

The main drawback behind the use of the scrubbing function (2) is the computation of the Hessian, which can be unfeasible for high dimensional model. Finally, the scrubbing function ( 2) is often coupled with Gaussian noise perturbation on the resulting weights (Golatkar et al., 2020a(Golatkar et al., ,b, 2021)), to compensate the quadratic approximation of the loss function or the approximation of the Hessian.

MU through noise perturbation. This unlearning method consists in randomly perturbing the trained model M(D) to unlearn specificities from data samples in D f [START_REF] Neel | Descent-to-delete: Gradient-based methods for machine unlearning[END_REF][START_REF] Gupta | Adaptive machine unlearning[END_REF][START_REF] Mahadevan | Certifiable machine unlearning for linear models[END_REF]). The noise is set such that the guarantees of Definition 1 are satisfied, where (ϵ, δ) are parameters quantifying the unlearning guarantees. (4) [START_REF] Guo | Certified data removal from machine learning models[END_REF] shows the relationship between Definition 1 and the definition a randomized mechanism in differential privacy [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF][START_REF] Chen | Understanding gradient clipping in private sgd: A geometric perspective[END_REF].

Federated Optimization and FEDAVG

In FL, we consider a learning setup with M clients, and define I = {1, ..., M } as the set of indices of the participating clients. Each client owns a dataset D i composed of |D i | = n i data samples. We consider a loss f (x i,l , y i,l , θ) assessed on each data sample (x i,l , y i,l ) ∈ D i , and define a client's loss function as

f i (θ) := 1/n i ni l=1 f (x i,l , y i,l , θ).
We define for the joint dataset D I := ∪ i∈I D i the federated loss function

f I (θ) := 1 |D I | i∈I |D i |f i (θ).
(5)

FEDAVG [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF] optimizes the loss (5) with theoretical guarantees for FL convergence to a stationary point [START_REF] Wang | Tackling the objective inconsistency problem in heterogeneous federated optimization[END_REF][START_REF] Li | On the convergence of fedavg on non-iid data[END_REF]. At each iteration step n, the server sends the current global model parameters θ n to the clients. Each client updates the model by minimizing its local cost function f i (θ) with K SGD steps initialized on θ n . Subsequently each client returns the updated local parameters θ n+1 i to the server. The global model parameters θ n+1 at the iteration step n + 1 are then estimated as a weighted average, i.e.

θ n+1 = θ n + 1 |D| i∈I |D i | θ n+1 i -θ n . ( 6
)
Algorithm 1 provides the implementation of FEDAVG. For the rest of this work, we define the joint dataset for a subset of client I x ⊂ I as D Ix := ∪ i∈Ix D i .

Federated Unlearning

Existing works [START_REF] Liu | Federaser: Enabling efficient client-level data removal from federated learning models[END_REF][START_REF] Wang | Federated unlearning via class-discriminative pruning[END_REF][START_REF] Halimi | Federated unlearning: How to efficiently erase a client in fl?[END_REF][START_REF] Wu | Federated unlearning with knowledge distillation[END_REF] already consider the problem of unlearning a client from a model optimized through FE-DAVG. However, these works do not provide theoretical nor quantitative guarantees on the unlearning procedure.

Algorithm 1 FEDAVG(I, N ) 1: for n from 0 to N -1 do 2:

The server sends θ n to every client in I.

3:

Clients perform K SGDs to compute θ n+1 i .

4:

The server creates θ n+1 , equation (6). 5: end for 6: return the trained global model θ N Also, we note that standard MU methods cannot seamlessly be used in the federated setting. On one hand, federated unlearning (FU) with model scrubbing would require clients to perform only K = 1 SGD and share their Hessian with the server. Hence, model scrubbing decreases significantly FL convergence speed, while exposing the clients' data by sharing high order quantities with the risk of model inversion [START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF]. Moreover, the computation of the Hessian is unfeasible for highly dimensional models. On the other hand, existing MU approaches based on model perturbation require to retrain the model after the noise is added to the model's parameters. As such, retraining generally requires a significant amount of SGD steps to guarantee convergence to a new optimum, negatively affecting the effectiveness of the unlearning procedure.

In this work, we introduce a novel unlearning paradigm which avoids retraining the final model by identifying the optimal FL iteration where unlearning should be applied. Therefore, retraining is applied to an "early" version of the global model with reduced perturbation, thus minimizing the amount of required SGD steps to achieve convergence.

Unlearning a FL client with IFU

In this section, we develop our theory for the scenario where a model is trained with FEDAVG on the set of clients I, after which a client c requests unlearning of its own data. In Section 3.1, we define the sensitivity of the global model with respect to a client's contribution, and provide a bound relating this sensitivity to the FL procedure. In Section 3.2, we provide a tighter model sensitivity for some specific FL applications. Using Theorem 1, we introduce in Section 3.3 the perturbation procedure to unlearn a client c from the model trained with FEDAVG (Theorem 2). Finally, using Theorem 2, we introduce Informed Federated Unlearning (IFU) (Algorithm 2).

Theorem 1, Bounding the Model Sensitivity

As defined in Section 2.2, θ n+1 i is the local update of client i sent to the server after performing K SGD steps on its dataset D i after initialization with global model θ n . Given the contribution θ n+1 i -θ n of a client i, we define the overall FL increment after aggregations across the set of clients I as

∆(I, θ n ) := 1 |D I | i∈I |D i | θ n+1 i -θ n . (7)
By comparing increments obtained by training on the set of clients I, and on the set I -c := I \ {c} obtained after dropping a given client c, we define the bounded sensitivity after n server aggregations as

Ψ(n, c) := n-1 s=0 ∥∆(I, θ s ) -∆(I -c , θ s )∥ 2 , (8)
We show in Theorem 1 that the model sensitivity of FE-DAVG can be bounded by the bounded sensitivity (8).

Theorem 1. Under Assumption 1, the model sensitivity of FEDAVG when removing a client c after n server aggregations is defined as

α(n, c) := ∥FEDAVG(I, n) -FEDAVG(I -c , n)∥ 2 , ( 9
)
where FEDAVG(I, n) is the output of Algorithm 1, and

α(n, c) ≤ Ψ(n, c). (10)
Proof. See Appendix B.

Improving the Tightness of the Sensitivity Bound

Theorem 1 shows that the bounded sensitivity provides a bound for the model sensitivity, while the computation of (8) only requires the clients' updated models, which are already shared with the server by design in FEDAVG. Nevertheless, we note that the bounded sensitivity (8) does not necessarily faithfully represent the evolution of the sensitivity across FL rounds. For instance, this quantity does not properly account for the unlearning of previous clients contributions for s < n -1. Indeed, these contributions should decrease across iterations due to the subsequent server aggregations and new clients' local work. To account for this aspect, we provide a tighter lower bound by assuming strongly convex and regularized local loss function, leading to a tighter bound for the model sensitivity of FEDAVG (Corollary 1).

Corollary 1. Under Assumption 1, when considering that clients loss functions are µ-strongly convex and regularized with an L2 norm of weight λ, we have α(n, c) ≤ Ψ(n, c) and

Ψ(n, c) = n-1 s=0 (1 -η(λ + µ)) [(n-1)-s]K × ∥∆(I, θ s ) -∆(I -c , θ s )∥ 2 , ( 11
)
where η and K are respectively the clients' local learning rate and amount of local work.

Proof. See Appendix B.3.

The bounded sensitivity of Corollary 1 shows the following aspects.

(1) The importance of a client's contribution decreases through aggregation rounds.

(2) Since FL is guaranteed to converge to a stationary point [START_REF] Wang | Tackling the objective inconsistency problem in heterogeneous federated optimization[END_REF][START_REF] Li | On the convergence of fedavg on non-iid data[END_REF], so does the bounded sensitivity since λ + µ > 0.

(3) The bounded sensitivity is not necessarily inversely proportional to K. Indeed, due to data heterogeneity, with an increase in K every local model gets closer to its local optimum and the quantity

∥∆(I, θ n ) -∆(I -c , θ n )∥ 2 increases with the amount of local work K.
When clients have same data distribution, we retrieve ∆(I, θ n ) = ∆(I -c , θ n ), which yields null bounded sensitivity for every client, i.e. Ψ(n, c) = 0. We also note that the bound provided in Corollary 1 is tight, e.g. when considering identical eigenvalues for the Hessian of every local loss. More generally, the bound is tight in the limit case where the local learning rate of the clients is small.

We can draw an analogy between the bounded sensitivity (8) and client clustering in FL [START_REF] Sattler | Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints[END_REF]Fraboni et al., 2021a), where clients are clustered based on their contribution. In this work, the bounded sensitivity ( 8) is used instead to bound the sensitivity of the global model across rounds in FEDAVG.

Satisfying Definition 1

In this section, we introduce a randomized mechanism to provide guarantees for the unlearning of a given client c, where the magnitude of the perturbation process [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] is defined based on the sensitivity of Theorem 1. In practice, we define a Gaussian noise mechanism to perturb each parameter of global model θ n such that we achieve (ϵ, δ)-unlearning of client c for the resulting model, according to Definition 1. We give in Theorem 2 sufficient conditions for the noise perturbation to satisfy Definition 1.

Theorem 2. Defining σ(n, c) := [2 (ln(1.25) -ln(δ))] 1/2 ϵ -1 Ψ(n, c), ( 12
)
the noise perturbation σ(n, c)I θ applied to the global model θ n , where I θ is the identity matrix, achieves (ϵ, δ)unlearnig of client c according to Definition 1.

Proof. Follows directly from Theorem 1 coupled with Theorem A.1 of [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF].

We note that, according to Theorem 2, (ϵ, δ)-unlearning a client from a given global model requires a standard deviation for the noise that is client-specific and proportional to its bounded sensitivity.

Algorithm 2 Informed Federated Unlearning (IFU) DURING LEARNING WITH FEDAVG FEDAVG(I, N ) initialized on initial model θ 0 .

for n from 0 to N -1, and i from 1 to c do Compute Ψ(n, i), equation ( 8). end for WHEN UNLEARNING CLIENT c Require: c, ϵ, δ, σ, and amount of retraining steps Ñ .

1: Get Ψ * with equation ( 13).

2: Get T = arg max n (Ψ(n, c) ≤ Ψ * ) with eq. ( 14).

3: The new global model is θ = θ T + N (0, σ 2 I θ ). 4: Run FEDAVG(I -c , Ñ ) initialized on θ.
In what follows, the unlearning procedure will be defined with respect to the sensitivity threshold Ψ * related to the unlearning budget (ϵ, δ) and standard deviation σ:

Ψ * := [2 (ln(1.25) -ln(δ))] -1/2 ϵσ. ( 13
)

Informed Federated Unlearning (IFU)

Using the bounded sensitivity (8) and Theorem 2, we introduce Informed Federated Unlearning (IFU) to unlearn the contribution of client c ∈ I from a FL training procedure based on FEDAVG. Algorithm 2 provides the implementation of IFU on top of FEDAVG. We note that during the FL training, IFU requires the server to compute the bounded sensitivity metric Ψ(n, i) from each client's contribution θ n+1 i and current global model θ n . These quantities are tracked throughout FL iterations and are used to identify the optimal unlearning strategy after request from a client c.

To unlearn client c, the server identifies the unlearning index T associated to the history of bounded sensitivity metrics, i.e. the most recent global model index such that a perturbation of size σ satisfies Theorem 2:

T := arg max n (Ψ(n, c) ≤ Ψ * ) . ( 14
)
The new global model is obtained after perturbation θ := θ T + ν, where ν ∼ N (0, σ 2 I θ ). Our unlearning criterion 1 is therefore satisfied for θ (Theorem 2), and the server can perform Ñ new optimization rounds with FEDAVG initialized on θ. Thanks to the contribution of the remaining clients in θ, we expect the retraining with IFU to be generally faster than retraining with a random initial model.

Since Ψ(n, i) is strictly increasing with n, the server can stop from computing the bounded sensitivity (8) for client i whenever Ψ(n i , i) > Ψ * is verified after n i optimization rounds. At this point, the model θ ni-1 will be selected for the unlearning request of client i, as the models at subsequent iterations do not comply with the desired unlearning budget Ψ * .

I r = I r-1 \ W r . 5:
Compute (ζ r , T r ) with O(r -1), eq. ( 17) and ( 18).

6:

Update O(r) with ζ r , T r , and O(r -1), eq. ( 19).

7:

The new global model is θ 0 r = θ Tr ζr + N (0, σ 2 I θ ).

8:

Perform FEDAVG(D r , N r ) initialized on θ 0 r . 9:

Compute Ψ r (n, i), eq. ( 15). 10: end for 4 Sequential FU with SIFU

In this section, we extend IFU to the sequential unlearning setting with Sequential IFU (SIFU). With Algorithm 3, SIFU is designed to satisfy a series of R unlearning requests {W r } R r=1 , where W r is the set of clients to unlearn at request index r. SIFU generalizes IFU for which R = 1 and W 1 = {c}. We provide an illustration of SIFU with an example in Figure 1.

The notations introduced thus far need to be generalized to account for our series of unlearning requests W 1 , W 2 , . . . , W R . Global models are now referenced by their coordinates (r, n), i.e. θ n r , which represent the unlearning request index r and the amount of server aggregations n performed during the retraining. Hence, θ 0 r is the initialization of the model when unlearning the clients in W r . Also, we consider that the retraining at request index r requires N r server aggregations on the remaining clients. Therefore, by construction, θ Nr r is the model obtained after using SIFU to (ϵ, δ)-unlearn the sequence of unlearning requests {W s } r s=1 . Finally, we define I r as the set of remaining clients after unlearning request r, i.e. I r := I \ ∪ r s=1 W s = I r-1 \ W r with I 0 = I. We extend the bounded sensitivity (8) with Ψ r (n, i) to compute the metric of client i at unlearning index r with

Ψ r (n, i) := n-1 s=0 ∥∆(I r , θ s r ) -∆(I r \ {i}, θ s r )∥ 2 . ( 15
)
When unlearning client c at r = 1, the metric at r = 0 is equivalent to the previous definition of Ψ. Also, when computing the metric on a client already unlearned, i.e. i / ∈ I r , we retrieve Ψ r (n, i) = 0. Finally, for a set of clients S, we generalize the bounded sensitivity (15) to

Ψ r (n, S) = max i∈S Ψ r (n, i). ( 16
) Training Unlearning W 1 Unlearning W 2
Unlearning W 3

Server aggregation

Noise perturbation

O(0) = {∅} O(1) = {(0, T 1 )} ζ 1 = 0 O(2) = {(0, T 1 ), (1, T 2 )} ζ 2 = 1 O(3) = {(0, T 1 ), (1, T 3 )} ζ 3 = 1 θ 0 0 θ 1 0 θ T1 0 θ N0 0 θ 0 1 θ T3 1 θ T2 1 θ N1 1 θ 0 2 θ N2 2 θ 0 3 θ N3 3
(θ 0 0 , . . . , θ T1 0 , θ 0 1 , . . . , θ T2 1 , θ 0 2 , . . . θ N2 2 )
. The new node is added to the oracle O(2) = {(0, T 1 ), (1, T 2 )}, and ζ 2 = 1. Finally, at request r = 3, the unlearning index is found at T 3 < T 2 in the branch of request r = 1. The updated training history is now

(θ 0 0 , . . . , θ T1 0 , θ 0 1 , . . . , θ T3 1 , θ 0 3 , . . . θ N3 3 ), the oracle is updated as O(3) = {(0, T 1 ), (1, T 3 )}, and ζ 3 = 1.
With SIFU, the selection of the unlearning index T for a request r depends of the past history of unlearning requests.

To keep track of the unlearning history, we introduce the oracle O(r) which returns at each request r the coordinates of the history of global models where unlearning has been applied. These coordinates represent the nodes of the training history across unlearning requests (Figure 1). With reference to Figure 1, we start with the original sequence of global models obtained at each FL round, i.e. (θ 0 0 , . . . , θ N0 0 ). Similarly to IFU, the first unlearning request requires to identify the unlearning index T 1 for which the corresponding global model θ T1 0 must be perturbed to obtain θ 0 1 and retrained until convergence, i.e. up to θ N1 1 . The oracle is updated with the coordinates of the branching O(1) = {(0, T 1 )}, and the current training history is now (θ 0 0 , . . . , θ T1 0 , θ 0 1 , . . . , θ N1 1 ). At the next unlearning request, the server needs to identify the coordinates (ζ r , T r ) in the new training history for which unlearning must be applied on the model θ Tr ζr to obtain θ 0 r = θ Tr ζr + N (0, σ 2 I θ ). The oracle is subsequently updated with the new set of nodes describing the new branching in the training history. By construction, we have ζ r ≤ r -1 and T r ≤ N ζr .

More precisely, we define the index ζ r associated to the first coordinate in O(r -1) for which the bounded sensitivity (15) of clients in W r exceeds Ψ * . Formally, we have

ζ r := min s {s : Ψ s (n, W r ) > Ψ * and (s, n) ∈ O(r -1), r -1}. ( 17
)
The definition of T r follows directly from the one of ζ r .

Similarly as for IFU, the unlearning index T r quantifies the maximum amount of server aggregations starting from the unlearning request index ζ r such that the bounded sensitivity Ψ ζr (n, W r ) on this global model is inferior to Ψ * , i.e.

T r := arg max

n {Ψ ζr (n, W r ) ≤ Ψ * }. (18)
Finally, we update the oracle O(r -1) to O(r) with the following recurrent equation

O(r) = {(s, n) ∈ O(r -1) s.t. s < ζ r , (ζ r , T r )}. ( 19
)
Theorem 3 shows that for a model trained with SIFU after a given training request r, (ϵ, δ)-unlearning is guaranteed for every client belonging to the sets W s , s ≤ r.

Theorem 3. The model θ Nr r obtained with SIFU satisfies (ϵ, δ)-unlearning for every client in current and previous unlearning requests, i.e. clients in ∪ r s=1 W s .

Proof. See Appendix C.

Experiments

In this section, we experimentally demonstrate the effectiveness of SIFU on a series of benchmarks introduced in Section 5.1. In Section 5.2, we illustrate and discuss our experimental results. Results and related code are publicly available at URL.

Experimental Setup

Datasets. We report experiments on reduced versions of MNIST (LeCun et al., 1998), FashionMNIST (Xiao et al., 2017), CIFAR-10 (Krizhevsky, 2009), CIFAR-100 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF], and CelebA [START_REF] Liu | Deep learning face attributes in the wild[END_REF]. For each dataset, we consider M = 100 clients, with 100 data points each. For MNIST and FashionMNIST, each client has data samples from only one class, so that each class is represented in 10 clients only. For CIFAR10 and CI-FAR100, each client has data samples with ratio sampled from a Dirichlet distribution with parameter 0.1 (Harry [START_REF] Hsu | Measuring the effects of non-identical data distribution for federated visual classification[END_REF]. Finally, in CelebA, clients own data samples representing the same celebrity. With these five datasets, we consider different level of heterogeneity based on label and feature distribution.

Models. For MNIST, we train a logistic regression model to consider a convex classification problem, while, for the other datasets, we train a neural network with convolutional layers followed by fully connected ones. More details on the networks are available in Appendix D.

Unlearning schemes. In addition to SIFU, we consider the following unlearning schemes from the state-of-the-art: SCRATCH, where retraining of a new initial model is performed on the remaining clients; FINE-TUNING, where retraining is performed on the current global model with the remaining clients; LAST [START_REF] Neel | Descent-to-delete: Gradient-based methods for machine unlearning[END_REF], where retraining is performed on the remaining clients via perturbation of the final FL global model; DP [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF], where training with every client is performed with differential privacy, and FEDACCUM [START_REF] Liu | Federaser: Enabling efficient client-level data removal from federated learning models[END_REF], where retraining is performed on the current global model from which the server removes the updates of the clients to unlearn, by re-aggregating the parameter updates of clients that were stored by the server across FL iterations. We provide in Appendix D the pseudo-code of FEDACCUM with the notation of our paper. We remind that FEDACCUM does not provide quantitative guarantees of the unlearning procedure, and requires the server to store the full sequence of models during the FL procedure.

Experimental scenario. We consider a sequential unlearning scenario in which the server performs the FL training procedure and then receives R = 3 sequential unlearning requests to unlearn 10 random clients per request. In the special case of MNIST and FashionMNIST, the server must unlearn 10 clients owning the same class. The server orchestrates each unlearning scheme through retraining until the global model accuracy on the remaining clients exceeds a fixed value specific to each dataset. We set the minimum number of 50 aggregation rounds, and a maximum budget of 10000 rounds when the stopping accuracy criterion is not met. Each unlearning method is applied with the same hyperparameters, i.e. stopping accuracy, local learning rate η, and amount of local work K (Appendix D). We define the set of clients requesting unlearning as: Unlearning quantification. We verify the success of an unlearning scheme with two metrics: (a) the amount of server aggregation rounds needed for retraining, and (b) the resulting model accuracy on the unlearned clients. we note that, by construction, SCRATCH perfectly unlearns the clients from a request W r . Therefore, we consider an unlearning scheme successful if it reaches similar accuracy of SCRATCH with less aggregation rounds, when tested on the data samples of F r .

F r = ∪ r s=1 W s . (

Experimental Results

Figure 2 shows that for every dataset and unlearning index, FINE-TUNING, FEDACCUM, and DP provide similar model accuracy for the unlearned clients in F r (Figure 2-2 nd row), albeit significantly higher than for SCRATCH, the unlearning standard. Noteworthy, unlearning with FINE-TUNING, FEDACCUM, and DP results in significantly less aggregation rounds than SCRATCH (Figure 2-1 st row). We note that SIFU and SCRATCH lead to similar unlearning results, quantified by low accuracy on the unlearned clients F r (Figure 2-2 nd row), while SIFU unlearns these clients in roughly half the amount of aggregation rounds needed for SCRATCH (Figure 2-1 st row). However, the model accuracy of SIFU is slightly higher than the one of SCRATCH, with perfect overlap only for FashionMNIST. This behavior is natural and can be explained by our privacy budget (ϵ, δ), which trades unlearning capabilities for effectiveness of the retraining procedure. With highest unlearning budget, i.e. ϵ = 0 and δ = 0, SIFU would require to retrain from the initial model θ 0 0 , thus reducing to SCRATCH. Finally, we observed that when unlearning with LAST, the retrained model always converged to a local optimum with accuracy inferior to our target after 10000 aggregation rounds. This behavior is likely due to the difficulty of calibrating the noise perturbation due to the numerous heterogeneous contributions of the clients. For this reason, we decided to exclude LAST from the plots of Figure 2.

Verifying Unlearning through Watermarking

The work of [START_REF] Sommer | Towards probabilistic verification of machine unlearning[END_REF] proposes an adversarial approach to verify the efficiency of an unlearning scheme based on watermarking. We apply here this method to our federated setting, in which watermarking is operated by each client by randomly assigning on all its data samples the maximum possible value to 10 given pixels. To ensure that clients' data heterogeneity is only due to the modification of the pixels, we define heterogeneous data partitioning across clients by randomly assigning the data according to a Dirichlet distribution with parameter 1. Figure 3 shows our results for this experimental scenario on CI-FAR100 and CelebA, while Appendix D provides similar results for MNIST, FashionMNIST and CIFAR10. We retrieve the same conclusions drawn from Figure 2. SIFU and SCRATCH have similar accuracies on the unlearned clients in F r , to demonstrate the effectiveness of the unlearning. Moreover, SIFU unlearns these clients in significantly less aggregation rounds than SCRATCH.

Impact of the noise perturbation on SIFU

Appendix D illustrates the impact of the perturbation amplitude σ on convergence speed when unlearning with SIFU. We note that when unlearning with a small σ, SIFU has identical behavior to SCRATCH as the unlearning is applied to the initial random model θ 0 0 . With large values of σ, SIFU performs instead identically to LAST and applies the unlearning to the finale global model θ Nr r .

Conclusions

In this work, we introduce informed federated unlearning (IFU), a novel federated unlearning scheme to unlearn a client's contribution from a model trained with federated learning. Upon receiving an unlearning request from a given client, IFU identifies the optimal FL iteration from which FL has to be reinitialised, with statistical unlearning guarantees defined by Definition 1. We extend the theory of IFU to account for the practical scenario of sequential unlearning (SIFU), where the server receives a series of forgetting request of one or more clients. We prove that SIFU can unlearn a series of forgetting requests while satisfying our unlearning guarantees, and demonstrate the effectiveness of our methods on a variety of tasks and dataset.

An additional contribution of this work consists in a new theory for bounding the clients contribution in FL. The server can compute this bound for every client without asking for any additional computation and communication.

The theoretical justification of this approach relies on the linear approximation of the clients' loss function, and its relevance is here demonstrated across several benchmarks. Future extensions of the work will focus on generalizing our unlearning framework to more general settings. A When fine tuning does not guarantee unlearning: example on linear regression

Let us consider a linear regression optimization, with feature matrix X and predictions y such that the loss function f is defined as

f (X, y, θ) = 1 2 [y -Xθ] T [y Xθ] . (21)
In this example, we assume there are more features than data samples, which makes X T X a singular matrix. While f is convex, f has more than one global optimum. Any model with parameter θ * such that

X T Xθ * = X T y (22)
is a global optimum. When X T X is non-singular, we retrieve the unique optimum in close-form θ * = X T X -1 X T y.

We show with this simple example that, upon unlearning a data sample, no amount of fine-tuning on the model θ * can lead to the same model obtained when retraining from a random initial model. We differentiate between (X, y) and (X -1 , y -1 ) our data with and without a given data point.

Optimizing f , as defined in equation ( 21), with N steps of gradient descent, learning rate η, and initial model θ 0 gives model parameters θ N defined as

θ N = I -ηX T X N A(X,N ) θ 0 + η N -1 n=0 I -ηX T X n X T y B(X,y,N ) . ( 23
)
We first note that we retrieve the standard form for the global optimum of linear regression when X T X is non-singular as lim n→∞ A(X, n) = 0 and lim n→∞ B(X, y, n) = X T X -1 X T y. In the general form accounting for the singular case, at least one eigenvalue of A(X, N ) is equal to 1 independently from the amount of gradient descent steps N . Hence, the parameters of the model obtained with gradient descent optimization always depend from the ones of the initial model θ 0 . Hence, when unlearning our data sample from θ N , the resulting trained model still depends of that data samples. Indeed, if we compare the model θ Ñ -1 trained on the data samples (X -1 , y -1 ), to the model ϕ Ñ -1 obtained after fine-tuning the model θ N with Ñ server aggregations, we have

ϕ Ñ -1 -θ Ñ -1 = A(X -1 , Ñ )A(X, N )θ 0 + A(X -1 , Ñ )B(X, y, N ). (24)
B Forgetting a Single Client with IFU, Proof of Theorem 1

We first consider the case where clients perform K = 1 SGD in Section B.1 before considering the general case K ≥ 1 in Section B.2.

B.1 Proof of Theorem 1 for K = 1

Proof. We define by θ N = FEDAVG(I, N ) and ϕ N = FEDAVG(I -c , N ) the models trained with FEDAVG on θ 0 with respectively all the clients, i.e. I, and all the clients but client c, i.e. I -c , performing K = 1 GD step.

When clients perform K = 1 GD step, two consecutive global models can be related, when training with clients in I as a simple GD step, i.e.

θ n+1 = θ n -η∇f I (θ n ). (25)
By considering the same process for I -c and with Assumption 1, we get

ϕ n+1 -θ n+1 = ϕ n -θ n -η ∇f I-c (ϕ n ) -∇f I (θ n ) (26) = I -ηH I-c (θ n ) [ϕ n -θ n ] -η ∇f I-c (θ n ) -∇f I (θ n ) . (27)
H I-c (θ n ) is semi-positive, Assumption 1. Let us define σ max (H I-c (θ n )) the highest eigenvalue of H I-c (θ n ). When consider that η ≤ 1/σ max (H I-c (θ n )), and due to the subadditivity of the norm, we get the following recurrent inequality

ϕ n+1 -θ n+1 2 ≤ η ∇f I (θ n ) -∇f I-c (θ n ) 2 + ∥ϕ n -θ n ∥ 2 , (28)
which when developed completes the proof when clients perform K = 1 GD.

B.2 Proof of Theorem 1 for K ≥ 1

Proof. We maintain the definitions of θ n and ϕ n introduced in Section B.1. To account for the amount of local K, we introduce θ n,k i the model of client i after k GD steps performed on global model θ n . We apply a similar reasoning for ϕ n,k i . With Assumption 1, we have

∇f i (ϕ n,k i ) = ∇f i (θ n,k i ) + H i (θ n,k i ) ϕ n,k i -θ n,k i , (29)
which gives

ϕ n,k+1 i -θ n,k+1 i = ϕ n,k+1 i -ϕ n,k i -θ n,k+1 i -θ n,k i + ϕ n,k i -θ n,k i (30) = -η ∇f i ϕ n,k i -∇f i θ n,k i + ϕ n,k i -θ n,k i (31) = I -ηH i (θ n,k i ) ϕ n,k i -θ n,k i (32) = k r=0 [I -ηH i (θ n,r i )] (ϕ n -θ n ) , (33)
where the third equality follows from equation ( 29), and the fourth from expanding the recurrent equation. For the rest of this work, we define

Q n i = K-1 k=0 I -ηH i (θ n,k i ) .
Using equation ( 33), we relate the difference between two global models with every client in I and in I c . When removing client c the clients' importance changes. We consider importance p i when training with I. Instead, when training with clients in I c , we consider the regularized importance q i = p i /(1 -p c ) for the remaining clients and q c = 0. We have

ϕ n+1 -θ n+1 = M i=1 q i ϕ n+1 i -ϕ n - M i=1 p i θ n+1 i -θ n (34) = M i=1 q i ϕ n+1 i -θ n+1 i + θ n+1 i -θ n - M i=1 p i θ n+1 i -θ n (35) = M i=1 q i Q n i (ϕ n -θ n ) + ∆(I -c , θ n ) -∆(I, θ n ). (36)
We consider a learning rate η such that η ≤ 1/σ max (H i (θ n,k )). Hence, ∥Q n i ∥ 2 ≤ 1. With equation ( 36), we get the following inequality

ϕ n+1 -θ n+1 2 ≤ ∥ϕ n -θ n ∥ 2 + ∥∆(I, θ n ) -∆(I -c , θ n )∥ 2 , (37)
which expansion completes the proof.

B.3 Local Loss Functions' Regularization and Strong Convexity, Proof of Corollary 1

Proof. Under L2 regularization, every client's regularized loss function F i is expressed as

F i (θ) = f i (θ) + λ 2 ∥θ∥ 2 and ∇F i (θ) = ∇f i (θ) + λθ. (38)
When clients perform K = 1 GD step, equation ( 36) reduces to

ϕ n+1 -θ n+1 = η ∇f I (θ n ) -∇f I-c (θ n ) + (1 -ηλ)I -ηH I-c (θ n ) (ϕ n -θ n ), ( 39
) which, if η ≤ 1/(λ + σ max (H i (θ n )), gives ϕ n+1 -θ n+1 2 ≤ η ∇f I (θ n ) -I-c (θ n ) 2 + (1 -ηλ -ηµ) ∥ϕ n -θ n ∥ 2 . ( 40
)
When clients perform K ≥ 1 GD steps, we have

ϕ n+1 i -θ n+1 i = Q n i [ϕ n -θ n ] with Q n i = K-1 r=0 [(1 -ηλ)I -ηH i (θ n,r i )] . (41)
Hence, we retrieve equation ( 36). We consider the local learning rate satisfy η ≤ 1/(λ + σ max (H i (θ n ))). Hence, considering that Q n i can be bounded with the µ-strong convexity of the Hessian, we get

ϕ n+1 -θ n+1 2 ≤ η ∥∆(I, θ n ) -∆(I -c , θ n )∥ 2 + (1 -ηλ -ηµ) K ∥ϕ n -θ n ∥ 2 . ( 42
)
Developing this recurrent equation completes the proof.

B.4 Generalization

The proof of Theorem 1 can be also extended to account for FL regularization methods [START_REF] Li | Federated Optimization in Heterogeneous Networks[END_REF](Li et al., , 2019;;[START_REF] Acar | Federated learning based on dynamic regularization[END_REF], other SGD solvers [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF][START_REF] Ward | AdaGrad stepsizes: Sharp convergence over nonconvex landscapes[END_REF][START_REF] Li | On the convergence of stochastic gradient descent with adaptive stepsizes[END_REF]Yu et al., 2019a,b;[START_REF] Haddadpour | Trading redundancy for communication: Speeding up distributed SGD for non-convex optimization[END_REF], client sampling [START_REF] Li | Federated Optimization in Heterogeneous Networks[END_REF][START_REF] Li | On the convergence of fedavg on non-iid data[END_REF][START_REF] Fraboni | On the impact of client sampling on federated learning convergence[END_REF] and/or gradient compression/quantization [START_REF] Reisizadeh | Fedpaq: A communicationefficient federated learning method with periodic averaging and quantization[END_REF][START_REF] Basu | Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations[END_REF][START_REF] Wang | Atomo: Communicationefficient learning via atomic sparsification[END_REF].

B.5 Calculus simplification with uniform importance

For computation purposes, we propose the following expression to estimate a client bounded sensitivity, equation (8. When removing client c, each client has new importance q i = p i /(1 -p c ) for the remaining clients and q c = 0. Hence, we have

∥∆(I, θ n ) -∆(θ n , D -c )∥ 2 = θ n+1 -θ n - M i=1 q i θ n+1 i -θ n 2 (43) = θ n+1 - 1 1 -p c θ n+1 -p c θ n+1 i 2 (44) = p c 1 -p c θ n+1 i -θ n+1 2 (45)
In the special case where clients have identical importance, we have p c /(1 -p c ) = 1/(M -1).

C Convergence of SIFU, Theorem 3 When considering the more general case where there exists an integer k such that u = s + k while (ν, t s ) ∈ O(s) and (ν, t u ) ∈ O(u), then it is sufficient to consider iteratively an integer j ranging from 1 to k. Considering (ν, t u ) ∈ O(u), there exists t s+j such that (ν, t s+j ) ∈ O(s + j). In that case, using the same reasoning as for k = 1, we have t s ≤ t s+1 ≤ . . . ≤ t s+k-1 ≤ t u .

C.2 Proof of Theorem 3

Proof. Proving that θ Nr r (ϵ, δ)-unlearns every client in F r , equation ( 20), reduces to proving that θ 0 r (ϵ, every client in F r , equation ( 20). Indeed, the data of clients in F r are not used on the noised perturbed model θ 0 r = θ Tr ζr + N (0, σ 2 I θ ).

We prove by induction that θ 0 r (ϵ, δ)-unlearns every client in F r , equation ( 20). The initialization (r = 1) directly follows from IFU, Algorithm 2, with Theorem 2. We now assume that for every s such that s ≤ r -1, θ 0 s (ϵ, δ)-unlearns every client in F s and prove that θ 0 r (ϵ, δ)-unlearns every client in F r .

• s ≤ ζ r . Using the induction property, θ 0 ζr (ϵ, δ)-unlearns every clients in W s . Clients in W s are not used for training on θ 0 ζr . Hence, θ Tr ζr and θ 0 r also (ϵ, δ)-unlearns every client in W s .

• s = r. By definition of ζ r , equation ( 17), the noise perturbations for every model in O(r) is such that θ 0 ζr (ϵ, δ)unlearns every client in W r . Hence, by definition of T r on the bounded sensitivity of clients in W r at unlearning request ζ r , equation ( 18), the noised perturbed model θ 0 r (ϵ, δ)-unlearns every client in W r , Theorem 2. 19). Therefore, using property 1, we have t s ≥ T r . Hence, we have Ψ ζr (T r , W s ) ≤ Ψ * . Therefore, with the noise perturbation of SIFU, clients in W s are (ϵ, δ)-unlearned in θ 0 r .

• ζ r < s ≤ r -1.

D Experiments

For every benchmark, we consider the number of SGD steps K, batch size B, number of clients M , the number of sampled clients m, the standard deviation σ of the noise perturbation, and the local learning rate η given in Table 1. Also, for our unlearning scheme SIFU, DP, and LAST, we consider an unlearning budget of ϵ = 10 and δ = 0.01. The unlearning budget plays the important role of identifying in the training history the global model to perturb. Theorem 2 shows that ϵ and σ are linearly related. Hence, to unlearn a client c from a global model c, a smaller σ can be considered, but at the cost of a lower unlearning budget (ϵ, δ), Definition 1. Also, for fair comparison of DP with other FU schemes, we select the best clipping value C, in a range from 0.001 to 1, for which the global model reaches the target accuracy in the smallest amount of aggregation rounds. Finally, for FashionMNIST, CIFAR10, CIFAR100, and CelebA, we consider model architectures composed of three convolutional layers followed by two fully connected layers, with implementation at URL.

Table 1: Hyperparameters used for our different unlearning benchmarks described in Section 5.1. The training and retraining depends on the initial model θ 0 0 and the clients' batches of data used at every aggregation to compute their local work. Hence, we replicate each unlearning scenario on 10 different seeds and plot in Figure 2 to 6 their averaged results. For the unlearning benchmarks described in Section 5.1 and used in Figure 2, 5, and 6, the stopping accuracies considered are 93% for MNIST, 90% for FashionMNIST, CIFAR10, and CIFAR100, and 99.9% for CelebA. For Figure 3 and 4 with unlearning benchmark described in Section 5.3, the stopping accuracies considered are instead 99.9% for MNIST, FashionMNIST, CIFAR10, and CelebA, and 99% for CIFAR100. Reaching such accuracies is easier with the backdoored datasets because the clients' data heterogeneity is only due to their watermark, Section 5.3.

Definition 1 .

 1 Let f m be a randomized mechanism taking model parameters as an input. (ϵ, δ)-Unlearning trough f m of a data point {x m , y m } from a model M(D) is achieved if, for any subset S of the model parameters space and D -m := D \ {x m , y m }, we have P(f m (M(D)) ∈ S) ≤ e ϵ P(f m (M(D -m )) ∈ S) + δ (3) and P(f m (M(D -m )) ∈ S) ≤ e ϵ P(f m (M(D)) ∈ S) + δ.

Figure 1 :

 1 Figure1: Illustration of SIFU (Algorithm 3) when the server receives R = 3 unlearning requests, through the evolution of the global model parameters θ n r after server aggregation and noise perturbation. After standard federated training via FEDAVG(I, N 0 ), the oracle is O(0) = {∅}, and the current training history is (θ 0 0 , . . . , θ N0 0 ). At request r = 1 the unlearning index is T 1 , and the training history becomes (θ 0 0 , . . . , θ T1 0 , θ 0 1 , . . . , θ N1 1 ). The oracle is updated to O(1) = {(0, T 1 )}, and ζ 1 = 0. At request r = 2 the unlearning index is T 2 and the training history becomes (θ 0 0 , . . . , θ T1 0 , θ 0 1 , . . . , θ T2 1 , θ 0 2 , . . . θ N2 2 ). The new node is added to the oracle O(2) = {(0, T 1 ), (1, T 2 )}, and ζ 2 = 1. Finally, at request r = 3, the unlearning index is found at T 3 < T 2 in the branch of request r = 1. The updated training history is now (θ 0 0 , . . . , θ T1 0 , θ 0 1 , . . . , θ T3 1 , θ 0 3 , . . . θ N3 3 ), the oracle is updated as O(3) = {(0, T 1 ), (1, T 3 )}, and ζ 3 = 1.

Figure 2 :

 2 Figure2: Total amount of aggregation rounds (1 st row) and model accuracy of unlearned clients (2 nd row) for MNIST, FashionMNIST, CIFAR10, CIFAR100, and CelebA (the lower the better). The server runs a federated routine with M = 100 clients, and unlearns 10 of them at each unlearning request (R = 3).

  20) In our experimental scenario, we have |F 0 | = 0 during training and |F 1 | = 10, |F 2 | = 20, and |F 3 | = 30 after each unlearning request.

Figure 3 :

 3 Figure 3: Total amount of aggregation rounds (1 st row) and model accuracy of unlearned clients (2 nd row) for the unlearning of watermarked data from CIFAR100 and CelebA.

Figure 4 :

 4 Figure 4: Total amount of aggregation rounds (1 st row) and model accuracy of unlearned clients (2 nd row) for the unlearning of watermarked data from MNIST, FashionMNIST, CIFAR10, CIFAR100, and CelebA (the lower the better).

Figure 5 :

 5 Figure 5: Impact of the noise standard deviation σ when unlearning with SIFU versus SCRATCH. Total amount of aggregation rounds (1 st row) and model accuracy of unlearned clients (2 nd row) for MNIST, FashionMNIST, CIFAR10, CIFAR100, and CelebA (the lower the better).

Figure 6 :

 6 Figure6: Total amount of aggregation rounds (1 st row) and model accuracy of unlearned clients (2 nd row) for MNIST, FashionMNIST, CIFAR10, CIFAR100, and CelebA (the lower the better). This figure displays the unlearning capabilities of the unlearning benchmarks introduced in Section 5.1 after training on clients in I and unlearning |W 1 | = 10 clients. For each integer on the x-axis, a different set of clients to unlearn is considered. Each unlearning request is composed of 10 random clients for CIFAR10, CIFAR100, and CelebA. For MNIST and FashionMNIST, each unlearning request |W 1 | has 10 clients of the same class such that the x-axis is the class forgotten. The integers on the x-axis corresponds to the class of the clients to unlearn.

  Algorithm 3 Sequential IFU (SIFU) DURING LEARNING WITH FEDAVG 1: FEDAVG(I, N ) initialized on initial model θ 0 0 . 2: Compute Ψ 0 (n, i), equation (15). UNLEARNING A SERIES OF REQUESTS {W r } Require: {W r } R r=1 , ϵ, δ, σ, and {N r } R

r=1 1: O(0) = {∅}. 2: Get Ψ * with equation (13). 3: for r from 1 to R do 4:

  Xiao, H., Rasul, K., and Vollgraf, R. (2017). Fashionmnist: a novel image dataset for benchmarking machine learning algorithms. CoRR, abs/1708.07747.

	Yu, H., Jin, R., and Yang, S. (2019a). On the linear
	speedup analysis of communication efficient momentum
	SGD for distributed non-convex optimization. In Chaud-
	huri, K. and Salakhutdinov, R., editors, Proceedings of
	the 36th International Conference on Machine Learn-
	ing, volume 97 of Proceedings of Machine Learning Re-
	search, pages 7184-7193. PMLR.
	Yu, H., Yang, S., and Zhu, S. (2019b). Parallel Restarted
	SGD with Faster Convergence and Less Communica-
	tion: Demystifying Why Model Averaging Works for
	Deep Learning. Proceedings of the AAAI Conference on
	Artificial Intelligence, 33(01):5693-5700.

  We first assume that s and u satisfy u= s + 1. Considering that (ν, t s ) ∈ O(s) and (ν, t u ) ∈ O(u), we have, by definition of ζ u in equation (17), ν ≤ ζ u . • ζ u > ν. Considering that u = s + 1, we have t s = t u , equation (19). • ζ u = ν. Considering that (ν, t s ) ∈ O(s) and (ν, t u ) ∈ O(u), then we have ν ≤ s -1. Therefore, by definition of ζ u ,we have Ψ ζu (t s , W u ) > Ψ * . By construction of T u , equation (18), we have t u = T u < t s .

C.1 Intermediate results

Property 1. If there exists ν, s, u such that s < u, (ν, t s ) ∈ O(s) and (ν, t u ) ∈ O(u), then t s ≥ t u .

Proof.

  The successive update of the oracle, equation (19), from O(ζ r ) to O(s) gives, by construction, that there exists t s such that the coordinates (ζ r , t s ) are in O(s). Hence, by definition of ζ s , equation (17), we have ζ s ≥ ζ r and the successive noise perturbations to obtain θ 0 ζr (ϵ, δ)-unlearns every client in W s . Also, while we have the coordinates (ζ r , t s ) in O(s), we also have the coordinates (ζ r , T r ) in O(r), equation (

Acknowledgments

This work has been supported by the French government, through the 3IA Côte d'Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002, and by the ANR JCJC project Fed-BioMed 19-CE45-0006-01. The project was also supported by Accenture. The authors are grateful to the OPAL infrastructure from Université Côte d'Azur for providing resources and support.