On the Target-kernel Alignment: a Unified Analysis with Kernel Complexity

Authors: chao  wang
yuwen  wang
junhui  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 15:12:14

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.

Main paper: 
 introduction: 
 Kernel-based methods have attracted increasing attention in recent years (Belkin et al., 2018; Liang & Rakhlin, 2020; Ghorbani et al., 2020; Li et 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 al., 2021) . It is of fundamental importance to provide theoretical explanations of their behaviors under these research topics.In literature, some recent works show that the learning rate of 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; Smale & Zhou, 2007) . Particularly, the existing learning rate for the kernel ridge regression (KRR) is proved to be O(n -2αγ 2αγ+1 ) for 1 2 ≤ γ ≤ 1, where γ is known as the source condition parameter (Cui et al., 2021 ) and can be treated as a measure of target-kernel alignment at the population level, and α controls the model complexity of the RKHS. This rate aligns with the intuitive sense that strong alignment and small model complexity contribute to a faster learning rate. Yet, with the increasing in γ such that γ > 1 which corresponds to a smoother target function, the best learning rate of KRR plateaus at O(n -2α 2α+1 ) (Caponnetto & 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; Gerfo 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 (2021) ; Amini et al. (2022) propose a truncated KRR based on the spectral-truncated 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.In this paper, motivated by this theoretical gap, we investigate the impact of target-kernel alignment through kernel complexity from the kernel complexity perspective for various kernel-based methods by considering a general loss function which belongs to a 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., 2021; 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 on the kernel complexity which quantifies the complexity of the RKHS (Bousquet & Herrmann, 2002) 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 4.3 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.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 a 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 a 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 (γ = 1 in Assumption 3.2), the learning rate of the kernel-based estimator plateaus with no improvement as γ 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 kernel-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 a unified perspective for realistic scenarios where the true target is assumed to reside in the RKHS. (iii) Various numerical experiments are conducted in the context of various regression and classification 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 trade-off arising from the model complexity of the RKHS and target-kernel alignment.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-based estimator have been established in Caponnetto & De Vito (2007) ; Li et al. (2007) ; Smale & Zhou (2007) ; Patle & 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 target-kernel alignment to some other learning tasks, including regression (Kandola et al., 2002) and multi-class classification (Guermeur et 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, 2011) .Most recently, many works have attempted to provide a theoretical understanding of the kernel-based method by considering the target-kernel alignment. Specifically, Canatar 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. Amini (2021) considers a spectrally truncated KRR and demonstrates that with a carefully chosen truncation, the truncated KRR outperforms the standard KRR. Li et al. (2022) verifies the saturation effect observed behind the KRR estimator by establishing a lower bound that O(n -2α 2+α ) whatever the smoothness degree of the target function is. Motivated by these works, Amini et 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. 
preliminaries: 
 Background on RKHS. Let H K denote the reproducing kernel Hilbert space (RKHS) induced by a positive semi-definite kernel function K(•, •) : X × X → R + , where X ⊂ R p . The inner product equipped withH K is denoted as ⟨•, •⟩ K with the endowed norm ∥ • ∥ 2 K = ⟨•, •⟩ K . For each x ∈ X , it is well-known that K x := K(x, •) ∈ H K and the reproducing property holds that ⟨f, K x ⟩ K = f (x)for all f ∈ H K . We assume that sup x,x ′ ∈X K(x, x ′ ) ≤ κ 2 for some positive constant κ. This condition is commonly assumed in literature and various popularly used kernel functions satisfy this condition, including the Gaussian kernel and Laplacian kernel.Problem setup. We consider a collection of pairs {(x i , Y i )} n i=1 where {x i } n i=1 is a collection of covariates and the response Y i is independently drawn from a conditional distribution P Y |xi on Y ⊂ R. Throughout this paper, we focus on the fixed design setting, where {x i } n i=1 are fixed, otherwise we treat all the random quantities as conditioning on {x i } n i=1 . A similar treatment also appears in Yang et al. (2017) ; Wei et al. (2017) ; Amini et al. (2022) .In the literature of machine learning, the learning task is often defined with some pre-specified loss function. Specifically, we consider a loss function L(•, •) : R × R → R + , where L(y, f (x)) quantifies the inaccuracy for predictor f (x) when y is the true response. Then, the population risk function can be defined asE(f ) := E Y n 1 n n i=1 L Y i , f (x i )),where E Y n denotes the expectation taken over Y 1 , ..., Y n . In literature, the target function of interest in the learning task is typically defined as the minimizer of the population risk f * = argmin f E(f ).In this paper, we assume f * ∈ H K 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 positive constant M L,b2 such that for any y ∈ Y and x ∈ X , and for any f, f ′ ∈ H K satisfying max{∥f ∥ K , ∥f ′ ∥ K } ≤ b, the following inequality holds:|L(y, f (x)) -L(y, f ′ (x))| ≤ M L,b |f (x) -f ′ (x)|.It is worth pointing out that the local Lipschitz continuity is satisfied for a variety of commonly used loss functions, and some of them are listed in Table 1 . Squared Exponential Check Hinge Huber LogisticML,b 2U + 2bκ 3 1 1 1 τ 4 1Note that the choice of the loss function is task-specific based on the problem of interest and prior knowledge on 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-based classification and the logistic loss can be specified for estimating the conditional probability. 
