Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper discusses a random feature-based multi-agent kernel learning approach. For both generalized inner-product (GIP) and random feature (RF) kernels, the authors propose, in each agent, to exchange the random feature matrix (instead of the model parameters). By considering the problem of kernel ridge regression, some theoretical results including the kernel matrix approximation error (Lemma 4.1), training (Theorem 4.2), and generalization performance (Theorem 4.3) are obtained in Section 4. Some numerical experiments on UCI datasets are provided in Section 5.

The authors argue (e.g., in Corollary 1) that the proposed approach is more efficient as it requires less communication to achieve min-max optimal generalization performance.
main_review: I find it difficult to position this paper in the existing literature on distributed kernel learning. 

For example, if the focus is on privacy issues and on not exchanging local data or labels, then more on privacy considerations should be discussed, e.g., in Algorithm 2 it is still required to exchange labels, the authors mention on page 7 that there are ways to avoid such privacy leakage, but details are deferred to the appendix. If the major contribution is the proposed method needs less communication, then it is then *necessary* to compare *explicitly* in which case/regime the proposed method improves previous results such as [Liu et al., 2021]. For the moment, it is not clear, at least to me as a reader, to which extend the results are significant. 

I would consider changing my scores if the authors could clarify the major contribution in this paper.

----

**After rebuttal**: I thank the authors for their clarification and their efforts in updating the paper. I believe the contribution of this paper is now much clearer and I've updated my score accordingly.
summary_of_the_review: Some detailed comments:

