Provable and Efficient Dataset Distillation for Kernel Ridge Regression

We thank the reviewer for the positive feedback, thoughtful comments, and for appreciating the novelty and value of our work!

Q1. Why is $\lambda_S$ not equal to $\lambda$?

A1. 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.

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.

A2. $\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.

This 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}$.

Practical 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.

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?

A3. 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).

For general injective mapping, we can’t guarantee $W_S =W$ with $k+1$ points.

Q4. Why the experiment results are different from previous papers or at least why did you use different architectures?

A4. Please refer to Q1 in the global response.

Q5. Missing related works

A5. Thanks for the relevant papers! We will make sure to properly cite and discuss these papers in the revised version.

I want to thank the authors for their response. They have addressed my comments.

Most importantly. I want to ask them to make sure to incorporate the clarity and detailed responses for Q1, Q2, and Q3 to be clearly stated in the paper - it makes things much easier to understand.

For Q4, I would say that the main motive of this work is the provable guarantees which are rare in the field. While I am aware of methods that get better practical results -- I still think that the paper is robust due to the formal guarantees. Hence, I recommend the authors explain that in the experimental results section - as the goal is to show how these guarantees transfer to practice.

For Q5. It is very important to add all of these missing citations to the related work to clearly explain the difference between the paper and those works.

Assuming all of these notes are addressed (as should be) I am raising my score to 7, and I vote for accepting the work.

We thank the reviewer for the detailed comments. We believe there are some misunderstandings. Please allow us to address your concerns point-by-point.

Q1: The main claims seem to be somewhat trivial extensions of [1].

A1. 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.

According 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].

We 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.

Q2. The k-dimensional case can be derived with the same techniques as the 1-dimensional case.

A2. 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].

Q3. More than the minimum number of points are used.

A3.

• 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.
• 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.
• 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.
• 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.

Q4. Results for kernel ridge regression is a trivial extension of the linear case.

A4. Please refer to Q2 in the global response.

Q5. Only studies distilling a single model from the data...

A5. 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.

Note [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].

Our 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.

Q6. If we restrict the original dataset to contain only realistic images, then only certain images can lead to the final model weights W…

A6. 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$.

Q7. Do the results in the paper have implications for practical uses of DD?

A7. 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.

Q8. Formal privacy definition that the proposed DD method obeys.

A8. Please refer to Q3 in the global response.

Thank the reviewer for further questions. Please see our response below.

A1. We agree with the reviewer that the assumed likelihood can be used to train the model by maximizing the log-likelihood, with the loss function being the negative log-likelihood. However, it does not include linear regression with square loss (least squares). Only when the distribution is normal, does the linear regression of the generalized linear model match the least-squares solution. Therefore there is no overlap between our results and [1] since the models and loss functions are different, i.e. ridge regression vs maximum likelihood estimation. [1] proves the single distilled data for the generalized linear model, where maximum likelihood estimation is used. We prove the single distilled data (one data per class) for least squares and ridge regression. We will clearly discuss the differences in the revised paper. We thank the reviewer for drawing our attention to this point.

That being said, for least squares and ridge regression, we indeed improve [1, Theorem 3] from $d$ data points to $k$ data points. Least squares and ridge regression are often used in practice and dataset distillation algorithms because their analytical solutions can be easily computed. We also draw a connection between our results and the practical kernel-based dataset distillation algorithms in Theorem 6.1.

In addition, we would like to emphasize our contributions of kernel ridge regression (both surjective and non-surjective cases), which improves the negative results in [1]. Our results also improve [2] from $p$ to $k$ for the random Fourier features/shift-invariant kernels in the surjective case.

[1] Izzo, Zachary and James Zou. "A theoretical study of dataset distillation." NeurIPS Workshop on Mathematics of Modern Machine Learning. 2023.

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

A2. We agree with the reviewer that the distilled data in [1, Theorem 3] works for all $\lambda \geq 0$ and $\lambda=\lambda_S$. But they need $d$ data points compared with our $k$ points. As demonstrated in Table 2 of our draft, in practical scenarios, $d \gg k$. In practice, we typically select the regularization parameter that yields the best performance.

Our analysis can recover the results of [1, Theorem 3]. When $n \geq d$ and $m \geq d$, $W_S = W$ is $Y_S X_S^\top (X_S X_S^\top + \lambda I_d)^{-1} = Y X^\top (X X^\top + \lambda I_d)^{-1}$. Taking $X_S$ and $Y_S$ to be similar quantities as [1, Theorem 3], we can show $X_S X_S^\top = X X^\top$ and $Y_S X_S^\top = Y X^\top$ and this hold for all $\lambda \geq 0$. When $m < d$, it is generally impossible to have this result (unless $X$ is low rank) since $X_S X_S^\top$ is at most rank $m$ and $X X^\top$ is rank $d$. Nevertheless, if we do not require the distilled data to be valid for all $\lambda \geq 0$, our approach can achieve the distillation with just $k$ data points. We will discuss this relationship and the distinctions more explicitly in the revised version of the paper.

