Machine Unlearning of Federated Clusters
Authors: Chao Pan
Jin Sima
Saurav Prakash
Vishal Rana
Olgica Milenkovic
Venue: ICLR 2023 poster (2023)
Keywords: federated learning
federated clustering
machine unlearning
secure aggregation

Abstract: Federated clustering (FC) is an unsupervised learning problem that arises in a number of practical applications, including personalized recommender and healthcare systems. With the adoption of recent laws ensuring the "right to be forgotten", the problem of machine unlearning for FC methods has become of significant importance. We introduce, for the first time, the problem of machine unlearning for FC, and propose an efficient unlearning mechanism for a customized secure FC framework. Our FC framework utilizes special initialization procedures that we show are well-suited for unlearning. To protect client data privacy, we develop the secure compressed multiset aggregation (SCMA) framework that addresses sparse secure federated learning (FL) problems encountered during clustering as well as more general problems. To simultaneously facilitate low communication complexity and secret sharing protocols, we integrate Reed-Solomon encoding with special evaluation points into our SCMA pipeline, and prove that the client communication cost is logarithmic in the vector dimension. Additionally, to demonstrate the benefits of our unlearning mechanism over complete retraining, we provide a theoretical analysis for the unlearning performance of our approach. Simulation results show that the new FC framework exhibits superior clustering performance compared to previously reported FC baselines when the cluster sizes are highly imbalanced. Compared to completely retraining K-means++ locally and globally for each removal request, our unlearning procedure offers an average speed-up of roughly 84x across seven datasets. Our implementation for the proposed method is available at https://github.com/thupchnsky/mufc.

Published as a conference paper at ICLR 2023
MACHINE UNLEARNING OF FEDERATED CLUSTERS
Chao Pan", Jin Sima", Saurav Prakash", Vishal Rana & Olgica Milenkovic Department of Electrical and Computer Engineering University of Illinois Urbana-Champaign USA (chaopan2, jsima, sauravp2, vishalr, mi w.shaalr,mmleeeorryylliiiiossss
ABSTRACT
Federated clustering (FC) is unsupervised learning problem that arises in num- ber of practical applications, including personalized recommender and healthcare systems. With the adoption of recent laws ensuring the "right be forgotten", the problem of machine unlearning for FC methods has become of significant importance. We introduce, for the first time, the problem of machine unlearning for FC, and propose an efficient unlearning mechanism for a customized secure FC framework. Our FC framework utilizes special initialization procedures that we show are well-suited for unlearning. To protect client data privacy, we develop the secure compressed multiset aggregation (SCMA) framework that addresses sparse secure federated learning (FL) problems encountered during clustering well as more general problems. To simultaneously facilitate low communication complexity and secret sharing protocols, we integrate Reed-Son -ooeomo encoding with special evaluation points into our SCMA pipeline, and prove that the client commu- nication cost is logarithmic in the vector dimension. Additionally, to demonstrate the benefits of our unlearning mechanism over complete retraining, we provide a theoretical analysis for the unlearning performance of our approach. Simulation results show that the new FC framework exhibits superior clustering performance compared to previously reported FC baselines when the cluster sizes are highly imbalanced. Compared to completely retraining K K-means++ locally and globally for each removal request, our unlearning procedure offers an average speed-up of roughly 84x across seven datasets. Our implementation for the proposed method is available at https:: //tt://gggtttb/tt/ htt.///b.cco//tuuucssss/////ee
INTRODUCTION
The availability of large volumes of user training data has contributed the success of modern machine learning models. For example, most wfate-of-the-at computer vision models are trained on large-scale image datasets including Flickr (Thomee et al.) (2016) and ImageNet (Deng et al. 2009). Organizations and repositories that collect and store user data must comply with privacy regulations, such as the recent European Union General Data Protection Regulation (GDPR), the California Consumer Privacy Act (CCPA), and the Canadian Consumer Privacy Protection Act (CPPA), all of which guarantee the right of users to remove their data from the datasets (Right to be Forgotten). Data removal requests frequently arise in practice, especially for sensitive datasets pertaining to medical records (numerous machine learning models in computational biology are trained using UK Biobank (Sudlow al. 2015) which hosts collection of genetic and medical records of roughly half a million patients (Ginart et al.] 2019)). Removing user data from a dataset is insufficient to ensure sufficient privacy, since training data can often be reconstructed from trained models (Fredrikson et al.) 2015, Veale et al. 2018). This motivates the study of machine unlearning (Cao & Yang 2015) which aims efficiently eliminate the influence of certain data points on model. Naively, one can retrain the model from scratch to ensure complete removal, yet retraining comes at high computational cost and is thus not practical when accommodating frequent removal requests. To avoid complete retraining, specialized approaches have to be developed for each unlearning application (Ginart et al. 2019 Guo et al. 2020 Bourtoule et al. 2021 (Sekhari et al. 202I).
"Equal contribution.

---

Published as a conference paper at ICLR 2023
x(u
Secure Compressed Multiset Aggregation
K-means++ Initialization & Quantization
Data Generation & K- K-means++
(SCMA)
Figure 1: Overview of our proposed FC framework. K-means++ initialization and quantization are performed at each client in parallel. The SCMA procedure ensures that only the server knows the aggregated statistics of clients, without revealing who contributed the points in each individual cluster. The server generates points from the quantization bins with prescribed weights and performs full K-means++ clustering to infer the global model.
At the same time, federated learning (FL) has emerged as promising approach to enable distributed training over a large number of users while protecting their privacy (McMahan et al. 2017 Chen et al. 2020 Kairouz et al. 2021 Wang al. 2021 Bonawitz al. 2021). The key idea of FL is to keep user data on their devices and train global models by aggregating local models in a communication. efficient and secure manner. Due to model inversion attacks (Zhu al. 2019 Geiping et al. 2020), secure local model aggregation at the server is a critical consideration in FL, as it guarantees that the server cannot get specific information about client data based on their local models (Bonawitz iet al. 2017 Bell et al. 2020 [oo et al. 2022; Chen et al. 2022). Since data privacy is the main goal FL., should be natural for a FL framework to allow for frequent data removal of subset of client data in cross-silo setting (e.g., when several patients request their data to be removed in the hospital database), or the entire local dataset for clients in a cross-device setting (e.g.. when users request apps not to track their data on their phones). This leads to the largely unstudied problem termed federated unlearning (Liu et al., 2021; Wu et al. 20022 Wang et al. 2002). However, existing federated unlearning methods do not come with theoretical performance guarantees after model updates, and often, they are vulnerable to adversarial attacks.
Our contributions summarized follows. 1) We introduce the problem of machine unlearning in FC, and design a new end-to-end system (Fig. T that performs highly efficient FC with privacy and low communication-ocm unlearning. 2) As part of the FC scheme with unlearning features, we describe a novel one-shot FC algorithm that offers order-optimal approximation for the federated K K-means clustering objective, and also outperforms the handful of existing related methods (Dennis et al. 2021 Ginart et al. 2019)) especially for the case when the cluster sizes are highly imbalanced. novel sparse compressed multiset aggregation (SCMA) scheme which ensures that the server only has access to the aggregated counts of points in individual clusters but has no information about the point distributions at individual clients. SCMA securely recovers the exact sum of the input sparse vectors with communication complexity that is logarithmic the vector dimension, outperforming existing sparse secure aggregation works (Beguier et al. 2020 Ergun et al. 2021), which have a linear complexity. 4) We theoretically establish the unlcarning complexity of our FC method and show that it is significantly lower than that of complete retraining. 5) We compile collection of datasets for benchmarking unlearning of federated clusters, including two new datasets containing methylation patterns in cancer genomes and gut microbiome information, which may be of significant importance to computational biologists and medical researchers that are frequently faced with unlearning requests. Experimental results reveal that our one-shot algorithm offers an average speed-up of roughly 84x compared to complete retraining across seven datasets.
guarantees, which also enables, when needed, simple and effective
For FC, we also describe
RELATED WORKS
Due to space limitations, the complete discussion about related works is included in Appendix
Federated clustering. The goal of this learning task is to perform clustering using data that resides at different edge devices. Most of the handful of FC methods are centered around the idea sending exact (Dennis al. 2021) quantized client (local) centroids (Ginart et al./ 2019)) directly to the server, which may not ensure desired levels of privacy as they leak the data statistics or cluster information of each individual client. To avoid sending exact centroids, Li et al. (022)) proposes sending distances between data points and centroids to the server without revealing the membership of data points to any of the parties involved, but their approach comes with large computational
2

---

