The optimality of kernel classifiers in Sobolev space
Authors: Jianfa Lai
zhifan Li
Dongming Huang
Qian Lin
Venue: ICLR 2024 poster (2024)
Keywords: kernel classification
minimax optimality
neural network classifiers
reproducing kernel Hilbert Space
Primary area: learning theory
TL;DR: We show the optimality of kernel classifiers in Sobolev space and propose a simple method to estimate the smoothness of the data with respect to the kernel

Abstract: Kernel methods are widely used in machine learning, especially for classification problems. However, the theoretical analysis of kernel classification is still limited. This paper investigates the statistical performances of kernel classifiers. With some mild assumptions on the conditional probability $\eta(x)=\mathbb{P}(Y=1\mid X=x)$, we derive an upper bound on the classification excess risk of a kernel classifier using recent advances in the theory of kernel regression. We also obtain a minimax lower bound for Sobolev spaces, which shows the optimality of the proposed classifier. Our theoretical results can be extended to the generalization error of overparameterized neural network classifiers. To make our theoretical results more applicable in realistic settings, we also propose a simple method to estimate the interpolation smoothness of $2\eta(x)-1$ and apply the method to real datasets.

Published as a conference paper at ICLR 2024
THE OPTIMALITY OF KERNEL SOBOLEV SPACE
CLASSIFIERS IN
Jianfa Lai"
Zhifan Li"
Tsinghua University, Beijing, China jianfala caanflla@mmalll @mail t edu.
Beijing Institute Mathematical Sciences and Applications, Beijing, China zhi fan wwwiieiiim........
Dongming Huang
Qian Lin
National University of Singapore, Singapore st stahd@nus edu.. sg
Tsinghua University, Beijing, China edu.
ABSTRACT
Kernel methods are widely used machine learning, especially for classification problems. However, the theoretical analysis of kernel classification is still lim- ited. This paper investigates the statistical performances of kernel classifiers. With mild assumptions on the conditional probability n)x)) IP(Y 1 X x). we derive an upper bound on the classification excess risk of kernel classifier us- ing recent advances the theory of kernel regression. We also obtain minimax lower bound for Sobolev spaces, which shows the optimality of the proposed clas- sifier. Our theoretical results can be extended to the generalization error of over- parameterized neural network classifiers. To make our theoretical results more applicable realistic settings, we also propose simple method to estimate the interpolation smoothness of 2n(x) 1 and apply the method real datasets.
INTRODUCTION
In this paper, we study the problem of binary classification in reproducing kernel Hilbert space (RKHS). Suppose n i.i.d samples {(X,, Y.) E X' {-1,1}} are drawn from a joint distribution (X, Y) p. where the conditional probability of the response variable Y given the predictor variable X x is denoted by πイ()) = IP(Y 1|X = x). We aim to find a classifier function f(x) X [] that minimizes the classification risk, defined
((f) == P(x,)~m)) (sign(((X)) +Y]
The minimal classification risk is achieved by the Bayes classifier function corresponding to P. which is defined as f/(aa) (x)) 1. Our main focus is on analyzing the convergence rate of the classification excess risk, defined as:
C(f)).
This paper studies a class of kernel methods called spectral algorithms (which will be defined in Section 2.3 for constructing estimators of fr The candidate functions are selected from RKHS H. which IS a separable Hilbert space associated with a kernel function K defined on X' (Smale well as kernel methods, are becoming increasingly important in machine learning because both experimental and theoretical results show that overparameterized neural network classifiers exhibit similar behavior classifiers based on kernel methods [Blkin et al. (2018). Therefore, understanding the properties of classifica- tion with spectral algorithms can shed light the generalization of deep learning classifiers.
& Zhou 2007 Steinwart & Christmann 2008). Spectral algorithms,
In kernel methods context, researchers often assume that f* H. and have obtained the mini-
max optimality of spectral algorithms (Caponnetto 2006 Caponnetto De Vito 2007). Some
"These authors contributed equally to this work.
"ooresponniig author.

---

