A Communication Efficient Federated Kernel $k$-Means
Authors: Xiaochen Zhou
Xudong Wang
Venue:  (2021)
Keywords: federated learning
kernel $k$-means
communication efficient

Abstract: A federated kernel $k$-means algorithm is developed in this paper. This algorithm resolves two challenging issues: 1) how to distributedly solve the optimization problem of kernel $k$-means under federated settings; 2) how to maintain communication efficiency in the algorithm. To tackle the first challenge, a distributed stochastic proximal gradient descent (DSPGD) algorithm is developed to determine an approximated solution to the optimization problem of kernel $k$-means. To tackle the second challenge, a communication efficient mechanism (CEM) is designed to reduce the communication cost. Besides, the federated kernel $k$-means provides two levels of privacy preservation: 1) users’ local data are not exposed to the cloud server; 2) the cloud server cannot recover users’ local data from the local computational results via matrix operations. Theoretical analysis shows: 1) DSPGD with CEM converges with an $O(1/T)$ rate, where $T$ is the number of iterations; 2) the communication cost of DSPGD with CEM is unrelated to the number of data samples; 3) the clustering quality of the federated kernel $k$-means approaches that of the standard kernel $k$-means, with a $(1+\epsilon)$ approximate ratio. The experimental results show that the federated kernel $k$-means achieves the highest clustering quality with the communication cost reduced by more than $60\%$ in most cases.

Under review as a conference paper at ICLR 2021
A COMMUNICATION EFFICIENT FEDERATED KERNEL カ- MEANS
A Aonymmus authors Paper under double-bling review
A ABSTRACT
A federated kemel k-means algorithm is developed in this paper. This algorithm resolves two challenging issues: 1) how to distributedly solve the optimization problem of kemel k-means under federated settings; 2) how to maintain commu- nication efficiency in the algorithm. To tackle the first challenge, a distributed stochastic proximal gradient descent (DSPGD) algorithm developed to deter- mine an approximate solution to the optimization problem of kemel k- means. To tackle the second challenge, a communication efficient mechanism (CEM) is de- signed to reduce the communication cost. Besides, the federated kemel k-means provides two levels of privacy preservation: 1) users' local data are not exposed to the cloud server; 2) the cloud server cannot recover users' local data from the local computational results via matrix operations. Theoretical analysis shows: 1) DSPGD with CEM converges with an O(/TT) rate, where T is the number of iterations; 2) the communication cost of DSPGD with CEM is unrelated to the number of data samples; 3) the clustering quality of the federated kemel k-means approaches that of the standard kernel k-means, with a (1 + E) approximate ra- tio. The experimental results show that the federated kemel k-means achieves the highest clustering quality with the communication cost reduced by more than 60% in most cases.
INTRODUCTION
Conventionally, kernel k-means Dhillon et all, 2004) is conducted in a centralized manner where training data are stored in one place, such as a cloud server. However, as a rapidly growing num- ber of devices are connected the Internet, the volume of generated data increase exponentially (Chiang & Zhang, (016)). Uploading all these data to the cloud server can lead to large cost of communication bandwidth. For example, a smartphone manufacturer usually needs analyze us- age pattemss of its smartphones, purposing to optimize energy consumption performance of these smartphones. The usage patterns can be obtained by clustering users' energy consumption data via kernel Æ- memnss. However, if the number of users reaches the order of millions, it may not be cost- effective scheme to upload all the users' energy consumption data to the cloud server. Besides, uploading users' raw data to the cloud server can lead to data privacy issues. To resolve these issues, a promising approach is to develop a distributed kernel k-- t-means algorithm that can be executed under federated settings (McMahan et all 2017: Yang et all 2019) where raw data are maintained by users and the cloud has no access to the raw data. In this algorithm, a local training process is conducted at each user's device, based on the local data only. The local computational results, rather than the local data, are then uploaded to the cloud server to accomplish the kernel k-means clustering. During this procedure, users' local data are no longer exposed to the cloud server, which provides a basic level of privacy. Besides, it is usually more communication efficient to upload the local computational results than upload the local data to the cloud server.
However, it is nontrivial to design a federated leamiing algorithm for kernel k-means due to three challenging issues: 1) how to solve the optimization problem of kernel k- e-means in a distributed manner without sending users' data to a central place; 2) how to maintain communication efficiency in the algorithm; 3) how to protect users' data privacy in the algorithm. Considering the first issue under federated settings, the key problem is to obtain the top eigenpairs of the kemel matrix K (as required by kernel k-means) in a distributed manner. To solve this problem, a distributed stochastic proximal gradient descent (DSPGD) algorithm is developed as follows. Since K is not available

---