* page 5 [Approximation for GIP kernel]: I get confused here because the authors first assume the feature vectors are normalized (which is OK but makes the GIP kernel defined in Equation (4) less interesting, which, in essence, only depends on the "angle" $\psi(x,x')$) and then further takes the nonlinear function $\zeta$ to a binary function: is there any evidence or previous results saying what type of kernel can one approximation with this particular choice of nonlinearity? At least, this is a much less general family of kernels than the GIP kernel defined in Equation (4).
* the theoretical results in Lemma 4.1, Theorem 4.2, and 4.3 are interesting: while it is stated in Lemma 4.1 that one needs at least $P = O(N)$ random features to well approximate the (whole) kernel matrix up to some $O(1)$ error, it turns out, in Theorem 4.2 that one only needs much less ($P = O(\log(N))$) to get similar training error in the distributed setting. Also, while the results for GIP and RF kernel in Lemma 4.1and Theorem 4.2 are somewhat similar (up to constants), the results in Theorem 4.3 for these two kernels are very different and one needs only $P = O(\sqrt{N})$ for random features but $P = O(n)$ for GIP kernel. Could the authors comment, or perhaps also provide some intuition on this (which may be of independent interest)?
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work considers multi-agent optimization over RKHS together with random feature approximations. The crux is the development of two different techniques for decentralized computation through a novel introduction of a generalized inner-product kernel. Convergence analysis and numerical validation are provided.
main_review: The main technical contribution in my reading is establishing minimax optimal generalization performance of the proposed technique. My main curiosity comes from whether the strength of this convergence result is through simply applying a stronger analysis technique, or if there is something specific about the derived algorithm that permits this strong result? Put another way, is the generalization performance an artifact of the analysis or a result of a carefully calibrated algorithm? This point is obscured in the current writing.

One of the technical innovations of this work is the use of the generalized inner-product kernel. This subsumes a number of common choices such has polynomial (polynimal ?), Gaussian, Laplace, sigmoid, etc. This is critical to obtaining a degree of privacy preservation as it allows agents to only require sharing knowledge of pairwise angles between feature vectors.

Is sharing the matrix $A_m$ actually more communication efficient than sharing local kernelized function evaluations? This seems like it would actually require more network throughput. Put another way, sharing the parametric representation of each agent's local function is computationally costly, and potentially worse than simply sharing estimates of the local label/target variable. In that way, Algorithm 2 seems much more practical, even it requires label exchange. 

In Assumption 2, I am a little concerned about the Lipschitz continuity assumption because of the presence of the norms in the denominator in equation (4). Can we be sure that this is independent of $z_2, z_3$? Some comment about this seems warranted.

In what sense is the convergence theory presented here stronger or sharper than that which is discussed in the introduction for multi-agent optimization over RKHS? Such a granular contrastive discussion is missing from Section 4.

Along the lines of the previous comment, the authors have not compared against any of the other decentralized methods for RKHS optimization experimentally, which makes it difficult to assess whether these results actually sharpen the state of the art in any meaningful way.


Minor comments:

 ``However this approach raises privacy concerns, thus almost never being used in practice." Is awkward syntax. Consider rephrasing.

Also, the main boldface question at the top of page 2 is a sentence fragment.

The statement "where the first one only needs one-shot information exchange, but requires
sharing data labels among the agents; the second one needs iterative information exchange, but does
not need to share the data labels." Is not accurate in the sense that if label exchange is required, then this is mathematically equivalent to data exchange, i.e., realizations of random variables are required... Therefore it is suspicious to state this and immediately afterward state that raw data exchange is not required.

summary_of_the_review: While the paper proposes some interesting methodologies for decentralized optimization over RKHS, it is difficult to assess whether in theory or practice they actually advance the state of the art. This is because they have not done a rigorous comparison of their convergence theory or contrastive numerical experimentation with competing approaches. These aspects need to be thoroughly addressed before I would consider this work to meet the bar for publication.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The decentralization problem has data distributed among many agents and each agent is wanted to maintain some privacy. In this paper, the authors study the decentralized empirical risk minimization problem with reproducing kernel hilbert space. Two large classes of kernels are considered: (1) generalized inner-product (GIP) kernel based on arccosine kernel (proposed in this work), (2) random feature (RF) kernel. In order to attain decentralization, authors approximate kernels based on the inner product of two finite vectors, and propose algorithms (one-shot and iterative) to optimize private models. In addition, authors study in theory the approximation error for kernels, optimization algorithm performance and generalization error. Finally, experiments are presented to validate the algorithms and theoretical results.
main_review: Strengths

1. The paper is clearly written. The contents are well organized and easy to follow. 

2. The algorithms and theoretical analyses are technically sound and novel. I read through the algorithms and corresponding discussions. I checked their details and everything looks correct to me. The rkhs setting is new and interesting. The theoretical analyses under the new settings are sound. I read the proof for theorem 4.1 and it looks good to me. These performance and error analyses are classical in the kernel field. Although I didn't read all proofs and there may be mistakes, I think they can be easy to fix.

Weaknesses

1. The experiment and comparison to other methods are weak. As mentioned in the introduction, communicating high-dimensional parameters is problematic and might leading to slow convergence, but I feel this is not convincing because of no sound evidence. I would suggest adding a simple experiment to demonstrate this. It is also unclear how previous approaches perform compared to this work. This work relies on kernels so there can be some shortcomings, e.g. kernels may not be a good choice for large-scale datasets. I would suggest (1) adding experiments to compare this work with previous ones to see when this approach is preferable or to highlight the shortcomings (or advantages) of other methods; (2) adding a table summarizing the difference between this work and others, e.g. whether they use neural network and what are pros and cons.


Minor: 

Above Eqn. (5) duplicate ''as''

Below Eqn. (3) '' ... represent (m . i)th element of vector [K \alpha] .. '' redundant to the notation section

Page 5 ''will dependent on the underlying kernel approximation schemes'' -> ''will be dependent ...''



summary_of_the_review: Overall, I think this paper is technically sound, has solid theoretical contributions and the paper is clearly written, but it doesn't position itself well in the related area and the experiment is weak. I vote for weak acceptance.
review_title: null

Meta-review: In this paper, the authors study the decentralized empirical risk minimization problem with Reproducing Kernel Hilbert Space. I found the problem formulation and the solution quite interesting. The authors also answered the main comments of the reviewers. Even though part of the work is incremental, I feel that there is enough merit to accept this paper.
Decision: Accept (Poster)