Generalized Kernel Thinning
Authors: Raaz Dwivedi
Lester Mackey
Venue: ICLR 2022 Poster (2022)
Keywords: coresets
maximum mean discrepancy
Markov chain Monte Carlo
reproducing kernel Hilbert space
thinning
compression

Abstract: The kernel thinning (KT) algorithm of Dwivedi and Mackey (2021) compresses a probability distribution more effectively than independent sampling by targeting a reproducing kernel Hilbert space (RKHS) and leveraging a less smooth square-root kernel. Here we provide four improvements.  First, we show that KT applied directly to the target RKHS yields tighter, dimension-free guarantees for any kernel, any distribution, and any fixed function in the RKHS. Second, we show that, for analytic kernels like Gaussian, inverse multiquadric, and sinc, target KT admits maximum mean discrepancy (MMD) guarantees comparable to or better than those of square-root KT without making explicit use of a square-root kernel.  Third, we prove that KT with a fractional power kernel yields better-than-Monte-Carlo MMD guarantees for non-smooth kernels, like Laplace and Matern, that do not have square-roots. Fourth, we establish that KT applied to a sum of the target and power kernels (a procedure we call KT+) simultaneously inherits the improved MMD guarantees of power KT and the tighter individual function guarantees of target KT.  In our experiments with target KT and KT+, we witness significant improvements in integration error even in 100 dimensions and when compressing challenging differential equation posteriors.

Published as a conference paper at ICLR 2022
GENERALIZED KERNEL THINNING
Raaz Dwivedi', Lester Mackey²
Department of Computer Science, Harvard University and Department of EECS, MIT
2 Microsoft Research New England
taaz@mit edu, imackey@microsoffr com
ABSTRACT
The kernel thinning (KT) algorithm of Dwivedi and Mackey (2021) compresses a probability distribution more effectively than independent sampling by targeting a reproducing kernel Hilbert space (RKHS) and leveraging a less smooth square- root kernel. Here provide four improvements. First, we show that KT ap- plied directly to the target RKHS yields tighter, dimension-fret guarantees for any kemnl,, any distribution, and any fixed function in the RKHS. Second, we show that, for analytic kernels like Gaussian, inverse multiquadric, and sinc, tar- get KT admits maximum mean discrepancy (MMD) guarantees comparable to better than those of square-root KT without making explicit use of square-root kernel. Third. we prove that KT with a fractional power kernel yields better-than- Monte-Carlo MMD guarantees for non-smooth kernels, like Laplace and Matérn, that do not have square-roots. Fourth, we establish that KT applied to a sum of the target and power kernels (a procedure we call KT+) simultaneously inherits the improved MMD guarantees power KT and the tighter individual function guarantees of target KT. In our experiments with target KT and KT+, we witness sigmificant improvements in integration error even in 100 dimensions and when compressing challenging differential equation posteriors.
INTRODUCTION
A core task in probabilistic inference is learning compact representation of probability dis- tribution P.. This problem is usually solved by sampling points 21....,Iy independently from or, if direct sampling intractable, generating n points from Markov chain converging to P. The benefit of these approaches is that they provide asymptotically exact sample estimates Pinf A Σi= (x;) ) for intractable expectations Pf A Ex)r However, they also suffer from serious drawback: the learned representations are unnecessarily large, requiring n points to achieve - = Onn 2) integration error. These inefficient representations quickly become prohibitive for expensive downstream tasks and function evaluations: for example, in computational cardiology, each function evaluation fx;; initiates a heart or tissue simulation that consumes 1000s of CPU hours (Niederer et al., 2011; Augustin et al., 2016; Strocchi al., 2020).
To reduce the downstream computational burden, a standard practice is to thin the initial sample by discarding every t-th sample point (Owen, 2017). Unfortunately, standard thinning often results in a substantial loss of accuracy: for example, thinning an i.i.d. or fast-mixing Markov chain sample from n points to n points increases integration error from (n $) to (n
The recent kernel thinning (KT) algorithm of Dwivedi & Mackey (2021) addresses this issue by producing thinned coresets with belter-than-i..dd. integration error in a reproducing kernel Hilbert space (RKHS, Berlinet Thomas- Aggan, 201 1). Given a target kernel' k and a suitable sequence of input points Sn. = (z+) approximating P, KT returns subsequence Sout of /nz points with better-than-i.i.d. maximum mean discrepancy (MMD, Gretton et al., 2012),
MMDx PPan)) supjss| P. Pl for Pont ta Exes 6m,
A kernel k any function that yields positive semi-definite matrices (k(2,, 2, 2,))),==1 for all inputs (2))==1 2MDD is metric for characteristic k, like those in Tab. and controls integration error for all bounded continuous ff when k determines convergence, like each k in Tab. except SINC. (Simon-Gabric al., 2020).

---

