Research map / Learning theory and algorithms / Kernels and regression theory
Provable and Efficient Dataset Distillation for Kernel Ridge Regression
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.
Provides theory for dataset distillation under kernel ridge regression, showing one distilled point per class suffices for surjective feature maps and deriving an analytical, fast distillation algorithm that beats KIP on CIFAR while being far cheaper.
Problem
Dataset distillation lacks thorough theoretical analysis; prior theory (Izzo and Zou, Maalouf et al.) requires d, n, or p distilled points, far more than the empirically observed one-per-class.
Approach
For KRR, characterize exactly which distilled features (and then inputs) recover the original model's parameters, showing k distilled points suffice for surjective feature maps and k+1 for deep linear networks; this yields closed-form distilled data without bilevel optimization.
Key results
- Analytically distilled data recovers original model test accuracy (e.g., CIFAR-100 linear 14.37% vs 14.37%) across linear, FCNN, and RFF models with IPC 1 to 50.
- Algorithm 1 beats KIP on CIFAR-10 at IPC=1 (47.85% vs 45.83%) and CIFAR-100 at IPC=1 (21.58% vs 20.08%) while being much cheaper.
- On CIFAR-100 with IPC=50, the method takes about 25 GPU seconds versus roughly 396000 for KIP, a reported ~15840x speedup.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use analytical dataset distillation instead of KIP | LeakyReLU KRR · CIFAR-10, IPC=1 | accuracy: 45.83±0.29 -> 47.85±0.10 | Helped |
| Use analytical dataset distillation instead of KIP | LeakyReLU KRR · CIFAR-10, IPC=10 | accuracy: 47.50±0.29 -> 47.76±0.12 | Helped |
| Use analytical dataset distillation instead of KIP | LeakyReLU KRR · CIFAR-10, IPC=50 | accuracy: 47.48±0.20 -> 47.77±0.06 | Helped |
| Use analytical dataset distillation instead of KIP | LeakyReLU KRR · CIFAR-100, IPC=1 | accuracy: 20.08±0.20 -> 21.58±0.15 | Helped |
| Use analytical dataset distillation instead of KIP | LeakyReLU KRR · CIFAR-100, IPC=10 | accuracy: 21.56±0.16 -> 21.59±0.15 | No clear effect |
| Use analytical dataset distillation instead of KIP | LeakyReLU KRR · MNIST, IPC=1, 10, and 50 | accuracy: 93.44±0.17 -> 93.72±0.14; 93.75±0.10 -> 93.69±0.17; 93.72±0.11 -> 93.62±0.24 | No clear effect |
| Use analytical dataset distillation instead of KIP | LeakyReLU KRR · MNIST, IPC=1, 10, and 50 | GPU seconds: 159 -> 16; 554 -> 16; 3114 -> 16 | Helped |
| Use analytical dataset distillation instead of KIP | LeakyReLU KRR · CIFAR-10, IPC=1, 10, and 50 | GPU seconds: 225 -> 21; 594 -> 20; 3510 -> 20 | Helped |
| Use analytical dataset distillation instead of KIP | LeakyReLU KRR · CIFAR-100, IPC=1 and 10 | GPU seconds: 616 -> 20; 9323 -> 20 | Helped |
| Analytically distill data to recover the original model's performance | Linear, FCNN, and RFF KRR · MNIST, CIFAR-10, and CIFAR-100 | test accuracy | No clear effect |
Surprising findings
- One data point per class is not sufficient in general for KRR with injective deep nonlinear feature maps, although k+1 suffices for deep linear networks.
Limitations
- Analysis fixes the feature mapping and does not cover learnable feature extractors.
- Non-surjective deep nonlinear networks need more than k distilled points, and the minimum count is unresolved.
- Results hold for KRR; the link to neural network training is empirical rather than proven.
Experimental setup
Datasets: MNIST CIFAR-10 CIFAR-100
Benchmarks: MNIST CIFAR-10 CIFAR-100
Metrics: test accuracy GPU seconds
Baselines: KIP Izzo and Zou Maalouf et al.
Builds on: KIP Izzo and Zou dataset distillation theory Random Fourier Features
Closest papers by meaning
- Boost Self-Supervised Dataset Distillation via Parameterization, Predefined Augmentation, and Approximation (ICLR 2025 · similarity 0.88)
- Large Scale Dataset Distillation with Domain Shift (ICML 2024 · similarity 0.88)
- Dataset Distillation via Knowledge Distillation: Towards Efficient Self-Supervised Pre-training of Deep Networks (ICLR 2025 · similarity 0.88)
- Data Distillation Can Be Like Vodka: Distilling More Times For Better Quality (ICLR 2024 · similarity 0.87)
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.87)
- Rethinking Dataset Distillation for Classification: Do Distilled Sets Outperform Coresets? (NeurIPS 2026 · similarity 0.87)
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.