Published as a conference paper at ICLR 2023
and communication overhead. Our work introduces novel communication--fffiisee secure FC framework, with a new privacy criterion that is intuitively appealing as it involves communicating obfuscated point counts of the clients to the server and frequently used in FL literature (Bonawitz
et al. 2017).
Machine unlearning. Two types of unlearning requirements were proposed in previous works: exact
unlearning (Cao & Yang 2015] Ginart et al.) [2019] [Bourtoule et al. 2021 Chen et al.] 2021) and
approximate unlearning (uo al. 2020; Golatkar al. 2020a bj Sekhari et al.) 2021 Fu al.
2022] Chien et al. 2022). For exact unlearning, the unlearned model is required to perform identically
as a completely retrained model. For approximate unlearning, the "differences" in behavior between the unlearned model and the completely retrained model should be appropriately bounded. A limited number of recent works also investigated data removal in the FI. settings (Liu et al. 202T Wu et al., 2022 Wang et al., 2022): however, most of them are empirical methods and do not come with theoretical guarantees for model performance after removal and/or for the unlearning efficiency. In contrast, our proposed FC framework not only enables efficient data removal in practice, but also provides theoretical guarantees for the unlearned model performance and for the expected time complexity of the unlearning procedure.
3 PRELIMINARIES
We start with a formal definition of the centralized K-means problem. Given a set of n points in Rd X' arranged into a matrix X E nxa and the number of clusters K, the K- K-means problem asks for finding a set of points C = {ci, .... CK ) E R vk E [K] that minimizes the objective
& C) = XX C
(1)
where || |I. denotes the Frobenius norm of a matrix, ||- denotes the & norm of vector, and C E Raxd records the closest centroid in to each data point 2; X' (i.e., c = arg min,, ec ||2 - -cyl). Without loss of generality, we make the assumption that the optimal solution is unique in order to facilitate simpler analysis and discussion, and denote the optimum by C' = {ch,...,
The
set of centroids C' induces an optimal partition U C₁ over X, where Vk: E [K],C] {ar ||x; - اll < ||ar eill Vi E [n].j E [K]]- We use (2)) to denote the optimal value of the objective function for the centralized K -mmeans problem. With a slight abuse of notation, we also use (C(C)) to denote the objective value contributed by the optimal cluster Cz. A detailed description of a commonly used approach for solving the K-means problem, K-means++, is available in Appendix B
In FC, the dataset X' is no longer available at the centralized server. Instead, data is stored on L edge devices (clients) and the goal of FC is learn a global set of K centroids C, at the server based on the information sent by clients. For simplicity, we assume that there exists no identical data points across clients, and that the overall dataset X' is the union of the datasets 2!)) arranged as (!) IR" xd on device I, VI E [L]. The server will receive the aggregated cluster statistics of all clients in a secure fashion, and generate the set C.. In this case, the federated K-means problem asks for finding K global centroids C, that minimize the objective
(x,x Σ x C.
where c!.) E g2n")x xd records the centroids of the induced global clusters that data points {a. In Ji=l on client belong to. Note that the definition of the assignment matrix C for the centralized K K-means different from that obtained through federated K-means c the i-th row of C only depends on the location of H; while the row in c.(0 corresponding to 2; depends on the induced global clusters that x; belongs (for a formal definition see (.I. In Appendix []] we provide simple example that further illustrates the difference between C' and C(() Note that the notion of induced global clusters was also used in Dennis et al. (202T).
Definition 3.1. Suppose that the local clusters at client I are denoted by c Vk E [K], E [L]. and thut the clusters at the server are denoted by Cg2 vk E [K]. The global clustering equals Ps = {x (x( E cll) (1) Note that (..., forms partition of the entire dataset X, and the representative centroid for Pet is defined Ca,k C.,
ec(()
.g Cr. Vj E [K], E [L]}, where ef is the centroid of cll) on client l.
3

---

Published as a conference paper at ICLR 2023
Exact unlearning. For clustering problems, the exact unlearning criterion may be formulated as follows. Let X' be given dataset and A a (randomized) clustering algorithm that trains on X' and outputs set of centroids C E M, where M is the chosen space of models. Let U be unlearning algorithm that is applied to A(x') to remove the effects of one data point x E X. Then U is an exact unlearning algorithm if VC M, X,
C) = (()(A()::) = C). To avoid confusion, in certain cases, this criterion is referred to as probabilistic (model) equivalence.
trilemma. How to trade-off data privacy, model performance, commu- nication and computational efficiency is a long-standing problem in distributed learning (Acharya & 2019 | Chen et al. 22000) Gandikota al. 202T) that also carries over to FL and FC. Solutions that simultaneously address all these challenges in the latter context are still lacking. For example, Den nis et al. (202T) proposed one-shot algorithm that takes model performance and communication efficiency into consideration by sending the exact centroids of each client to the server in a nonanony- mous fashion. This approach may not be desirable under stringent privacy constraints as the server can gain information about individual client data. On the other hand, privacy considerations were addressed in Li et al. 2022) by performing K K-means Lloyd's iterations anonymously via distribution of computations across different clients. Since the method relies on obfuscating pairwise distances for each client, it incurs computational overheads to hide the identity of contributing clients at the server and communication overheads due to interactive computations. None of the above methods is suitable for unlearning applications. To simultaneously enable unlearning and address the trilemma in the unlearning context, our privacy criterion involves transmitting the number of client data points within local client clusters in such a manner that the server cannot learn the data statistics of any specific client, but only the overall statistics of the union of client datasets. In this case, computations are limited and the clients on their end can perform efficient unlearning, unlike the case when presented with data point/centroid distances.
Privacy- wawpaccy-ccuuacyyttiiia
Algorithm Secure Federated Clustering
Random and adversarial removal. Most un- learning literature focuses on the case when all data points are equally likely to be removed, setting known as random removal. However, ad Adversarial data removal requests may arise when users are malicious in unlearning certain points that critical for model training (i.e., boundary points in optimal clusters). We re- fer to such removal request as adversarial removal. In Section we provide theoretical analysis for both types of removal.
1: input: Dataset X' distributed on L clients (2)(1,,.. ((())
2: Run K-means++ initialization each client in parallel, obtain the initial centroid sets C and record the corresponding cluster sizes (cc]) |c D), vi E [Z]-
3: Perform uniform quantization of ( on each dimension, and flatten the quantization bins into a vector 7 (2) Vl E [Z.].
4: Set oj (1)
(( with j being the index of the
(1) lies in for Vk [K].
4 FEDERATED CLUSTERING WITH SECURE MODEL AGGREGATION
quantization bin where ck
and cf is the centroid of cl. Set 15 = 0 for
all other indices.
5: Securely sum up ( at server by Algorithm 2. with the aggregated vector denoted as q.
The block diagram of our FC (Alg. D de- picted in Fig. It comprises five components: client-side clustering. client local informa- tion processing, secure compressed aggrega- tion, server data generation, and server-side clustering module. We explain next the role of each component of the system.
6: For index j E {t. * 0}. sample 9 points based on pre-defined distribution and denote their union as new dataset X, at server.
7: Run full K K-mmans++ clustering at server with
X, to obtain the centroid set C, at server.
For client- and server-side clustering (line 2 and of Alg. D. we adopt K K-means++ as lends it itself to highly efficient unlearning, as explained in Section 5 Specifically, we only run the K-means++ initialization procedure at each client but full K-means++ clustering (initialization and Lloyd's algorithm) the server.
8: return Each client retains its own centroid set
C server retains X,, 9 and C,,
Line 3 and 4 of Alg. describe the procedure used to process the information of local client clusters. As shown in Fig. [ we first quantize the local centroids to their closest centers of the quantization bins, and the spatial locations of quantization bins naturally form tensor, in which we store the sizes of local clusters. tensor is generated for each client 1, and subsequently flattened to form vector (9) For simplicity, we use uniform quantization with step size y for each dimension (line 3 of
4

---

Published as a conference paper at ICLR 2023
Alg. with more details included in Appendix H). The parameter quantization bins in each dimension. the client data is not confined to the unit hypercube centered at the origin, we scale the data to meet this requirement. Then the number of quantization bins in each dimension equals B = -- while the total number of quantization bins for d dimensions is Bd y
determines the number of
Line 5 of Alg. I describes how to aggregate information efficiently at the server without leaking individual client data statistics. This scheme is discussed in Section 4.1 Line pertains to generating zj points for the j-th quantization bin based on its corresponding spatial location. The simplest idea to choose the center of the quantization bin as the representative point and assign weight gj to Then, in line 7, we can use the weighted K K-means++ algorithm at the server to further reduce the computational complexity.
A simplified version of Alg. iis discussed in Appendix || for applications where the privacy criterion not an imperative.
4.1
SCMA AT THE SERVER
Once the vector representations g()) of length Id for client / are generated (line 4 of Alg. D. we can use standard secure model aggregation methods [Bonawitz et al. 2017 Bell al. 2020 So et al. 2022) to sum up all 70 securely and obtain the aggregated results q at the server. However, since the length of cach vector qdd) is Bd, securely aggregating the whole vector would lead to an exponential communication complexity for each client. Moreover, each gd)) is a sparse vector since the number of client centroids is much smaller than the number of quantization bins (i.e., K < Bd). It is ineffi- cient and unnecessary for each client to send out the entire qdd) with noisy masks for aggregation. This motivates us to first compress the vectors and then perform the secure aggregation, and we refer to this process as SCMA (Alg. 2}. with one example illustrated in Fig. 2
Algorithm 2 SCMA
1: input: L different vectors ( of length Bd to be securely aggregated, finite field F
2: Each client 1. E [L] communicates
(S(1)
((1) 2 to the server, where s(D)
:....
( <o Oj
(1) +2,1) mod i.ic E [2
and z1 is random key uniformly distributed over Fp and hidden from the server. The keys (1) (e(()) are generated offline using standard secure model aggregation so that (Er (0) mod p=
3: The server first computes the sum S (Erety) s(D)) mod Given S,, the server computes the coefficients of the polyno- mial gxx) = =u j x) using the Berlekamp- Massey algorithm (Berlekamp) 1968] Massey] 1969). Then, the server fac- torizes g(x) over the field F, to determine the roots j- a * O, using the polyno- mial factorizing algorithm (Kedlaya & Umans, 2011). Finally, the server solves a set of 2KT linear equations S; = -EEELE) s!D))
By observing that there can be at most K nonzero entries in qd) VI E [L] and at most KL nonzero entries in q. we invoke the Reed-Solomon code construction (Reed & Solomon 1960) for designing SCMA. Let IF, be a finite field of prime order ma Bd) We treat the indices of the quantization bins as distinct elements from the underlying finite field, and use them evalua- tion points of the encoder polynomial. In addi-
IO.
Ej Qj jr-1 for E [2KL], by consider- ing qj as unknowns and j²-1 as known coeffi- cients for gj + O. 4: return 9 reconstructed at the server.
(t) in vector q(1)
tion, we treat nonzero entry 9; as a substitution error at the j-th entry in a codeword. Then, we use our SCMA scheme shown in Alg. 2 where the messages that the clients send to server can be treated syndromes in Reed- Solomon decoding. Note that in our scheme, the server does not know q()) / E [L] beyond the fact that ΣiE(r (²)) = q. which fits into our privacy criterion. This follows because z(() uniformly distributed over F,, and independently chosen for different l E [L], E [2KL]. For details, please refer Appendix
4.2 PERFORMANCE ANALYSIS
We describe next the performance guarantees of Alg. 1 w.r.t. the objective defined in Eq. 2
5

---

Published as a conference paper at ICLR 2023
Theorem 4.1. Suppose that performed uniform quantization with step size r in Algorithm 7 Then we have B (2, C.)) Ollgg K) (2( O(ndy² log K).
The performance guarantee in Theorem 4.1 per- tains two terms: the approximation of the op- timal objective value and the quantization error (line 3 of Alg. D.. For the first term, the approx- imation factor Ollog" 2 K) is order-optimal for one-shot FC algorithms since one always needs perform rounds of clustering and each round will contribute a factor of (loo K). To make the second term constant w.r.t. n, we can choose (L/VV)), which is good choice practice for the tested datasets as well. The above conclusions hold for any distribution of data across clients. Note that SCMA does not contribute to the distortion as it always returns the exact sum, while other methods for sparse secure aggregation based on sparsification (Han et al. 2020) may introduce emrors and degrade the FC objective. See Appendix D for more details.
(1 +4+3
5, (8) 2 mod p
_ (1-22+4-3'= mod
52 (5.
5/
mod p
6 = (1+2"+4-33 modp
mad
Encoding
( (0,1,4,0)
Decoding
12.14...2
4/ 1'1+'+542 -)= modp
4 (2,6,4.0)
4B (2.1'+5-2" 20)-2"-)))mp33 m
Encoding
( (2,5,0,0)
Figure 2: Example of the SCMA procedure for K 2, L Bdd 4, n 12, 13.
4.3 COMPLEXITY ANALYSIS
We derived a cohort of in-depth analysis pertaining to the computational and communication complex- ity for our proposed FC framework (Alg. []. Due to space limitations, these results are summarized in Appendix
5 MACHINE UNLEARNING VIA SPECIALIZED SEEDING
We first describe an intuitive exact unlearning mechanism (Alg. 3 for K-means clustering in the centralized setting, which will be used later on as the unlearning procedure on the client-sides of the FC framework described in Section 5.3 The idea behind Alg. 3 is straightforward: one needs to rerun the K K-means++ initialization, corresponding to retraining only if the current centroid set C contains at least one point requested for removal. This follows from two observations. First, since the centroids chosen through K-means++ initialization are true data points, the updated centroid set C' returned by Alg. is guaranteed to contain no information about the data points that have been removed. Second, as we will explain in the next section, Alg. also satisfies the exact unlearning criterion (defined in Section 3
5.1 PERFORMANCE ANALYSIS
To verify that Alg. is an exact unlearning method, we need to check that C' is probabilistically equivalent the models generated by rerunning the K-means++ initialization process on X', the set of point remaining after removal. This is guaranteed by Lemma 5.1 and formal proof is provided in Appendix [E]
Lemma 5.1. For any set of data points X and removal set X assuming that the remaining dataset is X' = Xxx and the centroid set returned by Algorithm iis C', we have
F( XR) C) IP(A(())= C); E(o.((';;')) s 8(mn ()") where A represents Algorithm and 4 represents the unlearning mechanism in Algorithm
5.2 COMPLEXITY ANALYSIS
We present next analytical results for the expected time complexity removing a batch It data points simultaneously by our Alg. 3 For this, we consider both random and adversarial removal scenarios. While the analysis for random removal fairly straightforward, the analysis for adversarial removal requests requires to identify which removals force frequent retraining from scratch. In this regard, we state two assumptions concerning optimal cluster sizes and outliers, which will allow us characterize the worst-case scenario removal setting.

---

Published as a conference paper at ICLR 2023
Assumption 5.2. Let = K be constant denoting cluster size imbalance, where Smin equals the size of the smallest cluster in the optimal clustering; when 61 L, all clusters are of size n.
Assumption 5.3. Assume that Eg 2 1 is a fixed constant. An outlier xy in X satisfies 12: og -
||2 - vk [K] and ||:; efl V /=20 (C)))11))
Under Assumptions 5.2 and [.3] we arrive at an
Algorithm 3 Unlcarning via K + Init. I: input: Dataset X, centroid set C obtained by K-means++ initialization on N. re- moval request set Xn (Frg)...;FRR)
estimate for the expected removal time presented in Theorem belobw. Notably, the expected removal time does not depend on the data set size n.
Theorem 5.4. Assume that the number of data points in X n and the probability of the data set containing at least one outlier is upper bounded by O (1/n). Algorithm 3 supports removing R points within min O (RRKdd) (n) for random removals, and expected time min (RKK in expectation for adversarial removals. The com- plexity for complete retraining equals O d).
2:
if c $ XR Vej E C then C² C
3:
4:
else
5:
i (arg miny Cj E NR) -1
single request with expected time
6:
if 0 then
7:
C' - Ø, X' < X² X'
O(n d))
8:
else
9:
C' + (cl.... G.. X'' + XR.
Remark. Due to the distance-based K-means++ initialization procedure, the existence of outliers in the dataset inevitably leads to higher retraining probability. This the case since outliers are more likely to lie in the initial set of centroids. Hence, for analytical purposes, we assume in 1ercorem5544ihee the probability of the data set containing at least one outlier is upper bounded by O (1/m). This is not overly restrictive assumption there exist many different approaches for removing outliers before clustering Chawla & Gionis 2013): Gan &
10:
end if
11:
for -jit,,.... K do
12:
Sample x from x" with prob ((,,C") CT.
13:
C'+Ckf
14:
end for
15:
end if
return C'
Ng
2017): Hauttmaki et al. (2003), which effectively make the probability of outliers negligible.
5.3
UNLEARNING FEDERATED CLUSTERS
We describe next the complete unlearning algorithm for the new FC framework which uses Alg. 3 for client-level clustering. In the FL setting, data resides on client storage devices, and thus the basic assumption of federated unlearning is that the removal requests will only appear at the client side, and the removal set will not be known to other unaffected clients and the server. We consider two types of removal requests in the FC setting: removing It points from one client / (cross-silo, single-client removal), and removing all data points from clients 1....,,e In (cross-device, multi-client removal). For the case where multiple clients want to unlearn only part of their data, the approach is similar to that of single-client removal and can be handled via simple union bounds.
The unlearning procedure is depicted in Alg. 4 For single-client data removal, the algorithm will first perform unlearning at the client (say, client 1) following Alg. 3 If the client's local clustering changes (i.e., client 1 reruns the initialization). one will generate a new vector (() and send the server via SCMA. The server will rerun the clustering procedure with the new aggregated vector o' and generate a new set of global centroids C, Note that other clients do not need to perform additional computations during this stage. For multi-client removals, we follow similar strategy, except that no client needs to perform additional computations. Same as centralized unlearning described in Lemma 5.1 can show that Alg. is also an exact unlearning method.
Removal time complexity. For single-client removal, we know from Theorem 3.4 that the expected removal time complexity of client is min(O(RK2d)) On Kd)) and min{O(RK ()ed), 0( Kd)} for random and adversarial removals, respectively. " denotes the number of data points on client l. Other clients do not require additional computations, since their centroids will not be affected by the removal requests. Meanwhile, the removal time complexity for the server is upper bounded by ((K2LTd) where T is the maximum number of iterations of Lloyd's algorithm at the server before convergence. For multi-client removal, no client needs to perform additional computations, and the removal time complexity for the server equals O(L, RT))
7

---

Published as a conference paper at ICLR 2023
6 EXPERIMENTAL RESULTS
To empirically characterize the trade-off be- tween the efficiency of data removal and per- formance of our newly proposed FC method, we compare it with baseline methods on both syn- thetic and real datasets. Due to space limitations, more in-depth experiments and discussions are delegated to Appendix M
Algorithm 4 Unlearning of Federated Clusters
1: input: Dataset X' distributed on L clients (Z(l)...., X(L)), (C(t), Ny q. C,) obtained by Algorithm [ on X, removal request set x!!1) for single-client removal or CR for multi- client removal.
2: if single-client removal then
Datasets and baselines. We use one synthetic dataset generated by a Gaussian Mixture Model (Gaussian) and six real datasets (Celltype. Cov- type, FEMNIST, Postures, TMI, TCGA) in our experiments. We preprocess the datasets such that the data distribution is non-i.i.d. across dif- ferent clients. The symbol K' in Fig. 3 repre- sents the maximum number of (true) clusters among clients, while K represents the number of true clusters in the global dataset. A detailed description of the data statistics and the prepro- cessing procedure is available in Appendix M Since there is currently no off-the-shelf algo- rithm designed for unlearning federated clusters, we adapt DC-Kmeens (DC-KM) from Ginart et al. (2019) to apply to our problem setting, and use complete retraining as the baseline compari- son method. To evaluate FC performance on the complete dataset (before data removals), include the K-FED algorithm from Dennis et al. ) as the baseline method. In all plots, our Alg, referred to as MUFC. Note that in FL, clients are usually trained in parallel so that the estimated time complexity equals the sum of the longest processing time of a client and the processing time of the server.
3: Run Algorithm on client and update q!
if client has to perform retraining.
4: else
5:
9d)) +- 0 on client I, VI CR-
6: end if
7: Securely sum up g0) server by Algorithm 2 with the aggregated vector denoted as o/-
8: if q' = then
9:
C2 C..
else
11: Generate X" with q'.
12: Run full K-means++ at the server with X²
to obtain C²,,
end if
14:
return Client centroid sets C server data K. d' and centroids C₁
also
Clustering performance. The clustering performance of all methods on the complete dataset is shown in the first row of Tab. The loss ratio is defined as o C.)/ (2 which is the metric used to evaluate the quality of the obtained clusters. For the seven datasets, MUFC offered the best performance on TMI and Celltype, datasets for which the numbers of data points in different clusters are highly imbalanced. This can be explained by pointing out important difference between MUFC and K-FED/DC-KN the quantized centroids sent by the clients may have non-unit weights, and MUFC is essentially performing weighted K-means++ at the server. In contrast, both K-FED and DC-KM assign equal unit weights to the client's s centroids. Note that assigning weights to the client's s centroids based on local clusterings not only enables simple analysis of the scheme but also improves the empirical performance, especially for datasets with highly imbalanced cluster distributions. For all other datasets except Gaussian, MUFC obtained competitive clustering performance compared to K-FED/DC-KM. The main reason why DC-KM outperforms MUFC on Gaussian data is that all clusters are of the same size in this case. Also note that DC-KM runs full K Kmmenns++ clustering for each client while MUFC only performs initialization. Although rumning full K K-means++ clustering at the client side can improve the empirical performance on certain datasets, also greatly increases the computational complexity during training and the retraining probability during unlearning, which is shown in Fig. Nevertheless, we also compare the performance of MUFC with K-FED/DC-KM when running full K K-means++ clustering on clients for MUFC in Appendix M
We also investigated the influence of K' and y on the clustering performance. Fig. 3 a) shows that MUFC can obtain lower loss ratio when K' < K, indicating that data is non-i.i.d. distributed across clients. Fig. 3ib) shows that the choice of 7 does not seem to have a strong influence on the clustering uniform sampling in Step 6 of Alg. to
performance of Gaussian datasets, due to the fact that generate the server dataset. Meanwhile, Fig. ()) shows that can have a significant influence on the clustering performance of real-world datasets, which agrees with analysis in Theorem 4.1
(X) approximated by running K K-means++ multiple times and selecting the smallest objective value.
8