Published as a conference paper at ICLR 2022
where ||-I denotes the norm for the RKHS H. associated with k. That is, the KT output admits o(n=4) worst-case integration error across the unit ball of H.
KT achieves its improvement with high probability using non-uniform randomness and a less smooth square-root kernel k,r satisfying
k(r, v) = Iae ka(a, 2)k,(2, y)dz.
(2)
When the input points are sampled i.i.d. or from a fast-mixing Markov chain on I2, Dwivedi & Mackey prove that the KT output has, with high probability, Oa(n nl-gn error for P and Ka with bounded support, Oa(n (log light tails, and Oa(n 3 t Meanwhile, an i.i.d. coreset of the same size suffers 2(nn 4) MMDk. We refer to the original KT algorithm as ROOT KT hereafter.
d+1 noog log J-M error for IP and kn with Vlog n log log n) - error for P and kå with p > 2d moments.
Our contributions In this work, we offer four improvements over the original KT algorithm. First, we show in Sec. 2.1 that generalization of KT that uses only the target kernel k provides a tighter On Vlog ni integration error guarantee for each function KT guarantee (a) applies to any kernel k on any domain (even kernels that do not admit square- root and kernels defined on non- -on-Euclidean spaces), (b) applics to any target distribution (even heavy-tailed F' not covered by ROOT KT guarantees), and (c) is dimension-free, climinating the exponential dimension dependence and (log n)// factors of prior ROOT KT guarantees.
the RKHS. This TARGET
Second, we prove in Sec. 2.2 that, for analytic kernels, like Gaussian, inverse multiquadric (IM)), and sinc, TARGET KT admits MMD guarantees comparable to or better than those of Dwivedi & Mackey (2021) without making explicit use of a square-root kernel. Third, we establish in Sec. that generalized KT with fractional a-power kernel kg yields improved MMD guarantees for kernels that do not admit a square-root, like Laplace and non-smooth Matérn. Fourth, we show in Sec. that, remarkably, applying generalized KT thinning+ (KT+) simultaneously inherits the improved MMD of POWER KT and the dimension- free individual function guarantees of TARGET KT.
of k and k,- procedure call kernel
In Sec. 4, we use our new tools to generate substantially compressed representations of both i.i.d. samples in dimensions d 2 through 100 and Markov chain Monte Carlo samples targeting chal- lenging differential equation posteriors. In line with our theory, we find that TARGET KT and KT+ significantly improve both single function integration error and MMD, even for kernels without fast-decaying square-roots.
GAUSS(O) >>
LAPLACE(O)
MATÉRN(P,7) $.7 >
IMQ(47) 0,7 7
SINC( 0 #
B B-SPLINE(23+117) BE
exp
1 2
Hella
C (1ll=1)a)) K Ky- ((1(11111)12)
0+1-1//77
sin(es.) Bxy
d 2
2p IT ha(72))
Table 1: Common kernels k(æ, y) on Rd with = x y- In each case, || 1. Here, Ca _ 2
[(a) Ka
is the modified Bessel function of the third kind order (Wendland, 2004, Def. 5.10), hg is the
18/21 recursive convolution of 233 + copies of 1, $ f)r and 23 TH Σ 2,= (f))(() =
Related work For bounded k, both i.i.d. samples (Tolstikhin al., 2017, Prop. A.1) and thinned geometrically ergodic Markov chains (Dwivedi & Mackey, 2021, Prop. 1) deliver nà points with On- à) MMD with high probability. The online Haar strategy of Dwivedi et al. (2019) and low dis- crepancy quasi-Monte Carlo methods (see, e.g., Hickernell, 1998; Novak & Wozniakowski, 2010; Dick et al., 2013) provide improved Oz(n log" n) MMD guarantees but are tailored specifically to the uniform distribution on [0, 1]d. Alternative coreset constructions for more general IP include kernel herding (Chen et al., 2010), discrepancy herding (Harvey & Samadi, 2014), super-sampling with a reservoir (Paige et al., 2016), support points comeex-coccaee procedures (Mak & Joseph, 2018), greedy sign selection (Kamin & Liberty, 2019, Sec. 3.1), Stein point MCMC (Chen et al., 2019), and Stein thinning (Riabiz et al., 2020a). While some admit teater-than-i.i.d. MMD guar- antees for dimensiimellinnl kernels Rdd (Chen et al., 2010; Harvey & Samadi, 2014), none
2

---

Published as a conference paper at ICLR 2022
apart from KT are known to provide better-than-ii.d. MMD or integration error for the infinite- dimensional kernels covered in this work. The lower bounds of Phillips & Tai (2020, Thm. 3.1) and Tolstikhin et al. (2017, Thm. 1) respectively establish that any procedure outputring - core- sets and any procedure estimating IP based only on n i.i.d. sample points must incur ((x= MMD in the worst case. Our guarantees in Sec. match these lower bounds up logarithmic factors.
Notation We define the norm |k| xo suPa.y s.y |k(x; y)1 and the shorthand [m] _ (1.....,n... R4
{or E RR: : x 2 0}. No A NU (0). B& _ (ʃ E H || I }}, and B2(r) _ {v E TRd I|vll2 sr We write a 2 and a Σ b to mean a O()) and a = (2(6), use 3a when masking constants Op(b) to mean a/b is bounded in probability. For any distribu-
d, and write tion Q and point sequences S' S' with empirical distributions Qn. Q. we define MMDx(Q. S) & MMD (Q, Qn) and MMD S') e MMD (Qn,, (y).
dependent
GENERALIZED KERNEL THINNING
Our generalized kernel thinning algorithm (Alg. 1) for compressing input point sequence Sin (r+) proceeds in two steps: KT-SPLIT and KT-SWAP detailed in App. A. First, given a thinning parameter and an auxiliary kernel Ksplits KT-SPLIT divides the input sequence into 2nd candidate coresets of size n/2" using non-uniform randomness. Next, given a target kernel k, KT-SWAP selects a candidate coreset with smallest MMDj to S, and iteratively improves that coreset by exchanging coreset points for input points whenever the swap leads to reduced MMDk- When kyph square-root kernel Kn (2) of k, generalized KT recovers the original ROOT KT algorithm of Dwivedi & Mackey. In this section, we establish performance guarantees for more general kuplit with special emphasis on the practical choice Kypli KT has time complexity dominated by O(n²) evaluations of Ksplit and k and O min(d, n)) space complexity from storing either Snn or the kernel matrices (kspii (z, 24) )) and (k Zyy j-
Like ROOT KT, for any m, generalized
Algorithm 1: Generalized Kernel Thinning Return coreset of size [m with small MMDj ) thinning parameter m E N, split kernel kyplas target kernel k, point sequence Sm probabilities (6.) (6))lm/2)
Input:
[n/2]
(m 2 +- KT-SPLIT (kspli, Si,, m. (6.))=/²))
// Split Sm into 2 candidate coresets of size L
SKT
<- KT-SWAP (k, S... (S(m..)))²)) )2=1)
// Select best coreset and iteratively refine
return coreset SKT size [
2.1 SINGLE FUNCTION GUARANTEES FOR KT-SPLIT
We begin by analyzing the quality of the KT-SPIIT coresets. Our first main result, proved in App. B, bounds the KT-SPI.TT integration error for any fixed function in the RKHS H.pli generated by Kapli-
Theorem (Single function guarantees for KT-SPLIT) Consider KT-SPLIT (Alg. Ia) with oblivi- /2 and 8* & min, 8,. If 2m EN, then, for any fixed f E Hopiio index E [2"h, and scalar 8' E (0, 1), the output coreset S(m,E) with split A
ous' Sin and (8
m/2m Evesim.ey 8n satisfies
PPin
(p(() 1 S [I
om 2m//2oog 22)g(( for om A
v3 2 V /ikppiillooon log( 2m
with probability at least Pag A 11-8
EnT 5, Here, [|Ksphi A maxxes, Kypti (I. E 2 2j=1
Remark (Guarantees for known and oblivious stopping times) By Dwivedi & Mackey (2021, App. D), the success probability psg is at least 8 if we set 8' and 8, - 2 for stopping time n known a priori or ò, = 2 1=41) log" (141 for an arbitrary oblivious stopping time n.
mb
When compressing heavily from n to v points, Thm. and Rem. guarantee O(n Vlog n) inte- gration error with high probability for any fixed function f E Haplit- This represents near-quadratic
Throughout, oblivious indicates that sequence is generated independently of any randomness in KT.
3

---

Published as a conference paper at ICLR 2022
improvement over the Q2(n = integration error of v i..d. points. Moreover, this guarantee ap- plies to any kernel defined on any space including unbounded kernels on unbounded domains (e.g., energy distance (Sejdinovic et al., 2013) and Stein kemels (Oates et al., 2017: Chwialkowski al., 2016; Liu et al., 2016; Gorham & Mackey, 2017)); kernels with slowly decaying square roots (e.g., sinc kernels); and non-smooth kernels without square roots (e.g.. Laplace, Matérn with y E ( d)), and the compactly supported kernels of Wendland (2004) with guarantees of Dwivedi Mackey covered only bounded, smooth k on IR with bounded, Lipschitz, and rapidly-decaying square-roots. In addition, for ||k|| 1 Id the MMD bounds of Dwivedi & Mackey feature exponential dimension dependence of the form ed (log n)d/² while the Thm. guarantee is dimension- and hence practically relevant even when is large relative to n.
(d++1) 1)). In contrast, the MMD
Thm. 1 also guarantees better-than-i.i.d. integration error for any target distribution with [TP Finff o(n ). In contrast, the MMD improvements of Dwivedi & Mackey (2021, cf. Tab. 2) applied only to P with at least 2d moments. Finally, when KT-SPLIT is applied with a square- root kernel kplit kg. Thm. still yields integration error bounds for J E H. as H C Haplit However, relative target KT-SPLIT guarantees with Kspli- k, the error bounds are inflated by
multiplicatiiee factor of / - I1/lka
>ill I[fi* In App. H. we show that this inflation factor is at least 1 for each kernel explicitly analyzed in Dwivedi & Mackey (2021) and grows exponentially in dimension for Gaussian and Matérn kernels, unlike the dimension free target KT-SPLIT bounds.
Finally, if we run KT-SPLIT with the perturbed kernel Kipin defined in Cor. 1, then we simultancously obtain On Vlog n) integration error for f E Haplits near-i.idd Onn VVoo n)) integration error for arbitrary bounded f outside of Haplit and intermediate, better- than-i.i.d. o(n #) integration error for smoother I outside of Haplin (by interpolation). We prove this guarantee in App. C.
Corollary (Guarantees for functions outside of Hsplit Consider extending each input point I; with the standard basis vector e, E R." and running KT-SPLIT (Alg. Ia) on Sin = (I.,, e4) with ksn((r.))) + (w, v) for w, U, R" Under the notation and assumptions [
Kaptn ((z, w), (y, v))
of Thm. 1, for any fixed index E E [2 scalar 8' E 10, and f defined on Sin. we have, with probability least Psg.
[PPnn - 1p(2
-1((()
S min( Alloo.in (/akppirlloal1110
2 V8log( (
log(2"0
8m 2
(3)
2.2 MMD GUARANTEE FOR TARGET KT
Our second main result bounds the MMD (h)-the worst-case integration error across the unit ball of H for generalized KT applied to the target kernel, i.c., Kyplit k. The proof of this result in App. D is based on Thm. 1 and an appropriate covering number for the unit ball B& of the RKHS.
Definition 1 (k covering number) For set A and scalar e >> O, we define the k covering number (A,e) with M&(A,)) +) & log,N((A,s) as the minimum cardinality of a set C C B& satisfying
By S UnEclo E B& supseA [h(z)= g(x)) Se}.
(4)
Theorem 2 (MMD guarantee for TARGET KT) Consider generalized KT (Alg. 1) with K.pli k, oblivious Sin and (6,) [n/21, and 8* A min, 84. If SKT is of size 2 and satisfies
n EN, then for any 8' E (0, 1), the output coreset 2m
inf MMD SKT) eE(0,1), S.CA
2 2"
6m V / |||k||/c,in log(
(log(3) + Mk]A, (5) 2m
with probability at least Pag, where ||k|loo,in and peg were defined in Thm. 1.
When compressing heavily from n to vn points, Thm. 2 and Rem. with
kll and
A = (2 for Rm, e maxxess, 12 guarantee
MMDx SKT) 38 oo logn (R
k oo.n
(6)
4

---

Published as a conference paper at ICLR 2022
with high probability. Thus immediately obtain an MMD guarantee for any kernel k with a covering number bound. Furthermore, we readily obtain a comparable guarantee for since MMDx SKT) S MMDx (p, M (S SKr). Any of variety of existing algorithms can be used to generate an input point sequence Sin with MMDx (IP, Sm) no larger than the compression bound (6), including i.i.d. sampling (Tolstikhin al., 2017, Thm. A. geometric MCMC (Dwivedi & Mackey, 2021, Prop. 1), kernel herding (Lacoste-Julien et al., 2015, Thm. G.I), Stein points (Chen al., 2018, Thm. 2), Stein point MCMC (Chen et al., 2019, Thm. 1), greedy sign selection (Karnin & Liberty, 2019, Sec. 3.1), and Stein thinning (Riabiz et al., 2020a, Thm. 1).
2.3 CONSEQUENCES OF THM. 2
Tab. 2 summarizes the MMD guarantces Thm. under common growth conditions on the log covering number M& and the input point radius Rs, - max || In Props. 2 and of App. J, we show that analytic kernels, like Gaussian, inverse multiquadric (IMQ), and sinc, have LogGrowTH Mr (i..., Mx(B2(r),e) Za r" "log" (t)) while finitely differentiable kernels (like Matérn and B-spline) have POLYGROWTH Mr Mxc.,MM(B.l (B(((rr)e)) Za r²)
Our conditions on Rs, arise from four forms of target distribution tail decay: (1) COMPACT (Ms,, Za 1), (2) SUBGAUSS (Rs,, Za vlog ri). (3) SUBEXP (Rs,, Ze log n). and (4) HEAVYTAIL (Rs,, 3a n/) The first setting arises with a compactly supported TP (e.g., on the unit cube [0, 1)9), and the other three settings arise expectation and with high probability when Sin generated i..dd from I' with sub-Gaussian tails, sub-exponential tails, or moments respectively.
Substituting these conditions into (6) yields the eight entries of Tab. 2. We find that, for LOG- GROWTH MR. TARGET KT MMD is within log factors of the 12n=1/2) lower bounds of Sec. for light-tailed IP and is 1144) (i.e., better than i...d) for any distribution with p 4d moments.
Mcanwhile, for POLYGROWTH M&. TARGET KT MMD is o(n 0/4) whenever < for light- w) moments.
tailed whenever IP has 2d/( (
COMPACT IP
SUBGAUSS P Rm Za Vlog
SUBEXP Rin Za log
HEAVYTAIL Ai Za n 1/p
Ai 3a 1
LOGGROWTH Mr Mx(B2(r),e) Za r" (2)
(log m1
[log n) 22dtw41
Log n m 28/F
n
POLYGROWTH Mr (x(Ba(r),e) Sar"s""
log
(log ndd
(log m)24+1
log 24/p
Table 2: MMD guarantees for TARGET KT under Mr (4) growth and If tail decay. We report the MMD Skr) bound (6) for target KT with input points and /n output points, up to con- stants depending on d and ||]]lo..n. Here Ri & maxres, 11/||2-
Next, for each of the popular convergence-detemminng kernels of Tab. 1, we compare the ROOT KT MMD guarantees of Dwivedi & Mackey (2021) with the TARGET KT guarantees of Thm. combined with covering number bounds derived in Apps. J and K. We see in Tab. 3 that Thm. 2 provides better-than-i.i.d. and hetter-than-ROoT KT guarantees for kernels with slowly decaying or non-existent square-roots (e.g.. IMQ with 2. sinc, and B-spline) and nearly matches known
ROOT KT guarantees for analytic kernels like Gauss and IMQ with v 2 d. even though TARGET KT makes explicit use of square-root kernel. See App. K for the proofs related to Tab. 3.
3 KERNEL THINNING+
We next introduce and analyze two new generalized KT variants: (i) POWER KT which leverages power kernel k,, that interpolates between k and k₃ to improve upon the MMD guarantees of target KT even when K2 is not available and (ii) KTT which uses sum of k and k2 to retain both the improved MMD guarantee of k. and the superior single function guarantees of k.
Power kernel thinning First, we generalize the square-root kernel (2) definition for shift-invariant k using the order generalized Fourier transform (GFT, Wendland, 2004, Def. 8.9) of f Rd - R.
5

---

Published as a conference paper at ICLR 2022
Kernel k
TARGET KT
ROOT KT
KT+
GAUSS(O)
m 8641
(ogn)
(lox $ //n
Vn
V/i
LAPLACR(()
N/A
On (log (4
MATÉRN(P, (f.dd
n=4
N/A
MATÉRN(U, 1)
min("
(lg
Clos vo)
(log ms)
V
IMQ(1, 7):
(lo 144 V/
<lng 4---
Dog m3
+ Closs Voe
Blo m3
V
V+
SING(P)
[log m2
(log m)
B-SPLINE(28 + 1,7);
N/A
log 11
SPSLINNE(2 1,77:
Table 3:
MMDx(5, SKT) guarantees for commonly used kernels. For n input and /n output points, we report the MMD bounds of Thm. 2 for TARGET KT, of Dwivedi & Mackey (2021, Thm. 1) for ROOT KT, and of Thm. 4 for KT+ (with GAUSS kernel, COMPACT P for the B-SPLINNE kemel, and StnExp P for all other k (see Tah. for a definition of each P class). Here, Ca å log log 5; = -. = and error is reported up to constants depending on (k, 6, oz). The KT+ guarantee for LAPLACE applies with 241 MATÉRN with a>> d. TARGET KT guarantee MATÉRN with v 3d/2 assumes v-d/2 to simplify the presentation (see (53) for the general casc). The best rate is highlighted in blue.
wherever feasihle). We assume SUBBAUSS P for the
_d and for
Definition (a-power kernel) Define k1 A k. We say a kernel ky is t-power kernel for k if k(r, v) = (2m) 4/2 JR. k
3 (Ir, 2)kk (z, v)dz. For a (2, 1), kernel k, (x. v) K. (x (x-y) on Re an a-power kernel for k( y) = -x if =
By design, kj matches Kn (2) up to an immaterial constant rescaling. Given a power kernel k, we define POWER KT as generalized KT with kspli = ka. Our next result (with proof in App. E) provides an MMD guarantee for POWER KT.
Theorem (MMD guarantee for POWER KT) Consider generalized KT (Alg. 1) with Kypli ka for some a E [t, 1], oblivious sequences Sm and (0z) and 8* & min, 8,. If n EN, then for any 8' E (0, 1), the output coreset SKT is of size 2m and satisfies
MMDx(Sm. SKT) S [kallo))
M2.)))' 2 (2+
(1m)4/2 R ) T(+H))
(7)
with probability at least Pog (defined in Thm. 1). The parameters My and M are defined in App. and satisfy MR, Oal Oa(Vlogn) and Rmax = Oa(1) for compactly supported and k, and Mr = Oa(v/log log log n) and Rmax = -a(logn)) for subexponential IP and kao when 8* 6'
Thm. 3 reproduces the ROOT KT guarantee of Dwivedi & Mackey (2021, Thm. 1) when a = 1 and more generally accommodates any power kernel via MMD interpolation result (Prop. 1) that may be of independent interest. This generalization is especially valuable for less-smooth kernels like LAPLACE and MATÉRN(V, (v; with (g. df that have no square-root kernel. Our TARGET KT MMD guarantees are no better than i...d for these kernels, but, as shown in App. K, these kernels have MATÉRN kernels as a-power kernels, which yield o(n MMD in conjunction with Thm. 3.
Kernel thinning+ Our final KT variant, kernel thinning+, runs KT-SPLIT with scaled sum of Remarkably, this choice simultane- ously provides the improved MMD guarantees of Thm. 3 and the dimension-fre frree single function guarantees of Thm. 1 (see App. for the proof).
the target and power kernels, kf A k/ k/ll k /a//|/aall
WWhen S,n known in advance, alternatively choose k A k/llk/ooo.ia in Ka///kaalaa 2o.inn

---

Published as a conference paper at ICLR 2022
L...d.
Root KT (Gauss)
Target KT (Gauss)
KT+ (IMQ)
KT+ (Laplace)
KT+ (Bspline)
-00
5
0
-5
-10
-10
Gauss
IMQ
Laplace
Bspline k
2
2 MMD Pout)
2-2
--d 2:4
Root KT: n-
* lik -22
Sil n-22
lid n-124
2
Targut ST:
27
27
2 Coreset size
2
27
2
2
27
2 Coreset size vn
27
Coreset size vn
Coreset size vn
Figure Generalized kernel thinning (KT) i.dd. sampling an 8-component mixture Gaussians target P. For kernels without fast- fast-decaying square-roots, KT+ offers visible and quantifiable im- provements over i.i.d. sampling. For Gaussian k, TARGET KT closely mimics ROOT KT.
Theorem (Single function & MMD guarantees for KT+) Consider generalized KT (Alg. I) |n/2| 8* A min, 8, and a 2 E.N. For any fixed function
with Kaplit = kt, oblivious Sin and (6)):=1 f E H. index l E 1, and scalar 8' E E(0, 1), the KT-SPLIT coreset S(m,E) satisfies
Pin -p(1) P
S 2
16 log(
6m log( 3 )llfllk |k]loc 2
(8)
with probability at least Psg (for Psg and p(() spli defined Thm. 1). Moreover,
MMD SKT) S min [22. MtargetKT(k), 2 2 MMoowrkT (ka))
with probability at least Pag where MaargetKT(K, denotes the right hand side of (5) with ||k]|oo,in replaced by [|k]oo., and M MpoworkT(Ks, denotes the right hand side (7).
As shown in Tab. 3, KT+ provides better-than-i.i.d. MMD guarantees for every kernel in Tab. 1- even the Laplace, non-smooth Matérn, and odd B-spline kernels neglected by prior amlyysss-wii matching or improving upon the guarantees of TARGET KT and ROOT KT in each case.
4 EXPERIMENTS
Dwivedi & Mackey (2021) illustrated the MMD benefits of ROOT KT over i.i.d. sampling and stan- dard MCMC thinning with series of vignettes focused the Gaussian kernel. We revisit those vignettes with the broader range of kernels covered by generalized KT and demonstrate significant improvements in both MMD and single-function integration error. We focus on coresets of size yn produced from n inputs with 5; 2n
1 let P denote the empirical distribution of each output core- set, and report mean error (+1 standard error) over 10 independent replicates of each experiment.
Target distributions and kernel bandwidths 1 A
We consider three classes of target distributions on R4: (i) mixture of Gaussians IP = M7 Σ5= N(μu; I2) with M component means μą E IR² defined in App. (ii) Gaussian P A/(0, I,), and (iii) the posteriors of four distinct coupled ordinary
Σ

---

Published as a conference paper at ICLR 2022
differential equation models: the Goodwin (1965) model of oscillatory enzymatic control (d 4), the Lotka (1925) model of oscillatory predator-pre prey evolution (d = 4), the Hinch et al. (2004) model of calcium signalling in cardiac cells (d 38), and tempered Hinch posterior. For settings (i) and (ii), we an i.i.d. input sequence Snn from IP and kernel bandwidths = 1/7 v2d. For setting (iii), we use MCMC imput sequences Sin from 12 posterior inference experiments of Riabiz et al. (2020a) and the bandwidths 1/7 as specified by Dwivedi & Mackey (2021, Sec. K.2).
MMDxPP, Poath 2=
MMDx(D, Paul. d= 10
MMDDL.. Paul) d=
MMDo/P. Paa). 50
MMDDAP. Prac), 100
+ 6d
n-225 Root KT:
+6 Root KT:
Root KT:a
Bost KT: KT
Rost KT:
Yanget Kins oas
Ukrpet K3t 9.
Surpet a
Coccsot vi
Coresctsuee
Coresct sice Vit
Corcect sice
Coccaot sico
[(P Poaltt
Paulaa
IP PPP-Pa d-
K0- Paulkc),
[[P Paall)
2-4
g-tos
+
Surget KT: 2-55
Turget XT: a
Turget XT: g-14
Tarpet KT:
Surget ani
Coceent zion
Corsent 12z vi
Comeet 850
Cocoont clnn on
Px,)k d=
PsolkDr)) df
Psrlk1X1 d=
RP-
PsulkiX11 di
IPP
Paull(X)) d' 1000
2-
2-2
0d.
Dd 6a0 Target
+ 222
pd.
Target
Turget
Target
Target
2.a
[1P - PaaMaal d.
[RA, Paol d'
2-
10 - Paclful d' 20
10p - P d 50
[[p+ Paalfal
2-4
2-
Edl:
* ud a Target 2a2
tsl: 8-22
sdi a Surget KT
Swnget KT. ao0
Theppt 1.
Coessot
Corosct sizee
Corcact
Coreact sice
Figure MMD and single-function integration error for Gaussian k and standard Gaussian I in Rd Without using a square-root kernel, TARGET KT matches the MMD performance of ROOT KT and improves upon i.i.d. MMD and single-function integration error, even in d = 100 dimensions.
Function testbed To evaluate the ability of generalized KT to improve integration both inside and outside of H. we evaluate integration error for (a) a random element of the target kernel RKHS (f(x) = k(X', described in App. I), (b) moments (f(x) = and f(x) = =f)) and (c) a standard numerical integration benchmark test function from the continuous integrand family (CIF, Genz, 1984), fcr((r) = exp(- E
- uuy) for Uy drawn i.i.d. and uniformly from [0, 1].
Generalized KT coresets For an 8-component mixture of Gaussians target IP, the top row of Fig. highlights the visual differences between i..d. coresets and coresets generated using generalized KT. We consider ROOT KT with GAUSS k, TARGET KT with GAUSS k, and KT+ (a = 0.7) with LAPLACE k, KT+ (a })) with IMQ k (v = 0.5), and KT+(a 2) with B-SPLINE(5) k, and note that the B-SPLINE(S) and LAPLACE k do not admit square-root kernels. In each case, even for small n, generalized KT provides more even distribution of points across components with fewer within-component gaps and clumps. Moreover, as suggested by our theory, TARGET KT and ROOT KT coresets for GAUSS k have similar quality despite TARGET KT making no explicit use of square-root kernel. The MMD eтror plots in the bottom row of Fig. 1 provide similar conclusion quantitatively, where we observe that for both variants of KT, the MMD error decays as n 2, a significant improvement over the rate of i.i.d. sampling. We also observe that the empirical MMD decay rates are in close agreement with the rates guaranteed by theory in Tab. 3 0.36 for LAPLACE). We provide additional
(n 1/2 for GAUSS, B- BPSLIIEE, and IMQ and +. visualizations and results in Figs. 4 and 5 of App. I. including MMD errors for M = 4 and M component mixture targets. The conclusions remain consistent with those drawn from Fig. 1.
8

---

Published as a conference paper at ICLR 2022
TARGET KT vs. i..d. sampling For Gaussian IP and Gaussian k, Fig. 2 quantifies the improve- ments in distributional approximation obtained when using TARGET KT in place of a more typical iid. summary. Remarkably, TARGET KT significantly improves the rate of decay and order of magnitude of mean MM Pon), even in d = 100 dimensions with as few as 4 output points. Moreover, in line with our theory, TARGET KT MMD closely tracks that of ROOT KT without using kn. Finally. TARGET KT delivers improved single-function integration error, both of functions in the RKHS (like k(X,"" .)) and those outside (like the first moment and CIF benchmark function), even with large d and relatively small sample sizes.
KT+ vs. standard MCMC thinning For the MCMC targets, we measure error with respect to the input distribution Pi (consistent with our guarantees), as exact integration under each posterior intractable. We employ KT+ (a = 0.81) with LAPLAACE k for Goodwin and Lotka-Volterra and KT+ (a 0.5) with IMQ k (v 0.5) for Hinch. Notably, neither kernel has a square- root with fast-decaying tails. Fig. 3, we evaluate thinning results from one chain targeting each of the Goodwin, Lotka-Volterra and Hinch posteriors and observe that KT+ uniformly improves upon the MMD error standard thinning (ST), even when ST exhibits better-than-ii.d. accuracy. Furthermore, KT+ provides significantly smaller integration error for functions inside of the RKHS (like k )) and outside of the RKHŠ (like the first and second moments and the benchmark CIF function) in nearly every setting. See Fig. 6 of App. for plots of the other 9 MCMC settings.
MMDy (Pe. Pax))
(P Puelkil
RPa - Pool
KKPw kk
1eex Partfrr
Goodwin ADA RW Laplace
2
2.40
2.22
ST: n-222
2-14
ST: n
ST. -222 the sicn
ST.
5T: n-l.
MMD (Pa. Pax)
KPm Poulltl
KP - Poolx?]
KPp Paxil((X))
[0et Paatforl
Latka ADA RW Laplace
2
2-42
2-10
8T:
Ki+
2-44
* ST:
KT
ST. n KF+iz tin
2050
ST. axr
ST no KT+: tx
(M..(P...Pan)
KP Paelii
Rpp Parl
KPPm Parlk(07)
10%
Pautforl
2-
Hinch k
2.
XT+:
ST
KT+: a
ST
KT+:z
2-
KItin
ST KT+ n
2
27
2² Cornent sone NT
Coneat san VT
Carment sizw VIT
Coroenl sire v75
Corsant sioe VIT
Figure Kernel thimning+ (KT+) vs. standard MCMC thinning (ST), For kernels without fast-decaying square-roots, KT+ improves MMD and integration error decay rates in each posterior inference task.
5 DISCUSSION AND CONCLUSIONS
In this work, we introduced three new generalizations of the ROOT KT algorithm of Dwivedi & Mackey (2021) with broader applicability and strengthened guarantees for generating compact rep- resentations of probability distribution. TARGET KT-SPLIT provides /n--point summaries with O( n/n. integration еттоr guarantees for any kernel, any target distribution, and any func- tion in the RKHS; POWER KT yields improved better-than-i...d. MMD guarantees even when a square-root kernel is unavailable; and KTT simultaneously inherits the guarantees of TARGET KT and POWER KT. While we have focused on unweighted coreset quality we highlight that the same MMD guarantees extend to any improved reweighting of the coreset points. For example, for down- stream tasks that support weights, by directly minimizing MMDx- Finally, one can combine generalized KT with the COMPRESS++ meta-algorithm of Shetty et al. (2022) obtain coresets of comparable quality in near-linear time.
can optimally reweight our approximate P in ( time

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
See App. for supplementary experimental details and results and the goodpoints Python pack- age
h http:///gggttccccocc///////////p
for Python code reproducing all experiments.
ACKNOWLEDGMENTS
We thank I Lucas Janson and Boaz Barak for their valuable feedback on this work. RD acknowledges the support by the National Science Foundation under Grant No. of Data Science Institute (FODSI).
for the Foundations
REFERENCES
Christoph M Augustin, Aurel Neic, Manfred Liebmann, Anton Prassl, Steven Niederer, Gundolf Haase, and Gernot Plank, Anatomically accurate high resolution modeling of human whole heart electromechanies: A strongly scalable algebraic multigrid solver method for nonlinear deformation. Journal of computational physics, 305:622-660 646, 2016. (Cited on page 1.)
Necdet Batir. Bounds for the gamma function. Results in Mathematics, 72(1):865-874, 2017. doi: 10. 10.0077/000025--1--699---- URL htttpp://doi..rg/11.1000000 on page 26.)
0. (Cited
Alain Berlinet and Christine Thomas-Agnan Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011. (Cited on pages 1, 15, 17, 18, and 26.)
Wilson Ye Chen, Lester Mackey, Jackson Gorham, François- Xaviir Briol, and Chris J. Oates. Stein points. In Proceedings of the 35th International Conference Machine Learning, 2018. (Cited page 5.)
Wilson Ye Chen, Alessandro Barp, François-Xavice Briol, Jackson Gorham, Mark Girolami, Lester Mackey, and Chris Oates. Stein point Markov chain Monte Carlo. In International Conference on Machine Learning, pp. 1011-1022 PMLR, 2019. (Cited on pages 2 and 5.)
Yutian Chen, Max Welling, and Alex Smola. Super-samples from kernel herding, In Proceedings of the Twenty- Sixth Conference Uncertainty in Artificial Intelligence, UAI' 10, pp. 109-116, Arlington, Virginia, USA, 2010. AUAI Press. ISBN 9780974903965.. (Cited page 2.)
Kacper Chwialkowski, Heiko Strathmann, and Arthur Gretton. kernel test of gondness of fit. In International conference on machine learning, pp. 2606-2615. PMLR, 2016. (Cited on page 4.)
Josef Dick, Frances Y Kuo, and Ian H Sloan. High-dimensional integration: The quasi-Monte Carlo way. Acta Numerica, 22:1 12:133-2800 2013. (Cited on page 2.)
Raaz, Dwivedi and Lester Mackey, Kernel thinning. arXiv preprint arXiv:2105.0588 2021. (Cited on pages 1, 2, 4, 7, 8, 9, 14, 15, 16, 17, 20, 21, 28, 29, and 30.)
Raaz Dwivedi, Ohad Feldheim, Ori Gurel-Gurevich, and Aaditya Ramdas. The power of online thinning in reducing discrepancy. Probability Theory and Related Fields, 174(1):103-13) 2019. (Cited on page 2.)
Alan Genz. Testing multidimensional integration routines. Proc. of international conference on Tools, methods and languages for scientific and engineering computation, pp. 81-94, 1984, (Cited on page 8.)
Mark Girolami and Ben Calderhead. Riemann manifold Langevin and Hamiltonian Monte Carlo methods. Journal the Royal Statistical Society: Series B (Statistical Methodology). 73(2):123-214, 2011. (Cited on page 21.)
Brian C Goodwin. Oscillatory behavior enzymatic control process. Advances Enzyme Regulation, 3: 318-356, 1965. (Cited on pages and 21.)
Jackson Gorham and Lester Mackey. Measuring sample quality with kernels. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1292-1301. JMLR. org, 2017. (Cited on page 4.)
10

---

Published as a conference paper at ICLR 2022
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Berhhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723-77, 2012. (Cited on pages and 18.)
Heikki Haario, Eero Saksman, and Johanna Tamminen. Adaptive proposal distribution for random walk Metropolis algorithm. Computational Statistics, 14(3):375-395, 1999. (Cited on page 21.)
Nick Harvey and Samira Samadi. Near-optimal herding. In Conference on Learning Theory, pp. 1165-1182, 2014. (Cited page 2.)
Fred Hickemell. A generalized discrepancy and quadrature enror bound. Mathematiccs of computation, 67(2)1): 299 322, 1998. (Cited on page 2.)
Robert Hinch, J. Greenstein, AJ Tanskanen, I. Xu, and RL Winslow, A simplified local control model of calcium-induced calcium release in cardiac ventricular myocytes. Biophysical journal, 87(6):3723-3736, 2004. (Cited on pages 8 and 21.)
Zohar Karnin and Edo Liberty. Diserepancy, coresets, and sketches in machinc learning. In Conference Learning Theory, pp. 1975-1993, PMLR, 2019. (Cited on pages 2 and 5.)
Simon Lacoste-Julien, Fredrik Lindsten, and Francis Bach. Sequential kerel herding: Frank- Wolle optimiza- tion for particle filtering. In Artificial Intelligence and Statistics, pp. 544-552. PMLR, 2015. (Cited on page 5.)
Qiang Liu, Jason Lee, and Michael Jordan. A kemeliiedd Stein discrepancy for goodness-of-fit tests. In Proc. of 33rd ICML, volume 48 of ICML, pp. 276-284, 2016. (Cited page 4.)
Alfred James Lotka. Elements of physical biology. Williams Wilkins, 1925. (Cited on pages 8 and 21.)
Simon Mak and V Roshan Joseph. Support points. The Annals of Statistics, 46664))2562-253333 2018. (Cited on page 2.)
Whitney K. Newey and Daniel McFadden. Chapter 36: Large sample estimation and hypothesis testing. In Handbook of Econometrics, volume 4, pp. 2111-2245. Elsevier, 1994. doi: https://doi.or//10.000 $15733441 URL https:/ /www. www.eceiiieeer.................. hemm//ccennee/eeeeee $1573441205800054 (Cited on page 27.)
Steven A Niederer, Lawrence Mitchell, Nicolas Smith, and Gernot Plank. Simulating human cardiac electro- physiology on clinical time-scales. Frontiers in Physiology, 2:14, 2011. (Cited on page 1.)
E Novak and H Wozniakowski. Tractability of multivariate problems, volume ii: Standard information for functionals, european math. Soc. Publ. House, Zütiich, 3. 2010. (Cited page 2.)
Chris J Oates, Mark Girolami, and Nicolas Chopin. Control functionals for Monte Carlo integration. Journal of the Royal Statistical Society: Series (Statistical Methodology). 79(3):695-718, 2017. (Cited on page 4.)
Art B Owen. Statistically efficient thinning a Markov chain sampler. Journal of Computational and Graph- ical Statisties, 26(3):738 2017. (Cited on page 1.)
Brooks Paige, Dino Sejdinovic, and Frank Wood. Super-sampling with a reservoir. In Proceedings of the Seiony Conference Uncertainty in Artificial Intelligence, pp. 567-576 2016. (Cited on page 2.)
Jeff Phillips and Wai Ming Tai. Near-optimal coresets of kernel density estimates. Discrete Computational Geometry, 63(4):867 2020. (Cited on page 3.)
Marina Riabiz, Wilson Chen, Jon Cockayne, Pawel Swictach, Steven A Niederer, Lester Mackey, and Chris Oates. Optimal thinning of MCMC output. arXiv preprint arXiv:2005.03952, 2020a. (Cited on pages 2, 5, 8, and 21.)
Marina Riabiz, Wilson Ye Chen, Jon Cockayne, Pawel Swietach, Steven A. Niederer, Lester Mackey, and Chris Oates. Replication Data for: Optimal Thinning MCMC Output, 2020b. URL htttp:://o.. org/10. T ////////////////// MDKNWM. Accessed on Mar 23, 2021. (Cited on page 21.)
Gareth O Roberts and Richard L Tweedie, Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, 2(4):34 1996. (Cited on page 21.)
Alessandro Rudi, Ulysse Marteau-Ferey, and Francis Bach. Finding global minima via kemel approximations. arXiv preprint arXiv:20/2.11976 2020. (Cited pages 24 and 25.)
11

---

Published as a conference paper at ICLR 2022
Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu. Equivalence of distance-basee and rkhs-based statistics in hypothesis testing. The Annals of Statistics, pp. 2263 2291, 2013. (Cited on page 4.)
Abhishek Shetty, Raaz Dwivedi, and Lester Mackey, Distribution compression near- near-linear time. In Interna- tional Conference on Learning Representations, 2022. (Cited on page 9.)
Carl-Johann Simon Gabriel, Alessandro Barp, and Lester Mackey. Metrizing weak convergence with maximum mean discrepancies. arXiv preprint arXiv:2006. 09268, 2020. (Cited on page 1.)
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science Business Media, 2008. (Cited on pages 22, 25, and 27.)
Ingo Steinwart and Simon Fischer. A closer look covering number bounds Gaussian kernels. Journal of Complexity, 62:101513, 2021. (Cited on pages 25, 27, and 28.)
Marina Strocchi, Matthias Gsell. Christoph M Augustin, Orod Razeghi, Caroline Roney, Anton Prassl, Edward J Vigmond, Jonathan M Behar, Justin Gould, Christopher A Rinaldi, Martin Bishop, Gernot Plank, and Steven A Niederer. Simulating ventricular systolic motion in four-chamber heart model with spatially varying robin boundary conditions model the effect of the pericardium. Journal of Biomechanics, 101:109645, 2020. (Cited on page 1.)
Hong-Wo: Wei Sun and Ding Xuan Zhou. Reproducing kemel Hilbert spaces associated with analytic translation- invariant Mercer kernels. Journal Fourier Analysis and Applications, 14(1))89-101, 2008 (Cited on pages 22, 27, and 28.)
Ilya Tolstikhin, Bharath K Sriperumbudur, and Krikamol Muandet. Minimax estimation of kemel em- beddings. The Journal of Machine Learning Research, 18( (11))3000-3344 2017. (Cited on pages 2, 3, 5, and 29.)
Vito Volterra. Variazioni e fluttuazioni del numero d'individui specie animali conviventi. 1926. (Cited on page 21.)
Martin Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge Uni- versity Press, 2019. (Cited on pages 14, 26, and 28.)
Holger Wendland. Scattered data opproximation, volume Cambridge university press, 2004. (Cited on pages 2, 4, 5, 18, 19, and 27.)
Haizhang Zhang and Liang Zhao. On the inclusion relation of reproducing kernel hilbert spaces. Analysis and Applications, 11(02): 1350014,, 2013. (Cited on pages 18, 19, and 20.)
Ding-Xoe Xuan Zhou. Capacity of reproducing kernel spaces learning theory. IEEE Transactions on Information Theory, 4977))174311752 2003. (Cited on page 28.)
12

---

Published as a conference paper at ICLR 2022
APPENDIX
Details of KT-SPLIT and KT-SWAP
13
B Proof of Thm. 1: Single function guarantees for KT-SPLIT
14
Proof of Cor. I: Guarantees for functions outside of Heplit
14
Proof of Thm. 2: MMD guarantee for TARGET KT
16
E Proof of Thm. 3: MMD guarantee for POWER KT
16
F Proof of Thm. 4: Single function & MMD guarantees for KT+
17
Proof of Prop. An interpolation result for MMD
18
Sub-optimality of single function guarantees with root KT
19
1 Additional experimental results
20
J Upper bounds on RKHS covering numbers
22
Proof Tab. results
28
A DETAILS OF KT-SPLIT AND KT-SWAP
Algorithm la: KT-SPLIT Divide points into candidate coresets of size [n/2m]
Input: kernel keghn. point sequence S., (zx)i=1, thinning parameter m E N, probabilities
86.4) + 0 for S S m and < 8 2
// Empty coresets: $6i.9) has size 1 after round
J. for $j S m and E 2'-1
// Swapping parameters
for 1, .,, n/2]
(0011) append((:)); ((0.1) S(0.1) append(ra.)
Every 2 rounds, add one point from parent coreset s(--1.0) to each child coreset , S(1.2)) and i/2011 E N; j j=j+j do
for (j =
for l,..., 2 do (8) (8U-1.0) S0 11); (I, get last two points(S)
// Compute swapping threshold
d/s]/2 2 for b²= kP=kspnna: (2, x) kepli (ū. 2) 2k (11, F)
a, ogH wett.swaapparamsse.
// Assign one point each child after probabilistic swapping
+ (xp - (pplar, æ) Eyes (kypii (v. (p *)) 25 (2,)))( (spli(,, B))
(x, - (ā, x)) with probability min(1, (1 4)+)
16,22-11), append(x); S(1.00) appped(()
end end end
return (8tm.0))" candidate coresets of size [n/2m
function get_swap.params (a, 6,
f max(BooV2lo((220)
a +- o+b 2a)o /
return (a.
13

---

Published as a conference paper at ICLR 2022
Algorithm 1b: KT-SWAP - Identify and refine the best candidate coreset
Input: kemel k, point sequence S. = (s:)i candidate coresets (5(m..)) yE=1
Tē=1
((m,.0) basel i www.tniiiinnnggggnennennee s seze [n/2""]) // Compare to baseline (e.g., standard thinning)
SKT g(m,)) for f" argmillle (0, MMD4(Sinn ((m..) Select best candidate coreset
// Swap out each point in SKr for best alternative in Sin
for ..... [m/2 do
[ < ess,in,es, (M,, SKI with Skr[i] = z)
end
return SKT, refined coreset of size [n/2m
B PROOF OF THM. SINGLE FUNCTION GUARANTEES FOR KT-SPLIT
The proof is identical for each index so, without loss of generality, prove the result for the case f = 1. Define
Wm - Wi.m = in kptii P(.)
Kyplic
Exes, (spli n/2 Evestmat) Kspli (x,, -).
Next, we use the results about an intermediate algorithm, kernel halving (Dwivedi & Mackey, 2021, Alg. 3) that was introduced for the analysis of kernel thinning. Using the arguments from Dwivedi & Mackey (2021, Sec. 5.2), we conclude that KT-SPLIT with Kyllt and thinning parameter m, is equivalent to repeated kernel halving with kernel k.pli for m rounds (with no Failure in any rounds of kernel halving). On this event of equivalence, denoted by Eequi- Dwivedi & Mackey (2021, Eqns. (50, 51)) imply that the function Wm Hypli is equal distribution to another random function W.,, where Wm is unconditionally sub-aausiia with parameter
2 V3
2
kksti 2o log( Gm
m
2"88
that is,
Elexp((W k()) exp( exp(Fomnll for all f Haplits
(10)
where we note that the analysis of Dwivedi Mackey (2021) remains unaffected when we replace ||Kaptall ao by |kppti looiil in all the arguments. Applying the sub- Sab-Gaussin Hoeffding inequality (Wainwright, 2019, Prop. 2.5) along with (10), we obtain that
P[[(Wm, M'kuall > 4 < 2 exp( - //o 11 ( S 8 for 1. & aml emmll/llk, V log( )-
Call this event Egg. As noted above, conditional the event Eequis we also have
Wm Wi..
(Wis Jikey d Pin.f -p( f
where denotes equality in distribution. Furthermore, Dwivedi & Mackey (2021, Eqn. 48) implies that
2/-1 P(Esqui 2 1-1 -m
En 6;.
j=1 m
Putting the pieces together, we have
P[PP../ (()) /l & <1) (PEggeui n (2) 2 P(Eqqu) P((Eg) > 1- 11-E _
22-1
mn/2 m -iz1 85-
Pago
claimed. The proof is now complete.
C PROOF OF COR. 1: GUARANTEES FOR FUNCTIONS OUTSIDE OF HSPLI
Fix any index é [2m)], scalar 8' E (0, 1), and f defined on Sin and consider the associated vector
g E R" with 9: = f(;;) for each E [n]. We define two extended functions by appending the domain by R as follows: For any R define fı ((x, w)) f(x) and f2((x, w)) (g. w)
14

---

Published as a conference paper at ICLR 2022
(the Euclidean inner product). Then note that these functions replicate the values of on Sm= since fi ((2,, w)) = (az) for arbitrary w E R", and fx((x,,e,) = (g. ex) = 9i = f(z;). where e; denotes the i-th basis vector in R". Thus
write
Pmf 1P spli = fi IP(() sp IP in
(a(()
split
(11)
for the extended empirical distributions IP = 1 Ei òz,,, and pv(() spla
defined analogously. No-
tably, any function of the form f((x,, w)) (g. w) belongs to the RKHS of Kppin with
|lf Kan S ||ا12
(12)
by Berlinet & Thomas-Agnan (2011, Thm. 5).
By the repeated halving interpretation of kernel thinning (Dwivedi & Mackey, 2021, Sec. 5.2), on an event & of probability at least Psg 5' may write
/2 sph = ΣØ= (Wj, K.n. = ンド J2.3
where Wj denotes suitable random functions in the RKHS of Kgghir and each fe w)) (g()), w) for gاو) E Re" sparsification of with at most ""r non-zero entries that satisfy
(12) E[exp((W f2.)) 1 exp(#1112 I S exp( + (|(0) s exp( o 12 11 for Wo _ and
0f = =4=12a 11(21=11 2 split boc. log( (x)) S 2 . log 278
since by definition IK Kknil bo.in S 2. Hence, by sub-Gaussian additivity (see, e.g., Dwivedi & Mackey, 2021, Lem. 8), Pmnf2 Pp is 32 sub-Gaussian with
23 S 1| ΣØ 2 log 278-
( 1 2((2m - 1) log( 3
((2m 1)(m 1) + m)
= = 2((2 1) log( 2
m log 2)
S 8
2
Il loog( 2m
n
i..,
02 IIIlloo.in log g
(13)
on the event E, where step (i) makes use of the following expressions:
E 2 2(2 1) and 12 2((m 1)(2 1) + m).
Moreover, when f Hyplit we additionally have fa in the RKHS of Kplii with
Ilfa llu... S Illl K goo
argued in the proof of (23). The proof of Thm. then implics that Py fi Gaussian with
p((() sp is ō sub-
ō1 S llfall
2 2 V IK /
oo.in logi(
Gm g
<
2 II V Ksplit oo V log(
6m
(14)
V3
on the very same event E.
Recalling (11) and putting the pieces together with the definitions (13) and (14), we conclude that on the event ε, the random variable IPin - Tp(() S is ō sub-Gaussian for
(13)(14)
ã و min(,, )2)
min
| foo |If
kupk v (Kkktill
2
logí
8m 2
)
The advertised gigh-rrobabiltyy bound (3) now follows from the aub-Gaussianity on E exactly as in the proof of Thm. 1.
15

---

Published as a conference paper at ICLR 2022
D PROOF OF THM. 2: MMD GUARANTEE FOR TARGET KT
First, we note that by design, KT-SWAP ensures
(M SkT) I MMD (S,, (S. s(m.))
where 1(m,1) denotes the first coreset returned by KT-SPLIT. Thus it suffices to show that MMDx (S 1)m is bounded by the term stated on the right hand side of (5). Let IP()) A n/22 Enestm. 8 By design KT-SPLIT, supp(P(()) S supp(Pin). Recall the set A such that supp(Pin) S.A.
Proof of (5) Let C (A)) denote the cover of minimum cardinality satisfying (4). Fix any E BR. By the triangle inequality and the covering property (4) of C, we have
(P Ip(l)) )5| inf geC (Pin Pf 9) (Tim (())(()
< gnc [Pin g)و + | (ʃ 9) sup (Pin plul (g)
I gec 2 sup lf(x) - g(>)l + supgec (P'm )
s 20 + sup (Pin -Plld (g)
(15)
Applying Thm. 1, we have
(Pin - p )()
I 2n 11gllk
|k|loo.in log( /- log (+)
(16)
with probability at least 1-8' - Dド= that
20-1 n
1==
d Pag 8'. A standard union bound then yields
supgec (Pin Pull (g)
S 2 supgec ||allx
| log( (t) [log [C] + log( [
probability at least Pag - 8. Since f E 1k was arbitrary, and C BR and thus suppee l|9|| 1, we therefore have
MMD S(m.1)) = suppsl|as1 (Pin 1 (Pm-
(15) I 2$ + sup (Pin (P(1) (g)
8
kll Vlog( zt log |C| + log( +
S 25
3
n
with probability at least Psg - 8' as claimed.
E PROOF OF THM. 3: MMD GUARANTEE FOR POWER KT
Definition of M. and Rmax Define the ka tail radii,
R Kg min(r: Th, (r) [ }, where Th. (R) 2 (sup, Jivll, k2 -ydd)) (17)
n Ri. n A min :sup 21 ka w)| lkk. 1 )
and the Snn tail radii
Rs, A max ||0||2 and Asm. A min (Rsm n Hr + nă (t2lkk.llo (Tk (18) Furthermore, define the inflation factor
My. (n,m, d,6,8' RR) A 37 log
Gm 2
log( (1) 5 /llog(2 + 2 Lx, (Bk... + +R))
where Ln., denotes Lipsehitz constant satisfying (x. v) ka 2)1 I Lk,, lIv - 2112 for all
x, y, Fdd With the notations in place, we can define the quantities appearing Thm.
(19) The scaling of these two parameters depends on the tail behavior of k. and the growth of the radii Rs, (which in tur would typically depend the tail behavior of PP. The scaling of M and R stated in Thm. 3 under the compactly supported or subexponential tail conditions follows directly from Dwivedi & Mackey (2021, Tab. 2, App. l).
M., My. (n,m, d.ō" ,8' R.RR.......)) and Raax - maxxRRs,,. ma! k/.m//"))
16

---

Published as a conference paper at ICLR 2022
Proof of Thm. 3 The KT-SWAP step ensures that
MMD SakT) MMD S.m..)). Sd
where s!m,1) denotes the first coreset output by KT-SPLIT with Kyplit = Ka. Next, we state a key interpolation result for MMDx that relates it to the MMD of its power kernels (Def. 2) (see App. G for the proof).
Proposition 1 (An interpolation result for MMD) Consider a shift-invariant kernel k that admits valid a and 2a-power kernels ka and k2a respectively for some a discrete measures P and Q supported on finitely many points, we have
E
[2: Then for any two
MMD (P, @) S (MMDK, (I,, 2 (MMD (P. ())=))=-1
(20)
Given Prop. 1, it remains to establish suitable upper bounds MMDs of k, and k2a- To this end, first we note that for any reproducing kernel k and any two distributions IP and Q, Hölder's inequality implies that
MMD (I,, Q) = [[ Q)k = (P - QP - Q)k < ||P - I S 21 k
Now, let Pin and P(m.1) denote the empirical distributions of Sin and (,,,1), Now applying Dwivedi & Mackey (2021, Thm. 4(b)), we find that
MMD (S s/mm.1)) v 21 - (kam.l))alllo.i V2 2nh a
| in
(21)
with probability Psg - 8', where Mk., was defined in (19). We note that while Dwivedi & Mackey (2021, Thm. 4(b)) uses | in their bounds, we can replace it by ||kalloo,in and verifying that all the steps of the proof continue be valid (noting that ||k llo,,i is deterministic given Sn)) Furthermore, Dwivedi & Mackey (2021, Thm. 4(b)) yields that
MMD kzn. (S S.m.shmr.l 1) < 2" ka loo..in (++
(4m) r(
R
(22)
with probability Psg 0', where we have once again replaced the term ||ka bloo with ka loo for the same reasons as stated above. We note that the two bounds (21) and (22) apply under the same high probability event as noted in Dwivedi & Mackey (2021, proof of Thm. 1, eqn. (18)). Putting together the pieces, we find that
MMD (S S! s(m..))
(MMDk. (S.m St 56m.1))2-3
(MMD (Sim s(m.))))
(21,22)
S
2 2d
Ma
11-2 20
2 ka
loc,io
2+
(4x (4x)u/2
R
Ma
T(
11
2 ka loo.in)
2 (2. (2.20a
)1 d0
2++
(4x) ((++1)
R
Ma
as claimed. The proof is now complete.
F PROOF OF THM. 4: SINGLE FUNCTION & MMD GUARANTEES FOR KT+
Proof of (8) First, we note that the RKHS H. of k is contained in the RKHS Hi of ki Berlinet & Thomas-Agnan (2011, Thm. 5). Now, applying Thm. 1 with k.pli = kf for any fixed function f E H c Ht and 8' E (0, 1). we obtain that
Pin/ ʃ - p(()
spin /
< ||/
2 2
k so log(
6m gma
2 log
v3
||fllk
2
Gm 16 log(
log( 3),
2m
(1
2
16 [k]
6m log 2
n
17

---

Published as a conference paper at ICLR 2022
with probability at least Pag- Here step (i) follows from the inequality ||k*]| 2, and step (ii) follows from the inequality lI S //kk||aal (ifllalllflee ll, which in turn follows from the standard facts that
(tv)
Il
Lfll
and
If Ilflkkkk.
S Ilfllx for 0=0,E EH,
(23)
see, e.g., Zhang & Zhao (2013, Proof of Prop. 2.5) for proof of step (iii). Berlinet & Thomas- Agnan (2011, Thm. 5) for step (iv). The proof for the bound (8) is now complete.
Proof of (9) Repeating the proof of Thm. 2 with the bound (16) replaced by (8) yields that
(S SKT+)
S infe S. 2
16
log( |
6m 2
[log(
+
Mx,,
S V22 MargetKT (k)
(24)
with probability at least Psg. Let us denote this event by Ei.
To establish the other bound, first we note that KT-SWAP step ensures that
MMDx SKT.) I MMDx skm-1) )
(25)
where SKT+ denotes the first coreset output by KT-SPLIT with k-pli = kt. We can now repeat the proof of Thm. 3, using the sub-Gaussiae tail bound (8), and with minor substitution, namely, | oo replaced by 2 k Putting it together with (25), we conclude that
-1
MMDx SKT.) S 2 2/ (29II,, )2 2a 2+
(4m) T(]t))
Raax Mi,
2 M (Ka)),
(26)
with probability at least Psg. Let us denote this event by Eg.
Note that the quantities the right hand side of the bounds (24) and (26) are deterministic given Sm. and thus can be computed apriori. Consequently, we apply the high probability bound only for one of the two events & & depending which of the quantities (deterministically) attains the minimum. Thus, the bound (9) holds with probability at least Pog as claimed.
G PROOF OF PROP. 1: AN INTERPOLATION RESULT FOR MMD
For two arbitrary distributions P and Q, and any reproducing kernel k, Gretton al. (2012, Lem. 4) yields that
MMD Q [[(P - Q)
(27)
Let F denote the generalized Fourier transform (GFT) operator (Wendland (2004, Def. 8.9)). Since k(x,0) v) = #(x - y), Wendland (2004, Thm. 10.21) yields that
(F((()))) Il (2m]arz JR. F(x)(() dw, for f H.
dw,
(28)
Let F(R), and consider a discrete measure DD = Σ w:O.r supported on finitely many points, and let Dk(x)= a Σ w;k(x, x:)) Σ won(x 2T:). Now using the linearity of the GFT operator F, we find that for any w E Rdd
F(D))((w) = F(E wor( -x:)) En F(n(.-r;) = =EE wse - R(w)
=D(w)R(w)
(29)
where we used the time-shifting property of GFT that F(R(-- - =x;))ww = e (w)))))( (proven for completeness in Lem. 1), and used the shorthand D(w) A (Ei wze wee- (w,e)) in the last step.
18

---

Published as a conference paper at ICLR 2022
Putting together (27) to (29) with D P Q we find that MMD (IP, Q) सिमम.र JR D2 (w))
(30)
(27) SRx D' (w))) (R (W)) La de
(27)//2 J D2 (u (wl yde' S2x
(w)
(R (w²) - dw
Ind
1
(2m)a72 Jau D2 )r (w) (wi)
Km (w)dw
Jad (A(W (w') ydu
2-2
متا
(27)a/2 Jgx D2 (W') (Wd))))
d
Canjara Szg D2 (w')R (w )dw)
2-
Sa
(w( (w)
(2x)az2
(MMD2, (P. 2))-- -MMD Kg.. (P. 2))
where step (i) makes use of Jensen's inequality and the fact that the function + t²= for t 2 0 is concave for a E } 1], and step (ii) follows by applying (30) for kernels ka and k2a and noting that by definition F(ka) = R and F(kza) = R220 Noting MMD is a non-negative quantity, and taking square-root establishes the claim (20).
Lemma (Shifting property of the generalized Fourier transform) I denotes the generalized Fourier transform (GFT) (Wendland, 2004, Def. 8.9) of the function x : Tedd -> R, then e e- denotes the GFT of the shifted fanction s(. I4), for any I2 E IR..
Proof Note that by definition of the GFT R (Wendland, 2004, Def. 8.9), we have
f [x(2)((z)dz
((w))(
(31)
for all suitable Schwartz functions 7 (Wendland, 2004, Def. 5.17), where 7 denotes the Fourier transform (Wendland, 2004, Def. 5.15) of y since GFT and FT coincide for these functions (as noted in the discussion after Wendland (2004, Def. 8.9)). Thus to prove the lemma, we need to verify that
fn(e (x) = ʃ f- (o (())))((()))))
(32)
for all suitable Schwartz functions y. Starting with the right hand side of the display (32), we have
fe (w- ( (w)) f (e (w))) (w)) (i) ((z)((z + x;)dr (8)) J n(Z 21)7(z)dz,
where step (i) follows from the shifting property of the FT (Wendland, 2004, Thm. 5.16(4)). and the fact that the GFT condition (31) holds for the shifted function 7(- + x;; function well since it still a Schwartz function (recall that & is the FT), and step (ii) follows from a change of variable. We have thus established (32), and the proof complete.
H SUB-OPTIMALITY OF SINGLE FUNCTION GUARANTEES WITH ROOT KT
Define k, as the scaled version of kn, i.c., Kn e kn/ (aallo that is bounded by 1. Then Zhang & Zhao (2013, Proof of Prop. 2.3) implies that
Illl,, = VIlkall |15
(33)
And thus we also have Hr = Hr, where Ha and Hn respectively denote the RKHSs of kn and knt- Next, we note that for any two kernels k; and k2 with corresponding RKHSs Hi and He with Hi C H2. in the convention of Zhang & Zhao (2013, Lem. 2.2, Prop. 2.3), we have
I lxa [ 1x
s 81H, H2) S /X(H,, H2) for fe H.
(34)
19

---

Published as a conference paper at ICLR 2022
Consequently, have
v maxxes kn( v)
fike < Vikall
ki (39) Ii
< v A(H, Hmn)
(35)
17
17lk
T
where in the last step, we have applied the bound (34) with (k1, Hi) t (k, H) and (k2, H2) -- (kre, knt) since H C Hn krt.
Next, (35) the kernels studied in Dwivedi & Mackey (2021) where we that all the kernels in that work were scaled to ensure ||k|loo = and in fact satisfied k(x, x)) = 1. Conse-
quently, the multiplicative factor stated in the discussion after Thm. I, namely, V be bounded by V ((H, H.t) given the arguments above.
[kll Mi can
[k]loo, lf
For k = Gauss(o) kernels, Zhang & Zhao (2013, Prop. 3.5(1)) yields that XHH, H.r) =2//2,
For k B-spline (23 + 1, with 2N
Zhang & Zhao (2013, Prop. 3.5(l)) yields that X(H. H.H) 1.
For k = -atéénn(y;)) with v > d, some algebra along with Zhang & Zhao (2013, Prop 3.1) yields that
H(H = (o) d/2/
2 1.
I ADDITIONAL EXPERIMENTAL RESULTS
This section provides additional experimental details and results deferred from Sec. 4.
Common settings and error computation To obtain an output coreset of size n with n input points, we (a) take every n² -th point for standard thinning (ST) and (b) run KT with m = log, n using an ST coreset as the base coreset in KT-SWAP. For Gaussian and MoG target we use i.i.d. points as input, and for MCMC targets we use an ST coreset after burn-in as the input (see App. I for more details). We compute errors with respect use Pin. For each input sample size E { 2
whenever available in closed form and otherwise } with dę 2n we report the mean MMD or function integration error #1 standard error across 10 independent replications of the experiment (the standard errors are too small to be visible in all experiments). We also plot the ordinary least squares fit (for log mean error vs log coreset size), with the slope of the fit denoted as the empirical decay rate, c.g., for OLS fit with slope -0.25, we display the decay rate of n -0.25
Details test functions We note the following: (a) For Gaussian targets, the error with CIF function and i..dd input is measured across the sample mean over the input points and vn output points obtained by standard thinning the input sequence, since IP fCIF does not admit a closed form. (b) To define the function f +> k(X', .), first draw sample X P, independent of the input, and then set X' = 2x. For the MCMC targets, we draw a point uniformly from a held out data point not used input for KT. For each target, the sample is drawn exactly once and then fixed throughout all sample sizes and repetions.
1.1 MIXTURE OF GAUSSIANS EXPERIMENTS
Our mixture of Gaussians target is given by PP 3 N Ia) for M (4,6,8)
where
A1 [-3,3] 3]
#2 [- #3 [-3, -3 = 13. -3.-3]]
A4s 60,
A4s [ #17 [6,0]T, As 10,
Two independent replicates of Fig. 1 can be found in Fig. 4. Finally.we display mean MMD (+1 standard error across ten independent experiment replicates) as a function of coreset size Fig. for M = 4, 6 component MoG targets. The conclusions from Fig. 5 are identical to those from the bottom row Fig. 1: TARGET KT and ROOT KT provide similar MMD errors with GAUSS k, and all variants of KT provide a significant improvement over i..d. sampling both in terms of magnitude and decay rate with input size. Morever the observed decay rates for KT+ closely match the rates guaranteed by theory in Tab. 3.
20

---

Published as a conference paper at ICLR 2022
L.14.
Root KT (Gauss)
Target KT (Gauss)
KT+ (IMQ)
KT+ (Laplace)
KT+ (Bxpline)
5
0
-5
-10
1.1.d.
Root KT (Causs)
Target KT (Gauss)
KT+ (IMQ)
KI+ (Laplace)
KT+ (Bspline)
5
-10
5
0
-5
-10
-10
-10
100
Figure 4: Generalized kernel thinning (KT) and i...d coresets for various kernels k (in parentheses) and an 8-component mixture Gaussian target P with equidensity contours underlaid. These plots are independent replicates of Fig. 1. See Sec. 4 for more details.
1.2 MCMC EXPERIMENTS
Our set-up for MCMC experiments follows closely that of Dwivedi & Mackey (2021). For complete details on the targets and sampling algorithms we refer the reader to Riabiz et (2020a, Sec. 4).
Goodwin and Volter- experiments From Riabiz et al. (2020b), use the output of four distinct MCMC procedures targeting each two d 4-dimensional posterior distributions P: (1) posterior over the parameters of the Goodwin model of oscillatory enzymatic control (Goodwin, 1965) and (2) a posterior over the parameters of the Lotka- Volterra model of oscillatory predator- prey evolution (Lotka, 1925; Volterra, 1926). For each of these targets. Riabiz et al. (2020b) provide 2 x 10t sample points from the following four MCMC algorithms: Gaussian random walk (RW), adaptive Gaussian random walk (adaRW, Haario al., 1999), Metropolis-adjusted Langevin al- gorithm (MALA, Roberts & Tweedie, 1996), and pre-conditioned MALA (pMALA, Girolami & Calderhead, 2011).
Hinch experiments Riabiz et al. (2020b) also provide the output of two independent Gaussian random walk MCMC chains targeting each of two d 38-dimensional posterior distributions IP: (1) posterior over the parameters of the Hinch model of calcium signalling in cardiac cells (Hinch et al., 2004) and (2) tempered version of the same posterior, as defined by Riabiz et al. (2020a, App. $5.4).
Burn-in and standard thinning We discard the initial burn-in points each chain using the maximum burn-in period reported in Riabiz et al. (2020a, Tabs. S4 & S6, App. S5.4). Furthermore, we also normalize each Hinch chain by subtracting the post-burn-in sample mean and dividing each coordinate by its post-burn-in sample standard deviation. To obtain input sequence S,, of length
21

---

Published as a conference paper at ICLR 2022
M = Gauss
M= IMQ
M =4 Laplace
M = 4 Bspline k
2-1
MMD Pour)
2-3
+ Hoot KD
Lid 142
Rdi n-
Ud
Targett KT:
KTi:n n-
KTI: n-:
2 Coreset size Vn
2
2
2
2
2
2
2
27
Coreset size vnn
Coreset size vn
Coreset size vn
= 6 Gauss
M IMQ k
M Laplace k
M=
Bspline k
2-
2
(P, Poun)
2-
+
lid: n-
Root KT: a-154
1. KT+ n-
2d n-125
2-
Turget XT: 0-55
KT+: n-135
KT+ n-03
2 Coroset size VT
2
size vT
Coreent size V
Coresnt size VTT
Figure 5: Kernel thinning versus L.dd sampling, For mixture of Gaussians P with M E (4,6) com- ponents and the kernel choices of Sec. 4, the TARGET KT with GAUSS k provides comparable MMDx(IP, Powi) error to the ROOT KT, and both provide over the decay rate from i.i.d. sampling. For the other kernels, KT+ provides decay rate close to n for IMQ and B-SPLINE k, and n -u.35 for LAPLACE k, providing an excellent agreement with the MMD guarantees provided by theory. See Sec. 4 for further discussion.
decay rate improving significantly
n to be fed into a thinning algorithm, we downsample the remaining even indices of points using standard thinning (odd indices are held out). When applying standard thinning to any Markov chain output, we adopt the convention of keeping the final sample point.
The selected burn-in periods for the Goodwin task were 820,000 for RW; 824,000 for adaRW; 1,615,000 for MALA; and 1, 1,475,000 for pMALA. The respective numbers for the Lotka-Volterra task were 1,512,000 for RW; 1,797,000 for adaRW; 1,573,000 for MALA; and 1,251,000 for pMALA.
Additional remarks on Fig. 3 When a Markov chain is fast mixing (as in the Goodwin and Lotka-
Volterra examples), we expect standard thinning to have 2(n 22) error. However, when the chain is slow mixing, standard thinning can enjoy faster rate of decay due to certain degeneracy of the chain that leads it to lie close to a one-dimensional curve. In the Hinch figures, we observe these better-than-i...d. rates of decay for standard thinning, but, remarkably, KT+ still offers improvements in both MMD and integration error. Moreover, in this setting, every additional point discarded via improved compression translates into thousands of CPU hours saved in downstream moart-model simulations.
J UPPER BOUNDS ON RKHS COVERING NUMBERS
In this section, we state several results on covering bounds for RKHSes for both generic and specific kernels. We then use these bounds with Thm. 2 (or Tab. to establish MMD guarantces for the output of generalized kernel thinning as summarized in Tab. 3.
We first state covering number bounds for RKHS associated with generic kernels, that are either (a) analytic, or (b) finitely many times differentiable. These results follow essentially from Sun & Zhou (2008); Steinwart& & Christmann (2008), but we provide a proof in App. J.2 for completeness.
Proposition 2 (Covering numbers for analytic and differentiable kernels) The following results hold true.
22

---

Published as a conference paper at ICLR 2022
MMDD
Goodwen
ST:
ST:
* 5T.
ST.
5T.
Stica
KT ca
MMDy(PI, Pac)
Pagtral
BP Pag
Bi PaolKO
18% Popiford
Laphoce
MMDa(Ph. Parl
[1% Paalforl
K.
ST. gollaa KTi:: 411
2T.2-414 KT 2ris
ST. aole
Ki-in
Cornont
Coenest
Cornent don
Comeet
Conoet
MMDg/P.. Pash
[Ipe - Peattal
IP Paelof)
[1A - PaulkO
11 Pailfal
Laplsce
PTT+: g-
KT- nodio
Conoen 3000 VW
Loccadt 3t00
Cancall 2000 Vi Id Aool
Doveet acc
Canoot nox
MMDu/Ps. Plaa
BA.-RulkOOY
Laplace
2-m
RY
ST.
ST
+ st Kiis
KE
MMDJ(P...
Puclesl
BP
2+
(lmeb Tempered
s000
sito
MMDz/Ps.Padl
Pealtsl
Paclof)
Grodwnn Laplace
2-4
ST.
KI
Goessi
MMDD/ Park
[Ipa - Pualesl
lP Puclaf
IA - Poo
[IA Panllal
2-0
201
I.d Coensst dbs / B8 Px.
Cormon r0n
Gressie ris 20 Pegdtal
Commett d5n
MMD Pas)
IP% PaclkOON
Jlmch Tempoeood
ST yets
2.4
+ ST: getio
St KT p-417
* Stan Ki+
5t wean
XT+ p-3as
+ KT+
+ Ki- 1.40
Corcan: 2T
Gounst
Cannat CT
Figure Kernel thinning+ (KT+) vs. standard MCMC thinning (ST), For kernels without fast-dccaying square-roots, KT+ improves MMD and integration error decay rates in each posterior inference task.
23

---

Published as a conference paper at ICLR 2022
(a) Analytic kernels: Suppose that k(r, v) =([[ - -1l2) for RR - R real-analytic with convergence radius Ry. that is.
(0) S (2/RRR)) for all j JENo
(36)
for some constant CR. where ()) denotes the right-sided j-th derivative of K. Then for any set A C Ra and any (0, 5), have
Mx(A,e) S N2(A, /2)- (4log(1/e) +2 (0g((16 + +1)) where r A min
(37)
VRL 2d
RR + D2 - DA). and DA 2 maxayyEA 1 - ull2-
(38)
(b) Differentiable kernels:
Suppose that for X C Rd, the kernel k X x X + R is s-times continuously differentiable, i.e. all partial derivatives gr.nk: X x X - R exist and are continuous for all multi-indices (2(r) contained in X and any E > 0, we have
Ng with |a| S Then, for any closed Euclidean ball
(x( S Co.d. rd (1/E)a/s,
(39)
for constant Ca.d, that depends only s, and k.
Next, we state several explicit bounds on covering numbers for several popular kernels. See App. J.3 for the proof.
Proposition 3 (Covering numbers for specific kernels) The following statements hold true.
(a) When k- GAUSS(O), we have
(x(B)(r),)) S CGausa,d
Ing(4/s) log (og(4/))
d
log(1/e)
when S V2a' (3v2ra) otherwise,
(40)
where CGAUSS,d - (tett))-ds
/4.3699
for d =
S 30 all d d21
(41)
0.05 dd for 2 2
(b) When k = MATÉRN(U, 7), v 22 + 1, then for some constant CMATERN we have
(x((B((),e) CMATERN, pd (1/E)4/VV-))
(42)
(c) When IMQ(U, 7), we have
(x(B)(r),e) (1 (4log((()))/)) +2 2+ CIMQUAA) d-1 )d-1
(43)
where CIMQ.IY & 4log
(20
+1), and F & min 7
4/2 4r 4 227)
(44)
(d) When k = SINC(O), then for (0, we have
Mu(l-T,r)4,6 5) < d (1 # (4log(d/s) + + log 17)²,
(45)
where To A min
8 + 4r 2r).
(46)
(e) When k = B-SPLINE + 1,7), thenfor some universal constant CB-SPLINE: we have
M&([ 1 Ltd
21 ()d S d- max(7, 1) CR.SPLINE (d/e) 245.
(47)
J. AUXILIARY RESULTS ABOUT RKHS AND EUCLIDEAN COVERING NUMBERS
In this section, collect several results regarding the covering numbers of Euclidean and RKHS spaces that come in handy for our proofs. These results can also be of independent interest.
We start by defining the notion of restricted kernel and its unit ball (Rudi et al. (2020, Prop. 8)). For X C. Rdd let Ix denotes the restriction operator. That is, for any function f : Rd + R, we have flx X IR such that (x)) = f(xx for X.
24

---

Published as a conference paper at ICLR 2022
Definition 3 (Restricted kernel and its RKHS) Consider a kernel k defined on IR corresponding RKHS H. any set X' C. RR. The restricted kernel kix is defined as
R with the
x X X R such that k(x(2,1) v) 2 (xx y) k(x,)) for all z,y X, and H denotes its RKHS. For E Hlx, the restricted RKHS norm is defined follows:
|| iinnnen ||h|] such that h|x f. Furthermore, we use Bkxx A U corresponding to this restricted kernel.
UEE E H|x ||]|lxx S 13 denote the unit ball of the RKHS
In this notation, the unit ball of unrestricted kernel satisfies Br - Brgg" Now, recall the RKHS covering number definition from Def. 1. In the sequel, we also use the covering number of the restricted kernel defined as follows:
(X, = (2,,,
(48)
that is Mi (M( denotes the minimum cardinality over all possible covers C BRGx that satisfy
xxx Unee :supee (h(x)-g(=)]sef}
With this notation in place, now state result that relates the covering numbers Art (48) and N Def. 1.
Lemma 2 (Relation between restricted and unrestricted RKHS covering numbers) We have
Nxx.c(x)= S (x)
Proof Rudi et al. (2020, Prop. 8(d,f)) imply that there exists a bounded linear extension operator E Hlx H with operator norm bounded by 1, which when combined with Steinwart & Christmann (2008, eqns. (A.38), (A.39)) yields the claim.
Next, we state results that relate RKHS covering numbers for a change of domain for a shift-invarian kernel. We use Bi| (x;r) A {v E Rdd || - vll S r) to denote the r radius ball in Rd defined by the metric induced by a norm I|
Definition 4 (Euclidean covering numbers) Given set X Idd, norm Il- and scalar >> O, we use (X,)((e,)) to denote the E-covering number of X with respect to |I-I| I-olm-morm. That is, (X, denotes the minimum cardinality over all possible covers C that satisfy
X UzecBBH1(2;))
When ||.|| = 11-1. some q E oo), we use the shorthand Ng 2 Ni
Lemma 3 (Relation between RKHS covering numbers on different domains) Given a shift- invariant kernel k, a norm ||:I| on TRdd and any set C RRd, we have
( (2.1)
(x),))
Proof Let C denote the cover of minimum cardinality such that
X C Usec (2,
We then have
(6) ()( &
1),s) < Issc MMB (H)))) & [NMCE] 1 ..
(is)
|4|
where step (i) follows by applying Steinwart & Fischer (2021, Lem. 3.1 and step (ii) follows by applying Steinwart & Fischer (2021, Lem. 3.10). The claim follows by noting that C denotes cover of minimum cardinality, and hence by definition [C] A 1).
SSteinwart & Fischer (2021, Lem. 3.11) )) is stated for disjoint partition of X' in two sets, but the argument he repeated for any finite cover of X.
25

---

Published as a conference paper at ICLR 2022
Lemma 4 (Covering number for product kernel) Given X' R and a reproducing kernel K.
X' x X - R, consider the product kernel k _ k Rddd S2d R defined
k(z.v)= = I[ k(2s, Uc) for x. E X A X C CR...
diimss
Then the covering numbers of the two kernels are related as follows:
(x .)) [M(xX >)]
(49)
Proof Let H denote the RKHS corresponding to K. Then the RKHS corresponding to the kernel is given by the tensor product 44 _ H x H x ... H. Berlinet & Thomas- (2011, Sec. 4.6), ie., for any f E Hk. there exists f1, f2. ... fa H such that
f(x) I fi(;;) for all
E Xd
(50)
Let (Z) BR denote an 6-cover of B₂ -orm (Def. 1). Then for each fi H. we have fo E Cx(d,)) such that
sup=ex - - Se.
(51)
Now, we claim that for every f e Bk, there exists g Cx & (C, such that
()Peexs=/[(>) g(>)l - de|l<<lae
(52)
which immediately implies the claimed bound (49) on the covering number. We now prove the claim (52). For any fixed f Hk. let fú, f. denote the functions satisfying (50) and (51) respectively. Then, we prove our claim (52) with g II Fr Cx. Using the convention I fa(xx) 1, we find that
If(x) g(x)|
= [T f(x,) II Fa(z))
$ E (((x) ( Je(oss) I1 fs(7)) I (xxx))
(11)
< de supheB, | < dell<el
where in the last step we have used the following argument:
supzex (xx) = supzex h k(2z - ||h||, Vx(z,2) s VIlullo for any h E Bx-
The proof is complete.
Lemma (Relation between Euclidean covering numbers) We have
Noc (B) <
Vxd I.
(1
<
d V for all d 2 1.
Proof We apply Wainwright (2019, Lem. 5.7) with B (r(r) and B' = Boo (1) to conclude that
(B2()))) < (r) (I))
< Vol(B, + vd)) S r(5+1) (2r + Vdy².
4/2
Vol(B (1)
where Vol(2') denotes the d-dimensional Fuclidean volume of X c IRd, and T(a) denotes the Gamma function. Next, we apply the following bounds on the Gamma function from Batir (2017,
Thm. 2.2):
r(b + 1) 2 (b/e)*V2Tb for any b 2 1, and r(b + 1) < (b/c) for any b > 1.1.
Thus, have
Noc (B2()), <
V2nd 107 (2r Vdlad < - [a+
2r 2en va
as claimed, and we are done.
26

---

Published as a conference paper at ICLR 2022
J.2 PROOF OF PROP. 2: COVERING NUMBERS FOR ANALYTIC AND DIFFERENTIABLE KERNELS
First we apply Lem. 2 so that it remains to establish the stated bounds simply on log (XV,
Proof of bound (37) in part (a) The bound (37) for the real- sal--nnlytic kernel is restatement of Sun & Zhou (2008, Thm. 2) in our notation (in particular, after making the following substitutions
in their notation: R 4- 1, Co Cu, Ra, X A, F r!,
E, D + 2 n d).
Proof of bound (39) for part (b): Under these assumptions, Steinwart & Christmann (2008, Thm. 6.26) states that the i-th dyadic entropy number Steinwart & Christmann (2008, Def. 6.20) of the identity inclusion mapping from H (r) to T Bx())) is bounded by ',,,kk r-i--//d for some constant '',d,k independent of e and r. Given this bound on the entropy number, and applying Steinwart Christmann (2008, Lem. 6.21), we conclude that the log-covering number log (r), e) is bounded by 4n (()aa/////)) Ca,d,rd (1/e)4/s as claimed.
J.3 PROOF OF PROP. 3: COVERING NUMBERS FOR SPECIFIC KERNELS
First we apply Lem. 2 so that it remains to establish the stated bounds in each part on the corre- sponding log
Proof for GAUSS kernel: Part (a) The bound (40) for the Gaussian kernel follows directly from Steinwart & Fischer (2021, Eqn. 11) along with the discussion stated just before it. Furthermore, the bound (41) for CGauss,d are established in Steinwart & Fischer (2021, Eqn. 6), and in the discussion around it.
Proof for MATÉRN kernel: Part (b) We claim that MATÉRN(U, 7) [v 5 -times continuously differentiable which immediately implies the bound (42) using Prop. 2(b).
To prove the diffcrentiability, we use Fourier transform of Matérn kernels. For k MATÉRN(H, 7), let k Rd + IR denote the function such that noting that k(x, y) x(x-z) Then using the Fourier transform of from Wendland (2004, Thm 8.15), and noting that н: is real-valued, we can write
k zz, y) O. f cos(w (z - v)) + |||||| |w))))
for some constant Ck.d depending only on the kernel parameter, and d (due to the normalization of the kernel, and the Fourier transform convention). Next, for any multi-index a E No. we have
ga. cos(w T (æx y)? + ||ا||| ||ا) < I1 201 (72 + (1w122 s (72+|10133
where a denotes the partial derivative of order a. Moreover, we have
| | 1
(v2+|w | 13"- dw ca Saso pd - 2 (72+ dr S ca frso n 1-1422 -2 00,
(1)
where step (i) holds whenever
d- 1 + 2 2 2v < -1
Then applying Newey & McFadden (1994, Lemma 3.6), we conclude that for all multi-indices such that " Og S IV 4 the partial derivative Ia.ak exists and is given by
Ck.d I ga cas(wT (a - -))( + ||! d"w,
and we are done.
27

---

Published as a conference paper at ICLR 2022
Proof for IMQ kernel: Part (c) The bounds (43) and (44) follow from Sun & Zhou (2008, Ex. 3), and noting that F/22 is bounded by (1+ dr (Wainwright, 2019, Lem. 5.7). O
Proof for SINC kernel: Part (d) For k = SINC(O), we can write k(t, y) = II Ne yi) sin(6t) 8t
( sim(]/0]) where step (i) follows from the fact that [@t]
for Kig RR R defined (t) t ++ sin sint/t is an even function. Thus, we can apply Lem. 4. Given the bound (49), and noting that ||Ko|| x = 1, it suffices establish the univariate version of the bound (45), namely,
Mx(l-r,r,,e) S (1 + ) (4gg - 2 4 log 17)².
To do so, we claim that univariate SINC kernel an analytic kernel that satisfies the condition (36) of Prop. 2(a) with x(t) (ON)( R2 12 and C, and thus applying the bounds (37) and (38) from Prop. 2(a) with A (r) yields the claimed bound (45) and (46). To verify the condition (36) with the stated parameters, we note that
<(t)= = SINC(OVE)
iovV Ej= 121-1J] (0V8)25t1 = Li=0 12- (OVE)3)
= Ei= (2ý-1)) 8 t
1
which implies
(0) 12 0 S (2/R.Yji for Rs a 3 innfz21((2) ((2j + +)1)a//
gz.
and we are done.
Proof for B-SPLINE kernel: Part (e) For = B-SPLINE(2,3 + 1, 1, we can write k(z, y) =
IT K2,y
v4)) for K3 R + R defined as (t) 2 B @ 299+2 1 1 3.3. (7 (7.t), -), and thus apply Lem. 4. Given the bound (49), and noting that [|,,,, lloc S (Dwivedi & Mackey (2021, Eqn. 107)), it suffices to establish the univariate version of the bound (47). Abusing notation
((r; (2,,((1;
and using Kg.y denote the univariate B-SPLINE(23 + 1,)) kernel, we find that
log (1- K3.g 2" e) S 1), log./l
KB,1 (1- 51,s))
max(7; (7, 1) CD.SPLINE (1/e)=15
where step (i) follows from Steinwart & Fischer (2021, Thm. 2.4, Sec. 3.3), and for step (ii)
we use the fact that the unit-covering number of 70, is bounded by max(7, 1), and apply the covering number bound for the univariate B D-SPLINEkerne from Zhou (2003, Ex. 4) (by substituting m 2,3 in their notation) along with the fact that log Ag kg (1- 1. )), log A ((0. 1).=) since Ki is shift-invariant.
Kg.1
K PROOF OF TAB. 3 RESULTS
In Tab. 3, the stated results for all the entries in the TARGET KT column follow directly by substi- tuting the covering number bounds from Prop. radii growth conditions for the target P. (We substitute m = loga n since we thin to /n output size.) For the KT+ column, the stated result follows by either taking the minimum of the first two columns (whenever the ROOT KT guarantee applies) or using the POWER KT guarantee. First we remark how to always ensure rate of at least 0((=)) even when the guarantee from our theorems are larger, using a suitable baseline procedure and then proceed with our proofs.
the corresponding entry along with the stated
Remark 2 (Improvement over baseline thinning) First we note that the KT-SWAP step en- sures that. deterministically, MMDx(Sm. Sxt) < MMDx(Sm, Spase) and MMD Sxr) I 2 MMD, Sin) + MMDx Srase) for Space a baseline thinned coreset of size Tme and any tar- get P. For example if the input and baseline coresets are drawn i..dd and k is bounded, then
a
28

---

Published as a conference paper at ICLR 2022
MM SKT) and MMDx(PP SKI) O(v/2m) /n) with high probability (Tolstikhin et al., 2017, Thm. A. even if the guarantee of Thm. 2 is larger. As a consequence, in all well-defined KT variants, we can guarantee a rate of n for MMDx SKr) when the output size is vnn simply by using baseline as i..dd thinning in the KT-SWAP step.
GAUSS kernel The TARGET KT guarantee follows by substituting the covering number bound for the Gaussian kernel from Prop. 3(a) in (6), and the ROOT KT guarantee follows directly from Dwivedi & Mackey (2021, Tab. 2). Putting the guarantees for the RoOT KT and TARGET KT together (and taking the minimum of the two) yields the guarantee for KT+.
IMQ kernel The TARGET KT guarantee follows by putting together the covering bound Prop. 3(c) and the MMD bounds (6).
For the ROOT KT guarantee, we use a square-root dominating kernel K,t IMQ(U', 2') Dwivedi & Mackey (2021, Def.2) suggested by Dwivedi & Mackey (2021). Dwivedi & Mackey (2021, Eqq)()17)) shows that kn. is always defined for appropriate choices of v', v', The best ROOT KT guarantees are obtained by choosing largest possible v' (to allow the most rapid decay of tails), and Dwivedi & Mackey (2021, Eqn.()17)) implies with < d. the best possible parameter satisfies
V' S'S 4 + 2. For this parameter, some algebra shows that max(P:
1 RK.... Zd,u.y n' n!/2v, leading
Ri
guarantee worse than n 1, so that the guarantee degenerates KT. When // 2 d we can use a MATÉRN kernel as a square-root dominating kernel from Dwivedi 2. & Mackey (2021, Prop. 3), and then applying the bounds for the kernel radii (17), and the inflation factor (19) for a generic Matérn kernel from Dwivedi & Mackey (2021, Tab. 3) leads to the entry for the ROOT KT stated in Tab. 2. The guarantee for KT+ follows by taking the minimum of the two.
using Rem. for ROOT
MATÉRN kernel For TARGET KT, substituting the covering number bound from Prop. 3(b) in (6) with R log yields the MMD bound of order
(lng n) 2/
(53)
which is better than n 1 only when v > 3d/2, and simplified to the entry in the Tab. 3 when we assume v is an integer. When v S 3d/22, we can simply use baseline as i..d. thinning to obtain an order MMD error as in Rem. 2.
The ROOT KT (and thereby KT+) guarantees for v > follow from Dwivedi & Mackey (2021, Tab. 2).
When A E ($.d]. d). we use POWER KT with a suitable a to establish the KT+ guarantee. For MATÉRN(P. 7) kernel, the a-power kernel is given by MATÉRN( (az, 7) if av > (a proof of this follows from Def. 2 and Dwivedi & Mackey (2021, Eqns (71-72))). Since LAPLACE(O) MATÉRN( ( we conclude that its a-power kernel defined for a >> dd And us- ing the various tail radii (17), and the inflation factor (19) for generic Matérn kernel from Dwivedi Mackey (2021, Tab. 3), we conclude that M. Zd,k.. Vlog log log n, and max(RR kn.n Ri..,)) n Zd.k. log n, so that Rmax = Oakk. (logn) (18) for SUBExP P setting. Thus for this case, the MMD guarantee for /n thinning with POWER KT (tracking only scaling with n) is
1-1
2
Ka
l
oo)
To (2-D7,)
da 2+
(4r)
Rmax
M..
n
T($+1)
"==((( (Sn(loo m) (42d( I-o)
Jd.k..8
(Vc,, logn)' क
(llg n)
[c,,
n
where en = log log n;; and we thus obtain the corresponding entry (for KT+) stated in Tab. 3.
SINC kernel The guarantee for TARGET KT follows directly from substituting the covering num- ber bounds from Prop. 3(d) in (6).
29

---

Published as a conference paper at ICLR 2022
For the ROOT KT guarantee, note that the square-root kernel construction of Dwivedi & Mackey (2021, Prop.2) implies that SINC(0) itself is a square-root of SINC(#) since the Fourier transform of SINC is rectangle function bounded domain. However, the tail of the SINC kernel does not decay fast enough for the guarantee of Dwivedi & Mackey (2021, Thm. 1) to improve beyond the n bound of Dwivedi & Mackey (2021, Rem. 2) obtained when running ROOT KT with i.id. baseline thinning.
In this case, TARGET KT and KT+ are identical since K, = k.
B-SPLINE kernel
The guarantee for TARGET KT follows directly from substituting the covering number bounds from Prop. 3(d) in (6).
For B-SPLINB 7, kernel, using arguments similar that in Dwivedi & Mackey (2021, 4),.4), we conclude that (up to constant scaling) the a-power kernel is defined to be B-SPLINEE( A+ 1, whenever A 2a.3 + 2a - 2 2No. For odd 33 we can always take 1/2 and B-SPLINE + 1,7) a valid (up to a constant scaling) square-root kernel (Dwivedi & Mackey, 2021). For even 3+1 E (2) 1) by taking E N suitably, and the smallest suitable choice is = 1 = ah E N. which is feasible as long as 3 2 2. And, thus B-SPLINE(3 + 1, Ø+2 28+2 E (1 1). Whenever the
8, we have to choose a A p+1
suitable k. for B-SPLINE(2 + for even 8 Z 2 with
a-power kernel is defined, for the power B-SPLINE kernel from Dwivedi & Mackey (2021, Tab. 3) to obtain the MMD rates for POWER KT from Dwivedi & Mackey (2021, Tab. 2) (which remains the factors depending on a and (3)-
then apply the various tail radii (17), and the inflation factor (19)
ROOT KT upto
The guarantee for KT+ follows by taking the minimum MMD error for TARGET KT and ROOT KT for even 3, and c-POWER KT for odd B.
30


Reviews:
[{"review_id": "vAn1TJAxsoo", "reviewer": "Reviewer_8dTF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is hard to follow the ‘flow’ of this work. For instance, the definition of  KT-Split is only given in the appendix. It is preferable to recall briefly the principle and the intuition behind this algorithm in the main paper. The reader may ask some legitimate questions: what is the role of the kernel k_{split} in the algorithm? What are the benefits we gain from studying power kernel thinning?\n\nThe presentation of the paper is non-conventional. For example, Theorem 1 is followed by many remarks. The content of these remarks may fit in one or two paragraphs and the presentation would be more elegant.", "summary_of_the_paper": "This article studies a generalization of kernel thinning previously proposed in Dwivedi and Mackey (2021). The authors proposed a new variant of kernel thinning that does not require the knowledge of the square root of the kernel, for which they proved single function guarantees as well as the MMD guarantees. Several numerical simulations were conducted to support the theoretical claims.", "summary_of_the_review": "Up to my knowledge, the proposed algorithms and the corresponding theoretical guarantees are new in the community. However, the manuscript is heavily technical and dense. I am afraid that only readers familiar with kernel thinning may grasp the contribution of this paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "uK-ZRXzgOxG", "reviewer": "Reviewer_MW7b", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper seems as an extension of results of a previous paper. The algorithm for finding a subsample is the same, the first part of it (KT-split) is applied with a general kernel (split kernel), which may differ from square root kernel. Therefore, an interesting question is how the analysis given in arXiv:2105.05842 corresponds with an analysis given in terms of RKHS covering number. Is a new analysis leads to the same thinning error, when applied to square root kernel (or, the square root is somehow special?).\n\nFigure 2 shows that Root KT and Target KT give the same error as a function of coreset size. Is there any explanation of such behavior?\n\nExperimental part convinces that root/target KT gives smaller errors than iid, though Fig 3 shows more complicated picture when KT+ is compared with ST (Hitch IMQ k). Is there any explanation of that?", "summary_of_the_paper": "The paper's claims seem correct and sound. Claims are substantiated by a theoretical analysis, though the bulk of the paper's ideology comes from the previous publication (which the current paper extends). Experiments seem very similar to the previous paper's experiments.", "summary_of_the_review": "I believe this is a borderline paper. Some aspects of it were published before. A new analysis is presented (based on RKHS covering number).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "hxDm8B2KB2v", "reviewer": "Reviewer_5PwR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In terms of writing, the paper is quite technical and lacks intuition. I don't think putting so many results in the main body is necessary, e.g., there are six remarks after Theorem 1. \n\nI also have some concerns regarding the significance of the results. The summary from the authors emphasizes the error improvement from $n^{-1/4}$ to $\\sqrt{\\log n/ n}$, but this seems to be the main contribution of the prior work by Dwivedi and Mackey (2021). As for the current submission, the improvements are in the log factors. I didn't check the proofs of these two papers as they have 85 pages in total. Given that the prior work is twice the current length, I wonder if the authors can explain the technical novelty of the present paper that leads to the logarithmic improvement. In other words, why the prior work has the log factors?\n\nThe second contribution of the submission is  \"we show that, for analytic kernels, like Gaussian and inverse multiquadric, target kernel KT admits maximum mean discrepancy (MMD) guarantees comparable to square-root KT without the need for an explicit square-root kernel.\" I know this is related to Fourier transforms. Do the authors know under what condition the $\\mathbf{explicit}$ square-root kernels exist?\n\nThe experiments seem to be generated by the same software/scripts Dwivedi and Mackey (2021) used. It will be good if the author can also compare the run time of these algorithms. The proposed heuristics inherit the better rates the Dwivedi and Mackey (2021) algorithm provides and its quadratic time complexity. I would think that a more significant contribution would be reducing this algorithmic complexity, especially important for practical applications. ", "summary_of_the_paper": "The abstract already presents four contributions (first, second, etc.) of the paper. My summary: the submission extends the Kernel Thinning algorithm recently proposed by Dwivedi and Mackey (2021) to more general settings (kernel types). It also removes some dimension-dependent log factors in the bound. ", "summary_of_the_review": "I don't find the contribution of the current paper very significant compared to the Dwivedi and Mackey (2021) work. The paper adopts several critical theoretical contributions and algorithm designs from the prior work, maybe also the code. The writing is also technical and lacks intuitions and insights. I suggest the authors focus on improving the quadratic time-complexity instead, which should increase the significance/popularity of both works. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TlaQvHR6VIg", "reviewer": "Reviewer_LtTV", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I must apologise in advance that I am not an expert in the field of thinning, and the vast majority of the references were unfamiliar to me. However, I saw much more positives than negatives while reading the paper. \n\nFirstly, the paper was written in a clear manner, with a very convincing motivation of the problem. The contributions were well outlined in the context of existing works. The significance of the theoretical results were clear, and as far as I could see, the results were correct. One aspect I particularly appreciated was the amount of effort put into analysing all the different types of distributions and kernels, and summarising them in various tables. ", "summary_of_the_paper": "The paper proposes \"generalised kernel thinning\", which builds on the \"kernel thinning\" (KT) algorithm of [Dwivedi and Mackey, 2021]. The main generalisation is to replace the square-root kernel in the algorithm with k_{split}, which results in applicability without the knowledge of the square-root kernel, and theoretical guarantees are proved. Moreover, two instantiations of this generalisation are proposed, the alpha-power KT and KT+. ", "summary_of_the_review": "The paper motivates the problem in a clear and convincing way even for a non-expert, and clearly outlines its contributions. The results are significant, and as far as I can see, correct and sound. I recommend this paper to be accepted. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The focus of the paper is kernel thinning, i.e. the extraction of a core set from a sample with good integration properties meant in MMD (maximum mean discrepancy, hence worst case) sense. Particularly, the authors propose generalizations of the kernel thinning method (Dwivedi and Mackey, 2021) which relax the assumptions imposed on the kernel (k) and the target distribution (P), and possess tighter performance guarantees.

Designing compressed representation of samples for integration is a fundamental problem in machine learning and statistics with a large number of successful applications. As assessed by the reviewers, the authors deliver important new theoretical insights in the area which can be also of clear practical interest. They also pointed out that the self-containedness of the paper could be improved and additional intuition would help the dissemination of the results among the members of the ICLR/ML audience.
Decision: Accept (Poster)