Furthermore, a more interesting scenario would be the same distilled data for different models $\phi_1$ and $\phi_2$, which is possible to analyze based on our framework. We leave more explorations as future works.

A3. Bounding $||W - W’||_F$: Suppose we have two dataset $X = [x_1, \dots, x_n], X’ = [x_1’, \dots, x_n] \in \mathbb{R}^{d \times n}$ that differ only in the first point. Suppose $\lambda = 0$, then $W = Y X^+$. Therefore $W - W’ = Y (X^+ - X’^+)$. The Frobenius norm can be bounded as follows: $||W - W’||_F \leq ||Y||_F ||(X^+ - X’^+)||_F \leq ||Y||_F ||X^+||_2 ||X’^+||_2 ||x_1 - x_1’||_2$, where the last inequality is because $||(X^+ - X’^+)||_F \leq ||X^+||_2 ||X’^+||_2 ||X - X’||_F$ [3, Theorems 2.2]. Assume the the data points $x_i$ are bounded $||x_i||_2 \leq B$ and the smallest singular value of datasets is bounded from below $\sigma\_{min}(X) \geq \sigma > 0$. Then $||W - W’||_F \leq ||Y||_F \frac{2B}{\sigma^2}$.

To justify the boundness of the smallest singular value, suppose the data points $x_i$ are independent sub-gaussian (e.g. bounded) and isotropic, then by [4, Theorem 5.39], with probability at least $1 - 2e^{-ct^2}$, $\sigma\_{min}(X) \geq \sqrt{n} - C\sqrt{d} - t$, where $c, C$ only depends on the sub-gaussian norm of $x_i$.

Applying the Gaussian mechanism: Suppose $Y_S$ are deterministic and independent of $X$, e.g. we can take $Y_S$ to be one-hot labels, then $Y_S^+ W$ is a deterministic function of $X$. As we have shown above, the sensitivity of $Y_S^+ W$ is bounded. Since each element of $(I_m - Y_S^+ Y_S)Z$ is a zero-mean Gaussian and only its variance depends on $Y_S$, we can apply the Gaussian mechanism to $Y_S^+ W + (I_m - Y_S^+ Y_S)Z$.

We will include the rigorous proof in the revised paper.

[3] L. Meng and B. Zheng. The optimal perturbation bounds of the Moore–Penrose inverse under the Frobenius norm. Linear Algebra Appl., 432:956–963, 2010.

[4] Vershynin, Roman. "Introduction to the non-asymptotic analysis of random matrices." arXiv preprint arXiv:1011.3027 (2010).

We hope our responses have addressed all your concerns. Please let us know if you have any further questions! If your concerns are addressed, we would appreciate it if you could kindly consider raising your score.

We thank the reviewer for the positive feedback, thoughtful review, and for appreciating the merits of our work!

Q1: intuitions on where significant theoretical improvement comes from.

A1. 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.

In [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].

