On the Target-kernel Alignment: a Unified Analysis with Kernel Complexity
Authors: Chao Wang
Xin HE
Yuwen Wang
Junhui Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Learning theory
kernel method
reproducing kernel Hilbert space
saturation effect
Primary area: learning_theory
TL;DR: A unified analysis with kernel complexity for the impact of the target-kernel alignment on kernel-based method.

Abstract: This paper investigates the impact of alignment between the target function of interest and the kernel matrix on a variety of kernel-based methods based on a general loss belonging to a rich loss function family, which covers many commonly used methods in regression and classification problems. We consider the truncated kernel-based method (TKM) which is estimated within a reduced function space constructed by using the spectral truncation of the kernel matrix and compare its theoretical behavior to that of the standard kernel-based method (KM) under various settings. By using the kernel complexity function that quantifies the complexity of the induced function space, we derive the upper bounds for both TKM and KM, and further reveal their dependencies on the degree of target-kernel alignment. Specifically, for the alignment with polynomial decay, the established results indicate that under the just-aligned and weakly-aligned regimes, TKM and KM share the same learning rate. Yet, under the strongly-aligned regime, KM suffers the saturation effect, while TKM can be continuously improved as the alignment becomes stronger. This further implies that TKM has a strong ability to capture the strong alignment and provide a theoretically guaranteed solution to eliminate the phenomena of saturation effect. The minimax lower bound is also established for the squared loss to confirm the optimality of TKM. Extensive numerical experiments further support our theoretical findings. The Python code for reproducing the numerical experiments is available at https://github.com/wywangen.

On the Target-kernel Alignment: a Unified Analysis with Kernel Complexity
Chao Wang', Xin Hel:; Yuwen Wang Junhui Wang
School of Statistics and Management, Shanghai University of Finance and Economics : Key Laboratory of Mathematical Economics (SUFE), Ministry of Education, Shanghai
t Chinese University of Hong Kong
wang - chw.estu.uu.oooooo sufe, edu. en, he we..in11mmaal..mm shufe. edu. wangyw@ling ink. cuhk. edu.hk, junhuiwang@cuhi. edu. hk
Abstract
This paper investigates the impact of alignment between the target function of interest and the kernel matrix on variety of kernel-based methods based on a general loss belonging to a rich loss function family, which covers many commonly used methods regression and classification problems. We consider the truncated kernel-based method (TKM) which is estimated within reduced function space constructed by using the spectral truncation of the kernel matrix and compare its theoretical behavior to that of the standard kernel-based method (KM) under various settings. By using the kernel complexity function that quantifies the complexity of the induced function space, derive the upper bounds for both TKM and KM, and further reveal their dependencies on the degree target-keret alignment. Specifically, for the alignment with polynomial decay, the established results indicate that under the just-aligned and weakly-aligned regimes, TKM and KM share the same learning rate. Yet, under the strongly-alignee regime, KM suffers the saturation effect, while TKM can be continuously improved as the alignment becomes stronger. This further implies that TKM has a strong ability to capture the strong alignment and provide a theoretically guaranteed solution eliminate the phenomena of saturation effect. The minimax lower bound is also established for the squared loss to confirm the optimality of TKM. Extensive numerical experiments further support our theoretical findings. The Python code for reproducing the numerical experiments is available on Github
1 Introduction
Kernel-based methods have attracted increasing attention in recent years (Belkin et al.) 2018 Liang & Rakhlin 2020 Ghorbani al. 2020 Li al. 2023), due to its close connection with some
cutting-edge research topics, including the understanding of over-parameterized neural network through the neural tangent kernel (Jacot et al. 2018 Chizat et al. 2019) and large-scale kernel learning with gradient descent (Lin & Zhou 2018 Xu et 2021). It is of fundamental importance provide theoretical explanations of their behaviors under these research topics.
In literature, some recent works show that the learning rate kernel-based methods is actually affected by both the model complexity of the considered reproducing kernel Hilbert space (RKHS) and the target-kernel alignment, a measure to quantify the similarity between the considered RKHS (or kernel matrix from the empirical point of view) and the target function, which is also known as the smoothness of a target function in the RKHS (Caponnetto De Vito 2007 Smmal & Zhou
Xin He and Yuwen Wang are the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

2007). Particularly, the existing learning rate for the kernel ridge regression (KRR) is proved to be for S S 1, where y is known as the source condition parameter (Cui et al. 2021) and can be treated as measure of target-kernel aligmment at the population level, and ar controls the model complexity of the RKHS. This rate aligns with the intuitive sense that strong alignment and small model complexity contribute to faster learning rate. Yet, with the increasing in such
On 20ny
that 7 >>> 1 which corresponds to a smoother target function, the best learning rate of KRR plateaus
Caponnettoo & De Vito 2007). This phenomenon is known as the saturation effect (Bauer et al. 2007 Li et al. 2022) and is widely observed in many applications (Bauer et al., 2007] Gerto et al. 2008). It has been conjectured for decades that no matter what carefully chosen tuning parameter, the learning rate of KRR plateaus when the smoothness of the target function exceeds certain levels. Most recently, Li et al. (2022) establishes the rigorous saturation lower bound of KRR that confirms practical conjecture. |Amini (202T): : /Amini et al. (2022) propose a truncated KRR based kernel matrix, and further prove that as the alignment becomes stronger, the truncated KRR can be consistently improved in terms of the expected mean squared error and eventually tends to the parametric rate. Clearly, this improvement effectively tackles the saturation effect for the KRR where the squared loss is specified. Yet, it is still unclear whether the saturation effect can be solved for the general kernel-based methods where the specified loss function belongs to a rich loss function family.
at (n 2
on the spectral-truncatie
In this paper, motivated by this theoretical gap, we investigate the impact of target-kernel alignment from the kernel complexity perspective for various kernel-based methods by considering a general loss function which belongs to rich loss function family. Our established results shed light on the statistical benefits of the truncated estimator and are also verified by extensive numerical experiments. We want to emphasize that in contrast to the existing works that focus on the KRR benefit from the analytical solution and thus their theoretical analysis heavily relies on the closed form of the solution to establish some critical results (Cui et al. 202 I Amini et al. 2022), the explicit solution does not exist anymore in this paper, which requires different technical treatments to conduct the theoretical analysis. Specifically, our theoretical analysis crucially relies the kernel complexity
which quantifies the complexity of the RKHS (Bousquet & Herrmann| (002) and some empirical process techniques. The established results successfully capture the trade-off between the complexity of the truncated RKHS and approximation bias as presented in Theorem 4.2] A simpler bound when considering the polynomial case in Corollary 443 further indicates that with a carefully chosen truncated space, the truncated method can efficiently eliminate the saturation effect. More importantly, we establish the minimax lower bound when the squared loss is specified, and thus rigorously confirm the conjecture in Amini et al. (2022), stating that the truncated KRR attains minimax optimality.
1.1 Contributions
The main contribution of this paper is to offer a unified analysis and a comprehensive understanding of the impact of target-kernel alignment, and provide theoretically guaranteed solution to eliminate the phenomena of saturation effect. Some of its contributions are listed as follows.
(i) By leveraging the kernel complexity function, we establish the upper bounds for both the standard kernel-based estimator and the truncated estimator for general loss function belonging to a family of Lipschitz loss functions. The established bounds indicate that with the variation of the alignment level, the learning rates for these two estimators exhibit distinct trajectories. Specifically, under the polynomial decay assumption, when alignment is at a lower level, the standard kernel-based estimator and the truncated estimator share the same learning efficiency and improve with the rise in alignment level. Yet, when the alignment level surpasses a threshold (7 = 1 in Assumption 3.2), the learning rate of the kernel-basee estimator plateaus with no improvement as y increases - a phenomenon known as the saturation effect in literature. As opposed, the learning rate of the truncated estimator exhibits continuous improvement with the increasing alignment level, thus eliminating the saturation effect. This indicates a significant improvement in the truncated estimator over the standard kernel-based estimator.
(ii) By employing the standard Fano method, we establish minimax lower bound when the squared loss is specified, indicating that for both the just-aligned and weakly-aligned regimes, both the standard kemel-based estimator and the truncated estimator achieve minimax optimality. Furthermore, for the strong-aligned regime, we demonstrate that the standard kernel-based estimator can only attain sub- optimality, while the truncated estimator is also minimax-optimal. Our minimax analysis significantly

---

extends the existing results presented in Yang et al. (2017). offering unified perspective for realistic scenarios where the true target assumed reside the RKHS.
(iii) Various numerical experiments are conducted in the context of various regression and classifica- tion problems to demonstrate the advantages of the truncated estimator, to support the established theory substantially. More interestingly, we also empirically verify the existence of a tradc-off arising from the model complexity of the RKHS and target-kernel alignment.
1.2 Related Work
Kernel-based methods have been widely studied for the past few decades, and are known as the time- proven efficient tools for statistical analysis. The theoretical behaviors of the kernel- -asedd estimator have been established in Caponnetto & De Vito (2007): [i et al. (2007); |Smale & Zhou (2007); PPale & Chouhan (2013). The concept of target-kernel alignment has been introduced in Cristianini et al. (2001), where a classification algorithm is developed adapting to the target-kernel alignment with a significant improvement in classification accuracy. Follow-up works have expanded the concept of targe-kkenel alignment to some other learning tasks, including regression (Kandola al. 2002) and multi-class classification (Guermeur al. 2004). The implications of target-kernel alignment have also inspired some applications to spectral kernel learning (Hoi et al. 2006), and feature selection (Wong& & Burkowski] 201T).
Most recently, many works have attempted to provide a theoretical understanding of the kernel-based method by considering the target-kernel alignment. Specifically, Canattr et al. (2021) investigates the generalization error of KRR and derives an analytical framework for the generalization error that captures the effect of the target-kernel alignment. Ammini (2011) considers a spectrally truncated KRR and demonstrates that with a carefully chosen truncation, the truncated KRR outperforms the standard KRR. Li al. (002)) verifies the saturation effect observed behind the KRR estimator by establishing a lower bound that O(n 2n whatever the smoothness degree of the target function is. Motivated by these works, Amini al. (2022) further demonstrates the non-monotonicity of the regularization curve for the bandlimited alignment setting and further reveals that the learning rate of the truncated KRR can be consistently enhanced as the degree of target-kernel alignment increases.
2 Preliminaries
Background on RKHS. Let HK denote the reproducing kernel Hilbert space (RKHS) induced by a positive semi-definite kernel function K(.,-) X' X' P R+, where X' C RP. The inner product equipped with Hx is denoted as (.,)) k with the endowed norm || 11% = .). For each x E X. is well-known that Kx := K(x,,) E HK and the reproducing property holds that (ʃ, Kx,,K)) for all f E Hk. We assume that supx.x'ex K(x, x') I k² for some positive constant k. This condition is commonly assumed in literature and various popularly used kernel functions satisfy this condition, including the Gaussian kernel and Laplacian kernel.
fx)
Problem setup. We consider a collection of pairs {(x;, 11) where {x, is a collection of covariates and the response Y; is independently drawn from a conditional distribution PY|x, on Y R. Throughout this paper, we focus on the fixed design setting, where { are fixed, otherwise we treat all the random quantities as conditioning on {x, A similar treatment also appears Yang et al. (2017); Wei et al. 2017); Amini al. (2022).
In the literature of machine learning, the learning task is often defined with some pre-specified loss function. Specifically, quantifies the inaccuracy for predictor f(x) when y is the true response. Then, the population risk function can be defined as
consider a loss function I((,-) R x R R+, where L(y, (x))
I
n In Σ L(Y..
:=f)==Ey>
where Ey denotes the expectation taken over YI...., Y,. In literature, the target function of interest in the learning task is typically defined as the minimizer of the population risk f argmin, &()). In this paper, we assume f E Hx and consider a family of loss functions that L, is assumed to be convex and locally Lipschitz continuous in the second argument (Wainwright 2019 Dasgupta et al. 2019). Here, locally Lipschitz continuity is specified as that for any b 0, there exists some
3

---

positive constant Mz. such that for any E 3 and x A, and for any f.f' E Hx satisfying the following inequality holds;
max [Iffl II 1 [
[L(
L(v, f' (x)) & ML,lf((x) fx)))
It is worth pointing out that the local Lipschitz continuity is satisfied for variety of commonly used loss functions, and some of them are listed in Table
Table 1: Different losses with corresponding Lipschitz constant Ml.b
Loss
Squared
Exponential
Check
Hinge
Huber
Logistic
ML.6
20 + 20r
1
1
1
Note that the choice of the loss function task-specific based on the problem of interest and prior knowledge the data. For instance, under the regression setting, the squared loss can be specified for mean regression and the check loss can be specified for quantile regression. Under the classification setting, the hinge loss can be specified for margin- bassd classification and the logistic loss can be specified for estimating the conditional probability.
3 Standard Kernel-based Method
In the rest of this paper, we use lowercase letters {1/ )= to denote the observations of {Yi) and denote the empirical measure of {x,, "ii,....,,,,, x, by In.. Given an estimator ʃ. its accuracy can be
evaluated by the ((IP,))-rn which is defined as I|f f [| (i - f (x,))². We also use the excess risk that E()) E()*) as an evaluation measure. To estimate the underlying target function f", we consider the following penalized empirical risk minimization problem that
f = argmin (E(f) + Allf 1
(1)
JEHK
where E(f) = - My, f(x)) and is regularization parameter. We define a sample operator
Sx MkK + R" as Sx(f) = J (f(1). T(x,))T, and its adjoint operator SX R + Hx is defined as
1 (a) Vn
Σ 0 K (1, xj), a (an,..., an) E RR.
Then, by the representer theorem (Kimeldorf& & Wahba 1971), the minimizer of the learning task (I) must have finite form that ʃx = Sx (āx) where â E R" the solution to the following optimization task
= argmin (E(SI(a)) + Xa Ka). aER"
Let K [X,(x,, x))} } be the empirical kernel matrix where the scaling is for analytical simplicity. the subsequent analysis, we further assume that K positive which also required in literature (Liang & Rakhlin 2020; Amini et al., 2022). Then, the kemel matrix K admits an cigen-decomposition that and D E R Ra*= is diagonal matrix with positive elements #1...., Un arranging in a descending ordering. Without of loss generality, we further require that μ4j as oc.
UDU where
(u1 u,) Rax= is an orthonormal matrix
Let E" T (x").. The elements of the vector Amini et al. 2022), which quantify the agreement level between f* and K. Intuitively, a more
referred to target alignment (TA) scores
2 ML.& & is constant with possible dependence on 6.
3 FFor squared loss, assume that y C -U,U]. U.. which commonly adopted literature learning theory Barrlett et al. 2005) [Smale & Zhou 2005 2007 Wei al. 2017).
is the threshold parameter for Huber loss.

---

favorable learning rate can be achieved if the target and kernel are strongly aligned corresponding to fast decay TA scores. For example, the scenario that Sx()" is predominantly situated in the space generated by the eigenvectors corresponding to the first several eigenvalues of K indicates a strong alignment. In other words, Ej expected to be as large as possible for small j and as small as possible for large j. An ideal scenario that Sx((*) exactly matches the eigenvector u, leading In this paper, we are devoted to providing an analytic framework for the impact of alignment on the performance of the kernel-based methods based on the kernel complexity of K.
to -- (1, 0, .... 0) T with proper scaling such that Ilf 1|2
3.1 Technical Assumptions
The following necessary assumption is needed in our theoretical analysis. Assumption 3.1. There exist two constants < cu S c such that
calls 1 < E() E(f) S 6615-
for any Hx satisfying |l
1l S b with some sufficiently small constant b 0.
The first inequality in Assumption 3.1 is a co-locally strong convexity condition, and the second inequality is co-local smooth condition of the loss function with respect || -Il.. Assumption
3.1 is commonly assumed in literature (Steinwart & Christmann, 2008 Wei et al. 2017 Li et al. |arrell Farrell et al. (022T) Due space limit, some brief discussions are provided below. For the squared loss, Assumption 3.1 is satisfied with co = c = 1. For the check loss, the co-locally strong convexity condition is slightly more relaxing than the similar assumption in the literature (Lian 2022
that requires the conditional density function of the noise term to be uniformly bounded away from zero. And, the co-local smoothness condition holds if the conditional density function is uniformly bounded. Other widely used loss functions including Huber loss, Logistic loss, Hinge loss, and exponential loss also satisfy Assumption 3.1 under some mild conditions as discussed in Appendix F
Assumption 3.2. There exist some constants y 2 1 and u 2 2 such that Σ}=1 EG² py 27 S u² for any n.
2
Assumption 3.2 imposes the regularization on the TA scores 5* concerning K. Note that the parameter
reflects the degree of target-kerne kernel alignment, where a larger y indicates stronger alignment between
K and f Moreover, the parameter y in Assumption 3.2 can be considered analogous to the source condition parameter under the random design setting (Caponnetto & De Vito [007] Cui et al. [02T]]
Li et al. 2023). Further discussions on the extension to the random setting are deferred to Appendix In our subsequent analysis, we consider the following three cases that
Just-aligned regime: 7 1/ where we only assume f" AK.
Weakly-aligned regime: 1/ < 7 S 1 where f" E Hx and is more aligned with K. Over-aligned regime: 7 > where f E HK and has a strong alignment with K.
3.2 The Upper Bound for Standard Kernel-based Method
In the rest of this paper, we use c, C' to denote some constants independent of n, 7, which may hide the constants such as u, Co, cb and whose values may vary from line to line. literature, the empirical kernel complexity function is defined as R(6) == / Σn= min Bartlett et al. 2005). R(8) serves as measure of complexity of Hx and is closely connected to local Rademacher complexity (Bartlett et al.) 2005 Steinwart et al., 2009). It plays a crucial role in establishing our theoretical results via the critical radius 8,,, defined as the smallest positive value 8 such that
Clog L RR()) S Co g2
(2)
where 7 = min(7; 1, 1} and i is specified the subsequent theorems and corollaries. The learning
rate of the kernel-based estimator defined in (I) highly depends 5n. and the existence and uniqueness of 8n are verified in Appendix B.I As pointed out in Yang et al. (2017). the statistical
dimension is defined as the first index for which the associated eigenvalue μ3 drops below 8 that
d(o) ;= min{j E [n] Mj < 82). where [n]] = 2,,2,.. n2) and d()) == if (j E [n]] μj 82} 0.
5