Published as a conference paper at ICLR 2024
researchers have also studied the convergence rate of the generalization error of misspecified spec- tral algorithms (fr & Hd), assuming that fo falls into the interpolation space [7-] with some s >> (Fischer& & Steinwart, 2020 Zhang al.] 2023). In this line of work, researchers consider the embed- ding index condition which reflects the capability of H embedding into 1 space. Moreover, /Zhang
et al. (2023) extends the boundedness assumption the cases where [H]] n 1 (X, _ [H]].
Motivated by the aforementioned studies, we adopt similar assumptions in our study of kernel clas- sifiers trained via the gradient flow. We assume that the Bayes classifier f E [?]] satisfies the boundedness condition J E [- We first derive the upper bound of the classification excess risk, showing that the generalization error of the kernel classifier is highly related to the interpola- tion smoothness s. To clarify the minimax optimality of kernel classification, we then obtain the minimax lower bound for classification in Sobolev RKHS, which is a novel result in the literature. Our technique is motivated by the connection between kernel estimation and affnite-widthh neural networks, and our framework can be applied to neural network supervised learning. Furthermore, we provide a method to estimate the interpolation space smoothness parameter and also present some numerical results for neural network classification problems through simulation studies and real data analysis.
1.1 OUR CONTRIBUTION
In this paper, we study the generalization error of kernel classifiers. We show that
i) We show the generalization error of the gradient flow kernel classifier is bounded by ((n=s0((29+2)) provided that the Bayes classifier l E [H]], where 3 is the eigenvalue decay rate (EDR) of the kernel. This result is not only applicable to the Sobolev RKHS H. but also any RKHS with the embedding index ag 1/3, such as the RKHS with dot-product kerelss and the RKHS with shift-invariant periodic kernels.
ii
We establish a minimax lower bound on the classification excess risk in the interpolation space of Sobolev RKHS. Combined with the results in i), the convergence rate of the kernel classifier is minimax optimal in Sobolev space. Before our work, Yang (1999) illustrated a similar result of the minimax lower bound for Besov spaces. However, the result has only been proved for d by Kerkyacharian & Picard (1992) and the case for d remains unresolved.
iii)
To make our theoretical results more applicable in realistic settings, we propose a sim- ple method to estimate the interpolation smoothness s. We apply this method to estimate the relative smoothness of various real datasets with respect to the neural tangent kernels, where the results are in line with our understanding of these real datasets.
1.2 RELATED WORKS
We study the classification rules derived from a class of real-valued functions in a reproducing kernel Hilbert space (RKHS), which are used in kernel methods such as Support Vector Machines (SVM) (Steinwart & Christmann] (008). Most of the existing works consider hinge loss as the loss function, i.c. Wahba (002); Steinwart & Scovel (2007): Bartlett& Wegkamp (2008); Blaachard ct al. (2008) etc. Another kernel method, kernel ridge regression, also known as least-square SVM (Steinwart & Christmann 2008), is investigated by some researchers (Xiang Zhou 2009 Rilkin et al.) 2003). Recently, some works have combined the least square loss classification with neural networks (Demirkaya al. 2020 Hu et al. 202T).
We choose kernel methods because it allows us to use the integral operator tool for analysis De Vito
al. 2005; Caponnetto & De Vito. [2007] Fischer & Steinwart, 2020 | /Zhng et al. 2002). ). while pre- vious SVM works tend to use the empirical process technique (Steinwart & Scovel) 2007). More- over, we can easily extend the H. to the misspecified model case [7| when true model f belongs to a less-mmoohh interpolation space. Furthermore, we consider more regularization methods, collec- tively known as spectral algorithms, which were first proposed and studied by Rosasco et al. (2005); Bauer et al. (2007); Caponnetto & De Vito (2007). Zhang et al. (2023) combined these two ideas and obtained minimax optimality for the regression model. We extend their results to the classification problems.
2

---

Published as a conference paper at ICLR 2024
We study the minimax optimality of Sobolev kernel classification, and before work, the minimax lower bound classification excess risk for the RKHS class was seldom considered. Loustau (2008) 2009) have discussed Classification problems in Sobolev space, but they did not consider the lower bound of classification risk. Audibert (2004); Audibert & Tsybakov (2007); Massart & Nédélec (2006) provided some minimax lower bound techniques for classification, but how to solve RKHS remains unknown. Sobolev space (see, e.g., Adams & Fournier (2003) is known as a vector space of functions equipped with a norm that is combination of Lo-norms of the function together with its derivatives up to a given order and can be embedded into Hölder class, Inspired by the minimax lower bound for Hölder class classification in AAuiibert Tsybakov (2007). we derive the lower bound for the Sobolev class.
Recently, deep neural networks have gained incredible success classification tasks from image classification (Krizhevsky et al. 2012, He et al. 2016) to natural language processing (Devlin et al.) 2019). Since Jacot al. (2018) introduced the neural tangent kernel, The gradient flow of the training process can be well approximated by simpler gradient flow associated with the NTK kernel when the width of neural networks is sufficiently large (Lai al. 2023] Li et al. 2023a). Therefore, analyze the classification risk of neural networks trained by gradient descent.
2 PRELIMINARIES
We observe n samples {(X,, Yi) X X (-1,1) where C [d is compact. Let p be an unknown probability distribution on X' x 1] and μ be the marginal distribution X. We assume has a uniformly bounded density < Pmmn I u(z) I pmma for x E X. The classification task to predict the unobserved label y given
input x. The conditional probability is defined as ((x)) = IP(Y = 1|x = x). For any classifier f. the risk based on the 0-1 loss can be written as C(F) = E (ixxrr)<[(ssgg((((())
+ Y = Ex (1 (XX) 2 0} + m(X)LL((X) O}}.
(1)
One of the minimizers of the risk has the form fü = 2n7 - 1. Let L = L(f)). For any classifier learned from data, its accuracy is often characterized by the classification excess risk, which can be formulated as
E(î- = c(s) -- Ex (IX
< 03).
In the rest of this section, we introduce some essential concepts in RKHS and kernel classifiers. In Section 2.1, we review some definitions in the interpolation space of RKHS. The relationship between fractional Sobolev space and Sobolev RKHS is presented Section 2.2. Section 2.3
presents the explicit formula of the gradient-flor kernel classifier and the corresponding rewritten form through spectral algorithms and filter functions.
2.1 INTERPOLATION SPACE OF RKHS
Denote (x) () as the 2 space. Throughout the paper, denote by H. a sep- arable RKHS on X' with respect to a continuous kernel function K. We also assume that supzex K(xxx) I τ. for some constant The celebrated Mercer's theorem shows that there exist non-negative numbers d 2 d (es, (es,e)) = d,y and
and functions C1, 62, E L (2)) such that
Ka(a, Σ (,es(z)),(²')
(3)
where the series the right hand side converges in L²(X)).
Denote the natural embedding inclusion operator by Ss : H - 12) Moreover, the adjoint operator S (,) - H is an integral operator, i.e., for ʃ E 122(X and x E X, we have
(z) / K (x,x') (x') du (x').
It is well-known that Sд and St are Hilbert-Schmia operators (and thus compact) and their HS satisfy that
norms (denoted as
| 11, = 1|Sx = [ == ( K(ex 1/2
SK. K.
3

---

Published as a conference paper at ICLR 2024
Next, we define two integral operators as follows:
:= S (2( - 12(x, T==S H + H.
and T are self-adjoint, positive-defiitt, and in the trace class (and thus Hilbert- Hilbert-Schmidt and compact). Their trace norms (denoted as || satisfy that ||/||] = |||| || 12 = ||
For any s 2 0, the fractional power integral operator L (22, - I [22 pb) and T Hl H are defined as
L7() = Σ pg T')) = Σ
X3 (1 e5 2303.
(4)
==1
j=1
The interpolation space [H]] is defined
[H]]
Σ Casifee
oj Σ } (x)
(5)
easy to show that [7]] E is also a separable Hilbert space with orthogonal basis {A; es JeN- Specially, have [74]0 [ [22 14), [7] H and [7] ç [7] [7] for any numbers
0 < 81 < 82. For the functions in [H]] with larger we say they have higher (relative) interpolation smoothness with respect to the RKHS (the kernel).
2.2 FRACTIONAL SOBOLEV SPACE AND SOBOLEV RKHS
For E N, we denote the usual Sobolev space (X') by HxX( and (²( by (X). Then the (fractional) Sobolev space for any real number > can be defined through the real interpolation
H(X) (I,((2), (X)) 2.2
where m == mingk E k>
It is well known that when > d/2, !! is separable RKHS with respect to bounded kernel and the corresponding eigenvalue decay rate (EDR) is B = 2r/d. Furthermore, the interpolation space of H" (X)) under Lebesgue measure is given by
[ (X))* 1 (X)).
(6)
follows that given a Sobolev RKHS H" for d/2, if E H for any a > one can find that f [?(] with = a/r. Thus, in this paper, we will assume that the Bayes classifier fü is in the interpolation of the Sobolev RKHS [H]
2.3 KERNEL CLASSIFIERS: SPECTRA ALGORITHM
We then introduce a more general framework known as spectra algorithm (Rosasco et al., 2005 Caponnetto 2006 Bauer et al. 2007). We define the filter function and the spectral algorithms as
follows:
Definition (Filter function). Let {4., [0, R IvergA R+} be a class of functions and (2) 2xp(22). If spu and th satisfy:
Va E [0, we have sUP=E[o.Na] 20 (x(2) Eyl-a, TT;
3r s.t. Va E [0, we have sup=e(o,Na) [x(2)] S FFV0, WEr
where E, Fr are absolute constants, then we call yu a function. We refer to u as the regular- ization parameter and as the qualification.
Definition 2 (spectral algorithm). Let yy be a filter function index with 0. Given the samples Z,, spectral algorithm produces estimator of S given by fo = yuu (Tx gz.
4

---

Published as a conference paper at ICLR 2024
The following example shows that fa))) can be formulated by the spectral algorithms. Example 1 (Classifier with Gradient flow). The filter function of gradient flow by can be defined as " (z) = l- The qualification could be any positive number, E = and F, = (T/e)". So that for test imput z, the predicted output is given by sign(fu(x)).
Other spectral algorithms consist of kernel ridge regression, spectral cut-off, iterated Tikhonov, and so on. For more examples, we refer to Gerfo et al. (2008). Spectral algorithms differ in (u(()) and (z), which is corresponding to saturation effect defined in Gerfo et al. (2008). Moreover, Li et al. 2023b gives thorough analysis of the saturation effect for kernel ridge regression.
Notations. Denote Bxx,r) r) as ball, and A[B(z, r)] is denoted as the Lebesgue measure of B)), We use IIla,,,, to denote the operator norm of bounded linear operator from
Banach space B1 B2, i.e. ||A|] (B))B2)) = suP 21 || B2- Without bringing ambiguity, will briefly denote the operator norm as || In addition, we use tr and ||A|| to denote the trace and the trace norm of an operator. We use ||A||| to denote the Hilbert-Schmin norm.
3
MAIN RESULTS
3.1
ASSUMPTIONS
This subsection lists the standard assumptions for general RKHS H. and clarifies how these assump- tions correspond to properties of Sobolev RKHS.
Assumption (Source condition). For > there is a constant B such that fo [7]] and [|f]llm-- - B.
This assumption is weak since can be small. However, functions in [H]* with smaller are less smooth, which will be harder for an algorithm to estimate. Assumption 2 (Eigenvalue Decay Rate (EDR)). The EDR of the eigenvalues {}1} associated the kernel K is B > 1, ie.,
cj 22 SCj
for some positive constants and C.
Note that the eigenvalues X and EDR are only determined by the marginal distribution j and the RKHS H. For Sobolev RKHS H" equipped with Lebesgue measure and bounded domain with smooth boundary X' C Rd, it is well known that when r > d/2, H" is a separable RKHS with respect bounded kernel and the corresponding eigenvalue decay rate (EDR) munds & Triebel, 1996).
2r EEd-
Our next assumption is the embedding index. First, we give the definition of embedding property Fischer & Steinwart (2000): For 0 < < 1, there is a constant A >> 0 with [[]] + Loe (v)ll < A.
This means [7] is continuously embedded into Loe (v) and the operator norm of the embedding bounded by A. The larger is, the weaker the embedding property is.
Assumption (Embedding index). Suppose that there exists 0g 0, such that
0gg iinf inf {o E ( [1[[] (2, will {0).
and we refer ag the embedding index of an RKHS H.
This assumption directly implies that all the functions [H] are jr-a.e bounded for a >> On-- Moreover, will clarify this assumption for Sobolev kernels and dot-product kernels on gd-1 in the appendix.
3.2 MINIMAX OPTIMALITY OF KERNEL CLASSIFIESS
This subsection presents main results the minimax optimality of kernel classifiers. We first establish minimax lower bound for the Sobolev RKHS (x') under the source condition (As- sumption T).
We then provide upper bound based Assumptions and 3 and clarify that
5

---

Published as a conference paper at ICLR 2024
the Sobolev RKHS satisfies these assumptions. As result, demonstrate that the Sobolev kernel classifier is minimax rate optimal.
O, where H" is the Sobolev RKHS. For all learning methods f. for any fixed 5 E (0, 1), when is sufficiently large, there is distribution p E P such that, with probability at least 1 6, we have
Theorem (Lower Bound), Suppose f [X)
E(f) 2 Côn 200-11,
(8)
where C' is universal constant.
Theorem D shows the minimax lower bound on the classification excess risk over the interpolation space of the Sobolev RKHS. Theorem | also establishes minimax lower bound at the rate of rs. Yang (1999) illustrated similar result of the minimax lower bound for Besov spaces. However, the result has only been proved for d = 1 by Kerkyacharian Picard (992) and the case for d' remains unresolved.
2047 for the Sobolev space l7 with
The following theorem presents an upper bound for the kernel classifier.
Theorem (Upper Bound). Suppose that Assumptions 22 and andld for 0 < 8 S 2T, where
the qualification of the filter function. By choosing sufficiently large, with probability at least we have
n n*#+1, for any fixed 8 (0, 1), when is
(In
4
E(fx)= S C
where C' a constant independent of n and 8.
Combined with Theorem Theorem 2 shows that by choosing a proper early-stopping time, the Sobolev kernel classifier is minimax rate optimal. Moreover, given the kernel and the decay rate B, the optimal rate is mainly affected by the smoothness of f with respect to the kernel. Thus, in Section 5 we will introduce how to estimate the smoothness of functions or datasets given a specific kernel.
We emphasize that Theorem can be applied to any general RKHS with an embedding index Og = 1/3, such as RKHS with shift-invariaal periodic kernel and an RKHS with dot dot-prrouct kernel. Thanks to the uniform convergence of overparameterized neural networks (Lai et al. 2023 Li et al. 2023a), Theorem 2 can also be applied to analyze the generalization error of the neural network classifiers. We will discuss this application in the next section.
4 APPLICATIONS IN NEURAL NETWORKS
Suppose that we have observed n i.i.d. samples (X,, from p. For simplicity, we further assume that the marginal distribution μ of p the uniform distribution on the unit sphere gd-1 We use neural network with L hidden layers and width to perform the classification on (X,, Y, Y.ja.. The network model [2; 0) and the resulting prediction are given by the following equations
no <²(x) = xx 1((x) - V
2 ow (w
1= 1,
(10)
f(x;0) w and ÿ = sf
where h' represents the hidden layer, (z) == max(x, 0) the ReLU activation (applied element- wise), w E mg and W E Rm are the parameters of the model. We use 0 to represent the collection of all parameters flatten column vector. With the mirrored initialization (shown in Li al. (2023a)), we consider the training process given by the gradient flow é (0) where the squared loss function is adopted L())= 1 Σ (Y, - f(,, 0))
The consideration for this choice of loss function is that the squared loss function is robust for optimization and more suitable for hard learning scenarios (Hui & Belkin (2020); Demirkaya et al. (2200) Kornblith et al. (2020)). Hui & Belkin (2020) showed that the square loss function has been shown to perform well in modern classification tasks, especially in natural language processing
while Komblith al. (2020) presented the out-of-diitributiin robustness of the square loss function.

---

Published as a conference paper at ICLR 2024
When the network is overparameterized, Li et al. (2023a) showed that the trained network fa; can be approximated by kernel gradient method with respect to the following neural tangent kernel
Σ (a)
II KO (T)
(11)
where i = (2r, (xr,2"), xip)
Ki 2 represents p times composition of Kn and x (u) =
times
by convention; if = L., the product IT= is understood be 1. Denote Vnn = (Y,,.., ..,, Va)", K [x]])xx[n)) an n x n matrix of (K(,,, X.))). and Amin Amin (K (N], The following proposition shows the uniform convergence of fxx;;)
Proposition 1 (Theorem in Li et al. (023a)). Suppose x E S For any 6 > 0, any hidden layer L 2, and ô e (0, 1). when the width m Z poly (n, Jn, 1| (nl///, (n(L/)),n(LL/e) with probability at least - 8 with respect to random initialization, we have
sup sup (se Srtk (x)) Sc. 120
where 11th is defined as in Example but with the kernel Kntk-
Theorem G.5 in Haas et al. 2023) showed that the RKHS of the NTK on $ is Sobolev space. Moreover, the kernel Katk dot-product kernel satisfying polynomial eigenvalue decay d/(d-1) 1). Thus, we can obtain the following corollary by combining Theorem and Proposition |
Corollary 1. Suppose that æ E gd-1 and Assumption holds for Ht being the RKHS of the kernel Knt and 8 > O. Suppose t n-FFI. For any fixed (0, when m Z poly (n, > [[Y)]] |2, (2,1)( and sufficiently large, with probability least 6, we have
{()(1;0)) S C In n 2GPTIS
(12)
where C' a constant independent of n and 8.
This corollary shows that the generalization eтror of fine-tuned, overparameterized neural network classifier converges at the rate of श, This result also highlights the need for additional efforts to understand the smoothness of real datasets with respect to the neural tangent kernel. A larger value of s corresponds to a faster convergence rate, indicating the possibility of better generalization performance. Determination of the smoothness parameter will allow us to assess the performance of an overparameterizze neural network classifier on a specific dataset.
ESTIMATION SMOOTHNESS
In this section, we provide simple example illustrate how to determine the relative smoothness of the ground-truth function with respect to the kernel. Then we introduce simple method to estimate a with noise and apply the method real datasets with respect to the NTK.
Determination of 8. Suppose that A' E [0, 1] and the marginal distribution f.y is uniform dis- tribution on (0, 1). We consider the min kernel Kmin (x, min(x, x') (Wainwright, 2019 and denote by Hmin the corresponding RKHS. The eigenvalues and the eigenfunctions of Hmmin are
2j -
2j - πT), π : ej(x) 2in
A =
j j21.
(13)
2
2
Thus, the EDR is 2. For illustration, we consider the ground true function f*(x) cos (20s)
Suppose (x) = Σ3 fzez(z), then we have f, = 2 Jo cos(2 sin( 25-1
2 n. kr)dr x j_1 Thus,
fg -- where 1. By the definition of the interpolation space, we have 2r-1 0.5.

---

Published as a conference paper at ICLR 2024
404
0
322
102 100
100
(a)
(b)
Figure 1: Experiments for estimating the smoothness parameter s in regression settings. (a) Naive estimation based on 2, 000 sample points for a 0 (blue) and a 0.1 (orange). (b) Truncation Estimation based on 2, 000 sample points with truncation point 100. In both plots (a) and (b), the x-- axis the logarithmic index and the y-axis is the logarithmic py.(c) Truncation Estimation across various values of sample size each repeated 50 times. The blue line represents the average of estimates, the shaded area represents one standard deviation, and the true value is indicated by the orange dashed line.
Estimation of in regression. To better understand the estimation process, we first consider re- gression settings where the noises have an explicit form and we then consider classification settings. Suppose that we have n i.i.d. samples of X(x) .X.,....,)) and [n] [Yi,..., Yn]" E from Y, ff + oe,, where E ~ (0.
We start with a naive estimation method. Let Kman (-[m) ((m)) be the kernel matrix. Suppose the eigendecomposition given by Kmin (X(n), Xin) = VEVT, where eigenvector matrix, U/'s are the eigenvectors, and E is the diagonal matrix of the eigenvalues. We can estimate r by estimating the decay rate of py, where P, = Ym Uy. To visualize the convergence rate we perform logarithmic least-squares to fit pj with respect to the index j and display the values of the slope r and the smoothness parameter
[o,,..., UnJ is the
For a = 0, r can be accurately estimated by the above naive method since there is no noise in Yi's. The blue line and dots in Figure (a) present the estimation of in this case, where the estimate is around the true value 0.5. However, for a = 0.1, the naive estimation is not accurate, as shown by the orange line and dots in Figure (a).
To improve the accuracy of the estimation, we introduce a simple modification called Truncation Estimation, described as follows. We select some fixed integer as a truncation point and estimate the decay rate of Pj up to the truncation point. For the example with a 0.1, we choose the truncation point 100 and the result is shown Figure I (b). We observe that estimation becomes much more accurate than the naive estimation, with an estimate of = 0.53 not too far away from the true value 0.5. In general, noise in the data can worsen the estimation accuracy, while increasing the sample size can improve the accuracy and robustness of the estimation. In Figure (c), we show the result for estimating 8 in repeated experiments with more noisy data (a = 0.2), where we observe that the sample size n increases, the estimation becomes accurate.
Estimation of in classification. Now we consider the classification settings, where the popula- tion given by P(Y 1|X z) (f 1)/2. Unlike regression problems, the variance of the noise = y - (x) is determined by (x) and may not be negligible. Nonetheless, in clas- sification problems, we can still estimate the smoothness parameter & using Truncation Estimation, thanks to the fact that increasing the sample size improve its performance. The results are shown in Figure 2 where we can indeed make similar observations to those in [ and (c).
As application of Truncation Estimation, we estimate the relative smoothness of real data sets with respect to the NTK defined in equation [I] The results are shown in Table We can see that with respect to the NTK, MNIST has the largest relative smoothness while CIFAR-10 10 has the smallest one. This result aligns with the common knowledge that MNIST is the easiest dataset while CIFAR-10 10 is the most difficult one of these three datasets.
8

---

Published as a conference paper at ICLR 2024
(a)
(b)
Figure 2: Experiments for estimating the smoothness parameter s in classification settings. (a) The experiment uses 5, 000 sample points and the truncation point is 100. (b) Truncation Estimation across various values of sample size n, each repeated 50 times. The blue line represents the average of estimates, the shaded area represents one standard deviation, and the true value is indicated by the orange dashed line.
Kernel
MNIST
Fashion-MNIST
CIFAR-10
NTK-1
0.4862 (0.0824)
0.4417 (0.0934)
0.1992 (0.0724)
NTK-2
0.4871 (0.0793)
0.4326 (0.0875)
0.2047 (0.0831)
NTK-3
0.4865 (0.0815)
0.4372 (0.0768)
0.1965 (0.0795)
Table 1: Truncation Estimation of the relative smoothness s different real data sets with different NTKs. NTK L indicates the L-hidden-layer NTK. We only consider two classes of labels for each dataset: Label I and 7 for MNIST, trousers and sneakers for Fashion-MNIST, cars and horses for CIFAR-10. We randomly select 5,000 data points and choose the truncation point 100 estimate For each dataset and each kernel, we repeat 50 times and the standard deviation is in parentheses.
Limitations The misspecified spectral algorithms (assuming / E (H() are studied since 2009 Steinwart et al. (2009): Dicker et al. 2): Pillaud Vivien et al. (2018);1 Fischer & Steinwart (2020): Zhang et al. 2003 However, to the best our knowledge, there is barely any result on the estimation of the smoothness s. This paper is the first to propose the estimation method even though the method is more susceptible to noise when the sample size not enough or f" has more complex structures. For example, if f I==Ifeeeee (z), where f3
(e.g.(Steinwart
=18-1 when j is odd and
f3 j 828-1 when j is even (s1 > 82). For the kernel with EDR 3. f E [H] instead of [M or [M1 for some E (82, $1). In this mixed smoothness case, our method tends to give an estimation ($2, $1). A more detailed discussion of the limitations is presented in the appendix. We will try to find more accurate estimation methods for general situations in the near future.
DISCUSSION
this paper, we study the generalization error of kernel classifiers Sobolev space (the interpo- lation of the Sobolev RKHS). We show the optimality of kernel classifiers under the assumption that the ground true function is the interpolation of RKHS with the kernel. The minimax optimal rate ==/((((+++1) where the smoothness parameter of the ground true function. Building upon the connection between kernel methods and neural networks, we obtain an upper bound on the generalization error of overparameterizee neural network classifiers. To make our theoretical result more applicable to real problems, we propose simple method called Truncation Estimation to esti- mate the relative smoothness s. Using this method, we examine the relative smoothness of three real datasets, including MNIST, Fashion-MNISS and CIFAR- 10. Our results confirm that among these three datasets, MNIST is the simplest for classification using NTK classifiers while CIFAR- is the hardest.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
Lin's research was supported in part by the National Natural Science Foundation of China (Grant 92370122, Grant 11971257). This work has been supported by the New Cornerstone Science Foun- dation.
REFERENCES
Robert A Adams and John JF Fournier. Sobolev spaces, Elsevier, 2003.
Jean- Yves Audibert. Classification under polynomial entropy and margin assump-tions and ran- domized estimators. 2004. URL https: http://pp...eettt.cccccooo.....a
1986311
Jean-Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. Annals of statistics, 35(2):608-633 633, 2007.
Peter L Bartlett and Marten H Wegkamp. Classification with reject option using hinge loss. Journal of Machine Learning Research, 9(8), 2008.
Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco. On regularization algorithms in learning theory. Journal of complexity, 23(1):52 (6(1):52-722 12-5522-2122 2007.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To Understand Deep Learning We Need Under- stand Kernel Learning. In Proceedings the 35th International Conference on Machine Learning, pp. 541-549, PMLR, July 2018.
Gilles Blanchard, Olivier Bousquet, and Pascal Massart. Statistical performance of support vector machines. The Annals of Statistics, 36(2):489-531 2008.
Andrea Caponnetto. Optimal rates for regularization operators in learning theory. Technical report, MASSACHUSETTS INST OF TECH CAMBRIDGE COMPUTER SCIENCE AND ARTIFI- CIAL..., 2006.
Andrea Caponnetto and Emnesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Ernesto De Vito, Andrea Caponnetto, and Lorenzo Rosasco. Model selection for regularized least- squares algorithm in learning theory. Foundations of Computational Mathematics, 5:59-85, 2005.
Ahmet Demirkaya, Jiasi Chen, and Samet Oymak. Exploring the role of loss functions in multiclass classification. 2020 54th annual conference on information sciences and systems (ciss), pp. 1-5. IEEE, 2020.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HIT (1), 2019.
Lee H Dicker, Dean P Foster, and Daniel Hsu. Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators. Electronic Journal of Statistics. ((1):100221047,2211
D. E. Edmunds and H. Triebel. Function Spaces, Entropy Numbers, Differential Operators. Cambridge Tracts in Mathematics. Cambridge University Press, 1996. doi: 10.1017/ CIB0980511662201.
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algo- rithms. The Journal of Machine Learning Research, 21(1):846488501 2020.
Lo Gerfo, Lorenzo Rosasco, Francesca Odone, De Vito, and Alessandro Verri. Spectral algo- rithms for supervised learning. Neural Computation, 20(7):1873-188 2008.
Moritz Haas, David Holzmüller, Ulrike Luxburg, and Ingo Steinwart. Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension. arXiv preprint arXiv:2305.14077, 2023.
10

---

Published as a conference paper at ICLR 2024
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Tianyang Hu, Jun Wang, Wenjia Wang, and Zhenguo Li. Understanding square loss in training overparametrized neural network classifiers. arXiv preprint 1xXiv:2112.03666 2021.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy in classification tasks. In International Conference Learning Representations, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen-
cralization in neural networks. arXiv preprint arXiv: 1 000. 2018.
G Kerkyacharian and D Picard. Density estimation in besov spaces zyxwwusxpoonmkkjhgfeel cbazyxwvut. Statistics & probability letters, 13:15-24, 1992.
Simon Kornblith, Honglak Lee, Ting Chen, and Mohammad Norouzi. Demystifying loss functions for classification. 2020.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Advances neural information processing systems, 25, 2012.
Jianfa Lai, Manyun Xu, Rui Chen, and Qian Lin. Generalization ability of wide neural networks on R. arXiv preprint ar 2Xiv:2302.05933. 2023.
Yicheng Li, Zixiong Yu, Guhan Chen, and Qian Lin. Statistical optimality of deep wide neural networks. arXiv preprint arXiv:2305.02657 2023a.
Yicheng Li, Haobo Zhang, and Qian Lin. On the saturation effect of kernel ridge regression. In International Conference on Learning Representations, February 2023b.
Sébastien Loustau. Aggregation of svm classifiers using sobolev spaces. Journal of Machine Learning Research, 9(7), 2008.
Sébastien Loustau. Penalized empirical risk minimization over besov spaces. Electronic Journal of Statistics, 3:824-850, 2009.
Pascal Massart and élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, (155):322-23666 2006.
Loucas Pillaud-Vivien, Alessandro Rudi, and Francis R. Bach. Statistical optimality stochastic gradient descent on hard learning problems through multiple passes. ArXiv, /t///8855.0077
2018.
Ryan Rifkin, Gene Yeo, Tomaso Poggio, et al. Regularized least-qquares classification. Nato Science Series Sub Series III Computer and Systems Sciences, 190: 900:131-154 2003.
Lorenzo Rosasco, Ernesto De Vito, and Alessandro Verri. Spectral methods for regularization in learning theory. DISI, Universita degli Studi di Genova, Italy, Technical Report DISI-TR-05-18. 2005.
Steve Smale and Ding- Zhou. Learning theory estimates via integral operators and their ap- proximations. Constructive approximation, 2632):153-172, 2007.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008
Ingo Steinwart and Clint Scovel. Fast rates for support vector machines using gaussian kernels. The Annals of Statistics, 35(2):575-607, 2007.
Ingo Steinwart, Don R Hush, Clint Scovel, et al. Optimal rates for regularized least squares regres- sion. In COLT, pp. 79-93, 2009.
Grace Wahba. Soft and hard classification by reproducing kernel hilbert space methods. Proceedings of the National Academy of Sciences, 19(26):16224-11) 2002.

---

Published as a conference paper at ICLR 2024
Martin Wainwright. High-dimensional statistics: A non-asympiotic viewpoint, volume 48. Cam- bridge university press, 2019.
Dao-Hong Xiang and Ding-Xuan Zhou. Classification with gaussians and convex loss. Journal of Machine Learning Research, 10(7). 2009.
Yuhong Yang. Minimax nonparametric classification. rates of convergence. IEEE Transactions on Information Theory, 45(7):2271-2288 1999.
Haobo Zhang, Yicheng Li, Weihao Lu, and Qian Lin. On the optimality of misspecified kernel ridge regression. arXiv preprint arXiv2335.00224, 2023.
12


Reviews:
[{"review_id": "jpzqbWiKMs", "reviewer": "Reviewer_ABCa", "summary": "This paper considers estimating classifiers in the interpolation Sobolev RKHS. They have two theoretical contributions: (a) the lower bound on the excess risk and (b) the upper bound of the same at the t-th iterate. They apply this results to a neural network which can be approximated by a neural tangent kernel. The optimal rate depends on the smoothness of the optimal classifier, larger smoothness leading to faster convergence. They propose a truncation strategy for estimation of the smoothness, which when applied to real datasets corraborates the estimated smoothness with the difficulty of the dataset.", "questions": "-- Not very clear how the arrived results compare against the existing work on NTK. Would be interesting to understand that to appreciate the impact of the contributions\n-- It is not very clear about the impact of this work from an application front. The experiments to real datasets are restricted to estimation of the smoothness. Some insights would be helpful in this regard. How to enforce learning estimators constrained with a requirement on the smoothness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and easy to follow. The main results seem novel for the setup considered. The association of the estimated smoothness to the difficulty of the datasets is interesting.", "weaknesses": "see questions.", "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": "", "extra_scores": {}}, {"review_id": "7NoolUZ3iL", "reviewer": "Reviewer_yGYg", "summary": "This work shows the minimax optimality of kernel classifiers in Sobolev spaces and extends the theory to neural network classifiers through the connection between neural networks and neural tangent kernels. The paper also shows the error rate depends on the data smoothness. Thus the paper proposes a practical approach to estimate such data smoothness, helping us understand how hard it will be to model the data accurately.", "questions": "After estimating the smoothing parameter, can we further gain some insight into the optimal steps in the gradient flow algorithms? It would be helpful if some numerical studies can be performed to support this.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Studying the optimality of kernel classifiers is a fundamental problem in machine learning. \n* The theory in this paper has the potential to guide the practice of kernel learning and neural networks.", "weaknesses": "The primary concern regarding this paper is that the established minimax optimality for kernel classifiers relies on the gradient flow algorithm, which is mainly based on the L2 loss and is not commonly used in practical applications of building kernel classifiers. While the minimax rate is established, its optimality is only proven in an asymptotic sense, leaving a considerable gap between theory and practical usage. This approach is natural in the existing work when building the minimax rate for kernel classification, but not for the kernel classification. The paper's contribution would be more significant if the theoretical framework were based on widely used classifiers, such as SVM and logistic regression. \n\nA similar issue arises with the application of kernel classifier theory to neural networks, particularly those employing the L2 loss for fitting. Despite the L2 loss being effective in various neural network scenarios, the paper would benefit from incorporating theories that utilize loss functions more prevalent in practice.\n\nAn additional point of concern is that the paper's main theoretical underpinnings are based on unpublished works, specifically referenced as https://arxiv.org/abs/2305.07241. The validity and proofs presented in that work have not been verified in this review.", "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": "", "extra_scores": {}}, {"review_id": "zztiRQwDmU", "reviewer": "Reviewer_3CL4", "summary": "The paper shows that a variety of kernel regression methods known as spectral algorithms achieve optimal convergence rates for binary classification when the conditional probability function $\\eta$ stems from a Sobolev space. The authors also apply this theory to neural tangent kernels. Finally, the paper provides a simple (but not theoretically analyzed) method for estimating the smoothness of the conditional probability function $\\eta$ from a data set, which is applied to standard image classification data sets.", "questions": "**Questions**:\n(1) Does ridge regularization also qualify as a spectral algorithm? And what about gradient descent?\n\n(2) Could the results be generalized to multi-class classification? I am also wondering about other loss functions, but the Brier score should be trivial and the log-loss should require additional modifications.\n\n**Major comments**:\n(3) Before Corollary 1: While NTKs are dot-product kernels on the sphere, they are not in general dot-product kernels outside of the sphere. For example, from Eq. (15) we have $K_{ntk}(0, 0) = 1$, which means that $K_{ntk}$ cannot be a dot-product kernel. On the other hand, I also don't see why you would need it to be a dot-product kernel for Corollary 1.\n\n(4) In Theorem 2, you seem to implicitly assume that $\\alpha_0 = 1/\\beta$, see the text before Eq. (14) in the appendix. Please state this in the theorem. Moreover, it is not clear to me that this would also hold in the setting of Corollary 1 for general domains. In the special case of the sphere, this could be fixed at least for very similar network architectures because then the RKHS of the NTK is known to be a Sobolev space, see for example the proof of Theorem G.5 in https://arxiv.org/abs/2305.14077\n\n(5) I am not fully convinced by the proposed smoothness estimator. For example, assume that the target function $f^*: \\mathbb{R}^2 \\to \\mathbb{R}$ has different degrees $s_1$ and $s_2$ of (Sobolev) smoothness in dimensions $1$ and $2$. Then, I would expect the eigenvalues to decay at different rates depending on the direction that the eigenfunctions are more refined in, such that the eigenvalues in a plot as in Figure 1 (a) wouldn't lie on a single line but in between two lines corresponding to $s_1$ and $s_2$. Linear regression would then estimate a smoothness between $s_1$ and $s_2$, but in terms of interpolation spaces, the function would still only lie in the interpolation space with the lower smoothness. (This could be checked by just plotting the $p_j$ on the image data sets.) \n\nPerhaps this issue could be \"fixed\" by performing linear regression on top of $\\tilde p_j := \\sup_{k \\geq j} p_k$, which would try to filter out the \"upper line\" in the plot, but also potentially it could be more susceptible to noise. (Judging from the plots, perhaps it could be a good heuristic to automatically set the threshold in a way that only those $p_j$ are included that are larger than the maximum in the right half of the plot.) Another idea for the estimator would be to stay closer to the definition of interpolation spaces and work with (approximations of) the interpolation space norms of the regression function, maybe something like finding an \"elbow\" in $s \\mapsto y^\\top (K + \\lambda I)^{-1} K^s (K + \\lambda I)^{-1} y$.\n\nBesides the mixed smoothness case, another important case is the \"manifold assumption\" case where $\\mu$ is supported on a submanifold, and which is a popular assumption for image data sets. I am wondering whether the estimator can be trusted in this case.\nAnother potential test case is what happens if the classes are well-separated and non-noisy, i.e., with $\\eta(x) \\in \\{1, -1, \\text{undefined}\\}$. This is arguably close to the situation for MNIST. Can the estimator find out that the function is arbitrarily smooth?\nIn general, it would be interesting to see whether the rates predicted by the theory and the simple estimation method hold up in a practical setting.\n(I'm brainstorming a bit here, it is not necessary to try everything in order to address my comment.)\n\n**Minor comments**:\n- p. 1: Use \\operatorname{sign} or something like this to set the sign operator in non-italic font. (same for later)\n- \"trained via the gradient flow\" -> \"trained via gradient flow\"\n- Sec 1.1 i) \"bounded by $...$\" there should be a constant $C$ or an O-notation in there.\n- Please don't use all-caps for author names in citations (STEINWART & SCOVEL, 2007).\n- p. 3: \"Recently, Deep\" -> \"Recently, deep\"\n- \"gained incredible success\" -> \"achieved incredible success\" or so?\n- \"Another reason we choose\" -> \"Another reason why we choose\"?\n- \"spectra algorithm\" - should this be \"spectral algorithms\"? (also further below)\n- Same paragraph (last paragraph of Sec. 1): When you say \"Another reason ... NTK kernel ...\" it seems that this is essentially the same reason as before, just formulated in more detail.\n- Sec 2.3: Mention that it is gradient flow on the least-squares loss?\n- Assumption 3 could be formulated more clearly: $\\alpha_0$ always exists because $\\alpha = 1$ is always admissible by the bounded kernel assumption. Moreover, $\\alpha_0 > 0$ trivially because of the way that $\\alpha_0$ is defined. So here, I think Assumption 3 should be a definition (something like \"We define the embedding index $\\alpha_0$ as ...\"), unless you want to require $\\alpha_0 < 1$.\n- p. 6: \"minimax optimality of kernel classifier\" -> \"minimax optimality of kernel classifiers\"\n- p. 6: \"source condition 1\" -> \"source condition (Assumption 1)\"\n- \"Assumption 1, 2, and 3\" -> \"Assumptions 1, 2, and 3\"?\n- In Theorem 2: \"Assumption 1, 2, and3\" -> whitespace is missing\n- \"of the neural network classifier\" -> \"of neural network classifiers\"\n- Eq. (14): The last layer should use the matrix $W^L$, not $W^{(L, p)}$. (The latter notation seems to be a remnant of the mirrored initialization notation, which you do not adopt in the other parts of Eq. (14).)\n- The \"mirrored initialization\" seems to be already older and known as \"antisymmetric initialization trick\": http://proceedings.mlr.press/v107/zhang20a.html\n- The citation Hui (2020) is missing the second author M. Belkin.\n- The sentence before Proposition 1 is not ended by a period.\n- Before corollary 1: I think the eigenvalue decay shouldn't be $\\beta = d(d-1)$, maybe you meant $\\beta = d/(d-1)$?\n- p. 7: \"ground true function\" -> \"ground-truth function\"  (also in the conclusion)\n- p. 8, paragraph \"Estimation of $s$ in regression\": There is nothing sensible after the $\\in$ symbol \n- Related work: The authors could (briefly) mention/discuss other classes of assumptions that can be made in the classification setting, see e.g. https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-12/issue-1/Improved-classification-rates-under-refined-margin-conditions/10.1214/18-EJS1406.full\n\n**Summary of discussion**:\nI missed an assumption in the NTK part, now I am not concerned about its correctness anymore. The smoothness estimator is still not reliable in general, which means that the experiments cannot fully support the appropriateness of the Sobolev assumption, but the authors acknowledge the limitations. In conclusion, I am changing my score from 5 to 6.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper has a relatively clear message, and I think the paper is relatively well-written. I guess that the upper bound on the convergence rate in Theorem 2 should be a relatively direct corollary from Fischer and Steinwart (2020) in the special case of ridge regularization, but the authors formulate a more general result for spectral algorithms that also holds for gradient flow. The lower bound in Theorem 1 nicely complements the upper bound. While the square loss is not very common for classification, it is still noteworthy that optimal rates can be achieved with any loss.", "weaknesses": "The application to the NTK looks nice, but I have some concerns that Assumption 3 cannot be verified for a good $\\alpha_0$, see the major comments below.\n\nWhile the smoothness assumption on $f^*$ seems less natural to me in the classification setting, the authors provide interesting experiments that appear to show that this assumption is appropriate. However, I have doubts that the proposed (and not theoretically justified) estimator can really estimate what it is supposed to estimate, see the major comments below.\n\nOverall, the aforementioned concerns hold me back from recommending acceptance at the moment, but I am ready to adjust my score if these concerns can be addressed.", "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": "", "extra_scores": {}}, {"review_id": "AgIzdDe3ZN", "reviewer": "Reviewer_atim", "summary": "In this paper, the authors investigate the statistical performance of kernel classifier, and establish, under rather standard assumptions in Theorem 1 and 2, respectively, upper and lower bounds on the classification excess risk (over Sobolev spaces), showing the optimally of the proposed classifier.\n\nThe proposed theoretical analysis is then applied to (deep) neural network (NN) models, to establish some generalization error bound of a fine-tuned NN model in the over-parameterization regime.\n\nAn intuitive approach is also proposed in Section 5 to estimate the key smoothness parameter with respect to the kernel.", "questions": "I the following questions and/or comments for the authors:\n\n1. Page 3: \"Therefore, the framework of spectra algorithm\" -> spectral algorithm. Similarly for the first sentence in Page 5.\n2. Page 5: \"bounded domain with smooth boundary $\\mathcal{X} \\subseteq R^d$\" should be $\\mathcal{X} \\subseteq \\mathbb{R}^d$ here?\n3. I do not understand Assumption 3 and the notations therein, could the authors clarify this?\n4. The proof of Theorem 1-2, Corollary 2, and the appendix should be re-organized for better readability.\n5. I do not understand the statement of \"width m and the sample size n are sufficiently large\" in Corollary 1: should Corollary 1 be understood as asymptotic statements as $m,n \\to \\infty$? I am a bit confused since in many DNN and NTK literature, one must have $m \\gg n$ for the NTK to accurately approximate the DNN behavior. Also, can the results in Corollary 1 be compared to existing results in NTK kernel literature?\n6. I do not understand the connection between the min kernel discussed above Equation (17) and the NTK.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper focuses on the fundamental problem of kernel learning and, if I understand correctly, improves some previous efforts such as Kerkyacharian & Picard (1992).\n\nThe obtained results (Theorem 1 and 2) are rather strong, in that Theorem 1 and 2 together show the minimax rate optimality of the proposed kernel spectral classifier.\n\nThe authors establish an interesting connection between the proposed theoretical analysis to NTK and deep neural networks in Corollary 1.", "weaknesses": "I am not an expert in the theory of kernel learning and I personally find this paper a bit difficult to digest. I assume some other audiences from the (theoretical) AI/ML community may have the same impression.\nI think this paper can be improved in terms of presentation. See my detailed comments below.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)