Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

This 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.

Reasons for the score:

This 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. 

The 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.

Problem 1 seems to be an integer programming problem, thus with very high computation complexity. It is not clear how this is solved.

In the abstract please let me know what are those two levels of privacy you are talking about.

In the abstract, what does it mean that the clustering loss of the distributed method approaches the centralized one, please elaborate.

Why developing a federated learning algorithm is a promising approach? Please elaborate.

The 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.

The algorithm is in the appendix, so the description and analysis is made on an item that has not been presented in the main text.

The 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.

Numerical results are well presented,
review_title: A distributed method for kernel k means with some performance guarantees

final_score: rating: 1: Trivial or wrong
review_content: ##########################################################################

Summary:

This 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.


##########################################################################

Reasons for score:

I 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.


##########################################################################

Pros:

+ This paper develops a new method of distributed kernel k-means. The method is new, although I do not find it very useful.

+ This paper proves that two algorithms can correctly solve the trace-norm regularized problem in Section 4.1.


##########################################################################

Cons:

1. 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$.

    - 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$.

    - 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.

2. 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.

    - $Z^*$ has the same top eigenvectors as $\xi$. But $Z^*$ may not have the same as $K$.

    - The proof of Theorem 3 relies on that $Z^*$ has the same eigenvectors as $K$. This is wrong.


3. 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.





Typos:

17th page: "The following two lemmas will be used in the proof of Theorem 4.” Do you mean Theorem 3?

##########################################################################

Updates after discussing with the authors

1. The paper is not very clearly written, and I had misunderstandings. Some of my comments above are not right.

2. 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)$.

3. 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.

4. 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)$. 

    - 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. 

    - 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)$.




review_title: Not better than baseline; main theorem is wrong

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

There are several points that I think need to be clarified:
1. 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.

2. 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. 

3. 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. 

4. 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.

After rebuttal: I thank the author for their response but I have to lower my rating by one step after reading the comments of Reviewer2. 
review_title: The paper is not novel by itself but is technically solid and proposed a new distributed clustering algorithm.

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:

This 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. 

The 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. 


Pros:

- The federated setting of k-means with privacy preservation property is interesting and relatively new. 

- 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.

- I appreciate the discussion of the motivation and related works in the first two section of the paper. 


Cons:

- 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. 

- 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. 

- 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. 

------------------------------

Post-rebuttal:

I 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. 
review_title: Review

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