Research map / Learning theory and algorithms / Matrix and tensor methods
Low-Rank Thinning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a low-rank analysis of sub-Gaussian thinning that bounds kernel MMD and kernel max seminorm by sub-Gaussian constant and kernel/data rank, then applies it to attention approximation (Thinformer), SGD reordering (KH-SGD), and near-linear-time deep kernel two-sample testing (CTT).
Problem
Existing sub-Gaussian thinning guarantees cover only restricted distributions and kernel-based quality measures and have pessimistic dimension dependence, leaving thinning quality unclear for approximately low-rank data or kernels.
Approach
A low-rank analysis shows that any sub-Gaussian thinning algorithm's MMD and kernel max seminorm are controlled by its sub-Gaussian constant times an approximate rank (eigenvalue tail or data rank), applying to any kernel and distribution; this is used to design Thinformer, KH-SGD reordering, and deep-kernel CTT.
Key results
- Thinformer on T2T-ViT ImageNet reaches 82.18% top-1 versus 82.55% exact attention, with layer 1 runtime 2.06 ms vs 18.48 ms for exact.
- Thinformer on BigGAN achieves FID 30.54 versus 32.18 for exact attention, at 2.69 ms vs 5.79 ms runtime.
- Theory: Gaussian-kernel Kernel Halving MMD bound and KH-SGD convergence rate of O~(r/(n^2K^2)) with epsilon-rank r replacing dimension d.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace exact attention with Thinformer | T2T-ViT · ImageNet 2012 validation | Top-1 accuracy (%): 82.55 ± 0.00 -> 82.18 ± 0.05 | Hurt |
| Replace Performer attention with Thinformer | T2T-ViT · ImageNet 2012 validation | Top-1 accuracy (%): 80.56 ± 0.30 -> 82.18 ± 0.05 | Helped |
| Replace Performer attention with Thinformer | T2T-ViT · ImageNet 2012 validation | Layer 1 runtime (ms): 2.54 ± 0.01 -> 2.06 ± 0.01 | Helped |
| Replace Performer attention with Thinformer | T2T-ViT · ImageNet 2012 validation | Layer 2 runtime (ms): 0.60 ± 0.01 -> 0.54 ± 0.00 | Helped |
| Replace KDEformer attention with Thinformer | BigGAN · ImageNet validation | FID: 30.70 -> 30.54 | Helped |
| Replace KDEformer attention with Thinformer | BigGAN · ImageNet validation | Inception Score: 56.91 ± 4.16 -> 57.12 ± 3.96 | No clear effect |
| Replace exact attention with Thinformer | BigGAN · ImageNet validation | Runtime (ms): 5.79 ± 0.02 -> 2.69 ± 0.01 | Helped |
| Replace Performer attention with Thinformer | BigGAN · ImageNet validation | Runtime (ms): 2.29 ± 0.01 -> 2.69 ± 0.01 | Hurt |
Surprising findings
- Thinformer's attention approximation attains higher FID than exact attention on BigGAN (30.54 vs 32.18).
Limitations
- Guarantees for Thinformer hold with probability at least 1/2 only.
- Full-rank kernels with slow eigenvalue decay give weaker bounds (e.g., O(nu^{p/(p+1)}(n/nout)^{1/(2(p+1))}) for polynomial decay).
- Kernel Halving runtime is O(nin^2) for general kernels.
Experimental setup
Datasets: ImageNet Home Mortgage Disclosure Act Higgs
Benchmarks: ImageNet FID on ImageNet validation Higgs
Metrics: top-1 accuracy runtime FID Inception Score MMD detectable separation rate power
Baselines: Performer Reformer ScatterBrain KDEformer HyperAttention random reshuffling CD-GraB W-Block
Builds on: Kernel Halving Compress Compress Then Test Gram-Schmidt walk CD-GraB
Closest papers by meaning
- Supervised Kernel Thinning (NeurIPS 2024 · similarity 0.89)
- Generalized Kernel Thinning (ICLR 2022 · similarity 0.88)
- Debiased Distribution Compression (ICML 2024 · similarity 0.87)
- Distribution Compression in Near-Linear Time (ICLR 2022 · similarity 0.86)
- Learning to Jump: Thinning and Thickening Latent Counts for Generative Modeling (ICML 2023 · similarity 0.85)
- Attention-Driven Training-Free Efficiency Enhancement of Diffusion Models (CVPR 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.