提出低秩分析方法，实现任意数据与核函数的高效压缩采样。
Low-Rank Thinning
- 基于低秩结构分析，统一适用于任意分布和核函数的采样方法。
- 在近似低秩条件下，压缩质量媲美均匀采样且点数显著减少。
- 适用于注意力近似、训练加速和分布区分，适合大规模机器学习场景。
稀疏化的目标是用少量代表性点总结数据集。令人惊讶的是，如核二分法（Kernel Halving）和压缩法（Compress）等子高斯稀疏化算法，在保持与均匀采样相当的质量的同时，可大幅减少摘要点数量。然而，现有理论仅覆盖有限分布与核函数的质量度量，并存在维度依赖过强的问题。为此，本文引入一种新的低秩分析框架，适用于任意分布与任意核函数，当核矩阵或数据矩阵近似低秩时，保证高质量压缩。为验证方法的普适性，设计了实用的子高斯稀疏化方案，改进了当前最优的变压器注意力近似、通过重排序加速随机梯度训练，以及在近线性时间内区分分布的性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。