Distribution Compression in Near-Linear Time
Authors: Abhishek Shetty
Raaz Dwivedi
Lester Mackey
Venue: ICLR 2022 Poster (2022)
Keywords: Distribution compression
linear time
thinning
i.i.d. sampling
Markov chain Monte Carlo
maximum mean discrepancy
reproducing kernel Hilbert space

Abstract: In distribution compression, one aims to accurately summarize a probability distribution $\mathbb{P}$ using a small number of representative points. Near-optimal thinning procedures achieve this goal by sampling $n$ points from a Markov chain and identifying $\sqrt{n}$ points with $\widetilde{\mathcal{O}}(1/\sqrt{n})$ discrepancy to $\mathbb{P}$. Unfortunately, these algorithms suffer from quadratic or super-quadratic runtime in the sample size $n$. To address this deficiency, we introduce Compress++, a simple meta-procedure for speeding up any thinning algorithm while suffering at most a factor of $4$ in error. When combined with the quadratic-time kernel halving and kernel thinning algorithms of Dwivedi and Mackey (2021), Compress++ delivers $\sqrt{n}$ points with $\mathcal{O}(\sqrt{\log n/n})$ integration error and better-than-Monte-Carlo maximum mean discrepancy in $\mathcal{O}(n \log^3 n)$ time and  $\mathcal{O}( \sqrt{n} \log^2 n )$ space. Moreover, Compress++ enjoys the same near-linear runtime given any quadratic-time input and reduces the runtime of super-quadratic algorithms by a square-root factor. In our benchmarks with high-dimensional Monte Carlo samples and Markov chains targeting challenging differential equation posteriors, Compress++ matches or nearly matches the accuracy of its input algorithm in orders of magnitude less time.

