Year: 2021

Abstract:
This work develops a novel framework for communication-efficient distributed learning where the models to be learnt 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 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 or parameters. The proposed framework is a significant 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 `2 loss. We show that with M agents and N total samples, when certain generalized inner-product (GIP) kernels (resp. the random features (RF) kernel) are used, each agent needs to communicate O ( N/M ) bits (resp. O ( N √ N/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-art algorithms, for distributedly training models to fit UCI benchmarking datasets. Moreover, each agent needs to share about 200N/M bits to closely match the performance of the centralized algorithms, and these numbers are independent of parameter and feature dimension.

text: ( N2/M ) bits (resp. O ( N √ N/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-art algorithms, for distributedly training models to fit UCI benchmarking datasets. Moreover, each agent needs to share about 200N/M bits to closely match the performance of the centralized algorithms, and these numbers are independent of parameter and feature dimension.

heading: 1 INTRODUCTION
text: Recently, decentralized optimization has become a mainstay of the optimization research. In decentralized 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 parameters 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 et al., 2017; Fedus et al., 2021) poses a significant challenge to such parameter sharing approaches, mainly because sharing model parameters iteratively becomes excessively expensive as 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 approach raises privacy concerns, and it is rarely used in practice. Therefore, a fundamental question of decentralized learning in the overparameterized regime is:
(Q) For overparameterized learning problems, how to design decentralized algorithms that achieve the best optimization/generalization performance by exchanging minimum amount of information?
We partially answer (Q) in the context of distributed kernel learning (Vert et al., 2004). We depart from the popular consensus-based algorithms and propose an 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 an elegant way to model non-linear learning problems with complex data dependencies as simple linear problems (Vert et al., 2004; Hofmann et al., 2008), and (ii) kernelbased methods can be used to capture the behavior of a fully-trained deep network with large width (Jacot et al., 2018; Arora et al., 2019; 2020).
Table 1: Comparison of the total communication required per node by different algorithms for non-overparameterized (NOP) and overparameterized (OP) regimes. Please see Appendix B for a detailed discussion 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, β ≥ 2 is a constant, and T denotes the total communication (iterations) rounds utilized by the distributed algorithms.
Algorithm Kernel UB on M Communication (Real Values)NOP OP
DKRR-CM (Lin et al., 2020) Any O ( N T+1 2(T+2) ) dTN dTN
DKRR-RF-CM (Liu et al., 2021) RF O ( N T+1 2(T+2) ) O(T √ N) O(TNβ) Decentralized-RF (Richards et al., 2020) RF O(N 1 3 ) O(T √ N) O(TNβ) DKLA/COKE (Xu et al., 2020) RF Any M T √ N O(TNβ)
RF N √ N M O ( N1+β M ) Algorithm 2 (this work) GIP Any M O ( N2
M
) O ( N2
M ) Distributed implementation of kernel learning problems is challenging. Current state-of-the-art algorithms for kernel learning either rely on sharing raw data among agents and/or imposing restrictions on the number of agents (Zhang et al., 2015; Lin et al., 2017; Koppel et al., 2018; Lin et al., 2020; Hu et al., 2020; Pradhan et al., 2021; Predd et al., 2006). 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 (potentially high-dimensional) parameters (Bouboulis et al., 2017; Richards et al., 2020; Xu et al., 2020; Liu et al., 2021)1. 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 O(Nβ), β ≥ 2, random features (parameter dimension) using ReLU activation (Arora et al., 2019; Han et al., 2021)2. For such problems, in this work, we propose a novel algorithmic framework for decentralized kernel learning. Below, we list the major contributions of our work.
[GIP Kernel for Distributed Approximation] We define a new class of kernels suitable for distributed implementation, Generalized inner-product (GIP) kernel, that is fully characterized by the angle between a pair of feature vectors and their respective norms. Many kernels of practical importance including the NTK can be represented as GIP kernel. Further, we propose a 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 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. A key feature of these algorithms is 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 generalization performance of the proposed approximation algorithms for `2 loss. We show that GIP kernel requires communicating O(N2/M) bits and the RF kernel requires communicating O(N √ N/M) real values per agent to achieve minimax optimal generalization performance. Importantly, the required communication is independent of the function class and the optimization algorithm. We validate the performance of our approximation algorithms on UCI benchmarking datasets.
In Table 1, we compare the communication requirements of the proposed approach to popular distributed 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 outperforms other algorithms in both non-overparameterized 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 multiagent-kernel-approximation, it does not impose any upper bounds on the number of machines in the network.
Notations: We use R, Rd, and Rn×m to denote the sets of real numbers, d-dimensional Euclidean space, and real matrices of size n×m, respectively. We use N to denote the set of natural numbers.
1For a detailed literature review please see Appendix B. 2To achieve approximation error = O(1/ √ N).
N (0,Σ) is multivariate normal distribution with zero mean and covariance Σ. Uniform distribution with support [a, b] is denoted by U [a, b]. 〈a, b〉 (resp. 〈a, b〉H) denotes the inner-product in Euclidean space (resp. Hilbert space H). The inner-product defines the usual norms in corresponding spaces. Norm ‖A‖ of matrix A denotes the operator norm induced by `2 vector norm. We denote by [a]i or [a](i) the ith element of a vector a. [A · a](i)j denotes the (i · j)th element of vector A · a. Moreover, A(:,i) is the ith column of A and [A]mk is the element corresponding to mth row and kth column. Notation m ∈ [M ] denotes m ∈ {1, ..,M}. Finally, 1[E] is the indicator function of event E.

heading: 2 PROBLEM STATEMENT
text: Given a probability distribution π(x, y) over X × R, we want to minimize the population loss
L(f) = Ex,y∼π(x,y)[`(f(x), y)], (1)
where x ∈ X ⊂ Rd and y ∈ R denote the features and the labels, respectively. Here, f : X → R is an estimate of the true label y. We consider a distributed system of M agents, with each agent m ∈ [M ] having access to a locally available independently and identically distributed (i.i.d) dataset Nm = {x(i)m , y(i)m }ni=1 with3 (x (i) m , y (i) m ) ∼ π(x, y). The total number of samples is N = nM . The goal of kernel learning with kernel function, k(·, ·) : X × X → R, is to find a function f ∈ H (whereH is the reproducing kernel Hilbert space (RKHS) associated with k (Vert et al., 2004)) that minimizes (1). We aim to solve the following (decentralized) empirical risk minimization problem
min f∈H
{ R̂(f) = L̂(f) + λ
2 ‖f‖2H =
1
M M∑ m=1 L̂m(f) + λ 2 ‖f‖2H } , (2)
where λ > 0 is the regularization parameter and L̂m(f) = 1n ∑ i∈Nm `(f(x (i) m ), y (i) m ) is the local loss at each m ∈ [M ]. Problem (2) can be reformulated using the Representer theorem (Schölkopf et al., 2002) with L̂m(α) = 1n ∑ i∈Nm ` ([ Kα ](i) m , y (i) m ) , ∀m ∈ [M ], as
min α∈RN
{ R̂(α) = L̂(α) + λ
2 ‖α‖2K =
1
M M∑ m=1 L̂m(α) + λ 2 ‖α‖2K } , (3)
where K ∈ RN×N is the kernel matrix with elements k(x(i)m , x(j)m̄ ), ∀m, m̄ ∈ [M ], ∀i ∈ Nm and ∀j ∈ Nm̄. The supervised (centralized) learning problem (3) is a classical problem in statistical learning (Caponnetto & De Vito, 2007) and has been popularized recently due to connections with overparameterized neural network training (Jacot et al., 2018; Arora et al., 2019). An alternate way to solve problem (2) (and (3)) is by parameterizing f in (2) by θ ∈ RD as fD(x; θ) = 〈θ, φD(x)〉 where φD : X → RD is a finite dimensional feature map. Here, φD(·) is designed to approximate k(·, ·) with kD(x, x′) = 〈φD(x), φD(x′)〉 (Rahimi & Recht, 2008). Using this approximation, problem (2) (and (3)) can be written in the parameter domain with L̂m,D(θ) = 1n ∑ i∈Nm ` ( 〈θ, φD(x(i)m )〉, y(i)m ) , ∀m ∈ [M ], as
min θ∈RD
{ R̂D(θ) = L̂D(θ) + λ
2 ‖θ‖2 = 1 M M∑ m=1 L̂m,D(θ) + λ 2 ‖θ‖2 } . (4)
Note that (4) is a D-dimensional problem, whereas (3) is an N -dimensional problem. Since (4) is in the standard finite-sum form, it can be solved using the standard parameter sharing decentralized optimization algorithms (e.g., DGD (Richards et al., 2020) or ADMM (Xu et al., 2020) ), which share D-dimensional vectors iteratively. However, when (4) is overparameterized with very large D (e.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 high-dimensional parameters is to directly solve (3). However, it is by no means clear if and how one can efficiently solve (3) in a decentralized manner. The key challenge is that, unlike the conventional decentralized learning problems, here each loss term `([Kα](i)m , y (i) m ) is not separable
3The techniques presented in this work can be easily extended to unbalanced datasets, i.e., when each agent has a dataset of different size.
over the agents. Instead, each agent m’s local problem is dependent on k(x(i)m , x (j) m̄ ) with m 6= m̄. Importantly, without directly transmitting the data itself (as has been done in Predd et al. (2006); Koppel et al. (2018); Lin et al. (2020)), it is not clear how one can obtain the required (m·i)th element of Kα. Therefore, to develop algorithms that avoid sharing high-dimensional parameters by directly (approximately) solving (3), it is important to identify kernels that are suitable for decentralized implementation and propose efficient algorithms for learning with such kernels.

