Dataset Meta-Learning from Kernel Ridge-Regression
Authors: Timothy Nguyen
Zhourong Chen
Jaehoon Lee
Venue: ICLR 2021 Poster (2021)
Keywords: dataset distillation
dataset compression
meta-learning
kernel-ridge regression
neural kernels
infinite-width networks
dataset corruption

Abstract: One of the most fundamental aspects of any machine learning algorithm is the training data used by the algorithm. 
We introduce the novel concept of $\epsilon$-approximation of datasets, obtaining datasets which are much smaller than or are significant corruptions of the original training data while maintaining similar performance. We introduce a meta-learning algorithm Kernel Inducing Points (KIP) for obtaining such remarkable datasets, drawing inspiration from recent developments in the correspondence between infinitely-wide neural networks and kernel ridge-regression (KRR). For KRR tasks, we demonstrate that KIP can compress datasets by one or two orders of magnitude, significantly improving previous dataset distillation and subset selection methods while obtaining state of the art results for MNIST and CIFAR10 classification. Furthermore, our KIP-learned datasets are transferable to the training of finite-width neural networks even beyond the lazy-training regime. Consequently, we obtain state of the art results for neural network dataset distillation with potential applications to privacy-preservation.

DATASET META-LEARNING FROM KERNEL RIDGE-
REGRESSION
Timothy Nguyen
Zhourong Chen
Jachoon Lee
Google Research
(timothycnguyen, zrchen, jaehlee)@google.com
ABSTRACT
One of the most fundamental aspects of any machine learning algorithm the training data used by the algorithm. We introduce the novel concept of approximation of datasets, obtaining datasets which are much smaller than or are significant corruptions of the original training data while maintaining similar model performance. We introduce meta-learning algorithm called Kernel Induc- ing Points (KIP) ) for obtaining such remarkable datasets, inspired by the recent developments in the correspondence between infinitely-wide neural networks and kernel ridge-regression (KRR). For KRR tasks, demonstrate that KIP press datasets by one or two orders of magnitude, significantly improving previous dataset distillation and subset selection methods while obtaining state of the art results for MNIST and CIFAR-10 classification. Furthermore, our KIP -learned datasets are transferable the training finite-width neural networks even be- yond the sazy-training regime, which leads to state of the art results for neural network dataset distillation with potential applications to pweaccypreservatioon.
INTRODUCTION
Datasets are pivotal component in any machine learning task. Typically, a machine learning prob- lem regards a dataset as given and uses it to train a model according to some specific objective. In this work, we depart from the traditional paradigm by instead optimizing dataset with respect to learning objective, from which the resulting dataset can be used in a range of downstream learning tasks.
Our work is directly motivated by several challenges in existing learning methods. Kernel methods instance-based learning (Vinyals al. 2016 Snell et al. 2017 Kaya & Bilge 2019) in general require support dataset to be deployed at inference time. Achieving good prediction accuracy typically requires having a large support set, which inevitably increases both memory footprint and latency at inference time-thhe the scalability issue. It can also raise privacy concerns when deploying support set of original examples, e.g., distributing raw images to user devices. Additional challenges to scalability include, for instance, the desire for rapid 2019) and minimizing the resources consumed when replaying data for continual learning (Borsos) al. 2020). A valuable contribution all these problems would be to find surrogate datasets that can mitigate the challenges which occur for naturally occurring datasets without a significant sacrifice in performance.
search (Shleifer & Prokop)
This suggests the following
Question: What is the space of datasets, possibly with constraints in regards to size signal preserved, whose trained models are all (approximately) equivalent to some specific model?
In attempting to answer this question, in the setting of supervised learning image data, we dis- cover a rich variety of datasets, diverse in size and human interpretability while also robust to model architectures, which yield high performance state of the art (SOTA) results when used training data. We obtain such datasets through the introduction of a novel meta-learning algorithm called Kernel Inducing Points (KIP) Figure shows some example images from our learned datasets.

---

(a)
Airplane
Automobile
Bird Cat
(b)
Original
Frog
Bird
Myrite Ls 500 support
KIP
KIP p-09
Figure I: (a) Learned samples of CIFAR-10 using KIP and variant KIP,, for which p fraction of the pixels are uniform noise. Using 1000 such images to train hidden layer fully connected net- work results in 49.2% and 45.0% CIFAR-10 test accuracy, respectively, whereas using 1000 original CIFAR- 10 images results in 35.4% test accuracy. (b) Example of labels obtained by label solving (LS) ) (left two) and the covariance matrix between original labels and learned labels (right). Here, 500 labels were distilled from the CIFAR-10 train dataset using the the Myrtle 10-layer convolu- tional network. A test accuracy of 69.7% is achieved using these labels for kernel ridge-regression.
We explore KIP in the context compressing and corrupting datasets, validating its effectiveness in the setting of kernel-ridge regression (KRR) and neural network training benchmark datasets MNIST and CIFAR-10. Our contributions can summarized follows:
1.1 SUMMARY CONTRIBUTIONS
We formulate a novel concept of e-approximation dataset. This provides a theoretical framework for understanding dataset distillation and compression.
We introduce Kernel Inducing Points (KIP), meta-learning algorithm for obtaining é- approximation of datasets. We establish convergence in the case of a linear kernel in The- orem | We also introduce a variant called Label Solve (LS) ), which gives a closed-form solution for obtaining distilled datasets differing only via labels.
We explore the following aspects of e-approximation of datasets:
1. Compression (Distillation) for Kernel Bidge-Regression For kernel ridge regres- sion, we improve sample efficiency by over one or two orders of magnitude, e.g. using 10 images to outperform hundreds or thousands of images (Tables I vs Tables A A2 We obtain state of the art results for MNIST and CIFAR- 10 classification while using few enough images (10K) to allow for in in-memory inference (Tables A3 A4).
Compression (Distillation) for Neural Networks: We obtain state of the art dataset distillation results for the training of neural networks, often times even with only single hidden layer fully-con fully-connected network (Tables and 2
Privacy: We obtain datasets with a strong trade-off between corruption and test accu- racy, which suggests applications to grivacy-preserving dataset creation. In particular, we produce images with up to 90% of their pixels corrupted with limited degradation in performance as measured by test accuracy in the appropriate regimes (Figures 3 A3 and Tables A1)) and which simultaneously outperform natural images, in wide variety settings.
We provide an open source implementation of KIP and LS, available in an interactive Co- lab notebook!
2 SETUP
In this section we define some key concepts for methods.
https://cooahh hww.

---

Definition 1. A dataset in Rd is set of distinct vectors in R' for some 2 1. We refer to each such vector as a datapoint. A dataset labeled if each datapoint is paired with label vector in RC, for some fixed C. A datapoint along with its corresponding label is labeled datapoint. We use the notation D = [X, y). where X E RRaxd and y E R to denote the tuple of unlabeled datapoints X with their corresponding labels y-
We henceforth assume all datasets are labeled. Next, we introduce our notions of approximation, both of functions (representing learned algorithms) and of datasets, which are characterized in terms of performance with respect to loss function rather than closeness with respect to a metric. A loss function & IRC _C R is one that is nonnegative and satisfies {(2, 2) for all 2. Definition 2. Fix loss function f. and let f: Rdd IRC be two functions. Let e 2 0.
1. Given a distribution on Rd x IRC we say f and f are weakly e-close with respect to (e, P) if
B B( (e((()).)) - B(aay> (el(x))))) Sc.
(1)
2. Given a distribution P on Rdd we say and f are strongly e-close with respect to (e, P) if Egpp (e((())(
S.
We drop explicit reference to P) if their values understood or immaterial.
Given a learning algorithm (e.g. gradient descent with respect to the loss function of neural network), let AD denote the resulting model obtained after training A on D. We regard Ad as mapping from datapoints to prediction labels.
Definition 3. Fix learning algorithms A and Å. Let D and D be two labeled datasets in Hd with label space RC_ Let e 2 O. We say D is weak e-approximation of D with respect to (Á, A, P) if Ań and AD are weakly e-close with respect to P), where l is a loss function and P distribution on Idd RC, We define strong e-approximation similarly. We drop explicit reference to (some of) the Á, A, E, P if their values are understood or immaterial.
We provide some justification for this definition in the Appendix. this paper. we will measure e- approximation with respect 0-1 loss for multiway classification (i.e. accuracy). We focus weak e-approximation, since in most of our experiments, we consider models in the low-data regime with large classification error rates, in which case, sample-wise agreement of two models is not of central importance. On the other hand, observe that if two models have population classification error rates less than e/2, then (2) is automatically satisfied, in which case, the notions of weak-approximation and strong- apoon-aaprooimationn converge.
We list several examples of c-approximation, with e = 0, for the case when À A are given by the following:
Example 1: Support Vector Machines. Given dataset D of size N, train an SVM on D and obtain M support vectors. These M support vectors yield dataset i that is a strong 0-approximation to D in the linearly separable case, while for the nonseparable case, one has also include the datapoints with positive slack. Asymptotic lower bounds asserting M = O(N) have been shown in Steinwart 2003
Example 2: Ridge Regression. Any two datasets D and D that determine the same ridge-regressor O-approximations of each other. In particular, in the scalar case, we can obtain arbitrarily small O-approximating D as follows. Given training data D (X, y) in Rd the corresponding ridge- regressor is the predictor
x² w x" w = 2 (X)),,
(3)
(4)
4 x = x" (XX" + A1)-1
(5)
2 As specific example, many thousands of support vectors are needed for MNIST classification 2005)).
(ordds
3

---

where for À 0, we interpret the inverse a pseudoinverse. It follows that for any given R can always find (X, 35) of arbitrary size (i.e. X E Rxxd y Rax1 with arbitrarily small) that satisfies + x (x) Simply choose X such that is in the range of (x)).. The resulting dataset (X, 17) is 0-approximation to D. If have a C-ddimensiona regression problem, the preceding analysis can be repeated component-wise in label-space to show 0-approximation with a dataset of size at least C' (since then the rank of 2x(X) can be made at least the rank of w E IRd
We are interested in learning algorithms given by KRR and neural networks. These can be inves- tigated in unison via neural tangent kernels. Furthermore, we study two settings for the usage of e-approximate datasets, though there are bound be others:
1. (Sample efficiency/ / compression) Fix What is the minimum size of D needed in order for D to be an e-approximate dataset?
2. (Privacy guarantee) Can an e-approximate dataset be found such that the distribution from which it is drawn and the distribution from which the original training dataset is drawn satisfy a given upper bound in mutual information?
Motivated by these questions, we introduce the following definitions:
Definition 4. (Heuristic) Let D and D be two datasets such that D is weak c-approximation of D, with D < D and small. We call |D/| | the compression ratio.
In other words, the compression ratio is a measure of how well î compresses the information available in D, measured by approximate agreement of their population loss. Our definition is heuristic in that e not precisely quantified and so is meant as a soft measure of compression.
Definition 5. Let I be an algorithm that takes a dataset D in Red and returns a (random) collection of datasets in Rd, For 0 I p < 1, we say that I is p-corrupted if for any input dataset D, every datapoint drawn from the datasets of ((D) has at least p fraction its coordinates independent of D.
In other words, datasets produced by I' have p fraction of its entries contain no information about the dataset D (e.g. because they have a fixed value or are filled in randomly). Corrupting information is naturally way of enhancing privacy, as it makes it more difficult for an attacker to obtain useful information about the data used to train a model. Adding noise to the inputs to neural network or of its gradient updates can be shown to provide differentially private guarantees (Abadi et al. (206)).
3 KERNEL INDUCING POINTS
Given a dataset D sampled from distribution P, we want to find small dataset ò that is approximation to D (or some large subset thereof) with respect to (Å, A, e, P). Focusing on Ā A= A for the moment, and making the approximation
EEDEE 8 (AA(())))) Ro ELWEED ((A
(6)
this suggests we should optimize the right-hand side of (6) with respect to D, using D as a val- idation set. For general algorithms Á, the outer optimization for H computationally expensive and involves second-order derivatives, since one has to optimize over the inner loop encoded by the learning algorithm Á. We are thus led to consider the class of algorithms drawn from kernel ridge- regression. The reason for this are two-fold. First, KRR performs convex-optinization resulting in a closed-form solution, so that when optimizing for the training parameters of KRR (in particular, the support data). we only have to consider first-order optimization. Second, since KRR for a neural tan- gent kernel (NTK) approximates the training of the corresponding wide neural network (Jacot al.) 2018 Lee et al. 2019 Arora et al.] 2019a [ee et al.] 2020), we expect the use of neural kernels yield c-approximations of 1) for learning algorithms given by broad class of neural networks trainings as well. (This will be validated in our experiments.)
We ignore labels in our notion of p-corrupted since typically the label space has much smaller dimension than that of the datapoints.
4

