# On the Size and Approximation Error of Distilled Sets

arXiv: https://arxiv.org/abs/2305.14113 · HTML: https://mlsanity.com/paper/2305.14113/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 48 references that are in the map.
- First posted on arXiv 23 May 2023.

## Builds on (most cited first, 30 of 35)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Dataset Condensation with Gradient Matching](https://mlsanity.com/paper/2006.05929/) (2020)
- [Dataset Distillation by Matching Training Trajectories](https://mlsanity.com/paper/2203.11932/) (2022)
- [Dataset Condensation with Differentiable Siamese Augmentation](https://mlsanity.com/paper/2102.08259/) (2021)
- [Dataset Meta-Learning from Kernel Ridge-Regression](https://mlsanity.com/paper/2011.00050/) (2020)
- [Dataset Distillation with Infinitely Wide Convolutional Networks](https://mlsanity.com/paper/2107.13034/) (2021)
- [Coresets via Bilevel Optimization for Continual Learning and Streaming](https://mlsanity.com/paper/2006.03875/) (2020)
- [Dataset Distillation using Neural Feature Regression](https://mlsanity.com/paper/2206.00719/) (2022)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Efficient Dataset Distillation Using Random Feature Approximation](https://mlsanity.com/paper/2210.12067/) (2022)
- [Generative Teaching Networks: Accelerating Neural Architecture Search by Learning to Generate Synthetic Training Data](https://mlsanity.com/paper/1912.07768/) (2019)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [Adaptive Second Order Coresets for Data-efficient Machine Learning](https://mlsanity.com/paper/2207.13887/) (2022)
- [Implicit Regularization of Random Feature Models](https://mlsanity.com/paper/2002.08404/) (2020)
- [Dataset Distillation with Convexified Implicit Gradients](https://mlsanity.com/paper/2302.06755/) (2023)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Private Set Generation with Discriminative Information](https://mlsanity.com/paper/2211.04446/) (2022)
- [Sample Condensation in Online Continual Learning](https://mlsanity.com/paper/2206.11849/) (2022)
- [The Variational Gaussian Process](https://mlsanity.com/paper/1511.06499/) (2015)
- [On Coresets for Support Vector Machines](https://mlsanity.com/paper/2002.06469/) (2020)
- [Sets Clustering](https://mlsanity.com/paper/2003.04135/) (2020)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [Introduction to Coresets: Accurate Coresets](https://mlsanity.com/paper/1910.08707/) (2019)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)

## Built on by (most cited first, 3 of 3)

- [Emphasizing Discriminative Features for Dataset Distillation in Complex Scenarios](https://mlsanity.com/paper/2410.17193/) (2024)
- [What is Dataset Distillation Learning?](https://mlsanity.com/paper/2406.04284/) (2024)
- [Understanding Dataset Distillation via Spectral Filtering](https://mlsanity.com/paper/2503.01212/) (2025)

## Abstract (arXiv)

Dataset Distillation is the task of synthesizing small datasets from large ones while still retaining comparable predictive accuracy to the original uncompressed dataset. Despite significant empirical progress in recent years, there is little understanding of the theoretical limitations/guarantees of dataset distillation, specifically, what excess risk is achieved by distillation compared to the original dataset, and how large are distilled datasets? In this work, we take a theoretical view on kernel ridge regression (KRR) based methods of dataset distillation such as Kernel Inducing Points. By transforming ridge regression in random Fourier features (RFF) space, we provide the first proof of the existence of small (size) distilled datasets and their corresponding excess risk for shift-invariant kernels. We prove that a small set of instances exists in the original input space such that its solution in the RFF space coincides with the solution of the original data. We further show that a KRR solution can be generated using this distilled set of instances which gives an approximation towards the KRR solution optimized on the full input data. The size of this set is linear in the dimension of the RFF space of the input set or alternatively near linear in the number of effective degrees of freedom, which is a function of the kernel, number of datapoints, and the regularization parameter λ. The error bound of this distilled set is also a function of λ. We verify our bounds analytically and empirically.