---

Note that the statistical dimension serves as measure of the intrinsic dimension of the kernel matrix K. Moreover, a kernel is regular if the tail sum of its eigenvalue sequence can be well bounded as the form +1 Mi X d(6)8² (Yang et al. 2017). Note that kernels in the kernel class with the polynomial or exponential decay in their eigenvalues are regular. Then, the kernel complexity can be well approximated by v (d(0))%/n. The close connection between d(o) and R((5) enables us to find the explicit formulation of 6, our theoretical analysis.
The following theorem provides theoretical guarantees of fx defined in I in terms of ((P,))-ero)) and the excess risk which hold with high probability.
Theorem 3.3. Suppose that Assumptions 3.7 and 3.2 are satisfied and 6 S < min(7, 1}. Then, for any E (0, 1), with probabilliy at least 1 there holds
Let 1) =
max {1IA 1 E(Zx) - -((') C(5 + )
The proof of Theorem 3.3 is provided in Appendix C To complete the proof of Theorem we
only need to require the first inequality in Assumption 3.1 Note that the established bound for fx
consists of two terms that are related to the critical radius 6n and the parameter X. Compared to
the existing works (Yang et al. 2017: Amini et al. 2022) under the fixed setting where only the squared loss is considered, Theorem 3.3 provides a comprehensive theoretical analysis on various kemnel-based estimators by considering general loss function with the help of kernel complexity and also considers the effect of the target-kernel alignment on the estimation performance under different aligned regimes. Moreover, we notice that with the choice of À satisfying x 6% an optimal rate can be achieved that
E(AA) - E(f 1
Note that Amini al. (2022) provides some valuable insights into the learning rate of the kernel-based estimator under the squared loss in terms of the expected -error where the following polynomial decay condition is required.
Assumption 3.4. There exist some constants a > 1 and y 2 such that the eigenvalues of K and the TA scores exhibit polynomial decay rate that
x ja and E3² 27a-1
In Assumption 3.4 the parameter controls the complexity of H.K in the sense that a decreasing a results in the increasing compacity the RKHS HK (Cui al. 2021; Amini al. 2022). Various widely used kernels, including the Sobolev kernel and the Laplacian kernel, belong to this class. Note that with slight modification by setting E)² x j-ya--111000 (log.) -2, it can be verified that Assumption 3.4 directly leads Assumption 3.2 if ignore the logarithmic term.
By Assumption 3.4. it is clear that d(0) = 8-2/ and consequently 82 x (1logg -12 3 To better understand the established results in Theorem 3.3
n the following corollary is also provided.
Corollary 3.5. Suppose that Assumptions
3.7
3.2 and 3.4 are satisfied. Let n min(7, 1}. For any
1. E (0, 1). if we choose X x [log.
FI then with probability at least i, there holds
E(p)) - -(f') x 11 - 1 S o (log
2na
2no+1
Under the just-aligned regime that = 1. the learning rate turns to be ((log 11) /2)2//)))) पीं which consistent with that in literature (Wei et al. 2017) where merely assumes f E HK. Yet, under
the weakly-aligned regime that <<> < 1, the learning rate exceeds ((oog=1)3²)
पम due to the alignment. More interestingly, under the over-aligned regime that 7 > 1, the learning rate plateaus with no improvement as y increases, which indicates a saturation effect for the standard semellbased method. It is also interesting to notice that no matter how the choice of 20
stronger
X, the learning rate is always lower bounded by On z for 2 1 (Li et al. (022). In the next section, we will show that a careful choice of truncation allows us to construct an estimator based on a reduced RKHS that achieves the best rate and mitigates the saturation effect for 1.
'Note that we assume X < as the theoretical choice of À typically depends on n and is close to zero for sufficiently large n.

---

Truncated Kernel-based Method
To construct the reduced RKHS, we introduce collection of functions (ehhkeenl HK. defined as 4/ : argmin { [| k : v H Sx(b) = }z}- It can verified that (sh keem is unique and by the orthogonality of U1,.., U2. we also have (v,, 45)n for i = and otherwise (Amini et al.) 2022). Then, for a given r, we define a function space as
ouet a (a),....a)) ar) E
HK.
Let Hk, be equipped with the norm |l = (f.f)k,, where the inner product is defined as (f.gkk. == Ei Bx/4/ for f -i= og and g - Ei= Surh2. The following lemma from Amini al. (2022) indicates that Hk, is also an RKHS associated with a different kernel function.
Lemma 4.1. HK, C HK is an r-dimensional RKHS with reproducing kernel Kr (x, x')
Ex=1 (x0%
Clearly, HK, can be treated as relatively smaller function space compared to the full RKHS HK. Based on HK,, we can find truncated kernel-based estimator by solving
Bar argmin (E() + )11 JEHx,
For the truncated RKHS HK. we also define the operator ST : R² - HK.
$I = Σ 1=1
a,,K(()))) a = (ai...,, E R
Then, by the representer theorem (Kimeldorf& & Wahba 1971 again, fx. also has a finite solution that Pa. = - ( and &, can be obtained by solving the following optimization task
a argmin (E(SI, (a:) Aa ATTT...... K.a).
QER"
where K, --= 1 x,) x,)}" i,j=1 the empirical kernel matrix w.r.t. Ky. Note that the truncated method does not impose an additional computational cost compared to the standard kernel method, and its detailed discussion will be provided in Appendix B.5 By the construction of {+tx (e))) is easy to verify that K, UD, where D, is diagonal matrix with elements 1l. "i....s Pr, 0, ...,
detailed proof can be seen in Appendix B.2 This further implies that K,- = K when r = and thus leads to (x,) = FA.n(x,) for each i [n].
4.1
The Upper Bound for Truncated Kernel-based Method
Given the truncated RKHS Hk,,, our theoretical results below rely on the truncated kernel complexity function, defined (0) / Σ₁ (12, Moreover, the critical radius بn, can be defined as the smallest positive value 8 such that
Clog R (6)
Co 520+1 2
The existence and uniqueness of on,r are verified in Appendix B.1 It can be verified that (,) < R(8) and thus leads to ,n, I 8n- This observation indicates a potential improvement of the truncated estimator farr and is the core of our theoretical analysis. The following theorem shows that πx.- converges to the underlying target in terms of the L(P,) L(P,))-eroor and the excess risk with high probability.
Theorem 4.2. Suppose that Assumptions 3.1 and 3.2 are satisfied and max maxx Ej-441 S A < 1. Let n = minfy, 1}. Then, for any i (0, 1), with probability at least i, there holds
max fr 1', -(Fx,)) - E(f+)} < C( + X +
7

---

The proof of Theorem 4.2 is provided in Appendix D The established upper bound of fx.- first decomposes the total error into two components: estimation error (the first two terms), which is controlled by complexity of the reduced RKHS Hk.. and approximation bias (the last term), which results from the dissimilarity between the truncated RKHS HK, and the full RKHS HK where f" belongs to. Specifically, smaller value of reduces the complexity of K... possibly leading to more favorable estimation error. Yet, amplifies the gap between Hk. and HK and may lead to an extra approximation bias which may be significantly large. Clearly, can be regarded as trade-off' parameter that balances the approximation bias 2j=r+1 S and the estimation error o4 + A It
is clear that if r n, the approximation bias is zero and the upper bound of fx.n recovers that of fx. This implies that with careful choice of r, the truncated method at least performs as well as the standard estimator. If Assumption 3.4 also holds, we can conclude that Σj=r+1 5) 2 r--- 2y0
I [r<n)-
Then, the best choice of and À achieve an optimal rate is given by r = 2/(((a) if y > 1;r=
if 2 y 1, and À x pr. Accordingly, there holds
E(fxr)- E(f)) 1f,
For the comparison of Corollary 3.5 we also establish the following corollary for Jx.-- Corollary 4.3. Suppose that Assumptions [-
3.1 3.2 and
3.4 are satisfied. For any & E (0, 1), if
we choose À x [logg _12 probability at least L, there holds
and x (logı 1ya 27041 [6211) + nnssssspp then with
8(Ax)) - 1 - 1 S <0( (log 109
20a 250+7
Clearly, under the over-aligned regime that y > 1, the truncated estimator Fx,r can achieve a faster learning rate compared to fx: for S y S 1, the trivial choice of r is optimal and fx. shares the same learning rate as fx. More impressively, the learning rate of fx,- can be continuously increased with the enhancement of the target-kemell alignment, thus eliminating the saturation effect. Note that as y > 0o, the learning rate of fx.r approaches 1 a' meaning that the truncated estimator can successfully capture the strong alignment to attain comparable rate to the parametric rate.
The connection between and d(o). Recall that for the regular kernel class, we have R(d) x v d(0)oz It can also be shown by simple algebra that (6) x vn min(r, d( (See Appendix D.3 for details), Particularly, for the kernel class with polynomial decay, we have d(0) x 8/2/a, Once the critical radius ón is determined for specified kernel matrix, we denote dn = d(Sn,r) 8-2/a and take x 20/n)(1a)) to balance 8:1 and 22y Consequently, we obtain r dM//1, Such relation between and d, is very reflective and provides theoretical insight into why the truncated estimator is more efficient under a more aligned situation. Specifically, for the case y 1, it is clear that x 2/77 < dn, and have
(5 x V n 1,,, < V d = R(6n.))
As result, the truncated kernel complexity is substantially reduced compared to R(Bn,r), leading to an improved learning rate. On the contrary, for the case that S 7 S 1, we have x dn and (6,,r) invariant as decreases. To avoid introducing additional approximation bias, the best choice of truncation level turns be n.
n d, nrr x R(,n,r), which indicates the truncated kernel complexity remains
4.2 Minimax Lower Bound
In this section, we establish the minimax lower bound under squared loss based the Fano method (see Chapter 15 in Wainwright/ (2019) for more details). For r 2 2- we consider the space within a
ball H%s- {f E HK Σラ= E,² "pz -27 < u²) where E, are the TA scores associated with f.
8

---

Theorem 4.4. Suppose that the RKHS is induced by the regular kernel, and f is any estimator based on the data (x),))))==- If S Y S 1, we have
P(II - M c5 1
inf sup f S
If > with the choice of satisfying d(()!)) d((dnr)) ), we have
inf f MERA
sup
P(I - l 2 2 cd n.r 2
The proof of Theorem 4.4 is provided in Appendix For y > 1, the condition d(ol.)) s d((m.r) can be easily verified for the most popular polynomial decay case that My ja. Specifically, for the kernel class with polynomial decay, we have d(6) x 00-8822// 2/a, which leads
d( d(o2/7)) x 8/2/a < 8-2/1a x d(on.r)
Moreover, it can be seen that x 8n." 2/7a is the optimal choice, aligning with the optimal choice in the upper bound. Note that is common establish the upper bound for the other loss function and compare it to the lower bound established under the squared loss to check the optimality (Wei jet al. 2017 Lv al., 2018 Li h By comparing the lower bounds in Theorem 4.4 with the
achievable rates from Theorems 3.3 and 4.2 we can conclude that under the case that S S
both the standard kernel-based estimator fA and the truncated estimator Fx.r is minimax-optimat More importantly, under the more challenging case that y > 1, fx can only achieve a sub-optimal rate, whereas Fx,r can attain the minimax rate long as r d(o))/7) < d(ôn.r), suggesting that the truncated kernel-based method can be treated as optimal tackling. It is also worthy pointing out that under the just-aligned regime that y 2- Yang et al. (2017) derives the minimax lower bound by considering the regular kernel class, and Theorem extends it to the more general setting by allowing 7 2 2'
Numerical Verification
Our established results indicate that larger corresponding to a lower model complexity of the RKHS leads to a better rate. As opposed, a smaller model with lower complexity simultaneously may result in potential mismatch between the model space and the target. This may weaken the target-kernel alignment which undermines the learning efficiency. Consequently, a trade-off exists between model capacity and target-kernel kernel alignment y, with preference for relatively lower model complexity and stronger target-kernel alignment.
To illustrate this, we conduct some numerical experiments to study how the RKHS with varying model complexities affect the numerical performance of KM and TKM. Specifically, we use the spline kernel with order that Ka (x, x') = > ko-
-2wákx - (Wahba 1990), where a controls the model complexity of the induced RKHS at the population level. Morcover, we consider the nonparametric quantile regression that
Y= = f"x) ole (-)( i I,.,,
where (x) K3.5 0) sin( a= 2, N(O,1) 1), (x, ) are independently sampled from the uniform distribution on (0, 1) and & denotes CDF function standard normal distribution. We conduct the numerical experiments by varying 7 {0.3, 0.5, 0.7) and a {2, 4, 6, 8, 10} with fixed n = 300, The data generating scheme is repeated for 50 times and all the tuning parameters are tuned to the best for both methods. The obtained results are presented in Figure
From Figure [ we can conclude that the smaller a, corresponding to richer RKHS and potentially stronger alignment, results in significant improvement in TKM over KM. Conversely, the larger a, corresponding to smaller RKHS and potentially weaker alignment, results in a comparable performance for these two methods. This observation precisely aligns with our theoretical results. Clearly, based on our theoretical findings, the experiment results verify the existence of trade-off between the model complexity and target-kernel alignment, indicating that carefully data-driven

---

-00
r=0.3
r=0.5
r=0.7
-12
-1.2
-15
-16
-16
TIH KM
91
T=0.3
T=0.5
T=
-17
-2.6
-3.75
188
-1.00
Log ampriical
Log empirica
-3.85
TEM
2.0
Figure I: Averaged log MSE and log empirical excess risk for KM and TKM versus for different т.
choice of the kernel may be necessary to achieve better learning efficiency. We defer the deeper exploration of data-driven selection of an appropriate kernel to future research endeavors.
The real data analysis deferred Appendix [A] Furthermore, a variety of additional experiments are presented in Appendix H The obtained results are discussed in detail, which further supports our theoretical findings.
Discussions and Conclusion
6.1 Comparison and Discussions
Amini et al. (2022) studied how the target-kernel alignment affects both the standard KRR and the truncated KRR. Although our work is motivated by Amini al. (2022), especially for the
methodological aspect, there exist significant differences between our established results and those in Amini et al. (2022), and some are summarized as follows: (a) Amini et al. (2022) only focused on the upper bounds in terms of expected mean squared error, while our results provide more precise high-probability upper bounds. (b) Beyond the polynomial decay condition considered in Amiiii et al.. (2022), we introduce a more general condition as stated in Assumption 3.2, This condition involves y, reflecting the degree of target-kernel alignment. (c) In Ammiii et al.) (2022). both the standard KRR and the truncated KRR have explicit solutions. This allows leveraging analytic solutions to establish critical results, without requiring more advanced techniques. In contrast, no explicit solutions exist in our case and our theoretical analysis adopts an alternative analytic treatment by utilizing kernel complexity and empirical process techniques. (d) Last but not least, we rigorously confirm the conjecture in Amini et al. (2022) asserting that the truncated KRR can achieve the minimax optimality for all y 2
6.2
Conclusion and Future Work
This paper provides comprehensive theoretical understanding of the properties of the truncated kernel-based method for a broad family of loss functions. By using kernel complexity and empirical process techniques, the established results reveal some significant benefits from the truncated RKHS and indicate that a carefully chosen truncation allows for an optimal trade-off between the model complexity and approximation bias. Extensive numerical studies further justifyy our theoretical findings, demonstrating a consistent improvement of the truncated estimator over the standard kemne-- based estimator. We also derived an algorithm-fre minimax lower bound that matches the upper bound on the truncated estimator and therefore confirmed its optimality. To some extent, our results shed light on future research in statistical learning theory and real-world applications. This paper also leaves several interesting open questions for future investigation, including the theoretical explorations under the misspecified setting that 0 < 7 < 2 and how to develop a data-driven algorithm for selecting atoogly-alignee kernel with lower model complexity.
10

---

Acknowledgements
CW's research is supported by the Fundamental Research Funds for the Central Universities. XH's research is sponsored by Natural Science Foundation of Shanghai (SZZR1421400) NSFC-11901375. Shanghai Science and Technology Development Funds (23JC1402100) Program for Innovative Research Team of Shanghai University of Finance and Economics and Shanghai Research Center for Data Science and Decision Technology. JW's research supported part by HK RGC Grant GRF-14303424 and CUHK Startup Grant 4937091.
References
Amini, A., Baumgartner, R., & Feng, D. (2022). Target alignment in truncated kernel ridge regression. In Advances in Neural Information Processing Systems (pp. 21948-21960), Curran Associates, Inc. volume 35.
Amini, A. A. (2021). Spectrally-truncatedd kernel ridge regression and its free lunch. Electronic Journal of Statistics, 15, 3743-3761.
Bartlett, P. L.,, Bousquet, O., & Mendelson, S. (2005). Local rademacher complexities. The Annals of Statistics, 33, 1497-1537.
Bauer, F., Pereverzev, S., & Rosasco, L. (2007). On regularization algorithms in learning theory. Journal of Complexity, 23, 52-72.
Belkin, M., Ma. S., & Mandal, (2018). To understand deep learning we need understand kernel learning. In International Conference Machine Learning (pp. 541-549). PMLR.
Belloni, A., & Chemozhukov, V. (2011). 1). 4 1i-penalized quantile regression in high dimensional sparse models. The Annals of Statistics, 39, 82-130.
Bousquet, O. (2002). A Bennett concentration inequality and its application to suprema of empirical processes. Comptes Rendus Mathematique, 334, 495-500.
Bousquet, O., & Herrmann, D. (2002). On the complexity of learning the kernel matrix. Advances in Neural Information Processing Systems, 15.
Breiman, L. (2001). Random forests. Machine learning, 45, 5-32.
Canatar, A., Bordelon, B., Pehlevan, C. (2021). Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12, 2914.
Caponnetto, A., & De Vito, E. (2007). Optimal rates for the regularized least-squares algorithm. Foundations Computational Mathematics, 7, 333--636.
Chizat, L., Oyallon, E., & Bach, F. (2019). On lazy training differentiable programming. Advances in neural information processing systems, 32.
Cristianini, N., Shawe- Saylor,aylo,, J., Elisseeff, A., & Kandola, J. (2001). On kernel-target alignment. Advances in Neural Information Processing Systems, 14.
Cui, H., Loureiro, B., Krzakala, F,, & Zdeborová, L. (2021), Generalization error rates in kernel regression: The crossover from the noiseless noisy regime. Advances Neural Information Processing Systems, 34, 10131-10143.
Dasgupta, S., Goldberg, Y., & Kosorok, M. R. (2019), Feature elimination in kernel machines in moderately high dimensions. The Annals of Statistics, 47, 497-526.
Farrell, M. H., Liang, T., & Misra, S. (2021). Deep neural networks for estimation and inference. Econometrica, 89, 181-213.
Gerfo, I.., Rosasco, I.., Odone, F,, Vito, E. D., Verri, A. (2008). Spectral algorithms for supervised learning, Neural Computation, 20, 1873-1897.

---

Ghorbani, B., Mei, S., Misiakiewicz, T., & Montanari, A. (2020). When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33, 14820- 14830.
Guermeur, Y., Lifchitz, A., & Vert, R. (2004). A kernel for protein secondary structure prediction.
Hoi, S. C., Lyu, M. R., & Chang, E. Y. (2006). Learning the unified kemell machines for classification. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 187-196).
Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31.
Kandola, J., Shawe-Taylor, J., & Cristianini, N. (2002). On the extensions of kernel alignment. Technical report 120, Department of Computer Science, University of London,
Kimeldorf, G., & Wahba, G. (1971). Some results on Tchebycheffian spline functions. Journal of Mathematical Analysis and Applications, 33, 82-95.
Lai, J., Huang, Lin, Q. et al. (2024). The optimality of kernel classifiers in sobolev space. The Twelfth International Conference on Learning Representations.
Li, Y., Liu, Y., & Zhu, J. (2007). Quantile regression in reproducing kernel Hilbert spaces. Journal of the American Statistical Association, 102, 255-268.
Li, Y., Zhang, H., Lin, Q. (2022). On the saturation effect of kernel ridge regression. In The Eleventh International Conference on Learning Representations.
Li, Y., Zhang, H., & Lin, Q. (2023). On the asymptotic learning curves of kernel ridge regression under power-law decay. In Thirtty-eeenthh Conference on Neural Information Processing Systems.
Li, Z., Ton, J.-F., Oglic, D., & Sejdinovic, D. (2019). Towards unified analysis of random fourier features. In International Conference on Machine Learning (pp. 3905-3914), PMLR.
Lian, H. (2022). Distributed learning of conditional quantiles in the reproducing kernel Hilbert space. Advances in Neural Information Processing Systems, 35, 11686-11699 1666.
Liang, T., & Rakhlin, A. (2020). Just interpolate: Kernl "ridgeless" regression can generalize. The
Annals of Statistics, 48, 1329-1347.
Lin, S.B & Zhou, D.-X. (2018). Distributed kernel-basee gradient descent algorithms. Constructive Approximation, 47, 249-276.
Lv, S., Lin, H., Lian, H., & Huang. (2018). Oracle inequalities for sparse additive quantile regression in reproducing kernel hilbert space. The Annals of Statistics, 46, 781-813.
Ma, C., Pathak, R., & Wainwright, M. J. (2023). Optimally tackling covariate shift in RKHS-basee nonparametric regression. The Annals of Statistics, in press, 1-38.
Patle, A., & Chouhan, D. S. (2013). SVM kernel functions for classification. In 2013 International Conference on Advances Technology and Engineering (ICATE) (pp. 1-9). IEEE.
Smale, S., & Zhou, D.-X. (2005). Shannon sampling II: Connections to learning theory. Applied and Computational Harmonic Analysis, 19, 285-302.
Smale, S., & Zhou, D.-X. (2007). Learning theory estimates via integral operators and their approxi- mations. Constructive Approximation, 26, 153-172.
Steinwart, I., & Christmann, A. (2008). Support Vector Machines. Springer Science Business Media.
Steinwart, I., Scovel, C. al. (2009). Optimal rates for regularized least squares regression. In Proceedings of the Annual Conference on Learning Theory, 2009 (pp. 79-93).
Wahba, G. (1990). Spline models for observational data. In CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM.
12

---

Wainwright, M. J. (2019). High High-dimensional Statistics: A Non-asymptotic Viewpoint volume 48. Cambridge University Press.
Wei, Y., Yang, F,, & Wainwright, M. J. (2017). Early stopping for kernel boosting algorithms: A general analysis with localized complexities. Advances in Neural Information Processing Systems, 30.
Wong, W. W., & Burkowski, J. (2011). Using kernel alignment to select features of molecular de- scriptors in QSAR study. JEEE/ACM Transactions Computational Biology and Bioinformatics, 8, 1373-1384.
Xu, P., Wang. Y., Chen, X., & Tian, Z. (2021). Coke: Communication-ccnsorrd decentralized kernel learning. Journal of Machine Learning Research, 22, 1-35.
Yang, Y., Pilanci, M., & Wainwright, J. (2017). Randomized sketches for kernels: Fast and optimal nonparametric regression. Annals of Statistics, 45, 991-1023.
Zhai, R., Pukdee, R., Jin, R., Balcan, M. F., & Ravikumar, P. K. (2024). Spectrally transformed kernel regression, In The Twelfth International Conference on Learning Representations.
13

---

Appendix
This appendix is organized as follows. In Section A we conduct a real data analysis. Section B devoted to providing more discussions and future directions. In Section C provide the proof
is
for results in Section 3 including Theorem 3.3 and Corollary 3.5 In Section D we provide the
proof for results in Section 4 in part, including Theorem 4.2 and Corollary 4.3 Section E
complement the upper bounds by deriving the minimax lower bound. In Section we discuss the locally strong convexity condition and local smoothness condition presented in Assumption 3.2 for various loss functions in detail. In Section G we list some useful lemmas utilized in our proofs, including concentration inequality, symmetrization inequality, and Gaussian contraction inequality. Section H provides additional experiments under various settings.
Notation. Denote the vector inner product (ax, B) = Ei= 0g and the norm ||l|| = V(a, 0)2 for a. B E R". For any integer m, we use [m] represent the set 21,2.... m] for short.
A Real Data Analysis
We apply both TKM and KM with check loss to the wine quality dataset, which is available in the UCI Machine Learning Repository. Specifically, we first adopt the random forest method (Breiman 2001) to rank the feature importance and select the first three influential features: 'Alcohol', 'Sulfates'' and Volatile Acidity' for analysis. Then, randomly select 500 samples for training and another 500 samples for testing. The above procedure repeated 10 times, where the Laplacian kernel K x(xx') exp(-l| xx is adopted and the parameters y and r are tuned by 5-fold cross-validation. The averaged MSE with different E (0.3, 0.5, 0.7) is reported in Table 2
Table 2: Averaged MSE for different methods
0.3
0.5
0.7
KM
0.590 0.027
0.483 = 0.035
0.638 + 0.073
TKM
0.548 0.026
0.454 + 0.045
0.530 + 0.046
is thus clear that the obtained results the real application align with the results for synthetic data and our theoretical findings in the main text, which further demonstrates the benefits of TKM.
B
More Discussions and Future Directions
B.1 Verification of the Existence and Uniqueness of 8, and 8n,
In this section, we provide detailed verification of the existence and uniqueness of 8n and pn, where 6, and 8, are defined as the smallest solutions to and (3), respectively.
For any (0, 1) and 7 1. define
2Clogg-1R(0 R(8) cy62
g(
5 E (0,
where 77 = max 1). Here, we ignore the dependence g on and y for ease of presentation.
The verifying argument is based on Lemma 3.2 Bartlett et al. (2005), which states that [0, oc) + [0, oc) is nontrivial sub-root function") then it continuous on [0, oo), and the equation (r) = r has a unique positive solution.
Recall that we assume (i..... Pn > O. From the definition of R()), it can be easily seen that R R(v)) is a nontrivial sub-root function. Then from Lemma 3.2 in Bartlett et al. (2005). R(V6) is continuous on [0, oo), and thus ( is also continuous on (0, oc). Note that g[ō]o 20 is nonincreaing on oc), then (5) must be strictly decreasing (0, oc).
"A function v is called nontrivial sub-root if ab ş 0, and it is nonnegative, nondecreasing and if (1(r) /0rl)/rra is nonincreasing for > 0.
14

---

If g( is always larger than 1 on (0, oc), we have
lim g66)024 oc, 60000
which is impossible since g(8)62n nonincreasing on (0, oo). On the other hand, if g( always smaller than 1 on (0, ox), then
lim g(d))") 6-0
=0
implying g(8)82n = since g is nonincreasing. Since R(6) is not trivial, this is also impossible.
Therefore, by the continuity of on (0, 1), the equation g(6) = 1 has a positive solution on that unique by the strict monotonicity of g. Note that by the strict monotonicity of g. 6n can be equivalently defined as the smallest solution to g(o) < 1. According to the definition of g, we conclude the existence and uniqueness of 6n For Sn. repeat similar argument, we can also verify its existence and uniqueness.
B.2 Decomposition of the Reduced Kernel Matrix
Recall that K, = K xy)] the empirical kernel matrix w.r.t. K,, and K UDU where U (u,, u,,) R is orthonormal matrix and D Rexn is diagonal matrix with positive elements ,.,, Mn arranging in descending ordering. Denote u, (Uk1:-.. Wkn) By definitions of K, and (1hx Jee[]] we have
Σ (x. Σ
(K))
On the other hand, recall that D, is diagonal matrix with elements 1.l. Mry O, ..., we have
(UD.U Di = Σ
DELUREURY
Σ Uauneuky = (K+)
k=1
Therefore, conclude that K, = UD.U
B.3 Extension to Random Design Setting
In this work, we investigate the effect of target-kernel alignment and provide the best solution to overcome the well-known saturation effect. It is also worthy pointing out that although the obtained results are derived under the fixed design setting. it may be possible to extend them to the random design setting and we leave it to future exploration. Some key steps of the possible extensions discussed below.
Under the random design setting, we consider random variable X p, where p is probability measure supported on X' R². Let the covariates [x, be independently sampled from p. Denote the space of square-integrable functions f X + R with respect to p as L(X p). where &' C R".
Recall that Hx is RKHS induced by a positive semi-definite kernel function K. By Mercer's theorem (see, for instance, Theorem 12.20 in WWinwwight (2019)). if X' is compact and K is continuous, combined with our bounded assumption that supx.x'xX K(x, x') S x²? the kernel function admits an expansion of form
DC K(X,X') = Σ (n 1=1
where j.y are the non-negative eigenvalues descending ordering and oú 's are the corresponding eigenfunctions in L(X, p). Given this expansion of K, the RKHS Hx can be written
Hx = {f= Σ
OjØ :
<
j=1
j=1
equipped with inner product (f.g) = Σ5=1
for f = = agoy and Σÿ= 310g.
15

---

Under the random design setting, the population risk function is defined as
E(f = EX f(X))
where Y x ~ Pr|x- Then, the target function f defined as
f == argmin E(f).
If assume f Hk, then f can be expanded as f === = with a- = (aj a2 ...)
satisfying 2j=1 a;- 80.
An assumption analogous to Assumption 3.2 under the random design setting is required that 2j=1 0j aj² H u² for some constants 2 2 and u. Here, 7 measures the target-kernel alignment at the population level, and is equivalent to smooth (or source) parameter in literature (Caponnetto) & De Vito 2007 Cui et al. 2021 Li et al. 2023). Note that if 2. merely assume that the target function J belongs to the RKHS Hk. and as y increases, the target function becomes smoother the RKHS HK-
Furthermore, the polynomial decay assumption analogous to Assumption 3.4 under the random design setting can be made as
By x and a₃
27a-1
with constants a > 1 and y 2 2- Note that the assumption is equivalent to condition (8) Cui al. (022T)
Grant these assumptions, the impact of the target-kernel alignment on both standard and truncated kernel-based methods under the random design setting can be analyzed by using the population kernll complexity, defined as
R(0)=
min min (82,ūy}
j=1
Since the theoretical derivation should be more deeply involved, we leave this promising topic to future investigation.
B.4 Connection with Spectrally Transform Kernel Regression
The spectrally transformed kernel regression (SKRR, Zhai et al. (2024)) aims to use spectrally transformation for constructing new kernel that can leverage information contained in unlabeled data in an explicit way. Note that we have shown that the truncated kernel method can overcome the saturation effect thanks to the reduced kernel complexity. We also believe that SKRR may able to overcome the saturation effect if the transformation function can be properly chosen. The possible routine for establishing the theoretical results briefly discussed below.
Recall that by Mercer's theorem, we have
06 Σ (x),())
K(x,''
For SKRR, ((x, x') is replaced with a new kernel that
K' K'
Σ (x),,,
where s(-) R+ + R is the general transformation function. Let Fx.a be the kernel-based estimator via the RKHS H induced by K'. The primary goal is to study how the prediction error | f 1/ depends on the choice of
The idea of deriving an upper bound on the prediction error is to separately bound the estimation error |lfx f3113 and approximation bias ||f f 1/3 where || || denotes the norm equipped
16

---

with ((X', p), and f= s()))) is introduced as an immediate function belonging to H. Following similar technical treatment in Section D the upper bound on estimation error can be established. For the approximation bias, by writing أÿ=1 a50z. we find that
[1 - 1 Σ (s(a7) aag
Clearly, the selection of s(-) is crucial and it is favorable if s(-) 1) is close to the identity function for small and decays extremely rapidly as j tends to infinity, such as s(βt) the truncated method. Then, SKRR with some proper choices of s(-) may achieve similar conclusions about the upper bound as we provided in the main text. We leave such a promising topic as potential future work.
PyI() corresponding to
B.5 Computational Complexity of Truncated Kernel Method
For simplicity, we focus only the mean regression task where the squared loss is specified. Note that the total computational complexity of the truncated KRR is composed of three parts. Specifically, in the first part, spectrally decomposing the kernel matrix K has the computational complexity of
O(n²). In the second part, the basis {sh hisker can be simply calculated by thx = u K Kx with
1 (K(x,x1), K(x,, x(x,x,,)) Vn
Kx
for each k [n], which also has (n computational complexity. In the last part, computing the KRR via the r-dimensional RKHS Hk. has computational complexity of O(nr²). To sum up, the overall computational complexity of TKM is O(n²). Solving the standard KRR also has computational complexity of O(n²), and thus the truncated KRR does not impose an additional computational cost.
C Proof of Results for Kernel-based Method
C.1 Error Analysis
For case of presentation, without loss of generality, we assume μy < for all j [n] in the rest of
this paper We start the error analysis by noting that for any f = S (a) Hx with R", have
II = |K all2 and || ||K
(
This transform from the C(P,)) and the norm RKHS to vector norm will be frequently applied in our proof.
Denote
9- = VnSx((() (f* (* Tx
Recall that the TA scores are the elements the vector
s- = (UTT)((*
UTa..
Vn
Define an immediate function
f = S (at) E Hx with a² = ud= R
fä can be viewed the best approximation of f the n-dimensional function space Ha, defined as
H, := 1== (()) a a R
"Otherwise, by the assumption μı + always have μu 1 for exceeding constant
17

---

To be more clear, by the orthogonality of U, we have
|| 1
q- vn Ka
|' 1 - u UDU a²
-IU - UDU at
- ||5" - - - ||5
DU - 0,
(6)
implying
(xx)) (xxx) for each E [n]-
Therefore, we obtain
- 1|l-~ = - for all I Hk
(7)
and
8(f) - -( 8(f) E(f)) for all Hk.
(8)
Furthermore, by applying 5 we have
|| || -D- -
UD "
UD - ||D -11/
By our assumption that μ1, S for j. one has
| I = [ 10-1/2g1 Σ 10
- Σ 1i 2 S u²
(9)
j=1
where the last inequality holds by Assumption 3.2 with y 2 2-
The construction of f* plays crucial role in our proofs. Intuitively, the kernel complexity function R(8) is defined at an empirical level (depends on the fixed points X1; XI...,,,) x,) plexity measure of finite space Hn, This poses a technical challenge as the true function f lies in an
and serves as a com-
dinensooaii function space, creating a mismatch with the empirical kernel complexity R(6). To solve this problem, we introduce the best approximation f of f in finite-dimensional function space H,, Our proof will first focus on deriving the upper bound on Ilfx - f and then move to [|A 11 by using the relation
Another advantage to consider the best approximation of f* instead of itself is that fa lies in the same space H.. f², allowing us express [[ f21 and [l f 13 in the term of the kernel matrix K according to (5). which is useful in the technical proof. To the best of our knowledge, this novel treatment establish theoretical results for the kernel-based estimator. the truncated estimator in Section D we will adopt a similar proof strategy to construct the best approximation 1 of f in the reduced space HK.-
the proof for
Based on the error analysis, we are ready to present the proof for Theorem 3.3
C.2 Proof of Theorem
Define the localized function class
Hn,b { Hn. I f=1lx S Sb..
n, 74 which will be specified in the proof. Without loss of Here, is constant independent of n, generality, we assume > 1.
For any (0, 1) and > define the auxiliary event
((c,6) = {(()) {(Ft) - [E(f) - E(ft)]] < C'log R(O) holds for any f E Hn,
where W( = 5-11| f 11- + || - l for > and f E Hn.s-
The following two lemmas crucial for proving Theorem 3.3
18

---

Lemma C.1. Fix any E (0, 1) and > 0. The event V(e, 6) occurs with probability greater than 1 1-4 L.e.
P(V((,))) 2 1
As demonstrated in the proof of Lemma C.1 is incorporated into the constant of the upper bound C' C'log Moog-"R(60)) R(6), meaning that C' depends on b.
Recall that 6n is the critical radius defined as the smallest solution 2
Lemma C.2. Let 1j min(7,1) On the event (i, Sa), with the choice of X satisfying 8 SA
we have
- - 1'1 S C (6 + +
where C a constant independent of n,, n-
Proof of Theorem 3.3
By applying Lemma C.1 have P(V(e, 5,)) )) 2 L. Together with Lemma and the relation (6. it holds with probability at least 1 that
| f 1| I1 < C (6 + 2²1).
which completes the proof for the C(Px)
For the excess risk, it immediately follows from Assumption 3.1
Accordingly, it remains to prove Lemmas and C.2
C.2.1 Proof of Lemma C1
Denote
D: E(f) -E(f) - E(ft))
Then, our goal is to prove that for all E Hn,
D S R())
If W = O, the above inequality naturally satisfied. Therefore, without loss of generality, we assume W (f, for all f Hn... It equivalent to proving that
[D] Wf,
A = sup SEHn.
& CC'log 1loog-11mm R(0).
By applying the triangle inequality, together with @ we find that for any f E Hn.b
fl - f llf b.
Let : u + b. According to our assumption for the loss function in Section 2 L(y: :) satisfies the Lipschitz continuity over the function class Hr,s5 with Lipschitz constant M r,5 in the sense that for any y V, X, and f E Hn,b, the following inequality holds:
Ly,, f(x)) - L(y, f' (x))) S Mx,sl/(x)- f'(x)).
For simplifying notation, we hide the dependence of the Lipschitz constant on L(.,)), by writing M M,
The remaining proof follows standard procedure: first bound the expectation of .A and then bound the deviation of from its expectation. Finally, we combine these two bounds to obtain the desired result.
Bounding [[AA). Let wi,..., wn (0, 1) denote the standard Gaussian variables, independent of
the data. To bound B[A], we employ the symmetrization technique in Lemma G.2 Specifically,
19

---

have
D
[|AA-
E8
sup
W 6(
(0)
V
E wT
- L(ve, ((x)))
sup
71
W(f.6)
(10) 2V2TMM
Ei= wx(f(x;) - -x(x)))
sup fCH.,b
(10)
Y8
W(S66)
where (i) follows from Lemma G.2 and (ii) follows from the fact that the loss function is M-Lipschitz
continuous and the Gaussian contraction inequality in Lemma G.3 To further derive the upper bound for the RHS of (IO). we consider the localized function class of form
F(6) ( (a): - 1 11 ||5 f41, a
Recall that f== 5x (at) and for any f E Hn,b. there exists a E R" such that f = Sx (a))
Define the vector 3 = DUT (a a²). Then, by applying 5). f E F(6) implics the constraints on (3 that
| 1 S 8. D 0011 S and
Further note that any vector satisfying these two constraints must belong to the ellipse class
B3
:= B (21,82....)) R"
s 2 with vs min [0,,11)]
Vj
Denote (Wi, wn) we have
E
sup /EF((6)
Σ wx()(x;)) /* (xx)))
E
sup vnl (w, U
Bee
E
sup vnl (w.B31) BEE
(i))
33
E
sup Vn BBEE
Σ m3
(186)
1 Σ Vj v2nR(0),
/2nE
V2n
(11)
where follows (w, UB) (UT w, B) and U (O, since UT is an orthogonal matrix, (ii) follows from Sauchy-Schwarz inequality, and (iii) follows from Jensen's 's inequality.
Note that [1 holds when considering the supremum rescaled function
F(8). For E Hn,s. by defining the
3 f + fd. W(f,0)
we have
|| - f$1
|| 121
8-1 1a1 + Il fF1 5
and
|| - ff
|| - fllk 8-111/
f711 + II f I
20

---

As result, f F(6). On the other hand,
Ei=1 wi (x([(xx)= - (+(x)))
E
= R
Σ ws w: (f(x)) M(x)))]]>
Wff.8)
which, combined with (10)
and implies
2v 2
M
E (x(x)) (x(() (xxx))
B
n -
E
sup SEH
W(f.8)
(12)
2v 2V2TMM M
Σ -x - SEF(O)
S <VVMMR())
sup
1
Bounding A E(A). We use the concentration inequality in Lemma G.1 bound A E[A)). For each i [n]] and any f E F(0), define 8j sxgn(f(x;) (x:)) if and 8j if j and let s (81,..,,,)) then have
lf(x,) (x,)) Σ sf(((x)) - fF(x)))
( (vs UB) S vn
a
82
n
Σ
vn
Σ vj = V2nl(d),
j=1
where (i) follows from the fact that U is orthogonal and Cauchy-Schwerr inequality. Consequently, for each E [n]]. we have
[(,. f(x,)) L(y,, f(x))) & (xx - f(x) s Mv22
where the second inequality follows from that L(yi, -) is M-Lipschitz continuous. In addition, for any f F(8), we have
M " (f(x)) - (x()))
E (L(s.. [ (x,)))
n
-f fl1
-M
= (B,
n2
82
S 2 max (E(m)
S 2M 2
Σ
2n22n (6).
Vi
Vj
By similar rescaled method, have
L f(xx)) L(ys, Fxx)))
M)f(x,) - (x,,)
W(S
W(,
-M]F(x;) -x*(xx))
S V2MnR(0).
and
1
L(y:, f(x,)) L(v,, (*(:))
)9
2
2 n
Σ
f(x,) ((xx)-((xx)) 2
72
8(f,8)
n
W(f
i=1
M
L,
(F(x;) 1²(xx)))
S 2M
21

---

Thus, the requirements in Lemma G.1 hold with 17 22MnR(0) and ç = 2M² Then, by applying Lemma G.1. for any E (0, 1), let that
log cm it holds with probability at least
B(A - loge-1
2/2M
+
R(6) log
n
3
(13)
2 Clog -R(6),
where C = / (4M² 16/2xM²) 2vBM and (i) follows from 12
Therefore, by combining (12 and 13 it holds with probability at least that
A s
where C (4M2 + 8V27MMP) + 2VTM + 4VTM. This completes the proof of Theorem 3,3
C.2.2 Proof of Lemma C.2
For short, write
A CD gin + 2
On the event V(1, 6a), we claim that
| 1- sca. CA.
According to the optimality of FA and the feasibility of f*, obtain
E(fx) - - AI >| - 0.
(14)
Then, proving Ilfa have
1 12 & CA suffices to prove that if fifa fal > CA or l1fa - fal > b.
ε(A) -
* 0.
Below we are devoted to verifying this fact. Define the function class
g: := == Hi |f - fil s CA, | - f sb..
Suppose that FA & G. Since both G and H., are convex class by the convexity of L(y, -) and Jensen's 's inequality, there exists function f= afx + (1 - a1 with (0, 1] that sits the boundary of (Ma et al. 2023). If we can show that
E() - ε(}) + >| X||5 > 0.
(15)
by the convexity of -(y,-) -) and Jensen's 's inequality, we must have
- + AIIAA1 - X 2 a (E() E(()) + MITIRR ()MRR) >
Then, let us focus on proving (15 on the event (e,, 8n).
Note that belongs to the the boundary of G, we can split the remaining proof into two cases: (i)
|I fF1 CA and || f=1lx < b; and (ii) || - fil CA and | f$1 b.
Case (i): By applying 7 and { from Assumption 3.1 we have
coll F f coll -
so that the co otrston convexity also holds for ft.
22

---

On the event V(l, R,), we have
- - E()
s - C' loog lo R((,))
s --olll - + + Clogi-1R(5.) 1/- 1311, + 111 - fl1xx)
coCs + C'log c R(bn) (6= VCA + || - ftllx)
-c0CA + O8 loge R(5x) CCA + C(log - R((,,)) + 2
4 - - 131
(w6)
-CCC
+
Co 22n CC 2
+
CD
4 0
-
X || ft | k 4
where (i) follows from || 1 = CD, (ii) uses the elementary inequality that 2ab S a² + 82 and (iii) follows from the definition of 6n satisfying
Clogg- R((m)) S
82,+1 2 n
Further with the choice of X 2 82 we have
- S -coCs on 822 VCA+
+ CO 6th
A 1 f8l1zx-
4
4
On the other hand, we notice that
1|| K - >| -2N M4) k- - 18l
(16)
Note that (f.9)x = (K k2/2g) x for any f.g H.. f Hn so that it can be written as
== S (a) for some ā E R
Therefore, for 1/2 2 I 1, there holds
|ASF ,) = A(K at K (ā- at 1)2
| a² K (ā at a+))aa
S. A || - 112 | 0t)
= > A|DD' -1-" 11 K at)|1
= > A|ID 7 | (ā (a-a*)ll
2 ud K (ā - -at)ll
where (i) follows from Assumption 3.2
For 2 S 7 < 1. using similar treatment as that in Lian 2022), we apply Young's inequality
AB < A
F + g for any two positive operators A and B with
and p.g 2 to obtain
K " (@- - a
x² (12-2 - ( -Kāā a at))
X7 X7 "(((2- -27) + (27 - 1) K) K aut) ā ot))
(
$ 12 max { V (a at), K (2/22( / <K(ā at) K (ā -ai)/2
(10
$ x || - -=11x + +Xi117 - 1
(17)
23

---

where (i) holds by taking 2 and y = 1, and (ii) follows from max(a, - a a b.
For y > 1, we claim that |D- 2 S u. To see this, we find that
00 Σ
(1)
06
|DD 12
2
S
Σ
2x
S uu²
==1
j=1
where (i) holds by our assumption μjj S 1 for all j.
Then, similar to 17 with y 1, we have
- & WA - + =alls - 1al..
Combine these two case to obtain that for y 2 1/2
|A x0 S ux 1| 1311xx + -
(18)
= ux || fallxx + VCS.
Here, we recall that 17 min(7, 1}.
Putting the pieces together, for all y 2 1. we have
E( E(F)
>||5=11 - X
<-OCA
C0 527 + 2uA")
VCA
CD 54n
4 111 11 + 2 1110-111x -1113- 1811
X
2
4
-CCA +
C0 (00g2) + +2ud")
2
VCA
C0 00y +
n
X 1 - 1 +1 - -017- - 1-
2
< CACC
C0 g2n + 2uA")
VCA
+
CD 84n 4u²22n
(19)
2
4
where (i) uses the elementary inequality.
Below is devoted proving that for sufficiently large C, the RHS of 19 is less than 0. Precisely, let
(xx)= = cq
CD 82n + 2u22)
CD 8n 4u 22
2 n
x
4
Let = VOA, note that
((x) =CCC - C0D
829 + +2uX")
VCA
CD 8in 422222
4
Cu 82n + +2ud") VCA
=(coC - 1)A
2
-VCA
C/C' - 1 VA
c0 20 + 2ud²)
VC
2
(
ZVCA
COC
CCo
82n 2ud")
Cu 82n + 2ud")
V2C
2
where (i) follows from the basic inequality
a+b I v 2²4 Since s-C-1 is increasing in C, we can V2C max( 1}, which leads to p(xx) 0.
2
select C such that CaC-1 In conclusion, for sufficiently large C in the definition of the function class G. on the event VlL, 8n).
V2C
for case (i), we have
E(-))((5)) + XI AIFIR < O.
24

---

Case (ii): Repeat the similar argument as that in Case (i), on the event V(e, 6,) and by Assumption
3.1
we have
E(ft)- E(5)
s -colll - 10 + Cllog--R((n (5m'11 1a11. + 115 1511k(
Cloog 1100011111 (((,n)
fi11 + +1I - f*llx)
90 6 VCA+ + CD gent2 x-1
^ 11l - ft f11xx.
$
2
4
Further with the choice of X 2 82 we have
E(A) - E( -
00 2
VCA
CO 5th + 11 10
2
4
Combine with (66 and
18 to obtain
-(F))-(()) + 1 2
Co 62n + +2uA7)
VCA+ +
CD 84 +
X 1 1a1 +2ud
7+ $ =1111 -1 -115 1l1
4
c0 62m + 20d") VCA + c0 su + 22
2 211 |2
Note that 0 < X S 1 and x 2 8% together implies
A 2 and x 6.
Moreover, in Case (ii), 11f - fillx = b. Therefore
E(F)) - E + A|1 - 1
CO 822 + 2ud") VCA
Co 5 4u2
1
1 x2
$
2
2
$ 6th + Bu2APV/CA + Cp 44n + 4u 2x
1
12220
2
S v co
max (20,, 1,5,0m + Su x 2n
CD ghn + Xu
22
1 8,2 2m,
4
2
where the last line is less line is less than 0 for sufficiently large constant b.
At last, by combining Cases (i) and (ii). we prove
15p. Therefore, on the event ((,,, 8n), we have
|| 1 CA 8th + =n
which completes the proof.
C.3 Proof of Corollary 3.5
Recall that the statistical dimension is defined
d()) = min {j E [
: My s {8.
From the definition of d(o), we have
R(5)
1 d(6)82 n
Σ Pg-
(20)
n
d(6)+1
Recalling that Ed M3 S d(6)6² for regular kernel and kernel with the polynomial in its eigen- values is regular (Yang et al. 2017), the kernel complexity function satisfies
R(6) x d(8)82
25

---

Therefore, the solution to the inequality 2
can be bounded from above by the solution to
Clog d(8)6² - Co g
(21)
Moreover, if the eigenvalues of K exhibit a-polynomial decay that jáj j_ then have d(6) 8-2/a, Together with 21 leads to
6 s c (log 1)2
FyOFT
72
Then, with the choice of À 82, it holds with probability least 1 that
1 - f S C(6 + x²T) = o( (log 112
2n
2q041
We conclude the upper bound in Corollary 3.5
D Proof of Results for Truncated Kernel-based Method
D.1 Error Analysis
Recall that
9- = "==))(((")=((P S (xx,))
and
u In the proof for the truncated kernel-basee estimator, partition &* into two sub-vectors
5- (ET 12
with Ef E R" and E R
Moreover, we partition U into two sub-matrixs
U (U1, U2)
with U1 E Rax and U2 R=x(x-r), and partition D into two blocks D1 and D2, that is
D Di
D
where Dj Rexr and D2 E R (nx-))((--)) Since the last n - diagonal elements of D, are all zero, for any E R", the last elements of D.U are also all zero. Then, we have
D a (0)) for all a E R
(22)
Define
:n ( : R*)
For any f = SI, E Hn.r. we have
||/l|> K.a|| |ID. U a || D.U
where the last step holds by applying 22)
We also observe
[l all, [ID|'"uTa
U UT
(23)
Define an immediate function f = ST, E Hnrr with a = = 1 E R".
(24)
26

---

From 23
we have
|| Kr
=|D| U1 UIDI Sillk
(8) -ill sill = =En 59 > Mj S u.
(1)
(25)
= D 1/2
24
c=
3=1
where holds by our assumption μ4j S for j and (ii) follows from Assumption 3.2
The construction of I allows to analyze the prediction error of the truncated kernel-based estimator from two sources: the estimation error depending on the complexity of the truncated RKHS H.,, and the approximation error arising from the dissimilarity between the truncated RKHS Hk, and the full RKHS Hg. Specifically, we have the error decomposition as follows.
Error decomposition. By applying the elementary inequality that (a + (a² - 2a² + +2b, the total error [lfxr fl can be decomposed
|| f 1 S FA. 121
+2
| -1-
(26)
Estimation error
Agpeuximation bias
Note that both far and fe belong to Hn.r. allowing to analyze the estimation error based on the complexity of the reduced kernel matrix K,. This decomposition successfully captures two components of error: estimation error and approximation bias. The estimation error controlled by the model richness of the truncated space Hk., while approximation bias depends on the dissimilarity between the truncated RKHS Hk, and the full RKHS HK where the true target f is sitting in. A larger amplifies the space KK,, resulting in larger estimation error. At the same time, it narrows the gap between Hk, and H.. thereby decreasing the approximation bias. Consequently, a trade-off emerges, and an optimal choice of truncation r aims to balance the estimation error and approximation bias.
D.2 Proof of Theorem 4.2
We will separately bound each term from above appearing in the decomposition (6)).
Bounding the approximation bias. Note that
|| l 11 q- a
l D.U 2f (i)) ||s - D, U. 1|
where follows from the eigen-expansion that K, UK, T and (ii) follows from By the definition of at, we have
= U.D.U =
Therefore, we arrive
|| Il. || Σ 5
(27)
j=r-1
Bounding the estimation error. Define the localized function class
Ho.r.b = { f E Hn.r, |l - f*1 $ b).
where is a constant independent of n, 7, which will be specified in the proof.
Recall r from Section 4 For any given (0, 1) and 8 > 0, define the auxiliary event
(r 8) = { ε(+,) (E()) E(T)) < Clog -R (O)..- holds for any ʃ Horro)
where W,( = 8-1| fFll.. + | - f² for 8 > and f E Hn,r. To establish the bound for the estimation error, we need the following two lemmas.
27

---

Lemma D.1. Fix any & (0, 1) and 8 > 0. The event Vr 8) occurs with probability greater than 1 1-4ie. l.e.
(v, 2 Lt
Recall that o the critical radius w.r.t. the truncated kernel complexity function defined as the smallest solution to (3).
Lemma D.2. Let = min 1}. On the event Vr das), with the choice of satisfying
max 2j=r+1 5j x S L, we have
|f Flll. - c( 52g + + +
ex2
jmr+1
where C' is constant independent of n,
Proof of Theorem
4.2
By applying Lemma D.I we have
(1, 2 b
which, together with Lemma D.2 implies
| 11 C 54g + + +
j=r+1
holds with probability at least L. Finally, by applying the error decomposition (26) and the equality
27
one has
[|fa, 1", - fllfarr fEll 2
c((55 844 + 2
Σ
|=++
which completes the proof for the Assumption 3.1
For the excess risk, it immediately follows from
D.2.1 Proof of Lemma D.I
Denote
D, = E(() E(+)) (EC) - E(F))
Similar to the proof of Lemma
C.2 it is equivalent to proving that
|D,| Wr(f.0)
A
sup fEHa.na
< C log -1 R,,,
From 25 observe that for any f E Hn.r.b
ll $ 1| - ff k. + +|5 K, Su uutb. bb.
Let == + b, and we have that T(y..) satisfies the Lipschitz continuity over the function class Hngr,h with Lipschitz constant Mr Write M == MG, for short.
Bounding E[Arr] Following similar treatment that (0). by using the Lemma G.2 and Lemma we have
G.3
|D,| Wr(f
E[A.] =E
sup SEHa.mm
(28)
2 2n M
D w/ - -(xx))
sup SEHn,
n
W,(f.0
Let
F,(6) = {s = =[)((a): -1-fflkee S 11,11s -Sf fFll, 5.
28

---

For any f E Hn,r,b, there exists a R such that f = Sx, (a). Recall that f? = (a{) from (24).
Define the vector : D.U (a :
-z,,, then / E F6) is equivalent to the constraints on B, that | 12 <
and || s 8.
From (22). the last n r elements of ,3 are all zero, then any vector satisfying these two constraints must belong to the ellipse class
$3 with vy = ming68.113) S
E, :- {s g- ($1, (2,,82.... B2....) . E ER
Σ
==1 Vj
Denote (W1, ... Wp) TT, we have
Σ wx(f(x;) fxxx)))
sup v (w/ (w, U331| BEE
sup (EFF(()
= E
E
sup BEE,
vnl (w, (w,
(6)
r
EE
sup Vni BEE,
Σ Pjue j=1
Ui
S V2n
Σ
Uj = (6),
n
where (i) follows from Scchwa- incquality and the fact that the last elements of ( are all zero
Similar to the argument in the proof for Lemma
by appropriately scaling, we obtain
2 2m M
n
E [AA
sup (E)
Σ
wi (x(((x))))))))))))))))))( - (xx))) (AV
(29)
n
Bounding A, E[A,]. For each E [r]] and any / E (o), define 8, = sign([(xx) - ff(x,))
j = and 8, = 0 if * and let s = (s1,... then we have
lf(x)) (xx)) = Σ (f(((x)) fF(x))
32
=vnils U3) S Vn,
Σ 25
Vn.
Σ
U
V2nR,
Vj
Uj
Consequently, for each E [n]]. we have
Liv, f(x,)) L( fF(x:)) S (Mf(x) - fF(x)) S MV2nRR
In addition, note that
(L(y,, - - ((,,)))
2 - ((xx)) -2111 - 1211
83
(M. = M2(B,3) S 2 max v
Σ
< 2M
Σ V/ = 22
se|r]
V2
1=1
i=1
29

---

By similar rescaled method, we have
Livi, f(x))) LLy,, f+(x)))
Wr(f,0)
= -M -xx(x)) Ss (V),
and
1
E (
((x)) f(x)))
LIvi f((x):)) )
M
-(x))-
Σ
6)(5,6)
Wr(1,0)
i=l
M
(f(x.) - 17(xx))
n
Thus, the requirements in Lemma G.1 hold with 17 M (6) and Ç² 28)) Then, by applying Lemma G.1 for any E (0, 1), let
log 1-1, it holds at with probability least
1 - that
A, [(A,) SV loge-1 (5) 4MM22R +
2/2M
R2 (8)) -1
n
3
(30)
S C'oog ()))),)),))),, (o),
where C (4M2 + 16V2TM2² + 2vIM and (i) follows from 29
Therefore, by combining
29 and 30) it holds at with probability at least that
Ap S Clog.
(,,)).), (5),
(31)
where C' = V (4M2 + 16v2 + 2/2M 4.
This completes the proof of Theorem 4.2
D.2.2
Proof of Lemma D.2
Denote
A,
6O 84g + 4u?221
(C6 + cc)
Σ 5 |=++1
4
On the event (r, )n we claim that
Il 121 s CA,.
By the optimality of FA. and the feasibility of f/A we have
E(Px,) E(f+) + >lffar A115 S 0.
Define the function class
G, = { Hn.r ||f f.1. S CD,, - 12 $ b]
By following a similar argument as that the proof of Lemma suffices to prove that
T ε(:) + > >| > 0,
(32)
where f, is some function belonging to the boundary of G...
30

---

It follows from Assumption
3.1 that
co pr - - s <T() - -(())
and
E(f)) - -(())) S &ollff -
Then, have
co [ 111l (26g 200) 11 200) - 200l Fr - frl 26 - 1'1l"
1
(1)
S (f.)) E(ʃ-) 2(E(1)) E(L)))
= 2(8(f))- - -E(f)),
(33)
where (i) uses the elementary inequality.
Note that (33) establishes connection between the excess risk and )norm))norm at ff. which allows us to prove Lemma D.2 using a similar argument as the proof for Lemma C.2
Below we separately consider two cases: (i) Fr f11 = CA, and || filkx S b; and (ii) Ilf. flll < C', and [l fl = b.
Case (i): On the event (1,,, 6n,r). we have
E( -
S {{().) - E(T,) + C' l - (2 W dn,))
( 7, f 1 (c + co)
1', -llog-- Rr(rrr) (ont fill, + +11Fr ffllx.)
(10) 4D CA, + (co + co)
Σ
c 2 + C'log (R
(o + +1 f21l k..)))
2
j=r+1
where follows from (33 and (ii) follows from 11Fr f CA, and 27
Recall that 8, satisfies
C Clogg- B (Sn,r) <
C0 g2
2
and we choose À satisfying À 2 82 Following similar argument as the proof for Lemma C.2 we have
- -(()) 5 CA, + (c6 + co)
2x
24 CA,
1 /²1
2
nr
nr +
jmr41
Since Jr Hn,,, there exists ā RD such that
J, = Sā,
Note that
>||5 - -11 = - ()) - ~1I5r fFlls
(34)
Following the similar treatment as that in the proof of Lemma replaced by 2,, we have
C.2 with K replaced by K, and ă
IAJF, fm).1 wxn+ || fšlks, + - 1ill,
mnx+t -fills, + u CA.
(35)
31

---

Put the pieces together, and repeat the similar argument as that in the proof of Lemma C.2 for all
7 2 2.4 we obtain
E( - E(i.) + AILSFIRR - -
f 00 CA, + (c + cw) Σ Ej + ( 52h + +2ud2) VCA, + 20 j=r+1
2 =
S + 242
4
and for sufficiently large C, we have
{(A)) -
- Al1 <0 O.
Case (ii): Repeat the similar argument as that in Case (i), on the event Vr(c, (n,) and by Assumption
3.1 we have
E(ft) - E(F.)
< - 00 ||,, -1ll + (c6 + ca) Σ
E/² - Colog (R,
- - + +115. - -1
-f1lk.)) (l)
2
j=r+1
s 5(6 + co)
Σ
2 59
+ Clog -ollgo-"R,iin (R( ( f:ll + |||r- - s sEllk.)
==
5(b + co)
2
CD
/CA,
2 x + 1 fllks. Dir
5j
nn
2
|=++1
< (cb + m))
Σ j=7+1
2
+
co
2
CA,
n.
X 21 1|. 13l1
2
where the last step holds with the choice of X satisfying X 2 52.r-
Combine with 34 and
35 and by applying the elementary inequality to obtain
E(f+) - E(F+) + AlI
- fI
< (c6 + co)
Σ
2 + 2
Co 2n + 2ud") VCA, + Co C n.r - + 4uu
2 11 - -i11"x
2
j=r+1
By our choice that
< X < 1, x > max max B2.r. 2j=r+1 2 we have
A > 27
and
0²
n
j=r+1
Note that in this case, 11f. - 1 b². Therefore, repeat the similar argument as that in the proof of Lemma C.2 for a sufficiently large constant b the RHS of the above inequality is less than 0.
By combining Cases (i) and (ii), on the event V,,(, 8n,r), we have
1 1A1.. s CA, S 840 + 2 + Σ 5²
j=r+1
which completes the proof.
D.3
Proof of Corollary 4.3
From
n Σ
||
11
j=r+1
32

---

For the approximation bias, according to the polynomial assumption that Ej x z--22-11 we have
2-a-1,
S j j-2aa-1 S s0 f. t 2-200 dt S Cr
Σ
For the estimation error, control the truncated kernel function first. Similar to the equality (20) for R(6), if > d(6), we have
I +
Σ My
(6)
n
m d(6)+1
Moreover, for the regular kernel class, we have R, /d(o)52/n. If S d(8), we have R2 (6) = vr82/n. Combining these two results, we have
(o) min(r, d(o))0².
(36)
Next, we split the remaining proof by considering two cases: (i) S S 1; and (ii) 7
Case (i): Recall that for the eigenvalues of K that satisfy M4 x j_ we have d(6) x 8 8-2/o 2/0 In addition, we notice that in this case, the best truncation level to balance 8 and r 2ya is = d(6). This means that whatever is, always have R, V complexity remains the same, and avoid introducing additional approximation bias, the best choice of truncation level turns out to be Then, following similar argument that in Section CB3
/ d())02 Hence, the kernel
we have 82 S C (log I.
Choosing the optimal parameter of = 62,r- yields
E(fxr) - - x Par 11, s cc ((LLog" (1ogi-1)
2T
2y0+1
Case (ū): In this case, the best truncation level r to balance 8 and r 2 is = 5-2/(10), which implies S d(5) so that from (3). we have
201-2
R,
r0
Therefore, the solution to the inequality (3) can upper bounded by the solution to
207-2
Colog
-
Solving this inequality yields
S <c( (log( <(
na 24a+1
82
n
and we can choose
n
r
(1oga-1)2
The desired upper bound in the case 7 > follows by choosing À x 02 x 220 By combining these cases, complete the proof.
E Proof of Theorem 4.4
We consider the special case that the data is generated according to the mean regression model
Y, = f (x,) + E, with E; ~ (0,
for each E [n]. For this mean regression model, f is the minimizer of the population risk E() with squared loss specified.
33

---

For any 8 > 0 and 2 1 2 define the ellipse class
I u² sar). (min (mi,,,?,,,))3
(6) (fi, E R
For & E RR" define the rescaled norm
13
K
(min {8 12
Then, it is equivalent to write
(6) = { (E1, R² 1KE1?, u²
Recall that the statistical dimension is defined
d(o) min {j E [n] H S 88)
Our main proof is based on the following lemma that states result concerning metric entropy.
Lemma E.1. For any 8 > 0 and 7 2 1.2 there a collection of - sepaarate points {5' .... 5 EMy
E (8) such that log M Z d(8).
By using Lemma E. there exists a - collection of points (5 ,..,, 5di in (6) such
that log MM 2 32
d()). Given (..,,...5 S,M,, ), we construct f f'.... fM as f = S (UD (t) Note
that the TA scores corresponding to f" are given by
U Sx(f') U KUD =
Hence, {E-, " MM c (6) implies ft E H for each i E [M]. Moreover, we have
UD UD 15) l|s e'1l2 z 54
1 = DU DUT (UD
which implies that (f) f fM) is 1 2 sepaarate in Htx
Since E" E (6), we also have
2
1 1ee112
Sk
847
Sk
< u
200
84y
Therefore, by using the triangle inequality, we have
If f 11 < 2 for each i,j [M].
Let pa be the underlying distribution of the collected data ((x;, Vi) corresponding to fth Then, there holds
(L( ( Σ (LLN
n Ill - flll s u2
where KL((III) denotes the KI. divergence between two distributions, (i) follows from the fact that KL(P1 & PallQ1 @ Q2) (L Q1) + (L(P211Q2) and @ denoting the product measure, and (ii)
follows from the fact KL(N (mn, a²) ))I o²)) =2)
20
Below is devoted to establishing the minimax lower bound by applying the standard Fano's 's method (see, for instance, Proposition 15.12 in (Wainwright (2019)). To be specific, for 8 >> 0 and for any estimator f based the data {(x;, 3 have
inf sup P (15- 11 > f M'
84y
maxi
(L + log
21
4
log M
n284 + +log 2
>
(37)
d(o)/32
34

---

Below we separately consider two cases: i) 2 Y 1; and ii) > 1.
Case For S 1, we take 8 = (4c) on where on is the critical radius defined as the smallest
solution to in Section 3 Plugging into (37 yields
21 4cu + log
inf sup f MENK
PII f 2 cott)
d((4c) $ 6,.)/32
nc + log 2
21
(38)
d
where d, = d(,,,) ) and last inequality holds since d(d) is decreasing as å grows and (4c) 2 5n S 6n for sufficiently small c.
Recall that for 1/2 S r S 8n smallest solution to
C'log c -R(0)= - ch 82211
Moreover, for the regular kernel, we have R(() x V 1/ 16)6) which implies
2
d(on)82
d
Then, da 2 cind for some universal constant C₁. Plugging this inequality into (88
yields
inf sup P P ž co 21 r*E
4cu2no + log 2
1 2
cinon
where the last step holds for sufficiently small c.
Case it: For 1, we take = (4c) 45 61/7, where 8n is the critical radius defined as the smallest solution to 33 Section 4 follows from (37) that
P P(IF 1l c5
4cu2
n.r + log
inf sup f-
21
d((4c) + 81.7 3/32
2 n,r + log ((61))//5
Recall that for 7 1, ou, is smallest solution
C0 Clog (R,g-- - 0 83.
2
According to 36). if S d(o), we have
(0) -282
Hence, we have
Kn -
8
which leads tor 2 cond,, for some universal constant C2. Then, if we choose d(6l/?) satisfying d(o)/)) d(δn.r), we have
4u cnnon + log 2
1
inf sup S'
P(I3- 1 c51 21
Ceznot, /32
where the last step holds for sufficiently small This completes the proof of Theorem 4.4
35

---

Remark E.2. In the proof for the lower bound, we consider the Gaussian noise case. However, for the upper bound, we require y C [-U, U] when the squared loss specified. The bounded range assumption essentially requires the random noise to be uniformly bounded. Nevertheless, the upper bound established in this paper can also extended to the sub-Gaussian noise case with slight order sacrifice of some log factors in the upper bound. Specifically, suppose that {++)== are i.i.d. sub- Gaussian variables: that is, there exist positive constants C, o² such that P((e)) > t) I ccxp(-o²()) for all 2 Then, by the union bound, we have
P( max
|=,| f) S P PP
> =]] - Σ
cexp(-o = cn exp(-o²(3).
1=1
Consequently, for any i E (0, 1), by taking t= == log
@n
it holds with probability at least
1 that
max
| 1o-ooo
log
cn
S
log 1
+ Vlogn.
Further note that by the reproducing kernel property and our assumption that supx,x K(xxx) S k2, we have that for any x E X
(x) = 1ff ((x, k) s
-Ik S I
(39)
Therefore, for the sub-Gaussize Gaussian noise case, we can immediately complete the proof by replacing U with U., = xll + C(y C(ylog/ : + v)ogn). As a result, the upper bound for the uub-Gaussian noise case will align with that for the uniform bounded noise case up some log factors.
E.1 Proof of Lemma
Lemma states a result concerning metric entropy, and its proof is motivated by that of Lemma in Yang et al. 2017), which only focuses on the just-aligned regime 1 For each j E MM. let
2.
22)(8) d(d) 0 O..., )
82
82
8
5²
w
(40)
2d(
22)
where
w
(w .... w)()) ",..., WM (urf .... wd())
(O,
a collection of independent standard Gaussian vectors. We claim that with a probability greater
0, we can find a set {E² ...,,..,"" Ad generated in the above manner that are -er-separated in {(d) and
M 2 e # d(
On one hand, to show that (E.,,..,, C (ō), we need equivalently prove || S u² for each
E [M]. Indeed, for each index i E [M], since 8² < Pj for each j S d(0), we have || 2d(6) Note that ||w||| 1 X2(0y- Then, by using the tail bound for chi-square distribution (Example 2. 11 in Wainwright (2019) ), we have
|| 11
IP 1151 < v22
=P
1
12
< 2u² 222=-11 -1)
d())
>
1
12
1 $
> 1- 40d(8)
(41)
d(6)
where we use the assumption that 2. By applying the union bound, we have
IP (11)2, s u all i E (M) Me 494(6)
(42)
36

---

On the other hand, note that -5 - -
8
w
w
Since w and w are independent, we
2d(d)
have (wi w NO, Ia(s) (a(o) Then, similar to the inequality (41
we also have
P 115 - - 2 8
1
=P
[w - -w'1 2
2d(6)
=P
1
/w' w'11 11
3
2
1
9
123
2d(()
and by applying the union bound, have
P |5 - el1l2
2
84
for all i,j E [M
2 -Me
9916)
(43)
4
Combining 442 and 443 yields
8t7 for all i,j [M] 2 Me.
P
115 u² and || 1
49d(6)
M²
9d(5)
T28"
where the left side is positive by setting log M = d(2) We thus conclude the statement in Lemma E.1
More discussions on Assumption 3.1
As discussed in Section Assumption 3.1 is a relatively mild condition for many widely used loss functions. It is clear that the squared loss satisfies Assumption 3.1 with co c = 1. For the Huber loss (y, fx)) = (y - (x)) if y -xf(xx) S т, and fly - f(x) 3 otherwise. since is
locally equivalent to the squared loss function, thus it satisfies Assumption 3.1 under some mild tail conditions on the noise term Y - -*x(x) (Wainwright, 2019).
For the Hinge loss f(x)) = (1 (x), 0) that is designed for the margin-based classi- fication problem, as mentioned in (Wainwright 2019). whether Assumption 3.1 holds hinges on the distribution of the covariates and the hypothesis function class F. We remark that for the classification problem, the theoretical guarantee for 0-1 loss is also crucial. Once the 0-1 loss is considered, one possible routine for establishing the theoretical results for 0-1 loss is to follow similar technical treatment as that on Page 17 of Lai et al. (2024) with some slight modifications, where the bridge between the excess risk w.r.t 0-1 loss and mean squared error established, and based on the result in Lai et al. (202)), the excess risk only gets a slower rate compared to the rates established in our paper.
For other loss functions, including the check loss, Logistic loss, and exponential loss, we provide more detailed discussion and deduce some sufficient conditions to ensure the satisfaction of Assumption 3.1
F1
Check loss
Let (t) = - - and Ly f(x)) = p-(y-f(xx) - We next verify Assumption 3.1 the following assumption holds.
Assumption F.1. Denote Fyjx=x be the conditional distribution y given X x. We assume that there exist two constants cu, do such that
200l yl & (f
(f*(x; + v) - Fx|x=x; & 2c/lol.
Proposition F.2. Under Assumption F. for any b > O, both the local cu-strong convexity and the local d smooth condition are satisfied.
Proof. For each E [n). denote w = = l" (x, and v f(x,) - (xx)). By using Knight's
identity (Equation B.3 in Belloni & Chernozhukov (001 that Pr (w v) pr (ww -v(T
37

---

(moso)) ) + S0 ( (m(5e) (w=50) dt we have
E(pr(Y - f(x))) -Pr (x:))
= -x(( - ((xx))) - -(x))(()))))++++++ ((x))))((x))
(4x5)(0)4) - (xrss
(44)
Recall the definition of f*, we have
(x(((x)) (x:) (x=5=(0)))] (J(x) - (xxx) [x ([ys
Now we consider the second term in the right hand of (44) It follows from Fubini's theorem that
-(x))_((xx)
E
(xx)))(())
B[ - I(ySM()))
((x))-(((x))
(f +t) - (f (x:)).
According to Assumption
there holds
f(x.) f(x)) (x.)
"X (f'(xx( + - (x)(x)))
1(x))- 1 cc(((xx) (x;)))
o
and
f(x))-f((xx
(f* + Frxx=x (x:)))
1(x))-1
2c/lt/dt = -xx)))
Then, we have
f SE / ((x))- (((rs)(()))) - I(srr(x)
f
The desired conclusion immediately follows by summing from n. This completes the proof of Proposition
F2
F.2
Logistic loss
The Logistic loss L(y. fxx) log(1 exp(-yf(x)) is specified for the binary classification problem, where the response y takes values in {-1, Simple algebra yields the first and second derivatives of L(y, in the second argument that
aL.
eexp( (yp0
00
+
and
8 L
y² (exp(-y0/1) + exp(y0)/22
002
It is clear that for any 0 E R, we have
0L
0PL
<
1
and
<
00
002
4'
38

---

implying that -(v,)) is 1-Lipschitz continuous and the c/ elllocal smoothness condition holds with
c =
Recall from For f E Hx and E X satisfying
- D, denote B = x:lls*1 + D,
have
8
062 l f
c-B -2
implying the locally strong convexity condition holds with co --
F.3
Exponential loss
The Exponential loss T(y, [x)) = exp(- used the AdaBoost algorithm designed for the classification problem, where y E 1-, Note that the first and second derivatives of T. 0) in the second argument is given by
aT
0 002
00 ye ve and
For any 0 R, we have AL < which implies that L is 1-Lipschitz continuous. For the locally strong convexity condition and local smoothness condition, with a similar argument as that for the Logistic loss, have that
L 802
<
S e
This ensures that the local strong convexity condition holds with co cB and the local smoothness condition holds with c = e
G Supporting Lemmas.
The following lemma presents Talagrand's concentration inequality for random elements taking values some space (Bousquet 2002 Lv al. 2018). Detailed proofs can found in [Bouqquet (2002).
Lemma G.1 (Talagrand's concentration inequality). Let 71.... Zn be independent random elements taking values in some space Z equipped with norm functions acting Z. If we have
1|. Let F be a class of real-valued measurable
max iEIn
[[ En and
Var(f(Z,) SC. YfEF,
1=1
define the empirical process Z == sup ! E - -Ef(Zi)) then for any t >
2nt
222E ( +1122 2n)(2)) + 3
S exp(-ntt).
The following lemma is known as the symmetrization technique, which provides a fundamental tool to bound from above the expectation of the empirical process (Wainwright 2019). A typical version of the symmetrization lemma is to consider the Rademacher variables {E1, }n). ie. P(E, 1) P(e, -1) (Proposition 4.11 in Wainwright (2019)). ). In proof, consider sequence standard Gaussian variables to utilize the rotation invariance of the Gaussian vector.
Lemma G.2 (Symmetrization), Let XI,..,,,, be a sequence of random variables and Wi.... Wn ~ (0, 1) denote the standard Gaussian variables independent X1, .i...., Xn. For any measurable function class F, we have
a Σ (((x))-E((XE n fEF t=1
sup
< V2 sup n fEF
Σ w.
s(x(X
39

---

Proof. By applying Proposition 4.11 in Wainwright (2019), we have
B
H sup FEF
R [ S 2E sup n fEF
Σ
Therefore, it remains to prove that
n
R n
sup Σ ex((x))]]
$V
sup fe
w (xill
Indeed, we have
Eg
sup
Σ
E
sup
E
wm lw
T FEF
2
71
fEF
(44)
E
E sup FEF
wes s le: (Xxi)
2
/ (x:)]
sup FEF
2
(888)
wi ((x))]
fEF
where we use Ew to denote taking expectation with respect to W1, ... wn, and use similar notation Eg for taking expectation with respect el, En. (i) follows from B| - V (ii) uses Jensen's inequality and (iii) is due to the fact that W/ has the same distribution with E;W; for each i. This completes the proof of Lemma G.2
The following lemma can be found in Wainwright 2019), which allows us to utilize the symmetriza- tion technique for the Lipschitz function family.
Lemma G.3 (Gaussian contraction inequality). For any set T E R2,, and let {Ø) R + R.j 1..... d} be any family of M -Lpischiizz functions such that Φb (0) 0 for j E [d], we have
funcciitt
E
sup OET
Σ
(o,))
S
2ME
sup OET
Σ
H Additional Simulations
H.1
Assessing the Performance of the Truncated Kernel Method
In this section, we conduct numerical investigation to assess the performance of the truncated kernel method (TKM) and validate our theoretical results in the main text. The experimental design consists of four distinct examples, including kernel quantile regression, kernel ridge regression, kernel support machine, and kernel logistic regression. In each example, we consider both the univariate and multi-dimensional cases. In specific,
apply Sobolev kernel K (z, x²) min(z, 2'} for univariate cases and Laplacian kernel K (x, x') = exp(-II -x'|| for multi-dimension cases. The elements of dimen-ddimnsionall covariates are independently sampled from the normal distribution, while in the univariate case, the covariate is sampled from the uniform distribution on [o, 1]. Aligned with the previous notation, TKM means truncated dernel-based method, and KM means standard kernel-based method. All the experiments are repeated 50 times and all the tuning parameters are tuned to the best for both methods. All experiments were conducted the same hardware setup: Intel i9 13900K CPU @ 2.20GHz with 128 GB memory.
Example (Kernel quantile regression). this illustrative example, we begin by conducting a comprehensive analysis of multivariate kernel quantile regression and postpone the univariate case to the subsequent discussion. We consider the data- seraaagnneraingggg scheme that y = fo(x) + - +b)( where = 3, (0, 1) and & denotes CDF function of standard normal distribution. Here,
40

---

T=0.3
r=
r=0.7
Log MSE
Log MISE
15M
TEM
1000
2000
500
1000
2000
1000
2000
T=0.3
0.5
T=0.7
Log empirical eacess riak
Log empirical ezcess riak
empirical excess
-2
1EM
TEM
100
2000
1000
2000
2000
Figure 2: Averaged log MSE and log empirical excess risk for KM and TKM under check loss with varying sample size n.
0.3
r=0.5
T= 0.7
Log MSE
-15
-1.5
2.0
2.0
25
-2.5
-2
Log empirical eacess rlak
-1.0
T=0.3
Log empirical exccess risk
-1.0
0=0.5
Log ampirical excess rlak
-1.0
0=0.7
-15
-20
2.00
-.0
-25
-25
-30
Figure 3: Averaged log MSE and log empirical excess risk for KM and TKM under check loss with varying truncation level rl log(r/n)
we set fo(x) = sin 2(x1 + x2 + xz)) with x = (01, 22, Tz) and vary the quantile level T from 00.3,
We first compare the numerical performance between TKM and KM in estimating the true function fo under different sample sizes n. The averaged numerical results in terms of logarithmic mean square error (MSE) and empirical excess risk are illustrated in Figure
is clear that under different quantile levels, TKM always outperforms KMM More interestingly. the decline rate of TKM is significantly faster than that of KMM. which validates our theoretical findings that under the over-aligned regime > 1, TKM achieves a faster learning rate than KM as illustrated in Corollary 4.3
In the following study, we fix the sample size as n = 500 to investigate how the numerical perfor- mance of estimating fx(x) is affected by the truncation level by varying the logarithmic ratio of the truncation level r to the sample size n, rl = log(r/1) /n). The averaged numerical results in terms of logarithmic MSE and empirical excess risk illustrated in Figure
From Figure 3 we can see that the eurves turn to a gradual increase, and finally become stabilizing with little vibration. This confirms our
the scenarios have a steep decrease at first, then
41

---

T=0.3
r=0.5
r=0.7
-1.0
-1.0
+1.5
-1.5
-1.5
-2.0
2.0
-.00
2.5
-3.0
-3.0
-3.5
16M
3.5
T6M
-3.5
TEM
2000
2000
2000
T=0.3
0=0.5
T=0.7
-0.5
-1.0
-1.0
-1.0
-1.5
-1.5
-1.5
-2.0
-2.5
2.5
3.0
-3.0
3.00
11M
16M
-3.5
16M
500
200
500
200
500
Figure 4: Averaged MSE and empirical excess risk for KQR and truncated KQR in the multivariate case.
T=0.3
T=0.5
T=0.7
-1.0
-1.0
-1.0
Log MS2
MSB
-3.5
MSR
-1.5
-2.0
-2.5
-2.5
-2.
TM
r=0.3
0=0.5
T= 0.7
Log empirical excass Hisk
Log emplrical excess rtsk
empirical ezcess risk
-15
-1.5
-1.5
-2.
25
2.5
2.5
-30
-3.0
-3.0
Figure Averaged MSE and empirical excess risk vs rl log(r/n); the sample size is set to 500.
theoretical findings the truncation level and illustrates that properly chosen truncation level is necessary to boost the estimation accuracy of the truncated kernel-based method.
Now we demonstrate univariate simulation for kernel quantile regression. We assume the true function to be fo(x)= = sin sin(10r) and underlying model to be y = fo()) + a(e - o (r)), where 3, (0, 1) and Φb is CDF function of standard normal distribution.
As shown in Figures 4 and 5 for the univariate kernel quantile regression, we observe that, across different quantiles and various performance measures such as MSE or empirical excess risk, TKM consistently outperforms KM. This observation also confirms the advantages of TKM compared to KM.
Example 2 (Kernel ridge regression). In the kernel ridge regression, consider the model y fo(z)) + c, where fo(x)= = sin(z), No, 1) for univariate x. While for multi-dimension scenario, 3 and we generate data from y sin(2(ø; + I2 + xx)) + c, where <~ <~>N( (0, 0.5). Another setting is similar to quantile regression.
assume dimension
As shown in Figure 6 it can be observed that in both the univariate and multivariate scenarios, TKM outperforms KM significantly. Furthermore, multi-dimensional cases, the advantage of TKM even more pronounced. From the right panel, it can be seen that although the optimal value of
42

---

-1.00
-0.5
-1.0
1.5
-2.50
-2.0
-2.5
-4.00
200
500
1000
1500
2000
-6.0
-4.5
-3.0
-1.5
0.0
(b)
0.75
-1.75
-1.00
2.00
1.25
-150
-2.50
-2.00
-2.75
500
1000
(c)
(d)
Figure 6: Simulation for kernel ridge regression. (a) univariate covariate case: average accuracy vs univariate covariate case: average accuracy vs rl log(r /n); the sample size is set to
= 500. (c) multivariate covariate case: average accuracy vs n. (d) multivariate covariate case:
average accuracy vs rl log(r/n) the sample size is
500.
Clueeffcaton emer rate
0.220
Clssiffccaion rate
9.4
0.15
0.3
0.10
0.2
0.05
0.1
0.00
0.00
2000
1r
(a)
(b)
0.35
Dlssifcation antrr sate
Chassi catSon errrr ratt
0.30
0.30
0:25
0.25
0.20
0.15
0.20
0.10
0.15
(c)
(d)
Figure 7: Simulation for kernel support vector machine. (a) univariate covariate case: average accuracy vs n. (b) univariate covariate case: average accuracy vs = log(r/n): the sample size
set to 200. (c) multivariate covariate case: average accuracy for n. (d) multivariate covariate case:
average accuracy vs rl = log(r/n); the sample size is set to 200.
differs, they all reach their minimum at certain point within the range of [0, 1]. This verifies our theoretical conclusion.
Example 3 (Kernel support vector machine). In the kernel support vector machine, we denote the sign of x sign(x) and generate data through the model y sign(ffo + +). In univariate case fo(z) = sin(10x) and for the multi-dimensional counterpart fo(x) = 3 sinn(2 + D2 + 22). (0, 1.5) in both case.
As shown Figure 7 a similar trend can be observed both methods, where TKM outperforms KM under different sample sizes. Furthermore, the advantage of TKM becomes more pronounced in multi-dimensional cases. As the error curves against rl, it can seen that both univariate and multivariate scenarios reach their minimum value within the range of [0.1].
43

---

Chaetitcttio eirer rate
Classification airer rabe
TM
0.6
9.15
0.4
0.10
0.05
0.00
-250
(a)
(b)
Classificaton arror rate
0.330
TEM
Clasincation enrer
0.25
0.20
0.3
0.15
0.2
0.10
(c)
(d)
Figure 8: Simulation for kernel logistic regression. (a) univariate covariate case: average accuracy
vs n. (b) univariate covariate case: average accuracy vs rl = log(r /n); the sample size is set to 100. (c) multivariate covariate case: average accuracy n. (d) multivariate covariate case:
average accuracy vs rl = log(r/n); the sample size is set to n 100.
1.50
KSVM
KSVM
5:36
-04
-05
Figure 9: Kernel SVM; averaged classification error and log excess risk for KM and TKM versus a.
Example 4 (Kernel logistic regression). In kernel logistic regression, generate data from y Bernoullipp). where p (oosp(-oo(a))) where fo(z) = sin(15x) in univariate case and fo(x)
3 sin(2; + + 2z) for the multi-dimensional case.
As shown in Figure 8 its exhibited curve trend is similar that of kernel support machines. This validates that under different model assumptions, if a specific r is chosen, TKM performs much better than KM.
H.2 SVM with varying Model Complexities
In this part, we aim to investigate the problem how once the hinge loss is specified (corresponding to SVM), how the RKHS with varying model complexities affect the numerical performance of KM and TKM. Specifically, the experiment setup is the same as that in Section H.T. including the selection of kernel, repeat times, and tuning method for À and except that the underlying true function is set as (x) sin(l1x) and (x,, 322 is independently drawn from y; = sign( (x, + N (0, 4)) ,,...,300 300. The obtained numerical results are reported Figure 9 It is thus with x; 300 D that the error curves for the hinge loss align with those for the check Toss, which clear from Figure
further confirms our theoretical findings and also empirically supports that our theoretical analysis apply to SVM.
44

---

t-0.3
-06
-60
-10
-10
-18
-18
-10
-3.50
-315
-24
-210
+1.8
-035
-150
-240
+2.0
-1.5
+140
T=0.7
T=0.7
-08
-10
Lop
-28
-10
1.0
2.00
2:10
1:90
0.70
DU03
3.35
2.45
2,10
3.25
6.20
Figure 10: Kernel quantile regression; averaged log MSE and log empirical excess risk for KM and TKM versus log ratios (rl = log(r/n)) of the truncation level r to the sample size n across different quantile levels.
H.3 Exponential Decay Case
Note that our technical analysis can also cover the exponential decay case that My x exp(-oj) and 5 x cxp(-(2ya + B)j) with 3 > 0. Precisely, under the exponential decay setting, the explicit upper bound of the approximation bias term can be derived by
Σ 1=+
5 SC exp(- +8))+ 2Ta + 3 exp(- + 8)r).
L.
Note that if
1og BB we always have Σj 2j Consequently, can also derive the corresponding convergence rates under these scenarios, which suggests that both TKM and KM can attain an optimal rate whatever 7 is if is greater than certain threshold. We also conduct some numerical experiments to verify this finding.
Specifically, the experimental setup is the same as Example in Section H.I except that we set (x) sin(6x) and the Gaussian kernel used. The experiment result, presented in Figure I0 shows that TKM initially performs worse than KM for the small value of Whereas, as surpasses threshold, TKM maintains comparable performance to KM. This observation precisely aligns with our theory for the exponential decay scenario.
H.4 Determining via Cross-validation
Previously, all the tuning parameters tuned the best for both competitors. In this part, will also provide the numerical experiment with the tuning parameters selected in a data-driven fashion. Specifically, we consider the kernel quantile regression that the data is independently generated from the model y (x) + V2(E Φ -0 (T)) with fx( sin(6x), N (0, 1). In this experiment, use the Laplacian kemeel K [(xxxt x') exp(-lix x' and
0, 1 ..... n-1, and
45

---

the parameters and are tuned by 5-fold cross- validation. The obtained numerical results using the data-driven choice of r are attached in the following tables. Clearly. can be observed that TKM consistently outperforms KM, which further confirms our theoretical findings that TKM can achieve superior performance across various scenarios.
Table 3: Averaged MSE for different (T 0.3).
100
200
300
400
KM
0.583 + 0.257
0.220 E 0.104
0. 16166 + 0.071
0.121
0.374
TKM
0.367 = 0.174
0.188 I 0.078
0.140 + 0.004
0.099
0.029
Table 4: Averaged Empirical excess risk for different n (T = 0.3).
π
100
200
300
400
KM
0.323 = 0.039
0.208 + 0.040
0.175 + 0.036
0.155 + 0.059
TKM
0.289 = 0.066
0.192 + 0.060
0.161 + 0.021
0.128 + 0.018
Table 5: Averaged MSE for different (T 0.5).
100
200
300
400
KM
0.246 + 0.137
0.177 + 0.129
0.096 + 0.032
0.114 + 0.069
TKM
0.195 = 0.087 0.153 + 0.133
0.075 + 0.033
0.079 0.042
Table 6: Averaged Empirical excess risk for different n (r = 0.5).
72
100
200
300
400
KM
0.214 = 0.062
0.189 + 0.052
0.176 + 0.047
0.140
0.028
TKM
0.168 = 0.039
0.146 + 0.048
0.158 + 0.055
0.123 + 0.027
Table 7: Averaged MSE for different (T 0.7).
100
200
300
400
KM
0.434 + 0.272
0.273 E 0.099
063 + 0.086
0.121 + 0.072
TKM
0.325 = 0.195
0.200 + 0.079
0.134 + 0.072
0.098
0.054
Table 8: Averaged Empirical excess risk for different n (7 = 0.7).
100
200
300
400
KM
0.178 = 0.053
0.201 + 0.050
0.145 + 0.032
0.119 + 0.026
TKM
0.159 = 0.053
0.155 + 0.053
0.122 + 0.018
0.1 + 0.023
46

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See Abstract and Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section 0
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
47

---

Justification:
The assumptions are clearly stated in Assumptions 3.1 3.2 3.4 and all proofs
are presented in Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: See Section 5 and Appendix H
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
48

---

Answer: [Yes]
Justification: The code has been included in the supplemental material, and the data is generated through simulation or is available the UCI Machine Learning Repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/pp wwcppblic/guticcccccccceeeoooope /etggudddsse/eebbbinninn htt.SSbbbiiiiooooiiiiiooooi for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Section 5 and Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
See Section 5 and Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
49

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our simulations were done on a regular laptop. The type of compute worker and memory was described in Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We are sure to preserve anonymity and there no special consideration.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification: discussed the societal impacts of this paper in Section 6
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
50

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
51

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
52


Reviews:
[{"review_id": "O5EAQLBLjB", "reviewer": "Reviewer_rK2F", "summary": "This paper investigates the impact of target-kernel alignment to mitigate the saturation effect, where the learning rate of kernel ridge regression plateaus when the smoothness of the target function exceeds certain levels. The kernel complexity function is used to establish the upper bounds for both the standard kernel-based estimator and the truncated estimator. Also, the Fano method is employed to establish minimax lower bound when the squared loss is utilized.", "questions": "- Can you clarify how the choice of loss function impacts your theoretical results? It appears that in most cases, the squared loss is necessary. Does your analysis apply to SVMs?", "limitations": "- A more thorough experimental analysis can be helpful.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and provides a comprehensive review of related work. \n- Detailed theoretical results are given for standard and truncated kernel-based methods. \n- Confirming theoretical results by using numerical simulations.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time and great efforts in reviewing our paper and thanks a lot for your constructive comments and suggestions. Below are our point-to-point replies. \n\n**Question 1 (part I): Can you clarify how the choice of loss function impacts your theoretical results?**\n\n**Answer:** \nThank you very much for your question. In fact, the theoretical results in Theorems 3.3 and 4.2 and Corollaries  3.4 and 4.3 are established for a general loss function,  belonging to a rich loss function family with Lipschitz continuity and satisfying Assumption 3.1. As discussed after Assumption 3.1 and in Appendix E, many popularly used loss functions satisfy these requirements under some mild conditions. In the revised version, we will add more detailed discussions on the effect of the choice of loss function at the end of Section 4.1. \n\n**Question 1 (part II):  It appears that in most cases, the squared loss is necessary.**\n\n**Answer:** Thank you very much for your comments. Note that the theoretical upper bounds provided in Sections 3 and 4 are established for a general loss function, whereas the minimax lower bound provided in Section 4.2 is established only for the squared loss. We want to emphasize that it is common in literature to establish the upper bound for other loss functions and compare it to the lower bound for the squared loss to check the optimality (Wei et al., 2017; Lv et al., 2018; Li et al., 2019). Moreover, the theoretical results in Sections 3 and 4 are established by using the empirical process techniques, which is in sharp contrast to that in  Amini et al. (2022)  where only the squared loss is considered.  More detailed discussions on the differences will be added in Section 5 of the revised manuscript.\n\n**Question 1 (part III):  Does your analysis apply to SVMs?**\n\n**Answer:**\nThank you very much for your question. Note that from  Table 1 of the manuscript, the hinge loss satisfies the Lipshcitz continuity requirement with Lipshcitz constant 1. Moreover,   as pointed out by Wainwright (2019) on Page 472, Assumption 3.1 holds for the hinge loss when some conditions on data distribution and function class are satisfied.  Moreover, in this revision, we also added some numerical experiments using the hinge loss to verify our theoretical analysis, and the obtained numerical results as provided in Figure 1 of the total Rebuttal pdf file further support the applicability of our analysis to SVMs. In the revised version, we will add more detailed discussions on the applicability of the established results in Appendix E.\n\n**Limitations: A more thorough experimental analysis can be helpful.** \n\n**Answer:**\nThank you very much for your suggestion.   In the revised version,   more thorough numerical experiments will be added in Section 6 and Appendix. One added numerical experiment is to investigate the problem that once the hinge loss is specified (corresponding to SVMs), how the RKHS with varying model complexities affect the numerical performance of KM and TKM.  Clearly, this added numerical experiment serves as a complement to that reported in Section 6 of the original submission where the check loss is considered. Specifically, the experiment setup is the same as that of the original submission, including the selection of kernel, repeat times, and tuning method for $\\lambda$ and $r$ except that the underlying true function is set as $f^*(\\mathbf{x})=\\sin(11\\mathbf{x})$ and  $(\\mathbf{x}_i, y_i) _{i=1}^{300}$ is independently drawn from $y _i=\\text{sign}(f^*(\\mathbf{x} _i)+N(0, 4))$ with $\\mathbf{x}_i=\\frac{i-1}{300}, i=1, \\dots, 300$.  The obtained numerical results are reported in Figure 1 of the total Rebuttal pdf file. It is thus clear from Figure 1 that the error curves for the hinge loss align with those for the check loss, which further confirms our theoretical findings and also empirically supports that our theoretical analysis can apply to SVMs. Similarly, we will also add the numerical experiments when the logistic loss function is specified, and the numerical results will be added in Appendix.", "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": "Co392QciHD", "reviewer": "Reviewer_Pn9U", "summary": "In this paper the authors consider both truncated kernel-based method (TKM) and standard kernel-base method (KM) and how their performance is affected by the target-kernel alignment (a.k.a. the smoothness of target function in RKHS). The authors show that they have the same effects in weak and just-aligned regime, but TKM is able to tackle the saturation effect in the strongly-aligned regime since it can attain the minimax rate. The theoretical analysis of this paper includes a general class of loss function with Lipschitz continuity assumption.", "questions": "- As in the paper it is demonstrated that spectrally truncated kernel can overcome the saturation effect, can spectrally transform kernel [1] overcome it too? or improve the minimax rate? \n\n[1] Runtian Zhai et al. , Spectrally Transformed Kernel Regression", "limitations": "See weakness", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper characterizes the kernel complexity using statistical dimension and uses empirical process technique to derive the result\n- The paper discusses an interesting finding that TKM can overcome saturation effect\n- Can be any loss function with Lipschitz continuity assumption", "weaknesses": "- Some of the findings are also covered in this paper [1]\n\n[1] Arash A. Amini et al., Target alignment in truncated kernel ridge regression", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your nice summary and precious comments on this paper. Below are our point-to-point replies.\n\n**Weakness 1: Some of the findings are also covered in  Amini et al. (2022).**\n\n**Answer:**\nThank you very much for your comment. We agree with you that some findings in this paper contain the results provided in  Amini et al. (2022), where only the squared loss function is considered. In fact, this work is motivated by  Amini et al. (2022)  and part of our established results can be regarded as the extension of those in Amini et al. (2022), where a board of learning tasks is considered in our paper.  We want to emphasize that there exist some significant differences between our work and the prior work (Amini et al., 2022)  from multiple points of view.\n\nNote that  Amini et al. (2022) only considers the square loss function where the analytical solution exists, and thus their theoretical analysis heavily relies on the closed form of the solution to establish some critical results, including the theoretical bounds similar to Corollaries 3.5 and 4.3 in our paper. As opposed, our work considers a general loss function which covers many commonly\nused methods in regression and classification problems, and such explicit solution does not exist anymore, which requires different technical treatments to derive the theoretical results. Specifically, our theoretical analysis adopts an alternative analytic treatment by utilizing kernel complexity and deriving upper bounds associated with the critical radius. Our results successfully capture the trade-off between the model complexity of the truncated RKHS $\\widetilde{\\mathcal{H}}$ and approximation bias as presented in Theorem 4.2.  Moreover, we also establish the minimax lower bound when the squared loss is specified, and thus rigorously confirm the conjecture in Amini et al. (2022) stating that the truncated kernel ridge estimator attains minimax optimality. Numerically, extensive experiments are also conducted to confirm our theoretical findings and verify the existence of the trade-off between the target-kernel alignment and model complexity, which also highlights our contributions.  In the revised version,  more detailed discussions and comparisons on the differences between our work and the previous work (Amini et al., 2022) will be added in various parts, including Sections 1.1 and 5.\n\n\n**Question 1:  can spectrally transform kernel  (Zhai et al.,  2024)  overcome it too? or improve the minimax rate?**\n\n**Answer:**\n Thank you very much for your comment and for bringing us this interesting reference.  We notice that the spectrally transformed kernel regression method (SKRR;  Zhai et al.,  2024) aims to use spectrally transformation for constructing a new kernel, which can leverage the information contained in unlabeled data in an explicit way. \n\nWe believe that  SKRR may have the ability to overcome the saturation effect as well if the transformation function can be properly chosen.  The possible routine for establishing the theoretical results is discussed below. Recall that by Mercer's theorem, the kernel function admits a decomposition as  $K(\\mathbf{x}, \\mathbf{x}')= \\sum_{ j=1}^\\infty\\mu_j\\phi_j(\\mathbf{x}) \\phi_j({\\mathbf{x}}'),$\nwhere $\\mu_j$'s are the eigenvalues in descending ordering and $\\phi_j$'s are the corresponding eigenfunctions of the integral operator (Zhai et al.,  2024), and we can write the target function $f^*$ as $f^* =  \\sum_{ j=1}^\\infty \\alpha^*_j  \\phi_j$.  \n\nFor  SKRR, $K( \\mathbf{x}, {\\mathbf{x}}')$ is replaced with a new kernel that   $K'( \\mathbf{x}, {\\mathbf{x}}') = \\sum _{j=1}^\\infty s(\\mu _j) \\phi _j ( \\mathbf{x})\\phi _j ({\\mathbf{x}}')$, where  $s$ is the general transformation function. \nThe idea of deriving the upper bound is that we can separately bound the estimation error $|| \\widehat{f} _\\lambda- f^\\sharp|| _\\mu$ and approximation bias $|| f^{\\sharp}- f^*|| _\\mu$,  where $|| \\cdot || _\\mu$ denotes the norm equipped with  $ \\mathcal{L}(\\mathcal{X}, \\mu)$, and  $f^ \\sharp=\\sum _{j=1}^\\infty s(\\alpha^* _j) \\phi _j$ denotes an immediate function belonging to the RKHS induced by $K'$. \nFollowing a similar technical treatment in our paper,  the upper bound on estimation error can be established. For the approximation bias,  we notice that\n\n$$\n||{f}^{\\sharp}_r-f^*|| _\\mu^2= \\sum _{j=1}^\\infty  ( s(\\alpha _j^*)- \\alpha _j^*)^2.\n$$\n\nClearly, the selection of $s(\\cdot)$ is crucial and it is favorable if $s(\\cdot)$ is close to the identity function for small $j$ and decays extremely rapidly as $j$ tends to infinity, such as $s(\\mu_j)=\\mu_j\\mathbf{I}_{(j\\le r)}$. Then, SKRR with some proper choices of $s(\\cdot)$ may achieve similar conclusions about the upper bound as we provided in our paper.  Moreover, we think the minimax lower bound can not be improved since it is independent of any specific learning algorithm developed.  \n\nSince the theoretical derivation should be more involved, we decide to leave such a promising topic as potential future work, but add some detailed discussions on the possible route for establishing the theoretical results of SKRR in Appendix A of the revised version.", "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": "ijYnnOk6zO", "reviewer": "Reviewer_4evc", "summary": "This paper conducts a comprehensive theoretical analysis on the learning rate of kernel-based machine learning methods under a general setting. It establishes the upper bounds for standard kernel-based estimators, and demonstrates that standard kernel-based estimators suffer from saturation effect at high target-kernel alignment levels. It proves that the learning rate of truncated kernel-based estimators, where kernel matrices are spectrally truncated, continues to improve even at high alignment levels, indicating an improvement over standard estimators. It establishes minimax lower bound for both standard and truncated kernel-based estimators, and demonstrates that the standard kernel-based estimator can only attain suboptimality for the strong-aligned regime, while the truncated estimator is minimax-optimal. The author conducts various experiments on regression and classification problems to demonstrate the advantages of the truncated estimator and support the established theory.", "questions": "1) If the loss function is not Lipschitz continuous (e.g. 0-1 loss), would any of the results presented in the paper change? For instance, would the learning rate bounds for standard kernel-based estimators established in Section 3 remain the same?\n2) Are the choices of r and lambda mentioned in Section 4 the only feasible choices to achieve optimal learning rate for TKM?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The paper reveals that the saturation effect, i.e. the phenomenon that the learning rate of kernel ridge regression (KRR) no longer improves at high target-kernel alignment levels, also occurs in general kernel-based methods other than KRR. This discovery extends the original focus on KRR’s learning rate to general kernel-based methods, and may spark more interest and research in this direction.\n2) The paper demonstrates theoretically and experimentally that truncated kernel-based method (TKM) can overcome the saturation effect in a general loss-function setting. This indicates that the saturation effect can be addressed not only in KRR, but also in general kernel-based methods. It may provide insights for future research on tackling saturation effect and improve learning rate of kernel methods.\n3) The theoretical analysis is comprehensive and rigorous. Sufficient details are provided to help understand and verify the paper.", "weaknesses": "1) The truncated kernel-based method (TKM) considered in this paper is not a very novel approach. As mentioned in the paper, truncated KRR (Amini, 2021; Amini et al., 2022) also uses spectral-truncated kernel matrix as the underlying method; the main difference between TKM and truncated KRR is that TKM considers a more general loss function family, while truncated KRR specifies a squared loss. In other words, TKM is basically a generalized version of truncated KRR; hence, the methodological contribution of this paper is limited and largely incremental.\n2) The work in this paper only considers Lipschitz continuous loss functions. It is a reasonable setting, but there do exist some non-Lipschitz continuous loss functions in practice, e.g. 0-1 loss. The paper doesn’t take such condition into account; this limits its scope of application.\n3) The use of symbols and notations in some formulas is somewhat confusing. For example, in Section 1, the symbol r is used to denote target-kernel alignment level, but in Sections 3 and 4 the authors denote target-kernel alignment as gamma, and r becomes the dimensionality of reduced RKHS. It would be better if the authors could make their use of symbols and notations consistent throughout the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Your insightful comments and constructive suggestions are highly valued by us, and greatly contributed to the revision of this work. Below are our point-to-point replies.\n\n**Weakness 1:  TKM considered in this paper is not a very novel approach.**\n\n**Answer:** Thank you very much for your comment.  We agree that TKM considered in this paper is not a very novel approach and we admit that this paper is motivated by the prior work   (Amini et al., 2022)  where only the squared loss function is considered and the investigation on the problem of optimality is lacking.  In sharp contrast, our theoretical results are established for a general loss function by using totally different technical treatments,  which covers many commonly used methods in regression and classification problems, and a minimax lower bound is also established for the squared loss function, which confirms the optimality of TKM. \n\nWe want to emphasize that some significant gaps exist between our work and the prior work  (Amini et al., 2022) and we list some of them below.    Amini et al. (2022) only considers the square loss function where the analytical solution exists, and thus their theoretical analysis heavily relies on the closed form of the solution to establish some critical results, including the theoretical bounds similar to Corollaries 3.5 and 4.3 in our paper. As opposed, our work considers a general loss function and such an explicit solution does not exist anymore, which requires different technical treatments to derive the theoretical results.  Specifically, our theoretical analysis adopts an alternative analytic treatment by utilizing kernel complexity and deriving upper bounds associated with the critical radius. Moreover, we rigorously establish the minimax lower bound when the squared loss is specified, which is unsolved in  Amini et al. (2022) and confirms the optimality of the truncated kernel method. Extensive numerical studies are also provided in our paper, which further supports our theoretical findings and verifies the existence of the trade-off between the target-kernel alignment and model complexity.  This also highlights our contributions. \n\nIn this revision, various parts have been revised and more detailed discussions have been added to highlight the contributions of this paper, including Sections 1.1, 4 and 5.\n\n**Weakness 2 \\& Question 1: Non-Lipschitz continuous loss functions, e.g. 0-1 loss.**\n\n**Answer:** Thank you very much for your comment. It is true that the established results in this paper require the Lipschitz continuity assumption, and can not be directly applied to the non-Lipschitz continuous cases. Yet, we want to emphasize that this type of Lipschitz continuity assumption is commonly considered in the literature of machine learning  (Steinwart & Christmann, 2008; Wei et al., 2017; Li et al., 2019; Farrell et al., 2021),  which covers many commonly used loss functions as illustrated in Table 1 of the manuscript.\n\nWhen the loss function is non-Lipschitz continuous or even not continuous, extending our established results to the general non-Lipschitz continuous setting is not trivial due to the technical difficulties, such as the application of Talagrand’s concentration inequality requires the Lipschitz continuity of loss function. However, once the $0$-$1$ loss is considered, one possible routine for establishing the theoretical results for $0$-$1$ loss is to follow a similar technical treatment as that on Page 17 of Lai et al. (2024) with some slight modifications, where the bridge between the excess risk w.r.t $0$-$1$ loss and mean squared error is established, and based on the result in Lai et al. (2024), the excess risk only gets a slower rate compared to the rates established in our paper. \n\nIt is also interesting to point out that optimizing the $0$-$1$ loss is very difficult. In literature, it is common to replace it with a convex surrogate loss function, such as the logistic loss function, which is covered by our paper. We will leave this very interesting problem for future work, but add more detailed discussions on possible routines for the extension to the non-Lipschitz continuous case in the revised manuscript.\n\n**Weakness 3: Confusion of notation and symbols in some formulas.**\n\n**Answer:** Thank you very much for pointing out this problem.  We apologize for this abuse of notation. In this revision, this problem has been corrected that we consistently use $r$ to denote the dimensionality of the reduced RKHS, and use $\\gamma$ to denote the target-kernel alignment level. Moreover, we have proofread this manuscript again and made our best efforts to correct all the typos, confusing notations and symbols.\n\n**Question 2: The choices of $r$ and $\\lambda$.**\n\n**Answer:** Thank you very much for your question. Indeed, the theoretical orders of $r$ and $\\lambda$ mentioned behind Theorem 4.2 and in Corollary 4.3 of Section 4 are the only feasible choices to achieve optimal learning rate for TKM.  Specifically, under Assumption 3.4, the optimal choice of $\\lambda$ is unique that $\\lambda\\asymp \\delta_{n,r}^2 \\asymp \\big(\\frac{(\\log \\iota^{-1})^2}{n}\\big)^{\\frac{\\max(\\gamma,1) \\alpha}{2\\gamma\\alpha+1}}$ to balance the variance and bias, and the unique optimal choice of $r$ is $ r\\asymp (\\frac{n}{(\\log \\iota^{-1})^2})^{\\frac{1}{2\\gamma\\alpha+1}}\\text{I} _{(\\gamma> 1)}+n\\text{I} _{(\\frac{1}{2}\\le \\gamma\\le 1)}$ to balance the estimation error and approximation bias.  We want to emphasize that in literature, it is common to require the explicit unique orders of the parameters to achieve the fast learning rate (Yang et al., 2017; Wei et al., 2017; Cui et al., 2021; Amini et al., 2022). In practice, the values of $r$ and $\\lambda$ can be determined by using some data-driven procedures, such as the cross-validation technique. More detailed discussions on the choices of the two parameters will be added in Section 4 of the revised manuscript.", "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": "rBCnCbsUzW", "reviewer": "Reviewer_Twpu", "summary": "This paper investigated the impact of alignment between the target function of interest and kernel matrices.\nTo overcome the saturation effect, the TKM was introduced and its learning rate is analyzed.", "questions": "None.", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper is well-written and the theorems are solid.\n\nThis paper analyzed different alignment level and the learning rate in these cases.\nTKM decreases the kernel complexity to achieve the trade-off between model complexity and approximation error.", "weaknesses": "The approximation bias term in Thm 4.2 requires Assumption 3.4 holds. Could you also provide some results for different decay rate?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time in reviewing our work and thanks a lot for your question and valuable comments. We have carefully addressed your question below and provided some results for the exponential decay rate.\n\nIndeed, Assumption 3.4 is needed if we want to derive the explicit upper bound of the approximation bias term established in Theorem 4.2. Note that our technical analysis can also be modified to consider the exponential decay case that $\\widehat{ \\mu} _j  \\asymp \\exp(-\\alpha j)$ and ${\\xi_j^*}^2 \\asymp \\exp(-(2\\gamma \\alpha + \\beta) j)$ with $\\alpha, \\beta > 0$. \n\nPrecisely, under the  exponential decay setting, the explicit upper bound of the approximation bias term can be derived by\n\n$$\n\\sum _{j=r+1}^n{\\xi^* _j}^2 \\le C \\int _r ^\\infty \\exp(-(2\\gamma \\alpha + \\beta) t) dt = \\frac{C}{2\\gamma \\alpha + \\beta } \\exp(-(2\\gamma \\alpha + \\beta) r).\n$$\n\nNote that if $r\\ge\n\\frac{\\log n }{(2\\gamma \\alpha + \\beta)}$, there holds $\\sum_{j=r+1}^n{\\xi^*_j}^2\\lesssim \\frac{1}{n}$. Consequently, we can also derive the corresponding convergence rates under these scenarios, which suggests that both TKM and KM can attain an optimal rate whatever $\\gamma$ is if $r$ is greater than a certain threshold (to be added in the revised version). We also conduct some numerical experiments to verify this finding.\nSpecifically, \nthe experimental setup is the same as Example 1 in Appendix G of the manuscript except that we set $f^*(\\mathbf{x})=\\sin(6\\mathbf{x}) $ and  Gaussian kernel is used. The experiment result, presented in Figure 2  in the total Rebuttal pdf file, shows that  TKM initially performs worse than KM for very small value of $r$. Whereas,  as $r$ surpasses a threshold, TKM maintains comparable performance to KM. \n\nThis observation precisely aligns with our theory for the exponential decay scenario. \nIn this revision, more detailed results and discussions of this setting will be added in Section 4.1 and Appendix.", "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": "f2aoalSbZm", "reviewer": "Reviewer_ikTW", "summary": "This paper provides an in-depth error analysis of of kernel ridge regression (KRR) and truncated KRR (TKRR), where one replace the original kernel $K$ with its finite $r$-dimensional approximation $K^T$, such that their regressors $\\hat{f}$ and $\\hat{f}_r$ agree on the dataset. It is well known that KRR suffers from the so-called *saturation effect*, where increasing the smoothness/alignment of the target function cannot further improve the generalization performance after a certain threshold. TKRR, on the other hand, with correctly selected hyperparameter $r$, can continuously improve the generalization performance as the target function is more and more aligned with the reproducing kernel Hilbert space (RHKS) $\\mathcal{H}$ of the kernel $K$.", "questions": "I have several remark/questions regarding the algorithmic perspective on TKRR:\n\n1. Let $\\mathbf{K} = \\mathbf{U}^\\top\\mathbf{D}\\mathbf{U}$ be the diagonalization of the kernel matrix w.r.t. inputs $X = \\\\{\\mathbf{x}\\_i\\\\}\\_{i=1}^n$, and $ S_X : \\mathcal{H}\\_K \\to \\mathbb{R}\\^n $ be the evaluation operator $f \\mapsto (f(\\mathbf{x}\\_1),...,f(\\mathbf{x}\\_n))^\\top$. By line 239 in the paper (there is a small typo in the definition of $\\psi_k$, see below for the correct one), the finite dimensional RKHS $\\tilde{\\mathcal{H}}\\subset \\mathcal{H}$ has the basis $\\\\{ \\psi_k \\\\}\\_{k=1}^r$ where $r\\leq n$ and $\\psi_k := \\text{argmin} \\\\{ \\\\| \\psi \\\\|_K:\\psi\\in\\mathcal{H}, S_X(\\psi) = \\mathbf{u}_k \\\\}$ with $\\mathbf{u}_k$ the $k$-th column of the matrix $\\mathbf{U}$. This definition of $\\psi_k$ is simply the kernel interpolant: $\\psi_k(x) = \\mathbf{u}^\\top\\mathbf{K}^{-1}\\mathbf{K}_x$. Hence the computational bottleneck is the inversion of $\\mathbf{K}$ with complexity $\\mathcal{O}(n^3)$, and thus the total complexity of TKRR should not be much larger than KRR. Although it is not difficult to see, I think it is still worth a small section/paragraph to discuss this.\n\n2. The choice of the hyperparameter $r$ is important when the alignment parameter $\\gamma$ is at least $1/2$. But how can one determine the optimal choice of $r$ if $\\gamma$ is not directly accessible?", "limitations": "This is a theoretical paper. All limitations are stated clearly in the statements.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper offers a very general theoretical result on kernel performance with various losses, in contrast to the square loss considered in much of the previous literature. Additionally, this paper works under realistic assumptions and presents numerical validations to support its claims. The TKRR method presented in [Amini2021] and this paper offer a simple way to bypass the saturation effect of KRR, which might have significant applications in many realistic settings.\n\nReference:\nAmini, A. A. (2021). Spectrally-truncated kernel ridge regression and its free lunch. Electronic Journal of Statistics, 15, 3743–3761.", "weaknesses": "No major weakness is spotted in this paper. However, as a new algorithm, I think that there should be more discussion on the computational complexity TKRR, which is lacking in both [Amini201] and this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your acknowledgment and positive feedback on this work. Your valuable suggestions and comments are very helpful and significantly improve this paper. Below are our point-to-point replies.\n\n**Weakness 1 \\&  Question 1 (Part I): More discussion on the computational complexity of TKRR.**\n\n**Answer:**  Thank you very much for your precious suggestions on the computational complexity.  The total computational complexity of the truncated kernel method (TKM) is composed of three parts.   In the first part, spectrally decomposing the kernel matrix $\\mathbf{K}$ has the computational complexity of $\\mathcal{O}(n^3)$. In the second part, as pointed out by you, the basis $(\\psi _k) _{1\\le k \\le r}$  can be simply calculated by  $\\psi _k(\\mathbf{x})= \\mathbf{u}_k^T\\mathbf{K} ^{-1} \\mathbf{K} _{\\mathbf{x}}$, \nwhich also has  $\\mathcal{O}(n^3)$ computational complexity. In the last part, deriving the kernel estimator based on the $r$-dimensional RKHS $\\widetilde{\\mathcal{H}}$ has computational complexity of  $\\mathcal{O}(nr^2)$.  To sum up,  the overall computational complexity of TKM is $\\mathcal{O}(n^3)$ and clearly, the truncated method does not impose an additional computational cost compared to the standard kernel method. Following your suggestion, detailed discussions and comparisons on the computational complexities of  TKM and the standard kernel method have been added in Section 5 of the revised manuscript.\n\n**Question 1 (Part II): There is a small typo in the definition of  $\\psi_k$.**\n\n**Answer:**\nThank you very much for pointing out this typo and correcting it. In the revised version, this typo has been fixed and we have carefully proofread the manuscript again and tried our best to correct all the typos.\n\n**Question 2: How can one determine the optimal choice of $r$ if $\\gamma$ is not directly accessible?**\n\n**Answer:** Thank you very much for your question.  Indeed, the choice of the hyperparameter $r$ is crucial for the theoretical results of TKM that it balances the estimation error and approximation bias as discussed after Theorem 4.2, and the optimal theoretical choice of $r$ depends on the alignment parameter  $\\gamma$ under the setting $\\gamma\\ge 1/2$.  Note that a similar analysis framework is also considered in  Amini et al. (2022). In practice, since the underlying parameter $\\gamma$ is unknown, some data-driven strategies, such as the cross-validation procedure, can be used to determine the possible optimal choice of $r$. In our numerical example in Section 6,   all the tuning parameters are tuned to the best for both competitors and in this revision, we will also add the numerical experiments with the tuning parameters selected in the data-driven fashion, and part of the numerical results are provided below. Specifically, we consider the kernel quantile regression that the data is independently generated from the model $y=f^*(\\mathbf{x})+\\sqrt{2}(\\varepsilon-\\Phi^{-1}(\\tau))$ with $f^*(\\mathbf{x})=\\sin(6\\mathbf{x})$, $\\mathbf{x}=\\{0, \\frac{1}{n}, \\dots, \\frac{n-1}{n}\\}$, and $\\varepsilon\\sim N(0, 1)$. In this experiment, we use the Laplacian kernel  $K(\\mathbf{x}, {\\mathbf{x}}')=\\exp(-||\\mathbf{x}-{\\mathbf{x}}'||_1)$, and the parameters $r$ and $\\lambda$ are tuned by  $5$-fold cross-validation.  \nClearly, it can be observed from the obtained numerical results, attached in the following tables,  that using the data-driven choice of $r$, TKM consistently outperforms KM, which further confirms our theoretical findings that TKM can achieve superior performance across various scenarios.  In the revised version, some additional numerical experiments will be added in Appendix and more detailed discussions on this issue will be provided in Section 6 and Appendix. \n\n\n\n**Table 1： Averaged MSE for different $n$ ($\\tau=0.3$).**\n| $n$  | $100$           | $200$           | $300$           | $400$           |\n|------|-----------------|-----------------|-----------------|-----------------|\n| KM   | $0.583 \\pm 0.257$ | $0.220 \\pm 0.104$ | $0.165 \\pm 0.071$ | $0.121 \\pm 0.374$ |\n| TKM  | $0.367 \\pm 0.174$ | $0.188 \\pm 0.078$ | $0.140 \\pm 0.004$ | $0.099 \\pm 0.029$ |\n\n**Table 2： Averaged empirical excess risk for different $n$ ($\\tau=0.3$).**\n| $n$   | $100$            | $200$            | $300$            | $400$            |\n|-------|------------------|------------------|------------------|------------------|\n| KM    | $0.323 \\pm 0.039$ | $0.208 \\pm 0.040$ | $0.175 \\pm 0.036$ | $0.155 \\pm 0.059$ |\n|       |                  |                  |                  |                  |\n| TKM   | $0.289 \\pm 0.066$ | $0.192 \\pm 0.060$ | $0.161 \\pm 0.021$ | $0.128 \\pm 0.018$ |\n|       |                  |                  |                  |                  |", "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:
Dear Reviewers,

We sincerely thank you for your insightful comments and for the time you have dedicated to thoroughly reviewing our work.  Your valuable and constructive feedback has significantly contributed to enhancing the quality of our work.
We have carefully considered all comments, concerns, and questions and have provided detailed responses to each review separately. These responses have been meticulously incorporated into the revised paper, mainly covering the following aspects: 
- Highlighting the contributions of our paper from both theoretical and practical perspectives;
- Providing  deeper insights into the established results from both theoretical and numerical aspects; discussing the potential future direction, including the extension to non-Lipschitz continuous case;
-  Conducting additional experiments to further validate our theoretical findings, and part of the numerical results are contained in the attached pdf file；
- Correcting all typos and ensuring clarity of the introduced symbols and expressions.

Once again, we extend our sincere gratitude for your time, expertise, and contribution to our work. We would be grateful for your reply to ensure that all your concerns have been adequately addressed,  and we welcome any additional comments or suggestions you might have.

Warm regards,

the Authors

Meta-review: After reviewing the paper, reviewer comments, and author rebuttal, I recommend accepting this submission (poster).  During the rebuttal the authors satisfied several of the reviewer (and AC) comments, clarifying the contribution over existing works (extending TKM analysis to general Lipschitz functions and providing mimimax bounds), extended the analysis of TKM to target alignment with exponential decay rate, and providing some additional numerical verification on synthetic and small real-world datasets.  I expect the authors to update the final draft with these clarifications and additional results.
Decision: Accept (poster)