[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.

[2] Izzo, Zachary and James Zou. "A theoretical study of dataset distillation." NeurIPS Workshop on Mathematics of Modern Machine Learning. 2023.

Q2: Confusion about surjective feature map and intuitions why a surjective feature map matters.

A2. 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.

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.

A3. 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.

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$.

A4. 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$.

Q5: With prior knowledge of (the distribution of) $Z$, can standard denoising techniques be applied to recover the semantic information?

A5. 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.

It is also possible to prove differential privacy for the distilled data. Please refer to Q3 in the global response.

Thanks for your response and for recommending acceptance! We really appreciate it! We will make sure to follow the suggestions and clarify the questions in the revised version.

References

[1] Noel Loo, et al. Efficient dataset distillation using random feature approximation. NeurIPS 2022.

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

[3] Yongchao Zhou, et al. Dataset distillation using neural feature regression. NeurIPS 2022.

[4] Noel Loo, et al. Dataset distillation with convexified implicit gradients. NeurIPS 2023.

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.

Q1. Proof idea and techniques of Theorem 4.1: The proof works by essentially setting $X_S = W^+Y_S$.

A1. $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.

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$.

A2. 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.

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$

A3. 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.

Although 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.

More 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.

Q4: Scalability of the method: the accuracy is low on CIFAR

A4. Please refer to Q1 in the global response.

Q5: $X_S$ is recoverable from $\phi(X_S)$

A5. 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.

Q6: Line 578: "for any $Z_1$" should be "there exists some $Z_1$"?

A6. 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. 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.

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.

A7. 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.

Q8: Thm 6.1: $n$ should be $m$?

A8. It is $n$, because we want to guarantee $W_S \phi(X) = Y$ on the original dataset, where there are $n$ data points.

Q9: brief explanation of the baseline KIP.

A9. We will add a brief explanation of KIP algorithm in the appendix.

Dear Reviewer nkTx,

As the discussion period is close to the end and we have not yet heard back from you, we wanted to reach out to see if our rebuttal response has addressed your concerns. We are more than happy to discuss any further concerns and issues you may have. If your concerns have been addressed, we would appreciate it if you could kindly re-evaluate our work. Thank you for your time.

We thank the reviewer for the reply and further questions. Please see our response below.

Q1. There's no reason why we need or want to take $Z \neq 0$.

A1. There are reasons that we want to take $Z \neq 0$. When $Z = 0$, given fixed $W$ and $Y_S$, $D = Y_S^+ W$ is deterministic and so is $X_S$. There is no freedom to choose the distilled data we want. When $Z \neq 0$, as discussed in lines 136-139, we can choose $X_S$ by varying $Z$. For example, in Corollary 4.1.1, we choose $Z = \hat{X}_{\lambda_S}^+ - Y_S^+ W$ such that $X_S$ is close to real data. We can also take $Z$ to be random noise such that the distilled data is noisy as shown in Fig 2 in the draft.

Q2. Comment on the scaling of the two methods.

A2. Thanks for the suggestion! We will add a discussion in the revised version.

Q3. Thm C.1: when $k \leq m \leq d$.

A3. In Thm C.1, the first two cases share the same conditions and they are complementary ($m \leq d$ and $m \geq d$). The third case $m \geq k$ has its own conditions. To make it clearer, we will write the third case in a separate theorem.

The first case does not require $m \geq k$. The results still hold even when $m < k$. We will delete the sentence ``from Eq (2), $W_S = Y_S^+ X_{\lambda_S}$’’, which is misleading, as $W_S = Y_S^+ X_{\lambda_S}$ always hold.

Q4. Cor 4.1.1.: $Y_S = W \hat{X}\_{\lambda_S}$ then $D = Y_S^+ W = \hat{X}\_{\lambda_S}^+$. How/where is $\hat{X}_{\lambda_S}$ defined?

A4. Note when $d > k$, $Y_S^+ = (W \hat{X}\_{\lambda_S})^+ \neq \hat{X}\_{\lambda_S}^+ W$ in general. Therefore $Y_S^+ W = (W \hat{X}\_{\lambda_S})^+ W \neq \hat{X}\_{\lambda_S}^+$ in general.

$\hat{X}\_{\lambda_S}^+ = (\hat{X}_S^\top \hat{X}_S + \lambda_S I_m)^{-1} \hat{X}_S^\top$ is defined in the same way as $X\_{\lambda_S}$ (line 103). We will include a definition to make it clearer.

Q5. In Sec 3.2: are $\lambda$ and $\lambda_S$ the same?

A5. Thanks for pointing it out. It is a typo. It should be $\lambda$ between lines 93-94. $\lambda$ is a predefined hyperparameter in our setting. $\lambda_S$ needs to satisfy some conditions in Theorem 4.1 and 5.1 to guarantee $W_S = W$. Please also refer to our response to Q1 and Q2 of Reviewer RvWD.

Q6. Line 578: it cannot be "any" $Z$, since $\phi$ is "given".

A6. We consider the two conditions separately to find the form of $\phi(X_S)$ that satisfies each condition and then combine the conditions to solve $X_S$. If we only consider the second condition, we are trying to find the form of $\phi(X_S)$ such that $X_S$ is solvable from $\phi(X_S)$. Then $X_S$ is solvable from $\phi(X_S) = \prod_{l=1}^L W^{(l)} (W^{(1)})^+ Z_1$ in Eq (7) for any $Z_1$. If we consider the first condition together with the second condition, then the first condition requires $\phi(X_S)$ to be given in the form of $\phi(X_S) = (Y_S^+ W + (I_m - Y_S^+Y_S) Z)$ in Eq (6). Then it is indeed for some $Z_1$.

To make it more rigorous, we will revise it to be ``there exists some $Z_1$’’.

We hope our responses have addressed all your concerns. Please let us know if you have any further questions!

I apologize for my late response, and thank you for the clarifications!

Q1: I understand that $X_S = W^\dagger Y_S$ is only a special case (by taking $Z=0$); what I meant was that the proof works essentially the same as how one would proceed for this special case (i.e. SVD). Moreover, based on the theorem statement, there's no reason why we need or want to take $Z \neq 0$.

Q3, about the quadratic scaling in the number of samples $m$ (as in KIP) vs in the feature dimension $p$: thanks for the clarification. Please add a comment on the scaling, so that it's transparent how the two methods compare.

Q4: thanks for the new numbers, I think they are convincing.

I find the math writing in the paper confusing, especially with quantifiers.

• Thm C.1: when $k \leq m \leq d$,
• Cor 4.1.1.: the statement feels tautological: it says that to minimize the distance between $D$ and $\hat{X}_{\lambda_S}^\dagger$, take $Y_S = W\hat{X}_{\lambda_S}$, and set $D = Y_S^\dagger W = \hat{X}_{\lambda_S}^\dagger$ -- apologies for the poor formatting; I think the renderer got confused with LaTex and markdown.
  • Moreover, how/where is $\hat{X}_{\lambda_S}$ defined?
• In Sec 3.2: are $\lambda$ and $\lambda_S$ the same? I'm confused especially in the equation below line 93.
• Line 578: it cannot be "any" $Z_1$, since $\phi$ is "given".