Efficient Dataset Distillation using Random Feature Approximation
Authors: Noel Loo
Ramin Hasani
Alexander Amini
Daniela Rus
Venue: NeurIPS 2022 Accept (2022)
Keywords: dataset distillation
neural tangent kernel
privacy
interpretability

Abstract: Dataset distillation compresses large datasets into smaller synthetic coresets which retain performance with the aim of reducing the storage and computational burden of processing the entire dataset. Today's best performing algorithm, \textit{Kernel Inducing Points} (KIP), which makes use of the correspondence between infinite-width neural networks and kernel-ridge regression, is prohibitively slow due to the exact computation of the neural tangent kernel matrix, scaling $O(|S|^2)$, with $|S|$ being the coreset size. To improve this, we propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel which reduces the kernel matrix computation to $O(|S|)$.  Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets, both in kernel regression and finite-width network training. We demonstrate the effectiveness of our approach on tasks involving model interpretability and privacy preservation.

Efficient Dataset Distillation using Random Feature Approximation
Noel Loo, Ramin Hasani, Alexander Amini, Daniela Rus Computer Science and Artificial Intelligence Lab (CSAIL) Massachusetts Institute Technology (MIT)
(loo, rhasani, amini, rus} @mit.edu
Abstract
Dataset distillation compresses large datasets into smaller synthetic coresets which retain performance with the aim of reducing the storage and computational burden of processing the entire dataset. Today's 's best-performing algorithm, Kernel Induc- ing Points (KIP), which makes use the correspondence between infinite-width neural networks and kernel-ridge regression, is prohibitively slow due the exact computation the neural tangent kernel matrix, scaling (([5)), with [S] being the coreset size. To improve this, we propose novel algorithm that uses random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel, which reduces the kernel matrix computation O(SS)). Our algorithm provides at least a 100-fold speedup over KIP and can run on single GPU. Our method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms accuracy over a range of large-scale datasets, both in kernel regression and width network training. We demon- strate the effectiveness of our approach on tasks involving model interpretability and privacy preservation."
1 Introduction
Time per iteration 460s
Accuracy
Example Distilled Dataset from CelebA
191.6 .6 times faster
+6.1% gain
Coreset algorithms aim to summarize large datasets into significantly smaller datasets that still accurately represent the full dataset on downstream tasks [Jubran et al., 2019]. There are myriad applications of these smaller datasets including speeding up model training [Mirza- soleiman et al., 2020], reducing catastrophic for- getting [Aljundi al., 2019, Rebuffi et al., 2017, Borsos et al., 2020], and enhancing interpretabil- ity [Kim et al., 2016, Bien and Tibshirani, 201 1].
73.1%
67%
2.4s
KIP
RFAD (ours)
KIP
RFAD (ours)
Class Female
Train un this images, get 92% dlssification acc
Figure 1: RFAD provides over 100-fold speedup over the state-of-the thehhhrt art algorithm Kernel-Inducin Points (KIP) [Nguyen et al., 2021a), while exceed- ing performance on CIFAR-10. (right) Example distilled synthetic sets one image per class
While most coreset selection techniques aim to select representative data points from the dataset, recent work has looked at generating synthetic data points instead, a process known as dataset distillation [Wang et al., 2018, Bohdal et al., 2020, Sucholutsky and Schonlau, 2019, Zhao al., 2021, Zhao and Bilen, 2021b, Nguyen al., 2021b]. These synthetic datasets have the benefit of using continuous gradient- gradient-based optimization techniques rather than combinatorial methods and are limited the of images and labels given by the dataset, providing added flexibility and performance.
Code is available https://github http:/thhww..moooyly////////
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A large variety of applications benefit from obtaining an efficient dataset distillation algorithm. For instance, Kernel methods [Vinyals al., 2016, Kaya and Bilge, 2019, Snell et al., 2017, Ghorbani et al., 2020, Refinetti et al., 2021] usually demand large support set in order to generate good prediction performance at inference. This can be facilitated by an efficient dataset distillation pipeline. Moreover, distilling a synthetic version of sensitive data helps preserve privacy; a support set can be provided to an end-user for the downstream applications without disclosure of data. Lastly, for resource-hungry applications such as continual learning [Borsos et al., 2020], neural architecture search [Shleifer and Prokop, 2019] and automated machine learning [Hutter et al., 2019], generation of support-set on which we can fit models efficiently is very helpful.
Recently, a dataset distillation method called Kemel- Points (KIP) [Nguyen et al.. 202 showed great performance in neural network classification tasks. KIP uses Neural Tangent Kernel (NTK) ridge-regression to exactly compute the output states of an infinite-width neural network trained on the support set. Although the method established the state-of-the-ar for dataset distillation in terms of accuracy, the computational complexity of KIP is very high due to the exact calculation of the NTK. The algorithm, therefore, has limited applicability.
In this paper, we build on the prior work on KIP and develop a new algorithm for dataset distillation called READ, which has similar accuracy and significantly better performance than KIP. The key insight is to introduce new kernel inducing point method that improves complexity from ( (where [S] is the support-set size) to O(())). To this end, we make three major contributions:
I. We develop RFAD, a fast, accurate, and scalable algorithm for dataset distillation in neural network classification tasks.
II. We improve the time performance of KIP [Nguyen et al., 2021a,b] by over two orders of magnitude while retaining or improving its accuracy. This speedup comes from leveraging a random-feature approximation of the Neural Network Gaussian Process (NNGP) kernel by instantiating random neural networks.
III. We show the effectiveness of RFAD in efficient dataset distillation tasks, enhancing model interpretabillty and privacy preservation.
2 Background and Related Work
Coresets and Dataset Distillation. Coresets are subset of data that ensure models trained on them show competitive performance compared to models trained directly on data. Standard coreset selection algorithms use importance sampling to find coresets [Har-Peled and Mazumdar, 2004, Lucic et al., 2017, Cohen et al., 2017]. Besides random selection methods, inspired by catastrophic forgetting [TToneva et al., 2019] and mean-matching (adding samples to the coreset to match the mean of the original dataset) [Chen et al., 2010, Rebuffi et al., 2017, Castro et al., 201 8, Belouadah and Popescu, 2020, Scholkopf et al., 1999], new algorithms have been introduced. An overview of how coresets work on point approximation is provided in Phillips [2016]
More recently, aligned with coresct selection methods, new algorithms have been developed to distill a synthetic dataset from a given dataset, such that fitting to this synthetic set provides performance on par with training on the original dataset [Wang et al., 2018]. To this end, these dataset condensation (or distillation) algorithms use gradient matching [Zhao et al., 2021, Maclaurin et al., 2015, Lorraine et al., 2020], utilize differentiable siamese augmentation [Zhao and Bilen, 2021b), and matching distributions [Zhao and Bilen, 2021a]. Dataset distillation has also been applied to the labels rather than images [Bohdal et al., 2020]. Recently, novel algorithm called Kernel Inducing Points (KIP) INguyen et al., 202 has been introduced that performs very well on distilling synthetic sets by using neural tangent kernel ridge-regression (KRR). KIP, similar to other algorithms, is computationally expensive. Here, we propose a new method to significantly improve its complexity.
Infinite Width Neural Networks. Single-layer infinite-wide randomly initialized neural networks correspond to Gaussian Processes [Neal, 1996], allowing for closed-form exact training of Bayesian neural networks for regression. Recently, this has been extended to deep fully-connected networks [Lee et al., 2018, G. Matthews et al., 2018], convolutional networks [Novak et al., 2019, Garriga- Alonso et al., 2019], intention-based networks [Hron et al., 2020], and even to arbitrary neural architectures (Yang, 2019], with the corresponding GP kernel being the NNGP Kernel. Likewise, for infinite-width neural networks trained with gradient descent, the training process simplifies dramati-

---

cally, corresponding to kernel ridge regression when trained with MSE loss with the corresponding kernel being the Neural Tangent Kernel (NTK) [Jacot et al., 2018, Arora al., 2019, Loo al.. 2022]. These two kernels are closely related, as the NNGP kernel forms the leading term of the NTK kernel, representing the effect of the final layer weights. Calculation of kernel entries typically scales with OHHWD) for conv nets, with H, W being the image height and width, D the network depth, and O(H222) for architectures with global average pooling [Arora et al., 2019]. This, combined with the necessity of computing and inverting the N x N kernel matrix for kernel ridge regression, typically make these methods intractable for large datasets [Snelson and Ghahramani, 2006, Titsias, 2009].
Random Feature methods. Every kernel corresponds to dot product for some feature map: k(x, "(x)" 6(z'). Random feature methods aim to approximate the feature vector with a fiite-dimensional random feature vector, the most notable example being Random Fourier Features [Rahimi and Recht, 2007]. Typically, this limits the rank of the kernel matrix, enabling faster matrix inversion and allowing for scaling kernel methods to large datasets. Recently, these random feature methods have been used to speed up NTKs and NNGPs [Zandich et al., 2021, Novak al., 2022, 2019] at inference or for neural architecture search [Peng et al., 2020]. In this work, we focus on the NNGP approximation described in Novak et al. [2019], as it only requires network forward passes and is model agnostic, allowing for flexible usage across different architectures without more complex machinery needed to calculate the approximation, unlike those found in Zandich et al. [2021], Novak et al. [2022].
3 Algorithm Setup and Design
In this section, we first provide high-level background on the KIP algorithh We then sequentially outline our modifications leading to the RFAD algorithm.
3.1 KIP Revisit
The Kernel-Inducing Point algorithm [Nguyen et al., 2021a,b], or KIP, is a dataset distillation technique that uses the NTK kernel ridge-regression correspondence to compute exactly the outputs of an infinite-width neural network trained on the support set, bypassing the need to ever compute gradients or proppproeegate on any finite network. Let XT, yr correspond to the images and one-hot vector labels on the training dataset and let Xs, ys be the corresponding images and labels for the support set, which we aim to optimize. We have the outputs of trained neural network as f(XT) = KTs(Ks, + A - ys. with being the kernel matrices calculated using the NTK kernel, with T x S or S x S entries, for Krs and Kss. respectively. À is small regularization parameter. KIP then optimizes LMSE = ||yr- - )( directly. The key bottleneck is the computation of these kernel matrices, requiring O - HWD D) time and memory, necessitating the use of hundreds of GPUs working in parallel. Additionally, the use of the MSE loss is suboptimal.
3.2 Replacing the NTK Kernel with an NNGP Kernel
We first replace the NTK used in the kernel regression of KIP with an NNGP kernel. While this change alone would yield speed up, as the NNGP kernel is less computationally intensive to compute [Novak et al., 2020], we primarily do this because the NNGP kernel admits a simple random feature approximation, with advantages described later in this section. We first justify the appropriateness of this modification.
Firstly, we denote that in the computation of NTK (9) and NNGP (K) forms the leading term, as shown in Table Appendix of [Novak et al., 2020] which outlines the NTK and NNGP kernel computation rules for various layers of neural network. For fully connected (FC) layers, which is the typical final layer in neural network architectures, the remaining terms are suppressed by a matrix of expected derivatives with respect to activations, K, as observed by the recursion yielded from the computation of the NTK for an FC network [Novak et al., 2020]: Ol = K + Kt o 0 For ReLU activations, the entries in this derivative matrix are upper bounded by 1, so the remaining terms must have a decaying contribution. We verify that our algorithms still provide good performance under the NTK and for finite networks trained with gradient descent, justifying this approximation.
3

---

Algorithm Dataset distillation with NNGP random features
Require:
Training set and labels Xr, YT. Randomly initialized coreset and labels Xs, Us. Random network count N, Random network output dimension M, Batch size [B], Random network initialization distribution, p(f), Regularization coefficient, X, Learning rate 17.
while loss not converged do
Sample batch from the training set X Yn p(XT.
Sample N random networks each with output dimension M from p(0): .I,...N ~ p(0) Compute random features for batch with random nets:
& b(Xg)== रेेअ [e, (Xe)....en (Xx)]' CRINM x|8i
Compute random features for support set with random nets:
b(Xs)+ / [s, (X (Xx))* E3 Na/j/111
Compute kernel matrices: Kns- < ((XX)TTT(X)
Kss + ( (x()s)
Calculate trained network output on batch: iB t- RBs(Rss + (41s))
Calculate loss: L = L(yB, UB)
Update coreset: Xg & Xg axxss Us + ys - dc
DC
Bys
end while
3.3 Replacing NNGP with an Empirical NNGP
When we sample from a Gaussian process / ~ GP(,, K), it suggests a natural finite feature map corresponding to scaled draws from the GP: x(z) = - (f)) fN (x))²² For most GPs, this insight is not relevant, sampling from GP typically requires Cholesky decomposition of the kernel matrix, requiring its computation in the first place [Rasmussen and Williams, 2006]. However, for NNGP we can generate approximate samples of f by instantiating random neural networks, fi(x) fe, (z), 0g ~ p(0), for some initialization distribution p(0). Moreover, with given neural network, we can define to be vector of dimension M by having a network with multiple output heads, meaning that with N networks, we have N M features. For our purposes, we typically have M = corresponds to C = 256 convolutional channels per layer. Even with this relatively large number of features, we still see a significant computation speedup over exact calculation.
4096, giving 32768 total features. For the convolutional architectures we consider, this
To sample f ~ GP(O, K), we would have to instantiate random infinite width neural nets, whereas, in practice, can only sample finite ones. This discrepancy incurs O(1/C) bias to kernel matrix entries, with C' being the width-relevant parameter (i.e., convolutional channels) [Yaida, 2020]. However, we have OLI((NC)) variance of the mean of the random features [Daniely et al., 2016], meaning that in practice, the variance dominates the computation over bias. This has been noted empirically in Novak al. [2019], and we verify that the finite-width bias does not significantly affect performance in appendix I, showing that we can achieve reasonable performance with as little as one convolution channel.
The time cost of computing these random features is linear in the training set and coreset size, [S). With the relatively low cost of matrix multiplication, this results in the construction of the kernel matrices Kys and Kss having O(T) + (ST) and O([S)), time complexity, respectively, as opposed O(TT)S)) and ((15)2) with KIP. Noting that the cost of matrix inversion is relatively small compared to random feature construction, our total runtime is reduced to linear in the coreset size. We empirically verify this linear time complexity in section 4.1 and additionally provide more detailed discussion in appendix C.
3.4 Loss Function in dataset distillation
We denoted earlier that LMSE is not well suited for dataset distillation settings. In particular, there two key problems:
Over-influence of already correctly classified data points. Consider two-way classification, with the label 1 corresponding to the positive class and -1 corresponding to the negative class. Let æ1 and 222 be items in the training set whose labels are both 1. Let SKHR (x) = Kz,s(Kss + - be the KRR output on given support set Xs. If fIRR(I1) and fKRR(12) -1, then the

---

Table 1: Kernel distillation results on five datasets with varying support set sizes. Bolded numbers indicate the best performance with fixed labels, and underlined numbers indicate the best performance with learned labels. Note that DC and DSA use fixed labels. (n 4)
Fixed Labels
Leamed Labels
Img/Cls
DC
DSA
KIP
RFAD (ours)
KIP
RFAD (ours)
1
91.7 + 0.5
88.7
95.2 + 0.2
96.7 = 0.2
97.3 17.+000 0.1
97.2 + 0.2
MNIST
10
97.4 + 0.2
97.8
98.4 + 0.0
99.0 0.1
99.1 0.1
99.1 = 0.0
50
98.8 +: 0.1
99.2 + 0.1
99.1 + 0.0
99.1 0.0
99.4 0.1
99.1 : 0.0
1
70.5 + 0.6
78.9 0.6
81.6 0.6
82.9
84.6 0.2
Beshion-MNIST
10
82.3 + 0.4
0.3
87.6 0.1
0.1
91.0+0.1
90.3 + 0.2
50
83.6 = 0.4
0.2
90.0 + 0.1
91.3 0.1
0.1
91.4 0.1
31.2
1..4
48.1
51.414
0.44
57.4 88
SVHN
10
76.1 0.6
0.5
75.8 0.1
0.3
8
78.2
50
82.3
0.3
81.3 0.44
8.2
8.1
82.4
1
28.3
0.5
28.8
59.1
61.1
61.4 0.2
CIFAR-10
10
44.9
0.5
6..0
73.110.11
0.2
T3.7 0.2
50
53.9
0.5
0.56
7.27+
76.1
8..6
76.6 0.3
1
12.8
0.3
0.3
31.8
36.0
34.
41.1 +
CIFAR-100
10
25.2
+ 0.3
32.3 0.3
0..
0.2
0.33
46.8 0.2
resulting MSE error on 21 and 22 would be 16 and 4, respectively. Notably, 21 incurs a larger loss and results in a larger gradient on Xg than 222, despite being correctly classified and z2 being incorrectly classified. In the heavily constrained dataset distillation setting, fitting both data points simultaneously is not possible, leading to underfitting of the data terms of classification in order to better fit already-correctly labeled data points in terms of regression.
Unelear probabilistic interpretation of MSE for classification. This prevents regression from environment, necessitating the use of transformation
being used directly in calibration-sensse functions tasks such as GP classification [Williams and Barber, 1998, Milios et al., 2018].
Based on these two issues, we adopt: Platt scaling [Platt, 2000], by applying cross entropy loss to the labels instead of an MSE one: Craa x-entropy (3/r f(xr) /T). where is a positive learned temperature scaling parameter. Unlike typical Platt scaling, we learn jointly with our support set instead of post-hoc tuning on a separate validation set. f(Xr) is still calculated using the same KRR formula. Accordingly, this corresponds to training network using MSE loss, but at inference, scaling the outputs by and applying softmax to get a categorical distribution. Unlike typical GP classification, we ignore the variance of our predictions, taking only the mean instead.
The combination of these three changes, namely, using the NNGP kernel instead of NTK, applying random-fcature approximation of NNGP, and Platt-scaling result in our RFAD algorithm, which is given algorithm
4 Experiments with READ
Here, we perform experiments to evaluate the performance of RFAD in dataset distillation tasks.
Benchmarks. We applied our algorithm to five datasets: MNIST, FashionMNIST, SVHN, CIFAR-10 and CIFAR-100 [LeCun et al., 2010, Xiao et al., 2017, Netzer et al., 2011, Krizhevsky et al., 2009], distilling the datasets to coresets with 1, 10 or 50 images per class.
Network Structure and Training Setup. Similar to previous work on dataset distillation, we used standard ConvNet architectures with three convolutional layers with average pooling and ReLU activations [Zhao et al., 2021, 2020, Nguyen et al., 2021b]. Similar to KIP [Nguyen et al., 2021b), we do not use instancenorm layers because of the lack of an infinite-width analog. During training, we used N random models, each with = 256 convolutional channels per layer, and during test- time, we evaluated the datasets using the exact NNGP kernel using the neural-tangents library [Novak et al., 2020]. We consider both the fixed and learned label configurations, with Platt scaling applied and no data augmentation. We used the regularized Zero Component Analysis (ZCA) preprocessing
5

---

Table 2: Performance of finite networks trained with gradient descent on DC/DSA, KIP, and RFAD distilled images. * denotes the result was obtained using learned labels. (n 12)
Img/Cls
DC/DSA
KIP to NN
RFAD to NN
91.7 1 0.5
90.1 1 0.1
94.4 1 1.5"
MNIST
10
97.8 + 0.1
97.5 + 0.0
98.5 + 0.1
50
99.2
0.1
98.3 + 0.1
98.8 + 0.1
70.6 1 0.6
0.3
78.6 1 1.3"
Fashion- MNIST
10
84.6 + 0.3
8.1
87.0 = 0.5
50
88.7 0.2
85.0 0.1"
88.8 0.4
31.2 1.4
57.3 + 0.1"
52.2 2.2
SVHN
10
79.2 0.5
75.0 0.1
74.9 + 0.4
84.4 0.4
8.15
80.9 + 0.3"
28.8 0.7
0.2
53.6 1 1.2"
CIFAR-10
0.5
6.37
66.3 - 0.5
0.5
68.6 0.2
71.1
13.9
15.7 0.2
26.3 + 1.1"
CIFAR-100
32.3 0.3
28.3 0.1
33.0 0.3
for SVHN, CIFAR-10 10, and CIFAR-100, to improve KRR performance for color image datasets [Shankar et al., 2020, Nguyen et al., 2021b]. More details are available in appendix D.
Baselines. We compare RFAD recently developed advanced dataset distillation algorithms such as: KIP [Nguyen et al., 2021a,b], Dataset Condensation with gradient matching (DC) [Zhao et al., 2021]. 1]. and differentiable Siamese augmentation (DSA) [Zhao and Bilen, 202
Table summarizes the results. We observe that in the fixed label configuration, our method outperforms other models in almost every dataset. In particular, it outperforms KIP by up 6.1% in the CIFAR-10 10 img/cls setting. We attribute this gain primarily to the use of Platt scaling. READ falls slightly behind KIP with learned labels. While this could partially be explained because we did not apply data augmentation, which marginally elevated performance for KIP on some datasets [Nguyen et al., 2021b], hypothesize that the performance difference is caused by the increased gradient variance associated with the random feature method. Nevertheless, in all experiments, RFAD least two orders of magnitude faster than KIP (Figure 2).
4.1 Time Savings during training
Next, we evaluated the time efficiency of READ. fig. 2 shows the time taken per training iteration on CIFAR-10 over coreset sizes and the number of models, N used evaluate the empirical NNGP kernel during training. Each training iteration contains 5120 examples from the training set. fig. depicts that the time taken by RFAD is linear in both the number of models used during training and in the coreset size, validating the time complexity described above. We expect that for larger coreset sizes, the matrix inversion will begin dominate due to its cubic complexity, but for small coreset sizes, the computation of the kernel matrix dominates the computation time.
In the right-hand side plot in fig. 2 we show the same plot in log-scale, compared to KIP. For KIP, we used batch size of 5000, and rather than measuring the time taken, we use the calcu- lation provided in appendix B of [Nguyen et al., 2021b], which describes the running time of the algorithm. We observe evidently that even for the modest coreset sizes, the quadratic time complexity of computing the exact kernel ma- trix in KIP results in it being multiple orders of magnitude slower than our RFAD. Both KIP and RFAD converge in between 3000-15000 training iterations, resulting times between 1-14hrs for RFAD and several hundred GPU hours for KIP, depending on the coreset size dataset, and when the carly stopping condition is triggered.
ning per necaaiio RIDD us varying CIMAR-10
R14 x
22
Corese: Size (mgg(Ch)
Time per training iteration for READ and KIP with varying number of models, N. Left: Linear plot of time. Right: Logarithmic time for training iteration. RFAD achieves over two-orders- of-nagni speedup compared KIP per training iteration while converging with a similar number of iterations.
Figure 2:

---

distilled coresets 60 73
43.0
425
NNGP
12
Coreset Size (Img/Cls)
Figure 3: NNGP to NTK transfer performance on RFAD distilled images. The blue line indicates the performance of RFAD distilled images evaluated NNGP. The orange line shows the same images evaluated using NTK. Despite being trained using the empirical NNGP kernel, these images still perform well on the NTK kernel, losing at most few percentage points. (n = 4)
Empirical NNGP inference accuracy for CIFAR-10, 10 img/cls, fixed labels
70
Accuracy (%)
Exact
60
C 128
256
C 512
C 1024
10
20
30
10a
10a
10*
10a
10:
102
Number of models
Number of features
Time taken (s)
Figure 4: Empirical NNGP kernel performance test-time with varying number of models used to compute the empirical NNGP kernel and number of convolutional channels per model. (n =
4.2 NTK Kernel and Finite Network Transfer
One of the key elements of the RFAD algorithm is the replacement of NTK with the empirical NNGP kernel. While we argued earlier that the two should exhibit a similar performance given their similar formalism, in this section, verify this claim experimentally. We evaluated obtained from our RFAD algorithm in two different transfer scenarios. In the first setting, at test time, used an NTK kernel instead of the NNGP kernel. In the second setting, we trained finite-width network with gradient descent on the distilled datasets obtained via RFAD. Similar to [Nguyen et al., 2021b], we used wi24-width finite network for finite-transfer results since better mimies the infinite width setting that corresponds to the NTK.
Remarkably, as shown in fig. 3, in most datasets, these coresets suffer little to no performance drop when evaluated using NTK compared to the exact NNGP kernel, despite being trained using the empirical NNGP kernel. The largest performance gap is 8% SVHN with 10 images per class, and in some datasets, notably CIFAR-100 NNGP. This suggests that either the exact NNGP kernel or the random feature NNGP kernel could potentially be used as a cheaper approximation for the exact NTK kernel.
img/cls evaluating using the NTK kernel outperforms
table 2 shows the resulting finite network transfer when training with gradient descent our coresets. Our images appear to have the best performance finite-network transfer, outperforming KIP in almost all benchmarks and the DC/DSA algorithms in many, despite DC/DCA being designed specifically for finite-width networks. We attribute this performance gain over KIP primarily two tricks used during training. Firstly, we applied centering. which, rather than training typical network (x), we instead train a network with its output at initialization subtracted: fo(x) - fo, (z).
fo,
This has been shown empirically to speed up the convergence of finite-width networks by reducing bias caused by the finite-width initialization while still preserving the NTK [Lee et al., 2020, Hu et al., 2020]. We find that for these small datasets, this modification significantly improves performance. The second trick is label scaling; we scale the target labels by factor > La [l (z) az1l3/e 2 and at inference divide the model's 's outputs by a. Note that this does not
7

---

Fashion-MNIST
CIRAR-10
87-5
1/d5, piatt
10/cts, platt
50ldls platt
1KB, mse
82.0
10kis, mise
775
s0lcss, m5c
75.0
Models used during training [N]
Figure 5: Objective function sensitivity. (n 4) to use Platt scaling and the number of models during
training (N) for Fashion-MNIST and CIFAR-10
affect the infinite-width setting, as in KRR, the output is linear w.r.t. the support set labels. Ablations of these changes in appendix F.
4.3 Empirical NNGP Performance at Inference
To validate the efficacy our method, we evaluated our distilled coresets using features from random networks as opposed to the exact kernel. We varied the width of individual networks between 128 and 1024 channels and the number of models between and 32. fig. 4 shows the resulting classification accuracy the CIFAR-10 dataset with 10 images/class. The black dot represents the configuration we used during training: 8 models, each with width 256 (More ablations are provided appendix I). We conclude that the random feature method, for all network widths, is able reach close the exact NNGP kernel performance (dotted line) a sufficient number of models are used. Interestingly. the performance is almost entirely dependent the total number of features (proportional to C N, with C' being the number of convolutional channels) and not the width of individual networks, suggesting that the finite-width bias associated with random finite networks is minimal.
In appendix I, we show that this can be taken to the extreme, with 70% accuracy achieved with a network with a single convolutional channel. These results corroborate the findings of [Novak et al., 2019], which first proposed this random feature method, where they found, like us, that performance was almost entirely determined by the total feature count.
Platt scaling. We performed ablations on the use the cross-entropy loss and the number of models used during training. We reran our algorithm on CIFAR-10 and MaNSi,, using either 1, 2, 4, or models during training, using MSE loss or cross-entropy loss. fig. shows the resulting performance of these configurations. Evidently, using cross-entropy loss results in substantial performance gains, even as much as 8% as with Fashion-MNIST with one img/cls.
RFAD Application I: Interpretability
Large datasets contribute to the difficulty of understanding deep learning models. In this paper, consider interpretability in the sense of the influence of individual training examples on network predictions [Hasani et al., 2019, Lechner et al., 2020, Wang et al., 2022]. One method of understanding this effect is the use of influence functions, which seek to answer the following counterfactual question: which item in the training set, if left out, would change the model's prediction the most [Hampel, 1974, Koh and Liang, 2017, Kabra et al., 2015]? For deep networks, this can only be answered approximately. This is because retraining network on copies of the training set with individual items left out is computationally intractable. One solution is to use kernel ridge regression on a small support set. We can recompute the KRR the kernel matrices with the ith individual coreset element removed, with K2 Ky,sy, K Ksy,sy being the resulting kernel matrices with the ith row/column corresponding to the ith coreset entry removed.
In particular, let P(yee = c|S) be the probability prediction (computed by applying Platt scaling) of an example belonging to class computed on the entire coreset, S. Let p(uen c|S \ i) be the same prediction calculated with the ith coreset element removed. We define the influence score, I, of coreset element Feas Eesc [p(the clS) - p(yees c|S i)]. Taking the top values of I; yields the most relevant examples.
8

---

Incorrect
prediction
Deer
*
Bird
Bird
Deer
Deer
Deer
Deer
Bird
Bird
Deer
Bird
Bird
Correct
Dog
Prediction
Dog
Dog
Dog
Cat
Cat
Dog
Dog
Dog
Test Image
both cases, Most Relevant in Coreset
Most Relevant in Training Set
Figure 6: The most relevant images for incorrect (top row) and correct (bottom row) prediction CIFAR-10. The most relevant coreset images are picked based on the coreset influence score /, and for their training set, the training influence score J. These metrics are fast to compute and result in semantically meaningful explanations for these two predictions.
While this method provides a simple way of gaining insights into how a prediction depends on the coreset, it does not provide insight into how this prediction comes from the original training set which produced the coreset. The method can be extended to accommodate this. Hcuristically, we conjecture that two elements are similar if their predictions depend on the same elements in the coreset. We compute Ply = c) and p(y = cSS for every element j in the training set and in the coreset. Then, we define its influence embedding as = = P(U; clS) ply; = c|5 \ (), 2 E R|S|x[O), This way, 2² defines the sensitivity of training datapoint prediction on the coreset. We compute the same embedding for a test datapoint = and to compare data points we use cosine similarity, Jus., cos(= 22). Values of z can be precomputed for the training set, typically in few minutes for CIFAR-10 10, allowing for relatively fast queries, in contrast to the more expensive Hessian inverse vector product required in Koh and Liang [2017]. which costly to compute and difficult to store.
fig. 6 shows the results of this algorithm applied to CIFAR-10 with 50 img/cls for incorrectly and correctly predicted image. the resulting queries are visually similar to the test data point. One could use this information not only explain a single incorrect prediction but to understand harmful items in their test set, or where more data needs be collected.
Classification Accuracy
92.0
01.0
80. 00.4%
96.9 1.4%
Male
Female
As a second application of RFAD, we create coresets that contain no duman-understandable information from the source dataset yet still retain high test performance. [Nguyen al., 2021a] proposed the concept of a p-corrupted coreset: A fraction of the coresets elements are completely independent of the source dataset. Practically, for our algorithm, this means initial- izing the coreset with random noise and keeping random o fraction of the pixels kept at their initialization. We term this algorithm RFAD,,. Adding noise gradient updates of the inputs of network can be shown give differentially private guarantees [Abadi et al., 2016]. While our scheme does not provide the same guarantees, we note the following two seevacy-preservinn is irreversible: there are many datasets for which a distilled dataset provides zero loss. Secondly, if the true data distribution assigns a low probability to images of white noise, then for high values of this guarantees that the distilled dataset stays far away in L2 norm from real data points, since fraction of the pixels are stuck their initialization. This means that distilled READ, dataset will not recreate any real points in the training set.
0
p- 0.4
0.8
p 0.95
Increasing Corruption Ratio, /
Figure 7: CelebA distilled datasets for male/female classification with image per class at varying corruption ratios. At = 0, the distilled images are very interpretable, but at 0.95, the images look like white noise, despite achieving 86.9% accuracy on the classification task.
properties of READ,; firstly, the distillation process

---

6 RFAD Application II: Privacy
We applied READ, on CIFAR-10. and
CIFAR-10
CelebA
CelebA faces datasets. For CIFAR-10 we distilled the standard 10-class classification
50-
Accuracy (%)
task, with corruption ratios taking values of
60-
80-
[0, 0.2.0..... 0.4, 0.8, 0.9), with 1, 10 or 50 images per class. For CelebA, we performed male/female binary classification with corruption ratios be- tween 0 and 0.95 with I, 10, or 50 samples per class. fig. 8 show the resulting performance.
40
70-
1/cls
10/cls
60-
50/cls
50-
0.5
Corruption Ratio (p)
For CIFAR-IO, even at corruption ratios of 0.9, we are able to achieve 40.6% accuracy with one sample per class, far above the natural baseline of 16. 1% ([Nguyen et al., 2021b) lb] table Al). For CelebA, we achieve 81 % accuracy with only two images, one male and one female, with 95% of the pixels in the image being random noise. We additionally visualize the distilled images for the male and female classes in the CelebA distillation task with one image per class in fig. at varying corruption ratios. While the image initially contains visually interpretable features with p O, they quickly devolve into pure noise at 0.95.
Figure 8: Performance of READ on CIFAR-10 10 and CelebA classification with varying support set sizes and corruption ratios. Performance degrades very gradually as noise increased, still achieving high performance with 90% corruption. (n = 3)
7 Conclusions
We proposed READ, dataset distillation algorithm that provides a 100-fold speedup over the current state-of-the-art KIP while retaining accuracy. The speedup is primarily due to the use of the approximate NNGP kernel as opposed the exact NTK one, reducing the time complexity from (((S()) to O(IS)). The success of the approximation here, combined with the similarity between the NTK and NNGP kernels, suggests the random network NNGP approximation as an efficient method for algorithms where the exact computation of the NNGP or NTK kernel is infeasible. We analyzed our method comprehensively and showed its effectiveness, and proposed two applications in model interpretability and privacy preservation. With this new tool, we hope that future work could begin to use Neural Tangent Kernel as an algorithmic design tool in addition its current theoretical use for neural network analysis. Lastly, READ has the following limitations:
Use of instancenorm. In practice, we found that our datasets distilled without instancenorm do transfer well to finite networks with it. Conversely, if we use random networks with instancenorm in READ, these transfer finite networks with instancenorm but not ones without the NNGP kernel. This suggests that the features used by networks with/without instancenorm differ, making it difficult distill datasets that perform well on both. We discuss this further in appendix G.
Overfitting in dataset distillation. On Platt scaling, we argued that the heavily constrained nature of dataset distillation leads to underfitting of the training set when using MSE-style loss in KIP, and we verified the efficacy of using a Platt loss instead. However, we observed that in simple datasets, such MNIST, or with large coresets relative to the data, such as CIFAR- 100 with 10 images per class, we could overfit to the dataset. We found that these distilled datasets were able to achieve near 100% classification accuracy on the training set, meaning that was distilled perfectly in terms of the Platt-loss. This implies that adding more images would not improve performance. Thus we hypothesize that using a Platt loss would be detrimental if the compression ratio is low.
Acknowledgements
This research has been funded in part by the Office of Naval Research Grant Number Grant N00014- 18-1-2833 1-2830, DSTA Singapore, and the J. P. Morgan AI Research program. We are very grateful.
10

---

References
M. Abadi, A. Chu, Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security CCS '16, page 308-318, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341394, doi: 10.1145799767499998336 URL httph::////. //tp://ooi.o.o org/ 10. 1.00..1455.0 /144//976749.... 2978318.
R. Aljundi, M. Lin, B. Goujaud, and Y. Bengio. Gradient based sample selection for online continual learning. NeurlPS, 2019.
S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In NeurlPS, 2019.
E. Belouadah and A. Popescu. Scail: Classifier weights scaling for class incremental learning. In The IEEE Winter Conference on Applications of Computer Vision, 2020.
J. Bien and R. Tibshirani. Prototype selection for interpretable classification. The Annals of Applied Statistics, 5(4):2403-2424, 2011.
O. Bohdal, Y. Yang, and T. Hospedales. Flexible dataset distillation: Learn labels instead of images. Neural Information Processing Systems Workshop. 2020.
Borsos, M. Mutný, and A, Krause. Coresets via bilevel optimization for continual learning and streaming. NeurlPS, 2020.
M. Castro, M. Marin-Jiménez N. Guil, C. Schmid, and Alahari. End-to-end incremental learning. In Proceedings of the European Conference on Computer Vision (ECCV), pages 233-248, 2018.
Y. Chen, M. Welling, and A. Smola. Super-samples from kernel herding. The Twenty-Sixth Conference Annual Conference on Uncertainty Artificial Intelligence. 2010.
L. Chizat, E. Oyallon, and F. R. Bach. On lazy training in differentiable programming. In NeurlPS, 2019.
M. B. Cohen, Musco, and Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. In Proceedings of the eventy-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1758-1777. SIAM, 2017.
A. Daniely, R. Frostig, and Y. Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity.
Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc 2016. URL https: http:///proeennneeeeeeeee wwg.ocedinngennuuip.... www.ineurucc.m hwtrripp..c/ppppe///////.. abea47ba24142ed wtw.:666776622222400002
Paper pdf.
A. G. de G. Matthews, J. Hron, M. Rowland, R. Turner, and 7. Ghahramani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018. URL httph: http://ppperreiieeeeee
A. Garriga-Alnso, C. E. Rasmussen, and L. Aitchison. Deep convolutional networks as shallow gaussian processes. In International Conference on Learning Representations, 2019. URL
https://openreviee
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. When do neural networks outperform kernel methods? arXiv preprint arXiv:2006. 33409, 2020.
F. R. Hampel.
The influence curve and its role in robust estimation. Journal of the American Statistical Association, 696346):383-33,, 1974. ISSN 01621459. URL http:/ http::/wwwwjjsto.o org/stable/ tessstaleee22stt. 2285666.
Har- Mar-Peled and S. Mazumdar, coresets for k-means and k-median clustering. In Proceedings of the sixtt annual ACM symposium Theory of computing, pages 291-300, 2004.

---

R. Hasani. A. Amini, M. Lechner, F. Naser, R. Grosu, and D. Rus. Response characterization for auditing cell dynamics in long short-term memory networks. In 2019 International Joint Conference on Neural Networks (IJCNN), pages 1-8. IEFE, 2019.
J. Hron, Y. Bahri, J. Sohl-Dickstein, and R. Novak, Infinite attention: Nngp and ntk for deep attention networks. In ICML, 2020.
W. Hu, Z. Li, and D. Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In International Conference on Learning Representations, 2020. URL https: //tp://eoep.....//////m/ wwt. met/fooummiiii wtt.oommmm.....eegegaa.a.a...a
F. Hutter, L. Kotthoff, and J. Vanschoren. Automated machine learning: methods, systems, challenges. Springer Nature, 2019.
A. Jacot, Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances in Neural Information Processing Systems, 2018.
I. Jubran, A. Maalouf, and D. Feldman. Introduction to coresets: Accurate coresets. CoRR, abs/1910.08707, 2019. URL
http///wwww...////////..o.oo. 087077
M. Kabra, A. Robie, and K. Branson. Understanding classifier errors by examining influential neighbors. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3917-3925, 2015.
M. Kaya and H. Bilge. Deep metric learning: A survey. Symmetry, 11:1066, 08 2019. doi: 10.3390/sym1 1091066.
B. Kim, R. Khanna, and O. Koyejo. Examples are not enough, learn to criticize! criticism for interpretability. In Proceedings of the 30th International Conference Neural Information Processing Systems, NIPS' 16, page 2296, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN
P. W. Koh and P. Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, page 1885-1894. Jog, 2017.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
M. Lechner, R. Hasani, A. Amini, T. A. Henzinger, D. Rus, and R. Grosu. Neural circuit policies enabling auditable autonomy. Nature Machine Intelligence, 2(10):642-652, 2020.
Y. LeCun, C. Cortes, and C. Burges. Mnist handwritten digit database. ATT Labs [Online). Available: http://yan.leeunnccmmme htlp://yann. lww.n. wwwcun.comm/xd///niisss 2, 2010.
J. Lee, Sohl-dickstein, J. Pennington. R. Novak, S. Schoenholz, and Y. Bahri. Deep neural networks as gaussian processes. In International Conference on Learning Representations, 2018. URL
https://openrevier. wttp://www.ettommmimiiie B1EA-M--A-MM- MZOZ.
Lee, S. Schoenholz, Pennington, Adlam, L. Xiao, R. Novak, and J. Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15115661112.. Curran Associates, Inc., 2020. URL https: / /tttts://p/ttt http///rroeeeen..eeee////o/ nwwris.eurisp.ccm cc/ Paper pdf.
paper/2020/fiin http:///000//11////000001111ff10
N. Loo, R. Hasani, A. Amini, and D. Rus. Evolution of neural tangent kernels under benign and adversarial training. In Advances in Neural Information Processing Systems, 2022.
J. Lorraine, P. Vicol, and D. Duvenaud. Optimizing millions of hyperparameters by implicit differ- entiation. In International Conference on Artificial Intelligence and Statistics, pages 1540-1552. PMLR, 2020.
M. Lucic, M. Faulkner, A. Krause, and D. Feldman. Training gaussian mixture models at scale via coresets. The Journal of Machine Learning Research, (8())558555909 2017.
12

---

D. Maclaurin, D. Duvenaud, and R. Adams. Gradient trasient-based hyperparameter optimization through reversible learning. In International Conference on Machine Learning, pages 2113-2122, 2015.
D. Milios, R. Camoriano, P. Michiardi, L. Rosasco, and M. Filippone. Dirichlet- based gaussian processes for large-scale calibrated classification. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 6008-6018, 2018.
B. Mirzasoleiman, J. A. Bilmes, and Leskovec. Coresets for data-efficient training of machine learning models. In Proceedings of the 37th International Conference on Machine Learning, ICML. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6950-6960. PMLR, 2020.
R. M. Neal. Bayesian Learning for Neural Networks. Springer-Vetie Berlin, Heidelberg, 1996. ISBN 0387947248.
Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. Reading digits in natural images with unsupervised feature learning. Google Research, 2011.
T. Nguyen, Z. Chen, and Lee. Dataset meta-learning from kernel idge-reeressson International Conference Learning Representations, 2021a. URL https:// www./eeee//ttttaeemm 1-PrrQrKOQR.
T. Nguyen, R. Novak, L. Xiao, and J. Lee. Dataset distillation with infinitely wide convolutional networks. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021b. URL hett://orum.dd--iiiPaaaaaaaa https://openrevier
R. Novak, L. Xiao, Bahri, Lee, G. Yang, D. A. Abolafia, J. Pennington, and J. Sohl-dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. In International Conference on Learning Representations, 2019. URL http:t:::/// http::::s////pprveieeeeee wtt.:/wwwwee//oumiiieee B1g30j0qF7.
R. Novak, L. Xiao, J. Hron, J. Lee, A. A. Alemi, J. Sohl-Dickstein, and S. S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. International Conference Learning Representations, 2020. URL https: //penreviieee net/ tnee/fforue http//foummidddkdiae srrrum?iddSkDDDyFFS.
R. Novak, J. Sohl-Dickstein, and S. S. Schoenholz. Fast finite width neural tangent kernel. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvári, G. Niu, and S. Sabato, editors, International Conference on Machine Learning, ICML 2022. 17-23 July 2022, Baltimore, Maryland, USA. volume 162 of Proceedings of Machine Learning Research, pages 17018-17044. PMLR, 2022. URL https : httptt:::/pproeeeeee http://pooceeeeneeeeeee//ee mlr, press/ paress/vv62//ee www2//ovvak22 html.
D. Peng, D. S. Park, J. Lee, J. Sohl-dickstein, and Y. Cao. Towards gugdggided neural architecture search. In ArXiv, 2020.
J. M. Phillips. Coresets and sketches. arXiv preprint arXiv:1601.00617. 2016.
Platt. Probabilistic outputs for support vector machines and comparisons regularized likelihood methods. Adv. Large Margin Classif., 10, 06 2000.
A. Rahimi and B. Recht. Random features for large-scale kernel machines. Proceedings of the 20th International Conference on Neural Information Processing Systems, pages 1177-1184, 2007.
C. E. Rasmussen and C. K. I. Williams. Gaussian processes for machine learning. Adaptive computation and machine learning. MIT Press, 2006. ISBN 026218253X.
S.-A. Rebuffi, A. Kolesnikov, G. Sperl, and C. Lampert. icarl: Incremental classifier and representation learning. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5533-5542,, 2017.
M. Refinetti, S. Goldt, F. Krzakala, and I.. Zdeborová. Classifying high-dimensional gaussian mix- tures: Where kernel methods fail and neural networks succeed, arXiv preprint arXiv:2102. / 2021.
13

---

B. Scholkopf, S. Mika, C. Burges, P. Knirsch, K.-R. Muller, G. Ratsch, and A. Smola. Input space versus feature space kemel-based methods. IEEE Transactions on Neural Networks, 10(5): 1000-1017, 1999. doi: 10.1109/72.788441
V. Shankar, A. Fang, W. Guo, Fridovich-Keil. J. Ragan-Kelley, L. Schmidt, and B. Recht. Neural kernels without tangents. In ICML, pages 8614-8623 2020. URL http::/procceedingg mml.. press/v119 1ttee//1199/aaaaa22aa....
shankar20a.html
S. Shleifer and E. Prokop. Using small proxy datasets to accelerate hyperparameter search. search... arXiv preprint arXiv: (90..0087008 2019.
Snell, K. Swersky, and R. Zemel. Prototypical networks for few-shot learning. In Advances in neural information processing systems, pages 4077-4087, 2017.
E. Snelson and Z. Ghahramani. Sparse gaussian processes using pseudo-inputs. In Advances in neural information processing systems, pages 1257-1264, 2006.
I. Sucholutsky and M. Schonlau. Soft-label dataset distillation and text dataset distillation. arXiv preprint arXiv:1910.02551, 2019.
M. Titsias. Variational learning of inducing variables in sparse gaussian processes. In Artificial Intelligence and Statistics, pages 567-574, 2009.
M. Toneva, A. Sordoni, R. T. d. Combes, A. Trischler, Y. Bengio, and G. J. Gordon. An empirical study of example forgetting during deep neural network learning. ICLR, 2019.
O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra, al. Matching networks for one shot learning, In Advances in neural information processing systems, 2016.
T. Wang. J.-Y. Zhu, A. Torralba, and A. A. Efros. Dataset distillation. arXiv: 1. 10959, 2018
arXiv preprint
T.-H. Wang, W. Xiao, T. Seyde, R. Hasani, and D. Rus. Interpreting neural policies with disentangled tree representations, arXiv preprint S.I1:22200006500 2022.
C. K. I. Williams and D. Barber. Bayesian classification with gaussian processes. IEEE Trans. Pattern Anal. Mach. Intell. 20( 20(12):1342-133 dec 1998. ISSN 0162-8828. doi: 10. 10.1109/34.335877.
H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747 2017.
Yaida. Ron-Gaussian processes and neural networks at finite widths. In J. and R. Ward, editors, Proceedings of The First Mathematical and Scientific Machine Learning Conference, volume 107 of Proceedings of Machine Learning Research, pages 165-192. PMIR, 20-24 Jul 2020. URL https: htttss:/proceeet http://proccee....////// mlr ppppss//117/yaaiaa22/00 html.
G. Yang. Tensor programs Wide feedforward or recurrent neural networks of any architecture are gaussian processes. In NeurlPS 2019, December 2019.
A. Zandieh, I.
Han, H. Avron, N. Shoham, C. Kim, and J. Shin. Scaling neural tangent kernels via sketching and random features. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL /tttts://openrvviiii net/forum? IiR= A6558h.
B. Zhao and H. Bilen. Dataset condensation with distribution matching. a 10,04181 2021a.
arXiv preprint
B. Zhao and H. Bilen. Dataset condensation with differentiable siamese augmentation. arXiv preprint arXiv:2102.08255 2021b.
B. Zhao, K. R. Mopuri, and H. Bilen. Dataset condensation with gradient matching. In International Conference on Learning Representations, 2021. URL.httpss//ggenreiieer net/ forum?id- mSAK.
14

---

S. Zhao, Z. Liu, J. Lin, J.-Y. Zhu, and S. Han. Differentiable augmentation for data-efficient gan training. Neural Information Processing Systems, 2020.
Zhuang, Tang, Y. Ding, S. Tatikonda, Dvornek, X. Papademetris, and J. S. Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. arXiv preprini arXiv:2010.07468 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "uIpHuuXVr9L", "reviewer": "Reviewer_orEs", "summary": "The paper proposes a set of changes/improvements to a prior SOTA dataset distillation algorithm (KIP), that allows to achieve comparable or better results at a fraction (e.g. 1/100) of the compute cost.\n\nThe changes are:\n- Using finite-width NNGP at training time (vs the infinite-width NTK), allowing a dramatic compute improvement.\n- Using the infinite-width NNGP at test time (vs the infinite-width NTK).\n- Using cross-entropy loss with platt-scaling and a trainable temperature parameter.\n- Representing the optimized support set as a matrix product (trainable preprocessing) instead of a single matrix.\n- Using centering and label scaling for RFAD -> NN transfer.\n", "questions": "- In Table 2, are random seeds used to initialize RFAD, and those used to initialize NNs, completely disjoint? To make sure there is no benefit gained due to seed reuse.\n\n- Line 619 \"this does not add any extra variables to the coreset\" - why not, doesn't it add new $(CHW)^2$ trainable parameters?\n\n- Why do you present results with centering and label scaling in Table 2? Wouldn't it be more fair to not use these settings, since I assume they weren't used in KIP or DC/DSA (and/or rerun those methods with centering and label scaling), to which you compare? This way we could better disentangle the benefits of the images themselves vs these optimization settings.\n", "limitations": "This work will help lower the carbon footprint of the industry, and make dataset distillation algorithms more accessible to the broader community, so I believe it only has a positive societal impact.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper clearly demonstrates a dramatic speedup in achieving comparable to prior SOTA results, which is why I recommend acceptance. However, it does so with a moderately-sized bag of various tricks, and I find the analysis/interpretation/ablations of the results somewhat lacking. Therefore my recommendation is only weak.\n\n## Strengths:\n\n- Clearly demonstrated comparable or better to SOTA results at a fraction of the compute cost.\n- The paper overall is clear and easy to follow.\n- Code is released.\n\n## Weaknesses:\n\n- The compute cost analysis ($|S|$ vs $|S|^2$; section 4.1, abstract, conclusion, etc) appears vague and/or potentially wrong. \n\t* Firstly, the asymptotic inference costs of both KIP and RFAD are the same due to using the infinite-width kernel; RFAD could be a constant 2x faster than KIP due to using NNGP vs NTK. For a test set of size $T$, this inference cost would be something like $|S|^3 + (|S|^2 + |S||T|)H^2 W^2 D$, i.e. the cost of the support set matrix inversion plus the cost of computing the support/test set kernels.\n\t* At training, cost of a single KIP iteration should be same as above (where $T$ is the training set size; I think complexity on line 105 is incorrect), while RFAD would be something like $|S|^3 + (|S|^2 + |S||T|) N M + (|S|+|T|)N M^2D$, if $M$ is the number of channels (i.e. the cost of support set matrix inversion plus the cost of computing the NNGP kernels, plus the cost of computing the features for the NNGP kernel). The source of the speedup might be the relatively small $N M$ compared to $H^2 W^2 D$; but IIUC for large $|T|$, both methods remain linear in $|S|$. So I don't see immediately why KIP has different scaling with $|S|$ that your method, and how exactly you plot the KIP curve in Figure 2.\n    * My quick and rough math above might be wrong, but either way the authors should provide a more rigorous complexity analysis of both methods, and revise or substantiate their claims.\n\n- No ablations of RFAD with and without Platt scaling cross-entropy loss, and with/without trainable matrix product (as described in the appendix).\n\n## Minor:\n\n- Some minor typos, e.g. Line 691: \"Empirical NTK\" -> \"Empirical NNGP\". Line 676 - capitalize \"Table 5\". Line 671 - \"our times\", line 149: \"Probabilistic interpretation of MSE for classification?\" etc.\n\n- Could be useful to have an ablation table with results obtained from doing inference on the test set with the same exact NNGP as used during training (I assume you have these results from the appendix figures).\n\n- Would be interesting to also compare against the DC/DSA compute costs.\n\n- Codebase uses two frameworks (JAX and PyTorch), which is slightly inconvenient.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nvdJ8SZeSBh", "reviewer": "Reviewer_ta1Y", "summary": "The paper proposed an approximation algorithm to accelerate the Kernel Inducing Points (KIP) method with neural kernels for dataset distillation problem, which is mainly based on the random feature approximation of the Neural Network Gaussian Process (NNGP) kernel. To save the time cost of the KIP algorithm with neural kernels, the paper focused on approximating the NNGP kernel instead of the Neural Tangent Kernel (NTK), and proposed a simple approximation algorithm with empirical NNGP features which are easily generated from finite-width random neural networks. Besides, the paper changed the square loss to cross-entropy loss when learning the inducing points. In experiments, the efficiency superiority of the proposed method RFAD is verified with limited loss on performance. In addition, despite training KIP on the NNGP kernel which is naturally friendly for computation, the obtained distilled data could also apply to NTK and finite-width neural networks.", "questions": "1. What does it mean by \"n=4\"|\"n=12\" in the tables?\n2. What is the difference between fixed and learned label configurations? For fixed label configuration, do you mean the label solving (LS) method?\n3. As claimed in the experiments section, the performance gain is primarily attributed to the use of Platt scaling. Does this mean that if using cross-entropy loss, original KIP will perform even better than the results in tables?\n4. It looks that replacing the loss function is independent to the speeding up of the algorithm, thus a comparison with RFAD without cross-entropy loss, or KIP with cross-entropy loss is necessary.\n5. What are the technical challenges in the implementation? They should be written in the paper.\n\nminor issues:\n\nPage 8 and Page 4. The subscripts of the letters in the formulas are too large.\n\nBesides, compared to many related work about coresets, Reduced Set Construction is more similar to this paper and dataset distillation, which was studied in:\n\nScholkopf, B.; Mika, S.; Burges, C. J. C.; Knirsch, P.; Muller, K.; Ratsch, G.; and Smola, A. J. 1999. Input space versus feature space in kernel-based methods. IEEE Transactions on Neural Networks 10(5): 1000–1017.", "limitations": "NA.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Stengths:\n\n1. The efficiency superiority of the proposed method RFAD is impressing. The reduction on the computational cost for KIP on NNGP over MNIST and CIFAR is significant compared to prior works [Nguyen et al., 2021], and succeed to make the KIP with neural kernels more practical for real scenarios. The engineering efforts should be admired.\n\n2. The paper is technically sound and well presented with broad literature review. Extensive experiments could support the effectiveness of the proposed method.\n\nWeakness:\n\n1. The main weakness of the paper is: the novelty is limited, especially compared with the previous work [Nguyen et al., NeurIPS'21; Nguyen et al., ICLR'21]. The approximation scheme is direct, and theoretically guaranteed, and already verified in the experiments of existing work. Besides, the improvement on MNIST and CIFAR is significant in [Nguyen et al., 2021], and before that we can not imagine that one can get 64.3% performance on CIFAR with only 1 image per class. However, from training KIP with KRR on NTK, to training KIP with KRR on NNGP, and then to training KIP with KRR on random finite-width neural networks and cross-entropy loss. The theoretical rigor is getting weaker and weaker.\n\n2. The Platt scaling attributed highly to the performance of RFAD, but not compared separately.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "42ZQCjtireY", "reviewer": "Reviewer_DFgr", "summary": "The paper provides a data distillation inspired by KIP. While KIP is the current state-of-the-art data distillation model, the complexity of such an algorithm becomes impractical when dealing with large models as well as large datasets. The authors refer to the use of an approximated variant of the NNGPs via Random Features to accelerate the KIP algorithm while maintaining comparable results.", "questions": "1) Using a different loss than the MSE loss function is indeed clever. However, would it be better to use a more robust loss function than that of the MSE, for example, $\\ell_1$-loss for example? \n2) Is it possible to run your algorithm with coreset_size=50 with CIFAR-100? If not, is it related to insufficient memory?\n3) is the proposed method applicable when using the Imagenet dataset or a more complex deep learning model, e.g., ResNet50?\n ", "limitations": "The authors clearly stated their limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths:\n    1) The paper presents a practical algorithm for dataset distillation.\n    2) It was a great idea to introduce an alternative loss function, replacing the MSE to obtain better results.\n    3) The authors shed light on the applicabilities of their methods, from privacy, interpretability, and data corruption.\n    4) The paper is clear and properly written.\n\n* Weaknesses:\n    1) From a theoretical point of view, what is the approximation factor of the approximated NNGP kernel matrix with respect to the NNGP kernel matrix? Please do shed some light on this.\n    2) Similar to KIP, only coresets of size 10 were computed when handling the CIFAR-100 dataset. See Questions.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept