Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper tackles the problem of data compression using kernel induced points learned through deep kernel learning. The main contributions of the paper are :

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

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

On 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)

On 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

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

On significance: The area is an important research area and there are definitely a few ideas here that others can build upon.

Technical concerns/questions:
- In theorem 1: how do you enforce Eq A1? do you make sure that the norm of pseudo-inputs are less than 1 ?
- in def3: do you need D*_N to define the compression ratio? why not define it using D?
- 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?

review_title: Official Blind Review #3

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

Overall, I think the paper is well written and the proposed method is of potential value to existing literature. 

Strengths:
1. Some theoretical results are provided for the KIP algorithm under the linear KRR setting.
2. Numerical experiments are carefully designed and appear to be convincing.

Weakness: 
1. 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
2. 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?
3. 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. 

Other issues:
1. There are typos in multiple places such as equations (1) and (3), and in Definition 3. Please proofread carefully.
2. 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.
review_title: Recommendation to Accept

final_score: rating: 7: Good paper, accept
review_content: 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. 

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

A 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. 
review_title: Paper present a novel approach for approximate compression of datasets using Kernel Ridge Regression and experimental results show efficacy of the approach in terms of reducing sample complexity.

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

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

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

2. From a CS theory perspective, the \epsilon-kernel coreset has a clear definition, and please refer to [1] for details.

3. The two examples given are not precise. 

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

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

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

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

[1] Phillips, J. M. (2016). Coresets and sketches. arXiv preprint arXiv:1601.00617.
[2] Woodruff, D. P. (2014). Sketching as a tool for numerical linear algebra. arXiv preprint arXiv:1411.4357.
[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.
[4] Shi, B., & Phillips, J. M. (2020). A Deterministic Streaming Sketch for Ridge Regression. arXiv preprint arXiv:2002.02013.
[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.
[6] Tang, S., & de Sa, V. R. (2020). Deep Transfer Learning with Ridge Regression. arXiv preprint arXiv:2006.06791.
review_title: Interesting yet not efficient

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)