---

Published as a conference paper at ICLR 2023
Table 1: Clustering performance of different FC algorithms compared to centralized K-means++ clustering.
TMI
Celltype
Gaussian
TCGA
Postures
FEMNIST
Costype
MURC
1.24
1.14 + 0.03
1.25 + 0.02
1.18 0.05
1.10 + 0.01
1.20 4 0.00
1.03 + 0.02
Loss ratio
K-FED DC-KM
18440.000
1,72 + 0.24
1.25 = 0.01
1.56 + 0.11
1.13 + 0.01
1.21 = 0.00
1.60 + 0.01
1.14
1.46 0.01
0.00
1.15
1.03
0.00
0.00
1.03
Spood-up of MUFC retraining is performed)
151x
1535x
2074x
483x
613x
53x
267x
1.43
Goussan
Gaamen 6-1,6--
3.27
1.25
3.20
1:34
1.20
3.22
322
159
101
10
101
(8)
(b)
(c)
son-
sor K-4
Collype souidd 2.K
327
DC coean joi evergee spendiut veturra di
DC Kineas Ihs everage
DC Kenaro overge spree-4) (ecemm))
(C eriaass (fr Aeetage speed
ong
hurner rrmooda
Tranbor of renouat
Nurte namoods
Narber direeves
(6)
(8)
(h)
214
TOSAA ii 2od
300
10P
Posdumss moni 2
110
RENANEST roaidd A' 6.8
Cinfusti toe cud. K K=3
327
100
overage
MUPC ovcrage
average speniiu)
speid
krmans
Hersnanng
Rerarinng
Raraiinng
200
400
300
200
Manter
(i)
(8)
(
The shaded areas represent the standard deviation of results from different trails. (a) Influence of data heterogeneity on the clustering performance of MUFC: K' represents the maximum number of (global) clusters covered by the data at the clients, while K' = 10 indicates that the data points are i.i.d. distributed across clients, (b)(c) Influence of the quantization step size 7 on the clustering performance of MUFC. The red vertical line indicates the default choice of = 1///n, n. where n is the total number of data points across clients. (d) The change in the loss ratio after each round of unlearning.
Figure 3:
(e) The accumulated removal time for adversarial removals. (f-(() The accumulated removal time for random removals.
The red vertical line in both figures indicates the default choice of 7 = 1/vTi, where n stands for the number of total data points across clients.
Unlearning performance. Since K-FED does not support data removal, has high computational complexity, and its empirical clustering performance is worse than DC-KM (see Tab. [ we only compare the unlearning performance of MUFC with that of KC. For simplicity, we consider removing one data point from a uniformly random chosen client at each round of unlearning. The second row of Tab. [ records the speed-up ratio w.r.t. complete retraining for one round of MUFC unlearning (Alg. when the removed point does not lie in the centroid set selected at client l. Fig-Bje) shows the accumulated removal time on the TMI dataset for adversarial removals, which are simulated by removing the data points with the highest contribution to the current value of the objective function at each round, while Fig. (1) shows the accumulated removal time on different datasets for random removals. The results show that MUFC maintains high unlearning efficiency compared to all other baseline approaches, and offers an average speed-up ratio of 84x when compared to complete retraining for random removals across seven datasets. We also report the change in the loss ratio of MUFC during unlearning in Fig. dd) The loss ratio remains nearly constant after each removal, indicating that our unlcarming approach does not significantly degrade clustering performance. Similar conclusions hold for other tested datasets, as shown in Appendix M

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
The seven datasets used in our simulations are all publicly available. Among these datasets, TCGA and TMI contain potentially sensitive biological data and are downloaded after logging into the database. We adhered to all regulations when handling this anonymized data and will only release the data processing pipeline and data that is unrestricted at TCGA and TMI. Datasets that do not contain sensitive information can be downloaded directly from their open-source repositories.
REPRODUCIBILITY STATEMENT
Our implementation is available at https: htwplbbbe.t..sp/gggg.......////o htttss///ghhbbb..oo///hhhhhh//// instructions are included in the source code.
Detailed
ACKNOWLEDGMENT
This work was funded by NSF grants 1816913 and 1956384. The authors thank Eli Chien for the helpful discussion.
10

---

Published as a conference paper at ICLR 2023
REFERENCES
Jayadev Acharya and Ziteng Sun. Communication complexity in locally private distribution estimation and heavy hitters. In International Conference on Machine Learning, pp. 51-60. PMLR, 2019.
Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni. Streaming k-means approximation. Advances in neural information processing systems, 22, 2009.
Constance Beguier, Mathicu Andreux, and Eric W Tramel. Efficient sparse secure aggregation for federated learning. arXiv preprint arXiv:2007. 20886, 2020.
James Henry Bell, Kallista A Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure single-server aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1253-1269, 2020.
Elwyn R. Berlckamp. Algebraic coding theory. In McGraw-Hill series in systems science, 1968.
Jock A Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and electronics in agriculture, 24(3):131-155 1999.
Kallista Bonawitz, Peter Kairouz, Brendan McMahan, and Daniel Ramage. Federated learning and privacy: Building privacy-preserving systems for machine learning and data science on decentralized data. Queue, 19(5)87-114, 2021.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Chooe Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159. IEEE, 2021.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. LEAF: A Benchmark for Federated Settings. arXiv preprint arXiv:1812.01097. 2018
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium on Security and Privacy, pp. 463-480. IEEE, 2015.
Sanjay Chawla and Aristides Gionis, k-means-: A unified approach to clustering and outlier detection. In Proceedings of the 2013 SIAM international conference on data mining, pp. 189-197. SIAM, 2013.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. Graph unlearning. arXiv preprint 1033:::003314999 2021.
Wei-Ning Chen, Peter Kairouz, and Ayfer Ozgur. Breaking the communiction-pivvay-ccrrm trilemma. Advances in Neural Information Processing Systems, 33:3312-3324, 2020.
Wei-Ning Chen, Christopher A Choquette Choo, Peter Kairouz, and Ananda Theertha Suresh. The fundamental price of secure aggregation in differentially private federated learning. In International Conference Machine Leurning, pp. 3056-3089. PMLR, 2022.
Eli Chien, Chao Pan, and Olgica Milenkovic, Certified graph unlearning. NewrlPS 2022 Workshop: New Frontiers in Graph Leurning, 2022. URL https: penttss:/oppnsee /ttp:://///eeeeee..oom net forum? id=
Eli Chien, Chao Pan, and Olgica Milenkovic. Efficient model updates for approximate unlearning of graph-structured data. In The Eleventh International Conference on Learning Representations, 2023. URL http:p////.ooeeeeeeeeeeee/e//a// http://wwww.....ooo.oooooooooooa

---

Published as a conference paper at ICLR 2023
Jichan Chung, Kangwook Lee, and Kannan Ramchandran. Federated unsupervised clustering with generative models. In AAAI 2022 International Workshop on Trustable, Verifiable and Auditable Federated Learning, 2022.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. EMNIST: Extending MNIST to handwritten letters. 2017 international joint conference on neural networks (IJCNN), pp.
2926.2926. IEEE, 2017.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255, Icee, 2009.
Don Kurian Dennis, Tian Li, and Virginia Smith. Heterogeneity for the win: One-shot federated clustering. In International Conference on Machine Learning, pp. 2611-2620. PMLR, 2021.
Alfredo Eisinberg and Giuseppe Fedele. On the inversion of the vandermonde matrix. Applied mathematics and computation, 174(2):1384-1333 2006.
Irem Ergun, Hasin Us Sami, and Basak Guler. Sparsified secure aggregation for privacy-preserving federated learning. arXiv preprint arXiv:2112.128722 2021.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pp. 1322-1333, 2015.
Keith Frikken. Privacy-preservee set union. In International Conference on Applied Cryptography and Network Security, pp. 237-252. Springer, 2007.
Shaopeng Fu, Fengxiang He, and Dacheng Tao. Knowledge removal in sampling- bayesian
inference. In International Conference on Learning Representations, 2022. URL https://
openreview Beeenreview.ett/frrrreeeee wtw.ee/ooooommdddoooootoeto
Guojun Gan and Michael Kwok-Po Ng. K-means clustering with outlier removal. Pattern Recognition Letters, 90:8- 14, 2017.
Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector quantized stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, pp. 2197-2205. PMLR, 2021.
Andrew Gardner, Christian A Duncan, Jinko Kanno, and Rastko Selmic. 3D hand posture recognition from small unlabeled point sets. In 2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 164-169. IEEE, 2014a.
Andrew Gardner, Jinko Kanno, Christian A Duncan, and Rastko Selmic. Measuring distance between unordered sets of different sizes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 137-143, 2014b.
Jonas Geiping. Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients-how easy to break privacy in federated learning? Advances in Neural Information Processing Systems, 33: 13:3777777947, 2020.
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. Advances in Neural Information Processing Systems, 33:19586- 19597, 2020.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making AI forget you: Data deletion in machine learning. Advances in neural information processing systems, 32, 2019.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Etemaal sunshine of the spotless net: the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 9304-9313 2020a.
Selective forgetting in deep networks. In Proceedings the
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. In European Conference on Computer Vision, pp. 383-398. Springer, 2020b.
12

---

Published as a conference paper at ICLR 2023
Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O' O'Callaghan. Clustering data streams: Theory and practice. IEEE transactions on knowledge and data engineering, 15(3): 515-528, 2003.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3842. PMLR, 13-18 Jul 2020.
Pengchao Han, Shiqiang Wang, and Kin Leung. Adaptive gradient sparsification for efficient federated learning: An online learning approach. In 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS), pp. 300-310. IEEE, 2020.
Xiaoping Han, Renying Wang, Yincong Zhou, Lijiang Fei, Huiyu Sun, Shujing Lai, Assieh Saadat- pour, Ziming Zhou, Haide Chen, Fang Ye, al. Mapping the mouse cell atlas by microwell-seq. Cell. (7255)1001--1007 2018.
John A Hartigan and Manchek A Wong. Algorithm as 136: A k-means clustering algorithm. Journal of the royal statistical society. series с (applied statistics), 28(1):100-108, 1979.
Ville Hautamäki, Svetlana Cherednichenko, Ismo Kärkkäinen, Tomi Kinnunen, and Pasi Fränti. Improving k-means by outlier removal. In Scandinavian conference on image analysis, pp. 978- 987. Springer, 2005.
Carolyn Hutter and Jean Claude Zenklusen. The Cancer Genome Atlas: Creating Lasting Value beyond Its Data. Cell, 173(2):283-28) 285, 2018.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Kiran S Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. SIAM Journal on Computing, 1066):1767-1802, 2011.
Lea Kissner and Dawn Song. Conference, pp. 241-257. Springer, 2005.
set operations. In Annual International Cryptology
Euiwoong Lee, Melanie Schmidt, and John Wright, Improved and simplified inapproximability for k-means. Information Processing Letters, 120:40-43, 2017.
Songze Li, Sizai Hou, Baturalp Buyukates, and Salman Avestimehr. Secure federated clustering. arXiv preprint arXiv:2205. 2022.
Gaoyang Liu, Xiaoqiang Ma, Yang Yang, Chen Wang, and Jiangehuan Liu. Federaser: Enabling efficient client-level data removal from federated learning models. In 202/ IEEF/ACM 29th International Symposium on Quality of Service (IWQOS), pp. 1-10. IEEE, 2021.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan. The planar k-means problem is np-hard. Theoretical Computer Science, 442:13-21, 2012.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning. arXiv preprint arXiv:2002. 10611 2020.
James Massey, Shift-register synthesis and bch decoding. IEEE transactions Information Theory, 15(1):122-127, 1969.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication- efficiiet learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1282-1282. PMLR, 2017.
13

---

Published as a conference paper at ICLR 2023
Chao Pan, Eli Chien, and Olgica Milenkovic. Unlearning graph classifiers with limited data resources. In The Web Conference, 2023.
Jane Peterson, Susan Garges, Maria Giovanni, Pamela McInnes, Lu Wang, Jeffery A Schloss, Vivien Bonazzi, Jean E McEwen, Kris A Wetterstrand, Carolyn Deal, al. The NIH Human Microbiome Project. Genome research, 19(12):337-22233 2009.
Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics, 8(2):300-304 1960.
Felix Sattler, Klaus-Robels Müller, and Wojciech Samek. Clustered federated learning: Model- agnostic distributed multitask optimization under privacy constraints. IEEE transactions neural networks and learning systems, 32())3370-3372,, 2020.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh, Remember what you want to forget: Algorithms for machine unlearning. Advances Neural Information Processing Systems, 38:18075-11 1 2021.
Jae Hong Seo, Jung Hee Cheon, and Jonathan Katz. Constant-round multi-party private set union using reversed laurent series. International Workshop on Public Key Cryptography, pp. 398-412. Springer, 2012.
Jinhyun So, Corey J Nolet, Chien- Shiien-Sheng Yang, Songze Li, Qian Yu, Ramy E Ali, Basak Guler, and Salman Avestimehr. Lightsecagg: a lightweight and versatile design for secure aggregation in federated learning. Proceedings of Machine Learning and Systems, 4:694-720, 2022.
Cathie Sudlow, John Gallacher, Naomi Allen, Valerie Beral, Paul Burton, John Danesh, Paul Downey, Paul Elliott, Jane Green, Martin Landray, et al. Uk biobank: an open access resource for identifying the causes of wide range of complex diseases of middle and old age. PLOS medicine, 12(3): e1001779, 2015.
Bart Thomee, David A Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li. Yfec100m: The new data multimedia research. Communications of the ACM, 59(2):64-73, 2016.
Sergei Vassilvitskii and David Arthur. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1027-1035, 2006.
Michael Veale, Reuben Binns, and Lilian Edwards. Algorithms that remember: model inversion attacks and data protection law. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 376(2133):2018000) 2018.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. field guide to federated optimization. arXiv preprint arXiv:2107 :10.::::07.0011... 2021.
Junxiao Wang, Song Guo, Xin Xie, and Heng Qi. Federated unlcarning via class-discrmminative pruning. In Proceedings of the ACM Web Conference 2022, pp. 622-632, 2022.
Chen Wu, Sencun Zhu, and Prasenjit Mitra. Federated unlearning with knowledge distillation. arXiv preprint 4rX14:2201.09441, 2022.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019.
14

---

Published as a conference paper at ICLR 2023
A RELATED WORKS
Federated clustering. The idea of FC is perform clustering using data that resides at different edge devices. It is closely related to clustered FL (Sattler et al., 2020). whose goal is to learn several global models simultaneously, based on the cluster structure of the dataset, as well as personalization according to the cluster assignments of client data in FL (Mansour et al. 2020). One difference between FC and distributed clustering (Guha et al., 2003 Ailon et al. 2009) is the assumption of data heterogeneity across different clients. Recent works (Ghosh et al.] 2020 Dennis et al., 2021] [Chung (ct al. 2022) exploit the non-i.i.d nature of client data to improve the performance of some learners. Another difference pertains to data privacy. Most previous methods were centered around the idea of sending exact (Dnnns et al. 2021 or quantized client (local) centroids (Ginart et al. 2019) to the server, which may not be considered private it leaks the data statisties cluster information of all the clients. To avoid sending exact centroids. Li et al.) (2022) proposes sending distances between data points and centroids the server without revealing the membership of data points to any of the parties involved. Note that there is currently no formal definition of computational or information-theoreee secrecy/privacy for FC problems, making it hard to compare methods addressing different aspects of FL. Our method introduces a simple-to to-el-trnnncann clustering process and new privacy mechanism that is intuitively appealing as involves communicating obfuscated point counts of the clients to the server.
Sparse secure aggregation. Sparse secure aggregation aims to securely aggregate local models in a coamuuiccation-effiiiee fashion for the case that the local models are high- -igh-dimensional but sparse. Existing works on sparse secure aggregation (Beguier et al., 2020 Ergun et al. (222)) either have a communication complexity that is linear in the model dimension, or they can only generate an approximation of the aggregated model based on certain sparsification procedures (Han et al., 2020). In comparison, our SCMA scheme can securely recover the exact sum of the input sparse models with communication complexity that is logarithmic in the model dimension.
Private set union. The private set union KKsssner& & Song 2005 Frikken| 2007| Sco et al. 2012) is a related but different problem compared to sparse secure aggregation. It requires multiple parties to communicate with each other to securely compute the union of their sets. In SCMA we aggregate multisets, which include the frequency of each element that is not considered in the private set union problem. In addition, our scheme includes only one round of communication from the clients to the server, while there is no server in the private set union problem but multi-round client to client communication is needed.
Machine unlearning. For centralized machine unlearning problems, two types of unlearning requirements were proposed in previous works: exact unlearning and approximate unlearning. For exact unlearning. the unlearned model required to perform identically as a completely retrained model. To achieve this, Cao & Yangl (2015) introduced distributed learners, [Bourooue et al. (2021) proposed sharding- based methods, Ginart et al. (2019) used quantization to eliminate the effect of removed data in clustering problems, and and [Cen et al. (202T) applied sharding-based based methods to Graph Neural Networks. For approximate unlcarning, the "differences" in behavior between the unlearned model and the completely retrained model should be appropriately bounded, similarly to what is done in the context of differential privacy. Following this latter direction, Guo et al. (2020) introduced the inverse Newton update for linear models, (Sekhari al. (2021) studied the generalization performance of approximately unlearned models, Fu et al. (2022) proposed an MCMC unlearning algorithm for sampling-basee Bayesian inference, Golatkar et al. (2020a] b) designed model update mechanisms for deep neural networks based on Fisher Information and Neural Tangent Kernel, while Chien et al. (2022) 2023); Pan al. (023) extended the analysis Graph Neural Networks. A limited number of recent works also investigated data removal in the FL settings: Liu et al. (202I) proposed to use fewer iterations during retraining for federated unlearning, Wu et al. (2022) introduced Knowledge Distillation into the unlearning procedure to eliminate the effect of data points requested for removal, and Wang et al. (2022) considered removing all data from one particular class via inspection of the internal influence of each channel in Convolutional Neural Networks. These federated unlearning methods are (mostly) empirical and do not come with theoretical guarantees for model performance after removal and/or for the unlearning efficiency. In contrast, our proposed FC framework not only enables efficient data removal in practice, but also provides theoretical guarantees for the unlearned model performance and for the expected time complexity of the unlearning procedure.
learners,Bourtoulle
15

---

Published as a conference paper at ICLR 2023
B K-MEANS++ INITIALIZATION
The K-means problem is NP hard even for K = 2, and when the points lie in two-dimensional Euclidean space (Mahajan et al. 2012). Heuristic algorithms for solving the problem, including Lloyd's (Looyd 1982) and Hartigan's 's method (Hartigan & Wong 1979), , are not guaranteed to obtain the global optimal solution unless further assumptions are made on the point and cluster structures (Lee al. 2017). Although obtaining the exact optimal solution for the K-means problem is difficult, there are many methods that can obtain quality approximations for the optimal centroids. For example, a randomized initialization algorithm (K (K-means++) was introduced in Vassilvitski & Arthur (2006) and the expected objective value after initialization is a (log K) apprrxxxxmtto to the optimal objective (B())= S (8 In K + 16) K-means++ initialization works as follows: initially, the centroid set C is assumed to be empty. Then, point is sampled uniformly at random from X for the first centroid and added to C. For the following K rounds, a point x from X is sampled with probability d' (x, C) C) for the new centroid and added to C. Here, d(z, C) denotes the minimum f2 distance between x and the centroids in C chosen so far. After the initialization step, we arrive at K initial centroids in C used for running Lloyd's algorithm.
C COMPLEXITY ANALYSIS OF ALGORITHM
Computational complexity of client-side clustering. Client-side clustering involves running K- means++ initialization procedure, which is of complexity (n)
Computational complexity of server-side clustering. Server-side clustering involves running K-means++ initialization procedure followed by Lloyd's algorithm with T iterations, which is of complexity O(K2
Computational complexity of SCMA at the client end. The computation of s(D) on client / requires at most O(K log i) multiplications over F,, E [2KL]. The total computational complexity equals O(K² Log L)) multiplication and addition operations over Fp.
Computational complexity of SCMA at the server end. The computational complexity at the server is dominated by the complexity of the Barckampp-assee decoding algorithm (Berlekamp) 1968 Massey 1969), factorizing the polynomial g(x) over Fp (Kedlaya & Umans 2011 and solving
the linear equations S: ΣiE(r)
((()) = Ej 4 qj j²-1 with known j. 9j * The complexity
of Berlekaam-p Massey decoding over F, is 3 2)). The complexity of factorizing a polynomial g(x) over F, using the algorithm in Kedlaya & Umans (011 is (((K)) log + KL lol''" p)
operations over Fp- The complexity of solving for S. = EiE(Z) S equals that of finding the inverse of Vandermonde matrix, which takes O(K2 operations over Fp (Eisinberg & Fedele 2006). log p
Hence, the total computational complexity the server side is KL Kolog p)} operations over Fp.
Communication complexity of SCMA at the client end. Since each s can be represented by [log pk bits, the information (5 ]E|2K1) sent by each client I can be represented by 2K L < max maxx2K77 T. log n, 2K T.d log B} bits. Note that there at most ΣmE(KE] (z)) (a",) q-ary vectors of length Bd, Hence, the cost for communicating q( from the client to server / is at max{O(KI L log n), O(K Ld log B)} bits, which implies that our scheme is order-optimal w.r.t. the communication cost. Note that following standard practice in the area, we do not take into account the complexity of noise generation in secure model aggregation, as it can be done offline and independently of the Reed-Solomon encoding procedure.
least log (KE))) (4") ((r))
D PROOF OF THEOREM 4.
Proof. We first consider the case where no quantization is performed (Algorithm 5) The performance guarantees for the federated objective value this setting are provided Lemma D.I
16

---

Published as a conference paper at ICLR 2023
Lemma D.1. Suppose that the entire data across clients is denoted by X, and the of server centroids returedd by Algorithm is C.. Then we have
E ( C.)) < Ollgg K) .))
Proof. Let C* denote the optimal set of centroids that minimize the objective (T) for the entire dataset X 1R let C E Rn be the matrix that records the closest centroid in C* to each data point, C, the set of centroids returned by Alg. 1 and C₂ E R the matrix that records the corresponding centroid in C2 for each data point based on the global clustering defined in Definition 33. perform K K-means++ initialization on each client dataset, for client it holds
Since we
IE -c - (8 In K + 16) - 12
W [4]
S (8 In K 16) Cr
where ( E I xd optimal solution that can minimize the local K-means objective for client I, and (*,(0) denotes the row in C* that corresponds client Summing up over all clients gives
xd records the closest centroid in (( to each data point a. in 200 c is the
E
Σ |x EII
-000
< (8InK + 16) Σ |X 1E.
(4)
At the server side the client centroids are reorganized into a matrix X, 1 The weights of the client centroids are converted to replicates of rows in X,. Since we perform full K K-means++ clustering at the server, it follows that
E (1 C.Il²) E
|0000 c(O
(a) S (8ln K + 16)
Σ -c.o11?)
S (8In + 16)
Σ E
(5)
where C... E R is the optimal solution that minimizes the K-means objective at the server. worth pointing out that C.,, is different from C*, as they are optimal solutions for different optimization objectives. Note that we still keep the expectation on RHS for (a). The randomness comes from the fact that CO)) is obtained by K-means++ initialization, which is probabilistic procedure.
Combining and
results in
E E C.)) E
|x 1
< 2 E
(1X00) - c(0 + ||C
- +
-I
1
< (166 in + 32)
Σ
+ -c.00'>
-c (6)
For E (IIC
- cx.(0) we have
E ((CO0 ((=
< 2. E -x +|x(0 - c+,(0)113))
- 11
= (x()) (t2 +2 E (ICO) - xx
Replacing 7 into 6 shows that E (,b C.)) < Ollog² K) (X),,, which completes the proof.
17

---

Published as a conference paper at ICLR 2023
If we are only concerned with the performance of non-outlier points over the entire dataset, we can upper bound the term E E ||C*0) Cx,(0)1) 11: by
Σ | Ic0) -r:00 1B/ (x))
E
(8)
Here, we used the fact that rows of (+) are all real data points sampled by the K-means++ initial- ization procedure. For each data point æ4, it holds that ||x, cf [;; S (C;), where z; E C₁ In this case, we arrive at E (Z;; C.)) < O(e log K) o (X,,, where 2r corresponds to all non-outlier points.
Remark. In Theorem 4 of et al. (2003) the authors show that for the distributed K K-median problem, if we use (b) apprrxxiiinnnnnnn algorithm (i.e., &b S O(b) 6²) for the K K-median problem with subdatasets on distributed machines, and use a approxxipoinnaaooonn algorithmm for the K-median problem on the centralized machine, the overall distributed algorithm achieves effectively (bb))- approximation of the optimal solution to the centralized K K-median problem. This is consistent with our observation that Alg. can offer in expectation a O(log" K) approxxmmaii to the optimal solution of the centralized K -means problem, since K +-means++ initialization achieves O(log K)- approximation on both the client and server side.
We also point out that in Dennis et al. (2027) the authors assume that the exact number of clusters from the global optimal clustering client is known and equal to K(), and propose the K-FED algorithm which performs well when K' = max(e[L] K() < VK. The difference between K' and K represents the data heterogeneity across different clients. With a slight modifications of the proof, we can also obtain E ( (X'; C.)) < Ollo K loo K') (2)). when K(t is known for each client beforehand, and perform -manss++++++ + client I instead of K-means++ in Alg. I For the extreme setting where each client safeguards data of one entire cluster (w.rt. the global optimal clustering (L = K, K' = =1)), the performance guarantee for Alg. [becoes E (o C.)) O(1) 66 (X), which is the same as seeding each optimal cluster by a data point sampled uniformly at random from that cluster. From Lemma 3.1 of Vassilvitskii & Arthur (2006) we see that we can indeed have E (X; C.)) = (X),, where the approximation factor does not depend on K. This shows that data heterogeneity across different clients can benefit the entire FC framework introduced.
Next we show the proof for Theorem 4.1 Following the same idea as the one used in the proof of Lemma D.I we arrive at
[(, E
Σ
-xx0
- 10 +10 - + +1000 -100-C9113)) .
(9)
where (00) is the quantized version of C(O), The first term can be upper bounded the same way as in Lemma D.I For the second term, the distortion introduced by quantizing one point is bounded by vdx if we choose the center of the quantization bin as the reconstruction point. Therefore, 2
1.
Vdg
2
nd?
Σ
|000 - -
Sn n
(10)
2
4
The third term can be bounded as
E 10w0 - s (8ln + 16)
Σ c²
1=1
(10t) - -
s E (1170 - c00 |2+ + -
x 12 + ||x(0) cr.10112) (11)
Replacing
(10) and
into
9
leads to
E (o)((( < Ollog" K) o², + Ondy² log K),
which completes the proof. Similar as in Lemma D.I. we can have that for non-outlier points X,, E (X;; C,)) < O(ea log K) (x,) O(nd 2 log K).
18

---

Published as a conference paper at ICLR 2023
E PROOF OF LEMMA 5.1
Proof. Assume that the number of data points in X' is n. the size of XR is R. and the initial centroid set for X is C. We use induction to prove that C' returned by Alg. probabilistically equivalent to rerunning the K + initialization on X' X'
The base case of induction amounts to investigating the removal process for c1, the first point selected by K K-means++. There are two possible scenarios: с1 Ag and & Xg. In the first case, we will rerun the initialization process over X", which is equivalent to retraining the model. In the second case, since we know É Xn, the probability of choosing ei from X' as the first centroid equals the conditional probability
P(choose e1 from A' as the first centroid & Xx)
R PP(choose ei from X as the first centroid).
Next suppose that K 1, min, ej xR) The centroids C; [c-- G---
G-13 returned by Alg. can be viewed probabilistically equivalent to the model obtained from rerunning the initialization process over X' for the first - 1 rounds. Then we have
P(choose e; from X' as i-th centroid/e, c; $ xx) Píchoose c; from X' as i-th centroid C & Xn))
P((c & XR)
(a) P(choose a; from X' as i-th centroid)
PP(c, $ Xn)
d( C/ C
Enexa d(xr, C/-1)/o C,-1)
lc,,, O Ci-1)
6a(2;; C/11"//11/00 CL1)
de C/-1)
"e(X';
P(choose o; from X' as i-th centroid),
where (a) holds based on the definition of i, indicating that the i-th centroid is not in Xg. Therefore, the centroid o: c returned by Alg. can be seen as if obtained from rerumning the initialization process over X" in the i-th round. Again based on the definition of i, is clear that for j > i, C are the centroids chosen by the K-means++ procedure over X'. This proves our claim that C' returned by Alg. is probabilistic equivalent to the result obtained by rerunning the K K-means++ initialization on X"
Theorem 1.1 of Vassivitskii & Arthur (2006) then establishes that
Elp.(X'; C')) s 8(In K + (2'),
(12) L
which completes the proof.
F PROOF OF THEOREM 5.4
Proof. We first analyze the probability of rerunning K-means++ initialization based Alg. Assumptions an2 and 5.3 can be used to derive an expression for the probability of x; E C (where I;; the point that needs be unlearned), which also equals the probability of retraining.
Lemma F.1. Assume that the number of data points in X' is n and that the probability of the data set containing at least one outlier is upper bounded by O (1).). Let C he the centroid set obtained by running K K-means++ X. For arbitrary removal set X' X of size R, we have
for random removals: P(XR n C Ø) O (RK/n))
for adversarial removals: (P n C Ø) O (RK2e1e2/))
19

---

Published as a conference paper at ICLR 2023
Proof. Since outliers can be arbitrarily far from all true cluster points based on definition, during initialization they may be sampled as centroids with very high probability. For simplicity of analysis, we thus assume that outliers are sampled as centroids with probability 1 if they exist in the dataset, meaning that we will always need to rerun the K-means++ initialization when outliers exist in the complete dataset before any removals.
For random removals, where the point requested for unlearning. 24, is drawn uniformly at random from X, it is clear that P(a, E C) K, since C contains K distinct data points in X. To
For adversarial removals, we need to analyze the probability of choosing xy as the (k + 1-th centroid, given that the first & centroids have been determined and x; & C2 (c1,...,cca ,... For simplicity first assume that there is no outlier in X' Then we have
df (zi CK) P(choose x; from X' as the (k + 1) centroid Cx)= - Lyzer (y, C&) + (xi C+)
(13)
For the denominator Ense, dyy Cx) + dx Ck), the following three observations are in place
Σ dyy, Ck) + d (z. C+) 2 xx 2 (C)),, E C₁
Σ d (yy, Ck) + 82 (zi: Cx) N Σ Cly C*)
Σ dl Cx) + (z: Ct) 2 Ely
Therefore,
Ed +c), Ck) 2
(C))
2
el &( Ct))
5
5
MA
(a) 1 2
0.
(C)))
Σ 1la c21 y
(14)
5
where Cy. ot are the closest centroid in C₁ and C* to y. respectively. Here, (a) is a consequence of
the fact that Ila - bll2 = |la - c + c- b112 < 2(Iaa - cll + ||b c Since F; is not an outlier for
C based our assumption, we have
(C)))
20 - 2 2
n Kε₁62
12 of
E2
Consequently,
C
(C(C;) Σ
1cg c,,1²
o3 1 + Σ
Ie, - cGll
62
VEC;
C
|
1/1 +
1c, 1?11?
(15)
62
FEC;
For Vy E Ct hold ||= - c2113 + ||cy - c/12 2 1 || c/11 > z
1 (xi, Ck). Thus, 15
can be
lower bounded by
G7 |||
1
11 + - -112 >
d(;
C2) 2 2Ke
d( Ct).
(16)
62
Deg
VEC;
Combining (16) and 14 obtain
Σ
d (v. Ck) + (x Cc) 2
al Ct).
10K
20