heading: 3 THE PROPOSED ALGORITHMS
text: In this section, we define a general class of kernels referred to as the generalized inner product (GIP) kernels that are suitable for decentralized overparameterized learning. By focusing on GIP kernels, we aim to understand the best possible decentralized optimization/generalization performance that can be achieved for solving (3). Surprisingly, one of our proposed algorithm only shares O(nN) = O(N2/M) bits of information per node, while achieving the minimax optimal generalization 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 (4)); further, there is no requirement for achieving consensus among the agents. The proposed algorithm represents a 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. Definition 3.1. [Generalized inner-product (GIP) kernel] We define a GIP kernel as:
k(x, x′) = g(ψ(x, x′), ‖x‖, ‖x′‖), (5)
where ψ(x, x′) = arccos(xTx′/(‖x‖‖x′‖)) ∈ [0, π] denotes the angle between the feature vectors x and x′; and g(·, ‖x‖, ‖x′‖) is assumed to be Lipschitz continuous (cf. Assumption 2). Remark 1. Note that the GIP kernel is a generalization of the inner-product kernels (Schölkopf et al., 2002), i.e., kernels of the form k(x, x′) = k(〈x, x′〉). Clearly, k(〈x, x′〉) can be represented as k(〈x, x′〉) = g(ψ(x, x′), ‖x‖, ‖x′‖) for some function g(·). Moreover, many kernels of practical interest can be represented as GIP kernels, some examples include NTK (Jacot et al., 2018; Chizat et al., 2019; Arora et al., 2019), arccosine (Cho & Saul, 2009), polynimal, Gaussian, Laplacian, sigmoid, and inner-product kernels (Schölkopf et 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 a single hiddenlayer ReLU neural network: k(x, x′) = xTx′(π−ψ(x, x′))/2π (Chizat et al., 2019). This kernel can be fully learned with just the knowledge of norms and the pairwise angles of the feature vectors. For many applications of interest (Bietti & Mairal, 2019; Geifman 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 a kernel estimation procedure is independent of the problem’s parameter dimension (i.e., D in (4)), making them suitable for decentralized learning in overparameterized regime. Next, we define the RF kernel. Definition 3.2. [Random features (RF) kernel] RF kernel is defined as (Rahimi & Recht, 2008; Rudi & Rosasco, 2017; Li et al., 2019):
k(x, x′) = ∫ ω∈Ω ζ̄(x, ω) · ζ̄(x′, ω)dq(ω) (6)
with (Ω, q) being the probability space and ζ̄ : X × Ω→ R. Remark 2. The RF kernel can be approximated as: k(·, ·) ≈ kP (x, x′) = 〈φP (x), φP (x′)〉, with φP (x) = 1√P [ζ̄(x, ω1), . . . , ζ̄(x, ωP )]
T ∈ RP and {ωi}Pi=1 drawn i.i.d. from distribution q(ω). A popular example of the RF kernels is the shift-invariant kernels, i.e., kernels of the form k(x, x′) = k(x − x′) (Rahimi & Recht, 2008). The RF kernels generalize the random Fourier features construction (Rudin, 2017) for shift-invariant kernels to general kernels. Besides the shiftinvariant kernels, important examples of the RF kernels include the inner-product, and (Kar & Karnick, 2012), the homogeneous additive kernels (Vedaldi & Zisserman, 2012).
Algorithm 1 Approximation: Local Kernel Estimation 1: Initialize: Distribution p(ω) over space (Ω, p) and mapping ζ : X × Ω→ R (see Section 3.1) 2: for m ∈ [M ] do 3: Draw P i.i.d. random variables ωi ∈ Rd with ωi ∼ p(ω) for i = 1, . . . , P 4: Compute ζ(x(i)m , ωj) ∀i ∈ Nm and j ∈ [P ] 5: Construct the matrix Am ∈ RP×n with the (i, j)th element as ζ(x(i)m , ωj) 6: Communicate Am to every other agent and receive Am̄ with m̄ 6= m from other agents 7: If GIP is used, and data is not normalized, then communicate ‖x(i)m ‖, ∀ i ∈ Nm 8: Estimate the kernel matrix KP locally using (7) for the GIP and (9) for the RF kernel 9: end for
Next, we propose a 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 a 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 ψ(x(i)m , x (j) m̄ ) at a given agentm, where j ∈ Nm̄ and m̄ 6= 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 exchanged 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 as little information from other agents as possible.
[Iterative or one-shot scheme] It is not clear if such an approximation – optimization scheme should be one-shot 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 it just once. Again, this will be dependent on the underlying information sharing schemes.
Next, we will formally introduce the proposed algorithms. Our presentation follows the approximation – optimization strategy outlined above. We first discuss the proposed decentralized kernel approximation algorithm, followed by two different ways of performing decentralized optimization.

heading: 3.1 MULTI-AGENT KERNEL APPROXIMATION
text: The kernel K is approximated locally at each agent using Algorithm 1. Note that in Step 3, each agent randomly samples {ωi}Pi=1 from distribution p(ω). This can be easily established via random seed sharing as in Xu et al. (2020); Richards et al. (2020). In Step 6, each agent shares a locally constructed matrix Am of size P × n, whose elements ζ(x(i)m , ωi) will be defined shortly. The choices of p(ω) and ζ(·, ·) in Step 1 depend on the choice of kernel. Specifically, we have: [Approximation for GIP kernel] For the GIP kernel, we first assume that the feature vectors are normalized (Pedregosa et al., 2011). We then choose p(ω) to be any circularly symmetric distribution, for simplicity we choose p(ω) asN (0, Id). Moreover, we use ζ(x, ω) = 1[ωTx ≥ 0] such that Am is a binary matrix with entries {0, 1}. Note that such matrices are easy to communicate. Next, we approximate the kernel K with KP as
k(x(i)m , x (j) m̄ ) ≈ kP (x(i)m , x (j) m̄ ) = g(ψP (x (i) m , x (j) m̄ ), ‖x(i)m ‖, ‖x (j) m̄ ‖), (7)
where k(x(i)m , x (j) m̄ ) and kP (x (i) m , x (j) m̄ ) ∀i ∈ Nm, ∀m ∈ [M ] and ∀j ∈ Nm̄ and ∀m̄ ∈ [M ] are the individual elements of K and KP , resp., and ψP (x (i) m , x (j) m̄ ) is an approximation of the angle ψ(x (i) m , x (j) m̄ ) evaluated using Am, Am̄ as
ψ(x(i)m , x (j) m̄ ) ≈ ψP (x(i)m , x (j) m̄ ) = ∣∣∣π − 2π[A(:,i)m ]T [A(:,j)m̄ ]/P ∣∣∣ , (8)
Algorithm 2 Optimization: One-Shot Communication for Kernel Learning
1: Initialize: α1m ∈ RN , step-sizes {ηtm} Tm t=1 at each agent m ∈ [M ] 2: for m ∈ [M ] do 3: Using Algorithm 1 construct KP 4: Communicate ȳm = [y (1) m , . . . , y (n) m ]T ∈ Rn 5: Using KP and ȳm construct L̂P (α) (cf. (10)) locally using L̂m,P (α) 6: Option I: Solve (10) exactly at each agent 7: Option II: Solve (10) inexactly using GD at each agent 8: for t = 1 to Tm 9: GD Update: αt+1m = α t m − ηtm∇R̂P (αtm)
10: end for 11: end for 12: Return: αT+1m for all m ∈ [M ]
This implies that K can be approximated for the GIP kernel by communicating only nP bits of information per agent. Note that in the general case if the feature vectors are not normalized, then (7) can be evaluated by communicating additional n real values of the norms of the feature vectors by each agent; see Step 7 in Algorithm 1.
[Approximation for RF kernel] For the RF kernel, we choose ζ(·, ·) = ζ̄(·, ·) and p(ω) = q(ω) as defined in (6) and approximate K with KP as
k(x(i)m , x (j) m̄ ) ≈ kP (x(i)m , x (j) m̄ ) = 〈φP (x(i)m ), φP (x (j) m̄ )〉, (9)
where k(x(i)m , x (j) m̄ ) and kP (x (i) m , x (j) m̄ ) are elements of K and KP , resp., φP (x (i) m ) = 1/
√ P [A (:,i) m ]
and φP (x (j) m̄ ) = 1/
√ P [A
(:,j) m̄ ]. Note that K can be approximated for the RF kernel by sharing only
nP real values per agent. Further, the distribution q(ω) and the mapping ζ̄(·, ·) depend on the type of RF kernel used. For example, for shift-invariant kernels with random Fourier features, we can choose ζ̄(x, ω) = √ 2 cos(ωTx+ b) with ω ∼ q(ω) and b ∼ U [0, 2π] (Rahimi & Recht, 2008).
Now that using Algorithm 1 we have approximated the kernel matrix at all the agents, we are ready to solve (3) approximately.

heading: 3.2 THE DECENTRALIZED OPTIMIZATION STEP
text: The approximated kernel regression problem (3) with KP obtained using Algorithm 1, and local loss L̂m,P (α) := 1n ∑ i∈Nm ` ([ KPα ](i) m , y (i) m ) is
min α∈RN
{ R̂P (α) = L̂P (α) + λ
2 ‖α‖2KP =
1
M M∑ m=1 L̂m,P (α) + λ 2 ‖α‖2KP } . (10)
Remark 3. For the approximate problem (10), we would want KP constructed using the multi-agent kernel approximation approach to be positive semi-definite (PSD), i.e., the kernel function kP (·, ·) is a positive definite (PD) kernel. From the definition of the approximate RF kernel (9), 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 →∞ we have KP → K, i.e., asymptotically KP is PSD, since K is PSD. In the Appendix, we introduce a sufficient condition (Assumption 6) that ensures KP to be PSD for the GIP kernel. In the following, for simplicity we assume KP is PSD.
Decentralized optimization based on one-shot communication: In this setting, we share the information among all the agents in 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 is 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 a good global property. The label information is also exchanged among all the agents. In Algorithm 2, we list the steps of the algorithm. In Step 3, the agents learn KP (the local estimate of the kernel matrix)
using Algorithm 1. In Step 4, the agents share the labels ȳm so that each agent can (approximately) reconstruct the loss L̂(α) (cf. (10)) locally. Then each agent can either choose Option I or Option II to solve (10). A few important properties of Algorithm 2 are:
[Communication] Each agent communicates a total ofO(nP ) = O(NP/M) bits (if the norms also need to be transmitted, then with an additionalN/M real values) for the GIP kernel, andO(NP/M) real values for the RF kernels. Importantly, for the GIP kernel the communication is independent of the parameter dimension, making it suitable for decentralized overparameterized learning problems; see Table 1 for a comparison with other approaches.
[No consensus needed] Each agent executes Algorithm 2 independently to learn αm, without needing to reach any kind of consensus. They are free to choose different initializations, step-sizes, and even regularizers (i.e., λ in (10)). In contrast to the classical learning, where algorithms are designed to guarantee consensus (Koppel et al., 2018; Richards et 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 (10) can also be solved by using an iterative distributed gradient tracking algorithm (Qu & Li, 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 (10) to arbitrary accuracy using either Option I or Option II. However, it is by no means clear if the solution obtained by Algorithm 2 will be close to the solution of (3). Therefore, after problem (10) is solved, it is important to understand how close the solutions returned by Algorithm 2 are to the original kernel regression problem (3).

heading: 4 MAIN RESULTS
text: In this section, we analyze the performance of Algorithm 2. Specifically, we are interested in understanding the training loss and the generalization error incurred due to the kernel approximation (cf. Algorithm 1). For this purpose, we focus on `2 loss functions for which the kernel regression problem (10) can be solved in closed-form. Specifically, we want to minimize the loss:
L(f) = 1 2 Ex,y∼π(x,y)[(f(x)− y)2]. (11)
Then we solve the following kernel ridge regression problem with the choice L̂(α) = 12N ‖ȳ−Kα‖ 2,
min α∈RN
{ R̂(α) = 1
2N ‖ȳ −Kα‖2 + λ 2 ‖α‖2K
} (12)
where we denote ȳ = [ȳT1 , . . . , ȳ T M ] T ∈ RN with ȳm = [y(1)m , y(2)m , . . . , y(n)m ]T ∈ Rn. The above problem can be solved in closed form with α̂∗ = [K +N · λ · I]−1ȳ. The approximated problem at each agent with the kernel KP and with the loss function L̂P (α) = 12N ‖ȳ −KPα‖ 2 is
min α∈RN
{ R̂P (α) = 1
2N ‖ȳ −KPα‖2 +
λ 2 ‖α‖2KP
} (13)
with the optimal solution returned by Option I in Algorithm 2 as α̂∗P = [KP +N · λ · I]−1ȳ. The goal is to analyze the impact of the approximation on the performance of Algorithm 2. Specifically, 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 |k(x, x′)| ≤ κ2 and |kP (x, x′)| ≤ κ2 for some κ ≥ 1. Assumption 2. The function g(·) in (5) used to construct the GIP kernel is G-Lipschitz w.r.t. ψ, i.e., ∃G ≥ 0 such that: |g(ψ, z2, z3)− g(ψ̂, z2, z3)| ≤ G|ψ − ψ̂|, ∀ψ, ψ̂ ∈ [0, π] and ∀z2, z3 ∈ R. Assumption 3. We assume that the data labels |y| ≤ R almost surely for some R > 0. Assumption 4. There exists fH ∈ H such that L(fH) = infh∈H L(h).
A few remarks are in order. Note that Assumptions 1, 3 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 kernel Assumption 1 is automatically satisfied if |ζ(x, ω)| ≤ κ
almost surely (Rudi & Rosasco, 2017) (cf. (6) and (9)). 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 Assumption 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 are ready to present the results.
We analyze how well Algorithm 1 approximates the exact kernel. We are interested in the approximation error as a function of the number of random samples P . We have the following lemma. Lemma 4.1 (Kernel Approximation). For KP returned by Algorithm 1, the following holds with probability at least 1− δ: (i) For the GIP kernel, ‖K−KP ‖ ≤ GN (√ 32π2 P log 2N δ + 8π 3P log 2N δ ) .
(ii) Similarly, for the RF kernel, ‖K−KP ‖ ≤ κ2N (√ 8 P log 2N δ + 4 3P log 2N δ ) .
Note that as P increases KP → K, in particular, to achieve an approximation error of > 0, we need P = O( −2). 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 as a consequence of solving the approximate decentralized problem (13) in Algorithm 2 instead of (12). Theorem 4.2 (Approximation: Optimal Loss). Suppose P ≥ 29 log 2N δ , then for both the GIP and the RF kernels, the solution returned by Algorithm 2 (Option I) for solving (12) approximately (i.e, (13)), satisfies the following with probability at least 1− δ∣∣L̂P (α̂∗P )− L̂(α̂∗)∣∣ = O(√ 1P log 2Nδ ) and ∣∣R̂P (α̂∗P )− R̂(α̂∗)∣∣ ≤ O(√ 1P log 2Nδ ). Theorem 4.2 states that as P increases, the optimal training loss achieved by solving approximate problem (13) 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 G for a detailed proof.
The results of Lemma 4.1 and Theorem 4.2 characterize the approximation performance of the proposed approximation – optimization framework on 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 f̂P learned from solving (13) via Algorithm 2. We have the following result. Theorem 4.3 (Generalization performance). Let us choose λ = 1/ √ N , δ ∈ (0, 1), and N ≥
max {
4 3‖K‖2 , 72κ
2 √ N log 32κ 2 √ N
δ
} , also choose P ≥ max { 8, 512π 2G2
‖K‖2 , 288π 2G2N } log 16δ for
the GIP kernel and P ≥ max { 8κ2, 32κ 2 ‖K‖2 , 72κ 2 √ N } log 128κ 2 √ N δ for the RF kernel, where K is
defined in Appendix F. Then with probability at least 1− δ, we have for f̂P returned by Algorithm 2 (Option I) for approximately solving (12) (i.e., (13)): L(f̂P )− infh∈H L(h) = O ( 1/ √ N ) .
The proof of Theorem 4.3 utilizes a result similar to Lemma 4.1 but for integral operator defined using kernels k(·, ·) and kP (·, ·). Theorem 4.3 states that with appropriate choice of λ (the regularization parameter), N (the number of overall samples), and P (the messages communicated per agent), the proposed algorithm achieves the minimax optimal generalization performance (Caponnetto & De Vito, 2007). Also, note that the the requirement of P = O( √ N) 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 in 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. Corollary 1 (Communication requirements for the GIP and RF kernels). Suppose Algorithm 2 uses the choice of parameters stated in Theorem 4.3 to approximately optimize (12). Then it requires a total of O(N2/M) bits (resp. O(N √ N/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-CM (Liu et al., 2021), Decentralized RF (Richards et al., 2020), DKLA, and COKE (Xu et al., 2020), the number of message exchanges required by the proposed algorithm
is independent of the iteration numbers, and it is much less compared to other algorithms, especially for the GIP kernel in the overparameterized regime; see Table 1 for detailed comparisons.

heading: 5 EXPERIMENTS
text: We compare the performance of the proposed algorithm to DKRR-RF-CM (Liu et al., 2021), Decentralized 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 & López, 2009), where the goal is to predict aircraft noise based on a few measured attributes. The dataset consists of N = 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 x(i)m ∈ R5 represents the measured attributes such as, frequency, angle, etc., and each label y(i)m represents the noise level. Additional experiments on different datasets and classification problems, as well as the detailed parameter settings, are included in the Appendix A.
We evaluate the performance of all the algorithms with the Gaussian kernel. Note that the algorithms DKRR-RF-CM, Decentralized RF, and DKLA can only be implemented using the RF approach while our proposed algorithm utilizes the GIP kernel. Also, in contrast to these benchmark algorithms that use iterative parameter exchange, the proposed Algorithm 2 uses only one-shot communication. 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 Algorithm 2 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 seen that Algorithm 2 only requires a fraction of communication compared to other algorithms, and this fact demonstrates the utility of the proposed algorithms for over-parameterized learning problems. In Table 3, we compare the averaged MSE achievable by different algorithms, when a fixed total communication budget (in bits) is given for each setting (see the last row of Table 3 for the budget). Note that Algorithm 2 significantly outperforms all the other methods as P increases. This is expected since Algorithm 2 essentially solves a centralized problem (cf. Problem (10)) after the multi-agent kernel approximation (cf. Algorithm 1), and a large P provides a better approximation of the kernel (cf. Lemma 4.1). In contrast, for the parameter sharing based algorithms the performance deteriorates even though the kernel approximation improves with large P as learning a high-dimensional 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 algorithms 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 A.

heading: A ADDITIONAL EXPERIMENTS
text: The goal of this section is to empirically analyze the performance of the proposed approximation – optimization framework on real datasets. We evaluate the performance of the proposed approach on regression and classification tasks on datasets from the UCI repository. First for the regression task, we compare the mean squared error (MSE) and the communication performance of the proposed algorithm to popular decentralized regression algorithms DKRR-RF-CM (Liu et al., 2021), Decentralized RF (Richards et al., 2020), and DKLA (Xu et al., 2020). For the classification task, we benchmark the classification performance of the proposed algorithm against centralized algorithms. Specifically, via this set of experiments we determine the communication required by each agent to achieve performance similar to the centralized algorithms. To present the results, we use three types of popular GIP kernels, namely, the Polynomial, the Gaussian, and the NTK. Below, we discuss the dataset and the implementation details for both the tasks.
Regression Problem. We consider the regression task on the following UCI datasets: (i) Airfoil self-noise dataset. We compare the performance of the proposed algorithm with the benchmarking algorithms on National Advisory Committee for Aeronautics (NACA) airfoil noise dataset (Lau & López, 2009), where the goal is to predict aircraft noise based on a few measured attributes. The dataset consists of N = 1503 samples with each feature vector x(i)m ∈ R5 representing the measured attributes such as, frequency, angle, etc., and each label y(i)m ∈ R represents the noise level. (ii) Energy dataset. We also evaluate the performance of the algorithms on Appliances energy prediction dataset (Candanedo et al., 2017), where the goal is to predict the total energy consumption of a house based on attributes like, pressure, wind speed, and temperature and humidity in different areas of the house, etc. This dataset contains T = 19735 samples with the feature vector x(i)m ∈ R28 describing the measured attributes and y(i)m ∈ R representing the total energy consumption in the house.
Algorithm and Parameter Settings. For each setting we assume that there are M = 10 nodes in the network connected via a star topology. The overall data is split equally among the nodes. Each node utilizes 70% of its data for training and 30% for testing purposes. The learning performance of all the algorithms is evaluated by average MSE across all the nodes. Moreover, for our algorithm the testing is performed using Algorithm 4 in Appendix E. For all the algorithms, the regularization parameter λ is tuned from the set {10−3, 10−2, 10−1, 1, 10} while the step-sizes for Decentralized RF (Richards et al., 2020) and DKLA (Xu et al., 2020) are tuned from {10−3, 10−2, 10−1}. For the regression task, we compare the performance of the proposed algorithms with the Gaussian kernel and the NTK. Note that DKRR-RF-CM (Liu et al., 2021), Decentralized RF (Richards et al., 2020) and DKLA (Xu et al., 2020), can only be implemented using parameter sharing based RF approach (please see the respective papers) while our algorithm utilizes the GIP kernel approximation (cf. Algorithm 1) for the decentralized implementation. For the Gaussian kernel, we choose the scale parameter to be 1 and the P -dimensional random feature mapping is constructed using Algorithm 1 in Rahimi & Recht (2008). For the NTK, we generate the P -dimensional feature mapping utilizing the gradient of a single-hidden layer ReLU network with weights of the final layer chosen from U [{−1, 1}] (Cho & Saul, 2009; Chizat et al., 2019). Discussion. In Tables 2 and 3 of Section 5, we compared the performance of Algorithm 2 against the benchmarking algorithms on the Airfoil self-noise dataset with the Gaussian kernel. Next, in Table 4 we evaluate the performance of Algorithm 2 against other algorithms on the same dataset with the NTK. We choose P = 100 and compare the communication performance (measured in bits) for all the algorithms for a fixed MSE in Table 4a. Note that Algorithm 2 requires only a fraction of communication compared to other algorithms. Next, in Table 4b we compare the MSE performance of the algorithms for a fixed communication budget. Again, we observe that the proposed approximation – optimization approach achieves better performance compared to the state-of-the-art algorithms.
In Tables 5 and 6, we compare the communication and the MSE performance, respectively, of the algorithms for the energy dataset. We compare the performance with the Gaussian kernel for P = 100, 500, and 1000. In Table 5, we compare the communication required by each algorithm to achieve the same MSE for each setting, see last row of Table 5. We execute the parameter sharing algorithms DKRR-RF-CM (Liu et al., 2021), Decentralized RF (Richards et al., 2020), and (Xu et al., 2020) for a maximum of 100 iterations and report the total communication at the end of 100 rounds if the algorithm does not achieve the target MSE. Note that for all the algorithms and under all the settings, Algorithm 2 requires fewer bits of communication compared to other algorithms. In Table 6, we compare the averaged MSE achievable by different algorithms, when a fixed total communication budget (in bits) is given for each setting (see the last row of Table 6 for the budget). Again, note that Algorithm 2 significantly outperforms all the other methods.
Classification Problem. We benchmark the performance of the proposed approximation – optimization framework against the centralized algorithms on multi-class classification tasks. For this purpose, we use 90 UCI benchmarking datasets for evaluating the classification performance of the algorithms. For the datasets, we follow the pre-processing suggested in Fernández-Delgado et al. (2014). The datasets are chosen such that the sample sizes for each task are smaller than 5000 (Arora et al., 2020), with an average of approximately 965 samples per task. The samples are randomly split into equal sized training and test sets, and typical 4-fold cross-validation is used for performance comparison (Pedregosa et al., 2011). Note that for testing we utilize Algorithm 4 in Appendix E. For communication comparison, we consider three settings where the data is equally split randomly among agents with number of agents chosen as 5, 10 and 20. Next, we discuss the algorithms and parameter setting.
Algorithm and parameter settings. We evaluate the classification performance (test accuracy) of the proposed algorithm on three popular GIP kernels, namely the Polynomial, the Gaussian, and the NTK. For multi-class classification, we utilize kernel SVM with soft margin and regularization hyper-parameter λ tuned from the set {10−2, 10−1, 100, 101, 102}. For all the kernels, the hyperparameters are tuned using the validation method in Fernández-Delgado et al. (2014). For the NTK, we choose the kernel corresponding to a single hidden-layer ReLU network (please see (15)). Moreover, for the decentralized implementation all the kernels are estimated locally at individual nodes using the GIP kernel approximation in Algorithm 1. All the presented results are averaged over 3 independent runs of the algorithms.
Discussion. In Figure 1, we compare the test accuracy of the proposed approximation – optimization framework against the baseline centralized algorithm for the Gaussian, the Polynomial, and the NTK as P increases. Note that for all the kernels, the test accuracy of Algorithm 2 increases rapidly in the beginning and approaches the centralized benchmarks as P increases. Importantly, note that with only P = 1000, the test accuracy of Algorithm 2 is within 2% of the centralized benchmarks under all the settings. Since, this P is independent of the parameter dimension (i.e., D in (4)), this implies that the proposed approximation – optimization approaches can be utilized to alleviate the communication burden for distributed learning algorithms, especially for overparameterized learning problems. To analyze the communication performance of the proposed approach, in Table 7 we compare the overall bits communicated by each agent to achieve an accuracy of 75%. We note that for learning with the NTK, each agent needs to communicate only 220 real values4 on average for a network with 10 agents. This implies that a total of 2200 real values are shared across the network, which is only about 2.5 times the total sample size (N ≈ 965 on average). In contrast, if the agents share high-dimensional parameters (cf. Table 1) (resp. partial data), then the total real values shared will be 965β for β ≥ 2 per iteration (resp. 965 · df , where df is the dimension of the (shared) features), which will be much higher than our proposed approximation – optimization schemes even for moderate values of df .

heading: B RELEVANT LITERATURE
text: Current state-of-the-art decentralized/distributed kernel regression problems can be classified into three main categories. Below, we discuss each class of algorithms and their properties.
One of the most popular approaches for distributed kernel learning is the divide-and-conquer approach, where the overall dataset is partitioned among multiple agents, and each agent locally learns its corresponding optimal function (Zhang et al., 2015). These locally learned functions at each agent are then shared via one-shot communication to construct the global model. Divide-and-conquer approaches can guarantee the same generalization performance as of a centralized system (Zhang et al., 2015; Chang et al., 2016; Lin et al., 2017; Guo et al., 2017; Mücke & Blanchard, 2018). However, both practically and theoretically, divide-and-conquer approaches impose strict restriction on the number of agents, i.e., the performance of the distributed kernel regression degrades significantly as the number of agents increase (see Figure 2 in Lin et al. (2020)). In Lin et al. (2020), the au-
4On a 64 bit architecture, communicating 14, 080 bits is equivalent to communicating 220 real values.
thors proposed distributed kernel ridge regression with communications (DKRR-CM), where they showed that the dependence on the number of nodes can be improved by allowing some iterative communication between the nodes. However, a major issue with the state-of-the-art communication based approaches is that they require (neighboring) agents to share their local data with each other (or with the server), hence raising privacy concerns. A number of works have been proposed for decentralized/distributed kernel learning including Predd et al. (2006); Gao et al. (2015); Shin et al. (2016); Chouvardas & Draief (2016); Koppel et al. (2018); Pradhan et al. (2021) that require the (neighboring) agents to share raw data among each other that is undesirable for many practical applications.
Random Fourier features approach first proposed in Rahimi & Recht (2008) for centralized learning, and later adopted for decentralized kernel learning in (Bouboulis et al., 2017; Richards et al., 2020; Xu et al., 2020; Liu et al., 2021) alleviates some of the privacy concerns by allowing nodes to share finite dimensional parameters. In the random features (RF) approach, all the agents share a random seed to construct a finite dimensional feature map (Bouboulis et al., 2017; Xu et al., 2020). The kernel learning problem is then solved in the parameter domain with each agent iteratively updating the local parameters while sharing the learned parameters with the server (or the neighboring agents) in each cycle to achieve consensus. Specifically, Bouboulis et al. (2017) and Richards et al. (2020) developed distributed GD based algorithms for the kernel regression problems. In Bouboulis et al. (2017), the authors adopted a simple combine then adapt (CTA) algorithm, and provided asymptotic consensus guarantees and regret bounds for the optimization problem with general loss functions. In Richards et al. (2020) the authors proposed Decentralized RF algorithm based on RF approximation, they focused on `2 loss and provided generalization guarantees for the decentralized kernel learning problem. In contrast to Bouboulis et al. (2017) and Richards et al. (2020), Xu et al. (2020) proposed DKLA and COKE, where they utilized decentralized ADMM (Shi et al., 2014) to solve the (RF approximated) decentralized kernel learning problem, and provided both optimization and generalization guarantees for the proposed algorithms. The work Liu et al. (2021) proposed DKRRRF-CM and improved upon the results of Lin et al. (2020) by adopting the RF approach. Specifically, DKRR-RF-CM avoids data sharing and improves the dependence on the number of agents to guarantee optimal generalization guarantees compared to DKRR-CM (Lin et al., 2020). Please see Table 1 for a comparison of these approaches to that of the learning framework proposed in this work.
Despite of all the benefits of the RF approaches, they suffer from excessive communication overhead when the parameter dimension is large compared to the data size (i.e., the overparameterized regime) (Belkin et al., 2019). For example, the number of random features required to approximate the NTK (Jacot et al., 2018; Arora et al., 2019) of a multi-layer neural network increase exponentially with the number of layers and can be much larger than the number of data samples even for a single layer NTK (Arora et al., 2019; Han et al., 2021). For such problems, it is prohibitively expensive to share the learned local parameters at each communication round. To reduce the communication overhead, there are two classical approaches: (i) sharing model parameters intermittently between computations (McMahan et al., 2017; Stich, 2018; Lin et al., 2018), and/or, (ii) compressing model parameters before sharing (Seide et al., 2014; Alistarh et al., 2017; Bernstein et al., 2018). Although these approaches can lead to some communication savings, they require iteratively communicating high-dimensional parameters or might lead to increased variance (McMahan et al., 2017; Alistarh et al., 2017), hence slowing down convergence. As discussed in the introduction section, perhaps a more efficient way is to directly share the local data if the size of local data is much smaller than that of the parameters. However, this approach raises privacy concerns, and is rarely used in practice. Therefore, it is necessary to devise techniques for decentralize kernel learning where one can avoid sharing very high-dimensional parameters iteratively, and at the same time does not require raw data sharing among agents. In this work, we take an approach orthogonal to all the
above mentioned works and propose a decentralized kernel learning framework that is suitable for learning in the overparameterized regime. Specifically, the proposed framework departs from the popular consensus-based approaches by locally solving the learning problem independently at each agent. This is accomplished by approximating the “global” learning problem locally at each agent via one-shot information sharing among agents before initialization (see Section 3 for more details).

heading: C NEURAL TANGENT KERNEL
text: In this section, we discuss the NTK as a motivation to define the GIP kernels.
Neural tangent kernel (NTK): The NTK of an L hidden-layer fully-connected neural network with element wise activation a : R→ R is Jacot et al. (2018); Chizat et al. (2019); Arora et al. (2019):
k(x, x′) = L+1∑ h=1 ( Σ(h−1)(x, x′) · L+1∏ h′=h Σ̇(h ′)(x, x′) ) ,
where Σ(h) and Σ̇(h) are defined recursively as:
Σ(0)(x, x′) = xTx′,
Λ(h)(x, x′) = ( Σ(h−1)(x, x) Σ(h−1)(x, x′) Σ(h−1)(x′, x) Σ(h−1)(x′, x′) ) ∈ R2, (14)
Σ(h)(x, x′) = E(u,v)∈N (0,Λ(h))[a(u)a(v)] and Σ̇(h)(x, x′) = E(u,v)∈N (0,Λ(h))[ȧ(u)ȧ(v)],
where ȧ(·) is the derivative of a. For ReLU activation the NTK in (14) is a GIP kernel (Han et al., 2021) and can be defined in closed form (Arora et al., 2020; Han et al., 2021). Note that to approximate the multi-layer NTK one needs at least P = O(N2) parameters (Arora et al., 2019). Therefore, implementing a decentralized method that utilizes parameter sharing will incur heavy communication cost. Next, we show that the NTK can easily be approximated in a decentralized manner using the GIP kernel characterization. For ease of exposition, we consider the NTK with ReLU activation for a single hidden-layer neural network (Cho & Saul, 2009; Cho, 2012; Chizat et al., 2019) where the weights of the final layer are chosen from U [{−1, 1}]
k(x, x′) = xTx′ π − ψ(x, x′)
2π , (15)
where ψ(x, x′) = arccos(xTx′/‖x‖‖x′‖) ∈ [0, π]. Note that the NTK (15) depends on the innerproduct as well as the angle between x and x′, and the former can be constructed by the latter if one also knows the norms of the data samples. 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 as well as the angles between any pair of them are known at each agent. Moreover, for many applications of practical interest (Bietti & Mairal, 2019; Geifman et al., 2020; Pedregosa et al., 2011) normalized feature vectors are utilized for learning, for such problems the GIP kernel at each agent can be fully computed only with the knowledge of the pairwise angles between the (normalized) feature vectors. Further, the RF kernels also exhibit a special structure where they can be approximated with the knowledge of feature mapping φP (·) ∈ RP corresponding to all the feature vectors. The RF kernel approximation is expected to work well for generic kernels (Rahimi & Recht, 2008; Rudi & Rosasco, 2017), however, they might not be suited for all the problems, especially for overparameterized problems (like NTK in (15)), where P can be very large , i.e., P = O(Nβ) with β > 1 (Han et al., 2021; Arora et al., 2019) (cf. Table 1 and discussion in Section 1). For such overparameterized problems, GIP kernel is an appealing alternative to the RF kernel. The above discussed properties of the GIP (and the RF) kernels enable us to design an efficient decentralized kernel approximation and message exchange scheme, which allows the agents to estimate randomly approximated versions of these kernels, but without directly sharing the (raw) local data.
Algorithm 3 Decentralized Gradient Tracking for Kernel Learning
1: Initialize: α1m = α1 ∈ RN , ∆1m = ∇R̂P (α1m), step-sizes {ηt}Tt=1 at each agent m ∈ [M ] 2: for m ∈ [M ] do 3: Using Algorithm 1 construct KP 4: Construct local functions L̂m,P (α) (cf. equation 10) 5: for t = 1 to T do 6: Update: αt+1m = ∑ k∈NBm [W ]mkα t m − ηt∆tm
7: Gradient Tracking: ∆t+1m = ∑ k∈NBm [W ]mk∆ t k +∇R̂P (αt+1m )−∇R̂P (αtm) 8: end for 9: end for
10: Return: αT+1m for all m ∈ [M ]

heading: D AN ALGORITHM BASED ON DECENTRALIZED GRADIENT TRACKING
text: (DGT)
Note that in this setting we utilize DGT to learn α locally. Since, this algorithm is a natural extension of DGT in the functional space, there will be consensus in parameters αm learned at each agent m ∈ [M ] (Qu & Li, 2018). Note that in contrast to Algorithm 2, DGT does not require sharing labels. For DGT we assume that the agents communicate via a undirected graph represented by a doubly stochastic matrix W . We denote by NBm the neighbourhood of agent m ∈ [M ], i.e., NBm = {k ∈ [M ] : [W ]mk 6= 0}. The steps of DGT are listed in Algorithm 3. In Step 3, each agent locally computes KP . We utilize the fact that the once KP is known, the loss in (10) is decomposable in m ∈ [M ]. This implies that each agent can update the local parameters αm using Steps 6 and 7. Below we list important properties of Algorithm 3:
[Communication] The total communication required at each agent is O(nP +NT ) values (where the term nP are bits for the GIP and real values for the RF kernels). The DGT algorithm is useful when problem (10) is strongly-convex (or PL), in that case T = O(logN) (Qu & Li, 2018) and total communication becomes Õ(nP +N). Note that even for non-convex losses L̂m,P (·), the local objective at each agent can be made strongly-convex with large regularizer, λ.
[Consensus] DGT with appropriately chosen step-sizes {ηt}Tt=1 will guarantee consensus of αm’s, this will ensure functional consensus, i.e., f̂m,P ≈ f̂m̄,P for m 6= m̄ and m, m̄ ∈ [M ].

heading: E TESTING ALGORITHM FOR DECENTRALIZED KERNEL REGRESSION
text: In this section, we outline how to perform testing once the kernel model has been trained to solve (10). Suppose that there is a set Ntest test samples {(x(i), y(i))}Ntesti=1 . The idea is to utilize the local information at each agent, {Am}Mm=1, combined with the new data, to construct the testing kernel matrix, based on which the testing process can be carried out.
Specifically, we use Algorithm 4 to construct the kernel matrix KP,test ∈ RNtest×N as
1. GIP kernel: For the GIP kernel, we consider the same setting as (7) and construct KP.test as
kP (x (i), x(j)m ) = g(ψP (x (i), x(j)m ), ‖x(i)‖, ‖x(j)m ‖), (16)
where kP (x(i), x (j) m ) ∀i ∈ [Ntest] and ∀j ∈ Nm, ∀m ∈ [M ] are the individual elements of KP,test and where ψP (x(i) is defined using Atest and Am as:
ψP (x (i), x(j)m ) = ∣∣∣∣π − 2π [A(:,i)test ]T [A(:,j)m ]P ∣∣∣∣,
where A(:,i) ∈ RP represents the ith column of matrix A. 2. RF kernel: Similarly, for the RF kernel, we construct KP.test as
kP (x (i), x(j)m ) = 〈φP (x(i)), φP (x(j)m ))〉, (17)
Algorithm 4 Local Kernel Estimation for Testing
1: Initialize: Test samples {x(i)}Ntesti=1 ; {ωi}Pi=1 and matrices {Am}Mm=1 from Algorithm 1 2: Compute ζ(x(i), ωj) ∀i ∈ [Ntest] and j ∈ [P ] 3: Define matrix Atest ∈ RP×Ntest with elements ζ(x(i), ωj) 4: Estimate the kernel matrix KP,test using (16) for the GIP and (17) for the RF kernel
where again kP (x(i), x (j) m ) are the individual elements of KP,test, similar to (9), we have
φP (x (i)) = 1/ √ P [A (:,i) test ] and φP (x (j) m ) = 1/ √ P [A (:,j) m ].
Once we have KP,test, then the testing is performed as:
f̂P,m(x (i)) = [ KP,test · α(T+1)m ](i) , (18)
where and [ KP,test · α(T+1)m ](i) represents the ith element of the vector [KP,test · α(T+1)m ] ∈ RNtest . Using (18) we can evaluate the test loss
L̂P,test(αT+1m ) = 1
Ntest Ntest∑ i=1 ` ([ KP,test · α(T+1)m ](i) , y(i) ) . (19)
Next, we present the performance of the multi-agent kernel approximation framework proposed in this work. Note that the algorithms presented above work for arbitrary loss functions. However, in the sequel we focus on the `2 loss and provide training and generalization loss incurred because of the multi-agent kernel approximation. Remark 5 (Optimization performance of GD (Nesterov, 2003) and DGT (Qu & Li, 2018)). Algorithms 2 and 3 can solve the approximated kernel problem (10) to arbitrary accuracy. In particular, for strongly-convex and smooth objectives, both GD and DGT converge at a linear rate. On the other hand, for convex and smooth objectives both GD and DGT converge sub-linearly with rateO(1/T ).

heading: F NOTATIONS
text: First, we define some notations below.
• Recall that the features and the labels are generated as (x, y) ∼ π(x, y) where π(x, y) defines the joint probability distribution on X × R.
• πx denotes the marginal distribution of the features on X . • π(y|x) denotes the conditional distribution of the label y given the feature x on R. • We define by L2(X , πx) as the space of square integrable functions with Lebesgue measure
defined by πx.
• The inner-product and the norm on space L2(X , πx) is defined by Inner-product: 〈f, g〉πx = ∫ x∈X f(x)g(x)dπx(x),
Norm: ‖f‖πx = ( 〈f, f〉πx )1/2 , ∀f, g ∈ L2(X,πx).
• We define the RKHS induced by mapping k and kP asH andHP , respectively, as
H = span{k(x, ·) : x ∈ X}, and HP = span{kP (x, ·) : x ∈ X}.
with inner-products defined as 〈k(x, ·), k(x′, ·)〉H = k(x, x′) in H and 〈kP (x, ·), kP (x′, ·)〉HP = kP (x, x′) in HP . We also note that HP = RP for the RF kernels.
Next, we define some operators which shall be utilized in bounding the optimization and generalization losses.
• We define K : L2(X , πx)→ L2(X , πx) and KP : L2(X , πx)→ L2(X , πx) as
(Kh)(x) = ∫ z∈X k(x, z)h(z)dπz and (KPh)(x) = ∫ z∈X kP (x, z)h(z)dπz.
• Next, we define Φ : H → L2(X , πx) and ΦP : HP → L2(X , πx) as
(Φβ)(x) = 〈φ(x), β〉 and (ΦPβ)(x) = 〈φP (x), β〉
• Moreover, using the definitions of Φ and ΦP we define the covariances C : H → H and CP : HP → HP as
C = Φ∗Φ and CP = Φ∗PΦP ,
Also, note that from the definition of Φ we have K = ΦΦ∗ and KP = ΦPΦ∗P .
• We define the finite sample version of the operators Φ∗ and Φ∗P as Φ̂ ∗ : RN → H and Φ̂∗P :
RN → HP , respectively as
Φ̂∗ŷ = 1√ N N∑ i=1 φ(xi)ŷi and Φ̂∗P ŷ = 1√ N N∑ i=1 φP (xi)ŷi.
where ŷ ∈ RN . • From the definition of Φ̂ and Φ̂P
– We define Ĉ : H → H and ĈP : HP → HP as
Ĉ = Φ̂∗Φ̂ and ĈP = Φ̂∗P Φ̂P .
– Moreover, we define K̂ : RN → RN and K̂P : RN → RN as
K̂ = Φ̂Φ̂∗ and K̂P = Φ̂P Φ̂∗P .
• For an operatorA, we define the operatorAλ asAλ = A+λI . We also denote by λmax(A) as the largest eigen value of A. We denote by ‖A‖ the operator norm and ‖A‖HS the Hilbert-Schmidt norm of a linear operator A.
Remark 6. Note from the definition of operators K̂ and K̂P we have
K̂ = 1
N K, and K̂P =
1
N KP .
We will utilize this fact and the operators defined above in the proofs for bounding the optimization and generalization errors for the kernel methods.

heading: G OPTIMIZATION PERFORMANCE OF MULTI-AGENT KERNEL APPROXIMATION FRAMEWORK: PROOF OF THEOREM 4.2
text: In this section, we present the complete proof of Theorem 4.2. Specifically, the main technical results in this section is to analyze the impact of the multi-agent kernel approximation framework proposed in this work on the training performance for the proposed algorithms. For this purpose, we bound difference between the optimal losses for the exact and the approximated kernel ridge regression problems (12) and (13). Towards this end, we first provide a few technical lemmas.
First, we present two concentration inequalities to bound the distance between the empirical mean of a sequence of random matrices (and random variables) from their mean. These results will be later used in Proposition G.4 to bound the operator norms of difference between the kernel matrix K and its approximation KP . First, we present the Bernstein’s inequality for random matrices.
Proposition G.1 (Bernstein’s inequality for random matrices, Theorem 6.1.1 in Tropp (2012)). Consider a sequenceX` for ` ∈ N of independent, random, Hermitian matrices of dimensionN . Assume that
E[X`] = 0 and ‖X`‖ ≤ C almost surely.
Define a random matrix as Y := ∑ `X`, and denote its variance as σ
2 := ‖E[Y 2]‖. Then for all ≥ 0, we have P[‖Y ‖ ≥ ] ≤ 2N exp ( − 2
2(σ2 + C · /3)
) .
Moreover, with probability at least 1− δ for δ ∈ (0, 1] we have: ‖Y ‖ ≤ √ 2σ2 log 2N
δ +
2C
3 log
2N
δ .
In the next proposition, we present the Bernstein’s inequality to bound the distance between the empirical mean of a sequence of random variables and their mean. Proposition G.2 (Bernstein’s inequality for random variables). Consider a sequence {x`}`∈N of independent, random variables such that the following holds:
E[x`] = 0 and |x`| ≤ C almost surely. Define the random variable y := ∑ ` x`, and denote its variance as σ
2 := E[y2]. Then for all ≥ 0, we have:
P[|y| ≥ ] ≤ 2 exp (
− 2
2(σ2 + C · /3)
) .
Next, using the above propositions we derive a union bound on the estimate ψP (x (i) m , x (j) m̄ ) in (8) from its mean ψ(x(i)m , x (j) m̄ ) for all training data samples, i.e., for all i ∈ Nm and j ∈ Nm̄ with m, m̄ ∈ [M ]. Recall from Algorithm 1 and (8) that we have
ψP (x (i) m , x (j) m̄ ) = ∣∣∣∣π − 2π [A(:,i)m ]T [A(:,j)m̄ ]P ∣∣∣∣, (20)
where A(:,i)m ∈ RP . Specifically, the matrix Am for the GIP kernel for the mth agent is
Am =  ζ(x (1) m , ω1) ζ(x (2) m , ω1) · · · ζ(x(n)m , ω1) ζ(x (1) m , ω2) ζ(x (2) m , ω2) · · · ζ(x(n)m , ω2) ... ... . . . ...
ζ(x (1) m , ωP ) ζ(x (2) m , ωP ) · · · ζ(x(n)m , ωP )  ∈ RP×n, where we choose ζ(x, ω) = 1[ωTx ≥ 0] and with {ω`}L`=1 chosen uniformly randomly from a circularly symmetric distribution. Please see discussion in Section 3.1 for details.
Below, we present the union bound. Proposition G.3 (Union Bound: GIP kernel). Let ψ(x(i)m , x(j)m̄ ) = arccos ( 〈x(i)m ,x (j) m̄ 〉
‖x(i)m ‖‖x(j)m̄ ‖
) be the
angle between two feature vectors x(i)m and x (j) m̄ , and letψP (x (i) m , x (j) m̄ ) be an estimate ofψ(x (i) m , x (j) m̄ ) as defined in (20). Then with probability at least 1− δ, the following holds:
∣∣ψP (x(i)m , x(j)m̄ )− ψ(x(i)m , x(j)m̄ )∣∣ ≤ √ 32π2
P log
2N
δ +
8π 3P log 2N δ ,
∀i ∈ Nm, ∀j ∈ Nm̄ and ∀m, m̄ ∈ [M ].
Proof. Note from the definition of ψP (x (i) m , x (j) m̄ ) in (20) for the GIP kernel, we have∣∣ψP (x(i)m , x(j)m̄ )− ψ(x(i)m , x(j)m̄ )∣∣ (i)= ∣∣∣∣∣∣∣π − 2π [A(:,i)m ]T [A(:,j)m̄ ]P ∣∣∣− ∣∣π − 2πE[ζ(x(i)m , ω)ζ(x(j)m̄ , ω)]∣∣ ∣∣∣∣ (ii)
≤ 2π ∣∣∣∣ [A(:,i)m ]T [A(:,j)m̄ ]P − E[ζ(x(i)m , ω)ζ(x(j)m̄ , ω)] ∣∣∣∣ (21)
with ζ(x, ω) = 1[ωTx ≥ 0] and where (i) uses E[ζ(x(i)m , ω)ζ(x(j)m̄ , ω)] = π−ψ(x(i)m ,x (j) m̄ )
2π for ω ∼ N (0, I) Chizat et al. (2019); Cho & Saul (2009); Cho (2012), and (ii) follows from the reverse triangle inequality. Next, note from the definition of Am, we have
[A (:,i) m ]T [A (:,j) m̄ ]
P =
1
P P∑ `=1 ζ(x(i)m , ω`)ζ(x (j) m̄ , ω`) (22)
Let us define the random variable z` as
z` := 1
P
[ ζ(x(i)m , ω`)ζ(x (j) m̄ , ω`)− E [ ζ(x(i)m , ω)ζ(x (j) m̄ , ω) ]] .
Note from the definition of z` that we have
E[z`] = 0 and |z`| ≤ 1
P , ∀` ∈ [P ].
To proceed, let us define the sum of z`’s as Z(x (i) m , x (j) m̄ ) = ∑L `=1 z`. Noticing that we can relate Z(x (i) m , x (j) m̄ ) to the quantity (21) we want to bound in as
Z(x(i)m , x (j) m̄ ) = P∑ `=1 z`
= 1
P P∑ `=1 [ ζ(x(i)m , ω`)ζ(x (j) m̄ , ω`)− E [ ζ(x(i)m , ω)ζ(x (j) m̄ , ω) ]] (i) = [A (:,i) m ]T [A (:,j) m̄ ]
P − E
[ ζ(x(i)m , ω)ζ(x (j) m̄ , ω) ] .
where the equality (i) follows from (22). Moreover, note that this term is zero mean which follows from the fact that each z` is zero mean in the first equality. Further, we bound the variance of Z(x (i) m , x (j) m̄ ) as
σ2 = E[(Z(x(i)m , x (j) m̄ ))
2] = E [( P∑
`=1
z`
)2] (i) = P∑ `=1 E[z2` ] (ii) ≤ 1 P ,
where (i) comes from the facts that (a): each z` for ` ∈ [P ] is zero mean, and (b): z` and zk are independent for all ` 6= k; (ii) uses the fact that z2` ≤ 1/P 2 for all ` ∈ [P ].
Applying Proposition I.1 to the random variable Z(x(i)m , x (j) m̄ ), we get P [∣∣Z(x(i)m , x(j)m̄ )∣∣ ≥ ] ≤ 2 exp( − 22((1/P ) + ( /3P )) ) .
Taking the union bound over all the training samples, i.e., ∀i ∈ Nm, ∀j ∈ Nm̄ with ∀m, m̄ ∈ [M ], we get
P [ ⋃ m,m̄∈[M ] ⋃ i∈Nm,j∈Nm̄ {∣∣Z(x(i)m , x(j)m̄ )∣∣ ≥ }] ≤ M∑ m=1 M∑ m̄=1 ∑ i∈Nm ∑ j∈Nm̄ P [∣∣Z(x(i)m , x(j)m̄ )∣∣ ≥ ]
≤ 2N2 exp (
− 2 2 ( (1/P ) + ( /3P ) )). Note from above that we have that with probability at least 1− δ
|Z(x(i)m , x (j) m̄ )| = ∣∣∣∣ [A(:,i)m ]T [A(:,j)m̄ ]P − E[ζ(x(i)m , ω)ζ(x(j)m̄ , ω)] ∣∣∣∣
≤ √ 8
P log
2N
δ +
4
3P log
2N
δ , ∀i ∈ Nm,∀j ∈ Nm̄ with ∀m, m̄ ∈ [M ].
Substituting the above in (21) completes the proof..
Next, we provide a key technical result, which bounds the operator norm of the difference between the kernel, K and it’s approximation KP . We present the results for both th GIP and the RF kernel. The following proposition is utilized in the proof of Theorem 4.2. Proposition G.4. The following holds with probability at least 1− δ
1. For GIP kernel, we have ‖K−KP ‖ ≤ G ·N · (√ 32π2
P log
2N
δ +
8π 3P log 2N δ
) .
2. For RF kernel, we have ‖K−KP ‖ ≤ κ2 ·N · (√ 8
P log
2N
δ +
4
3P log
2N
δ
) .
Proof. First, we consider the GIP kernel.
(i): GIP kernel: Note from the definition of approximated GIP kernel in (7) that the individual elements of KP ∈ RN×N are g(ψP (x(i)m , x(j)m̄ ), ‖x (i) m ‖, ‖x(j)m̄ ‖). Similarly, from (5) individual elements of K ∈ RN×N are g(ψ(x(i)m , x(j)m̄ ), ‖x (i) m ‖, ‖x(j)m̄ ‖), ∀i ∈ Nm, ∀j ∈ Nm̄ with ∀m, m̄ ∈ [M ].
Next, we use the notation B = [ bij ] ∈ RN×N to denote the matrix with individual elements bij , i.e.,
B =  b11 b12 · · · b1N... ... . . . ... bN1 bN2 · · · bNN  = [bij] ∀i, j ∈ [N ]. (23) Then we have with probability at least 1− δ
‖K−KP ‖ (i) = ∥∥∥∥∥ [ g(ψ(x(i)m , x (j) m̄ ), ‖x(i)m ‖, ‖x (j) m̄ ‖)− g(ψP (x(i)m , x (j) m̄ ), ‖x(i)m ‖, ‖x (j) m̄ ‖) ]∥∥∥∥∥ (ii)
≤ ∥∥∥∥∥ [∣∣∣∣g(ψ(x(i)m , x(j)m̄ ), ‖x(i)m ‖, ‖x(j)m̄ ‖)− g(ψP (x(i)m , x(j)m̄ ), ‖x(i)m ‖, ‖x(j)m̄ ‖)∣∣∣∣ ]∥∥∥∥∥ (iii)
≤ G · ∥∥∥∥∥ [∣∣∣ψ(x(i)m , x(j)m̄ )− ψP (x(i)m , x(j)m̄ )∣∣∣] ∥∥∥∥∥ (iv)
≤ G · (√ 32π2
P log
2N
δ +
8π 3P log 2N δ
) · ∥∥∥∥∥∥∥ 1 1 · · · 1... ... . . . ...
1 1 · · · 1
 ∥∥∥∥∥∥∥
(v) ≤ G ·N · (√ 32π2
P log
2N
δ +
8π 3P log 2N δ
) ,
where equality (i) uses the definition of the GIP kernel and its approximation in (5) and (7), resp.; inequality (ii) results from the fact that for Lp-operator norm with p an even integer we have for any matrix B ∥∥∥∥∥∥∥  b11 b12 · · · b1N... ... . . . ... bN1 bN2 · · · bNN  ∥∥∥∥∥∥∥ ≤ ∥∥∥∥∥∥∥  |b11| |b12| · · · |b1N |... ... . . . ... |bN1| |bN2| · · · |bNN |  ∥∥∥∥∥∥∥ ,
inequality (iii) results from the Lipschitzness of function g(·, z1, z2) in Assumption 2 and the fact that for any matrices A and B with positive entries, we have ‖B‖ ≤ ‖A + B‖; inequality (iv) utilizes Proposition G.3 and again the fact that for any matrices A and B with positive entries, we have ‖B‖ ≤ ‖A + B‖; Finally, (v) uses the fact that the L2-operator norm (maximum eigenvalue) of the all one matrix of dimension N ×N is N .
Therefore, the first result has been proven.
(ii): RF kernel: First, we note that the matrix KP can be decomposed as
KP = 1
P L∑ `=1 K`,
where K` ∈ RN×N consists of individual elements of the form ζ(x(i)m , ω`) · ζ(x(j)m̄ , ω`), ∀i ∈ Nm, ∀j ∈ Nm̄ with ∀m, m̄ ∈ [M ]. Recall that {ω`}P`=1 are drawn i.i.d from distribution p(ω). Please see discussion in Section 3.1 on RF kernel approximation. Then using the matrix notation defined in (23) we we write K` as
K` := [ ζ(x(i)m , ω`) · ζ(x (j) m̄ , ω`) ] ∈ RN×N ∀i ∈ Nm,∀j ∈ Nm̄ with ∀m, m̄ ∈ [M ].
We apply Proposition G.1 on the sequence of random matrices defined by [K` −K]/P . Note that we have:
E [ K` −K
P
] = 0 and
∥∥∥∥K` −KP ∥∥∥∥ ≤ 2N · κ2P ,
where the first equality follows from the definition of the RF kernel in (6) and the definition of K`, and the second inequality follows from Assumption 1. To apply Proposition G.1, we need to upper bound the variance of the sum ∑P `=1 K`−K P = KP −K. Towards this end, we obtain:
σ2 ( KP −K ) := ∥∥E[(KP −K)2]∥∥
(i) =
1
P 2 ∥∥∥ L∑ `=1 E[(K` −K)2] ∥∥∥
(ii) =
1
P ∥∥E[(K` −K)2]∥∥ (iii)
≤ 1 P ∥∥∥∥ ∣∣∣E[(K` −K)2]∣∣∣ ∥∥∥∥ (iv)
≤ 4κ 4N
P ∥∥∥∥∥∥∥ 1 1 · · · 1... ... . . . ...
1 1 · · · 1
 ∥∥∥∥∥∥∥