standard kernel-based method: 
 In the rest of this paper, we use lowercase letters {y i } n i=1 to denote the observations of {Y i } n i=1 , and denote the empirical measure of {x 1 , ..., x n } by P n . Given an estimator f , its accuracy can be evaluated by the L(P n )-error which is defined as∥ f -f * ∥ 2 n = 1 n n i=1 ( f (x i ) -f * (x i )) 2 .We also use the excess risk that E( f ) -E(f * ) as an evaluation measure. To estimate the underlying target function f * , we consider the following penalized empirical risk minimization problem thatEQUATIONwhereE(f ) = 1 n n i=1 L(y i , f (x i ))and λ is regularization parameter. We define a sample operator S x : H K → R n as S x (f ) := 1 √ n (f (x 1 ), ..., f (x n )) ⊤ , and its adjoint operator S ⊤x : R n → H K is defined asS ⊤ x (α) := 1 √ n n j=1 α j K(•, x j ), α = (α 1 , ..., α n ) ⊤ ∈ R n .Then, by the representer theorem (Kimeldorf & Wahba, 1971) , the minimizer of the learning task (1) must have a finite form that f λ = S ⊤ x ( α) where α ∈ R n is the solution to the following optimization taskα = argmin α∈R n E(S ⊤ x (α)) + λα ⊤ Kα . Let K = 1 n K(x i , x j ) n i,j=1be the empirical kernel matrix where the scaling is for analytical simplicity. In the subsequent analysis, we further assume that K is positive which is also required in literature (Liang & Rakhlin, 2020; Amini et al., 2022) . Then, the kernel matrix K admits an eigen-decomposition that K = U D U ⊤ , where U = (u 1 , ..., u n ) ∈ R n×n is an orthonormal matrix and D ∈ R n×n is a diagonal matrix with positive elements µ 1 , ..., µ n arranging in a descending ordering. Without of loss generality, we further require that µ j → 0 as j → ∞.Let ξ * = U ⊤ S x (f * ). The elements of the vector ξ * are referred to as target alignment (TA) scores (Amini et al., 2022) , which quantify the agreement level between f * and K. Intuitively, a more 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 S x (f * ) 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, ξ * j is expected to be as large as possible for small j and as small as possible for large j. An ideal scenario is that S x (f * ) exactly matches the eigenvector u 1 , leading to ξ * = (1, 0, ..., 0) ⊤ with proper scaling such that ∥f * ∥ 2 n = 1. 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.The following necessary assumption is needed in our theoretical analysis. Assumption 3.1. There exist two constants0 < c 0 ≤ c ′ 0 such that c 0 ∥f -f * ∥ 2 n ≤ E(f ) -E(f * ) ≤ c ′ 0 ∥f -f * ∥ 2 n , for any f ∈ H K satisfying ∥f -f * ∥ 2n ≤ b with some sufficiently small constant b > 0.The first inequality in Assumption 3.1 is a c 0 -locally strong convexity condition, and the second inequality is a c ′ 0 -local smooth condition of the loss function with respect to ∥ • ∥ n . Assumption 3.1 is commonly assumed in literature (Steinwart & Christmann, 2008; Wei et al., 2017; Li et al., 2019; Farrell et al., 2021) . Due to space limit, some brief discussions are provided below. For the squared loss, Assumption 3.1 is satisfied with c 0 = c ′ 0 = 1. For the check loss, the c 0 -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 c ′ 0 -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 γ ≥ 1 2 and u ≥ 2 such thatn j=1 ξ * j 2 µ j -2γ ≤ u 2 for any n.Assumption 3.2 imposes the regularization on the TA scores ξ * concerning K. Note that the parameter γ reflects the degree of target-kernel alignment, where a larger γ indicates stronger alignment between K and f * . Moreover, the parameter γ in Assumption 3.2 can be considered analogous to the source condition parameter under the random design setting (Caponnetto & De Vito, 2007; Cui et al., 2021; Li et al., 2023) . Further discussions on the extension to the random setting are deferred to Appendix B. In our subsequent analysis, we consider the following three cases that • Just-aligned regime: γ = 1 2 where we only assume f * ∈ H K . • Weakly-aligned regime: 1 2 < γ ≤ 1 where f * ∈ H K and is more aligned with K. • Over-aligned regime: γ > 1 where f * ∈ H K and has a strong alignment with K.In the rest of this paper, we use C to denote some constant independent of n, γ, α, which may hide the constants such as u, c 0 , c ′ 0 and whose values may vary from line to line. In literature, the empirical kernel complexity function is defined as R(δ) := 1 n n j=1 min{δ 2 , µ j } (Bartlett et al., 2005) . R(δ) serves as a measure of complexity of H K 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 δ n , defined as the smallest positive value δ such thatEQUATIONwhere η = min{γ, 1} and ι is specified in the subsequent theorems and corollaries. The learning rate of the kernel-based estimator defined in (1) highly depends on δ n , and the existence and uniqueness of δ n are verified in Appendix B.1. As pointed out in Yang et al. (2017) , the statistical dimension is defined as the first index for which the associated eigenvalue µ j drops below δ 2 that d(δ) := min{j ∈ [n] : µ j ≤ δ 2 }, where [n] = {1, 2, .., n} and d(δ) := n if {j ∈ [n] : µ j ≤ δ 2 } = ∅.Note that the statistical dimension serves as a 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 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 d(δ)δ 2 /n. The close connection between d(δ) and R(δ) enables us to find the explicit formulation of δ n in our theoretical analysis.n d(δ)+1 µ j ≲ d(δ)δ 2 (The following theorem provides theoretical guarantees of f λ defined in (1) in terms of L(P n )-error and the excess risk which hold with high probability. Theorem 3.3. Suppose that Assumptions 3.1 and 3.2 are satisfied and δ 2 n ≤ λ ≤ 15 . Let η = min{γ, 1}. Then, for any ι ∈ (0, 1), with probability at least 1 -ι, there holdsmax ∥ f λ -f * ∥ 2 n , E( f λ ) -E(f * ) ≤ C(δ 4η n + λ 2η ).The proof of Theorem 3.3 is provided in Appendix C. To complete the proof of Theorem 3.3, we only need to require the first inequality in Assumption 3.1. Note that the established bound for f λ consists of two terms that are related to the critical radius δ n and the parameter λ. 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 kernel-based estimators by considering a 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 λ ≍ δ 2 n , an optimal rate can be achieved that Amini et al. (2022) provides some valuable insights into the learning rate of the kernel-based estimator under the squared loss in terms of the expected L(P n )-error where the following polynomial decay condition is required. Assumption 3.4. There exist some constants α > 1 and γ ≥ 1 2 such that the eigenvalues of K and the TA scores exhibit polynomial decay rate that µ j ≍ j -α and ξ * j 2 ≍ j -2γα-1 .E( f λ ) -E(f * ) ≍ ∥ f λ -f * ∥ 2 n ≍ δ 4η n . Note thatIn Assumption 3.4, the parameter α controls the complexity of H K in the sense that a decreasing α results in the increasing compacity of the RKHS H K (Cui et al., 2021; Amini et 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 ξ * j 2 ≍ j -2γα-1 (log j) -2 , it can be verified that Assumption 3.4 directly leads to Assumption 3.2 if we ignore the logarithmic term. By Assumption 3.4, it is clear that d(δ) ≍ δ -2/α , and consequently δ 2 n ≍ (log ι -1 ) 2 n α 2ηα+1 . To better understand the established results in Theorem 3.3, the following corollary is also provided. Corollary 3.5. Suppose that Assumptions 3.1, 3.2 and 3.4 are satisfied. Let η = min{γ, 1}. For any ι ∈ (0, 1), if we choose λ ≍ (log ι -1 ) 2 n α 2ηα+1 , then with probability at least 1 -ι, there holds∥ f λ -f * ∥ 2 n ≍ E( f λ ) -E(f * ) ≤ C (log ι -1 ) 2 n 2ηα 2ηα+1 .Under the just-aligned regime that γ = 1 2 , the learning rate turns to be (log ι -1 ) 2 /n α α+1 , which is consistent with that in literature (Wei et al., 2017) where merely assumes f * ∈ H K . Yet, under the weakly-aligned regime that 1 2 < γ ≤ 1, the learning rate exceeds (log ι -1 ) 2 /n α α+1 due to the stronger target-kernel alignment. More interestingly, under the over-aligned regime that γ > 1, the learning rate plateaus with no improvement as γ increases, which indicates a saturation effect for the standard kernel-based method. It is also interesting to notice that no matter how the choice of λ, the learning rate is always lower bounded by O(n -2α 2α+1 ) for γ ≥ 1 (Li et al., 2022) . 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. 
truncated kernel-based method: 
 To construct the reduced RKHS, we introduce a collection of functions {ψ k } k∈[n] ⊂ H K , defined as ψ k := argmin ∥ψ∥ K : ψ ∈ H K , S x (ψ) = u k . It can be verified that {ψ k } k∈[n] is unique and by the orthogonality of u 1 , ..., u n , we also have ⟨ψ i , ψ j ⟩ n = 1 for i = j and 0 otherwise (Amini et al., 2022) . Then, for a given r, we define a function space asH Kr := r k=1 α k ψ k : α = (α 1 , ..., α r ) ⊤ ∈ R r .Let H Kr be equipped with the norm ∥f ∥ 2 Kr = ⟨f, f ⟩ Kr , where the inner product is defined as ⟨f, g⟩ Kr :=r k=1 α k β k /µ k for f = r i=1 α k ψ k and g = r i=1 β k ψ k .The following lemma from Amini et al. (2022) indicates that H Kr is also an RKHS associated with a different kernel function. Lemma 4.1.H Kr ⊂ H K is an r-dimensional RKHS with reproducing kernel K r (x, x ′ ) = r k=1 µ k ψ k (x)ψ k (x ′ ).Clearly, H Kr can be treated as a relatively smaller function space compared to the full RKHS H K . Based on H Kr , we can find a truncated kernel-based estimator by solvingf λ,r = argmin f ∈H Kr E(f ) + λ∥f ∥ 2 Kr .For the truncated RKHS H Kr , we also define the operator S ⊤ x,r : R n → H Kr asS ⊤ x,r (α) := 1 √ n n j=1 α j K r (•, x j ), α = (α 1 , ..., α n ) ⊤ ∈ R n .Then, by the representer theorem (Kimeldorf & Wahba, 1971 ) again, f λ,r also has a finite solution that f λ,r = S ⊤ x,r ( α r ) and α r can be obtained by solving the following optimization taskα r = argmin α∈R n E(S ⊤ x,r (α)) + λα ⊤ Krα .where Kr = 1 n K r (x i , x j ) n i,j=1 is the empirical kernel matrix w.r.t. K r . 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 {ψ i } i∈ [n] , it is easy to verify that Kr = U DrU ⊤ , where Dr is diagonal matrix with elements µ 1 , ..., µ r , 0, ..., 0, detailed proof can be seen in Appendix B.2. This further implies that Kr = K when r = n, and thus leads tof λ (x i ) = f λ,n (x i ) for each i ∈ [n].Given the truncated RKHS H Kr , our theoretical results below rely on the truncated kernel complexity function, defined as R r (δ) := 1 n r j=1 min{δ 2 , µ j }. Moreover, the critical radius δ n,r can be defined as the smallest positive value δ such thatEQUATIONThe existence and uniqueness of δ n,r are verified in Appendix B.1. It can be verified that R r (δ) ≤ R(δ) and thus leads to δ n,r ≤ δ n . This observation indicates a potential improvement of the truncated estimator f λ,r and is the core of our theoretical analysis. The following theorem shows that f λ,r converges to the underlying target in terms of the L(P n )-error and the excess risk with high probability.Theorem 4.2. Suppose that Assumptions 3.1 and 3.2 are satisfied and max{δ 2 n,r ,n j=r+1 ξ * j 2 } ≤ λ ≤ 1. Let η = min{γ, 1}.Then, for any ι ∈ (0, 1), with probability at least 1 -ι, there holdsmax ∥ f λ,r -f * ∥ 2 n , E( f λ,r ) -E(f * ) ≤ C δ 4η n,r + λ 2η + n j=r+1 ξ * j 2 .The proof of Theorem 4.2 is provided in Appendix D. The established upper bound of f λ,r first decomposes the total error into two components: estimation error (the first two terms), which is controlled by complexity of the reduced RKHS H Kr , and approximation bias (the last term), which results from the dissimilarity between the truncated RKHS H Kr and the full RKHS H K where f * belongs to. Specifically, a smaller value of r reduces the complexity of H Kr , possibly leading to a more favorable estimation error. Yet, it amplifies the gap between H Kr and H K and may lead to an extra approximation bias which may be significantly large. Clearly, r can be regarded as a trade-off parameter that balances the approximation bias n j=r+1 ξ * j 2 and the estimation error δ 4η n,r + λ 2η . It is clear that if r = n, the approximation bias is zero and the upper bound of f λ,n recovers that of f λ . 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 thatn j=r+1 ξ * j 2 ≲ r -2γα I {r<n} .Then, the best choice of r and λ to achieve an optimal rate is given by r ≍ δ-2/(γα) n,r if γ > 1; r = n if 1 2 ≤ γ ≤ 1, and λ ≍ δ 2 n,r. Accordingly, there holdsE( f λ,r ) -E(f * ) ≍ ∥ f λ,r -f * ∥ 2 n ≍ δ 4η n,r .For the comparison of Corollary 3.5, we also establish the following corollary for f λ,r .Corollary 4.3. Suppose that Assumptions 3.1, 3.2 and 3.4 are satisfied. For any ι ∈ (0, 1), ifwe choose λ ≍ (log ι -1 ) 2 n max{γ,1}α 2γα+1and r ≍ (n (log ι -1 ) 2 ) 1 2γα+1 I {γ>1} + nI { 1 2 ≤γ≤1}, then with probability at least 1 -ι, there holdsE( f λ,r ) -E(f * ) ≍ ∥ f λ,r -f * ∥ 2 n ≤ C (log ι -1 ) 2 n 2γα 2γα+1 .Clearly, under the over-aligned regime that γ > 1, the truncated estimator f λ,r can achieve a faster learning rate compared to f λ ; for 1 2 ≤ γ ≤ 1, the trivial choice of r = n is optimal and f λ,r shares the same learning rate as f λ . More impressively, the learning rate of f λ,r can be continuously increased with the enhancement of the target-kernel alignment, thus eliminating the saturation effect. Note that as γ → ∞, the learning rate of f λ,r approaches 1 n , meaning that the truncated estimator can successfully capture the strong alignment to attain a comparable rate to the parametric rate.The connection between r and d(δ). Recall that for the regular kernel class, we have R(δ) ≍ n -1 d(δ)δ 2 . It can also be shown by simple algebra that R r (δ) ≍ n -1 min{r, d(δ)}δ 2 (See Appendix D.3 for details). Particularly, for the kernel class with polynomial decay, we have d(δ) ≍ δ -2/α . Once the critical radius δ n,r is determined for specified kernel matrix, we denoted n = d(δ n,r ) ≍ δ -2/α n,r and take r ≍ δ -2η/(γα) n,rto balance δ 4η n,r and r -2γα . Consequently, we obtain r ≍ d η/γ n . Such a relation between r and d n is very reflective and provides theoretical insight into why the truncated estimator is more efficient under a more aligned situation. Specifically, for the caseγ > 1, it is clear that r ≍ d 1/γ n < d n , and we have R r (δ n,r ) ≍ n -1 rδ 2 n,r < n -1 d n δ 2 n,r ≍ R(δ n,r ).As a result, the truncated kernel complexity is substantially reduced compared to R(δ n,r ), leading to an improved learning rate. On the contrary, for the case that1 2 ≤ γ ≤ 1, we have r ≍ d n and R r (δ n,r ) ≍ n -1 d n δ 2 n,r ≍ R(δ n,r), which indicates the truncated kernel complexity remains invariant as r decreases. To avoid introducing additional approximation bias, the best choice of truncation level turns out to be r = n.In this section, we establish the minimax lower bound under squared loss based on the Fano method (see Chapter 15 in Wainwright (2019) for more details). For γ ≥ 1 2 , we consider the space within a ball asH b K = f ∈ H K : n j=1 ξ j 2 µ j -2γ ≤ u 2, where ξ j 's are the TA scores associated with f .Theorem 4.4. Suppose that the RKHS is induced by the regular kernel, and f is any estimator based on the data{(x i , y i )} n i=1 . If 1 2 ≤ γ ≤ 1, we have inf f sup f * ∈H b K P ∥ f -f * ∥ 2 n ≥ cδ 4γ n ≥ 1 2 . If γ > 1, with the choice of r satisfying r ≍ d(δ 1/γ n,r ) ≤ d(δ n,r ), we have inf f sup f * ∈H b K P ∥ f -f * ∥ 2 n ≥ cδ 4 n,r ≥ 1 2 ,where c > 0 is a constant independent of n and γ.The proof of Theorem 4.4 is provided in Appendix E. For γ > 1, the condition d(δ1/γ n,r ) ≤ d(δ n,r) can be easily verified for the most popular polynomial decay case that µ j ≍ j -α . Specifically, for the kernel class with polynomial decay, we have d(δ) ≍ δ -2/α , which leads tod(δ 1/γ n,r ) ≍ δ -2/α n,r ≤ δ -2/γα n,r ≍ d(δ n,r ).Moreover, it can be seen that r ≍ δ-2/γα n,ris the optimal choice, aligning with the optimal choice in the upper bound. Note that it is common to 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 et al., 2017; Lv et al., 2018; Li et al., 2019) . 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 1 2 ≤ γ ≤ 1, both the standard kernel-based estimator f λ and the truncated estimator f λ,r is minimax-optimal. More importantly, under the more challenging case that γ > 1, f λ can only achieve a sub-optimal rate, whereas f λ,r can attain the minimax rate as long as r ≍ d(δ1/γ n,r ) ≤ 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 γ = 1 2 , Yang et al. (2017) derives the minimax lower bound by considering the regular kernel class, and Theorem 4.4 extends it to the more general setting by allowing γ ≥ 1 2 . 
numerical verification: 
 Our established results indicate that a 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 a 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 alignment γ, with a 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 Wahba, 1990) , where α controls the model complexity of the induced RKHS at the population level. Moreover, we consider the nonparametric quantile regression thatK α (x, x ′ ) = ∞ k=-∞ e 2πikx e -2πikx ′ |k| -α (Y i = f * (x i ) + σ(ϵ i -Φ -1 (τ )), i = 1, ..., n, where f * (x) = K 3.5 (x, 0) sin(x), σ = 2, ϵ i ∼ N (0, 1), {x i } ni=1 are independently sampled from the uniform distribution on (0, 1) and Φ denotes CDF function of standard normal distribution. We conduct the numerical experiments by varying τ ∈ {0.3, 0.5, 0.7} and α ∈ {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 1 .From Figure 1 , we can conclude that the smaller α, corresponding to richer RKHS and potentially stronger alignment, results in significant improvement in TKM over KM. Conversely, the larger α, corresponding to a 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 a trade-off between the model complexity and target-kernel alignment, indicating that a carefully data-driven 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 is deferred to 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. 
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 et 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 Amini et al. (2022) , we introduce a more general condition as stated in Assumption 3.2. This condition involves γ, reflecting the degree of target-kernel alignment. (c) In Amini 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 γ ≥ 1 2 .This paper provides a 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 justify our theoretical findings, demonstrating a consistent improvement of the truncated estimator over the standard kernelbased estimator. We also derived an algorithm-free 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 < γ < 1 2 and how to develop a data-driven algorithm for selecting a strongly-aligned kernel with lower model complexity.This appendix is organized as follows. In Section A, we conduct a real data analysis. Section B is devoted to providing more discussions and future directions. In Section C, we provide the proof 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. In Section E, we complement the upper bounds by deriving the minimax lower bound. In Section G, 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 ⟨α, β⟩ 2 = n i=1 α i β i and the norm ∥α∥ 2 = ⟨α, α⟩ 2 for α, β ∈ R n . For any integer m, we use [m] to represent the set {1, 2, ..., m} for short.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, we randomly select 500 samples for training and another 500 samples for testing. The above procedure is repeated 10 times, where the Laplacian kernel K(x, x ′ ) = exp(-∥ x -x ′ ∥ 1 ) is adopted and the parameters γ and r are tuned by 5-fold cross-validation. The averaged MSE with different τ ∈ (0.3, 0.5, 0.7) is reported in Table 2 . It is thus clear that the obtained results in 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 δ n and δ n,rIn this section, we provide a detailed verification of the existence and uniqueness of δ n and δ n,r , where δ n and δ n,r are defined as the smallest solutions to (2) and (3), respectively.For any ι ∈ (0, 1) and γ ≥ 1 2 , defineg(δ) := 2C log ι -1 R(δ) c 0 δ 2η+1 on δ ∈ (0, ∞),where η = max{γ, 1}. Here, we ignore the dependence of g on ι and γ for ease of presentation.The verifying argument is based on Lemma 3.2 in Bartlett et al. (2005) , which states that if ψ : [0, ∞) → [0, ∞) is a nontrivial sub-root function6 , then it is continuous on [0, ∞), and the equation ψ(r) = r has a unique positive solution.Recall that we assume µ 1 , ..., µ n > 0. From the definition of R(δ), it can be easily seen that R( √ δ) is a nontrivial sub-root function. Then from Lemma 3.2 in Bartlett et al. (2005) , R( √ δ) is continuous on [0, ∞), and thus g(δ) is also continuous on (0, ∞). Note that g(δ)δ 2η is nonincreaing on (0, ∞), then g(δ) must be strictly decreasing (0, ∞).If g(δ) is always larger than 1 on (0, ∞), we havelim δ→∞ g(δ)δ 2η = ∞,which is impossible since g(δ)δ 2η is nonincreasing on (0, ∞). On the other hand, if g(δ) is always smaller than 1 on (0, ∞), then lim δ→0 g(δ)δ 2η = 0, implying g(δ)δ 2η ≡ 0 since g(δ)δ 2η is nonincreasing. Since R(δ) is not trivial, this is also impossible.Therefore, by the continuity of g on (0, 1), the equation g(δ) = 1 has a positive solution δ n that is unique by the strict monotonicity of g. Note that by the strict monotonicity of g, δ n can be equivalently defined as the smallest solution to g(δ) ≤ 1. According to the definition of g, we conclude the existence and uniqueness of δ n . For δ n,r , repeat a similar argument, we can also verify its existence and uniqueness.Recall that Kr = 1 n K r (x i , x j ) n i,j=1 is the empirical kernel matrix w.r.t. K r , and K = U DU ⊤ , where U = (u 1 , ..., u n ) ∈ R n×n is an orthonormal matrix and D ∈ R n×n is a diagonal matrix with positive elements µ 1 , ..., µ n arranging in a descending ordering. Denote u k = (u k1 , ..., u kn ) ⊤ . By the definitions of K r and {ψ k } i∈[n] , we have(K r ) ij = 1 n r k=1 µ k ψ k (x i )ψ k (x j ) = r k=1 µ k u ki u kj .On the other hand, recall that Dr is diagonal matrix with elements µ 1 , ..., µ r , 0, ..., 0, we have(U DrU ⊤ ) ij = n k=1 Dkkukiukj = r k=1 µ k u ki u kj = (K r ) ij .Therefore, we conclude that Kr = U DrU ⊤ .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 are discussed below.Under the random design setting, we consider a random variable X ∼ ρ, where ρ is a probability measure supported on X ⊂ R p . Let the covariates {x i } n i=1 be independently sampled from ρ. Denote the space of square-integrable functions f : X → R with respect to ρ as L(X , ρ), where X ⊂ R p .Recall that H K is an RKHS induced by a positive semi-definite kernel function K. By Mercer's theorem (see, for instance, Theorem 12.20 in Wainwright ( 2019)), if X is compact and K is a continuous, combined with our bounded assumption that sup x,x ′ ∈X K(x, x ′ ) ≤ κ 2 , the kernel function admits an expansion of formK(x, x ′ ) = ∞ j=1 μj ϕ j (x)ϕ j (x ′ ),where μj 's are the non-negative eigenvalues in descending ordering and ϕ j 's are the corresponding eigenfunctions in L(X , ρ). Given this expansion of K, the RKHS H K can be written asH K = f = ∞ j=1 α j ϕ j : ∞ j=1 α 2 j μj < ∞ , equipped with inner product ⟨f, g⟩ K = ∞ j=1 αj βj μj for f = ∞ j=1 α j ϕ j and g = ∞ j=1 β j ϕ j .Under the random design setting, the population risk function is defined asE(f ) := E L Y, f (X)) ,whereY |X = x ∼ P Y | x .Then, the target function f * is defined asf * := argmin f E(f ).If we assume f * ∈ H K , then f * can be expanded asf * = ∞ j=1 α * j ϕ j with α * = (α * 1 , α * 2 , ...) ⊤ satisfying n j=1 α * j 2 μj < ∞.An assumption analogous to Assumption 3.2 under the random design setting is required that∞ j=1 α * j 2 μ-2γ j ≤ u 2 for some constants γ ≥ 12 and u. Here, γ measures the target-kernel alignment at the population level, and it is equivalent to smooth (or source) parameter in literature (Caponnetto & De Vito, 2007; Cui et al., 2021; Li et al., 2023) . Note that if γ = 1 2 , we merely assume that the target function f * belongs to the RKHS H K , and as γ increases, the target function becomes smoother w.r.t. the RKHS H K .Furthermore, the polynomial decay assumption analogous to Assumption 3.4 under the random design setting can be made asμj ≍ j -α and α * j 2 ≍ j -2γα-1 (4)with constants α > 1 and γ ≥ 1 2 . Note that the assumption ( 4) is equivalent to condition (8) in Cui et al. (2021) . 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 kernel complexity, defined asR(δ) := 1 n ∞ j=1 min{δ 2 , μj }.Since the theoretical derivation should be more deeply involved, we leave this promising topic to future investigation.The spectrally transformed kernel regression (SKRR, Zhai et al. (2024) ) aims to use spectrally transformation for constructing a new kernel that can leverage the 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 be able to overcome the saturation effect if the transformation function can be properly chosen. The possible routine for establishing the theoretical results is briefly discussed below.Recall that by Mercer's theorem, we haveK(x, x ′ ) = ∞ j=1 μj ϕ j (x)ϕ j (x ′ ).For SKRR, K(x, x ′ ) is replaced with a new kernel thatK ′ (x, x ′ ) := ∞ j=1 s(μ j )ϕ j (x)ϕ j (x ′ ),where s(•) : R + → R + is the general transformation function. Let f λ,s be the kernel-based estimator via the RKHS H K ′ induced by K ′ . The primary goal is to study how the prediction error ∥ f λ,s -f * ∥ ρ depends on the choice of s.The idea of deriving an upper bound on the prediction error is to separately bound the estimation error ∥ f λ,s -f ♯ s ∥ ρ and approximation bias ∥f ♯ s -f * ∥ ρ , where ∥ • ∥ ρ denotes the norm equipped with L(X , ρ), and f ♯ s := ∞ j=1 s(α * j )ϕ j is introduced as an immediate function belonging to H K ′ . Following a similar technical treatment in Section D, the upper bound on estimation error can be established. For the approximation bias, by writing f * = ∞ j=1 α * j ϕ j , we find thatf ♯ s -f * 2 ρ = ∞ j=1 s(α * j ) -α * j 2 .Clearly, the selection of s(•) is crucial and it is favorable if s(•) is close to the identity function for small j and decays extremely rapidly as j tends to infinity, such as s(μ j ) = μj I {j≤r} corresponding to 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.For simplicity, we focus only on 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 3 ). In the second part, the basis {ψ k } 1≤k≤r can be simply calculated byψ k (x) = u ⊤ k K -1 K x with K x = 1 √ n K(x, x 1 ), ..., K(x, x n ) ⊤ for each k ∈ [n], which also has O(n 3 ) computational complexity. In the last part, computing the KRR via the r-dimensional RKHS H Kr has computational complexity of O(nr 2 ). To sum up, the overall computational complexity of TKM is O(n 3 ). Solving the standard KRR also has computational complexity of O(n 3 ), and thus the truncated KRR does not impose an additional computational cost.For ease of presentation, without loss of generality, we assume µ j ≤ 1 for all j ∈ [n] in the rest of this paper7 . We start the error analysis by noting that for anyEQUATION)This transform from the L(P n )-norm and the norm in RKHS to vector norm will be frequently applied in our proof.Denoteq * := √ nS x (f * ) = (f * (x 1 ), ..., f * (x n )) ⊤ .Recall that the TA scores are the elements of the vectorξ * = U ⊤ S x (f * ) = 1 √ n U ⊤ q * .Define an immediate functionf ♯ := S ⊤ x (α ♯ ) ∈ H K with α ♯ = U D -1 ξ * ∈ R n .f ♯ can be viewed as the best approximation of f * onto the n-dimensional function space H n , defined asH n := f = S ⊤ x (α) : α ∈ R n .To be more clear, by the orthogonality of U, we haveEQUATIONimplying f * (x i ) = f ♯ (x i ) for each i ∈ [n].Therefore, we obtainf -f * n = f -f ♯ n for all f ∈ H K (7)andEQUATIONFurthermore, by applying (5), we havef ♯ K = K 1/2 U D -1 ξ * K = U D 1/2 U ⊤ U D -1 ξ * K = D -1/2 ξ * K .By our assumption that µ j ≤ 1 for all j, one hasEQUATIONwhere the last inequality holds by Assumption 3.2 with γ ≥ 1 2 . The construction of f ♯ plays a crucial role in our proofs. Intuitively, the kernel complexity function R(δ) is defined at an empirical level (depends on the fixed points x 1 , ..., x n ) and serves as a complexity measure of finite space H n . This poses a technical challenge as the true function f * lies in an infinite-dimensional function space, creating a mismatch with the empirical kernel complexity R(δ).To solve this problem, we introduce the best approximation f ♯ of f * in finite-dimensional function space H n . Our proof will first focus on deriving the upper bound on ∥ f λ -f ♯ ∥ n , and then move to ∥ f λ -f * ∥ n by using the relation (6).Another advantage to consider the best approximation of f * instead of itself is that f λ lies in the same space H n as f ♯ , allowing us to express ∥ f λ -f ♯ ∥ 2 2 and ∥ f λ -f ♯ ∥ 2 K 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 is a novel treatment to establish theoretical results for the kernel-based estimator. In the proof for the truncated estimator in Section D, we will adopt a similar proof strategy to construct the best approximation f ♯ r of f * in the reduced space H Kr . Based on the error analysis, we are ready to present the proof for Theorem 3.3.Define the localized function classH n,b := f : f ∈ H n , ∥f -f ♯ ∥ K ≤ b .Here, b is a constant independent of n, γ, which will be specified in the proof. Without loss of generality, we assume b > 1.For given ι ∈ (0, 1) and δ > 0, define the auxiliary eventV(ι, δ) := E(f ) -E(f ♯ ) -[E(f ) -E(f ♯ )] δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K ≤ C log ι -1 R(δ) holds for any f ∈ H n,b .The following two lemmas are crucial for proving Theorem 3.3.Lemma C.1. For given ι ∈ (0, 1) and δ > 0, the event V(ι, δ) occurs with probability greater than 1 -ι, i.e.P (V(ι, δ)) ≥ 1 -ι.As demonstrated in the proof of Lemma C.1, b is incorporated into the constant C of the upper bound C log ι -1 R(δ), meaning that C depends on b.Recall that δ n is the critical radius defined as the smallest solution to (2). Lemma C.2. Let η = min{γ, 1}. On the event V(ι, δ n ), with the choice of λ satisfying δ 2 n ≤ λ ≤ 1, we havef λ -f ♯ 2 n ≤ C δ 4η n + λ 2η, where C is a constant independent of n, γ.By applying Lemma C.1, we have P(V(ι, δ n )) ≥ 1 -ι. Together with Lemma C.2 and the relation ( 6), it holds with probability at least 1 -ι thatf λ -f * 2 n = f λ -f ♯ 2 n ≤ C δ 4η n + λ 2η, which completes the proof for the L(P n )-error.For the excess risk, it immediately follows from Assumption 3.1. Accordingly, it remains to prove Lemmas C.1 and C.2.C.2.1 Proof of Lemma C.1 Denote D := E(f ) -E(f ♯ ) -E(f ) -E(f ♯ ) . Then, our goal is to prove that for all f ∈ H n,b |D| ≤ C log ι -1 R(δ) δ -1 f -f ♯ n + f -f ♯ K . If δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K = 0,the above inequality is naturally satisfied. Therefore, without loss of generality, we assume δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K > 0 for all f ∈ H n,b . It is equivalent to proving that A := sup f ∈H n,b |D| δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K ≤ C log ι -1 R(δ).By applying the triangle inequality, together with (9), we find that for any The remaining proof follows a standard procedure: first bound the expectation of A and then bound the deviation of A from its expectation. Finally, we combine these two bounds to obtain the desired result.f ∈ H n,b ∥f ∥ K ≤ f -f ♯ K + f ♯ K ≤ u +Bounding E[A]. Let w 1 , ..., w n ∼ N (0, 1) denote the standard Gaussian variables, independent of the data. To bound E[A], we employ the symmetrization technique in Lemma G.2. Specifically, we haveEQUATIONwhere (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 right-hand side of (10), we consider the localized function class of the formF(δ) := f = S ⊤ x (α) : f -f ♯ K ≤ 1, f -f ♯ n ≤ δ, α ∈ R n .For any f ∈ H n,b , there exists α ∈ R n such that f = S ⊤ x (α). Recall that f ♯ = S ⊤ x (α ♯ ). Define the vector β := D U ⊤ (α -α ♯ ). Then, by applying (5), f ∈ F(δ) implies the constraints on β that ∥D -1/2 β∥ 2 ≤ 1 and ∥β∥ 2 ≤ δ.Further, note that any vector satisfying these two constraints must belong to the ellipse classE := β ∈ R n : n j=1 β 2 j ν j ≤ 2 with ν j = min{δ 2 , µ j } .Denote w = (w 1 , ..., w n ) ⊤ , we haveEQUATIONwhere (i) follows ⟨w, Uβ⟩ = ⟨U w, β⟩ and U w ∼ N (0, In) since U is an orthogonal matrix, (ii) follows from Cauchy-Schwarz inequality, and (iii) follows from Jensen's inequality.Note that (11) holds when considering the supremum over F(δ). For f ∈ H n,b , by defining the rescaled functionf = f -f ♯ δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K + f ♯ , we have f -f ♯ n = ∥f -f ♯ ∥ n δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K ≤ δ and f -f ♯ K = ∥f -f ♯ ∥ K δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K ≤ 1.As a result, f ∈ F(δ).On the other hand,E n i=1 w i (f (x i ) -f ♯ (x i )) δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K = E n i=1 w i ( f (x i ) -f ♯ (x i )) .This result, combined with (10) and ( 11), impliesEQUATIONBounding A -E(A). We use the concentration inequality in Lemma G.1 to bound A -E(A). For each i ∈ [n] and any f ∈ F(δ), define s j = sign(f (x i ) -f ♯ (x i )) if j = i and s j = 0 if j ̸ = i and let s = (s 1 , ..., s n ) ⊤ , then we have|f (x i ) -f ♯ (x i )| = n j=1 s j (f (x i ) -f ♯ (x i )) = √ n⟨s, Uβ⟩ (i) ≤ √ n n j=1 β 2 j ν j n j=1 ν j s 2 j ≤ √ n n j=1 β 2 j ν j n j=1 ν j = √ 2nR(δ),where (i) follows from the fact that U is orthogonal and Cauchy-Schwarz inequality. Consequently, for each i ∈ [n], we haveL(y i , f (x i )) -L(y i , f ♯ (x i )) ≤ M |f (x i ) -f ♯ (x i )| ≤ M √ 2nR(δ),where the second inequality follows from that L(y i , •) is M -Lipschitz continuous. In addition, for any f ∈ F(δ), we have1 n n i=1 E L(y i , f (x i )) -L(y i , f ♯ (x i )) 2 ≤ M 2 n n i=1 (f (x i ) -f ♯ (x i )) 2 = M 2 ∥f -f ♯ ∥ 2 n = M 2 ⟨U β, U β⟩ = M 2 ⟨β, β⟩ ≤ M 2 max i∈[n] ν j n i=1 β 2 j ν j ≤ 2M 2 n i=1 ν j = 2M 2 nR 2 (δ).By a similar rescaled method, we haveL(y i , f (x i )) -L(y i , f ♯ (x i )) δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K ≤ M |f (x i ) -f ♯ (x i )| δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K = M | f (x i ) -f ♯ (x i )| ≤ √ 2M nR(δ),and1 n n i=1 E L(y i , f (x i )) -L(y i , f ♯ (x i )) δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K 2 ≤ M 2 n n i=1 f (x i ) -f ♯ (x i ) δ -1 ∥f -f ♯ ∥ n + ∥f -f ♯ ∥ K 2 = M 2 L, b n n i=1 ( f (x i ) -f ♯ (x i )) 2 ≤ 2M 2 nR 2 (δ).Thus, the requirements in Lemma G.1 hold with η = √ 2M nR(δ) and ζ 2 = 2M 2 nR 2 (δ). Then, by applying Lemma G.1, for any ι ∈ (0, 1), let t = log ι -1 n , it holds at with probability at least 1 -ι thatEQUATIONwhereC = (4M 2 + 16 √ 2πM 2 ) + 2 √ 2M 3and (i) follows from (12).Therefore, by combining ( 12) and ( 13), it holds with probability at least 1 -ι thatA ≤ C log ι -1 R(δ)whereC = (4M 2 + 8 √ 2πM 2 ) + 2 √ 2M 3 + 4 √ πM . This completes the proof of Theorem 3.3. □ C.2.2 Proof of Lemma C.2For short, we write ∆ = c 0 4 δ 4η n + 4u 2 λ 2η .On the event V(ι, δ n ), we claim thatf λ -f ♯ 2 n ≤ C∆.According to the optimality of f λ and the feasibility of f ♯ , we obtainEQUATIONThen, proving∥ f λ -f ♯ ∥ 2 n ≤ C∆ suffices to prove that if ∥ f λ -f ♯ ∥ 2 n > C∆ or ∥ f λ -f ♯ ∥ K > b, we have E( f λ ) -E(f ♯ ) + λ∥ f λ ∥ 2 K -λ∥f ♯ ∥ 2 K > 0.Below we are devoted to verifying this fact. Define the function classG := f ∈ H n : f -f ♯ 2 n ≤ C∆, f -f ♯ K ≤ b .Suppose that f λ ̸ ∈ G. Since both G and H n are convex class by the convexity of L(y, •) and Jensen's inequality, there exists a function f = α f λ + (1 -α)f ♯ with α ∈ (0, 1] that sits on the boundary of G (Ma et al., 2023) . If we can show thatEQUATIONby the convexity of L(y, •) and Jensen's inequality, we must haveE( f λ ) -E(f ♯ ) + λ∥ f λ ∥ 2 K -λ∥f ♯ ∥ 2 K ≥ 1 α E( f ) -E(f ♯ ) + λ∥ f ∥ 2 K -λ∥f ♯ ∥ 2 K > 0.Then, let us focus on proving (15) on the event V(ι, δ n ).Note that f belongs to the the boundary of G, we can split the remaining proof into two cases: (i)∥ f -f ♯ ∥ 2 n = C∆ and ∥ f -f ♯ ∥ K ≤ b; and (ii) ∥ f -f ♯ ∥ 2 n ≤ C∆ and ∥ f -f ♯ ∥ K = b.Case (i): By applying ( 7) and ( 8), from Assumption 3.1, we havec 0 f -f ♯ 2 n = c 0 f -f * 2 n ≤ E( f ) -E(f * ) = E( f ) -E(f ♯). so that the c 0 -strong convexity also holds for f ♯ .On the event V(ι, δ n ), we haveE(f ♯ ) -E( f ) ≤ E(f ♯ ) -E( f ) + C log ι -1 R(δ n ) δ -1 n f -f ♯ n + f -f ♯ K ≤ -c 0 f -f ♯ 2 n + C log ι -1 R(δ n ) δ -1 n f -f ♯ n + f -f ♯ K (i) = -c 0 C∆ + C log ι -1 R(δ n ) δ -1 n √ C∆ + f -f ♯ K (ii) ≤ -c 0 C∆ + Cδ -1 n log ι -1 R(δ n ) √ C∆ + C(log ι -1 R(δ n )) 2 λ -1 + λ 4 f -f ♯ 2 K (iii) ≤ -c 0 C∆ + c 0 2 δ 2η n √ C∆ + c 0 4 δ 4η+2 n λ -1 + λ 4 f -f ♯ 2 K ,where (i) follows from ∥ f -f ♯ ∥ 2 n = C∆, (ii) uses the elementary inequality that 2ab ≤ a 2 + b 2 and (iii) follows from the definition of δ n satisfyingC log ι -1 R(δ n ) ≤ c 0 2 δ 2η+1 n .Further with the choice of λ ≥ δ 2 n , we haveE(f ♯ ) -E( f ) ≤ -c 0 C∆ + c 0 2 δ 2η n √ C∆ + c 0 4 δ 4η n + λ 4 f -f ♯ 2 K .On the other hand, we notice thatEQUATION)Note that ⟨f, g⟩ K = ⟨K 1/2 f, K 1/2 g⟩ K for any f, g ∈ H n . f ∈ H n so that it can be written asf = S ⊤ x ( α) for some α ∈ R n .Therefore, for 1 2 ≤ γ ≤ 1, there holdsλ⟨f ♯ , f -f ♯ ⟩ K = λ⟨K 1/2 α ♯ , K 1/2 ( α -α ♯ )⟩ 2 = λ⟨K 1-γ α ♯ , K γ ( α -α ♯ )⟩ 2 ≤ λ K 1-γ α ♯ 2 K γ ( α -α ♯ ) 2 = λ D 1-γ D -1 ξ * 2 K γ ( α -α ♯ ) 2 = λ D -γ ξ * 2 K γ ( α -α ♯ ) 2 (i) ≤ uλ K γ ( α -α ♯ ) 2 ,where (i) follows from Assumption 3.2.For 1 2 ≤ γ ≤ 1, using a similar treatment as that in Lian (2022), we apply Young's inequality AB ≤ A p p + B q q for two positive operators A and B with 1 p + 1 q = 1 and p, q ≥ 1 to obtainEQUATIONwhere (i) holds by taking γ = 1 2 and γ = 1, and (ii) follows from max{a, b} ≤ a + b. For γ > 1, we claim that ∥D -1 ξ * ∥ 2 ≤ u. To see this, we find thatD -1 ξ * 2 2 = ∞ j=1 µ -2 j ξ * j 2 (i) ≤ ∞ j=1 µ -2γ j ξ * j 2 ≤ u 2 ,where (i) holds by our assumption µ j ≤ 1 for all j.Then, similar to (17) with γ = 1, we haveλ⟨f ♯ , f -f ♯ ⟩ K ≤ uλ 3 2 f -f ♯ K + uλ f -f ♯ n .Combine these two case to obtain that for γ ≥EQUATIONHere, we recall that η = min{γ, 1}.Putting the pieces together, for all γ ≥ 1 2 , we haveEQUATIONwhere (i) uses the elementary inequality.Below is devoted to proving that for a sufficiently large C, the RHS of ( 19) is less than 0. Precisely, letφ(x) = c 0 x 2 - c 0 2 δ 2η n + 2uλ η x - c 0 4 δ 4η n -4u 2 λ 2η . Let x = √ C∆, note that φ(x) =c 0 C∆ - c 0 2 δ 2η n + 2uλ η √ C∆ - c 0 4 δ 4η n -4u 2 λ 2η =(c 0 C -1)∆ - c 0 2 δ 2η n + 2uλ η √ C∆ = √ C∆ c 0 C -1 √ C √ ∆ - c 0 2 δ 2η n + 2uλ η (i) ≥ √ C∆ c 0 C -1 √ 2C √ c 0 2 δ 2η n + 2uλ η - c 0 2 δ 2η n + 2uλ η ,where (i) follows from the basic inequalitya+b 2 ≤ a 2 +b 2 2 . Since c0C-1 √ 2C is increasing in C, we can select C such that c0C-1 √ 2C ≥ max{ √ c 0 , 1}, which leads to φ(x) > 0.In conclusion, for a sufficiently large C in the definition of the function class G, on the event V(ι, δ n ), for case (i), we haveE(f ♯ ) -E( f ) + λ∥f ♯ ∥ 2 K -λ∥ f ∥ 2 K < 0.Case (ii): Repeat the similar argument as that in Case (i), on the event V(ι, δ n ) and by Assumption 3.1, we haveE(f ♯ ) -E( f ) ≤ -c 0 f -f ♯ 2 n + C log ι -1 R(δ n ) δ -1 n f -f ♯ n + f -f ♯ K ≤ C log ι -1 R(δ n ) δ -1 n f -f ♯ n + f -f ♯ K ≤ c 0 2 δ 2η n √ C∆ + c 0 4 δ 4η+2 n λ -1 + λ 4 f -f ♯ 2 K .Further with the choice of λ ≥ δ 2 n , we haveE(f ♯ ) -E( f ) ≤ c 0 2 δ 2η n √ C∆ + c 0 4 δ 4η n + λ 4 f -f ♯ 2 K .Combine with ( 16) and ( 18) to obtainE(f ♯ ) -E( f ) + λ∥f ♯ ∥ 2 K -λ∥ f ∥ 2 K ≤ c 0 2 δ 2η n + 2uλ η √ C∆ + c 0 4 δ 4η n + λ 4 f -f ♯ 2 K + 2uλ η+ 1 2 f -f ♯ K -λ f -f ♯ 2 K ≤ c 0 2 δ 2η n + 2uλ η √ C∆ + c 0 4 δ 4η n + 4u 2 λ 2η - λ 2 f -f ♯ 2 K .Note that 0 < λ ≤ 1 and λ ≥ δ 2 n together implies λ ≥ λ 2η and λ ≥ δ 4η n .(ii), ∥ f -f ♯ ∥ K = b. Therefore, E(f ♯ ) -E( f ) + λ∥f ♯ ∥ 2 K -λ∥ f ∥ 2 K ≤ c 0 2 δ 2η n + 2uλ η √ C∆ + c 0 4 δ 4η n + 4u 2 λ 2η - 1 2 b 2 δ 4η n - 1 2 b 2 λ 2η ≤ c 2 0 2 δ 4η n + 8u 2 λ 2η √ C∆ + c 0 4 δ 4η n + 4u 2 λ 2η - 1 2 b 2 δ 4η n - 1 2 b 2 λ 2η ≤ √ C c 0 4 max{2c 0 , 1}δ 4η n + 8u 2 λ 2η + c 0 4 δ 4η n + 4u 2 λ 2η - 1 2 b 2 δ 4η n - 1 2 b 2 λ 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 (15). Therefore, on the event V(ι, δ n ), we havef λ -f ♯ 2 n ≤ C∆ ≲ δ 4η n + λ 2η ,which completes the proof. □Recall that the statistical dimension is defined asd(δ) = min j ∈ [n] : µ j ≤ δ 2 .From the definition of d(δ), we haveEQUATION)Recalling that n d(δ)+1 µ j ≲ d(δ)δ 2 for regular kernel and kernel with the polynomial in its eigenvalues is regular (Yang et al., 2017) , the kernel complexity function satisfiesR(δ) ≍ 1 n d(δ)δ 2 .Therefore, the solution to the inequality (2) can be bounded from above by the solution toEQUATION)Moreover, if the eigenvalues of K exhibit α-polynomial decay that is µ j ≍ j -α , then we have d(δ) ≍ δ -2/α . Together with (21) leads toδ 2 n ≤ C (log ι -1 ) 2 n α 2ηα+1 .Then, with the choice of λ ≍ δ 2 n , it holds with probability at least 1 -ι that∥ f λ -f * ∥ 2 n ≤ C(δ 4η n + λ 2η ) ≤ C (log ι -1 ) 2 n 2ηα 2ηα+1 .We conclude the upper bound in Corollary 3.5. □Recall thatq * = √ nS x (f * ) = (f * (x 1 ), ..., f * (x n )) ⊤ and ξ * = U ⊤ S x (f * ) = 1 √ n U ⊤ q * .In the proof for the truncated kernel-based estimator, we partition ξ * into two sub-vectors as r) , and partition D into two blocks D1 and D2, that isξ * ⊤ = (ξ * 1 ⊤ , ξ * 2 ⊤ ) with ξ * 1 ∈ R r and ξ * 2 ∈ R n-r . Moreover, we partition U into two sub-matrixs U = (U 1 , U2) with U1 ∈ R n×r and U2 ∈ R n×(n-D = D1 D2 ,where D1 ∈ R r×r and D2 ∈ R (n-r)×(n-r) . Since the last n -r diagonal elements of Dr are all zero, for any α ∈ R n , the last n -r elements of DrU ⊤ α are also all zero. Then, we haveEQUATION) Define H n,r := f = S ⊤ x,r (α) : α ∈ R n .For any f = S ⊤ x,r (α) ∈ H n,r , we have∥f ∥ n = Krα 2 = DrU ⊤ α 2 = D1U ⊤ 1 α 2 ,where the last step holds by applying (22) . We also observeEQUATION)Define an immediate functionEQUATION)where (i) holds by our assumption µ j ≤ 1 for all j and (ii) follows from Assumption 3.2.The construction of f ♯ r allows us 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 Kr , and the approximation error arising from the dissimilarity between the truncated RKHS H Kr and the full RKHS H K . Specifically, we have the error decomposition as follows.Error decomposition. By applying the elementary inequality that 1 2 (a + b) 2 ≤ a 2 + b 2 , the total error ∥ f λ,r -f * ∥ 2 n can be decomposed asEQUATION)Note that both f λ,r and f ♯ r belong to H n,r , allowing us to analyze the estimation error based on the complexity of the reduced kernel matrix Kr. This decomposition successfully captures two components of error: estimation error and approximation bias. The estimation error is controlled by the model richness of the truncated space H Kr , while approximation bias depends on the dissimilarity between the truncated RKHS H Kr and the full RKHS H K where the true target f * is sitting in. A larger r amplifies the space H Kr , resulting in a larger estimation error. At the same time, it narrows the gap between H Kr and H K , 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.We will separately bound from above each term appearing in the decomposition (25).Bounding the approximation bias. Note thatf ♯ r -f * 2 n = 1 n q * - √ nK r α ♯ r 2 n (i) = ξ * -DrU ⊤ α ♯ r 2 2 (ii) = ξ * 1 -D1U ⊤ 1 α ♯ r 2 2 + ξ * 2 2 2 ,where (i) follows from the eigen-expansion that Kr = UKrU ⊤ and (ii) follows from ( 22).By the definition of α ♯ r , we haveD1U ⊤ 1 α ♯ r = D1U ⊤ 1 U1D -1 1 ξ * 1 = ξ * 1 .Therefore, we arrive atEQUATION)Bounding the estimation error. Define the localized function classH n,r,b := f : f ∈ H n,r , ∥f -f ♯ ∥ K ≤ b ,where b > 1 is a constant independent of n, γ, which will be specified in the proof.For given ι ∈ (0, 1) and δ > 0, define the auxiliary eventV r (ι, δ) := E(f ) -E(f ♯ r ) -[E(f ) -E(f ♯ r )] δ -1 ∥f -f ♯ r ∥ n + ∥f -f ♯ r ∥ Kr ≤ C log ι -1 R r (δ) holds for any f ∈ H n,r,b .To establish the bound for the estimation error, we need the following two lemmas.Lemma D.1. For given ι ∈ (0, 1) and δ > 0, the event V r (ι, δ) occurs with probability greater than 1 -ι, i.e.P (V r (ι, δ)) ≥ 1 -ι.Recall that δ n,r is 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 V r (ι, δ n,r ), with the choice of λ satisfying max{δ 2 n,r ,n j=r+1 ξ * j 2 } ≤ λ ≤ 1, we have f λ,r -f ♯ r 2 n ≤ C δ 4η n,r + λ 2η + n j=r+1 ξ * j 2 ,where C is a constant independent of n, γ.By applying Lemma D.1, we haveP(V r (ι, δ n,r )) ≥ 1 -ι,which, together with Lemma D.2, impliesf λ,r -f ♯ r 2 n ≤ C δ 4η n,r + λ 2η + n j=r+1 ξ * j 2 .holds with probability at least 1 -ι.Finally, by applying the error decomposition ( 25) and the equality ( 26), one hasf λ,r -f * 2 n ≤ 2 f λ,r -f ♯ r 2 n + 2 f ♯ r -f * 2 n ≤ C δ 4η n,r + λ 2η + n j=r+1 ξ * j 2 ,which completes the proof for the L(P n )-error. For the excess risk, it immediately follows from Assumption 3.1.D.2.1 Proof of Lemma D.1 Denote D r = E(f ) -E(f ♯ r ) -E(f ) -E(f ♯ r ) . Similar to the proof for Lemma C.2, it is equivalent to proving that A r := sup f ∈H n,r,b |D r | δ -1 ∥f -f ♯ r ∥ n + ∥f -f ♯ r ∥ Kr ≤ C log ι -1 R r (δ).From ( 24), we find that for anyf ∈ H n,r,b ∥f ∥ Kr ≤ f -f ♯ r Kr + f ♯ r Kr ≤ u + b.Similar to that in Section C. Bounding E[A r ]. Following a similar treatment as that in (10), by using the Lemma G.2 and Lemma G.3, we haveEQUATION) Let F r (δ) := f = S ⊤ x,r (α) : f -f ♯ r Kr ≤ 1, f -f ♯ r n ≤ δ, α ∈ R n . For any f ∈ H n,r,b , there exists α ∈ R n such that f = S ⊤ x,r (α). Recall that f ♯ r = S ⊤ x,r (α ♯ r ). Define the vector β := DrU ⊤ (α -α ♯ r ), then f ∈ F(δ) is equivalent to the constraints on β r that ∥D -1/2 r β∥ 2 ≤ 1 and ∥β∥ 2 ≤ δ.From ( 22), the last n -r elements of β are all zero, then any vector satisfying these two constraints must belong to the ellipse classE r := β ∈ R n : r j=1 β 2 j ν j ≤ 2 with ν j = min{δ 2 , µ j } . Denote w = (w 1 , ..., w n ) ⊤ , we have E sup f ∈Fr(δ) n i=1 w i (f (x i ) -f ♯ r (x i )) = E sup β∈Er √ n ⟨w, Uβ⟩ = E sup β∈Er √ n ⟨w, β⟩ (i) ≤ E sup β∈Er √ n r j=1 β 2 j ν j r j=1 ν j w 2 j ≤ √ 2n 1 n r j=1 ν j = √ 2nR r (δ),where (i) follows from Cauchy-Schwarz inequality and the fact that the last n -r elements of β are all zero.Similar to the argument in the proof for Lemma C.2, by appropriately scaling, we obtainEQUATION)Bounding A r -E[A r ]. For each i ∈ [n] and any f ∈ F r (δ), define s j = sign(f (x i ) -f ♯ r (x i )) if j = i and s j = 0 if j ̸ = i and let s = (s 1 , ..., s n ) ⊤ , then we have |f (x i ) -f ♯ r (x i )| = n i=1 s i (f (x i ) -f ♯ r (x i )) = √ n⟨s, Uβ⟩ ≤ √ n r j=1 β 2 j ν j r j=1 ν j s 2 j ≤ √ n r j=1 β 2 j ν j r j=1 ν j = √ 2nR r (δ).Consequently, for each i ∈ [n], we haveL(y i , f (x i )) -L(y i , f ♯ r (x i )) ≤ M |f (x i ) -f ♯ r (x i )| ≤ M √ 2nR r (δ).In addition, note that1 n n i=1 E L(y i , f (x i )) -L(y i , f ♯ r (x i )) 2 ≤ M 2 n n i=1 (f (x i ) -f ♯ r (x i )) 2 = M 2 ∥f -f ♯ r ∥ 2 n = M 2 ⟨U β, U β⟩ = M 2 ⟨β, β⟩ ≤ M 2 max i∈[r] ν j r i=1 β 2 j ν j ≤ 2M 2 r i=1 ν j = 2M 2 nR 2 r (δ).By a similar rescaled method, we haveL(y i , f (x i )) -L(y i , f ♯ r (x i )) δ -1 ∥f -f ♯ r ∥ n + ∥f -f ♯ r ∥ Kr ≤ M |f (x i ) -f ♯ r (x i )| δ -1 ∥f -f ♯ r ∥ n + ∥f -f ♯ r ∥ Kr = M | f (x i ) -f ♯ r (x i )| ≤ M √ 2nR r (δ),and1 n n i=1 E L(y i , f (x i )) -L(y i , f ♯ r (x i )) δ -1 ∥f -f ♯ r ∥ n + ∥f -f ♯ r ∥ Kr 2 ≤ M 2 n n i=1 f (x i ) -f ♯ r (x i ) δ -1 ∥f -f ♯ r ∥ n + ∥f -f ♯ r ∥ Kr 2 = M 2 n n i=1 ( f (x i ) -f ♯ r (x i )) 2 = 2M 2 nR 2 r (δ).Thus, the requirements in Lemma G.1 hold with η = M √ 2nR r (δ) and ζ 2 = 2M 2 nR 2 r (δ). Then, by applying Lemma G.1, for any ι ∈ (0, 1), let t = 1 n log ι -1 , it holds at with probability at leastEQUATIONwhereC = (4M 2 + 16 √ 2πM 2 ) + 2 √ 2M 3and (i) follows from (28).Therefore, by combining ( 28) and ( 29), it holds at with probability at least 1 -ι thatEQUATIONwhereC = (4M 2 + 16 √ 2πM 2 ) + 2 √ 2M 3 + 4 √ πM .This completes the proof of Theorem 4.2. □D.2.2 Proof of Lemma D.2 Denote ∆ r = c 0 4 δ 4η n,r + 4u 2 λ 2η + (c ′ 0 + c 0 ) n j=r+1 ξ * j 2 .On the event V r (ι, δ n,r ), we claim thatf λ,r -f ♯ r 2 n ≤ C∆ r .By the optimality of f λ,r and the feasibility of f ♯ r , we haveE( f λ,r ) -E(f ♯ r ) + λ∥ f λ,r ∥ 2 Kr -λ∥f ♯ r ∥ 2 Kr ≤ 0.Define the function classG r := f ∈ H n,r : f -f ♯ r 2 n ≤ C∆ r , f -f ♯ r K ≤ b .By following a similar argument as that in the proof of Lemma C.2, it suffices to prove thatEQUATIONwhere f r is some function belonging to the boundary of G r .It follows from Assumption 3.1 thatEQUATIONwhere (i) uses the elementary inequality.Note that (32) establishes a connection between the excess risk and L(P n )-norm at f ♯ r , which allows us to prove Lemma D.2 by using a similar argument as the proof for Lemma C.2.Below we separately consider two cases:(i) ∥ f r -f ♯ r ∥ 2 n = C∆ r and ∥ f r -f ♯ r ∥ Kr ≤ b; and (ii) ∥ f r -f ♯ r ∥ 2 n ≤ C∆ r and ∥ f r -f ♯ r ∥ Kr = b.Case (i): On the event V r (ι, δ n,r ), we haveE(f ♯ r ) -E( f r ) ≤ E(f ♯ r ) -E( f r ) + C log ι -1 R r (δ n,r ) δ -1 n,r f r -f ♯ r n + f r -f ♯ r Kr (i) ≤ - c 0 2 f r -f ♯ r 2 n + (c ′ 0 + c 0 ) f ♯ r -f * 2 n + C log ι -1 R r (δ n,r ) δ -1 n,r f r -f ♯ r n + f r -f ♯ r Kr (ii) = - c 0 2 C∆ r + (c ′ 0 + c 0 ) n j=r+1 ξ * j 2 + C log ι -1 R r (δ n,r ) δ -1 n,r C∆ r + f r -f ♯ r Kr ,where (i) follows from (32), and (ii) follows from ∥ f r -f ♯ r ∥ 2 n = C∆ r and ( 26). Recall that δ n,r satisfiesC log ι -1 R r (δ n,r ) ≤ c 0 2 δ 2η+1 n,rand we choose λ satisfying λ ≥ δ 2 n,r . Following a similar argument as the proof for Lemma C.2, we haveE(f ♯ r ) -E( f r ) ≤ - c 0 2 C∆ r + (c ′ 0 + c 0 ) n j=r+1 ξ * j 2 + c 0 2 δ 2η n,r C∆ r + c 0 4 δ 4η n,r + λ 4 f r -f ♯ r 2 Kr .Since f r ∈ H n,r , there exists α r ∈ R n such thatf r = S ⊤ x,r ( α r ).Note thatEQUATIONFollowing the similar treatment as that in the proof for Lemma C.2 with K replaced by Kr and α replaced by α r , we haveEQUATIONPut the pieces together, and repeat the similar argument as that in the proof for Lemma C.2, for all γ ≥ 1 2 , we obtainE(f ♯ r ) -E( f r ) + λ∥f ♯ r ∥ 2 Kr -λ∥ f r ∥ 2 Kr ≤ - c 0 2 C∆ r + (c ′ 0 + c 0 ) n j=r+1 ξ * j 2 + c 0 2 δ 2η n,r + 2uλ η C∆ r + c 0 4 δ 4η n,r + 4u 2 λ 2ηand for sufficiently large C, we haveE(f ♯ r ) -E( f r ) + λ∥f ♯ r ∥ 2 Kr -λ∥ f r ∥ 2 Kr < 0.Case (ii): Repeat the similar argument as that in Case (i), on the event V r (ι, δ n,r ) and by Assumption 3.1, we haveE(f ♯ r ) -E( f r ) ≤ - c 0 2 f r -f ♯ r 2 n + (c ′ 0 + c 0 ) n j=r+1 ξ * j 2 + C log ι -1 R r (δ n,r ) δ -1 n,r f r -f ♯ r n + f r -f ♯ r Kr ≤ (c ′ 0 + c 0 ) n j=r+1 ξ * j 2 + C log ι -1 R r (δ n,r ) δ -1 n,r f r -f ♯ r n + f r -f ♯ r Kr ≤ (c ′ 0 + c 0 ) n j=r+1 ξ * j 2 + c 0 2 δ 2η n,r C∆ r + c 0 4 δ 4η+2 n,r λ -1 + λ 4 f r -f ♯ r 2 Kr ≤ (c ′ 0 + c 0 ) n j=r+1 ξ * j 2 + c 0 2 δ 2η n,r C∆ r + c 0 4 δ 4η n,r + λ 4 f r -f ♯ r 2 Kr ,where the last step holds with the choice of λ satisfying λ ≥ δ 2 n,r . Combine with ( 33) and ( 34) and by applying the elementary inequality to obtainE(f ♯ r ) -E( f r ) + λ∥f ♯ r ∥ 2 Kr -λ∥ f r ∥ 2 Kr ≤ (c ′ 0 + c 0 ) n j=r+1 ξ * j 2 + c 0 2 δ 2η n,r + 2uλ η C∆ r + c 0 4 δ 4η n,r + 4u 2 λ 2η - λ 2 f r -f ♯ r 2 Kr .By our choice that 0< λ ≤ 1, λ ≥ max{δ 2 n,r , n j=r+1 ξ * j 2 }, we have λ ≥ λ 2η , λ ≥ δ 4η n,r , and λ ≥ n j=r+1 ξ * j 2 .Note that in this case, ∥ f r -f ♯ r ∥ 2 Kr = b 2 . 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 r (ι, δ n,r ), we havef λ,r -f ♯ r 2 n ≤ C∆ r ≲ δ 4η n,r + λ 2η + n j=r+1 ξ * j 2 ,which completes the proof. □From ( 26)f ♯ r -f * 2 n = n j=r+1 ξ * j 2 .For the approximation bias, according to the polynomial assumption that ξ * j ≍ j -2γα-1 , we have∥f ♯ r -f * ∥ 2 n = n j=r+1 ξ * j 2 ≤ C n j=r+1 j -2γα-1 ≤ C ∞ r t -2γα-1 dt ≤ Cr -2γα .For the estimation error, we control the truncated kernel function first. Similar to the equality (20) forR(δ), if r > d(δ), we have R r (δ) = 1 n d(δ)δ 2 + 1 n r d(δ)+1 µ j .Moreover, for the regular kernel class, we have R r (δ) ≍EQUATIONNext, we split the remaining proof by considering two cases: (i) 1 2 ≤ γ ≤ 1; and (ii) γ > 1. Case (i): Recall that for the eigenvalues of K that satisfy µ j ≍ j -α , we have d(δ) ≍ δ -2/α . In addition, we notice that in this case, the best truncation level r to balance δ 4η and r -2γα is r ≍ d(δ). This means that whatever r is, we always have R r (δ) ≍ 1 n d(δ)δ 2 . Hence, the kernel complexity remains the same, and to avoid introducing additional approximation bias, the best choice of truncation level turns out to be r = n. Then, following a similar argument as that in Section C.3, we have δ 2 n,r ≤ C (log ι -1 ) 2 n α 2γα+1 . Choosing the optimal parameter of λ ≍ δ 2 n,r yieldsE( f λ,r ) -E(f * ) ≍ f λ,r -f * 2 n ≤ C (log ι -1 ) 2 n 2γα 2γα+1 .Case (ii): In this case, the best truncation level r to balance δ 4η and r -2γα is r ≍ δ -2/(γα) , which implies r ≲ d(δ) andR r (δ) ≍ 1 n rδ 2 ≍ 1 n δ 2αγ-2 αγ .Therefore, the solution to the inequality (3) can be upper bounded by the solution toC log ι -1 1 n δ 2αγ-2 αγ ≤ c 0 2 δ 3 .Solving this inequality yieldsδ 2 n,r ≤ C (log ι -1 ) 2 n γα 2γα+1 ,and we thus obtainr ≍ n (log ι -1 ) 2 1 2γα+1 .The desired upper bound in the case γ > 1 follows by choosing λ ≍ δ 2 n,r ≍ r -2γα . By combining these two cases, we complete the proof. □ E Proof of Theorem 4.4We consider the special case that the data is generated according to the mean regression modelY i = f * (x i ) + ε i with ε i ∼ N (0, 1)for each i ∈ [n].For this mean regression model, f * is the minimizer of the population risk E(f ) with squared loss specified.For any δ > 0 and γ ≥ 1 2 , define the ellipse classE γ (δ) :=    ξ = (ξ 1 , ..., ξ n ) ⊤ ∈ R n : n j=1 ξ 2 j (min{δ 2 , µ j }) 2γ ≤ u 2    .For ξ ∈ R n , define the rescaled norm∥ξ∥ 2 Eγ := n j=1 ξ 2 j (min{δ 2 , µ j }) 2γ .Then, it is equivalent to writeE γ (δ) = ξ = (ξ 1 , ..., ξ n ) ⊤ ∈ R n : ∥ξ∥ 2 Eγ ≤ u 2 .Recall that the statistical dimension is defined asd(δ) = min j ∈ [n] : µ j ≤ δ 2 .Our main proof is based on the following lemma that states a result concerning metric entropy. Lemma E.1. For any δ > 0 and γ ≥ 1 2 , there is a collection of 1 2 δ 2γ -separated points {ξ 1 , ..., ξ M } in E γ (δ) such that log M ≥ 1 32 d(δ).By using Lemma E.1, there exists a 1 2 δ 2γ -separated collection of points {ξ 1 , ..., ξ M } in E γ (δ) such that log M ≥ 1 32 d(δ). Given {ξ 1 , ..., ξ M }, we construct f 1 , ..., f M as f i = S ⊤ x (U D -1 ξ i ). Note that the TA scores corresponding to f i are given byU ⊤ S x (f i ) = U ⊤ K U D -1 ξ i = ξ i . Hence, {ξ 1 , ..., ξ M } ⊂ E γ (δ) implies f i ∈ H b K for each i ∈ [M ]. Moreover, we have∥f i -f j ∥ 2 n = ∥ D U ⊤ (U D -1 ξ i -U D -1 ξ j )∥ 2 = ∥ξ i -ξ j ∥ 2 2 ≥ δ 4γ 4 , which implies that {f 1 , ..., f M } is 1 2 δ 2γ -separated in H b K . Since ξ i ∈ E γ (δ), we also have ∥f i ∥ 2 n = ∥ξ i ∥ 2 2 = n k=1 ξ i k 2 = δ 4γ n k=1 ξ i k 2 δ 4γ ≤ u 2 δ 4γ .Therefore, by using the triangle inequality, we have∥f i -f j ∥ 2 n ≤ 2u 2 δ 4γ for each i, j ∈ [M ].Let ρ k be the underlying distribution of the collected data {(x i , y i )} n i=1 corresponding to f k . Then, there holds KL(ρ i ∥ρ j )(i) = n i=1 KL(N (f i (x i ), 1)∥N (f j (x i ), 1)) (ii) = n 2 ∥f i -f j ∥ 2 n ≤ u 2 nδ 4γwhere KL(•∥•) denotes the KL divergence between two distributions, (i) follows from the fact that KL(P 1 ⊗ P 2 ∥Q 1 ⊗ Q 2 ) = KL(P 1 ∥Q 1 ) + KL(P 2 ∥Q 2 ) and ⊗ denoting the product measure, and (ii) follows from the fact KL(N (µ 1 , σ 2 )∥N (µ 2 , σ 2 )) = (µ1-µ2) 2 2σ 2.Below is devoted to establishing the minimax lower bound by applying the standard Fano's method (see, for instance, Proposition 15.12 in Wainwright ( 2019)). To be specific, for δ > 0 and for any estimator f based on the data {(x i , y i )} n i=1 , we haveEQUATION)Below we separately consider two cases: i) 1 2 ≤ γ ≤ 1; and ii) γ > 1. Case i: For 1 2 ≤ γ ≤ 1, we take δ = (4c) 1 4γ δ n , where δ n is the critical radius defined as the smallest solution to (2) in Section 3. Plugging into (36) yieldsEQUATIONwhere d n = d(δ n ) and the last inequality holds since d(δ) is decreasing as δ grows and (4c) 1 4γ δ n ≤ δ n for sufficiently small c.1 2 ≤ γ ≤ 1, δ n is smallest solution to C log ι -1 R(δ) ≤ c 0 2 δ 2γ+1 .Moreover, for the regular kernel, we have R(δ) ≍ 1 n d(δ)δ 2 , which impliesδ 2γ+1 n ≲ 1 n d(δ n )δ 2 n = 1 n d n δ 2 n .Then, d n ≥ c 1 nδ 4γ n for some universal constant c 1 . Plugging this inequality into (37) yieldsinf f sup f * ∈H b K P ∥ f -f * ∥ 2 n ≥ cδ 4γ n ≥1 - 4cu 2 nδ 4γ n + log 2 c 1 nδ 4γ n ≥ 1 2 ,where the last step holds for sufficiently small c.Case ii: For γ > 1, we take δ = (4c)1 4γ δ 1/γ n,r, where δ n,r is the critical radius defined as the smallest solution to (3) in Section 4. It follows from (36) thatinf f sup f * ∈H b K P ∥ f -f * ∥ 2 n ≥ cδ 4 n,r ≥1 - 4cu 2 nδ 4 n,r + log 2 d((4c) 1 4γ δ 1/γ n,r )/32 ≥ 1 - 4cu 2 nδ 4 n,r + log 2 d(δ 1/γ n,r )/32 . Recall that for γ > 1, δ n,r is smallest solution to C log ι -1 R r (δ) ≤ c 0 2 δ 3 .According to (35), if r ≤ d(δ), we haveR r (δ) = 1 n rδ 2 .Hence, we haveδ 3 n,r ≲ 1 n rδ 2 = 1 n rδ 2 ,which leads to r ≥ c 2 nδ 4 n,r for some universal constant c 2 . Then, if we choose r ≍ d(δ1/γ n,r ) satisfying d(δ 1/γ n,r ) ≤ d(δ n,r ), we have inf f sup f * ∈H b K P ∥ f -f * ∥ 2 n ≥ cδ 4 n,r ≥1 - 4u 2 cnδ 4 n,r + log 2 Cc 2 nδ 4 n,r /32 ≥ 1 2 ,where the last step holds for sufficiently small c. This completes the proof of Theorem 4.4. □ Remark E.2. In the proof for the lower bound, we consider the Gaussian noise case. However, for the upper bound, we require Y ⊂ [-U, U ] when the squared loss is specified. The bounded range assumption essentially requires the random noise to be uniformly bounded. Nevertheless, the upper bound established in this paper can be also extended to the sub-Gaussian noise case with a slight order sacrifice of some log factors in the upper bound. Specifically, suppose that {ε i } n i=1 are i.i.d. sub-Gaussian variables: that is, there exist positive constants c, σ 2 such that P |ε i | > t ≤ c exp(-σ 2 t 2 ) for all t ≥ 0. Then, by the union bound, we haveP max i=1,...,n |ε i | > t ≤ P n i=1 |ε i | > t ≤ n i=1 c exp(-σ 2 t 2 ) = cn exp(-σ 2 t 2 ).Consequently, for any ι ∈ (0, 1), by taking t = σ -1 log cn ι , it holds with probability at least 1 -ι that max i=1,...,n|ε i | ≤ σ -1 log cn ι ≲ log 1 ι + log n.Further note that by the reproducing kernel property and our assumption that sup x,x ′ K(x, x ′ ) ≤ κ 2 , we have that for any x ∈ XEQUATIONTherefore, for the sub-Gaussian noise case, we can immediately complete the proof by replacingU with U ι,n = κ∥f * ∥ K + C( log 1 ι + √ log n).As a result, the upper bound for the sub-Gaussian noise case will align with that for the uniform bounded noise case up to some log factors.E.1 Proof of Lemma E.1 Lemma E.1 states a result concerning metric entropy, and its proof is motivated by that of Lemma 4 in Yang et al. (2017) , which only focuses on the just-aligned regime γ = 1 2 . For each j ∈ [M ], letEQUATIONwherew 1 = (w 1 1 , ..., w 1 d(δ) ) ⊤ , ..., w M = (w M 1 , ..., w M d(δ) ) ⊤ ∼ N (0, Id(δ)) are a collection of independent standard Gaussian vectors. We claim that with a probability greater 0, we can find a set {ξ 1 , ..., ξ M } generated in the above manner that are δ 2γ -separated in E(δ) and M ≥ e 1 32 d(δ) . On one hand, to show that {ξ 1 , ..., ξ M } ⊂ E γ (δ), we need to equivalently prove ∥ξ i ∥ 2Eγ ≤ u 2 for each i ∈ [M ]. Indeed, for each index i ∈ [M ], since δ 2 ≤ µ j for each j ≤ d(δ), we have∥ξ i ∥ 2 Eγ = ∥w i ∥ 2 2 2d(δ) . Note that ∥w i ∥ 2 2 ∼ χ 2 d(δ). Then, by using the tail bound for chi-square distribution (Example 2.11 in Wainwright ( 2019)), we haveEQUATIONwhere we use the assumption that u ≥ 2. By applying the union bound, we haveEQUATION)On the other hand, note that ∥ξ i -ξ j ∥ 2 2 = δ 4γ 2d(δ) ∥w iw j ∥ 2 2 . Since w i and w j are independent, we have (w iw j )/ √ 2 ∼ N (0, Id(δ)). Then, similar to the inequality (40), we also haveP ∥ξ i -ξ j ∥ 2 2 ≥ δ 4γ 4 =P 1 2d(δ) ∥w i -w j ∥ 2 2 ≥ 1 4 =P 1 2d(δ) ∥w i -w j ∥ 2 2 -1 ≥ - 3 4 ≥ 1 -e -9d(δ) 128 ,and by applying the union bound, we haveEQUATION)Now we consider the second term in the right hand of (43). It follows from Fubini's theorem thatE f (xi)-f * (xi) 0 (1 {Y ≤f * (xi)+t} -1 {Y ≤f * (xi)} )dt = f (xi)-f * (xi) 0 E[1 {Y ≤f * (xi)+t} -1 {Y ≤f * (xi)} ]dt = f (xi)-f * (xi) 0 F Y |X=xi (f * (x i ) + t) -F Y |X=xi (f * (x i )) dt.According to Assumption F.1, there holdsf (xi)-f * (xi) 0 F Y |X=xi (f * (x i ) + t) -F Y |X=xi (f * (x i )) dt ≥ f (xi)-f * (xi) 0 2c 0 |t|dt = c 0 (f (x i ) -f * (x i )) 2 ,andf (xi)-f * (xi) 0 F Y |X=xi (f * (x i ) + t) -F Y |X=xi (f * (x i )) dt ≤ f (xi)-f * (xi) 0 2c ′ 0 |t|dt = c ′ 0 (f (x i ) -f * (x i )) 2 .Then, we havec 0 (f (x i ) -f * (x i )) 2 ≤E f (xi)-f * (xi) 0 (1 {Y ≤f * (xi)+t} -1 {Y ≤f * (xi)} )dt ≤c ′ 0 (f (x i ) -f * (x i )) 2 .The desired conclusion immediately follows by summing from 1 to n. This completes the proof of Proposition F.2.The Logistic loss L(y, f (x)) = log(1 + exp(-yf (x))) is specified for the binary classification problem, where the response y takes values in {-1, 1}. Simple algebra yields the first and second derivatives of L(y, θ) in the second argument that∂L ∂θ = -y exp(-yθ) 1 + exp(-yθ)and∂ 2 L ∂θ 2 = y 2 (exp(-yθ/2) + exp(yθ)/2) 2 .It is clear that for any θ ∈ R, we have∂L ∂θ ≤ 1 and ∂ 2 L ∂θ 2 ≤ 1 4 , implying that L(y, •) is 1-Lipschitz continuous and the c ′ 0 -local smoothness condition holds with c ′ 0 = 1 4 . Recall from (38). For f ∈ H K and x ∈ X satisfying |f (x)-f * (x)| ≤ D, denote B = κ∥f * ∥ K +D, we have ∂ 2 L ∂θ 2 θ=f (x)≥ 1 e -B + e B + 2 , implying the locally strong convexity condition holds with c 0 = 1 e -B +e B +2 .The Exponential loss L(y, f (x)) = exp(-yf (x)) is used in the AdaBoost algorithm designed for the classification problem, where y ∈ {-1, 1}. Note that the first and second derivatives of L(y, θ) in the second argument is given by∂L ∂θ = -ye -yθ and ∂ 2 L ∂θ 2 = e -yθ .For any θ ∈ R, we have ∂L ∂θ ≤ 1, 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, we have thate -B ≤ ∂ 2 L ∂θ 2 ≤ e B .This ensures that the local strong convexity condition holds with c 0 = e -B and the local smoothness condition holds with c ′ 0 = e B .G Supporting Lemmas.The following lemma presents Talagrand's concentration inequality for random elements taking values in some space Z (Bousquet, 2002; Lv et al., 2018) . Detailed proofs can be found in Bousquet (2002) . Lemma G.1 (Talagrand's concentration inequality). Let Z 1 , . . . , Z n be independent random elements taking values in some space Z equipped with norm ∥ • ∥. Let F be a class of real-valued measurable functions acting on Z. If we havemax i∈[n] ∥f (Z i )∥ ≤ η and 1 n n i=1 Var(f (Z i )) ≤ ζ 2 , ∀f ∈ F, define the empirical process Z := sup f ∈F | 1 n n i=1 (f (Z i ) -Ef (Z i ))|, then for any t > 0 P Z ≥ E(Z) + t 2 (ζ 2 + 2ηE(Z)) + 2ηt 2 3 ≤ exp(-nt 2 ).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 {ε 1 , ..., ε n }, i.e. P(ε i = 1) = P(ε i = -1) = 1 2 (Proposition 4.11 in Wainwright ( 2019)). In our proof, we consider a sequence of standard Gaussian variables to utilize the rotation invariance of the Gaussian vector. Lemma G.2 (Symmetrization). Let X 1 , ..., X n be a sequence of random variables and w 1 , ..., w n ∼ N (0, 1) denote the standard Gaussian variables independent of X 1 , ..., X n . For any measurable function class F, we haveE 1 n sup f ∈F n i=1 (f (X i ) -E[f (X i )]) ≤ √ 2πE 1 n sup f ∈F n i=1 w i f (X i )Proof. By applying Proposition 4.11 in Wainwright (2019), we haveE 1 n sup f ∈F n i=1 (f (X i ) -E[f (X i )]) ≤ 2E 1 n sup f ∈F n i=1 ε i f (X i ) .Therefore, it remains to prove thatE 1 n sup f ∈F n i=1 ε i f (X i ) ≤ π 2 E 1 n sup f ∈F n i=1 w i f (X i ) Indeed, we have E ε 1 n sup f ∈F n i=1 ε i f (X i ) (i) = π 2 E ε 1 n sup f ∈F E w n i=1 |w i |ε i f (X i )) (ii) ≤ π 2 E ε 1 n E w sup f ∈F n i=1 |w i |ε i f (X i ) = π 2 E 1 n sup f ∈F n i=1 |w i |ε i f (X i ) (iii) = π 2 E 1 n sup f ∈F n i=1 w i f (X i ) ,where we use E w to denote taking expectation with respect to w 1 , ..., w n and use a similar notation E ε for taking expectation with respect to ε 1 , ..., ε n , (i) follows from E[|w i |] = 2 π , (ii) uses Jensen's inequality and (iii) is due to the fact that w i has the same distribution with ε i w i 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 symmetrization technique for the Lipschitz function family. Lemma G.3 (Gaussian contraction inequality). For any set T ∈ R d , and let {ϕ j : R → R, j = 1, ..., d} be any family of M -Lipschitz functions such that ϕ j (0) = 0 for j ∈ [d], we haveE   sup θ∈T d j=1 w j ϕ j (θ j )   ≤ 2M E   sup θ∈T d j=1 w j θ j   .In this section, we conduct a 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, we apply Sobolev kernel K(x, x ′ ) = min{x, x ′ } for univariate cases and Laplacian kernel K(x, x ′ ) = exp(-∥ x -x ′ ∥ 1 ) for multi-dimension cases. The elements of multi-dimensional covariates are independently sampled from the normal distribution, while in the univariate case, the covariate is sampled from the uniform distribution on [0, 1]. Aligned with the previous notation, TKM means truncated kernel-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 on the same hardware setup: Intel i9 13900K CPU @ 2.20GHz with 128 GB memory. Example 1 (Kernel quantile regression). In 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-generating scheme that y = f 0 (x) + σ(ϵ -Φ -1 (τ )), where σ = 3, ϵ ∼ N (0, 1) and Φ denotes CDF function of standard normal distribution. Here, we set f 0 (x) = sin 2(x 1 + x 2 + x 3 ) with x = (x 1 , x 2 , x 3 ) ⊤ and vary the quantile level τ from {0.3, 0.5, 0.7}. We first compare the numerical performance between TKM and KM in estimating the true function f 0 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 2 .It is clear that under different quantile levels, TKM always outperforms KM. More interestingly, the decline rate of TKM is significantly faster than that of KM, 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. Example 2 (Kernel ridge regression). In the kernel ridge regression, we consider the model y = f 0 (x) + ϵ, where f 0 (x) = sin(x), ϵ ∼ N (0, 1) for univariate x. While for multi-dimension scenario, we assume dimension p = 3 and we generate data from y = sin(2(x 1 + x 2 + x 3 )) + ϵ, where ϵ ∼ N (0, 0.5). Another setting is similar to quantile regression.As shown in Figure 6 , it can be observed that in both the univariate and multivariate scenarios, TKM outperforms KM significantly. Furthermore, in multi-dimensional cases, the advantage of TKM is even more pronounced. From the right panel, it can be seen that although the optimal value of r differs, they all reach their minimum at a 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 as sign(x) and generate data through the model y = sign(f 0 (x) + ϵ). In univariate case f 0 (x) = sin(10x) and for the multi-dimensional counterpart f 0 (x) = 3 sin(x 1 + x 2 + x 3 ). ϵ ∼ N (0, 1.5) in both case.As shown in Figure 7 , a similar trend can be observed in both methods, where TKM outperforms KM under different sample sizes. Furthermore, the advantage of TKM becomes more pronounced in Note that our technical analysis can also cover the exponential decay case that µ j ≍ exp(-αj) and ξ * j 2 ≍ exp(-(2γα + β)j) with α, β > 0. Precisely, under the exponential decay setting, the explicit upper bound of the approximation bias term can be derived by Note that if r ≥ log n (2γα+β) , we always have n j=r+1 ξ * j 2 ≲ 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 γ is if r is greater than a certain threshold. We also conduct some numerical experiments to verify this finding. Specifically, the experimental setup is the same as Example 1 in Section H.1 except that we set f * (x) = sin(6x) and the Gaussian kernel is used. The experiment result, presented in Figure 10 , shows that TKM initially performs worse than KM for the small value of r. Whereas, as r surpasses a threshold, TKM maintains comparable performance to KM. This observation precisely aligns with our theory for the exponential decay scenario.Previously, all the tuning parameters were tuned to the best for both competitors. In this part, we 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 = f * (x) + √ 2(ε -Φ -1 (τ )) with f * (x) = sin(6x), x = 0, 1 n , . . . , n-1 n , and ε ∼ N (0, 1). In this experiment, we use the Laplacian kernel K(x, x ′ ) = exp(-||x -x ′ || 1 ), and the parameters r 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, it can be observed that TKM consistently outperforms KM, which further confirms our theoretical findings that TKM can achieve superior performance across various scenarios. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.M L,b is a constant with possible dependence on b.For squared loss, we assume that Y ⊂ [-U, U ], which is commonly adopted in literature of learning theory(Bartlett et al., 2005;Smale & Zhou, 2005, 2007;Wei et al., 2017).τ is the threshold parameter for Huber loss.Note that we assume λ ≤ 1 as the theoretical choice of λ typically depends on n and is close to zero for sufficiently large n.A function ψ is called nontrivial sub-root if ψ ̸ ≡ 0, and it is nonnegative, nondecreasing and if ψ(r)/ √ r is nonincreasing for r > 0.Otherwise, by the assumption µj → 0, we always have µj ≤ 1 for j exceeding some constant j * . 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: N/A
questions: 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: limitations: - A more thorough experimental analysis can be helpful.
paper_summary: paper_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.
strength_weakness: strength_weakness: - Some of the findings are also covered in this paper [1]

