Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: In order to rationalize the existence of non-trivial exponents that can be independent of the specific kernel
used, this paper introduces the Teacher-Student framework for kernels. In this scheme, a Teacher generates data according to a Gaussian random field, and a Student learns them via kernel regression. Theresults quantify how smooth Gaussian data should be to avoid the curse of dimensionality, and indicate that for kernel learning the relevant dimension of the data should be defined in terms of how the distance between nearest data points depends on sample numbers.
The paper is well written, tghe major issue of this paper is the lack of comparison with other previous methods. Therefore, the efficacy of the proposed model can not be well demontrated.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper studies, empirically and theoretically, the learning rates of (shift-invariant) kernel learners in a misspecified setting. In the well-specified setting, the rate of kernel learners is at least $n^{-1/2}$, and in a misspecified setting assuming only Lipschitz targets, the rate is $n^{-1/d}$. Neither seems to match the experimental rate on MNIST and CIFAR-10; this paper proposes a theoretical model that can more-or-less match the experimental rate with essentially-reasonable assumptions.

My main complaint is on the basic setting of the work: in your motivation, you say "it is nowadays part of the lore that there exist kernels whose performance is nearly comparable to deep networks." The main such kernel, though, is the (convolutional) neural tangent kernel of Arora et al. (2019), which unlike the kernels you study here is not shift-invariant, and your theorems do not at all apply to this kernel. This is fine, but should probably be clearer in the description.

A related comment on your main theorem: your target function evaluated at every conceivable point (not just on a grid) is a sample from a Gaussian process. Samples from GPs with mean zero and covariance kernel $K_T$ almost surely are not in the RKHS $\mathcal H_T$, but they *are* almost surely in the RKHS of any kernel $K_R$ which nuclearly dominates $K_T$ (see Lukic and Beder, "Stochastic Processes with Sample Paths in Reproducing Kernel Hilbert Spaces", Trans. AMS 2001). If such a kernel exists, using it as the "student" kernel should give us a rate of at least $n^{-1/2}$ with standard results (with some slight details still to be worked out, but should be true). Thus, it seems that your theorem implies that for $\alpha_T < \frac32 d$, no such translation-invariant kernel $R$ exists. This might be already easy to see from a Fourier definition of nuclear dominance, I'm not sure, but if not it is something that seems of somewhat independent interest.

It is also notable that both your practical results and your theorem are for algorithms essentially without any regularization other than the choice of kernel: the regression setting is exact interpolation, and your soft-margin uses $C = 10^4$ so is "almost" a hard-margin SVM. This is also fine – interpolation methods have seen a lot of interest of late, and certainly can perform well. But it's not the typical setting, and it would be interesting to see if the curves of Figure 1 look different when using e.g. a cross-validated setting for the amount of regularization.

Another complaint: you argue that applying Theorem 1 with this particular notion of effective dimension seems to give good results, but at least as it's stated, Theorem 1 doesn't actually apply with effective dimension, only ambient dimension. Is it possible to prove Theorem 1 with an appropriate version of effective dimension? I didn't carefully check the proof, but from your outlined sketch it seems like it might be only a small change.

Empirically, your investigations are nice, but it would be good to consider some other shift-invariant kernels as well: inverse multiquadric, Matérn, or spline RBF kernels would be prominent options.

Overall: I think this is a worthwhile study with interesting results. The theoretical setting, though, is somewhat limited by its fundamental approach, and the experiments aren't as thorough as they could be. Also, honestly, I'm not sure ICLR is the best venue for it (if I had written this paper around this time, I probably would have submitted it to AISTATS; it's certainly not *off* topic for ICLR, but fairly distant from most work at it).

Some typos:
- Under (2): "man-square error."
- Under (25): "where where."
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper experimentally investigates how fast the generalization error decreases when some specific kernel functions are used in real datasets. This paper conducted numerical experiments on several datasets to investigate the decreasing rate of the generalization error, and the rate is determined for such datasets. This decreasing rate is theoretically analyzed by using the approximation theory of RKHS in the teacher-student setting. It is shown that the rate is determined with the smoothness and effective dimensionality of input. Then, the smoothness of the teacher function is also derived through this analysis.

Overall, the paper is well written. I could easily follow the line. The pros and cons of the paper are summarized as follows.

Pros:
The numerical experimetns conducted in this paper are thorough, and they show interesting observations on the real datasets. This paper gives a practical information on the theoretical analysis as an empirical study.

Cons:
- The approximation theory shown in this paper (Theorem 1) is closely related to well-known results on kernel interpolation. However, this paper misses several related work in the literature. The result should be properly put in the literature. See, for example, [R1].

[R1] H. Wendland. Scattered Data Approximation. Cambridge University Press, Cambridge, UK, 2005.

- It is mentioned that this paper investigates the "generalization error." However, what is acutally done is more like "approximation error" analysis (about linear interpolation in RKHS). In reality, there are observation noises and thus we typically consider the generalization error. But, the teacher-student setting does not assume the existence of noise. Under existence of noise, generalization error analysis seems more appropriate as performed in [R2].

[R2] I. Steinwart and A. Christmann. Support Vector Machines. Springer, 2008.

Minor comment:
- In the introduction, it is mentioned that the assumption that the target function is included in RKHS is strong. However, the teacher-student setting considered in Theorem 1 assumes this assumption. The introduction requires some modification to make the message consistent.

---Update---
Thank you for your reply.
I understand the RKHS for teacher and that for student are different. But, in the introduction, you stated as "Yet, RKHS is a very strong assumption which requires the smoothness of the target function to increase with d (Bach, 2017) (see more on this point below), which may not be realistic in large dimensions.", which sounds like that an assumption that the target function is included in "some" RKHS corresponding to a smooth kernel is a strong assumption. At least, this sentence is not saying anything about difference between teacher and student, but is just saying assuming smoothness on the target is unrealistic. For me, this sounds inconsistent to your analysis. (This is just a minor concern. I wanted to clarify my understanding of your problem setting.) 

I think the setting where the teacher is not included in the student RKHS is also analyzed, for example, in the following papers (there are also several related papers):
F.J. Narcowich, J.D. Ward, and H. Wendland. Sobolev Error Estimates and a Bernstein
Inequality for Scattered Data Interpolation via Radial Basis Functions. Constr. Approx.,
24:175–186, 2006.
SCHEUERER, M., SCHABACK, R., & SCHLATHER, M. (2013). Interpolation of spatial data – A stochastic or a deterministic problem? European Journal of Applied Mathematics, 24(4), 601-629. 

Therefore, I still feel that the paper requires more expositions about the relation to the literature.
review_title: Official Blind Review #2

Meta-review: The paper studies, theoretically and empirically, the problem when generalization error decreases as $n^{-\beta}$ where $\beta$ is not $\frac{1}{2}$. It analyses a Teacher-Student problem where the Teacher generates data from a Gaussian random field. The paper provides a theorem that derives $\beta$ for Gaussian and Laplace kernels, and show empirical evidence supporting the theory using MNIST and CIFAR.

The reviews contained two low scores, both of which were not confident. A more confident reviewer provided a weak accept score, and interacted multiple times with the authors during the discussion period (which is one of the nice things about the ICLR review process). However, this reviewer also noted that ICLR may not be the best venue for this work.

Overall, while this paper shows promise, the negative review scores show that the topic may not be the best fit to the ICLR audience.
Decision: Reject