Provable and Efficient Dataset Distillation for Kernel Ridge Regression
Authors: Yilan Chen
Wei Huang
Tsui-Wei Weng
Venue: NeurIPS 2024 poster (2024)
Keywords: Dataset Distillation
Kernel Ridge Regression
Primary area: other
TL;DR: For dataset distillation of kernel ridge regression, we show theoretically that one data per class is necessary and sufficient to recover the original model's performance in many settings.

Abstract: 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$\times$ faster on CIFAR-100. Our code is available at \href{https://github.com/Trustworthy-ML-Lab/provable-efficient-dataset-distill-KRR}{GitHub}.

Provable and Efficient Dataset Distillation for Kernel Ridge Regression
Yilan Chen UCSD CSE y1c031@uesd. edu
Wei Huang RIEKN AIP wei huang.ungggg vr@riken.
Tsui- Tei Weng UCSD HDSI
lweng@uesd. edu
Abstract
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 the original dataset. While there have been many empirical efforts to improve dataset distillation algorithms, thorough theoretical analysis and provable, efficient algorithms are still lacking. In this paper, by focusing on dataset distillation for kemel ridge regression (KRR), show that 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 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 is the number of classes. Our theoretical results enable directly constructing analytical solutions for distilled datasets, resulting 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. 15840x faster on CIFAR-100. Our code is available at GitHub
Introduction
Deep learning models are now trained on increasingly massive datasets, incurring substantial com- putational costs and data quality challenges. For instance, Llama 3 was pre-trained on over 15 trillion tokens, while the training of GPT-4 exceeded $100 million. Reducing these burdens is crucial. Dataset distillation 34 aims to distill a large dataset into small synthesized dataset such that models trained on it can achieve similar performance to those trained on the original dataset. A good small distilled dataset not only useful in saving computational cost and improving data quality but also
has various applications such as continual learning [39] 40 35), privacy protection [24 40
[8
5
and neural architecture search 39).
While there have been many empirical efforts to improve dataset distillation algorithms 24
39
38
a thorough theoretical analysis is still lacking. Izzo and Zou show single distill data sufficient for a class of generalized linear models with one-dimensional output, where the data is assumed to follow a generalized exponential density function and the negative log-likelihood is optimized by gradient descent. For a linear ridge regression (LRR), Izzo and Zou [9] show d data points are needed to recover the original model's parameter for all regularization at the same time, where is the dimension of the data and is large even for small datasets like MNIST [13 and CIFAR [12 (d 784 and 3072) computer vision. For kernel regression with Gaussian kernel, they show n data points necessary, where n is the number of original data points and can be large for modern datasets, e.g.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table Comparison with existing theoretical analysis of dataset distillation. The number of distilled data needed to recover original model's 's performance and models analyzed. "-" means not applicable. For linear ridge regression (LRR) and kernel ridge regression (KRR) with subjective feature mapping, our results only need one distilled data per class (k: S d in our setting), which is far less than the
existing work 99 21 that require n or p points. As an example, k 10, d = 3072, n = 50000
for CIFAR-10. 10. The k d, n of standard datasets are listed in Table 2
p is the dimension of feature
mapping é Rd + IPP.
LRR
Kernel ridge regression (KRR)
surjective &
non-surjective
Izzo and Zou 9
d
n (Gaussian Kernel)
Maalouf et al. 21
p (Shift-invariant Kernels)
Our work
k, (Ks I d)
k. (k S p) (Invertible NNs, FCNN, CNN, Random Fourier Features)
p in general (Deep nonlinear NNs).
k + 1 for deep linear NNs
n 60000 and 50000 for MNIST and CIFAR (see Table 2 Maalouf et al. [2] use Random Fourier Features (RFF) to approximate shif-invariant kernels that may have an infinite-dimensionall feature space, and construct p distilled data for such RFF model, where p is the dimension of the RFF model and can be l( log n1) in general cases. The results in ( 21. however, have a large gap compared with the empirical evidence that one data point per class can often achieve comparable performance to the original model [24] 39 2
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 's performance in many settings, which is far less than 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 [ compares our theoretical results with previous analysis. We summarize our contributions as follows.
data points needed in prior works 9 21 Besides, our
In Sec. 4.1 and 5 for lincar 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 real data in Sec. 42
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 + data points can be sufficient for deep linear NNs, where k is the number of classes.
Our thcoretical 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 I We verify our theory experimentally and show that our algorithm outperforms previous SOTA dataset distillation algorithm KIP 255 while being significantly more efficient, e.g. 15840x faster CIFAR-100.
S 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.
2 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 bilevel optimization problem and maximize the performance of
the model trained on the distilled dataset [4 Some recent works such as KIP 24 25), FRePo [0)]
RFAD 177. and RCIG (18) approximate the inner loop optimization of training neural networks by

---

KRR with Neural Tangent Kernel [10] or neural network Gaussian process (NNGP) kernels [14] 2) Gradient Matching: this category minimizes the distance between the gradients of models trained on the original dataset and distilled dataset [39 37 15 3) Trajectory Matching: this category
aims to match the training trajectories of models trained on the original dataset and distilled dataset 24 g 7 4) Distribution Matching: this approach directly matches the distribution of the original
dataset and distilled dataset via a single-level optimization [3
33 36]. Our work is closely related [8 in category (I). Our theoretical
to kernel-based dataset distillation algorithms [24 25 40
17
analysis provides theoretical foundations and implications for these kernel-based algorithms.
Theoretical analysis of dataset distillation. In addition to the papers discussed in the introduction, Maalouf et al. [19] propose an efficient algorithm to construct a d 1 core set of the original dataset for least mean squares problems. Maalouf et al. [20] further propose to use the SVD of the original dataset to construct a distilled dataset of size Tukan et al. (32 utilize the idea of subset selection to improve the initialization and training procedure of dataset distillation. Our paper focuses on KRR and constructs & distilled data analytically, where l usually much less than d (see Table (
3 Preliminaries
3.1 Dataset Distillation
For an original dataset { yr 3= we denote X [æi...., xx,] d and Y (y1....., vn] Rxxn where d is the dimension of the data, k is the dimension of the label the number of the classes, and is the number of data points. The goal of dataset distillation is to create synthetic dataset Xs [æst...... #s... E Raxm and Ys = .ys...... ysm] I E R with the number of distilled data points m < n, such that a model trained on this synthetic dataset (Xg, Ys) can achieve similar performance to those trained on the original dataset.
Table 2: & (number of class), d (dimen- sion of data), and (number of training data) of standard datasets.
Dataset MNIST 13
k:
10
784
60000
CIFAR-I0 12
10.
3072
50000
CIFAR-100 12
100
3072
50000
ImageNet-1k 1k 28
1000
196608
1281167
As the data dimension is usually larger than the label dimension in practice, e.g. MNIST has
= 728, = 10 and other datasets have even larger d, we consider d 2 k in this paper. For a matrix A, we use A to denote its pseudoinverse and Range (A) to denote its range space.
3.2 Dataset Distillation for Kernel Ridge Regression (KRR)
Given a kernel K(x, x') (ő(x), ((z')) where o R + EP is the feature mapping from input space to a feature space of dimension p. a KRR model f(x) = WΦ(z) trained on original data set with a predefined regularization À 2 tries to minimize following objective
Original model:
min (XX()) Y + A W|
where W E Rex and ((X) = [ ((x,)] E R The solution can be computed analytically W- You (X) where
(x) + (K( X) + AIn) x(X) = =x( T (o(X)((X) + AI,)
if >>>00 0, if 0.
x(X)*
and K(X, X) =)= ((X) T (X) E Raxn d> (X) can be considered as regularized features. Linear ridge regression is special case of kernel ridge regression (KRR) with db ((x) æ.
In this paper, we mainly consider mnite-dimensional c. This matches the practical neural networks which are usually used in dataset distillation. For thift-invarriat kernels with dimensoadi RKHS space, e.g. Gaussian
KRR is used in many dataset distillation algorithms 24
25
40
18]
kernel, they can be well approximated by finite-dimensional random Fourier features [2] 16).
Distilled dataset model: Similarly, KRR trained on distilled dataset with regularization Às 2 0 is fs( = (o) where Ws = So (Xx)* with o (z) 2r, i.e.
E IR kxd Additionally, denote X,, = 2xs (Xs)
[X 5 Xs + A
X = =X (X + Asta)
if As > 0, if x = 0.
x
X
3

---

The goal of dataset distillation here is to find (Xs, s) such that Ws W, where W is supposed be given, i.e. can be computed from the original dataset (X, Y).
4 Dataset Distillation for Linear Ridge Regression (LRR)
In this section, we first analyze the dataset distillation for the linear ridge regression (LRR), In Sec. 4.1 for LRR model, we show that &t distilled data points (one per class) are necessary and sufficient to guarantee Ws = W. We provide analytical solutions of such Xş allowing us to compute the distilled dataset analytically instead of having to learn it heuristically
existing works [24 25 40 17 [8]. Then, in Sec 4.2] we show how to find distilled data that is close to real data.
Lastly, for fixed data and only distilling labels, we show d points are needed in 4.3
4.1 Analytical Computation for Linear Ridge Regression
Theorem 4.1. When m < k. there is no Xs can guarantee W W unless the columns of W are in the range space of y. When
k and Y s is rank ki let min(m, d) and take D y W (Im Y Z, where Z E Rmxx is any matrix of the same size X Suppose the reduced SVD of D Vdiag(o ,,,)),, with of ....2 of 2 the following results hold:
1. As
0: Ws W if and only if. for any D defined above, Xs āo? and Xs
0,
f
Udiag( .r)
)r) VT where oi
1t /
otherwise.
20
As 0 Ws w and only Xs D for any D defined above.
Proof sketch. The proof can be found in Appendix C The key idea is that we want to solve Xş from Ws = Y W (Note: W is given and
select/decide Ys). When < k; this is an overdetermined system for X There no solution for X in general therefore no solution for Xs. When m 2 k and Y is rank ki the solutions of X are given by X Y W (Im - Y Y Z. where Z E gaxd is any matrix of the same size as X However, not all such X As corresponds to
a Xs. To solve Xs, we assume we have the SVD of X and solve it from the SVD of Xt C
Intuitively, original dataset (X, Y) compressed into Xs through original model's parameter k, i.e. one distilled data per class, D Y W is
W W=X Y - AI,) -'x. deterministic and Xg is fully determined by W and Yg. In this case, when As = and W is full rank, Xs can be easily computed as Xş W As example, Figure [ shows the distilled data for MNIST and CIFAR-100 when m = 10/100. When m > k. i.e. more than one distilled data per class, there exist infinitely many distilled datasets since Z is free variable to choose. When m = n, one can verify that X distilled dataset for itself by taking Y.- = Y and Z (X X AL,) X When Compared with 9 that needs data, our approach only requires data and usually S in practice. Our result is also more flexible to distill any > k data points.
" When
n,
generate more data than original dataset.
apple,
Mussum
bed
boetle
bioydl
botto
k. Discussion. The requirement for Àg can be easily satisfied by setting Às S J for a given D. want fix predefined Äs e.g. As X, we need to sample different D (by sampling different Z) so that Äs & -σ7z is satisfied, Theorem 4.1 generally suggests that a smaller Äg is better for
Figure 1: Distilled data of MNIST (first row) and 100 (second row) for LRR when

---

constructing distilled data. Practical algorithms, e.g. KIP, FRePo, and RFAD, usually use a very small regularization, which may already satisfy the requirement.
In practice, we usually do not want the dataset to be singular. Below we show that it is easy to satisfy as long as Z is full rank and the rows of W and Z are linearly independent.
Proposition 4.1. When m. 2 k and s. W are rank k, the Xg in Theorem 4.7 is full rank for any full-rank Z such that Range (W) T) n Range (Z {0).
4.2 Finding Realistic Distilled Data
In Theorem 4.1, any D satisfying the condition will guarantee the distilled dataset model to recover the original model's performance. For example, we can choose Z to be random Gaussian matrix. However, to make the distilled data more realistic and generalizable, we can select m real training data X as initialization of distilled data and find the distilled data that closest to Xs-
Corollary 4.1.1. Given fixed Xs, Xs, and Ys, the D that satisfies Theorem 4.1 and minimize is
D As
D D= Y + (Im - X (xt ())
where x is defined analogous to X Taking Y = WX Xs can further minimize the distance.
When Äs 0, Y WXs the prediction of original model for Xs. Combining this with
Theorem 4.1 we summarize the computation of the distilled data in Algorithm with ((x) = æ.
Figure shows some distilled data that close to the real data or generated with random noise.
1
2
3
4
5
6
8
9
1
2
3
4
5
6
7
8
9
(a) MNIST with IPC=50.
(b) CIFAR-100 with IPC=5.
Figure 2: Initialized data (first row), distilled data generated from real images using techniques in Sec 4.2 (second row), and distilled data generated from random noise using techniques in Sec 4.] (third row) for LRR with m 500 on MNIST and CIFAR-100 100. IPC: images per class.
4.3 Label Distillation
If we fix the Xs and only distill labels, also shown in (24) we need at least m = d to guarantee Ws W because labels have fewer learnable parameters than data.
Theorem 4.2. For any fixed Xs,
5

---

directly construct 1. when m < d, there is no Ys can guarantee Ws W in general unless the rows of W are in the row space of Xxs The least square solution Ys WXxs and [ s W|
- I- | (Xig& X As
2. when 2 d, Xs is rank d, then Ys WX Ay sufficient for Ws W.
Dataset Distillation for Kernel Ridge Regression (KRR)
In the last section, we analyzed the dataset distillation for LRR. However, more complex models such as KRR and neural networks (NNs) are usually used in practice for better performance. Therefore, it is crucial to extend the analysis to these practical settings. In this section, we first extend the results of LRR to KRR in the feature space and then construct distilled data from desired features by considering two cases subjective and non-surjective feature mappings.
The results in Theorem 4.1 of LRR can be directly extended to the KRR the feature space by replacing data X3 with features ((Xs) in Theorem 4.1 For completeness, we state it below.
k there is ((Xs) can guarantee Ws W unless the columns of W are in the range space of y. When m 2 k and Y is rank k, let r = min(m, p) and take
Theorem 5.1. When
D = Y (Im- - -Y ()) ()) Z, where Z RRxXP is any matrix of the same size as (Xss) Suppose the reduced SVD of D is D = Vdiig((l,....,..
with of 2 ... 2 of 2 0, the
following results hold:
Às >
Ws = W if and only if. for any D defined above, Às S Jop and o(Xs) =
Udiag( 1, ;r) VT where o, {
0,
if; -d==0,
11
1-
otherwise.
20;
2. As 0: Ws = W if and only if ofx(s)) = D for any D defined above.
This shows that in the feature space, features are necessary and sufficient to recover the original model's parameter. However, what get is the feature of distilled data ((Xs) instead of distilled data X itself. To get Xs, we need to construct the data from the features. To do this, we consider two cases surjective and non-surjective é. For subjective é, we show that xg from ø s)) For non-surjective & such as neural networks (NNs), we show one data per class is in general not sufficient, but k + 1 data points can be sufficient for deep linear neural networks.
5.1 Surjective Feature Mapping
When o is surjective bijective, can always find a Xs for desired ((Xs). In this case, distilled data (one data per class) is sufficient to recover the original model's performance, in contrast to 21 that needs p distilled data. We summarize the computation of the distilled data in Algorithm Here we give some examples of surjective/bijective é.
Example 5.1 (Invertible NN). Φ is invertible such as invertible NNs used in normalizing flows, then we can directly compute æ & (=(()))
Example 5.2 (Fully-connected NN (FCNN)). For (L + 1)-layer FCNN f(x) Wo(x) and
* (x) = o (W w (((())))))
where is surjective bijective activation function such as LeakyReLU, and W R with d = do 2 di 2 dr. for / E [L]. If all W!!) are full rank, given Φ(x), we can compute
= ( (w!!)) 0-1 (...wiit)) o -d((()))))
where -1 is any right inverse of a. When some W!)) are not full rank, we can still compute an approximated solution.
Example 5.3 (Convolutional Neural Network (CNN)). CNN known as special type of FCNN. To illustrate, give example of a convolution layer of 2 x 2 filter. Let w e IR 4 be convolutional

---

filter of size 2. Then the convolution operation with stride can be represented as
W1
W2
0
...
0
0
W1
2
0
0
0
3
0
((x))
:
W1
W2
W
the data is three-channel images, same operation can be done for each channel followed by a matrix that sums over three channels. When the matrix equation has a solution, the data can be solved from the feature.
Example 5.4 (Random Fourier Features (RFF) 27 shift-invariant kernel K( x') K(
x') can be approximated by random Fourier features K ((x, x') ~ (d(x), ((x")) Here ((x) =
[cos(a) + bi), cos(a, J + bp)] E IP' where a.,...,, Up E I are independent samples from a distribution P (a) = उे f jjaaa - (A)) dA (Fourier transform of K(A)) and bi.... . by are i..dd sampled from the uniform distribution on [0, 2m]. For example, Gaussian kernel K (xz [mm=2'112 Za
has IP (a) have <(x)) = / cos( cos(Arr Ax + b). Whenever p S d and A is rank p. given ((x) we can solve as,
app and b [bi,... 4p] then we Denote A [ai,...,
aarcoss (
x = A+
To ensure the computed (50(Xs) [-1,1], can normalize it by its largest absolute value, which is equivalently scaling D in Theorem 5.1 and does not affect the direction of Ws. Ws
use random Fourier features to approximate shif-in thif-invariant kernels that may have an infinite- dimensional feature space, and construct p distilled data for such RFF model, where E 9((n log n) in general cases. Their construction, however, only uses label distillation and the X5 can be any random data. Our analysis constructs Xş explicitly and shows that whenever the dimension of RFF p needs to approximate shif-invariant kernels is less than d, k distilled data suffice recover the performance of the original RFF model and approximate the original KRR with shif-invariant kernels.
5.2 Non-surjective Feature Mapping
When @ is injective or non-surjective, given a ((Xs), we may not find an exactly matched Xs.. However, we can find an approximated distilled data X5s first and then adjust Y to ensure Ws ss W. As in the label distillation for LRR case, 2 p distilled labels can guarantee Ws W.
Below we show one data per class in general not sufficient for non-surjective o, but k + 1 can be sufficient for deep linear NNs. Consider deep NN, f(x) Wo(z) with
<(x) a ( (
where a is an invertible activation function such as LeakyReLU, Sigmoid, and ( Rd dj p for 1 [L]. o(x) is an injective function in this definition.
with d do < d1
Theorem 5.2. For deep nonlinear NN defined above with fixed é. assume 2 ,y.).... (!)) are full rank. Suppose Às = 0 and Y is rank k. When m = k. there is no distilled data X that can guaran- tee Ws = W in general useless the columns of o ((W(2))-1... (W(L))- o ((X are in the range space of (())
When m = k. only ((xs) = (Y 3 W)+ that can guarantee Ws = W. One data per class is not sufficient in general as long as (Y; W)+ is not in the range space of d.. Although data is not sufficient, we show k + data can be sufficient for deep linear neural networks, where oxx) æ.
Theorem 5.3. For a deep linear NN defined above with fixed 6, assume W ,..,, W(L) are full rank. Suppose Às = 0 and Y W are rank k. Denote H Il' w (wa)) (W+ W - E p

---

1. When m = k, there is no distilled data Xs that can guarantee Ws W in general useless the columns of W + Y+ are in the range space of I w
When m > If is full rank and right singular vectors VH H E 222x2p's last p submatrix is full rank, then there exists a Xg such that W W.
Proof sketch. To find the distilled data theoretically, we need to guarantee 1) the feature d ((Xs) need to guarantee Ws W and 2) there are some distilled data Xs corresponding to the feature. For the first condition, Theorem 5.1 gives the sufficient and necessary condition of ((Xs). However, the formulation involves pseudoinverse of sum of matrices, which does not have concise formulation and therefore is hard to handle when solving Xs. Instead, in Theorem C.2 we derive a sufficient condition of ((Xs) without pseudoinverse. For the second condition, di an overdetermined system linear equations of X We find the formulation o (Xxs) such that the overdetermined system has solutions. Then combining the two conditions together, an equation that has multiple free variables. Combing the variables together and solving the equation will give the results. In the proof, we provide the algorithm compute the distilled data when the assumptions are satisfied.
& for given o' is
end up with
Applications
In this section, we show that our theoretical results can useful some applications. We first show the conditions in Theorem 5.1 can be necessary or sufficient conditions for KIP-type algorithms to converge in 6ec We also show our distilled dataset for KRR can provably preserve the privacy of the original dataset in Sec 6.2
6.1
An Implication for KIP-type Algorithms
In KIP 25
FRePo
40
READ
and RCIG [1], loss function follows is optimized:
L(Xs)
W s XX=
Y
P Ys (K(Xs, Xs) + AsIm) K K(Xs X)
Y
(1)
Below we show our results can be sufficient conditions for the above loss function to converge to 0
even if the loss function is highly non-convex.
Theorem 6.1. Suppose o(X) is full rank and W is computed with X Then
when n S p. the o (x) that can guarantee W 5 W Theorem 5.1 is sufficient for I((x))
when n 2 p. the of (3) that can guarantee W s W Theorem 5.1 0.
is necessary for L(Xs)
From this theorem, we see that KIP-type algorithms are enforcing Ws s to some extent. While
the KIP algorithm is computationally expensive, our solution for o( Xx)) can be computed efficiently
and directly utilized in KIP-type algorithms for efficient optimization.
6.2 Privacy Preservation of Dataset Distillation
For our dataset distillation algorithm for KRR, we show that the original dataset cannot be recovered from the distilled dataset, therefore provably preserving the privacy of the original dataset while having the performance guarantees the same time.
Proposition 6.1. Suppose n. > k and Y is rank k. Given Äs, o, for a distilled dataset (Xs, Ys) that can guarantee Ws W in Theorem 5.1 we can reconstruct W from ((Xs). However, given W, there are infinitely many solutions for Φ1
Since there are infinitely many solutions for (X),, it impossible recover o(X) without additional information. As long & does not contain any information of X, then X will not be able to recover from distilled dataset (X.s, s). Note See, 4.2 we use additional information (real images as reference points) to compute Xs. Therefore X resembles original images and we may recover these original images from Xs. However, we generate the distilled data with random noise, the distilled data will contain no additional information and protect the privacy of the original dataset. In
8

---

summary, we can control whether to generate realistic data by using real data as reference points or protect privacy by generating noisy distilled data as shown in Figure 2
More formally, we prove that the distilled data can be differential private with respect to the original dataset if we take Z to be random Gaussian with suitable variance.
Theorem 6.2. Under the same setting of Theorem 4.. suppose that = O, all data are bounded > B, and the smallest singular value of the original datasets is bounded from below mmin (X) > do- Suppose Ys is independent of and unknown to the adversary. Let
[}5] denote its i-th row. Let e, E (0,1) and take the elements of Z N((,, with
2 /
a 2 maxie[m]
then each row of Xs is (e,f private with 66 Y.
respect to X.
7 Experiments
(I) Analytical Computation of Dataset Distillation. In Table verify our theory of dataset distillation for LRR and KRR with subjective mapping. We compute the distilled dataset for different models using Algorithm[] [ (linear model), 2) one-hidden-layer LeakyReL.U neural network, and 3) Random Fourier Features (RFF) of Gaussian kernel. The feature mappings are constructed such that the feature dimension equal to the data dimension, i.e. = d. For NNs, we use random initialized ones and use the activations feature mappings. As increasing the depth of NNs does not improve the performance, we only use one hidden layer. For simplicity, we set Às 0 for all experiments. To choose the original model's regularization X, we split the original training into training set and validation set, and choose the À that performs best on the validation set. The results show that our analytically computed distilled dataset can indeed recover the original models' parameters and performance. Some slight differences are caused by the numerical eтrоr in recovering the data from features and computing the KRR solutions. As the purpose of this experiment is to verify the distilled dataset can recover the performance of a specific original model, we did not report the error bars.
The models KRR with different feature mappings: 1) identity mapping
Table 3: Verification of our theory. Test accuracy of original models and models trained on the distilled dataset. IPC: images per class.
Dataset
IPC
Linear
FCNN
RFF
MNIST
Original model
86.41
93.89
93.82
86.41
93.89
93.82
10
86.41
93.89
93.82
50
86.41
93.85
93.82
CIFAR-10
Original model
39.48
47.86
42.84
39.48
47.87
42.84
10
39.48
47.84
42.87
50
39.48
47.81
42.73
CIFAR- 100
Original model
14.37
21.42
18.71
14.37
21.41
18.70
10
14.37
21.52
18.69
50
14.37
21.49
18.57
(II) Comparison with KIP. In Table we compare our algorithm with KIP in terms of performance and efficiency under the setting of subjective mapping. The test accuracy of models trained on distilled datasets and averaged computational cost (GPU Seconds) are reported. The mean and standard deviation of test accuracy are computed over four independent runs. As the experiment (I), we use a randomly initialized see-hidden-lae layer LeakyReLU NN with p as the feature mapping. For KIP, we implement their algorithm where we optimize a loss function (I) and use label distillation at each training step. For our results, we compute the distilled dataset using Algorithm | Our algorithm performs better than KIP on CIFAR-10 and CIFAR-100 while being significantly more efficient. We did not report the result of KIP with IPC=50 on CIFAR 100 because the estimated running time is more than 110 hours.

---

This experiment mainly aims to show that our theoretical guarantee can be transferred to practice. As the proposed Algorithm i mainly for KRR with surjective mappings, we verified and compared with baselines in this setting. We use randomly initialized bijective NN in order to match previous algorithms that use randomly initialized NN. If pre-trained NN is used, the accuracy can be improved and may match the SOTA.
Table 4: Comparison between algorithm and KIP.
Dataset
IPC
KIP
25
Ours
Accuracy
Cost
Accuracy
Cost +
Speedup over KIP
(GPU Sec.)
(GPU Sec.)
MNIST
93.44=10.17
159
93.72:10.14
16
9.9x
10
93.75+00.10
554
93.69++0.17
34.6x
50
93.72-+0.11
3114
93.62++0.24
194.6x
CIFAR-IE
45.83:10.29
225
47.85:10.10
10.7x
10
47.50:10.29
594
47.76:10.12
20
29.7
50
47.48
3510
47.77.10.06
20
175.5x
CIFAR-100
20.08+00.20
616
21.58++0.15
20
30.8x
10
21.56.10.16
9323
21.5910.115
20
466.1x
50
~396000
21.1
25
~15840.0
(II) Privacy Protection. this experiment, we show our algorithm can be used to protect the privacy of the original dataset. Same as experiment (II), neural network with p = d as the feature mapping and train a KRR model on the original dataset. Then distill the dataset using Algorithm [ and generate the distilled data with random Gaussian noise. As shown Figure 3 the distilled data for MNIST are essentially random noise, which protects the privacy of the original MNIST dataset. At the same time, the model trained it can recover the original model's performance of 93.87% test accuracy.
one-hidden-layer LeakyReLU
Figure 3: Distilled images of MNIST generated from random noise for a two-layer neural network.
m 10 (first row) and 100 (second row).
8 Conclusion and Future Works
In this paper, by focusing on dataset distillation for KRR, we show that one data point per class already necessary and sufficient to recover the original model's performance 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 not sufficient general, + data points can be sufficient for deep linear neural networks. Our theoretical results facilitate the direct construction of analytical solutions for distilled datasets, leading to provable and efficient dataset distillation algorithm for KRR. Additionally, we have developed applications for KIP-type algorithms and privacy protection.
Several future research directions are worth exploring. First, while the current analysis shows that I data points are generally insufficient for non-surjective deep non-lineat neural networks, determining the minimum number of distilled data points required remains an open question worthy of investigation. Second, this paper focuses on KRR with fixed feature mappings, which differs from some empirical works that train all neural network parameters. Extending the analysis learnable feature mappings would bridge this gap and provide further insights.
10

---

Acknowledgement
The authors thank the anonymous reviewers for valuable feedback the manuscript. T.-W. Weng is supported by National Science Foundation awards CCF-2107189, IIS-2313105, IIS-2430539, the Hellman Fellowship, and Intel Rising Star Faculty Award.
References
[1] Nicholas Carlini, Vitaly Feldman, and Milad Nasr. No free lunch in" privacy for free: How does dataset condensation help privacy". arXiv preprint arXiv:2209. 14987, 2022.
[2] George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexei Efros, and Jun- Yan Zhu. Dataset distillation by matching training trajectories. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Puttern Recognition, pages 4750-4759, 2022.
[3] Randall E Cline. Representations for the generalized inverse of sums of matrices. Journal of the Society for Industrial and Applied Mathemttcc, Series B: Numerical Analysis, 2(1):99-114, 1965.
[4] Justin Cui, Ruochen Wang, Si Si, and Cho-Jui Hsich. Scaling up dataset distillation to imagenet- IK with constant memory. In International Conference on Machine Learning, pages 6565-6590. PMLR, 2023.
[5] Tian Dong, Bo Zhao, and Lingjuan Lyu. Privacy for free: How does dataset condensation help privacy? In International Conference on Machine Learning, pages 5378-5396 PMLR, 2022.
[6] Cynthia Dwork, Aaron Roth, et The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, ((3-4):211-44 407, 2014.
[7] Yunzhen Feng, Shanmukha Ramakrishna Vedantam, and Julia Kempe. Embarrassingly simple dataset distillation. The Twelfth International Conference on Learning Representations, 2024. URL httpps///openreeviww wwtp://wwww.eeeeooooooooo/oooo/.
[8] Ziyao Guo, Kai Wang, George Cazenavette, HUI LI, Kaipeng Zhang, and Yang You. Towards lossless dataset distillation via difficulty-aligned trajectory matching. In The Twelfth Inter- national Conference on Learning Representations, 2024. URL httphttts:///c //ppr/eeeeeeeeeeee/eeeeeeeeeeeee net/
forum?id-=TTBLO0hhht
[9] Zachary Izzo and James Zou. A theoretical study of dataset distillation. In NeurlPS 2023 Workshop on Mathematics of Modern Machine Learning, 2023. URL httpss
[10] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[11) Jang-Hyun Kim, Jinuk Kim, Seong Joon Oh, Sangdoo Yun, Hwanjun Song, Joonhyun Jeong, Jung-Wor Woo Ha, and Hyun Oh Song. Dataset condensation via efficient synthetic-data param- eterization. In International Conference Machine Learning, pages 11102-1101 11118. PMLR, 2022.
[12] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[13] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-234, 1998.
[14] Jachoon Lec, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington. and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint arXiv:1711.00165. 2017.
[15] Saehyung Lee, Sanghyuk Chun, Sangwon Jung, Sangdoo Yun, and Sungroh Yoon. Dataset condensation with contrastive signals. International Conference on Machine Learning, pages 1236-1 PMLR, 2022.

---

[16] Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards unified analysis of random fourier features. Journal of Machine Learning Research, 22(108):1-51, 2021.
[17] Noel Loo, Ramin Hasani, Alexander Amini, and Daniela Rus. Efficient dataset distillation using random feature approximation. Advances in Neural Information Processing Systems, 35: 13877-13891, 2022.
[18] Noel Loo, Ramin Hasani, Mathias Lechner, and Danicla Rus. Dataset distillation with convexi- fied implicit gradients. In International Conference on Machine Learning, pages 22649-22674. PMLR, 2023.
[19] Alaa Maalouf, Ibrahim Jubran, and Dan Feldman. Fast and accurate least-mean-squares solvers. Advances in Neural Information Processing Systems, 32, 2019.
[20] Alaa Maalouf, Ibrahim Jubran, and Dan Feldman. Fast and accurate cast-mean-square solvers for high dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(12):9977-9994 2022.
[21] Alaa Maalouf, Murad Tukan, Noel Loo, Ramin Hasani, Mathiss Lechner, and Daniela Rus. On the size and approximation error of distilled sets. arXiv preprint arXiv:2305. 2023.
[22] G.
Marsaglia and G. P. H. Styan. When does rankke+b)-srmm(((arrknkkk?? Canadian Mathemat- ical Bulletin, 15(3):451-455 1972. doi: 144155//MBB-1922-0222
[23] Lingsheng Meng and Bing Zheng. The optimal perturbation bounds of the moore-penrose inverse under the frobenius norm. Linear algebra and its applications, 432(4):956-963, 2010.
[24] Timothy Nguyen, Zhourong Chen, and Jaehoon Lee. Dataset meta-learning from kernel ridge-regression. arXiv preprint arXiv:201 1.022001100000 2020.
[25] Timothy Nguyen. Roman Novak, Lechao Xiao, and Jachoon Lee. Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems, 34:5186-5198, 2021.
[26] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, figh-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[27] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
(28) Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):111-2522 2015. doi: 10. 10.100//s1 1233-01--0------1
[29] Noveen Sachdeva and Julian McAuley. Data distillation: A survey. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. httptpps//gopneeeveeeeeee/rraese ImXMXP74TO] Survey Certification.
[30] James R Schott. Matrix analysis for statistics. John Wiley & Sons, 2016.
[31] Felipe Petroski Such, Aditya Rawal, Joel Lehman, Kenneth Stanley, and Jeffrey Clune. Genera- tive teaching networks: Accelerating neural architecture search by learning to generate synthetic training data. In International Conference on Machine Learning, pages 9206-9216. PMLR, 2020.
[32] Murad Tukan, Alaa Maalouf, and Margarita Osadchy. Dataset distillation meets provable subset selection. arXiv preprint arXiv:2307 201.0000000 2023.
[33] Kai Wang, Bo Zhao, Xiangyu Peng, Zheng Zhu, Shuo Yang, Shuo Wang, Guan Huang, Hakan Bilen, Xinchao Wang, and Yang You. Cafe: Learning to condense dataset by aligning features. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 12295-1200, 2022.
12

---

[34] Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint arXiv: 1811.10999 2018.
[35] Enneng Yang, Li Shen, Zhenyi Wang, Tongliang Liu, and Guibing Guo. An efficient dataset condensation plugin and its application to continual learning. Advances in Neural Information Processing Systems, 36, 2023.
[36] Zeyuan Yin, Eric Xing, and Zhiqiang Shen. Squeeze, recover and relabel: Dataset condensation imagenet scale from perspective. Advances in Neural Information Processing Systems, 36, 2024.
[37] Bo Zhao and Hakan Bilen. Dataset condensation with differentiable siamese augmentation. In International Conference on Machine Learning, pages 12674-12685. PMLR, 2021.
[38] Bo Zhao and Hakan Bilen. Dataset condensation with distribution matching. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 6514-6523, 2023.
[39] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. arXiv preprint arXiv:2006.05929, 2020.
[40] Yongchao Zhou, Ehsan Nezhadarya, and Jimmy Ba. Dataset distillation using neural feature regression, Advances in Neural Information Processing Systems, 35:9813-9827, 2022.
13

---

Appendices
Algorithm 1 Dataset distillation for kernel ridge regression
Input:
Number of distilled data number of classes k. regularization Aş, feature mapping ø, original model's parameter W, generate from original data or random noise
1: if Generate from original data then
2: Sample balanced initialized data Xs from original dataset. Initialize Ys corresponding
one-hot labels
3: Compute OAS (Xs)
4: if Rank (Wess (Xs) = k then
5: Ys Wors (Xs)
6: end if
7: Construct Z = (Im - Y) (Xs)( Ygw).
8: else if Generate from random noise then
9: Sample Z from random noise. Initialize Ys balanced one-hot labels
10: end if
11: Compute D Y W (Im Y Z
12: if As > then
13:
Compute the SVD of D, Vdiag(d).....
14:
if' As 2077 then
15:
As 4072
16:
end if
Construct d(Xs) = Udiag( 01, o,, VT where = 0f 0 and 1-V4-4
17:
2n%
otherwise.
18: else if Às 0 then
Construct ((xs) D
20: end if
21: Construct Xs from o(Xs)
Output: Xs.As
A Broader Impact
Our approach can be used to protect data privacy, which may have positive societal impact. There are no particular ethical concerns we are aware of.
B Additional Experiment Details
All the experiments are implemented with PyTorch 226 and conducted on single 24G A5000 GPU.
14

---

C Proofs for Linear Ridge Regularization
C.1 Analytical Computation for Linear Ridge Regression
Theorem 4.1, When m < k. there is no Xs can guarantee Ws W unless the columns of W are in the range space of s. When
k and Y rank k. let min(m, d) and take Y s W (Im- Y S Z. where Z E Rmxd is any matrix of the same size as s. Suppose with of 2 ... oz 2 the following results the reduced SVD of D o.....
D
hold:
Às
0: Ws W if and only for any D defined above, As S प,द? and Xs
0,
io
Udiag( 01, σr) V where o;
11 11 1-V1-4
otherwise.
2n²
As - Ws = W and only if D+ for any D defined above.
Proof. Recall Wg Y where
X (X]Xs + +AIIm)
X3 = X3 (X5X² AsIa)
if As > 0,
X
if As
Let Ws W
YsX, W.
When m < k this an overdetermined system for X There is no solution for X general therefore no solution for Xg unless all the columns of W are in the range space of Y When there a solution, we can solve it as following m 2 cases.
In the following, we consider the m 2 k case. Since m 2 k and Ys is rank k the solutions of X given by
x Y W + (Im - Y Z
where E Rond any matrix the same size as X When k = m, the solution is unique x W. However, there are solutions for x does not mean there are solutions for Xs. Next, we need to solve Xs from Xt.
When m S d. Suppose the reduced SVD of Xg is Xg UEVT where Σ diag(o1,.... Tm) E Rmxm V mm is unitary matrix and U Rdx is the first m columns of unitary matrix. Then when Äs > O,
X (x,Xs "
(VEU UEV + +m VEU
(VE'VT + +1SIm) VEUT
(V + + V VEUT
(V +
V VVVEUT
VVE + +
EUT
Vdiag(
01
m d2 + +
UT.
(3)
of +
Combining 2 and 3
we must have
Vdiag(
On
JU = Y W + (In - Y Z.
of + As
02 + As
Denote D = Y W + IIm Ys) Z.
Given D, we can compute its reduced SVD D
V' d'dia((o(, on U with of 2
> o'n. Note that SVD of matrix is unique. Since
15

---

"T) = Vdiag( 01 D = V'diag(o )
U we must have V = V U-U-U U.
of
..... o +is
and
0i
0 0 + Xs
That is
d0 o, + Aso =0
When of 00, we have 0, 0. When of * and Xs S 1
S 1
has solutions given by
10.
0 + 4Aso!
20
Take the above computed U, V, and E, we can construct Xs. Above shows such Xs is necessary condition for Ws W. To show the sufficiency, take such Xs into Ws.
m UUT
Ws Vdiag
of AS
o + As
Vd 11...,, "
YsD
= =Ys (YS + (Im - YY Z)
= W
which shows a sufficient condition.
When Às = 0, we have Ws = YsX Let Ws = Y
W. The solution for X is
X = = W + (Im Y s) Z
where Z jgaxd is any matrix of the same size X Therefore
Xs (Y3 w + (Im Y Y z)*
Similarly, this is necessary condition for W 5 = W. To show the sufficiency, take such Xş into Ws.
Ws = Ys Y W + (In. Y3 Z)
= W
which shows a sufficient condition.
When m > d. Suppose the reduced SVD of Xs UEVT, where Σ diag(o),.... oa) E Rdxd U E dddd is unitary matrix and V E goxd is the first columns of unitary matrix. Then when Äg > 0,
x As = X [X + +AsId)
VEUT (UEVIVEU + A
VEU (UE'UT + +AsTa)
~EUU (U + Asta) UT)
VVUUU U (>² + Asla)) UU
VE 2 + AgLs) T
dd T 03
Vdiag(
(4)
of As
As
Then we proceed similarly to the m case. Last, we can unify two cases by taking min(m, d).
Proposition When m 2 Is and s. W are rank k, the Xs in Theorem 4.1 is full rank for any full-rank Z such that Range (W") 1 Range (z (0).
16

---

Proof. Xs is computed from = Y W + (Im -YyYs) Z. It is easy to check that Xs is full rank if and only if D is full rank.
When Ys and W are rank k, Rank rank, by Sylvester's s rank inequality.
S W) = k. Since Rank Y Ys) = m k and Z is full
Rank( Y Ys) Z) 2 Rank(Lm m Yz + Rank(Z) m
k min (m, d) m
= min(mm d) &
For D Y + (Im- Ys) Z, since the columns of Y W Rangee (Y3) and the columns of (Im Ys) (y E Null (Ys). By the fundamental theorem of linear algebra, Range (Yg) and Null (Ys) are orthogonal subspaces of R Therefore Range (Y3 W) n Range (m Y Z) = [0). This can also be seen from (Y) T (In - Y s)) Z = 0.
which shows their columns are orthogonal to each other. If we have Range (WT) n Range (Z
(0), then Range ((Y w) Range (ZT (Im- Y = (0). By 22
Rank Rank(D) = Rank Y W) + (aank(I,.. Y Z 2 k + min(m, d) k = min(m, d).
Therefore D full rank and X is full rank.
C.2 Characterization of Distilled Data without Pseudoinverse
In the last section, we give analytical solutions for X that can guarantee W; expression of Xs involves some pseudoinverse calculation and the explicit expression of Xs remains unclear because there is no concise formulation for the pseudoinverse of sum of matrices. this section, we give some direct characterization for Xs.
W. However, the
Again, supposed its reduced SVD is Xs (ddag(ol....... Jr VT, where min(m, d). When D
As > 0, from Eq. (3) and Eq.
X As
Vdiag( of o7 U and Xxs
Udiag( ojtAs :......... ..... o2 V where |dag(( of+As o#tAs Jis o, As if else 0. When Äs 0, X = = and XA. = Xss Given XAo and As. we can easily compute Xs by
a,
SVD. Below we give conditions for W s = W through Xxg.
Suppose the eigenvalues of Xxy are of. Then by the definition of XAg. 0f ai = if > That
of - ooo + As =0
Only when xf2 2 4hs, there solution(s) 0; a: / of 4As Xs corresponds to XAs the nonzero singular values of Xx₃ need to be larger than or equal to 2 22ss. When Às = 0, there is no requirement.
Therefore, make sure there is
Theorem C.1. Suppose k S d and W is rank k. Take
X = w +
Z',
where E pddd is any matrix of the same size as Xxg such that Xxs is full rank.
1. When m S d, it is a necessary condition for Ws W.
2. When m 2 d, it is a sufficient condition for Ws W.
Proof. Case 1. When m < d, recall that Ws = Y YsX f
Set the parameter to be the same
Ws = W and try to solve Xx.
W Y X W
Multiply XA. on both sides. Since XA₂ bg is full rank and X Ng X1g Im.. we have
WX = Ys
17

---

Since k I d and W is rank k, Xs has infinite many solutions. The general solutions are
Xx W (I. W W) Z
(5)
where Z' E Rd is any matrix of the same size as Xs. Therefore, this is necessary condition for Ws = W.
Case 2. When m 2 d, to show the sufficiency, for any Xxg W+Ys + (La w+W)Z,
wX = W W Ys + (L. W W) z = =Ys
Multiply X on both sides. Since XA.X,
-ds
W Y Ws.
From these two cases, we can also conclude that when m d. such XAs W (Ia ---We * w) Z' is sufficient and necessary condition for Ws = W.
Below we give sufficient condition of Xx2 when m 2 k. It will be used in the proof of Theorem 5.3 Theorem C.2. When m 2 k, a sufficient condition for Ws W Ys is rank and
X = - (Ia W W) z (Im Y
where E Bdxmm is any matrix of the same size as Xxg-
Proof. When m 2 k for the sufficient condition
Xxs W+Ys and
W
(Ia W W) Z [Im - s)).
denote
=
(La W+W) Z [Im Y Y s). Since A A B
a AB O, b, 3 (A B) A +++B+.
Therefore
x (W+ YW+Yss* + [L. W W+ Z' (Im. Y
-Y + [ W W) Z' (I... - Ys]
where the last equality is because W and Y are full rank and therefore (W+Ys)+ W.W. From this, we have
Ws Y
Ys Y + [L. W+ (I.. v)Yz))*)
W W [I. w+ Z (Im Y)Ys)]"
For any matrix A and B, if AB = 0 then B+A+
0
30
Since
(La- w) Z' (Im Y Y = Ys (L-- w w) Z' (Im Y Y Y
There-
fore we conclude W = W. Note in this case, we do not require XAs to be full rank.
C.3 Finding Realistic Distilled Data
Corollary 4.1.1
Given fixed Xs, Xs, and Ys the D that satisfies Theorem 4.1 and minimize
D
X
is F
D= D=Y$ W + (Im Y (xt Y)
where x+ L is defined analogous X Taking Y WXAe can further minimize the distance.
18

---

Proof. Given fixed Xs. and Ys the linear ridge regression trained on Xs is
Ws= Y As E m2
By Theorem 4.1
ensure Ws W, we need X to be equal to some Z, where Z is a free variable to be determined. Therefore let
Y
(Im
Y&W + (Im Y Z X As (Im Y=)
That is
Y
Since - Y
( s) is idempotent and therefore singular, does not have a solution general (because the system of equations can be inconsistent). The least-squares solution is
= [Im Y
(xt - Y w = (Im Y
(xt Y W
where verify that (Im Y Ys)) 5) Il -Y' by SVD. This least-squares solution
minimize
(1m Y X Y W
X x
Take such into D, we have
D= Y W + (Im - -Y
(Im - Y
8 - Y -
= Y + (Im - YgYYs) (xts - -Y w)
Then we have the difference between D and X is
x As
D X Y W (Im YsYs) (xts YgW)
Y (x - W)
=Y`s (YSX w)
To further minimize the difference, we can let yg = W. The least square solution is Y
WX
C.4 Label Distillation
Theorem 4.2 For any fixed X
1. when < d, there is no Yg can guarantee Ws W in general unless the of W
in the row space of X The least square solution is Ys WXxe and |[ W||
| (Xxs XT, -Ia]l-
when 2 d, Xs rank d, then Y WX sufficient for W W.
Proof. When m < d, let
Ws s W Ag
and solve Ys. Ys does not have solution in general unless the equations are consistent, i.c. the of W the row space of X The least-squares solution is
Ay
Ys WX As
Therefore we have
W = YSXAS = WXA, X+
Then we can bound the difference between Ws and W,
|| W
= W
X x
Ia)
|
(X X - -ba]
19

---

When m 2 d, let
Ws = YgXis A3 = W
and solve ys. Since Xs is rank d, then X As = Xg (X5X3 + AsIa) -1 is rank d and Y has solutions. Take the minimum norm one,
Ys WXAs
To show the sufficiency, take Y into Ws.
Ws = WX XAs W
20

---

D Proofs for Kernel Ridge Regression
Theorem 5.1 When m < k, there is no ((Xs) can guarantee Ws = W unless the columns of K and Y is rank k. let r min(m, p) and take D= Y (Im- - -Y Yss Z, where Z IEmXP is any matrix of the same size ((xs) Suppose the reduced SVD of D is D Vdiag(oi.......o
W are in the range space of Y When
with oj 2 2 of 2 0. the
following results hold:
1. Às >
0: Ws W if and only if. for any D defined above, As S I and o(Xs)
0,
o 0,
Udiag(O1,-.. ,r)
V where or 11
otherwise.
As 0: Wg w and only (Xx)) D for any defined above.
Proof. The proof same as Theorem 4.1 but just replace Xs with oi s).s.
D.1 Deep Nonlinear Neural Networks
Theorem 5.2 For deep nonlinear NN defined above with fixed 6. assume W W are full runk. Suppose Äs = 0 and Y is rank k. When = k. there is no distilled data Xs that can guaran-
tee Ws = W in general useless the columns of a ((W(2)) (W(2))-1... (W(r))- o (X are in the range space of W().
Proof. To get distilled data Xs that can guarantee Ws s
W, the sufficient and necessary condition
is that
1. ((Xs) need guarantee Ws W.
2. There is some Xs corresponds to such o(Xs) Equivalently X5 is recoverable from o sXxs).
For the first condition, when Äg = 0, we have shown in Theorem 5.1 ((Xs) has to be
s (Yg w + (Im Y Ys)
When k and Y is rank k this reduce (Xs) (Y w)+
2. For the second condition, given d(xs) (W(L).... (w())ss)). solving X is same as solving
W x ((wie)) ... (wll)) (w())"/--
0- " (0(xs))
When m = le and combined with the first condition, it becomes
w -0- ((wie)) -1
0-1 \
Since this is an over-determined system of linear equations and RHS is fixed, It does not have solution in general unless The RHS is in the range space of W11)
D.2 Deep Linear Neural Networks
Theorem 5.3 For a deep linear NN defined above with fixed o, assume ( W(L) are full rank.
Suppose Às = 0 and Y s, are rank k. Denote = Il' w (w())+ (W w - 11)
R2x22
1. When m k, there is no distilled data Xs that can guarantee Ws = W in general useless the columns of W Y are in the range space of II w()).
21

---

2. When m > k, H is full rank and its right singular vectors VH E R2 's last p submatrix full rank, then there exists a X such that Ws g W.
Proof. To get a distilled data X that can guarantee Ws W, the sufficient and necessary condition that
1. ((xs) need guarantee Ws W.
There is some Xs corresponds to such dXss). Equivalently Xs solvable from ((Xs).
1. For the first condition, when Aş = O, we have shown in Theorem 5.1 ((Xs) has to be
(Y W + (Im Ys 2)*
When and Y 8, W rank k; this reduce ((Xs) 5)
W Y g. When k; from
Theorem C.2 we know 6(X, (Xs) w Ys (Ip W) Z' (Im
Y 8 Ys) for any Z' E 1Rxx
also a suffeiien condition for Wg = W.
For the second condition, given ((Xs) -II w Xs, solving Xs is same as solving
x = (II w
I
o(Xs)
This is an over-determined system of linear equations. necessary and sufficient condition for any solution(s) to exist that RHS in the range space of W(1) or equivalently Xs = (wO)+ (IL-2 w o(Xs) is solution. Take this solution into equation,
W (Wrr)²
+
I
L
II W
L
((Xs)
((Xs)
1=2
V=2
1 (h- wwa))
(Wrc)))
II w())
I.
-1
x(Xs)= =0
( mh)) -1 o(Xs), we have
Solve the equation for
I|
1. W
-1
[,-W()) ( +) [I, 10- (wxz)) ) z
o(xs) =
I I, w
1=2
I - ((()) (w())()
(I, w()) (wrx)))) Z
Ip
Ip I, (-- (wra)") ()) Z
( (w(') Z
for any Z, E IR Therefore to guarantee X is solvable from o(Xs), 6(Xs) have to be in the form of
(Xx) = IIl w (wi))
Z
(8)
1=1
X In this case, X5 = (W()) + Z, For any Zi, W() (W())+ a projector that projects Z₁ to the range space of (11). Combing two conditions
7 and 8 we need to solve
L
II w (w(')) + z, = (X3 W + (Im Y 2)+
for Z and Zi
22

---

1. When m = k, it becomes
L X Ws
II
Since Ih w Rexd and p > d, the equation has solution only when W+Ys g is in the range space of Il W
2. When (Lp W W) Z' (Im Y for any Z' E Rex is sufficient condition for Ws W. Therefore we can instead solve
k, from Theorem C.2 know 6Xxs)
W+ Ys
L 1 (wr))* Zi = W (1p W W Z ( 1=1
Combine the variables Z' and Z₁, we have
II' w (w(')* (W+W ()w--))] -b,)
Z Z' (Im - Y Ys) = w
Denote H Ih w (W(!)+ the solutions are
(W+W- 1,) E Rpxxp, If H is full rank (rank p), then
Iz
Z z' (Im - Y = H + (Iep H) Z2
where Zg E 22xx is any matrix. For any RHS, we can find a solution for Z1. Next, we try find solution for Z' and Zn such that the equation is consistent. Suppose the full
SVD of H UEVT, where U E Rpxp, E E Rpx2p V E R2px2p, Then 12p H+H V Vdiag O, O. V
10
Vpt1 VT Then the equation be-
comes
Z Z' (Im
0
V 74
V2p V Z2
H+
Y Y
b
Denote B
VT
E 22xxm
Since Z2 is solvable from any B, we can instead solve
bap
B. Then the equation is
b p+1
Z₁ [Im - Y
Vp+1
V2pl
-
Z'
2p
C
Denote H+W+Y
where C₁, C2 Roxm are the first and last p rows. Then the
C2
equation can be partitioned into two parts
p+1
V Mpt1
V2pl1
Zi C₁
(9)
Dzp
b bp+1
VV Wp
V 22p1p+122p
Z' (Im - Y C2
(10)
bap
where IV PVt1 last p rows.
V V2ply.p denotes its first p rows and [V p+1
V V V2ppp412p denotes its
For the first equation, there is always solution for Z, So we will mainly
23

---

care about if there is solution for the second equation. For the second equation, when
p+1
[Vp+1 12 full rank, then there is always a solution for and therefore
2p
solutions for B and Zg. The equations do not depend bi..... bp they can be anything.
In conclusion, when [V p+1
V2lp+112p is full rank, there is solution for Z₁ and Xs. To construct Xs, take any Z' and ((Xs) W+Ys + (Tp w) Z' (Im Y Ys)s). Then construct H I1 w (way) (W+ - 1,) E Rox22 and its SVD H UEVT. If
[V p+1
V 1:2p full rank, solve (TO).
bp+1
V p+1
V p1:2p
[z' (Im Yss) -C2]
bip
Then get Z₁ from
9
b p+1
Z ppt1
V2pli.2
:
+ C
b2p
Then we can construct X5- = (W(1))+ Zi
D.3 Additional Trainable Layer
Here we consider whether adding an additional trainable layer to the distilled dataset model will help dataset distillation. Suppose original model is I' [xx = Wo(z) and distilled dataset model is fs(x) = AΦ()(z) where E RPxP is the additional trainable layer. In this case, the feature of distilled dataset model is Ao(x) instead of σ(x) and the analytical solution for W s becomes Ws
Ys (() A + AsLm)
(Ao(Xs)) Here the objective becomes Ws = W.
Theorem D.1. When m < and Às > O, suppose Y g is rank k. there exists distilled dataset (Xs, Y) can guarantee W W if below equation has solution for some Z E Rmxp such that ((xs) is full rank and some e > 0:
(Xs)+ Y W (Im - Y Z. c+1
Proof. What we want now is WsA = W. That is
Ys ((A)(X))) Ao(Xs) + + -1 (Ap(Xs))
A W
For given Yss since S m, the solution of LHS is
(o(Xs) A AØ(Xs) + AmIm) & (Xxs) 8) T A A Y W (Im Y Z
for any Z E IRxx, Denote RHS as D Y W + (Im Y Y s) Z and multiply the inverse on both sides,
o(Xs) A A = (ø(Xs) Aø(Xs) + )sIm) D
Arrange the terms,
((xs) T AT (X))DD) = AsD
(
there exists D such that I, ((Xx) rank p.
Xs) T A =
24

---

Here o(Xs) E Rmxp, Since m there are solutions for A A A. Take the minimum norm one:
A = As (x(x))
(T, (Xx))D)
Since A T A is symmetric and positive semidefinite, the RHS also needs be positive semidefinite. A sufficient condition that D (Ip- (XXs)
(X) for some constant Solve it
get D = c (Xs)). In this case, 1p 0 (Xs D = L c (Xx) is indeed full rank.
By the definition of D and D (Xs) + the problem boils down to
c c o(xs)* Y W + (Im. Y Z
Compared with Eq. 7 adding one additional trainable layer only relaxes the original equation with constant scaling and does not help too much.
25

---

E
Applications
E.1 An Implication for KIP-type Algorithms
Theorem 6.1 Suppose ((X) is full rank and W is computed with À 0. Then
1. when $ p. the (Xx)) that can guarantee W W in Theorem 5.1 is sufficient for L(Xs) 0.
2. when 2 p. the (X)) that can guarantee W W in Theorem 5.1 is necessary for L(Xs)
Proof. The (Xx)) Theorem 5.1 guarantees W 8
W. Since À and ((X) is full rank,
W + Therefore we have
Ws = Yo(X)*
When & p, multiply ((X) on both sides,
Wxo(X) Y
which implies s(Xs) [ (Wo6()) YI 0. This shows that ((Xs) in Theorem 5.1 is sufficient for L(Xs) = O.
When 2 p. the L L(Xs) 0 means
W wso(X) =Y
Multiply o(X)+ on both sides, we have
Ws YØ(X)+ = W.
This implies that Wss W a necessary condition for I.(Xs) Since the @ in Theorem 5.1 is sufficient and necessary for Ws W. Therefore ob ((Xs) in Theorem 5.1 is necessary for L(Xs) O.
E.2 Privacy Preservation of Dataset Distillation
Proposition 6.1, Suppose n > and is rank k. Given As, for a distilled dataset (Xs, Y)) that can guarantee Ws = W in Theorem 5.1
W, there are infinitely many solutions for we can reconstruct W from o(Xs). However, given
Proof. Since W Ws. reconstruct W by simply compute Ws.
When n k, since W (X) and Y is rank k, given W, there are infinitely many solutions for dx (X)+,
2 x + (I, - Y
for any Z E Raxp, Using similar approach as the proof of Theorem 4.1
can solve ((X) by
SVD and there are infinitely many solutions for (XX). Therefore it is impossible to recover oi (X) without additional information.
Theorem
Under the same setting of Theorem 4.1 suppose that = 0, all data are B, and the smallest singular value of the original datasets is bounded from du- Suppose Ys s is independent of and unknown to the adversary. Let [X denote its i-th row. Let e, (0,1) and take the elements of N(0,, with
6.2
bounded I
below Gmin
2 maxig[m] 2 (1((125/8)) bY then each row of Xs is (c, diiff-eiifrllt private with
respect to X.
Proof. We prove that D W Y Z is (c, diffferrret private with respect to X using the Gaussian mechanism 6 Then follows that Xs (e, d)ffifferett private since the computation from D to X is deterministic and independent with X.
26

---

We first show the sensitivity of Y & W is bounded and then use (Im. Ys) Z as random Gaussian apply the Gaussian mechanism. Without loss generality, suppose have X' = [21 F22 ................................ Fn. E RRdx that differ only in the first point and their resulting parameters are W and W'. Since X = O. W = YX+ For each row of Y W, we have
Ys)
datasets
(=) ........ E..]
Y k W [Y W
Y Y x x²)
11
$ Y Y
x X
112
x || Y
X - -x"11s
|
|
112 ||
|| ziilr
2
2B
|
of
where the third inequality is due to Theorem 2.2 in Meng and Zheng [23 Therefore the sensitivity
of [ W bounded. Suppose the elements ~ N (0, o²), the elements of (Im Y Y Z
are also Gaussian. The i-th row of (Im
Y Y
is
I
s)
0². each row Y : W IIm Y s], Z, we can apply the Gaussian mechanism. Let (0, 1), by
whose elements are independent Gaussian with the variance
2 Therefore, for
Theorem 3.22 in 66, as long as
2B [m Y Y 5) 2 (l((1.25/0) | 1|1
offe
2 2/In(1.25/8)/)
Y 1
oi. [Imm
s
[Y - is (e, 8) diifferential private. Take a to be the maximum one so that all the rows are (e, dddffferenta private.
2 ln
Y
2
mm oic
In
Y Y
27

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims made match the theoretical and experimental results
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals motivation long is clear that these goals attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See for example the last paragraph in Section g
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, c.g., if the approach only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to- seech-to-teet system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
The assumptions stated in the Theorems and all the proofs are in the Appendix.
Guidelines:
28

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification:
The experiment details are provided in Section
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
model (e.g., a large language model), then there should either
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
The experiment details are provided in the paper. We will release the code once the paper is published.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
29

---

Please see the NeurIPS code and data submission guidelines (https://niis.co//l) Sttps//ooooSuumisiioooioo
for more details.
While we encourage the release code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nipp) httpe//iisscccpuuiiiii..... guides/Codeeubmis ssi sssionoliccy for more details.
The authors should provide instructions data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended. but including URLs data and code is permitted.
Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits. hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experiment details are provided in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See for example Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, statistical significance tests, least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates). If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
30

---

8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification:
See Section and Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
Code Of Ethics
Does the research conducted in the paper conform, every respect, with the NeurIPS Code of Ethics ltttps://neurips: http://ii...p.pppaa..///aaaaaaaa
Question:
Answer: [Yes]
Justification:
There are no particular ethical concerns we are aware of.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., g., if there a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
Our approach can be used protect data privacy, which may have positive societal
impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point out. For example, an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point out that
The authors should consider possible harms that could arise when the technology being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
31

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper will not release models and datasets that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cited the datasets and packages used.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwpppswippteeeeecapppppappp..pae thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
32

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
33


Reviews:
[{"review_id": "kzzYOJeWH6", "reviewer": "Reviewer_nkTx", "summary": "This paper studies the number of synthetic data required in dataset distillation to ensure that the optimal parameter learned on the synthetic dataset is the same of that learned on the original dataset.\n\nThe task considered is kernel ridge regression (KRR), where the labels contain $k$ classes. The goal is to preserve the optimal $W$ in $\\min_W \\|W\\phi(X) - Y\\|_F^2 + \\lambda \\|W\\|_F^2$.\nLet $m$ denote the number of synthetic samples in the distilled dataset.\n- For linear ridge regression (LRR), the paper finds that $m = k$ suffice to recover the parameter.\n  - The paper assumes access to $W \\in \\mathbb{R}^{k \\times d}$. Let $Y_S \\in \\mathbb{R}^{k \\times m}$ be any choice of synthetic labels such that it has rank $k$.\n  - The proof works by essentially setting $X_S = W^\\dagger Y_S$.\n  - If we want the synthetic data to be realistic, the paper suggests to set $Y_S = W\\hat{X}_S$ where $\\hat{X}_S$ are sampled from the real dataset -- this means $X_S = \\hat{X}_S$. In other words, $W$ can be preserved from a subset of $k$ samples in the real data set, as long as these samples span a rank-$k$ space.\n- For KRR with surjective feature mappings $\\phi$, $m = k$ samples also suffice to recover the parameter.\n  - Examples of surjective feature mappings include invertible NNs, fully-connected nets with invertible activation and full-rank parameters, and random Fourier features with full-rank parameters.\n  - Proof idea: first, note that recovering the linear weight on top of the feature $\\phi(X)$ is the same as LRR. The next step is then to recover $X$ from $\\phi(X)$, which is feasible when $\\phi$ is invertible.\n- For KRR with injective feature mappings (e.g. given by NNs), $k$ samples are not sufficient in general. For deep linear NNs, $k+1$ samples suffice.", "questions": "- In the proof of Thm 5.2, the second bullet point says there existing some $X_S$ corresponding to $\\phi(X_S)$ is equivalent to $X_S$ being recoverable from $\\phi(X_S)$. I don't see why the equivalency is true; for example, $\\phi$ could map all samples from the same class to a same feature embedding. What am I missing?\n- Line 578: \"for __any__ $Z_1$\" should be \"there exists some $Z_1$\"?\n- The choice of $Z$ is \"any matrix of the correct size\" at multiple places, whereas Thm C.1 additionally requires it to make $X_{\\lambda_S}$ full rank. Please fix the conditions.\n- Thm 6.1: $n$ should be $m$?\n- For completeness of the paper, please include a brief explanation of the baseline KIP.", "limitations": "There is no direct societal impact.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper provides a theoretical analyses on the minimal number of samples required for a synthetic dataset to preserve the parameter to a ridge regression problem.\n- The conditions proposed in this paper can be used to ensure 0 loss in some objectives proposed in prior work.\n- The paper empirically verify the number of samples required to, and is significantly faster than KIP (Kernel Inducing Points, a method in prior work).", "weaknesses": "- The method proposed in this paper requires knowing $W$, which is not always feasible. Moreover, the algorithm explicitly uses $W$, which means that the computational time grows with the feature dimension, which could be infinite.\n    - In contrast, KIP uses the kernel trick and hence does not incur a dependency on the feature dimension.\n- I'm concerned about the scalability of the method: although the synthetic dataset can preserve the performance on the full dataset, the accuracy is low (e.g. 42% on CIFAR10). I wonder if the method can preserve the performance of SOTA models on CIFAR10 (e.g. reaching >80% accuracy) and CIFAR100 (e.g. reaching >60% accuracy).\n- Some conditions in the theorem statements and wordings in the proofs may be problematic. Please see questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our paper and constructive comments. We believe there are some misunderstandings. Please allow us to address your concerns point-by-point.\n\n---\n**Q1. Proof idea and techniques of Theorem 4.1: The proof works by essentially setting $X_S = W^+Y_S$.**\n\nA1. $X_S = W^+Y_S$ is only a special case when $m=k$, $\\lambda_S = 0$ and $W$ is full rank. Our framework is more general for any $m \\geq k$, $\\lambda_S \\geq 0$ and $W$. The proof works by setting $W_S = Y_S (X_S^\\top X_S + \\lambda_S I)^{-1}X_S^\\top = W$, from which we can solve $(X_S^\\top X_S + \\lambda_S I)^{-1}X_S^\\top = Y_S^+W + (I - Y_S^+Y_S)Z$ for any $Z$. Then we developed some SVD techniques to solve the nonlinear equation of $X_S$. $X_S$ needs to be computed using SVD or pseudoinverse as in Theorem 4.1. \n\n---\n**Q2: Realistic distilled data in Corollary 4.1.1: the paper suggests to set $Y_S=W \\hat{X}_S$ where $\\hat{X}_S$ are sampled from the real dataset -- this means $X_S = \\hat{X}_S$.**\n\nA2. In Corollary 4.1.1, we mainly find the distilled data $X_S$ instead of setting the distilled labels $Y_S=W \\hat{X}\\_{\\lambda_S}$. We solve the $D$ that is closest to the original data $\\hat{X}\\_S$ in the sense that $||D - \\hat{X}\\_{\\lambda_S}^+||\\_F$ is minimized. Then $X_S$ can be computed from this $D$ using Theorem 4.1. Note $X_S \\neq \\hat{X}\\_S$ in general because the equation in line 504 can be inconsistent. As you can see from the first two rows of Figure 2 (page 5), there are still some differences between original and distilled images. After solve this $D$, we find $Y_S=W \\hat{X}\\_{\\lambda_S}$ can further minimize the difference of $||D - \\hat{X}\\_{\\lambda_S}^+||\\_F$ (line 510). However, $Y_S=W \\hat{X}_{\\lambda_S}$ alone without solving $D$ will not work. Because, with only label distillation, we need $d$ data points as per Theorem 4.2.\n\n---\n**Q3: The method proposed requires knowing $W$. The computational time grows with the feature dimension $d$. KIP uses the kernel trick and avoids the dependency on $d$**\n\nA3. First, $W$ can be easily computed given the original dataset so it should not be a problem. Second, we would like to note many dataset distillation methods require an original model. For example, Gradient Matching [30, 28, 12, 8 in the paper] and Trajectory Matching [1, 3, 5, 4 in the paper] match the gradients or training trajectories of models trained on the original dataset and distilled dataset. \n\nAlthough KIP avoids the dependency on $d$ by using NTK, it is prohibitively slow because the NTK computation scale with $O(m^2)$ [1], where $m$ is the number of distilled data. It is even computationally infeasible for CIFAR-100 with $m=50$ [2]. RFAD [1] proposes to speed up KIP by replacing NTK with random features. Also, there is still a gap between NTK and finite-width NNs, leading to performance degradation when transferred to NNs. \n\nMore recent methods such as RFAD [1], FRePo [3], and RCIG [4] solve a kernel regression on top of the NN’s features, which is more similar to our setting. Their approaches also depend on the feature dimension $d$. However, in general, the dimension of NN’s features is not too large and these algorithms are more computationally feasible than KIP. Our algorithm is even more computationally efficient for $d=784$ (MNIST) and $d=3072$ (CIFAR) and much more efficient than KIP as shown in Table 4. The run time is 17 seconds for MNIST and 13 seconds for CIFAR-10 on an A5000 GPU.\n\n---\n**Q4: Scalability of the method: the accuracy is low on CIFAR**\n\nA4. Please refer to Q1 in the global response.\n\n---\n**Q5: $X_S$ is recoverable from $\\phi(X_S)$**\n\nA5. Thanks for pointing it out. We meant that we need to find a $X_S$ such that $\\phi(X_S)=\\phi^*$ where $\\phi^*$ is some desired feature. In the case that $\\phi$ maps all samples from the same class to the same feature embedding, any sample from that class should suffice to be a solution. But we also have another condition that $\\phi(X_S)$ should guarantee $W_S = W$. We will make it clearer in the revised paper.\n\n---\n**Q6: Line 578: \"for any $Z_1$\" should be \"there exists some $Z_1$\"?**\n\nA6. This is a homogeneous system of linear equations and the matrix is singular (the number of equations is less than the variables), so there are infinitely many solutions. Therefore arbitrary $Z_1$ will make up a solution. See for reference: [Obtaining all solutions of a linear system](https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse#Obtaining_all_solutions_of_a_linear_system). Note here we only consider the second condition – $X_S$ is solvable from a given $\\phi^*$, and any $Z_1$ will guarantee $X_S$ is solvable.\n\n---\n**Q7: The choice of $Z$ is \"any matrix of the correct size\" at multiple places, whereas Theorem C.1 additionally requires it to make $X_{\\lambda_S}$ full rank**.\n\nA7. In Theorem C.1 it is $Z’ \\in \\mathbb{R}^{d \\times m}$, which is different with $Z \\in \\mathbb{R}^{m \\times d}$ at other places. Theorem C.1 does not conflict with other results. In Theorem 4.1, we give conditions for $X_S$ through some pseudoinverse calculation, which is hard to handle when doing more analysis because there is no concise formulation for the pseudoinverse of sum of matrices. In Theorem C.1, we provide additional direct characterizations of $X_S$ without pseudoinverse. Because Theorem C.1 is only used in the proof of Theorem 5.3, we did not include it in the main paper. Also, note that the third condition of Theorem C.1 does not require $X_{\\lambda_S}$ to be full rank as noted in line 495. This condition is used in the proof of Theorem 5.3.\n\n---\n**Q8: Thm 6.1: $n$ should be $m$?**\n\nA8. It is $n$, because we want to guarantee $W_S \\phi(X) = Y$ on the original dataset, where there are $n$ data points.\n\n---\n**Q9: brief explanation of the baseline KIP.**\n\nA9. We will add a brief explanation of KIP algorithm in the appendix.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UDkCoINJu3", "reviewer": "Reviewer_7eAw", "summary": "This work presented a theoretical framework of dataset distillation for KRR, showing that (slightly more than) one data point per class is often necessary and sufficient to recover the performance of the original model. The theory led to a provable and efficient algorithm for dataset distillation, whose effectiveness was verified through experiments.", "questions": "- While Theorem 6.2 implies that it's impossible to *exactly* recover $\\phi(X)$ from $\\phi(X_S)$ and $W$, from Figure 2, it seems that when $Z$ is chosen to be (an affine transform of) real trained data $\\hat{X}_S$, $X_S$ can still reveal *most semantic information* of $X$. This is slightly confusing and would be helpful to clarify.\n- Figure 3 shows that changing the arbitrary matrix $Z$ from (an affine transform of) real trained data $\\hat{X}_S$ to a Gaussian random matrix leads to a private dataset distillation, at least to human eyes. But from the expression $D = Y_S^\\dagger W + (I - Y_S^\\dagger Y_S) Z$, it seems that such private distilled data are semantic information + Gaussian noise. With prior knowledge of (the distribution of) $Z$, can standard denoising techniques be applied to recover the semantic information?", "limitations": "The major limitations are well-discussed in future works. Some further limitations are mentioned in Weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The introduction provides a concise and clear view of the related work on dataset distillation and the contributions of the theoretical findings. The following setup and results are well-organized.\n- The theoretical results for the linear and surjective kernel cases are strong, both in terms of improving the existing theories and in terms of providing insights for designing efficient algorithms. \n- The visualizations are straightforward and helpful for understanding, e.g., Figure 2 provides good support for the choice of $Z$ in Corollary 4.1.1.", "weaknesses": "- When comparing with the existing theories, in addition to the direct comparison of the required number of distilled data (e.g., $k$ v.s. $d$), it would be helpful to provide more intuitions on where such significant improvement comes from. Whether it is due to specific settings or assumptions or due to new techniques or insights?\n- It is slightly confusing to refer to the feature map $\\phi$ as \"surjective\", especially in the introduction without clear definitions. It would be helpful to provide more intuitions why a surjective feature map matters.\n- It seems that the analysis is relatively limited to the linear and surjective kernel cases, whereas the non-surjective kernel (or neural network) case is a direct extension of the surjective kernel results and relies on several strong assumptions like invertible activation (which excludes ReLU) and full-rank weight matrices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback, thoughtful review, and for appreciating the merits of our work!\n\n---\n**Q1: intuitions on where significant theoretical improvement comes from.**\n\nA1. Thanks for the great suggestion! The improvement mainly comes from new techniques of solving distilled datasets. In [1], they only use label distillation and $X_S$ can be arbitrary data. $d$ data points are needed for label distillation according to our Theorem 4.2. Label distillation only utilizes the $k \\times m$ parameters of $Y_S$ and more parameters of $X_S$ ($d \\times m$) are not used. Our analysis constructs $X_S$ explicitly which has more parameters and therefore requires fewer data points.\n\nIn [2, Theorem 3], they simply set the distilled data to be the right singular vectors (multiplied with the singular values) of the original dataset to keep the training loss always the same as on the original dataset. To do so, they need $d$ distilled data points. We do not require the training loss to be the same but only require the trained parameters to be the same, i.e. $W_S = Y_S (X_S^\\top X_S + \\lambda_S I)^{-1}X_S^\\top = W$. To solve the distilled dataset, we developed some SVD techniques to solve the nonlinear equation of $X_S$. Because of these new techniques, we can achieve $k$ distilled data instead of $d$ in [2].\n\n[1] Alaa Maalouf, Murad Tukan, Noel Loo, Ramin Hasani, Mathias Lechner, and Daniela Rus. On the size and approximation error of distilled sets. NeurIPS 2023.\n\n[2] Izzo, Zachary and James Zou. \"A theoretical study of dataset distillation.\" NeurIPS Workshop on Mathematics of Modern Machine Learning. 2023.\n\n---\n**Q2: Confusion about surjective feature map and intuitions why a surjective feature map matters.**\n\nA2. A function is surjective if, for every $y$ in its codomain, there exists at least one element $x$ in the function's domain such that $f(x) = y$. In this case, we can analyze kernel ridge regression in the feature space similar to a linear model and find the desired features that can guarantee $W_S = W$. Because of the property of surjective mapping, there always exists some distilled data that maps to the desired features. Non-surjective mapping is harder because there may not exist distilled data that corresponds to the desired feature. We will add more explanations in the introduction.\n\n\n---\n**Q3: The analysis is relatively limited to the linear and surjective kernel cases, whereas the non-surjective kernel (or neural network) case is a direct extension of the surjective kernel results.**\n\nA3. The non-surjective mapping case (Theorem 5.3) is not a direct extension of the surjective case. As explained in A2, non-surjective mapping is harder because there may not exist distilled data that corresponds to the desired features. To find the distilled data theoretically, we need to guarantee 1) the feature can guarantee $W_S = W$ and 2) there are some distilled data corresponding to the feature. These involve many technical challenges: 1) handling the pseudoinverse of sum of matrices in the distilled feature (Theorem C.1), 2) solving an overdetermined system of linear equations that has solutions only in limited cases (line 572), 3) solving a system of equations that has multiple free variables (line 589). The analysis for linear NN is already very involved and complicated. Please see the proof of Theorem 5.3, lines 564-613, for reference. We leave more analysis for non-surjective deep non-linear NNs as future works.\n\n\n---\n**Q4: From Figure 2, when $Z$ is chosen to be (an affine transform of) real trained data,  $X_S$ can still reveal most semantic information of $\\hat{X}_S$.**\n\nA4. We can choose $\\hat{X}_S$ to be real data that is outside of the training data $X$. In this case, even if $X_S$ resembles $\\hat{X}_S$, it will not leak the information of training data. At the same time, $X_S$ can still guarantee $W_S = W$.\n\n\n---\n**Q5: With prior knowledge of (the distribution of) $Z$, can standard denoising techniques be applied to recover the semantic information?**\n\nA5. Thanks for the insightful question! Given $D = Y_S^+ W + (I_m - Y_S^+Y_S) Z$, if we know $Y_S$, we can easily recover the semantic part $W$ by $Y_S D = W$. But even if we can recover $W$, there are infinitely many solutions of $\\phi(X)$ according to Theorem 6.2. For example, when $\\lambda = 0$, $\\phi(X) = [Y^+ + (I_n - Y^+Y) Z]^+$ (line 660), where $Z \\in \\mathbb{R}^{n \\times p}$ can be arbitrary matrix. \n\nIt is also possible to prove differential privacy for the distilled data. Please refer to Q3 in the global response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uQKSC3zuks", "reviewer": "Reviewer_ish1", "summary": "The authors study theoretical aspects of dataset distillation for kernel ridge regression. They first provide analytical results for KRR with a k-dimensional label and linear features. They then extend these results to certain types of finite-dimensional feature maps, including feature maps which can be computed by a certain class of neural networks. They also study the privacy properties of their distilled datasets. They conduct experiments on standard benchmarks to verify their theory and show the computational advantage over another DD method designed for kernel regression (KIP).", "questions": "Do the results in the paper have implications for practical uses of DD, e.g. hyperparameter tuning/NAS or continual learning?\n\nIs there a formal privacy definition (e.g., differential privacy) which the proposed DD method obeys?", "limitations": "Some limitations are discussed in the Future Work section. Potential negative societal impact is N/A.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "Dataset distillation (DD) is a relevant topic for the community, as it offers the potential to provide significant cost reductions in terms of both model training and data storage. This seems especially crucial as the size of both models and training data continues to grow. Furthermore, most work on DD has been empirical leaving the theoretical aspect under-studied. Theoretical insights may be helpful in moving towards more effective DD methods, as well as understanding the limits of what can be expected from DD.\n\nI generally found the writing clear and easy to follow.", "weaknesses": "The main claims of the paper seem to be somewhat trivial extensions of known results [1] (reference [6] in the submitted manuscript) for linear regression. There are three extensions as compared to [1]:\n1. The present paper consider a k-dimensional label instead of a 1-dimensional real-valued label. The k-dimensional case can be derived with essentially the same techniques as the 1-dimensional case, as all the same formulas for ridge-regularized linear regression still hold.\n2. The present paper studies additional possibilities for distilled datasets when more than the minimum number of points are used. Most of these results are again direct consequences of applying the formulas used in point 1. The authors also motivate the use of more than the minimum number of points in the distilled dataset as a way of enforcing privacy, but there are problems with this claim as well (see below). If privacy is not preserved, then it's not clear what is the value in studying a larger-than-necessary distilled dataset.\n3. The present paper gives positive results for kernel ridge regression with finite-dimensional feature maps, whereas [1] only gave a negative result for kernel regression. However, these results are again a trivial extension of the linear case: the results of the linear setting hold directly in the feature space, and then some additional assumptions are made (e.g., surjectivity of the feature map) which allow one to recover points in the original data space mapping to the required features. This doesn't seem to provide much additional insight.\n\nOn the other hand, the present paper only studies the problem of distilling a single model from the data. As some of the primary motivating examples for the usefulness of DD are neural architecture search/hyperparameter tuning or continual learning, some theoretical results related to these problems would be of greater interest (and these questions were also studied by [1]).\n\nThe claims that the proposed method preserves the privacy of the original dataset have also not been adequately supported. Specifically, the authors show in Theorem 6.2 that there are infinitely many possible original datasets which could have led to the learned weights W. This fact is not sufficient to claim that privacy is preserved. For instance, in an image classification setting, Theorem 6.2 does not rule out the possibility that if we restrict the original dataset to contain only realistic images, then only certain images can lead to the final model weights W. This would then constitute a privacy breach. Put another way, Theorem 6.2 is essentially claiming that model training is inherently private since the map from data to model weights is not injective. This is at odds with the consensus of the ML community, since there is a great deal of literature dedicated to making the training of ML models private (e.g. [2] has over 6000 citations).\n\n**References:**\n\n[1] Izzo, Zachary and James Zou. \"A theoretical study of dataset distillation.\" NeurIPS Workshop on Mathematics of Modern Machine Learning. 2023.\n\n[2] Abadi, Martin, et al. \"Deep learning with differential privacy.\" Proceedings of the ACM SIGSAC conference on computer and communications security. 2016.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. We believe there are some misunderstandings. Please allow us to address your concerns point-by-point.\n\n---\n**Q1: The main claims seem to be somewhat trivial extensions of [1].**\n\nA1. Our results are totally different from [1]. As discussed in the paper and Table 1, for linear ridge regression, [1, Theorem 3] requires $d$ distilled data points instead of $k$. In their case, $k=1$ and $d \\gg k$. Our results of linear ridge regression and kernel ridge regression with surjective mapping only require $k$ distilled data. In [1, Theorem 1], only for a generalized linear model, where the data and label are assumed to follow a specific exponential density function (page 3 in [1]), they can achieve single distilled data. This is a very limited case and practical data generally do not satisfy this assumption. In contrast, our analysis does not have any assumptions about the data. We will make it clearer in the revised paper.\n\nAccording to the proofs in [1, Theorem 3], they simply set the distilled data to be the right singular vectors (multiplied with the singular values) of the original dataset to keep the training loss always the same as on the original dataset. To do so, they need $d$ distilled data points. We do not require the training loss to be the same but only require the trained parameters to be the same, i.e. $W_S = W$. To solve the distilled dataset, we developed some SVD techniques to solve the nonlinear equations of $X_S$. Because of these new techniques, we can achieve $k$ distilled data instead of $d$ in [1].\n\nWe would appreciate it if you could specify which parts of our work you consider to be “trivial extensions” of [1], so we can address your concerns more effectively.\n\n---\n**Q2. The k-dimensional case can be derived with the same techniques as the 1-dimensional case.**\n\nA2. It is a good thing that our framework can be easily generalized to the $k$-dimensional case. However, we would like to emphasize that our techniques and results are totally different from [1].\n\n---\n**Q3. More than the minimum number of points are used.**\n\nA3.\n- First, we would like to emphasize that it is our paper shows that $k$ data points are necessary and sufficient for linear ridge regression and kernel ridge regression with surjective mapping. Previous results including [1] do not know the minimum number of points needed for these cases.\n- Second, it is crucial to study the behavior of dataset distillation with different numbers of data points. Our results show that when $m=k$ (minimum number of points as you said), there is only one solution of distilled data (see Figure 1 for example). But when $m > k$, there are infinitely many distilled datasets and we give analytical solutions to compute them. Only when $m > k$, we have some freedom to choose the distilled datasets that we want.\n- As said in the last point, only with more than minimum number of points, we can have some freedom to choose the distilled datasets we want from the infinitely many solutions. In this case, we can find realistic distilled data or noisy distilled data as shown in Corollary 4.1.1 and Figure 2 in our draft.\n- Previous dataset distillation algorithms all use different numbers of distilled points. Generally, with more distilled data, the performance becomes better and the distilled data becomes more realistic.\n\n---\n**Q4. Results for kernel ridge regression is a trivial extension of the linear case.**\n\nA4. Please refer to Q2 in the global response.\n\n---\n**Q5. Only studies distilling a single model from the data...**\n\nA5. We believe that single-model distillation is the basis for further theoretical analysis. If we can’t even understand the single-model distillation thoroughly, we can’t analyze the more complicated cases such as distillation for multiple models, neural architecture search, and continual learning. In this paper, we give a thorough analysis of single-model distillation and theoretically ​​show that one data per class is necessary and sufficient to recover the original model's performance in many settings. This will pave the way for the analysis of more complicated seniors. \n\nNote [1] **did not** study the distillation of multiple models, neural architecture search, or hyperparameter tuning. Compared with [1], our setting is similar to their setting of hyperparameter distillation, where the same regularization is used for the original model and the distilled dataset model, i.e. $\\lambda_S = \\lambda$. Our framework is even more flexible than [1] to allow $\\lambda_S$ and $\\lambda$ to be different. As emphasized in earlier points, our results are totally different from [1].\n\nOur results have implications for hyperparameter tuning: Theorem 4.1 generally suggests a smaller $\\lambda_S$ is better for constructing distilled data that can perfectly recover the original model’s performance.\n\n---\n**Q6. If we restrict the original dataset to contain only realistic images, then only certain images can lead to the final model weights W…**\n\nA6. The infinitely many solutions do not depend on the specific training data used. For example, when $\\lambda = 0$, given $W$, the original data can be $\\phi(X) = [Y^+W + (I_n - Y^+Y) Z]^+$ (line 660), where $Z \\in \\mathbb{R}^{n \\times p}$ can be arbitrary matrix. We can take $Z$ to be any random noise with arbitrarily large magnitude, $\\phi(X) = [Y^+W + (I_n - Y^+Y) Z]^+$ will still guarantee the trained parameter to be $W$.\n\n---\n**Q7. Do the results in the paper have implications for practical uses of DD?**\n\nA7. See A5. Theorem 4.1 generally suggests a smaller $\\lambda_S$ is better to construct distilled data that can perfectly recover the original model’s performance. Our distilled data can be used in applications such as NAS and continual learning. We leave more explorations as future works.\n\n---\n**Q8. Formal privacy definition that the proposed DD method obeys.**\n\nA8. Please refer to Q3 in the global response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gpPmPEeCcQ", "reviewer": "Reviewer_RvWD", "summary": "The paper presents provable algorithms for computing distilled sets for various problems.\n\nStarting with LRR, they prove that it is enough to have m = number of classes to compute an exact solution as on the whole data.  Then they directly show how to make this distilled point \"Realistic\" by initializing m points from the data and computing matrix D (the distilled data) to satisfy the conditions required for the distilled set while being close to these m points.\n\nThen they prove that distilling the labels only can yield the same performance with d points (which is notably immediate from [16] which basically proved the same for the more generic case of KRR via RFF).\n\nSection 5 is an extension of the previous results from LRR to KRR which is done in the same way after swapping the original feature with the mapped features. However, what was missing was how to construct the distilled set of points in the original space from the mapped distilled points -- which is easy if \\phi is bijective. But when it is not, the authors show how to at least compute an approximation for these points.  \n\nSection 6 is crucial to draw a connection as to why practical algorithms were working in the first place!\n\nMy summary:\n\n* I like the contribution of this paper, and I think it is super crucial to have theoretical results in this practical field.\n* However, I have some major and minor concerns and questions I wish to solve in order to accept that paper, specifically about the correctness of the theorems and experiments.\n* I am willing to increase my score once my questions/concerns are addressed.", "questions": "Please see all my questions in the *Weaknesses* section", "limitations": "I suggest the authors to clearly frame the distillation problem and what is the goal of it-- explaining the confusing \\lambda_s and stating the main results clearer.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 4, "strengths": "* Provides important provable guarantees and algorithms for the distillation work which was mainly practical.\n\n* It is very important to provide a better understanding of distillation and why it works in the first place -- a gap that has been missing for so long.\n\n* The method is very efficient which is very useful.", "weaknesses": "My main concerns can be split into three:\n\n*a. The framing and guarantees:*\n\n1. why is \\lamba_s not equal to \\lamda? How do you formulate the distillation with both \\lambda and \\lambda_S?\n\n2. For theorem 4.1 (line 118), can you provide an explanation why \\lambda_S \\leq 1/(4\\alpha'^2). This seems to be a very rare case not related to practice. Or do you suggest solving the problem of LRR on the small data with another lambda? if so, how can it be determined?\n\n3. Same question as before for theorem 5.1. How do you find these lambda_s?\n\n4. Section 5.2, I did not fully understand the result, if \\phi is injective, can you guarantee W_s =W with k+1 points? if yes do you prove the existence of such a set or also provide an algorithm to compute it?\n\nb. *Experimental results:*\n\n5. Table 4 in the experimental results is not clear and might have some issues. For example \"https://proceedings.neurips.cc/paper_files/paper/2022/file/5a28f46993c19f428f482cc59db40870-Paper-Conference.pdf\" and https://arxiv.org/pdf/2307.08086 conducted similar experiments and got much higher results both for KIP and their methods. Could you elaborate on why the results are different or at least why did you use different architectures?\n\n\n*c. Simple comment but important:*\n\n6. Related work is missing specifically, for LRR:  \"https://proceedings.neurips.cc/paper/2019/hash/475fbefa9ebfba9233364533aafd02a3-Abstract.html\"  showed how to construct a set of d^2 points with the same exact solution and is a subset of the input,*  then, https://ieeexplore.ieee.org/abstract/document/9677460 extended the result and showed how to compute a distilled set (not subset) with only d point and yield the same solution.  \n* For KRR https://arxiv.org/pdf/2307.08086 also showed the first basic theoretical guarantees for full network distillation.\n* https://arxiv.org/pdf/2406.04284 provided research on the information and dynamics of dis-tilled data post-distillation process\n\n________________________\nFollowing the rebuttal (response) from the authors, my concerns have been addressed, I am raising my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback, thoughtful comments, and for appreciating the novelty and value of our work! \n\n---\n**Q1. Why is $\\lambda_S$ not equal to $\\lambda$?**\n\nA1. Our goal is to find $X_S$ such that $W_S = W$. $\\lambda_S$ and $\\lambda$ are predefined hyperparameters in our setting. We allow them to be different so that the framework is more general and flexible. We can also simply set them to be the same. In our framework, $\\lambda$ does not matter much because it is only used to compute the original model’s parameter $W$, and $W$ is supposed to be given or easily computed in our framework. $\\lambda_S$ needs to satisfy some conditions in Theorem 4.1 and 5.1 to guarantee $W_S = W$. We will make it clearer in the revised paper.\n\n\n---\n**Q2. Explanation why $\\lambda_S \\leq \\frac{1}{4 \\sigma_1'^2}$. This seems to be a very rare case not related to practice. How to determine the $\\lambda_S$ in Theorem 4.1 and 5.1.**\n\nA2. $\\lambda_S \\leq \\frac{1}{4 \\sigma_1'^2}$ is required because $X_S$ needs to be solvable from a given $D$. From Eq (2), line 420, $(X_S^\\top X_S + I_m)^{-1} X_S^\\top = D$. Given a $D$, in order to have a solution for $X_S$, the equation $\\sigma_i’ \\sigma_i^2 - \\sigma_i + \\lambda_S \\sigma_i’ = 0$ on line 427 must have a solution for $\\sigma_i$. From this, we have the requirement between $\\lambda_S$ and $\\sigma_1’$. When $\\lambda_S=0$, it is simpler and there is no such requirement.\n\nThis requirement is easy to satisfy. For example, given a $D$ and its largest singular value $\\sigma_1’$, we can simply set $\\lambda_S = \\frac{1}{4 \\sigma_1'^2}$ or any number less than it. If we want to fix a predefined $\\lambda_S$, e.g. $\\lambda_S=\\lambda$, we need to sample different $D$ (by sampling different $Z$) so that its largest singular value satisfies the condition $\\lambda_S \\leq \\frac{1}{4 \\sigma_1'^2}$. \n\nPractical algorithms, e.g. KIP, FRePo, and RFAD, usually use a very small regularization $\\lambda_S$, which may already satisfy this requirement. For example, KIP uses $\\lambda_S = 10^{-6} \\cdot Tr(K(X_S, X_S)) / m$. Theorem 4.1 generally suggests a smaller $\\lambda_S$ is better to construct distilled data that can perfectly recover the original model’s performance. \n\n\n---\n**Q3. Section 5.2: if $\\phi$ is injective, can you guarantee W_S =W with k+1 points? if yes do you prove the existence of such a set or also provide an algorithm to compute it?**\n\nA3. For deep linear NNs (Theorem 5.3), we can guarantee $W_S =W$ with $k+1$ points if the conditions are satisfied: $H$ is full-rank and its right singular vectors’ last $p \\times p$ submatrix is full rank. If these conditions are satisfied, we prove the existence of the distilled dataset and provide the algorithm to compute the distilled data in the proof (lines 607-612). \n\nFor general injective mapping, we can’t guarantee $W_S =W$ with $k+1$ points.\n\n\n---\n**Q4. Why the experiment results are different from previous papers or at least why did you use different architectures?**\n\nA4. Please refer to Q1 in the global response.\n\n\n---\n**Q5. Missing related works**\n\nA5. Thanks for the relevant papers! We will make sure to properly cite and discuss these papers in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for taking the time and effort to review our paper! We are delighted that the reviewers found: 
- The paper provides a theoretical analysis on the minimal number of samples required for a synthetic dataset to preserve the parameter to a ridge regression problem (Reviewer nkTx);
- The theoretical results for the linear and surjective kernel cases are strong, both in terms of improving the existing theories and in terms of providing insights for designing efficient algorithms (Reviewer 7eAw);
- The visualizations are straightforward and helpful for understanding, e.g., Figure 2 provides good support for the choice of $Z$ in Corollary 4.1.1 (Reviewer 7eAw);
- Theoretical insights may be helpful in moving towards more effective DD methods, as well as understanding the limits of what can be expected from DD (Reviewer ish1);
- I like the contribution of this paper, and I think it is super crucial to have theoretical results in this practical field (Reviewer RvWD). 

Below, we respond to common questions shared by reviewers in this global response. Please don’t hesitate to let us know if you have any additional feedback or questions regarding our response. We would be happy to address any remaining concerns with you in the discussion period if any. If our responses have addressed your concerns and questions, we would appreciate it if you could kindly let us know and consider raising your review score.

---
**Q1: Scalability of the method: the accuracy is low on CIFAR. (Reviewer nkTx and RvWD)**

A1. As Algorithm 1 we proposed is mainly for KRR with surjective mappings, we verified it and compared it with baselines under this setting. In experiment (II), we use a randomly initialized bijective NN as $\phi$. It matches previous algorithms that start with a randomly initialized NN. If we use a pre-trained NN as $\phi$, the accuracy can be improved and may match the SOTA. 

We conduct additional experiments to use a pre-trained 5-layer FCNN as $\phi$. Under this setting, we can get an accuracy of 57.91%$\pm$0.23 on CIFAR-10 and 31.78%$\pm$0.23 on CIFAR-100 for IPC=1, which is comparable to the SOTA dataset distillation algorithms such as KIP [1] (49.9$\pm$0.2 for CIFAR-10 and 15.7$\pm$0.2 for CIFAR-100) and MTT [2] (46.3$\pm$0.8 for CIFAR-10 and 24.3$\pm$0.3 for CIFAR-100) when IPC=1.

[1] Nguyen, et al. Dataset Distillation with Infinitely Wide Convolutional Networks. NeurIPS 2021.

[2] Cazenavette , et al. Dataset distillation by matching training trajectories. CVPR 2022.


---
**Q2. Results for kernel ridge regression is a direct extension of the linear case. (Reviewer 7eAw and ish1)**

A2. The non-surjective mapping case (Theorem 5.3) is not a direct extension of the linear case. Non-surjective mapping is much harder because there may not exist distilled data that corresponds to the desired feature. To find the distilled data theoretically, we need to guarantee 1) the feature can guarantee $W_S = W$ and 2) there are some distilled data corresponding to the feature. These involve many technical challenges: 1) handling the pseudoinverse of sum of matrices in the distilled feature (Theorem C.1), 2) solving an overdetermined system of linear equations that has solutions only in limited cases (line 572), 3) solving a system of equations that has multiple free variables (line 589). The analysis is very involved and complicated and the results are not a direct extension of the linear case. Please see the proof of Theorem 5.3, lines 564-613, for reference. 

The surjective mapping case can not be fully covered by the linear case. In particular, we give examples of models that satisfy the condition and provide useful cases, including Invertible NN, FCNN, CNN, and Random Fourier Features. These models are ubiquitously used in practices. More importantly, for Random Fourier Features, our results theoretically improve previous $p$ distilled data [3] to $k$, where $p \in \Omega(\sqrt{n} \log n)$ in general can be very large.

[3] Alaa Maalouf, Murad Tukan, Noel Loo, Ramin Hasani, Mathias Lechner, and Daniela Rus. On the size and approximation error of distilled sets. NeurIPS 2023.


---
**Q3. Is there a formal privacy definition (e.g., differential privacy) which the proposed DD method obeys? (Reviewer ish1)**

A3. It is possible to prove the distilled dataset is differential private for the original dataset. For example, for the linear case (Theorem 4.1), $D = Y_S^+W + (I_m - Y_S^+ Y_S)Z$. We can take the elements of $Z$ to be i.i.d. random variables drawn from a zero-mean Gaussian distribution, then the elements of $(I_m - Y_S^+ Y_S)Z$ will still be zero-mean Gaussian random variables. Supposed original datasets $X$ and $X’$ only differ in one data point and their resulting parameter are $W$ and $W’$. As long as $||W-W’||_F$ is bounded, by the Gaussian mechanism [4, Theorem 3.22], $Z$ with suitable variance will guarantee $D$ to be differential private for the original dataset. The computation from $D$ to $X_S$ is deterministic therefore will keep the differential privacy. 

[4] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 2014.

Meta-review: This paper received high-quality reviews from four knowledgable reviewers who engaged actively during rebuttal, with diametrically opposing opinions. Reviewers ish1 and nkTx had the two most critical reviews. ish1 believes the main claims are somewhat trivial extensions of known results and questions the novelty and technical contributions. They remained unconvinced of the merits of the paper after a lengthy discussion with the authors. Reviewer nkTx, on the other hand, had concerns about the scalability of the method and the dependency on the feature dimension. The reviewer also found some conditions and wordings in the proofs problematic. However, after the discussion with the authors, this reviewer seemed satisfied with many of the clarifications, and had mostly notation and presentation outstanding comments, even though they did not update their score to reflect this. 

On the other side of the discussion, we have reviewers 7eAw and RvWD, who were in favor of accepting the paper. Reviewer 7eAw expressed appreciation for the **theoretical framework** and contributions, especially the those for the linear and surjective kernel cases. Reviewer RvWD also highlighted the theoretical contributions of the paper, but initially expressed concerns about the correctness of the theorem statements and the experiments. However, the reviewer conceded that their major concerns were resolved by the authors’ response, and updated their score to reflect this. Both of these reviewers had a long list of recommendations for the authors in terms of presentation and framing, which they requested the authors to incorporate in a revised version if the paper were to be accepted. 

After reading the paper myself twice, and going through the forum multiple times, I find myself torn and could easily find myself advocating for rejection or acceptance, depending on what issue is being highlighted. I take ish1’s points about novelty and extent of contribution, but whether these extensions are considered “trivial” or “substantial” is subjective. In cases of novelty ambiguity, I believe we should fall back to correctness and clarity, and this paper seems to satisfy both. Despite the various questions and concerns about notation raised by the reviewers, it does not seem to me that the mathematical errors/misunderstandings that came up during the discussion is unusually widespread or critical. Most of these were clarified during the rebuttal phase and none of them seem to have undone or substantially weakened the theoretical results.  In terms of contribution it should be pointed out that [6] is a workshop paper, and therefore brief. Even if the only contribution of this paper where extensions over that paper, this one provides a much more detailed analysis and discussion of the results, which make it a valuable addition to [6] for the community. 

All in all, I think this is an interesting but perhaps not ground-breaking paper that provides interesting theoretical guarantees for dataset distillation in certain simplified scenarios, some of which are extensions of known results, while some are not, but which could nevertheless be found interesting and relevant by the NeurIPS community.
Decision: Accept (poster)