[1] Arash A. Amini et al., Target alignment in truncated kernel ridge regression
questions: 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? 

[1] Runtian Zhai et al. , Spectrally Transformed Kernel Regression
limitations: limitations: See weakness
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2) 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.
3) 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.
questions: 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?
2) Are the choices of r and lambda mentioned in Section 4 the only feasible choices to achieve optimal learning rate for TKM?
limitations: limitations: Yes.
paper_summary: paper_summary: This paper investigated the impact of alignment between the target function of interest and kernel matrices.
To overcome the saturation effect, the TKM was introduced and its learning rate is analyzed.
strength_weakness: strength_weakness: The approximation bias term in Thm 4.2 requires Assumption 3.4 holds. Could you also provide some results for different decay rate?
questions: questions: None.
limitations: limitations: None.
paper_summary: paper_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$.
strength_weakness: strength_weakness: 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.
questions: questions: I have several remark/questions regarding the algorithmic perspective on TKRR:

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

2. 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: limitations: This is a theoretical paper. All limitations are stated clearly in the statements.

Comments: title: Appreciation for Reviewer Pn9U
Appreciation for Reviewer ikTW
Appreciation for Reviewer Twpu
Reference
Reference
Reference
Reference
comment: Thank you very much for your question and for bringing us these references. Following your suggestion, 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, we randomly select 500 samples for training and another 500 samples for testing. The above procedure is repeated 10 times, where the Laplacian kernel is adopted and the parameters $\gamma$ and $r$ are tuned by $5$-fold cross-validation. The averaged MSE  with different $\tau\in (0.3,0.5,0.7)$ is reported in Table 1.  

It is thus clear that the obtained results in the real application align with the results for synthetic data and our theoretical findings, which further demonstrates the benefits of TKM.  Due to the time limit, a more comprehensive analysis and discussion of these two competitors in real applications will be added to Appendix of the revised manuscript.

**Table 1： Averaged MSE for different $\tau$.**
| $\tau$  | $0.3$           | $0.5$           | $0.7$           | 
|------|-----------------|-----------------|-----------------|
| KM   | $0.590 \pm 0.027$ | $0.483 \pm 0.035$ | $0.638 \pm 0.073$ | 
| TKM  | $0.548 \pm 0.026$ | $0.454 \pm 0.045$ | $0.530 \pm 0.046$ | 

**Reference:**

[1] Breiman, L. (2001). Random forests. *Machine Learning,* 45:5–32.
Thank you for your detailed response and dialog with reviewers.

One comment/question I have is around your numerical evaluation: from what I can see, the evaluation is conducted with synthetic data only. Do you know if you also see similar improved MSE on some non-synthetic datasets (as used in previous kernel alignment studies [1], [2])?  

[1] Cristianini, Nello, et al. "On kernel-target alignment." Advances in neural information processing systems 14 (2001).
[2] Cortes, Corinna, et al. "Algorithms for learning kernels based on centered alignment." The Journal of Machine Learning Research 13 (2012): 795-828.
Thank you for your feedback. We sincerely appreciate your time and effort in reviewing our work and the valuable comments during the review.
Thank you for your detailed response! And I will keep my already positive score
We sincerely appreciate your feedback and the positive evaluation of our paper. Thank you once again for the insightful comments during the review, which greatly contributed to the improvement of our work.
Thank you for your response and your prompt experimental results. I would keep my score and lean to accept this paper.
Thank you very much for your response and raising the score!  We are pleased to hear that your concern has been addressed.
Once again, thank you for the positive evaluation of our paper and the constructive comments, which are greatly helpful to us.
Thank you for your reply. My concern is addressed, and I will raise my score.
We apologize for any confusion regarding the references cited in our response during the rebuttal phase. Below, we have provided the complete reference information that you may need.

