Supervised Kernel Thinning
Authors: Albert Gong
Kyuseong Choi
Raaz Dwivedi
Venue: NeurIPS 2024 poster (2024)
Keywords: Kernel methods
distribution compression
non-parametric regression
Primary area: learning_theory
TL;DR: We apply recent advances in distribution compression (Kernel Thinning) to speed up kernel smoothing and kernel ridge regression.

Abstract: The kernel thinning algorithm of Dwivedi & Mackey (2024) provides a better-than-i.i.d. compression of a generic set of points. By generating high-fidelity coresets of size significantly smaller than the input points, KT is known to speed up unsupervised tasks like Monte Carlo integration, uncertainty quantification, and non-parametric hypothesis testing, with minimal loss in statistical accuracy. In this work, we generalize the KT algorithm to speed up supervised learning problems involving kernel methods. 
Specifically, we combine two classical algorithms---Nadaraya-Watson (NW) regression or kernel smoothing, and kernel ridge regression (KRR)---with KT to provide a quadratic speed-up in both training and inference times. We show how distribution compression with KT in each setting reduces to constructing an appropriate kernel, and introduce the Kernel-Thinned NW and Kernel-Thinned KRR estimators. We prove that KT-based regression estimators enjoy significantly superior computational efficiency over the full-data estimators and improved statistical efficiency over i.i.d. subsampling of the training data. En route, we also provide a novel multiplicative error guarantee for compressing with KT.  We validate our design choices with both simulations and real data experiments.