Under review as a conference paper at ICLR 2021
under federated settings, an estimate of K, denoted as E, is first constructed distributively at users' devices based on random features (Rahimi & Recht 2008 of local data samples. Since the estimate is distributed among different devices, is processed by the distributed Lanczos algorithm (DLA) (Penna & Stanczak, 2014)) to obtain an estimate of K (denoted as Z) at the cloud server. A Atterwarss an approximate version of the top eigenpairs of K can be obtained from Z through singular value decomposition (). To improve the accuracy of approximation, the former steps are conducted in an iterative way. More specifically, in the t-th iteration, an estimate & is constructed at users' devices, and then the estimate Z, at the cloud server is updated to Z₁-1 via stochastic proximal gradient descent (SPGD) (Zhang et all 2016). is proved that, after sufficient iterations, Ze can converge to a low rank matrix whose top eigenpairs are the same as those of K As result, top eigenpairs of K are finally obtained at the cloud server.
To resolve the second issue, DLA operations in DSPGD need to be enhanced to reduce commu- nication cost. W hen DLA is executed in DSPGD, the process of obtaining an updated Z, at the cloud server results in high communication cost between users' devices and the cloud server, be- cause the operation is conducted upon matrices (e.g., E,) with the number of rows/columns equal to the number of data samples. To prevent the communication cost from growing with the number of data samples, a communication efficient mechanism (CEM) is designed so that DLA is operated upon different type of matrices whose dimensions are reduced and independent of the number of data samples. More specifically, a new matrix W. is designed such that: 1) W. A W has the same eigenvectors as those of Z,+1, but its eigenvalues are smaller by a constant; 2) W, and Zr can be constructed distributively at users' devices based on local values of & Furthermore, DLA is applied to W W, (instead of W, W its operations are performed upon matrices with a highly re- duced dimension. Via DLA operations between users' devices and the cloud server, W. and Z, are updated iteratively, and then the top eigenpairs of W, W, are obtained at users' devices. Once Z, converges, users' devices transform the top eigenpairs of W W, to those of W, W.W. and further obtain the eigenpairs of Z, Instead of sending these eigenpairs to the cloud server, a distributed linear k- means algorithm (Balcan et all 2013) is incorporated into CEM so that the cloud server can perform clustering directly on the eigenpairs of the converged Z,. As shown in the process of CEM, the communication efficiency of DSPGD is significantly improved.
For the third issue, FK h-means based on DSPGD and CEM provides two levels of privacy preser- vation: 1) users' local data are not exposed to the cloud server; 2) the cloud server cannot recover users' local data from the local com computational results via matrix operations. To provide stronger pri- vacy, differential privacy mechanism (woork et al 2006) needs to be integrated with FK k- means, which is subject to future study.
The theoretical analysis shows that DSPGD with CEM converges to Zt at an O(L/T) rate, where T'ss is the iteration number. The communication cost of DSPGD with CEM is linear to the dimension of the right singular vector times the number of users, which can be much smaller than the number of data samples. The clustering quality of the federated kemel k- b-means approaches that of kernel k- means, with a (1++c) approximate ratio. The experimental results show that, compared with the state- of of-the-art art schemes, FK k- s-means achieves the highest clustering quality with the communication cost reduced by more than 60% in most cases.
2 RELATED WORK
2.1 DISTRIBUTED KERNEL k-MEANS
Many algorithms have been developed to conduct the kemne k-means clustering in a distributed way. The kernel approximation method is popular approach employed in these algorithms, such as the Nystrom method (Chitta et all 2011 2014 Wang et all, 2019) and the random feature method CChitta et al. 2012). A trimmed kemme k-means algorithm (Tsapanos et all 2015) decreases the computational cost and the space complexity by significantly reducing the non-zero entries in K via a kemel matrix trimming algorithm. In (Elgohary et all (201g) approximate nearest centroid (APNC) embedding is developed to embed the data samples so that the clustering assignment step
1 Moore specifically, the top eigenvectors of the low rank matrix are the same as those of K and its nonzero eigenvalues are smaller than those of K by constant.
2

---

Under review as a conference paper at ICLR 2021
of kemel ke-mans can be parallel executed. A communication efficient kemel principle component analysis (PCA) algorithm (Balcan et all, 2016) along with distributed liner k-means can approx- imately solve the optimization problem of kemel k- k-maans while maintaining the communication efficiency. However, these algorithms are designed with an assumption that they are executed at the cloud server where users' raw data are collected. Besides, many of these algorithms (Chitta et all 2011: 2012: 2014 Wang et al. 2019 are mee-hhot algorithms, i.e., they only determine an approx- imate kemel matrix K once. Thus, their clustering quality is limited by the accuracy of K. In contrast to these algorithms, FK k-means is the first distributed kernel k-means scheme designed under federated settings. In addition, FK k- k-maans is an iterative algorithm that can approach the top eigenpairs of K more accurately by employing more iterations.
2.2 FEDERATED LEARNING
Federated leamnngg (M al. 2017) is new machine learning framework aiming to protect users' data privacy and save the communication cost during the learning process. In the framework, a local model updated at each user's device, and these local models instead of users' local data are then aggregated at the cloud server to generate global model. The distributed optimization method in the framework is applicable to the models whose optimization problem can be decomposed into several independent subproblems, such as neural networks. and many algorithms (Konečný et all, 2016: Yang et al., 2018 Y Yurcchiin et all, 2019) are developed. However, it is non-trivial to decom- pose the optimization problem of kernel k- meaas under the federated learning framework. Some algorithms (Liu et al., 2017: Caldas et all 2018) improve federated multi- mulli--ask learning (Smith et all, 2017) with kemel. However, these algorithms either employ explicit feature mapping (Liu et all 2017) that can lead to impractical computational cost, or require to send the support vectors of users' local data (i.e., some local data samples) to the cloud server (Caldas et all, 2018), which can leak users' privacy information. Due to these limitations, these algontthms are not applicable to kemel k-means under the federated learning twor..... Recently, concept of clustered federated leam- ing (Ghosh et all, 2020, Sattler et alL, 2020: Mansour et al. 2020) is proposed, where the clients are clustered according to their gradient updates or their local models. However, their clustering prob- lems are different from the optimization problem of kernel k- m-maas, and thus are not feasible for the optimization problem of kernel k: t--ass in the federated setting.
2.3 STOCHASTIC KERNEL PCA
In (Zhang et 2016), the stochastic kemel PCA is accomplished a stochastic proximal gradient descent () algorithm. As a result, SPGD is centralized counterpart of the distributed proxi- mal gradi ent descent (D SPGD) algorithm in FK k- k-means. However, D SPGD is distinct from SPGD in three features. First, DSPGD is conducted under federated settings while SPGD is conducted in a centralized manner where users' raw data are collected at the cloud server. Second, the communi- cation cost is considered in the design of DSPGD, which results in CEM, while the communication cost is not considered in SPGD. Third, although both DSPGD and the SPGD aim at approaching the top eigenpairs of K, in the 1-th iteration, DSPGD only needs obtain an approximate solution Ze+1 to the problem of updating Ze instead of the exact solution Zi+1 to the same problem like SPGD, which leads to less communication cost under federated settings.
3 PRELIMINARY
Let [x,) i=] C X be set of N data samples. Given a feature mapping o(-) X + H. and the number clusters k; the problem of kernel k- means whose objective to find an optimal indicator matrix Y can be written as
min Ye
Tr(K) Tr(L à Y KYL s.t. Y1,- = 1,,
(1)
where K is the kemel matrix with each entry K,₃ ((x;) Tx(xx) Lå Diag
vxp 1) is
a diagonal matrix, N₂ is the number of samples in the i-th cluster, and 1, is a column vector with all the k items equal to 1. However, the problem in equation (1 is an NP-hard problem (Garey et all. 1982. Wang et al. 2019) To this end, an approximate solution Y is required. An efficient approach
3

---

Under review as a conference paper at ICLR 2021
to obtaining the approximate solution is as follows. K is decomposed as K UAU T via eigen- value decomposition (EVD), and then linear m-mmans is applied to the matrix H UA & to obtain Y (Ding et al., 2005 Chitta et all, 2012; Wang et all, 2019). To reduce the computational complex- ity, only the first 8 column vectors of H are selected as the input of linear A- k-means (Cohen et all, 2015).
4 FEDERATED KERNEL k-MEANS
In FK k- k-means, the approximate solution to the problem in equation 1I is also determined based on the top-s eigenpairs of the kemel matrix K. To obtain these eigenpairs under federated settings, a distributed stochastic proximal gradient descent (DSPGD) algorithm is developed in Section 4.1 A communication efficient mechanism is then designed to reduce the communication cost of DSPGD in Section
4.1 DISTRIBUTED STOCHASTIC PROXIMAL GRADIENT DESCENT
The key problem for designing FK k- m-mas is to obtain the the top-s eigenpairs of K in dis- tributed manner. To solve this problem, a distributed stochastic proximal gradient descent algonihhm is developed as follows. Under the federated settings, the main challenge on determining the top-s eigenpairs of K is that K is not available since users' local data cannot be exposed to the cloud server or other users. To this end, an estimate of K, denoted as is constructed distributively at users' devices based on the random features (Rahimi & Recht 2008 Kar & K Kamick, 2012) of their local data samples. More specifically, & = AAA and [E[]] = K, where D is the number of ran- A is the random feature matrix distributed over M users' devices (the details of the random feature method are included in Ap- pendix A. Since E is distributed over users' devices, it is then processed by the distributed Lanczos algorithm (D LA) ) (Penna & Stanczak 2014 to obtain an estimate of K, i.e., Z at the cloud server. A fterwards, an approximate version of the top eigenpairs of K can be obtained from Z through SVD. To improve the accuracy of approximation, one method is to increase the value of D. However, this method is only feasible when each user's 's device has enough memory space. To adapt DSPGD to de- vices with different memory space, DSPGD improves the accuracy of approximation via an iterative method. More specifically, in the t-th iteration, an estimate E, is constructed at users' devices, and then the estimate Z, at the cloud server is updated to Z++1 via stochastic proximal gradient descent (Zhang et all 2016):
dom features of each data samples, and A = [A
1 IZ Zell + (Z Ze, Z. - -E)) + M
Z++1 arg min ZeRux. 2
where ne is a learning rate. Ze+1 has an explicit expression Ze+1 = Enidn (dix - n) uf where (ū.,,: Ax,)) is the i-th eigenpair of matrix R, = (1 no Zz + E. Since & is distributed over users' devices, Ze+1 is determined via DLA at the cloud server. it proved that, after sufficient iterations, Z, can converge to a low rank matrix K = Ees.s (A: u) where (u, A,) is the i-th eigenpair of K. As a result, the top eigenpairs of K are finally obtained at the cloud server.
The t-th iteration of DSPGD is executed as follows. The main task is to approach the top eigenpairs of R. via DLA, The cloud server first initializes random vector e₁ E R. In the q-th iteration of DLA, the cloud server determines a vector g, R.C, (1 - m) Zc + T c D, where Z,c, is computed at the cloud server, and A, cq is computed in a distributed manner. The computation of A,A, c.y is accomplished by five steps: 1) the cloud server partitions the vector cy = [c,[1]] ..... c, [M]]]] into M parts and sends the m--h part [y[r to the user mn; 2) the user m computes local vector A.[m]] c, [mi] and uploads the vector to the cloud server; 3) the cloud server sums up these vectors to obtain the vector A, c, and then broadcasts this vector to all the users; 4) the m-th user computes new local vector A, [m] A cg and then uploads this vectors to the cloud server; 5) the cloud server finally concatenates these vectors from users to form A,A, c,p W When g is determined, the cloud server then applies the Lanczos algorithm to the collected vectors (g:...., ) to approximate the top eigenpairs of R, (the details about the Lanczos algorithm and
4

---

Under review as a conference paper at ICLR 2021
the complete procedure of DLA are provided in A ppeendixBB BB. 1...Aff After sufficient iterations of DLA, the top eigenpairs of R, are obtained at the cloud server, and then Z,41 is determined accordingly.
4.2 COMMUNICATION EFFICIENT MECHANISM
When DLA is executed in DSPGD, the process of obtaining an updated Z, at the cloud server results in high communication cost between the cloud server and users' devices, because its operation is upon matrices (e.g., 5,) with the number of rows/columns equal to the number of data samples. To prevent the communication cost from growing with the number of data samples, a communication efficient mechanism (CEM) is designed so that DLA is operated upon different type of matrices whose dimensions are independent from the number of data samples.
A new matrix W, that satisfies W. W equals R. is designed follows. Let Z. Ü,A.Ü, U, be the eigendecomposition of Z,, and B, equal Ü,A, Based on B, and the random feature matrix AG, W, constructed as W, = [v / D At, v B.B. A ssume that B, is divided like A,, i.e., and B, [m] is maintained at the m-th user's device. As a result, a submatrix W, can be constructed at the m-th device by W Wm[m] = |v TE D [ml, vT- 17: B, [ma]]]
B, = [B [1]T ..... B, [M
Furthermore, DLA is applied to W, W, instead of W, W.T. The number of rows/columns of W, W, equals rr + D where is the rank of Z, and D is the number of random features. Compared with the number of data samples NN, r. - D is usually much smaller than N, so the operation of DLA is upon matrices with highly reduced dimension. In the q-th iteration of DLA, the computation of B, W. Wie, is accomplished by three steps: 1) the cloud server first broadcasts vector Cgi each user m computes local vector W, [m]] W, [m]cc and uploads the vector to the cloud server, 3) the cloud server sums up these vectors to obtain g,y The cloud server then transforms g,, into C.+1 following the Lanzcos iteration. A fter sufficient iterations of DLA, the top-s; 8, eigenpairs (()... V.e), = 1, 1,....&& }t} of W W, converge at the cloud server: The cloud server then broadcasts the obtained top-s, eigenpairs to all the users' devices. Since the user m keeps We [m]] it then determines s, vectors U; [m]]
W [e[m]Vi.s = I,..., St, where ū.,:[m] is one part of the
ū, [M] Based on the vectors { i = 1, (....... $t} and the eigenvalues (di,a, i = I,... st). the user m also determines a submatrix B [m]] of B via [m+][m]] Iv A T/e Aūr. / / iteration DSPGD with CEM.
eigenvector u,,,, i.e., ū, = [ü,
which enables the + 1)-th
As DSPGD with CEM converges after T' iterations, a matrix H is constructed at the th user's device by mm] / / +1 "y )ūū (uu.r-ii [m],.... / /A,r + (1 7/x [m]]- A distributed linear k- means algorithm (Balcan et all 2013) is then applied to the rows of = [H[]T .... [ to obtain the clustering result. DSPGD with CEM and the distributed linear k-means algorithm constitute FK k-means. The pseudo code of FK k-means shown Algo-
rithm 1
THEORETICAL A NA LY SIS
The communication cost of CEM analyzed in Section 52 which shows CEM is important for FK k-meaas to maintain the communication efficiency. It is then proved that the clustering quality of FK k-means can approach that of the standard kemel k-maa in Section 5.3 Besides, the privacy preservation provided by FK k-means is analyzed in Section |54
The convergence of DSPGD with CEM is analyzed in Section 5.1
5.1 CONVERGENCE NALY SIS FOR DSPDG
The convergence rate of DSPGD with CEM is derived in Theorem |I
Theorem 1. Define 7 maxte(r) |Ze||- and C2 maxte(r] [|Z, 1. Assume ||E, K|| S G, and [Z. Z'|lr < H, 1L 2. By setting mi 2/t, the following upper bound of
5

---

Under review as a conference paper at ICLR 2021
Algorithm Federated Kemel k- M-Mas Algorithm
1: Input:
The threshold parameter the number of eigenvectors to be approached, the number of random features D, the maximal number of iterations T, local datasets Lm, 1, M, the initial local matrix B₁ [m] O, m I...,
2: Output: the clustering assigmment for each data sample
3: Server executes:
4: for 1, ................................ do
5: Initialize 7/. = 1/t, q =
6: for each client m, m 1, 2, ........ Mf in parallel do
7:
Compute A [m] by applying random feature method to L.n
8:
Construct W [m] = V A.A.mm) [m]. . vI :,BB((m)
9:
end for
10:
Call DLA to determine the eigenpairs {(As., Vi.e), 1,... of w. W.W. W
11:
for each client m, m 1, 2.............. M in parallel do
12:
Compute ب, [m]] = Vx., Wi[m] for = L,
Compute [m]] ly A m:Aui, (mm), ..., Vinne Medūs.
13:
14:
end for
15: end for
16: for each client m., m 1,2,... ..., MM in parallel do
17: Construct H[m] = Iv Ar. + (1 "r A Vder (1 Aus
18: end for
19: pplly distributed linear k-means algorithm over the rows of H [H[]] H H[M]T]
20: Return clustering assignment for each data sample
1z+1 1 holds with a probability at least 1 -
((22 + 20 2 S
4 + T
2CH 3 + + - 0(/7),
1 z
1|
(2)
where
log
[2 T7
The result Theorem iidicaate that DSPGD with CEM converges to Z* at an O(1/T) rate. The proof of Theorem is provided in A ppendix C
5.2 COMMUNICATION CoST ANALY SIS FOR CEM
Define the communication cost as the number of Seating-point numbers uploaded from users' de- vices to the cloud server. In Theorem 2 the communication cost of DSPGD with CEM and the communication cost of DSPGD without CEM are both analyzed.
Theorem 2. For DSP D with CEM, in the t-th iteration, its communication cost is linear rt + D where r, is the rank of Z, and D is the number of random fea tures. Define the communication ratio as the ratio of the communication cost of DSPGD without CEM to that of DSPGD with CEM. In the t-th iteration, the communication ratio equals Mir++D)Q M is the number of users; Qo and QI are the number of Lanczos iterations for DSGGD without CEM and DSPGD with CEM, respectively.
M) where is the number data samples;
By Theorem 2 the communication cost of DSPGD with CEM is unrelated to the number of data samples N, and the communication cost reduced by CEM can be revealed by the ratio. The values of Qn and Q: are affected by the selection of initial vector cı However, empirically the values of Qo and Q1 are at the same order no matter which initial vectors chosen. The dominant factor of the ratio is still NDMD
M(r++Dj Since Z, is used to approach the top-s eigenpairs of K, empirically its rank has an upper bound. In our experiments, the value of re is at the same order of i.c. the number of eigenvector ectors K be determined by DSPGD. Usually, the number of data samples at user's s device is much larger than so that it is easy to satisfied that N > Mr,, and CEM can definitely reduce the communication cost for DSPGD these cases. The proof Theorem [2 and the empirical results for r, are given in A ppendix [

---

Under review as a conference paper at ICLR 2021
5.3 APPROXIMATE RATIO A NNLL SIS FOR FEDERATED KERNEL A- M-MEANS
Before the analysis, approximmaee algorithm is first defined as follows.
Definition 1. A linear k- meass algorithm is applied to a matrix H with n row, where an indicator matrix Y is obtained. This algorithm is called a y-approximate algorithm if, for any matrix H, H) S miny f(Y;H) where f is the objective function of linear A- means.
has been proved that the standard kemel k--mans algorithm (Dhillon et all 2004) is ?-- approximate algorithm (Wang et all, (2019). The approximate ratio is then derived in Theorem B FKr k-meas.
Theorem 3. The objective function of kernel k- k-means in is denoted as fx. Hy is the output of DSPGD with CEM after T iterations, and a n-approximate algorithm is applied to the first s columns of Hy to obtain Yr. Assume the assumptions in Theorem [ For Yr, the following inequality holds with a probability at least 1 8(T), ie., fx (Yr) S 7(1 + + () miny fY),,, where E Olv ))
Note that as T increases, ((") decreases. If T then the clustering quality (in terms of the loss fK () of FK I-means approaches that of the standard kemel k- t-manns with (1 + approximae ratio. The proof of Theorem is given in A pppendix [E]
5.4 PRIVACY A SIS FOR FEDERATED KERNEL k- &-MEANS
FK k- meamess can provide two levels of privacy preservation: 1) one user's local data are not ex exposed to the cloud server and other users; 2) the cloud server cannot. recover users' local data from the collected local computational results via matrix operation. The first level can be easily verified from the procedure of FK k- means. The second level is proved by Theorem
Theorem 4, Based on the collected local computational results, the cloud server can at most recover the matrices { [m²] W [m], m = I.... M) } via matrix operations. Moreover, recovering the random feature matrix Ar from such matrices is an ill-posed problem with infinite solutions.
By Theorem 4 the cloud server cannot recover the random feature matrices from the local com- putational results. Without such random feature matrices, is infeasible for the cloud server to recover users' local data via matrix operations. More explanation and the proof of Theorem are provided in A ppendix [1] Moreover, FK k-means can incorporate the differential privacy mechanism (Dwork et all 2006: Suu et al. 2016) or random perturbation (Lin, 2016) to provide higher level of privacy preservation, which is subject to future work.
6 EXPERIMENTS
6.1 EXPERIMENTAL SETTING
Four types of existing schemes are considered in the experiments: centralized kemel k-means (Zha et all 2001) (denoted CK k-means), scalable kemee k- means (Wang et al 2019 (denoted as SK k- m-meass) distributed kemel k- k-means with random feature (Chitta et al., 2012) (denoted as RFK k-means), and communication efficient distributed kemel PCA (Balcan et al. 2010 @ (denoted as CE PCA). CK k-means and SK k-means are executed at the cloud server (denoted as cloud- based algorithms), and the rest methods are executed in a distributed manner where users' raw data cannot be uploaded to the cloud server (denoted as client- bastdaaedd algorithms). Besides, Gaussian ker- nel used in each algorithm. Four datasets are selected for performance evaluation: Three public datasets (Mushrooms, MNIST, and Covtype) from the LIBSVM M dataset repository and one dataset (Smartphone) provided by a company. In addition, 20, 000 data samples are randomly selected from the dataset MNIST to construct dataset MNIST-small that is used to validate the convergence of DSPGD. The statistical information of these datasets is given in Table [ The description of the Smartphone dataset and the existing methods are included in ppendix G
The hyperparameters FK k-means are determined as follows. The kemel parameter yy is com-
puted based on the average interpoint distance in the given dataset (Wang et al. (019): : Y

---

Under review as a conference paper at ICLR 2021
Table 1: Datasets statistics and hyperparameter settings for FK k-means
Dalasot
#samples (N)
#eatures (d)
*tlustors (k)
#randm featuros (D)
*kigenvecoors (+)
Mushrooms
8. 124
112
2
15
2
MNIST-
20, 000
780
10
200
10
MNIST
60, 000
780
10
200
12
Covtype
581, 012
7
Smartphone
177. 029
12
4
20
6
Norma ized Recever Error
4
x10
w/ CEM CEM 0/4/t
Standerd Derivation of
Normalized malieedd Reccover Error
x10
CEM W/o CEM
x100
w/ CEM w/l CEM
Standerd Derivation of Wermalized Recover
x10-1
w/ CEM CEM
Normaltzos Recover
0.03/t
20
40
50
10
30
40
50
20
40
50
10
40
lteraion
(a) Mushrooms
Fleration
lteration
(b) MNIST-Small
lleration
Figure 1: The convergence curves of the two versions of DSPGD and standard deviation curves of the normalized recover error on the Mushrooms dataset and the MNIST-small dataset.
2 2EM, EN xx xx-xxll I The threshold parameter of DSPGD is set to the (A: + 2)-th eigenvalue obtained in the first iteration of DSPGD. The configuration of the number of random features D and the parameter in the top-s s eigenvectors for each dataset is provided in Table hy perparamette configuration of the existing methods and a discussion on the configuration of are provided in Ap- pendix [ In the experiments, M = 5 worker processes and one coordinator process are generated to simulate users' devices and the cloud server, respectively. The worker processes communicate with the coordinator process via the message passing interface (MPI) in a synchronized manner. All the experiments are executed in a server with one i7-6850k CPU and 32 GB RAM.
6.2 EXPERIMENTAL RESULTS
The experimental results are presented from three aspects. First, the convergence results of DSPGD is shown in Figure D to verify its convergence rate. Second, the average communication cost per iteration of the two versions of D SPGD is provided in Figure 2 to show that CEM highly reduces the communication cost of DSPGD. Third, in Figure 3 FK k-means is compared with the cloud- based kemel k- means schemes in terms clustering quality to show FK k-means can achieve the comparable clustering results that of the cloud- based schemes; FK k-means is also compared with the existing distributed kernel k- m-mass schemes under the federated settings to show the higher communication efficiency of FK k- t-means.
The convergence of DSPGD is validated over two datasets, Mushrooms and MNIST-small, whose low rank matrices K = Ei= Au can be computed by performing SV D on their kernel matrices
K. A nomalizzd recover error KK | (Zhang et all, (2016) is recorded for each iteration t of DSPGD, where K, = Σg (7, + (1 ))))) A) T . is the estimation of K at iteration In the left subfigure of Figure aaa and that of Figure I the convergence curves of DSPGD are lower than the curve of 0.4/t and the curve of 0.03/ 4, respectively, which verifies DSPGD converges an O(1/l) rate. In Figure (aa and [[b] the curves of two versions of DSPGD nearly overlap, indicating that CEM has little impact on the convergence of DSPGD.
N
The average communication cost per iteration of DSPGD with CEM and that of DSPGD without CEM are compared in Figure 2 to evaluate the effectiveness of CEM. The log-scale is used for the y-axis of each subfigure, and the unit of the y-axis is the number of the floating- point numbers. As shown in the four subfigures, CEM can reduce communication cost of DSPGD by more than 98%, which indicates that CEM is important for FK k-mans to maintain communication efficiency.
In order to evaluate the clustering quality and the communication cost of FK k- k-means, curves of average nomalized mutual information (NMI) (Strehl & Ghosh 2002) versus average communi-
8

---

Under review as a conference paper at ICLR 2021
Average Communication tost
Averagge Communication Cost
Averaga Communtration Cost
20F
10"
104
Average Cammunicatin
204
10f
20*
302
-05
200
we CEM
w/ CEM
w/o CEM
W/ CEM
wee CEM
CEM w/
w/o CEM
CEM
Mushrooms
(b) MNIST
(c) Covtype
(d) Smartphone
Figure 2: The average communication cost per iteration of the two versions of DSPGD.
0.60
0.50
0.50
0.48
0.14
0.80
OK moatss
moans RFK kimaass
SK moons
RIK minins
0.20
TX E-mmans
CE PCA
0.38
Fo Io-maa
CE PCA
0.10
CE PCA
FK Sommaas
0.60
0.10
0.5
10
0.25
6:50
0,35
1.00
3:25
0.09
000
Communicatin Cost
Communication Costx10
Communication Costxio
Communication Costx1ot
(a) Mushrooms
(b) MNIST
(c) Covtype
(d) Smartphone
Figure 3: The NMI score versus the average communication cost of FK A- k-means and the existing methods on the four datasets.
cation cost are plotted in Figure 3 for FK k-means and the existing schemes. The enror bars in Figure [J are the 95% confidence interval of the average NMI scores. For the three public datasets, FK k-means can achieve comparable average NMI scores to that of the cloud- based algorithms (CK k-means for Mushroom dataset and SK k-means for MNIST dataset and covtype dataset). For cloud-based algorithm, its communication cost equals to the volume of dataset, which is too large to be shown. Thus, in Figure 3(a 3 and [ the dash line only represents the average NMI scores rather than the relationship of average NMI scores versus the corresponding communication cost. In Figure 3(a) and 3(b) given fixed communication cost, FK k-means can achieve the highest average NMI scores among the three client-based algorithms. Besides, in 3(b] FK h-means nearly achieves the upper bound the average NMI score with a low communication cost. To reach such NMI score, FK k- means reduces the communication cost by more than 60% compared with RFK k-means. In Figure with CE PCA, FK k-means reduces the communication cost by more than 60% when the highest average NMI score is considered. For the Smartphone dataset, since it has no labels, the cluster qual- ity of given clustering algorithm is evaluated by measuring the similarity between the clustering results of the algorithm and that of SK k-means. To this end, the clustering results of SK k-means are used as the labels to compute NMI scores. shown in Figure [3d] that FK k-means has much higher upper bound for the average NMI score (close to 0.9) than that of RFK k- t-mans and CE PCA.
3( FK k-means has a similar performance to that of RFK k-means. Compared
CONCLUSION
In this paper, FK k-means was developed. In the algorithm, distributed stochastic proximal gra- dient descent approach was first designed to determine the eigenpairs of the kemel matrix in a distributed manner. A communication efficient mechanism was then designed to reduce the com- munication cost. In theoretical analysis, DSPGD with CEM was proved to converge at an O(1/T) rate. The communication cost of DSPGD with CEM unrelated to the number data samples. The clustering loss of FK k-means can approach that of the centralized kernel k- t-messs. It was also analyzed that FK k--maas provided two levels of privacy preservation. The effectiveness of the FK m-means was validated by experiments on several real-word world datasets. FK k-means can still be improved in terms the asynchronous execution, the robustness to dropout users, and stronger privacy, which can be interesting topics in our future work.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Maria Florina Balcan, Yingyu Liang, Le Song, David Woodruff, and Bo Xie. Communication effi- cient distributedd kemel principal component analysis. In Proceedings of the 22nd ACM SIG International Conference on Knowledge Discovery and Data Mining, pp. 725- 734, 2016.
Maria-Florina F Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k- k-median clustering on general topologies. In Advances in Neural Information Processing Systems 26, pp. 2003, 2013.
Sebastian Caldas, Virginia Smith, and meet Talwalkar. Federated kemelized multi- tasti-takk/a learning. In SysML Conference 2018, 2018.
Mung Chiang and Tao Zhang. Fog and iot: An overview of research opportunities. IEEE Internet of Things J ournall, 3(6):854-866 2016.
Radha Chitta, Rong Jin, Timothy C Havens, and Anil K. Jain. A pproximate kernel k-means: So- lution to large scale kernel clustering. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 995-903, 2011.
Radha Chitta, Rong Jin, and Anil K Jain, Efficient kemnel clustering using random fourier features. In 2012 IEEE 12th International Conference on Data Mining, pp. 161-170, 2012.
Radha Chitta, Rong Jin, Timothy C Havens, and A nil K Jain. Scalable kemel clustering: A pproxi- mate kemel k-means. arXiv preprint arXiv: 440.3889,, 2014.
Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimen- sionality reduction for k-means clustering and low rank approximation. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pp. 163- 2015.
James W Demmel. Applied numerical linear algebra. SIAM, 1997.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernl k-means: spectral clustering and nor- malized cuts. In Proceedings of the 10th ACM SIG KDD International Conference on Knowledge Discovery and Data Mining, pp. 551-556, 2004.
Chris Ding, iiaofeng He, and Horst D Simon. On the equivalence nonnegative matrix factoriza- tion and spectral clustering. In Proceedings of the 2005 SIAM International Conference on D ata Mining, pp. 606-62 610, 2005.
Cynthia Dwork, Frank McShery, Kobbi Nissim, and A Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265- 284, 2006.
Ahmed Elgohary, A hmed K Farahat, Mohamed S Kamel, and Fakhri K Karray. Embed and conquer: Scalable embeddings for kemel k-means on mapreduce. In Proceedings of the 2014 SIAM Inter- national Conference Data Mining, pp. 425-4444433 433, 2014.
MR Garey, David Johnson, and Hans Witsenhausen. The complexity of the generalized lloyd- -ax problem (corresp.). IEEE Transactions on Information Theory, 28(2):255-22 256, 1982.
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated leaming. arXiv preprint arXiv: 20lv:20060000 04088, 2020.
Purushottam K and Harish Karnick. Random feature maps for dot product kemels.. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, pp. 583-591, 2012.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, A nanda Theertha Suresh, and Dave Bacon. Federated leaming: Strategies for improving communication efficiency. arXiv preprint arXiv: 1610.05492 2016.
Comelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differ- ential and integral operators. United States Governm. Press Office Los Angeles, CA, 1950.
Keng-Pes Pei Lin.
kemel k- k-means clustering outsourcing with random transforma- tion. Knowledge and Information Systems, 49(3):885-90) 908, 2016.
10

---

Under review as a conference paper at ICLR 2021
Sulin Liu, Sinno Jialin Pan, and Qirong Ho. Distributed multi-task relationship learning. In Pro- ceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and D ata Mining, pp. 937-946, 2017.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning, arXiv preprint wiXiv:2002.1066 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise A y A Arcas. Communication-eficoi learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1273-1282, 2017.
Federico Penna and Stawomir Stańczak. Decentralized eigenvalue algorithms for distributed signal detection in wireless networks. IEEE Transactions Signal Processing, 63(2):427-440, 2014.
Ali Rahimi and Benjamin Recht. Random features for laaal---cllleeeeeeoo kemel machines. In Advances in Neural Information P Processing Systems 20, pp. 1177-1184 2008.
Felix Sattler, Klaus- Roburt Müller, and Wojciech Samek. Clustered federated learning: Model- agmostic distributed multitask optimization under privacy constraints. IEEE Transactions on Neu- ral Networks and Learning Systems, 2020.
Virginia Smith, Cha Chiang, Maziar Sanjabi, and Ameet S Talwalkar: Federated multi-task leaming. Advances in Neural Information Processing Systems 30, pp. 1424-4434, 2017.
Alexander Strehl and Joydeep Ghosh. Cluster ensembles knowledge reuse framework for com- bining multiple partitions. J Journal of machine learning research, X(Dec):583-617 2002.
Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, and Hongxia Jin. Differentially private keaass clustering. In P Proceedings of the 6th ACM Conference on Data and Application Security and Privacy, pp. 26-37, 37, 2016.
Nikolaos Tsapanos, A nastasios Tefas, Nikolaos Nikolaidis, and Ioannis Pitas. A distributed frame- work for trimmed kernel k-means clustering. Pattern recognition, 28(8):2685-2690 2015.
Shusen Wang, Alex Gittens, and Michael W Mahoney. Scalable kemel k-means clustering with Nyström approximation: relative-enoo bounds. The Journal of Machine Learning Research, 20 (1):431-479, 2019.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology, 10(2):1-19, 2019.
Timothy Yang, Galen A Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ra- mage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXiv: 1812.02902 2018.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated leaming of neural networks. In Proceed- ings of the 36th International Conference on Machine Learning, pp. 7252-7261, 2019.
Hongyuan Zha, Xiaofeng He, Chris Ding, Ming Gu, and Horst D Simon. Spectral relaxation for k- m-mans clustering. In Advances Neural Info imforon Processing Systems 14, pp. 1057-1064, 2001.
Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Stochastic optimization for kemel PCA. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, pp. 2316- 2322, 2016.
11

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Lanczos Algorithm
1: Input: An symmetric matrix R, an initial vector cı
2: Output: An approximation Po to the eigenvectors of R, and an approximation o (d1,..., σql to the eigenvalues of R
3: Initialize 5gg and Co = 0
4: for 1. Q do
5:
RC
6:
0x cg
7:
g = g Cq B 1
8:
3 |g 12
9:
if 3 then
10:
break
11:
end
12:
Cy+11 = g/
13:
Construct a symmetric tridiagonal matrix To
14:
Perform EVD on To to obtain its eigenvectors PQ and its eigenvalues [o TQ
15:
Compute CoPQ
16:
end for
A
DETAILS OF RANDOM FEATURE METHOD
For kernel matrix a random feature method (Rahimi & Recht, 2008 Kar & Karnick, 2012) can generate an unbiased estimate of K, denoted as &, with the following expression:
E - AAT,
where the i-th row of A is the random feature vectors a(x,) for the data sample x,, The matrix E satisfies [ K.
We then use the example of shift- infft-invariant kernels to show how a random feature vector is con-
structed. For popular shift- cefft-invariant kemels r:(x,, Xy) with Fourier representation
<(x,, x,) pw))pp(ppppp) ((w)exp(jw T (x; xy))
where (w) ) is probability density function, they can be estimated by the random Fourier features (Rahimi & Recht 2008) as follows. By randomly drawing D independent samples {w....., WD} random feature vector a(x,) for data sample x, can be written axx,) IV2 coccow w x; + b1)............ v2 cos(w (w; bb)] where (bI..... ......,bu bD} are independent random vari- ables drawn from [0, 2x) uniformly. As result, an unbiased estimation of K can be written as AAA where A [a(x:),... a(x,))]
from pww),
B DETAILS ABOUT DISTRIBUTED LANCZOS ALGORITHM
To find the eigenpairs of a symmetric matrix R, the Lanczos algorithm (LA) Lanczos 1950) first build a Krylov subspace K.g (R. c1) = span/c1. Rc,, R C1] where c₁ is an initial vector, and then it employs the Rayliegh-RBe Ritz procedure to construct the best approximate eigenpairs for R in the Krylov subspace. In the first step, LA constructs an orthogonal basis of the Krylov subspace following the procedure of line 5 to line 12 in Algorithm 2 Meanwhile, a symmetric tridiagonal matrix TQ RCC can be explicitly constructed with aq and B2 via
Tan
81
B1
To
SQ-1
BQ-1
oiQ
Based on Tę, the Rayliegh- Ritz procedure can be utilized to approximate the eigenpairs of R. Let To PP PJ I be the eigendecomposition of TQ. It has been proved that the columns of CoP
12

---

Under review as a conference paper at ICLR 2021
and the diagonal entries of Eg are the optimal approximation to the eigenvectors and eigenvalues of R. respectively (D (Demmll 1997). Thus, in the Rayliegh- Ritz procedure, PQ and Σi are determined by performing EVD on T and then CoPo o are computed as the approximation to the eigenvectors of R. As the number of iteration Q increases, the columns of CoPo and the diagonal entries of Eq can converge to the eigenvectors and ei of R, respectively (Demmell (1977).
As for the distributed Lanczos algorithm (DLA), only the step of line 5 in Algorithm (2is conducted in distributed manner, and other steps are conducted at the cloud server. In our problem, if
R = (1 - mp L + n.C, = (1 To mz + The
A,A,
D
where Z, and c, are known at the cloud server, and A, [A,[1]] ................................ A. are distributed
over M users' devices, then (1 7/ C, is computed at the cloud server and 17, A,A, / is computed in a distributed manner as follows. The vector c [c, ..... CylM
is first partitioned into M parts at the cloud server, and the m-th part ,,) ] is sent to the m- user's device. A local vector Ar [m]] Cog Cg[mm] is then computed at the m-th user's device. These local vectors from M users' devices are summed up at the cloud to obtain vector A, Cg. A, A, c. is then broadcast to M users' devices, and vector A, [m]] A, Cy is computed at the m-th user's device. These M vectors are sent back the cloud server where they are concatenated to form A,A, Cq. If
M
R- W. W.
Σ W.[m] m=
[.[m]] [m]]]
where [m[m] T W, [m]] can be computed at the m-th user's device, then each user' devices first determines W.[m] W, [m]cc, locally, and these M vectors are then uploaded to the cloud server where they are summed up to form W. W.c.-
In the t-th iteration of DSPGD, DLA is used to compute the eigenvalues larger than n) of the R,- Thus, in practice, the convergence criterion of DLA is that all the approximated eigenvalues larger than A converge, rather than that the number of iteration reaches its maximal value Q.
One issue of LA and DLA in practice is that they can only be conducted in floating point ari thmeticc, which can destroy the orthogonality of the columns in C,,, and further affect the converge erggenence of DSPGD. To this end, a full reorthogonalization method (Demmel, 1997) is utilized to guarantee that C, is an orthogonal matrix with a high probability. The key idea of this method to generate new vector cg from a subspace that is orthogonal to all the previous vectors (C1, ..., Cg which can be accomplished by replacing line 7 in A Algorithm 2 with
Σ g c.C. i=1
g=g
The operation in 3 can be called multiple times in one iteration of LA to increase the probability that C,2 is an orthogonal matrix. In the implementation of federated kernel k-means, such operation is called twice in each iteration of DLA. Note that the full reorthogonalization only requires more flops at the cloud server, which does not affect the algorithm complexity at users' devices.
C PROOF OF THEOREM 1
This proof partially follows the proof of Theorem in Zhang al. (011). The difference is that the t-th iteration of z obtained by DSPGD, i.e., Z. may not equal Z = D [[l mh Ze + m. The gap between Z, and Z; is caused by that the distributed La Lanczos algonthm (DLA) only approximates the eigenpairs of target matrix. Thus, in this proof, it is assumed that
12, Z 11 S 6, 11.
(4)
when DLA reaches its convergence criterion, where << 1.
Before the proof, we first define
F(Z) = E|| Z - El
2
(Z) IZ 1.
13

---

Under review as a conference paper at ICLR 2021
For p-strongly convex function (Z)), (f 2 (Z)), then
すー 7 -2212
/ 2
I (Z - (Z2))
(5)
In the 1-th iteration of DSPGD, the goal is to determine the optimal solution Z;+1 to the following optimization problem
min Ze ZERuxa Xm
1 2- + + Th (Z Z.. V..(Z.)) + +
(6)
By DLA, an approximate solution Zi+1 that satisfies can be obtained. The following lemma is key step in this proof.
Lemma 1. Before the convergence of DSGGD, the following inequality holds, i.e.
Ze+1 - 2 + 7/2 (Z++1 Ze VZt( + 1Z
2
Iz' Z, 7/ + n (Z' Z. V (Z.)) + 1/1111
2
Proof. The objective function in 6 can be rewritten
Z Z,
7 (Z- Z₁ fZ. + 1/
2
1
Z 1. + (7 2 fz, + T 2
- 2
f.
- z [[1 1/: 1z + = my |
1
Since
of 2
[Z.)) is constant, we can only consider
[Z)) ] Z [(1 7 + n) 1//1
1
in the following part of the proof. Now first assume that ((Z") S. ((Z,+1), then have
1(Z++1) ((Z ((Z) ((Z(+1)
# 2
7i+1 11
(8)
Moreover, 1(Z++1) ((Z1+1) can be expanded as
1(4+1) 1(Z4+))
2 |zt+ - Rel ReI12 + 17tr Z1+1/|+ 1
511zi+1 - Rell% + n// Zi 1|+
(1 (lZ,41 RB/l |F | R4 Re(l=)(([Ze+] |1 + |Z R (F)
(9)
- |(11)
Zt+1 Zi+1llr (1| Z + 2 - R((r) + . Z
is well known that given a matrix M the following inequality holds for its nuclear nomm and its Frobenius norm, i.e., | 2 < rank(M))|M f. By this inequality, have
|| Zi+ill+ $ Z Ziille I Vre,
(10)
where r is the rank of (Z,+1 Z;+1) Substitute 4 and 110 into 9
we have
((Z++1) 1(Zi,,) < 2
e + el Z
R l| + mAVTEe
Since |Zi+1 - R1 is constant, this upper bound of ( ((Z++)) - I(Zi+1) can become arbitrarily
small if e is arbitrarily small. Hence, according to 8 |Z,+1 I can also arbitrarily small. However, this contradicts that || Z" 13 cannot become arbitrarily small before the conver- gence of DSPGD. Therefore, before the convergence of DSPGD, I(Z") > I(Z,.)) ) is satisfied. n
14

---

Under review as a conference paper at ICLR 2021
The rest part then follows the proof of Theorem in Zhang et all (2016). Based on Lemma and the property of strongly convex function in (5), the update nule of SPDG implies
Z Z.1l² + The (Ze+1 Z. (..)( + 7> | 1Z
(11)
1 11 Zt+1
2 Iz' Z
1/. + n ( Zt (z,)) + n + ||-
2
Since F(Z) is 1-strongly convex, it can be shown that
1
2 IZz 1
<Z, >l|Zz|11. F(Z") 1/|Z1||
< <Z, - Z', vF(Z,))
2 12, Z 1/7 + 2/| |. Z/
=(Z , vZ((Z.))
-11 277
[Z, 1
1
+ + Z |10 2
Z 1'1 +
12e
z
1/
1|3 (VF(Z,) Vf((Z,), Ze Z²)
2Tp
1
1
(Z. Z111, vz((Z)) A11Z
12141 1.
I Z1+1113
2/7t
21
+ A|| Z + 1/
1
-1) |1
1)
117
+ (Z.(Z,) Vf((Z,), Z. - -z)
1/
S max (W. (z(()))
1
||
1
Z1+1 13
21//
21/
1
1
+ +1I /11-= \1
1/11/|
1)
1Ze 1 + (VF(Z)) - Vf(Z),, --z))
2
17
1
1z,+1 - 1/
2//²
1
1/1 1
| -11 1) 1z, 27 + (VF(Z.) - V.((Z)) Z, 2²),
+ X| M
Z11 + 2 7h
(12)
where the third inquality holds based on the inequality in
By substituting 6, = (E. K, Z. - Zz* and C² = ma IZ, - 11 into 12).
1|- S 1) C2 + 2n + 2Am (I]Z,||+ ||Z,+11l)) + (1 - 2m)) I|, 1/
(13)
The inequality in (13) is the same as the result of Lemma 1 in Zhang et al. (0016) Thus, the fol- lowing lemmas from Zhang et al. (2016) can be directly utilized to derive a probability bound for [|Z,+1
Z 11.
Lemma 2 (Lemma 2 in Zhang et al. 2016)). Define 7 max ||z]|.. By setting t 3. an
upper bound of Z Z 1/ can be written
1(C² X7)
2 T(T - 1)
T
T
Zr+1 11
<
M t=
(t - 1)o,
Σ t=2
(t - 1)] - 2/
The upper bound of ΣT 2 (t 1)6, in Lemma 2 then provided in Lemma
L Lemma 3 (Lemma in Zhang et all (2016)). Assume ||&, - K|r S G, and 12.-Z'l1 1' S H,
Vt > 2. With probability at least 5, ΣT= (t 1)8, is upper bounded by
T
1 T
2 1 + 2CT 1) (T GH([ 1), 1)|- (t-
(t - 1)6, < 2
Σ
2
2
Thhese lemmas can be found in the supplementary material of Zhng et al. (016) that can be downloaded from https::/ccs nj wdu..du.ccm cm//2///pff/AAAA-2001. 2016 S.
15

---

Under review as a conference paper at ICLR 2021
27
Average number of DLA iterations
Qo
Average number of DLĀ iterations
Qo
26
8-
Q:
Q:
25
7-
24
23
22
21
20 Iteration
20
Iteration
(a) Mushrooms
(b) MNIST
30
14
Average number of DLA iterations
28
Average number
iterations
13
26
12
Qo
11
Qo
Q
Q1
20
10
20
40
0
20
40
Iteration
Iteration
(c) Covtype
(d) Smartphone
Figure 4: The values of Qo and Qı versus the number of iteration for the four real-world datasets
where log [2 12 17
Based on Lemma 2 and Lemma 3 the following upper bound of ||z 13 holds with probability at least 1
4 + 2 GHT - - T
ZT+I z
(14)
D PROOF OF THEOREM AND EMPIRICAL RESULTS
For DSPGD with CEM, in the the iteration, the m-th user's 's device only needs to upload one vector in each iteration of DLA, i.e., [.(mn] W, [m]]ee Cy. Since W, [m)] = IV A. [m]. VT `/ B, [m]]], the dimension of W, [m]] W, [m]c,, c,, equals D rr, where r, is the rank of Z, and D is the number of random feature. Moreover, DLA requires several Lanczos iterations to approach the eigenpairs of W. W.. Thus, the communication cost of DSPGD with CEM is linear to + Tt.
To compute the ratio, we first derive the communication cost for DSPGD without CEM. in the 1-the iteration, the m- th user's s device needs to upload two vectors in each iteration of DLA: A, [,
and A, [m]] A Cq. where the dimension of A, C. equals D. For the concatenation of all M vectors M), its dimension equals the number of data samples N. Thus, the
[m, A, Cy: communication cost of DSPGD without CEM is linear to N + M.
Given the number of Lanczos iterations Qo for DSPGD without CEM and the number of Lanczos iterations Q1 for DSPGD with CEM, the ratio can be determined by (N+MD)Q. M(.++D)Q
Accrdiigg Figure 4 it can be seen that the average value of Qo is close to that of Q1 in each iteration t, which indicates Qa < ss 1. As a result, the dominant factor of the ratio is still NDMD M(r++D
Empirically, the figures of the average value of r, versus the number of iterations for the four woal-world datasets are shown in Figure 5 The results show that the rank r, tends to converge as
16

---

Under review as a conference paper at ICLR 2021
12
Average Rank
10
Average Rank
16
6
14
4-
12
20
Iteration
Iteration
(a) Mushrooms
(b) MNIST
25
11
22
10
Average Rank
Average Rank
20
9
18
15
12
10
8
5
0
20
40
20
40
Iteration
Iteration (d) Smartphone
(c) Covtype
Figure 5: The rank of Z, versus the number of iteration for the four
datasets
the value of & increases. Besides, the upper bound of is constant factor larger than the number of eigenvectors Table[] and such upper bound is much smaller than the number users' local data samples, which can explain the dramatical reduction on the communication cost in Figure
PROOF OF THEOREM 3
Define K = UAUT, and P UA The low-rank approximation K with rank s is denoted as
K, = UA and P , UA where the diagonal of A, contains the largest eigenvalues of K while its rest diagonal entries are all zero. The output of DSPGD at iteration is an estimation of K,, denoted as K,, and K, = P.P.
The following two lemmas will be used in the proof of Theorem
Lemma 4. Given K,, the following inequality holds with probability at least 1 for any rank k projection matrix II Raxn
TrITIKK K.)) < Ol )
Proof.
Since rank-A projection matrix, it is obvious that
Tr[II K2)) < K, K.ll..
Fora a rank-s matrix A, the following inequality holds for its Nuclear nom and its Frobenius norm
|| | 2 < =
Hence,
K, K.ll. VolK Kills-
17

---

Under review as a conference paper at ICLR 2021
By Theorem I1 Ze converges to Z' at an (1/tt) rate. Note Z' has the same eigenvectors as K Thus, K, constructed based on Z, also converyes to K, at an ((1/t) rate with a probability at least 1 - 6, ie., K k has an upper bound as
K, K.ll² - O(1(t).
Hence, the following inequality holds with a probability at least 1 - ò
Tr(II(K, K.)) S vsl K. K.llF
- 0 ?
Lemma 5. Fix error parameter e E (0,1). For any rank k projection matrix II Ruxx,
Tr [IK k) (s + I|p np f.
Proof. holds that
Tr (L. IIJ(K -ki) Tr(K K,) Tr (IIKK K,)
= K K. + Tr(K, K.) Tr (II(K R))
Thus, Tr [I(K-K,) - can be rewritten as
Tr [[K - K. (I(K-K))I]
= =IKK- - K,ll- + Tr(K, -K,) Tr II( KI, -m)
It follows that
Tr (I, [I] KI) mI)
=Tr (IIn - II] K.) - II)) + TI (In. - II)(K, - K.) - -m)
=Ir ((In - [K) - KK,) -I)) + Tr(K, K.) Tr(II(,, -K)))
P.++l1 Tr(K, Kk)) -o
where the last inequality comes from Lemma A Thus,
Tr (IICK [I(K-KK))) K.)I s |K K,ll. - ||P - Potil1: +0// -
||p P.
|P P. P
11 + +0lV :
Σ
Σ
n
d() 0 /
i=sth+1
of (P) + o0
Σ
*##1
< k
(P) + ol
Since O(v3 can be arbitrarily small, it can be rewritten as O ( = e Pxll2. Besides,
L of S Ei of = =|P II. Hence, it can be obtained that
Tr [ - -KKKKK))) s (E + k 1IP P
18

---

Under review as a conference paper at ICLR 2021
It can be obtained that
[I II)PII II( -Td, II)PP) Tr((I, I)P.P.)
=T<PPPT -P,P.) Tr(IIPPTT.. P,P, m.
Let TrPPP - -P.P.) ), and then the above equation can rewritten as
[I IP f TNPII -P.P. II) = a + II - 1|
fter sufficient iterations, both a and Tr [I
P,P, II) are non-ne non-negative with high prob-
ability. Thus, by Lemma(5lit holds that
II(I, I| + II PI
II II) + TT(((IPPPT P,P, II)
(15)
k >
$1
Based on 15), Theorem can be proved as follows. Let Y,L, where Y, is the indicator matrix obtained by applying a-appoxximate algorithm to P., then
[I(I, - Y,LY Y PIl v a (In Y,L,Y. P.l
- ).
where Y is the optimal indicator matrix for the linear k-means problem on P.. Since y 1, follows that
a >1( YYL, P.ll < a vl(,, -YL'" P.
7111 (11+++ h Il Y - P1
Thus,
[I - Y,LY PI S 71 ++ I[ - P which is equivalent to fx(Y,) S 7(1 + + 3) miny fY()).
F
PRIVACY PRESERVATION PROPERTY OF FEDERATED KERNEL A- MEMNN
F.1 RECOVER USERS' DATA FROM RANDOM FEATURE MATRICES
A random feature for data samplex has the form cos(w x; bb) where the w and b are determined by the cloud server. Since the value of w x; + cannot be arbitrarily large, the number of its possible values is limited. If enough such random features are collected, the cloud server can determine the value of x; + for each random feature, and then recover x; by solving a system linear equations.
F.2 PROOF OF THEOREM 4
We then prove that the cloud server can at most recover the matrices [Wi[m] T W. [m]m] m = 1,..., M) (only the multiplication W, W.(m)
[ml WW [m] not the matrix (.(m)) from the local com-
putational results (e.g., W, im] W, [m [m]c.)) c.)). The eigenpairs W. [m[m] W. [m] are determined via the distributed Lanczos algorithm. Since
Me A
[m] A+[m]
V /m(1--)) v.)
A+[m] (. By[m]
W.|m] T
D
D
B [m]
A [m]
(1 - n B. B.[m]
A₂ A.[m]] [m]]TA A, [m] can be recovered from W, W.[m].
[m]
19

---

Under review as a conference paper at ICLR 2021
For matrix A, [m] RmmxD (nm D), matrix A' E "m x can be constructed via
= U,A,m]]
where U, Re Xm an arbitrary orthogonal matrix with U. U. 1, By this construction, can be derived that
A' A' = A [m] U. U.A, [m] = Am[m] 1, A im] = Ap[m] Armm].
Since there exist infinite matrices U, satisfying U, I,, the problem A, [m]] A, A.[m] A A' has infinite solutions. Hence, recovering the random feature matrix A.[m]] from [, Ar[m]] an ill- all-posed problem with infinite solutions.
Since by employing CEM, the cloud cannot recover the random feature matrices via matrix opera- tions, according to Section[F.] is infeasible for the cloud server to recover users' data by solving a system of linear equations.
G DDDITIONLL EXPERIMENTAL SETTINGS
The three public datasets (Mushrooms, MNIST, Covtype are selected from the LIBSV M dataset repository. The Smartphone dataset is provided by a company. The smartphone dataset contains the power consumption data of one app on users' smartphones. Its twelve features represent the power consumption on twelve hardware components. The clustering task for this dataset is to find the distinct usage patterns of the app based on the power consumption data. For the concern of privacy, the Smartphone dataset will not be disclosed.
The description of the four existing methods used in the experiments are listed as follows.
1. Centralized kernel k-means Zha et all (001)) (denoted as CK k-mmans): directly perform truncated SVD on the kemeel matrix K UAUT obtain a matrix that consists of the first s column vectors of UA & and then apply linear k- k-means to this matrix;
2. Scalable kemne k- d-masss Wang et all (2019) (denoted as SK k- k-means): utilize the Nyström method to approximate the kemel matrix K, and conduct kernel l- k--eans over the approx- imated kernel matrix;
3. Distributed kemel k-means with random feature (Chitta et al., 2012) (denoted as RFK k- means): first transform the raw data samples to the corresponding random vector via the random Fourier feature method (Rahimi & Recht, 2008 and then utilize distributed linear means to find the clusters space of these random features;
4. Communication efficient distributed kemne PCA Balcan et al. (2016) (denoted CE PCA) first conduct dimension reduction on the raw data samples through the communication efficient kernel PCA that integrates subspace embedding and adaptive sampling techniques to perform approximated kemel PCA in distributed manner, and then apply distributed linear k- means algorithm the data samples after the dimension reduction.
Forthree distributed algorithms (FK k-means, RFK k-means, and CE PCA), the distributed linear k- means algorithm developed in (Balcan et all, 2013) is utilized to obtain the clustering results. Thus, the number of data samples C in the coreset should be assigned.
For FK k- k-means, the maximal iteration number T is selected from [10, 20, 30, 40. 50). In the exper- iments the Mushrooms dataset, C' is set to 1000. In the experiment of the MNIST dataset, C' set to 1000. In the experiment of the Covtype dataset, C' is set to 4000. In the experiment of the Smartphone dataset, is set 4000.
RFK k- m-maans has two hyperparameters: the kernel parameter y, and the number of random features D. The hyperparameter configuration for RFK k-means is set as follows. The value of y is the same that of FK k- meaass. In the experiments of the Mushrooms dataset, D 200, and C is selected from [100, 300, 500, 700). In the experiment of the MNIST dataset, = 800, and C is
3These datasets can be downloaded from https://www/ csie. ntu. edu. htw/"jciLmmiiissmooools/////////
20

---

Under review as a conference paper at ICLR 2021
selected from [100, 300, 500, 700, 900]. In the experiment of the Covtype dataset, D 100, and C' is selected from [1000, 2000, 3000, 5000]. In the experiment the Smartphone dataset, D 50, and C' is selected from [500, 1000, 2000, 3000).
CE PCA has six hyperparameters: the kerne parameter y, the number of principle components d after PCA, the number of random features D, the subspace embedding dimension for the feature expansion d,, The subspace embedding dimension for the data points d,, and the number repre- sentative points p. The hyperparameter configuration for CE PCA is set follows. The value of ς is the same as that of FK k-means In the experiments over different datasets, some hyperparameters of these two methods are not changed. For CE PCA, d₂ = 50, dp 250, and P 500. Besides, the number of principle components d in CE PCA is the same as the number of eigenvectors s in FK k- means. To obtain different comm unication cost and normalized mutual information scores, the value of D is set to different values for both methods. In the experiment over the Mushrooms dataset, D is selected from [20. 50, 100, 200), and C' is set to 1000. In the experiment over the MNIST dataset, D is selected from [100, 200, 400, 800], C' is set to 1000. In the experiment over the Covtype dataset, D are selected from [20, 50, 100, 200), and
set to 4000. In the ex experiment over the Smartphone dataset, D is selected from [20, 50, 100), C is set to 4000.
The discussion of the configuration of D is as follows. For RFK k-means and CE PCA, D is usually set to large values (more than 100). W hile for federated kemel k-manns, D can be set to relatively small values (less than 50). The reason is as follows. RFK A- means (and CE PCA) only employs random feature once to estimate the kemel matrix. Thus, it requires a large number of random features to obtain an estimation of the kernel matrix with low approximation error, and furthermore high NMI score. In contrast, federated kemel k-means is an iterative algorithm where random features are employed in each iteration to reduce the gap between the estimation and the kemel matrix. Hence, the number of random feature is not necessary to be set large value in each iteration.
The communication cost of the three algorithms are determined follows. For FK k- t-means, the communication cost is the communication cost of DSPGD with CEM plus the that of the distributed linear k-means. For RFK k- m-meass its communication cost equals the communication cost of the distributed linear k- m-means For CE PCA, its communication cost is the communication cost of performing distributed PCA plus the communication cost of the distributed linear k- k-means. The communication cost the distributed linear k- t-means equals the number of data samples in the coreset times the dimension of a data sample. In both FK k-means and CE PCA, the dimension of data sample equals the number of eigenvectors In RFK k- k-meass, the dimension of a data sample equals the number of random features D since the raw data cannot be exposed to the cloud server, and only the random feature vectors can be uploaded to the cloud server.
21


Reviews:
[{"review_id": "XJEFrCiFDDP", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper proposes a distributed version of kernel k-means clustering where some federated structure is used to do distributed processing on the data. Privacy and communication issues are also studied. Numerical results are provided.\n\nReasons for the score:\n\nThis paper seems provide a new algorithm for distributed clustering. However, the way the algorithm is presented look like a patch of a number of things coming together one after the other with no general structure. This might be caused by the fact that the algorithm is only presented in the appendix. \n\nThe paper is written in a convoluted manner. This is the main limitation, at some point, we are talking about k means, SVS, DLA,DSPGD, EVD, SPGD, a bunch of other methods that are coupled together towards the main approach.\n\nProblem 1 seems to be an integer programming problem, thus with very high computation complexity. It is not clear how this is solved.\n\nIn the abstract please let me know what are those two levels of privacy you are talking about.\n\nIn the abstract, what does it mean that the clustering loss of the distributed method approaches the centralized one, please elaborate.\n\nWhy developing a federated learning algorithm is a promising approach? Please elaborate.\n\nThe second part of the intro turns into a detail technical analysis of the algorithm components, and so far we haven’t seen the algorithm so it all remains a technical abstract  discussion that takes away the main messages.\n\nThe algorithm is in the appendix, so the description and analysis is made on an item that has not been presented in the main text.\n\nThe way the result is presented makes it look like the proposed method is a concatenation of other results, rather than the solution of a technical challenge in the problem.\n\nNumerical results are well presented,", "extra_scores": {}, "extra_text": {}}, {"review_id": "JF3IaHcgkSd", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThis paper proposes a new method and two algorithms for solving kernel k-means. The contribution is that the algorithms converge to the optimal solution. The downsides are 1) the method is not better than a simple baseline (i.e., random features + distributed power method) and 2) the main theorem (Theorem 3) is wrong.\n\n\n##########################################################################\n\nReasons for score:\n\nI vote for rejection for two reasons. First, the proposed method appears not useful. The same problem can be solved in a much simpler and faster way. Second, the main theorem, Theorem 3, is wrong.\n\n\n##########################################################################\n\nPros:\n\n+ This paper develops a new method of distributed kernel k-means. The method is new, although I do not find it very useful.\n\n+ This paper proves that two algorithms can correctly solve the trace-norm regularized problem in Section 4.1.\n\n\n##########################################################################\n\nCons:\n\n1. First and foremost, I do not see a good reason for using the proposed algorithm. The goal of the algorithm is to find the top singular vectors of the random features, $A$.\n\n    - The solution to the trace norm regularized problem, $Z^*$, has the same singular vectors as K. By finding $Z^*$, you can find the eigenvectors of $K$.\n\n    - However, the same goal could be achieved in an easier and less expensive way, i.e., random features + distributed power method. Random features are naturally distributed among the clients. Their truncated SVD could be found by the distributed power method or Krylov subspace methods. Truncated SVD is easier than solved the proposed trace norm regularized problem because the latter uses SVS which repeatedly performs SVD.\n\n2. I am very surprised that Theorem 3 does not reply on $D$ (the number of random features). So I checked some of the proofs. I found Theorem 3, which is the main theorem, is wrong.\n\n    - $Z^*$ has the same top eigenvectors as $\\xi$. But $Z^*$ may not have the same as $K$.\n\n    - The proof of Theorem 3 relies on that $Z^*$ has the same eigenvectors as $K$. This is wrong.\n\n\n3. The description of the algorithm is difficult to follow. I’d suggest splitting algorithm description into 3 paragraphs: 1) Client-side computation, 2) server-side computation, and 3) communications.\n\n\n\n\n\nTypos:\n\n17th page: \"The following two lemmas will be used in the proof of Theorem 4.” Do you mean Theorem 3?\n\n##########################################################################\n\nUpdates after discussing with the authors\n\n1. The paper is not very clearly written, and I had misunderstandings. Some of my comments above are not right.\n\n2. However, I will not change my rating. I found the convergence rates stated in the paper are misleading. The paper claims $O(1/T)$ convergence rate. In fact, this is WRONG. The authors assume the Frobenius and trace norms of $n\\times n$ matrices are CONSTANTS. This is not possible. The norms are $O(n)$. Simple arguments can show $|| \\xi ||_F = G$ is $O(n)$.\n\n3. Based on the right assumption that $|| \\xi ||_F = G = O(n)$, the required number of iterations is $T = O(n^2)$. The algorithm is not communication-efficient. It is more expensive than communicating the $n\\times n$ kernel matrices.\n\n4. After reading my comments, the authors changed their notation from $G$ to $\\gamma$, $C$, $G$, and $H$. They are also Frobenius and trace norms of $n\\times n$ matrices. The authors assume $\\gamma$, $C$, $G$ and $H$ are constants. This is WRONG. They are $O(n)$. \n\n    - For example, if they use the bound of Rahimi and Recht,  then $|| \\xi - K ||_F^2 = G^2$ is $O(n^2)$.  A bound as good as $|| \\xi - K ||_F^2 = O(n)$ would surprise me; if the authors know such a bound, please let me know. \n\n    - Let me strengthen my point again: IT IS WRONG TO ASSUME MATRIX NORMS ARE CONSTANTS! If the authors can prove they are constants, they need to show me the proofs. If they cannot, they should assume Frobenius norm and trace norm are $O(n)$.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FG_d-Jy3fm7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed a new distributed kernel k-means algorithm that has lower communication overhead compared to the available methods while does not require transmitting the data samples from agents to the master node and therefore claims to preserve the privacy of agents. The paper is rather difficult to follow and the novelty of the paper is not very clear to me. It seems to me that the major contribution of the paper is to come up with efficient tricks during the implementation of the distributed Lanczos algorithm (DLA) to find the eigenvalues of the kernel approximated by using the well-known random Fourier features (Rahimi, nips 2008). So the end result is not something utterly novel but rather an efficient way of utilizing available tools to design a new distributed algorithm.\n\nThere are several points that I think need to be clarified:\n1. The literature review does not clearly illustrate the contribution of the paper. For instance, in Section 2.1, the author says \"However, these algorithms are designed with an assumption that they are executed at the cloud server where the constraint on transmissions of the raw data samples does not exist.\" Does this mean that your work is the first to constrain the transmission of data samples? If so you should clearly say so. Besides, why transmitting the raw data sample is important here? Is it due to privacy issues? Because the way I see it, one does not need to transmit the raw data samples but rather its local kernel matrix K, and doing so does not necessarily endanger the privacy of an agent, since one cannot easily recover data samples from K.\n\n2. In Section 6.2, the author says \"According to the results in the four subfigures, it is shown that CEM can reduce communication cost of DSPGD by more than 95%.\" It would be interesting to explain what values of r_t, Q_0, and Q_1 leads to this improvement and why. \n\n3. The 60% communication cost reduction mentioned throughout the paper seems a bit exaggerated as it does not consistently happen. It only happens for the MNIST dataset in Figure 3(b). Do you know why? My guess is that due to the high sparsity level of MNIST samples, the kernel matrix might contain a lot of zeros leading to such behavior. \n\n4. What about the drawbacks of the proposed method? What I see is a very complicated algorithm that requires heavy computational resources at each agent, which makes it unsuitable for the toy example explained in the introduction about smartphones.\n\nAfter rebuttal: I thank the author for their response but I have to lower my rating by one step after reading the comments of Reviewer2. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "-bzpPnS8Vmp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper proposes a federated kernel k-means algorithm (FK k-means). The algorithm consists of two parts: a distributed stochastic proximal gradient descent (DSPGD) update rule, and a communication efficient mechanism (CEM) to reduce the communication cost. Instead of solving the original integer programming problem, the authors consider the relaxed convex stochastic composite optimization (SCO) problem and extends it to a distributed setting. \n\nThe main contribution is that the authors show, both theoretically and experimentally, that their proposed algorithm converges to the true solution of the SCO problem at O(1/T) rate. It is also proved that the communication cost does not grow with the number of samples N. In addition the authors characterize the error ratio between their algorithm and the original k-means. At the end the authors prove that the central server cannot recover the feature matrices. The authors compare their algorithm with other k-means algorithms on several datasets. \n\n\nPros:\n\n- The federated setting of k-means with privacy preservation property is interesting and relatively new. \n\n- The presentation of the theorems is very clear. The authors put interpretation after each statement and it is easy to follow most of the time. In particular it is shown that the proposed algorithm approaches the baseline scalable kernel k-means algorithm as T increases, both theoretically and experimentally.\n\n- I appreciate the discussion of the motivation and related works in the first two section of the paper. \n\n\nCons:\n\n- The whole Section 4 of the paper is filled with technical details and hard to follow. Considering the page limit, why not put the algorithms here, and put the details in the appendix? In addition the authors can consider putting important observations as lemmas. \n\n- It seems the proof techniques are somehow standard. The whole proof of Theorem 1 feels like an extension to [Zhang et al., 2016] in a distributed setting. I did not check the other proofs though. \n\n- My biggest concern is about novelty. Currently the proposed algorithm is heavily influenced by [Zhang et al., 2016] and [Wang et al., 2019]. If that is not the case, the authors can consider including a table to illustrate the difference between the algorithms. \n\n------------------------------\n\nPost-rebuttal:\n\nI appreciate the authors' feedbacks. However the authors' response to the proof of Theorem 1 is not the most convincing, which is a big part of the claimed contribution. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a approach to the distributed kernel k-means problem using a combination of random features to efficiently approximate the kernel matrix, a distributed stochastic proximal gradient algorithm which calls a distributed lanczos algorithm as a primitive to find a low-rank approximation to the kernel matrix, and additional compression to reduce the cost of the communications. 

The algorithm is a novel combination of prior ideas, and empirically works well. However, the claimed theoretical convergence rate is not convincing: e.g., the convergence rate depends on the Frobenius norm of the error in approximating the kernel with random feature maps, which is O(n^2) for a problem with n data samples. This implies that O(n^2) iterations must be used in the algorithm, which is already slower than a naive approach to kernel k-means.

This paper takes a promising approach to the problem, but as the potential contribution lies in combining prior ideas in order to obtain a provably guaranteed approximate solution to the distributed kernel k-means problem, and the proposed algorithm was not shown to satisfy this promise, the recommendation is to reject.
Decision: Reject