[1]  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.
We apologize for any confusion regarding the references cited in our response during the rebuttal phase. Below, we have provided the complete reference information that you may need.

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

[2]  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.*
We apologize for any confusion regarding the references cited in our response during the rebuttal phase. Below, we have provided the complete reference information that you may need.

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

[2]  Steinwart, I., & Christmann, A. (2008). *Support Vector Machines.*  Springer Science & Business Media.

[3]  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.

[4]  Li, Z., Ton, J.-F., Oglic, D., & Sejdinovic, D. (2019). Towards a unified analysis of random Fourier features. *In International Conference on Machine Learning* (pp. 3905–3914). PMLR.

[5] Farrell, M. H., Liang, T., & Misra, S. (2021). Deep neural networks for estimation and inference. *Econometrica,* 89, 181–213.

[6] Lai, J., Huang, D., Lin, Q. et al. (2024). The optimality of kernel classifiers in Sobolev space. *In The Twelfth International Conference on Learning Representations.*

[7] Yang, Y., Pilanci, M., & Wainwright, M. J. (2017). Randomized sketches for kernels: Fast and optimal nonparametric regression. *Annals of Statistics,* 45, 991–1023. 14.

[8] Cui, H., Loureiro, B., Krzakala, F., & Zdeborová, L. (2021). Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. *Advances in Neural Information Processing Systems,* 34, 10131–10143.
We apologize for any confusion regarding the references cited in our response during the rebuttal phase. Below, we have provided the complete reference information that you may need.

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

[2]  Lv, S., Lin, H., Lian, H., & Huang, J. (2018). Oracle inequalities for sparse additive quantile regression in reproducing kernel Hilbert space. *The Annals of Statistics, 46,* 781–813.

[3]  Li, Z., Ton, J.-F., Oglic, D., & Sejdinovic, D. (2019). Towards a unified analysis of random Fourier features. *In International Conference on Machine Learning* (pp. 3905–3914). PMLR.


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

[5]  Wainwright, M. J. (2019). *High-dimensional Statistics: A Non-asymptotic Viewpoint* volume 48. Cambridge University Press.