Supervised Kernel Thinning
Albert Gong
Kyuseong Choi
Raaz Dwivedi
Cornell Tech, Cornell University
agong, wet.k:k22,,,iiieeee dwivedi @cornell.
Abstract
The kernel thinning algorithm of [10] provides a better-than-i..dd compression generic set of points. By generating high-fidelity coresets of size significantly smaller than the input points, KT is known to speed up unsupervised tasks like Monte Carlo integration, uncertainty quantification, and non-parametric hypothesis testing, with minimal loss in statistical accuracy. In this work, we generalize the KT algorithm to speed up supervised learning problems involving kernel methods. Specifically, we combine two classical (NW) regression or kernel smoothing, and kernel ridge regression (KRR)-with KT to provide quadratic speed-up in both training and inference times. We show how distribution compression with KT in each setting reduces to constructing an appropriate kernel, and introduce the Kernel-Thee Thinned NW and Kernel- Thinned KRR estimators. We prove that KT-based regression estimators enjoy significantly superior computational efficiency over the full-data estimators and improved statistical efficiency over i.i.d. subsampling of the training data. En route, we also provide novel multiplicative error guarantee for compressing with KT. We validate our design choices with both simulations and real data experiments.
Saatttmms-Ndarayaaa Mattarrayaaatoonnn Watson
Introduction
In supervised learning, the goal of coreset methods is to find representative set of points on which to perform model training and inference. On the other hand, coreset methods in unsupervised learning have the goal of finding representative set of points, which can then be utilized for a broad class of downstream tasks-fron integration [10, 9] to non-parametric hypothesis testing [8]. This work aims to bridge these two research threads.
Leveraging recent advancements from compression in the unsupervised setting, we tackle the problem of non -oraamemtt regression (formally defined in Sec. 2). Given dataset of n i.i.d. samples, (rr, y:) we want learn a function f such that f((x:) As y/s- The set of allowable functions is determined by the kernel function, which is powerful building block for capturing complex, non-linear relationships. Due its powerful performance in practice and closed-form analysis, non-parametric regression methods based on kernels (a.k.a "kernel methods") have become popular choice for a wide range of supervised learning tasks [13, 20, 24].
There are two popular approaches to non-parametric kernel regression. First, perhaps a more classical approach, kernel smoothing, also referred as Nadaraya- Watson (NW) regression. The NW estimator at a point is effectively smoothing of labels yı such that is close to æ. These weights are computed using the kernel function (see Sec. 2 for formal definitions). Importantly, the NW estimator takes (n) pre- nre-processing time (to simply store the data) and ((n) inference time for each test point x (n kernel evaluations and n simple operations).
Another popular approach is kernel ridge regression (KRR), which solves a non- con-paraettric least squares subject to the regression function lying the reproducing kernel Hilbert space (RKHS) of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

specified reproducing kernel function. Remarkably, KRR admits closed-form solution via inverting the associated kernel matrix, and takes (n training time and (n)) inference time for each test point x.
Our goal is to overcome the computational bottlenecks of kernel methods, while retaining their favorable statistical properties. Previous attempts at using coreset methods include the work of Boutsidis et al. [4], Zheng and Phillips [32]. Phillips [18], which depend on a projection type compression, having similar spirit to the celebrated
lemma, metric preserving projection result. So accuracy and running depend unfavorably on the desired statistical error rate. Kpotufe [14] propose algorithm reduce the query time of the NW estimator to Olog n). but the algorithm requires super-linear preprocessing time.
Other lines of work exploit the structure of kernels more directly, especially in the KRR literature. slew of techniques from numerical analysis have been developed, including work on Nyström subsampling by El Alaoui and Mahoney [11], Avron et al. [1], Díaz et al. [7]. Camoriano et al. [5] and Rudi et al. [22] combine early stopping with Nyström subsampling. Though more distant from approach, also note the approach of Rahimi and Recht [21] using random features, Zhang et al. [31 I] using Divide-and- Seide-and-Conquee Conquer, and Tu et al. [28] using block coordinate descent.
Our contributions. In this work, we show how coresct methods can be used to speed up both training and inference in non- man-paraettric regression for a large class of function classes/kernels. At the heart of these algorithms is general procedure called kernel thinning [10, 9]. which provides a worst-case bound on integration error (suited for problems in the original context of unsupervised learning and MCMC simulations). In Sec. 3, we introduce meta-algorithm that recovers our two thinned non-paramen non-parametric regression methods each based on NW and KRR. We introduce the kernel-thinned Nadaraya- Wattson estimator (KT-NW) and the kernel-thinned kernel ridge regression estimator
We show that KT-NWW requires (n log 12) time during training and (VT)) time at inference, while achieving a mean square error (MSE) rate of n स (Thm. I)-a a strict improvement over uniform subsampling of the original input points. We show that KT-KRR requires ((n3/2) time during training and and O( time during inference, while achieving an near-minimax optimal rate of m mog n when the kernel has finite dimension (Thm. 2). We show how our KT- KRRR guarantees can setting (Thm. 3). In Sec. 5, we apply our proposed methods to both simulated and worldworld data. In line with our theory, KT-NW and KT-KRR outperform standard thinning baselines in terms of accuracy while retaining favorable runtimes.
also be extended to the
Problem setup
We now formally describe the non parametric regression problem. Let Z1...., be i.i.d. samples from the data distribution P (with density p) over the domain X' C Bdd and Wi,..., Wn be i.i.d. samples from (0, 1). In the sequel, we use || || to denote the Euclidean norm unless otherwise stated. Then define the response variables yı,... Yn by the follow data generating process:
y4 P (x,) + for i= 1,2,.....
(I)
where f* X' + R is the regression function and v; 2 ow, for some noise level 0. Our task is to build an estimate for f" given the n observed points, denoted by
Sin ((11,)),...,, 3n)).
Nadaraya- Aadaraya-Watson Watson (NW) estimator. A classical approach to estimate the function f* is kernel smoothing, where one estimates the function value at point 2 using a weighted average of the observed outcomes. The weight for outcome y; depends on how close x; is the point 2; let K Rd + Ie denote this weighting function such that the weight for x; is proportional to <(||>; - =lI/h) for some bandwidth parameter h > 0. Let k Rd x R + IR denote a shift-invariant kernel defined as
k(m,, <[|1=] x22 1//).
Then this smoothing estimator, also known as Nadaraya- Watson (NW) estimator, can be expressed as
F(.) A > [(mnes. k(.,z)
(2)
Eves,, k(,
2

---

whenever the denominator in the above display is non-zero. In the case the denominator in (2) is zero, we can make a default choice, which for simplicity here we choose as zero. We refer to the estimator (2) as FULL-NW estimator hereafter. One can easily note that FULL-NW requires (n)) storage for the imput points and (n) kernel queries for inference at each point.
Kernel ridge regression (KRR) estimator. Another popular approach estimate f* is that of non-pane con-parmmetri (regularized) least squares. The solution in this approach, often called as the kernel ridge regression (KRR), is obtained by solving least squares objective where the fitted function is posited to lie in the RKHS H of a reproducing kernel k, and regularization term is added to the objective to avoid overfitting. Overall, the KRR estimate is the solution the following regularized least-squares objective, where À > 0 denotes a regularization hyperparameter:
min L.... + >llflik where FEN
L
Σ (s.y)eS..
(f(x) y)²
(3)
T2
Like NW, an advantage of KRR is the existence of a closed-form solution
(-)
Σ a,k(,,;;)
where
(4)
y/1
2 (K + mAL
ER" and K 21(1,, E R
(5)
Notably, the estimate frull, which we refer to the FULL-KRR estimator, can also be seen as yet another instance of weighted average of the observed outcomes. Notably, NW estimator imposes that the weights across the points sum to 1 (and are also non-negative whenever k is), KRR allows generic weights that need not positive (even when is) and need not sum 1. We note that naïvely solving ftul,A requires (n²)) kernel evaluations to compute the kernel matrix, O(n²) to compute matrix inverse, and (nn) kernel queries for inference at each point. One of our primary goals in this work is to tackle this high computational cost FULL-KRR.
Speeding up non-parametric regression
We begin with general approach to speed up regression by thinning the input datasets. While computationally superior, generic approach suffers from a loss statistical accuracy motivating the need for strategic thinning approach. To that end, briefly review kernel thinning and finally introduced our supervised kernel thinning approach.
3.1 Thinned regression estimators: Computational and statistical tradeoffs
Our generic approach comprises two main steps. First, we compress the input data by choosing a coreset Sont C Sin of size Nout A Soutl- Second, we apply our off-the-shelf non-parametric regression methods from Sec. 2 the compressed data. By setting nout n, can obtain notable speed-ups over the FULL versions of NW and KRR.
Before introduce the thinned versions of NW and KRR, let define the following notation. Given an input sequence Sin and output sequence Sout. define the empirical probability measures
P
)(m,)) and Qout
8(2.9))
(6)
Tout
(Z.
(x.u)
Thinned NW estimator. The thinned NW estimator is the analog of Full-NW except that S,, is replaced by Sout in (2) so that the thinned-NW estimator is given by
Ps.. (.) E(E,)ss.... k(.,z)y
Qoa()))
Exssmm. k(.,
Qoak
'We note that while KRR approach (14) does require k to be reproducing, the NW approach (2) in full generality is valid when k not valid reproducing kemel.
3

---

whenever the denominator in the display is not zero; and 0 otherwise. When compared to the FULL-NW estimator, we can easily deduce the computational advantage of this estimator: more efficient (Nout) storage as well the faster (nout) computation for inference at each point.
Thinned KRR estimator. Similarly, we can define the thinned KRR estimator as
()) Σ a,k(; where
(8)
ví
a' 2 (K' + nout X'Rous)
Roui
and
K' A 2 E RR XBout
Inous
given some regularization parameter X > 0. When compared to FULL-KRR, fSome has training time ( and prediction time ((nout).
A baseline approach is standard thinning, whereby we let Sout be an i.i.. sample of Rout = v points from Sm- For NW, let call the resulting fs.... (7) the standard thirnde Nadaraya- Watson (ST-NW) estimator. When Yuu Vn, ST-NW achieves an excess risk rate of O 2F4d compared to the FULL-NW rate of O 2212). For KRR, us call the resulting fs... (8) the standard-thinned KRR (ST-KRR) estimator. When Rout vn, ST-KRR achieves excess risk rate of O _ "ouu
compared to the FULL-KRR rate of O m Our goal is provide good computational benefits without trading off statistical error. Moreover, we may be able to do better by leveraging the underlying geometry of the input points and summarize of the input distribution more succinctly than i..dd sampling.
3.2 Background on kernel thinning
A subroutine central to our approach is kemne thinning (KT) from Dwivedi and Mackey [10, Alg. 1]. We use a variant called KT-COMPRESS++ from Shetty et al. [23, Ex. 6] (see full details in App. A), which provides similar approximation quality the original KT algorithm of Dwivedi and Mackey [10, Alg. 1J, while reducing the runtime from Onn²) Onn log n). Given an input kernel kxto and input points Sjn. KT- KTTCOMPRESS++ outputs coreset SKT Sin with size nout & /n & In this work, we leverage two guarantees KT-COMPRESS++. Informally, SKT satisfies (with high probability):
Vdl log Nont
(T bound)
[[(Pi - Qom KAnallos S Oi
(9)
Nout
(Pin -ou s C22 Vog Nout log Nu... (B2(PRi))
/out
(MMD bound)
sup [ 21
(10)
nout
where C1, > are constants that depend on the properties the input kernel KALG and the chosen failure probability of KT- CT-COMPRRSS++, Ri, characterizes the radius of {x,) and
Nk... (BR.... 1/ 1/nout) denotes the kernel covering number of H((AAL) over the ball B, (RR,.) C Rd specified tolerance (see Sec. 4.2 for formal definitions).
At its highest level, KT provides good approximation of function averages. The bound (9) (formally stated in Lem. 1) controls the worst-case point-wise error, and is near-minimax optimal by Phillips and Tai [19, Thm. 3. In the sequel, we leverage this type of result to derive generalization bounds for the kernel smoothing problem. The bound (10) (formally stated in Lem. 2) controls the integration error of functions in (KALG) and is near- minimax optimal by Tolstikhin et al. [26, Thm. 1, 6]. In the sequel, we leverage this type of result derive generalization bounds for the KRR problem.
"In the sequel, we use "KT" and "KT- NKT-COMPRESS+++ interchangeably since the underlying algorithm (kemel halving [10, Alg. la]) and associated approximation g guarantees the same up small constant factors.

---

3.3 Supervised kernel thinning
We show how the approximation results from kernel thinning can be extended to the regression setting. We construct two meta-kemels, the Nadaraya-Watte Watson meta-kemnl kyw and the ridge-regression meta-kernel KRR, which take in base kernel k (defined over &' only) and return a new kernel (defined over x y). When running KT, we set this new kernel as KALG-
3.3.1 Kernel-thinned Nadaraya- Cadaraya-Watson regression (KT-NW)
tempting choice of kernel for KT-NW is the kernel itself. That is, we can thin the input points using the kernel
KALO (211,1)) (12, A k(x1,
(II)
This choice is sub-optimal since it ignores any information in the response variable y. For our supervised learning set-up, perhaps another intuitive choice would be to use KT with
KALo ((11, (æ2, v2)) k((11, (22, U2)),
(12)
where (z, y) denotes the concatenation of and y. While this helps improve performance, there remains better option we illustrate next.
In fact, a simple but critical observation immediately reveals a superior choice the kernel to be used in KT for NW estimator. We can directly observe that the NW estimator is ratio of the averages of two functions:
fnumer v-) A k(r, (y,, 1)R
and
fdenom (-) & k(x,
over the empirical distribution Pin (6). Recall that KT provides a good approximation of sample means of functions an RKHS, so it suffices to specify a "correct" choice of the RKHS (or equivalently "correct" choice of the reproducing kernel). We can verify that Sdenom lies in the RKHS associated
with kernel k(r1, x2) and fnmeer lies in the RKHS associated with kernel k k(#1, 911/2 This motivates our definition for the Nadaraya- Wataon kernel:
U2)) kNw (121, yr), (2)) k(T1, 22) + k(21, x22 V/3/2
(13)
since then we do have Stenoms Jaumer E H(KNW) Intuitively, thinning with KRR should simultaneously provide good approximation of averages of faenom and foumer over Pi (see the formal argument in Sec. 4.1). When Sout = STT-COMPRES+++(Sm.. kNw, o), we call the resulting
solution to (7) the kernel-thinned Nadaraya- Watson (KT-NW) estimator, denoted by frT.
As we show in Fig. (a)), this theoretically principled choice does provide practical benefits in MSE performance across sample sizes.
Mean Squared Error
Mi @vp.0e bov(tm Onuasil
Moon Squared Error
Weli @xs de (ssi)) Ieee (eurs))
2-2
2
2
210
214
Input sample size
Input sample size
(a) NW ablation with (en base kernel
(b) KRR ablation with Gaussian base kernel
Figure 1: MSE vs choice of kernels. For exact settings and further discussion see Sec. 5.1.
5

---

3.3.2 Kernel-thinned kernel ridge regression (KT-KRR)
While with NW estimator, the closed-form expression was ratio of averages, the KRR estimate (4) can not be expressed as an easy function of averages. However, notice that Ls.., in (3) is an average of the function Ey X y IR defined
(z v) f(x) 2f(r))++) +2 for f H(k).
Thus, there may be hope of deriving a KT-powered KRR estimator by thinning Ls.,, with the appropriate kernel. Assuming f E H(k),
verify that f lies in the RKHS associated with kernel k2 (z1, 22) and that (z) lies in the RKHS associated with kernel k(æ1, x2) 9132. We
now define the ridge regression kernel by
KRR (x11 v1), (22, v2)) & k2 (21, 12) + k(T1, 222 9192
(14)
and we can verify that f(x) 2x(x) lies in the RKHS H((RR).² When Sout & CTT-COMPRESS++($.. KRR, 5), we call the resulting solution to (8) the kernel-thinned KRR (KT- KRR) estimator with regularization parameter > 0, denoted fKT, We note that the kernel KRR also appears in [12, Lem. 4], except our subsequent analysis comes with generalization bounds for the KT-KRR estimator. Like for NW, in Fig. i(b) do comparison for KRR-MSE across many kernel choices and conclude that the choice (14) is indeed a superior choice compared to the base kernel k and the concatenated kernel (12).
4
Main results
We derive generalization bounds of our two proposed estimators. In particular, we bound the mean squared error (MSE) defined by - f Ex (f( - (x)))² Our first assumption that of well-behaved density the covariate space. This assumption mainly simplifies analysis of Nadaraya- Watson and kernel ridge regression, but can in principle be relaxed.
Assumption 1 (Compact support). Suppose that X C. (2(R;)) C. Rd for some Rin 0 and that the density p satisfies 0 < Pinin I p(x) S Pmux for all x E X.
4.1 KT-NW
For the analysis of the NW estimator, we define function complexity in terms of Hölder smoothness following prior work [27].
Definition! 1. For L > 0 and B E (0, 11. a function f X - IR is (3, L)-Höderr ifr all x1,02 E X, [f(x1) - f(z2) - L|| 221
Our next assumption that on the kernel. Whereas typically the NW estimator does not require reproducing kernel, our KT-NW estimator requires that k be reproducing to allow for valid analysis. Assumption 2 (Shift-invariant kernel). k is reproducing kernel function (i.e., symmetric and positive semidefmitte defined by k(x1, 322) A <([<2] x2 s22//h), where h O and IR R is bounded by 1, L, Lipsshic, square -guare-integrable and satisfies:
log(La K5 (1/n)) = Ologn), where xt(u) A sup(r x(r) 2 u):
(15)
Additionally; there must exist constants Cı, c2,02 0 such that
28 sup zEX
k(r, - 2)d2 S C1 sup ZEX
k(x, - 2)dz and (16)
(2 (d220m(21 5) -1) 1' n(()uu-I'du du for all j= 1,2,
(17)
When k is a compact kernel, such as Wendland, Sinc, and B-spline, Assum. 2 is easily satisfied. In App. G, prove that Gaussian and Matérn (with v > d/2 + 1) kernels also satisfy Assum. 2. We now present our main result for the KT-NW estimator. See App. B for the proof.
One might expect the ridge regression kernel to include a term that accounts for y². However, the generalization bounds turn out to be essentially the same regardless of whether we include this term when detining knn.

---

Theorem (KT-NW). Suppose that Assum. I and 2 hold and that f E(B, Ly) with (0. 1/.
Then for any fixed 8 E (0, 11, the KT-NW estimator (7) with Nout n and bandwidth h = n 28-2a satisfies
l| - 1 S Cn sea log nI,
(18)
with probability at least 1 5, for some positive constant C that does not depend
Tsybakov and Tsybakov [27]. Belkin al. [3] show that FULL-NW achieves a rate of O(n オ which is minimax optimal for the (3, Lö-dee function class. Compared to the ST-NN rate of n f
KT-NW achieves strictly better rates for all 3 > 0 and d > O, while retaining ST-NW's fast query time of (()n). Note that our method KT-NW has a training time of lon n). which not much more than simply storing the input points.
4.2 KT-KRR
We present our main result for KT-KRR using finite-rank kernels. This class of RKHS includes linear functions and polynomial function classes.
Theorem 2 (KT-KRR for finite-dimensional RKHS). Assume f H(k),, Assum. is satisfied, and k has rank m E N. Let fKT. denote the KT-KRR estimator with regularization parameter
X' O( m log Rout) n/Aigut
Then with probability least 28 2e "151 -
the following holds:
l.FKT.X' - f Cm log nout [II + 1)²
(19)
min(n, nout)
for some constant C that does not depend n or Nout-
See App. C for the proof. Under the same assumptions, Wainwright [29, Ex. 13.19] showed that FURI-KRR estimator Stalt, achieves the minimax optimal rate of (mm/n) in ((n²) runtime. When Poout v log" n, the KT-KRR enror rates from Thm. 2 match this minimax rate in (n2//2) time, (near) quadratic improvement over the KRR. On the other hand, standard thinning- BRRRing-KRR with similar-sized output achieves quadratically poor MSE of order Vx
Our method and theory also extend to the setting of infinte-dimensie dimensional kernels. To formalize this, we first introduce the notion of kernel covering number.
Definition (Covering number). For kernel k Z x + R with Bx L H: |1 I 1}, sei A C Z and > O, the covering number N₂ is the minimum cardinality of all sets C C B& satisfying B& c Unecig E B& sup,e (h(()) ((x) cc.
We consider two general classes of kernels. Assumption 3. For some C. O, all and E (0, 1), and B2(r) {a Rd ||=112 S rr.
kernel k is
LoGGRoWTH(a, ()) when log.N ( POLyGROWTH(A,)) 3) when log (B2 S (r( with a <<> 2.
<
with a, > 0 and
We highlight that the definitions above cover several popular kernels: LOGGROWTH kernels include finite-rank kernels and analytic kernels, like Gaussian, inverse multiquadratic (IMQ), and sinc [9, Prop. 2], while POLyGROWTH kernels includes finitely-many continuously differentiable kernels, like Matérn and B-spline [9, Prop. 3J. For clarity, here present our guarantee for LOGGROWTII kernels and defer the other case to App. E.
Theorem 3 (KT-KRR guarantee for and k is LOGGROWTH(C. .3) (Assum. 3). Then fKT. with X' = (11//oot satisfies the following I15 12 lor"
RKHS). Suppose Assum. I is satisfied
bound with probubility at least 28- 2e (201712104)
1 f* 1 < C log" Vlgg
111 1/2.
(20)
Dont
for some constant C that does not depend Nout-
7

---

See App. E for the proof. When Pout Vi, ST-KRR achieves an excess risk rate of n- log" for k satisfying LoGGROWTH(c, B). While KT-KRR does not achieve a strictly better excess risk rate bound over ST-KRR, we see that in practice, KT-KRR still obtains an empirical advantage. Obtaining a sharper error rate for the infiniteddimensional kernel setting is an exciting venue for future work.
5 Experimental results
We now present experiments on simulated and real-world data. On real-world data, we compare our KT-KRR estimator with several state-of-the-arr KRR methods, including Nyström subsampling- based methods and KRR pre-conditioning methods. All our experiments were run on machine with 8 CPU cores and 100 GB RAM. Our code can be found at https: attpp://githus com hamm//gg43///ggg
5.1 Simulation studies
We begin with some simulation experiments. For simplicity, let X = and P = Unif Unif[-V3, v so that Var[X] = 1. We set
f (z) 8 sin (8T.Z) exp(x) and a=1
(21)
and follow (1) to generate (vi) (see Fig. 2). We let the input sample size vary between 2 200 212 2 and set the output coreset size to be nout /n in all cases. For NW, we use the Wendland(() kernel defined by
k(21, x22) -
)+ for h > O.
(22)
For KRR, we use the Gaussian kernel defined by
Figure Simulated data.
x2) A exp( ||
for
O.
(23)
2h
We select the bandwidth h and regularization parameter X' (for KRR) using grid search. Specifically, we use held-out validation set of size 10 and run each parameter configuration 100 times to estimate the validation MSE since KT-KRR and ST-KRR are random.
Ablation study. In Fig. 1, we compare thinning with our proposed meta-kernel KALG = kNw to thinning with the baseline meta-kernels (11) and (12). For our particular regression function (21), thinning with (11) outperforms thinning with (12). We hypothesize that the latter kernel is not robust the scaling of the response variables. By inspecting (22), see that [z (11.111)00 (Ir2, 92)ll2 is heavily determined by the values when they are large compared to the values of x,-as is the case on the right side of Fig. (when X > 0). Since is a uniform distribution, thinning with (11) evenly subsamples points along the input domain X', even though accuractely learning the left side of Fig. 2 (when 0) is not needed for effective prediction since it is primarily noise. Validating our theory from Thm. 1. the best performance is obtained when thinning with knw (13), which avoids evenly subsampling points along the input domain and correctly exploits the dependence between X and Y.
In Fig. 1, we perform a similar ablation for KRR. Again we observe that thinning with KALo((Z1 31), (2),
k(z1, 422) outperforms thinning with KALa y1), (2)) (((z1, 31), (I2, 32)), while thinning with KALO = KRR achieves the best performance.
Comparison with FULL, ST, RPCHOLESKY. In Fig. 3(a), compare the MSE of KT-NW to FULL-NW, ST-NW (a.k.a "Subsample"). and RPCHOLESKY-N across four values of n. This last method uses the pivot points from RPCHOLESKY as the output coreset Sout- At all FULL-NW achieves the lowest
evaluated,
KT-NW achieves lower MSE than ST-NW and RPCHOLESKY- MSE across the board, but it suffers from significantly worse times, especially test time. Owing to its Onn n) runtime, KT-NW is significantly faster than RPCHOLESKY-N for training and nearly matches ST-NW both training and testing time. We hypothesize that RPCHOLESKY while it provides good low-rank approximation of the kernel matrix-is not designed to preserve averages.
In Fig. 3(b), we compare the MSE of KT-KRR to FUL.I- ST-KRR (a.k.a "Subsample"), and the RPCHOLESKY- KRR method from Chen al. [6, Sec. 4.2.2], which uses RPCHOLESKY to select

---

Full
Mean Squared Error
Subsample
Tost time (s)
4
CCClelesky
(Ours)
3
2
1
21
2
0.0
0.2
0.3
0.4
Input sample size
Train time (s)
(a) Nadaraya- Watson estimator with Wendland ()) kernel (22).
2.0
Full
Mean Squared Erroc
Subsample
RPCholesky
2-1
1.55
(Ours)
Test Lime
2-
1.0
124
2-7
0.0
2
2
2/4
0.001
0.03
52
Input sample size
Train time
(b) Kernel ridge regression estimator with Gaussian kernel (23).
Figure 3: MSE and runtime comparison simulated data. Each point plots the mean and standard deviation across 100 trials (after parameter grid search).
landmark points for the restricted KRR problem. We observe that KT-KRR achieves lower MSE than ST-KRR, but higher MSE than RPCHOLESKY- KRRR--KKKRRRRR and FULL-KRR. In Fig. 3(b), we also observe that KT KRRR is orders of magnitude faster than FULL-KRE across the board, with runtime comparable ST-KRR and KRCHOLESKY-KRR both training and testing.
5.2 Real data experiments
We now present experiments real-world data using two popular datasets: the California Housing //sciiiit-eearrn wtt.:////atattseeeeeeeeeeeeeeee //atas/s/atttsss/////
regression dataset from Pace and Barry [17] BSD-3-Clause license) and the SUSY real_world. html#falifornia siifoornaahousingg dataset; binary classification dataset from Baldi et al. [2] 279/ susy; CC-BY-4.0 license).
ics uci edu.dddaseeee
California Housing dataset (d = 8. 2 10*). Tab. I(a) compares the test MSE, train times, and test times. We normalize the input features by subtracting the mean and dividing by the standard use the Gaussian kernel (23) with bandwidth = 10. We use X = X' = 10-3 for FULL-KRR, ST KRR, and KT-KRR and 10-5 On this dataset, KTTKKRR lies between ST-KRR and RPCHOLESKY-KRR
deviation and 80-20 train-test split. For all methods,
for EPCHOLESKY-KRE in terms of test MSE. When nout = /n, RPCHOLESKY pivot selection takes (n²)) time by Chen al. [6, Alg. 2], compared KT-COMPRESS++, which compresses the input points in only On log time. This difference in big- O runtime is reflected in our empirical results, where KT-KRR take 0.0153s versus 0.3237s for RPCHOLESKY- KRR.
SUSY dataset KT-KRR (with h = 10 RPCholesky preconditioning [7], FALKON [22], and Conjugate Gradient (all with h 10, 10-3) in terms of test classification error and training times. For the baseline methods, we use the Matlab implementation provided by Díaz et al. [7] (https: (uttps://github com/ eepperly
18, N 5 x 108). Tab. 1(b) compares our proposed method 10-1) to several large-scale kernel methods, namely
for kernel ridge- rwigr-ieggeeereeeee regression). In for--ernel-

---

Method
MSE (%)
Training time (s)
Prediction time (s)
Full
0.4137
11.1095
0.7024
ST-KRR
0.5736
0.0018
0.0018 = 0.0005
0.0092 = 0.0006
RPCHOLESKY
0.3503
0.0001
0.3237 + 0.0094
0.0060 + 0.0008
KT-KRR (Ours)
0.5580 0.0015
0.0153 + 0.0013
0.0083 + 0.0003
(a) California Housing regression dataset.
Method
Test Error (%)
Training Time (s)
RPCholesky
19.99 + 0.00
3.46 0.03
FALKON
19.99 + 0.00
5.06
0.02
CG
20.35 + 0.00
6.16 + 0.03
ST-KRR
22.71 + 0.30
0.09 = 0.00
KT-KRR (Ours)
22.00 + 0.21
1.79 0.00
(b) SUSY dataset.
Table 1: Accuracy and runtime comparison real-world data. Each cell represents mean standard error across 100 trials.
our experiment, we use x 10t points for training and the remaining 10 points for testing. As common practice for classification tasks, we use the Laplace kernel defined by k( 222 & exp(-1l=ı x2ll2//
/all|//)) h). All parameters chosen with volssvaaii
We observe that KT-KRR achieves test MSE between ST-KRR and RPCHOLESKY preconditioning with training time almost half that of RPCHOLESKY preconditioning. Notably, our Cython implementation of KT-COMPRESS++ thinned the four million training samples in only 1.7 seconds on a single CPU woth-with further speed-ups to be gained from parallelizing on a GPU in the future.
6 Conclusions
In this work, we introduce meta-algorithm for speeding up estimators from non-parametric regression, namely the Nadaraya- Vadaraya-Watson Watson and Kernel Ridge Regression estimators. Our method inherits the favorable computational efficiency of the underlying Kernel Thinning algorithm and stands to benefit from further advancements in unsupervised learning compression methods.
The KT guarantees provided in this work apply only when f* H(k) for
base kernel k. In practice, choosing a good kernel k is indeed challenge common to all prior work. Our framework is friendly to recent developments in kernel selection handle this problem: Dwivedi and Mackey [9, Cor. 1] provide integration-error guarantees for KT when f & H(k)) Moreover, there recent results on finding the best kernel (e.g., for hypothesis testing [8, Sec. 4.2]). Radhakrishnan et al. [20] introduce the Recursive Feature Machine, which uses a parameterized kernel kas (2)) A exp(-(x) - x2)_ M x22 //)/ (2)?)), and propose an efficient method to learn the matrix parameter M via the average gradient outer product estimator. An exciting future direction would be to combine these parameterized (or "learned") kernels with our proposed KTT
methods for non-parametric regression.
7 Acknowledgements
AG is supported with funding from the NewYYokk-Preshttriaa Hospital.
References
[1] Haim Avron, Kenneth I. Clarkson, and David P Woodruff. Faster kernel ridge regression using sketching and preconditioning. SIAM Journal on Matrix Analysis and Applications, 38(4): 1116-1138. 2017. (Cited on page 2.)
10

---

[2] Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles in high-energy physics with deep learning. Nature communications, 5(1):4308, 2014. (Cited on page 9.)
[3] Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference Artificial Intelligence and Statistics, pages 1611-1619. PMLR, 2019. (Cited on pages 7 and 21.)
[4] Christos Boutsidis, Petros Drineas, and Malik Magdon-Isman Ismail. Near- optrmol coresets for least-squares regression. IEEE transactions on information theory, (9(10)968800-63333 2013. (Cited on page 2.)
[5] Raffaello Camoriano, Tomás Angles, Alessandro Rudi, and Lorenzo Rosasco. Nytro: When subsampling meets early stopping. In Artificial Intelligence and Statistics, pages 1403-1411. PMLR, 2016. (Cited on page 2.)
[6] Yifan Chen, Ethan N Epperly, Joel Tropp, and Robert J Webber. Randomly pivoted cholesky: Practical approximation of kernel matrix with few entry evaluations. arXiv preprint arXiv:2207006503, 2022. (Cited on pages 8 and 9.)
[7] Mateo Díaz, Ethan Epperly, Zachary Frangella, Joel A Tropp, and Robert J Webber. Robust, randomized preconditioning for kernel ridge regression. arXiv preprint arXiv:230..12665 2023. (Cited on pages and 9.)
[8] Carles Domingo-Enrinn Enrich, Raaz Dwivedi, and Lester Mackey. Compress then test: Powerful kernel testing in near-linear time. arXiv preprint wrXiv2231.009944 2023, (Cited pages I and 10.)
[9] Raaz Dwivedi and Lester Mackey, Generalized kernel thinning. International Conference on Learning Representations, 2022. (Cited on pages 1, 2, 10, 14, and 15.)
[10] Raaz Dwivedi and Lester Mackey. Kerne thinning. Journal of Machine Learning Research, 25 1152):1-77, 2024. (Cited on pages 1, 2, 4, 13, 14, 18, 24, 32, 48, and 49.)
[11] Ahmed Alaoui and Michael W Mahoney. Fast randomized kernel methods with statistical guarantees. stat, 1050:2, 2014. (Cited on page 2.)
[12] Steffen Grünewäller. Compressed empirical measures (in finite dimensions). arXiv preprint arXiv:2204.08847, 2022. (Cited on pages and 46.)
[13] Ming-Yuek Huang and Shu Yang. Robust inference of conditional average treatment effects using dimension reduction. Statistica Sinica, 32(Supp)):547, 2022. (Cited on page 1.)
[14] Samory Kpotufe. Fast, smooth and adaptive regression in metric spaces. Advances in Neural Information Processing Systems, 22, 2009. (Cited on page 2.)
[15] Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of statistics, pages 1 1302-1338, 2000. (Cited on page 48.)
[16] Lingxiao Li, Raaz Dwivedi, and Lester Mackey. Debiased distribution compression. arXiv preprint arXiv:2404. /2290, 2024. (Cited pages 37 and 39.)
[17] R Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters. 33(3):291-299 1997. (Cited on page 9.)
[18] Jeff Phillips. Coresets and sketches. In Handbook of discrete and computational geometry, pages 1269-1288. Chapman and Hall/CRC, 2017. (Cited page 2.)
[19] Jeff M Phillips and Wai Ming Tai. Improved coresets for kernel density estimates. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2718-2727. SIAM, 2018. (Cited on page 4.)

---

[20] Adityanarayanan Radhakrishnan, Daniel Beaglehole, Parthe Pandit, and Mikhail Belkin. Feature learning in neural networks and kernel machines that recursively learn features. arXiv preprint arXiv:2212.3388) 2022. (Cited on pages and 10.)
[21] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007. (Cited on page 2.)
[22] Alessandro Rudi, Luigi Carratino, and Lorenzo Rosasco. Falkon: An optimal large scale kernel method. Advances in neural information processing systems, 30, 2017. (Cited on pages 2 and 9.)
[23] Abhishek Shetty, Raaz Dwivedi, and Lester Mackey. Distribution compression in near- near-linear time. In International Conference Learning Representations, 2022. (Cited pages 4, 13, 14, and 15.)
[24] Rahul Singh, Liyuan Xu, and Arthur Gretton. Sequential kemnel embedding for mediated and time-varying dose response curves. arXiv preprint arXiv:2111.03950, 2021. (Cited on page 1.)
[25] Ingo Steinwart and Simon Fischer. A closer look at covering number bounds for gaussian kernels. Journal of Complexity, 62:101513, 2021. (Cited on page 29.)
[26] Ilya Tolstikhin, Bharath K Sriperumbudur, Krikamol Mu, et al. Minimax estimation of kernel mean embeddings. Journal of Machine Learning Research, 18(86):1-47, 2017. (Cited on page 4.)
[27] Alexandre B Tsybakov and Alexandre B Tsybakov. Nonparametric estimators. Introduction to Nonparametric Estimation, pages 1-76, 2009. (Cited on pages and 7.)
[28] Stephen Tu, Rebecca Roelofs. Shivaram Venkataraman, and Benjamin Recht. Large scale kernel learning using block coordinate descent. arXiv preprint arXiv:1602.05310, 2016. (Cited on page 2.)
[29] Martin J Wainwright. High-dimensiooal statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019. (Cited on pages 7, 21, 22, 23, 28, 32, 33, 34, 36, 37, 40, 41, 42, 44.
45, and 46.)
[30] Holger Wendland. Scattered data approximation, volume 17. Cambridge university press, 2004. (Cited on page 48.)
[31] Yuchen Zhang, John Duchi, and Martin Wainwright. Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates. The Journal of Machine Learning Research, 16(1):329933340, 2015. (Cited on page 2.)
[32] Yan Zheng and Jeff M Phillips. Coresets for kernel regression. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 645-6544 2017. (Cited page 2.)
12

---

A Background on KT- KT-COMPRESS++
This section details the KT-COMPRESS++ algorithm of Shetty et al. [23, Ex. 6]. a nutshell, KT- KT-COMPRESS (Alg. 2) takes input point sequence of size n, compression level g. (reproducing) kernel functions KALC. and a failure probability 5. KT-COMPRESS++ first runs the KTTCOMPRESSS algorithm of Shetty al. [23, Ex. 4] to produce an intermediate coreset of size 29 / Next, the KT algorithm is run on the intermediate coreset to produce a final output of size vn.
KT-COMPRESS proceeds by calling the recursive procedure COMPRESS, which uses KT with kernels KALS an intermediate halving algorithm. The KT algorithm itself consists of two subroutines: (I) KT-SPLIT (Alg. 3a), which splits a given input point sequence into two equal halves with small approximation error in the KALO reproducing kernel Hilbert space and (2) KT-SWAP (Alg. 3b), which selects the best approximation amongst the KT-SPLIT coresets and baseline coreset (that simply selects every other point in the sequence) and then iteratively refines the selected coreset by swapping out each element in turn for the non-coreset point that most improves MMDk... error. As in Shetty et al. [23, Rem. 3], symmetrize the output of KT by returning either the KT coreset its complement with equal probability.
Following Shetty et al. [23, Ex. 6). we always default to g = [log2 log + 3.1] so that KT- KT-COMPRESS++ has overall runtime of On log n). For the sake of simplicity, we drop any dependence on g the main paper.
Algorithm 1: KT-COMPRESS++ Identify coreset of size vni
Input: point sequence Sn, of size compression level g. kernel kAu, failure probability Sc + KT-COMPRESS( Sm, // coreset of size 2 /n // coreset of size vn
Sc.. KT(Se,, KALS, (1)
return ScH
Algorithm 2: KT-COMPRESS Identify coreset of size 2 20/n Input: point sequence S.. of n, compression level g. kernel KAUsi failure probability return COMPRESS(Sin, KALG, w4 140
(log,
function COMPRESS (S, g. kALa: 8): [S] = then return S Partition S into four arbitrary subsequences (5 each of size n//4 for 1,2,3,4 4 do
S. COMPRESS(S,, g, KAIn; 6) run COMPRESS recursively return corescts of size 2
end
combine coresets to obtain a coreset of size 2 KT(S, KALG. (5(88) // halve the coreset to size 2 / via symmetrized kernel thinning
CONCATEMIEES....
S
return
function KAtS. 8):
// Identify kernel thinning coreset containing ||8//2] input points
SKT KT-SWAP(KALO, KT-SPLIT(KALL:: 6)) return SKT with probability and the complementary coreset S \ SKT otherwise
Define the event
EKT,S & [KT-COMPRESS*+ succeeds).
(24)
Dwivedi and Mackey [10, Thm. Rmk. 4] show that
P(EKT,8) 2 1 8.
We restate [10, Thm. 4] in our notation:
Lemma 1 8 guarantee for KT- KT-COMPRESS+4) Let Z C Rdd and consider reproducing kernel
KALG Z x Z R. Assume n nout E N Let SKT KT-COMPRESS ++(Sms g, KALG, 8) and
13

---

Algorithm 3a: KT-SPLIT - Divide points into candidate coresets of size [n/2]
Input: kernel Kepii point sequence Snn = (2x)(=1> failure probability
s()) . + Initialize empty coresets: s(2) have size after round
a +-
// Initialize swapping parameter
for 1,2,.... [n/2] do
// Consider two points at time
(æ,x') 4- (125
// Compute swapping threshold a; a, a -get_swap_ppae parapsarammss (o, b, ) with b²= -opin 2)) Kapan (x', a²)- 2kspue (2r, xc)
I/ Assign one point to each coreset after probabilistic swapping
0 < "3 (x)p (pp(()),z))) 2ress (kypli (2, kupla xf'))
(x, + (x',x) with probability min(1, {1 ))+)
(()) append(())) ((2) ((2) append((a))
end
return
(8 S,) candidate coresets of size [n/2]
function get. wwt.s/awpppraammmmmmmm b):):
22 62) a² f 7- 02+ (6 2n, at)
return (a)
Algorithm 3b: KT-SWAP- Identify and refine the best candidate coreset
Input: kernel kass. point sequence S.. (as)i= candidate coresets (5(+),(()))
((0) basseline_.oresett..ii size= [m/2])
Compare to baseline (e.g. standard thinning)
SKT + S(())) for t* + aragmim MMD (Sm, 5(0) // Select best coreset
// Swap each point in SKT for best alternative Sm while ensuring no point is repeated SKT
for i = 1...., [n/2] do
SKT [i] f argmin, (SkT (i),, (ier) MMDKAI (Sm SKT with Skr(i] 2)
end
return SKT, refined coreset of size |n/2]
define Pin 2 Exesm 8g and Qout
1 Exeseo 8z. Then on event EgT,s, the following bound
Pout
holds:
| Myaro (n, Nout d, 8, R), where Nou
[T KALalos I
(25)
Mxuu (n, Nout, d, R) A log
Dout logg (ongn///uuun /out))
(26)
V (+) +
log
Leaap kaialla
(Besonn + 1t)
LiaL
A sup SUP21.22,3322
(k -akcll)))))-ku and
(27)
220-20
Rk inf r : sup
[kAIA(2))2))
|
(28)
1
for some universal positive constant c.
Proof. The claim follows by replacing k [10, Thm. 4] with KALG- replacing the sub-Gaussian constant
of KT with that of CTT-COMPRES+++ in [23, Ex. 5], and replacing ||ALaoloo with | Il oloo و sup.es., kaLa(z, 2) throughout.
L
We restate [9, Thm. 2] in our notation:
14

---

Lemma (MMD guarantee for KT-COMPRESS++)) Lea 2 RR. and consider reproducing kernel KALO: 2x 2 > IR. Assume n/ nout E 2% Let SKT & KT-COMPRESS++ g) and define
Pin a =. d2 and Qout Rout ExESKT 82. Then on event ÊKT,S, the following bound holds:
{ 22
2/[kauu so.in 2 2RAA RALL (n, nout, 8, A, e)
1/2
H(Kmo (1PPn Qou)ha I inf.e Smnad
22
where
Mout
ka (n, nout, ó, R. c) & ev log log(n/mou))
(log(t) - log NiKu (A,e)]
(29)
for some universal postive constant
Proof. The claim follows from replacing in 19, Thm. 2] with KALa and replacing the sub-Gaussian constant of KT with that of KT-COMPRESS++ in [23, Ex. 5].
B Proof of Thm. 1: KT-NW
Our primary goal is to bound Ess,, (foo(/))) - ( for fixed zo E N. Once we have this bound, bounding ll f 112 is straightforward as integrating zo X.
Consider the following decomposition:
Ess... (Jee((z)) - ((00)
Est.. (FeT(Co)) [(x0) [(x0) - ((xo) 27
$ Esn.. (FRT(ZO)- - (F(o)))))((o)) )
(30)
(f(oo) (zx0) 121
+ 2 Est.
(31)
Define the random variables
- 1
X, moll
< <1} for i= 1,2,.....
Also define the event
8 1> 13 > 0).
(32)
Since X; are i.i.d. samples from P. it follows that t i.i.d. Bernoulli random variables with parameter
p p = 1) 2 CoPmin
(33)
where cu > 0 depends only on d and x (see Assum. 2). Denote the denominator terms f and Fr by
p(-) 2 E k(,,;; and PKT(-) Mout
(34)
respectively, and the numerator terms in f and FKR by Á(-) A ; Σ k(.,,;))) and AKT(-)
Ej=1
Bout
k(., 2.)0)
(35)
respectively.
We now consider two cases depending the event E.
Case I: Suppose event E" is satisfied. It follows from (34) that p(xo) 0, in which case f( 0. Since Sout Sm. necessarily follows that Pigt (xa) and fKr (ax) Thus, we can bound (30) and (31) by
Esn.. (FRT(ZE)) - -(xo)) [[] = 0 and
15

---

Esn. (F(xo) - 100--f((aa (x(0) I[E9]]
Es.. (0 (xx)) [[E9]
s (ZO)
$ (z))
I (f*) (mo) exp c
for some positive constant C' that does not depend on n. Note that these are low-order terms compared to the rest of the calculations, may ignore them in the final bound.
Case I: Otherwise, may assume event & is satisfied. Let us first bound (30). On event ÊKT,6
(24), we claim that
Ess..
(Fee((Zo) - -(zoo) T[
Cdloge nh
whenever p=w(y n).
(36)
We defer the proof to B.I.
Letting X - (XI,..., x and Y & (Yi...., .n) denote the and y components of Sm. respectively, we can further decompose (31) by
Es... (f(zo)-
- (z0)) I[E]] = Ex Erix (f(zo) Erix (f(oo))) | Illl (Bxix [f(cos) - f (2o) T[ε]
+ Ex
where the first RHS term corresponds to the variance and the second RHS term corresponds to the bias. We claim that
Ex
By
-Erix -FxI
27
T[E] - (n -Cnh") + nad) and (37)
(Bylx (
Ex
[[]]
SC 1G3120 log" n,
(38)
for some constant C > 0 that does not depend on either n or h. We defer the proofs to App. B.2 and B.3. Combining (36) to (38), we have
Es... (feerEe)) (xx) ][E]
Cd log" n na KT bound
Onn" 20 Cnns
nha + 2C13322 log* n. (39)
Variance bound
Bias bound
Note that Ad < 1, so the Cdllgg" a term dominates the nhd term. Thus, the optimal choice of nh.a
bandwidth h comes from balancing
nhza
2L
1842R
(40)
Finally, must verify our growth rate assumption p in (36) is satisfied. Since B 0, we have p
(33)
(40)
CoPmin/t
20422
lim
Vogg
Plugging (40) into (39) yields the advertised bound (18).
B.1 Proof of claim (36)
We first provide generic result for approximating the numerator and denominator terms defined in (34) and (35). Lemma 3 (Simultaneous L bound using KT-COMPRESS++ with kxw). Suppose k satisfies Assum. Given Sin. the following bounds hold on the event Exi,a:
1b PKT I CpV L (logn log(1/8))
(41)
A AKTIII S cpv _ (logn log(1/8)) where Ca. Cp 0 are constants that do not depend d or
(42)
16

---

See App. B.1.1 1 for the proof. In the sequel, will simply treat the log(1/0) term as constant, meaning the log n terms dominate the expressions.
With this lemma in hand, let us prove the claim (36). Define the following events:
A - (For(xo) = 0} B (Per(ro) # 0}
C - (p(00 2 /
On event &, consider the following decomposition:
S.. (frr(Zo) -(xo)) 2 [[EKT,o]
(FoT(Z))- (2o) -f(o)) 1[EKT, neql
Ess.
(43)
(FiT(ZO) M(ao)) I[ ndnc)
Es...
(44)
(Frr(zo) - Flzo)) I[EXT, nBnc
+ Es,.
(45)
Bounding (43).
Note that almost surely, have
[f(zo)] S max and
(fkT( S muxx.
Thus, have
Es..
(Firr(z)- ](20)) 1|99
nZ < 4Y IP(n n p(x0) <
( 4Y2 max P
Giml 7h mp < マラ mp
(8)
cn exp exphh)
where (i) follows from subtracting up from both sides of the probability statement and (ii) follows from concentration of Bernoulii random variables (see App. B.2).
Bounding (44). Note that on event εKT, n C. have
(p)) 2 P(ro) 1|0 PkT
(1)
2
cpVe logn
(36)
(33)
ci ca > 0.
(46)
where step (i) follows from applying (41) and substituting P2 P. Hence the events εKr,5 and A mutually exclusive with probability 1, thereby yielding
Es... (fAT((ZO)= - i(zo)) 2
I[EKT, nnnc] 0.
AKT(#o) and f(xo) Bounding (45). On the event B CCC, we have fKT(10)= yields
M(aa) p(za)
which
Pier (xo)
fKT(IZ0) - f(zo)
AsT. A(za) ART (wa) ( Pieria)))
PRT
plao)
(( Perr(to
(AsT(w)) ) -(z0)) (Pp))))(())))))) (oooo)++ A(zo)) (p( ( (xo)(xo))
p(zo) PPoo (we)
Akr((o)- (((o)) (( A(za)) (7 (x)
Mao) (xo)
We can invoke (41) and (42) to bound (((.)) PKTT (2o) and AKT (2o) A(za) respectively. Thus,
we have
(Fkr((z)- -(oo)) T[EXT, n Bnc] < <oy log noggn-llza)se / log A(zaa) Pkr (mp)
Es...
17

---

2d-log"
)
A(za))
)²
pir((zo) )
a
PKT((r))
(m0)
D(aoo
2d-log
+ max
PKT (m1)
Cogo"" nh2n
for some positive constant C that does not depend on n, where step (i) uses the fact that A(zo)
S Y max
p(mo)
and step (ii) uses the lower bound on (KT( from (46). Combining (43) to (45), we have
Es... (Feer(zo) - f(0o)) 2 TEXT,,1] S co expf -opf-cnnh") +
C.llogn nh"
Note that the second term dominates so that we may drop the first term with slight change to the value of the constant C' in the bound (36).
B.1.1 Proof Lem. 3: Simultaneous - bound using KT-COMPRESS++ with kyw
We first decompose knw as
kww((r1, (22, = kg (1(11, (22) + k2 (2((21. (12,, (22, ki ((x1, 91), (z2, 1/2) A x()1,22) and
where
(47)
k2((11, 31), v2)) A k( x2) 9132.
(48)
and note that
H(kNw) = H(ki) @ H(k2).
(49)
This fact will be useful later for proving simultaneous 7, approximation guarantees for À and p.
Given that k satisfies Assum. 2, we want to show that knw defined by (13) satisfies the Lipschitz and tail decay properties, so that we may apply Lem. Note that
kkwll = ||k]] (1 + Y2 Y
(50)
We claim that kernel knw satisfies
(|kll1 + max) and LANW I Lx Y max [kk] R & Rk, + 2Ymax
(51)
(52)
By [10, Rmk. 8), we have
Lx
La
and Rk S hal (1/n),
(53)
k
where kt is defined by (15). Applying (50) and (51), we have
Luww
Lx + Ymax ([[k]l +mx
[k lI
[1kl (1+ (1+Y Vmnx)
s
Lxx
+ [kll
||]]
Vmax
(53) 2hm + Vmac"
Finally, we have
Laga Bugw.. kxw Ilx
22h
Ymnx ) (hxtt + 22maas
=L,kkl (1/n) HbrYmax + hrd (1/0)1
+
Vaax
< 4 max (1, Lu Y max) x (1(1n))
h < 4 max (1, L Ymax) c'n
(54)
where the last inequality follows from Assum. 2 for some universal positive constant d'
18

---

Since Assum. is satisfied, R is constant. Applying (54) Vkx (n, nout; d,,,R) R) defined by (26), we have the bound
kxw (n, nout: d, S d' (1olo(("z (lo + 5.dd
for some positive constant c", Substituting this into (25), we have
iI - Qow)kkwlls I C1
||k| (1-X
v /og (3gga()
[Vlog()) d
Nouut
||k| oe (1 - maxe
Vdlllogn Vlog(100))
for some positive constants c1, c2. By definition,
[1(P Gow))kwlle al = sup ((P Qou kyw: kxw (:, kww
Define kj and k2 by (47) and (48), respectively, and note that ki z), (2(-22) E H(kww) for all E Z. We want to show that
supzez ((Pin kww, (i k))kww S 02
[k]l (1+V
V Vd(llogn v /loo(1/8)) and
Pout
suPzez ((Pin kow) kg(,, 2)) kNw I C2
|kll (1+ muxx)
vd( + /log(1/8))
which would imply (41) and (42) (after simplifying all terms besides n, d, and 8).
The first inequality follows from replacing all occurrences of the test function kww (xc y)) in the proof of Lem. 1 with the function ki (:,:)) and noting that (kNw(; (:, (222, y:)). (1 ( (3r; y) y) kow
(ki(,, 2:), ki (()())))))))))) ())))) from the fact that H(kNw) Hkk) 4 H(k2) (49).
The second inequality follows from replacing all occurrences of the test function kNw(s, ( (z, v)) in the proof of Lem. with the function (g x) and noting that (KNw (Ii, 84)), kg(,, (I, ())) = (ka(s (ot 1.)), (2(,, (z, k)) again from the fact that H(kyw) = H(k) @ H(kg) (49).
Proof of claim (51). We leverage the fact that the Lipschitz constants defined by (27) satisfies the following additivity property. Letting& = Sin we have
Lky = sup 31 22.
kww .2) ks))
22 2alla
(21.2))
(2r,2a)
(g(()122)) -
< sup 21 22
2a
sup 28
2alla
Lki + Lag-
We proceed bound Tk, and Lug separately. Note that
Lx Lx--
Applying the definition (27) to Lks, we have
Lng Sup=;=(x,.p))
k 2220 ua k(a as)v1vs
22
3+ 11922
=3=(23 (3a.yy)
|8a| k(a as M2 k(x 122 + www.s//sssk......o....ooo k( (0g)))
sup 21 = (x1 .
V1l22-25 wall
23=(222122
[gn k(i Lra) Val -aao
sup 21 = -M1)
(ura-Va)
(ma-Ma
kk( 21l sups, =x) -Kk())_es)k((1...aa
sup (at
VI || - 2 -
||=2-=>|]++|
+11 -
(32-122
(22-1/)
23
2s (83.Ms)
Y Ymaxx |kl0o
+ Lx Y max.
Putting together the pieces yields the claimed bound.
19

---

Proof of claim (52). can be rewritten as
We aim show that Rkyw., is not much larger than R...- Note that kxw
kyw kyw((z1, Un), (02, v2)) (1 + v1 (211))
We define the sets
21,22: k(2,,, 22)1 S l|kl and
sup
(55)
|| 22
N
y* : sup
(11.01) || [anl= +||0n - vall"
(2(11, y1222
1k
(56)
noting that
Rk,n inf r and Rk = inf
by definition (28).
Suppose r E T. Then for any (1), (I22, 82) such that
| - æ21l" + 11 - 82ll 2 r² + 4Y2
max:
it must follow that ||r =22 2 > y2 (since || yzll satisfies (55), it must follow that
4Y max by triangle inequality). Since
(())) (113/2 1)1 k( 22 22) max + 1) S
| (y max
(50) ||kew
Il...
meaning 2/2 4Y² max ET" where recall I* is defined by (56). Thus, we have
Rkww S V R2k, + 4Y S Rkkn + 2Y max
as desired.
B.2 Proof of claim (37)
Suppose event & (32) satisfied. Define the shorthand for the variance:
o² ( X) A Eyix (F(zo) Exix [
Conditioned on X1 21; X2 I2,..., Xn = Ins we have
D Vik(Xi.zo) Eylx [((o)) = Byi|xx..... Na
Do ((X
(57)
2i-1 k( k(((,,o))
21 k(X,,
where we have used the fact that [E(Y X x= by assumption (1). Note that event E, we have
0² (No: X) (57) Eyix
En Y.k(X,,ro) En k(X2.ro)
E (XX,)k((X,.o)) 27
Ee, ke ((X,,.0)
=Eyx
Varluz]
E
k(X
(E k(X..
where recall .i...., Un are i.i.d. random variables with Var[u;] = o² by (1). Taking the expectation w.r.t. XI,..., Xn, and leveraging symmetry, we have
Ex (20 X) [[8]] no² ox. where o e Ex
k2
(58)
[=" k(X..zo))
ox can be bounded by
2x < Ex
(X
S
up
+
2
Ex
[22 (x1,
[n k(X,
20

---

$ P
np
+
2 Sx (0
where step (i) follows from the fact that
ka Ei k(Xi.to))
1. Using Bernstein's 's inequality [29,
Prop. 2.14], the first term can bounded by
P
PE T
P 2i=1 1
np S
(np)² S cxp 2(n7(1 D) 07/3)
S expl -
for some universal positive constant c. Applying the fact that p is bounded by Assum. I and is square-integrable by Assum. 2, we can bound the second term by
ap Sx k2 (21 (o)(z)))(
np Pm Sga x² (u)du
(4) (mp)7
(a)h))
n
for some positive constant 02 that does not depend either h Substituting these expressions into (58) yields bound on Ex (wo; X) [[[]] as desired.
B.3 Proof of claim (38)
Define the following shorthand for the bias:
b(zu; X) & Byix [((o)) ff" fxo))
We state a more detailed version of the claim.
Lemma 4 (Bias of Nadaraya- Watson). Suppose Assum. and 2 are satisfied and the event (32) holds. If I E EB3 Lf) for 3 E (0, 1}, Ly > O, then with high probability, the following statements hold true uniformly for all vo X:
(La) k is compactly supported, then b( X) S Lyh
(L.b) Otherwise, k non-compactly supported, we have b(zo; X) S c Lyh log n for some positive constant that does not depend on
For completeness, we first state the proof of claim (La) from Belkin et al. [3, Lem, 2]. On the event (32), we have
(i)
En Ly [|x (k(X,, (18) S Lyh²,
b(r X
57))
(X
S Eiz: k(X;,0))
Er k(X,,ao)
where step follows from our assumption that f* Σ(3, Ly) and step (ii) follows from assumption that is compactly supported, so k(r, = 0 whenever || rall > h. We now proceed proving claim (I.b).
Step I: Decomposing the bias. For any E X, define the random variables
Ar(zo)
1 En k(X,, zo |I||, zoll < and
(59)
Ay(20) A 1
n Er 2o) || soll s 22h] for j= 1,2,.....
(60)
where
T
log 12 log
(logn)
(61)
when (.) has compact support under Assum. and h is defined by (40). We call these random variables the kernel empirical means. We can directly verify that
E Ao(zo) = En 20) for all Zg E X.
21

---

With these definitions in hand, may rewrite b(ro; X) in terms of Ao(xo), (1oo), ...,, Ar(so) as follows:
b(xu; X) 1. +E k(X, (xx,
E k(X,
En k(X,, X (
Ao( do(m))+ij= As(an)
Ei 1
A0( A3(20)
Eiss
Ao( (20)
Σ/ Eim k(X,, www.::/ppp-ccix---33333111-----.
Ao(mo)+ +/ As(o
(1))
Ee Lis x0
(62)
An(zo)+ -i= (z(20)
ΣT 21=1 Ei k(X 2 1 hx x 21
(63)
Au( - (,
where step (i) follows from the fact that ((X,) (wo) LyI|x; xoll by Def. and step (ii) follows from the fact that || zoll < h under the indicator functions. Applying (59) to (62) and (60) to (63), we have
bzz X) <
Ei A
S L
EE= Ei As(w0) )
A1(a))210
(64)
(o(m))+E Ay(1n)
A A5(20)
For any E X, define the following shorthands:
(=(=) 2 (x =) - =|| s /t]] and
(65)
for j= 1,2,..,, a (=) - Ex k((,, xx(x,x)][ x)) < || =|| S 2/h]]
(66)
We can directly verify that
Fx [Ao[=)] = az))) and Ex[A,(=)] = az(²) for all j = 1,2,...,??
Under Assum. 1, (=) can be computed directly from the decay properties of k as follows:
ax(2) -| 5k k(r, 2)px (dx) 2 Punin Sji=-Sish k(0, 2)dr
az(2) = 121-1 <|===1 k(a, =)px (dx) S Pmax f21-1 < k(r, z)dr for j = 1,2,..... T,
Remark 1. Note that for fixed Do E X, A,(ZO). Hoeffding's 's inequality implies that A,(xo)
concentrates uround a (xn) for all = 0, 1,.,,...
.,. T with high probability. Assuming that decays ((a((ro)) for all j [T]) we have
sufficiently rapidly (so that a az(2o))2t
b( X) h (EL,0(1) (L logn).
remains show that this bound holds uniformly over zi E with high probability.
Step I:: Uniform concentration of empirical kernel means. Fix E (0, AJ and let Co be c-cover of X' w.r.t. the Euclidean norm (see [29, Def. 5.1] for the detailed definition). We will optimize the choice of e at the end of the proof. By [29, Lem. 5.7], we have
CCo < (1 + 2R)
(67)
We now introduce slightly modified version of (65) and (66) defined
()(2) A Ex [[X X, 2|][I 2|1 < h c]] and
(2(2) A Ex [x(X, =)[ c ||X 2|| < 2' c]] for j 1=
respectively. Using the fact that h/2, Assum. and 2, and change of variables, we have
(z(2) 2 Pmin / k(æ, z)dx Pmin h h wa-1 S0² =(u)u==1dds du, and
22

---

az(z) S Pmax 1(2-1 -/1= - jm k(a, 2/)drr = Pmax Sp k(u)ud- du for jE [T].
where wa-1 & 2T/// (dd denotes the surface area of the unit sphere in R Moreover, consider the following concentration events:
(5(2) E k(X,, 2)]] - - c a5(2) - 40} and
(68)
A5(2) - H E k(X,, 2)
|X =|| s 2 cc] S d3(2)) + ر,} for j E [T].
(69)
where Do. A Ar are positive scalars to be chosen later. For any scalars 0 b and X, further denote the empirical mass contained within the ball or annulus centered at point by
Mass: 2 (a) 2 - +|| - =11 S a] and
Mass; (a. b) A n Σ I[a ||X; =11 b).
We now introduce a lemma that bounds the empirical kernel mean restricted to each ball and annuli:
Lemma (Uniform concentration of empirical kernel means). Suppose event Lecco N Af(2) (2) is
satisfied. Then for every zo X, there exists z/g E Co such that | x' ll S and the following bounds hold simultaneously:
Ao(ro) 2 a6(2%)) - Do Mass,ú (h -6-
c) Iike and
(70)
Ay(m0) S (0((1))) + Aj + Massy (2/-1)- e, 2 h + e) x( 22 n 2 for jE [T..
x022
(71)
Here, La and K(.)) are properties k from Assum.
See App. B.3.1 for the proof. This result suggests that we can control the error between the empirical kernel mean, A, and its (shifted) population counterpart, (f(2)) by choosing to be small and leveraging the decay property of k. To bound the Mass,; (h e) and Mass,, (2/-1), 2,25h + e) terms, we define the following events:
Mo(xh)) A (Mass.;, (h <) S Ex Ma (h- c)] + to) and
(72)
(x66)) A (Mass,r (2/-1 h - e, 2 + e) S Ex [Mass (2) e, 22 + +c) +tz} for j [T],
(73)
where la, 41,...,44 .....,, lr are positive scalars to be chosen later. For any scalars 0 < < b, we may apply Assum. obtain
Ex [Mass.;(a) (a)] S Pmux Vol(a) and Ex Mass (a. b)] S Pmmx Vol(b).
(74)
where Vol(r) & nd /dd/2222+ + 1)rd denotes the volume of the Euclidean ball B2(r) C Rd.
Step III: Putting things together. For any Co, note that
=] X; - =|| < - <] E [0, ||]]]]] and
=) - c < X - =|| < 2 + c] E [o.
and therefore these random variables are sub-Gaussian with parameter a bound (68) and (69) using Hoeffding's 's bound [29, Prop. 2.5], obtaining
|k|
Thus, we may
P(A{(=))) S exp {
2nd3
||<|| for all
0, 1, 1,...,T T and E Co.
(75)
Again by Hoeffding's bound [29, Prop. 2.5], we have
P(M:(=)9) < exp( 2 for all i= i= 0,0,1.... T and z E Co.
Next, it remains to choose the values of e, Ao...., AT and la..... ..., lr. Consider
Ao = 1/4 W 1/ x(u)u du.
(76)
23

---

A 2- Toa Jo² x(u)wd-1do du for 1.1,2....,
(77)
to Pmax Vol(h - c),, and
(78)
1j Pinxx (2 + +c) for j 1,,......,
(79)
Combining (70), (72), (74), (76), and (78), we have on the event Eo & Nzeco (A5(z) n Mo(z)) the following bound:
rd (r( 2 Pamin h Sor n(u)ud- du Pmnxx r( e)d T&g.
2 h h (fPmii Sot x(u)utt du Pmax ri r(g+1)us LKE)
ad
So sa(u)ud-ddds du,
where step (i) follows from setting
= -minng (
h Similarly, for each j 1,2. ..... T, we may combine (71), (73), (74), (77), and (79) obtain a bound on (xo)) Hence, on the E, Nzeco (A5(=) n (2)))), we have
I Pmin So² x(u)ut- Pmmx r( x² 1(g+1)uu-1 T1ke
(80)
A, (10) S Pmax S 1 2 k(u)u* d- du + 2-50 Ja k(u) ((u)ud-id)) + Pmax +( (2 h + c)d x:22' 12-11-2-
Pmmax Piaahhwas-
21- n(u)u 2 du + 2- Jot k(u)u - +
r(s+1)uu k(20-1 - -1))
where step (i) employs the fact that S h/2. Note that for j = 1,,,....* T:
23 23-1
x "(u)a" Adu+ a(a)a" dut * *10+ 11 rc4 -1wa-- x(25 1-1)
(2)))24
S
4Pmmx
= =011)
Ao(za)
Puiin
10 k(u))ut-dd
(81)
where the last inequality comes from the fact that
2/8
23- m(w)a==idd du
2d
Ara 112 0(1)
rC res+12a--
= (() and
10t a(u)ud-idu
S u(w)ud-Idd
by Assum. 2. Substituting this bound into (64), we have
(64) b(zo; X) I L ET
(((a))228 Σラ= (a
I L (EL
A.(o))230 Ao(zo)
(1)
S L (61)
OlLph logn)
as desired. Finally, it remains to control the probability that this bound on b(zo; X) holds. Applying union-bound, we have
(67) P(E U... U..)
2n S (1+ + 2Rtd Σ [xpp
+ exp 2nt??
| j
$ (1 + 2Rd d ΣJ Σソ= (xxp -cthh - + exp ccnnhid))
18 787 + exp - conh?dd)) (1+ 28 ( + (cxp -1nh 2d
for some universal positive constants c1, C2 that do not depend on n. Note that by (80), we have (1 + 28 d = ((1 + # 1)d). Setting h = en zaiza as in (40) and recalling that = Ollog n), we have P(g U....... ...... U EE) for sufficiently large n. This completes the proof of Lem. 4.
B.3.1 Proof Lem. 5: Uniform concentration of empirical kernel means
Fix any To E X. By definition of Co. there exists 26 E Co such that || x'6l I e. Consider any B2 e; 2 By triangle incquality, || zoll || z'6ll + ||ا/ zo ll S (h - e) + e.
Therefore, we have
(2 x6)) Bg mo).
(82)
We now introduce the following lemma, which sample version of [10, Lem. 8]:
We use the notation BB (r::)) 2t) to denote the Euclidean ball of radius centered E R.

---

Lemma 6 (T.20 bound 1,2 kernel error (finite sample)). Consider any bounded kernel k T,2,00, points 20, 20 E X, function E 1.2 (TP.) For any r, a, 2 with a a+ = 1, points F1,-- In E X. and set A X, we have
E (kz;)(k(zs, - - 2))11a(z)))
S =100 |Ik(;,
Mass ( ( + A =bll 2 br]
where
[I A (
|| max ( (2:4
(r) - 1/2 Σ || 2; - S r, E A]
(F) sup E of mo.=o } + Ei=l k² (x x' Ull== 21, A\)
|||A,,2 - sup x' a( | x') I.
See App. B.3.2 for the proof. We now use this lemma to prove each of the claims in Lem. 5.
Proof of claim (70). We consider the following basic decomposition:
+ T i= k(Xi, 20 [|I - zoll S h]]
(83)
1 E kX,,, 2/) | X; - ='1l |l - - c]
(84)
- ( E k(X,, [|| - ='6ll S h -c]
-zoll S hi).
(85)
Note that the term (84) can be directly bounded using the definition of (68). Next, we bound the term (85). Define
g - 1 and B2 E; x/));
so that [l = Mass? 1 2/
(12 - e). By property (82), we have
I[II; 2'6l S S I[|| X; rol s hl for all
i= 1,2,.... ......
(86)
Observe that
7 E (Kx)))((X,)) mn) k(o,, La
(87)
1 [k X1, x/6) k(X,, zp | - -'oll S h -
1 Em k( Xi, [[[ X, m'6ll S - - Σm k( [X, vn |[|| - =b6l - h - c)
(86)
1.4 ΣE k(X,, 26 U||| X, 266l < h c {] - Σ
- k(X,, xo ||||| xol || S h).
To upper bound (87), we now apply Lem. with r= = h, a == 1.2 and = 2 to obtain
1 E g(x;) (k(;))(((;; zT) - k(r;, x/) 14
I Mass 3 20 (h- e) [k((50)) k(-,z))) Mass + 2Tx.A + 2
- 2b61 > 2
c). < Mass 20 (h- c)) [[ne -Mss 3 (h- e c)}
(88)
where the last inequality uses the fact that
[kk(, k(,,a/)llA.c S Lx||20 - 2'bll s LKKE
from the Lipschitz property of k (see Assum. 2) and the fact that
Mass (h) = Mass & (h- - c), Substituting the bounds (68), (87), and (88) into the decomposition (83) yields the desired claim.
Th (=)= 0, and | - Fol < 4
25

---

Proof of claim (71). We consider the basic decomposition:
| -> i=
-X 2 2
2o
(89)
1 == -x
- =z/ll - 2 +
(90)
+ E x(,, - 2
Σ x6)
|| - - 2 + +e)
(91)
Note that the term (90) can be directly bounded using the definition of (69). Next, we bound the term (91). By triangle inequality, we have
| roll S I - zoll + 1 2'ol S 2 c. for all
E IB (2'(2); zo);
which implies that (22 .o) C (22(2'h+)3r() Moreover, we can verify that B3 (3(2) 1 h- 36) C (2;2-11; Hence,
I[2 ||x moll
= 2 S
zbll 2 for all i= 1.1,..... ... n.
(92)
Now define
g - 1 and
A - B2 + +, (2 - =;4%)):
(93)
so that [l = Mass %11
(2/ - 2 + t). Hence, (91) can be bounded by
k(X,, x [2 2 /2 < || - zo - 2 Σ x e < ||X,, - -
2 s 22hh+ +
E k k(Xi, 1
|| - =b - h + c]
k(X;, 21 22 - < |Xx - =bll - 2' h +
E (K),) k( 1)))
I Mass (2 /2 e, 2/ + +e) ||| v0) k(, A Mass " (2(2')
(2 + + 2 | A,,3 || =b 2 2 + +e|
(94)
where the last inequality follows from applying Lem. 6 with 2(2 + E) and a = b= 2. By triangle inequality, we have
1X xoll 2 XX - 2b - || - xoll 2 (2/-1) c) c c 22-12 2c,
where step (i) follows from the definition of A (93). Since is monotonically decreasing by Assum. we have n²( [X, [X:=
h s x( 2 Thus, we have
[l)(; k(,, 1b)l,, S max (ok((()((,zz))) A,مo:
I max { (s(2 1 rr( 22 } }
k( 2 1 1-22)
(95)
where step (i) again uses the fact that x monotonically decreasing. Moreover, note that
Mass A + ))) Mass (25-1)- 2,2th +c),
TA,k I 26ll S 2 c Substituting the bounds (69), (94), and (95) into the decomposition (89) yields the desired claim.
and
B.3.2 Proof of Lem. 6: 0 bound on T,2 kernel error (finite sample)
Define the restrictions
(x( = 9(x) 1 (x),
[c) = gr,
k, x) & k(x, (2) and ( 2 k kr
26

---

so that mm) = (2, (2, and k(2,)/)) (2, +k, (2,)))) We now apply the triangle inequality and Hölder's inequality to obtain
1/4 Ei= ((z;)(k(T) zo) - k(r,, (
Ei= Ir (o (k. (1)2
k, (2i, (Z)
Ei= gi " (a:))(c,((0 k:-² (1Z2
Ei= Ir (k:) (1) 20) (
+ Ei= gr (0) (I:) (k, (0)
(1; (k,))
k.¹) (5 La)
< |1gr La Lalla ([(((;))0)) - ((,,x))]1a()))
(96)
+ H Dr (c) (k(r, - k k =6) 1 (2:;)
(97)
where || -1Ie-(P.)) is defined by [[]]) E To bound the term (96), we apply Cauchy-Schwarz to or L (L to obtain
|19. L. (P.) S 11ge LAll v (r) s II v Mass (r).
Next, we bound the term (97). For any x² E {zo, m6) and x; satisfying [| a''l 2 r and scalars a. b E [0, 1] such that + b 1, either 1|= - -2;ll 2
or ||a* a'll > br. Hence,
E 1==1
(c) (k(at, xo) - k +6), =()1)((;))
i= I|| - zull 2 rlgs (0) (zi) Emvefroitt k(z,, x" ( (x*) 8og (x*1)) a
Ei= = Ex I[| - x*1l 2 arlgt (c) (1))))((ss==)) (x*) - 8ee (z. (x98)
4T;
1 Ei Exe E( U|| zoll > (2) (xx)))(" - dugg (x*))
Ta
(99)
where we define 6m (2) 2 I[: mol and (z)
(z) A [[= x/gl.
Bounding (98).
Exchanging the order of the summations and applying Cauchy-Schwarz, we have
T = Σ Ere(ao..0)
# - I|||=* z;1l 2 orlg (x,))<x* (z) (x*) (xg())))
}
E Eneezo:th
1 E I|||, - x11| 2 arlg [1
(2)00=)) - 8e6 (x*)
1 7/2
1 E I[[|: x1
"
2 Ei
T[| - x'1l 2 ar
k2
(z,
1 (x*) 5ng (x*))
1/2
E
1 Em [|] x² 2 arl (4) (z, 2 (2x))
suprrefzooó ( -
(r 1000 (x*) Sag (x*)
Ereetene 11g LAll - (ar)) (xm) (x+)
2 IAlle(E,)) ((r)
Bounding (99). Rearranging the terms and applying Cauchy- Schwwr,, have
T2 = [E=e(conte) T[||=* - x'61l > br] En gi (0) (m.) k( xt LL (Z:) (x*) - 82g (a*)) 3)
$ Exeef Al||=* - 4'61l > br] 1 E. of (e) (I:) (u =1 1800 (2+) - 6gg (x+)
< 3x' E I[||== - 2'6ll > br] ||g 1 Lall sup P [k(, x0) 1 1alle<(P))
27

---

8zo (x+) dug (x+1)
llg LAlL sup, apo [lk(;,²)) -1ll T[
=oll br]
C Proof of Thm. 2: KT-KRR for finite-dimensional RKHS
We rely on the localized Gaussian/Rademadee analysis of KRR from prior work [29]. Define the Gaussian critical radius En > 0 to be the smallest positive solution to the inequality
In (H;
<
R e 2n
where Fe; A En sup JEF: 11
E we wo(())))
(100)
lt (3) is the Il-lk-bblll of radius 3 and wi ~ NN 1).
Assumption 4. Assume that [|f [x(R) and fKT, Bx(c, for some constant o > 0
Note that for any g E Bx(c;R), we have
(9) l0 S suPzex (g, k(: a)) S supzex I19]1 (k),)))ll S | /kl SRRVIkkl L
where step (i) follows from bounded. Now define the Rademacher critical radius ón > 0 to the smallest positive solution to the inequality
Thus, the function class Bk(c R) is B-uniformly
R₂ (6; S 82, where Fd; a Ez, sup JEF: 1fll.50
1/- Em vff(xa)
(101)
and v = +1 each with probability 1/2.
Finally, we use the following shorthand to control the KT approximation error term,
Tn.
(2 + 20 (n,, Nout; 8, Rins Toout }), where
(102)
Thame
Ri max ||1|| and
||
oo.in Y-
(103)
max
and 20k is an inflaction factor defined in (29) that scales with the covering number Ni (see Def. 2).
With these definitions in place, we are ready to state a detailed version of Thm. 2:
Theorem 4 (KT-KRR for finite-dimensional RKHS, detailed). Suppose the kernel operator associated
with k and P has eigenvalues μi 2 Z Pm > (by Mercer's theorem). Define Cm - 1/ pm Let En and 8n denote the solutions to (101) and (100), respectively. Further assume"
no > log(4log(1/6w)).
(104)
Let JKT.X denote the KT-KRR estimator with regularization parameter
X 2 2 where &. - S V AV (I. + 1)
Then with probability at least 28 2e (0 we have
I.TKT. - - + + +52
(105)
where recall 8 the success probability of KT-COMPRESS++ (24).
See App. D for the proof. We set X' 2c2 that (105) becomes
ll f 113 < 3r I co
(106)
It remains bound the quantities e, (100), 8, (101), and 17,k (102). We claim that
en - Co R v n
(107)
NNote that when k finite-rank, this condition is automatically satistied.
28

---

5n S caby" m mmllo Bont Bont (1/6)
(108)
1n. S C2
(109)
Bont
for some universal positive constants C1, C2. Now set
R || 1/ δ 6=e-1/R
Thus, have
Sn S c T VbV 4yCm TH
VnAAous
for some universal positive constant d' Substituting this into (106) leads to the advertised bound (19).
Proof claim (107). For finite rank kernels, As = o for j m. Thus, we have j=1 As} L Vmee. From the critical radius condition (100), we want min(=?,
m R may e RV=
Proof of claim (108). By similar logic as above, we have E min = v mmo.
From the critical radius condition (101), we want _ m < 52 so we may set o, = b/2 -
Proof of claim (109). Consider the linear operator T H R that maps function to the coefficients in the vector space spanned by {Ør [ Note that
|| < 1/lk
[T]
Since the image of has dimension m, we have rank(T) S m. Moreover, | S pr 912 Now we can invoke [25, Eq. 14] with a/nout to obtain
(Td a/nont) S WT,, a/Noot) S (1 + (ug 9i nout/ /a)m
Taking the log on both sides and substituting this bound into (102), we have
ln.k
a²
(2 21k (n, Mont, 0, Rins Hour
a
Noue
+
log
nout log(n/nous))
) [log(t) + log (Bs(())) a
Nout
now
a² (2 +
log
Pout Iog(n/Doul
(og(()) + m log 1 2||T||
Nour
V m- m-log Root -loge
Rout
for positive constant that doesn't depend m, Nout, 8.
D Proof of Thm. 4: KT-KRR for finite-dimensional RKHS, detailed
We rescale observation model (1) by I so that the noise variance is (f/l]]*>)))) and our new regression function satisfies || [| = Our final prediction error should then be multiplied by || to recover a result for the original problem. For simplicity. denote
= l/
For notational convenience, define an event
[Il 1 S c(E + x)),
and our goal is to show that & occurs with high-probability in terms of IP, the probability regarding all the randomness. For that end, introduce several events that are used throughout,
Ecoee A
supeEn |1lll: ||allal <
&m T
and
Elower A {llSKT.N - ff > 5m (110)
29

---

where ón is defined in (101) and H. the RKHS generated by k hence star-shaped. Further, introduce two technical events (K)(u), ß&T defined (123) and (136) respectively, which are proven occur with small probability, and define a shorthand
Egood (En) Bir n &cone &XT,6-
Equipped with these shorthands, observe the following inequality,
P(E) = IP(E n Elower) + IP(E n (jwwr)
2 TP(E n Elower) + PP
(111)
where the second inequality is because Elower C &lower O & due to the assumption X > 2 > 26
we are able show the inclusion {Egood O Etower) {E Etower and that PP small, able refine (111) the following
((E) 2 Pgggdd O Elower) + (((owe)))) 2 1 - IP IP( + P(Elower) = 1 - P(Ee P(g good):
where the last quantity 1 - F(Egued) would be large.
To complete this proof strategy, we claim the set inclusion
{Egood O Elwwer) { Elawer)
(112)
to hold and prove it in App. D.I and further claim
P(EguN)) S cd(6 + e (B8./ (B22 e
(113)
which verify in App. D.2.
Putting the pieces together, claims (112) and (113) collectively implies
P(E) 2 f + e-c -c'n6, c=203/(B,
desired.
D.1
Proof of claim (112)
There are several intermediary steps we take show the inclusion of interest (112). We introduce the shorthand
ÅKT A JKTX--1 J
By invoking Propositions and basic inequalities to come, we successively show the following chain of set inclusions
Egood O Elower Egond 7 Elrwer n [||
Hoom Sc(EE + X))
(114)
C Eoood O Elower n { || & cEE + X)}
(115)
Egood O Ejower N
(116)
Elower E
(117)
Note that step (117) is achieved trivially by dropping Egood- Further note that (115) is the crucial
intermediary step after which we may apply uniform concentration across n independent samples.
Proof of (115) leverages the Proposition come (Prop. 1) that allows || || and I| to be exchangeable for finite rank kernels.
Recovering step (114) Since FKT, and fo are optimal and feasible, respectively for the central optimization problem interest
min Nous Erer (yl [(x())² X1
we have the basic inequality
Enow (16 ( + +
1 Doou (1), (+x)))²) + X (118)
Pout
Mout
30

---

With some algebra, may refine (118)
AKT
Mout
Eisr of (KT())) + x(11-11R - 11
(119)
Noms
where AKT = SKTX Suppose that | < En. then we trivially recover (114) by adding X > O. Thus, we assume that || Ex.
Under the assumption | 2 En. which is without loss of generality, utilize the basic inequality (119) and control its stochastic component
Pout
(
Pout
with careful case work to follow, which is technical by nature.
Case where I.FTT, ll 2: Under such case, we introduce technical event
ART(U) A {
13 3g Ey F
(2())) n (lgglnow 2 ut such that
Nout (g(((a) 31lellmow w
Phous
for any star-shaped function class J C. H. Since |lf 1, triangle incquality implies |kTTIk S llfer, xx w/lk= + Il.f
Moreover, on the event &lower (s Egood). we have ||árrlla > 6n Thus, we may apply ÄKT to the event (Ex)(En) with F 18 (3) (i.e., the H--all of radius 3) to attain
Tous ((KT(T))) s coEn. (KTTI/AATT|IR... on the event (kr((n) n Elower
(120)
Upper bounding the stochastic component of the basic inequality (119) by (120) and dropping the 1l term in (119), we have
|l 12 coEn | Inou X.
As last step under the case 1. l < 2, apply the quadratic formula (specifically, if a, b 2 0 and x² ax S O, then x S a² + b) to obtain
1 S 4c + 2X.
Case where fi ll& > 2: Under such case, by assumption have fKTT, > 2 12 |[ Thus, may derive the following
|| Il, < and || + 1
which further implies the following inequality
|| II 12 lI
II + 115TT, S 111s1Ix
II (121)
Further writing fKT, f + ÅKT and noting that |[ - |15 S FRTT,NIIK holds through triangle inequality, we may further refine (121) as
|| Il llx 2|1[/"
|KkTl| < ||
so that the basic inequality in (119) reduces to
AK Tout
Eie of (KAT((T))
+ X [[ār]]kk)
(122)
We again introduce technical event that controls the stochastic component of (122), which is
BKT A FgEFI F B2(6.) Allalk 2 1}
{
(123)
Nout v/g(x?))
> 46n Ill + +25211911
12
Mont Diml
31

---

for star-shaped function class F C H.
By triangle inequality, have || llfTr,, - 11 1, and event Elower (C Egood), we have | 2 > 8n Thus, we may apply ÅKT to the event BKT, and the resulting refined basic inequality is
I 45 + (2 X) l + 2X
I 45n | hout
2X on the event BKT n Elower
where the second inequality is due to the assumption that X' 2 25, We apply the quadratic formula (specifically, a, 0 and x² ax bb S O, then x S a² + b) to obtain
1 4cj5s + 2X'
Putting the pieces together, we have shown
| c(E + X))
on the event (KT(En) n Birr n Ejowers
which is sufficient to recover (114).
Recovering step (115)
We now upgrade events
(1kkT S <c(5 X))
(1 S cd + x))
by exploiting the events & n EKT, (subset of Eguod) that otherwise not used when recovering (114). For this end, the following result is crucial ingredient, which shows that [1-Ilmoot and II-IIm are essentially exchangeable with nigh-prbbability,
Proposition (Multiplicative guarantee for KT- KT-COMPRESS++ with KRR). Let C. 2 1/ and suppose 5n satisfies (104). Then on event εxT,s n Econes where ExT.8 and Econe are defined in (24) and (110) respectively, have
(1-4Cm T7n.k) S 1191|non $ (1 4Cm .7,kk)lll1
(124)
uniformly over all g E such that ||s/l12 > 8n.
See App. D.3 for the proof.
An immediate consequence of Prop. is that
II S c( + X)}
[K < dd + +X)
on the event εKT,S O &cunc n Etowerss which is sufficient to recover (115).
Recovering step (116) Our last step show
AK < d' + X))
(1 S + X)).
Such result can be immediately shown on the event Econe by observing that ÄRT H. by our assumption that f E H and by the definition
FK E argmin Liow (f) + XIIfI
D.2 Proof of claim (113)
It suffices to show the appropriate bounds for the following four probability terms
P(AKT(Sx)), P(BKT), P( P(E
Fix the shorthand
Bx A |||| R < co.
We know from [10] that P( (S,) < å and then we may apply [29, Thm. 14.1] to obtain a high probability statement,
PP <'nn6,/
(125)
Now present two Lemmas that bound the IP(: S..) probability of events AgT(En) and BKT.
32

---

Lemma 7 (Controlling bad event when [, ||x 2). Suppose uz Eu- Then for some constani
c 0,
P(ART(U) Sm) S - + -cna
(126)
where ō = =o/1lS"
See App. D.4 for the proof. Note that by plugging En into (126) results in a probability that depends on Sin (as çn depends on Sm.) By invoking the definition of En. we may further refine the probability bound of AKT(Sn) by
(EAKT(En) Sm) S 5 + e e-nn6// BB + e0
(127)
Lemma 8 (Controlling bad event when [1 11 2). For some constants d 0,
P(BK Sm) S + e con0 / ce ce-nea/(c
(128)
where ā = =
See App. D.5 for the proof. is notable that &n in the probability bound of (128) contains a term En defined in (100) that is function of Sin Invoking the definition of En. we observe the probability upper bound (128) can be refined
P(BKT Sin) 5 56+e-on0 BB + ce co-_
(129)
which does not depend on S..
Putting the pieces together, we have the following probability bound for some constants c, d' 0,
P good Sm) I (((AKT(n)) Sm) + P(BKT Sm)) + PP Sm) + PPERT, Sm)
(125X127K(199) I
ef + (66
thereby implying P(g S c c'n., (12
for some constant e".
D.3 Proof of Prop. 1: Multiplicative guarantee for KT-COMPRESS+4 with KRR
Fix g E H. Denote (g, h) f g(z))(()))) (()ddr as the inner product in the L sense. By Mercer's theorem [29, Cor. 12.26], the k-norm of has a basis expansion l Ei (g. 0.) /A, so that
| < Σ _ (g. 2.) /
1lgl2 since
C.n 1/2m-
(130)
The assumption ||g||2 2 5, implies that on the event Eoonc (110), we have
5nn S |اا1| 5 S lgg1:
(131)
Moreover, g must be non-zero function. Note that 9² E H(KRR) (see App. F.3.. Thus, we may apply Lem. 14 to fi = f2 = and = 1, b = 0 to obtain
|| | En (x()))
Hous Enen g (x S llgli In.
(132)
The LHS can be expanded as
||l|| - || 1. |||a||
||9
||r||
||l9|n + ||g|lroul
by (131)
Thus, we may rearrange (132) and combine with (130) to obtain
||l lz |n
Toll Malloo 7n
Cm Ball
(133)
On event Econc, have
(6) || $ (25,. + 11
(110)
x - 5.llll1m + +11911.
(134)
33

---

Thus, have
(134)
6
5,, 8.11olln
119
Mart
I1gll 11 nous
11 i nout
19
Pout
(131)
62 + on + 11911n
11
2hn
11ll +1 Fgll
6 + l1glln
(131)
3||g|la
11911 411g|1n-
(135)
Using (135) to refine (133), we have on event εkr,5 n Econe:
||glln - Illlno... 4.mmlllli lnnkk-
With some algebra, this implies with probability at least - expl - nd BB.):
4Cm 17n,k) S I1gllnou $ (1 4Cm 17nkk)
uniformly over all non-zero H such that ||l|| > 8n.
D.4 Proof of Lem. 7: Controlling bad event when
|| 2
Recall εKT,6 and &cone defined by (24) and (110). Also recall that ÊKT, n &come combined with the assumption ||و|| 2 on invokes the event (124). Our aim is to show
Akr(u) n E n Evone S (2n) > 2u²), where (n(()
sup gEF: 119 19
EE (.
(136)
so that we have probability bound
((AKT(u)) & ((ERT,))) + P(E + (2)) 2 2n²).
The first RHS term can bounded by 8 (see (24)). The second RHS term can bounded by (125).
The third term can be bounded by
(6) (2u, 2n²) = (M) 2 /2/2+ u2/2) 3 (u) 2 ue,/2++ -2/2+/// u²/2)
582
where (i) follows from our assumption that u 2 en and (ii) follows from applying generic concentration bounds Zn (u) (see [29, Thm. 2.26, Eq. 13.66)). Putting together the pieces yields our desired probability bound (126).
Proof of claim (136). Consider the event ART (u) & The norm equivalence established on the event εKT,8 O Econc in Prop. 1 is an important ingredient throughout.
Let E H be the function that satisfies three conditions: ||اا| &n IIgllmow. 2 and
Hous Eee c(g(()) 2 311gg|mmou
Define the normalized function
= 9/l1g//mn..
so that it satisfies || mgll and also
Dier
2 3u².
(137)
By triangle inequality, the LHS of (137) can be further upper bounded by
(p(()) < C==,00(0))))
Tallonn Ei= v:g(xs)
x(g(x;))
Yout
nour
(138)
34

---

Recall the chosen y satisies noul u. Observe that
mgg(s;) ! (yi (x()))))()))) (xa)g + vig(zs);
so we may apply Lem. 14 with fi = f2 - and a = 6 = 1. Thus, on the event &XT, O E we have
1/ m Σ (gg(a:)
Per v/g(z))
S
+) Jn.k-
(139)
nout
Thus, we may rearrange (138) and combine with (137) and (139) to obtain
1 Σ vz](z))
2
3u²
1 (1) fll + 1) 77.k
alll
Note that
119 k 1 moat
||ll
19ll2
T
11 m
(130)
We tackle each term in turn. First,
VC m
Since assume ||ا||2 2 8n we have
llllla lall=
21/2l1llll
(131)
I
2 on event E and
lall.
(144)
S
2 on event Egone n EKT,5. Taken together,
Pont
lalll
4vC event Ecome n EKT,S-
(140)
Iglloout
As 2 En 2 (I
1)m,k k by assumption, we have therefore found g with norm
[ Hous satisfying
1 En v0((x))
2 3u² u2 2u².
We may further show that
9 ha Tallmout I1lln S u [[
I u 2 on event Esenc O E
where the last inequality follows from the fact that ||g||2 2 8n and by applying (144). So we observe
2n < Σ v.)().))
S Suppp l. El v1)();) Z (2u)
D.5 Proof of Lem. 8: Controlling bad event when fI >
Our aim is to show for any E OH with l|9ll 2 1,
Thou ((g((t))
mllllll + 2C Ilglle + 1e Illll with high probability.
Tlast
Note that it is sufficient prove aim for g OH with llgll 1- by proving only for g with ||gll = 1, then for any 0H with || 2 1, we may plug g = h/|lhl| into
Dlen
< 2l.llg/ + 2 + 1/ 1
(141)
Tlgur
recover the aim of interest. So without loss of generality, show (141) for all such that g 0H and |ا 1.
Let Bxt denote the event where (141) is violated, i.e. there exists 87l with llalk = 1 so that
Pout ofg((=)) > 38lllel + +222 + 1l19112
(142)
We prove the following set inclusion,
BKT n εKT, O Eoonc
35

---

cf = g E on s.t. lllll and
n E.= v,((x,))
2 2En + 1o 1el1o11
(143)
where we know the RHS event of (143) has probability bounded by or neenee//e which proven in [29, Lem. 13.23]. So the set inclusion (143) implies bound over the event BKT:
P(BKT) S (T)) P( + CE (eenn///6
where P( 8 by (24) and P(E by (125).
Choose 9 that ||9|| 1 and (142) holds. Condition ||g|| = well as the condition (130) resulting from finite rank kernel k implies 6n S 1 S ||g|| I vCmllgllz Invoke Prop. 1 for the
choice of that satisfies ||al|2 2 6n/vCn 2 8n, so that on the event &KT,5 n Econce we have the following norm equivalence,
n/z ال 2 I19llo.. S. 1llll1 for any n such that Cm Tn,k S 1/18.
(144)
Then we have the following chain of inequalities, which holds on event Econc n εKI,6
SE=rva vg(()))
Ei=1
n Ei= v2g((ss
Thus Eiet vlg((())
Mout
35 155.1gllmm
+ + + lllgl1?.om - 1191l + 1) 7n,k
(1410)
2
+ 262 + El1gllmgum 4v mlmlmllmmm (llf + 1) 1n
S. 2 |1 + 1) (l9,l) + 2 + I6 Il
(145)
where step (i) follows from triangle inequality and step (ii) follows from our assumption (142) to bound the first term and our approximation guarantee (139) bound the second term. By definition of En, we have
S. - (If + +) Tr.k 2 2
Using this to refine (145), we have
Σ vgg(2;) 2xll1lll, + +
16 19911
which directly implies the inclusion (143) desired.
E Proof of Thm. 3: KT-KRR guarantee for infiniteddimensional RKHS
We state detailed version of the theorem:
Theorem 5 (KT-KRR guarantee for infnite-dimensiinall RKHS, detailed). Assume f H(k) and Assum. is satisfied. If is LoGGRowtH(e,, (o, (3), then for some constant e (depending on d, o, B), FRT. with X' O11 satisfies
I. 13 S e log" n
Vlgg Nous ) 11 1]3
(146)
Hous
with probability at least 1 - 28 2e "xill
If k is POLYGROWTH(C, 3) with E (0,2), 2). then for some constant e (depending on d, a. 3), FKT.
with x = =0(r -2-0 satisfies
lIKKX - fr < cllf
n + [|lf* 11 +
172m n -
log nout + dbbzaa zia
(147)
with probability at least 1 28 2e
36

---

E.1 Generic KT-KRR guarantee
We state a generic result for infinite-dimensional RKHS that only depends on the Rademacher and Gaussian critical radii well the KT approximation term, all introduced in App. C.
Theorem 6 (KT-KRR), Let f E H(k) and Assum. is satisfied. Let das en denote the solutions to
(100), (101), respectively. Denote fKT,X with regularization parameter 21m,k. where In is
cIe 02 "
defined by (102). Then with probability at least 25 2e airigt
have
|l - S Ufull + UKT where
Ufull - cle X) + 1)²
c6
and
UKT & c. 1n. [II || 1]2.
See App. F the proof. The term Tfulll follows from the excess risk bound of FULL.-KRR Stull The term UJT follows from our KT approximation. Clearly, the best rates are achieved when choose À = 2m,.k-
E.2 Proof of explicit rates
The strategy for each setting is as follows:
1. Bound the Gaussian critical radius (101) using [29, Cor. 13.18], which reduces to finding
e > satisfying the inequality
2/4
E min(s?, S $,86, where
B A l
(148)
and A1 2 2 ... An 2 0 are the eigenvalues of the normalized kernel matrix K/m n,
where K is detined by (5).
2. Bound the Rademacher critical radius (100) using [29, Cor. 14.5), which reduces to solving the inequality
E min (02 M4) S
8²
(149)
5
where (mz))=1 are the eigenvalues of the according to Mercer's theorem [29, Thm. 12.20] and is the uniform bound on the function class. 3. Bound Tn.k (102) using the covering number bound A (BB))R).. e) from Assum.
In the sequel, make use of the following notation. Let
R A supzes,,
||
(103)
Rn and Ix(r) & Cu n log?
according to [16, Eq. 6], where C. is the constant that appears in Assum. 3. E.2.1 Proof of (147)
We begin by solving (148).
Lemma (Critical Gaussian radius for POLYGROWTH kernels). Suppose Assum. is satisfied and POLYGROWTH with < as defined by Assum. 3. Then the Gaussian critical radius satisfies
2
2 o
(Rn)((1
(150)
Proof. [16, Cor. B.1] implies that
Agj < 4
(u(RR) 1-1
for all j j> L (R() +
37

---

Let & be the smallest integer such that
k > (R( +1 and 4( (xrlttn) =
By Assum. 1, Rn is constant, so the first inequality is easily satisfied for large enough n
k 2x22=LL (x()))s +1.
(151)
Then
2
Ej=1 min
2
kea + Ej=k+1 4 (u(RRn)
1-1
Vn
(4)
_ マा V
kE² + 3
2/a-1 ki 2/1x
(151)
$ マ v
2 La (1n)) =2-
4.22 a
L2
52
2/a-1
where step (i) follows from the approximation
Ej
(R))
< <4 Sx 122/a (lre(Rn))
2//
k1-
2/a-1
To solve (148), suffices to solve
2c v
2 a
Lu
Rn)) )1 (1+ 2/a-1)E2-0 ) BE
16
Zia
L R.,. (1 (1+
32a 2-a
21a
2ia
Since en is the smallest such solution to (148) by definition, we have (150) as desired.
We proceed solve (149).
Lemma 10. Suppose Assum. is satisfied and k is POLYGROWTH with 2 as defined by Assum. 3. Then the Rademacher critical radius satisfies
2a b2t0 2 I 32cc
20a 24a
Proof. Thus, we can solve the following inequality
Vj min n3 152
Following the same logic as in the proof of Lem. 9 but with B yields the desired bound.
Finally, it remains to bound (102). We have
nn,k
a²
(2 Wx,n Mout, 8, Fi niu..)
Pout
(2 +
log Mout log(n/nomi
(log(t) + log (BB moit
a² Mout
(2 +
log
Nout log(n/ log(n/neus)
[log(] ) + Cul (rous) )d1 "(Ri + 1)
a² Bont
2 + V
log
Nous log(n/momt)
VLog(E) v Ca
(9t +1) x
nout
5 nout
a²
2 + log
nont logg(n (aan///aaa))
+100 a"
for some universal positive constant c. In summary, there exists positive constants co, C1, C2 such that
2 < co
17
a
Jt
T1
82 S Scbbzta
n 2
Ta.k S n2a2n
-22
log nout
38

---

Setting X C2aan 2
out
log Nout. wc have
1K - 1 v c
X + kn.k) [IIs* || + +1]2+ c
- S flll - n शंं |ll 1 + 1] nutt log nout + d'baian n zic.
E.2.2 Proof of (146)
We begin by solving (148).
Lemma 11 (Critical Gaussian radius for LOGGROWTH kernels). Under Assum. I and LOGGROWTH version of Assum. 3, Gaussian critical radius satisfies
log(2e.
11 4a
vny
Tae( Ca
for some constant C. that only depends a. where ignore log-log factors.
Proof. [16, Cor. B.1] implies that
A S 4exp 2- Lx( )² for all j > (x( +
Let k be the smallest integer such that
k > La (Rn) + and cxp ( 2
2 j-1
S E
By Assum. I, Rn is constant, so the first inequality is easily satisfied for large enough Lx (Rn) log (² +
(152)
Thus, h: = [L (on (2)) )0 + +17. Then
ke² Ej=k+1 4exp 2 222((zuti))) J-1 E22 A.. s 7a
[x(lin)
(153)
Consider the following approximation:
E exxp 2 22- In(R..) 20-2(T((m.)
+ +)
1/a 462 f00 Iulken
dt pk- clin dt,
where e
E (0,1). Defining m llgg > 0 and k' 1, we have
SK Ll dl < C. 1)
(154)
by Li et al. [16, Eq. 50), where C. is constant satisfying (xr + y)aa < Ca + y for any y and b is known constant depending only Plugging in k' [R,( log( 22 "1, can bound the exponential by
e m/ Se- -mmy log 2:) 2e -mLx(Ra)"
Note that can simplify the exponent by -mL (R,) - -Lx(( (/2 Lx(,,, -22/a, Note that K' k - > L(R,)) 2m - Thus, absorb the ba m term in (154) into I and obtain the following bound
E 4exp 2- 2 Ix(Hn)) )²) S C 2//4
where C², depends only a. Plugging this bound into (153), have
2 va
min <
2 / V ke² + +C,k(E) 21/a
2e 2e
V (x(B
log(n))g((( ( C%
39

---

3/ Vxx log( ()) "C
for some constant C" that only depends on a and universal positive constant c. solve (148),
suffices to solve
2c V La (k(nn) log 2) (" <
which is implied by the looser bound
Ae (x(Rn)C =² 2olooog (2) -a
The solution (148) (up to log-log factors)
(2g(2e-8 //)a//2
4c Ba
Ix(Rn)
e
VR
V
We proceed to solve (149).
Lemma 12 (Critical Gaussian radius for LOGGROWTH kernels). Under Assum. I and LOGGROWTH version of Assum. 3, the Rademacher critical radius satisfies
8 ~ logl logllo v/)"
Lu (R(R))
Proof. Following the same logic as in the proof of Lem. 11 but with 1/b yields the desired bound.
Finally, it remains to bound (102). We have
1o.k
(2 + 20 Mout, 5, Rins now:
Dont
(2+ + log Nost Log(n/ log(n/nout) /oott)
[log(t) ) + log N& (R.)) mom)) })
+ log Dout log(n/nomn)
[log(t) + C. log(
eRront (Rin + 1)8)
for some universal positive constant In summary, there exists universal positive constants Co. C1, C2 such that
2 e S 6D 1
log(2e:
1/ 1n
83 S ci 12 log( &5 //r/22
Tn S C2 Mout
log(
EMamm
ja/29/ 8/2 in
Setting X = 202 a log( eMout ja/2, we have
|ITKT. fr < c(Eu + X' mm.k) [|If*1|x + 1]2 cc5z
I log(2e: 11 vay"
+ [llff 1k + 112 c_ log( enamm )o/2 cbb2 log( 2r wnye//
Proof of Thm. 6: KT-KRR
Our first goal is bound the in-sample prediction error. We relate [l - f to II. 1 where the latter quantity has well known properties from standard analyses of the KRR estimator (refer to [29]). Note that regularization parameter X' of KT based estimator fKT, is independently chosen from the regularization parameter of the estimator based on original samples f For Srun, we choose the regularization parameter
2
(155)
which is known to yield optimal 2 error rates.
40

---

Define the main event of interest,
3 _ (1lKT,, - 1' - c(c + 8n + X + Tn,k)ll + 1]2].
Our goal is to show & occurs with high probability. For that end, we introduce several additional events that are used throughout this proof.
For some constant define the event of appealing in-sample prediction error of fKT.X,
(l),n(1)= - [I - 11% z cf{e + X' + mo.k] (I]/*|| + -))3] for 1 2 En-
where k, is defined in (102). Recall ε is the event where KT-COMPRESS++ succeeds as defined by (24).
Further f* and fKT. are both in {f H. | S R). we may deduce that all the functions under consideration satisfies I| S (ell=x1lffl S | Re where ||k]| < oc. Accordingly, we
define uniform concentration event,
Ebome - (supfer
| I1 - 11 + 6//23 where F= e H: 11 S 2 oz R)-
(156)
Event (156) analogous the event Eoone previously defined in (110) when dealing with finite rank kernels.
We first show that
n V 5n) n C E.
(157)
Notice that almost surely we have
[lTTT - 1" /2
thereby implying
1K - 11 2 1I 1 5% on the event &gone.
(158)
Next invoking the event (en 6,,) along with (158), have
Il 13113 < 2c((en V 5,,)² X km, (II [|k + 1)2 + 82
cle 62 X m 1/2.
which recovers the event of E.
The remaining task to show & is of high-probability, which amounts to showing events EKT, (t) and &ooe are of high-probability by reflecting on (157). From [29, Thm. 14.1], we may immediately derive
P(E 2 eie
-2 18 R3
for some constants C12 02 0.
We further claim that
"lr 12
P(EKT,n (1) S...) 2
20o
Cie
(159)
for some constants co, C2 > O. Proof of claim (159) deferred App. F.I. Plugging in / e, V into (159), and invoking inequality en V 6n 2 5n so as to decouple the dependence on Sin. we have
ns2
10
(C V 5%) S.n)) 2 5
age
c
which further implies
nd2
((E V 6,)) 2 21- - 200
Cie
Putting the pieces together, for some constants Co, > O, we have
P(E) 2 5 que -1 22 / 1
(160)
Overall, (157) and (160) collectively yields the desired result.
41

---

F.1 Proof of claim (159)
To prove claim (159), we introduce two new intermediary and technical events. For some positive constant Co. define the event 6 when in-sample prediction error of feall, is appealing
an (t) a {ILfan, 1 S 3c0 [ for I 12 En. En.
(161)
The second intermediary event, denoted as E (1), is the intersection of (169) and (170), which do not elaborate here due to its technical nature event E (t) plays analogous role to AKT 0 kT defined in (123) and (136) respectively.
Our goal here is two-folds: first is to show
( (t) n EKT, n E (t))
(t),
and second is to prove the following bound
P. E (1) n EKT,8 n E (1) Sin) 2 1 - 8 - o
o²
from which (159) follows. Note that Wainwright [29, Thm. 13.17] show
P(Etun, (t)) 2 1- eje -2 "
for some constants C1, C2 >> O and that P(EKT,5 Sm) 2 1 8. So it remains bound the probability of event E (t), which we show below.
Given f. define the following quantities
La (J) - ((t))
Σi= and Tont (F(((( ( 2f((=))))) Em=1%
Ligur (f) 2
In the sequel, we repeatedly make use of the following fact: event εxT,S defined in (24), we have
[Ln(F) Lnow (f) S (I + 2) .n.k for all non-zero E H.
(162)
The claim of (162) is deferred to the end of this section. Given f. we can show with some algebra that
I, 1 E. (f(,,) - v.)² Ilf f 2, E) + + e,
(163)
where Z A (f(x1) (21)...., f(xx) (xx)) and (EI...., En) are vectors in R.. Define the shorthands
ÄKT A JKT, 1 and Amm a J S
In the sequel, we use the following shorthands:
Ful (Aru((z1).... ..... (Anu(t))....AAnn((t))) and ZKT & (ĀKT(Z1), ... (KT()
Now for the main argument to bound 1 When | I t, we immediately have
Akrll < t², which implies (159). Thus, we may assume that AKTIIa 2 f. Note that
| 112 (163) In((KT,,x) + + ( - Σ
= =L, [n
- In((hau)))
(ZKT, E.
Given the optimality of FeauLA on the objective (3), we have
Ln (ran..))) < A -. + XIIME-
Il S C + +
"Since the input points in S.., are fixed, the randomness in Fran,A originates entirely from the randomness of the noise variables e.
42

---

where the last inequality follows trivially from dropping the - -II A l term. Thus,
AKT I = = -i c + A1 + [x(FTT,))))) In (FrulL,)
+ 2 (ZKT,
Ei= E?
s (2 A [In(FT,,)) In Phan.))
(164)
Using standard arguments to bound the term 2(ZKT, E), we claim that on the event Egp we have
A I ot (1lf"ll + 1) + d' [n((KT.x)) Ln (Frnnx)
(165)
al2 20
for positive constants c, d' and that P(E | 2 1 (1 (165) to the end of this section.
We defer the proof of claim
Now we bound the stochastic term [fTT)))))))))))))))))) Ln (fruua) in (165)- first observe the following decomposition:
[n(fKT,x) L, (frn.)) = (Ln (Fn(fTT.))) - Liom (FTT)) + (Enon (RTT,)) Ln (frn.)))
On the event εKT,5 (24), the first term in the display can be bounded by
Ln(frr - Lione (FTT,))
(162)
I (llfTT. + 2) mn.k.
Note that FKT. is the solution to the following optimization problem,
minge Lnow (f) + XIIf
so the second term the display can be bounded by the following basic inequality
D (fRT,)) X X1I S Lnon (FULN)) = X X1Iffmm l12 so that Innon (FTT,X)) Irngu (PrulLe) S X (1 1ITTT,,111
Thus, on event EKT,5, we have
Ln(fKTx))- - La (runns) S (lIFTT, 11 2) Mr.k + X2{ (Ilfann 1I
2mm.k + XIIFrann l1 + [mmk - N3 II l
(14)
2m..k + XI S.S V(II +
where steps (i) and (ii) both follow from the fact that X 2 21J, (see assumptions in Thm. 6). To
bound [ 11 we use the following lemma:
Lemma 13 (RKHS norm of fral,)). On event Egurt, (161), we have the following bound
ll <c0()
(166)
for some constant O.
See App. F.2 for the proof. Putting things together, we have
L, (fKT.) L,, (Pawix)) s cX(II* + 1)²
for some constant C s-suutiitutiig this bound into (165) yields
1 1* < (II 1)2 + d'X 1)2,
for some constants c', which directly implies (159), i.e. implying
(1) n EXT,8 n & (1) = E
43

---

Proof of claim (162). Given define the function
eg ; y +B where (g(x, - [2(x) 2y f(x)
(167)
and note that
(n Lnou (f) -i= 1 (,4, nout Etet (2 8/))
We first prove a generic technical lemma:
Lemma 14 IKT-COMPRESS++ approximation bound using KRR). Suppose S1, E H(k) and a, b E R. Then the function
f1.f2 x x where (1,3) a a. (x) b-)
(168)
lies in the RKHS H(KRR)) Moreover, on event EKT,8, we have
Finlr.Ja Qoml S (1al lkllfllk + |b| 11f22lk)) 7n.kk
uniformly for all non-zero J1 E H(k)).
See App. F.3 for the proof. Applying the lemma with fi - f. - and a 1, 22, we have Pint' Qomll S (Il 2) 17..k
which combined with the observation (168) yields the desired claim.
Proof of claim (165). Case I: First suppose that | ||x S 1. Recall that || 2 26> Sn by assumption. Thus, we may apply [29, Lem. 13.12] obtain
ne? e 20
a (KTT, 5) s 2 Akr
w.p. at least
(169)
ne?
Plugging the above bound into (164), we have with probability at least
e
202:
| < 4/ AkTllat + AI [n.(fTT)))))))))))))))))))) - Lu [n(Fruu
We solve for ÁKTIIA using the quadratic formula. Specifically, if a, 0 x² ax then S a vb. Thus, we have with probability at least 1 e 20
nc?
| 11 S a vb,
where
a 4f and
A 12 + IL (fKT,.)) Ln (mmnx)))
Using the fact that (a + vb)² < 2a + 26, we have with probability at least e
207
I.fKT, - f* < 321² + f 11 + (L (KTT,N))))) - Ln Ln((rnn
(155)
ctl + 1)2 + 2 2 (FKT.)) Ln Li (ua(Fann))) I
Case II: Otherwise, we may assume that | >
Now we apply [29, Thm. 13.23] to obtain
1 (ZKT, $) < 21 AKT in + | T6
| w.p. at least Cie
(170)
for some universal positive constants C1, C2. Plugging the above bound into (164) and collecting terms, we have with probability at least
eie
2
I. [l ll: < -41/AkTT + 442 1| - (nnna)
44

---

Solving for || Il using the quadratic formula, have with probability least cic ogo7
| lle Sa+ vb,
where
t and
_ 7 (2 A AKT +MIS + Li Lo Frana) b
m022
Using the fact that (a + vb)² = 2a + 2b, we have with probability at least c1e
1z02;
[l - f < 42f + 10e A KT l + 2.3 + 2.3 Ln (KT.)) - Lu (Frona))
- 42t 10t
| l + 1 + 2.3 In [xI(KTT))))) La (FrnL
(155)
cg ca (1 l 1)² c4 T.n (KT,,))) - -ao----aaaaa Trn(Frul..)
for some positive constants C3 Ca, where step (i) follows from that fact that = 25 by (155).
F.2 Proof of Lem. 13: RKHS norm of Jran,
Given the optimality of F on the objective (3), we have the following basic inequality
Ln(frun.x) + FralL Rh S + 1 57 + All
1l l - 1 + - 5? Ln (RunL))
Since Ilfruu. 1 2 O, we also have the trivial lower bound
Ln (Prn.)))
(163)
FL f+ 2 (Z
E)
- 4
2 (Z E EE= 5?.
Thus,
[ S 11 + (2 E))
(171)
and it remains to bound 2 (Zi E)-
Case First, suppose that ABuull 1. Then we may apply [29, Lem. 13.23] to obtain
(Zfult, {) < 22, Armn Il + 2: Aranlla lll 1. Aman l
w.p. at least
1- cie 12n
"ca
Combining this bound with (171), we have with probability at least cie ogo??
Al < ||
+
2:
x
2 ((26m)) Armll |l, 1/ Atan
(1)
2cL Flau + ||x) + 2 2E Araull + To Amull?
(155)
L + Ilfrau llk + || + 225 Araul + + A
where step (i) follows from triangle inequality. Solving for |r lix using the quadratic formula, we have
P 2 2+ ||
|1 llx + 2 (22e,)) A A ll + To Amn
On the event Ei (161), we have |ا S llls*|lken for some positive constant e, which implies the claimed bound (166) after some algebra.
45

---

Case I[()): Otherwise, assume || I/ S 1 and |uuuul S En-
Applying [29, Thm. 2.26] the
function sup | 1/2 2im1 Eig(s;),, we have
Sc,
1 5Z fulls E) - ca
ne. Boy
w.p. least
Combining this bound with (171), we obtain
a S 11
(155)
1
2
which immediately implies the claimed bound (166).
Case II(b): Finally, assume || | kk I and Aaullnn > En. Applying [29, Lem. 13.12] with
Ens have
8. fu E) & 2s
- e 20 w.p. at least
Combining this bound with (171), we obtain
M S | + (155)
|| + +
which immediately implies the claimed bound (166).
F.3 Proof of Lem. 14: KT-COMPRESS++ approximation bound using kRR
By Grünewälder [12, Lem. 4], f1.f2 lies in the RKHS H(KRR), which is a direct sum of RKHS: H(KRR) = H(ki) @ H(k2),
where k1, k2 2 > IR are the kernels defined by
kj (((21,81), (I2, 82)) k2 (21, and k2((21, vi), (22, 82)) k(x1, x2) V182.
Applying Lem. with
[|kl be +Ymax)
x V, KALG knn, and e*
Pout
yields the following bound event εKT,8 (24):
H (IP Qoa /h| S 2c* [Kan loo 2knn (n, nouts 6, Rins C*).
Mout
l S1
We claim that
[knk S |k||ooc.nn oc.in + V-2 max and
(172)
log (Sin, S c. log. log.N((Sin.. |k|///2 +Ymax
(173)
for some positive constant where Nrt KAR is the cardinality of the cover of B
kar
{ Il f E P((kk) for E defined by (167). Proof of the claims (172) and (173) are deferred to the end of this section. By definition of 2kkg. we have
M (n, Douts 5, Rin. c*)
Vc- 20x (n, Nout, 5, Rin.
|| Mone
+ymax
A 210
On event EKT,s. we have
( Quma) < 2([k 1/22 Ymmx)) )
|| Rollo in 42
supke H(kaa)
+
-20
Dout
Pout
[ Ann 51
( [k]] oa.
+ 222
max
12y2
(174)
where step (i) follows from the fact that [||]| 2/2 + Ymax) S 2(( looiin + +22 )
46

---

Since /1 non-zero, have [1 > O. Thus, the function h E IRRR H(knn) well-defined and satisfies ||
1. Applying (174), we obtain
[kll maax
Pinh- Qouth
+ 2
on event EKT,5.
Now
Multiplying both sides by | ll and noting that
[|Cs,all ||a f fifallzzo + l16 @ (,, DaIlERR
S 1 + 1/11/211
S (Ia) |1/1 | /21 + |6| 111211a)²
have event &KT,6;
Iell
Pinli..2 Qouk S (|a) 111 f22ll + |6| 111f22l1xx
max
(2 + 20,)
Thame
which directly implies the bound (162) after applying the shorthand (102).
Proof of (172) Define Ymax suPyE(Sm)) y. We have
= (L (k x2)² k(x1, 9132 + (8132)3
< (EE x2)) + sup suP k(11, sup y1 (2 1/1/2 ((,,),, (21
=||k||a + ||k bolii
Y2 max + Y4
s (Ikiloo,in + Y2
Proof of (173) Since H(KRR) is direct sum, we have
log. log.Vtt kaR (Sin, S log.Ni, (Sm, E" /2) log. Nt, (S e²)
(175)
where Not and Log,Nt, are the covering numbers of Bi & { : I E H(k) and Bi - {S @ (sw)a/1lS @ (.vlllka. I 8 (-1)2 E H(k2)), respectively.
Note that
log.1t ki (Sm, E*) & 2 2og No (S Se /2
[|k]] 1kll2// +Yuss 2n
< 2 log ( (1 +1+
Ymax
[k]l
[|k] 1/2 +Ymax
2 log (
2nont
Define kernel on R by KR(V1, 32)
A V1322 When suP lol S Ymax, we have
Nis (1- Ymaxs Em O( /e) for e> 0.
Similarly, note that
log ky (Sm,, c*) I log.NN Na e² <([k]| + ||k 1/2)) + No. co ((] 1/2 + +1|ka11
x (S
[k]] 1/2
Ymax
log
Aous
Aggut.
Substituting the above two log-coves coveriverng number expressions into (175) yields
||k| 1/2 +Ymux
ya [1|k
1/2 Vanx
log log (Sm, e*) S lig
+ log
Bontt
Phont
[k]| 1/2 +Ymax
c Log.NoN
neat
for some universal positive constant
47

---

G Non-compact kernels satisfying Assum. 2
The boundedness, Lipschitz assumption, square-integrability. and (15) follow from [10, App. O] and [10, Rmk. 8j. Thus, it only remains to verify (16) and (17) for each kernel.
G.1 Gaussian
For the kemne by k(r1, 22) A exp(- || || ), we have n(()) A exp(-u²//2 12). 2h2
Verifying (16). For any and X, we have
S [elle((2r-- 410, k(r, 2)d2 s 11112(22-1-- fih k(r, - 2)dz
(2Th2) 4/2 PP-Ni1o. ||| 2 (2) 4
(2Th2) d/2 Px 1P-~N1011 || 2 - -
-
d 2 - d. (2Th2) d/2 Px X|
(176)
By [15, Lem. 1], we have
Px-M((La |XI (I - d> 2v 26 see for any 12 0.
(177)
Define _ 2d and R & 2Vi. We can directly verify that R2 d 2 2v di + 2/. Thus, we may further upper bound (176) by
Fx Fx~N(0.1)) || - d (2'-1 1)2 - d S {Px-N(O.L)
X d 2v dt 2
(177) c R2 c- -21-2
whenever R 2 2v2d, or equivalently. j 2 log + 4v)d). Under this regime, we have
283 (1 k(x, z)dz - (2m11))d/2 (22 1 C
for some positive constant C' that does not depend on j or as desired.
Verifying (17).
Fixing j 2 1, we have
(2 1 1) s 20(++0) expl } -1)9)
s () 8) d)
s exp(max ( (log () B) +d)
Note that (log (j(d + B) + d) (23-1 1)2 is concave over > and maximized [log(1 + /1+ 2(3 d))J. Treating Jo² x(u)ud-2dd du constant, there exists 02 such that (17) is satisfied for all positive integers j.
G.2 Matérn
We consider the kernel k(rr,, .22 - c ||ا] -
K, ( with > d, where K, denotes the modified Bessel function of the third kind [30, Def. 5.10], and c - 21-b We have k(01, #2) = x( [|z] (مااق =alla
I(b
k of |||] (لا where
(u) cs Ko(u).
48

---

Verifying (16). Fix j E 10.1..... 7}. Applying Jensen's inequality, have
supzex ([ale((er-- k(2, 2)d2 S suprex (Ji=le((er- 200,,200+ k2 k2
2)dx)
3
- supsex (J1112(22 -14 k2 x - =)dzz)
= (2 2)),
where ne(-) the kernel tail decay defined by [10, Assum. 3]. We may use the same logic as [10,
App. 0.3.6] but ignoring the Avynd term and making the substitutions, a t- v 2 y + 1 and
T(v 1) t [22v - 1) to obtain
T(2u 1) exp( (R) S 1d 2n TT T()+))
2-22-
R) for R 2 d h.
/2
Hence, we have
218 supzex ( + 4)a x(x, 2)dz S 20 Ch,d,v expl (21-1 0(1),
2 for some constant Ch,d,v that does not whenever (20-1 41h 2 2 h j 2 + log( 2ndd depend on j.
v2
v2
Verifying (17). Following similar logic in [10, App. 0.3.1], we have
Ra(u)= S min(1,
xxp(-2)} for a 2 2(a 1).
Fixing 2 1, we have
(2' + x 1) - 20(++8)+ min 1, VTcc 4 (2/ 1)0 exp( e -
Note that when v/ d 1 < 1. the RHS can be rewritten as C3 12i-1 exp( 2 for some 2
constant Cs.dd that doesn't i depend on j. When v/ & - 2 1, the RHS can be upper-bounded by Ca (2 11) exp(exp( 1 2 for some constant C² that doesn't depend on j. Observe that the function e constant that does not depend on n as desired.
1/2 -t22 attains its maximum at 2b. Hence, the RHS can be bounded by
49

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Abstract and introduction give clear outlines on our contributions, and we present our contributions in the main text accordingly. We have also included pointers in the introduction that would link to the referred main text containing specific contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
In Sec. 6, we discuss limitations as well as future work to address these limitations.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
50

---

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have clarified the assumptions and models required for all the theorems and corollaries provided in the main text and appendix. Also we provide a complete proof in the appendix for all the stated results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced
statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We describe details of the experiments in Sec. and provide links to all code and data.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
51

---

some way (e-g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide link to our GitHub repository containing all code in Sec. 5,
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ca/ public/guides/ Stttess/CooSSuuisssionnne
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https: ttaiss.ccppbllee pppulicggguddss /CodeSumii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide train-test splits and hyperparameters in the main paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In all figures, we plot error bars representing standard deviation across 100 trials. In all tables, report mean +/- standard error across 100 trials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
52

---

The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
We indicate the computer resources for running all experiments in Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https / /t/.//nuurirrree http///ulcc//ccccciiiieeeeeeeeee
Answer: [Yes]
Justification:
We have reviewed the NeurlPS Code of Ethics and our paper conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work reduces the computational costs of classical methods and is applied standard datasets. Thus, it has outsize societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
53

---

If the authors NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release models or data as part of this paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We include URL and licenses for baseline code and datasets used in Sec. 5.2.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
54

---

If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release code with documentation at atttppss//ggttubb..cmm/a222233 npr under a BSD-3 Clause license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: We do not have any studies results regarding crowdsourcing experiments and human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do have any studies results including study participants.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
55

---

Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
56


Reviews:
[{"review_id": "ahZO0ZPHDn", "reviewer": "Reviewer_Vy1C", "summary": "After the rebuttal, I have updated my score from 3 to 5. \n\n----\nThis paper provides a meta-algorithm based on Kernel Thinning for non-parametric regression, in particular, the Nadaraya-Watson (NW) regression, and the Kernel Ridge Regression (KRR). \n\nThe idea is to run NW or KRR on a thinned coreset by KT. The core of the method is to choose a suitable kernel for which the KT assumptions are satisfied. The paper introduces to meta-kernels that takes a base kernel of features x and produces the kernel over (x,y) suitable for regression tasks. \n\nThe paper provides the theoretical guarantees for kernel thinned NW and kernel thinned KRR. \n\nIn empirical study, the paper includes simulation results and real data results which demonstrate the proposed method's strength over full computation and standard thnnning in accuracy and time; however, the SOTA RPCholesky method seems to have a better empirical performance than kernel thinned KRR.", "questions": "- There is not an algorithmic description for Kernel Thinning algorithm. \n\n- Eq 4 and 6: why do you choose the kernel in this way? In particular, can you comment on the part $k(x_1,x_2) y_1, y_2$. Does the performance of the kernel rely on the relationship of $y$ and $x$, and if so, how? Also, in eq 6, is this a typo $k^2(x_1,x_2)^2$? \n\n- Notation suggestion: instead of $S_{KT}$ for KT-NW, could use $S_{NW}$ to match the use of $K_RR$ in KT-KRR part. \n\n- Sec 4.1: are the kernels listed in 1.2.3 used as the base kernel to construct the kernel for thinning, or they are the kernel for thinning?\n\n- Fig 2: Right panel: why not include RPCholesky?\n\n- Fig 2: why si the full not performing the best?\n\n- Fig 3 and Fig 4: why not use the function in (11)? \n\n- Fig 3 and Fig 4: what is the unit of y axis? Are they all in the same unit?\n\n- Sec 4.2: what is the conclusion from Fig 5?\n\n- Sec 4.3: line 283-284: \"In this example (and ....)\" incomplete sentence. \n\n- It'd be good to include Fig 5 in the main text instead of appendix.", "limitations": "- KT-KRR does not demonstrate an empirical advantage over RPCholesky. Missing a discussion on this point. \n\n- Missing a discussion on potential failure cases of the method, though there is  a discussion on kernel mis-specification and potential way to deal with it.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper in general is easy to read\n\n- The idea to introduce kernel thinning to non-parametric regression methods is novel. \n\n- Provides theoretical guarantees of the method under suitable assumptions.", "weaknesses": "- The empirical advantage of the proposed kernel thinned KRR over RPCholesky is not clear. In fact, from figure 5, RPCholesky has slighly higher training time compared to kernel thinned KRR, however, a much lower test MSE. \n\n- Some technical background and discussion can be made more clear. See questions. \n\n- Writing can be improved. See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time you’ve spent reviewing our work and for your thoughtful feedback. We address each of your concerns below.\n\n$\\blacktriangleright$ $\\textbf{Comparison with RPCholesky}$\n- _\"The empirical advantage...\"_\n- _\"KT-KRR does not demonstrate...\"_\n\nThank you for raising these points. The main focus of this work was to build a stepping stone towards bridging two literatures: distribution compression and non-parametric regression, by designing algorithms and developing theory. Tuning to optimize empirical performance, e.g., by combining the pre-conditioning step of RPCholesky with KT, is a great future direction.\n\nAs another sanity check, we have added an experiment on the SUSY dataset ($d=18, N=5\\times 10^6$) from Diaz et al. (2023). KT-KRR's (22%) performance lies between RPCholesky (20%) and ST-KRR (22.7%). Thinning 4 million points with our method took only 1.7 seconds on a single CPU core, with further speed-ups to be gained from parallelizing on a GPU. \n\n- _\"Fig 2: Right panel: why not include RPCholesky?\"_\n\nIn Fig. 2b of the attached PDF, we have added Restricted KRR with RPCholesky for landmark selection. In Fig. 2a of the attached PDF, we have added RPCholesky-NW, where $S_{NW}$ are the pivot points from RPCholesky.\n\n$\\newline$\n\n$\\blacktriangleright$ $\\textbf{Choice of kernel}$\n- _\"Eq 4 and 6: why do you choose the kernel in this way?...\"_\n- _\"Sec 4.1: ... the kernels listed in 1.2.3 used... are the kernel for thinning?\"_\n\nThis is a great question central to the novelty of our work while bridging the two literatures. Directly applying generic kernels would not work in theory and our experiments confirm that. Overall the choice we make are informed by the following points:\n- Roughly speaking, KT with input kernel $\\mathbf{k}_{ALG}$ provides a coreset that well approximates the averages of functions in its RKHS $\\mathcal H$. \n- Dwivedi & Mackey (2022), Thm. 4 showed that thinning with $\\mathbf{k} _{ALG} := \\mathbf{k} _1 + \\mathbf{k} _2$ produces a coreset that simultaneously well approximates averages for any $ f\\in \\mathcal{H}(\\mathbf{k} _1)$ or $f\\in \\mathcal{H}(\\mathbf{k} _2)$ (aka the \"aggregate kernel trick\"). \n- The NW estimator is a ratio of averages: an average of $f(x)=k(x, x_0)$ in the denominator and an average of $f _{num}(x,y)=\\langle y,1 \\rangle k(x,x_0)$ for the numerator. \n    - $f _{num}$ lies in the RKHS corresponding to the kernel $\\mathbf{k} _{num}((x_1,y_1),(x_2,y_2)) := \\mathbf{k}(x_1,x_2) y_1 y_2$, so thinning with this kernel provides good approximation of the numerator.\n   - Applying aggregate kernel trick to $\\mathbf{k} _1 = \\mathbf{k}$ and  $\\mathbf{k} _2= \\mathbf{k} _{num}$ yields the $\\mathbf{k} _{NW}$ from (4).\n\n- For KRR, we approximate the training loss, which is an average of $\\ell_f(x,y) = (f(x)-y)^2 = f^2(x) -2 f(x)y + y^2$. \n     - Assuming $f\\in \\mathcal{H}(\\mathbf{k})$, $\\ell_f$  lies in the RKHS of $\\mathbf{k}^2(x_1,x_2) + y_1 y_2 \\mathbf{k}(x_1,x_2) + y_1^2 y_2^2$, where the last term can be dropped (see Sec. 3 of _Compressed Empirical Measures_ by Grünewälder (2022)), yielding (11) (thanks for pointing out the typo).\n\n-  **Remarkably, our ablation studies in Fig. 2 of the original manuscript and Fig. 2 of the attached PDF confirm this theory.**\n   - Thinning with $\\mathbf{k} _{ALG}((x_1,y_1),(x_2,y_2)) = \\mathbf{k}(x_1,x_2)$ (orange; Ablation #2 in Sec. 4.1) performs poorly because it only exploits the $x$ information. \n    - Thinning with $\\mathbf{k} _{ALG}((x_1,y_1),(x_2,y_2)) = \\mathbf{k}(x_1\\oplus y_1,x_2\\oplus y_2)$ (i.e., ) (brown; Ablation #1 in Sec. 4.1)—despite incorporating information from both $x$ and $y$ by concatenating the two—also yields poor empirical performance. \n    - Thinning with $\\mathbf{k} _{ALG} = \\mathbf{k} _{NW}$ and $\\mathbf{k} _{ALG} = \\mathbf{k} _{RR}$ perform the best for the NW and KRR settings, respectively.\n\n$\\newline$\n\n$\\blacktriangleright$ $\\textbf{Improvements to notation and writing}$\n- _\"Notation ... instead of for KT-NW, could use...KT-KRR part.\"_\n\nWe will use $S_{NW}$ to denote the coreset for the thinned NW estimator and $S_{RR}$ to denote the coreset for the thinned KRR estimator. We will use $\\mathbf{k}$ exclusively to denote the base kernel and use $\\mathbf{k} _{ALG}$ to denote the kernel for thinning.\n\n- _\"There is not an algorithmic description for Kernel Thinning algorithm.\"_\n\nWe apologize for this oversight. We will add a paragraph in the revised paper and an algorithm with details in the appendix.\n\n- _\"Fig 3 and Fig 4: why not use the function in (11)?\"_\n- _\"Fig 3 and Fig 4: what is the unit of y axis?...\"_\n\nIn the attached PDF, we have reproduced Fig. 3 and 4 with (11) and improved the formatting. The y-axis is in seconds and we use log-scale to make the difference between ST, KT, and RPCholesky clearer.\n\n - _\"Sec 4.2: what is the conclusion from Fig 5?\"_\n\nWe will revise the discussion for Fig. 5 as follows: On the California Housing dataset, KT-KRR lies between ST-KRR and RPCholesky in terms of test MSE. In terms of train time, KT-KRR is quite a bit faster than RPCholesky (0.0153 s vs 0.3237 s).\n\n$\\newline$\n\n$\\blacktriangleright$ $\\textbf{Discussion on potential failure cases}$\n- _\"Missing a discussion on potential failure cases of the method...\"_\n\nWe will expand our discussion:\n- The supervised KT guarantees apply when t $f^\\star$ lies in the RKHS $\\mathcal{H}(\\mathbf{k})$, where $\\mathbf{k}$ is the base kernel. In practice, choosing $\\mathbf{k}$ is indeed a challenge _common to all prior work_.\n- Dwivedi & Mackey (2022), Cor. 1 provide integration-error guarantees for KT when $f^\\star \\notin \\mathcal{H}(\\mathbf{k}). Moreover,  there are recent results on finding the best kernel (in testing; Dominigo-Enrich et al. (2023), Sec. 4.2). \n- Combining these results, potentially with the recursive feature machines of Radhakrishnan et al. (2024) (also see our response to Rev PSUT) to build a practical strategy is an exciting future direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d6JD2aexBK", "reviewer": "Reviewer_PSUT", "summary": "The authors speed up two non-parametric regression estimators, Nadaraya-Watson (NW) and Kernel Ridge Regression (KRR), by using a kernel thinning (KT) technique to compress the input data in a way that preserves important statistical properties. They include a theoretical analysis proving that that KT-based regression estimators are computational more efficient and also exhibit improved statistical efficiency over i.i.d. subsampling of the training data. They also include empirical validation of their method on simulated and real-world data.", "questions": "I have no particular questions.", "limitations": "The comparison with other large-scale kernel methods is limited to RPCholesky; a more comprehensive comparison and overview would be nice.\n\nPerformance/utility of the proposed method on real-world data remains unclear. The results obtained on real-world dataset in section 4.2 are not convincing, and the authors acknowledge the problem of kernel mis-specification but do not elaborate or provide any resolution. Btw, there is an incomplete sentence in lines 283-284.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Good presentation with a solid analytical analysis providing theoretical guarantees. Overall well-organized paper.\nThe proposed method of combining KT with the estimators is novel (to my knowledge) and shows potential.", "weaknesses": "The empirical analysis is limited. The shortcomings on the real-world data are not adequately addressed (see also limitations).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time you’ve spent reviewing our work and for your thoughtful feedback. We now address each of your questions and concerns in turn.\n\n$\\blacktriangleright$ $\\textbf{Comparison with large-scale kernel methods}$\n- _\"The comparison with other large-scale kernel methods is limited to RPCholesky\"_\n\nThank you for this suggestion. We have added new results in the global response pdf.\n- It includes an experiment on the SUSY dataset ($d=18, N=5\\times 10^6$) from Diaz et al. (2023). We sample $4\\times 10^6$ points to use for training. (Full KRR is now infeasible as we can only store 3k-4k columns at a time, e.g., on a machine with 100 GB RAM).\n- We include the _RPCholesky preconditioning method_ from Diaz et al. (2023) and the _FALKON method_ from Rudi et al. (2017) as SOTA baselines. As a sanity check, we also include the _Conjugate Gradient method_ (without preconditioning).\n- In Fig. 2 of the attached PDF, we have added RPCholesky-NW (where $S_{NW}$ are the pivot points from RPCholesky) and Restricted KRR with RPCholesky for landmark selection (see box plots in red). While it outperforms the KT method in the KRR setting, **RPCholesky is less suitable for speeding up the NW estimator as shown in Fig. 2a of the attached PDF and is outperformed by KT-NW.**\n\n$\\newline$\n\n$\\blacktriangleright$ $\\textbf{Kernel mis-specificiation}$\n- _\"the authors acknowledge the problem of kernel mis-specification but do not elaborate or provide any resolution\"_\n\nWe will elaborate our discussion in the revision.\n- The supervised KT guarantees apply when $f^\\star$ lies in the RKHS $\\mathcal{H}(\\mathbf{k})$, where $\\mathbf{k}$ is the base kernel. \n- In practice, choosing a good kernel $\\mathbf{k}$ is indeed a challenge _common to all prior work_.\n- Our framework is friendly to recent developments in kernel selection to handle this problem:\n   - Dwivedi & Mackey (2022), Cor. 1 provide integration-error guarantees for KT when $f^\\star \\notin \\mathcal{H}(\\mathbf{k}).\n   - Moreover,  there are recent results on finding the best kernel (in testing; Dominigo-Enrich et al. (2023), Sec. 4.2). \n   - Radhakrishnan et al. (2024) introduce Recursive Feature Machines, which use a parameterized kernel $\\mathbf{k} _{M}(x_1,x_2) := \\exp(-\\frac{(x_1-x_2)^\\top M (x_1-x_2)}{2\\sigma^2})$, and propose an efficient method to learn the matrix parameter $M$ via the average gradient outer product estimator. An exciting future direction would be to combine these parameterized (or \"learned\") kernels with our proposed KT methods for non-parametric regression.\n- Formally combining these results, potentially with the recursive feature machines of Radhakrishnan et al. (2024) to build a practical strategy with theoretical guarantees is an exciting future direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uJ50iZM2EW", "reviewer": "Reviewer_QHUc", "summary": "This paper applies the kernel thinning approach to non-parametric regression, with two kinds of estimators (NW and KRR) considered. This approach speeds up the computational efficiency by using carefully chosen coresets for approximation. Theoretical results on the approximation error are established. Numerical experiments include synthetic data and the well-known California housing dataset.", "questions": "1. In the beginning of Sec 3, the NW and KRR estimators are restricted to kernels taking the form of (4) and (6). What are the specific reasons to make these restrictions? And to see how restrictive/general this is, could you give some examples of commonly used kernels that fall under this category?\n2. The theory makes the sub-Gaussian tail decay assumption on the kernel, which would exclude many commonly used kernels such as the Matern kernel. How would the theory work out, and how would the rates change if this assumption is generalized to sub-Weibull tail decay, or say a bound on the Orlicz-norm?\n3. The method (or at least the theory) is developed for one-dimensional response data. How could this be generalized to multi-dimensional response data, where issues with computational efficiency becomes more significant?\n4. In the discussion section, it is mentioned that the rates on the excess risk could be sub-optimal. Do you have a sense of what rate could be minimax optimal?", "limitations": "See weaknesses and questions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well organized and written, with enough background and clear motivation\n2. Solid theoretical results are developed for the proposed method\n3. Certain experimental results are given to justify the proposed method", "weaknesses": "1. Despite the well developed theory, I am not fully convinced yet by the significance/contribution of this method - I am willing to stand corrected if more comparisons can be made with other existing methods for efficient non-parametric regression. \n2. The application are only to toy examples or standard small datasets - e.g. for the Californian housing dataset with n = 20,640, doing non-parametric regression without thinning also seems fine.\n3. In the experiments, the baseline is chosen to be NW / KRR with naive thinning - some more competitive, state-of-the-art baselines could have been chosen.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time you’ve spent reviewing our work and for your thoughtful feedback. We now address each of your questions and concerns in turn.\n\n$\\blacktriangleright$ $\\textbf{Comparisons to existing methods for efficient non-parametric regression}$\n- _\"The application are only to toy examples or standard small datasets...\"_\n- _\"In the experiments, the baseline is chosen to be NW / KRR with naive thinning...\"_\n\nThank you for this suggestion. \n- We have added an experiment on the SUSY dataset ($d=18, N=5\\times 10^6$) from Diaz et al. (2023). We sample $4\\times 10^6$ points to use for training. (Full KRR is now infeasible as we can only store 3k-4k columns at a time, e.g., on a machine with 100 GB RAM).\n- We include the **RPCholesky preconditioning method** from Diaz et al. (2023) and the **FALKON method** from Rudi et al. (2017) as SOTA baselines. As a sanity check, we also include Conjugate Gradient method (without preconditioning).\n- In Fig. 2 of the attached PDF, we have added RPCholesky-NW (where $S_{NW}$ are the pivot points from RPCholesky) and Restricted KRR with RPCholesky for landmark selection (see box plots in red). **While it outperforms the KT method in the KRR setting, RPCholesky is less suitable for speeding up the NW estimator as shown in Fig. 2a of the attached PDF.**\n\n$\\newline$\n\n$\\blacktriangleright$ $\\textbf{Kernel assumptions}$\n- _\"In the beginning of Sec 3...\"_\n- _\"The theory makes the sub-Gaussian tail decay assumption on the kernel...\"_\n\nThank you for raising this question. \n- Our theory in fact permits a large class of base kernels. This strength is borrowed partially from the Kernel Thinning results of Dwivedi & Mackey (2021).\n- In our revision, we will use $\\mathbf{k}$ exclusively to denote the base kernel and use $\\mathbf{k} _{ALG}$ to denote the kernel for thinning. Given a valid base kernel $\\mathbf{k}$, we can construct $\\mathbf{k} _{NW}$ and $\\mathbf{k} _{RR}$ following (4) and (6), respectively.\n- For NW, we only showed the results when the kernel is compactly supported or admits sub-Gaussian tails (for ease of presentation); **remarkably, the same results hold when the kernel has sub-exponential tails or poly-tails as well.** In fact, $\\mathbf{k}$ can be any radial kernel $\\mathbf{k}(x_1,x_2) := \\kappa(\\lVert x_1-x_2\\rVert_2/h)$ such that $\\kappa(u)$ is a bounded, L-Lipschitz function and decays (at any rate). This includes kernels with sub-Weibull tail decay. The kernel density estimation guarantees from Dwivedi & Mackey (2021), which we use in our analysis, indeed use an Orlicz bound.\n- For KRR, $\\mathbf{k}$ can be any kernel such that the log-covering number satisfies the PolyGrowth (e.g., finitely-times differentiable kernels) or LogGrowth (e.g., analytic kernels, finite-rank kernels) property (see Assump. 4). For KRR, our results do degrade with increasingly less smooth kernels.\n\n$\\newline$\n\n$\\blacktriangleright$ $\\textbf{Multi-dimensional response data}$\n- _\"The method (or at least the theory) is developed for one-dimensional response data...\"_\n\nThe reviewer’s comment on multi-dimensional response data has direct and interesting applications for speeding up multivariate response regression problems. \n\n- Roughly speaking, KT with input kernel $\\mathbf{k}_{ALG}$ provides a coreset that well approximates the averages of functions in its RKHS $\\mathcal H$. \n- Dwivedi & Mackey (2022), Thm. 4 showed that thinning with $\\mathbf{k} _{ALG} := \\mathbf{k} _1 + \\mathbf{k} _2$ produces a coreset that simultaneously well approximates averages for any $ f\\in \\mathcal{H}(\\mathbf{k} _1)$ or $f\\in \\mathcal{H}(\\mathbf{k} _2)$ (aka the \"aggregate kernel trick\"). \n    - We use the aggregate kernel trick to tackle multi-variate regression via one-dimensional kernel thinning on an aggregated kernel.\n- To be precise, let $f  = (f _1, …, f _m)$ be multi-dimensional response function, and for all $j = 1, …, m$, $f _j : R^d \\to R$ are coordinate functions in some RKHS $\\mathcal{H}( \\mathbf{k} _j)$ generated by some base kernel $\\mathbf{k}(j)$. \n- Now define the aggregated kernel $\\mathbf{k} _{ALG}((x_1,y_1),(x_2,y_2)) := \\sum _{i=1}^{m} w _j \\mathbf{k}(j) ((x _1,y _{1,j}),(x _2,y _{2,j}))$ (for NW and use $\\mathbf{k} _{RR}(j)$ instead of $\\mathbf{k} _{NW}(j)$ for KRR), where weights $w _j$ reflect prior beliefs. \n- Then $\\mathbf{k} _{ALG}$-kernel thinned core-sets are shared across all coordinate functions, that also balances information across all coordinates. \n- Notably, aggregate kernel tricks have been used in Generalized Kernel Thinning by Dwivedi & Mackey (2022) for improving integration error guarantees and Compress-then-Test by Domingo-Enrich et al. (2023) for increasing power of kernel-based hypothesis tests. Here we use it for speeding multi-variate non-parameteric regression.\n\n$\\newline$\n\n$\\blacktriangleright$ $\\textbf{Minimax optimal rates}$\n- _\"In the discussion section, it is mentioned that the rates on the excess risk could be sub-optimal...\"_\n\nWe will include the expanded discussion in the revision:\n- The following is classically known (see Tsybakov (2009)): \n  - When $f^\\star$ belongs to a Hölder class with smoothness $\\beta > 0$, the minimax optimal rate is $\\mathcal{O}(n^{-\\frac{2\\beta }{2\\beta + d}} )$.\n  - When $f^\\star$ belongs to a Sobolev space with smoothness $\\nu=1/\\alpha$ (for $\\alpha\\in (0,2)$), the minimax optimal rate is $\\mathcal{O}(n^{-\\frac{2}{2+\\alpha}})$.\n- As shown by Dwivedi & Mackey (2021), KT produces a coreset that achieve the minimax rates (as if all $n$ points were used) for a large class of kernel density estimation tasks—e.g., employing any radial kernel $\\mathbf{k}(x_1,x_2) = \\kappa( \\lVert x_1-x_2\\rVert _2 / h)$ with bounded, L-Lipschitz $\\kappa: \\mathbb{R} \\to \\mathbb{R}$. However, our current proof techniques do not yield a minimax rate for supervised learning task. We believe a modified proof technique should yield the same rate as obtained by $n$ points for some class of kernels.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their helpful and detailed feedback on our work. We summarize our additions as follows:

$\blacktriangleright$ $\textbf{New experiment on SUSY dataset}$
- In Table 1 of the attached PDF, we have added results on the SUSY dataset ($d=18,N=5\times 10^6$). We use $4\times 10^6$ points for training and the remaining $10^6$ points for testing.
- We compare our method KT-KRR ($\sigma=10,\lambda=10^{-1}$) to several large-scale kernel methods, namely RPCholesky preconditioning, FALKON, and Conjugate Gradient (all with $\sigma=10,\lambda=10^{-3}$). The parameters are chosen with cross-validation.
- We show that KT-KRR achieves test MSE between ST-KRR and RPCholesky with training time almost half that of RPCholesky. These findings are consistent with our results on the California Housing dataset (Fig. 5 in the original manuscript).

$\newline$

$\blacktriangleright$ $\textbf{Addtitional comparisons with RPCholesky}$
- In Fig. 2a of the attached PDF, we have added a new baseline: RPCholesky-NW, where $S_{NW}$ are the pivot points from RPCholesky (see box plots in red).
  - **KT-NW outperforms RPCholesky-NW in terms of both test MSE and train times.** While it provides a good low-rank approximation of the kernel matrix, RPCholesky is not designed to preserve averages. Moreover, RPCholesky requires $\mathcal{O}(n^2)$ time to produce a coreset of size $\sqrt{n}$, whereas KT-NW requires $\mathcal{O}(n \log^3 n)$ time. This difference is reflected in our wall-clock timings (see Fig. 3a of the attached PDF).
- In Fig. 2b of the attached PDF, we have added a new baseline: Restricted KRR using RPCholesky for landmark selection (see box plots in red). 
  - Consistent with our real-world experiments, RPCholesky-KRR outperforms KT-KRR in terms of test MSE (Fig. 2b of the attached PDF), but with slower train times (Fig. 3b of the attached PDF).

$\newline$

$\blacktriangleright$ $\textbf{Insight into the choice of kernels}$

We expand the discussion of the following points:
- **Choice of base kernels $\mathbf{k}$**:
  - Our theory for KT-NW permits any bounded, Lipschitz radial kernel with tails that decay at any rate—e.g., compact, sub-Gaussian, sub-exponential, and poly tails. 
  - Our theory for KT-KRR permits any kernel satisfying PolyGrowth or LogGrowth log-covering number—e.g., finitely-times differentiable, analytic, finite-rank kernels.
- **Construction of supervised kernels**: We explain the form of $\mathbf{k} _{NW}$ and  $\mathbf{k} _{RR}$ and validate these design choices with our ablation studies (see Fig. 2 of attached PDF and Fig. 2 of original manuscript).
- **Kernel mis-specification**: We describe several potential approaches for finding the right kernel and for deriving guarantees when the regression function $f^\star$ lies outside the RKHS $\mathcal{H}(\mathbf{k})$.
- **Multi-dimensional response data**: Our theory in fact applies effortlessly to the setting when $f^\star$ is multi-dimensional (e.g., for multi-class classification tasks). The resulting supervised kernel looks like the sum of one-dimensional supervised kernels (or equivalently, replacing $y_1 y_2$ with $\langle \mathbf{y} _1,\mathbf{y} _2\rangle$ in $\mathbf{k} _{NW}$ and $\mathbf{k} _{RR}$ ).
- **Minimax rates**: We discuss the minimax rates for each regression problem and although our rates our sub-optimal, we believe we this is a limitation in the analysis and that minimax rates can be achieved for some class of kernels.

$\newline$

We now respond to the specific comments and questions from each review.

Meta-review: This paper introduces a meta-algorithm based on Kernel Thinning for non-parametric regression. The authors apply their meta-algorithm to Nadaraya-Watson regression and Kernel Ridge Regression and prove computational speedups and statistical efficiency in both cases. Overall the paper could benefit from more experimental evidence. In the original set of results there was not much empirical advantage over RPCholesky. Moreover the paper was missing comparisons to other nonparametric regression methods, there were no experiments on large datasets, and the results were limited to kernels with fast decaying tails (excluding Matern kernels). The authors have clarified all of these points in the rebuttal, including new experimental results and a claim (without proof) that their results extend to heavy tailed kernels. I believe that this paper should be accepted for publication despite these omissions. Nevertheless, I urge the authors to include all new results in the camera-ready, as well as a detailed proof for non sub-Gaussian kernels.
Decision: Accept (poster)