Low-Rank Thinning
2025/02/17 by Annabelle Michael Carrell, Carrell, Annabelle Michael, Albert Gong +7 · 6 voices · 1 citation
#stat.ML #cs.LG #math.OC #math.ST #stat.ME
paper · pdf · doi:10.48550/arxiv.2502.12063
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.
Cited by
Discussions
- Off to ICML next week? Check out my student Annabelle’s paper in collaboration with @lestermackey.bsky.social and colleagues on low-rank thinning! New theory, dataset compression, efficient attention [bsky, 11 points, 0 comments]
- Anyway I've been hearing about these results for months from Annabelle and I think genuinely it could end up in production systems, which is unusual for something that's not "threw shit at the wall an [bsky, 8 points, 1 comments]
- If you’re not at ICML, you can still read our work. Our new theoretically principled algorithms beat recent baselines across multiple tasks—including Transformer approximation! [bsky, 5 points, 0 comments]
- If you’d like to expand your analysis to support equal weighted kernel thinning coresets, have a look at Low-Rank Thinning (arxiv.org/pdf/2502.12063); that bounds kernel thinning MMD directly in terms [bsky, 1 points, 1 comments]
- arxiv.org/abs/2502.12063 [bsky, 0 points, 0 comments]
- 📈🤖 Low-Rank Thinning. Carrell, Gong, and Shetty et al.. The goal in thinning is to summarize a dataset using a small set of representative points. Remarkably, sub-Gaussian thinning algorithms like K [bsky, 0 points, 0 comments]
Related