Decentralized Learning for Overparameterized Problems: A Multi-Agent Kernel Approximation Approach
Authors: Prashant Khanduri
Haibo Yang
Mingyi Hong
Jia Liu
Hoi To Wai
Sijia Liu
Venue: ICLR 2022 Poster (2022)
Keywords: distributed optimization
over-parameterized optimization
kernel learning

Abstract: This work develops a novel framework for communication-efficient distributed learning where the models to be learned are overparameterized. We focus on a class of kernel learning problems (which includes the popular neural tangent kernel (NTK) learning as a special case) and propose a novel {\it multi-agent kernel approximation} technique that allows the agents to distributedly estimate the full kernel function, and subsequently perform decentralized optimization, without directly exchanging any local data or parameters. The proposed framework is a significant departure from the classical consensus-based approaches, because the agents do not exchange problem parameters, and no consensus is required. We analyze the optimization and the generalization performance of the proposed framework for the $\ell_2$ loss. We show that with $M$ agents and $N$ total samples when certain generalized inner-product kernels (resp. the random features kernel) are used, each agent needs to communicate $\mathcal{O}\big({N^2}/{M}\big)$ bits (resp. $\mathcal{O}\big(N \sqrt{N}/M \big)$ real values) to achieve minimax optimal generalization performance. We validate the theoretical results on 90 UCI benchmarking datasets (with average data size $N \approx 1000$) and show that each agent needs to share a total of $200N/M$ bits (resp. $3N/M$ real values) to closely match the performance of the centralized algorithms, and these numbers are independent of parameter and feature dimensions. 