---

Published as a conference paper at ICLR 2023
Using this expression in 13
results in
10Ke162
Pichoose T2 from X' as the (A + 1)-th centroid C f
(17)
which holds for Ak E [K]. Thus, the probability P(æ; E C) can be computed as
P(x, C)
P(choose 2; from X' the (I 1)-th Cantroid/22)P(C
K
Σ
P(choose æi from X' the (A: 1)-th centroid(Cr)
10K(K 1)E1c2 <0
K KK
(18)
n
n
n
Here, we assumed that C. Ø.
For the case where outliers present in the dataset, we have
F(x; E C) = =P(;; E Cla, is outlier) ; is outlier) + P(a; E C| is not outlier)P((;; is not outlier)
K 2162 1<0
K K
$1.0 +0
which completes the proof for the adversarial removal scenario. Finally, by union bound we can have that for the removal X' of size R,
RK
random removals: P(Xn nc + Ø0) <
|RK2
adversarial removals: P(Xx nC Ø) 0
Also, the probability naturally satisfies that
P( 1.
Next show the proof for Theorem 5.4 The expected removal time for random removals can be upper bounded by
[(Removal time)
E Removal new initialization needed) initialization needed)+ +
E Removal time new initialization not needed) [Peww initialization not needed)
<OnnK RK) - RK + +(RK)
<O(R22d).
Following similar argument, we can also show that the expected removal time for adversarial removals can be upper bounded by O O(RK3 And based on our Algorithm 3 the unlearning complexity for both types of removal requests would be always upper bounded by the retraining complexity O(nKd) as well, which completes the proof.
G COMPARISON BETWEEN ALGORITHM AND QUANTIZED K K-MEANS
In Ginart al. (201)), quantized K K-means were proposed solve a similar problem of machine unlearning in the centralized setting. However, that approach substantially differs from Alg. First, the intuition behind quantized K-means is that the centroids are computed by taking an average, and the effect of small number of points is negligible when there enough terms left in the clusters after removal. Therefore, we quantize all centroids after each Lloyd's 's iteration, the quantized centroids will not change with high probability when remove small number of points from the
21

