Provable and Efficient Dataset Distillation for Kernel Ridge Regression

Deep learning models are now trained on increasingly larger datasets, making it crucial to reduce computational costs and improve data quality. Dataset distillation aims to distill a large dataset into a small synthesized dataset such that models trained on it can achieve similar performance to those trained on the original dataset. While there have been many empirical efforts to improve dataset distillation algorithms, a thorough theoretical analysis and provable, efficient algorithms are still lacking. In this paper, by focusing on dataset distillation for kernel ridge regression (KRR), we show that one data point per class is already necessary and sufficient to recover the original model's performance in many settings. For linear ridge regression and KRR with surjective feature mappings, we provide necessary and sufficient conditions for the distilled dataset to recover the original model's parameters. For KRR with injective feature mappings of deep neural networks, we show that while one data point per class is not sufficient in general, k +1 data points can be sufficient for deep linear neural networks, where k is the number of classes. Our theoretical results enable directly constructing analytical solutions for distilled datasets, resulting in a provable and efficient dataset distillation algorithm for KRR. We verify our theory experimentally and show that our algorithm outperforms previous work such as KIP while being significantly more efficient, e.g. 15840× faster on CIFAR-100. Our code is available at GitHub. In this paper, by focusing on dataset distillation for kernel ridge regression (KRR), we show that one data point per class is already necessary and sufficient to recover the original model's performance in many settings, which is far less than n or p data points needed in prior works [9, 21] . Besides, our analysis is more general than prior works [9, 21] and can handle more and different models, including invertible neural networks, fully-connected neural networks (FCNN), Convolutional neural networks (CNN), and Random Fourier Features (RFF). Table 1 compares our theoretical results with previous analysis. We summarize our contributions as follows. • In Sec. 4.1 and 5, for linear ridge regression (LRR) and KRR with surjective feature mappings, we show that one distilled data point per class is necessary and sufficient to recover the original model's parameters and provide necessary and sufficient conditions for such distilled datasets. In addition, we show how to find distilled data that is close to real data in Sec. 4.2. • In Sec. 5.2, for KRR with injective feature mappings of deep neural networks (NNs), we show that one data point per class is in general not sufficient to recover the original model's parameters. However, k + 1 data points can be sufficient for deep linear NNs, where k is the number of classes. • Our theoretical results enable us to directly construct analytical solutions for the distilled datasets, resulting in a provable and efficient dataset distillation algorithm for KRR in Algorithm 1. We verify our theory experimentally and show that our algorithm outperforms previous SOTA dataset distillation algorithm KIP [25] while being significantly more efficient, e.g. 15840× faster on CIFAR-100. • In Sec.6, we show our theoretical results can be used for several applications. First, it can be used as necessary or sufficient conditions for KIP-type algorithms to converge to a global minimum even if the loss function is highly non-convex. Second, our distilled dataset for KRR can provably preserve the privacy of the original dataset while having a performance guarantee. Related works Dataset distillation. Dataset distillation aims to distill a large dataset into a small synthesized dataset such that models trained on it can achieve similar performance to those trained on the original dataset. Previous approaches can be mainly divided into four categories [29]: 1) Meta-model Matching: this category formulates the problem as a bilevel optimization problem and maximize the performance of the model trained on the distilled dataset [34] . Some recent works such as KIP [24, 25] , FRePo [40], RFAD [17], and RCIG [18] approximate the inner loop optimization of training neural networks by