Published as a conference paper at ICLR 2022
DECENTRALIZED LEARNING FOR OVERPARAMETER- IZED PROBLEMS: A MULTI-AGENT KERNEL APPROX- IMATION APPROACH
Prashant Khanduri! Haibo Yang", Mingyi Hong', Jia Liu', Hoi-To Wai", Sijia Liu 'University of Minnesota, 'hee Ohio State University, CCUKK Michigan State University, *MIT-IBM Watson AI Lab, IBM Research 15aand99@@umi edu, yang. 59520osu. edu, mhong@umn edu liußece. osu. edu, htwai cuhk. edu. hk, Liusijia5emsu.edi edu
ABSTRACT
This work develops a novel framework for communication-efficceent distributed learning where the models to be learnt are overparamettrized. class of kernel learning problems (which includes the popular neural tangent ker- nel (NTK) learning as a special case) and propose a novel multi-agent kernel approximation technique that allows the agents to distributedly estimate the full kernel function, and subsequently perform distributed learning, without directly exchanging any local data parameters. The proposed framework is signifi- cant departure from the classical consensus-based approaches, because the agents do not exchange problem parameters, and consensus is not required. We analyze the optimization and the generalization performance of the proposed framework for the Eg loss. We show that with M agents and N total samples, when certain generalized inner- mnor-product (GIP) kernels (resp. the random features (RF) kernel) are used, each agent needs to communicate O (NN2/M) bits (resp. ONNNN/M) real values) to achieve minimax optimal generalization performance. Further, we show that the proposed algorithms can significantly reduce the communication complexity compared with state-of-the-arr algorithms, for distributedly training models to fit UCI benchmarking datasets. Moreover, each agent needs to share about 200 //M bits to closely match the performance of the centralized algo- rithms, and these numbers independent of parameter and feature dimension.
focus on a
INTRODUCTION
Recently, decentralized optimization has become mainstay of the optimization research. In de- centralized optimization, multiple local agents hold small to moderately sized private datasets, and collaborate by iteratively solving their local problems while sharing some information with other agents. Most of the existing decentralized learning algorithms are deeply rooted in classical consensus-based approaches (Tsitsiklis) 1984), where the agents repetitively share the local param- eters with each other to reach an optimal consensual solution. However, the recent trend of using learning models in the overparameterized regime with very high-dimensional parameters (He et al., 2016 Vaswani al., 2017 Fedus et al.) 202I) poses significant challenge to such parameter sharing approaches, mainly because sharing model parameters iteratively becomes excessively ex- pensive the parameter dimension grows. If the size of local data is much smaller than that of the parameters, perhaps a more efficient way is to directly share the local data. However, this ap- proach raises privacy concerns, and it is rarely used in practice. Therefore, fundamental question of decentralized learning in the overparameterized regime is:
(Q) For overparameterizze learning problems, how to design decentralized algorithms that achieve the best optimizationnggeerrlzzaiiio performance by exchanging minimum amount of information?
We partially answer (Q) in the context of distributed kernel learning (Vert et al. 2004p. We depart from the popular consensus based algorithms and propose optimization framework that does not require the local agents to share model parameters or raw data. We focus on kernel learning because: (i) kernel methods provide elegant way to model non-linear learning problems with complex data

---

Published as a conference paper at ICLR 2022
Table Comparison of the total communication required per node by different algorithms for non- overparameterized (NOP) and overparameterized (OP) regimes. Please see Appendix g for a detailed dis- cussion of the algorithms. Here N is entire sample size, UB on M denotes the upper bound on the number of nodes, M, d is the data dimension, 8 2 2 is constant, and T' denotes the total communication (iterations) rounds utilized by the distributed algorithms.
Communication (Real Values)
Algorithm
Kernel
UB on M
NOP
OP
DKRR-CM Li et al. 2020
Any
(Na1r+
((TTN)
O(dTN)
DKRR-RF-CM (Liu 2021)
RF
(NN
O(TVN)
O(TN2)
Decentralized-Rl RF (Richards al.
2020
RF
((N+)
O(TVN)
O(TN2)
DKLA/COKE (uu et al.
2020
RF
Any M
((TVN)
O(TNA)
RF
O (NNN
Algorithm (this work)
Any M
GIP
M
dependencies as simple linear problems (Vert et al. 2004; Hofmann et al. 2008). and (ii) kerne- based methods be used capture the behavior of fully- trainee deep network with large width (Jacot et al. 2018 Arora et al. 2019 2020).
Distributed implementation of kernel learning problems is challenging. Current state-of-the- algo- rithms for kernel learning either rely on sharing raw data among agents and/or imposing restrictions
on the number of agents (Zhag et al. 2015 Lin et 2017 Koppel al. 2018 Lin et al., 2020
Hu et al. 2020: Pradhan et al. 2021 Predd et al. (006). Some recent approaches rely on specific random feature (RF) kernels to alleviate some of the above problems. These algorithms reformulate
the (approximate) problem in the parameter domain and solve it by iteratively sharing the (poten-
tially high-dimensional) parameters (Bouboulis et al., 2017, Richards et al., 2020 Xu et al, 2020 Liu et al.) 202T). These algorithms suffer from excessive communication overhead, especially in the overparameterized regime where the number of parameters is larger than the data size N. For example, implementing the neural tangent kernel (NTK) with RF kernel requires at least ((N
3 2. random features (parameter dimension) using ReLU activation (Arora et al. 2019 Han et al,, 2021 For such problems, in this work, we propose novel algorithmic framework for decentral- ized kernel learning. Below, we list the major contributions of our work.
[GIP Kernel for Distributed Approximation] We define new class of kernels suitable for dis- tributed implementation, Generalized inner- umerr-rrdduct (GIP) kernel, that is fully characterized by the angle between pair of feature vectors and their respective norms. Many kernels of practical impor- lance including the NTK can be represented as GIP kernel. Further, we propose multi-agent kernel approximation method for estimating the GIP and the popular RF kernels at individual agents.
[One-shot and Iterative Scheme] Based on the proposed kernel approximation, we develop two optimization algorithms, where the first one only needs ohe-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. key feature of these algorithms that neither the raw data features nor the (high-dimensional) parameters are exchanged among agents.
[Performance of the Approximation Framework] We analyze the optimization and the general- ization performance of the proposed approximation algorithms for &a loss. We show that GIP kernel requires communicating O(N2/M) bits and the RF kernel requires communicating real values per agent to achieve minimax optimal generalization performance. Importantly, the re- quired communication is independent of the function class and the optimization algorithm. We validate the performance of our approximation algorithms on UCI benchmarking datasets.
/M)
compare the communication requirements of the proposed approach to popular dis- tributed kernel learning algorithms. Specifically, DKRR- CM (Lin et al.] 2020) relies on sharing data and is therefore not preferred in practical settings. For the RF kernel, the proposed algorithm out- performs other algorithms in both non-overparameteriiee and the overparameterized regimes when T N/M. In the overparameterized regime, the GIP kernel is more communication efficient compared to other algorithms. Finally, note that since our analysis is developed using the multi- seen---ermelapppooimattio it does not impose any upper bound on the number of agents in the network.
In Table I
To achieve approximation error = (1//NN).
2

---

Published as a conference paper at ICLR 2022
Notations: We use R. R", and R"xm to denote the sets of real numbers, d-dimensional Euclidean space, and real matrices of size n x m, respectively. We use N to denote the set of natural numbers. (0, Σ) is multivariate normal distribution with zero mean and covariance E. Uniform distribution with support [a. b] is denoted by ( b]. (a, b) (resp. (a, b) denotes the inner-product in Euclidean space (resp. Hilbert space H). The inner-product defines the usual norms in corresponding spaces. Norm ||| of matrix A denotes the operator norm induced by l vector norm. We denote by [a]; or [a] [ the 7th element of vector a. [A al.") denotes the (i j)th element of vector A a. Moreover, A A is the 1 column of A and [A]ma is the element corresponding to m row and htth column. Notation m [MM] denotes m E {l... M. Finally, 11 [[E] is the indicator function of event E.
PROBLEM STATEMENT
Given a probability distribution x (.. y) over X' x R. we want to minimize the population loss
L()) E.g Fvs.sra((e.))) ((()rtteee((((()))))))))))())()) (((f()),
where x E X C Rdd and y E R denote the features and the labels, respectively. Here, f X + I is an estimate of the true label We consider distributed system of M agents, with each agent m E [M]] having access to locally available independently and identically distributed (i.i.)) dataset Nm = {amm (8) (i)
π (I, v). The total number of samples is N n.M. The goal of kernel learning with kernel function, -(.,-) X x X + I. is to find a function f E H (where H. is the reproducing kernel Hilbert space (RKHS) associated with & (Vert al.) 2004g) that
1/ J'=1 with (1) ( ,
minimizes 1 We aim to solve the following (decentralized) empirical risk minimization problem
A (R()= = 2()) + 11 = M m=1
M (f) + 2
min JEH
(2)
where À > 0 is the regularization parameter and (f)= = EiEN {(f( ), ym is the local loss at each m E [M]. Problem 2 can be reformulated using the Representer theorem (Schölkopf
al. 2002 with 7m (ax) +/ EiEN,, {[Ka),, (t) w Vm E [M]. as
> aallk = M {R(a)= c(a)+ + 2 2
1 M
E Em (a) + [allk]
min aERN
(3)
m=1
where K E RNN is the kernel matrix with elements k(am) x (1) Vm, mn E [M] Vi E Ni and Vj E Nm. The supervised (centralized) learning problem 3 is a classical problem in sta- tistical learning (Caponnetto & De Vito 2007) and has been popularized recently due to con- nections with overparameterizee neural network training (Jacot al. 2018 Arora al. 2019 An alternate way to solve problem 2 (and 33) is by parameterizing in by Ø E R as fo (2; 8) (0, Φz())) where ΦD
+ R is a finite dimensional feature map. Here, (-(()
is designed to approximate k(.,.) with kn xx' = ((D(()) Φn("')) (Rahimi & Recht 2008
Using this approximation, problem (and can be written in the parameter domain with (2)
(m, = EiEN {((8, (1(())
ym vm E [M]. as
M M Σ
11012 = 2
>
(m) + +
X |1011
min BERD
(4)
Note that 4 is a D D-dimensional problem, whereas is N-dimensional problem. Since 4 is
in the standard finite-suni suite-summae form, it can be solved using the standard parameter sharing decentralized optimization algorithms (e.g., DGD (Richards et al., 2020) ADMM (Xu al.. 2020p which share D-dimensional vectors iteratively. However, when 4 is overparameterized with very large D (c.g., D O(N²) with > 2 for the NTK), such parameter sharing approaches are no longer feasible because of the increased communication complexity. An intuitive solution to avoid sharing these -igh-dimensional parameters to directly solve B However, is by no means clear if and how one can efficiently solve Bb in decentralized manner. The key challenge is that, unlike the
The techniques presented in this work can be easily extended to unbalanced datasets, i.c., when each agent has dataset of different size.
3

---

Published as a conference paper at ICLR 2022
conventional decentralized learning problems, here each loss term {(Ka)) Vin is not separable over the agents. Instead, each agent m's local problem is dependent on k(am Im
(8)
() with m + m.
Importantly, without directly transmitting the data itself (as has been done in Predd al. (2006); Koppel et al. (2018); Lin et al. (2020), it is not clear how one can obtain the required (m-i) element of Ka. Therefore, to develop algorithms that avoid sharing high- figh-dimensional parameters by directly (approximately) solving ( it is important to identify kernels that are suitable for decentralized implementation and propose efficient algorithms for learning with such kernels.
3 THE PROPOSED ALGORIHHM
In this section, we define a general class of kernels referred to as the generalized inner product (GIP) kernels that are suitable for decentralized overparameterizzed learning. By focusing GIP kernels, we aim to understand the best possible decentralized priimization/geerrlizaaai mance that can be achieved for solving (3). Surprisingly, one of our proposed algorithm only shares ((nN)= = O(N2 /M) bits of information per node, while achieving the minimax optimal gener- alization performance. Such an algorithm only requires one round of communication, where the messages transmitted are independent of the actual parameter dimension (i.e., D in problem 4D;; further, there is no requirement for achieving consensus among the agents. The proposed algo- rithm represents significant departure from the classical consensus-based decentralized learning algorithms. We first define a class of kernels that we will focus on in this work.
perfor-
Definition 3.1. [Generalized inner-product (GIP) kernel] We define GIP kernel as:
k(z, x') g (1r, x'), || I|='
where (ar,, x() arccos(aF"d) x/ ([I== ||| I|)) [0, denotes the angle between the feature vectors x and oo; and g(:, ||=|| ||a11) is assumed to be Lipschitz continuous (cf. Assumption D.
m]
Remark 1. Note that the GIP kernel is generalization of the inner-product kernels (Schölkopf
et al. 2002 i.e., kernels of the form l(x x') = k(xx,x')) Clearly, k((x, x²)) can be represented as k( [r, interest can be represented as GIP kernels, some examples include NTK (Jacot et al. 2018 Chizat
= g(v(2, z²), ||=]], ||a²']]
for some function g-).. Moreover, many kernels of practical
jet al. 2019 Arora et al. 2019). arccosine (Cho & Saul 2009). polynimal, Gaussian, Laplacian,
sigmoid, and inner-product kernels (Schölkopi al.] 2002).
The main reason we focus on the GIP kernels for decentralized implementation is that, this class of kernels can be fully specified at each agent if the norms of all the feature vectors and the pairwise angles between them are known at each agent. For example, consider an NTK of single hidden- ==x''====x (z/x, xx' 22m)/2r (Chizat et al. 2019). This kernel can be fully learned with just the knowledge of norms and the pairwise angles les the feature vectors. For many applications of interest BBetti & Mairal 2019: Geitman et al. 2020 Pedregosa et al. 2011). normalized feature vectors are used, and for such problems, the GIP kernel at each agent can be computed only by using the knowledge of the pairwise angles between the feature vectors. We show in Sec. 3.1 that such kernels can be efficiently estimated by each agent while sharing only a few bits of information. Importantly, the communication requirement for such kernel estimation procedure is independent of the problem's is parameter dimension (i.e., D in 4 making them suitable for decentralized learning in overparameterized regime. Next, we define the RF kernel.
layer ReLU neural network: k(z, 2²) ) x² x²xx x²'x((
Definition 3.2. |Random features (RF) kernel] RF kernel is defined (Rahimi & Recht 2008
Rudi & Rosasco 2017 Li et all
2019:
[ ((ar,w) (w))(() Jwe
k(x,=')
(6)
with (2, q) being the probability space and č: S2 RR
Remark 2. The RF kernel can be approximated as: k(,,,) se kr(xxx²) (dr(x), (r()))) E R² and (wi drawn i.id. from distribution
with (x(x) = J (1), ((x,")))"" g(w). A popular example of the RF kernels is the shift-invariant kernels, i.e., kernels of the form k(x,x') = k(x - z') Rahimi & Recht 2008 The RF kernels generalize the random Fourier features construction (Ruinn 2017) for shift-invariant kernels to general kernels. Besides the shift- invariant kernels, important examples of the RF kernels include the inner-product (Kar & Karnick
2012), and the homogeneous additive kernels (Vedaldi & Zisserman 2012).
4

---

Published as a conference paper at ICLR 2022
Algorithm 1 Approximation: Local Kernel Estimation
1: Initialize: Distribution p(w) over space (S2, p) and mapping < : x Q + R (see Section 3.1
2: for m E [M]] do
3: Draw P Pi..dd random variables wi E IRd with wi ~ p(w) for 1, 1....
4: Compute ((am w)) Vi E Nm and e [P]
5:
Construct the matrix Am E P with the (i, element as ((am (W)))
6: Communicate Am to every other agent and receive An, with m o m from other agents
7: If GIP is used, and data is not normalized, then communicate ||=((] [| Vi N
8: Estimate the kernel matrix Kp locally using 7 for the GIP and for the RF kernel
9:
end for
Next, propose multi-agent approximation algorithm to effectively learn the GIP and the RF kernels at each agent, as well as the optimization algorithms to efficiently solve the learning problem. Our proposed algorithms will follow an approximation optimization strategy, where the agents first exchange some information so that they can locally approximate the full kernel matrix K; then they can independently optimize the resulting approximated local problems. Below we list number of key design issues arising from implementing such an approximation optimization strategy:
[Kernel approximation] How to accurately approximate the kernel K, locally at each agent? For example, for the GIP kernels, how to accurately estimate the angles ( ( at a given agent m, where j Nm and m * m? This is challenging, especially when raw data sharing is not allowed.
[Effective exchange of local information] How shall we design appropriate messages to be ex- changed among the agents? The type of messages that gets exchanged will be dependent on the underlying kernel approximation schemes. Therefore, it is critical that proposed approximation methods are able to utilize little information from other agents as possible.
[[terative or one-shot scheme] It is not clear if such an approximation optimization scheme should be one-shol or iterative that is, whether it is favourable that the agents iteratively share information and perform local optimization (similar to classical consensus-based algorithms), or they should do just once. Again, this will dependent on the underlying information sharing schemes.
Next, we will formally introduce the proposed algorithms. Our presentation follows the approxi- mation - optimization strategy outlined above. We first discuss the proposed decentralized kernel approximation algorithm, followed by two different ways of performing decentralized optimization.
3.1 MULTI-AGENT KERNEL APPROXIMATION
The kernel K is approximated locally at each agent using Algorithm D Note that in Step 3, each agent randomly samples {wi ).f from distribution p(w). This can be easily established via random seed sharing as Xu et al. (2020): Richards et al. (2020). constructed matrix Am of size P x n. whose elements (( (8) ; w;) will be defined shortly. The choices of p(w) and <(--)) in Step depend on the choice of kernel. Specifically, we have:
Step 6, each agent shares a locally
AAprroxmmation for GIP kernel] For the GIP kernel, we first assume that the feature vectors normalized (Pedregosa et al. 201 We then choose p(w) to be any circularly symmetric distribu- tion. for simplicity we choose p(w) (0, Ia). Moreover, we use ((2, w) 1 [w' 0] such that
Am is a binary matrix with entries (0, 1}. Note that such matrices are easy to communicate. Next,
approximate the kernel K with K as
(1x (1) ()) xo (2(2)))
(1) ()) = g(bp(xx00 1)) || Il. 1.11=%/11 ID),
Vi E Nm. Vm [M] and Vj E Nm and Vm. E [M] are the individual elements of K and Kr, resp., and (lr(a
where k( ) and kp( 2
(0) (.0 an approximation of the angle
vb (a (6) ()) evaluated using An, Am as
(1 x(/² (2(((()) xm
1--27(A ( (A 1/P
(8)
5

---

Published as a conference paper at ICLR 2022
Algorithm 2 Optimization: One-Shot Communication for Kernel Learning
1: Initialize: a,,, E step-sizes (nm)e
yTm at each agent m E [M]
2: for m [M] do
3: Using Algorithm construct Kpp
4: Communicate Fm = [ym ...... ymm R
5: Using Kp and Vm construct Cp(a) (ef. (10) locally using Pm,p(a)
6:
Option I: Solve 10 exactly at each agent
7:
Option II: Solve for to Tm
inxxactly using GD at each agent
8:
9:
GD Update: (+1 a VRp(a
10:
end for
11: end for
12:
Return: T for all m [M]
This implies that K can be approximated for the GIP kerne by communicating only nP bits of information per agent. Note that in the general case if the feature vectors are not normalized, then M can be evaluated by communicating additional n real values of the norms of the feature vectors by each agent; see Step 7 in Algorithm
[Approximation for RF kernel] For the RF kernel, we choose ((---) = ((t--) and p(w) q(w) as defined in and approximate with Kp as
k(Em (1) s kp 2 (0p (p()")))))))))
(9)
where k(rm ()) and (x (i) 2l are elements of K and Kp, resp., op ( I/VP|A(")
and (p(a))) (1) = /////(///// (1.))) Note that can approximated for the RF kernel by sharing only nP real values per agent. Further, the distribution g(w) and the mapping ((..)) depend the type of RF kernel used. For example, for shift-invariant kernels with random Fourier features, we can choose ((z,w) = /2 cos(w" + b) with w q(w) and b ([0 2T] (Rahimi & Recht 2008).
Now that using Algorithm y we have approximated the kernel matrix at all the agents, we ready to solve 3 approximately.
3.2 THE DECENTRALIZER OPTIMIZATION STEP
The approximated kernel regression problem
with Kp obtained using Algorithm and local
loss (m,p(a): = EiENin {[Kpa]] 3m is
(i)
min (erla)=L((rn + ~ GERN
M Σ (a) + aall 2 "aalkk M m==1
>
(10)
Remark For the approximate problem TOP. we would want Kp constructed using the multi-agent kernel approximation approach to be positive semi-definie (PSD), i.e., the kernel function kp(:)) a positive definite (PD) kernel. From the definition of the approximate RF kernel p it is easy to verify that it is PD. However, it is not clear if the approximated GIP kernel is PD. Certainly, for the GIP kernel we expect that as P - oo we have Kp - K, i.e., asymptotically K PSD, since K introduce sufficient condition (Assumption 66) that ensures Ky to be
PSD. In the Appendix, PSD for the GIP kernel. In the following, for simplicity we assume Kp p is PSD.
Decentralized optimization based on one-shot communication: In this setting, we share the in- formation among all the agents one-shot, then each agent learns its corresponding minimizer using the gathered information. We assume that each agent can communicate with every other agent either in a decentralized manner (or via a central server) before initialization. This a common assumption in distributed learning with RF kernels where the agents need to share random seeds before initialization to determine the approximate feature mapping (Richards et al. 2020 Xu et al. 2020). Here, consensus is not enforced as each agent can learn a local minimizer which has good global property. The label information also exchanged among all the agents. In Algorithm 2 we list the steps of the algorithm. In Step 3, the agents learn K,p (the local estimate of the kernel matrix)

---

Published as a conference paper at ICLR 2022
using Algorithm In Step 4, the agents share the labels ym so that each agent (approximately) reconstruct the loss [(aa) (ef. 110 locally. Then each agent either choose Option I Option II to solve 10 A few important properties of Algorithm 2 are:
[Communication] Each agent communicates a total of O(nP) (NN)/M) bits (if the norms also need to be transmitted, then with an additional N/M real values) for the GIP kernel, and O/NP/M) real values for the RF kernels. Importantl, for the GIP kernel the communication is independent of the parameter dimension, making it suitable for decentralized overparameterized learning problems; see Table I for a comparison with other approaches.
[No consensus needed] Each agent executes Algorithm@inderr iiddependently to learn Om, without need- ing reach any kind of consensus. They are free choose different initializations, step-sizes, and even regularizers (i.e., À in [O). In contrast to the classical learning, where algorithms are designed
to guarantee consensus (Koppel al., 2018 Richards al. 2020 Xu et al. 2020), our algorithms allow each agent to learn a different function.
The proposed framework relies on sharing matrices Am 's that are random functions of the local features. Note that problem (T)) can also be solved by using an iterative distributed gradient tracking algorithm (Qu & 2018), with the benefit that no label sharing is needed; see Appendix D
Remark 4 (Optimization performance). Note that using Algorithm 2 we can solve the approximate problem (TOp arbitrary accuracy using either Option or Option II. However, it is
means will be close to the solution of (3). Therefore, after
clear if the solution obtained by Algorithm P problem (TOp is solved, it is important understand how close the solutions returned by Algorithm 2 are to the original kernel regression problem
MAIN RESULTS
In this section, we analyze the performance of Algorithm Specifically, we are interested in un- derstanding the training loss and the generalization error incurred due to the kernel approximation (ef. Algorithm|] I. For this purpose, we focus on &g loss functions for which the kernel regression problem 10 can be solved in closed-form. Specifically, we want to minimize the loss:
1 - (E -) 2
C(F)
(11)
We solve the following kernel ridge regression problem with the choice L(a) = 2N
Kall?,
{R((a=
1 2N 2N Kxrl2 + [
min aER
(12)
where we denote 7 = ..... VM E EN with Im = Iym 3m ym 1n E R". The above problem can be solved in closed form with â" [K + NN.NN. . 17-18. The approximated problem at each agent with the kernel Kp and with the loss function Lp(a) = 2
llū K i
min CERN
{ (R((a)=
2N 1l
1
Kpall 1|2 [|aa|
(13)
with the optimal solution returned by Option in Algorithm as a [Kp +
X- 11-1-- The Specifically,
goal is to analyze the impact of the approximation on the performance of Algorithm 2 we bound the difference between the optimal losses of the exact and the approximated Kernel ridge regression. We begin with some assumptions.
Assumption 1. We assume |xx2, x')l < x² and [kp(a, S R² for some 2 1.
Assumption 2. The function g(-) in 5 used to construct the GIP kernel is G-Lipschitz w.r.t. di i..,, 3G 2 such that: 1g(#, 22, 23) g( ( 22, 23)1 s Glyl R1 Vo, E [0, m] and V22, 23 E RR Assumption 3. We assume that the data labels [y] < R almost surely for some > 0.
Assumption 4. There exists fre E such that [(fx) infaeæ C(h).
A few remarks are in order. Note that Assumptions and 4 are standard in the statistical learning
theory (Cucker Zhou 2007] Caponnetto & De Vito. 2007| Ben- Hur & Weston 2010 Rudi & Rosasco 2017). Moreover, for RF kerne Assumption automatically satisfied [(x, w) S
7

---

Published as a conference paper at ICLR 2022
almost surely (uudi & Rosasco 2017 (cf. and Assumption 2 is required for estimating the kernel by approximating the pairwise angles between feature vectors. It is easy to verify that the popular kernels including, NTK (15). Arccosine, Gaussian and Polynomial kernels satisfy Assump- tion 2 with feature vectors belonging to a compact domain (this ensures that the Lipschitz constant G' is independent of the feature vector norms). Now we ready present the results.
We analyze how well Algorithm | approximates the exact kernel. We are interested in the approxi- mation error function of the number of random samples P. We have the following lemma.
Lemma 4.1 (Kerel Approximation), For Kp returned by Algorithm 7
the following holds with
probability at least 1 8: (i) For the GIP kernel, 1K-Kpll S G. (v
32x² log
2N
8
log 2N
3F
(ii) Similarly, for the RF kernel, || - [K- - N2N
(v 8 log 2N à
+ 4 log 2
3F
Note that as P increases Kp - K, in particular, to achieve an approximation error of >> O.
we need P = 3) Importantly Lemma 4.1 plays a crucial role in analyzing the optimization performance of the kernel approximation approach. Next, we state the training loss incurred a
consequence of solving the approximate decentralized problem (33 in Seoorithm@inster of (22)
2N, Theorem 4.2 (Approximation: Optimal Loss). Suppose P 2 log & then for both the GIP and the RF kernels, the solution returned by Algorithm (Option for solving (22 approximately (i.e, satisfies the following with probability at least 5
13
(Cp(ap)-L(aa) - =0("))=((()
=o
1. log P
2N 8 and [Rp(aş) -((---(((()) s
=0)l==(((v) (V log 22 8
Theorem states that as P increases, the optimal training loss achieved by solving approximate problem S via Algorithm 2 (Option I) will approach the performance of the centralized system
(12 for both the GIP and the RF kernels. The proof of the above result utilizes Lemma 4.1 and the
definition of the loss functions in 12 and (13)
See Appendix for detailed proof.
The results of Lemma 4.1 and Theorem 4.2 characterize the approximation performance of the proposed approximation optimization framework fixed number of training samples. Of course, it is of interest to analyze how the proposed approximation algorithms will perform on unseen test data. Towards this end, it is essential to analyze the performance of the function fp learned from solving 13 via Algorithm We have the following result.
Theorem 4.3 (Generalization performance). Let us choose À = L/VN, = (0, and N 2 512m2G2 28877 log 3o for 16
max K 72x2 /N log 32 }. also choose P> max 8, ||K
the GIP kernel and P P max {8K2,
32x² TKT 72k² VN) blog 1/8 for the RF kernel, where K is defined in Appendix F Then with probability at least - 6, we have for fr returned by Algorithm
(Option for approximately solving
12 (i.e. 13 J: L(fp) infrEM [(h) (1/VN).
3 utilizes a result similar to Lemma 4.1 but for integral operator defined using kernels k(--) and k)) Theorem 4.3 states that with appropriate choice of X (the regu- larization parameter), N (the number of overall samples), and P (the messages communicated per agent). the proposed algorithm achieves the minimax optimal generalization performance (Capon- netto & De Vitol 2007 Also, note that the the requirement of P O(VN) for the RF kernel compared to P O(N) for the GIP kernel is due to the particular structure of the RF kernel (cf. (6). It can be seen from Lemmas H.4 and H.5 Appendix H that the approximation obtained with the RF kernel allows the derivation of tighter bounds compared to the GIP kernel. The next corollary precisely states the total communication required per agent to achieve this optimal performance.
The proof of Theorem
Hnd
Corollary 1 (Communication requirements for the GIP and RF kernels). Suppose Algorithm 2 Quses the choice of parameters stated in Theorem 4.3 to approximately optimize (2). Then it requires total of O(22 /M) bits (resp. ONN /M) real values) of message exchanges per node when the GIP kernel (resp. the RF kernel) is used, to achieve minimax optimal generalization performance. Moreover, if unnormalized feature vectors are used, then the GIP kernel requires an additional O(N/M) real values of message exchanges per node.
Compared to DKRR-RF RF-CM (Liu et al. 202T). Decentralized RF (Richards et al. 2020). DKLA, and COKE Xu al. 2020 the number of message exchanges required by the proposed algorithm
8

---

Published as a conference paper at ICLR 2022
Table Total communication (in bits) per node required to achieve a fixed MSF (x10 performance.
Communication (bits)
Algorithm
P = 100
P' 500
P' 1000
DKRR SERR--FF-CEE RF-CM Liu et al. 2021)
25, 600
640, 000
896, 000
DecentralizedRF (Richards ct al. 2020
57, 600
352,000
500,000 000
DKLA (Xu et al.
2020
44, 800
288, 000
448, 000
Algorithm 2 [Our Paper)
22, 800
62, 800
112, 800
Target MSE (x10**
24.36
20.93
19.25
Table Comparison of MSE for fixed communication budget.
MSE (x10-3)
Algorithm
P = 100
P P= 500
P P= 1000
DKRR-RF-CM Liu et al. 2021)
35.30
50.51
67.48
DecentralizedRI (Richards et al. 2020
39.12
43.37
15.77
DKLA (Xu 2020
35.89
43.87
44.73
Algorithm (Our Paper)
24.36
20.93
19.25
Communication Budget (bits)
22, 800
62, 800
112, 800
is independent of the iteration numbers, and it much less compared to other algorithms, especially for the GIP kernel in the overparameterized regime; see Table for detailed comparisons.
5 EXPERIMENTS
We compare the performance of the proposed algorithm to OKRR-RF-CK. Liu et al. 202T). De- centralized RF (Richards et al. 2020), and DKLA (Xu et al. 2020 We evaluate the performance of all the algorithms on real world datasets from the UCI repository.
Specifically, we present the results on National Advisory Committee for Aeronautics (NACA) airfoil noise dataset (Lau & López, 2009), where the goal is to predict aircraft noise based on few mea- sured attributes. The dataset consists of
1503 samples that are split equally among M = 10 nodes. Each node utilizes 70% of its data for training and 30% for testing purposes. Each feature vector Zim E R.S represents the measured attributes such as, frequency, angle, etc., and each la- bel ymm represents the noise level. Additional experiments on different datasets and classification problems, as well as the detailed parameter settings, are included in the Appendix
We evaluate the performance of all the algorithms with the Gaussian kernel. Note that the algo- rithms DKRR-RF-CH Decentralized RF, and DKLA can only be implemented using the RF ap- proach while our proposed algorithm utilizes the GIP kernel. Also, in contrast to these benchmark algorithms that use iterative parameter exchange, the proposed Algorithm jsess only one-shot com- munication. First, in Table 2 we compare the communication required by each algorithm with the Gaussian kernel for P = 100, 500, and 1000 to achieve the same test mean squared error (MSE) for each setting, see last row of Table 2 Note that for P 100, the communication required by Algo- rithm is less than 50% of that required by DKLA and Decentralized RF while it is only slightly less than that of DKRR-RF-CM. Moreover, as P increases to 500 and 1000, it can be Algorithm D demonstrates the utility of the proposed algorithms for per-pparaeterrieed learning problems. In 3 we compare the averaged MSE achievable by different algorithms, when fixed total com- munication budget (in bits) is given for each setting (see the last row of Table for the budget). Note that Algorithm significantly outperforms all the other methods as P increases. This is expected since Algorithm
that only requires a fraction of communication compared to other algorithms, and this fact
Table
2 essentially solves a centralized problem (cf. Problem (T)) after the multi-agent kernel approximation (cf. Algorithm D.. and large P provides a better approximation of the kernel (cf. Lemma T. contrast, for the parameter sharing based algorithms the performance deterio- rates even though the kernel approximation improves with large P. learning nigh-dimensiooal parameter naturally requires more communication rounds as well as a higher communication budget per communication round.
Please note that we also compare the performance of Algorithm 2 with the benchmarking algo- rithms discussed above for the NTK. We further benchmark the performance of Algorithm 2 against the centralized algorithms for the Gaussian, the Polynomial, and the NTK. However, due to space limitations, we relegate these numerical results to the Appendix

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their valuable comments and suggestions. The work of Prashant Khanduri and Mingyi Hong is supported in part by NSF grant CMMII-727777, AFOSR grant 19RT0424, ARO grant W911NF-19-1-0247 and Meta research award on "Mathematical mod- eling and optimization for large-scale distributed systems". The work of Mingyi Hong is also supported by an IBM Faculty Research award. The work of Jia Liu is supported in part by NSF grants CAREER CNS-2110259, CNS-2112471, CNS-2102233, CCF-2110252, ECCS-2140277, and Google Faculty Research Award. The work of Hoi-To Wai was supported by CUHK Direct Grant #4055113.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effcieen sgd via gradient quantization and encoding. Advances in Neural In- formation Processing Systems, 30: 7091700-,7 2017.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Wallach, H. Larochelle, A. Beygelz- imer, F. d Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. In International Conference on Learning Representations, 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical birs-variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 15854,, 2019.
Asa Ben-Hur and Jason Weston. A user's guide to support vector machines. Data mining tech- niques for the life sciences, pp. 223-239. Springer, 2010.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. International Conference on Machine Learning, pp. 560-569. PMLR, 2018
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. Wallach, H. Larochelle, A. Beygelzimer, F. d. Alché-Buc, F. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Pantelis Bouboulis, Symeon Chouvardas, and Sergios Theodoridis. Online distributed learning over networks in rkh spaces using random fourier features. IEEE Transactions on Signal Processing, 66(7):1920-1932. 2017. 2017.
Luis M Candanedo, Véronique Feldheim, and Dominique Deramaix. Data driven prediction models of energy use of appliances in low-energy house. Energy and buildings, 140:81-97, 2017.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):311-36,, 2007.
Xiangyu Chang, Shaobo Lin, and Yao Wang. Divide and conquer local average regression, 2016.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d. Alché-Buc. E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Youngmin Cho. Kernel methods for deep learning. University of California, San Diego, 2012.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Y. Bengio, D. Schuur- mans, J. Lafferty, C. Williams, and A. Culotta (eds.). Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
10

---

Published as a conference paper at ICLR 2022
Symeon Chouvardas and Moez Draief. A diffusion kernel Ims algorithm for nonlinear adaptive networks. In 2016 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4164-4168. IEEE, 2016.
Felipe Cucker and Ding Xuan Zhou, Learning theory: an approximation theory viewpoint, vol- ume 24, Cambridge University Press, 2007.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint arXiv:2101.0380 2021.
Manuel Fernnddez-Delgddo Eva Cernadas, Senén Barro, and Dinani Amorim. Do need hun- dreds of classifiers to solve real world classification problems? The journal of machine learning research, 15(():3133-3181 2014.
Wei Gao, Jie Chen, Cédric Richard, and Jianguo Huang. Diffusion adaptation over networks with kernel -qasue. In 2015 IEEE 6th International Workshop Computational Advances in Multi-Sensen Adaptive Processing (CAMSAP), pp. 217-220, 2015. doi: 10.1109/CAMSAP. 2015.7383775.
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the laplace and neural tangent kernels. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, Curran Associates, Inc., 2020.
volume 33, pp. 1451-1461.
Zheng-Chi Chu Guo, Shao-Bo Lin, and Ding- Xuan Zhou. Learning theory of distributed spectral algo- rithms. Inverse Problems, 33(7):074009, 2017.
Insu Han, Haim Avron, Neta Shoham, Chaewon Kim, and Jinwoo Shin. Random features for the neural tangent kernel. arXiv preprint arXiv:2104.01351, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola. Kernel methods in machine learn- ing. The annals of statistics, 36(3):1171-12) 2008.
Ting Hu, Qiang Wu, and Ding-Xunt Xuag Zhou. Distributed kemel gradient descent algorithm for min- imum error entropy principle. Applied and Computational Harmonic Analysis, 49(1):229-256, 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Purushottam Kar and Harish Karnick. Random feature maps for dot product kernels. Artificial intelligence and statistics, pp. 583-591. PMLR, 2012.
Alec Koppel, Santiago Paternain, Cédric Richard, and Alejandro Ribeiro. Decentralized online learning with kernels. IEEE Transactions Signal Processing, 66(12):3240-3255 2018.
Kevin Lau and Roberto López. A neural networks approach to aerofoil noise prediction. Tech. Report, 2009.
Zhu Li, Jean- Francoiss Ton, Dino Oglic, and Dino Sejdinovic. Towards unified analysis of random fourier features. In International Conference on Machine Learning, pp. 3905-3914, PMLR, 2019.
Shao-Bo Lin, Xin Guo, and Ding-Xuan Zhou. Distributed learning with regularized least squares.
The Journal of Machine Learning Research, 18(1):3202-3232. 2017.
Shao-Bo Bo Lin, Di Wang, and Ding Xuan Zhou. Distributed kernel ridge regression with communi- cations. J. Mach. Learn. Res., 21:93-1, 2020.

---

Published as a conference paper at ICLR 2022
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini- mini-batches, use local sgd, 2018.
Yong Liu, Jiankun Liu, and Shuqiang Wang. Effective distributed learning with random features: Improved bounds and algorithms. In International Conference on Learning Representations, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efice learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273 1273-1282. PMLR, 2017.
Nicole Mücke and Gilles Blanchard. Parallelizing spectrally regularized kernel algorithms. The Journal of Machine Learning Research, 190)):1069-1997 2018.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer
Science & Business Media, 2003.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Courapeea, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning Python. Journal of Machine Learning Research, 002222-28300 2011.
Hrusikesha Pradhan, Amrit Singh Bedi, Alec Koppel, and Ketan Rajawat. Adaptive kernel learn- ing in heterogeneous networks. IEEE Trunsuctions on Signal and Information Processing over Networks, 2021.
Joel B Predd, Sanjeev R Kulkarni, and H Vincent Poor. Distributed kemnel regression: An algorithm for training collaboratively. In 2006 JEEE Information Theory Workshop-ITW'06 Punta del Este, pp. 332-336. IEEE, 2006.
Guannan Qu and Na Li. Harnessing smoothness accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 5(3): 1260, 2018. doi: 10.1 10.110/9/CS 2698261.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008.
Dominic Richards, Patrick Rebeschini, and Lorenzo Rosasco. Decentralised learning with random features and distributed gradient descent. In International Conference Machine Learning, pp- 8105-8115 15. PMLR, 2020.
Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In NIPS. pp. 3215-3225, 2017.
Walter Rudin. Fourier unalysis on groups. Courier Dover Publications, 2017.
Bernhard Schölkopf, Alexander Smola, Francis Bach, al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to lata-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association. Citeseer, 2014.
Wei Shi, Qing Ling, Kun Yuan, Gang Wu, and Wotao Yin. On the linear convergence the admm in decentralized consensus optimization. IEEE Transactions on Signal Processing, 62(7):1750- 1761, 2014.
Ban-Sok Shin, Henning Paul, and Armin Dekorsy. Distributed kernel least squares for nonlinear regression applied to sensor networks. In 2016 24th European Signal Processing Conference (EUSIPCO), pp. 1588-1592. IEEE, 2016.
Sebastian U Stich. Local sgd converges fast and communicates little. 2018.
arXiv preprint
12

---

Published as a conference paper at ICLR 2022
Joel A Tropp. User-friendly tools for random matrices: An introduction. Technical report, California Institute Of Technology Pasadena Div Of Engineering and Applied Science, 2012.
John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Andrea Vedaldi and Andrew Zisserman. Efficient additive kernels via explicit feature maps. IEEE transactions on pattern analysis and machine intelligence, 34(3)480-492 2012.
Lean-Philippe Vert, Koji Tsuda, and Bernhard Schölkopf. A primer kernel methods. Kernel
methods in computational biology, 47:35-70, 2004.
Ping Xu, Yue Wang, Xiang Chen, and Tian Zhi. Coke: Communication-consored kernel learning decentralized non-parametric learning. arXiv preprint urXiv:2001.10133 2020.
Yuchen Zhang, John Duchi, and Martin Wainwright. Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates. The Journal of Machine Learning Research, 16( 0113999333440 2015.
13


Reviews:
[{"review_id": "drfsssxuLgC", "reviewer": "Reviewer_MEfo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I find it difficult to position this paper in the existing literature on distributed kernel learning. \n\nFor 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. \n\nI would consider changing my scores if the authors could clarify the major contribution in this paper.\n\n----\n\n**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_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.\n\nThe 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.", "summary_of_the_review": "Some detailed comments:\n\n* 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).\n* 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)?", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NkcuTzMWnGz", "reviewer": "Reviewer_gN2n", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "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.\n\nOne 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.\n\nIs 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. \n\nIn 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.\n\nIn 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.\n\nAlong 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.\n\n\nMinor comments:\n\n ``However this approach raises privacy concerns, thus almost never being used in practice.\" Is awkward syntax. Consider rephrasing.\n\nAlso, the main boldface question at the top of page 2 is a sentence fragment.\n\nThe statement \"where the first one only needs one-shot information exchange, but requires\nsharing data labels among the agents; the second one needs iterative information exchange, but does\nnot 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.\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FyTIj2LDrkH", "reviewer": "Reviewer_ut1q", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n1. The paper is clearly written. The contents are well organized and easy to follow. \n\n2. 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.\n\nWeaknesses\n\n1. 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.\n\n\nMinor: \n\nAbove Eqn. (5) duplicate ''as''\n\nBelow Eqn. (3) '' ... represent (m . i)th element of vector [K \\alpha] .. '' redundant to the notation section\n\nPage 5 ''will dependent on the underlying kernel approximation schemes'' -> ''will be dependent ...''\n\n\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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)