(v) ≤ 4κ 4N2
P ,
where (i) follows from the fact that K` −K are zero mean and independent across ` ∈ [P ]; (ii) utilizes that K` −K are i.i.d. across ` ∈ [P ]; for inequality (iii), we used the notation that for a matrix B, |B| denotes the matrix with absolute values of B and combined it with the fact that for Lp-operator norm with p as an even integer we have for any matrix B that∥∥∥∥∥∥∥  b11 b12 · · · b1N... ... . . . ... bN1 bN2 · · · bNN  ∥∥∥∥∥∥∥ ≤ ∥∥∥∥∥∥∥  |b11| |b12| · · · |b1N |... ... . . . ... |bN1| |bN2| · · · |bNN |  ∥∥∥∥∥∥∥ .
Inequality, (iv) results from the use of Assumption 1, specifically, using Assumption 1 verify that each element of E[(K`−K)2] is bounded by 4κ4N and combine with the fact that for any matrices A and B with positive entries, we have ‖B‖ ≤ ‖A+B‖; finally, (v) utilizes that for all one matrix of dimension N ×N the L2 operator norm (maximum eigen-value) is equal to N .
Therefore, we have the result. Next, using Proposition G.1 with X` = K`−KP , we have ‖KP −K‖ ≤ √ 8κ4N2
P log
2N
δ +
4Nκ2
3P log
2N
δ = κ2 ·N ·
(√ 8
P log
2N
δ +
4
3P log
2N
δ
) .
with probability at least 1− δ. Therefore, the proof is complete.
Finally, we state our main result.
Theorem G.5. For any fixed λ > 0, the following holds with probability at least 1− δ
1. For the GIP kernel, we have:∣∣∣L̂P (α̂∗P )− L̂(α̂∗)∣∣∣ ≤ 2R2 ·Gλ · (√ 32π2 P log 2N δ + 8π 3P log 2N δ ) .
Moreover, we have:∣∣∣R̂P (α̂∗P )− R̂(α̂∗)∣∣∣ ≤ 3R2 ·Gλ · (√ 32π2 P log 2N δ + 8π 3P log 2N δ ) .
2. For the RF kernel, we have:∣∣∣L̂P (α̂∗P )− L̂(α̂∗)∣∣∣ ≤ 2R2 · κ2λ · (√ 8 P log 2N δ + 4 3P log 2N δ ) .
Moreover, we have∣∣∣R̂P (α̂∗P )− R̂(α̂∗)∣∣∣ ≤ 3R2 · κ2λ · (√ 8 P log 2N δ + 4 3P log 2N δ ) .
Proof. Recall from the notations in Appendix F that we have
K̂ = 1
N K, and K̂P =
1
N KP . (24)
and we defined
K̂λ = K̂ + λ · I, K̂P,λ = K̂P + λ · I, (25)
where I is the identity matrix of some appropriate size. It is easy to observe that the optimal solutions to problems (12) and (13) are given by the following closed-form solutions
α̂∗ = [K +N · λ · I]−1ȳ = 1 N · K̂−1λ · ȳ, α̂ ∗ P = [KP +N · λ · I]−1ȳ = 1 N · K̂−1P,λ · ȳ. (26)
From the definition of the loss function for the `2 loss, we obtain:∣∣∣L̂P (α̂∗P )− L̂(α̂∗)∣∣∣ (i)= 12N ∣∣∣ ‖ȳ − K̂P · K̂−1P,λ · ȳ‖2 − ‖ȳ − K̂ · K̂−1λ · ȳ‖2 ∣∣∣ (ii) = 1
2N ∣∣∣ 〈[K̂P · K̂−1P,λ − K̂ · K̂−1λ ]ȳ, [K̂P · K̂−1P,λ + K̂ · K̂−1λ ]ȳ〉 − 2 〈 ȳ, [ K̂P · K̂−1P,λ − K̂ · K̂ −1 λ ] ȳ 〉 ∣∣∣
(iii)
≤ 1 2N [ ∥∥∥[K̂P · K̂−1P,λ + K̂ · K̂−1λ ]ȳ∥∥∥︸ ︷︷ ︸ term(A) ∥∥∥[K̂P · K̂−1P,λ − K̂ · K̂−1λ ]ȳ∥∥∥︸ ︷︷ ︸ term(B)
+ 2‖ȳ‖ ∥∥∥[K̂P · K̂−1P,λ − K̂ · K̂−1λ ]ȳ∥∥∥︸ ︷︷ ︸
term(B)
] (27)
where (i) utilizes (25) and (26); (ii) uses the following
‖A · z − z‖2 − ‖B · z − z‖2 = ‖A · z‖2 − ‖B · z‖2 − 2〈z, [A−B]z〉 = 〈[A+B]z, [A−B]z〉 − 2〈z, [A−B]z, 〉,
and (iii) results from the application of Cauchy-Schwartz and triangle inequality.
Next, we consider the term(A) and term(B) in (27), and provide upper bounds for them. Let us first analyze term(B). we have:[
K̂ · K̂−1λ − K̂P · K̂ −1 P,λ
] ȳ = [( K̂ + λ · I − λ · I ) K̂−1λ − ( K̂P + λ · I − λ · I ) K̂−1P,λ ] ȳ
(i) = [( I − λ · K̂−1λ ) − ( I − λ · K̂−1P,λ )] ȳ
= λ · [ K̂−1P,λ − K̂ −1 λ ] ȳ
(ii) = λ · K̂−1P,λ [ K̂λ − K̂P,λ ] K̂−1λ · ȳ
(iii) = λ · K̂−1P,λ [ K̂ − K̂P ] K̂−1λ · ȳ (28)
where (i) follows from the definition of K̂λ and K̂P,λ; (ii) results from A−1 − B−1 = A−1(B − A)B−1 for invertible matrices A and B and (iii) again results from the definition of K̂λ and K̂P,λ. This implies that we have:∥∥[K̂ · K̂−1λ − K̂P · K̂−1P,λ]ȳ‖ (i)≤ λ · ‖K̂−1P,λ‖ · ‖K̂ − K̂P∥∥ · ‖K̂−1λ ‖ · ‖ȳ‖
(ii) ≤ √ N ·R λ ‖K̂ − K̂P ∥∥
(iii)
≤ R√ N · λ
‖K−KP ∥∥
where inequality (i) results from the Cauchy-Schwartz inequality; (ii) uses the fact that ‖K̂−1P,λ‖ ≤ 1/λ, ‖K̂−1λ ‖ ≤ 1/λ and ‖ȳ‖ ≤ √ N ·R, and (iii) utilizes the definition of K̂ and K̂P .
Next, we utilize high probability bounds for the term ‖K −KP ‖, which characterize the effect of sampling using P observations. Towards this end, we invoke Proposition G.4, which provides two high probability bounds for this term, one for the GIP, and one for the RF kernel. Specifically, for the former kernel, we have the following∥∥[K̂ · K̂−1λ − K̂P · K̂−1P,λ]ȳ‖ ≤ R ·G · √Nλ (√ 32π2 P log 2N δ + 8π 3P log 2N δ ) , with probability at least 1− δ. Similarly, we have for the RF kernel∥∥[K̂ · K̂−1λ − K̂P · K̂−1P,λ]ȳ‖ ≤ R · κ2 · √Nλ (√ 8 P log 2N δ + 4 3P log 2N δ ) ,
with probability at least 1 − δ. This completes the analysis for term(B) in (27). Next, we consider the term(A) in (27). We have:∥∥∥[K̂P K̂−1P,λ + K̂K̂−1λ ]ȳ∥∥∥ ≤ ∥∥[K̂P K̂−1P,λ]ȳ∥∥+ ∥∥[K̂K̂−1λ ]ȳ∥∥
≤ 2‖ȳ‖ ≤ 2 √ N ·R.
Now substituting the bounds for term(A) and term(B) into (27), we get the following bounds: For the GIP kernel:∣∣∣L̂P (α̂∗P )− L̂(α̂∗)∣∣∣ ≤ 2R2 ·Gλ · (√ 32π2 P log 2N δ + 8π 3P log 2N δ ) . (29) For the RF kernel:∣∣∣L̂P (α̂∗P )− L̂(α̂∗)∣∣∣ ≤ 2R2 · κ2λ · (√ 8 P log 2N δ + 4 3P log 2N δ ) . (30)
Next, we bound the loss incurred because of multi-agent kernel approximation for the oveall objective for both the kernels. Note from the definition of the R̂(α) and R̂P (α)∣∣∣R̂(α̂∗)− R̂(α̂∗P )∣∣∣ = ∣∣∣L̂(α̂∗)− L̂(α̂∗P ) + λ2 ‖α̂∗‖2K − λ2 ‖α̂∗P ‖2KP ∣∣∣
≤ ∣∣∣L̂(α̂∗)− L̂(α̂∗P )∣∣∣+ λ2 ∣∣∣‖α̂∗‖2K − ‖α̂∗P ‖2KP ∣∣∣, (31)
which follows from the use of triangle inequality. Note that we have already bounded the first term. In the following, we bound the second term of (31) above. λ
2 · ∣∣∣‖α̂∗‖2K − ‖α̂∗P ‖2KP ∣∣∣ (i)= λ2N · ∣∣∣ȳT [K̂−1λ · K̂ · K̂−1λ − K̂−1P,λ · K̂P · K̂−1P,λ]ȳ∣∣∣
(ii)
≤ λ 2N · ‖ȳ‖2 · ∥∥K̂−1λ · K̂ · K̂−1λ − K̂−1P,λ · K̂P · K̂−1P,λ∥∥ (iii)
≤ λ 2 ·R2 · [ ∥∥K̂−1λ · K̂ · K̂−1λ − K̂−1P,λ · K̂ · K̂−1λ ∥∥︸ ︷︷ ︸ term(C) + ∥∥K̂−1P,λ · K̂ · K̂−1λ − K̂−1P,λ · K̂P · K̂−1P,λ∥∥︸ ︷︷ ︸ term(D) ] ,
(32) where (i) follows from the definition of α̂∗ and α̂∗P along with the notation in (24) and (25); (ii) results from Cauchy-Schwartz inequality, and (iii) uses Assumption 3 and the triangle inequality. Next, we bound term(C) and term(D) in (32). First, from the definition of term(C), we have
term(C) = ∥∥K̂−1λ · K̂ · K̂−1λ − K̂−1P,λ · K̂ · K̂−1λ ∥∥ (i)≤ ∥∥K̂−1λ − K̂−1P,λ∥∥ · ∥∥K̂ · K̂−1λ ∥∥
(ii) ≤ ∥∥K̂−1λ ∥∥ · ∥∥K̂P − K̂∥∥ · ∥∥K̂−1P,λ∥∥ · ∥∥K̂ · K̂−1λ ∥∥
(iii) ≤ 1 λ2 · ∥∥K̂P − K̂∥∥
(iv)
≤ 1 N · λ2
· ∥∥KP −K∥∥,
where (i) results from the Cauchy-Schwartz inequality; (ii) utilizesA−1−B−1 = A−1(B−A)B−1 for invertible matrices A and B along with Cauchy-Schwartz inequality; (iii) uses that fact that we have ‖K̂−1λ ‖ ≤ 1/λ, ‖K̂ −1 P,λ‖ ≤ 1/λ and ‖K̂ · K̂ −1 λ ‖ ≤ 1, and (iv) results from the notation in (24). Next, we bound term(D) as
term(D) = ∥∥K̂−1P,λ ·K · K̂−1λ − K̂−1P,λ · K̂P · K̂−1P,λ∥∥ (i)≤ ∥∥K̂−1P,λ∥∥ · ∥∥K̂ · K̂−1λ − K̂P · K̂−1P,λ∥∥
(ii) ≤ λ · ∥∥K̂−1P,λ∥∥2 · ∥∥K̂P − K̂∥∥ · ∥∥K̂−1λ ∥∥
(iii) ≤ 1 λ2 · ∥∥K̂P − K̂∥∥
(iv)
≤ 1 N · λ2
· ∥∥KP −K∥∥,
where inequality (i) follows from Cauchy-Schwartz inequality; (ii) results from (28) and the application of Cauchy-Schwartz inequality; (iii) follows from the fact that we have ‖K̂−1λ ‖ ≤ 1/λ and ‖K̂−1P,λ‖ ≤ 1/λ, and (iv) results from the notation defined in (24).
Substituting the upper bounds of term(C) and term(D) in (32), we get λ
2 ∣∣∣‖α̂∗‖2K − ‖α̂∗P ‖2KP ∣∣∣ ≤ R2N · λ · ∥∥KP −K∥∥. Finally, using Lemma G.4, we have for the GIP kernel
λ
2 ∣∣∣‖α̂∗‖2K − ‖α̂∗P ‖2KP ∣∣∣ ≤ R2 ·Gλ · (√ 32π2 P log 2N δ + 8π 3P log 2N δ ) ,
Substituting, the above expression in (31) and combining with the bound in (29), we get the statement of the theorem.
Similarly, we have for the RF kernel
λ
2 ∣∣∣‖α̂∗‖2K − ‖α̂∗P ‖2KP ∣∣∣ ≤ R2 · κ2λ · (√ 8 P log 2N δ + 4 3P log 2N δ ) .
Finally, substituting the above expression in (31) and combining with the bound in (30), we get the statement of the theorem.
Therefore, the proof is complete.
Finally, the proof of Theorem 4.2 is a simple consequence of Theorem G.5.

heading: H GENERALIZATION PERFORMANCE OF MULTI-AGENT KERNEL APPROXIMATION FRAMEWORK: PROOF OF THEOREM 4.3
text: To prove generalization bounds we extensively use the notations defined in Appendix F. Definition H.1. We define by fπ as the MMSE estimator for f as
fπ(x) = Ey∼π(y|x)[y|x].
We make the following assumption. Assumption 5. There exists fH ∈ H s.t. L(fH) = infh∈H L(h). From the definition of MMSE estimator above we have fπ = fH. Moreover, this assumption implies that there exists h ∈ L2(X , πx) s.t. we have
fH(x) = (K 1/2h)(x). (33)
for some ‖h‖πx ≤ R.
Note that Assumption 5 is same as Assumption 4 in the main paper. The existence of fH ensures that (33) holds for some h ∈ L2(X , πx). Moreover, without loss of generality we assume ‖h‖πx to be bounded by R (same R as in Assumption 3).
Note that for the `2 loss defined in (11) and under Assumption 5, we have for any f ∈ L2(X , πx) (Caponnetto & De Vito, 2007)
L(f)− inf h∈H L(h) = L(f)− L(fπ) = ‖f − fπ‖2πx . (34)
Now the goal is to bound the generalization error with f replaced by the f̂P (learned by solving the approximate kernel problem stated in (13)). Using the notations defined in Appendix F, we have
f̂P = ΦP Φ̂ ∗ P [[ K̂P + λ · I ]−1 ŷ ] = ΦP Φ̂ ∗ P [[ Φ̂P Φ̂ ∗ P + λ · I ]−1 ŷ ]
= ΦP [[ Φ̂∗P Φ̂P + λ · I ]−1 Φ̂∗P ŷ ] = ΦP · Ĉ−1P,λ · Φ̂ ∗ P · ŷ.
where we have defined ŷ = 1√ N ȳ.
Using the above we have
f̂P − fπ = ΦP · Ĉ−1P,λ · Φ̂ ∗ P · ŷ − ΦP · Ĉ−1P,λ · Φ ∗ P · fπ︸ ︷︷ ︸
term(A)
(35)
+ ΦP · Ĉ−1P,λ · Φ ∗ P · fπ − ΦP · C−1P,λ · Φ ∗ P · fπ︸ ︷︷ ︸
term(B)
(36)
+ ΦP · C−1P,λ · Φ ∗ P · fπ − K ·K−1λ · fπ︸ ︷︷ ︸
term(C)
(37)
+K ·K−1λ · fπ − fπ︸ ︷︷ ︸ term(D) . (38)
Next, we bound each term separately below for both the GIP and the RF kernels. We note that for the RF kernel we follow the proofs developed in Rudi & Rosasco (2017) with some minor corrections.
Bound for term(A) First, we consider term(A) given in (35). Lemma H.1. For any δ ∈ (0, 1], with λ ≤ 34‖K‖ and N ≥ max { 72κ2 λ , 2λ 9 } log 4κ 2 λ·δ . Moreover,
with P ≥ max { 8, 512π 2G2
‖K‖2 } log 2δ for the GIP kernel and with P ≥ max { 8κ2, 32κ 2 ‖K‖2 } log 2δ for
the RF kernel, we have with probability at least 1− 3δ ‖term(A)‖πx = ∥∥ΦP · Ĉ−1P,λ · Φ̂∗P · ŷ − ΦP · Ĉ−1P,λ · Φ∗P · fπ∥∥πx ≤ 6R · κ√λ ·N log 2δ + √ 18R2 · κ2 λ ·N log 2 δ .
Proof. From the definition of term(A) in (35), we have
term(A) = ΦP · Ĉ−1P,λ · Φ̂ ∗ P · ŷ − ΦP · Ĉ−1P,λ · Φ ∗ P · fπ = ΦP · Ĉ−1P,λ · [ Φ̂∗P · ŷ − Φ∗P · fπ ] (i) = ( ΦP · Ĉ−1P,λ · C 1/2 P,λ
)︸ ︷︷ ︸ term(A1) · ( C −1/2 P,λ · [ Φ̂∗P · ŷ − Φ∗P · fπ ])︸ ︷︷ ︸ term(A2) . (39)
where (i) follows from C1/2P,λ · C −1/2 P,λ = I . Next, we individually bound term(A1) and term(A2) below.
First, we bound term(A1) using Proposition 8 in Rudi & Rosasco (2017), we define β1 := λmax [ C −1/2 P,λ · ( CP − ĈP ) · C−1/2P,λ ] ‖term(A1)‖ = ‖ΦP · Ĉ−1P,λ · C 1/2 P,λ‖ (i) ≤ ‖ΦP · Ĉ−1/2P,λ ‖ · ‖Ĉ −1/2 P,λ · C 1/2 P,λ‖
(ii)
≤ ‖Ĉ−1/2P,λ · C 1/2 P,λ‖
2 (iii) ≤ 1 1− β1 ,
where (i) utilizes the Cauchy-Schwartz inequality; (ii) follows from the fact that:
‖ΦP · Ĉ−1/2P,λ ‖ = ‖ΦP · C −1/2 P,λ ‖︸ ︷︷ ︸
≤1
·‖C1/2P,λ · Ĉ −1/2 P,λ ‖ ≤ ‖Ĉ −1/2 P,λ · C 1/2 P,λ‖,
finally, (iii) utilizes Proposition 8 in Rudi & Rosasco (2017). Next, we bound term β1. Using Lemma H.2, with the choice of λ ≤ ‖CP ‖ and with N ≥ max { 72κ2 λ , 2λ 9 } log 4κ 2 λδ , we have with
probability at least 1− δ
β1 = λmax [ C −1/2 P,λ · ( CP − ĈP ) · C−1/2P,λ ] ≤ 1
3 ,
Finally, we need to ensure that the random variable ‖CP ‖ ≥ λ with high probability for both the GIP and the RF kernel.
Note from Proposition H.7 that for: (i) the GIP kernel with P ≥ max { 8, 512π 2G2
‖K‖2 } log 2δ and (ii)
for the RF kernel with P ≥ max { 8κ2, 32κ 2
‖K‖2 } log 2δ , we have with probability at least 1− δ
‖K −KP ‖ ≤ 1
4 ‖K‖.
Next, choosing λ s.t. we have λ ≤ 34‖K‖. Note that the choice of λ and the choice of P implies that we have with probability at least 1− δ
‖CP ‖ = ‖Φ∗P · ΦP ‖ = ‖ΦP · Φ∗P ‖ = ‖KP ‖ ≥ ∣∣‖K‖ − ‖K −KP ‖∣∣ ≥ ‖K‖ − ‖K −KP ‖ ≥ 3
4 ‖K‖ ≥ λ.
Now combining the two facts that β1 ≤ 1/3 holds with probability 1− δ conditioned on ‖CP ‖ ≥ λ and ‖CP ‖ ≥ λ holds with probability at least 1− δ, it is easy to verify that we have β1 ≤ 1/3 with probability at least 1− 2δ. This further implies that we have with probability at least 1− 2δ
‖term(A1)‖ ≤ 3 2 . (40)
Next, we consider term(A2) in (39)5
term(A2) = C−1/2P,λ · [ Φ̂∗P · ŷ − Φ∗P · fπ ] = C −1/2 P,λ ·
[ 1
N N∑ i=1 ( φP (xi) · yi − Φ∗ · fπ )] 5For ease of presentation, we relabel the set {(x(i)m , y (i) m ) : ∀i ∈ Nm, ∀m ∈ [M ]} with {(xi, yi)} N i=1.
We modify Lemma 6 in Rudi & Rosasco (2017) to bound this term. First, note that the random variable φP (xi)·yi−Φ∗P ·fπ is zero mean. Next, we apply Bernstein’s inequality stated in Proposition I.2. Consider the random vector zi defined as
zi = C −1/2 P,λ · φP (xi) · yi,
with mean E[zi] = µ = C−1/2P,λ ·Φ∗L ·fπ . Note that zi are i.i.d. with the moments of random variable z = C
−1/2 L,λ · φP (x) · y bounded as
E‖zi − µ‖pHP = E‖zi − E[z]‖ p HP
(i) ≤ EzEzi‖zi − z‖ p HP (ii) ≤ 2p−1EzEzi ( ‖zi‖pHP + ‖z‖ p HP ) = 2pE‖z‖pHP ,
where (i) follows from the Jensen’s inequality and (ii) utilizes the convexity of ‖ · ‖pHP . Next, we bound E‖z‖pHP as
E‖z‖pHP = E ∥∥C−1/2P,λ · φP (x) · y∥∥pHP
(i) ≤ E [ ‖C−1/2P,λ · φP (x)‖ p HP · |y| p ] (ii) ≤ Rp · E [∥∥C−1/2P,λ · φP (x)∥∥pHP ] (iii)≤ ( R · κ√ λ )p ,
where (i) utilizes Cauchy-Schwartz inequality; (ii) follows from Assumption 3 and, (iii) results from the following∥∥C−1/2P,λ · φP (x)∥∥2HP ≤ 1λ · ‖φP (x)‖2HP = 1λ · 〈φP (x), φP (x)〉HP = 1λ · kP (x, x) ≤ κ2λ , where we utilized the definition of kP (·, ·) and Assumption 1. Combining with the above we get
E‖zi − µ‖pHP ≤ ( 2R · κ√ λ )p .
This implies that we can apply Bernstein’s inequality stated in Proposition I.2 with σ = B = 2Rκ/ √ λ, therefore, we get with probability at least 1− δ
‖term(A2)‖HP ≤ 4R · κ√ λ ·N log 2 δ + √ 8R2 · κ2 λ ·N log 2 δ . (41)
Finally, substituting the bound for term (A1) derived in (40) and the bound for term (A2) derived in (41) in (39) and noting the fact that (40) holds with probability at least 1 − 2δ and (41) holds with probability at least 1− δ, we have with probability at least 1− 3δ
‖term(A)‖πx ≤ 6R · κ√ λ ·N log 2 δ + √ 18R2 · κ2 λ ·N log 2 δ .
Therefore, the lemma is proved.
Lemma H.2. For some δ ∈ (0, 1] and with λ ≤ ‖CP ‖ we have with probability at least 1− δ
λmax [ C −1/2 P,λ · ( CP − ĈP ) · C−1/2P,λ ] ≤ 2
3N log
4κ2 λ · δ +
√ 2κ2
λ ·N log
4κ2 λ · δ .
Proof. The proof follows from Proposition 6 in Rudi & Rosasco (2017).
Next, we bound term(B).
Bound for term(B) Let us consider term(B) in (36), we have Lemma H.3. For δ ∈ (0, 1], with P ≥ max { 8, 288π 2G2
λ2 } log 2δ for the GIP kernel and with
P ≥ max {
2λ 9 ,
72κ2
λ
} log 4κ 2
λ·δ for the RF kernel, we have with probability at least 1− 4δ
‖term(B)‖πx = ∥∥ΦP · Ĉ−1P,λ · Φ∗P · fπ − ΦP · C−1P,λ · Φ∗P · fπ∥∥ ≤ 12R · κ2√
λ ·N log
2 δ + √ 36R2 · κ4 λ ·N log 2 δ .
Proof. Consider term(B), note that from Lemma 3 in Rudi & Rosasco (2017), we have ‖term(B)‖πx = ∥∥ΦP · Ĉ−1P,λ · Φ∗P · fπ − ΦP · C−1P,λ · Φ∗P · fπ∥∥πx
≤ R · ∥∥K−1/2P,λ ·K1/2∥∥︸ ︷︷ ︸
term(B1)
· ∥∥ΦP · Ĉ−1P,λ · C1/2P,λ∥∥︸ ︷︷ ︸
term(B2)
· ∥∥C−1/2P,λ · (CP − ĈP )∥∥︸ ︷︷ ︸
term(B3)
. (42)
Next, we bound each term individually. First, we consider term(B1) in (42) above, we define β2 := λmax [ K −1/2 λ · ( K−KP ) ·K−1/2λ ] , then we have
‖term(B1)‖ = ∥∥K−1/2P,λ ·K1/2∥∥ (i)≤ ∥∥K−1/2P,λ ·K1/2λ ∥∥ (ii)≤ ( 11− β2 )1/2 ,
where (i) follows from the fact that ‖K1/2‖ ≤ ‖K1/2λ ‖ and (ii) utilizes Proposition 8 in Rudi & Rosasco (2017). Note that from Lemma H.4 for (i) the GIP kernel with P ≥ max { 8, 288π 2G2
λ2 } log 2δ and for (ii) the RF kernel with P ≥ max { 2λ 9 , 72κ2 λ } log 4κ 2
λ·δ , we have with probability at least 1− δ
β2 ≤ 1
3 .
This implies that with probability at least 1− δ, we have ‖term(B1)‖ ≤ 2. (43)
Next, note from the definition of term(B2) in (42) that it is same as term(A1) in (39). Therefore, using the same bound as derived in (40), we have with probability at least 1− 2δ
‖term(B2)‖ ≤ 3 2 . (44)
Next, we bound term(B3) in (42). Using Equation (28) of Lemma 7 in Rudi & Rosasco (2017), we have with probability at least 1− δ
‖term(B3)‖ ≤ 4κ 2
√ λ ·N
log 2
δ +
√ 4κ4
λ ·N log
2 δ . (45)
Finally, substituting the bounds derived in (43), (44) and (45) in (42) and utilizing the fact that (43) holds with probability at least 1− δ, (44) holds with probability at least 1− 2δ and (45) holds with probability at least 1− δ, we get with probability at least 1− 4δ
‖term(B)‖πx ≤ 12R · κ2√ λ ·N log 2 δ + √ 36R2 · κ4 λ ·N log 2 δ .
Therefore, the lemma is proved.
Lemma H.4. For some δ ∈ (0, 1], then with probability at least 1− δ for
1. We have for the GIP kernel
λmax [ K −1/2 λ · ( K −KP ) ·K−1/2λ ] ≤ 8π ·G
λ · P log
2 δ + √ 8π2 ·G2 λ2 · P log 2 δ .
2. We have for the RF kernel (Proposition 6 in Rudi & Rosasco (2017))
λmax [ K −1/2 λ · ( K −KP ) ·K−1/2λ ] ≤ 2
3P log
4κ2 λ · δ +
√ 2κ2
λ · P log
4κ2 λ · δ .
Proof. For the GIP kernel, we have λmax [ K −1/2 λ · ( K −KP ) ·K−1/2λ ] (i) ≤ ‖K−1/2λ · ( K −KP ) ·K−1/2λ ‖ (ii)
≤ 1 λ · ‖K −KP ‖.
where (i) follows from the definition of the operator norm and (ii) uses the fact that ‖K−1/2λ ‖ ≤ 1/ √ λ. Next, utilizing the bound for ‖K − KP ‖ from Proposition H.7, we have the proof of the lemma.
Next, we consider term(C).
Bound for term(C) We consider term(C) in (37). Lemma H.5. For δ ∈ (0, 1], with probability at least 1− δ
1. For the GIP kernel, we have
‖term(C)‖πx = ∥∥ΦP · C−1P,λ · Φ∗P · fπ−K ·K−1λ · fπ∥∥ ≤ 8πR ·G√
λ · P log
2 δ +
√ 8π2R2 ·G2
λ · P log
2 δ .
2. For the RF kernel, with P ≥ max {
2λ 9 ,
72κ2
λ
} log 4κ 2
λ·δ we have from Lemma 8 in Rudi & Rosasco (2017)
‖term(C)‖πx = ∥∥ΦP · C−1P,λ · Φ∗P · fπ −K ·K−1λ · fπ∥∥
≤ 4R · (λ+ κ 2)
3 √ λ · P
log 16κ2
λ · δ +
√ 8R2 · κ2
P log
16κ2 λ · δ .
Proof. Let us consider the first term of term(C) for the GIP kernel, we have from the definition of CP,λ
ΦP · C−1P,λ · Φ ∗ P · fπ = ΦP · ( CP + λI )−1 · Φ∗P · fπ (i)= ΦP · (Φ∗P · ΦP + λ · I)−1 · Φ∗P · fπ (ii) = ΦP · Φ∗P · ( ΦP · Φ∗P + λ · I
)−1 · fπ (iii)= KP · (KP + λ · I)−1 · fπ (iv)= KP ·K−1P,λ · fπ where (i) follows from the definition of CP ; (ii) uses the fact that for any continuous spectral function and compact operator Z, we have F (Z∗Z)Z∗ = Z∗F (ZZ∗); (iii) uses the definition of KP and finally, (iv) results from the notation of KP,λ. Therefore, we have
term(C) = KP ·K−1P,λ · fπ −K ·K −1 λ · fπ = ( KP ·K−1P,λ −K ·K −1 λ ) · fπ
(i) = λ · ( K−1P,λ −K −1 λ ) · fπ
(ii) = λ ·K−1P,λ ( K −KP ) K−1λ · fπ
(iii) = λ ·K−1P,λ · ( K −KP ) ·K−1λ ·K 1/2 · h
= ( λ ·K−1P,λ ) · ( K −KP ) ·K−1/2λ · ( K −1/2 λ ·K 1/2 ) · h
where (i) uses the identityA ·(A+λ ·I)−1 = I−λ(A+λ ·I)−1 for bounded positive operators; (ii) results from A−1−B−1 = A−1 · (B−A) ·B−1 for invertible bounded positive operators, and (iii) utilizes Assumption 5. Taking the norm on both sides and utilizing Cauchy-Schwartz inequality, we get ‖term(C)‖πx ≤ ∥∥λ ·K−1P,λ∥∥ · ∥∥K −KP∥∥ · ∥∥K−1/2λ ∥∥ · ∥∥K−1/2λ K1/2∥∥ · ‖h‖πx ≤ R√
λ · ‖K −KP ‖,
where the last inequality follows from ∥∥λ ·K−1P,λ∥∥ ≤ 1, ∥∥K−1/2λ ∥∥ ≤ 1/√λ, ∥∥K−1/2λ ·K1/2∥∥ ≤ 1 and ‖h‖πx ≤ R from Assumption 5. Finally, using Proposition H.7 we have for the generalized inner-product kernel with probability at least 1− δ
‖term(C)‖πx ≤ 8πR ·G√ λ · P log 2 δ +
√ 8π2R2 ·G2
λ · P log
2 δ .
Therefore, the lemma is proved.
Let us next consider term(D).
Bound for term(D) We consider term(D) in equation 38.
Lemma H.6. We have
‖term(D)‖πx = ‖K ·K−1λ · fπ − fπ‖πx ≤ R · √ λ.
Proof. We have term(D) = K ·K−1λ · fπ − fπ = ( K ·K−1λ − I ) · fπ
(i) = −λ ·K−1λ · fπ (ii) = −λ ·K−1λ ·K 1/2 · h = − ( λ ·K−1/2λ ) · ( K −1/2 λ ·K 1/2 ) · h,
where (i) uses the identityA · (A+λ ·I)−1 = I−λ(A+λ ·I)−1 and (ii) follows from Assumption 4. Taking the norm on both sides and applying Cauchy-Schwartz inequality, we get
‖term(D)‖πx ≤ ∥∥λ ·K−1/2λ ∥∥ · ∥∥K−1/2λ ·K1/2∥∥ · ‖h‖πx ≤ R · √λ,
where the last inequality results from ‖λ1/2 ·K−1/2λ ‖ ≤ 1, ‖K −1/2 λ ·K1/2‖ ≤ 1 and ‖h‖πx ≤ R follows from Assumption 5.
Next, we combine the four terms to bound ‖f̂P − fπ‖πx . Proposition H.7. The following holds with probability at least 1− δ
1. For the GIP kernel, we have
‖K −KP ‖ ≤ 8πG
P log
2 δ +
√ 8π2G2
P log
2 δ .
2. For the RF kernel, we have
‖K −KP ‖ ≤ 4κ2
P log
2 δ +
√ 2κ2
P log
2 δ .
Proof. We first prove (i), note from the definition of K −KP and the norm in L2(X , πx)-space we have
‖K −KP ‖ = sup ‖h‖πx=1 ∥∥∥∫ z∈X ( k(x, z)− kP (x, z) ) h(z)dπz ∥∥∥ πx
= sup ‖h‖πx=1 ∥∥∥∫ z∈X ( g(ψ(x, z), ‖x‖, ‖z‖)− g(ψP (x, z), ‖x‖, ‖z‖) ) h(z)dπz ∥∥∥ πx
= sup ‖h‖πx=1 ∥∥∥∫ z∈X ∣∣g(ψ(x, z), ‖x‖, ‖z‖)− g(ψP (x, z), ‖x‖, ‖z‖)∣∣h(z)dπz∥∥∥ πx
≤ G sup ‖h‖πx=1 ∥∥∥ ∫ z∈X ∣∣ψ(x, z)− ψP (x, z)∣∣h(z)dπz∥∥∥ πx
Recall using ζ(x, ω) = 1[ωTx ≥ 0] for the GIP kernel, we have from the definition of ψ(x, z) and ψP (x, z)
ψ(x, z) = ∣∣∣∣π − 2πE[ζ(x, ω)ζ(z, ω)]∣∣∣∣ and ψP (x, z) = ∣∣∣∣π − 2πP P∑ `=1 ζ(x, ω`)ζ(z, ω`) ∣∣∣∣.
Substituting in the above, we get
‖K −KP ‖
≤ G sup ‖h‖πx=1 ∥∥∥∥∥ ∫ z∈X ∣∣∣∣∣∣∣∣π − 2πE[ζ(x, ω) · ζ(z, ω)]∣∣∣− ∣∣∣π − 2πP P∑ `=1 ζ(x, ω`) · ζ(z, ω`) ∣∣∣∣∣∣∣∣ · h(z)dπz ∥∥∥∥∥ πx
≤ 2πG sup ‖h‖πx=1 ∥∥∥∥∥ ∫ z∈X ∣∣∣∣E[ζ(x, ω) · ζ(z, ω)]− 1P P∑ `=1 ζ(x, ω`) · ζ(z, ω`) ∣∣∣∣ · h(z)dπz ∥∥∥∥∥ πx
= 2πG sup ‖h‖πx=1 ∥∥∥∥∥ ∫ z∈X ( E [ ζ(x, ω) · ζ(z, ω) ] − 1 P P∑ `=1 ζ(x, ω`) · ζ(z, ω`) ) · h(z)dπz ∥∥∥∥∥ πx
= 2πG · ∥∥Ω− ΩP∥∥
≤ 2πG · ∥∥Ω− ΩP∥∥HS .
Finally, we bound ∥∥Ω − ΩP∥∥ using Proposition I.2. Using the notation ζω` = ζ(·, ω`), we define the random variable Θ` = Ω− ζω` ⊗ ζω` , this implies that from the definition of Ω− ΩP , we have from Lemma 1 in Rudi & Rosasco (2017)
1
P P∑ `=1 Θ` = Ω− ΩP with E[Θ`] = 0 ∀` ∈ [P ].
Next, note that Θ` are random vectors belonging to the Hilbert space of Hilbert-Schmidt operators on L2(X , πx). Therefore, we can apply Proposition I.2. Moreover, from the definition of Ω and ΩP , ‖Ω− ζω` ⊗ ζω`‖HS ≤ 2 and E‖Θ`‖2HS ≤ 1. Therefore, from the application of Proposition I.2, we have with probability at least 1− δ
‖Ω− ΩP ‖HS ≤ 4
P log
2 δ +
√ 2
P log
2 δ .
Substituting in the expression above we get the result of statement (i).
The proof of (ii) follows from Lemma 9 in Rudi & Rosasco (2017).
Combining bounds on term(A), term(B), term(C) and term(D) Here, we combine the results of Lemmas H.1, H.3, H.5 and H.6 to bound ‖f̂P − fπ‖πx . We get the following theorem. Theorem H.8. For the two classes of kernels with λ ≤ 34‖K‖, the following is satisfied with probability at least 1− δ
1. For the GIP kernel, with
N ≥ max {72κ2
λ ,
2λ
9
} log 32κ2
λ · δ and with
P ≥ max { 8, 512π2G2
‖K‖2 ,
288π2G2
λ2
} log 16
δ ,
we have ‖f̂P − fπ‖πx ≤ √
216R2 · κ4 λ ·N log 16 δ +
√ 32π2R2 ·G2
λ · P log
16
δ +R ·
√ λ.
2. For the RF kernel, with
N ≥ max {72κ2
λ ,
2λ
9
} log 32κ2
λ · δ and with P ≥ max { 8κ2, 32κ2
‖K‖2 ,
2λ
9 ,
72κ2
λ ,
2(λ+ κ2)2
9κ2
} log 128κ2
λ · δ ,
we have ‖f̂P − fπ‖πx ≤ √
216R2 · κ4 λ ·N log 16 δ +
√ 32R2 · κ2
P log
128κ2
λ · δ +R ·
√ λ.
Finally, using the above Theorem H.8 and (34), we bound the generalization error. Theorem H.9. For the two classes of kernels with λ ≤ 34‖K‖, the following is satisfied with probability at least 1− δ
1. For the GIP kernel, with
N ≥ max {72κ2
λ ,
2λ
9
} log 32κ2
λ · δ and with
P ≥ max { 8, 512π2G2
‖K‖2 ,
288π2G2
λ2
} log 16
δ ,
we have
L(f)− inf h∈H L(h) ≤ 648R
2 · κ4
λ ·N log
16
δ +
96π2R2 ·G2
λ · P log
16
δ + 3R2 · λ.
2. For the RF kernel, with
N ≥ max {72κ2
λ ,
2λ
9
} log 32κ2
λ · δ and with P ≥ max { 8κ2, 32κ2
‖K‖2 ,
2λ
9 ,
72κ2
λ ,
2(λ+ κ2)2
9κ2
} log 128κ2
λ · δ ,
we have
L(f)− inf h∈H L(h) ≤ 648R
2 · κ4
λ ·N log
16
δ +
96R2 · κ2
P log
128κ2
λ · δ + 3R2 · λ.
Finally, we choose the parameters to get the result of Theorem 4.3.
Choosing parameters: Here, we optimally choose the parameters λ, P , N such that all the conditions in Theorem H.8 and H.9 are satisfied and the proposed approximation approach achieves the (minimax) optimal generalization performance.
• GIP kernel: For the GIP kernel, we choose the parameters as follows: – Regularization parameter: λ = 1/ √ N .
– Number of overall samples: N ≥ max { 4
3‖K‖2 , 72κ2 ·
√ N · log 32κ
2 · √ N
δ } – Number of bits communicated:
P ≥ max { 8, 512π2G2
‖K‖2 , 288π2G2 ·N
} log 16
δ
• RF kernel: For the RF kernel we choose the parameters as follows: – Regularization parameter: λ = 1/ √ N .
– Number of overall samples: N ≥ max { 4
3‖K‖2 , 72κ2 ·
√ N · log 32κ
2 · √ N
δ } – Number of real values communicated:
P ≥ max { 8κ2, 32κ2
‖K‖2 , 72κ2 ·
√ N } log 128κ2 · √ N
δ
Now with the above choice of parameters we have Theorem 4.3 stated beolw. Theorem H.10. With the choice of parameters stated above, we have with probability at least 1− δ for both the GIP and RF kernels that
L(f)− inf h∈H L(h) = O ( 1√ N ) .

heading: I CONCENTRATION INEQUALITIES
text: Proposition I.1. For x1, . . . , xN , a sequence of zero-mean i.i.d. random variables with xi ∈ R for all i ∈ [N ]. If there exists T, S ∈ R s.t. xi ≤ T a.s. and Ex2i ≤ S for all i ∈ [N ]. Then with probability at least 1− δ we have
1
N N∑ i=1 xi ≤ 2T log 1δ 3N + √ 2S log 1δ N .
Proposition I.2. For x1, . . . , xN , a sequence of i.i.d. random vectors on a separable Hilbert space H. Assume µ = Exi and let σ,B ≥ 0 s.t.
E‖xi − µ‖pH ≤ 1 2 p!σ2Bp−2 ∀p ≥ 2,
for any i ∈ [N ]. Then we have with probability at least 1− δ∥∥∥∥ 1N N∑ i=1 xi − µ ∥∥∥∥ H ≤ 2B log 2δ N + √ 2σ2 log 2δ N . Proposition I.3. Let F be a separable Hilbert space and let X1, . . . , XN be a sequence of i.i.d. self-adjoint positive random operators on F . Assume that E[Xi] = 0 and λmax(Xi) ≤ T a.s. for some T > 0 for all i ∈ [N ]. Let S be such that E(Xi)2 ≤ S. Then with probability at least 1 − δ we have
λmax
( 1
N N∑ i=1 Xi ) ≤ 2Tβ 3N + √ 2‖S‖β N ,
with β = log 2TrS‖S‖·δ .

heading: J SUFFICIENT CONDITION FOR POSITIVE DEFINITE GIP KERNEL
text: Assumption 6. We assume that there exists a mapping from {xi, . . . , xN} 7→ {x̃i, . . . , x̃N} with xi ∈ Rd and x̃i ∈ RD for some D ∈ N such that the following is satisfied:
1. ‖x̃i‖ = ‖xi‖ for all i ∈ [N ].
2. ψ(x̃i, x̃j) = ψP (xi, xj) for all i, j ∈ [N ] where ψP (xi, xj) is defined in (8).
The above assumption implies that there exists a mapping that transforms the feature vectors such that their norms are preserved and the pairwise angles between the transformed set of vectors are same as the approximated angles for the GIP kernel (cf. (8)). Proposition J.1. Under Assumption 6, the kernel KP approximated using (7) for the GIP kernel is positive semi-definite.
Proof. From the definition of the approximated GIP kernel (7) and Assumption 6, we have kP (xi, xj) = g(ψP (xi, xj), ‖xi‖, ‖xj‖) = g(ψP (x̃i, x̃j), ‖x̃i‖, ‖xj‖) = k(x̃i, x̃j).
Using the above fact, we have for the approximated GIP kernel for any vector v ∈ RN
vTKP v = N∑ i,j=1 [v]i[v]jkP (xi, xj)
= N∑ i,j=1 [v]i[v]jk(x̃i, x̃j)
(i) = 〈 N∑ i=1 [v]iφ(xi), N∑ j=1 [v]jφ(xj) 〉
= ∥∥∥∥ N∑ i=1 [v]iφ(xi) ∥∥∥∥ ≥ 0,
where (i) follows from Mercer’s theorem, i.e., for positive definite kernel k, there exists φ(·) such that k(xi, xj) = 〈φ(xi), φ(xj)〉. Moreover, we used the fact that the GIP kernel k is well defined irrespective of the dimension of the feature vectors.
Therefore, we have the proof.

Review summaries:
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.

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.

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.