DISTRIBUTION COMPRESSION IN NEAR-LINEAR TIME
Abhishek Shetty', Raaz Dwivedi Lester Mackey²
Department of EECS, UC Berkeley
2 Department of Computer Science, Harvard University and Department of EECS, MIT
3 Microsoft Research New England SHETTY @ BERKELEY.EDU, RAAZ @ MIT.EDU, LMACKEY @ MICROSOFT.COM
ABSTRACT
In distribution compression, one aims to accurately summarize a probability dis- tribution P using small number of representative points. Near-optimal thinning procedures achieve this goal by sampling n points from a Markov chain and iden- tifying vn points with (1/vV) discrepancy to P.. Unfortunately, these algo- rithms suffer from quadratic or super-quadratic runtime in the sample size n. To address this deficiency, we introduce Compress++, simple meta- prece-pr for speeding up any thinning algorithm while suffering at most factor of in er- ror. When combined with the quadratic-time kernel halving and kernel thinning algorithms of Dwivedi and Mackey (2021), Compress++ delivers v points with O /ogg n /)) integration error and NetterthhanMMont-Caarrt maximum mean dis- crepancy in On log" n) time and O log" n) space. Moreover, Compress++ enjoys the same near-linear runtime given any quadratic-time input and reduces the runtime of super-quadratic algorithms by square-root factor. In our bench- marks with high-dimensional Monte Carlo samples and Markov chains target- ing challenging differential equation posteriors, Compress++ matches or nearly matches the accuracy of its input algorithm in orders of magnitude less time.
INTRODUCTION
Distribution compression- constructing a concise summary probability distribution iss at the heart of many learning and inference tasks. For example, in Monte Carlo integration and Bayesian inference, n representative points are sampled i.i.d. or from a Markov chain to approximate ex- pectations and quantify uncertainty under an intractable (posterior) distribution (Robert & Casella, 1999). However, these standard sampling strategies are not especially concise. For instance, the Monte Carlo estimate f 2 4 Σ ((;; of an unknown expectation P/ - Ex=r[/(X)] based on i.i.d. points has O(n à) integration error [P Pin requiring 10000 points for 1% rela- tive eтror and 10th points for 0.1% error. Such bloated sample representations preclude downstream applications with critically expensive function evaluations like computational cardiology, where a 1000 CPU-hour tissue or organ simulation is required for each sample point (Niederer et al., 2011; Augustin et al., 2016; Strocchi et al., 2020).
To restore the feasibility of such critically expensive tasks, it is common to thin down the initial point sequence to produce a much smaller coreset. The standard thinning approach, select every t-th point (Owen, 2017), while being simple often leads to an substantial increase in error: e.g., standard thinning n points from fast-mixing Markov chain yields 2(n 1) error when nå points are returned. Recently, Dwivedi & Mackey (2021) introduced a more effective alternative, kernel thinning (KT), that provides near optimal Ös(n à) error when compressing n points in IR down to size n While practical for moderate sample sizes, the runtime of this algorithm scales quadratically with the input size n, making its execution prohibitive for very large n. Our goal is to significantly improve the runtime of such compression algorithms while providing comparable error guarantees.
Problem setup Given a sequence Sin of n input points summarizing target distribution IP, our aim is to identify a high quality coreset Sout of size /ni in time nearly linear in n. We measure coreset quality via its integration error [P - PS |Pf
Sous Ezes.. f(x) for functions

---

in the reproducing kernel Hilbert space (RKHS) Hx induced by given kemne k (Berlinet & Thomas-Agnan, 201 We consider both single function error and kernel maximum mean discrep- ancy (MMD, Gretton et al., 2012), the worst-case integration error over the unit RKHS norm ball: (I, - suppiflles [Pf Sont fl.
(1)
Our contributions We introduce new simple meta procedue-CCoMRResS+++ that significantly
speeds up a generic thinning algorithm while simultaneously inheriting the error guarantees of its input up to a factor of 4. A direct application of COMPRESS+ to KT improves its quadratic ((n))
runtime to near linear (n log n) time while preserving its error guarantees. Since the (a(n=
KT MMD guarantees of Dwivedi & Mackey (2021) match the (2(n²)) minimax lower bounds of Tolstikhin et al. (2017); Phillips & Tai (2020) up to factors of vlog ni and constants depending on also provides near-optimal MMD compression for wide range of k and P. Moreover, the practical gains from applying COMPRESS++ are substantial: KT thins 65, 000 points in 10 dimensions in 20m, while KT-COMPRESS++ needs only 1.5m; KT takes more than day to thin 250, 000 points in 100 dimensions, while KT-COMPRESS++ takes less than 1hr (a 32x speed- up). For larger n, the speed-ups are even greater due to the order log"n reduction in runtime.
d, KT-COMPRESSS
COMPRESS+ can also be directly combined with any thinning algorithm, even those that have suboptimal guarantees but often perform well in practice, like kernel herding (Chen et al., 2010). MMD-critic (Kim et al., 2016), and Stein thinning (Riabiz et al., 2020a), all of which run in (2(n²) time. As a demonstration, we combine COMPRESS+ with the popular kernel herding algorithm and observe 45x speed-ups when compressing 250, 000 input points. In all of our experiments, COMPRESS+ leads to minimal loss in accuracy and, surprisingly, even improves upon herding accuracy for lower-dimensional problems.
Most related to our work are the merge-reduce algorithms of Matousek (1995); Chazelle & Ma- tousek (1996); Phillips (2008) which also speed up input thinning algorithms while controlling ap- proximation error. In our setting, merge-reduce runs in time 2(n (55 given n input and in time ((n(++)/2) for slower n -time inputs (see, e.g., Phillips, 2008, Thm. 3.1). In contrast, COM- PRESS++ rums in near-linear O(n log n) time for any n -time input and in O(n log" time for dlowern-ttnng inputs. After providing formal definitions in Sec. 2, we introduce and analyze COM- PRESS+ and its primary subroutine COMPRESS in Secs. and 4, demonstrate the empirical benefits of COMPRESS++ in Sec. 5, and present conclusions and opportunities for future work in Sec. 6.
Notation We let Ps denote the empirical distribution of S. For the output coreset SALG of algo- rithm ALG with input coreset Sm,
the simpler notation PALG & I and Pin & P.... We extend our MMD definition to point sequences (S,, via (S,, & MMM (P's Ps,) and MMDx((P S1) & MMD (P, Ps.)). We use a 3 b to mean a
O(b). a 2 b mean a Q(b), a (b) to mean both a = (b)) and a = ?(bb). and log to denote the natural logarithm.
2 THINNING AND HALVING ALGORIHTM
We begin by defining the thinning and halving algorithms that our meta-procedures take as input.
Definition (Thinning and halving algorithms) A thinning algorithm ALG takes as input a point sequence S.n of length and returns (possibly random) point sequence SALG of length nout. We say ALG is ar -thinniin if nout = |n/os, an. and root-thinning if an = v n.. Moreover, we call ALG a halving algorithm if SALa always contains exactly [ of the input points.
Many thinning algorithms offer high- probbbbbbbbbltty bounds on the integration error IP.... - P We capture such bounds abstractly using the following definition of a sub-Gaussiag thinning
Definition 2 (Sub-Gaussian thinning algorithm) For a function J, we call a thinning algorithm
ALG f-sub-Gaussian with parameter v and write ALG E E.5(v) (v) if
(22) 2
(A(F' ((exp(A(F's..
P f)) Sial S exp
for all
X E E.
Def. 2 equivalent to a Lub-Gaussian tail bound for the integration error, and, by Boucheron et al. (2013, Section 2.3), if AL.G E g (v) then E[PsuaJ (S.]] = P.s.. and, for all 5 E (0.1),
PPs... --Fsaa S v(n) log( {), with probability at least 8 given S..
2

---

Hence the integration error of ALG is dominated by the sub- Gaussian parameter v(n).
Example (KT-SPLIT) Given a kernel and n input points Si,. the KT-SPLIT(6) algorithm' of Dwivedi & Mackey (2022; 2021, Alg. Ia) takes ((n") kernel evaluations to output coreset of size Pour. with setter-than-ii.d. integration error. Specifically, Dwivedi & Mackey (2022, Thm. 1) prove that, event with probability 2. KT-SPLIT(O) (²) with
v(n)
2 Moui3 v3 V log( 6roaa log, (n/nons)
|
for all / with | =1
Many algorithms also offer high-probability bounds the kernel MMD (1), the worst-case inte- gration error across the unit ball of the RKHS. We again capture these bounds abstractly using the following definition of a &-sub-Gaussian thinning algorithm.
Definition 3 (k-sub-Gaussian thinning algorithm) For kernel k. call a thinning algorithm ALG k-sub-Gaussian with parameter e and shift a and write ALG E GK(v, a) if
P[MMDx(Sin: Saia) an + Un V Sm] Se for all 120 0.
We also call (n) A max(Un, an) the k-sub-Gaussian error of AL.G.
Example 2 (Kernel thinning) Given kernel k and input points Sin. the generalized kernel thin- ning (6) algorithm' of Dwivedi & Mackey (2022; 2021, Alg. 1) takes ((n²) kernel evaluations to output coreset of size nout with near-optimal MMD error. In particular, by leveraging appro- priate auxiliary kernel kaplit, Dwivedi & Mackey (2022, Thms. 2-4) establish that, on an event with probability 2.
8 KT())= E Sk(a, v) with
On
Co
and
Un
Co.
V
|apkiit log( 6roout log, (oout)
Ms Kapla
Rome
Nome
where | olco sup, keplie (I, .r), Co and C, explicit constants, and M. S. > 1 is non- decreasing in n and varies based on the tails of Keplit and the radius the ball containing Sin-
COMPRESS
The core subroutine of COMPRESS++ is new meta-procedure called COMPRESS that, given halv- ing algorithm HALVE, an oversampling parameter and input points, outputs a thinned coreset of size 28 /T. The COMPRESS algorithm (Alg. 1) is very simple to implement: first, divide the input points into four subsequences of size 4 (in any manner the user chooses); second, recursively call
COMPRESS on each subsequence to produce four coresets of size 28- Vn: finally, call HALVE on concatenation of those coresets to produce the final output size 29 vni. As we show in App. H. COMPRESS can also be implemented in a streaming fashion to consume most ((49 /T) memory.
3.1 INTEGRATION ERROR AND RUNTIME GUARANTEES FOR COMPRESS
Our first result relates the runtime and single-function integration error of COMPRESS to the runtime and еттог of HALVE. We measure integration error for each function f probabilistically in terms of the sub-Gaussian parameter v of Def. 2 and measure runtime by the number of dominant operations performed by HALVE (e.g., the number of kernel evaluations performed by kernel thinning).
Theorem (Runtime and integration error of COMPRESS) If HALVE has runtime ru(n) for in- puts of size n, then COMPRESS has runtime
re(n) -ih 4 rn((,22")),
(S)
where L, & 20+1 /n (twice the output size of COMPRESS), and 3n e logz( log, n Furthermore, if. for some function J. HALVE E (UH). then COMPRESS E G (vc) with
g 1.
(2(n) - 3 vR((,,2-))
(6)
'The 5 argument of KT-SPLIT(A8) KT()) indicates that each parameter & 9 in Dwivedi & Mackey (2022, Alg. la), where & is the size af the input point sequence compressed by KT-SPI.IT(8) KT(8).
3

---

Algorithm 1: COMPRESS
Input: halving algorithm HALVE, oversampling parameter g. point sequence Sin of size 4 then return Su. Partition S., into four arbitrary subsequences (5:) each of size n/4
for 1,2,3, 4 do
S. COMPRESS(S,, HALVE,
I/ return coresets of size 2
end
S.. S.,
I/ coreset of size 2 2 Vi
return HALVE(S)
I| coreset of size 29 vn
we prove in App. B, the runtime guarantee (5) is immediate once we unroll the COMPRESS recursion and identify that COMPRESS makes 4' calls to HALVE with input size f, The ror guarantee (6) is more subtle: here, COMPRESS benefits significantly from random cancellations among the conditionally independent and mean-zero HALVE errors. Without these properties, the errors from each HALVE call could compound without cancellation leading to significant degrada- tion in COMPRESS quality. Let
unpack the most important implications of Thm. 1.
Remark 1 (Near-linear runtime and quadratic speed-ups for COMPRESS) Thm. implies that a quadratic-time HALVE with (n = n²² yields a near-linear time COMPRESS with rc(n) S 40+1 nn(log, (m) (n)- g). If HALVE instead has super-quadratic runtime (n( = n², COMPRESS enjoys
a quadratic speed-up: (n) S c, n²/ for e, & 2r(0+2)
2--4 More generally, whenever HALVE has superlinear runtime rn(n)= = n² p(n) for some 2 and non-decreasing P. COMPRESS satisfies
rc(n) - Cr n (log, (n) 8) plen) for
for <
where - 4(7-110++1,
4 n/2 p(Ln)
Remark (COMPRESS inflates sub-Gaussian error by at most Vlog, n) Thm. also implies
vc(n)= S VB, + ((())) = Vlog, n g ((())
in the usual case that n (n) is non-decreasing in n. Hence the sub-Gaussian error of COMPRESS is at most Vloga n larger than that of halving an input of size f.. This is an especially strong benchmark, as fn is twice the output size of COMPRESS, and thinning from n to & points should incur at least as much approximation error as halving from éy to la points.
Example 3 (KT-SPLIT-COMPRN) of size HALVE KT-SPLIT( (A,+*( from Ex. 1. Since KT-SPLIT runs in time O(n²), COMPRESS runs in near-linear (n log time by Rem. 1. In addition, as we detail in App. F.I, on an event of probability 1 8 2. every HALVE call invoked by COMPRESS is f-sub-Gaussian with
Consider rumning COMPRESS with, for each HALVE input &
PH({) W/ V log( 12n4" +
||||| for all with || =
Hence, Rem. implies that COMPRESS is f-sub-Gaussian on the same event with vc(n) S Vlog4 n (fx),,, guarantee within Vloga of the original KT-SPLIT(6) error (2).
3.2 MMD GUARANTEES FOR COMPRESS
Next, we bound the MMD error of COMPRESS in terms of the MMD error of HALVE. Recall that MMD (1) represents the worst-case integration error across the unit ball of the RKHS of k. Its
proof, based on the concentration of subexponential matrix martingales, is provided in App. C.
Theorem (MMD guarantees for COMPRESS) Suppose HALVE E Gk v) for n an and n Un non-decreasing and E. [ IHAIIE Sin] P. k. Then COMPRESS E 91a 8) with
Un 2 4(ae, + tue.) (ee.)) 2(log, n n-g) g). and ān 2 U, log(og) where l, 20+1 Fu in Thm. I.
(8)
4

---

Remark 3 (Symmetrization) We convert any halving algorithm into that satisfies the un- biasedness condition E (HHvvg Sin] = Pink without impacting integration error by symmetriza- tion, i.e. by returning either the outpuited half its complement with equal probability.
Remark 4 (COMPRESS inflates MMD guarantee by at most 10 log(n+1)) Thm. 2 implies that the Aesub-Gaussian error of COMPRESS is always at most 10 log(n++1) times that of HALVE with input size ln = 29+1 /n since
Ck, COMPRESS (n) Def. max ú.) S (n + 1) max(ae,, vt,)) = 10 + 1) (K,
As in Rem. 2, HALVE applied to an input of size é, is a particularly strong benchmark, as thinning fe points should incur least as much MMD error as halving from l 4z. from 2
Example 4 (KT-COMPRESS) Consider running COMPRESS with, for each HALVE input of size e, 2
HALVE = KT (8) from Ex. 2 after symmetrizing as in Rem. 3. Since KT has (()²) runtime, COMPRESS yields near- near-linear O(n log n) rumtime by Rem. 1. Moreover, as we detail in App. F2, using the notation of Ex. 2, on an event & of probability at least 1 S. every HALVE call invoked by COMPRESS is Gau-Gaassian with
ag = 20 k lcc and 02 = 20
k |/o log( 12n49 +1)
S.s..k
26
Thus, Rem. implies that, on E, KT-COMPRESS has k-sub-Gaussian error 6k CoMPeSssS (n) 10 log(n+ HAvk guarantee within 10 log((+1)) of the original KT MMD error (4).
COMPRESS++
To offset any excess error due to COMPRESS while maintaining its near-linear runtime, we next troduce COMPRESS+ (Alg. 2), simple two-stage meta- meta--rocedurr for faster root-thinning. COM- PRESS++ takes as input an oversampling parameter g. a halving algorithm HALVE, and a 29 -thinning algorithm THIN (see Def. 1). In our applications, HALVE and THIN are derived from the same base algorithm (e.g., from KT with different thinning factors), this not required. COMPRESS ++ first runs the faster but slightly more erroncous COMPRESS COMPRESS(HALVE HALVEE, g) algorithm to produce an interme- diate coreset of size 2 /T. Next, the slower but more accurate THIN algorithm is run on the greatly compressed intermediate coreset produce final output of size vn. In the sequel, we demonstrate how to set g to offset error inflation due to COMPRESS while maintaining its fast runtime.
Algorithm 2: COMPRESS++
Input: oversampling parameter g. halving alg. HALVE, 2e-thinning alg. THIN, point sequence S., of size // coreset of size 2 /n // coreset size v/n
Sc COMPRESS(HALVE, 0, S..)
Sc+ < THIN(Sc)
return ScH
4.1
INTEGRATION ERROR AND RUNTIME GUARANTEES FOR COMPRESS+
The following result, proved in App. D, relates the runtime and single-function integration error of COMPRESS++ to the runtime and error of HALVE and THIN.
Theorem (Runtime and integration error of COMPRESS++) If HALVE and THIN have run- times (n(n) and (T(n) respectively for imputs of size n, then COMPRESS+ has runtime
(n) = rc(nn) + +r((c//2) where re(n) ( Bn 4' (H(,22-'),
(9)
ln 20+1 VT, and 3n log, g g-1 as in Thm. 1. Furthermore, if for some function f. HALVE E (1H) and THIN E G (VT), then COMPRESS++ E G (vC++) with
(n) = (2(m) + =2((n/2) where vn( Din 4 . 1
5

---

Remark 5 (Near-linear runtime and near-quadratic speed-ups for COMPRESS++) When HALVE and THIN have quadratic runtimes with max(r=(n)) (r)))r((())) (r(n)) = n2, Thm. 3 and Rem. yield
that rc++ (n) I 48+1 (logg, (n) g) 4 Hence, COMPRESS++ maintains near-linear runtime
(n) = log logg+1(()) whenever 4 (logi nt..
(10)
HALVE and THIN instead have super-quadratic runtimes with max(r=(w), (T()) = n², then by Rem. 1 we have (c++(n) - 2
-4 + 1) n/2, so that COMPRESS++ provides a near-quadratic oT/2 (n)) whenever 48 = OOlog n))
speed up (c++(n) = O(n" logi
Remark 6 (COMPRESS++ inflates sub-Gaussian error by at most v22 In the usual case that n (n)n)) is non-decreasing in n, Thm. and Rem. 2 imply that
C (n) S (log, (n x4( (x) (1 log 10
( ((((n/2))
Su(6e)
where we have introduced the rescaled quantities (n((),)) - (n((e and Gr - vovr( Therefore, COMPRESS+ satisfies
(n++ & v2vr((e) whenever g 2 log, log, + log2 Sn(te) (r(e./))
(11)
That is, whenever COMPRESS++ is run with oversampling parameter g satisfying (11) its sub- Gaussian error is never than v2 times the second-stage THIN error. Here, THIN represents strong baseline for comparison as thinning from fn/2 to vn points should incur at least as much error thinning from v points.
As we illustrate in the next example, when THIN and HALVE are derived from the same thin- ning algorithm, the ratio (ulfa) is typically bounded by constant C so that the choice
[n(En/2]
[log, log, n + log2 C7 suffices to simultaneously obtain the v2 relative error guarantee (11) of Rem. 6 and the substantial speed-ups (10) of Rem.
Example 5 (KI-SPLIT-COMPREEL
In the notation of Ex. consider rumning COMPRESS++
82 with HALVE = KT-SPLIT( 1n=2( (1. 5) when applied to an input of size and THIN = KT-SPLIT +1) 6). As detailed in App. E3, on an event of probability z. COM- +RESS+ invocations of HALVE and THIN are simultaneously f-sub-Gaussian with parameters sat- isfying
Vlog( S 20 (0
|||1
Cn(C.)) for all f with || Ci )
|K 1. (12)
Since KT-SPLIT runs in On=²) time, Rems. 5 and 6 imply that KT-SPLIT-COMPRESSH with [log, log, n. runs in near-linear On log² n) time and inflates sub-Gaussian error by at most /2.
4.2 MMD GUARANTRES FOR COMPRESS+
Next, we bound the MMD error of COMPRESS+ in terms of the MMD error of HALVE and THIN. The proof of the following result can be found in App. E.
Theorem (MMD guarantees for COMPRESS++) If E Gk(a',v),, HALVE e Gx(a,v) for n 0n and n Ur non-decreasing, and E. PHALVEE Smn] Pink, then COMPRESS++ E 9x(ā, 7) with
Tr Un + vle/12 and on an + dlc,/2 + En Fogg
for Un and on defined in Thm. and l, 20+1 fn in Thm. 1.
Remark 7 (COMPRESS++ inflates MMD guarantee by at most 4) Thm. 4 implics that the COMPRESS+ Gaub-Ga error E ck ComPreSSt+ = max(a,, (,) satisfies
Ek. COMPRRES+++ (n) < log(n + EK. (lx) + Ek, La (1+ vlg
< THIN (x)
10gg(n+11) (n(e.)) + 1) + 2),
20
ST(

---

where we have introduced the rescaled quantities Su(en) _ fn EK, (Cn) and (r(
-
v TT (.) Therefore, COMPRESS++ satisfies
(o S E ( whenever
2 log, log(n + 1) + log, (8.5 Gulba)) Gr (T))
(13)
In other words, relative to strong baseline of thinning from fn to / points, COMPRESS+ inflates error by at most factor of 4 whenever g satisfies (13). For example, when the ratio (n(en)/Sr(( 4e) bounded by C, it suffices to choose g = [log, log(n + 1)+ log2(8.5)))
Example 6 (KT-COMPRESS+++ In the notation of Ex 2 and Rem. 3, consider running COM- 1
PRESS+ with HALVE symmetrized KT in22 (n +1)00 when applied an input of size l and THIN KT 9+2. (9,,,,,11,)) As we detail in App. F.4,
event of probability 1 - /. all
COMPRESS+ invocations of HALVE and THIN are simultaneously A-sub-Gaussiar with
(a((e)) = (+) C. v | log( 6/n(0+20(B, Mss..k
(n((..) <T(
=1. 1.
As KT runs @nn²) time, Rems. and imply that *T-COMPRESS++ with g [log2 log + runs in near-linear (n log n) time and inflates k-sub- -suu-Gaussian error by at most 4.
EXPERIMENTS
We now turn to empirical evaluation of the speed-ups and error of COMPRESS++. We begin by describing the thinning algorithms, compression tasks, evaluation metrics, and kernels used in our experiments. Supplementary experimental details and results can be found in App. G.
Thinning algorithms Each experiment compares a high-accuracy, quadratic time thinning algorithm-either target kernel thinning (Dwivedi & Mackey, 2022) or kernel herding (Chen al., 20th)-with our near-linear time COMPRESS and COMPRESS++ variants that use the same input algorithm to HALVE and THIN. In each case, we perform root thinning, compressing input points down to /n points, so that COMPRESS is run with = 0. For COMPRESS++, we use g = 4 through- out satisfy the small relative error criterion (11) in all experiments. When halving we restrict each input algorithm to return distinct points and symmetrize the output as discussed in Rem. 3.
Compressing i.i.d. summaries To demonstrate the advantages of COMPRESS++ over equal-sized i..d. summaries we compress input point sequences Sn, drawn i.i.d. from either (a) Gaussian targets (O, Ia) with d E {2, 4, 10, 100} or (b) M-component mixture of Gaussian targets PP M |E=NN(( I2) with M E {4, 6, 8, 32} and component means P4 E R2 defined in App. G.
T
Compressing MCMC summaries To demonstrate the advantages of COMPRESS++ over standard MCMC thinning, also compress input point sequences S,, generated by variety of popular MCMC algorithms (denoted by RW, ADA-RW, MALA, and PMALA) targeting four challenging Bayesian posterior distributions P. In partieular, (2020a) based on the Goodwin (1965) model of oscillatory enzymatic control (d = 4), the Lotka (1925); Volterra (1926) model of oscillatory predator-prey evolution (d 4), the Hinch et al. (2004) model of calcium signalling in cardiac cells (d = 38), and tempered Hinch model posterior (d = 38). Notably, for the Hinch experiments, each summary point discarded via an accurate thinning procedure saves 1000s of downstream CPU hours by avoiding an additional critically expensive whole-heart simulation (Riabiz al., 2020a). See App. for MCMC algorithm and target details.
adopt the four posterior targets of Riabiz et al.
Kernel settings Throughout we use a Gaussian kernel k(æ, y) = exp( - 2 || - -11(2) with o² as specified by Dwivedi & Mackey (2021, Sec. K.2) for the MCMC targets and o² 2d otherwise.
Evaluation metrics For each thinning procedure report mean runtime across 3 runs and mean MMD error across 10 independent runs + I standard error (the error bars are often too small to be visible). All runtimes were measured a single core of an Intel Xeon CPU. For the i.i.d. targets, we report MMDx(IP Pout) which can be exactly computed in closed-for form. For the MCMC targets, report the thinning error MMD,, (P IP..... analyzed directly by our theory (Thms. and 4).
Kernel thinning results We first apply COMPRESS+ to the opar-optimal KT algorithm to obtain comparable summaries at fraction of the cost. Figs. and 2 reveal that, in line with our guarantees,
7

---

d=2
d=4
d=10
d=100
2
Nean MMD
2
2
2-
2.4
+-61
4-Tiicnns
K7
2.4
2-10
X2
Input
Ioput
Ingut
Input
2=2
d=4
d=10
d=100
Singl corn runtim
XT
Brd
KT-Comp++
KT Comp
10m
10m
10m
10m
1m
Im
10
14
Input
Input
Inpul
Inpur
d-2
dm4
d=10
d=100
Mean MMD
Hard Doep
Hlrrk- Comp--
Hard-Gorp
Hard-Capp
Dhep
Hard-Corp
HardCaapp
Input size
Ingut size
Input size
Input size
d=2
d=4
d=10
d=100
Stagle core runtine
10hr
10hr
Hard d-cod---
thr
the
Hlerd Comp
10m
10m
10m
Im
Im
10x
10s
101
10
10
10a 12
10a
107
10
10
10
10P
10'
304
107
Input slze
Input size
Ingitt size
Ingut size
Figure 1: For Gaussian targets P in R KT-COMPRESS++ and Herd- COMPRESS++ improve upon the MMD i..d. sampling (ST), closely track the error of their respective quadratic- input algorithms KT and kernel herding (Herd), and substantially reduce the runtime.
KT-COMPRESS++ matches or nearly matches the MMD error KT in all experiments while also substantially reducing runtime. For example, KT thins 65000 points in 10 dimensions in 20m, while KT-COMPRESS++ needs only 1.5m; KT takes more than a day to thin 250000 points in 100 dimensions, while KT-COMPRESS++ takes less than hour (a 32x speed-up). For reference also display the error of standard thinning (ST) to highlight that KT--COPPRESS++ significantly improves approximation quality relative to the standard practice of i.idd. summarization or standard MCMC thinning. See Fig. 4 in App. G.1 for analogous results with mixture of Gaussian targets.
Kernel herding results A strength of COMPRESS+ is that can be applied any thinning algorithm, including those with suboptimal or unknown performance guarantees that often perform well in practical. In such cases, Rems. and still ensure that COMPRESS++ error is never much larger than that of the input algorithm. As an illustration, we apply COMPRESS++ to the popular quadratic-time kernel herding algorithm (Herd). Fig. shows that Herd-CoMPRESS++ matches or nearly matches the MMD) error of Herd in all experiments while also substantially reducing runtime. For example. Herd requires more than 11 hours to compress 250000 points in 100 dimensions, while Herd-CoMPRESSC
takes only 14 minutes (a 45x speed-up). Moreover, surprisingly, Herd- COMPRESS++ is consistently more accurate than the original kernel herding algorithm for lower dimensional problems. See Fig. 4 in App. G.1 for comparable results with mixture of Gaussian P..
Visualizing coresets For a 32-component mixture of Gaussians target, Fig. visualizes the core- sets produced by i.i.d. sampling. KT, kernel herding, and their COMPRESS+ variants. The COM- PRESS++ coresets closely resemble those of their input algorithms and, compared with i.i.d. sam- pling, yield visibly improved stratification across the mixture components.
8

---

Goodwin RW
Goodwin ADA-RW
Goodwin MALA
Goodwin PMALA
2-
2-
Mean MMD
2--
+-5
KT Gaap
XT Campl
KT-Compeeraa s
K1
Ioput
Toput size
Input
Input
Lotka-Volterra RW
Volteraol ADA-RW
Lotka-Volteraa MALA
Lotka-Volterre PMALA
Moan MMD
2--
KT-lorpp
2-
2-13
Input
Input size
Ingut size
Input size
Hinch RW1 1
Hinch RW 2
Tempered Hinch RW
Tempered Hinch RW 2
Moan MMD
2--
2-1
2
2.
Kr. Ail
2
Input size n
Iaput size n
Input size n
Input size
Figure Given MCMC sequences summarizing challenging differential equation posteriors P, KT- COMPRESS* consistently improves upon the MMD of standard thinning (ST) and matches or nearly matches the error of of its quadratic-time input algorithm KT.
Lid.
KT-Comp++
KT
Herd Comp++
Herd
20
10
0
-10
-20
20
10
0
-10
-20
-20
0
20
-20
20
-20
0
2.0
20
0
20
-0
0
20
Figure 3: Coresets of size 32 (top) or 64 (hottom) with equidensity contours of the target underlaid.
6 DISCUSSION AND CONCLUSIONS
We introduced a new general meta-procedure, COMPRESS++, for speeding up thinning algorithms while preserving their error guarantees up to factor of 4. When combined with the quadratic-time KT-SPLIT and kernel thinning algorithms of Dwivedi & Mackey (2021; 2022), the result is near- optimal distribution compression in near-linear time. Moreover, the same simple approach can be combined with any slow thinning algorithm to obtain comparable summaries in a fraction of the time. Two open questions recommend themselves for future investigation. First, why does Herd- COMPRESS++ improve upon the original kernel herding algorithm in lower dimensions, and can this improvement be extended to higher dimensions and to other algorithms? Second, is it possible to thin significantly faster than COMPRESS++ without significantly sacrificing approximation error? Lower bounds tracing out the computationallstati statissiicl trade-offs in distribution compression would provide a precise benchmark for optimality and point to any remaining opportunities for improvement.
9

---

REPRODUCIBILITY STATEMENT
See the goodpoints s Python package for Python implementations of all methods in this paper and
for code reproducing each experiment.
ACKNOWLEDGMENTS
We thank Carles Domingo-Enin Emrrich for alerting us that an outdated proof of Thm. 2 was previously included in the appendix. RD acknowledges the support by the National Science Foundation under Grant No. DMS-2023528 for the Foundations of Data Science Institute (FODSI). Part of this work was done when AS was interning at Microsoft Research New England.
REFERENCES
Christoph M Augustin, Aurel Neic, Manfred Liebmann, Anton Prassl, Steven A Niederer, Gundolf Haase, and Gernot Plank. Anatomically accurate high resolution modeling of human whole heart electromechanies: strongly scalable algebraic multigrid solver method for nonlincar deformation. Journal of computational physics, 305:622-646, 2016. (Cited on page 1.)
Alain Berlinet and Christine Thomas-Agnan Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011. (Cited on page 2.)
Boucheron, G. Lugosi, and P. Massart. Concentration Inqqualities: Nonasymptotic Theory of Indepen- dence. OUP Oxford, 2013. ISBN 9780199535255. URL https: /twooksoos////////// http://oooooooooo..oooooooo books? iddkoNggRluhPOC (Cited on pages 12, 15, and 19.)
Bernard Chazelle and Jiri Matousek. On linear-ting deterministic algorithms for optimization problems in fixed dimension. Journal of Algorithms, 21(3):579-59) 597, 1996. (Cited on page 2.)
Yutian Chen, Max Welling, and Alex Smola. Super-samples from kernel herding. In Proceedings the Twenty- Sixth Conference on Uncertainty Artificial Intelligence, UAI'10, 10, pp. 109 116, Arlington, Virginia, USA. 2010. AUAI Press. ISBN 9780974903965. (Cited on pages 2 and 7.)
Raaz Dwivedi Lester Mackey, Kernel thinning. arXiv preprint arXiv:2105.05844 2021. (Cited on pages 2, 3, 7, 9, 23, and 24.)
Raaz Dwivedi and Lester Mackey. Generalized kernel thinning. Representations, 2022. (Cited on pages 3. 7, 20, 21, and 22.)
In International Conference on Learning
Mark Girolami and Ben Calderhead. Riemann manifold Langevin and Hamiltonian Monte Carlo methods.
Journal of the Royal Statistical Suciety: Series B (Statistical Methodology). 73()):233321 2011. (Cited on page 23.)
Brian C Goodwin. Oscillatory behavior enzymatic control process. Advances in Enzyme Regulation, 3: 118-356, 1965. (Cited on page 7.)
Arthur Gretton, Karsten M. Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. kernel two-sample test. Journal of Machine Learning Research, 13(25):723-773 2012. (Cited on page 2.)
Heikki Haario, Eero Saksman, and Johanna Tamminen. Adaptive proposal distribution for random walk Metropolis algorithm. Computational Statistics, 14(3):355-33 -395, 1999. (Cited on page 23.)
Robert Hinch, JL Greenstein, AJ Tanskanen, L Xu, and RL Winslow. A simplified local control model of dalcium-induces calcium relcase in cardiac ventricular myocytes. Biophysical journal, 87(6):372333736, 2004. (Cited page 7.)
Been Kim, Rajiv Khanna, and Oluwasanmi O Koyejo. Examples not enough, learn to criticize! criticism for interpretability, Advances neural information processing systems, 29, 2016. (Cited page 2.)
Alfred James Lotka. Elements of physical biology. Williams & Wilkins, 1925, (Cited on page 7.)
Jiri Matousek. Approximations and optimal geometric divide-and-conquer. Journal of Computer and System Sciences, 50(2):003-008, 1995. (Cited page
10

---

Steven A Niederer. Lawrence Mitchell, Nicolas Smith, and Gernot Plank. Simulating human cardiac electro- physiology on clinical time-scales. Frontiers Physiology, 2:14, 2011. (Cited on page 1.)
Art B Owen. Statistically efficient thinning of Markov chain sampler. Journal of Computational and Graph- ical Statistics, 26(3).738-744 744, 2017. (Cited on page 1.)
Jeff M Phillips. Algorithms for s-approximations of terrains. In International Colloquium on Automata, Lan- guages, and Programming, pp. 447 458. Springer, 2008. (Cited on page 2.)
Jeft M Phillips and Wai Ming Tai. Near-optimal coresets of kernel density estimates. Discrete & Computational Geometry, 63(4)8867-877 2020. (Cited on page 2.)
Marina Riabiz, Wilson Chen, Jon Cockayne, Pawel Swietach, Steven Niederer, Lester Mackey, and Chris Oates. Optimal thinning of MCMC output. arXiv preprint arXiv:2005. 2020a. (Cited on pages and 23.)
Marina Riabiz, Wilson Chen, Jon Cockayne, Pawel Swietach, Steven Niederer, Lester Mackey, and Chris Oates. Replication Data for: Optimal Thinning of MCMC Output, 2020b. URL https://doi. org/10. org/10.7910 7910/DVD /DD///DDDVDA/// MDDNNMM. Accessed on Mar 23, 2021. (Cited on page 23.)
Christian P Robert and George Casella. Monte Carlo integration. In Monte Carlo statistical methods, pp-
71-138. Springer, 1999. (Cited on page 1.)
Gareth O Roberts and Richard L Tweedie, Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, 2(4):341-363 1996. (Cited on page 23.)
Marina Stroechi, Matthias AF Gsell, Christoph M Augustin, Orod Razeghi, Caroline Н Roney, Anton Prassl, Edward J Vigmond, Jonathan M Behar, Justin S 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 the pericardium. Journal of Biomechanics, 101:109645, 2020. (Cited on page 1.)
Ilya Tolstikhin, Bharath K Sriperumbudur, and Krikamol Muandet. Minimax estimation kemee mean em- beddings. The Journal of Machine Learning Research, 18(1):3002-3044 2017. (Cited on page 2.)
Joel Tropp. User-friendd]
bounds for sums random matrices. Foundations of Computational Mathe- matics, 12(4):389-42) 2012. doi: 10. 10.100//000000-00 1-9099-7. URL. https: /ooi wrgg/1.0.... 1007/ s 02000-2000000 011 1 9099-299922 z. (Cited on pages 15 and 18.)
Vito Volterra. Variazioni e fluttuazioni del numero d'individui specie animali conviventi. 1926. (Cited on page 7.)

---

APPENDIX
A Additional Definitions and Notation
12
B Proof of Thm. 1: Runtime and integration error of COMPRESS
13
Proof of Thm. 2: MMD guarantees COMPRESS
13
Proof of Thm. 3: Runtime and integration error of COMPRESS+
19
E Proof of Thm. 4: MMD guarantees for COMPRESS+
19
Proofs of Exs. 3,
20
G Supplementary Details for Experiments
22
H Streaming Version of COMPRESS
23
A ADDITIONAL DEFINITIONS AND NOTATION
This section provides additional definitions and notation used throughout the appendices. We associate with each algorithm ALG and input Sin the measure difference
(S A Pss.. P.... 1 E.e....
Dout ExESur 8.
(14)
that characterizes how well the output empirical distribution approximates the input. We will often write ΦALG instead of (S,) for brevity if Sin is clear from the context.
We also make of the following standard definition of sub-Gaussian random variable (see, e.g.. Boucheron et al., 2013, Sec. 2.3).
Definition 4 (Sub-Gaussian random variable) We say that random variable G is sub-Gaussiae with parameter v and write G E G(v)
B[exp(AG)] S exp
x3u² 2 for all A A R.
Given Def. 4, it follows that ALG E G5 for function f as in Def. 2 if and only if the random variable @sLa(f) P S I is sub-Gaussian with parameter v conditional on the input Sin-
In our proofs, often more convenient work with an unnormalized measure discrepancy
(SAL((Sa) A (ALO((S)) Exes 82
Aone EsuO 6r.
(15)
By definition (15), we have the following useful equivalence:
(f n (f)a(f) G(a = @sLa(f) E G(VALO) for GALG= VALG. (16)
The following standard lemma establishes that the sub-Gaussian property is closed under scaling and summation.
Lemma (Summation and scaling preserve sub-Gaussianity) Suppose G ((a,). Then, for all 8 E R. have B G E ((Br)). Furthermore, if G is F-measurable and G2 E ((72) given F. then G1 + G2 E @( oz))
12

---

Proof Fix any 3 R. Since G1 ((o1), for each R,
E(exp(A B- G.G]]] exp X((8)) so that 8G1 ((Br)) advertised.
2
Furthermore, if 11 is F-measurable and G2 E ((02) given F, then, for each À E R.
E exxp(> A (G1 + G2)) B[exp(A. G. + G2)] = E exp(A A Gi) E e(ex((> A G2) | F1]
S eepp
(2
E exp ( f(G2))
exp
exp 2
*²(of+03)
2
exp
so that G1 + G2 G( - as claimed.
B PROOF OF THM. 1: RUNTIME AND INTEGRATION ERROR OF COMPRESS
First, we bound the running time of COMPRESS. By definition, COMPRESS makes four recursive calls to COMPRESS on inputs of size n/4. Then, HALVE is run input of size 28+1 /n. Thus, re satisfies the recursion
re(n) 4rc rr((/7220
Since rc(49) = 0, we may unroll the recursion to find that
re(n) Ei 4'rn (20+ VnA-1).
claimed in (5).
Next, we bound the nub-Gaussian error for a fixed function f. In the measure discrepancy (15) notation of App. A we have
(S = Ei= vC(S)) + v22 (H()
(17)
where S and S are defined as Alg. Unrolling this recursion, we find that running COMPRESS on an input of size with oversampling parameter leads to applying HALVE on 4 coresets of size n, 20+1-1 / for S i < B,, Denoting these HALVE inputs by (S we have
Vc(S..)= /n2 - D Bn D 2 (H(!))) 1=0
8-1
(18)
Now define (n) = (n). Since tHe (H (ʃ) are oH(ns) sub-Gaussian given (S (S and (Sin (st )) Lem. implies that vho(S,)) (f) is ae sub- Gaussansiin given Sin for
(m) n4- 8- D. of (m:).
Recalling the relation (16) between and from App. A. conclude that
r2(n) = Σdn 4 (n.)
as claimed in (6).
C PROOF OF THM. 2: MMD GUARANTEES FOR COMPRESS
Our proof proceeds in several steps. To control the MMD (1), we will control the Hilbert norm of the measure discrepancy of COMPRESS (15), which first write weighted sum of measure discrepancies from different (conditionally independent) runs of HALVE. To effectively leverage the MMD tail bound assumption for this weighted sum, reduce the problem to establishing
13

---

concentration inequality for the operator norm of associated matrix. We carry this plan in four steps summarized below.
First, in App. C.I express the MMD associated with each HALVE measure discrepancy as the Euclidean norm of a suitable vector (Lem. 2). Second, in App. C.2 we define a matrix dilation control vector norms using matrix spectral norms (Lem. 3).
operator for vector that allows Third, in App. C.3 we prove and apply sub-Gaussian matrix Freedman concentration inequality (Lem. 4) control the MMD error for the COMPRESS output, which in requires to establish moment bounds for these matrices by leveraging tail bounds for the MMD error (Lem. 5). Finally, we put together the pieces in App. C.4 to complete the proof.
We now begin our formal argument. We will make use of the unrolled representation (17) for the COMPRESS measure discrepancy ( in terms of the HALVE inputs (S of size vi 20-1-* ni for 0 < k < log, n- 1. For brevity, we will use the shorthand t/c - (c(Sm)) Pk.j A ( and 1ोr (ST(Sc) hereafter.
C.I REDUCING MMD TO VECTOR EUCLIDEAN NORM
Number the elements of Sn as (Ii,...,,Ty Tn), define the n x n kernel matrix K (k(x;, 2y Ty)) and let K denote matrix square-root such that K K K (which exists since K is a positive semidefinite matrix for any kernel k). Next, let Skue denote the output sequence corresponding
tii (i.e., running HALVE on Sky and let {ei}== denote the canonical basis of I The next lemma (with proof in App. C.5) relates the Hilbert norms to Euclidean norms of carefully constructed vectors.
Lemma (MMD as a vector norm) Define the vectors
U. A k Ei= ex (()r))))))))))))) -2 (x: ESgy) and uc A log, n- Zi=0
ΣØ= uk.j (19)
where Wk.j
vn 20+ Then, we have
n² MMD Sc) |lucll2. and Bluksl(uw,'' j E 14 k)] -0 for k o,..., log, g-2,
(20)
(21)
and for j E [4h] are conditionally independent given (ur.y : [4 1,k' > k))
Applying (20), we effectively reduce the task of controlling the MMD errors controlling the Euclidean norm of suitably defined vectors. Next, we reduce the problem to controlling the spectral norm of suitable matrix.
C.2 REDUCING VECTOR EUCLIDEAN NORM TO MATRIX SPECTRAL NORM
To this end, we define a symmetric dilation matrix operator: given vector E R define the matrix M, as
M,
0 u
u² O
E 1)+(())++
(22)
Opxn
It is straightforward to see that + M,, is linear map. In addition, the matrix M,, also satisfies few important properties (established App. C.6) that we use our proofs.
Lemma 3 (Properties of the dilation operator) For any R", the matrix M,, (22) satisfies
|ulla (b) (M,), and M (c) 3 || for all E N.
|MMlllpp
(23)
Define the shorthand M A Man,jun, (defined in Lem. 2). Applying Lems. 2 and 3, we find that
n MMD Se) Juc
Xmaxx M Muc
Xmaa
logs n k=0
Σ/ MR.)).
(24)
where step (i) follows from the linearity of the dilation operator. Thus to control the MMD error, suffices control the maximum eigenvalue of the sum of matrices appearing in (24).
14

---

C.3 CONTROLLING THE SPECTRAL NORM VIA A SUB- BUB-GAUSIIA MATRIX FREEDMAN INEQUALITY
To control the maximum eigenvalue of the matrix M make use of (24) and the following sub- Gaussian generalization of the matrix Freedman inequality of Tropp (2012, Thm. 7.1). The proof of Lem. 4 can be found App. C.7. For two matrices A and B of the same size, we write A B if
B - A is positive semidefinite.
Lemma 4 (Sub-Gaussian matrix Freedman inequality) Consider sequence (Y,) N of self-
adjoint random matrices in R and a fixed sequence of scalars (Ri) satisfying
(B)
E | and E (Y) |= |
(1)RT, for all i [N] and g 2N. (25)
Define the variance parameter 0² 2 E R² Then.
P[Amax (E Y,) /8 log m]] Se for all t> 0,
and equivalently
Pl E Y,) S / Blo((m/6) 2 for all ò E (0,
To apply Lem. with the matrices MR.j. we need to establish the zero-mean and moment bound conditions for suitable R in (25).
C.3.1 VERIFYING THE ZERO MEAN CONDITION (A5) FOR Majj
To this end, first we note that the conditional independence and zero-mean property of will implies that the random vectors üj.j and the matrices MR.j also satisfy similar property, and in particular that
E Ma.5 (Merg : > k,j E [4411] -0 for jE [4 l E {0, (0.1....,,lo.. n
-1}.
(26)
C.3.2 ESTABLISHING MOMENT BOUND CONDITIONS (B5)(B) FOR MRj TERMS OF Rk.j VIA MMD TAIL BOUNDS FOR HALVE
To establish the moment bounds Maj. note that Lems. 2 and 3 imply that
M
M M
(23)
W ukj
L.+1
(20) w/,,
uk.j 112 I.+1
(27)
where Wkj was defined in Lem. 2. Thus it suffices to establish the moment bounds on || [|/- To this end, we first state lemma that converts tail bounds to moment bounds. See App. C.8 the proof inspired by Boucheron al. (2013, Thm. 2.3).
Lemma 5 (Tail bounds imply moment bounds) For non-negative random variable Z,
P|Z > sttuut for all t 2 0
2 < (2a+ for all E 2N.
To obtain a moment bound for | we first state some notation. For each n, define the quantities
a/ A nann 1/ nun
(28)
where an and vn the parameters such that HALVE Gu(an, vn) inputs of size n. Using argument similar to Lem. 2, we have
|uusl nky MMD S2. for nk. = Sky -
Thereby, using the Gk assumption HALVE implies that
Pilluesl12 2 d'g v'e, Vtl (u j [4 b)] S for all +2 20,
(29)
15

---

where
6 _ mej. /n220-1R
(30)
and, notably, =
= %. Combining the bound (29) with Lem. 5 yields that
Bllluw (urry J E 11 > b)] S (z)) + + )9,
(31)
for all 2N, where & is defined in (29). Now, putting together (27) and (31), and using the conditional independence of Ma.j. we obtain the following control on the q-th moments of M for q 2N:
E M (M K > k. E (1491)
(27) 3 why [|uusslll(uueer N k.je [1m1]]]
Ina1
(31)
3 whi (22dz + (())) I1t1
(2) R.j Int1 I where R & 2w ( + v/4))
(32)
where la is defined in (30). In summary, the computation above establishes the condition (B) from the display (25) for the matrices M& in terms of the sequence RR.j defined in (32).
C.4 PUTTING THE PIECES TOGETHER FOR PROVING THM. 2
Define
log, n g 2(a /72011 + (um2001)
(33)
Now, putting (26) and (32) together. we conclude that with a suitable ordering of
the indices (k. j), the assumptions of Lem. 4 are satisfied by the random matrices (MRj.J E [4*], k E (0, .o....,,og,," Vn22-1-k (29) is decreasing in k, Wk.i प (as defined in Lem. 2), and a' and vn (28) are assumed non-decreasing in n, we find that
1-1--11 1}) with the sequence (Ru.g)- Now, since l
n 2 (33) n² (log1 n (2(
vT2o+1 +
())2041))
(log, g) I (2(1/g + o/2z))
Ekeo
logg n- 1-1
(2(a's + v/( ))2
log, n g
Σ j=1 - (2(d4g + +1/% ))
k=U
Σ
log, n--------000
Σラ ビj=1 (2wk. (a + 1/2 ))²
k=0
32
k=0
log, n- g 8
2Ø=1
12
Finally, applying (24) and invoking Lem. 4 with nō and m n + 1, we conclude that
P[MMD(S Sc) 2 /. /S(lg(n + +))
(24) P(Amax Elor,
loz, a Ejt MR.) 2 nō /8 + + +
Se- for all t> 0.
which in turn implies
PMMM Sc) an + + S et for 0,
since the parameters Un. Cn (8) satisfy
Un (8) 4(ar,, vv. vv 2(log, n-g) (33) Gv8, and ān on V log(n+1) //8log(n + +
(8)
Comparing with Def. 3, Thm. 2 follows.
16

---

C.5 PROOF OF LEM. 2: MMD AS VECTOR NORM
Let U - Ei= 1 (k,)) - 2 E Sgut)
By the reproducing property of k have
1 (k) Eresp k(x, - 2-EE2zse Exsoo k(z, 1
Exrett WESt" k(x,,1) v) Exesgy DeSt,, k(x,y) v) + Exespy veSpy k(r, y) Kok, (19)
(34)
Using (18), (19), and (22), and mimicking the derivation above (34), we can also conclude that (1) || 11.
Additionally, we note that
MMDx(Sm. Sc) /upl]/[/==1 (f, (cckk) N4.
(k))()
Finally the conditional independence and zero mean property (21) follows from (18) by noting that conditioned on (S >>kkk21 the sets (Sk 522 are independent.
C.6 PROOF OF LEM. 3: PROPERTIES OF THE DILATION OPERATOR
For claim (a) in the display (23), we have
M
||u|2 2
( 1
In+1
M
(8i)
||u||2
0,
uu
where step (i) follows from the standard fact that un T = ||u|| I,, and step (ii) from the facts M [|u|ße for E the first canonical basis vector [g++1 and || l = | Claim (b) follows
directly by verifying that the vector v = [L, [ is an eigenvector of M,, with eigenvalue ||w]]2- Finally, claim (c) follows directly from the claim (a) and the fact that [M = M for all integers q 2
C.7 PROOF OF LEM. 4: SUB-GAUSSIAN MATRIX FREEDMAN INEQUALITY
We first note the following lemmas about the tail bounds and symmetrized moment generating functions (MGFs) for matrix valued random variables (see Apps. C.9 and C.10 respectively for the proofs of Lems. and 7).
Lemma (Sub-Gaussian matrix tail bounds) Let (X₂ E RRXm)
K21 be a sequence of self- 121 be sequence of determin- adjoint matrices adapted to a filtration Fk. and let (Ax E IRmm
istic self-adjoint matrices. Define the variance parameter o² Σx Aullog random variable independent of (Xx, Fk) we have
If. for Rademacher
log T. (ex((ex((2s0X FR 20 Ax for all 0
(35)
then we also have
TP Amax (Ex Xx) 21)] & me- for all t 12 0.
Lemma (Symmetrized sub-Gaussian matrix MGF) For a fixed sealar R. let X be self- adjoint matrix satisfying
EX and EX 1 RR) for q E 2N.
(36)
e a Rademacher random variable independent of X, then Eexp(2:0X) I exp((20 1221 for all 0 R.
17

---

The assumed conditions (25) allow apply Lem. 7 conditional on (Yi)sck along with the oper- ator monotonicity of log to find that
log E exp(= (II 20 R for all e R.
for Rademacher random variable e independent of (Y 12 Moreover, 1|Ex Aullop [> 1l = >n R o². Thus, applying Lem. 6, we find that [Amax(E, 2 4 I me -f//(6")) for all 0. As immediate consequence, we also find that
P[ Y,Y,) 2 ( log logm) S for all t t 0,
as claimed.
C.8 PROOF OF LEM. 5: TAIL BOUNDS IMPLY MOMENT BOUNDS
We begin by bounding the moments of the shifted random variable X = = a. Note that Z 0. so that 2 aa. Next, note that X x++ X_ where X= max (+x,+(XX00 and that X = + Furthermore, X a by the nonnegativity of P[X+ > u| = P(X u] PfZ + u| for any u > O, we apply the tail bounds on Z to control the moments of X In particular, we have
that |X|* & < a X For any u >> since
[[x
Lo 15-1p[X+ > uldu
(6) I (uvi) > vV di
(10) I qui S00h 13/2-1e- (in) (e))
where we have applied (i) integration by parts, (ii) the substitution vvl. and (iii) the assumed tail bound for Z.
Since Z X + a, the convexity of the function + 1 for q 2 1, and Jensen's inequality imply
that for each g E 2N, we have
EZ < (a" + (| < (2a" + EX < (2a)* - 2 10--299-900 (g) (2a)² - 2
900 129-1900 - 1)! < (2a + (
where the last step follows since 2² + 82 < (xr + 5) for all g N and y 0. The proof is now complete.
C.9 PROOF OF LEM. 6: SUB-GAUSSIAN MATRIX TAIL BOUNDS
The proof of this result is identical to that of Tropp (2012, Proof of Thm. 7.1) as the same steps justified under our weaker assumption (35). Specifically, applying the arguments from Tropp (2012, Proof of Thm. 7.1), we find that
E[tr exp(E [x+)] S E
exp mn-1 0X + log [(pp
(35) trexp
Σk= 0X, + +02 Am
S tr exp 20 Σn AA) S m exp (202
(37)
where step (i) follows by iterating the arguments over n- 1, ..... 1 and step (ii) from the standard fact that tr (ex))(AA) & m /el/(ex)))lll = m exp( llop) for an m X m self-adjoint matrix A. Next, applying the matrix Laplace transform method Tropp (2012, Prop. 3.1), for all > 0, we have P Amax EE Xx) 2 t) s infazo fo f--tt. E exp (xp( {X+)]
(37) s m infozuf e 0t 22020² = me - /80())
where the last step follows from the choice 0 . The proof is now complete.
18

---

C.10 PROOF OF LEM. 7: SYMMETRIZED SUB- GUB-GAUSIIAN MATRIX MGF
We have
E [2exX( I
Ex=1
2 q
22 (26)
16 X 2k
k=
(61)
22 E1R I (2k)!
I+ -k=1
((0)
(20 120² exp R&I),
2k=1
where step (i) uses the facts that (a) E[E*] = (q E 2N) and (b) X = BiEa E X since is
independent of X, step (ii) follows from the assumed condition (36), and step (iii) from the fact that 2" (2A))
(Boucheron et al., 2013, Proof of Thm. 2.1).
D PROOF OF THM. 3: RUNTIME AND INTEGRATION ERROR OF COMPRESS+
First, the runtime bound (9) follows directly by adding the runtime of COMPRESS HALVE, g) as given by (5) in Thm. and the runtime of THIN.
Recalling the notation (14) and (15) from App. A and noting the definition of the point sequences Se: and Sc++ in Alg. 2, we obtain the following relationship between the different discrepancy vectors:
(c(Smm) = Emes. 82 - 2a vn ExEse 6R.
Exescn 8er (T() 20/7 Exese 8s vn
and
(S EmnEs 8x to E.Ess... dx = =dc(Smm) + @T(S)).
Noting the g property of HALVE and applying Thm. 1, we find that (c(Sm))()) is sub-Gaussian with parameter ve(n) defined in (6). Furthermore, by assumption THIN, given Sc, the variable (T()))()) is ve( sub-Gaussian. The claim now follows directly from Lem. 1.
E
PROOF OF THM. 4: MMD GUARANTEES FOR COMPRESS+
Noting that MMD is metric, and applying triangle inequality, we have
(S Sc..)= S MMD Se) + MMD
Since ScH+ is the output of THIN(29) with Se the input, applying the MMD tail bound assump- tion (38) with |Sc| = /n2 substituted in place n, we find that
IP MMD Sc..) 2 d 20
Ao Se for all
0.
Recall that f,/2 2 VT. Next, we apply Thm. 2 with HALVE to conclude that
PMMMD Sc) 2 an + Jn v < Set for all t t2 0.
Thus, have
MMD Sc++) 2 de + ān (oh + Un) Tnl 2- for all t2 0,
which in turn implies that
(MDx Sc..) 2 d'c./2 + an + (Ve,,12 + Un) Vog + (V'_, + TWnVl se- for all
t 12 0,
thereby yielding the claimed result.
19

---

F PROOFS OF EXS. 3, 4, 5, AND 6
We begin by defining the notions of uub-Gaussianity and Suub-aaassianity on an event.
Definition (Sub-Gaussian on an event) We say that a random variable G is sub-Gaussian on an event & with parameter a if
B exp(A G)) s expl (x2) for all AER.
Definition 6 (k-sub-Gaussian on event) For kernel k, we call a thinning algorithm ALG k- sub-Gaussian on an event & with parameter v and shift a if
P(E, M SALa) 2 on + unvt Sull Set for all
t t 0.
(38)
We will also make regular of the unrolled representation (17) for the COMPRESS measure dis- crepancy (S() in terms of the HALVE inputs (S)), jE(AM) of size
n1 28+1-1 Vn for 0 S k S Bn.
(39)
For brevity, we will use the shorthand v/c (S vh A ('H(S).))) and vi 2 xvT(Sc) hereafter.
F.1 PROOF OF Ex. 3: KT-SPLIT-COMPRESS
1 For HALVE = KT-SPLIT( 240+" 8) when applied to an input of size f, the proof of Thm. 1 in Dwivedi & Mackey (2022) identifies sequence of events Ex.j and random signed measures vhk.j such that, for each 0 < k < 8n, j [4*] and with [If | = 1,
(a) P( 249 [1,+1)
+1)
1 [[E 1 1b and
(c) vx is ny uH(nn) sub- GoosGaussian (7) given ("wr)) and (Wer))
where step (ii) follows from substituting the definition ny 28+1-k Vri (39). To establish step (ii) in property (a),
n the definition' of KT-SPLIT( (.. 0) for an input of size ng, which nhe 415 6 in the notation of Dwivedi & Mackey (2022). The proof of Thm. implies that n4o
in Dwivedi & Mackey (2022) then implies that
PI < 22 8;
(1a+T)
(1.+1))
Hence, on the event & NR. Ekej these properties hold simultaneously for all HALVE calls made by COMPRESS, and, by the union bound,
P|E < Ede P < Exe
P(
k== 2 24.
(40)
Now fix any ff with || 1. We invoke the measure discrepancy representation (17), the equiva- Ience of Why and Wh.y 8, the nonnegativity of the exponential, and Lem. 1 in turn find
[[1[E] exp(A dc(()) = [[] exp(A [ve(f))]
[[ exp(A n 7 k= Σ Ej=1 2- 2 (f))
|[|[E| exp(A /n2 Ah
k=0 1= 2 k Sh. (f))
S EF(exp(A 1 8-1 9 D/"
2 (h.
S <exp( X22((n) for vn(n) = Ede 4 4
so that Φc( is ve sub-Gaussian E.
20

---

F.2 PROOF OF Ex. 4: KT- CTTCPOSSESS
For HALVE = symmetrized KT (10 (p.+ when applied to an input of size l, the proof' of Thms. 1-4 in Dwivedi & Mackey (2022) identify sequence of events Exj and random signed measures Uk.y such that, for each 0 I k S 8n, and [4*]
(a) P(EE, S 2 +=]
(b) 1E = 1 1
(c) Pl Ii (k)llk 2 ane una Vt
S Se- for all f 2 0, and
(d) E [bx (k) (whee 221. (Wey)) )y )5 0,
where ny 2 vn was defined in (39). We derive property (a) exactly as in App. F.1. Hence, on the event & = Nk.J Ex.j. these properties hold simultaneously for all HALVE calls made by COMPRESS, and, by the union bound (40), P[E?] 2-
Furthermore, may invoke the measure discrepancy representation (17), the equivalence of wH and dk.s on E, the nonnegativity of the exponential, and the proof of Thm. 2 in turn to find PEEE, MMD Sc) 2 ān on Vl Sm] PlE, [ll/c(k)]l k 2 an o Vl Sin]
= | 1 8-1 Ex=u Σ/ و (k) 2 a. + in Vn Smm
8n
s P 1V22 8-1 E k= Σラ 2 . (k) 2 ān + E.vE | Smal S e for all t t20 0,
so that COMPRESS is k-sub-Gaussian & with parameters (ū, ā).
F.3 PROOF OF Ex. 5: KT-SPLIT- CASSPLIT-COMPRSSSHE
For THIN KT-SPLIT 6+25(0, +1) 5) and HALVE KT-SPLIT( Tn20 +2900 when applied to an input of size the proof of Thm. in Dwivedi & Mackey (2022) identifies sequence of events
Ek. and & and random signed measures v and oT such that, for each Br. [4"]. and f with ||/|| 1,
(181)
6 and P[E (a) P 1 S 4n20 4n20 (8.2 +1)) (B,
2
2a
8
8+20 -1)
18 1/ and [(TT [T and
(c) (nr (f) is ny (nn)) sub- sub-Gaussian (12) given (Nh i ))s)) and ( and wr f/r PT( (z) sub-Gaussian (12) given Sc-
Here, step (i) and (ii) follow exactly as in steps (i) and (ii) of property (a) in App. F.I. For step (iii,, we use the definition! of KT-SPLIT( (9. +1) for an input of size 2 2 which implies that
(120 (2. +1)] 5 in the notation of Dwivedi & Mackey (2022). The proof of Thm. I in Dwivedi & Mackey (2022) then implies that
P(E S Ei= 2 Ee
Vnn 5; = -E=
2 20 /
8
Vn2
g+20
+1)
8-20 +1j 2
claimed.
Hence, on the event & Nke Ek.j O Er, these properties hold simultaneously for all HALVE calls made by COMPRESS, and, repeating an argument similar to the union bound (40),
B P[6 < P( Eı Σラ 1 (+2
Bn k=
29
(41)
1h (00+2
Moreover, since oct+ = | (w' + MT). Lem. and the argument of App. F.1 together imply that Φc()) is vc++ aub-Gaussian on for each with || 1.
21

---

F.4 PROOF OF Ex. 6: KT- CT-CREPRSSS++
In the notation of Ex. 2, define
ar, = Vridi./2 = Ca Cav / o0: and
L T Vr, = Vnu'e, Co Co //lk///oo log(
6(n v7 Bl) S.....
Since HALVE
symmetrized KT (3, 6) for inputs of size and THIN
12
R KT (+20 +1J 6). the proofs of Thms. 1-4 in Dwivedi & Mackey (2022) identify a sequence of events Ex, and & and random signed measures vix. and vi such that, for each 0 S I 3n and j E [1%)
2 (a) PE 5 4 (8,, +1)]
5 and P[Eç! 91 &
1 [ w = 1 16 and 1(ET|UT [8T
(c)
mi Ilve. (k) 2 Ons + Una Vl (#w)))se)) (Verr) S e and
P (k)(kl dew/12 + th V2, Sc] -t for all / 0, and
E 1 (k) (1b2e )) (e
We derive property (a) exactly in App. F.3. Hence, on the event NR.S Enii O Er, these properties hold simultancously for all HALVE calls made by COMPRESS and
(H((e)) = (5) = C. v |k 6(n-vn(20 M....
Moreover, by the union bound (41), P[ <
Finally, since oc++ (th + t/r) and the argument of App. F.2 implies that COMPRESS is k- sub-Gand uub-Gaussian on with parameters (Ü, ä), the triangle inequality implies that COMPRESS+* k-sub-Gaussian on & with parameters (Ū, â) as in App. E.
G SUPPLEMENTARY DETAILS FOR EXPERIMENTS
In this section, we provide supplementary experiment details deferred from Sec. 5, well some additional results.
In the legend of each MMD plot, we display empirical rate of decay. In all experiments involving kernel thinning. we set the algorithm failure probability parameter = and compare KT(()) to COMPRESS and COMPRESS++ with HALVE and THIN set as in Exs. and respectively.
G.1 MIXTURE OF GAUSSIAN TARGET DETAILS AND MMD PLOTS
For the target used for coreset visualization in Fig. 3, the mean locations are on two concentric circles of radii and 20, and are given by
sin(j)] cos(s) where a, 10 1(j < 16) 20 1(j 16) for 1.2.....5 .32.
M4 =
Here also provide additional results with mixture of Gaussian targets given by P M E N(uj. I2) for M E (4, 6, 8). The mean locations for these are given by
M
A1 3| 3
A22 [-3,3] As [-3, - f4 -3
AG 0, T]. n4 -
μ7 TT. Pg = 10,
Fig. 4 plots the MMD emrors of KT and herding experiments for the mixture of Gaussians targets with 4, 6 and 8 centers, and notice again that COMPRESS++ provides a competitive performance to the original algorithm, in fact suprisingly, improves upon herding.
22

---

M=4
M=6
M
2
2-3
2-3
Mean MMD
Commm 4444
Comup 9-145
2-2
KT Comp---+
152
2-9
KT +:n
4.51
KI Comp++:
351
4
4
4"
4"
4'
4"
Input size n
Input size n
Input size
M=4
M=6
M=
Mean MMD
4
Herd Comp: a
Herd Comp: a
Herd Comp: a g
Herd Coer--oom-++rr
Herd Compe
Herd Compo+:
Hord 2-0.0
Herd: a
Hard a
4
4
4' Input size
Input size
Input size
Figure 4: For M Mccomponent mixture of Gaussian targets, KT-COMPRESS++ and Berd-CoMPRESS++ im- prove upon the MMD of i.dd sampling (ST) and closely track or improve upon the enror of their quadratic-time input algorithms, KT and kernel herding (Herd). See App. G.I for details.
G.2 DETAILS OF MCMC TARGETS
Our set-up for the MCMC experiments is identical to that of Dwivedi & Mackey (2021, Sec. 6). except that we use all post-burn-in points to generate our Goodwin and Lotka- Volterra input point sequences Snn instead of only the odd indices. In particular, we use the MCMC output of Riabiz al. (2020b) described in (Riabiz et al., 2020a, Sec. 4) and perform thinning experiments after discarding the burn-in points. To generate an input S., of size n for a thinning algorithm, we downsample the post-burn-in points using standard thinning. For Hinch, we additionally do coordinate- wise normalization by subtracting the sample mean and dividing by sample standard deviation of the post-burn-in-points
In Sec. 5, RW and ADA-RW respectively refer to Gaussian random walk and adaptive Gaussian random walk Metropolis algorithms (Haario et al., 1999) and MALA and pMALA respectively refer to the Metropoliss-djjssee Langevin algorithm (Roberts & Tweedie, 1996) and pre-conditioned MALA (Girolami & Calderhead, 2011). For Hinch experiments, RW and RW refer to two independent runs of Gaussian random walk, and "Tempered" denotes the runs targeting a tempered Hinch posterior. For more details on the set-up, refer the reader to Dwivedi & Mackey (2021, Sec. 6.3, App. J.2).
H STREAMING VERSION OF COMPRESS
COMPRESS can be efficiently implemented in a streaming fashion (Alg. 3) by viewing the recursive steps in Alg. as different levels of processing, with the bottom level denoting the input points and the top level denoting the output points. The streaming variant of the algorithm efficiently maintains memory at several levels and processes inputs in batches of size 40-1, At any level (with O denoting the level the input points), whenever there are 2'40+1 points, the algorithm runs HALVE on the points in this level, appends the output of size 2 to the points level i+1, and empties the memory at level i (and thereby level never stores more than 2 4-4+1 points). In this fashion, just 4 +1 points, the highest level is l - 1, which contains compressed coreset of size 2 1 = p+++++120 29 /n28 (outputted by running HALVE at level & for the first time), which is the desired size for the output of COMPRESS.
after processing
23

---

Algorithm 3: COMPRESS (Streaming) Outputs stream of coresets of size 2 v 4 and &s
Input: halving algorithm HALVE, oversampling parameter stream of input points 21, 02, Initialize empty level 0 coreset
So - 0 for = 1, l,.,..., do
1.40+1 Sn <- So u (z,) (zz) 1-10)))))))000000
// Process input in batches of size 4
i - 4' for j N then
Initialize level j coreset after processing 4i+0+1 input points
end
for
i 0. [log, {] + 1 do [ 21 then
if
S - (S.)E(S.)
// Halve level coreset to size 2/-1 // Update level + coreset: has size f1,2,3, ---22-1-0-1 Empty coreset level
1 S411 US 6 0
end
end
if == 4 for j N then
output SJ+1
I| Coreset of size /n22 with 140+1 and = for E
end
end
Our next result analyzes the space complexity of the streaming variant (Alg. 3) of COMPRESS. The intuition for gains memory requirements is very similar to that for running time, as we now maintain (and run HALVE) on subsets of points with size much smaller than the input sequence. We count the number of data points stored as our measure of memory.
Proposition 1 (COMPReSS Streaming Memory Bound) Let HAIVE store su(n) data points on inputs of size Then, after completing iteration the streaming implementation of COMPRESS (Alg. 3) has used at most sc(t) = 49+3 Vt+ sH(2 vt) data points of memory.
Proof At time t, we would like to estimate the space usage of the algorithm. the ith level of memory, we can have at most 26+240 data points. Since we are maintaining a data set of size at most /ē4a at time t, there are at most log levels. Thus, the maximum number of points stored at time t bounded by
0.5 t < 40+3 > Zimo
Furthermore, at any time up to time I, we have run HALVE on a point sequence of size at most Vē20+1 which requires storing at most sn( (V22++1) additional points.
Example 7 (KT-COMPRESS and KT-COMPRESS++) First consider the streaming variant of COMPRESS with HALVE symmetrized KT وكーس; for HALVE inputs of size as Ex. 4. Since (n) < n (Dwivedi & Mackey, 2021, Sec. 3), Prop. I implies that sc(n) - 48+4 Vn.
Next consider COMPRESS++ with the streaming variant of COMPRESS, with HALVE symmetrized KT 27 when applied to an input of size E, and THIN = KT( 2 8) as in Ex. The space complexity (n) = sc(n) +KKT((n) 4 /n + b, S 40+5 Vn. Setting g as Ex. 6, we get (n) = O0 n))
24


Reviews:
[{"review_id": "_kUulIC_LP", "reviewer": "Reviewer_aMbB", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The strength of the paper is obvious: it gives a substantial improvement in the running time for a natural and important problem.\n\nThe main new idea is very simple. One could even say obvious. In my opinion it's only obvious in hindsight, or obvious to experts in fine-grained complexity (a subfield of theoretical computer science where one tries to classify problems into linear vs quadratic vs cubic, etc.). Therefore, I think this paper is valuable to the broader community.", "summary_of_the_paper": "This paper gives a meta algorithm for speeding up coreset constructing algorithms for the distribution compression problem.\n\nThe benefit of this meta algorithm is that its running time is faster by a square-root factor (e.g. quadratic to linear) while keeping the error rate roughly the same: only a factor of 4 worse.\n\nThe method is very simple: split the input into four pieces of size n/4 each, recursively solve each of them, then combine all four answers into a set and take a coreset of this set.\n\nThe speed-up in running time is immediate (just because of how recursive formulas work) and the error bounds are also rather clear.", "summary_of_the_review": "While simple in hindsight, I think the new idea of this paper deserves being published in this venue.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "O4i69GJNNKC", "reviewer": "Reviewer_hLMP", "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": "The paper introduces a new framework to improve on runtime of existing thinning procedures. The framework is quite simple and analysis is quite straight forward (except error analysis using Sub-Gamma) . Eventhough the framework is simple, it helps improve the runtime of existing thinning algorithms (from magnitude of days to hours). The runtime improvements are only pronounced for higher input size (10^3) (not sure if mentioned applications have such high sample size requirements).\n", "summary_of_the_paper": "The paper introduces meta algorithms \"Compress\" and \"Compress++\" that take existing thinning algorithm as a subroutine and improves on their runtime while incurring marginally more error. \n\nThe algorithm \"Compress\" runs in recursive fashion: divides input set into four parts, runs Compress on each part independently, combines the resulting sets and halves the combined set using \"HALVE\" algorithm. As an example, the authors demonstrate that one can use KT-SPLIT as HALVE algorithm and get faster runtimes to compress albeit suffering extra error (upto log factors). Compress ensures that KT-SPLIT runs on sets of much smaller size.\n\n They build on Compress to obtain better error rates while sacrificing on runtimes (upto log factors). For this, they use the thinning algorithm on much smaller set obtained after running Compress. The runtimes are quite easy to derive based on recursion of algorithms. They use sub-gamma property to prove the error guarantees of the algorithms. They demonstrate the faster runtimes of their algorithms using high dimensional Monte Carlo samples.", "summary_of_the_review": "Even though the framework and analysis is simple, I believe community can benefit from these faster thinning meta algorithms. I am not sure how well \"distribution compression\" fits ICLR. ", "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": {}}, {"review_id": "KmGXTHIlMlF", "reviewer": "Reviewer_FqWv", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "I believe the paper makes a good contribution to the field by proposing a general reduction scheme that improves the runtime of existing algorithms at cost of minimal increase in error.\nThe underlying idea is clear and simple (in hindsight), which adds to the strength of the contribution. Thus I recommend accept. I have following suggestions/comments, and look forward to hearing back from authors.\n\n## Major Remarks\n\n1. I think the proof sketch of MMD guarantees should be added to the main text because I found this result to be more fundamental than Theorem 1, which focuses on a single $f$. \n\n\t+ I also found the full proof of Theorem 2 (in Appendix) difficult to follow. It would be helpful to the reader if additional details are provided. For example, how is the $\\lambda_{max}$ related to $\\||\\psi_{CP}\\||\\_k$, how does one get $u_{\\tilde{\\psi}_k,j}$? etc.\n\n2. (Page 7, fourth line) why one should not use RecHalve directly? \n3. (Example 1) What is the main difference between the recursion-based reduction proposed in this paper and the recursion-based thinning (KT-SPLIT) of Dwivedi and Mackey?\n\n## Minor Remarks\n\n1. I believe the clarity and presentation of the paper can be significantly improved by fixing the following: grammatical issues, omitted words, defining concepts *before* using them in text. I suggest the paper should be proofread carefully to improve the clarity. I am listing a subset of errors that I found: \n\t+ (appendix) $ell$ in the text before Lemma 3. \n\t+ (abstract) The sentence containing \"quadratic-time input\" did not parse for me.\n\t+ Some expressions that were used before defining them:  KT (\"Our contributions\"), 2-thinning  (\"Overview of Compress++\"), $\\sigma^2,c,r_{CP}$ (Page 3, last line)\n\t+ KT should be KT-SPLIT in last line of Example 1?\n\t+ space is missing between several words, for example, \"simpleyet\" (page 6).\n\t+ $\\Gamma_+^{\\mathcal F}$ instead of $\\Gamma_+^{\\mathcal f}$ at several places.\n\t+ Theorem 4 statement: \"is\" \n\t\n\n2.  Please add citation for the claim of $\\Omega(n^{-1/4})$ error in the second paragraph on Page 1.\n\n3. Page 3, Line 1: I suggest changing \"closed under multiplication\" to \"closed under scaling\".\n\n4. At several points, the paper uses that $\\sigma(\\cdot)$ and $c(\\cdot)$ are monotonic. It is explicitly mentioned for one calculation (Remark 1)  but not everywhere. Either it should be mentioned everywhere or change the definition to include monotonicity.\n\n5. (Section 3, 1st paragraph) What does \"significantly improved error rate\" mean?\n\n\n----\nUpdate: I thank the authors for their response. I am satisfied with the response and continue to recommend accept.\n", "summary_of_the_paper": "The topic of the study is distribution-compression/thinning algorithms for Monte-Carlo estimation of functions in RKHS, i.e., given a set of $n$ points, such that uniform distribution on these n points approximates an underlying distribution (with respect to integration over functions in a RKHS) with a certain error, output a set of $m$ points $(m \\ll n)$ that has a similar error.\nThe paper proposes three reductions/meta-algorithms to speed up existing distribution-compression algorithms while maintaining the error guarantee of the original algorithms.\nThe main result is that the proposed reduction improves the runtime of existing algorithms (with quadratic runtime or more) by a quadratic factor without increasing the corresponding error by a polylog factor.", "summary_of_the_review": "As mentioned earlier, the paper makes a good contribution and thus I recommend acceptance.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a simple meta algorithm to speed up data thinning algorithms with good theoretical guarantees. The method is both theoretically interesting and useful for practical applications.
Decision: Accept (Poster)