---

Algorithm 1: Kernel Inducing Point (KIP)
Require: A target labeled dataset (Xe, yc) along with a kernel or family of kernels.
1: Initialize a labeled support set (Xx, Us).
2: while not converged do
3: Sample random kernel. Sample random batch (X Ms) from the support set. Sample random batch (Xt, l)t)) from the target dataset.
4: Compute the kernel ridge-regression loss given by using the sampled kernel and the sampled support and target data.
5: Backpropagate through X, (and optionally Ys and any hyper-parametenn of the kernel) and update the support set (Xs: Us) by updating the subset (Xx, Us).
6: end while
7: return Learned support set (X Uo)
This leads to our first-order meta-learning algorithm KIP (Kernel Inducing Points), which uses kernel-ridge regression to learn e-approximate datasets. It can regarded as an adaption of the inducing point method for Gaussian processes (Snelson & Ghahramani 2006) to the case of KRR. Given a kernel K, the KRR loss function trained on a support dataset xx, Us) and evaluated on larget dataset (X,, yo) is given by
L(X Mo) = 1y.
+ AT)-'yal?
where if and V are sets, Kuv is the matrix of kernel elements (K(u, v))ueU Here À > fixed regularization parameter. The KIP algorithm consists of optimizing with respect to the support set (either just the X, or along with the labels y.). see Algorithm| Depending on the downstream task, it can be helpful to families of kernels (Step 3) because then KIP produces datasets that are e-approximations for a variety of kernels instead of single one. This leads to corresponding robustness for the learned datasets when used for neural network training. We remark on best experimental practices for sampling methods and initializations for KIP in the Appendix. Theoretical analysis for the convergence properties of KIP for the case of a linear kernel is provided by Theorem I
Sample K KTP -learndd images can be found in Section F
KIP variations: i) We can also randomly augment the sampled target batches in KIP This effec- tively enhances the target dataset (X,, Vt), and we obtain improved results in this way. with no extra computational cost with respect to the support size. ii) We also can choose a corruption fraction 0 < p < 1 and do the following. Initialize random p-percent of the coordinates of each support datapoint via some corruption scheme (zero out all such pixels or initialize with noise). Next, do not update such corrupted coordinates during the KIP training algorithm (i.e. only perform gradient updates on the complementary set of coordinates). Call this resulting algorithm KIP p. In this way, is p-corrupted according Definition and we use it obtain highly corrupted datasets. KIPp p
Label solving: In addition to KIP, where we learn the support dataset via gradient descent, we propose another inducing point method, Label Solve (LS ), in which directly find the minimum of (7) with respect to the support labels while holding X, fixed. This is simple because the loss function is quadratic in ya. We refer to the resulting labels
v @o (Kx.x (Kx.x. + +
as solved labels. As Pu is the pseudo-inverse operation, y is the minimum- norm solution among minimizers of (7. If Kx.x, injective, using the fact that (A (B) for A injective and B surjective (Greville ((eviilee(166)) (1666)), we can rewrite (8)
y = (Kx.x, + (Xx
4 EXPERIMENTS
We perform three sets of experiments to validate the efficacy of KIP and LS for dataset learning. The first set of experiments investigates optimizing KTP and L.S for compressing datasets and achieving
5

---

state of the art performance for individual kemnlls. The second set of experiments explores transfer- ability of such learned datasets across different kernels. The third set of experiments investigate the transferability of KIP -learned datasets to training neural networks. The overall conclusion is that KTP -Te-learned datasets, even highly corrupted versions, perform well in a wide variety of settings. Experimental details can be found in the Appendix.
We focus on MNIST (LeCun et al. 2010 and CIFAR-10 (Krizhevsky et al. 2009) datasets for comparison previous methods. For LS, we also use Fashion-MNIST.. These classification tasks are recast as regression problems by using mean-centered one-hot labels during training and by making class predictions via assigning the class index with maximal predicted value during testing. All our kernel-based experiments use the Neural Tangents library (Novak et al.) (020), built on top of JAX (Bradbury al. 2018). In what follows, we use FCm and Convm to denote depth m fully-connected or fully-convolutions network. Whether we mean finite-width neural network or else the corresponding neural tangent kernel (NTK) will be understood from the context. We will sometimes also use the neural network Gaussian process (NNGP) kernel associated to neural network in various places. By default, a neural kernel refers to NTK unless otherwise stated. RBF denotes the radial-basis function kemnl.. Myrtle-V architecture follows that of Shaanaar al. (2020), where an N -llyyer neural network consisting of a simple combination of N convolutional layers along with (2, 2) average pooling layers are wnter-weaved to reduce internal patch-size.
We would have used deeper and more diverse architectures for KIP, but computational limits, which will be overcome in future work, placed restrictions, see the Experiment Details in Section
4.1 SINGLE KERNEL RESULTS
We apply KTP to learn support datasets of various sizes for MNIST and CIFAR-10. The objective is to distill the entire training dataset down datasets of various fixed, smaller sizes to achieve high compression ratio. We present these results against various baselines in Tables and These comparisons occur cross- coostarchitecturally, but aside from Myrtle LS results, all our results involve the simplest of kernels (RBF or FC1), whereas prior art use deeper architectures (LeNet, AlexNet, ConvNet).
We obtain state the art results for KRR on MNIST and CIFAR-10, for the RBF and FC1 kernels, both in terms of accuracy and number of images required, see Tables [ and 2 In particular, method produces datasets such that RBF and FC1 kemnlss fit to them rival the performance of deep convolutional neural networks on MNIST (exceeding 99.2%). By comparing Tables and A2] we see that, e.g. 10 or 100 KIP images for RBF and FC1 perform on par with tens or hundreds times more natural images, resulting
compression ratio of one or two orders of magnitude.
For neural network trainings, for CIFAR-10, the second group of rows in Table 2 shows that FCI trained on KIP images outperform prior art, all of which have deeper, more expressive architectures. On MNIST, we still outperform some prior baselines with deeper architectures. This, along with the state of the art KRR results, suggests that KIP, when scaled up to deeper architectures, should continue to yield strong neural network performance.
For LS, we use mix of NNGP kernel and NTK kernels associated to FC1, Myrtle-5, Myrtle- 10 to learn labels on various subsets of MNTST, Fashion-MNIST and CIFAR-10. Our results comprise the bottom third of Tables [ and and and Figure 2] As Figure shows, the more targets are used, the better the performance. When all possible targets are used, get optimal compression ratio of roughly one order of magnitude at intermediate support sizes.
4.2 KERNEL TO KERNEL RESULTS
Here we investigate robustness of KIF and LS learned datasets when there is variation in the kernels used for training and testing. We draw kernels coming from FC and Conv layers of depths 1-3, since such components form the basic building blocks of neural networks. Figure AT shows that KTP- datasets trained with random sampling of all six kernels do better on average than KIP -datasets trained using individual kernels.
*For FCI, NNGP and NTK perform comparably whereas for Myrtle, NNGP outperforms NTK.

---

Myrte-1o Label Solve (CIFAR-11)
FC1 (NNGPP Label So (CIFAA9-11))
Myrted, (NNGP)) Lubel Soiee (Fashion MNIST)
Myttlet
(MNE81)
0.5
Accuracy
Toa Accurcy
0.-
0.2
0.2
10
105
10
10"
10'
105
12
10
10P
127
10
10"
Support Set Size
Support Get Size
Support Set Size
Support Set Size
Figure 2: IS performance for Myrtle-(5/10) and FC on CIAAR-IIFaahiooNNNIIYYANSS Results computed over independent samples per support set size.
Table I: MNIST: KIP and LS vs baselines. Comparing KRR (kernel ridge-regression) and NN (neural
network) algorithms using various architectures and dataset distillation methods on datasets of varying sizes (10 to 10K).
Alg.
Arch., Method
100
500
5000
10000
KRR
RBF, KIP
89.60=0.09
97.31=0.09
98.29-10.06
98.70:10.04
98.7440.04
KRR
RBF, KIP (a (a++1) 1)²
90.63:0.27
97.84=0.06
98.85:10.04
99.31:10.04
99.34:10.03
KRR
FCI, KIP
89.30=0.01
96.64=0.08
97.64=0.06
98.52:00.04
98.59=0.055
KRR
FC1, KIP (a+
85.46=0.04
97.15=0.11
98.36=0008
99.18+0.04
99.26=10.03
NN
FC1, KIP2
86.49-10.40
88.96:10.37
95.70+10.09
97.97+10.07
NN
ConvNet, DC
91.7=00.5
97.410.2
NN
LeNet, DC
93.9
NN
LeNet, SLDD
82.7+2.8
NN
LeNet, DD
79.5+8.1
KRR
FCI, LS
61.0::0.28
87.210.71
94,410016
97.5+10.06
97,9-L000
KRR
Myrtle-5 NNGP, LS
70.24=1.59
95.44=0.117
98.32=0091
99.17#0.01
99.33
KRR
Myrtle-5, LS
68.50=2.52
95.53+0.22
98.17:0.07
99.05+0.06
99.22+0.02
NN
LeNet, L.D
64.57+2.67
87.85+0043
94.75++0.29
(a I) denotes K trained with augmentations and learning of lahels
KIP images are trained using the same kernel (FC1) corresponding evaluation neural network. Likewise for
KRR, the train and test kernels coincide.
ConvNet is neural network consisting of convolutional blocks, where block consists of convolution, instance
normalization, and a (2,2) average pooling, See/Zhao al. (2020).
DC Zhao et 2020), LD (Bohdal et al. 2020), SLDD (Sucholutsky Schonlau 2019 DD Wang 2018
For L.S transferability between FCI and Myrtle- 10 kernels on CIFAR-10 is highly robust, see Fig- label solve using FC1 and train Myrtle-10 using those labels and vice versa. There is only negligible difference in performance in nearly all instances between data with transferred learned labels and with natural labels.
A2
Namely,
4.3 KERNEL TO NEURAL. NETWORKS RESULTS
Significantly, KIP -eaamed datasets, even with heavy corruption, transfer remarkably well to the training of neural networks. Here, corruption refers to setting random p fraction of the pixels of each image uniform noise between -1 and (for KIP, this is implemented via KIP [5] The deterioriation in test accuracy for KIP -images is limited as a function of the corruption fraction, especially when compared to natural images, and moreover, corrupted KIP -images typically out- perform uncorrupted natural images. We verify these conclusions along the following dimensions:
Robustness to dataset size: We perform sets of experiments.
(i) First, we consider small KTP datasets
(10, 100, 200 images) optimized using multiple kernels A6 We find that our in-distribution transfer (the downstream neural network has its neural kernel included among the kernels sampled by KIP) performs re-
(FC1-3, Convl-2), see Tables A5
Our images preprocessed so to he mean-centered and unit-variance per pixel. This choice of corrup- tion, which occurs post-processing, is therefore meant to (approximately) match the natural pixel distribution.

---

Table 2: CIFAR-10: KIP and LS baselines. Comparing KRR (kernel ridge-regression) and NN (neural
network) algorithms using various architectures and dataset distillation methods on datasets of various sizes (10 to 10K). Notation same as in Table
Alg.
Arch., Method
10
100
500
5000
10000
KRR
RBF, KIP
39.9=0.9
49.310.33
51.2:10.8
KRR
RBF, KIP (a+
40.3
53.8+0.33
60.1
65.621.2
66.3:10.2
KRR
FC1, KIP
39.3+1.6
49.1+1.1
52.1+0.8
54.9:10.5 54.5
KRR
FC1, KIP (a+ 1)
40.
53.1
58.6+0.4
63.8+0.3
64.6+0.2
NN
FCI, KIP
36.2:0011
45.7:10.3
46.910.2
50.1
51.7200.4
NN
ConvNet, DC
28.3+0.5
44.9
NN
AlexNet, DC
39.1#1.2
NN
AlexNet, SLDD
39.8
NN
AlexNet, DD
36.8+
KRR
FCI NNGP, LS
27.5+0.3
40.1
46.420.4
53.5
50.
KRR
Myrtle- 10 NNGP, LS ZCA*
31.7+-0.2
0..0
69.8
80.2+
82.3++.11
KRR
Myrtle-10, 10, LS
28.8++0.4 38.33+0044 25.69
45.8+0.7
58.0+0.3
69.6+0.2
72.0+0.2
NN
AlexNet, LD
43.16:10.47
We apply regularized ZCA whitening instead of standard preprocessing images, see Appendix details.
further
markably well, with both uncorrupted and corrupted KIP images beating the uncorrupted natural images of corresponding size. Out of distribution networks (LeNet (LeCun et al. 1998) and Wide Resnet (Zagoruyko & Komodakis, 2016)) have less transferability: the uncorrupted images still out- perform natural images, and corrupted KIP images still outperform corrupted natural images, but corrupted KIP images no longer outperform uncorrupted natural images.
(ii) We consider larger KIP datasets (IK, 5K, 10K images) optimized using single FCI kernel for training of a corresponding FCI neural network, where the KIP training uses augmentations (with and without label learning), see Tables A7 A10 and Figure A3 We find, before, KIP images outperform natural images by an impressive margin: for instance, on CIFAR-10, 10K KIP -learned images with 90% corruption achieves 49.9% test accuracy, exceeding 10K natural images with no corruption (acc: 45.5%) and 90% corruption (ace: 33.8%). Interestingly enough, sometimes higher corruption leads to better test performance (this occurs for CIFAR-10 10 with both natural and KIP -learned images), a phenomenon to be explored in future work. We also find that KIP with label-learning often tends to harm performance, perhaps because the labels overfitting to KRR.
entropy loss for
Robustness to hy perppaaraeter::: For CIFAR-10, we took 100 images, both clean and 90% cor- rupted, and trained networks on a wide variety of hyperparameters for various neural architectures. We considered both neural networks whose corresponding neural kernels were sampled during KIP- training those that were not. We found that in both cases, the KIP -learned images almost always outperform 100 random natural images, with the optimal set of hyperparameters yielding margin close to that predicted from the KRR setting, see Figure This suggests that KIP -learned images can be useful accelerating hyperparameter search.
5 RELATED WORK
classical approach compressing datasets is via subset selection, or some approxi- mation thereof. One notable work is Borsos et al. (2020), utilizing KRR for dataset subsclection. For an overview notions coresets based on pointwise approximatation of datasets, see Phillips 2016).
Coresets:
Neural network approaches to dataset distillation: Maclaurin et al. (2015); Lorraine et al. (2020) approach dataset distillation through learning the input images from large-scale gradient-based meta-
learning syper-parameters. Properties of distilled input data was first analyzed in Wang et al.
(018). The works Sucholutsky & Schonlau (2019): Bohdal et al, (2020) build upon Wang et al.
8

---

Jin Dlenibution)
(hs Datr bullon)
(Ouboo Distribtion
KIP Tout Aocuraoy
0.4
MSE XENT
0.4
0.1
02 Orig lisst Acouracy
Original Test Aocuracy
Original Fisst Acouracy
Original Test Accuracy
aoss Comaptio strbutinn
Convé Comuption
Conié Comppton (Out Distributon)
50% Comuption jout-ol stributioon
Dist
K0P Ted Pooaedy
0.3
MSE XENT
02
0.2
0.4
0.2 Compled irput Aecuuc
0.4
0.2 Compled Input TIee Acturay
0.4
Comples apst Ted Acsuncy
Compted ippa Aecur
Figure 3: KTP learned images transfers well finite neural networks. Test accuracy on CIFAR- 10 comparing natural images (X-axis) and KIP -learned images (y-axis). Each scatter point cor- responds to varying hyperparameters for training (e.g. learning rate). Top row are clean images, bottom row are 90% corrupted images. KIP images were trained using FC1-3, Convl 1-2 kernels.
2018 by distilling labels. More recently, Zhao al. (2020) proposes condensing training set by gradient matching condition and shows improvement over Wang et al. (2018).
Inducing points: Our approach has as antecedant the inducing point method for Gaussian Pro- cesses (Snelson & Ghahramani 2006;; Titsias) (209).. However, whereas the latter requires prob- abilistic framework that optimizes for marginal likelihood, in our method we only need to consider minimizing mean-square loss on validation data.
Low-rank kernel approximations: Unlike common low-rank approximation methods (Williams) & Seeger 2001; Drincas & Mahoney 2005), obtain not only low-rank support-support kernel matrix with KIP, but also a low-rank target-support kernel matrix. Note that the resulting matrices obtained from KIP need not approximate the original support-support target-support matrices since KIP only optimizes for the loss function.
Neural network kernels: Our work is motivated by the exact correspondence between infinitely- wide neural networks and kernel methods (Neal) 1994; Lee et al. 2018 Matthews et al., 2018 Jacot al. 2018 Novak al. [019] Garriga-Alon
al. 2019: Arora al.) (0T9a). These correspondences allow us to view both Bayesian inference and gradient descent training of wide neural networks with squared loss as yielding Gaussian process or kernel ridge regression with neural kernels.
Distacc--Bssd Encryption: related approach corrupting datasets involves encrypting indi- vidual images via sign corruption (Huang et al. (2020)).
6 CONCLUSION
We introduced novel algorithms KIP and LS for the meta-learning of datasets. We obtained va- riety of compressed and corrupted datasets, achieving state of the art results for KRR and neural network dataset distillation methods. This was achieved even using the simplest of kernels and neu- ral networks (shallow fully-comnected networks and purely-convolutional networks without pool- ing), which notwithstanding their limited expressiveness, outperform most baselines that use deeper architectures. Follow-up work will involve scaling up KIP to deeper architectures with pooling (achievable with multi-device training) for which we expect to obtain even more highly performant datasets, both in terms of overall accuracy and architectural flexibility. Finally, obtained highly corrupt datasets whose performance match or exceed natural images, which when developed at scale, could lead to practical applications for privacy-preserving machine learning.

---

ACKNOWLEDGMENTS
We would like to thank Dumitru Erhan, Yang Li, Hossein Mobahi, Jeffrey Pennington, Si Si, Jascha Sohl-Dickstein, and Lechao Xiao for helpful discussions and references.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Con- ference Computer and Communications Security, Oct 2016. doi: 10.1145/2976749.29788333
URL
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems, pp. $141-8150 Curran Associates, Inc., 2019a.
Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. arXiv preprint arXiv:1910.01663 2019b.
Ondrej Bohdal, Yongxin Yang, and Timothy Hospedales. Flexible dataset distillation: Learn labels instead of images. arXiv preprint arXiv:2006.08557, 2020.
Antoine Bordes, Seyda Ertekin, Jason Weston, and Léon Bottou. Fast kernel classifiers with online and active learning. Journal of Machine Learning Research, 6(Sep):1579-1619 2005.
Zalán Borsos, Mojmír Mutn3, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. arXiv preprint arXiv:2006.03880 2020.
James Bradbury. Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, and Skye Wanderman-Milne. JAX: composable transformations of Python+NummP programs, 2018. URL htRphhtp://gitt
com c hoom/goooll/aax
Petros Drincas and Michael W Mahoney. On the nyström method for approximating a gram matrix for improved kernel-based learning. journal of machine learning research, 6(De)):2153-2115, 2005.
Adrià Garriga-Alonso, Laurence Aitchison, and Carl Edward Rasmussen. Deep convolutional net- works as shallow gaussian processes. In International Conference on Learning Representations, 2019.
T. N. F. Greville. Note on the generalized inverse of a matrix product. SIAM Review, 8(4::118-521, 1966. ISSN 00361445, URL http://////w. http///wwwjttrr.ooooooooo. /ttg///al///////////to
Trevor Hastic, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation, 2019.
Yangsibo Huang, Zhao Song. Kai Li, and Sanjeev Arora. Instahide: Instance-hiding schemes for private distributed learning, 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. In Advances in Neural Information Processing Systems, 2018.
Ibrahim Jubran, Alaa Maalouf, and Dan Feldman. Introduction to coresets: Accurate coresets. arXiv preprint arXiv:1910.08709 2019.
T. Kato. Perturbation Theory of Linear Operators. Springer- Verlag, Berlin, edition, 1976.
Mahmut Kaya and H.s Bilge. Deep metric learning: A survey. Symmetry, 11:1066, 08 2019, doi: 10.3390/sym1 1091066.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
10

---

Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11)22278-25 1998.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. 2010.
Available: http:://ann.lecue http:/yann.lecun..cm
com/exdd/mnist, http://ww...e...oo////mmdmmsi
Jaehoon Lee, Yasaman Bahri, Roman Novak, Sam Schoenholz, Jeffrey Pennington, and Jascha Sohl- dickstein. Deep neural networks gaussian processes. In International Conference Learning Representations, 2018.
Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, 2019.
Jachoon Lee, Samuel S Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. arXiv preprint arXiv:2007. 2020.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference on Artificial Intelligence and Statistics, pp- 1540-1552. PMLR, 2020.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter optimiza- tion through reversible learning. In International Conference on Machine Learning, pp. 2113- 2122, 2015.
Julien Mairal, Piotr Koniusz, Zaid Harchaoui, and Cordelia Schmid. Convolutional kernel networks. In Advances in Neural Information Processing Systems, 2014.
Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018.
Radford M. Neal. Priors for infinite networks (tech, rep. no. crg-tr-94-1). University of Toronto, 1994.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A. Abo- lafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels gaussian processes. In International Conference on Learning Representations, 2019.
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Diil-Dicksttin, and Samuel S. Schoenholz. Neural tangents: Fast and casy infinite neural networks in python. In International Conference Learning Representations, 2020. URL htLhttt:: //ggtgttte github....... com/
google//eeee Baoggle/neural-tangeee
Jeff M Phillips. Coresets and sketches. arXiv preprint arXiv: 2016.
Vaishaal Shankar, Alex Chengyu Fang, Wenshuo Guo, Sara Fridovich-Keis Ludwig Schmidt, Jonathan Relan-Kelley, and Benjamin Recht. Neural kernels without tangents. In International Conference Machine Learning, 2020.
Sam Shleifer and Eric Prokop. Using small proxy datasets to accelerate hyperparameter search. arXiv preprint arXiv: Nete::996000888 04887, 2019.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learn- ing. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and Garnett (eds.), Advances in Neural Information Processing Systems 30. pp. 4077-4087. Curran Associates, Inc., 2017. URL http::/ nips cc/papez/ 6996 pr96-prrtottppicall-ee
for few wwww-shott-eerrninnne
Edward Snelson and Zoubin Ghahramani. Sparse gaussian processes using pseudo-inputs. Ad- vances neural information processing systems, pp. 1257-1264, 2006.

---

Jascha Sohl-Dickstein, Roman Novak, Samuel S Schoenholz, and Jachoon Lee. On the infinite width limit of neural networks with a standard parameterization. arXiv preprint arXiv:200.00301,, 2020.
Ingo Steinwart. Sparseness of support vector machines. Journal of Machine Learning Research, (Nov):1011-1105, 2003.
Ilia Sucholutsky and Matthiss Schonlau. Soft-label dataset distillation and text dataset distillation. arXiv preprint arXiv:1910.0255// 2019.
Michalis Titsias. Variational learning of inducing variables in sparse gaussian processes. In Artificial Intelligence and Statisfics, pp. 567-574, 2009.
Oriol Vinyals, Charles Blundell, Timothy P. Lillicrap, Koray Kavukcuoglu, and Daan Wierstra.
Matching networks for one shot learning. CoRR, abs/1606.04080, 2016. htttp://aaaa::
org/abs/160s 04080
Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei Efros. Dataset distillation. arXiv preprint arXiv: 18/ 1. 10959, 2018.
Christopher KI Williams and Matthias Seeger. Using the nyström method speed up kernel ma- chines. In Advances in neural information processing systems, pp. 682-688, 2001.
Sergey Zagonuyko and Nikos Komodakis. Wide residual networks. CoRR, abs/ 1605.0101011 0005600746,,. 2016. URL /oRK:/ttpp//aaxx...rr/////////// 07146
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. arXiv preprint arX1v:2006.05929, 2020.
12

---

A REMARKS ON DEFINITION OF E-APPROXIMATION
Here, we provide insights into the formulation of Definition One noticeable feature of our def- inition is that it allows for different algorithms A and À when comparing datasets D and D. On the one hand, such flexibility is required, since for instance, a mere preprocessing of the dataset (e.g. rescaling it), should be regarded as producing an equivalent (0-approximate) dataset. Yet such a rescaling may affect the hyperparameters needed to train an equivalent model (e.g. the learning rate). Thus, one must allow the relevant hyperparameters of an algorithm to vary when the datasets are also varying. On the other hand, it would be impossible to compare two datasets meaningfully the learned algorithms used to train them differ too significantly. For instance, if D much larger dataset than D. but is much less expressive algorithm than Á, then the two datasets may be c-approximations of each other, but it would be strange to compare D and D in this way. Thus, we treat the notion of what class of algorithms to consider informally, and leave its specification as a practical matter for each use case. In practice, the pair of algorithms we use to compare datasets should be drawn from family in which some reasonable range of hyperparameters are varied, the ones typically tuned when learning on an unknown dataset. The main case for us with differing A and À is when we compare neural network training alongside kernel rigge-regression.
Another key feature of our definition is that datapoints of e-approximating dataset must have the same shape as those of the original dataset. This makes our notion of an e-approximate dataset more restrictive than returning specialized set of extracted features from some initial dataset.
Analogues of our a-approximation definition have been formulated in the unsupervised setting, e.g. in the setting of clustering data (Phillips 2016 Jubran et al., 2019).
Finally, note that the loss function é used for comparing datasets does not have to coincide with any loss functions optimized in the learning algorithms and Á. Indeed, for kernel ridge-regression, training mimmmizes mean square loss while l can be 0-1 loss.
B TUNING KIP
Sampling: When optimizing for KRR performance with support dataset size N, it is best to learn a support set D of size and sample this entire set during KIP training. It is our observation that subsets of size M < N of D will not perform as well as optimizing directly for a size M dataset through KIP. Conversely, sampling subsets of size M from a support dataset of size N during KTP will not lead to a dataset that does as well as optimizing for all N points. This is sensible: optimizing for small support size requires resourceful learning of coarse features at the cost of learning fine-grained features from many support datapoints. Conversely, optimizing a large support set means the learned support set has leveraged higher-order information, which will degrade when restricted to smaller subsets.
For sampling from the target set, which we always do in a class-balanced way, found larger batch sizes typically perform better on the test set if the train and test kernels agree. If the train and test kernels differ. then smaller batch sizes lead to less overfitting to the train kernel.
Initialization: We tried two sets of initializations. The first ('image init") initializes (X,: Vs) to be subset of (X,, M1). The second ("noise init") initializes X, with uniform noise and ys with mean-centered, one-hot labels (in class-balanced way). We found image initialization to perform better.
Regularization: The regularization parameter À in 7 can be replaced with LA Lr(Kx,xx where n is the number of datapoints in X,. This makes the Toss function invariant with respect to rescaling of the kernel function K and also normalizes the regularization with respect to support size. In practice, we use this scale-invariant regularization with À = 10
Remarkably, KIP converges very quickly in all experimental set- tings we tried. After only on the order of a hundred iterations, independently of the support size, kernel, and corruption factor, the learned support set has already undergone the majority of its learn- ing (test accuracy is within more than 90% of the final test accuracy). For the platforms available to us, using single V100 GPU, hundred training steps for the experiments ran involving
Number of Training Iterations:

---

target batch sizes that were few thousand takes the order of about 10 minutes. When we add augmentations to our targets, performance continues to improve slowly over time before flattening out after several thousands of iterations.
C THEORETICAL RESULTS
Here, we analyze convergence properties of KTP in returning an e-approximate dataset. In what follows, we refer to gradient-descent KIP as the case when we sample from the entire support and train datasets for each update step KIP. We also assume that the distribution P used to evaluate e-approximation is supported on inputs x E IRd with | I 1 (merely to provide a convenient normalization when evaluating loss regression algorithms).
For the case of a linear kernel, we prove the below convergence theorem: Theorem 1. Let D (X,, Wt) Ra x IR be an arbitrary dataset. Let wx RdxC be the coefficients obtained from training À ridge-regression (X-RR) on (Xt, mt), as given by (4)
1. For generia initial conditions for the support set (X Vs) RR Rx and suf- ficiently small X > O, gradient descent KIP with target dataset D converges to dataset D.
2. The dataset D is strong e-approximation to D with respect to algorithms (A-RR, O-RR) and loss function equal to mean-square loss, where
6 --
(A1)
and in E TRdxC are the coefficients of the linear classifier obtained from training X-RR on D. If the size of D is at least C, then in is also least squares classifier for D. In particular, if D has unique least squares classifier, then e = 0.
Proof. We discuss the case where X, is optimized, with the case where both (X.. are optimized proceeding similarly. In this case, by genericity, we can assume y, + O else the learning dynamics is trivial. Furthermore, to simplify notation for the time being, assume the dimensionality of the label space C 1 without loss of generality. First, we establish convergence. For a linear kernel, we can write our loss function
L(Xs) __11 -llv XXXX + 1y.12
1
(A2)
defined on the space Ml,, x of d matrices. It is the pullback of the loss function
Lg n, ( / llue X,0 + Rdxn.
(A3)
under the map X, (X,)) XX(x,X? AT)-1 The function A3 is quadratic in & and all its local minima are global minima given by an affine subspace M Mixxn, Moreover, each point of A has a stable manifold of maximal dimension equal to the codimension of M. Thus, the functional L has global minima given by the inverse image क~ (M) (which will be nonempty for sufficiently small A).
Next, we claim that given fixed initial (Xe, Vo), then for sufficiently small X, gradient-flow of (22 starting from (Xs. Us) cannot converge to a non-global local minima. We proceed as follows. If X -UVVTT is singular value decomposition of X, with Σ a n, n, diagional matrix of singular values (and any additional zeros for padding), then ((X) Vo(EUT where ((E) denotes the diagonal matrix with the map
b: 22 - R220
(A4)
/
(1) n - X
(A5)
'A set can be generic by either being open and dense or else having probability one with respect to some measure absolutely continuous with respect to Lehesgue measure. In our particular case, generic refers to the complement of submanifold of codimension least one.
2

---

applied to each singular value of Σ. The singular value decomposition depends analytically on X (ato (1976)). Given that ø R + R is a local diffeomorphism away from its maximum value at j 14 == X1/2, it follows that 4x M xd -> Maxn. locally surjective, i.e. for every X, there exists a neighborhood U of X such that & (2(2)) contains neighborhood of Φ (X). Thus, away from the locus of matrices in Mln, that have a singular value equaling μ², the function (A2) cannot have any non-global local minima, since the same would have to be true for (A3). We are left to consider those matrices with some singular values equaling μ²" Note that as X - 0, we have <(x") + oc. On the other hand, for any initial choice of X.. the matrices @x (X.) have uniformly bounded singular values as a function of A. Moreover, as X, = (() evolves, ||xxxXX (())ll never ||sell
needs to be larger than some large constant times || (X,, + 5 1*1l,, I| where μ4 is the smallest positive singular value of Xz. Consequently, Xt()) never visits a matrix with singular value μ² for sufficiently small À > 0; in particular, never have to worry about convergence to non-global local minimum.
Thus, generic gradient trajectory 7 of L will be such that 4 o is gradient-like trajectory for Lggxn, that converges to .M. We have to show that y itself converges. It is convenient to extend ø to map defined on the one-point compactification [0, oc] J R200 so to make ó two-to-one map away from μ², Applying this compactification to every singular value, we obtain compactification
M Xd M of M and we can naturally extend 4 such a compactification. We have that y
converges to element of M (M) C M" ". where we need the compactification to account for the fact that when 4 o 7 converges to a matrix that has a zero singular value, y may have one of its singular values growing to infinity. Let Mo denote the subset of . with singular value. Then y converges to an element of MI. xd precisely when y does not converge to an element of Mxx =- Φ (Mo) xd, MM.xd). However, Mo M has codimension one and hence does Ma C Φ (Moo) Thus, the stable set to Ma has codimension one in M xd and hence its complement is nongeneric. Hence, we have generic convergence of a gradient trajectory of L to a (finite) solution. This establishes the convergence result of Part 1.
For Part 2, the first statement is a general one: the difference of any two linear models, when evaluated on P, can be pointwise bounded by the spectral norm of the difference of the model coefficient matrices. Thus Ó is strong e-approximation to D with respect (A-RR, O-RR) where e is given by (T.). For the second statement, observe that L is also the pullback of the loss function
1 LRaxe (w) 2 llye X
WE R
(A6)
under the map X, + wxX)) = (Xx))) ,)yy.- The function L is quadratic in w and has a unique minimum value, with the space of global minima being an affine subspace W* of IR given by the least squares classifiers for the dataset (X,, yt). Thus, the global minima of L are the preimage of W under the map w( (X.). For generic initial (X,, ys), we have ys E R. is full rank. This
implies, for n, 2 C, that the range of all possible w (X,) for varying X, is all of RdxC so that the
minima of (A6) and (A3) coincide. This implies the final parts of Part 2.
We also have the following result about e-approximation using the label solve algorithm:
Theorem 2. Lei D = (X vt) E Ra x TRx be an arbitrary dataset. Let wx E RRxx be the coefficients obtained from training À ridge-regression (X-RR) on (Xt, as given by 4 Let X. E Re, xd be an arbitrary initial support set and let X Z O. Define Vt = (A) via (8)
Then (X.. Vt) yields a strong E(A) apprrxxoxxnntoo of (Xe: Ve) with respect to algorithms (X-RR, O-RR) and mean- seean-square loss, where
<(A) = 2 (l=((A)= - woll2
1
(A7)
2
and w² (X) is the solution
W = im (xx(x)) ker (X=(A(())) + Rdx()
w" (A) argmin 11 12
(A8)
7A vector field v is gradient-like for function f if grad(f) 2 0 everywhere.
3

---

Moreover, for X
O. if rannk(X))) ran d, then w" (A) = wy. This implies y Xg wo, i.e. V. coincides with the predictions of the O-RR classifier trained on (X,, X1,y1 y1) evaluated on X..
Proof. By definition, V/ is the minimizer of
L(ys) - live X, (X.
2
with minimum norm. This implies v2 E ker xx,) and that w" (A) = (X(x)) satisfies
A8
At the same time, w² (A) *x are the coefficients of the X-RR classifier trained on V.). If rank(X.)) rank(X,) = d, then (X(),) is surjective and X, is injective, in which
case
(0) Do(X))
@o(Xx) P (X, Po (X.)))
xo,
wp.
The results follow.
For general kernels, we make the following simple observation concerning the optimal output of KIP.
Theorem 3. Fix target dataset (Xt, yt). Consider the family of all subspaces S of R given by fim Kx.x, : X. E 3,, i.e. all possible column spaces of Xx.x, Then the infinum of the loss over all possible (x). equal inf || ys 1|2 where Ug is orthogonal projection onto the orthogonal complement of S (acting identically on each label component).
Proof. Since y. is trainable, (Kx,x. + + is an arbitrary vector in XC Thus, minimizing the training objective corresponds to maximizing the range of the linear map K Kx, X,xx, over all possible X.. The result follows.
D EXPERIMENT DETAILS
In all KTP trainings, we used the Adam optimizer. All our labels are mean-centered 1-hot labels. We used learning rates 0.01 and 0.04 for the MNIST and CIFAR-IO datasets, respectively. When sampling target batches, we always do so in class-balanced way. When augmenting data, we used the ImageGenerator class from Keras, which enables us to add horizontal flips, height/width shift, rotatations (up to 10 degrees), and channel shift (for CIFAR- 10). All datasets are preprocessed using channel-wise standardization (i.e. mean subtraction and division by standard-devvaaioon) For neural (tangent) kernels, always use weight and bias variance of 2 and of 10-1 respectively, For both neural kernels and neural networks, we always use ReLU activation. Convolutional layers all use (3, 3) filter with stride I and same padding.
Compute Limitations: Our neural kernel computations, implemented using Neural Tangents li- braray (Nvvk al. (2220) such that computation scales (i) linearly with depth; (ii) quadratically in the number of pixels for convolutional kernels; (iii) quartically in the number of pixels for pooling layers. Such costs mean that, using single V100 GPU with 16GB RAM, we were (i) only able to sample shallow kernels; (ii) for convolutional kernels, limited to small support sets and small target batch sizes; (iii) unable to use pooling learning more than just a few images. Scaling up KTP to deeper, more expensive architectures, achievable using multi-device training, will be the subject of future exploration.
Kernel Purameterization: Neural tangent kernels, or more precisely each neural network layer of such kernels, as implemented in Novak et al. (2020) can be parameterized in either the "NTK" pa- rameterization "standard" parameterization Sohl-Dickstein the width corresponding finite-width neural network while the former does not. Our exper- iments mix both these parameterizations for variety. However, because
al. (2020). The latter depends on
scale-invariant
4

---

regularization for KRR (Section B). the choice of parameterization has a limited effect compared to other more significant hyperparameters (e.g. the support dataset size, learning rate, etc.
Single kernel results: (Tables and 2 For FC, we used kernels with NTK parametrization. For RBF,
our rbf kernel is given by
rbf .2) exp(->lla;
/2ll2/d)
(A9)
where d is the dimension of the inputs and = 1. We found that treating as a learnable parameter during KIP had mixed results and keep it fixed for simplicity.
For MNIST, we found target batch size equal to 6K sufficient. For CIFAR-10, helped to sample the entire training dataset of 50K images per step (hence, along with sampling the full support set, we are doing full gradient descent training). When support dataset size is small or if augmentations are employed, there is no overfitting (i.e. the train and test loss/accuracy stay positively correlated). If the support dataset size is large (5K or larger), sometimes there is overfitting when the target batch size is too large (e.g. for the RBF kernel on CIFARIO, which is why we exclude in Table the entries for 5K and 10K). We could have used validation dataset for a stopping criterion, but that would have required reducing the target dataset from the entire training dataset.
We train KIP for 10-20k iterations and took 5 random subsets of images for initializations. For each such training, we took 5 checkpoints with lowest train and loss and computed the test accuracy. This gives 25 evaluations, for which we can compute the mean and standard deviation for our test accuracy numbers in Tables [nd
For transfering of KIP images, both to other kernels and to neural networks, we found it useful to use smaller target batch sizes (either several hundred or several thousand), else the images overfit to their source kernel. For random sampling of kernels used in Figure Al and producing datasets for training of neural networks, we used FC kernels with width 1024 and Conv kernels with width 128, all with standard parametrization.
Kernel transfer results:
Neural network results: Neural network trainings on natural data with mean-square loss use mean- centered one-hot labels for consistency with KIP trainings. For cross entropy loss, one-hot labels. For neural network trainings on KIP -learned images with label learning, we transfer over the labels directly (as with the images), whatever they may be.
For neural network transfer experiments occurring in Table I Table 2 Figure Table A5 and Table A6 we did the following. First, the images were learned using kernels FC1-3, Conv 1-2. Second, we trained for a few hundred iterations, after which optimal test performance was achieved. On MNIST images, we trained the networks with constant learning rate and Adam optimizer with cross entropy loss. Learning rate was tuned over small grid search space. For the FC kernels and networks, we use width of 1024. On CIFAR- 10 images, we trained the networks with constant learning rate, momen- tum optimizer with momentum 0.9. Learning rate, L2 regularization, parameterization (standard vs NTK) and loss type (mean square, softmax-crov crommaxxcrrss-ettoyy)) was tuned over small grid search space. Vanilla networks use constant width at each layer: for FC we use width of 1024, for Conv2 use 512 channels, and for Conv8 we use 128 channels. No pooling layers are used except for the WideResNet architecture, where we follow the original architecture of Zagoruyko & Komodakis 2016) except that our batch normalization layer is stateless (i.e. no exponential moving average of batch statistics are recorded).
we did the following. Our KIP -leanned images were trained using only an FCI kernel. The neural network FCI has an in- creased width 4096, which helps with the larger number of images. We used learning rate 4 x 10-4 and the Adam optimizer. The KIP learned images with only augmentations used target batch size equal to half the training dataset size and were trained for 10k iterations, since the use of augmenta- tions allows for continued gains after longer training. The KIP learned images with augmentations
For neural network transfer experiments in Figure A3 Tables A7
$ our final readout layers use the fixed NTK parameterization and all our statements about which pa- rameterization we are using should be interpreted accordingly. This has no effect on the training of our neural networks while for kernel results, this affects the recursive formula for the NTK at the final layer if using stan- dard parameterization (by the changing the relative scales of the terms involved). Since the train/test kernels are consistently parameterized and can adapt to the scale of the kemne,, the difference hetween our hybrid parameterization and fully standard parameterization has a limited affect.
9On MNIST it led very slight improvement. For CIFAR10 10, for small support sets, the effect was small improvement on the set, whereas for large support sets, we got worse performance.
5

---

Table Al: Accuracy on random subsets of MNIST. Stan- dard deviations over 20 resamplings.
# Images
Kernel
Linear
RBF
FC1
10
44.613.7
45.3+3.9
45.8+3.9
51.9+3.11
54.6+2299
54.7+-2.8
40
59.4+22.4
66.9++2.0
66.0+1199
80
62.6+:2.7
75.6++1.6
74.3+117
160
62.24:2.1
82.7+:14
81.1=1.6
320
52.3+119
88.140.8
86.9-1.9
640
11.9=1.4
91.8=0.5
91.1=0.5
1280
71.0=0.9
94.2.10.3
93.6=1033
2560
79.
95.7+0.2
95.3+002
5000
83.2+0.4
96.8+0.2
96.4+0022
10000
84.9+0.4
97.5++022
97.2++0.2
and label learning used target batch size equal to a tenth of the training dataset size and were trained for 2k iterations (the learned data were observed overfit to the kernel and have less transferability if larger batch size were used or if trainings were carried out longer).
All neural network trainings were run with random initializations to compute mean and standard deviation of test accuracies.
In Table regularized ZCA preprocessing was used for Myrtle- kernel (denoted with ZCA) on CIFAR- 10 dataset. [Shankar et al. 2020) and Lee et al. (2020) noticed that for neural (convolutional) kernels on image classification tasks, regularized ZCA preprocessing can improve performance sig- nificantly compared to standard preprocessing. We follow the prepossessing scheme used in Shankar ct al. 2020), with regularization strength 10-5 without augmentation.
E TABLES AND FIGURES
E. KERNEL BASELINES
We report various baselines of KRR trained natural images. Tables A1 and A2 shows how various kernels vary in performance with respect to random subsets of MNIST and CIFAR-10. Linear denotes a linear kernel, RBF denotes the rbf kernel (A9) with y = 1, and FC1 uses standard parametrization and width 1024. Interestingly enough, we observe non-monotonicity for the linear kernel, owing double descent phenomenon Hastie et al. (2019). We include additional columns for deeper kernel architectures in Table A2
taken from Shankar al. (2020) for reference.
we see that 10 KIP leaared images, for both RBF and FCI, has comparable performance several thousand natural images, thereby achieving a compres- sion ratio over 100. This compression ratio narrows as the support size increases towards the size of the training data.
Comparing Tables [ 2 with Tables AT
A2
Next, Table A3 compares FCI, RBF, and other kernels trained on all of MNIST to FCI and RBF trained on KIP -learned images. We see that our KIP approach, even with 10K images (which fits into memory), leads to RBF and FC1 matching the performance of convolutional kernels on the original 60K images. Table (4 shows state of the art of FC kernels on CIFAR-10. 10. The prior state of the art used kernel ensembling on batches of augmented data in Lee et al. (2020) to obtain test accuracy of 61.5% (32 ensembles each of size 45K images). By distilling augmented images using KIP, we are able to obtain 64.7% test accuracy using only 10K images.
E.2
KIP AND LS TRANSFER ACROSS KERNELS
Figure Al plots how KIP (with only images learned) performs across kernels. There are training scenarios: training individually on FCI, FC2, FC3, Conv Conv2, Conv3 NTK kernels and random sampling from among all six kemels uniformly (Avg All). Datasets of size 10, 100, 200

---

Table A2:
Accuracy on random subsets of CIFAR-10. Standard deviations over 20 re-
samplings.
# Images
Kernel
Linear
RBF
FC1
CNTK
1yrtle10-Gi
10
16.2411.
15.742.1
16.4=18
15.33 + 2.43
19.15 = 1.94
20
17.1+1.6
17.1+1.7
18.0+1.9
18.79 + 2.13
21.65 + 2.97
40
17.8+11.6
19.7+118
20.6+1.8
21.34 + 1.91
27.20 = 1.90
80
18.6
23.0::1.5
23.911..6
25.48 1.91
34.22 = 1.08
160
18.5+114
25.8+:1.4
26.5+114
30.48
1.17
41.89 = 1.34
320
18.14111
29.211.22
29.91111
36.57
+: 0.88
50.06 + 1.06
640
16.8+0.8
32.8+0.9
33.4=0.8
42.63
+ 0.68
57.60 0.48
1280
15.1
35.920.77
36.7=0.6
48.86
+ 0.68
64.40 = 0.48
2560
13.0+0..5
39.1+0.7
40.2+007
5000
17.8+0.4
42.1+0.5
43.7+0066
10000
24.910..6
45.3+0066
47.7=0.6
Conv 14 kernel with global average pooling (Arora et al. Gaussian
2019b
Myrtle10 Myrtee0-Gaussian kernel (Sannarr et al. 2020)
Table A3: Classification performance on MNIST. Our KIP -datasets, to
FCI or RBF kernels, outperform non-convolutional kernels trained on all train- ing images.
Kernel
Method
Accuracy
FC1
Base
98.6
ArcCosine Kernel2
Base
98.8
Gaussian Kernel
Base
98.8
FCI
KIP (a+1); 10K images
99.2
LeNet-5 (LeCun al. 1998)
Base
99.2
RBF
KIP (a+1), 10K images
99.3
Myrtle5 Kernel (Shankar al. 2020)
Base
99.5
CKN (Mairal et al. 2014)
Base
99.6
Base refers training on entire training dataset natural images.
Non RBF/FC numbers taken from (Shankar et al. 2020)
1) denotes KIP with augmentations and label learning during training.
are thereby trained then evaluated by averaging over all of FC1-3, Conv1-3, both with the NTK and NNGP kernels for good measure. Moreover, the FC and Conv train kernel widths (1024 and 128) were swapped at test time (FC width 128 and Conv width 1024), as an additional test of robustness. The average performance is recorded along the y-axis. AvgAll leads overall boost in performance across kernels. Another observation that Conv kernels alone tend to do a bit better, averaged over the kernels considered, than FC kernels alone.
KIP Transfer to the Other Kernels
0.5
Accuracy
0.3
0.4
0.48
0.48
0.39
0:54
0.38
0.38
10
Support Set Size
0.35
100
0.32
200
0.40
0.40
0:41
0.40
0.28
Average
0.1
Avg
FC2
FC3
Conv1
Conv2
Conv3
Figure A1: Studying transfer between kernels.
7

---

Table A4: CIFAR-10 test aceuracy for FC/RBF kernels. Our KIP datasets, fit RBF/FC1,
outperform baselines with many more images. Notation same as in Table A3
Kernel
Method
Accuracy
FC1
Base
57.6
FC3
Ensembling (Lee al. 2020
61.5
FC1
KIP (a+I), 10k images
64.7
RBF
Base
52.7
RBF
KIP (a+I), 10k images
66.3
Mynte-t0-a
careet
target
target
sagen
Text Acauracy
9.4
Haw
New
02
107
16
10"
10
16P
10f
10
10"
10
16 Support Set Size
10f
10"
50"
101
Support Set Size
Support Size
Support Set Size
Support Set Size
Myrde-1100 10: larger.
FG oo Myr de- sarget
FC Myrie-10: 10x largel
PG oo Myrit 10: 208 larpet
FG Myrte 10, SCk sarer
Teat Accuscy
0.4
0.2
101
10F
Support
Support
Support Support
Figure A2: Label Solve transfer between Myrtle-10 and FC for CIFARIO. Top row: LS labels using Myrtle-10 applied to FCI. Bottom row: LS labels using FC1 applied to Myrtle-10. Results averaged over 3 samples per support set size. In all these plots, NNGP kernels were used and Myrtle-10 used regularized ZCA preprocessing.
we plot how LS learned labels using Myrtle-10 kernel transfer the FCI kernel and vice versa. We vary the number of targets and support size. We find remarkable stability across all these dimensions in the sense that while the gains from LS may be kernel-ppecffi, LS -labels do not perform meaningfully different from natural labels when switching the train and evaluation kernels.
In Figure A2
E.3
KIP TRANSFER TO NEURAL NETWORKS AND CORRUPTION EXPERIMENTS
Table A5: KIP transfer to NN NN baselines MNIST. For each group of four experiments, the best number marked boldface, while second number in italics. Corruption refers 90% noise corruption. KIP images used FC1-3, Conv 1-2 kernel during training.
Method
10 uncrpt
10 crpt
100 unerpt
100 crpt
200 uncrpt
200 crpt
FC1, KIP FC1, Natural
1.55
44.95+11.23
86.84+1.65 1..65+1.117
79.73+1.10
89.5
83.3
12.28+1.59
35.00+2..3
45.39+2.25
31.70+1.03
54.20+2.611
LeNet, KIP
59.69
38.25.16.42
87.85
69.45.13.99
91.08
70.52-14.39
LeNet, Natural
48.69.14.10
30.56.14.35
80.22.1..26
59.9910.95
89.03.1..13
62.00.10.94
8

---

Table A6: KIP transfer to NN NN baselines CIFAR-10. Notation as in Table A5
Method
100 uncrpt
100 crpt
FC3, KIP
43.09=0.20
37.71
FC3, Natural
24.48=00.15
18.92:10.61
Conv2. KIP
37.08:1048 03.68-0046
Conv2, Natural
26.23 +0.69
17.10+1.33
WedeResNet, KIP
33.29=11114
23.89 1.30
NideResNet, Natural
27.93=+0775
19.00++1001
Table A7: MNIST. KIP and natural images on FC1. MSE Loss. Test accuracy of image datasets of size IK. 5K, 10K, trained using FCI neural network using mean-square loss. Dataset size, noise corruption percent, and dataset type are varied: natural refers to natural images, KIP refers to KIP learned images with either augmentations only (a) or both augmentations with label learning (a + l). Only FC1 kernel was used for KIP For each KIP row, we place a * next the most corrupt entry whose performance exceeds the corresponding 0% corrupt natural images. For each dataset size, we boldface the best performing entry.
Dataset
0% crpt
50% crpt
75% crpt 90% crpt
Natural 1000
92.8
87.
82.3#0.9
1..
KIP (a) 1000
94.5+10.4
95,9:1011
94.4=1.2
92.0+0.33
KIP (a+I) 1000
9.2
95.9
95.1+003
94.6+11.9*
Natural 5000
96.4110.1
92.8+0.22
88.5+0.5
80.0
KIP (a) 5000
97.0+10.6
97.1
96.310.2
96.61104*
KIP (a+l) 5000
97.6=0.0*
95.8+0.00
94.5+0.4
91.4+
Natural 10000
97.3
93.910.11
90.2.0.11
81.3+11.0
KIP (a) 10000
97.8=0.1*
96.1
95.8+0.2
96.0+0.22
KIP (a+l) 10000
97.9=0.1*
95.8+0.1
94.7+0.2
88.1
Table A8: MNIST. KIP and natural images on FC1. Cross Entropy Loss. Test accuracy of image datasets trained using FCI neural network using cross entropy loss. Notation same as in Table A7
Dataset
0% crpt
50% crpt
75% crpt
90% crpt
Natural 1000
91.3=0.4
86.3+0.3
81.9+#0.5
75.0+1.. 90.9-10.3
KIP (a) 1000
95.9 0.1
95.0+10.1
93.5
Natural 5000
95.8=0.1
91.910.2
87.3+0.33
80.4+0.5
KIP (a) 5000
98.3 0.0
96.8+0.8*
95.5++0.3
95.14-0.2
Natural 10000
96.9-0.1
93.810.1
89,6+0.22
81.3+0.5
KIP (a) 10000
98.8-0.0
97.0+0.0*
95.240..2
94.711..3

---

Table A9: CIFAR-10. KIP and natural images on FC1. MSE Loss. Test accuracy of image datasets trained using FCI neural network using mean-square loss. Notation same as in Table A7
Dataset
0% crpt
50% crpt
75% erpt
90% erpt
Natural 1000
34.1
34.3:0044
31.7.0.5
27.7.0.8 44.3
KIP (a) 1000
48.0110.5
46.71:..
45.7
KIP (a+I) 1000
47.5++..
46.7++.8
44.3+0.4
41.6+0.5*
Natural 5000
41,410..6
41.34:0.4
37.2+1.2
32.510.77
KIP (a) 5000
51.410.4
50.0
48.8
47.5
KIP (a+1) 5000
50.6
48.5+0.9
44.720.6
43.4
Natural 10000
44.5++0.3
43.2+..2
39.5+0.2
34,3+002
KIP (a) 10000
53.3:1..8
50.5+1..3
49,410.2
48.2+0.6*
KIP (a+1) 10000
51.910.4
50.0
46.5+1.0
43.8
Table A10: CIFAR-10. KIP and natural images FC1. Cross Entropy Loss. Test accuracy of image datasets trained using FCI neural network using cross entropy loss. Notation same as in Table A7
Dataset
0% crpt
50% crpt
75% crpt
90% crpt
Natural 1000
35.4:10.3
35.4
31.7+10.9
27.2-10.8
KIP (a) 1000
49.2
47.6+10.4
47.4+0.4
45.0+10.3*
Natural 5000
43.1+00.8
42.0+0.2
38.0+004
31.7++0.6
KIP (a) 5000
44.5++1.0
51.5+
51.0++0.4
48.9+0.4*
Natural 10000
45.3+002
44.8+0..1
40.6+00.3
33.8++0.2
KIP (a) 10000
46.9+t0.4
54.0+H0.3
52.1+0.3
49.9+
10

---

Images Loss)
Images
0.45
0.25
tCSt accuracy
a accuracy
0.90
0.05
1900:natural
0.85
0.80
0.75
0.5
0.75
0.2
05
0.75
55
corruption fraction
corruption fraction
CIFAR 10. KIP vs Natural Images (MSE Loss)
CIFAR-10. KP vs Natural Images (XENT Loss]
0.55
8.55
0.93
0.50
best accuracy
0.15
tost accuracy
0.45
0.40
0.40
0.33
0.35
0.33
0.3
05
0.75
0.9
0.75
0.9
corruption fraction
cornuption fraction
Figure A3: KIP natural images, FCI. Data plotted from Tables A7
A7AI0 A showing natural
images vs. KIP images for FCI neural networks across dataset size, corruption type, dataset type, and loss type. For instance, the upper right figure shows that MNIST using cross entropy loss, Ik KIP + aug learned images with 90% corruption achieves 90.9% test accuracy, comparable to Ik natural images (acc: 91.3%) and far exceeding 1 natural images with 90% corruption (ace: 75.0%). Similarly, the lower right figure shows on CIFAR1O using cross entropy loss, 10k KIP + aug learned images with 90% corruption achieves 49.9%, exceeding 10k natural images (ace: 45.3%) and 10k natural images with 90% corruption (ace: 33.8%).
11

---

F
EXAMPLES OF KIP LEARNED SAMPLES
0
1
2
3
4
5
6
7
8
9
0
3
3
4
5
6
7
3
9 2 9
0
1
2
3
4
5
6
7
8
9
0
2
3
4
5
6
7
8 8
0
/
2
3
4
5
6
7
8
9
0
/
2
3
4
5
6
7
0
/
3
3
4
5
6
7
8
9
O
/
2
3
4
5
6
8 8
9 9 G
/
2
3
4
5
6
7
9
O
2
3
4
5
6
7
O
1
4
5
6
7
8
O
2
3
4
5
6
7
8
0
/
2
3
4
5
6
7
8
9
O
2
3
4
5
6
8
9 9 9
O
1
2
3
5
6
8
9
O
1
2
3
4
3
6
7
8
0
/
Z
4
5
6
7
8
9
0
/
2
3
4
5
6
7
8
/
4
7
9
0
2
3
4
5
6
7
8
9
Figure A4: KIP learned images (left) vs natural MNIST images (right), Samples from 100 leamee images. Top row: 0% corruption. Bottom row: 90% noise corruption.
12

---

040
1rg
1008
Truck
CH1
Figure A5: KIP learned images (left) vs natural CIFAR-10 images (right). Samples from 100 leamned images. Top row: 0% corruption. Bottom row: 90% noise corruption.
13


Reviews:
[{"review_id": "usbVTFub14r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a data-driven approach to choose an informative surrogate sub-dataset,  termed \"a \\epsilon-approximation\", from the original data set. A meta-learning algorithm called Kernel Inducing Points (KIP ) is proposed to obtain such sub-datasets for (Linear) Kernel Ridge Regression (KRR), with the potential to extend to other machine learning algorithms such as neural networks.  Some theoretical results are provided for the KRR with a linear kernel. The empirical performance of the proposed algorithm is evaluated by experiments based on synthetic data and some standard benchmark data sets. \n\nOverall, I think the paper is well written and the proposed method is of potential value to existing literature. \n\nStrengths:\n1. Some theoretical results are provided for the KIP algorithm under the linear KRR setting.\n2. Numerical experiments are carefully designed and appear to be convincing.\n\nWeakness: \n1. The theoretical results are only for Linear KRR. However, this model cannot be used for classification with categorical labels (when the response y is categorical variables). When the classification is involved\n2. The KIP algorithm depends on (1) the choice of the kernel; (2) the choice of Loss function; (3) the choice of tuning parameters for the kernel machine.  If we choose the sub-dataset based on one set of rules and later want to use it for some other purposes, this certainly would cause some problems. How can you address this issue? In other words, how the proposed algorithm can be adapted to obtain a sub-dataset that works for multi-purposes?\n3. Step 5 in Algorithm 1 is not very clear to me. How exactly do you decide to add a batch of data into the support set? based on what threshold/criterion? If one has to evaluate the loss function (4) on all possible subset of size N out of a total sample size n, it will cost about {n \\choose N} number of operations, which is clearly not scalable when n is large.  More details on how to update the support set and the convergence criterion. \n\nOther issues:\n1. There are typos in multiple places such as equations (1) and (3), and in Definition 3. Please proofread carefully.\n2. For the classification problems, it appears that the support vector machine is always the best choice seems it is \"0-approximation\" to the original dataset. Please clarify why and why not.", "extra_scores": {}, "extra_text": {}}, {"review_id": "o6y-1zO9zu", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper proposed an objective based on kernel ridge regression to find a coreset of the training set. The objective first adopts gradient descent to find the coreset in the input space, then generates targets for fake samples in the coreset. I do have many comments on the claims made in this paper, and I hope the authors can answer them. \n\n1. If the goal is to find a minimum number of samples, either original or fake ones, why is the definition of \\epsilon-approx measuring the difference between two expected losses under two distributions respectively, not the difference between two conditional distributions y|x or the joint distributions x,y ? Also, the loss function defined in Eq. 4 clearly minimises the distance between two conditional distributions.\n\nOne might be able to find a coreset of samples that in expectation gives a lower loss value than the original dataset, e.g. denoising, so then measuring the difference between loss values doesn't seem reasonable to me.\n\n2. From a CS theory perspective, the \\epsilon-kernel coreset has a clear definition, and please refer to [1] for details.\n\n3. The two examples given are not precise. \n\nFor example 1, the described situation only holds when the original dataset is linearly separable. When the dataset is not linearly separable, once SVM determines the support vectors on the original dataset, there are samples in between two margins, therefore, a new SVM which is only trained on the samples with support vectors and samples in between will not give you 0-approx by the definition in the paper. \n\nFor example 2, from a statistical learning perspective, the most important part for linear/ridge regression models is the covariance structure derived from X, so then it is true that one can always find a 0-approx dataset, but not of any size. In terms of privacy related issues, regression models rarely have privacy issues as only the X^T X and X^T Y are kept, the information regarding to specific data samples is eliminated due to the inner product. Therefore, the claim that the proposed algorithm can help improve privacy isn't valid,  as linear/ridge regression models already do that.\n\n4. There are many ways of computing inducing points of a given dataset without learning, including random projections[2], frequent directions[3,4], other subsampling methods for Nystroem[5], etc. Many of those methods are well-studied with nice theoretical guarantee in reconstruction. The paper largely ignored those methods in comparison. \n\n5. I don't see how NTK is necessary here. If the authors are interested in testing whether their proposed method work, they can simply start from simulated data in 2D space, and illustrate that the proposed method is indeed able to pick out a high-quality coreset than other methods. Then one can quickly run experiments using pretrained neural networks as feature extractors, as was done in [6]. Given different feature extractors, the selected coresets from individual one of them give us a probe to understand how different neural networks are learnt.\n\n[1] Phillips, J. M. (2016). Coresets and sketches. arXiv preprint arXiv:1601.00617.\n[2] Woodruff, D. P. (2014). Sketching as a tool for numerical linear algebra. arXiv preprint arXiv:1411.4357.\n[3] Ghashami, M., Liberty, E., Phillips, J. M., & Woodruff, D. P. (2016). Frequent directions: Simple and deterministic matrix sketching. SIAM Journal on Computing, 45(5), 1762-1792.\n[4] Shi, B., & Phillips, J. M. (2020). A Deterministic Streaming Sketch for Ridge Regression. arXiv preprint arXiv:2002.02013.\n[5] Kumar, S., Mohri, M., & Talwalkar, A. (2012). Sampling methods for the Nyström method. The Journal of Machine Learning Research, 13(1), 981-1006.\n[6] Tang, S., & de Sa, V. R. (2020). Deep Transfer Learning with Ridge Regression. arXiv preprint arXiv:2006.06791.", "extra_scores": {}, "extra_text": {}}, {"review_id": "foqvnQHx_oK", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper tackles the problem of data compression using kernel induced points learned through deep kernel learning. The main contributions of the paper are :\n\n1 - the formalism of the notion of $\\epsilon$ - approximation of datasets that describes how to rely on one learning algorithm (here KRR) to find the compression set for another one, while keeping the generalization error below $\\epsilon$.\n\n2 - the proposal of the KPI and LS algorithms that find the pseudo-inputs set by leveraging kernel methods and by modifying respectively the inputs and the labels of those pseudo-inputs while monitoring the loss of a regressor using them on the original dataset that is being compressed. Since the starting pseudo-inputs can be corrupted versions of the original dataset, the authors advocate that their method preserves privacy.\n\nOn Quality: The paper is well written and structured though could benefit from more details at many places (e.g. most figures and table  descriptions are lacking or not detailed enough)\n\nOn Clarity: The intention and the contribution of the authors are clear. The main concerning point is linking their work to too many areas instead of focusing on the main scope of the paper which is explicit data compression/distillation. By doing so, the authors confuse the reader especially given that the related work is just after the intro. Another confusing aspect is the usage of terms like meta-learning to describe their algorithm when the algorithm only deals with a single dataset (episodic-looping through one dataset is not meta-learning). Clearer language  and simplification of related work could go along way\n\nOn originality: the epsilon-approximation is an interesting idea that could lead to interesting algorithm developments. I believe the idea is not novel but the authors are the first to formalize it. On the usage of deep kernel learning to do data distillation, the idea has been explored too (Snelson & Ghahramani, 2006) but the authors took it a bit further with the LS algorithm and the privacy preservation aspect.\n\nOn significance: The area is an important research area and there are definitely a few ideas here that others can build upon.\n\nTechnical concerns/questions:\n- In theorem 1: how do you enforce Eq A1? do you make sure that the norm of pseudo-inputs are less than 1 ?\n- in def3: do you need D*_N to define the compression ratio? why not define it using D?\n- In the label solving, after a batch the label solved can fall outside of the possible label set. How do you handle that? or it does not matter?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NBIGQVsBHLI", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Paper present a novel approach for approximate compression of datasets using Kernel Ridge Regression, referred to as KIP.  Paper is well written and technically sounds and experimental results show efficacy of the approach in terms of reducing sample complexity. It also provides an added benefit of corrupting input datasets without much loss test accuracy for privacy preserving use case learning. \n\nThe definition of $\\epsilon$-approximation is introduced in terms bounds on difference between the expected empirical loss for original and compressed dataset which in potentially also bounds generalization error as well. The KIP algorithm iterates over an initial support-set to finally converge over a support dataset that gives similar test performance. The idea of choosing a support set and growing sounds familiar to Nystorm method for kernel approximation provides intuition on  why the approach might work.  Also selection of multiple base kernels also means selection of multiple feature spaces which naturally leads to overall boost in performance. Results on MNIST and CFIR shows the efficacy of these results.\n\nA potential gap in this work is the trade-off between the compressed dataset size N and  test error for a given fixed $\\epsilon$. Is there a way to choose say N, for a given $\\epsilon$ for a given test error performance.  It may be so that we end choosing all points in the original dataset for a given approximation and test error. A characterization of this using generalization bounds would be helpful. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers agree on the value of the contribution and recommend acceptance. A reviewer votes for rejection but the authors have clarified all the major concerns raised by the reviewer. Therefore, I recommend acceptance. 
Decision: Accept (Poster)