Low-Rank Thinning
Authors: Annabelle Michael Carrell
Albert Gong
Abhishek Shetty
Raaz Dwivedi
Lester Mackey
Venue: ICML 2025 poster (2025)
Keywords: sub-gaussian
thinning
distribution compression
kernel maximum mean discrepancy
low-rank
fast attention
sgd reordering
deep hypothesis testing
Primary area: theory->probabilistic_methods
TL;DR: New low-rank analysis of thinning algorithms enables applications to fast attention, stochastic gradient reordering, and testing with deep kernels.

Abstract: The goal in thinning is to summarize a dataset using a small set of representative points. Remarkably, sub-Gaussian thinning algorithms like Kernel Halving and Compress can match the quality of uniform subsampling while substantially reducing the number of summary points. However, existing guarantees cover only a restricted range of distributions and kernel-based quality measures and suffer from pessimistic dimension dependence. To address these deficiencies, we introduce a new low-rank analysis of sub-Gaussian thinning that applies to any distribution and any kernel, guaranteeing high-quality compression whenever the kernel or data matrix is approximately low-rank. To demonstrate the broad applicability of the techniques, we design practical sub-Gaussian thinning approaches that improve upon the best known guarantees for approximating attention in transformers, accelerating stochastic gradient training through reordering, and distinguishing distributions in near-linear time.

Low-Rank Thinning
Annabelle Michael Carrell Albert Gong?
Abhishek Shetty?
Raaz Dwivedi?
2 Lester Mackey
Abstract
Harvey & Samadi, 2014; Phillips & Tai, 2020; Alweiss et al., 2021; Dwivedi & Mackey, 2024; 2022; Shetty al., 2022; Li et al., 2024). We introduce new analysis for sub- uub-Gaussian thinning algorithms that applies to any kernel and shows that one can efficiently identify a better-than- uniform set of representative points whenever the kernel or data matrix is nearly low-rank. This opens the door to a va- riety of impactful applications including approximate dot- product attention in transformers, accelerating model train- ing through gradient reordering, and distinguishing distri- butions with deep kernels in near-linear time.
The goal in thinning is to summarize dataset using a small set of representative points. Re- markably, sub-Gaussian thinning algorithms like Kernel Halving and Compress can match the quality uniform subsampling while substan- tially reducing the number of summary points. However, existing guarantees cover only a re- stricted range of distributions and kernel-based quality measures and suffer from pessimistic di- mension dependence. To address these deficien- cies, we introduce a new low-rank analysis of sub-Gaussian thinning that applies to any distri- bution and any kernel, guaranteeing high-quality compression whenever the kernel or data ma- trix is approximately low-rank. To demonstrate the broad applicability of the techniques, we de- sign practical Sab--aussiin thinning approaches that improve upon the best known guarantees for approximating attention in transformers, ac- celerating stochastic gradient training through reordering, and distinguishing distributions in near-linear time.
In Sec. 2, we introduce our formal definition of thinning, two kernel-based measures of thinning quality, and a suite of candidate thinning algorithms. Sec. 3 presents our main theorem relating thinning quality low-rank properties of dataset and its induced kemnel matrix. In Sec. 4, trans- late the problem of approximating attention into thinning problem and develop practical solution, Thinformer, with state-of of-the-art quality guarantees. In Sec. 5, we develop a thinned stochastic gradient reordering rule that provably accelerates training and bridges the theory-practeo gaps left open by prior work. Finally, in Sec. derive new and improved power guarantees for practical thinned hy- pothesis tests that distinguish distributions in near-linear time. Each section also includes its own discussion of re- lated work.
1. Introduction
This work is about thinning, finding a small set of repre- sentative points accurately summarize larger dataset. Here, we use the term "dataset" liberally to refer to any collection of points, be they experimental observations (as in Sec. 6), stochastic gradients (as in Sec. 5), or vey-value pairs (as in Sec. 4). State-of-the-art thinning techniques provably improve upon uniform subsampling but only for restricted classes of kernel-based quality measures and with pessimistic dependence on the data dimension (see, e.g.,
Notation. For each n E N and a.b E R. we define [n] A {1...., ......,7) n), anb A min(a, b), and avb & max(a, b). We let ||A | and ||A respectively repre- sent the maximum singular value, absolute entry, and row Euclidean norm of matrix A and let (K.) denote the r- th largest eigenvalue of a suitable matrix K. We also define the Fuclidean norm balls Bm - {u E R ||al22 S 1} and BRT(R) A BB for each m E N and R > 0. For an event & and an integrable random variable X, we de- fine Ex[X] e E[X 1[]]]. We write an I Ö(b,) mean an bn polylog(n).
'University of Cambridge "Comell Tech 'MIT *Microsoft Research New England. Correspondence to: Annabelle Carrell <<c2411 122411100 @ @cam.ac.uk>, Albert Gong leroon@@c..cornel..oom Abhishek Shetty <ashetty 1995 @assaimallmmsss Dwivedi <dwivedi @connell.du...
Raaz Lester Mackey
2. Sub-Gaussian Thinning
<lmackey microsoft.com...
We begin with a formal definition of our problem set- ting. Consider a fixed collection of nin input points Xn belonging a potentially larger universe of datapoints
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Low-Rank Thinning
Table I: Examples of (K, v, --suub-Gausiia thinning algorithms. For input size Tin output size nour 2 Tins and
K
maa = we report each sub-Gaussian parameter v and runtime up to constants independent of (Ran: Routs 6, K).
SUBSAMPLING Prop. B.I
KH
KH- (H-COMPRESS(O)
GS-THIN GS-COMPRESS Prop. B.6
Algorithm
Prop, B.2
Prop. B.
Prop. B.10
Sub-Gaussian
log( ())
(Xour) (ouus) (nous /8)
log
parameter
nout
Nout
Poout
Nout
Nouu
Runtime
nout
out
2
n
out
X A (EI....,TT?) The aim of thimning algorithm is to select You points from Xn that together accurately sum- marize Xin. This is formalized by the following definition.
Notably, when the input points lie in Rd and k x)) is the linear kernel (ar; By) (so that K XXT), MMD measures the Euclidean discrepancy in datapoint means be- tween the input and output distributions:
Definition (Thinning algorithms). A thinning algorithm ALG lakes imput Xin and returns a possibly random subset Nout of size Nout- We denote the input and out- put empirical distributions by IPin - 1 ELEx., 8æ and Pun A 1. Emex.. 6n and define the induced probability vectors Pmn: Poua E An over the indices [n] by
MMD Pon)
|X Pm
X Pour
A common strategy for bounding the error of a thinning algorithm is establish its sub-Gaussianity.
Definition 3 (Sub-Gaussian thinning algorithm). We write ALG E Gu.o and say ALG is (K, v, 6)-sub- Gaussian, if ALG is a thinning algorithm, K is a symmetric positive semidefinite (SPSD) matrix, v >
Pin.i
E[x] and Pout, Vin
1 1/0, Krne)
for all E [m].
Thoa
When X C. Rd. use X [x1..... xn Baxd
[0, 1), and there exists event & with probability at least - 5/2 such that, the input and output probubility vectors satisfy
denote the input point matrix so that
E En [x] = X Pmn and
EusFan [x]] = X Pour
Eg [exep((u, K(P.. -Pa)))) S exp ( Ku), Yu E R".
We will make use of two common measures of summa- rization quality.
Here, the sub- Sab-Gaussian parameter controls the summa- rization quality of the thinning algorithm, and from Tab. that a variety of practical thinning algorithms are (K, v, -uu--Gaaaasssa for varying levels of
Definition 2 (Kernel MMD and max seminorm). Given two distributions f. and a reproducing kernel (Stein- wart & Christmann, 2008, Def. 4.18), the associated ker- nel maximum mean discrepancy (MMD) is the worst-case difference in means for functions in the unit ball By of the associated reproducing kernel Hilbert space:
2.1. Examples of sub-Gaussian thinning algorithms
Perhaps the simplest sub-Gaussian thinning algorithm is uniform subsampling: by Prop. B.1, selecting Vlour points from Xi uniformly at random (without replacement) is (K, vg (D--sub-Gaussin with = ||| / Un- fortunately, uniform subsampling suffers from relatively poor summarization quality. As we prove in App. B.1.1, its root-mean-squant squared MMD and KMS are both 2211 /oou) meaning that nout = 10000 points are needed to achieve 1% relative error.
MMD (i) A Sup [Z== Be-af(x))
When l Pi and jı Pout as in Def. and K & ax)2,,,,))E j=.j E Raxx denotes the induced kernel ma- trix, then the MMD can be expressed a Mahalanobis distance between Pin and Pout
Proposition 1 (Quality of uniform subsampling). For any I S [n], uniformly subsampled thinning satisfies
MMD (TP in Poa)
/ (Pm Poul)
'(Ppn Pou.)
A MMDK (Pm. Pow).
MMM (Pm. PoaD) E
Bie
Ck
and
For any indices C [n]] we further define the kernel max seminorm (KMS)
noat The
K(p Pan)) 1
I Mia-Hue noat
max,Ez CKeee,
Me
K ([pm Poun) llz - maxier le K(pn - Po (1)
for any SPSD K with CK A En Pmn, Km, P Kpn
2

---

Low-Rank Thinning
Fortunately, uniform subsampling is not the only sub- Gaussian thinning algorithm available. For example, the Kernel Halving (KH(ō)) algorithm of Dwivedi & Mackey (2024) provides a substantially smaller Sub-Gaussian pa- rameter, V = O( V (ogg / (oun)) in n time by select- ing one out of every two points and biasing selection toward the point that yields smaller approximation error. Similarly, the (H--CO)PRES)()) algorithm of Shetty et al. (2022, Ex. 3) delivers = Ol O(Vlog (og() log (ooaa only now time by halving and concatenating coresets of geometrically increasing size until the target output size is met. We derive simplified versions of these algorithms with identical sub-Gaussian constants in Apps. B.2 and B.5 and a linear-kernel variant (L) with und runtime in App. B.3, To round out our set of examples, we show in App. B.6.1 that two new thinning algorithms based on the Sram-SSh walk of Bansal et al. (2018) yield even smaller v at the cost of increased runtime. We call these algorithms Gram-Schmidt Thinning (GS-THIN) and GS- COMPRESS.
algorithms of Tab. 1 all enjoy (f v /lg ((z)) /nout) KMS, significant improvement over the 52(1 2 /lom) KMS of uniform subsampling. The bound (3) follows from the sub-Gaussianity of the thinning algorithm (Def. 3) and the union bound over the for each i E I.
For datapoints in R.. Thm. also provides a refined O log( Lz)) bound (4) on KMS. For bounded data, this trades an explicit dependence on the number of query points [I] for rank factor that is never larger (and sometimes significantly smaller) than d. This refinement follows from a more elaborate chaining argu- ment that frames (e: ((p - Powz))ez as a Gaussan process (Lem. C.5) and uses the Lipschitzness of K to con- trol its entropy integral. We will make use of these results when approximating dot-product attention in Sec. 4.
in
Notably, Thm. 3.1 of Phillips & Tai (2020) implies that any thinning algorithm must incur at least 22 (2(d/ KMS error for some dataset in R and many common kernels. Meanwhile, our Tab. and Thm. I imply that GS-THIN has V/ = (11/nau) and hence KMS ((Vd/nouu) Taken together, these results imply that no algorithm can have sub-Gaussian constant v = o(1/nmul and that GS-THIN enjoys minimax rate-optimal KMS and minimax rate- optimal uub-Gaussian constant.
3. Low-rank Sub-Gaussian Thinning
One might hope that the improved sub-Gaussiaa constants of Tab. would also translate into improved quality met- rics. Our main result, proved in App. C, shows that this is indeed the case whenever the inputs are approximately low-rank.
Finally, Thm. I provides an O(uVF+ + / / high- probability bound on kernel MMD, where the approximate rank parameter r can be freely optimized. We establish this result by projecting K' k1/3(pm. - Poot) onto the first r eigen- vectors of K, bounding the residual error in terms of Xr+1, and bounding the projection magnitude with high probabil- ity using the sub-Gaussianity of ALG and a union bound over a finite cover of a Euclidean ball in RT.
Theorem (Low-rank sub-Gaussian thinning). Fix any 8' E 10, r S n, and I C [n]. If ALG E Gu. (K), then the following bounds hold individually with probability at least 1 - 5/2- 8':
MMD (mn Pou) S v² +
When K- = (k(2;,,;)) x,)) is generated by a finite-rank kernel k, like a linear kernel (I.,, æz), a polynomial ker- nel (1 + zz))?, or a random Fourier feature kernel (Rahimi & Recht, 2007), this guarantee becomes O(v) and improves upon uniform subsampling whenever O(1//Taat) In this case, the non-uniform algorithms of Tab. I all enjoy ((log(Toun/ provement over the 22(1/ /Taa)) MMD of uniform subsam- pling. We will revisit this finite-rank setting when studying stochastic gradient accelcration strategies in Sec. 5.
+ +>4+1( Rune
1
and
Thn
K(Pin Pout)l S vDIV log(
2|
Here, Xj denotes the j-th largest eigenvalue of K, Aut1 O, and Dz & maxieI VK,,
MMD, a significant im-
Suppose that, in addition, X C Rd and [Ka- K31 S LK || - 12l12 for some LK > O and all i E I and I E supp(Pm.. Then, with probability at least 1 - 8/2- - 8',
[(Pm - Pom) ll S VDD log( 4/ (1 +
32
More generally, Thm. 1 guarantees improved MMD even for full-rank K, provided that the eigenvalues of K de- cay sufficiently rapidly. For example, optimizing over the approximate rank parameter r yields an O(v O( (2)m)(())m)) bound under exponential eigenvalue decay Ar+1 = n. ((P+), ) bound under
v3
+ +vD 32 / rank Xx) log( 3c²R, Lx
(4)
DEA(BTLK)
for Ri A maxiez |2 and X [T.]TEr
O(ne-or"/r and O polynomial eigenvalue decay \x+1 O(//r)). Fortu- nately, some of the most commonly-use kemnlss generate kernel matrices with rapid eigenvalue decay.
Let us unpack the three components of this result. First, Thm. 1 provides a high-probability O(v /logl))(() bound (3) on the KMS for any kernel and any sub-Gaussian thin- ning algorithm on any space. particular, the non-uniform
Thast
3

---

Low-Rank Thinning
For example, the popular Gaussian kernel R2,
4. Approximating Attention
GAUSS(1): k(x, v) = exp(-nliæ - wllB) for 1 > (5)
We will first use our analysis to accelerate attention ap- proximation in transformers. Dot-product attention lies at the heart of the transformer neural network architecture that has revolutionized natural language processing, com- puter vision, and speech recognition over the last decade (Vaswani et al., 2017; Dosovitskiy et al., 2021: Dong et al., 2018). Given a collection of query, key, and value vectors (q. k; v, each in R dot-product attention computes the softmax matrix
generates K = (k(x F.3) Satissiinn
satisfying
Ar+1 S ne # 2/ log( (ct0R?
for (2e)a < < (6)
whenever X' C. (R) (Altschuler et al., 2019, Thm. 3). Combined with Thm. 1, this fact immediately yields an MMD guarantee for each algorithm in Tab. 1. We present representative guarantee for KH( Corollary 1 (Gaussian MMD of KH). If Xm C (R) for R > O, then KH()) with k = GAUSS(1), and n = Ain delivers
T ATTENTION (q.)) (k;; Uy 13)}==) - D-IAV
(8)
for A.j - exp( (q, ( diag( Al,), and V Vij-
vd
MMD (Pmm Puul S
While attention has enjoyed unprecedented success in cap- turing long-range dependencies amongst datapoints, its computation is expensive, requiring (dd time to con- struct and multiply the matrix A. This quadratic-tima bot- tleneck has inspired a plethora of practical approximate at- tention mechanisms (e.g., Kitaev et al., 2020; Choromanski et al., 2021: Chen al., 2021), but, to our knowledge, only two guarantee accurate reconstruction of the softmax ma- trix T (Zandieh et al., 2023; Han et al., 2024). In this sec- tion, we design new fast attention approximation based on sub-Gaussian thinning and derive guarantees that improve upon the prior art.
O log(nuu/ /6) (ooeennnly + log( ()))
with probability at least 1 5/2 8'
The proof in App. provides a fully explicit and easily computed bound on the Gaussian MMD. Under the same assumptions, the distinct analysis of Dwivedi & Mackey (2022, Thm. 2, Prop. 3) provides squared MMD bound of size O log(Rae//)) ( nou
loog) (mou) n/22 + log( à ))). Notably, (log log()aa))"
Cor. 1 improves upon this best known KH()) guarantee whenever the datapoint radius R O(log Nour), property that holds almost surely for any bounded, sub-Gaussian or subexponential data sequence (see Dwivedi & Mackey, 2024, Prop. 2).
4.1. Thinning attention in theory
Algorithm 1: Thinformer
Altschuler et al. (2019, Thm. 4) additionally showed that Gaussian kernel matrix eigenvalues satisfy
Input: Queries, keys, and values (g;, k., v.) in IRd, Mlur I/ Define key-value attention kernel
Ar41 S ne ne-or 2/(64)) for 1 15r<n
(7)
kan ((ks 8), (K'', b0)) 2 exp ((ke, k')) (0,
// Thin augmented key-value pairs using Katt
for a constant c independent of X when X' belongs to a smooth compact manifold of dimension d² < d. In this case, low-rank analysis yields adaptive MMD guar- antees that scale with the potentially much smaller intrin- sic dimension d². We use Thm. 1 to prove the first such intrinsic- dimension guarantee for (H) in App. E.
Umax + max |/ ||ao: (Is, ū.). + (kt//d (ws, Vmax)) =6
Nou + KH-COMPRESS(O0
(k:, 8, 8,) katt, noa)
Return exact attention on selected vey-v subset
return T A PNTENTIOO((4))L) ((k, u) (ks, ū) E Naw))
Corollary 2 (Intrinsic Gaussian MMD of KH). If Xm lies on a smooth manifold Q C Bd of dimension d' < d (Assump. E.1), then KH()) with k GAUSS(T), and Vin delivers
Alg. summarizes our new Thinformer module. At its heart is a new key-value attention kernel kat that mim- ies the special structure of the softmax matrix T. Alg. uses the attention kernel and a high-quality thinning algo- rithm, (HH-COMPRESS(O.5) to subselect key-value pairs and then computes exact attention (8) for the key-value subset. In total, this requires only ( time to run KH-COMPRESS and O n now) time to compute
MMD K (Pm. Ponn) S s0(
log( Sou
(1 log((na)
y + +ogg 1 ))
with probability at least
8' for e independent of Xm-
In Sec. 6, we will use Cors. I and 2 to establish new guar- antees for distinguishing distributions in near-linear time.
'A third remarkable work (Alman & Song, 2024) establishes upper and lower bounds for attention approximation but without practical implementation.
With our core theory in hand, we now turn our attention to a series of impactful applications.
4

---

Low-Rank Thinning
Table 2: Practical approximations with guarantees. For each approximation T E Raxd to the softmax matrix T (8), we report, up to a constant factor, the best worst-case error guarantee for ||T Tilmax given O(d +t) running time and 7-bounded (9) queries and keys. Here, the ratio || VV lies in [1, vTl and T = 0.173 + o(1).
and guarantee, for example, O ( error in Ö(dn 2 +20)
Vn
time. contrast, the Tade and Thyp bounds require quadratic runtime to guarantee O ( error in the best case loop = (()) and cannot guarantee consistent sub- quadratic estimation in the worst case ( (|V = (Vvn)).
4.2. Thinning attention in practice
Approximation
Guarantee
22 / d (n (V Vllma) log
To gauge the practical effectiveness of Alg. 1, we recre- ate the benchmark Tokens-To-Tokkes Vision Transformer (T2T-ViT) and BigGAN image generation experiments of Zandich et al. (2023). the T2T-ViT experiment, attention approximations are scored on their ImageNet classification accuracy and computational expense when used as drop-in replacements for the two most expensive attention layers in pretrained T2T- ViT neural network (Yuan et al., 2021), In the BigGAN experiment, approximations are scored on their computational expense and two popular measures of image generation quality, the Frechet Inception Distance (FID, Heusel al., 2017) and Inception Score (IS, Sali- mans et al., 2016). Using the exact implementations and settings provided by Zandich et al. (2023), we benchmark our Py PyTorch implementation of Thinformer against exact attention and four leading attention approximations: Per- former (Choromanski et al., 2021), Reformer (Kitaev et al., 2020), ScatterBrain (Chen et al., 2021), and KDEformer.
Thinformer
no
+ 5 (0+2)
KDEformer
n2/2
17s (log
HyperAttention
|
wa/0
ATTENTION with n queries and Nout key-value pairs. In contrast, computing the exact softmax matrix T with stan- dard matrix multiplication requires ((d time. Our next result, proved in App. F, shows that Alg. also admits a strong quality guarantee for approximating T.
Theorem 2 (Quality of Thinformer). With probability at least's 2. Thinformer (Alg. 1) yields
coxpl 2R [V logg (Ness) 18g(8mun (8ran loga
I ||| maxx
In Tab. we find that Thinformer (g 2) provides the highest Top-1 accuracy on the ImageNet 2012 validation set (Russakovsky et al., 2015), while running faster than all of the alternatives. In Tab. 4, Thinformer (g = 2) yields better FID and IS than all of the alternatives while run- ning significantly faster than exact, KDEformer, Reformer, and ScatterBrain. Performer runs faster still but at the ex- pense of substantially worse FID and IS. The final attention call of Thinformer can also be combined with optimized attention implementations like FlashAttention (Dao et al., 2022; Dao, 2024) to further reduce the time and mem- ory footprint. We provide Py PyTorch code replicating this experiment at https: / / thub. com mi croso ft/ thinformer and supplementary experiment details in App. L.I.
for
C
128
v3V
V
(d + logo (3 +2)
2 I
+
Vlog(8)
128
and R a max max | (1.1))).
To put this result into context, let us compare with the exist- ing guarantees for practical attention approximation, sum- marized in Tab. 2. Under the y-boundedness assumption,
maxie[n] max k
1 ( S Vooologn n,
(9)
the KDEformer approximation (Zandieh et al.. 2023, Cor. 3.6) with = 0.173 + o(1), the HyperAttention ap- proximation (Han et al., 2024, Thm. 1) with masking, and the Thinformer approximation (Thm. 2) guarantee the [ - max bounds of Tab. 2 with O(dn++a) ++4) runtime and probability at least 2- The Thinformer guarantee exhibits four improvements over its predecessors. First, it estab- lishes a significantly faster eттor decay rate (n -a versus n-a/2 or n n=/6 for given subquadratic runtime n!ta Second, it reduces the dependence on the error inflation factor y. Third, like the Hyper guarantee, it elim- inates all dependence on the KDEformer penalty parameter T. Finally, it reduces dependence on the value matrix by a factor of | E [1,
5. Faster SGD Training
We now turn to second application, accelerating training through gradient reordering. To train a machine learning model parameterized by w E Rd, , standard approach is to minimize the empirical risk s(w) e 1 stochastic gradient descent (SGD) updates.
n Σ Se(w) using
TV
w ++ " w k+ -=1 a fz. (*))
(10)
Put otherwise, with bounded ||V|2,,0 Tiin can provide consistent (i.c., [ - TIlmax + O as n + oc) sub- quadratic estimation whenever is bounded away from 1/2
for each epoch E [K] and datapoint i E [n]. Here, a > is a step size, each fi is -atepoint-speeific loss function,
5

---

Low-Rank Thinning
Table 3: Quality of ViT attention approximations on ImageNet. We report mean Top-1 accuracy =:1 standard deviation across five random seeds and mean forward pass runtime #1 standard deviation across 50 batches of 64 images.
Attention Algorithm
Top-1 Aceuracy (%)
Layer Runtime (ms)
Layer 2 Runtime (ms)
Exact
82.55 0.00
18.48 0.12
1.40 = 0.01
Performer
80.56 0.30
2.54 = 0.01
0.60 + 0.01
Reformer
81.47 + 0.06
7.84 = 0.03
1.53 + 0.01
KDEformer
82.00 + 0.07
5.39 + 0.03
2.28 + 0.03
Scatterbrain
82.05 0.08
6.86 + 0.02
1.55 + 0.03
Thinformer (Ours)
82.18 0.05
2.06 = 0.01
0.54 = 0.00
Table 4: Quality of BigGAN attention approximations for image generation. We report Frechet Inception Distance (FID) with the ImageNet validation set, Inception Scores (IS), and mean forward pass runtime standard deviation across 10 batches of 32 images. lower FID or higher indicates better image generation quality.
Attention Algorithm
FID (4)
IS (t)
Runtime (ms)
Exact
32.18
58.37 = 4.21
5.79 0.02
Performer
33.58
38.07 = 3.43
2.29 + 0.01
Reformer
72.23
19.14 2.09
12.14 + 0.02
KDEformer
30.70
36.91
6.74:00.46
ScatterBrain
38.47
3
Thinformer (Ours)
30.54
2.69 + 0.01
and Ty is a permutation of [n] representing the order in which datapoints are processed the k-th epoch.
problems unaddressed.
First, while the established convergence rates of Lu et al. (2022) nearly match the minimax lower bounds for per- muted SGD algorithms (Cha al., 2023, Thm. 4.5), a mul- tiplicative gap of size ((d) remains in the worst case. This led Cha et al. (2023) to declare, "It is an open problem whether there exists a permutation- based SGD algorithm that gives a dimension-fres upper bound while maintaining the same dependency on other factors."
Algorithm 2: Thinned Reordering
Stochastic gradients (ar & V (1) (w 1=1 ) prior ordering R,, thinning algorithm ALG
Input:
// Select half of points using linear kernel
a (L.
(o y = 2 k(,, y) = (x, v))
II -++ }: IT' -
I/ Initialize empty start and end lists
for i 1,..., do T.append(Tx of e 2t else IT', prrepend(m(()))
Second, Lu et al. (2022) carry out their analysis using the self-balancing walk (SBW) thinning algorithm of Alweiss et al. (2021) but find its overhead to be too high in practice. Hence, in all experiments they instead employ a greedy thinning algorithm that often works well in practice but is not covered by their analysis.
end
return 1 concatenate(I,IIT)
Typically, one selects the orderings Th uniformly at ran- dom, but recent work has demonstrated faster convergence using non-uniform, adaptively selected orderings. Specifi- cally, Lu et al. (2022); Cooper al. (2023) show that any sufficiently accurate thinning algorithm can be efficiently transformed into a reordering rule that improves the con- vergence rate of SGD by substantial ((n factor. Their approach, distilled in Alg. 2, uses an elegant construc- tion of Harvey & Samadi (2014, Thm. 10) to translate a high-quality thinning of stochastic gradients into a higher- quality reordering. However, these prior studies leave two
5.1. Bridging the dimension gap
To address the first problem, we derive a new guarantee for SGD with LKH reordering that replaces the typical (d) penalty with soft notion of rank.
Definition 4 (e-rank). The e-rank, rank, of matrix X is the number of singular values greater than c.
Theorem 3 (LKH-SGD convergence). Suppose that, for
6

---

Low-Rank Thinning
Full Train Loss
Test Accuracy
Full Train Loss
Test Accuracy
6.330
07.4-
6,358
82.1-
0.337
813
CD-GruB: SBW
0.356
8211
RR
LKH-SGD
0.338
CD-GraB: Gready
(8) 600 Seconds
(00)
Epochs
Epocis
Seconds
Figure Train and test convergence trajectories for mortgage classification with reordered SGD variants. We display mean values 11 standard deviation across 5 random seeds. See Sec. 5.2 for more details.
alli [n] and w, v E Rd, the losses f and fü satisfy
to the scale of each input and has hyperparameterss to tune. Moreover, with a linear kernel, LKH 2K can be run online in ((nd) time. Hence, LKH( 2K is a promis- ing substitute for the greedy thinning of Lu et al. (2022); Cooper et al. (2023). Indeed, when we recreate the Home Mortgage Disclosure Act logistic regression experiment of Cooper al. (2023) with single worker (Fig. 1), we find that LKH-SGD strongly outperforms the standard practice of random reshuffling (RR) and the theoretically justified but overly conservative CD-GraB: SBW variant. In ad- dition, LKH-SGD matches the state-of-the-an test accu- racy of CD-GraB: Greedy and lags only slightly in terms of training convergence.
(w) V >13 S o² (bounded noise).
(ww) (f())l L|w vl12 (smoothness), and f(w) - f & 2p ( (PL) f inf f(v).
Then, with probability at least 2. SGD (10) with LKH 2x reordering (Alg. 2) and step size a given in App. G satisfies
f(wk)- f S Ō n<
for
max ranke, (la
x [)),, x 2 +
and Ej A max ke(n
9c loggg//(K lon(en/ / 2)) log(4K #1
v/
The accelerated convergence rate of LKH-SGD over the standard slow SGD rate of RR provides direct verification of the Thm. 3 guarantee, and we further verify in Fig. L.1 that the singular values of the gradient update matrices drop off steeply, resulting in relatively small 6 -arkss (see Fig. L.1). See ht //github. com/ khagd for PyTorch code replicating this experiment and App. L.2 for supplementary experiment details.
The proof Thm. 3 in App. G simply uses Thm. to bound the thinning quality of LKH( 2k and then adapts the prior SGD analysis of Cooper al. (2023). Notably, the standard practice of random reshuffting. i.c., SGD with uni- form reordering, can only guarantee a significantly slower 2 (I) rate under these assumptions (Rajput et al., 2020, Thm. 2), while Lu et al. (2022, Thm. 4) implies a similar but cemnension-dependeee Ō (())))
=)) rate for SBW reorder- ing. Thm. matches the minimax lower bound of Cha et al. (2023, Thm. 4.5) up to the e-rank parameter and shows that dimension dependence update matrices ... x* ( ally, = (( log( Kn)
6. Cheap Two-Sample Testing
Our final application is two-sample testing, determining whether two datasets are drawn from the same underly- ing distribution.
be avoided when the gradient are low-rank, or, more gener- >aapprxximable by low-rank matrices.
observe independent samples X' A (xx) and y (ı,)}= from the unknown distributions P and Q respectively, and we seek to accept or reject the null hypothesis that P Q. Standard kernel MMD tests tackle this task by computing the empirical MMD
5.2. Bridging the theory-practice gap
Two criticisms levied by Lu et al. (2022) against the SBW algorithm were the need to estimate the maximum Eu- clidean norm any possible gradient vector in advance and the need to tune its free hyperparameter. LKH( 2k has neither of these drawbacks as it automatically adapts
MMD (P Qma for Pin: Qua A 1 E n. Eyey
for an appropriate kernel and rejecting the null hypoth- esis whenever (MD Qm) is sufficiently large (Gret- ton et al., 2012). Such tests are prized both for their broad
7

---

Low-Rank Thinning
applicability and for their high discriminating power, that is, their probability of rejecting the null when P * Q. A standard way to summarize the power properties of a test is through its detectable separation rate.
Alg. 3 details the Compress Then Test (CTT) approach of Domingo-Enrich et al. (2023, Alg. 1). Given a core- set count 2 2, a compression level g 2 0, and a nom- inal level a E (0, 1), CTT divides N' and y into data- point bins of size Vinn
thins each bin down to size noot - 2 V using KT-COMPRESS(C) (a refinement of KH-COMPRESS(5) detailed in App. H), and uses the thinned coresets to cheaply approximate MMD (P'm Qin) and permuted versions thereof. Domingo-Eninn Enrich et al. (2023, (8)) showed that the total runtime of CTT is domi- nated by
P m+
Definition 5 (Detectable separation rate). We say a two- sample test has detectable separation rate ék,m,n if. for any detection probability 1 3 E (0, 1), there exists constant Ck.9 > O such that the test has power al least 1 - 8 of rejecting the null whenever MMD& (IP, Q) 2 Ok,3 Ck,m,
Standard MMD tests can detect distributional differences on the order of 6k,m,n Vwin(m.n) (Gretton et al., 2012,
0 + () + loga men g)))
Cor. 9), and this detectable separation rate is known to be the best possible for MMD tests (Domingo-Entre Enrich et al., 2023, Prop. 2) and minimax optimal for translation invari- ant kernels (Kim & Schrab, 2023, Thm. 8). However, standard MMD tests also suffer from the @((m + n)²) time burden of computing the empirical MMD. Recently, Domingo-Enricn et al. (2023) showed that one can improve scalability while preserving power by compressing Pi and Qu using a high-quality thinning algorithm. However, their analysis applies only restricted class of distributions and kernels and exhibits a pessimistic dimension depen- dence on Rd, Here, we offer new analysis of their Com- press Then Test approach that applies to any bounded ker- nel on any domain and, as an application, develop the first non-asymptotic power guarantees for testing with learned deep neural network kernels.
kernel evaluations, yielding a near-linear (((m + n) log" (m (m++)) time algorithm whenever 8 = Olog, (m+ n)) and I c clog, log(mm + n)). Moreover, Prop. of Domingo-Entn Enrich et al. (2023) ensures that CTT has proba- bility at most a of falsely rejecting the null hypothesis.
Our next, complementary result shows that CTT also matches the detectable separation rate of standard MMD tests up to an inflation factor Rk/28 depending on the com- pression level g.
Theorem 4 (Low-rank analysis of CTT power). Suppose the parameters of CTT (Alg. 3) satisfy m S n,
Sm 2
32 9
2e log
and = ==min (
30es
for B 2 1+3/2 and 7
4: (8) Then CTT has
6.1. Low-rank analysis of Compress Then Test
detectable separation rate (Def. 5)
CKmmn = (1 + Rx/ 29/ mm.
Algorithm 3: Compress Then Test (CTT)
Input: Samples (XY, )), # coresets s, compression level g. kernel k. failure probability 8, # replicates B, level a
where RS denotes the (1
B )-th quantile of
20s
Partition X' into 8m.
equal-sized bins (x(()) m+n an
am
Partition y into s,,
cqual-sized bins (m m
R2 A log( m+n log( (
(12)
min [[]k]lsor log(")) (3) + AK) + Ax+1 (K')
// Identify coreset of size Neur 2a mott for each bin for 1, 1,... S. do p(())
2
KT CO-CORRRES g, k)
for K A (k(x, Mi K' |||| - sup supr.yesupp(P+ (((x,)),
and
for i = 1,...,8, Sn do Quel
(T-COMPRESS(5))) g. k)
// Compute CORESETMMD test statistic
M841 <- MMD (
Am. Eim out 2n, Ee
1
(1I)
The proof in App. I combines the low-rank sub-Gaussian error bounds of Thm. 1 with the generic compressed power analysis of Domingo-Enrich et al. (2023, App. B.1) to yield power guarantees for bounded kernels on any do- main. Notably, when rank(K) and rank(K') are bounded or, more generally, polylog(n) one can choose the com- pression level g = @(log, log(m + n)) to exactly match the optimal quadratic-tima detectable separation rates with a near- pear-linear time CTT test. Moreover, the inflation factors remain well-controlled whenever the induced kernel matri- ces exhibit rapid eigenvalue decay.
II Simulate null by randomly permuting the s coresets times for = =1,..,,BB 13d do
(1(()
oun. (mm (1)
(f + PERMUTE((P(C))
out ym
(y (m
M. + MMDD (L EiT p(()) 1 Din, ((8) bur.b En
end
// Threshold test statistic
R t position of M841 in an increasing ordering of (M
B+1
with ties broken uniformly at random
return Reject with prob. min(1, max(0,
(0, R - (B) + 1)))
8

---

Low-Rank Thinning
As a concrete example, consider the learned deep neural network kernel of Liu al. (2020),
1.0
B 2
Power (1- Type II Error)
Kdeep (z, y) [11 ())()(()) p(y)) + (a, y), (13)
0.8
7
where Φ _2_ + Rddand is pretrained neural network, q and λ are GAUSS(n) kernels (5) on I' and Rdeald re- spectively, and E (0, 1). This deep kernel generates full-rank kernel matrices (Liu et al., 2020, Prop. 5) but induces exponential eigenvalue decay due its decom- position mixture of Gaussian kernels. Hence, as we show in App. J, CTT with Keeep (logg, log(m + n)), and sub-Gaussian inputs matches the detection quality of a quadratic-time MMD test near-linear time.
0.6
CTT
0.4
W-B W-Block
Su Subsampling
0.2
Level 0.05
0
10
20
30
40
50
Time per test (ms)
Corollary (Power of deep kernel CTT). Instantiate the assumptions of Thm. 4 with k Kdeep (13). If the inputs (Ø(z1), (ly)) ), Vi) are sub- Gaussian, that is,
Time-power trade-off curves for detecting Higgs bosons with deep kernel MMD tests. We plot mean values +1 standard error across 1000 independent trials with level 0.05 and B 100 permutations.
Figure 2:
E(eellé((a)) (o,,). )1ž} < co
(14)
for some > 0, then CTT satisfies the conclusions of Thm. with d' & dembd + d and
Rkwep = Olog * (g)).
6.2. Powerful deep kernel testing in near-linear time
Moreover, when the input and neural features lie on smooth compact manifolds (as, e.g., in Zhu et al., 2018), the error inflation of CTT adapts to the smaller intrinsic manifold di- mension, enabling improved trade-off between runtime and detection power. See App. K for our proof.
To evaluate the practical utility of deep kernel CTT, we follow the Higgs mixture experiment of Domingo-Enrich et al. (2023, Sec. 5) and use the deep kernel training proce- dure of Liu et al. (2020, Tab. 1). Here, the aim is to distin- guish Higgs boson signal process from background process Q given m n 16384 observations, particle-detector features, and five-layer fully-connected neural network ó with softplus activations and embedding dimension demba = 20.
Corollary (Power of deep manifold kernel CTT). Un- der the assumptions of Cor. 3, if Fı, yr, (I1, ((xx))))))))))))>>)))))) )), and (y1, ((y1)) belong to smooth compact manifolds (As- sump. E with dimension d² < d' then CTT satisfies the conclusions of Thm. 4 with
R Keeep O(log +
+ (g))..
Fig. 2 compares the time-power trade-off curves induced by three fast kernel testing approaches to this prob- lem: SUBSAMPLING, standard wild-bootstrap MMD test (Chwialkowski al., 2014) that simply evaluates empirical MMD using Now Moai uniformly subsampled points; W-BLOCK wild-bootstrap test that averages subsam- pled squared MMD estimates based on 7out = Mou points (Zaremba et al., 2013); and CTT with & = 32 bins and varying We find that the CTT curve dominates that of the alternative methods and matches the power of an exact MMD test (SUBSAMPLING with Yoour n)) in a fraction of the time. The improvements of CTT over the standard power-runtime trade-off of SUBSAMPLING pro- vides direct verification of the Thm. 4 guarantee, and we additionally verify in Fig. L.2 that the empirical infla- tion factor R O(log5(1) in this setting due to ap- proximate low-rankness. See https::/ /ttp::///ttii /ggthub.b....g.g/gg/////.g..bb.. com/ microsoft deepctt for PyTorch code replicating this experiment and App. L.3 for supplementary experiment de- tails.
Cors. 3 and follow from explicitly bounding the eigenval- ues of the generated deep kernel matrices as in (6) and (7). By Kim Schrab (2023, Thm. 8), the separation rate of Thm. 4 is minimax optimal up to the inflation factor Rx/20 and, hence, those of Cors. and are minimax optimal up to log factors.
One could alternatively bound the compression eтror of KT-COMPRESS($) using the covering number approach of Dwivedi & Mackey (2022, Thm. 2, Prop. 3). In the set- ting of Cor. 3, the argument of App. combined with this distinct analysis would yield alternative error inflation factor R Rkwnp/ /20 with worse dimension dependence,
R = O
34' +2 +z))),
and without known adaptivity to an intrinsic manifold di- mension.

---

Low-Rank Thinning
Impact Statement
Chwialkowski, K. P., Sejdinovic, D., and Gretton, A. A wild boot- strap for degenerate kernel tests, Advances in Neural Informa- tion Processing Systems, 27, 2014. (Cited on page 9.)
This work introduced a new analysis of thinning algorithms that adapts to low-rank structures. We exploited this adap- tivity to design fast algorithms with strong quality guar- antees for three key applications in machine learning: dot- product attention in Transformers, stochastic gradient train- ing in optimization, and deep kernel testing for distinguish- ing distributions. More broadly, our techniques provide a general framework for reducing computational resource use in machine learning. Such tools have the potential to reduce energy costs and environmental harms from model training, inference, and evaluation and to improve acces- sibility in essource-constraine settings, all while provably maintaining high quality.
Cooper, A. F., Guo, W. Pham. K. Yuan, T., Ruan, C. F., Lu, Y.. and De Sa. C. Coordinating distributed example orders for provably accelerated training. In Thirty-seventh Conference Neural Information Processing Systems, 2023. (Cited on pages 6, 7, 32, 33, and 37.)
Dao, T. Flashattention-22 Faster attention with better parallelism and work partitioning. In The Twelfih International Con- ference on Learning Representations. 2024. URL https: / opwnreview..e...... www.viewwneeeeeee.ee seree//ooumiiiie wooooooooon222nynse.ae.. (Cited on page 5.)
Dao, T., Fu, D., Ermon, S., Rudra, A., and Ré, C. Flashat- tention: Fast and memory-efficiet exact attention with io- awareness. Advances in Neural Information Processing Sys- tems, 35:16344-16338 2022. (Cited on page 5.)
Acknowledgments We thank Insu Han, A. Feder Cooper, and Wentao Guo for their assistance with their code bases and datasets.
Domingo-Enrich C.,, Dwivedi, R., and Mackey, L. Compress then test: Powerful kernel testing in near-linear time. In Proceed- ings of The 26th International Conference ligence and Statistics, Proceedings of Machine Learning Re- search. PMLR, 25 27 Apr 2023. (Cited on pages 8, 9, and 34.)
Artificial Intel-
References
Dong, L., Xu, S., and Xu, B. recurrence sequence-to-seqqeece model for speech recogni- tion. In 2018 IEEE International Conference on Acous- tics, Speech and Signal Processing (ICASSP). pp. 5884-5888, 2018. doi: 10. 10.11009CCASS2.0188..546 8466566
A no-
Alman, J. and Song, Z. Fast attention requires bounded entries. Advances in Neural Information Processing Systems, 36, 2024. (Cited on page 4.)
(Cited on page 4.)
Altschuler, J., Bach, F., Rudi, A., and Jiles-Weed. J. Massively scalable sinkhom distances via the nyström method, Advances in Neural Information Processing Systems, 32, 2019. (Cited on pages 4, 29, and 30.)
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlshy, N. An im- age is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representa- tions, 2021. URL ht htsps: / opppreeeeeeeeeeeeeeeeeeeeeeeeeee nnt// net//orum? E--YibFFaNNTTT (Cited on page 4.)
Alweiss, R., Liu, Y. P., and Sawhney, M. Discrepancy minimiza- tion via a self-halancing walk. In Proceedings of the 53rd An- mual ACM SIGACT Symposium on Theory of Computing, pp- 14-20, 2021. (Cited on pages and 6.)
Dwivedi, R. and Mackey, L. Generalized kemnl thinning. In International Conference on Learning Representations, 2022. (Cited on pages 1, 4, and 9.)
Bansal, N., Dadush, D.. Garg, S., and Lovett, The gram- schmidt walk: cure for the banaszezyk blues. In Proceedings of the 50th annual acm sigact symposium on theory of comput- ing. pp. 587-55777 187-597,770 2018 (Cited on pages 3, 19, and 22.)
Dwivedi, R. and Mackey, L. Kernel thinning. Journal of Machine Learning Research, 25(152):1-7, 2024. (Cited on pages 1, 3, 4, 15, 16, 17, 18, 34, and 36.)
Cha, J., Lee, J., and Yun, C. Tighter lower bounds for shuffling sgd: Random permutations and beyond. In International Con- ference on Machine Learning, pp. 3855-3912. PMLR, 2023. (Cited on pages 6 and 7.)
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012. (Cited on pages and 8.)
Chen, B., Dao, T., Winsor, E., Song, Z., Rudra, A., and Ré. C. Scatterbrain: unifying sparse and low-rank attention ap- proximation. In Proceedings of the 35th International Con- ference on Neural Information Processing Systems, NeurIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393. (Cited on pages 4 and 5.)
Han, I., Jayaram, R., Karbasi, A., Mirrokni, V., Wondruff, D., and Zandieh, A. Hyperautention: Long-context attention near- linear time. In The Twelffh International Conference on Learn- ing Representations, 2024. URL https: / /penreview. net/ /
(Cited on pages and 5.)
Harshaw, C., Sävje, F., Spielman, D. A., and Zhang, P. Balancing covariates in randomized experiments with the gram-schmidt walk design. Journal of the American Statistical Association, pp. 1-13, 2024. (Cited on page 22.)
Choromanski, K. M., Likhosherstov, V., Dohan, D., Song. X., Gane, A., Sarlos, T., Hawkins, P., Davis, Q. Mohiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. Rethinking attention with performers. In International Con- ference on Learning Representations, 2021. URL https: / opeerevii www.et.///eeeeeeeee..eee fowumorruiioooo d- ZuuOORA (Cited on pages and 5.)
Harvey, N. and Samadi, S. Near-Optimal Herding. In Proceedings of The 27th Conference on Learning Theory, volume 35, pp. 1 1165- 1182, 2014. (Cited on pages 1, 6, and 32.)
10

---

Low-Rank Thinning
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in neural in- formation processing systems, 30, 2017. (Cited on page 5.)
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei, L. ImageNet Large Scale Vi- sual Recognition Challenge. International Journal of Com- puter Vision (IJCV). 115(3):211-222, 2015. doi: 10.1007/ si 1263-015-0816... (Cited on page 5.)
Hoeffdiing W. Probability inequalities for sums of bounded ran- dom variables. Journal of the American Statisticul Associ- ation, 58(301):13- 30, 1963. doi: 10.1080001621499.199 1963. 10500830. (Cited on page 15.)
Sandetoglu, M. and Dinsev, S. M. Inverses and determinants x block matrices. Mathematics, 11(17), 2023, ISSN 2227-7390. doi: 10.3390/mathh1177777 URL https:// www. mdpi. 2tt.o//2222222 01107777799111117113 page 23.)
(Cited on
Hom, R. A. and Johnson, C. R. Matrix Analysis. Cambridge University Press, 1985. (Cited on page 36.)
Salimans, T., Goodfellow. I., Zaremba, W., Cheung, V., Radford, A., and Chen, X. Improved techniques for training gans. Ad- vances in neural information processing systems, 29, 2016. (Cited on page 5.)
Kim, I. and Schrab, A. Differentially private permutation tests: Applications to kernel methods. arXiv preprint arXiv:2310.19443, 2023. (Cited on pages and 9.)
Kitaev. N., Kaiser, L.. and Levskaya, A. Reformer: The efficient transformer. In International Conference on Learning Rep- resentations, 2020. URI. https: openrevi ew n forum? i vrrkNNkkHE.... (Cited on pages 4 and 5.)
Sherman, and Morrison, W. Adjustment of an Inverse Ma- trix Corresponding to a Change in One Element of a Given Matrix. The Annals of Mathematical Statistics, 21(1):124 - 127, 1950. doi: 10. 4/aom//177/// URL https: (Cited on
//doi. worg/rr/g.... 121 4/ //aa/////////99////// page 23.)
Li, L., Dwivedi, R., and Mackey, Debiased distribution com- pression. In Proceedings of the 41st International Conference on Machine Learning, volume 203 of Proceedings of Machine Learning Research. PMLR, 21-27 Jul 2024. (Cited on page 1.)
Shelty, A., Dwivedi, R., and Mackey, L. Distribution compression in near-linear time. International Conference on Learning Representations, 2022. (Cited on pages 1, 3, 18, 19, 24, 34, and 35.)
Liu, F. Xu, W., Lu, J., Zhang, G., Gretton, A., and Sutherland, Learning deep kernels for non non-parametric two-sample tests. In International conference on machine learning, pp. 6316-6326, PMLR, 2020. (Cited on pages and 38.)
D. J.
Steinwart, I. and Christmann, A. Support Vector Machines. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387772413. (Cited on page 2.)
Lu, Y., Guo, W., and De Sa. C. M. Grab: Finding provably better data permutations than random reshuffling, Advances in Neural Information Processing Systems, 35:8969-8983 2022. (Cited on pages 6 and 7.)
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones. L.. Gomez, A. N., Kaiser, L.. and Polosukhin, 1. Attention you need. In Proceedings of the 31st International Con- ference on Neural Information Processing Systems, NIPS' 17, pp. 6000-600 6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964, (Cited on page 4.)
Markov, A. On certain applications of algebraic continued frac- tions. Unpublished Ph. D. thesis, St Petershurg, 1884. (Cited on pages 26 and 27.)
Wainwright, J. High-dimensioall statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019. (Cited pages 25, 28, and 29.)
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T.. Lin, Z., Gimelshein, N., Antiga, L., et al. Py- torch: An imperative style, high-performance deep learning li- brary. Advances in Neural Information Processing Systems, 32, 2019. (Cited on page 36.)
Yuan, L., Chen, Y., Wang. T., Yu, W., Shi, Y., Jiang, Z.H Tay. E. E.,, Feng. J., and Yan, S. Tokens-to-token vit: Training vision transformers from scratch on imagenet. In Proceedings of the IEEF/CVF international conference on computer vision, pp. 558-567, 2021. (Cited on page 5.)
Phillips. J. M. and Tai, W. M. Near-optimal coresets of kernel density estimates. Discrete & Computational Geometry, 63 (4):867-887, 2020. (Cited on pages and 3.)
Zandieh, A., Han, I., Daliri, M., and Karbasi, A. Kdeformer: Ac- celerating transformers via kernel density estimation. In Inter- national Conference on Machine Learning, pp. 10605-4062) PMLR, 2023. (Cited on pages 4, 5, and 37.)
Rahimi, A. and Recht, Random features for large-scale kernel machines. Advances in Neural Information Processing Sys- tems, 20, 2007. (Cited on page 3.)
Zaremba, W., Gretton, A., and Blaschko, M. B-test: A non- parametric, low variance kernel two-sample test. Advances in Neural Information Processing Systems, 26, 2013. (Cited on page 9.)
Rajput, S., Gupta, A., and Papailiopoulos, D. Closing the conver- gence gap of sgd without replacement. In International Con- ference on Machine Learning, pp. 7964-7973. PMLR, 2020. (Cited on page 7.)
Zhu, W., Qiu, Q.. Huang, J., Calderbank. R., Sapiro, G., and Daubechics, I. Ldmnet: Low dimensional manifold regular- ized neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2743-2751, 2018. (Cited on page 9.)
Rudin, W. Functional Analysis. International series in pure and applied mathematics. McGraw-Hill, 1991. ISBN 9780070542365.. URL https: //cookkk.... google goom/..com/ books? di VAAAAMAAJ. (Cited on page 14.)

---

Low-Rank Thinning
Appendix Contents
A Appendix Notation and Definitions
13
Proof of Tab. 1: Sub-Gaussian Thinning Examples
14
B.I
SUBSAMPLING
14
B.2
KH
15
B.3
(KH())
16
B.4
RKH(0)
17
B.5
KH-COMPRESS (0)
18
B.6
GS-THIN
19
B.7
GS-COMPRESS
24
C Proof of Thm. 1: Low-rank sub-Gaussiaa thinning
24
C.1 Proof of MMD bound (2)
25
C.2 Proof of kernel max seminorm bound
26
C.3 Proof of Lipschitz kernel max seminorm bound (4)
27
C.4 Proof of Lem. C.4: Bounded-Hölder uub-Gaussian process
29
Proof of Cor, 1: Gaussian MMD of KH
29
Proof of Cor. 2: Intrinsic Gaussian MMD of KH
30
F Proof of Thm. 2: Quality of Thinformer
30
F.I Proof of Lem. F.1: Decomposing attention approximation error
31
F2 Proof of Lem. F2: KMS bound on attention approximation error
31
F3 Proof of Lem. F3: Thinned attention problem parameters
31
G Proof of Thm. 3: LKH-SGD convergence
32
H KT-COMPRESS(O)
34
I Proof of Thm. 4: Low-rank analysis of CTT power
34
L1 Proof of Thm. L1: Low-rank analysis of CTT power, detailed
34
I.2 Proof of Lem. L.1: (K, ( thinning algorithms are k-sub-Gaussian
................................
35
J Proof of Cor. 3: Power of deep kernel CTT
36
K Proof of Cor. 4: Power of deep manifold kernel CTT
36
Supplementary Experiment Details
36
12

---

Low-Rank Thinning
L.1 Approximating attention experiments
36
L.2 Faster SGD training experiments
37
L.3 Cheap two-sample testing experiment
38
A. Appendix Notation and Definitions
We often use the shorthand (a)+ _ max(a, 0) well the shorthand k(X, X) ) represent the matrix (k(x),,,)){ ( In addition, for each kernel k, we let Hx and ||-1|k represent the associated reproducing kemnel Hilbert space (RKHS) and RKHS norm, that B& {f E 7k ||f k 1) and define
(
Font k
1. Pin
ExEx. k(x,
1. Piue
E k(x,,).
We also relate our definition of a sub-Gause Gaussann thinning algorithm (Def. 3) to several useful notions of sub-Gaussianity. Definition A.1 (Sub-Gaussian vector). We say that a random vector w E IR" is SasuuGassssnn on an event & if is SPSD and v > O satisfies
Eg cxp(u' [w]] S exp(2 u Ku) for all u E R".
(15)
If. in addition, the event has probability 1, we say that w is (K, 1) -usuuG-Ganniaan
Notably, a thinning algorithm is (K, (yb-))))-GGassiia if and only if its associated vector Pm Pon is (K, -)-sub-Gaussian on an event & of probability at least 6/2.
Definition A.2 (Sub-Gaussian fuunction) For a kernel k, we say that a random function & E Hk (k, on an event & if > satisfies
Eelexp(UJ ()x) S exp( 11 for all f E Hk.
(16)
If. in addition, the event has probability 1, we say that & -)s-ub-aaussian.
Our next two lemmas show that for Gaussianity equivalent the prior notion of vector sub-Gaussianity, allowing us use the two notions interchangeably. Hereafter, we say that generates SPSD matrix K if k(X,X) K.
signed measures like P. Pout this notion of functional sub-
Lemma A.1 (Functional aub-Gaussianity implies vector sub-Gauss uub-Gaussianity). In the notation Def. 3, if (Pi - Pout k (k, v))--uub-Gaussiie Gaussian
event E and k generates K, then the vector Pm Paut is v). Gaussian Gasuassinaa E.
Proof. Suppose (Pn - IP our Ik is (k, (ub))suuu--Sssiiiii
event E, fix vector E R", and define the function
fu Ei u.k(; E Hu.
By the reproducing property,
K(P.. -Pam) = (fui (PP ko and [l = Ku.
(17)
Invoking the representations (17) and the functional uub-Gaussianity condition (16) we therefore obtain
Eg [exp(u T K(Pi. Pomr)] = [ex[cx(((f (fus (Pin - Pou k))) s exp(11full = exp(u Ku 4)/
so that P.. Pout (K, (it-vu)sss-usssstt Gaubb-an on the event claimed.
Lemma A.2 (Vector sub- uub-Gausiannity implies functional sub-Gaussianity). In the notation of Def. 3, if Pm Pout is (K, -)-suu-Gaussian on an event E and generates K, then (Pin Pow)) k (k, -uub-GGiinnn Gaussian on E.
Proof. Suppose Pin Pout is (K, (.s.V)-uub-Guusee Gauu-Gasiiiin on an event ε, fix a function f E Hk. and consider the set
{ fu Ei u.((, u R
13

---

Low-Rank Thinning
Since C is closed linear subspace of Hk. we can decompose f as - Su fL, where u E R and f is orthogonal to L. (Rudin, 1991, Theorem 12.4), that
1 = 11fulll + llf=lli and ll = u Ku.
(18)
Invoking the orthogonality of f1 and iPin Pluu) L., the reproducing property representations (17), and the vector sub-Gaussianity condition (15), we find that
Eg [e (Pinn Pou kk)) x)] = Eg Eelexp((Fue u + fL. (I - Four (k)))) = Eg [exp(u T K(Pm - Poul))
I exp(u Ku 2 S exp(11f11 )2)
so that iI - IP lk is (k, (), sub-Gussiian the event & as claimed.
end our discussion about the versions of aub-Gaussianity considered above by presenting the standard fact about the additivity of sub-Gaussianity parameters under summation of independent sub-Gaussian random vectors, adapted to our setting.
Lemma A.3 (Vector sub-Gaussian additivity). Suppose that, for each j E [m], Aj E RR is (K, on an event E given A1:(-1) 2 (AI,..., and Ezj- A n &s. Then Σ j=1 A is (K, 1= 12) -sbb/))suuaaasssin on &sm.
Proof. Let Ego = =N== E for each s [m]. We prove the result for 2, = Ei= Aj by induction on E [m]] The result holds for the base case of s = by assumption. For the inductive case, suppose the result holds for [m -1. Fixing u E RR, we may apply the tower property, our conditional sub-Gaussianity assumption, and our inductive hypothesis in turn to conclude
E eepp( KE X))+ sot1l E exp( (u, - (E5,) ( A Egol]
L u Ku) s exp م
exp((( (u,
E j=1 |[}
exp
Ku).
Hence, Es41 is (K, (Ej=1 03) - Gauu-Sssan on Eg++1, and the proof is complete.
B. Proof of Tab. 1: Sub-Gaussian Thinning Examples
This section provides supplementary details for each of the sub-Gaussian thinning algorithms of Tab. 1.
B.1. SUBSAMPLING
B.1.1. PROOF OF PROP. 1: QUALITY UNIFORM SUBSAMPLING
We begin by computing the first and second moments of Pour E 1'(poul
Pin and
E Peon Puol
diag(Pm)
(PuPii
Ai diag(Pm))
fla - ni
diag(P..) +
neal mon 1) PinP
Ria Ria 1)
neat
Hence,
EMMDD (Pm. Poml)
Pid Kpm
2p KF Poun] + E(pTT Kpoul = tr(KKt
PownP - pit Kpm.
Min
(tr diag(P..) (P..)) P KP.) = 1
Rin Yea OOK
(19)
nes
Dio
To derive the second advertised result, we note that
E K (Pm Pown) 12 z maxiez [e, K(pm. - Pom))) max EM Kejpl (Pm Pou)]
and invoke the initial result (19) to conclude.
14

---

Low-Rank Thinning
B.1.2. SUB-GAUSSIANITY OF SUBSAMPLING
Proposition B.1 Gaus-aaus of uniform subsampling). For any SPSD K R"x", uniform subsampling (without -usuuuaaaunsi replacement) is (K, 1/ -)- Gaussian thinning algorithm with
Voa
Proof. Fix any vector E R", and let Ji...., , Inn be the random indices in [n]] selected by uniform subsampling. Since u (Pmm Pour) = 1 Ei=l u ((mm eJ,) is an average of mean-centered scalars drawn without replacement and satisfying
Ku with probability n KeJ, S Vu Kuy Kt,ye),Ker Kes, V K max Vu
by Cauchy- wchha,,, Thm. and equations (1.8) and (4.16) of Hoeffding (1963) imply that
Elexp(u K(p Pour) ))] S exp(
K
|maxx
u Ku).
2nma
B.2. (H)
Algorithm B.1: KH) Kernel Halving with simplified swapping thresholds and failure probability 6/2
Input: point sequence Nim (2.) with even Yi. kernel
((1), (2(2) + O: Vu + 0 E Hk
Initialize empty coresets: (()), s((2) // Max function norm so far
, have size after round
Umax. +
for 1 1.2,.... m2m2 do
// Construct keree difference function using next two points
x²) <- (æ2:-1- 1, a2:): <- k( k( :); T/ -1
// Compute swapping threshold a; b? 02=11 f x) +<a'' x x2)-22(zz, bmax, max(b,, 0max.e-1) <- 6,bmax, log 0))
// Compute RKHS inner product (v:,1, which has simple form 0, シド (k( x) - k(æ,, x²)) - Exs (k(z, x) 1(2,
// Assign one point to each coreset after probabilistic swapping
(x, x') + (x' and Y7 f-1 with probability min(1, [1 21 )+) (0)_ .pppend(x): s(2) append(a'); W/ 1 + neft 11 1/ = E(es))k(ad.)) -
end
return Xos $ 5(), coresct of size Dou Tim/2
In this section, analyze ( (Alg. B. variant of the Kernel Halving algorithm (Dwivedi & Mackey, 2024, Alg. 2) with simplified swapping thresholds. Prop. B.2, proved in App. B.2.1, establishes the uub-Gaussianity of KH()) and its intermediate iterates.
Proposition B.2 Gaussiausianyty of (H())). Suppose ni 2 2. the notation of Alg. B.l, on common event & of probability at least 8/2, for all i E [nm./]], 24 1/ is (k, vi)-sub-Garr sub-Gaussian with
P/ imax,
(lgg(2n./8)
max MMDx(6m 8w2))
1ogg(2m./5) 18)
maxjeld MMDx ,,00))))
2i
/ /lg((2n//)) min miin(max
k(( maX MMD (m))
Prop. B.2 and the triangle inequality imply that (I' Pour ) Tin
Vnna2 is (k, 2) -us---uuuss-saaa & with
(log(2mm//)) (6 min (maxExx. v(( maxxex, MMDx(6, Pin)).
= b maxxmaa/ ma/ /2
15

---

Low-Rank Thinning
By Lem. A.I, we thus have that the (H()) output Pmn PPout (K, -aub--asnaaas on for K generated by k and that (H()) (K).
B.2.1. PROOF OF PROP. B.2: SUB-GAUSSIANITY OF (H
We begin by studying the sub-Gaussian properties of a related algorithm, the self-balancing Hilbert walk (SBHW) of Dwivedi & Mackey (2024, Alg. 3). By Dwivedi & Mackey (2024, Thm. 3()), when the SBHW is run on the RKHS H4 with the same ft and a, sequences employed in (H()), the output ih of each round is o......b-Gauusiiii for
a and
o + I بي of (I - 20:)) 2i2 1.
(20)
The following lemma bounds the growth of the uub-Gaussian constants o, in terms of the swapping thresholds a, Lemma B.1 (Growth of SBHW aub-Gaussian constants). For each i, the SBHW sub Gaussian constants (20) satisfy
of S G for C; f max]e[] max(b3,r;) r3) and a
a² 2a.-b? 2a, bmax.
a?
Proof. We will prove the result by induction on i.
Base case. of b bf S C1 as desired.
Inductive case. Suppose of-1 C.-1. Then of g(0ž-1) for g(x) 1- bi/r; for r; and 1 for x >> rú. If /2/r; 2 0, then g is increasing and its maximum value over [0, cj] is at c,. If, on the other hand, 1 - 6/ /r; < 0, then first decreases and then increases so its maximum value over [0, ci] is either at 0 or at C.. Since 2 max(r;; 1-1), of < max(g(0), g(c;)) = max(b? c.) = The proof is complete.
62(1 - x/rs)+- Note that the slope of g is
Invoking Lem. B.I, the assumption Rin 2 2, and the fact that 5 + (og(2/8) is increasing on (0, 1J. we find that 12g(2/8)
of < 62 max,i log(2mmm /0) /2) S 6% max, log(2n ( +)o(())) 2(log(4))
(21)
2(1og(mm,/0)))
The first inequality in (21) and the definition (20) further imply that + log(2n) (6)) 2 o,bay logg(2nn//))) 2 o.-ib. log (0)
a 6, bab
Hence, by Dwivedi & Mackey (2024, Thm. 3(ii)), for each i [Mma/2], the vector 8. of KH coincides with the vector ;) of SBHW on a common event of probability at least 8/2. Therefore, each 1 1/s (k, La..)-sb--Gausse Gaussian on E, implying the result.
2;
B.3. (K)
In this section, we analyze LKH()) (Alg. B.2), the Kernel Halving algorithm of (Dwivedi Mackey, 2024, Alg. 2) with linear kernel, k(2, y) (z, y). on Ra and failure probability 8/2. Notably, Alg. B.2 can be carried out in only O(nd) time thanks the linear kernel structure. Prop. B.3, proved in App. B.3.1, establishes the sub-Gaussianity of LKH(() and its intermediate iterates.
Proposition B.3 (Sub-Gaussianity of LKH(8)). Suppose Pim 2 2. In the notation of Alg. B.2, on a common event & of probability least 5/2, for all i [mm/2], 2 is (k, Gaasssinnn with k( y) (xx, y) and
[2 [lo(m.. / 2)+ 1)/5)
maxje(1) [22-1 xzjlle l|2
21
(loganan.ooooaaaalllllllallalaaa 2)+ 1)/5)
2 miiinmmmxa.
|| max || z. l2) for i Eme da-
2
Prop. B.3 and the triangle inequality imply that (P'm - Pour )kor) = 1 Unn/12 12 is (k, -ub-suss---aaa Gaussian on E with
(1og(n maxje(ma/2) | 222i112
v
Log(2nm (lgggnnn 2 min (maXxeX.
| max || 12--1p x x122)
for a 1 Tie
Exex, 5z.
16

---

Low-Rank Thinning
Algorithm B.2: (8): Kernel Halving with linear kernel and failure probability 5/2
Input: point sequence Am (2:)22) with even Pin and æ; R
((1), s(44) f- + tu 0 R
// Initialize emply coresets: S S(22) have size after round Keep track sub- Gaussian constant
du +0
R for i Ra, do
// Consider two points
(æ. x/) c (#22-1, #23);
7/
// Compute swapping threshold
6? = (ar x', x'):
6;
(2)))11
(a:,0:) + get swap parans 10,-1, b;,
// Compute inner product
0; (vi-1,
// Assign one point to each coreset after probabilistic swapping
x²) + (x',x) and T) +-1 with probability min(1, 2 3. ())+)
(()) append(x)); ( appendd(x);; Ve t wh-1 + n.f.
end
return Aet A st), coreset of size Yea = Tum/
function get.swap.params bo,
max(brr/2ogg(//0), a² f ( /
return (a)
By Lem. A.I, thus have that the LKH(6) output Pm -Pout is -Bb.V)-Gu-Guussii & for K generated by k and that LKH(8) E (K.)
B.3.1. PROOF OF PROP. B.3: SUE-GAUSSIANITY OF LKH(6)
We begin by studying the sub-Gaussian properties of a related algorithm, the self-balancing Hilbert walk (SBHW) of Dwivedi Mackey (2024, Alg. 3). By Dwivedi Mackey (2024, Thm. 3()), when the SBHW run on the RKHS Hi with the same fi and a sequences employed LKH(0), the output v of each round is (k, (.)--ub-Gauusian Moreover, since
a; 2 0,-1,, 2,g (2/0.) for each E [mm]
Dwivedi & Mackey (2024, Thm. 3(ii)) implies that, for each i E /2, the vector iy of LKH(8) coincides with the vector v/s of SBHW on common event & of probability at least 1 5/2. Therefore, each 1 2: 55 is (k, de)--:uu-Gaaa sub-aGaaaans
on E. Finally, Dwivedi & Mackey (2024, (46)) shows that a; S M4 for each i E /2i/2),, yielding the result.
B.4. RKH(()
Algorithm B.3: (KH( Repeated KH
Input: point sequence Xim (ax, Mi kernel k, output size Nou Tim 2
// Repeatedly divide coreset size in half
log, (Nim/ PPin/nose (ows)
for 1, ...,... do Xmm (H(6f/))(2,) k) return X... Xm. coreset of size Thasr Thin /
In this section, we analyze repeated KH()) (RKH(Ø), Alg. B.3), variant of the KT-SPIIT algorithm (Dwivedi & Mackey, 2024, Alg. la) with simplified swapping thresholds. Our next result, proved in App. B.4.1, establishes the sub-Gaussianity of (5).
17

---

Low-Rank Thinning
Algorithm B.4: KH- CH-COMPRESS(E):: Compress with KH halving and failure probability 8
Input: point sequence Am (i=))=), kernel k, Rour Vnn 2
< logg (Nom/ Vni)
I/ identify compression level
function compress (S): [S] = then return S
Partition S into arbitrary subsequences {Si) each size |S]/4
for = 1, 2, 4 do
S, compress (S.)
return coresets of size 2
end
+ CONCATENATEES S2, Ss, 8 2 return KH
vSS
coresct of size E || coresct of size 2 V
Big 10 (los, ni pu)-))0 (5,,k
return compress (Ain)
|| coresct of size Neut 2 Tin
Proposition B.4 Suub-Gausianity of RKH( nou 2 then RKH(6) (Alg. B.3) is (k, -)suu-Gaasss with
3 V log( Green log, Cogg(Ma//aas min(max v /(xx x)) max (M,
2
on an event & of probability at least 1 - 0/2.
By Lem. A.1, we thus have that the RKH(5) output Pin Pout D)- Gaussian on & for K generated by and that RKH()) E (K)) Finally, O /oonn/n/// /6) when Nout 2 Vin-
Than
B.4.1. PROOF OF PROP. B.4: GUUSSAUSIY OF RKH(5)
Let 2 minnmax v /a x), ma MMD (6 Pin),, and, for each E [m]] let 300 represent the vector /2 produced at the end of the f-th call to KH(8). By the proof of Prop. B.2 and the union bound, event & of probability at least 1 - 5/2, (eEm)) = (15(0) (EE()) where each 2 w0(0 is (k, (ul))-sub-Gauusian given ((50)))E(e-1) for
v10 C.V Vlog (ong (2
nial /
Hence, on E, the weighted sum
(Pin Pom)) Eee(m]] 2f-1 (500)
Eeg(mi
2/-1 w0(0)
(k, v Exefmn (ul0))2)-sub suauasiaaub Gaussian by Dwivedi & Mackey (2024, Lem. 14). Finally, by Dwivedi Mackey (2024,
Eq. (63)), v Exe(m (v(0)2 Sv. v.
B.5. KH-COMPRESS(0)
In this section, we analyze KH-COMPRESS(6) (Alg. B.4), variant of the KT-SPLI--COPPEESS algorithm (Shetty et al., 2022, Ex. 3) with simplified swapping thresholds.
Proposition B.5 (Sub-Gausiaanity of KH-COMPRESS(O). If Nout E VTm 2 then KH-COMPRESS($) (Alg. B.4) (k, ---sub--Cuuuu Gaussian with
Toot V logz(nout) log( 4rae loga (nan (nau) maX x(
on an event & of probability at least 1 5/2.
Proof. Since the original Kernel Halving algorithm Dwivedi & Mackey (2024, Alg. 2) is equal to the KT-SPLIT al- gorithm of Dwivedi & Mackey (2024, Alg. la) with m = halving round, KH-COMPRESS(0 is simply the KT-SPLIT- COMPRESS algorithm of (Shetty et al., 2022, Ex. 3) with KH()) of Alg. B. substituted for KT-SPLIT m 1). The
18

---

Low-Rank Thinning
result now follows immediately from the (H sub-Gaussian constant of Prop. B.2 and the argument of Shetty et al. (2022, Rem. 2, Ex. 3).
Prop. B.5 and Lem. A.1 imply that KH- KH-COMPRESS(O) E (KK) for any kernel k that generates K. In addition, O V [ogg(eo)) log(tea// (6) when Toout 2 Min- Furthermore, Shetty et al. (2022, Rem. 1) implies that KH-COMPRESS(()) has Vin-
runtime less than 40+1 nm (7 - g) 4n logg(nin/ (/an///nnn nout O( when Rout
B.6. GS-THIN
The section introduces and analyzes the Gram-Schmice Thinning algorithm (GS-THIN, Alg. B.5). GS-THIN repeatedly divides input sequence in half using. GS-HALVE (Alg. B.6), symmetrized and kernelized version of the Gram- Schmidt (GS) Walk of Bansal et al. (2018). We will present two different implementations of GS-HALVE: quartic-time implementation (Alg, B.6) based on the GS Walk description of Bansal et al. (2018) and cubic-time implementation based on local updates to the matrix inverse (Alg. B.7). While both the algorithms lead to the same output given the same source of randomness, we present the original implementation" for conceptual clarity and the optimized implementation for improved runtime. Throughout, for matrix Q and vector u. we use the notation QIxx and ur to represent the submatrix (Qi))ez.Jee and subvector (u.)EE.
Algorithm B.5: GS-TIIN: Gram-Schmidt Thinning
Input: point sequence Xim = (2 kernel k, output size Thom T2//2", HALVE (GS-HALVE, GS-HALLE-CUBII)
// Repeatedly divide coreset size in half
logg (Mm//icus)
for 1, ........ ..... m do Xi, < (A,, k):
return Xour & Xm. coreset of Tlaur T2a/2"
Our first result, proved in App. B. shows that GS- GS-THIN is sub-Gaussian thinning algorithm. Proposition B.6 (GS-THIN Sub-Sausia. For K generated by k, GS-THIN (Alg. B.5) is (K, v. OJssubGGanssian thinning algorithm with parameter
1
P
2
||| mas
(22)
Thoat
Our second result, proved in App. B.6.2, shows that GS-THIN with the GS-HALVE implementation has ( runtime. Proposition B.7 (Runtime of GS-THIN with GS-HALVE). The runtime of GS-THIN with implementation GS- CS-HALVE (Alg. B.6) is (-
Our third result, proved in App. B.6.3, establishes the equivalence between GS-HALVE and GS-HALYE-CURIL More precisely, we show that the sequence of partial assignment vectors generated by kernel-gs kernel.gs.walk (-) of Alg. B.6 and kerrel.gs wa wtu.ilccuubccoo (+) of Alg. B.7 are identical given identical inputs, invertible induced kernel matrix, and an identical source of randomness.
Proposition B.8 (Agreement of GS-HALYE and GS-HALNE-CURIC) Lel 21, be the fractional assignment sequence generated by keznel.gs.walk, ((x) ) in Alg. B.6 and z z',... ... be the fractional assignment sequence generated by wwrneelgg..wal..crl
(m)) in Alg. B.7 with an identical source of randomness. If the pairwise
difference mairix
(k(zz)-1, 12,-1 + k(22, k(12-1,22;) ((z2),
is positive definite, then 2, = for all t.
Our fourth result, proved in App. B.6.4, shows that GS-THIN with the GS-HALVE-CUBIC implementation has (( runtime.
Proposition B.9 (Runtime of GS-THIN with CS-HALYE-CUBIC) The runtime of GGSTTHIN with implementation GS- HALVE-CUBIC (Alg. B.7) is (
Towards making this equivalence clear, Alg. B.6 has been expressed with the same variables that Alg. B.7 uses. Alg. B.6 can he slightly simplified if were be considered independently.
19

---

Low-Rank Thinning
Algorithm b.6: GS-HALVE: Gram-Schmidt Halving
Input: point sequence Xn = (mx) with even Rim, kernel
Xom 0 // Initialize empty coreset
// Select one point keep from each consecutive pair using kemelized GS Walk
x f kernel.gs.walk. (Ain)
for = Rim. do
if then appeaapen))
else
You appen((((()
end
end
return You, coresct size /
function kernel.gs.a ww ( (x:))
+ 1; Zt + (0, O, ......00 0) E R
Initialize fractional assignment vector // Initialize set of active coordinates
A (inn
p~A A
// Select pivot uniformly random
while Zt $ {+13"m/² do A' --A min (fi [ma/2]
13 ((m=/2) A))}
// Update
of active coordinates by removing smallest index set 1:
p & A'' then p' ~ Unif(AA) // Select new pivot from A'' uniformly at random
else end
p' tp
// Compute step direction in which to update fractional assignment vector
W: argmin, ge 22 u Qu subject u 1 and u, 0 for all i A''
where R (2 (x,,)/ has entries Q; & ((22x1,,22)-1) k(r2,, 323) k(xx< 1, ((222,
{5 R:: 21 + Su: E [11, |1]m+1|
8 mmax A and 8' + [min A), where
// Select candidate step sizes // Choose step size and sign random
+- 5+ with probability 5 /(8* + 8-); otherwise 8-8
Z++1 f- z: 6,44 // Update fractional assignments
f + 1+ A A': --
end
return 2:, sign vector in 1
20

---

Low-Rank Thinning
Algorithm B.7: HLLLA--LE-UIICCC Gram-Schmidt Halving with cubie runtime
Input: point sequence A (z:) with even Rin, kernel with positive definite k(>a, Ai)
Xem // Initialize empty coreset
// Select point keep from each consecutive pair using kemeliizdd GS Walk
f kernel_gs_wa lk_cubic (Akm)
for = 1, Tim / do
if 2; then
Yon append
else
X. an.aapeen((2))
end
end
return Neus coresel size /
function wernel.gs.walk.cube....... (x:))
+ 2: < (..0......) E RT
Initialize fractional assignment vector
A [
Initialize set active coordinates
A
// Select pivot uniformly random
Q + (k(122-1, 12)-1 + k(221, k(r21-1, T25) ((T21,
// Form paired difference kernel matrix
C + (Q)) )-1
while 2t (+1) min do
A' min (fi E [mm/2]] |z. 13 [2m..2] A))}
// Update of active coordinates by removing smallest index set 111
p E A'' then
p' Unif(AA) // Select new pivot from A' uniformly at random
elsc
p' xp
end
Ai
- A {p} A
A' (p')
Ai Ao Choose i the (unique) index was removed from active coordinates
Compute (QAzXA2)* using block matrix inversion and the Sherman-Morrison formula
+ CA5XA2
C D-
DQ (
Select candidate step sizes // Compute step direction in which update fractional assignment vector Compute u, (u=)Az
(Q'))((p)) Uhy 1, and the for & A''
8+ + max A and 8- <- Imin AJ, where {ō E RR z, + 8u, E [-1,,+1] +1
+ 8t with probability 8 /(8* + 6-); otherwise ó, + -8- Choose step size and sign random Z141 + z: + d.ue // Update fractional assignments
f + t 1: A A'; p
end
return 2,, sign vector in (+13/a/2
21

---

Low-Rank Thinning
B.6.1. PROOF OF PROP. B.6: GHIN SUB-GAUSSIANITY
Our first lemma bounds the Gub-Gaussian constant of GS-HALVE (Alg. B.6).
Lemma B.2 (GS-HALVE sub- aub-Gaussianity), In the notation Def. consider the input and output vectors Pmn Pout E" of HAL-- (Alg. B.6) for X' 2 Xm with [X] 2 Tin-
K k(X, X), then Pin
Pout is (K, sub--Gaaassii with
2
K 1/2
Proof. Since is SPSD, there exists a matrix o E Raxd such that K = $ T. Let Rdx be the matrix with entries
2 121-1. 2is for i [ and E [d].
Note that, for each i E [Min/2]
Eje(g B K2i 1,21-1 K - 22 S
max-
1 BN is (I, sub- susb-----Guuussin Gaussian where I the identity matrix in Rdddd Hence, by Harshaw et al. (2024, Thm. 6.6), nn
Now fix any Rd. Since
1Bz
T T Pout) by construction,
Thn
E[exp(u u K(Pin Pou))]
S E exp (-( u, Min B2)) S exp (0ppp51 15..TTul33 =exp =xx(($ T..uK
Now, for l E [m], let Ps E Rn denote the output probability vector produced by the f-th call to GS-HALVE. Defining
Po 2 Pm and Pow 2 pms we have
Pin Pont
Σm ===1 Di
for A P P. for i [m].
2/12///2
By Lem. B.2, each Pi-1 P; is (K,
conditional on (Ai Ai-1). Applying Lem. A.3 to the
nn/21-1
sequence (A:) we find that Pin Pout is (K, (K, (K), Gauu--aa with parameter
V
E)=
K|| Imax (ma/2) 21/2
|||
1/2
[E 45
m
K
1/2
1
4m
Simplifying the above using the fact that Noom
72m/2 yields our desired result (22).
B.6.2. PROOF OF PROP. B.7: RUNTIME OF GS-THIN WITH GS-HALVE
We essentially reproduce the argument from Bansal et al. (2018) for the runtime of the GS-HALVE algorithm in kernelized context.
The main computational cost of GS-HALVE the execution of the kernel saernel_gs_wer _gs_wallll (-) subroutine in Alg. B.6. The number of iterations in while loop for 2, is at most nm. 22 This is due to the fact that in each iteration, at least one new variable set to {+1). Further, each iteration, the main computational cost is the computation of
argmin /ER" argmin,cRR*./2 u Qu
under the constraints that up = 1 and u, = for all & A. Since this can be implemented in ( time using standard convex optimization techniques, HALLE has total runtime
ra(e) < Ce*
for an input sequence of size and a constant C independent of Now, note that GS- GS-THIN calls GS- GS-HALVE iteratively on inputs of size n for i 0, 1,...,m. mm where m loga noau/ Thus, GS-THIN has runtime
mn rn /n(mm// (2mmm///)) E m-1
E C(naa /2 (m
22

---

Low-Rank Thinning
B.6.3. PROOF OF PROP. B.8: AGREEMENT OF GS-HALVE AND CS-HALVE-CURIC
We want reason that any round of partial coloring leads to the same output across the two algorithms. Fix any fractional assignment update round. Recall that Ai AA(p) and A2 A' \ {p/}. These represent the active set coordinates without the pivot before and after the update respectively.
The main difference between Algs. B.6 and B.7 is in the computation of the step direction uy which is the solution of the program
< argmin u Qu
Tuuu
subject to uy and u, = 0 for all i i A'.
Wr has closed form with entries
(u))Az - (QA2xA2) QAxx(=')-
Note that the invertibility of QAxxA follows from the positive-defimitnnss of Q, as, for any E IR/
QA2xA, w Qu
for second vector t with i A, and all other entries equal Therefore, compute uy it suffices to keep track of the inverse of A2 as A' across iterations.
Let i be the unique element in Ai Ag. Writing QAxxA, in block form, we have
QAAxx (1)xxA2
QAxxa
QAIXAL
Q
By block matrix inversion (see, e.g,, Saadetoglu & Dinsev, 2023, Thm. 2), the leading size [Ag] x |Az principal submatrix of (QAiXA))-
equals
D A QAAxAA= (12x(1) 9
Qa
Thus, by the therman-Morisse formula (Sherman & Morrison, 1950),
(QAxaa))- ID-1+
Q(xxa) Qui
)
to D Qn Q DQA2xt0"
(23)
Hence, we already have access to matrix C = (QAixA,)) we can compute D by dropping the row and column of corresponding to i and then compute (Q.A)xAs)= using (23). Since in Alg. B.7 we begin by explicitly computing the inverse of Q,''x the update step in Alg. B.7 maintains the required inverse and thus its partial assignment updates match those of Alg. B.6.
B.6.4. PROOF OF PROP. B.9: RUNTIME OF GS-THIN WITH GS-HALYE-CURIC
We begin by establishing the runtime of kernel gs walk cubic(+).
Lemma B.3 (Running time of kernel gs walk cubic(.) ). The routine kernel gs walk cubic (.) runs in ((1)) time given a point sequence of size
Proof. First, the initialization of C costs O(E3) time using standard matrix inversion algorithms. Second, the number of iterations the while loop at most 6/2 since, in each iteration, at least one new variable is assigned a permanent sign in [+1]. In each while loop iteration, the main computational costs are the update of C and the computation of the step direction u. both of which cost ((2)) time using standard matrix- vector multiplication. Hence, together, all while loop iterations cost (E33 time.
Given the above lemma, we have that CGS-HAIYE-CUBIE, on input of size f, has running time
(e(()= s Ce3
for some C independent of l. When used GS-TIHNN this yields the runtime E rn (n(mm//2 /2 < E = C(naa /2// (mg))
23

---

Low-Rank Thinning
Algorithm B.8: GS-COMPRESS: Compress with USS-HALVE-UURE halving
Input: point sequence Xin (a:; (=)))=) kernel k, nout v Amm 2
g + ( (m))
identify compression level
function compress (S): if [S] 49 then return S
Partition S into four arbitrary subsequences (8:) each of size |S|/4 for 1, do
S. compress (S.)
I/ return coresets of size 2
15]
end
S &,, (S-HAALE-CUuic((5.k)
2
VSS
II coreset of size f
|/ coreset of size 2 V
return compress (Ak,)
// coreset of size
2 /Tnn
B.7. COMCORSSSSS
This section introduces and analyzes the new GS-COMPRESS algorithm (Alg. B.8) which combines the COMPRESS meta- algorithm of Shetty et al. (2022) with the GS-HALVE-CUBIC halving algorithm (Alg. B.7), The following result bounds the Lub-Gaussian constant and runtime of GS- COMPRESS.
Proposition B.10 (GS-COMPRESS sub-Gaussianity and runtime). If K is generated by k, then CS-CCOPRESS is (K, v, Sub-b--suubuu (o--su--Gausann Gaussian with
logg oou)
K
Whott
maxe
Moreover, GS-COMPERR CS-COMPRESS has (m rantime.
Proof. By Lem. B.2 and Prop. B.8, GS-HALVE-CUBICI is (K, (((O)-ssb-Gaussiiin for an input point sequence of size ! and (f) 2 2 mmax/f. Hence, by Lem. A.2, GS-HALYE-CURLE is also uH (?) f-sub-Gaussian in the sense of Shetty al. (2022, Def. 2) for each Hk. By Shetty et al. (2022, Rmk. 2), CS-COMPRESS is therefore Gaubsia with parameter
S Vlogz (Nin/ Nem p1 (2 S / /log2 (Mout)
K
max
Muui
for each f E Hx. Hence, Lem. A.1 implies that CS-COMPRESS is (K, 1/ Sub--Gaasna Gaussian thinning algorithm. Furthermore, Shetty et al. (2022, Thm. 1) implies that GS-COMPRESS has runtime of
Eloga(mu (2mon)) 4 "2n
where the HAL-H--LL--ULEEEEE runtime (f()) S CB for C independent of the input size by Lem. B.3. Therefore, the GS CS-COMPRESS runtime is bounded by
log, (ma/ (2naa)) 48 (2 Eis0
32 32
(
Remark 1 (COMPRESS with GS-HALVE). the CS-HALVE implementation used in place of GS-HAIVE-CURIC, parallel reasoning would yield an (mn runtime for GS-COMPRESS.
C. Proof of Thm. 1: Low-rank sub-Gaussian thinning
We establish the MMD bound (2) in App. C.I, the first kernel max seminorm bound (3) in App. C.2, and the Lipschitz kernel max seminorm bound (4) in App. C.3. Throughout, we use the notation Pe(E") A P(E,E") E') for events (E,E²).
24

---

Low-Rank Thinning
C.I. Proof of MMD bound (2)
Without loss of generality, we suppose that S rank(K). Let VAVT be eigendecomposition of K with orthonormal
V E R and diagonal A diag(A).".. ; An) R=x". Let V, represent the first columns of V, and let V-r
represent the last n columns of V. Introduce the shorthand
w _ Pin Pout E l and 4 - V E @Rax
(24)
We can directly verify that
VV -V= VV -VV, + V_,VI,
and K = 4b
(25)
Using the above equalities, we decompose the squared MMD into two components,
MMD (Pm Pomn
Kw w
o w w VVV + w w VV,
w + w T -V-,VV VT VV
V +
w + |V_ 1b w 3
(26)
In Apps. C.1.1 and C.1.2 respectively, we will establish the bounds
P( + w S ev²(er + (1/8)))))))))))) 2 6/2 - 8 and
(27)
P T w S Ar+1 1)) 1,
(28)
which when combined with (26) yield the advertised claim (2) on the squared MMD.
1.1. PROOF OF (27): BOUNDING V i "wl2
Our first lemma bounds the Euclidean norm of a vector in terms of a finite number of inner products.
Lemma C.1 (Euclidean norm cover). For any v E R' and s E (0,1),
||al| S - maxnec., (u, v)
(29)
for set Ce,r contained in the ball B with Ce,rl $ + 2/e)-.
Proof. Fix any E (0, 1), and let Ce,r be set of minimum cardinality satisfying
Ce. C B and suPugar minweec..- ||u - u'll2 S.
By Wainwright (2019, Lem. 5.2), |C,rl I (1 + 2/e)". Now we invoke the variational representation of ||:Il2 and the Cauchy-Schwarz inequality to conclude that
|| suP (u, v) sup min EC.,, (u (uu w', + v
< supwear minweec., 1|u u' w/||a||w/ll + maxw (u', v)
$ e||o||a + max (u', v).
Rearranging terms yields the claimed bound (29).
Our next lemma uses this covering estimate bound the exponential moments of V., &b wwl2. Lemma C.2 (Norm sub-Gausianitty. For any >> and any
Es [ex(((( V Twll2)] < (1+ zy exp 2(1
Proof. Fix any t > 0. Since a + exp(tar) is increasing, Lem. C.I implies that Ec[exp(!|| V T T "w]l2)] < Ee(exp(t= + maxuec (u, V x w))]
Ee [maxueCe,r exp - (V, u, $ T w))]
< Emec., Es Ex|exp( - (V, & [w)]]
25

---

Low-Rank Thinning
for subset Ce.r with |C,,rl S (1 2 and |ul22 for each Ce.r-
Now fix any E Cg.r and let A, diag( A1, ...... Ar). Using (24) and (25), we have
V, 4 V, 1/2 and therefore
(V,u, $ w) ( V / u. +b w) = (V,A, Kw))
1/2
In addition, we have
(V,,, "(V,' = = 1
V, 1/2 u uuu.
Next, we can invoke our sub-Gaussianity assumption (Def. 3) to conclude that
2², Eelexp(r-s (V, & T w))] Ee (Beeexp(TE (V.A, (V Kw))] S exp( 2(1-2)=
(V, V.A. 1 u, K.A.A.A. u1)
exp( ( ll.3).
n2t²
Since ||u||2 I and [Ca,rl $ (1 + "r, the advertised result now follows.
By Markov's inequality (Markov, 1884) and Lem. C.2, for any > 0,
F(IVV & wll2 > a) = V + w|12 > a) P( & _ w'lll > a, E9)
V 1 w|12
PPE
s infe>o Eg cxp V + T w|12)\//a/// cxp(ta) + 6/2
S (1 + 2) inl exp(
X[- - (a) + 6/2
(1 y expl (1-e)
+ 8/2.
2/
Next, we have
(1 + 2 exp( -(--))=0² 20
rv2 1 8 if a 1- V (og(}>) + rlogg1 + 2).
Since this bound holds for any choosing = = 1 - 12/e, we find that
| Φ T w133 I ev2 log(1 + 2/ - (2/e))2/e) + log(1/5") s <evê(er + log(1/8')
with probability at least - 6/2 - 8' as claimed.
1.1.2. PROOF OF (28): BOUNDING | w//
Since
w 11 Pin Pin + PouPon 2p Pout
22g
2n
(30)
Vig Plas
Plia
we have, for A., A (Arag(A4+11" '.. An) and Amax the maximum eigenvalue of SPSD matrix,
1 w w T V V_ < Amax V -_
w
(30)
Ap+1
nus
nin
C.2. Proof of kernel max seminorm bound (3)
We begin by establishing general bound on the maximum discrepancy between input and output expectations over collection of test functions admitting finite cover.
Lemma C.3 (Diserepancy cover bound). Fix any kernel k, subset F C. Hyo and scalars and 8' (0, 1). Define
- sup || and By A {f Hk Ilf a),
26

---

Low-Rank Thinning
and let Ce be set of minimum cardinality satisfying
C C BB and ser ming' ma [f(x) - (x))
(31)
If iPin Pon J is (k, - Gau-saas on an event & (Def. A.2), then, on E,
PP Poull = - sup sup F S 2e + va (o with probability least 8'.
Proof. The triangle inequality and the covering property (31) together imply that, with probability 1,
iPin Po Pout) f I min (Pin - Po + [[PPn Pown (J (f- f')l
< |Pnn Pauile,, + men, Pin f¹)l |Pom (f f'1
S ||P Powllc,, + mec max [f(x) s'(x)))
x |[P Pourllc..r + 2
(32)
for each f F. Since e is increasing, the bound (32), the assumed sub- Saab-Guussintty (Def. A.2), and the fact that Cr,F belongs to By imply that
Ee(exp(t||Pnn - Poull Poullyt ( s Es - Foullc,,,))
s Erecr
2 Eexpp(t - )o)
E'ecc. exp( P + 2te) [Ce,Fl |xxp 2 + 2te).
Evva?
Now, by Markov's inequality (Markov, 1884), for any > 0,
Ce.r infe>o exp( PPva"" Pe (Pin Pow)) > + 26) S infezo Re(exp(t[[Pnn Pou [ exp(t(a + +6))
2 ta) [C., exp( 2v (xpp22202
-a?
Finally, choosing a = vay (og C. (18)) yields the desired claim.
Now fix any e 2 0, 8' (0, 1), and kernel k that generates K, and consider the subset J {=k(ar, : Z}. Since [Pin Powt )ou))lz = in IP Puull and sup l| Dz, Lem. C.3 implies that, on the event E,
K(Pmn Pou)ll < 2e + vDr yDgg2log((C.. C..5 with probability at least 1 - 8¹.
Since P(89) < 0/2 and [F] < 2| we use the estimate |Co.=| S 2|Z] with 0 to obtain the advertised bound (3).
C.3. Proof of Lipschitz kernel max seminorm bound (4)
Introduce the query point set A (x; i E). any 8' E (0, 1) and 2o E Z, and define the symmetrized seminorm
(P'm Pou kk 1z,z A supz,z'ez (PP Pour Peu))k(2) (Pmn - P Four kk(z)))
By the triangle inequality and the derivation of App. C.2, we have, on the event E,
[(ppp - 1z S |I(P Pomr)k/ zzz + ((P P Pour )
[T P.m))k] z.z + v /k(20, za) / 22log(4//8)))
with probability least 1 8'/2.
(33)
Since P(E9) < 5/2, it only remains to upper bound [P - Poul ) 2, on E with probability at least - 8' /2/2.
To this end, we first establish that ((Pi - Poan ((=))(()) is a sub-Gaussian process on with respect to a particular
bounded bounded-Hölder metric
Definition C.1 (Sub-Gaussian process on an event), We say an indexed collection of random variables (Xe)see is a Lab-Gaussian process with respect to p on an event & if p a metric O and
(Xo-X)) p(8,8' }
Ee
exp
< for all 0,0' E
27

---

Low-Rank Thinning
Lemma C.4 (Bounded-Höldes sub- Gaussinn process). Consider kernel k on X' I& satisfying [k(z, - x)) S Txxl= z- 22 for all z,z' E 2 C X and E Xm- If (Pin (ou)) is (k, --------aussian
event (Def. A.2), then
((IP - I' (P (z) is sub-Gaussian process on & with respect the metric
x(z,z') a min(ssupes vk(z,2), /2Lx =2
(34)
The proof of Lem. C.4 can be found in App. C.4. Our next lemma, slight modification of Wainwright (2019, Thm. 5.3)). bounds the suprema of symmetrized sub-Gaussian processes event in terms of covering numbers.
Lemma C.5 (Sub- Gaussin process tails). Suppose (Xe) is sub- Gaussian process with respect p on event E, and define the diameter diam((, p) - suee,eree p(0, 0*), the covering number
Nu; O p) & min Cu _ maxage ming EC., p(0, () S 4} for all > 0,
and the entropy integral J (O, p) Jo
Vlog(1 + NN p)) du. Then,
Ps(supo,oree Xg- X 8(J(H, + +)) 2 exp( ( heef/ddammm@.pmm p) for all t> 0.
Proof. Since / Vlo((1 + +xy) < Vlog(( x1 y)) < / /og(11 .)) + Vlo((1 + v) for all 2, > 0, the proof is identical to that of Wainwright (2019, Thm. 5.36) with C1 and (P)) substituted for (E, P).
Our final lemma bounds the diameter, covering numbers, and entropy integral of Z using the metric p.
Lemma C.6 (Covering properties of bounded-Höön Hölder metric). Consider the bounded-Hölder metric p (34) for a kernel k on X' Rd and a finite set Z C X. I is a matrix with one row corresponding to each element of Z, r rank (Z). and R = m || then, in the notation of Lem. C.5,
N(u 2, S <1++2/u2) for c 32 RLL and all 0,
(35)
diam (3.p) s D a min(e, v/ 32 maxxez vk(z,2)), and
(36)
J(2 < DV2r log( D))
Proof. The diameter bound (36) follows directly from the definition of p (34) and the fact max || =z'12 S 2R.
To establish the covering number bound (35), we let U be compact singular value decomposition of Z so that
V Rdxr,
Z ZVVT, and max V =1|2 = m ||
Fix any > 0, and let C and Cext be sets of minimum cardinality satisfying
c (R),,
max min - ull2 2//2
Cen C (R), and max min eC.. || - 2112 < 2/2.
(37)
Since V [BT (R) for each z E Z and Vo' Bd for each of E B", we have
max min Ve' =x112 max min VV V T=)ll1
max mingrec || VT =1|2 S 2/22,
so that VC satisfies the criteria of (37). Since |CC| < C < (1 + 4R/2Y by Wainwright (2019, Lem. 5.2), we must also have |Coal= < (1 (1+44) (R)
Now, since Cost has minimum cardinality amongst sets satisfying (37), for each z' e Cext. there some z Z satisfying ||z 2||2 < e²/ /2 (or else z' would be superfluous). Hence, there exists set Cim 2 satisfying
[Cnll |Cerll < (1 + 4 and max ming'eCu || =|122 S 2
28

---

Low-Rank Thinning
Moreover, by our metric definition (34),
m EC. p(2,z2) S
_ maxxez min || 2'12 S 2VR
2/R
Hence, for
2V7 NV p) Call - (1+ (1 Since O was arbitrary, we have established (35).
Finally, we bound the entropy integral using the inequality S //2 for u E [0, DJ, the concavity of the square-rool function, and Jensen's ' inequality:
p) - So Vlog(1 (1 //())) du S So Vlog(3ce/w2)ddd So" 2rrlog(V33 (v3c/) du
s DDV b 1o 2r log( 3c/u)) du DV 2r log( (ogg/))
Together, Lems. C.4, C.5, and C.6 imply that, in the notation of Lem. C.6,
[I in PPu) klluk 2.2 & 8DV22r log( /Be// D) + 8D /D/g/g(4/8)))
on with probability at least 82/2. Combining this bound with the inequality (33) yields the result.
C.4. Proof of Lem. C.4: Hounded-Höldde sub-Gaussian process Define X₂ (Pi Pou))(() for each = E 2, and any 2, 2. Our sub-Gaussianity assumption implies
Eg [e(exp(A(Xx Xx s exp( 2 k((,,))
k(2', ()))
for all de R.
Moreover, by our Lipschitz assumption,
[k(2,-) -) <(z', (a(=z,-))le 1I k(z, =) k(z, x') 1(2''x'' 2') - k(z',2) I min(4 max4e2 k(z, x), 2L 12 2 z'112).
Finally, Lem. C.7 shows that Eg (exp( ا S 2 that (Xx +EZ is sub-Gaussian process & with respect p.
Lemma C.7 (Squared exponential moment bound). Es (exp (AX)) S exp( x²X²) 2²x)) all R. then Eglexp( 3x2
8uz )] s
2.
Proof. The proof is identical to that in Wainwright (2019, Sec. 2.4) with Eg substituted for E.
D. Proof of Cor. 1: Gaussian MMD of KH
Cor. follows immediately from the following explicit, non-asymptotic bound.
Corollary D.1 (Detailed Gaussian MMD of KH), If Xm Bd( for R then KH(8) with k GAUSS(n). nin (2e)d, and b & delivers
MMD (Pir Pow) S mio log( Aram e² max
[2 log bon) Penoatyd + log((t) +
2 now Meat
Tha
with probability at least 6/2
Proof. Consider the approximate rank parameter
max [ log bo)) (Iene"4/d))
The assumption Thn 2 (2e)d and the fact that b 2 1/(2)) ensure that log (og(Ainnout)) 2 d + log(nomb/22) 2 d and therefore that r** z (2e)d. Hence, by Altschuler et al. (2019, Thm. 3), the (r* + 1)-th eigenvalue of K satisfies
Ar-+1 S nin exp {
max 20 lom(nanmnt me2me (4/d))
Ze max 2 log(
log
$ 1nn expl
< nin (
nemb"
29

---

Low-Rank Thinning
Since
|
max
and (6) Gy (K) with defined in Prop. B.2, the result follows from Thm. 1.
E. Proof of Cor. 2: Intrinsic Gaussian MMD of KH
Assumption E.1 (d* mdn-iiifoldd with Q-smooth atlas (Altschuler et al., 2019, Assum. 1)), Let Rd be a smooth compact manifold without boundary of dimension d' < d. Let (3)ee)m for T N be an atlas for Q where (Uz); are open sets covering Qt and 3 UÚ + (r;() are smooth maps with smooth inverses, mapping bijectively to _d (rz)- Assume that there exists Q > such that supuebs" Bup)eB=(rs)))D D
(rz)
(uu]] S [u))l
Qla for all a E N and j E [T].
where [e| Σ}= Oj and D duj .u.
ge for a E Nd
Cor. follows immediately from the following more detailed result.
Corollary E.1 (Detailed Intrinsic Gaussian MMD of KH). Suppose Xin lies on a manifold Q C Id satisfying As- sump. E.I. Then KH()) with = GAUSS(n) and n = nin delivers
MMD (Pin: Pout) I log( Amae c5 log " (ou)) e (og({)))
1 That
nis
with probability at least 8' for e independent Xm.
Proof. Altschuler al. (2019, Thm. 4) showed that the (r++ 1)-th eigenvalue of K satisfies (7) for constant c iindependent of X' Xin- Since | Imax 1 and KH())= (u( with v defined in Prop. B.2, the result follows from Thm. with r = (log( (Di /c)) 12
F. Proof of Thm. 2: Quality of Thinformer
Throughout will make of the convenient representation
D AV for Iom & e [n] (k,, o2) Nout); À A
(exp(
(g. va
)1 Iaml My and D e Al,. (38)
Our proof makes use of three lemmas. The first, proved in App. F.1, bounds the approximation error for the attention matrix T in terms of the approximation error for AV and A1,,
Lemma F. (Decomposing attention approximation error). In the notation of Alg. I and (38),
[ Av - D-1AV max S min DD -11maxx |({ 11 |I ( A AV|| + I11A,, A1, oz0 |||
The second, proved in App. F.2. bounds the approximation error for AV and A1, in terms of the KMS (1) for specific choice of attention kernel matrix.
Lemma F.2 (KMS bound on attention approximation error). Instantiate the notation of Alg. and (38) and define the query set
X' e (Ditns A (ā. e ) E [m].] [d 1}} where q. q
and ett1 the j-th standard basis vector in Id++1 If Kat e kau 2t o X a x' Xm, then
max ( A)VIl max: _ A ||K Pou))lz for I I In(d 1)].
Our third lemma, proved in App. F.3, bounds the size of key parameters of the thinned attention problem.
Lemma E3 (Thinned attention problem parameters). Instantiate the notation of Lem. F2, and define R A
30

---

Low-Rank Thinning
max max 11 2. (12)) Then, for all i,j I and E supp(Pm).
D) S exp( val
max v (a, x) S exp( 20d
R
|V
+ |
maxt
Rr _ maxier 20 v va +,, DI - maxiez v Katt, S exp( 2
rank XI) S <d+1 for X₃ - laileez and
KKaut Kat,jil S Kan ||, - æ,l12 for Lua - expl
Vi
vd
2
V
max-
Now instantiate the notation of Lem. F.2, and define the coefficient
c 2 32 38 (d 13g(
2) maxx logog(8)( + )
Vd
Together, Lem. F.3, the KMS quality bound of Thm. 1, and the KH-COMPRESS(O..5 sub-Gaussian constant of Prop. B.5 imply that, with probability at least 2.
logg (Mon log(S loga
Pic. must
Kate (Prn Pomn) 11z - 2 exp
I + V
max
Hence, by Lems. F.1 and F.2, with probability at least
logg (Fear) (Srion logg
[ - -
max S
V2
21 exp
Val
VI + I
max
2R cexp
loga (New) log(Sn loga
weat
Pan
F.I Proof of Lem. F.l: Decomposing attention approximation error
By the triangle inequality, have
| -VAV-D--AA max
I DD - -D--V--AVI max + +IĐ-1AV - - maxx
We bound the first term on the right-hand side using the submuliiplicatiityy of the max norm under diagonal rescaling:
D Av - -- --1AV max < | |max
Áv - AV|| = =I( Á - max-
To bound the second term we use the same submultiplicativity property and the fact that each entry of D D-!AV is the average of values in V:
ID-iAV- -D--AV-D-'AV max 1D- AV max S BI mmmax D
D mm
D AV max
< 1 -1I--/Imxx 1 AI1 A max-
identical argument reversing the roles of (D, A) and (D, A) yields the second bound.
F.2 Proof of Lem. F2: KMS bound on attention approximation error
Define the augmented value matrix V
[V,
|| mmax 1,] E dd+1
By the definition of Katt and Å,
KKtt(Pm -Pou) Iz = (xx{e()) Σeejy A Vez (Pm -Padee 21((A A) = 21((A A)V max.
F.3. Proof of Lem. F3: Thinned attention problem parameters
First, by the Cauchy-Schwarz inequality and the nonnegativity of D = A 1n we have
[1 ! D I|mxx minigjn] A.4 Eyen A.
min exp( 19,1214,13 S expl 122
(oiing/nnl.efgg exp( kg
31

---

Low-Rank Thinning
Second, the max v Kate (2e, æ)) inequality follows
Katt (ks, 0;), (ks, ū:)) = exp(
111 + | S expl
V + V
Third, the Ry inequality follows as
( eg )12 Vl0..1 15
R
for all e E [d 11.
Fourth, the Dx inequality follows as
maxiez Katt.ii max exp(
12
exp B
vd
Fifth, the rank inequality follows as 2; E Rd+1 for i E I. Finally, the Lipschitz inequality follows as, for any i, k. E [n]] and j, m E [d + 1].
eepp
(9..k))
(e -i)) exp( (qc.ki)
(emt 01i1
dd
5 exp(
(g. |0ū1 8mml + eepp(
(q (q.
exp(
19 .ki)
)l[mmml
Vd
Vd
vd
Vi S exp(
11q.1l:
1k:ll2
)1le9 u+1 ed+1
10 6iml
+ exp(
max( la. 1..l2.11q. (al.lllaalalalle (a )|
(9.-92. kk)
11m
v2
Vil
v
< exp(
Rd
Ilee
1+1
eut1
10r pim
exp(
R
|1 v lla p0mll
Vi
vd
exp
R²
Ile,
2+1
ed+1
112
V
Immax
exp(
R²
l1a, - q lla
V Imax
Vi
va
S Sexp(
va
R
+
V
max
( (+1)
(āx. e
by the triangle incquality, multiple applications of Cauchy-SShwanee and the mean-value theorem applied to +> e².
G. Proof of Thm. 3: LKH-SGD convergence
Our proof makes use of three intermediate results. The first, inspired by Harvey & Samadi (2014, Thm. 10) and Cooper et al. (2023, Lem. 1), relates the quality the ordering produced by Alg. 2 to the quality of the thinning.
Lemma G.1 (Quality of thinned reordering). The output of thinned reordering (Alg. 2) satisfies
maxje[m] EE a " (0) 112 S maxye[m] EE af ll2 + maxjel EE ,/ an ll + Ei= 2r/12
where oh is the inverse permutaaioon of ah and ntt A 2(1 x E x - 1).
Proof. Fix any j* arlmax
IE o mp (1))2. j S n/2, then
2 2
( (0) ll2 < 2maxjem EE 1 [,t = 1] S maxje(x) IE 2/112 + max 11E n/a2/112
by the triangle incquality. Similarly, if j n/2, then.
2 201 x " 2 (0))l2 || aflle) s 2 It oh (0 (1) l12 S maxje(n) EE 1n1 = -1]] 1| 112
s max I at 12 + max ||- /f
The second, a mild adaptation of Cooper et al. (2023, Thms. 2 and 3), bounds the convergence rate of SGD with thinned reordering in terms of the thinning quality.
32

---

Low-Rank Thinning
Theorem G.1 (Convergence of SGD with thinned reordering). Suppose that, for all i [n]] and w, Rd.
[V)((w> - Vf(w)ll S o² and IVf((w) - V)i(())l2 S Lilw v/12
and that SGD (10) with thinned reordering (Alg. 2) satisfies the prefix discrepancy bound |
maxje(n] EE= V. ax [|2 S 2A max
1² for of - 2(1 [a E X 1), x* A - xt (39)
and each epoch l [K]. Then the step size setting
1/3
4F = 16L(2n+A)' 12L2"=AAPkK +
with Fi a f(w1) - and f - inf f(0)
18
yields the convergence bound
K [ 9(F Ay (72F) (oool////44488 L(2+A/(n))
(nK)a/a
If. in addition, f satisfies the u-Polyak-Lojassiwviis (PL) condition,
p(f(w) - f*) s / for all w Rd.
and the number of epochs satisfies
K2 10 1 A/n)W for W W W and a (Fi+o*/L)e
22
where Wo denotes the Lambert W fanction, then the step size setting
20 Knp
yields the convergence bound
f(wk) - ff (mX)² (nky (FL++12))
2 43
+
Proof. The proof is identical to that of Cooper et al. (2023, Thms. 2 and 3) with m = 1 worker once each instance of || replaced with 11. each instance of T, is replaced with I,, each instance of 7 is replaced with K, and Lem. G. substituted for Cooper et al. (2023, Lem. 1).
The final result uses Thm. to bound the prefix discrepancy of (K) Lemma G.2 (8) prefix discrepancy). Fix any epoch k [K]. With probability least 8', thinned reordering (Alg. 2) with LKH(6) satisfies the prefix discrepancy bound (39) with
= /og/( 2n(login/2)+1)) [e2 ranke, (X*) + 10c log( []]
for x A
x ck A maxie(n)
De 1ng(2n lo 22/88) log(n//""] la and a A En x...
V/
Proof. Define x = (ot,... x J maxxen[ ||at - x* 12. and = ranke, (X*). ). For any j [n]], we can write
EE 1/ a = | at Ei=1 lank
X ao || = (x (T - Pumil12 2 = 2j MMDxx (Pi Plan)
where pi,, and p'u are the empirical distributions over Ath = (ar ) and X {at E 2 i [i]].
Since (KH(O)) is an online algorithm that assigns signs (nt: 1/411 = v/(²) to the points (xef; aft1) sequentially, we can view X-h the output of LKH()) applied to Ahe with Nou = and the linear kernel k(æ, y) (x, y) for each j E [n]] Therefore, we may invoke the established LKH(8) sub-Gaussian constants v of Prop. B.3, Thm. 1, the union bound, and
the definition of c-rank (Def. 4) to deduce that
maxjelm] E 1/ a maxxein] 452 [e2r + elog(#)] + +,,11(X A
with probability at least
-8'
8'.
Thm. 3 now follows directly from Thm. G.1 and Lem. G.2 applied to LKH epochs.
with 8 = 4k and a union bound over 1 2R
33

---

Low-Rank Thinning
H. KT- (TT-COMPRESS())
We describe the thinning algorithm KT-COMPRESS(Ó) used Alg. We use KH for every halving round except for the last round, which thins point sequence of size 2n to nour- For this final halving round we use KH- (H-REFINE(O) (Alg. H.1) derived from the KT-SWAP algorithm of Dwivedi & Mackey (2024, Alg. lb). The refinement stage of Alg. H.1 greedily improves the MMD of the initial (H output. Hence, MMD (Xmm Xea) I MMMD S()) with probability 1.
Algorithm H.1: KH-REFINE(()- KH with greedy refinement (Dwivedi & Mackey, 2024, Alg. la)
Input: point sequence Vin (xx))_),, kernel k, input size rin E 2N
+ (Ai, k); nour n2n
// Swap out each point in Xom for the best alternative in Xin Nou f- S.copy () for S do
Xou f- Naui \ { U (argmin MMDx(Pmn Pout + neat
(6,z 5m))}
end
return Neat, refined coreset of size n2
I. Proof of Thm. 4: Low-rank analysis of CTT power
Thm. 4 follows from the following more detailed statement, proved in App. I.1, as
3 R (Tin: 20s,, 9) R (Pins 20s, g) O
Theorem L11 (Low-rank analysis of CTT power, detailed). Under the assumptions of Thm. with nin & m+n CTT (Alg. 3) rejects with probability at least whenever e' MMD 1) /lo((1)) exceeds
|
B (R mies 20
9) (u 20am
20 3(2/))
29 7m
Here, d a universal constant, c5 2 2+ / (2lg(( ( and Ru (IP, min g) and Rk (Q, Nins ö, g) respectively denote the
(1 6 ) quantiles of RK (Nim: 8, g) and RK (nm, 8.9) g). where
R2 (ne, 8, g) A 256(1ogı Pen
1)(1)) log(nn + +1) Vlog(2/8))
(40)
K
e log(
6:29 /mallog, Tin g)
+ V log( 3mm (mng(nng Win B B-12
+ v /r+1 (2)-0011 / })²
2
+ min 320 /ma
2v K
max
c2p e2rlog
6.20 6.20 (log, (lg,,
-20-1
v3
I.1. Proof of Thm. L.1: Low-rank analysis of CTT power, detailed
Recall the following definition from Shetty et al. (2022, Def. 3).
Definition I.1 (k-sub-Gaussian thinning algorithm). We say thinning algorithm ALG (satisfying Def. 1) k-sub-
Gaussian on an event & with shift and parameter if
Pe(MMD Pou) zatovi Xn) ct for all t t2 0.
Fix K E K'). To conclude our power result, suffices, by Domingo-Enrich et al. (2023, Rmk. 2, App. B.1) and the failure probability setting of Domingo-Enrich et al. (2023, Lem. 11), to establish that
R2 (m), 8. 256(log, Fij g 1)(C (6, 28 (T 2z 29+1 V \ log (log, K
)
(Vlog (Nin 1) + /ogg///////// 2
(41)
34

---

Low-Rank Thinning
for any scalars C (6, 20+1 vn and 2 (6. 20+1 (nnn) satisfying the property that, event of probability least 1- 8/2, every call to HALVE A KH n. flog, m=- with input size & and output size f/2 is k-sub-Gaussian (Def. 1.1) with shift L,,,, and parameter ' ",ma. satisfying
0 L. K
(g(6,)) 1/2
and
28 (6.2)
2/2
log(
12n (log,
28
Substituting Mg (6, 20+1 vmnm)
(20 V 120+1 "o.
llog(
12nu4 (log, 9)
and CR 20+1 20+1
20 vn,
(29 M Na into (41), we obtain the sufficient condition
R Mmm: 0. = 256(1og, 7mm - (29 mm . (Vlog(na + +) + log(2/0)))
1/2
020-1 V un + U2o m. [oog(
12m 12 ("0R, mi 2) 20 20th v
log( 3r 8-11)
(loRs (nallog,
na -
(42)
We now identify suitable t, K and E,n,. with the aid of the following lemma, proved in App. 1.2.
Lemma I.1 (K,, v, -ubb-Gaaann thinning algorithms are --subaGa Suppose ALG a (K, v, 8)-sub- Gaussian thinning algorithm, satisfying Def. 3 with an event & of probability at least -6/2. Then ALG is k-sub-Gaussian (Def. 1.1) on & with shift a R. and parameter Una Den defined as
Grn K - V minysma (uver+ Ar41( (K)
1)
and
Vna K - vvVe.
Mix
min
By Prop. B.4 and Lem. A.I, KH sub-Gaussian thinning algorithm with
0² Rip (log The 00) 8) with input size l and output size 8/2 is (K, Nin 1o Tlog,, Nie - 0) 8)
v $ (1/2)v3 log 6(t/2) (ogg(e/(0/2), Roa
(logs ma-
max
log
12m (loga Nie Ni-- 9)
K muax-
8
82
(4/2)v3
68
By Lem. I.1, on an event of probability least output size f/2 is k-sub-Gaussian thinning algorithm with shift ar K and parameter Ve,,,, K defined as
8, KH
4o 4 Clona mia a) with input size é and
nn 8)
2
log
12mg (log, nu - g)
K max V 2og
L.n.KK K
(1/2)/3
+ min.ge
(1/2)v3 / log
1log,, nie 1)
K
max eer (xr11 - 2) and (43)
66
U/ R.n.. K (1/2)33
log 12ng (log, na (a--)
Imx Ve.
(44)
Moreover, by the union bound, as detailed in Shetty et al. (2022, App. F.I), every HALVE call made by KT-COMPRESS simultaneously uisub-Gaussian with these input-size-dependent parameters on a common event of probability at least 3- Substituting (43) and (44) with e = 20+1 vn into (42), we obtain our erro inflation factor expression (40), completing the proof.
- à
L.2. Proof of Lem. L1: (K, v. (...:o.uuu-Guusseee Jubb-aausiaan thinning algorithms are k-sub-Gaussian
Fix any 2 and let 8' = -t. By our sub-Gaussian assumption, Thm. implies that, as advertised,
- 2 P3 > (Pin (Pmn Pomt) 2 min 2² v²(e2r + et] + Ar (K) Man
1)
= =P
MMDK (Pm. ) 2 min, v /vleer + et + (e+i(K) 1
2 Pe MMDx (Pm. Pom)) vveett / min, vveer + / (/4t
Mea
Piee
35

---

Low-Rank Thinning
J. Proof of Cor. 3: Power of deep kernel CTT
Define the radius
R' - maxyevux ((((()). 3)1l..
the augmented vectors )" _ {(0(y), y) yey and the augmented kernel
(((((z),,)) ( y)) & ((d(z) y) exp(-n]((((x),a)) (0()). 1))
Since the deep kernel (13) takes the form
Kdeep (2t, y) = (1 (0)d='''(((00)) w) (b(v), v)) + <g(xx, y)
we also have
K deeep
A kdeep (V, = Q)' + cQ for o' and Q - (()
Hence, by Weyl's inequality (Horn & Johnson, 1985, Thm. 4.3.1) and the Gaussian kernel matrix eigenvalue bound (6),
2 1/d log
Agr+1 (Kdssp) < (1 - -) + (Q)+1((Q) < ne
for (2e)d Sr < n.
Parallel reasoning and the assumption m S n yield the same bound for x2r+1 (Kapp X)) and (2e) Sr << m. Now consider the approximate rank parameter
e max ( log lo]()) d' (R/de24/dddd for 8 6 2
(45)
Then, for (2c) we have, exactly in App. D,
Agr +1 (Keep) + A2r +1 (X) I nece
and therefore
R = 0 Vlo
log(?
(3) log( max [ log(n d2 12 (1
Our final step is to bound the quantile of the sole remaining data-dependent term, R'. Since the inputs are Suub-Gaussian (14), Lem. of Dwivedi & Mackey (2024) with (r) yielding the result.
>/oggr implies that the 20s ve
3
quantile of R' is O Ol, (log()))
K. Proof of Cor. 4: Power of deep manifold kernel CTT
Our reasoning is identical to that in App. J with the manifold Gaussian kernel matrix eigenvalue bound (7) now substituted for the Euclidean ball bound (6) and the approximate rank setting r* =
substituted for (45).
L. Supplementary Experiment Details
L.I. Approximating attention experiments
The experiment of Tab. 3 was carried out using Python 3. 12.9, PyTorch 2...0....22222000700022222 (Paszke al., 2019), and an Ubuntu 22.04.5 LTS server with AMD EPYC 7V13 64-Core Processor, 220 GB RAM, and single NVIDIA A100 GPU (80 GB memory, CUDA 12.8, driver version 570. 124.04). For reference, attention layer has (n, d) (3136, 64) and attention layer 2 has (n, d) = (784, 64). For each of the first 50 ImageNet 2012 validation set batches of size 64, we measured the time required to complete a forward pass through each the approximate softmax matrix (8) layer using CUDA events following 10 warm-up batches to initialize the GPU. Tab. L.1 provides the hyperparameter settings for each attention approximation in Tab. 3.
36

---

Low-Rank Thinning
The experiment of Tab. 4 carried out using Python 3.12.9, PyTorch 2.6.0, and Ubuntu 22.04.5 LTS server with Intel(R) Xeon(R) Gold 5218 CPU Processor, 100 GB RAM, and single NVIDIA A6000 GPU (48 GB memory, CUDA 12.1, driver version 530.30.02). For reference, the BigGAN model contains single attention layer with 4096 queries in R 1024 keys in R and 1024 values in R We measured the time required to complete forward pass through the approximate softmax matrix (8) layer using CUDA events following 10 warm-up batches to initialize the GPU. Tab. I.2 provides the hyperparameter settings for each attention approximation in Tab. 4.
The settings and implementations for all methods other than Thinformer were provided by Zandich et al. (2023), and our experiment code builds on their open-source repository https: http://gtttub..t/ wwwmmoommcccceec.coc.. daliri/kdee former.
Table I.1: Configurations for the attention approximation methods of Tab. 3.
Attention Algorithm
Layer Configuration
Layer Configuration
Performer
num_ fum_features=49
num_ nun_features=12
bucket_s bucket_size-49
bucket_size-1
Reformer
2_hashes=2
n_hashes=2
1 local_ Docal_context=49
local_context==
ScatterBrain
num nun_features-Q8
nun_features=6
sample_size-64
sample_size-56
KDEformer
bucket_size=32
bucket_size=20
Thinformer (Ours)
g=2
g=4
Table L.2: Configurations for the attention approximation methods of Tab. 4.
Attention Algorithm
Layer Configuration
Performer
num num_ features=11
bucket_size=62
Reformer
n_hashes=8
ScatterBrain
num_features=128
sample_size=
KDEformer
bucket_size=64
Thinformer (Ours)
g-2
L.2. Faster SGD training experiments
The experiment of Sec. 5.2 carried out using Python 3.10, PyTorch 2.0.1, a Rocky Linux 8.9 server with 64 CPU cores (Intel(R) Xeon(R) Platinum 8358 CPU @ 2.60GHz), and NVIDIA A100 GPU (40 GB memory, CUDA 12.4, driver version 550.54.15).
Technically, the CD-GraB: SBW algorithm requires an a priori upper bound on the maximum Euclidean norm bmax of any stochastic gradient that it will encounter. To conduct our experiment, we first estimate b by calculating the maximum gradient Euclidean encountered across epochs running SGD with LKH (zz) reordering. One would typically not choose to carry out such two-step procedure in practice, but the experiment serves to demonstrate that the CD-GraB: SBW leads to overly conservative performance even if reasonable upper bound is known in advance.
The settings and implementation for both random reshuffling (RR) and CD-GraB: Greedy were those used in the original logistic regression on mortgage application experiment of Cooper et al. (2023). Our experiment code builds on the open- source CD-GraB repository https: / //gitttthus com/Garlln CCCarrCuo/CD-CCC was carried out with a learning rate of a = 0.01, datapoints were loaded in batches of size 16, and stochastic gradients were reordered for each datapoint individually.
As in Cooper et al. (2023), optimization
37

---

Low-Rank Thinning
Median=10
1319:33
cz
12
Singular Value (log scale)
244.201
Number Occurrences
10
56.397
17.233
8.085
8
0.889
0.208
4
0.007
2
0.002
0.001
10 15 eg-rank of SGD Matrix x
20
4
5 6 7 8 10111213 14 16 17 1819
Singular Value Index
Figure L.1: Approximate low-rank structure of stochastic gradient matrices. Left. For each epoch of the LKH 2K
experiment of Sec. 5.2, we record the eg-rank of the stochastic gradient matrix X _ |=f = E IRaxd (see Def. and Thm. 3). Notably, the egrrnnss are significantly smaller than the ambient dimension d = 19. Right. We display the singular values of the first stochastic gradient matrix, X The singular values drop off steeply, resulting relatively small ex egrranks
L.3. Cheap two-sample testing experiment
The experiment of Sec. 6.2 carried using Python 3.12.9, PyTorch 2.6.0+cul 14,, and Ubuntu 20.04.6 LTS server with AMD EPYC 9554 64-Core Processor, 100 GB RAM, and single NVIDIA H100 GPU (96 GB memory, CUDA 12.2, driver version 535. 154.05). Each test is run with replication count B = 100, nominal level a 0.05, and failure probability = 0.5. The neural network & was trained exactly as in Liu et al. (2020) (with learning rate 5 x 10-5 and batch size equal to the full training sample size), and runtime measurements exclude the time required to train ø. Our ex- com comm/fnngli9900
periment code builds on the open-source deep kernel testing ropp:// repositories. and Compress Then Test / / httpa///cccccccooooooooooooooooa
for-IST)
0.024
0.022
Rkinp / logs (n)
0.020
0.018
0.016
0.014
0.012
43
44
45
46 47
Sample Size
Figure I.2: Slow-growing error inflation. In the experimental setting of Sec. 6.2, the error inflation factor R R enjoys
Ollgg 5 (n)) growth the ratio Rkaup/ log"(n) decreases with n. Here, R2 Kin, is defined by (12) with Pan 2n and
Trat 20 Tim for constants 3 = 0.05. 32, and g 4.
38


Reviews:
[{"review_id": "FSmGysOFr2", "reviewer": "Reviewer_fAVp", "summary": "This paper presents a new analysis of sub-Gaussian thinning algorithms based on a low-rank assumption. It provides theoretical guarantees that apply to many data distributions and kernel functions, in contrast to previous work with more limited applicability and poor dimension dependence. The key insight is that high-quality dataset summarization can be achieved whenever the kernel or data matrix is approximately low-rank, enabling efficient identification of representative points. The authors introduce practical sub-Gaussian thinning methods. They apply them in three key applications with good performance: approximating attention in transformers, accelerating stochastic gradient descent, and distinguishing distributions using deep kernels.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "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": "We thank the reviewer for championing this submission and are delighted that the reviewer found the paper “clear and easy to follow,” the theoretical results “solid and comprehensive,” and the “wealth and diversity of application quite impressive.”\n\nThank you also for the interesting question concerning variance proxies. If we understand correctly, the question is whether for each thinning algorithm we have identified the smallest possible sub-Gaussian constant $\\nu$. We have not yet had a chance to verify this, but one tractable lower-bounding strategy would be to compute (or lower-bound) each algorithm’s variance parameter $\\sigma^2 = \\sup_{u} E[u^\\top K(p_{in} - p_{out})(p_{in} - p_{out})^\\top K^\\top u] / u^\\top K u$ as a function of the sample size, $\\delta$, and the kernel matrix. It seems at least plausible that the derived sub-Gaussian and variance parameters would match in the worst-case setting. \n\nWhile we do not yet have a precise answer to this question, we can currently comment on the rate optimality of our sub-Gaussian constants. Specifically, Thm. 3.1 of Phillips & Tai implies that any thinning algorithm must incur at least $\\Omega(\\sqrt{d}/n_{out})$ KMS error for some dataset in $R^d$ and many common kernels. Meanwhile, our Prop. B.6 and Thm. 1 imply that GS-Thin has $\\nu = O(1/n_{out})$ and hence KMS $O(\\sqrt{d}/n_{out})$. Thus, GS-Thin has a minimax rate-optimal sub-Gaussian constant, and no thinning algorithm can have sub-Gaussian constant $\\nu = o(1/n_{out})$.\n\nFinally, thank you for flagging our typo. In the revision, we will replace \"Since\" with \"Moreover\" and \"surely\" with \"with probability 1.\"", "claims_and_evidence": "The answer is a definite yes! The paper is very neatly organised, making the claims particularly clear and easy to follow. There is convincing evidence for all theoretical claims, with rigorous proofs in appendix.On top of the main theoretical results presented in section 3, the authors specify these in three quite diverse applications in the last three sections: approximating attention in transformers, accelerating stochastic gradient descent, and distinguishing distributions using deep kernels. Specifics theoretical results are proven in each of them, and numerical experiments are proposed as well. These evaluation criteria make sense, and I find the wealth and diversity of application quite impressive. I'm not an expert in these applications but found them interesting and informative.", "methods_and_evaluation_criteria": "On top of the main theoretical results presented in section 3, the authors specify these in three quite diverse applications in the last three sections: approximating attention in transformers, accelerating stochastic gradient descent, and distinguishing distributions using deep kernels. Specific theoretical results are proven in each of them, and numerical experiments are proposed as well. These evaluation criteria make sense, and I find the wealth and diversity of application quite impressive. I'm not an expert in these applications, but found them interesting and informative.", "theoretical_claims": "I set out to carefully check all of the proofs, as I am both familiar with and interested in sub-Gaussian properties, but did not manage to read every proof in full detail; I reviewed the main arguments through Appendix D with reasonable care. The parts I read were well-written and convincing.", "experimental_designs_or_analyses": "As said earlier, I am not much familiar with the applications of section 4 to 6. I did not check the soundness of the experimental designs or analyses, but all seemed very reasonable to me. A quick look at the code and some of the Python notebooks within the suppl materials convinced me that the experiments were conducted very thoroughly.", "relation_to_broader_scientific_literature": "See below.", "essential_references_not_discussed": "Relevant literature is covered to a good extent. I am not familiar enough with the thinning literature to make a definite judgement.", "other_strengths_and_weaknesses": "Strengths:\n- a paper thoroughly written;\n- very solid and comprehensive theoretical results: every proposed algorithm comes with its own approximation/convergence guarantees and sub-Gaussian parameter \\nu;\n- the code provided seems well presented and complete (from skimming through it);\n- applications and experiments are well motivated and show the interest of the proposed thinning algorithms.\n\nWeakness\n- I honestly do not see much to say as weaknesses. As my score and evaluation indicate, I am clearly championing the paper. I do feel, however, that the 8-page conference format makes the presentation somewhat compressed. A journal format with more space could have better served the exposition. That said, the authors make excellent use of content division between the main text versus the appendix.", "other_comments_or_suggestions": "Just a few typos:\n- last eqn page 12: what is meant by \"surely\"?\n- the sentence starting with \"Since\" in App C.4 misses an end.", "questions_for_authors": "I don't think the response to this question would affect my score, but here it is anyway:\nThe authors partly characterize the performance of their thinning algorithms using sub-Gaussian parameters. These can in principle be optimized (ie, minimized) to yield a so-called optimal (i.e., minimal) variance proxy $\\nu_opt^2$. For many standard distributions, this optimal variance proxy parameter is known. I was curious whether the sub-Gaussian parameters derived for the proposed thinning algorithms are optimal in this sense. Are there technical reasons preventing such a result? Establishing optimality—or proving lower bounds showing that the guarantees cannot be improved—would be a valuable addition and strengthen the theoretical contribution of the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ySWwj5A9fP", "reviewer": "Reviewer_yDej", "summary": "This paper introduces a novel theoretical analysis of \"thinning algorithms\" that adapt effectively to low-rank structures present in data. The authors develop a theoretical upper bound on the discrepancy metrics (Theorem 1) applicable to any kernel and any data distribution, thereby demonstrating that thinning algorithms with sub-Gaussian guarantees (per Definition 3) achieve improved quality metrics especially when the kernel or data matrix is approximately low-rank. Three significant applications are also discussed: (1) approximating dot-product attention in Transformers efficiently, (2) expediting stochastic gradient descent (SGD) training by optimized data reordering, and (3) conducting two-sample kernel maximum mean discrepancy (MMD) tests efficiently via Compress-Then-Test approach. The authors provide theoretical guarantees for these applications (Theorems 2, 3, and 4, respectively) and extensive empirical experiments validating the efficacy of the proposed thinning-based approaches.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for the positive and constructive feedback and are delighted that the reviewer found our methods broadly applicable, our experiments extensive and convincing, and our contributions novel and clearly positioned within the literature.\n\n**Summaries:** Following the reviewer’s advice, we will add a summary of core ideas underpinning the main results. For example, for (3), we decompose the sub-Gaussian error vector $K^{1/2}w$ for $w = p_{in}-p_{out}$ into a rank-r projection $V_r^\\top K^{1/2}w\\in R^r$ and a residual. We bound the residual error in terms of $\\lambda_{r+1}$ and $\\vert\\vert w\\vert\\vert_2=1/n_{out}-1/n_{in}$ and bound $\\vert\\vert V_r^\\top K^{1/2}w\\vert\\vert_2=\\sup_{\\vert\\vert u\\vert\\vert_2\\le1} u^\\top V_r^\\top K^{1/2}w$ with high probability using the sub-Gaussianity of $w$ and the union bound over a finite cover of the unit ball in $R^r$. Similarly, (4) follows from the sub-Gaussianity of $w$ and the union bound over $\\pm e_i$ for each $i\\in\\mathcal{I}$. Finally, (5) follows from a more elaborate chaining argument that frames $(e_i^\\top Kw)_{i\\in\\mathcal{I}}$ as a sub-Gaussian process and uses the Lipschitzness of $K$ to control its entropy integral.\n\nWe will also add summaries and high-level discussions of theoretical takeaways. For example, in Sec. 6.1, we will highlight that a standard way to summarize the discriminating power of a test is through its detectable separation rate, the smallest MMD separation between P and Q detectable with power at least $1-\\beta$. Standard quadratic-time MMD tests have a minimax-optimal separation rate of order $1/\\sqrt{\\min(m,n)}$ (Kim & Schrab, 2023, Thm. 8), and our Thm. 4 shows that CTT matches this rate up to an inflation factor $R_k/2^g$ depending on the eigenvalue decay of the kernel. In other words, CTT provides minimax-optimal detectable separation in near-linear time whenever $\\textup{rank}_{\\epsilon}(K)$ is polylog(n) for $\\epsilon=$polylog(n). As a practical concrete example, we derive the first power guarantees for deep kernel CTT in Cors. 3 and 4; these ensure that CTT can match the power of quadratic-time deep kernel testing in near-linear time. The original CTT analysis used the RKHS covering number bounds of Dwivedi & Mackey (DM) instead of kernel matrix eigenvalues to bound compression error, yielding less sharp results. For example, substituting DM bounds into our deep kernel analysis would yield a larger, order $\\log^{3d/4+2}(n/\\widetilde \\beta)$ inflation factor that does not adapt to the intrinsic manifold dimension.\n\nWe will also add a brief summarization of the methods analyzed in the revision and follow the reviewer’s other suggestions to improve clarity.\n\n**Tightness:** In the revision we will highlight that our Thm. 1 guarantee (5) with GS-Thin matches the minimax lower bound of Phillips & Tai (Thm. 3.1) for KMS coresets on $R^d$; that our Thm. 3 matches the minimax lower bound of Cha et al. (Thm. 4.5) for reordered SGD algorithms up to the epsilon rank parameter r; and that, by Kim & Schrab, 2023 (Thm. 8), the separation rate of our Thm. 4 is minimax optimal up to the inflation factor $R_k/2^g$ and that of Cors. 3 and 4 is minimax optimal up to log factors.\n\nWe will also clarify that the observed accelerated convergence rate of LKH-SGD over the standard slow SGD rate of RR provides a direct verification of the Thm. 3 guarantee, while the improved power-runtime trade-off of CTT over the standard Monte Carlo tradeoff of subsampling provides a direct verification of the Thm. 4 guarantee.\n\nFollowing the reviewer’s advice, we have also conducted two new analyses to explicitly measure the approximate low-rankness of our matrices and thereby gauge the relevance of our guarantees. In the CTT setting of Sec. 6.2, we find that the empirical inflation factor $R_k = O(log^5(n))$ owing to approximate low-rankness: see https://imgur.com/a/hmAVQIU. In the LKH experiment setting of Sec. 5.2, we find that the stochastic gradient matrices $X_k$ have rapidly decaying singular values and a median $\\epsilon_k^*$-rank of 10: see https://imgur.com/a/MyA7gR1. We will investigate whether another simple experiment could provide further insight into bound tightness.", "claims_and_evidence": "The paper makes four main claims: a general theorem providing high-probability upper bounds on the MMD and kernel max seminorm (Theorem 1), and three application-specific theorems demonstrating the utility of thinning-based approaches (Theorems 2, 3, and 4). Overall, these theoretical claims---particularly regarding improved complexity and performance bounds---are well-supported through rigorous proofs provided in the appendix and extensive empirical validation. However, the paper's presentation could be improved by succinctly summarizing the high-level ideas behind these proofs, especially for Theorem 1, in the main text. Currently, relegating all proofs to the appendix leaves readers without clear intuition on the core ideas underpinning the main results. Additionally, clearer explicit summaries and high-level discussions of theoretical takeaways, especially in Section 6.1 (e.g., how Algorithm 3's analysis compares with prior works), would significantly improve the readability and impact of the paper.", "methods_and_evaluation_criteria": "The methods proposed and their associated evaluation criteria are appropriate and practical for the applications considered. For the Transformer approximation task, benchmark experiments on ImageNet provide relevant and convincing empirical evidence of efficiency and accuracy. Similarly, the logistic regression experiment for accelerating SGD and the Higgs boson detection task for two-sample testing are both well-chosen and pertinent.", "theoretical_claims": "I briefly checked Theorem 1 and its associated proofs in the appendix, which appear rigorous and sound. Nonetheless, I haven't checked the correctness of details in the proof.", "experimental_designs_or_analyses": "The experimental designs---e.g., especially the Transformer approximation experiments (Section 4.2) and SGD training (Section 5.2)---seem well-executed to support and complement the theoretical claims.", "relation_to_broader_scientific_literature": "The authors clearly position their contributions within existing literature on kernel methods, coresets, and thinning algorithms, differentiating from recent related studies. The connections to practical applications in Transformers, SGD acceleration, and kernel two-sample tests are effectively highlighted.", "essential_references_not_discussed": "It seems essential references are properly cited and discussed.", "other_strengths_and_weaknesses": "Strengths:\n  - Originality in providing generally applicable theoretical guarantees for (sub-Gaussian) thinning algorithms that can effectively adapt to (approximate) low-rank structure.\n  - Broad applicability showcased through multiple practical applications.\n  - Solid and comprehensive theoretical guarantees, complemented by extensive empirical evidence.\n\nWeaknesses:\n  - Although the contributions are substantial and the manuscript is generally clear, the presentation could be improved (see suggestions in \"Other Comments or Suggestions\" below).", "other_comments_or_suggestions": "* It would significantly benefit readability and clarity if the authors provided a concise, high-level summary of key proofs, particularly for Theorem 1, in the main body of the text.\n\n* Presentation could be improved by ensuring algorithm references are not prematurely made before formal definitions, especially those relegated to appendices.\n\n* Explicitly summarizing the key theoretical results in Section 6.1 and clearly situating Algorithm 3 relative to prior methods would enhance readability and interpretability of the contributions.\n\n* $\\nu$ is used to denote the sub-Gaussian constant in Definition 3, but it was also used to denote a distribution in Definition 2. Please try to avoid overloading notation.\n\n* In the sentence surrounding Eq. (7), please specify that Eq. (7) applies to Gaussian kernel for clarity.\n\n* It seems Table 2 is redundant as the three-line display at the bottom right of page 4 contains the same information.  Please consider removing one to use the saved space for other purposes.", "questions_for_authors": "1. Could you comment on the tightness of the upper bounds provided in Theorem 1? Do you have any insights or conjectures regarding their sharpness? Additionally, if feasible, could you empirically evaluate the tightness of your theoretical upper bounds through a simple experiment with synthetic datasets?\n\n2. The numerical experiments in Sections 4–6 demonstrate the practical effectiveness of thinning-based approaches, yet the connection to the theoretical results (Theorems 2–4) seems unclear (or indirect). Could you clarify whether and how these experiments validate the tightness or relevance of your theoretical guarantees?  Could you also comment on the tightness of these theorems, and any room for further improvements, if any?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fpRqKeiauU", "reviewer": "Reviewer_UEYY", "summary": "This paper focuses on the thinning problem and proposes a low-rank method to simplify datasets with a limited number of data points, based on the analysis of sub-Gaussian thinning. The proposed low-rank analysis generalizes sub-Gaussian thinning to any distribution and kernel, ensuring high-quality compression of datasets.\n\n## Update After Rebuttal\n\nThanks for the rebuttal. I will keep the initial score but with low confidence.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We thank the reviewer for the positive and constructive feedback and are glad that the reviewer found our framework “comprehensive” and our speed improvements “significant.”\n\nWe apologize for any inaccessibility in our presentation. We aimed to showcase the broad applicability of theory developed in this paper by explicitly deriving sub-Gaussian thinning solutions with state-of-the-art guarantees for three practical problems. We will improve the coherence of the presentation and the accessibility for non-expert readers by providing a more detailed overarching roadmap in the introduction (with guidelines on what will be included in each section), improving transitions between the different application sections, summarizing our main proof arguments, and providing more high-level discussion of theoretical and practical takeaways.\n\nIn addition, we will make the definition and broad scope of thinning clearer from the outset by highlighting that thinning flexibly allows one to summarize any of collection of points, be they datapoints (as in our testing application), stochastic gradients (as in our SGD application), or key-value pairs (as in our attention application).\n\nWe will also clarify in the introduction that related work for the main results and applications are discussed separately in each section.", "claims_and_evidence": "The claims in this paper are mainly supported by theoretical analysis.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "The related work section not available in this paper.", "other_strengths_and_weaknesses": "**Clarification: I don't have a background in thinning or kernel methods, so my assessment below comes with low confidence.** \n\n## Strengths\n\n1. The paper extends sub-Gaussian thinning beyond previous constraints, providing a comprehensive framework applicable to arbitrary kernels and distributions. \n2. Based on the proposed method, the paper introduces Thinformer attention, a mechanism that provides a computationally efficient alternative to traditional self-attention while maintaining competitive accuracy. The Thinfomer layer is 2x faster than baselines like KDEformer while achieving a comparable accuracy.\n3. In additional to the network architecture, the paper also involves the SGD acceleration, and shows significant convergence speed improvements over random reshuffling.\n\n## Weaknesses\n\nMy main concern is the poor presentation of the paper, which makes it less accessible to non-expert readers. For instance, the thinning problem is not clearly defined at the outset. For example, the paper claims that *\"This work is about thinning, finding a small set of\nrepresentative points to accurately summarize a larger dataset\"*. At first glance, the paper appears to address the Core Set problem, which also aims to represent a dataset with a small subset. However, it is actually a general algorithm and is not related to DATASETS. \n\nIn addition, the main topic changes frequently in this paper. In the methodology section, the focus shifts to the Thinformer module for fast attention approximation. Then, in Section 5, the discussion pivots again—this time to fast SGD optimization. These transitions between seemingly different topics make the paper somewhat difficult to follow and may lead to confusion about its contribution.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ihSA6HtBWt", "reviewer": "Reviewer_XcrH", "summary": "This paper proposes Low-Rank Thinning, a method for selecting representative data points using sub-Gaussian thinning with improved efficiency. By leveraging low-rank structures, it enhances dataset summarization capability. Theoretical guarantees and empirical results demonstrate its ability to reduce computation while preserving data quality.\n\n\n## update after rebuttal\n\nMy concerns are addressed by the authors, I improved my rating to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for the positive and constructive feedback and are delighted that the reviewer found our theoretical guarantees strong, our methods practical, and our applications diverse and of benefit to the community.\n\n**A new application:** We presented three vignettes with three diverse applications (SGD training, two-sample testing, and attention approximation) to demonstrate the broad applicability and generalizability of the techniques, but we are happy to include an additional experiment with a different architecture and application as further evidence of generalizability. We have recreated the BigGAN image generation benchmarking experiment of Zandieh et al. where leading attention approximation methods are scored on computational expense and image generation quality. We used the experimental setup and released implementations of Zandieh et al. for all other methods. Our results table (https://imgur.com/a/F5Y7pfh) shows that Thinformer (g=2) yields better Frechet Inception Distance (FID) and Inception Scores (IS) than all of the alternatives while running significantly faster than exact, KDEformer, and Reformer. Performer runs faster still but at the expense of substantially worse FID and IS.\n\n**Low-rankness:** For attention approximation, even if the matrices Q and K are full rank, we still obtain the theoretical and practical benefits advertised (since their rank is d < n). The KMS guarantees (4) and (5) of Thm. 1 also ensure that we obtain a high-quality KMS approximation even if the kernel matrix is full-rank. \n\nFor the other two applications, we have run two new analyses to test to what extent the relevant matrices are approximately low-rank in practice. In the CTT setting of Sec. 6.2, we find that the empirical inflation factor $R_k = O(\\log^5(n))$ owing to approximate low-rankness: see https://imgur.com/a/hmAVQIU. In the LKH experiment setting of Sec. 5.2, we find that the stochastic gradient matrices $X_k$ have rapidly decaying singular values and a median $\\epsilon_k^*$-rank of 10: see https://imgur.com/a/MyA7gR1.\n\nThank you for the suggestion regarding hyperparameters! We initially omitted hyperparameters when recreating experiments fully specified in prior work, but we will include those hyperparameters in the revision. These include Sec. 6.2 (learning rate = 5e-5; batch size = full sample), Sec. 5.2 (learning rate = 1e-2; batch size = 16), and Sec. 4.2 (learning rate = N/A (inference only); batch size = 64).", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "yes I checked the proof of C part in the appendix and it looks ok", "experimental_designs_or_analyses": "The paper presents experiments evaluating Low-Rank Thinning on transformer attention, stochastic gradient training, and distribution testing. Theoretical guarantees are supported by empirical results. Although the experiments show gains in computational efficiency and accuracy, additional validation on other task apart from image classification would enhance the claims of generalizability and practical relevance, e.g., semantic segmentation, object detection.", "relation_to_broader_scientific_literature": "This paper extends sub-Gaussian thinning to broader distributions and kernels, overcoming limitations in prior dataset summarization methods. By leveraging low-rank structures, it enhances attention approximation, stochastic optimization, and distribution testing with improved efficiency and theoretical guarantees.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\n\n1. The proposed Low-Rank Thinning framework improves dataset summarization across diverse aspects, including transformer attention, stochastic gradient optimization, and two-sample testing, which can benefit the community.\n\n2. The paper provides strong theoretical guarantees, extending sub-Gaussian thinning to more general distributions and kernels while addressing limitations in prior work.\n\n3.Experimental results demonstrate that Low-Rank Thinning reduces computational costs while maintaining high accuracy, making it practical for large-scale machine learning tasks.\n\n\nWeaknesses:\n\n1. The experiments focus on constrained settings but lack extensive evaluation on other tasks, e.g., object detection, which may hinder the evaluation of the generalizability.\n\n2, The method assumes a low-rank structure in the data, which may not always be present in real-world scenarios and can decrease its effectiveness for high-dimensional or complex datasets.\n\n3. In Table 3, experiments are only conducted on T2T-ViT, more transformer architectures are suggested to be included while their variants should aslo be considered to test the cross backbone generalizability of the proposed method.\n\n4. The training details regarding the hyperparamters, e.g., lr, batch size, are not well described in both of the main paper and appendix.", "other_comments_or_suggestions": "Please refer to the weaknesses", "questions_for_authors": "My questions are all derived from the weaknesses I mentioned.\n\n1. The experiments are conducted in constrained settings and do not include tasks like object detection. How would the proposed method perform on more diverse applications, and could additional benchmarks improve the evaluation of its generalizability?\n\n\n2. The method relies on a low-rank structure in data, which may not always hold in practical settings. How does its performance degrade when applied to high-dimensional or non-low-rank data, and are there strategies to mitigate this limitation?\n\n3. Table 3 only includes experiments on T2T-ViT, without testing on other transformer architectures or their variants. Would extending the evaluation to different transformer backbones provide stronger evidence of the method’s cross-architecture generalizability?\n\n4. The paper lacks detailed descriptions of training hyperparameters such as learning rate and batch size in both the main text and appendix. Can the authors provide the details of the experiments in main text or appendix further?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper gives theoretical guarantees for  thinning (or subsampling data) algorithms that can adapt to low-rank structure. The bounds assume sub-Gaussian thinning, which is a broad class.  I enjoyed particularily the range of applications, from subsampling key-query pairs in an attention layer, to reordering the training data for SGD, and finally distinguishing two distributions in nearly linear time. Because the reviewers were also very positive, I recommend the paper be accepted. 

The reviewers raised some issue around clarity, and that the paper is hard to access for non-experts. So I encourage the authors to make the paper more didactic, so a wider audience can appreciate their results. Though I know this is challenging, given the limited space, and all the results you would like to present. Furthermore, the assumptions in Theorem 3 are a bit restrictive, since you assume that loss is both Lipschitz, smooth and PL. Though I understand these assumptions hold for logistic regression with no L2 regularization, It would be nice to see if you could establish a proof in one of the more broad classes such as the smooth setting (smooth+PL) or non-smooth setting (Lipschitz + PL)
Decision: Accept (poster)