---

Published as a conference paper at ICLR 2023
dataset. Meanwhile, the intuition behind Alg. B is described in Lemma F.1 Second, the expected removal time complexity for quantized K-means equals O (R'K which is high since one needs to check if all quantized centroids remain unchanged after removal at each iteration, where T denotes the maximum number of Iloyddss iteration before convergence and e is some intrinsic parameter. In contrast, Alg. only needs O (1 even for adversarial removals, Also note that the described quantized K -means algorithm does not come with performance guarantees on removal time complexity unless it is randomly initialized.
H QUANTIZATION
minjez For uniform quantization, we set 0 = 7=aaaa))))))))))))) where a(y) = arg min jez -0-. E P The parameter y > 0 determines the number of quantization bins in each dimension. Suppose all client data lie in the unit hypercube centered at the origin, and that if needed, pre-processing is performed to meet this requirement. Then the number of quantization bins in each dimension equals B y while the total number of quantization bins for d dimensions is B ym
In Section 4 remarked that one can generate 9 points by choosing the center of the quantization bin as the representative point and endow it with a weight equal to qj. Then, in line 7, we can use the weighted K-means++ algorithm at the server further reduce the computational complexity, since the effective problem size at the server reduces from n to KL. L. However, in practice we find that when the computational power of the server is not the bottleneck in the FL system, generating data points uniformly at random within the quantization bins can often lead to improved clustering performance. Thus, this is the default approach for our subsequent numerical simulations.
I SIMPLIFIED FEDERATED K-MEANS CLUSTERING
When privacy criterion like the one stated in Section 3 is not enforced, and as done in the framework of Dennis al. (2021). one can skip line 3-6 in Alg. lnd send the centroid set C(') obtained by client
I along with the cluster sizes (Ic()) l..., (())
K |) directly to the server. Then, one can run the weighted K K-means++ algorithm at the server on the aggregated centroid set obtain C,, The pseudocode for
this simplified case is shown in Alg. 5 It follows similar idea as the divide-and-on divide-and-conquer schemes
of Guha et al. (2003) Ailon al. 2009), developed for distributed clustering.
Algorithm 5 Simplified Federated K-means Clustering
1: input: Dataset X' distributed on L clients (2) ....., X,())).
2: Run K-means++ initialization each client in parallel, obtain the initial centroid sets ((),
and record the corresponding cluster sizes (ic""),..., |0 )) AI [L].
3: Send ......,..)
(1)
along with the corresponding cluster sizes (Ict")....,
to the server,
VI E [Z].
4: Concatenate (c.,...,.)) ck as rows of X, and set (Ic(),,..,, 1c2,1 as the weights for the
corresponding rows, VI E [L].
5: Run full weighted K K-means++ clustering at server with X. obtain the centroid set server C..
6: return Each client retains their centroid set ( while the server retains X, and C,,
In line of Alg. weighted K K-means++ would assign weights to data points when computing the sampling probability during the initialization procedure and when computing the average of clusters during the Lloyd's iterations. Since the weights we are considering here are always positive integers, weighted data point can also be viewed as there exist identical data points in the dataset with multiplicity equals to the weight.
We can also add random shifts during quantization as proposed in Ginart al. 2019) to make the data appear more uniformly distributed within the quantization bins.
22

---

Published as a conference paper at ICLR 2023
J THE UNIQUENESS OF THE VECTOR GIVEN {Si) (EpKRT]
To demonstrate that the messages generated by Alg. 2 can be uniquely decoded, we prove that there exists a unique q that produces the aggregated values {Si at the server. The proof by contradiction. Assume that there exist different vectors and q' that result in the same {S: (E(x In this case, we have the following set of linear equations Ej (h.j"=1~} - Lig of- j = 0, E L]. Given that {Ø * 0} and {1} o * 0} represent at most 2K unknowns and j coefficients, the linear equations can be described using a square Vandermonde matrix for the coefficients, with the columns of the generated by indices of the nonzero entries in q. This leads contradiction since square Vandermonde matrix with different column generators is invertible, which we show below. Hence, the aggregated values {S;} must be different for different Similarly, the sums Σ Ej.gh" 20 Uj" j²= are distinct for different choices of vectors q(), i [2K L),
(1)
1 E [4].
two vectors 9 and q' result in the same {St then Ej.g, #0 9j 1 - - 0, for all E [] Let fii...., least one of 9smm and d.nm nonzero for E [u]. Note that a S 2KL Rewrite this equation
(u] (fj qj # 0} {j of 0}) be the of integers such that
1
96.
g
i
0.
(19)
22k-1
2KL
9b..
d
Since s 2KL, we take the first u equations in
19 and rewrite them
Bv 0,
where
i1
bu
B
2KL
2K Pu
square Vandermonde matrix and
dip %%
9b.
nonzero vector since q # q'. It is known that the determinant of square Vandermonde matrix B given by IIm <ma,m, m,aama, (fma - im,), which in our case nonzero since all the i,,..., , fy are different. Therefore, B is invertible and does not admit a non-zero solution, which contradicts the equation Bv 0.
K A DETERMINISTIC LOW-COMPLEXITY ALGORITHM FOR SCMA AT THE SERVER
In the SCMA scheme we described in Alg. the goal of the server is to reconstruct the vector given values S, Σj Uj ji-1 mod for E [2KL], To this end, we first use the Berlekamp- Massey algorithm to compute the polynomial g(x) = II 10 ji-j-z) Then, we factorize g(x) over the finite field FF, using the algorithm described in Kedlaya & Umans (011). The complexity ((KL) log p KLL log" p) referred to in Section 4.3 corresponds to the average complexity (finding deterministic algorithm that factorizes a polynomial over finite fields with (loy()og worst-case complexity is open problem). The complexity max{O LK?) O(KL)) log
KTT log" p}} referred to in Appendix for the SCMA scheme represents average complexity.
23

---

Published as a conference paper at ICLR 2023
We show next that the SCMA scheme has small worst-case complexity under deterministic decoding algorithm at the server as well. To this end, we replace the integer p in Alg. 2 with a large number such that p' is larger than the largest possible S; and there is no overflow when applying the modulo p' operation on S. It is known (Bertrand's ' postulate) that there exists a prime number between any integer
p' max K LB2dki, n , +
and 2n 2n-2 2, and hence there must be prime numher lower-bounded by max{ K LB2aKL n] + 1 and twice the lower bound mmmxx [ L B2dKL n) + 1). However, since searching for prime number of this size can be computationally intractable, we remove the requirement that p' is prime. Correspondingly, Fp is not necessarily finite field. Then, instead of sending ( (n y0 ()) - + 2; 2(1)) mod p. client I, 1 E [T], will send
5(0) = C j.gg #0 Lj - + (D) + mod p' to the server, i E [2KL]] where random keys 2.") are independently and uniformly distributed over {0....../' - 1) and hidden from the server. After obtaining St, E L). the server can continue performing operations over the field of reals since there is no overflow in computing S mod p'. We note that though p' is exponentially large, the computation of s and S,, E [4] and i [2KL] is still manageable, and achieved by computing and storing 5/00) and S; using L) floating point numbers, instead of computing and storing s(D) in single floating point number. Note that j' can be computed using (i) floating point numbers with complexity almost linear in (i.e., Oii log" i) for some constant c).
We now present a low complexity secure aggregation algorithm at the server. After reconstructing S. we have S, = - Ei 70 93 -²m The server switches to computations over the real field. First, it uses the Berlekamp- Paaseaamp-Massey algorithm to find the polynomial g(x) i * (1 - x) (the algorithm was originally proposed for decoding of BCH codes over finite fields, but it applies to arbitrary fields).
Let m be the degree of (zx). Then h(x) = x" (1/xx) = i j). The goal is to factorize Mx) over the field of reals, where the roots are known to be integers in [Bd] and the multiplicity of each root is one.
If the degree of h(x) is odd, then h(0) < 0 and h(B") > 0. Then we can use bisection search to find root of h(r), which requires Ollog Bd) polynomial evaluations of h(x)), and thus O(M K log Bd) multiplication and addition operations of integers of size at most log After finding one root j. we can divide h(x) by z-j
j and start the next root-finding iteration.
If the degree of fzx)) is even, then the degree of h ('(x) is odd, and the roots of ht' (1(x)) are different and confined [Bd.. We use bisection search to find a root j' of hz))). If h(j') O, then we use to find root of h(z) and start new iteration as described above when the degree of h(xx) odd. If h())) > 0, then h/(3' ([j'-11 1) > 0 and h' h'(0) < O. We use bisection search to find another root of 1 (xx in []' - 1]. Note that for every two roots H and já and h(12) > we can always find another root j/8 of 1 l((x) in 01-1,22 - 1]. We keep iterating the search for every two such roots jí 22 until we find a list of roots TI...., 12..1, of h (z) such that f(r:)) < for odd in [2R +1 1] and (rr)) > 0 for even i E R2R 1]. Then we can run bisection scarch on the sets r1 [r1, r2]. .... [228. 128+1), [12R+1, Bd, to find 2R + 2 roots of h(x). Note that during the iteration we need 2 + bisection search iterations to
bisection search on j'] {0. ......J' J'}
0f < 12) of (ar) satisfying h(1)
find the roots rı, .,,..., T28+1 P2,+11, for h((x) and 2R 2 bisection search iterations to find 2R + 2 roots for h(x).
The total computations complexity is hence at most O(M K log Bd) evaluations of polynomials with degree at most O(MK) and at most O(MK) polynomial divisions, which requires at most O((M 2 log Bd) multiplications and additions for integers of size at most log This results in an overall complexity of ((MK)) log (MM(( K) log B), for some constant < 2.
L DIFFERENCE BETWEEN THE ASSIGNMENT MATRICES C AND C.
One example that explains the difference between these two assignment matrices is as follows. Suppose the global data sets and centroid sets are the same for the centralized and FC settings, i.e.,
X())
X =
... x(()
C = C. = {c .c......c0 ck).
24

---

Published as a conference paper at ICLR 2023
Suppose that for 21, which is the first row of X, we have
d(a1, e1) < d(),,)), Vj E [K],j
Then, the first row of C equals o1- However, if 21 resides on the memory of client I and belongs to the local cluster c and the recorded local centroid oi satisfies
(
( (G): Vj E [K],j #2
then the first row of C. is cg2 even if d(I1 c1) < (2) Here C. is the row concatenation of the matrices c on client I. This example shows that the assignment matrices C' and C. are different, which also implies that Ø and de are different.
M EXPERIMENTAL SETUP AND ADDITIONAL RESULTS
1. DATASETS
In what follows, we describe the datasets used in our numerical experiments. Note that we prepro- cessed all datasets such that the absolute value of each element in the data matrix is smaller than 1. Each dataset has an intrinsic parameter K for the number of optimal clusters, and these are used in the centralized K K-means++ algorithm to compute the approximation of the optimal objective value. We use o5 in subsequent derivation to denote the objective value returned by the K K-means++ algorithm. Besides K, set additional parameter K' VK for each client data so that the number of true clusters at the client level is not larger than K". This non-i.i.d. data distribution across clients is discussed in Dennis al. (202T). For small datasets (e.g.. TCGA, TMI), we consider the number of clients L as 10, and set L 100 for all other datasets.
Celltype [n- 12009, d = 10, K = 4] (Han et al. 2018; Gardner al. 2014b) comprises single cell RNA sequences belonging to a mixture of four cell types: fibroblasts, microglial cells, endothelial cells and mesenchymal stem cells. The data, retrieved from the Mouse Cell Atlas, consists of 12009 data points and each sample has 10 feature dimensions, reduced from an original dimension of 23, 433 using Principal Component Analysis (PCA). The sizes of the four cluster are 6506, 2328, 2201, 974.
Postures [n- 74975, d = 15, K 5] (Gardner et al. 2014b a) comprises images obtained via a motion capture system and glove for 12 different users performing five hand postures - fist, pointing with one finger, pointing with two fingers, stop (hand flat), and grab (fingers curled). For establishing a rotation and translation invariant local coordinate system, rigid unlabeled pattern on the back of the glove was utilized. There are total of 74975 samples in the dataset and the data dimension is 15. The sizes of the given clusters are 19772, 17340, 15141, 12225, 10497.
Covtype [n 15120, d 52, K 7] (Blackard & Dean 1999) comprises digital spatial data for seven forest cover types obtained from the US Forest Service (USFS) and the US Geological Survey (USGS). There are 52 cartographic variables including slope, elevation, and aspect. The dataset has 15120 samples. The sizes of the seven clusters are 3742, 3105, 2873, 2307, 1482, 886, 725.
Gaussian [n 30000, d 10, K 10] comprises ten clusters, each generated from 10-variate Gaussian distribution centered at uniformly at random chosen locations in the unit hypercube. From each cluster, 3000 samples are taken, for total of 30000 samples. Each Gaussian cluster is spherical with variance 0.5.
FEMNIST [n 36725, 784, K = 62] Caldas et 2018 is a popular FL benchmark dataset comprising images of digits (0-9) and letters from the English alphabet (both upper and lower cases) from over 3500 users. It dataset is essentially built from the Extended MNIST repository (Cohen et al.) 2017) by partitioning it on the basis of the writer of the digit/character. We extract data corresponding 100 different clients, each of which contributed at least 350 data points. Each image has dimension 784. The size of the largest cluster is 1234, and that of the smallest cluster is 282.
TCGA [n = 1904, d = 57, = 4] methylation consists of methylation microarray data for 1904 samples from The Cancer Genome Atlas (TCGA) (Hutter & Zenklusen 2018) corresponding to four
Thhe clusters are obtained by running centralized K K-means++ clustering multiple times and selecting the one inducing the lowest objective value.
25

---

Published as a conference paper at ICLR 2023
different cancer types: Low Grade Glioma (LGG), Lung Adenocarcinoma (LUAD), Lung Squamous Cell Carcinoma (LUSC) and Stomach Adenocarcinoma (STAD). The observed features correspond to subset of values, representing the coverage of the methylated sites, at 57 locations the promoters of 11 different genes (ATM, BRCAI, CASP8, CDH1, IGF2, KRAS, MGMT, MLH1, PTEN, SFRP5 and TP53). This subset of genes was chosen for its relevance in carcinogenesis. The sizes of the four clusters are 735, 503, 390, 276.
TMI [n 1126, d 984, K 4] contains samples from human gut microbiomes. We retrieved 1126 human gut microbiome samples from the NIH Human Gut Microbiome (Peterson et al., 2009). Each data point of dimension 983, capturing the frequency (concentration) of identified bacterial species or genera in the sample. The dataset can be roughly divided into four classes based on gender and age. The sizes the four clusters are 934, 125, 46, 21.
M.2 BASELINE SETUPS.
We the publicly available implementation of K-FED and DC-KM our baseline methods. For DC-KM, we set the height of the computation tree to 2, and observe that the leaves represent the clients. Since K-FED does not originally support data removal, has high computational complexity, and its clustering performance not comparable with that of DC-KM (see Tab. [ we thus only compare the unlearning performance of MUFC with DC-KM. During training, the clustering parameter K is set to be the same in both clients and server for all methods, no matter how the data was distributed across the clients. Experiments on all datasets except FEMNIST were repeated 5 times obtain the mean and standard deviations, and experiments on FEMNIST were repeated 3 times due to the high complexity of training. Note that we used the same number of repeated experiments as in Ginart et al.) (2019).
M.3 ENABLING COMPLETE CLIENT TRAINING FOR MUFC
Note that both K-FED and DC-KM allow clients to perform full K-means++ clustering to improve the clustering performance at the server. Thus is reasonable to enable complete client training for MUFC as well to compare the clustering performance on the full datasets. Although in this case we need to retrain affected clients and the server for MUFC upon each removal request, leading to similar unlearning complexity as DC-KM, the clustering performance of MUFC is consistently better than that of the other two baseline approaches (see Tab. 2). This is due to the fact that we utilize information about the aggregated weights of client centroids.
Table 2: Clustering performance of different FC algorithms compared to centralized K- + clustering.
TMI
Celltype
Gaussian
TCGA
Postures
FEMNIST
Covtype
MUFC
1.05 1 0.01
1.03 1 0.00
1.02 1 0.00
1.02 1 0.01
1.02 1 0.00
1.12 1 0.00
1.02 1 0.00
K-FED
1.84
1.72 0.24
4 0.01
1.56
1.13 4 0.01
1.60
DC-KM
1.51
1.46 = 0.01
1.02 4 0.00
1.15 0.00
1.03 = 0.00
1.18
1.03 0.02
M.4 Loss RATIO AND UNLEARNING EFFICIENCY
In Fig. 4 we plot results pertaining to the change of loss ratio after each removal request and the accumulated removal time when the removal requests are adversarial. The conclusion is consistent with the results in Section 6
M.5 BATCH REMOVAL.
In Fig. 5 we plot the results pertaining to removing multiple points within removal request (batch removal). Since in this case the affected client is more likely to rerun the K-means++ initialization for each request, it is expected that the performance (i.e., accumulated removal time) of our algorithm would behave more similar to retraining when we remove more points within one removal request, compared to the case Fig. where we only remove one point within one removal request.
26

---

Published as a conference paper at ICLR 2023
Callppe EOrLId, Kard
I03A 11 2.6.6
Ponure 2,4-33
Caugae neviLs E K=l.K??
1.50
125
125
Riaden
LI0
1.N0
1173
1.29
hunbe of inrivil
Mumber atronoouu
Punbo oficrooss
(x)
(b)
Cantpp nanils 2
107
330
L0P
MURC evange spred-upt DC/eeeum (Ic everaee spemtopt
MUFC foxr deerage spend
M. FC (21 imerae spard
og
krawaa everage spandiug)
komeom So ivenge (panc-u))
Retualnng
Number cinervvs
320
Numbe: IEEICAsS
(4)
(h)
Figure 4: The shaded areas represent the standard deviation of results from different trails for all subplots. (a)-(d) The change of loss ratio (X; (X) after each round of unlearning procedure. (e)-(h) The accumulated removal time for adversarial removals.
10P
124
suni tic anrige spea sil 0C-Cmern Db evrage
MUli: occanegg rped si) OC 24 Ecoenge
MuFo evrage saedd ko.krmam evarge Screoug
VLEC awingg specc-i Sreen mvae
83
100
20
30
50
40
53
200
10
20
43
Figure 5: The shaded areas represent the standard deviation of results from different trails for all subplots. (a), (c) Remove 10 points within one batch removal request. (b), (d) Remove 30 points within one batch removal request.
27


Reviews:
[{"review_id": "fvu5Byfrvx", "reviewer": "Reviewer_BrQd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel approach for unlearning data under federated learning setting for the purpopse of clustering. The proposed method also has security gaurantees. Theoretical analysis in terms of clustering performance and complexity analysis has been done for the proposed method.", "summary_of_the_review": "The reviewer thinks the topic in this paper is very interesting and is of importance in practice. However, there are several concerns that is critical to the proposed method. Therefore, the reviewer believe additional work or clarification is needed before the work can be published.", "strength_and_weaknesses": "The paper discusses a new topic of federated unlearning for the purpose of clustering. Given the rich content of the paper, the reviewer believe additional work needs to be done to make the story easier to follow. The reviewer has several suggestions:\n\n1. There are several places in the paper that a term is described first and the definition is given several sections later in the paper, which brings difficulty for the reader to follow.\n2. The reviewer thinks it would be useful to first introduce the intuitions behind the algorithms and then present the algorithm. This is particularly the case for algorithm 2.\n3. In section 4.2, the reviewer feel a little bit lost since the outliers are introduced in the paper. The discussion of outlier removal is not very closely related to the existence of outliers. Given the space limit of the paper, it would be clearer to focus only on one topic and brings other issues in the appendix or the discussion section.\n\nMajor concerns:\n1. The reviewer has several questions in terms of algorithm 2 that needs further clarification.\n- The quantization of $C^{(l)}$ is performed dimension-wise, can the authors be more specific on how step 4 is performed? \n- There is a well known label switching issue under clustering, in step 5 to sum up $q^{(l)}$ at the server, will there be any issue if the label is switched? The reviewer believes switching label at the first place will lead to different $q^{(l)}$ at the first place and hence $q$, this could potentially be a severe issue for clustering.\n\n2. For removing adversarial points, will the cost be necessarily smaller than refitting the model? This is not discussed as the magnitude of $\\epsilon_2$ and $s_{\\text{min}}$ is not specified in the main paper.\n\nMinor issues:\n\n1. Could the author ellaborate more on the difference between $\\phi_f$ and $\\phi_{c}$? The value of these two terms are equal when $C=C_s$, are there any particular reason to define two terms?\n\n2. Can the authors ellaborate more on the role of the hyperparameters $\\alpha$ and $p$ in the proposed method?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "eMO5TNW_3E6", "reviewer": "Reviewer_j6JM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new federated unlearning method for a specific federated clustering workflow. A key to the federated unlearning method is secure compressed multiset aggregation (SCMA) to aggregate local contributing data and enhance data privacy. Theoretical analysis is shown to demonstrate the computation and communication effectiveness of the proposed method. Experimental results are also shown to justify the practical speedup of the proposed method.", "summary_of_the_review": "The paper proposes a good and efficient method for federated unlearning of federated clustering tasks. Both theoretical and empirical results are shown to justify its performance. The scope of the proposed method is limited by it only tackles federated clustering problems.", "strength_and_weaknesses": "Strength:\n- The paper is well-written.  \n- Solving the unlearning problem for federated tasks is of great importance.  \n- Both theoretical analysis and experimental results are shown to justify the effectiveness of the proposed method.  \n\nWeaknesses:\n- It seems the scope of the proposed method is a bit limited as it seems to only be designed for federated clustering. I wonder how hard it will be to generalize the proposed method to general federated unlearning.  \n- the scale of the experiment is a bit small. What will the performance look like on datasets with the ImageNet scale?  \n- I am almost sure that SCMA (or at least its variants) has been studied in communication-efficient distributed optimization, e.g., via gradient or model quantization and/or sparsification. This limits the novelty of the proposed method.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WDSivc4ahB", "reviewer": "Reviewer_ci9j", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes the first known unlearning mechanism for federated clustering with privacy criteria that support simple, provable, and efficient data removal at the client and server level, by combining special initialization procedures with quantization methods that allow for secure aggregation of estimated local cluster counts at the server unit.\n\nIn the empirical studies, results show it can achieve 84x across seven datasets compared to completely retraining K-means++ locally and globally for each removal request", "summary_of_the_review": "Overall I believe it is an interesting paper, with clear writing as well as high quality experiment. My major concern is the benchmark comparison. Authors claim it is the first unlearning algorithm for federate cluster, so it makes hard to understand how innovative compared with peer works. So I choose marginal above threshold with low confidence.", "strength_and_weaknesses": "My major concern is the benchmark comparison. Authors claim it is the first unlearning algorithm for federate cluster, so it makes hard to understand how innovative compared with peer works", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5JbyJ1dYzL_", "reviewer": "Reviewer_5qA2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on unlearning federated clustering problems with k-means++ initialization and secure compressed multiset aggregation. The idea of unlearning is to perform k-means++ initialization at each local client. By exploiting the nature of k-means++ approximation, the centroid set C may remain unchanged if removed points are not in C.", "summary_of_the_review": "In general, the studied problem is interesting and important. In addition, the methodology is principled with three major merits as discussed above. However, the work still has some unaddressed concerns to well justify its technical and empirical contributions.", "strength_and_weaknesses": "Strength:\n1.The paper proposes a unlearning mechanism for federated clustering with privacy criteria that enables  efficient data removal at the client and server level.\n\n2. The extensive theoretical analyses are derived to validate the performance guarantees of the proposed method.\n\n3. The algorithm is evaluated on a number of datasets to demonstrate the effectiveness of the proposed approach for machine unlearning.\n\nWeakness:\n1.\tAccording to algorithms 1 and 4, the unlearning process requires the help of removal set XR. This requirement is naturally fulfilled in the context of centralized unlearning but may not be available. In such case, the retraining in line 3 in algorithm 4 will always be required and significantly increase the complexity.\n2.\tThe unlearning strategy in this paper relies heavily on the k-means++ algorithm, which approximates the k-means problem proposed in 2007. The paper exploits the nature of k-means++ initialization with no technical improvement, making the novelty and contribution questionable.\n3.\tLine 2 in algorithm 1 implies that the centroid set C can remain the same if the removal point is not inside the centroid set C without further restrictions. This is very questionable when a certain number of biased data points are removed within a single request. In the unlearning experiment setting, the unlearning requests are carried out with one data point per client at each round of unlearning, which is insufficient to evaluate the performance of the proposed unlearning method. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster