On the Size and Approximation Error of Distilled Datasets
Authors: Alaa Maalouf
Murad Tukan
Noel Loo
Ramin Hasani
Mathias Lechner
Daniela Rus
Venue: NeurIPS 2023 poster (2023)
Keywords: Dataset Distillation
Size and Approximation Error
TL;DR: We provide the first theoritical guaratees on the existance of small distilled datasets and their corresponding excess risk for shift-invariant kernels

Abstract: 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 data points, and the regularization parameter $\lambda$. The error bound of this distilled set is also a function of $\lambda$.  We verify our bounds analytically and empirically.

On the Size and Approximation Error of Distilled Sets
Alaa Maalouf MIT CSAIL
Murad Tukan' DataHeroes
Noel Loo MIT CSAIL
Ramin Hasani MIT CSAIL
Mathias Lechner
Daniela Rus MIT CSAIL
MIT CSAIL
Abstract
Dataset Distillation is the task of synthesizing small datasets from large ones while still retaining comparable predictive accuracy the original uncompressed dataset. Despite significant empirical progress in recent years, there is little understanding of the theoretical fimitations/uuurantess of dataset distillation, specifically, what excess risk is achieved by distillation compared to the original dataset, and how large are distilled datasets? 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 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 approximation towards the KRR solution optimized on the full input data. The size alternatively
of this set is linear in the dimension of the RFF space of the input near linear in the number of effective degrees freedom, which is a function the kernel, number of datapoints, and the regularization parameter X. The error bound of this distilled set is also a function X. We verify our bounds analytically and empirically.
Introduction
Motivated by the growing data demands of modern deep learning, dataset distillation [ZB21, NNXL21, ZNB22, WZTE18) aims to summarize large datasets into significantly smaller synthetic distilled datasets, which when trained retain high predictive accuracy, comparable the original dataset. These distilled datasets have applications in continual learning [ZNB22, SCCB22], architec- ture search [SRL+ 19], and privacy preservation [CKF22]. Recent years have the development of numerous distillation algorithms, but despite this progress, the field has remained largely empirical. Specifically, there is little understanding of what makes one dataset "easier distill" than another, whether such small synthetic datasets even exist.
This work aims to fill this gap by providing the first bounds the sufficient size and relative error associated with distilled datasets. Noting prior work relating neural network training to kernel ridge regression (KRR), shift-invariant kernels. By casting the problem into the Random Fourier Feature (RFF) space, we show that: The size and relative error of distilled datasets is governed by the kernel's "number of effective degrees of freedom", dz. Specifically, in Section 4, we show that distilled sets of size ((d log d exist, with 12A + 2Lx predictive enror on the training dataset, and only 8A error with
consider dataset distillation in the kernel ridge regression settings with
'Equal contribution. Correspondence E-mail: alaam mit.edu.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

respect to the optimal solution computed on the full dataset, where À is the kernel ridge regression regularization parameter and Cx the KRR training error on the original dataset; see Theorem 3 and Remark 7 for full details.
These bounds hold in practice for both real and synthetic datasets. In section 5, we validate our theorem by distilling synthetic and real datasets with varying sizes and values of dž. showing that in all scenarios our bounds accurately predict the error associated with distillation.
2 Related work
Coresets. Coresets are weighted selections from a larger training dataset, which, when used for train- ing, yield similar outcomes the whole dataset was used [MSSW18, MBL20, PDM22, MEM 22]. The key benefit of using coresets is that they significantly speed up the training process, unlike when the full data set is used. Current coresets methods incorporate clustering techniques [FL11, LBK16, BLHK 16]. bilevel optimization [BMK20], sensitivity analysis [MSSW18, 18, HCB16, TMF20, MSF20J, and surrogate models for approximation [TZM Newer strategies are specifically designed for neural networks, where before each training epoch, coresets are chosen such that their gradients align with the gradients of the entire dataset [MBL.20 PDM22, TZM+23], followed by training the model on the chosen coreset. Although coresets are usually theoretically supported, these methods fall short when the aim is to compute a coreset once for a full training procedure.
Dataset Distillation. To this end, dataset distillation algorithms construct synthetic datasets (not necessarily a subset from the original input) such that gradient descent training on the synthetic data- points results in high predictive accuracy on the real dataset. Cast as bilevel optimization problem, early methods involve unrolling training computation graph [WZTE18] for a few gradient descent steps and randomly sampled weight initializations. More sophisticated methods aim to approximate the unrolled computation using kernel methods [NC1,21, NNXL221, ZNB22, LHAR22a, LHIR23a)], surrogate objectives such gradient matching [ZMB21, ZB21J. trajectory matching [CWT+ 22] or implicit gradients [L.HLR23b], The kernel-induced points (KIP) algorithm [NCI.21, NNXL.21] is technique that employs Neural Tangent Kernel (NTK) theory[JGH18, LHAR22b] to formulate the ensuing loss: LKIP- = 2 l/
Ks This loss signifies the predictive loss of training infinitely wide networks on distilled datapoints Xs with corresponding labels ys, on the original training set and labels Xr, yr. with K.,- being the NTK. Dataset distillation is closely related to the use of inducing points to accelerate Gaussian Processes [SG05, TRB16, 16), for which convergence rates exist, but the existence of such inducing points is not unknown [BRVDW19].
From dataset distillation to kernel ridge regression. Kernel ridge regression (KRR) extends the linear machine learning ridge regression model by using a kernel function to map input data into higher-dimensional feature spaces, allowing for more complex non-linear relationships between variables to be captured [Mu Various methods have been proposed to improve and accelerate the training process of kernel ridge regression. Most notably, Random Fourier Features [RR07] approximates shift-invariant kernel functions by mapping the input data into a lower-dimensiona feature space using a randomized cosine transformation. This has been shown to work effectively in practice due to regularizing effects JJSS UIS, as well as providing approximation bounds to the full kernel ridge regression [SS15, AKM+ 17, LTOS199.. Training -nfinite-width neural networks can be cast as kernel ridge regression with the Neural Tangent Kernel (NTK) [JGH18), which allows a closed-form solution of the infinite-width neural network's predictions, enabling kernel-based dataset distillation algorithms such as [NCL21, NNXL21, LHAR22a].
3 Background
Goal, We provide the first provable guarantees on the existence and approximation error of a small distilled dataset in the KRR settings. We first provide notations that will be used throughout the paper.
Notations. Let 7 be Hilbert space with 11-11x as its norm. For a vector a E R", we use ||a|| to denote its Euclidean norm, and a; to denote its ith entry for every i E [n].. For any positive integer n.
we use the convention [n] = {1, 2, ,n). Let A E Raxm be a matrix, then, for every i E [M] and j E [m]. A:. denotes the ith row of A, A.j denotes the jth column of A, and A is the jth entry of
the ith row of A. Let B E axx then we denote the trace of B by Tr(B). We use I, E mmmx to denote the identity matrix. Finally, vectors are addressed column vectors unless stated otherwise.

---

3.1 Kernel ridge regression
Let X E Rand be matrix and let y E R be a vector. Let : R x R2 + [0, oo) be kernel function, and let K R= be its corresponding kernel matrix with respect to the rows of X; i... K = k kemel ridge regression (KRR) involving X, y, k, and is to find
x
for every i,j E [n]. Let À > 0 be a regularization parameter. The goal of
1 |Iy Ka + Aa"Ko "xx. E arg min HER"
(1)
We use the notation / IRd + R to denote the in-sample prediction by applying the KRR solution obtained on X, y and A using the kernel k. i.e., for every z E R
(xx = Σ of M.M, (X)
To provide our theoretical guarantees on the size and approximation error for the distilled datasets, the following assumption will be used in our theorem and proofs.
Assumption 1. We inherit the same theoretical assumptions used at [LTOS21] for handling the KRR problem: (I) Let F be the set of all functions mapping R to R. Let f E F be the minimizer of Σ 19: 1 (Xx:)) subject to the constraint that for every I E I2 and E R.
f*(x) +
where B(() = 0 and Var(t) 0². Furthermore, we assume that is bounded, i.e, lul S yo- (II We assume that | < 1. (III) For a kernel k. denote with X1 2 ... 2 An the eigenvalues of the kernel matrix K. We assume that the regularization parameter satisfies S nd S A1.
The logic behind our assumptions. First, the idea behind Assumption (I) that the pair (X, y) can be linked through some function that can be from either the same family of kernels that we support (i.e., shift-invariant) or any other kernel function. intuition behind Assumption (I) is that there exists network from the desired architectures that gives a good approximation for the data. Assumption (II) aims to simplify the bounds used throughout the paper as it is a pretty standard assumption, characteristic to the analysis of random Fourier features [LTOS 19, RRI I7. Finally, Assumption (III) is to prevent underfitting. Specifically speaking, the largest eigenvalue of K (K + n^A,)= is 21 +AA+ Thus, in the case of nA > A1, the in in-sample prediction is dominated by the term nλ. Throughout the following analysis, we will use the above assumptions. Hence, for the sake of clarity, we will not repeat them, unless moblemm-seciffi clarifications are required.
the context of neural networks, the
Connection to Dataset distillation of neural networks. Since the neural network kernel in the case of infinite width networks describes a Gaussian distribution [JGH18], 8), we aim at proving the existence of small sketches (distilled sets) for the input data with respect to the KRR problem with Gaussian kernel. However, the problem with this approach is that the feature space (in the Gaussian kernel corresponding mapping) rather intangible hard map to, and sketch (distilled set) construction techniques require the representation of these points in the feature space.
To resolve this problem, we use randomized approximated feature map, e.g., random Fourier features (RFF), and weighted random Fourier features (Weighted RFF). The dot product between every two mapped vectors in this approximated feature map aims to approximate their Gaussian kernel function [RRO7]. We now restate a result connecting ridge regression in the RFF space (or alternatively weighted RFF), and KRR in the input space.
Theorem 2 (A result of the proof of Theorem 1 and Corollary 2 of [LTOS21]. Let X Raxd be an imput matrix, E TR." be an input label vector, l Rdd x Red + [0, 00) be a shift-imvariant kernel function, and K. E Raxn, where Vi,j E [n] K k(X,,,
Let X >> 0, and let
[K(K (K n)).)=1). Let SS Ω (dz log (dR)) be a positive integer. Then, there exists dxx= Tr a pair (6,X) such that (i) 6 is mapping & Rd + R (which is based on either the weighted RFF function the RFF function [LTOS2I]), (ii X is matrix X E Bgxxs where for every i [n].
3

---

X,, : o (X and (iii) (ó. X) satisfies
1
(2iz)
Σ Us
fx (Xx) + +41,
1=1
where
fix [.o)
R
F such that for every row vector 2 E R o [xm00
2 X + AnsaAIso
X
y. Note that, Table I gives bounds on s4 when x
Intution behind Theorem Theorem 2 bounds the difference (additive approximation error) between (i) the MSE loss between the ground truth labels and the predictions obtained by applying Kernel Ridge regression (KRR) on the raw (original) data, and (ii) the MSE between the ground truth labels and the predictions obtained when applying Ridge regression on the mapped (full) training data via random Fourier features (RFF). Theorem 2 will be utilized to set the minimal dimension of the RFF which yields the desired additive approximation, i.c., 4X. Thus the intuition behind using this theorem is to link the dimension of the RFF with the size of the distilled set. In other words, we this error bound and sufficient size (of the minimal dimension of the RFF) to provide proof of the sufficient small size of the distilled set.
4 Main result: on the existence of small distilled sets
In what follows, we show that for any given matrix X E Rexd and a label vector E R", there exists matrix S E R and label vector ys E R" such that the fitting solution in the RFF space mapping of S is identical to that of the fitted solution on the RFF space mapping of X. With such S and ys, we proceed to provide our main result showing that one can construct a solution for KRR in the original space of S which provably approximates the quality of the optimal KRR solution involving X and y. Thus, we obtain bounds on the minimal distilled set size required for computing a robust approximation, as well as bounds on the error for such a distilled set.
We now provide Theorem 3 followed by its proof of the existence of a small distilled set. Then provide extensive details and intuitive explanations about the steps of the proof.
Theorem 3 (On the existence of some distilled data). Let X E R be a matrix, y E R. be label vector, k : Rd x Rd + [0, oo) be a kernel function, T = (0, 1) (2). and let s. and X be defined as in Theorem 2. Assume that the rank of X. is 8g, then, there exists matrix S E Raaxd and label vector ys such that
(i) the weighted RFF mapping S E ReaX*e S, satisfies that
X Amsadley)
X
(STS + AnsgAAl.)
ST ys, and
(ii) there exists an in-sample prediction [5. satisfying
A.y
(not necessarily the optimal on S and ys)
( 41
[ix.y.1) (Xix)= - A.X /...s.
(X:))
S min TET
2 max
T, {1,
(3)
4 4 =(1+ x
2 min
1 +
3r
and
min { 11+ + T,
4(147]
yi
A.X.y |S.va. Ail
(X,.)
2
<
min TET
3r
n
y/
fiX.M. (Xin)
n
im1
4 4(1 +
{T. 4
+ min
1 T,
+ 2 max
(T. X
37
(4)

---

Proof. Let S be any matrix in Rsoxd xd such its weighted RFF mapping S is of rank equal to that of X and for every i [*+]. j=1
Σ h (Si.; X..) #0. 0.
Proof of (i). To ensure (i), need to find corresponding proper y/s We observe that
(STS+ AI.
X AnsgAI=o)
X y
S ys
Let b (STS
(STS + AI
X + AI
X y, be the left-hand side term above. b is
vector of dimension Sg. Hence we need to solve b = S ys for ys. Since has full rank then we have a linear system involving &6 variables and b equations. Thus, the solution to such system exists and is
( ( b, where (-) denotes the pseudo-inverse of the given matrix.
Proof of (ii). Inspired by [LHAR22a] and [NCL20), the goal is find of instances that their in-sample prediction with respect to the input data (X in our context) would lead to an approximation towards the solution that would achieve if the KRR used only with the input data. To that end, we introduce the following Lemm.
Lemma 4 (Restatement of Lemma 6 [LTOS2I]). Under Assumption I and the definitions in Theorem 2, for every f E H with Ilfl S 1, with constant probability, it holds that
Σ f (X+,) x 2
n
inf ( AER*
22.
Note that Lemma 4 shows that for every in-sample prediction function with respect to X, there exists a query E Re in the RFF space of that input data such that the distance between the in- prediction sample function in the input space and the in-sample prediction in the RFF space is at 2X.
Furthermore, [LTOS21] was shown that 3 is defined 3 1T [XX* mdI..) -1 where [[X]: (X:.) for every E [n].
f[X),
We thus set out to find in-sample prediction function that is defined over such that by infimum by Lemma 4 would be the same solution 3 that the ridge regression on attains with respect to the
eA.X.y Specifically speaking, we want to find an in-sample prediction [(S.
(-) such that
xx
_xx" + +nalag)
8-
fs [X].
(5)
8
8
where (i) X E IR" such that for every E [n]. fs[X]:
AAXY (X:.); and [SSuu All
(ii) / ()) Σ
a,k ( (Sa.,)) such that a IR*
A.X.y Hence we need to find an in-sample prediction function [S. satisfying 5. Now, notice that
[ nAI,) X Due the fact that we aim find (S. such task boils down to finding E R which defines [(s.ns.)) as in (ii). The above problem can be reduced to system of linear equations where the number of equalities is 8g, while the number of variables 8g-
8 R* fs[X] R" and X
p.X.yy
To do so, we denote
TT ( XXX + nnI, 59
by Å, and observe that we aim to solve
agk (S.. X1+)
Σ 0, (S:., X².)
8= 8 A
86
Σ
aek (Si., X.a)
5

---

We now show that every entry b, (i E [s&] in 3 can be rewritten as inner products between another pair of vectors in I instead of the inner product between two vectors in R" Formally, for every j E [8p]. it holds that
ark (Ste, X14)
a1
aski (Sio, X2-)
Bj Ajo
Σ Ag. (Si,; E Azek (S (es
aso
Σ Oskk (Sio: Xno)
Σ A (S1. X,,).
2 Σ A (Sec.. (e.) E R
Thus, for every j [sø], define Aj.
In other words, A is the result of a Hadamard multiplication of and 1-rank matrix G such that each its rows equal to Σ (SI., X..)
k (Sego, (S.),;
LXX" + ndlm)) ) )-) = rank ( 80
Since the rank of Å is full, i.e., rank (A) rank
X 60
by assumption, then it holds that
rank (A) rank (AoG) rank (DrAD.) rank (A).
where the first equality holds by definition of A and denoting the Hadamard multiplication product, the second inequality holds since by construction of and G = uv such that u, v E He are vector with non-zero entries, and Du, D2 x& are diagonal matrices where their diagonal are and respectively. The last inequality holds by property of rank function, i.e., the rank of any product of pair of square matrices C and D such that D is of full rank is equal to the rank of C.
The right-hand side of (5) can reformulated as
1 S6
X $6
XX" + nAI,
fs = Ao,
where now we only need to solve 3 Aa. Such a linear system of equations has a solution since have 8& variables (the length of a)) and sy equations and the rank A is equal to sg. For simplicity, solution the above equality would be ==:=6 (A)² 8. To proceed in proving (ii) with all of the above ingredients, we utilize the following tool.
Lemma 5 (Special case of Definition 6.1 from 16)). Let X be set, and let (x.1111)) be
2-metric space i.e., for every x, y. 2 E X, ||x E (0, 1), and x, y, X,
2112 < 2 [| 212 11y -=12) Then, for every
4 212
4 | 1z=2113- (1 F) 11 =11
=1- ly 2
Ir 211 s 2²
(7)
We note that Lemma implies that I. 2 Rdd
{ 4 T. {1 || =112 + min
(
4 4(1 411+
x 2112 < min max
{
T, 37
11 2
(8)
rET
where for - = 2 we get the inequality associated with the property of 2-metric, and for any r E (0, 1), obtain the inequality (7).

---

We thus observe that
1
[X. - (X:x) ?
S [ (Xin) - S [x.00 (Xis) + 1x (x..) - [ A.X. (Xi.)
S min TET
max
4 } {T+ 7r)
Σ
11
fix.N.N (Xia) l s2x.voo) (xxx) +
n
min
+ T,
4(1++) 37
[x,1.o] (Xix) ) - f[S.uss.h] (Xim)
4
A + 2 min { 1 T, 4(1 + { x
< min 2 max
TET
7
37
41 + T)
= min 2 max
T, 72
+ 2 min
1
X
TET
3T
where the first equality holds by adding and subtracting the same term, the first inequality holds by Lemma 5, and the second inequality holds by combining the way AA.X,y was defined and Theorem 2. Finally, to conclude the proof of Theorem 3, we derive 4
Vi N.X.N.
(X..)
1
1x (X..) + spx.0.o) (X..) 1550--18.a -S (Xix)
-
1=1
min 1 + T, 37
4(1+T)
min rET
Vi
S 1xx.0000 0l (xcx)
4 } {T.
max
,-, Σ
(xx.)
/ (Xie)
[
n
1=1
min (1 + T, 4(1+T)
3r
n
y1 //x.v0ol (Xis)
12
{ 11
$ <min TET
+ 2 max
T: [,:7))
A
min { (1+7. T, 37
1(1+r)
V/ lix..MM) (Xx.)) 2
< min rET
4 4(1 +
{T. 4 ))
+(4min 4min 1 + T,
+ 2 max
[T, X,
37
(9)
where the equality holds by adding and subtracting the same term, the first inequality holds by (8). and the second inequality follows as result of the way fš was constructed and the fact that / is its infimum based on Lemma 4, and the last inequality holds by Theorem 2.
Intuition behind Theorem 3. The goal of Theorem 3 is to prove the existence of a small distilled set (its size is function of the minimal dimension of the RFF mapping required to ensure the provable additive approximation stated in Theorem 2) satisfying that: (i) The Ridge regression model trained on the mapped training data via RFF is identical to that of the Ridge regression model trained on the mapped small distilled set via RFF, (ii) more importantly there exists KRR solution formulated for S with respect the loss of the whole big data X, which approximates the KRR solution on the whole data X (which is the goal of KRR-based dataset distillation techniques). Thus, (iii) we derive bounds on the difference (approximation error) between (1) The MSE between the ground truth labels of the full data and their corresponding predictions obtained by the specific KRR model (we previously described) on our distilled set and (2) The MSB between the ground truth labels and the predictions obtained when applying KRR on the whole data X.
7

---

The heart of our approach lies in connecting the minimal dimension of the RFF required for provable additive approximation and the size of the distilled set. This is first done by showing that the distilled set can be any set S of instances from the input space (e.g., images) and their corresponding labels, as long as the corresponding labels must maintain a certain property. Specifically speaking, the labels of the distilled set need to be in correlation with the normal of the best hyperplane
found to fit the mapped training data via RFF X via the Ridge regression model trained on X v):
i... (STS + Ams
X + Ansg X y ST ys- From here, the idea hinges upon
showing the existence of KRR model (represented by prediction function) that would be dependent on the prediction function that can be obtained from applying the Ridge regression problem to the mapped full training data via RFF. With such model, the idea is to retrieve the predictions obtained when using the Ridge regression problem from the mapped training data via RFF via the use of some KRR model used the distilled set. We thus show that through careful mathematical derivations, equation reformulation (involving ). and solving a system of equations, one is able to show the existence of a KRR solution that would allow to use Theorem 2. Finally, to obtain our bounds, we also rely on the use of the weak triangle inequality. To that end, we now utilize the described KRR model on the distilled data together with Theorem achieve (iii).
Remark 6. Note that the assumption that X is of full rank (i.e. S6) can be dropped easily from Theorem 3, and as result, we obtain that S can contain (rank of X) instances (rows of S). For additional details, please refer to Section E in the Appendix.
To simplify the bounds stated at Theorem 3, we provide the following remark.
Remark 7. fixing == 2, the bounds in Theorem 3 become
1
[i....M) (Xi.) - S 13.0...1 (Xt.)
2 S 8A,
71
and
n
A.X.y S.
(X,.)
n S
[. (Xio) 2 122.
y/1
Ai
y/1
n1
n2
As for fixing == E (0, 1}, we obtain that
V/
X S..u Ail
(X:.)
S
1 1 8
Σ 1m1
-
B2.. (X..)) + (1(1+e)+ )
5 Experimental Study
To validate our theoretical bounds, we performed distillation on three datasets: two synthetic datasets consisting of data generated from Gaussian Random Field, and classification of two clusters, and one real dataset of MNIST binary and multi-class classification. Full experimental details for all experiments are available in the appendix.
2d Gaussian Random Fields. We first test our bounds by distilling data generated from the Gaussian Process prior induced by a kernel, A: on 2d data. We use a squared exponential kernel with lengthscale
11=-2'118 ara
parameter| / = 1.5: k(æ,z') = e with o2 [0.25, 5.0). We then sample y ~ (O, Kxx + ojin), oy = 0.01. We fix A 10 and distill down to s = di log d The resulting values of d s, and compression ratios are plotted in fig. 2. We additionally plot the predicted upper bound given by Remark 7 and the actual distillation loss. Our predicted upper bound accurately bounds the actual distillation loss. To hetter visualize how distillation affects the resulting KRR prediction, the distilled predictive f for a 5.0 in fig. 1b and fig. Ic.
For X, we sample n = 10s datapoints from A/ o2),
show the KRR predictive function f& and
Two Gaussian Clusters Classification. Our second synthetic dataset is one consisting of two Gaussian clusters centered at (-2 0) and (2, 0), with labels -1 and +1, respectively. Each cluster contains 5000 datapoints so that n 10a. Each cluster as standard deviation or E [0.25, 5.0). Additionally, two allow the dataset to be casily classified, we clip the x coordinates of clusters I and
8

---

Clusters, 300, d,
Training Data Predictive, f
Distilled Data Predictive, f
10-
10
-10
-0
-10 10 35
20
20
-5
-10
5
10
15
(a)
(b)
Figure 1: (a) visualizes the two clusters dataset with 300 and 0₂ 1.5. (b) and (c) visualizing the KRR predictive functions generated by the original dataset (b) and the distilled dataset (c) for
the Gaussian Random Field experiment for oN 5.0. The distilled dataset is able to capture all the nuances of the original dataset with fraction of the datapoints.
Gaussian Random Field
dp
Distilled Set Size,
Compression Ratio
Upper Bound vs. Actual Loss
2000
300
16t
Predicted Déstltatioo
200
1000
10-
16
0-
1
1
1
2
4
1
4
Cluster Stddev,
Cluster Stddev,
Cluster Stddev,
Stadee,
Figure 2: Distillation results for synthetic data generated by Gaussian Random Field (n 3)
clusters 2 to not exceed/drop below -0.4 and 0.4, for the two clusters, respectively. This results in a margin between the two classes. We visualize the dataset for 300 and a 1.5 in fig. la. We use the same squared exponential kernel as before with / = 1.5, fix À 10-5, and distill with the same protocol before. We likewise plot d 8, and compression ratios and distillation losses in fig. again with our bound accurately containing the true distillation loss.
Two Clusters
de
Distilled Set Size,
Compression Ratio
Upper Bound vs. Actual Loss
400
10
2000
1500
10a
10-
100
16a
Predicted Upper Bound
10--
Distllztion Loss
0.
Stddev, d2
Stddev, d.
Stddev, dx
Stadev, d.
Figure 3: Distillation results for synthetic data of two Gaussian clusters (n 3)
Real Word Datasets Classification. For next test, first consider binary classification (i) MNIST and digits, (ii) SVHN and digit, and (iii) CIFAR-10 ship vs deer; all with labels -1 and +1, respectively. We the same eitaared-expoenntill kernel with = 13.9. 1 3.0. and I 1= 8.0, for MNIST, SVHN and CIFAR-10, respectively, which was chosen to maximize the marginal- log-likelihood, treating the problem Gaussian Process regression. We vary n E [500,, 10000), with an equal class split, and perform the same distillation protocol. Here, we additionally scale X x v
such that = 10-4 when n 5000. Distilling yields fig. 4, fig. 5, and fig. 6, showing that our bounds can accurately predict distillation losses for real-world datasets. In fig. 7 and fig. 8 in the appendix, we test our bound for the multi-class case on MNIST 0, digits with similar settings as in the binary classification case. The results justify our bounds.

---

MNIST O vs. Classification Compression Ratio
Distilled
Upper Bound Actual
2.30
Predided
100
60-
4x
3-300
2003 <300 1903 3930 10000 Traiiing Set Size,
2333 4830 1300 3500 3500s Training Sut Size,
2203 4800 6300 s50e 38200 Training Set Size,
2300 4030 5300 350e 30903 Training Sut Size,
2300 4003 s000 550e 10000 Tra Training Set Size,
Figure 4: Distillation results for MNIST binary O vs. 1 classification (n = 3)
SVHN 0/1 Classification Optimizing BA
Distilled Set Size,
Compression Ratio
Upper Bound Actual Loss
600
Axteet
110
500
10-
20%
170
602
Upper Dound
Lon
4x
2000 4300 6000 sdec 33900
2000 e000 rice sice 10093 Training Set Size, n
7000 4ces 6000 300o 10ice
2000 spec 5000 8000 10000
2000 1000 (002 5060 10000
Training Set Size, n
Training Set Size,
Traniing Set Stat, i
Training Set S20,
Figure 5: Distillation results for SVHN binary vs. classification (n = 3)
CIFAR-10 Deer vs. Ship Classification
Distille Size,
Compression Ratio
Upper Bound vs. Actual
Useer
10
66.
10
2005 ebmn e9ns wnss xides Training Set Size,
2201 semn eotn wins stres
2002 sein eotn wiee 19000
2otn ands wetn wie 18995 Training Set Siee,
20tn anio wnnn wale 1999 Traliing Set Size.
Training Size.
Training Set Sizc,
Figure 6: Distillation results for CIFAR-IO binary deer vs. ship classification (n = 3)
6 Conclusion
In this study, we adopt a theoretical perspective to provide bounds on the (sufficient) size and approximation error of distilled datasets. By leveraging the concept of random Fourier features (RFF), we prove the existence of small distilled datasets and we bound their corresponding excess risk when using shift-invariant kernels. Our findings indicate that the size of the guaranteed distilled data is a function of the "number of effective degrees of freedom," which relies on factors like the kernel, the number of points, and the chosen regularization parameter, X, which also controls the excess risk. In particular, we demonstrate the existence of a small subset of instances within the original input space, where the solution in the RFF space coincides with the solution found using the input data in the RFF space. Subsequently, we show that this distilled subset of instances can be utilized to generate KRR solution that approximates the KRR solution obtained from the complete input data. To validate these findings, we conducted empirical examinations on both synthetic and real-world datasets supporting our claim. While this study provides a vital first step understanding the theoretical limitations of dataset distillation, the proposed bounds are not tight, as seen by the gap between the theoretical upper bound and the empirical distillation loss in section 5. Future work could look at closing this gap, as well as better understanding the tradeoff between distillation size and relative error.
acknowledgements
This research has been funded in part by the Office of Naval Research Grant Number Grant N00014 18- 1--30,, DSTA Singapore, and the J. P. Morgan AI Research program.
References
[AKM+17] 17] Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Vel- ingker, and Amir Zandich. Random fourier features for kernel ridge regression:
10

---

Approximation bounds and statistical guarantees. In International conference on machine learning, pages 253-262. PMLR, 2017.
[Bac17] Francis Bach. On the equivalence between kemnel quadrature rules and random feature expansions. The Journal of Machine Learning Research, 18(1::714-75,, 2017.
[BFL 16] Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. New frameworks for offline and streaming coreset constructions. arXiv preprint arXiv:1612.00889, 2016.
[BLHKI6] Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause. Approximate k-means++ in sublinear time. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 1459-1467. AAAI Press, 2016.
[BK200] Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 14879-14890, 2020.
[BRVDW19] David Burt, Carl Edward Rasmussen, and Mark Van Der Wilk. Rates of convergence for sparse variational Gaussian process regression. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pages 862-871. PMLR, 09-15 Jun 2019.
[CKF22] Dingfan Chen, Raouf Kerkouche, and Mario Fritz. Private set generation with discrim- inative information. In Neural Information Processing Systems (NeurIPS), 2022.
[CWT+22] George Cazenavette, Tongzhou Wang. Antonio Torralba, Alexei A. Efros, and Jun- -an Zhu. Dataset distillation by matching training trajectories. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2022.
[FL11] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569-578, 2011.
[HCB16] Jonathan H. Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pages 4080-4088, 2016.
[J23] Matt J. Extract linearly independent subset of matrix columns, 2023.
[JGH88] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Con- vergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018
JJSS + 20] Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Implicit regularization of random feature models. In International Conference Muchine Learning, pages 4631 16400 PMLR, 2020.
[LBK16] Mario Lucic, Olivier Bachem, and Andreas Krause. Strong coresets for hard and soft bregman clustering with applications to exponential family mixtures. Artificial intelligence and statistics, pages 1-9. PMLR, 2016.
[LHAR22a] Noel Loo, Ramin Hasani, Alexander Amini, and Daniela Rus. Efficient dataset distillation using random feature approximation. arXiv preprint arXiv: 12067, 2022.
[LHAR22b] Noel Loo, Ramin Hasani, Alexander Amini, and Daniela Rus. Evolution of neural tan- gent kernels under benign and adversarial training. arXiv preprint arXiv:22 10. 12030, 2022.
11

---

[LHLR23a] Noel Loo, Ramin Hasani, Mathias Lechner, and Daniela Rus. Dataset distillation fixes dataset reconstruction attacks. arXiv preprint arX1v:2302.01428, 2023.
[LHLR23b] Noel Loo, Ramin Hasani, Mathias Lechner, and Daniela Rus. Dataset distillation with convexified implicit gradients, 2023.
[LTOSI9] Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards unified analysis of random fourier features. In International conference machine learning, pages 3905-3914, PMLR, 2019.
[LTOS21] Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards a unified analysis of random fourier features. The Journal of Machine Learning Research, 22(1):4887-49333 2021.
[MBL20] Baharan Mirzasoleiman, Jeff A. Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. Proceedings of the 37th International Confer- ence Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6950-6960. PMLR, 2020.
[MEM+22] Alaa Maalouf, Gilad Eini, Ben Mussay, Dan Feldman, and Margarita Osadchy. A unified approach to coreset learning. IEEE Trunsactions on Neural Networks and Learning Systems, 2022.
[MSF20] Alaa Maalouf, Adiel Statman, and Dan Feldman. Tight sensitivity bounds for smaller coresets. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. pages 2051-2061, 2020.
[MSSW18] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David Woodruff. On coresets for logistic regression. Advances in Neural Information Processing Systems, 31, 2018.
[Mur12] Kevin P Murphy. Machine learning: a perspeciistcceespecttievi MIT press, 2012.
[NCL.20] Timothy Nguyen, Zhourong Chen, and Jaehoon Lee. Dataset meta-learning from kernel ridge-regression. arXiv preprint wwXiv:2011.00050 2020.
[NCL21] Timothy Nguyen, Zhourong Chen, and Jachoon Lee. Dataset meta-learning from kernel ridge-regression. In International Conference on Learning Representations. 2021.
[NNXL21] Timothy Nguyen, Roman Novak, Lechao Xiao, and Jachoon Lee. Dataset distillation with infinitely wide convolutional networks. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[PDM22) Omead Pooladzandi, David Davini, and Baharan Mirzasoleiman. Adaptive second order coresets for data-efficient machine learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaha Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 17848-17869, PMLR, 2022.
[RR07] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
[RR17] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. Advances in neural information processing systems, 30, 2017.
[SCCB22] Mattia Sangermano, Antonio Carta, Andrea Cossu, and Davide Bacciu. Sample condensation in online continual learning, 2022.
[SG05] Edward Snelson and Zoubin Ghahramani. Sparse gaussian processes using pseudo- inputs. In Y. Weiss, B. Schölkopf, and Platt, editors, Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005.
12

---

[SRL* + 19] Felipe Petroski Such, Aditya Rawal, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Generative teaching networks: Accelerating neural architecture search by learning to generate synthetic training data. CoRR, abs/1912.07766. 2019.
[SSI5] Danica J Sutherland and Jeff Schneider. On the error of random fourier features. arXiv preprint S.4K::5506.028.. 2015.
[TMF20] Murad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 2020.
[TRB16] Dustin Tran, Rajesh Ranganath, and David M. Blei. The variational gaussian process, 2016.
[T7M+23] Murad Tukan, Samson Zhou, Alaa Maalouf, Daniela Rus, Vladimir Braverman, and Dan Feldman. Provable data subset selection for efficient neural network training. arXiv preprint arXiv:2303.05133 2023.
[WZTE18] Tongzhou Wang, Jun- Jun-Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distilla- tion. arXiv preprint arXiv:1811.10954 2018.
[ZB21] Bo Zhao and Hakan Bilen. Dataset condensation with differentiable siamese augmen- tation. In International Conference on Machine Learning, 2021.
[ZMB21] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In International Conference on Learning Representations, 2021.
[ZNB22] Yongchao Zhou, Ehsan Nezhadarya, and Jimmy Ba. Dataset distillation using neural feature regression. In Proceedings of the Advances Neural Information Processing Systems (NeurIPS), 2022.
13

---

A Experiment Details
All experiments unless otherwise stated present the average/standard deviations of n 3 runs. Each run consists of a random subset of MNIST 0/1 digits for MNIST binary classification, or random positions of sampled datapoints for synthetic data, and different samples from the GP for the Gaussian Random Field experiment. Distilled datasets are initialized as subsets of the original training data. We distill for 20000 iterations with Adam optimizer with a learning rate of 0.002 optimizing both images/data positions and labels. We use full batch gradient descent for the synthetic datasets and maximum batch size of 2000 for the MNIST experiment. For the MNIST experiment we found that particularly for larger values of n, with minibatch training, we could obtain lower distillation losses by optimizing for longer, so the closing of the gap between the upper bound and experiment values in fig. 4 may be misleading: longer optimization could bring the actual distillation loss lower.
To ensure that assumption (II) fulfilled, we scale the labels such that ||
For example, if we are working with MNIST binary classification, with labels {+1,-1} we first compute |
using [+1,-1] labels, then rescale the labels by 1/r so that the labels are {+ } Suppose this results in some upper bound Lu and some real distillation loss L For the corresponding plots in figs. 2 to 4, we plot Lu and 2² Ln- We do this because the r values for different parameters (such as or σ₂) could be different, and scaling for the plots allows the values to be comparable.
In the figures for the upper bounds on the distillation loss we plot the smallest value of the upper bounds in remark 7.
A.1 Code
Code is available in the supplementary material.
B
Proof of Technical Results
B.1 Proof of Theorem 2
Note that the proof of Theorem 2 follows from the proof's of Theorem I and Corollary I of [LTOS21]. For completeness, we provide the following proof.
Theorem 2 (A result of the proof of Theorem 1 and Corollary 2 of [LTOS2I]). Let X Raxd be an input matrix, y E RR" be an input label vector, k IR x RR + 00) be a shift-invariant kernel function, and K E Raxn, where Vi,j E [n] Kij kX Xz.). Let X >> O, and let Let ss Ω (d log (dx)) be positive integer. Then, there exists a pair (0.X) such that (i) o is a mapping Φ Rd + R (which is based on either the weighted RFF function or the RFF function (LTOS2I1). (ii) X is matrix X E Tgxxas where for every i E [m],
dx = TTr K (K (K<+nAl) ndln)
X. = Φb (Xi.), and (ii)) (0, X) satisfies
1
n
<
ys
P...M (Xx) + 44,
π
where P
RS0
R such that for every row vector & E R*0 S (x))(()) =
X + Amsadles))
x y. Note that, Table I gives bounds 84 when À x Vx
Proof.
First, let B IR be the ridge regression solution involving x and y, i.c.
3 E arg min SER's 1=1
Vi
Xist
+ As ||
Note that, by construction, for every E [n]], fa [x (x..) is equal to X.. B.
14

---

Thus,
12
12 1 yt
y/4
(x (x..)
Σ
inf
Σ yi
(X,,)
(10)
72
n
|
v2
where the first equality holds by definition of [X.v,o]
for every i E [n]. and the second
equality follows from the proof of Lemma 6 of [LTOS21] which indicates that || S 2. Note that,
inf 1 Sven 1=1
Σ
Vi
J(X;.)
inf
Σ
Vi (. (Xea) + [(x.1.)) (Xi.) - (Xix)- F((((xxii (X..))
i=1
(I1)
=inf
inf
V/ f/x.v.11 (X:.) /?
1
Σ i=1
[(X,)) - -P (X:x)²
|V
n
2
n
Us - M (X1)) (fix...M) (X:+) - f (X:..)
n
where the first equality holds by adding and subtracting the same amount, while the last equality holds by simple expansion.
To properly bound the terms above, rely on Lemma 7 of (LTOS21].
Lemma 8 (Restatement of Lemma [LTOS21]). Under Assumption and the definitions in Theo- rem 2, and for
P E arg min FER. YL
Mi (X..) (X..) + +1115|2
==1
where H. is the corresponding RKHS space of X, it holds that
n
J. (Xi.) (Iia.u (Xix) - pa Ma (X..) S X.
n
Hence, combining Lemma with (11) yields
Ut i F(X..) ?
inf
1=1
Vi FiX.U.M) (X:x) )
+ +2 +
inf
1 Σ f (Xx;))
S. (x,))
(12)
|| SV2 n
1=1
1=1
K
Σ
V: fix.y (X+))
+ +41
where the last incquality holds by Lemma 4 (or equivalently Lemma 6 [LTOS2I]), and thus concluding Theorem 2.
C Regarding S6
In what follows, we discuss cases for determining the quantity 89- To quantify s6 which in turn determines the size the distilled set, we need to measure dx which the trace of K (K + n²
15

---

Table 1: Table from [LTOS19]. The trade-off in the worst case for the squared error loss.
SAMPLING SCHEME
SPECTRUM
NUMBER FEATURES
finite rank
86 E 12(1)
X, x A
8o E S2(log n log logn)
WEIGHTED RFF
Ox 1t
8o E 1/2 log n)
A 1 Ax
86 E S2( vn log
finite rank
86 52( /n)
A α A'
86 E (2( / log log n)
PLAIN RFF
o (12
S6 E 52( v log n))
A Axi-
86 E 52 log
For the case where K has a finite rank, i.c., the number of positive eigenvalues is lower than n, then S6 E (2(1).
As for the exponential decay, it occurs when the kernel is Gaussian and the marginal distribution of the input data (e.g., images) is sub-Gaussian. In such case, it was shown
in [Bac17] that dx (log 1). Thus S6 poly-logarithmic in n when = O
For the case where the Hilbert space is also a Sobolov space of order 7 larger or equal to 1, then dx O x
which in the case of X == O
we have E Ω n
VTL
In the general case, where the decay of the eigenvalues admits A; x O then da in the worst case is bounded by O( Taambdta and thus, via Theorem 2, we can deduce that
& E O(yn log n) for the case of X O
Note that the choice of À E O ( is used in the literature of KRR to ensure that the learning rate is vn as shown [RR17].
D Multi-class Experiments
In fig. 7 and fig. 8 we test our bound for the multi-class case on MNIST 0,1,2 digits with similar settings as in the binary classification case. The results justify our bounds.
MNIST 0/1/2 Classification Optimizing 12A
Distilled Set Size,
Compression Retio
A
Upper Bound vs. Actual Loss
10ah
1071
258
2x-10
1900 30002
1992 s006e 12509
900 750e (9000 12ice Trairing Sel Stow,
2500 5099 7000 28003 Liloe
scec 7993 1c000
Taininn Swi Stow,
Taiining Sei Stow,
Training Sel Siow,
Triining Sei Siow,
Figure Distillation results for MNIST multi class 0, 1, classification (n =)
MNIST 0/1/2 Classification Optimizing BA
Distilled Size,
Compression Ratio
Upper Bound Actual Loss
1500
1400
4x<10
278
1200
4:200
1000
5x30
10
2xx0
2x10
10*
Restrec den Ieooniat
2500 5039 1500 30200 12500
3500 5000 1533 i0éce 1352a
2523 500 7500 takco 1750e
2500 soba 7500 sadoa 12500
2500 5000 7003 ardes 33500
Trinnin Set Size, B
Training Set Sizo, nn
Trairing Set Size, n
Training Set Size, n
Taining Set Size, n
Figure 8: Distillation results for MNIST multi class 0, 1, classification (n 3); testing the 8A bound
16

---

E On the rank of X and its connection to the distilled set S
First, recall that X is the RFF image of X. There mainly two cases connecting the rank of X to
S:
(I) The rank of X s0, i.e., X of full rank.
Otherwise.
Regarding Case (I). For such a case, Theorem is exactly what we need prove the existence of distilled set S.
Handling Case (II). For this case as well, one can also choose to ensure that the rank of S (matrix form of 5) is so (full rank) and apply the same derivations done in the proof of Theorem 3 without any violation from the perspective of the validity of our proof. However, due to the nature of this case, one can also ensure that the size of S (number of instances) is much smaller than Se, specifically, (the rank of X). To that end, must ensure that
(A) the following equation
-1 X" ST ys: (X"X+ + Ansahles)
S''S AnsgALes)
has a solution, i.e., Us exists, and also
(B) we need to ensure that (6) also has a solution, i.e., there exists E R" such that
1 x
XX + +nII,)
[s|X] = Ao.
86
We observe that since X is rank deficient adds some obstacles to our proofs; when attempting ensure both (A) and (B). Specifically speaking, the rank of )
X equal the rank X (due to proper- ties of rank function) and since aim to maintain that S has exactly that number of rows while also its RFF image S has rank equal to that of X, obtain that the linear system of equations in (A) might have no solution at all. This unless the row span of S coincides with that of X.
(S'S An (XTX+ Ans Ans
Having an such that the row span of its RFF image coincides with the row span X, also ensures the existence of a solution concerning the linear system of equations present at (B).
F
One of many ways to construct S
Following the previous section, properly construct S that would satisfy the proof of Theorem we discuss two possible constructions:
If X is of full rank (the rank is sz), then there exists subset S of the rows of X such that its image in the RFF space a linearly independent subset Š of the rows of X. Such a subset is of full rank as it is linearly independent. Such an algorithm can be accessed via [J23].
If X is rank deficient, i.e., r < & where r denotes the rank of X, then the problem by X y by
self requires r independent vectors, i.e, one can represent (XTX )nsadles)
Az where A E R and E R". This is since the rank of (XTX + Xmsaalay) is at max the minimum between the rank of (xTX + Ansadlee) and the rank of XT. Such rank is bounded from above by r since the rank of (XT + Xnsodla)) -1 is 8g.
XT
17

---

To this end, we can invoke the first case with respect to (B,2). Thus, by choosing S to contain the linearly independent rows in X and an additional row from X (not already in 5), there exists ys such that,
(ST + AnsoAIs.) ) B= = ST
Connection to subset selection and label solve. Observe that according to this section, we showed that our bounds in Theorem 3 hold for subset of the data but with different (potentially learned) labels (not necessarily from the set of input labels) which can be thought of as a hybrid between distillation and subset selection. Intuitively, this justifies the label-solve approach of [NCL20), where here we showed that a subset of the data can achieve similar bounds but with learning the labels.
18


Reviews:
[{"review_id": "14XFhFDT2U", "reviewer": "Reviewer_mfyC", "summary": "This paper presents a theoretical analysis of dataset distillation, specifically focusing on the size and approximation error of distilled datasets. The authors provide bounds on the sufficient size and relative error of distilled datasets for kernel ridge regression (KRR) based methods using shift-invariant kernels. They prove the existence of small distilled datasets and show that a KRR solution can be generated using these distilled datasets that approximate the solution obtained on the full input data. The theoretical results are validated through empirical experiments on synthetic and real datasets.", "questions": "(1) Can you provide more experimental results on larger real-world datasets and make appropriate visualizations to prove effectiveness?\n(2) Can you provide more explanation about how understanding data distillation can guide the performance of data distillation?", "limitations": "Not fully discussed how a better understanding of data distillation will guide and evaluate subsequent data distillation work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The paper addresses an important problem in dataset distillation by providing theoretical bounds on the size and approximation error of distilled datasets. This fills a gap in the literature where previous work has mainly been empirical.\n(2) The use of random Fourier features (RFF) and kernel ridge regression (KRR) provides a solid theoretical foundation for the analysis.\n(3) The paper includes both analytical proofs and empirical validation to support the theoretical results.", "weaknesses": "(1) The evaluation of the proposed method could be further strengthened by comparing it with other baseline methods in the field of dataset distillation.\n(2) The clarity of the exposition could be improved, as some sections of the paper are not easy to understand without prior knowledge of the topic.\n(3) In line 223, two clusters and each cluster has 5000 points. Will they conflict with 10^5 points?\n(4)The paper should provide more experiments on real and bigger datasets and the visualization of KRR predictive functions on the MNIST dataset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The reviewer's comments and expert evaluation are highly valued by us. Indeed, incorporating your feedback has already led to enhancements to the paper. We eagerly anticipate continued interaction with the reviewer during the forthcoming open discussion phase.\nWe have meticulously addressed each of the comments and questions raised in the initial review. We remain hopeful that, based on our comprehensive responses, the reviewer might contemplate raising the score. Should there be a need for additional clarification, please feel free to contact us without hesitation.\n\n**Response to Comment 1 and Comment 4:**\n\nThanks for pointing this out. We first want to clarify that in this work, we did not propose new (competing) methods for distillation. We aimed at providing the first proof that answers the questions \"Why do KRR-based distillation methods work?” and “Which guarantees about the size and error can we obtain?\" Notably, this paper is the first to prove the existence of a small distilled set with its approximation error in the field of data distillation. The experiments were basically conducted to practically validate the theoretical analysis.\n\nHowever, following your valuable comment and to further improve the practical justification of our work, we have added more experiments on Cifar10 (see the attached PDF) and we are running now more experiments on SVHN -- will be added once done. \n\nFor visualizing KRR predictive functions on the MNIST dataset, can you please elaborate more on that? We will be happy to do so. \nFinally, our paper's objective is to establish the achievable loss bounds using the KIP dataset distillation algorithm. Given this, we do not see how we should benchmark other methods, as our derived bounds aren't pertinent to their evaluation. \n\n**Response to Comment 2:**\n\nThis is indeed important! Following your comment, we have revised the writing of the paper, by providing more details before each theorem/claim/definition. We also added an intuition paragraph behind the proof idea; please see the \"Clarity of our theoretical results\" section above that provides most of the added details to our manuscript -- explaining theorems 2 and 3.  \n\nFor your convenience: https://openreview.net/forum?id=XWYv4BNShP&noteId=RA4SAIBzsG\n\n**Response to Comment 3:**\n\nThanks for the careful reading. We applied thresholding to the data points so they wouldn't conflict as depicted in Figure 1. This would ensure that the KRR on this data is able to distinguish between the two classes. Following this comment, we have clarified that in the paper. \n\n------\n**Answer to Question 1:**\n\nCertainly, see responses to comments 1 and 4. \n\n**Answer to Question 2:**\n\nCertainly, and thanks for raising this. We first state that in general, deriving bounds on the size of the distilled sets helps researchers develop new distillation algorithms and test them on new datasets. Such bounds on the size and approximation error provide a mechanism to debug new suggested algorithms on these new datasets. Additionally, understanding the theory behind the existence of such small distilled sets (with providing proofs) is the first stepping stone towards providing provable dataset distillation techniques which do not exist at all in the literature. In this case, the final (long-term) goal is to leverage this knowledge and understanding of dataset distillation and provide algorithms that provably generate a small set $S$ that encapsulates all of the information in the input data $X$, and thus will guarantee the success of the training of a deep learning model on the distilled data. \n\nWe believe that our paper is the first step towards a better understanding of dataset distillation, which will allow the research community to provide better provable distillation algorithms and interpret the theory behind them. We hope that our work will provide the first theoretical stepping stone towards analyzing and better understanding the magic behind dataset distillation techniques (specifically KRR-based).\n\nFurthermore, specifically in our work, we note that our theoretical derivations indicate that any set can be distilled (achieving the approximation error we provided) as long as the labels satisfy that the solution of the ridge regression which involves the mapped distilled set via random Fourier features (RFF) is equivalent to that of the solution of the ridge regression which involves the mapped input data via random Fourier features (RFF) — From a practical point of view, this serves to indicate the success of using LabelSolve (LS) [2, 3] which aims to learn the labels given a set of distilled points, which minimizes the KRR error between the distilled set and input data, and to that end, our paper can be regarded also as a theoretical justification for such a method. We also note that our method can be used to guide a distillation algorithm in finding the best labels given the distilled set, i.e., one can use our theoretical derivations to guide a distillation method in refining the labels of the distilled set, allowing for provable guarantees and better results in the case of KRR-based distillation techniques, which then one can apply bi-level based optimization which can combine both LabelSolve for instance and KIP (or RFAD [1]) using our theory to better direct these optimizers (instances and their labels) to a better-distilled set. We leave this as an open question and direction in the field of dataset distillation.\n\n\n    [1] Loo, N., Hasani, R., Amini, A., & Rus, D. (2022). Efficient dataset distillation using random feature approximation. Advances in Neural Information Processing Systems, 35, 13877-13891.\n\n    [2] Nguyen, T., Novak, R., Xiao, L., & Lee, J. (2021). Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems, 34, 5186-5198.\n\n    [3] Nguyen, T., Chen, Z., & Lee, J. (2020). Dataset meta-learning from kernel ridge-regression. arXiv preprint arXiv:2011.00050.\n\n"}, {"review_id": "9MVXxrNjCc", "reviewer": "Reviewer_BMB1", "summary": "The paper attempts to provide the first theoretical guarantees on the existence of dataset distillation, under the setup of kernel ridge regression. The proof techniques are mainly based on theory of random fourier features. They also provide experiments which are indicated to support their theoretical results.", "questions": "1. Where is the existence of S proved?\n2. Can you give the intuition or short strategy of the proof before Theorem3? For example, why can the number of the distilled data S be $s_\\phi + 1$? How can we construct it explicitly?\n3. Where did you explain what distillation algorithm is used in experiments? How does the algorithm relate to the construction in the theoretical results?", "limitations": "Limitation is discussed in the last section.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The paper is the first attempt to theoretically guarantees the existence of dataset distillation, which is an important topic for efficient learning.\n2. Experimental results are seemingly consistent with the theoretical results, which could strength their claim if the relationship between the theoretical results and the experimental protocol was clear.", "weaknesses": "1. The paper seems not to pay attention to readability of its theoretical results. E.g., Theorem 2 is explained by just 2 lines (l.130-131) without any proof; the notations and statements in Theorem 2 and Theorem 3 are not sophisticated.\n2. The proof of Theorem 2 is not provided even in the supplementary materials, but just stated as \"A result of the proof of Theorem 1 and Corollary 2 of [ LTOS21]\".\n3. I cannot find the proof of the existence of the distilled dataset S in the proof of Theorem 3, which is the main claim in this paper.\n4. The relationship between the theoretical construction (which I cannot find) and the distillation method used in experiments is unclear. So I'm not confident in whether the experiments really support their theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to extend our heartfelt appreciation to the esteemed reviewer for their dedicated commitment to meticulously evaluating our paper. The thoughtful points and careful reading hold a pivotal role in the refinement of our work. We have diligently addressed each of these valuable concerns, and we remain enthusiastic about engaging in further dialogues with the reviewer to ensure the complete resolution of any lingering matters.\n\nSumming up, we hold the belief that our comprehensive response will ideally have a positive effect on your assessment, potentially boosting your score.\n\n**Response to Comment 1:** \n\nThank you for raising this comment. This is indeed important. We kindly refer the reviewer to the section “Clarity of our theoretical results” in the general comments  that provides most of the added details to our manuscript -- explaining theorems 2 and 3\n\nFor your convenience: https://openreview.net/forum?id=XWYv4BNShP&noteId=RA4SAIBzsG\n\n**Response to Comment 2:**\n\nWe thank the reviewer for the careful reading and professional review.  The proof of Theorem 2 can be done by following some derivations from the proofs of Theorem 1 and Corollary 2 from [LTOS21]. Following your insightful comment, and for better readability and completeness, we have restated these derivations in the appendix of the paper, while pointing out the original derivations from [LTOS21]. \n\n**Response to Comment 3:**\n\nWe thank the reviewer for raising this concern. Let $X$ be the input data, $S$ be the desired set we wish to prove its existence and denote by $\\tilde{\\mathbf{S}}$ and $\\tilde{\\mathbf{X}}$ the matrix corresponding to the instances of the image of instances of $S$ in the space of RFF, and the matrix corresponding to the instances of the image of instances in $X$ in the RFF space, respectively. \nFirst, note that $S$ can be any set of points as long as the labels $y_S$ satisfy that:\n * The solution of the ridge regression on $\\left( \\tilde{\\mathbf{S}}, y_S \\right)$ is equivalent to the solution of the ridge regression on $\\left(\\tilde{\\mathbf{X}}, y \\right)$ (the image of input data $X$ in the space of RFF); see lines 151-155 in our manuscript. \n\nIn other words, we aim to ensure that the optimal solution in the context of Ridge regression on the RFF image of $X$ and its corresponding labels $y$ is identical to the optimal solution in the context of Ridge regression on the RFF image of $S$ and its corresponding labels $y_{S}$; this was done at lines 151–155. \n\nThe motivation behind such a goal lies in the core of Lemma 4 which indicates that:\n * For every KRR in-sample prediction function $f$ with respect to $X$ defined by the instances of $S$ (referred to $f_{\\mathbf{S}}\\left[ \\mathbf{X} \\right]$ in our context), there exists a Ridge regression solution $\\beta$ obtained from training a Ridge regression model on $\\left( \\tilde{S}, y_S \\right)$ that admits an additive approximate to the MSE of $f$ and $\\mathbf{X}\\beta$; see the summation term in the inequality at Lemma 4.\n\nWith this in mind, we aimed at constructing such an in-sample prediction function using a Ridge regression solution. To that end, to ensure proper usage of Lemma 4, we have shown that through equation reformulation (involving $\\beta$ which is the solution of the aforementioned Ridge regression) and a system of equation solving, there exists a KRR in-sample prediction with respect to the input data involving the distilled set $S$, which satisfies Lemma 4 with respect to $\\beta$. With this in mind and the weak triangle inequality (Lemma 5), we derive (i) and (ii) of Theorem 3. This concludes the existence of $S$ that depends on a certain structure that the labels of the distilled set need to admit. \n\nThus, in summary, by showing that (i) $S$ can be any set with (ii) its labels satisfying a concrete structural property, and the specific (iii) derivation of the KRR solution on $S$, we proved Theorem 3. \n\nAll of these details were added to the appendix and a part of them in the relevant places of the proof of Theorem 3 following your fruitful comment. \n\n**Response to Comment 4:**\n\nWe apologize for missing this. In our experiments, we were directly minimizing the left-hand side of the equation in line 205 which directly corresponds to the KIP [1]  loss which uses KRR for distillation. This method directly satisfies our theoretical assumptions and guarantees.\n    \n    [1] Nguyen, T., Novak, R., Xiao, L., & Lee, J. (2021). Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems, 34, 5186-5198.\n\n------\n\n**Answer to Question 1:**\n\nPlease see the answer to Comment 3.\nFor instance, see also Lines 151-155 for the construction of $y_S$ given $S$, and the derivation of $f_{\\mathbf{S}}[X]$ at lines 169-187.\n\n**Answer to Question 2:**\n\nSure and thank you for pointing this out. We wrote a detailed explanation of the proof of Theorem 3 in the answer to Comment 1. Also, see the response to Comment 3 regarding the construction of S.\nRegarding the use of $s_{\\phi} + 1$: This is done to ensure that the equation system that led to the derivation of $y_S$ has infinite solutions which leads to the freedom of choosing any $S$ to be a distilled set as long as $y_S$ maintains a connection to the Ridge regression solution in the RFF space as elaborately explained in Comment 3.\n\n**Answer to Question 3:**\n\nWe apologize for missing this. In our experiments, we were directly minimizing the left-hand side of the equation in line 205 which directly corresponds to the KIP [1] loss which uses KRR for distillation. This method directly satisfies our theoretical assumptions and guarantees.\n\n\n"}, {"review_id": "fZgc3CB2tm", "reviewer": "Reviewer_piM1", "summary": "This manuscirpt first give theoretical understanding on synthetic dataset generated in dataset distillation task. In concrete, the authors prove (1) the existance of distilled datasets and (2) the generalization error is related to the \"number of effective degrees of freedom\" in the random Fourier features (RFF) regime. The theoretical bounds are further verified by simple experiments.\n", "questions": "See weekness.", "limitations": "See weekness.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. First theoretical work on the field of dataset distillation and the theoretical results are well established;\n\n2. Theoretically show the correlation between the size of distilled dataset and the characteristics of kernels in RFF regime;\n\n3. Theoretically show the generalization bound w.r.t. distilled datasets in kernel ridge regression (KRR) regime.", "weaknesses": "1. The theoretical results are biult on KRR, which has a gap to the finite-width network architectures used in dataset distillation.\n\n2. Can the derived generalization bounds provide insights on developing novel dataset distillation algorithms. For example, imporving the kernel architecture to decrease the right-handed term in the generalization bound to reduce the risk trained on synthetic datasets. In this way, the bound can be seen to be tight and impractical. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our appreciation to the reviewer for their expert evaluation, insightful remarks, positive feedback, and valuable suggestions that have contributed to the enhancement of our manuscript.\n\nWe now delve into a comprehensive discussion of the concerns raised by the reviewer. We trust that our responses provide a thorough resolution to all your queries, and we look forward to the possibility of you revising your evaluation positively. Should there be any lingering points of concern, we welcome the opportunity to address them to your satisfaction.\n\n**Response to Comment 1.**\n\nWe thank the reviewer for pointing this out. Many theoretical papers in the field of deep learning focus on infinite-width neural networks which are easier to analyze and interpret [1,2,3], as well as connecting such networks to other famous models in the field of deep learning [4,5]. In addition, such networks are widely used for the case of practical datasets distillation [6,7]. This phenomenon arises because KRR-based distillation techniques exhibit strong theoretical compatibility with neural networks of infinite width. In this context, the training process of the neural network aligns with kernel regression principles, as elegantly demonstrated by [1].\n\nTo this end, we started by analyzing infinite-width architectures that satisfy such helpful theoretical attributes. We believe it is the first step towards a better understanding of dataset distillation, which will allow us to provide better provable distillation algorithms and interpret the theory behind them. We hope that our work will provide the first theoretical stepping stone towards analyzing and better understanding the magic behind dataset distillation techniques (specifically KRR-based).\n\n[1] Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31.\n[2] Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R. R., & Wang, R. (2019). On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32.\n\n[3] Yang, G., & Hu, E. J. (2020). Feature learning in infinite-width neural networks.\n\n[4] Lee, J., Bahri, Y., Novak, R., Schoenholz, S. S., Pennington, J., & Sohl-Dickstein, J. (2017). Deep neural networks as gaussian processes. \n\n[5] Sohl-Dickstein, J., Novak, R., Schoenholz, S. S., & Lee, J. (2020). On the infinite width limit of neural networks with a standard parameterization.\n\n[6] Nguyen, T., Novak, R., Xiao, L., & Lee, J. (2021). Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems\n\n[7] Loo, N., Hasani, R., Amini, A., & Rus, D. (2022). Efficient dataset distillation using random feature approximation. Advances in Neural Information Processing Systems\n\n\n**Response to Comment 2.**\n\nThis is indeed important, and we thank the reviewer for pointing this out. For space limit purposes, we kindly refer the reviewer to our answer to Question 2 of Reviewer myfC. For your convenience: https://openreview.net/forum?id=XWYv4BNShP&noteId=q8bbHghfO8."}, {"review_id": "SiiFzEHUCL", "reviewer": "Reviewer_uCrm", "summary": "This paper provides theoretical analysis towards recent errors of recent dataset distillation methods based on kernel ridge regression (KRR).  It mainly utilizes some previous results on KRR and applies them in the context of dataset distillation. Some simple simulation results verify the derived bounds.", "questions": "1. The analysis for cases that the number of synthetic samples is smaller than the feature dimension.\n2. The analysis for cases that the output dimension is larger than 1.\n3. Experimental analysis on larger datasets. \n\nPlease refer to the weaknesses part for details.", "limitations": "I have not found issues related to this part.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper derives valid error bounds for KRR-based dataset distillation methods under some assumptions. It provides a guidance for the size of synthetic dataset that is required to result in pleasant errors. \n2. The writing is logical and consistent. The contributions of this paper and how this paper inherits previous results is very clear.", "weaknesses": "1. My major concern is that the analysis is not consistent with the typical setting of dataset distillation:\n    * This paper uses a distilled dataset whose size is greater than the number of features encoded by the kernel. However, in practice, the KRR-based methods in dataset distillation often rely on infinite-wide neural networks and in practice this is achieved by a large feature dimension, while the size of distilled dataset is in fact very small, e.g., only 1 image per class.\n    * In fact, the setting that the number of distilled samples is larger than the feature dimension makes the problem much simpler according my own experience. For example, we can directly solve the label $y$ without touching the samples $X$ as shown in Proof of (i) to get exactly the same KRR solution. Intuitively, if KRR solutions of real and synthetic datasets are consistent, predictions on data should also be consistent, which indicates that the results in the paper are somewhat trivial.\n    * Moreover, this paper assumes that the output dimension is only 1. However, the output dimension is in fact the number of classes for typical classification problems. It is unclear whether the error bounds derived by the current paper still useful in real cases.\n2. The technical contribution is not enough for a NeurIPS paper. The paper directly applies results of previous works. The results in the current paper can be viewed as an implication of previous results on the dataset distillation setting, since the setting is simple as mentioned previously.\n3. The error bounds are not tight as shown in the experiment section, which means the theoretical results are not very useful in practice.\n4. The experiments are too simple. The largest scale is only binary classification on MNIST dataset. For dataset distillation, at least results on CIFAR10 are expected as very standard benchmarks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the insights shared by the reviewer and the expert evaluation they provided. Integrating their feedback, have already made significant improvements to the paper. We are looking forward to further engagement with the reviewer as we enter the upcoming open discussion phase.\n\nWe have taken careful consideration of every comment raised in the review, ensuring a thorough response to each. We are optimistic that our comprehensive explanations may encourage the reviewer to consider raising the score. If any further clarification is required, please do not hesitate to reach out to us.\n\n*Comment 1.1:* The size of the distilled set is not related to the “feature space” dimension correlated with the NTK of infinite-wide networks or the dimension of the input. It is proportional to the dimension that is guaranteed by the “weighted RFF” of [1]. Thus, it is not necessarily large and depends mostly on the eigenvalues’ decay rate of the Gram matrix $K$ that corresponds to the kernel. For example (for shift-invariant kernels), if the decay rate is exponential, the size of the distilled set is polylogarithmic in $n$ or even $O(1)$ when $K$ has finite rank.\n\n*Comment 1.2:* We do not ensure that the KRR solution for $(\\mathbf{S},y_{\\mathbf{S}})$ is exactly the same KRR solution on the full data. In fact, the distilled set KRR solution is formulated via instances of the distilled set where the corresponding in-sample prediction function lies in a ball of radius $2\\lambda$ from the in-sample prediction function of the solution $\\beta$ to the Ridge regression (RR) model optimized for the RFF image of the full data, i,e., in our derivations, we aimed to find another in-sample prediction function in the KRR space involving $S$ such that it lies within a bounded space that would also encapsulate the optimal KRR found on the full data.\n\nFinally, the KRR objective function involves a weight vector $\\alpha$, which is used to define the in-sample prediction of any $x\\in X$ as a linear combination between each instance in the data ($S$). Thus the solution of the KRR on the entire data is not the same solution that we obtain due to the fact that these two solutions lie in two different spaces (different dimensionalities), and thus the in-sample prediction function is not guaranteed to be the same.\n\n*Comment 1.3:* The theory behind our approach can be used for the case of multiclass classification as kindly described in [1]. For multi-output data, $\\beta$ will be a matrix where our theory will hold for every column in $\\beta$ with the corresponding column of the labels matrix. We have expanded on this in our paper.\n\n*Comment 2:*  We thank the reviewer for the honesty. However, we respectfully disagree with those claims.  This result is indeed **not** an implication of previous results. While we did rely on tools from [1], the novelty of our paper lies in carefully analyzing the implied meaning of such tools and exploiting their underlying structure to our benefit.\n\nSpecifically, we showed how to design the labels of the distilled set $S$ such that certain properties will hold, i.e., we showed that we can construct a label function for $S$ where we applied variable equation reformulation to enable solving a system of equations that would (a) yield that the label function maintains a direct connection to the solution of the RR problem involving the RFF image of the input data $X$, and (b) hinge upon the minimal size of $S$ to ensure the existence of such a label vector is dependent on the dimension of the RFF space that was investigated by [1].\n\nFrom there, we further ensure the existence of a KRR solution by showing that there exists a different in-sample prediction function that is close to the solution of the aforementioned solution to the RR problem involving the RFF space of $X$ in terms of the quality of the prediction. Such existence is indeed not trivial and requires careful analysis to ensure the existence of such a trait, e.g., (a) ensuring that the minimal distilled set needs to be larger than the dimension of the RFF space to enable the existence of a label vector corresponding to a distilled set that can be any set of instances (b) maneuvering through the properties that this label vector hinges upon exploiting the underlying structure associated with such vector to ensure the existence of an in-sample prediction function that resides in the same space that the optimal in-sample prediction function which is defined by the solution of the KRR model on  $X$. At first glance, this is not an immediate pass, and it did require careful derivation and ensuring certain properties hold.\n\nOur analysis did not stop here but rather we also bounded the added error of using our distilled set leading to a different bound to that of [1]. Note that in our context, no prior paper suggested any provable guarantee on the size of the distilled set or its approximation error; our paper is the first.\n\n*Comment 3:* Initially, our proofs are crucial for advancing the field in practice. By setting bounds on size and approximation, we offer a way to analyze, validate, and debug the implementation and correctness of new algorithms when used with unexplored datasets.\n\nExploring the underlying theory supporting small distilled sets, substantiated by rigorous proofs, is a crucial milestone. This marks an initial step towards creating provably robust dataset distillation techniques, an aspect lacking in the existing literature. This is by using the foundational understanding of dataset distillation started in this work.  Hence, our work can be seen as the primary stride towards such a goal.  While more investigation is necessary for a comprehensive grasp of data distillation, this work serves as the first step in introducing theoretical guarantees to dataset distillation.\n\n*Comment 4:* following your valuable comment, we added experiments on Cifar10 (attached in PDF). Results on SVHN will be added.\n\n[1] = [LTOS21]\n"}]

Author rebuttal:
We deeply thank the reviewers for providing us with both positive feedback and valuable constructive criticism. Your professional review and careful reading have already helped us improve our work. We have thoroughly addressed all the comments raised during the initial review. If further clarity is required, please do not hesitate to reach out. Your engagement is highly valued.


We thank the reviewers for providing the following **Positive feedback**:

1. Rev BMB1: “The paper is the first attempt to theoretically guarantee the existence of dataset distillation”| Rev mfyC: fills a gap in the literature|  Rev piM1: “First theoretical work in dataset distillation + theoretical results are well established”| Rev uCrm: "The paper derives valid error bounds for KRR-based dataset distillation methods"

2.  Rev mfyC: Experimental study justifying the theoretical bounds: The paper includes both analytical proofs and empirical validation to support the theoretical results| Reviewer BMB1: “Experimental results are seemingly consistent with the theoretical results + the experimental protocol was clear".

3. The writing is logical and consistent (Rev uCrm).

4. The contributions of this paper and how this paper inherits previous results are very clear (Rev uCrm).

5. The use of random Fourier features (RFF) and kernel ridge regression (KRR) provides a solid theoretical foundation for the analysis (Rev mfyC).

**Clarity of our theoretical results**

Following your insightful comments, we revised the writing, by providing details before each theorem/claim/definition. We also added an intuition paragraph behind the proof idea.

Specifically, we added the following before Theorem 2:

The following theorem bounds the difference (additive approximation error) between (i) The MSE loss between the ground truth labels and the predictions obtained by applying Kernel Ridge regression (KRR) on the raw (original) data, and (ii) The MSE between the ground truth labels and the predictions obtained when applying Ridge regression on the mapped (full) training data via random Fourier features (RFF).

With this in mind, the goal of Theorem 2 is to set the minimal dimension of the RFF which yields the desired additive approximation ($4 \lambda$). The intuition, in our context, behind using this theorem, is to link the dimension of the RFF with the size of the distilled set in Theorem 3.

To that end, we use this error bound and sufficient size (of the minimal dimension of the RFF) to provide proof of the sufficient small size of the distilled set. This is done in Theorem 3. We added the following details to further explain it:

*The goal of Theorem 3.* is to prove the existence of a small distilled set $S$ (its size is a function of the minimal dimension of the RFF mapping required to ensure the provable additive approximation stated in Theorem 2) satisfying that:  

   (i) The Ridge regression model trained on the mapped training data via RFF is identical to that of the Ridge regression model trained on the mapped small distilled set via RFF,

   (ii) more *importantly* there exists a KRR solution formulated for $S$ with respect to the loss of the whole big data $X$, which approximates the KRR solution on the whole data $X$ (which is the goal of KRR-based dataset distillation techniques). Thus,

   (iii) we derive bounds on the difference (approximation error) between (1) The MSE between the ground truth labels of the full data and their corresponding predictions obtained by the specific KRR model (we previously described) on our distilled set and (2) The MSE between the ground truth labels and the predictions obtained when applying KRR on the whole data $X$.

*Main idea.* The heart of our approach lies in connecting the minimal dimension of the RFF required for provable additive approximation and the size of the distilled set. This is first done by showing that the distilled set can be any set $S$ of instances from the input space (e.g., images) and their corresponding labels, *as long as the corresponding labels must maintain a certain property*. Specifically speaking, the labels of the distilled set need to be in correlation with the normal of the best hyperplane found to fit the mapped training data via RFF $\tilde{\mathbf{X}}$ via the Ridge regression model trained on $(\tilde{\mathbf{X}},y)$, i.e., $(\tilde{\mathbf{S}}^T\tilde{\mathbf{S}} +$ $\lambda n$ $s_\phi$ $\lambda$ $I_{s_\phi})$ $(\tilde{\mathbf{X}}^T$ $\tilde{\mathbf{X}}$ + $\lambda n s_\phi$ $\lambda I_{s_\phi}$ $)^{-1}$ $\tilde{\mathbf{X}}^T y$ $= \tilde{\mathbf{S}}^T y_{\mathbf{S}}$.

From here, the idea hinges upon showing the existence of a KRR model (represented by a prediction function) that would be dependent on the prediction function that can be obtained from applying the Ridge regression problem to the mapped full training data via RFF.

With such a model, the idea is to retrieve the predictions obtained when using the Ridge regression problem from the mapped training data via RFF via the use of some KRR model used on the distilled set.
We thus show that through careful mathematical derivations, equation reformulation (involving $\beta$), and solving a system of equations, one is able to show the existence of a KRR solution that would allow us to use Theorem 2. Finally, to obtain our bounds, we also rely on the use of the weak triangle inequality.
To that end, we now utilize the described KRR model on the distilled data together with Theorem 2 to achieve (iii).

*For Remark 6*, we note that it is an immediate result of Theorem 3. In Theorem 3, the approximation error is a function of a parameter $\tau$ that is related to which version of the weak triangle inequality is being used. Setting $\tau = 2$, we achieve the bound in Remark 6., which is a simplified version of Theorem 3.

Finally, for better readability and completeness, we have restated the proof of Theorem 2 from [LTOS21] in the appendix of the paper.
Thanks for the valuable comments.

Meta-review: The paper provides a theoretical analysis of dataset distillation. Utilizing the KRR approach, the authors provide the first formal proof regarding the existence of a small distilled dataset capable of effectively approximating the full input set. They also engage in discussions concerning the conditions and size specifications for such a distilled dataset.

Given that this marks the first theoretical analysis within the field of dataset distillation, all the reviewers, as well as the AC, acknowledge its significant contribution. However, the original submitted version of this paper lacks clarity in its presentation, leading to numerous questions from reviewers. After multiple rounds of communication, reviewers have been satisfied with the correctness of the analysis. Consequently, we recommend the paper for acceptance and encourage the authors to incorporate all the additional experiments and discussions in the camera version.
Decision: Accept (poster)