MSC2020 subject classifications: 62H30, 41A25, 41A35, 68Q32.
Introduction
Learning theory studies how to infer the structure of an unknown function from sample data. In high-dimensional spaces, learning algorithms often face the curse of dimensionality, as the sample size n n n d d d R d \mathbb{R}^{d} R d ϱ \varrho ϱ d d d
Kernel methods, including support vector machines (SVMs), are a classical family of machine learning algorithms with a solid mathematical foundation in reproducing kernel Hilbert space (RKHS) theory [2 , 15 ] . The choice of kernel determines the hypothesis space and its approximation properties. In this paper, we focus on the Gaussian kernel, which measures similarity through Euclidean distances and provides a nonparametric framework for nonlinear prediction. Classical results on Euclidean domains establish fast learning rates for Gaussian SVMs. For hinge-loss classification, the work [17 ] combines Tsybakov’s noise condition with a geometric noise condition to control estimation and approximation errors. Classification with varying Gaussian kernels and general convex losses is studied in [27 ] , which combines Sobolev approximation, RKHS covering estimates, and comparison inequalities for excess misclassification risk. For least-squares and conditional quantile regression, the work [8 ] derives oracle inequalities and essentially minimax optimal learning rates under suitable smoothness and distributional assumptions. The work [14 ] considers correntropy loss and uses varying Gaussian kernels to achieve the minimax rate of convergence.
Despite the dependence on the ambient metric, existing studies show that Gaussian kernel methods can overcome the curse of ambient dimensionality under suitable manifold and regularity assumptions, with learning rates governed by the intrinsic dimension [10 , 13 , 21 , 28 , 29 , 30 ] .
The early work in [29 , 30 ] develops the connection between Gaussian approximation and learning on manifolds and establishes approximation estimates and learning bounds governed by the manifold dimension. However, the approximation results in [29 , 30 ] identify a saturation issue. For the direct Gaussian integral approximation, increasing the regularity α \alpha α α = 2 \alpha= 2 α = 2
Subsequent work in [28 ] studies Gaussian process regression on manifolds and derives intrinsic-dimensional RKHS entropy estimates, but the accompanying approximation result remains restricted to smoothness at most two, leaving the second-order saturation issue unresolved.
The work [10 ] introduces a more general box-counting dimension condition. By expressing the low-dimensional structure through covering numbers of the input domain, their work obtains learning rates for Gaussian SVMs on supports that need not be smooth manifolds. Related ideas are developed for pairwise learning in our earlier work [13 ] , where oracle inequalities and a box-counting dimension assumption yield fast rates for Gaussian kernel estimators. In their squared-loss approximation analyses, both works use signed combinations of Gaussian kernels with different bandwidths to cancel lower-order approximation terms. Under their smoothness assumptions on extensions to the ambient Euclidean space, these constructions achieve arbitrarily high approximation orders and thus overcome second-order saturation of the approximation error. However, the use of ambient-space extensions yields squared RKHS norm bounds of order γ − d \gamma^{-d} γ − d γ \gamma γ
Our principal inspiration is the recent work [21 ] on adaptive Bayesian regression with low intrinsic dimensionality. The results in [21 ] , Lemma 4.1 and Proposition 4.2 establish high-order Gaussian expansions and remove the smoothness restriction by recursively correcting the input function. They provide approximation of intrinsically defined Hölder functions of arbitrary positive order, with error measured in the supremum norm. By constructing the approximant directly on the manifold without extending the target function to the ambient Euclidean space, they also obtain a squared RKHS norm bound of order γ − ϱ \gamma^{-\varrho} γ − ϱ ϱ \varrho ϱ
Building on the high-order Gaussian expansion in [21 ] , we extend the approximation framework from intrinsic Hölder classes to the broader Besov spaces B 2 , ∞ α ( X ) B_{2,\infty}^{\alpha}(X) B 2 , ∞ α ( X ) α > 0 \alpha> 0 α > 0 L 2 ( X ) L_{2}(X) L 2 ( X ) f f f L 2 ( X ) L_2(X) L 2 ( X ) C γ − ϱ ∥ f ∥ L 2 ( X ) 2 C\gamma^{-\varrho}\|f\|_{L_2(X)}^2 C γ − ϱ ∥ f ∥ L 2 ( X ) 2 L 2 ( X ) L_2(X) L 2 ( X ) [19 , 20 , 23 ] .
In this paper, we study the statistical learning problem of binary classification with logistic loss
ϕ ( t ) = log ( 1 + e − t ) . \phi(t) = \log(1 + e^{-t}). ϕ ( t ) = log ( 1 + e − t ) . The Bayes function
f ∗ = log η 1 − η f^* = \log\frac{\eta}{1-\eta} f ∗ = log 1 − η η can be unbounded when the conditional class probability η \eta η [15 Theorem 7.22] , are not directly applicable to logistic loss. Some existing analyses, such as [9 ] , impose a boundedness assumption on the Bayes function f ∗ f^* f ∗ f ∗ f^* f ∗
Logistic classification with Gaussian kernels is studied directly in [26 ] . It combines Sobolev approximation with a truncation level that can increase with the sample size, and its general analysis already addresses potentially unbounded targets. Its stochastic analysis does not exploit variance bounds that shrink with the excess risk. Combined with its approximation and truncation estimates, this yields a slow rate for the misclassification error. Previous works [1 , 9 ] consider the variance estimate, but with an exponential dependence on the supremum bound for logistic loss. Hence their bound can deteriorate rapidly when regularization decreases.
The concentration argument in this paper follows the localization strategy developed in [16 ] . That analysis uses the regularized excess risk to control both the norm of the candidate functions and the variance of their loss differences, and then combines local complexity estimates with concentration. We adapt this framework using a logistic Bernstein-type inequality whose constant grows only linearly with the supremum norm of the predictor. This variance control permits an oracle analysis without a uniform bound on the Bayes function f ∗ f^* f ∗
The unboundedness issue also motivates the work [32 ] on classification with deep neural networks and logistic loss. Their result [32 Theorem 2.1] introduces an oracle-type inequality with a flexible auxiliary reference loss. A carefully chosen bounded reference preserves the Bayes risk in expectation while controlling the second moments needed for concentration. They also provide an efficient ReLU approximation of the logarithm near zero, with only polylogarithmic dependence on the inverse distance to the singularity in the network complexity. See [32 Theorem 2.4] . These tools yield learning rates under regularity assumptions on the conditional class probability, without requiring a bounded Bayes function f ∗ f^* f ∗
In this paper, we study norm-regularized Gaussian kernel estimators on a compact Riemannian manifold X X X ϱ \varrho ϱ
We establish an oracle inequality for logistic loss without assuming a uniform bound on the Bayes function f ∗ f^* f ∗ Theorem 3.2 applies to separable normed function spaces, with constants uniform in the relevant entropy exponent. Corollary 3.3 further allows covering estimates that are available only above a positive radius b b b b 2 / λ b^2/\lambda b 2 / λ
We prove approximation bounds for Besov functions on the manifold by constructing a signed multiscale Gaussian approximation S γ , s f S_{\gamma,s}f S γ , s f α > 0 \alpha>0 α > 0 Theorems 4.1 and 4.3 give
∥ S γ , s f ∥ H γ ( X ) ≤ C γ − ϱ / 2 ∥ f ∥ L 2 ( X ) , \|S_{\gamma,s}f\|_{\mathcal{H}_\gamma(X)} \le C\gamma^{-\varrho/2}\|f\|_{L_2(X)}, ∥ S γ , s f ∥ H γ ( X ) ≤ C γ − ϱ /2 ∥ f ∥ L 2 ( X ) , ∥ S γ , s f − f ∥ L 2 ( X ) ≤ C γ α ∥ f ∥ B 2 , ∞ α ( X ) . \|S_{\gamma,s}f-f\|_{L_2(X)} \le C\gamma^\alpha\|f\|_{B^\alpha_{2,\infty}(X)}. ∥ S γ , s f − f ∥ L 2 ( X ) ≤ C γ α ∥ f ∥ B 2 , ∞ α ( X ) . Thus the construction removes second-order saturation while retaining a squared RKHS norm bound of order γ − ϱ \gamma^{-\varrho} γ − ϱ
We combine the oracle and approximation bounds with the manifold covering estimate in [28 Lemma 5.4] to derive, for a density g ∈ L p ( X ) g \in L_p(\mathcal{X}) g ∈ L p ( X ) 2 ≤ p ≤ ∞ 2 \le p \le\infty 2 ≤ p ≤ ∞
( ( log n ) ℓ + 1 n ) 4 α ( 1 − 1 / p ) 4 α ( 1 − 1 / p ) + 3 ℓ \left(\frac{(\log n)^{\ell+1}}{n}\right)^{\frac{4\alpha(1-1/p)}{4\alpha(1-1/p)+3\ell}} ( n ( log n ) ℓ + 1 ) 4 α ( 1 − 1/ p ) + 3 ℓ 4 α ( 1 − 1/ p ) Its polynomial and logarithmic exponents depend on the intrinsic dimension ℓ \ell ℓ α \alpha α f ∗ f^* f ∗ p p p d d d Theorem 4.7 .
( ( log n ) ℓ + 2 n ) 2 α ( 1 − 1 / p ) 2 α ( 1 − 1 / p ) + ℓ \left(\frac{(\log n)^{\ell+2}}{n}\right)^{\frac{2\alpha(1-1/p)}{2\alpha(1-1/p)+\ell}} ( n ( log n ) ℓ + 2 ) 2 α ( 1 − 1/ p ) + ℓ 2 α ( 1 − 1/ p ) For bounded densities, the logistic excess-risk bound for the clipped predictor has the same polynomial exponent 2 α / ( 2 α + ℓ ) 2\alpha/(2\alpha+\ell) 2 α / ( 2 α + ℓ ) n − α / ( 2 α + ℓ ) n^{-\alpha/(2\alpha+\ell)} n − α / ( 2 α + ℓ )
The rest of this paper is organized as follows. § 2 introduces the problem setting and related notations. § 3 presents the Bernstein-type bound and the oracle inequalities for logistic loss. § 4 establishes Gaussian approximation bounds for Besov functions on manifolds and derives learning rates for both the original and clipped predictions. § 5 summarizes the results and discusses further questions. All proofs are collected in Appendix § 6 .
Preliminaries
This section reviews some basic notions of the logistic classification problem, function spaces on manifolds, Gaussian RKHSs and complexity measures of function classes.
The Logistic Classification Problem
We consider the binary classification problem where we regard a separable metric space X \mathcal{X} X Y = { − 1 , 1 } \mathcal{Y}=\{-1,1\} Y = { − 1 , 1 } P P P X × Y \mathcal{X}\times\mathcal{Y} X × Y P X P_{\mathcal{X}} P X P P P X \mathcal{X} X η ( x ) : = P ( Y = 1 ∣ X = x ) \eta(x):=P(Y=1\mid X=x) η ( x ) := P ( Y = 1 ∣ X = x )
ϕ ( t ) : = log ( 1 + e − t ) . \phi(t):=\log(1+e^{-t}). ϕ ( t ) := log ( 1 + e − t ) . We define the logistic risk of a measurable function f : X → R f:\mathcal{X}\to\mathbb{R} f : X → R
R ( f ) : = E P ϕ ( Y f ( X ) ) . \mathcal{R}(f):=\mathbb{E}_{P}\phi(Yf(X)). R ( f ) := E P ϕ ( Y f ( X )) . With the convention 0 log 0 = 0 0\log0=0 0 log 0 = 0
R ∗ : = inf f : X → R f m e a s u r a b l e R ( f ) = ∫ X ( − η log η − ( 1 − η ) log ( 1 − η ) ) d P X . \mathcal{R}^*:=\inf_{\substack{f:\mathcal{X}\to\mathbb{R}\\ f\ \mathrm{measurable}}}\mathcal{R}(f)=\int_{\mathcal{X}}\left(-\eta\log\eta-(1-\eta)\log(1-\eta)\right)dP_{\mathcal{X}}. R ∗ := f : X → R f measurable inf R ( f ) = ∫ X ( − η log η − ( 1 − η ) log ( 1 − η ) ) d P X . When 0 < η ( x ) < 1 0<\eta(x)<1 0 < η ( x ) < 1
f ∗ ( x ) : = log η ( x ) 1 − η ( x ) . f^*(x):=\log\frac{\eta(x)}{1-\eta(x)}. f ∗ ( x ) := log 1 − η ( x ) η ( x ) . We do not regard f ∗ f^* f ∗ η \eta η
ψ ( x , y ) : = { ϕ ( y f ∗ ( x ) ) , 0 < η ( x ) < 1 , 0 , η ( x ) ∈ { 0 , 1 } . \psi(x,y):=
\begin{cases}
\phi(yf^*(x)), & 0<\eta(x)<1,\\
0, & \eta(x)\in\{0,1\}.
\end{cases} ψ ( x , y ) := { ϕ ( y f ∗ ( x )) , 0 , 0 < η ( x ) < 1 , η ( x ) ∈ { 0 , 1 } . Then E P ψ ( X , Y ) = R ∗ \mathbb{E}_{P}\psi(X,Y)=R^* E P ψ ( X , Y ) = R ∗ P X { η ∈ { 0 , 1 } } > 0 P_X\{\eta\in\{0,1\}\}>0 P X { η ∈ { 0 , 1 }} > 0
To learn a classifier from n n n D = ( ( X 1 , Y 1 ) , … , ( X n , Y n ) ) D=((X_1,Y_1),\ldots,(X_n,Y_n)) D = (( X 1 , Y 1 ) , … , ( X n , Y n )) F \mathcal{F} F
f ^ D ∈ arg min f ∈ F 1 n ∑ i = 1 n ϕ ( Y i f ( X i ) ) . \widehat{f}_D\in\underset{f\in\mathcal{F}}{\arg\min}\ \frac{1}{n}\sum_{i=1}^{n}\phi(Y_i f(X_i)). f D ∈ f ∈ F arg min n 1 i = 1 ∑ n ϕ ( Y i f ( X i )) . or, usually, a regularized version:
f ^ D , λ ∈ arg min f ∈ F { 1 n ∑ i = 1 n ϕ ( Y i f ( X i ) ) + λ ∥ f ∥ F 2 } . (1) \widehat{f}_{D,\lambda}\in\underset{f\in\mathcal{F}}{\arg\min}\left\{\frac{1}{n}\sum_{i=1}^{n}\phi(Y_i f(X_i))+\lambda\lVert f\rVert_{\mathcal{F}}^2\right\}. \tag*{(1)} f D , λ ∈ f ∈ F arg min { n 1 i = 1 ∑ n ϕ ( Y i f ( X i )) + λ ∥ f ∥ F 2 } . (1) where λ > 0 \lambda>0 λ > 0 ∥ ⋅ ∥ F \lVert\cdot\rVert_{\mathcal{F}} ∥ ⋅ ∥ F F \mathcal{F} F R ( f ^ D , λ ) − R ∗ R(\widehat{f}_{D,\lambda})-R^* R ( f D , λ ) − R ∗ n n n λ \lambda λ F \mathcal{F} F λ n \lambda_n λ n F n \mathcal{F}_n F n n n n n → ∞ n\to\infty n → ∞
The logistic loss serves as a convex surrogate for the 0–1 classification loss to facilitate optimization. For a measurable decision function f : X → R f:\mathcal{X}\to\mathbb{R} f : X → R
R 01 ( f ) : = E P 1 { sgn ( f ( X ) ) ≠ Y } , R_{01}(f):=\mathbb{E}_{P}\mathbf{1}_{\{\operatorname{sgn}(f(X))\ne Y\}}, R 01 ( f ) := E P 1 { sgn ( f ( X )) = Y } , R 01 ∗ : = ∫ X min { η ( x ) , 1 − η ( x ) } d P X ( x ) . R^*_{01}:=\int_{\mathcal{X}}\min\{\eta(x),1-\eta(x)\}\,dP_X(x). R 01 ∗ := ∫ X min { η ( x ) , 1 − η ( x )} d P X ( x ) . Here we agree that sgn ( 0 ) = 1 \operatorname{sgn}(0)=1 sgn ( 0 ) = 1 R 01 ( f ) R_{01}(f) R 01 ( f ) f f f [4 , 7 , 15 , 31 ] . For the logistic loss ϕ \phi ϕ [4 ] , the calibration inequality takes the form
R 01 ( f ) − R 01 ∗ ≤ C R ( f ) − R ∗ . (2) R_{01}(f)-R^*_{01}\le C\sqrt{R(f)-R^*}. \tag*{(2)} R 01 ( f ) − R 01 ∗ ≤ C R ( f ) − R ∗ . (2) This calibration inequality can be improved when the distribution P P P [24 ] . See a detailed discussion in Remark 4.1.
Function Spaces on Manifolds
For a data domain X ⊂ R d \mathcal{X}\subset\mathbb{R}^d X ⊂ R d n n n d d d f ∗ ∈ C α ( [ 0 , 1 ] d ) f^*\in C^\alpha([0,1]^d) f ∗ ∈ C α ([ 0 , 1 ] d ) n − 2 α / ( 2 α + d ) n^{-2\alpha/(2\alpha+d)} n − 2 α / ( 2 α + d ) [18 ] . To address the curse of dimensionality, a common assumption is that the marginal distribution P X P_X P X X ⊂ R d \mathcal{X}\subset\mathbb{R}^d X ⊂ R d ϱ ≪ d \varrho\ll d ϱ ≪ d
We now specify the manifold assumption and introduce the function spaces used to measure regularity on it. Suppose that X ⊂ R d \mathcal{X}\subset\mathbb{R}^d X ⊂ R d C ∞ C^\infty C ∞ 1 ≤ ϱ < d 1\le\varrho<d 1 ≤ ϱ < d d X d_{\mathcal{X}} d X d V dV d V E x \mathcal{E}_x E x inj ( X ) \operatorname{inj}(\mathcal{X}) inj ( X ) x ∈ X x\in\mathcal{X} x ∈ X inj ( X ) > 0 \operatorname{inj}(\mathcal{X})>0 inj ( X ) > 0 m ≥ 1 m\ge1 m ≥ 1 H m ( X ) H^m(\mathcal{X}) H m ( X )
∥ f ∥ H m ( X ) 2 = ∑ ℓ = 0 m ∫ X ∣ ∇ ℓ f ( x ) ∣ 2 d V ( x ) . \lVert f\rVert_{H^m(\mathcal{X})}^2=\sum_{\ell=0}^{m}\int_{\mathcal{X}}\lvert\nabla^\ell f(x)\rvert^2\,dV(x). ∥ f ∥ H m ( X ) 2 = ℓ = 0 ∑ m ∫ X ∣ ∇ ℓ f ( x ) ∣ 2 d V ( x ) . Here, ∇ \nabla ∇ X X X f ∈ L 2 ( X ) + H m ( X ) f \in L_2(X) + H^m(X) f ∈ L 2 ( X ) + H m ( X ) K K K
K ( t , f ; L 2 ( X ) , H m ( X ) ) : = inf f = f 0 + f 1 f 0 ∈ L 2 ( X ) , f 1 ∈ H m ( X ) { ∥ f 0 ∥ L 2 ( X ) + t ∥ f 1 ∥ H m ( X ) } . K(t,f;L_2(X),H^m(X)):=\inf_{\substack{f=f_0+f_1\\ f_0\in L_2(X),\ f_1\in H^m(X)}}\{\lVert f_0\rVert_{L_2(X)}+t\lVert f_1\rVert_{H^m(X)}\}. K ( t , f ; L 2 ( X ) , H m ( X )) := f = f 0 + f 1 f 0 ∈ L 2 ( X ) , f 1 ∈ H m ( X ) inf {∥ f 0 ∥ L 2 ( X ) + t ∥ f 1 ∥ H m ( X ) } . Given α > 0 \alpha>0 α > 0 m > α m>\alpha m > α
B 2 , ∞ α ( X ) : = ( L 2 ( X ) , H m ( X ) ) α / m , ∞ , B^\alpha_{2,\infty}(X):=(L_2(X),H^m(X))_{\alpha/m,\infty}, B 2 , ∞ α ( X ) := ( L 2 ( X ) , H m ( X ) ) α / m , ∞ , ∥ f ∥ B 2 , ∞ α ≍ sup t > 0 t − α / m K ( t , f ; L 2 ( X ) , H m ( X ) ) . (3) \lVert f\rVert_{B^\alpha_{2,\infty}}\asymp\sup_{t>0}t^{-\alpha/m}K(t,f;L_2(X),H^m(X)). \tag*{(3)} ∥ f ∥ B 2 , ∞ α ≍ t > 0 sup t − α / m K ( t , f ; L 2 ( X ) , H m ( X )) . (3) The real-interpolation identity in (3) and the independence, up to equivalence of norms, of the choice of m > α m>\alpha m > α [5 Chapter 3] and [22 Chapter 7] .
We also recall the chartwise definition of the classical Hölder spaces. Fix a finite smooth atlas { ( U ν , ϕ ν ) } ν = 1 J \{(U_\nu,\phi_\nu)\}_{\nu=1}^J {( U ν , ϕ ν ) } ν = 1 J { χ ν } ν = 1 J \{\chi_\nu\}_{\nu=1}^J { χ ν } ν = 1 J supp χ ν ⋐ U ν \operatorname{supp}\chi_\nu\Subset U_\nu supp χ ν ⋐ U ν k ∈ N 0 k\in\mathbb{N}_0 k ∈ N 0 0 < β ≤ 1 0<\beta\leq1 0 < β ≤ 1
∥ f ∥ C k , β ( X ) : = ∑ ν = 1 J ∥ ( χ ν f ) ∘ ϕ ν − 1 ∥ C k , β ( R ϱ ) . \lVert f\rVert_{C^{k,\beta}(X)}:=\sum_{\nu=1}^{J}\lVert(\chi_\nu f)\circ\phi_\nu^{-1}\rVert_{C^{k,\beta}(\mathbb{R}^{\varrho})}. ∥ f ∥ C k , β ( X ) := ν = 1 ∑ J ∥( χ ν f ) ∘ ϕ ν − 1 ∥ C k , β ( R ϱ ) . where each localized function is extended by zero from ϕ ν ( U ν ) \phi_\nu(U_\nu) ϕ ν ( U ν ) R ϱ \mathbb{R}^{\varrho} R ϱ
∥ u ∥ C k , β ( R ϱ ) : = ∑ ∣ a ∣ ≤ k ∥ D a u ∥ ∞ + ∑ ∣ a ∣ = k sup z ≠ z ′ ∣ D a u ( z ) − D a u ( z ′ ) ∣ ∣ z − z ′ ∣ β . \lVert u\rVert_{C^{k,\beta}(\mathbb{R}^{\varrho})}:=\sum_{\lvert a\rvert\leq k}\lVert D^a u\rVert_\infty+\sum_{\lvert a\rvert=k}\sup_{z\neq z'}\frac{\lvert D^a u(z)-D^a u(z')\rvert}{\lvert z-z'\rvert^\beta}. ∥ u ∥ C k , β ( R ϱ ) := ∣ a ∣ ≤ k ∑ ∥ D a u ∥ ∞ + ∣ a ∣ = k ∑ z = z ′ sup ∣ z − z ′ ∣ β ∣ D a u ( z ) − D a u ( z ′ )∣ . Thus C k , β ( X ) C^{k,\beta}(X) C k , β ( X )
There is also a chartwise difference characterization of the Besov space B ∞ , ∞ α B^\alpha_{\infty,\infty} B ∞ , ∞ α α > 0 \alpha>0 α > 0
k : = ⌈ α ⌉ − 1 , β : = α − k ∈ ( 0 , 1 ] , k:=\lceil\alpha\rceil-1,\qquad\beta:=\alpha-k\in(0,1], k := ⌈ α ⌉ − 1 , β := α − k ∈ ( 0 , 1 ] , and, for u ∈ C k ( R ϱ ) u\in C^k(\mathbb{R}^{\varrho}) u ∈ C k ( R ϱ )
∥ u ∥ B ∞ , ∞ α ( R ϱ ) : = ∑ ∣ a ∣ ≤ k ∥ D a u ∥ ∞ + ∑ ∣ a ∣ = k sup h ≠ 0 ∣ h ∣ − β ∥ Δ h 2 D a u ∥ ∞ , \lVert u\rVert_{B^\alpha_{\infty,\infty}(\mathbb{R}^{\varrho})}:=\sum_{\lvert a\rvert\leq k}\lVert D^a u\rVert_\infty+\sum_{\lvert a\rvert=k}\sup_{h\neq0}\lvert h\rvert^{-\beta}\lVert\Delta_h^2D^a u\rVert_\infty, ∥ u ∥ B ∞ , ∞ α ( R ϱ ) := ∣ a ∣ ≤ k ∑ ∥ D a u ∥ ∞ + ∣ a ∣ = k ∑ h = 0 sup ∣ h ∣ − β ∥ Δ h 2 D a u ∥ ∞ , Δ h 2 u ( z ) : = u ( z + 2 h ) − 2 u ( z + h ) + u ( z ) . \Delta_h^2u(z):=u(z+2h)-2u(z+h)+u(z). Δ h 2 u ( z ) := u ( z + 2 h ) − 2 u ( z + h ) + u ( z ) . Then, using the same atlas and partition of unity, define
∥ f ∥ B ∞ , ∞ α ( X ) : = ∑ ν = 1 J ∥ ( χ ν f ) ∘ ϕ ν − 1 ∥ B ∞ , ∞ α ( R ϱ ) . \lVert f\rVert_{B^\alpha_{\infty,\infty}(X)}:=\sum_{\nu=1}^{J}\lVert(\chi_\nu f)\circ\phi_\nu^{-1}\rVert_{B^\alpha_{\infty,\infty}(\mathbb{R}^{\varrho})}. ∥ f ∥ B ∞ , ∞ α ( X ) := ν = 1 ∑ J ∥( χ ν f ) ∘ ϕ ν − 1 ∥ B ∞ , ∞ α ( R ϱ ) . with zero extension. This defines B ∞ , ∞ α ( X ) B^\alpha_{\infty,\infty}(X) B ∞ , ∞ α ( X ) [22 Section 1.2.2, Definition 7.2.2, Theorem 7.2.3, and Theorem 7.3.1(ii)] . If α = k + β \alpha=k+\beta α = k + β 0 < β < 1 0<\beta<1 0 < β < 1 C k , β ( X ) C^{k,\beta}(X) C k , β ( X ) α = k + 1 \alpha=k+1 α = k + 1 B ∞ , ∞ k + 1 ( X ) B^{k+1}_{\infty,\infty}(X) B ∞ , ∞ k + 1 ( X ) C k , 1 ( X ) C^{k,1}(X) C k , 1 ( X )
Using B ∞ , ∞ α ( X ) B^\alpha_{\infty,\infty}(X) B ∞ , ∞ α ( X ) B 2 , ∞ α ( X ) B^\alpha_{2,\infty}(X) B 2 , ∞ α ( X ) C k , β ( X ) C^{k,\beta}(X) C k , β ( X )
Proposition 2.1 (Hölder–Besov embedding). Let k ∈ N 0 k\in\mathbb{N}_0 k ∈ N 0 β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ] α = k + β \alpha=k+\beta α = k + β
C k , β ( X ) ↪ B 2 , ∞ α ( X ) . C^{k,\beta}(X)\hookrightarrow B^\alpha_{2,\infty}(X). C k , β ( X ) ↪ B 2 , ∞ α ( X ) . More precisely, there is a constant C = C ( X , k , β ) C=C(X,k,\beta) C = C ( X , k , β )
∥ f ∥ B 2 , ∞ α ( X ) ≤ C ∥ f ∥ C k , β ( X ) for all f ∈ C k , β ( X ) . \lVert f\rVert_{B^\alpha_{2,\infty}(X)}\leq C\lVert f\rVert_{C^{k,\beta}(X)}\quad\text{for all }f\in C^{k,\beta}(X). ∥ f ∥ B 2 , ∞ α ( X ) ≤ C ∥ f ∥ C k , β ( X ) for all f ∈ C k , β ( X ) . Gaussian RKHSs
For a bandwidth γ > 0 \gamma>0 γ > 0 H γ ( X ) \mathcal{H}_\gamma(X) H γ ( X )
k γ ( x , y ) : = exp ( − ∥ x − y ∥ R d 2 γ 2 ) , x , y ∈ X . k_\gamma(x,y):=\exp\left(-\frac{\|x-y\|_{\mathbb{R}^d}^2}{\gamma^2}\right),\qquad x,y\in X. k γ ( x , y ) := exp ( − γ 2 ∥ x − y ∥ R d 2 ) , x , y ∈ X . H γ ( X ) \mathcal{H}_\gamma(X) H γ ( X ) k γ ( x , x ) = 1 k_\gamma(x,x)=1 k γ ( x , x ) = 1
∥ f ∥ ∞ ≤ ∥ f ∥ H γ ( X ) , f ∈ H γ ( X ) . \|f\|_\infty\le\|f\|_{\mathcal{H}_\gamma(X)},\qquad f\in\mathcal{H}_\gamma(X). ∥ f ∥ ∞ ≤ ∥ f ∥ H γ ( X ) , f ∈ H γ ( X ) . For a detailed analysis of H γ ( X ) \mathcal{H}_\gamma(X) H γ ( X ) [15 ] , Section 4.4. Its separability and the norm bound above verify the function-space assumptions used in the oracle inequality developed in § 3 below. For fixed n n n λ > 0 \lambda>0 λ > 0 γ > 0 \gamma>0 γ > 0 f ^ D , λ , γ \hat f_{D,\lambda,\gamma} f ^ D , λ , γ D D D
Complexity Measures of Function Classes
To describe the complexity of the function class, we introduce dyadic entropy numbers, covering numbers and empirical Rademacher complexity. For a bounded linear operator T : E → F T:E\to F T : E → F i i i
e i ( T ) : = inf { δ > 0 : T ( B E ) is covered by 2 i − 1 balls of radius δ in F } . e_i(T):=\inf\{\delta>0:T(B_E)\text{ is covered by }2^{i-1}\text{ balls of radius }\delta\text{ in }F\}. e i ( T ) := inf { δ > 0 : T ( B E ) is covered by 2 i − 1 balls of radius δ in F } . Here B E B_E B E E E E m a t h c a l Q ⊂ F mathcal{Q}\subset F ma t h c a l Q ⊂ F
e i ( Q , F ) : = inf { δ > 0 : Q is covered by 2 i − 1 balls of radius δ in F } . e_i(\mathcal{Q},F):=\inf\{\delta>0:\mathcal{Q}\text{ is covered by }2^{i-1}\text{ balls of radius }\delta\text{ in }F\}. e i ( Q , F ) := inf { δ > 0 : Q is covered by 2 i − 1 balls of radius δ in F } . For an arbitrary subset Q ⊂ F \mathcal{Q}\subset F Q ⊂ F
N ( δ , Q , ∥ ⋅ ∥ F ) : = min { n ≥ 1 : ∃ q 1 , … , q n ∈ F such that Q ⊂ ⋃ i = 1 n B ( q i , δ ) } . N(\delta,\mathcal{Q},\|\cdot\|_F):=\min\left\{n\ge1:\exists q_1,\ldots,q_n\in F\text{ such that }\mathcal{Q}\subset\bigcup_{i=1}^{n}B(q_i,\delta)\right\}. N ( δ , Q , ∥ ⋅ ∥ F ) := min { n ≥ 1 : ∃ q 1 , … , q n ∈ F such that Q ⊂ i = 1 ⋃ n B ( q i , δ ) } . For a class Q \mathcal{Q} Q X × Y X\times Y X × Y D D D
Rad D ( Q ) : = E σ sup q ∈ Q ∣ 1 n ∑ i = 1 n σ i q ( X i , Y i ) ∣ . \operatorname{Rad}_D(\mathcal{Q}):=\mathbb{E}_{\sigma}\sup_{q\in\mathcal{Q}}\left|\frac{1}{n}\sum_{i=1}^{n}\sigma_iq(X_i,Y_i)\right|. Rad D ( Q ) := E σ q ∈ Q sup n 1 i = 1 ∑ n σ i q ( X i , Y i ) . where σ 1 , … , σ n \sigma_1,\ldots,\sigma_n σ 1 , … , σ n − 1 -1 − 1 1 1 1 D D D
Our oracle inequality imposes a polynomial decay expected empirical dyadic entropy condition on the hypothesis class F \mathcal{F} F γ > 0 \gamma> 0 γ > 0 H γ ( X ) \mathcal{H}_{\gamma}(X) H γ ( X )
An Oracle Inequality for Logistic Loss with Potentially Unbounded Bayes Functions
To derive an oracle inequality for regularized empirical risk minimization, typical arguments combine a Bernstein-type variance condition with a capacity assumption for the hypothesis class and concentration inequalities such as Talagrand’s inequality. The variance condition controls the second moment of the excess loss in terms of the excess risk. For logistic loss, obtaining such a condition with a useful constant is nontrivial. The results in [9 Lemma 8] and [1 Proposition 8.1] yield variance bounds with constants that grow exponentially with the uniform bound ∥ f ∥ ∞ \|f\|_{\infty} ∥ f ∥ ∞ ∥ f ∥ ∞ \|f\|_{\infty} ∥ f ∥ ∞ f ∗ ( x ) → − ∞ f^{*}(x) \to-\infty f ∗ ( x ) → − ∞ η ( x ) → 0 \eta(x) \to0 η ( x ) → 0 f ∗ ( x ) → + ∞ f^{*}(x) \to+\infty f ∗ ( x ) → + ∞ η ( x ) → 1 \eta(x) \to1 η ( x ) → 1
The following lemma gives a sharp Bernstein-type bound with only linear dependence on ∥ f ∥ ∞ \|f\|_{\infty} ∥ f ∥ ∞ η \eta η
Lemma 3.1 (Bernstein-type bound for logistic loss). For every bounded measurable f : X → R f : X \to\mathbb{R} f : X → R
E P ( ϕ ( Y f ( X ) ) − ψ ( X , Y ) ) 2 ≤ ( ∥ f ∥ ∞ + 2 ) ( R ( f ) − R ∗ ) . \mathbb{E}_{P}\left(\phi(Yf(X))-\psi(X,Y)\right)^{2} \leq\left(\|f\|_{\infty}+2\right)\left(\mathcal{R}(f)-\mathcal{R}^{*}\right). E P ( ϕ ( Y f ( X )) − ψ ( X , Y ) ) 2 ≤ ( ∥ f ∥ ∞ + 2 ) ( R ( f ) − R ∗ ) . We now state an oracle inequality for regularized empirical risk minimization over a separable normed function space. Using the Bernstein-type bound in Lemma 3.1, we do not require the conditional probability η \eta η D = ( ( X 1 , Y 1 ) , … , ( X n , Y n ) ) D=((X_{1},Y_{1}),\ldots,(X_{n},Y_{n})) D = (( X 1 , Y 1 ) , … , ( X n , Y n )) L 2 ( D ) L_{2}(D) L 2 ( D )
∥ g ∥ L 2 ( D ) 2 : = 1 n ∑ i = 1 n ∣ g ( X i , Y i ) ∣ 2 , g : X × Y → R . \|g\|_{L_{2}(D)}^{2} := \frac{1}{n}\sum_{i=1}^{n}|g(X_{i},Y_{i})|^{2},\qquad g:X\times Y\to\mathbb{R}. ∥ g ∥ L 2 ( D ) 2 := n 1 i = 1 ∑ n ∣ g ( X i , Y i ) ∣ 2 , g : X × Y → R . Similarly, for D X = ( X 1 , … , X n ) D_{X}=(X_{1},\ldots,X_{n}) D X = ( X 1 , … , X n ) L 2 ( D X ) L_{2}(D_{X}) L 2 ( D X )
∥ f ∥ L 2 ( D X ) 2 : = 1 n ∑ i = 1 n ∣ f ( X i ) ∣ 2 , f : X → R . \|f\|_{L_{2}(D_{X})}^{2} := \frac{1}{n}\sum_{i=1}^{n}|f(X_{i})|^{2},\qquad f:X\to\mathbb{R}. ∥ f ∥ L 2 ( D X ) 2 := n 1 i = 1 ∑ n ∣ f ( X i ) ∣ 2 , f : X → R . Theorem 3.2 (Oracle inequality for logistic loss). Let F \mathcal{F} F be a separable normed linear space of bounded measurable functions f : X → R f:X\to\mathbb{R} f : X → R such that
∥ f ∥ ∞ ≤ ∥ f ∥ F , f ∈ F . \|f\|_{\infty}\leq\|f\|_{\mathcal{F}},\qquad f\in\mathcal{F}. ∥ f ∥ ∞ ≤ ∥ f ∥ F , f ∈ F . For every n ≥ 1 n\geq1 n ≥ 1 and 0 < λ ≤ 1 0<\lambda\leq1 0 < λ ≤ 1 assume that the regularized empirical risk minimization problem (1) admits a minimizer for every sample D D D and fix a choice f ^ D , λ ∈ F \widehat{f}_{D,\lambda}\in\mathcal{F} f D , λ ∈ F that is measurable as a function of D D D Define the approximation error by
a F ( λ ) : = inf f ∈ F { λ ∥ f ∥ F 2 + R ( f ) − R ∗ } . (4) a_{\mathcal{F}}(\lambda):=\inf_{f\in\mathcal{F}}\left\{\lambda\|f\|_{\mathcal{F}}^{2}+\mathcal{R}(f)-\mathcal{R}^{*}\right\}. \tag*{(4)} a F ( λ ) := f ∈ F inf { λ ∥ f ∥ F 2 + R ( f ) − R ∗ } . (4) Furthermore, suppose that, for some p ∈ ( 0 , 1 / 2 ] p\in(0,1/2] p ∈ ( 0 , 1/2 ] and A ≥ 1 A\geq1 A ≥ 1 for every n ≥ 1 n\geq1 n ≥ 1
E D X ∼ P X n e i ( id : F → L 2 ( D X ) ) ≤ A 1 / ( 2 p ) i − 1 / ( 2 p ) , i ≥ 1. (5) \mathbb{E}_{D_{X}\sim P_{X}^{n}}e_{i}\left(\operatorname{id}:\mathcal{F}\to L_{2}(D_{X})\right)\leq A^{1/(2p)}i^{-1/(2p)},\qquad i\geq1. \tag*{(5)} E D X ∼ P X n e i ( id : F → L 2 ( D X ) ) ≤ A 1/ ( 2 p ) i − 1/ ( 2 p ) , i ≥ 1. (5) Then there is a numerical constant C ≥ 1 C\geq1 C ≥ 1 uniform over p ∈ ( 0 , 1 / 2 ] p\in(0,1/2] p ∈ ( 0 , 1/2 ] such that, for every n ≥ 1 n\geq1 n ≥ 1 0 < λ ≤ 1 0<\lambda\leq1 0 < λ ≤ 1 and t ≥ 1 t\geq1 t ≥ 1 with probability at least 1 − e − t 1-e^{-t} 1 − e − t
R ( f ^ D , λ ) − R ∗ ≤ C [ a F ( λ ) + λ + λ − 1 ( A n ) 2 / ( 1 + p ) + λ − 1 t 2 n 2 ] . (6) \mathcal{R}(\widehat{f}_{D,\lambda})-\mathcal{R}^{*}\leq C\left[a_{\mathcal{F}}(\lambda)+\lambda+\lambda^{-1}\left(\frac{A}{n}\right)^{2/(1+p)}+\lambda^{-1}\frac{t^{2}}{n^{2}}\right]. \tag*{(6)} R ( f D , λ ) − R ∗ ≤ C [ a F ( λ ) + λ + λ − 1 ( n A ) 2/ ( 1 + p ) + λ − 1 n 2 t 2 ] . (6) The entropy assumption in Theorem 3.2 requires control of every entropy number. In our manifold application, the available covering estimate holds only above a positive radius, as stated in Proposition 4.6 . The following corollary considers this restriction by requiring the covering estimate only for b ≤ δ ≤ 1 b \le\delta\le1 b ≤ δ ≤ 1
Corollary 3.3 (Oracle inequality under a truncated entropy condition). Suppose that the assumptions of Theorem 3.2 hold with the entropy condition (5) replaced by the following covering number condition: for some p ∈ ( 0 , 1 / 2 ] p \in(0,1/2] p ∈ ( 0 , 1/2 ] A ≥ 1 A \ge1 A ≥ 1 b ∈ ( 0 , 1 / 4 ] b \in(0,1/4] b ∈ ( 0 , 1/4 ]
log N ( δ , B F , ∥ ⋅ ∥ ∞ ) ≤ A δ − 2 p , b ≤ δ ≤ 1. (7) \log N(\delta, B_F, \lVert\cdot\rVert_{\infty}) \le A\delta^{-2p}, \qquad b \le\delta\le1. \tag*{(7)} log N ( δ , B F , ∥ ⋅ ∥ ∞ ) ≤ A δ − 2 p , b ≤ δ ≤ 1. (7) Then there is a numerical constant C ≥ 1 C \ge1 C ≥ 1 p p p A A A b b b n ≥ 1 n \ge1 n ≥ 1 0 < λ ≤ 1 0 < \lambda\le1 0 < λ ≤ 1 t ≥ 1 t \ge1 t ≥ 1 1 − e − t 1-e^{-t} 1 − e − t
R ( f ^ D , λ ) − R ∗ ≤ C [ a F ( λ ) + λ + λ − 1 ( A n ) 2 / ( 1 + p ) + b 2 λ + λ − 1 t 2 n 2 ] . (8) \mathcal{R}(\widehat{f}_{D,\lambda})-\mathcal{R}^{*} \le C\left[a_F(\lambda)+\lambda+\lambda^{-1}\left(\frac{A}{n}\right)^{2/(1+p)}+\frac{b^2}{\lambda}+\lambda^{-1}\frac{t^2}{n^2}\right]. \tag*{(8)} R ( f D , λ ) − R ∗ ≤ C [ a F ( λ ) + λ + λ − 1 ( n A ) 2/ ( 1 + p ) + λ b 2 + λ − 1 n 2 t 2 ] . (8) Remark 3.1 (Regularization dependence). The factor λ − 1 \lambda^{-1} λ − 1 (6) comes from the dependence of both the localized envelope and the variance bound on the predictor norm. In the proof of Theorem 3.2 , functions in a localized class at level ϵ \epsilon ϵ C ( ϵ / λ ) 1 / 2 C(\epsilon/\lambda)^{1/2} C ( ϵ / λ ) 1/2 Lemma 3.1 then gives the second-moment bound C ϵ 3 / 2 λ − 1 / 2 C\epsilon^{3/2}\lambda^{-1/2} C ϵ 3/2 λ − 1/2 C λ − 1 ( A / n ) 2 / ( 1 + p ) C\lambda^{-1}(A/n)^{2/(1+p)} C λ − 1 ( A / n ) 2/ ( 1 + p )
In the squared-loss settings of [10 , 13 ] , fixed-level clipping gives a bounded loss class and a Bernstein constant independent of λ \lambda λ ϵ \epsilon ϵ C λ − p A / n C\lambda^{-p}A/n C λ − p A / n
This difference in the dependence on λ \lambda λ
Gaussian Approximation and Learning Rates on Manifolds
We now combine the oracle inequality with Gaussian approximation bounds to derive learning rates on the manifold X X X X X X § 2.2 . We construct Gaussian RKHS approximants that fully exploit the Besov smoothness α \alpha α ϱ \varrho ϱ
Gaussian Approximation on Besov Spaces
Define the Gaussian integral operator
T γ f ( x ) : = ( 1 γ π ) ϱ ∫ X exp ( − ∥ x − y ∥ R d 2 γ 2 ) f ( y ) d V ( y ) . T_{\gamma}f(x):=\left(\frac{1}{\gamma\sqrt{\pi}}\right)^{\varrho}\int_X \exp\left(-\frac{\lVert x-y\rVert_{\mathbb{R}^{d}}^2}{\gamma^2}\right)f(y)\,dV(y). T γ f ( x ) := ( γ π 1 ) ϱ ∫ X exp ( − γ 2 ∥ x − y ∥ R d 2 ) f ( y ) d V ( y ) . Results in [21 Lemma 4.1 and Proposition 4.2] use a high-order correction scheme to establish a one-bandwidth expansion in the C k , β C^{k,\beta} C k , β j γ j\gamma j γ
Given α > 0 \alpha> 0 α > 0
s : = ⌈ α ⌉ + 1 , c j : = ( − 1 ) j + 1 ( s j ) , 1 ≤ j ≤ s . s:=\lceil\alpha\rceil+1,\qquad c_j:=(-1)^{j+1}\binom{s}{j},\qquad1\le j\le s. s := ⌈ α ⌉ + 1 , c j := ( − 1 ) j + 1 ( j s ) , 1 ≤ j ≤ s . and define the multiscale approximation operator
S γ , s f : = ∑ j = 1 s c j T j γ f . (9) S_{\gamma,s}f:=\sum_{j=1}^{s}c_jT_{j\gamma}f. \tag*{(9)} S γ , s f := j = 1 ∑ s c j T j γ f . (9) The coefficients satisfy the finite-difference identities
∑ j = 1 s c j = 1 , ∑ j = 1 s c j j ℓ = 0 , 1 ≤ ℓ < s . (10) \sum_{j=1}^{s} c_j = 1,\qquad\sum_{j=1}^{s} c_j j^\ell= 0,\qquad1 \le\ell< s. \tag*{(10)} j = 1 ∑ s c j = 1 , j = 1 ∑ s c j j ℓ = 0 , 1 ≤ ℓ < s . (10) The following theorem bounds the RKHS norm of S γ , s f S_{\gamma,s}f S γ , s f
Theorem 4.1 (RKHS norm bound). For every f ∈ L 2 ( X ) f \in L_2(X) f ∈ L 2 ( X ) and γ > 0 \gamma> 0 γ > 0
∥ S γ , s f ∥ H γ ( X ) ≤ C α , X , d γ − ϱ / 2 ∥ f ∥ L 2 ( X ) . \left\|S_{\gamma,s}f\right\|_{H_\gamma(X)} \le C_{\alpha,X,d}\gamma^{-\varrho/2}\left\|f\right\|_{L_2(X)}. ∥ S γ , s f ∥ H γ ( X ) ≤ C α , X , d γ − ϱ /2 ∥ f ∥ L 2 ( X ) . We next establish an operator expansion in which all operator coefficients are independent of the bandwidth. This result is a Sobolev counterpart of [21 Lemma 4.1] . They establish a uniform expansion for functions in C k , β ( X ) C^{k,\beta}(X) C k , β ( X ) L 2 ( X ) L_2(X) L 2 ( X ) γ 2 N + 2 \gamma^{2N+2} γ 2 N + 2 ∥ f ∥ H 2 N + 2 ( X ) \left\|f\right\|_{H^{2N+2}(X)} ∥ f ∥ H 2 N + 2 ( X )
Lemma 4.2 (Uniform Sobolev expansion). Let Diff m ( X ) \operatorname{Diff}^{m}(X) Diff m ( X ) denote the space of linear differential operators on X X X of order at most m m m with smooth coefficients. Then, there exist differential operators A r A_r A r r ≥ 0 r \ge0 r ≥ 0 depending only on X X X such that A 0 = I A_0 = I A 0 = I A r ∈ Diff 2 r ( X ) A_r \in\operatorname{Diff}^{2r}(X) A r ∈ Diff 2 r ( X ) and, for every N ∈ N 0 N \in\mathbb{N}_0 N ∈ N 0 there exists a constant C N , X , d > 0 C_{N,X,d} > 0 C N , X , d > 0 satisfying
∥ T γ f − ∑ r = 0 N γ 2 r A r f ∥ L 2 ( X ) ≤ C N , X , d γ 2 N + 2 ∥ f ∥ H 2 N + 2 ( X ) (11) \left\|T_\gamma f-\sum_{r=0}^{N}\gamma^{2r}A_r f\right\|_{L_2(X)}
\le C_{N,X,d}\gamma^{2N+2}\left\|f\right\|_{H^{2N+2}(X)} \tag*{(11)} T γ f − r = 0 ∑ N γ 2 r A r f L 2 ( X ) ≤ C N , X , d γ 2 N + 2 ∥ f ∥ H 2 N + 2 ( X ) (11) for all 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 and f ∈ H 2 N + 2 ( X ) f \in H^{2N+2}(X) f ∈ H 2 N + 2 ( X ) Moreover,
A r = 1 4 r r ! Δ X r + B r , B r ∈ Diff 2 r − 2 ( X ) , r ≥ 1 , A_r=\frac{1}{4^r r!}\Delta_X^r+B_r,\qquad B_r\in\operatorname{Diff}^{2r-2}(X),\qquad r\ge1, A r = 4 r r ! 1 Δ X r + B r , B r ∈ Diff 2 r − 2 ( X ) , r ≥ 1 , where Δ X = div ∇ \Delta_X=\operatorname{div}\nabla Δ X = div ∇
The identities (10) cancel the lower-order terms in this expansion when the operators are combined in S γ , s S_{\gamma,s} S γ , s L 2 ( X ) L_2(X) L 2 ( X )
Theorem 4.3 (Besov approximation). Let α > 0 \alpha> 0 α > 0 and let S γ , s S_{\gamma,s} S γ , s be defined by (9) , with s = ⌊ α ⌋ + 1 s=\lfloor\alpha\rfloor+1 s = ⌊ α ⌋ + 1 Then there is a constant C α > 0 C_\alpha>0 C α > 0 independent of γ \gamma γ and f f f such that, for every f ∈ B 2 , ∞ α ( X ) f\in B^\alpha_{2,\infty}(X) f ∈ B 2 , ∞ α ( X )
∥ S γ , s f − f ∥ L 2 ( X ) ≤ C α γ α ∥ f ∥ B 2 , ∞ α ( X ) , 0 < γ ≤ 1. (12) \left\|S_{\gamma,s}f-f\right\|_{L_2(X)}
\le C_\alpha\gamma^\alpha\left\|f\right\|_{B^\alpha_{2,\infty}(X)},\qquad0<\gamma\le1. \tag*{(12)} ∥ S γ , s f − f ∥ L 2 ( X ) ≤ C α γ α ∥ f ∥ B 2 , ∞ α ( X ) , 0 < γ ≤ 1. (12) Recall the approximation error defined in (4) . For the bandwidth-dependent Gaussian RKHS H γ ( X ) H_\gamma(X) H γ ( X )
a γ ( λ ) : = inf f ∈ H γ ( X ) { λ ∥ f ∥ H γ ( X ) 2 + R ( f ) − R ∗ } . (13) a_\gamma(\lambda):=\inf_{f\in H_\gamma(X)}
\left\{\lambda\left\|f\right\|_{H_\gamma(X)}^2+\mathcal{R}(f)-\mathcal{R}^*\right\}. \tag*{(13)} a γ ( λ ) := f ∈ H γ ( X ) inf { λ ∥ f ∥ H γ ( X ) 2 + R ( f ) − R ∗ } . (13) Theorem 4.4 (Approximation error). Suppose that 0 < η < 1 0<\eta<1 0 < η < 1 holds P X P_X P X almost surely and the Bayes decision function
f ∗ = log η 1 − η f^*=\log\frac{\eta}{1-\eta} f ∗ = log 1 − η η has a measurable extension in B 2 , ∞ α ( X ) B^\alpha_{2,\infty}(X) B 2 , ∞ α ( X ) for some α > 0 \alpha>0 α > 0 The extension is again denoted by f ∗ f^* f ∗ Suppose also that P X P_X P X has a density g ∈ L p ( X ) g\in L_p(X) g ∈ L p ( X ) with respect to d V dV d V for a fixed 2 ≤ p ≤ ∞ 2\le p\le\infty 2 ≤ p ≤ ∞ Then, for every λ > 0 \lambda>0 λ > 0 and 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1
a γ ( λ ) ≤ C α , p , X , d γ 2 α ( 1 − 1 / p ) ∥ g ∥ L p ( X ) ∥ f ∗ ∥ B 2 , ∞ α ( X ) 2 ( 1 − 1 / p ) + C α , X , d λ γ − ϱ ∥ f ∗ ∥ L 2 ( X ) 2 . (14) a_\gamma(\lambda)\le C_{\alpha,p,X,d}\gamma^{2\alpha(1-1/p)}
\lVert g\rVert_{L_p(X)}\lVert f^*\rVert_{B^\alpha_{2,\infty}(X)}^{2(1-1/p)}
+C_{\alpha,X,d}\lambda\gamma^{-\varrho}\lVert f^*\rVert_{L_2(X)}^2. \tag*{(14)} a γ ( λ ) ≤ C α , p , X , d γ 2 α ( 1 − 1/ p ) ∥ g ∥ L p ( X ) ∥ f ∗ ∥ B 2 , ∞ α ( X ) 2 ( 1 − 1/ p ) + C α , X , d λ γ − ϱ ∥ f ∗ ∥ L 2 ( X ) 2 . (14) The Besov assumption in Theorem 4.4 can be verified through regularity and endpoint conditions on η \eta η [6 Definition 3.1] controls the probability that a conditional class probability is close to zero. For binary classification, it controls both η \eta η η \eta η [25 Assumption 3.1] for kernel logistic regression. Unlike the usual Tsybakov noise condition, which concerns η \eta η 1 / 2 1/2 1/2 f ∗ f^* f ∗ f ∗ f^* f ∗ d V dV d V
Proposition 4.5 (Besov regularity of the Bayes function). Let α > 0 \alpha> 0 α > 0 η : X → [ 0 , 1 ] \eta: X \to[0,1] η : X → [ 0 , 1 ] 0 < η < 1 0 < \eta< 1 0 < η < 1 d V dV d V f ∗ : = log ( η / ( 1 − η ) ) f^* := \log(\eta/(1-\eta)) f ∗ := log ( η / ( 1 − η )) B 2 , ∞ α ( X ) B^\alpha_{2,\infty}(X) B 2 , ∞ α ( X )
(i) Let 0 < α < 1 0 < \alpha< 1 0 < α < 1 α ≤ β ≤ 1 \alpha\le\beta\le1 α ≤ β ≤ 1 η ∈ C 0 , β ( X ) \eta\in C^{0,\beta}(X) η ∈ C 0 , β ( X )
∫ X [ η ( x ) ( 1 − η ( x ) ) ] − 2 α / β d V ( x ) < ∞ , (15) \int_X [\eta(x)(1-\eta(x))]^{-2\alpha/\beta}\,dV(x) < \infty, \tag*{(15)} ∫ X [ η ( x ) ( 1 − η ( x )) ] − 2 α / β d V ( x ) < ∞ , (15) then f ∗ ∈ B 2 , ∞ α ( X ) f^* \in B^\alpha_{2,\infty}(X) f ∗ ∈ B 2 , ∞ α ( X )
∥ f ∗ ∥ B 2 , ∞ α ( X ) ≤ C X , α , β ( 1 + ∥ η ∥ C 0 , β ( X ) α / β ) ( ∫ X [ η ( 1 − η ) ] − 2 α / β d V ) 1 / 2 . (16) \|f^*\|_{B^\alpha_{2,\infty}(X)} \le C_{X,\alpha,\beta}(1+\|\eta\|_{C^{0,\beta}(X)}^{\alpha/\beta})\left(\int_X [\eta(1-\eta)]^{-2\alpha/\beta}\,dV\right)^{1/2}. \tag*{(16)} ∥ f ∗ ∥ B 2 , ∞ α ( X ) ≤ C X , α , β ( 1 + ∥ η ∥ C 0 , β ( X ) α / β ) ( ∫ X [ η ( 1 − η ) ] − 2 α / β d V ) 1/2 . (16) (ii) Let m ≥ 2 m \ge2 m ≥ 2 α ≤ m \alpha\le m α ≤ m η ∈ C m ( X ) \eta\in C^m(X) η ∈ C m ( X )
∫ X [ η ( x ) ( 1 − η ( x ) ) ] − m d V ( x ) < ∞ , (17) \int_X [\eta(x)(1-\eta(x))]^{-m}\,dV(x) < \infty, \tag*{(17)} ∫ X [ η ( x ) ( 1 − η ( x )) ] − m d V ( x ) < ∞ , (17) then f ∗ ∈ H m ( X ) f^* \in H^m(X) f ∗ ∈ H m ( X )
∥ f ∗ ∥ H m ( X ) ≤ C ( ∫ X [ η ( 1 − η ) ] − m d V ) 1 / 2 , (18) \|f^*\|_{H^m(X)} \le C\left(\int_X [\eta(1-\eta)]^{-m}\,dV\right)^{1/2}, \tag*{(18)} ∥ f ∗ ∥ H m ( X ) ≤ C ( ∫ X [ η ( 1 − η ) ] − m d V ) 1/2 , (18) where C C C X X X m m m ∥ η ∥ C m ( X ) \|\eta\|_{C^m(X)} ∥ η ∥ C m ( X )
In particular, suppose that, for some C 0 > 0 C_0 > 0 C 0 > 0 κ > 0 \kappa> 0 κ > 0
V { x ∈ X : min { η ( x ) , 1 − η ( x ) } ≤ u } ≤ C 0 u κ , 0 < u ≤ 1 2 . (19) V\{x \in X : \min\{\eta(x),1-\eta(x)\} \le u\} \le C_0u^\kappa,\qquad0 < u \le\frac{1}{2}. \tag*{(19)} V { x ∈ X : min { η ( x ) , 1 − η ( x )} ≤ u } ≤ C 0 u κ , 0 < u ≤ 2 1 . (19) Then (15) follows when κ > 2 α / β \kappa> 2\alpha/\beta κ > 2 α / β (17) follows when κ > m \kappa> m κ > m
It is worth noting that the small value condition in [6 Definition 3.1] is imposed under P X P_X P X (19) . If one additionally assumes that the density g ≥ c > 0 g \ge c > 0 g ≥ c > 0 P X P_X P X (19) .
Learning Rates
We now combine the Gaussian approximation bounds with the oracle inequalities to derive learning rates on the manifold. The remaining ingredient is a covering estimate for the Gaussian RKHS whose dependence on the bandwidth is governed by the intrinsic dimension.
Proposition 4.6 (Gaussian covering numbers above a fixed scale). Fix an integer m ≥ 2 m \ge2 m ≥ 2 C m ≥ 1 C_m \ge1 C m ≥ 1 γ m ∈ ( 0 , 1 ) \gamma_m \in(0,1) γ m ∈ ( 0 , 1 ) m m m X X X γ m m − 1 < 1 / 4 \gamma_m^{m-1} < 1/4 γ m m − 1 < 1/4 0 < γ ≤ γ m 0 < \gamma\le\gamma_m 0 < γ ≤ γ m
log N ( δ , B H γ ( X ) , ∥ ⋅ ∥ ∞ ) ≤ C m γ − ϱ ( log 2 δ ) ϱ + 1 , γ m − 1 < δ ≤ 1. (20) \log N(\delta,B_{H_\gamma}(X),\|\cdot\|_\infty) \le C_m\gamma^{-\varrho}\left(\log\frac{2}{\delta}\right)^{\varrho+1},\qquad\gamma^{m-1}<\delta\le1. \tag*{(20)} log N ( δ , B H γ ( X ) , ∥ ⋅ ∥ ∞ ) ≤ C m γ − ϱ ( log δ 2 ) ϱ + 1 , γ m − 1 < δ ≤ 1. (20) This implies, uniformly for the entropy exponent q ∈ ( 0 , 1 / 2 ] q \in(0,1/2] q ∈ ( 0 , 1/2 ]
log N ( δ , B H γ ( X ) , ∥ ⋅ ∥ ∞ ) ≤ C m q − ( ϱ + 1 ) γ − ϱ δ − 2 q , γ m − 1 < δ ≤ 1. (21) \log N(\delta,B_{H_\gamma}(X),\|\cdot\|_\infty) \le C_mq^{-(\varrho+1)}\gamma^{-\varrho}\delta^{-2q},\qquad\gamma^{m-1}<\delta\le1. \tag*{(21)} log N ( δ , B H γ ( X ) , ∥ ⋅ ∥ ∞ ) ≤ C m q − ( ϱ + 1 ) γ − ϱ δ − 2 q , γ m − 1 < δ ≤ 1. (21) The proof of Proposition 4.6 is based on [28 Lemma 5.4] at the fixed smoothness order m m m [10 Theorem A.10] also uses [28 Lemma 5.4] . Here we retain the strict lower limit δ > γ m − 1 \delta> \gamma^{m-1} δ > γ m − 1 λ − 1 γ 2 ( m − 1 ) \lambda^{-1}\gamma^{2(m-1)} λ − 1 γ 2 ( m − 1 ) m m m
Theorem 4.7 (Learning rate). Under the assumptions of Theorem 4.4 , write f ^ n , λ , γ \widehat{f}_{n,\lambda,\gamma} f n , λ , γ for the regularized empirical minimizer over H γ ( X ) \mathcal{H}_{\gamma}(X) H γ ( X ) Set β : = 2 α ( 1 − 1 / p ) \beta:= 2\alpha(1-1/p) β := 2 α ( 1 − 1/ p ) and define
γ n : = ( ( log n ) ϱ + 1 n ) 2 2 β + 3 ϱ , λ n : = ( ( log n ) ϱ + 1 n ) 2 ( β + ϱ ) 2 β + 3 ϱ . \gamma_n := \left(\frac{(\log n)^{\varrho+1}}{n}\right)^{\frac{2}{2\beta+3\varrho}}, \qquad\lambda_n := \left(\frac{(\log n)^{\varrho+1}}{n}\right)^{\frac{2(\beta+\varrho)}{2\beta+3\varrho}}. γ n := ( n ( log n ) ϱ + 1 ) 2 β + 3 ϱ 2 , λ n := ( n ( log n ) ϱ + 1 ) 2 β + 3 ϱ 2 ( β + ϱ ) . For every fixed t ≥ 1 t \ge1 t ≥ 1 and all sufficiently large n n n with probability at least 1 − e − t 1-e^{-t} 1 − e − t
R ( f ^ n , λ n , γ n ) − R ∗ ≤ C ( ( log n ) ϱ + 1 n ) 4 α ( 1 − 1 / p ) 4 α ( 1 − 1 / p ) + 3 ϱ . (22) \mathcal{R}(\widehat{f}_{n,\lambda_n,\gamma_n})-\mathcal{R}^{*}\le C\left(\frac{(\log n)^{\varrho+1}}{n}\right)^{\frac{4\alpha(1-1/p)}{4\alpha(1-1/p)+3\varrho}}. \tag*{(22)} R ( f n , λ n , γ n ) − R ∗ ≤ C ( n ( log n ) ϱ + 1 ) 4 α ( 1 − 1/ p ) + 3 ϱ 4 α ( 1 − 1/ p ) . (22) Here C C C may depend on t , α , p , X , ∥ g ∥ L p ( X ) t,\alpha,p,X,\lVert g\rVert_{L_p(X)} t , α , p , X , ∥ g ∥ L p ( X ) and ∥ f ∗ ∥ B 2 , ∞ α ( X ) \lVert f^{*}\rVert_{B^{\alpha}_{2,\infty}(X)} ∥ f ∗ ∥ B 2 , ∞ α ( X ) but is independent of n n n
Remark 4.1 (From logistic risk to misclassification risk). Recall the calibration inequality (2) . This calibration inequality can be improved when the distribution P P P satisfies the Tsybakov noise condition [24 ] . Specifically, assume that there exist 0 ≤ q < ∞ 0\le q<\infty 0 ≤ q < ∞ and C q > 0 C_q>0 C q > 0 such that
P X { x ∈ X : ∣ 2 η ( x ) − 1 ∣ ≤ u } ≤ C q u q , u > 0. P_X\{x\in X:|2\eta(x)-1|\le u\}\le C_q u^q,\qquad u>0. P X { x ∈ X : ∣2 η ( x ) − 1∣ ≤ u } ≤ C q u q , u > 0. For q = ∞ q=\infty q = ∞ we instead assume that there exists u 0 > 0 u_0>0 u 0 > 0 such that P X { x ∈ X : ∣ 2 η ( x ) − 1 ∣ ≤ u 0 } = 0 P_X\{x\in X:|2\eta(x)-1|\le u_0\}=0 P X { x ∈ X : ∣2 η ( x ) − 1∣ ≤ u 0 } = 0 Then, by [26 (2.4)] , the excess misclassification risk satisfies
R 01 ( f ) − R 01 ∗ ≤ C ( R ( f ) − R ∗ ) ( q + 1 ) / ( q + 2 ) (23) \mathcal{R}_{01}(f)-\mathcal{R}_{01}^{*}\le C\left(\mathcal{R}(f)-\mathcal{R}^{*}\right)^{(q+1)/(q+2)} \tag*{(23)} R 01 ( f ) − R 01 ∗ ≤ C ( R ( f ) − R ∗ ) ( q + 1 ) / ( q + 2 ) (23) for every measurable f : X → R f:X\to\mathbb{R} f : X → R For finite q q q the constant C C C depends only on q q q and C q C_q C q For q = ∞ q=\infty q = ∞ the exponent ( q + 1 ) / ( q + 2 ) (q+1)/(q+2) ( q + 1 ) / ( q + 2 ) is interpreted as 1 1 1 and C C C depends on u 0 u_0 u 0
Under the assumptions and with the parameter choices of Theorem 4.7 , if the above noise condition holds, then, for every fixed t ≥ 1 t\ge1 t ≥ 1 n n n (23) gives, with probability at least 1 − e − t 1-e^{-t} 1 − e − t
R 01 ( f ^ n , λ n , γ n ) − R 01 ∗ ≤ C ( ( log n ) ϱ + 1 n ) 4 α ( 1 − 1 / p ) ( q + 1 ) ( 4 α ( 1 − 1 / p ) + 3 ϱ ) ( q + 2 ) . \mathcal{R}_{01}(\widehat{f}_{n,\lambda_n,\gamma_n})-\mathcal{R}_{01}^{*}\le C\left(\frac{(\log n)^{\varrho+1}}{n}\right)^{\frac{4\alpha(1-1/p)(q+1)}{(4\alpha(1-1/p)+3\varrho)(q+2)}}. R 01 ( f n , λ n , γ n ) − R 01 ∗ ≤ C ( n ( log n ) ϱ + 1 ) ( 4 α ( 1 − 1/ p ) + 3 ϱ ) ( q + 2 ) 4 α ( 1 − 1/ p ) ( q + 1 ) . Remark 4.2 (Intrinsic norm control and comparison with squared-loss regression). Throughout this comparison, we suppress logarithmic factors, write β : = 2 α ( 1 − 1 / p ) \beta:=2\alpha(1-1/p) β := 2 α ( 1 − 1/ p ) and use q q q for the entropy exponent. As we have mentioned in Remark 3.1, in the bounded squared-loss settings of [10 , 13 ] , fixed-level clipping gives an envelope and a Bernstein constant independent of λ \lambda λ At localized risk level ε \varepsilon ε the second moment is of order ε \varepsilon ε and the leading Rademacher term has the form
( ε λ ) q / 2 ε ( 1 − q ) / 2 ( A n ) 1 / 2 = ε 1 / 2 λ − q / 2 ( A n ) 1 / 2 . \left(\frac{\varepsilon}{\lambda}\right)^{q/2}\varepsilon^{(1-q)/2}\left(\frac{A}{n}\right)^{1/2}
=\varepsilon^{1/2}\lambda^{-q/2}\left(\frac{A}{n}\right)^{1/2}. ( λ ε ) q /2 ε ( 1 − q ) /2 ( n A ) 1/2 = ε 1/2 λ − q /2 ( n A ) 1/2 . For logistic loss, the second-moment bound instead gives
( ε λ ) q / 2 ( ε 3 / 2 λ − 1 / 2 ) ( 1 − q ) / 2 ( A n ) 1 / 2 = ε ( 3 − q ) / 4 λ − ( 1 + q ) / 4 ( A n ) 1 / 2 . \left(\frac{\varepsilon}{\lambda}\right)^{q/2}\left(\varepsilon^{3/2}\lambda^{-1/2}\right)^{(1-q)/2}\left(\frac{A}{n}\right)^{1/2}
=\varepsilon^{(3-q)/4}\lambda^{-(1+q)/4}\left(\frac{A}{n}\right)^{1/2}. ( λ ε ) q /2 ( ε 3/2 λ − 1/2 ) ( 1 − q ) /2 ( n A ) 1/2 = ε ( 3 − q ) /4 λ − ( 1 + q ) /4 ( n A ) 1/2 . Requiring each term to be bounded by a sufficiently small ε \varepsilon ε gives ε ≥ C λ − q A / n \varepsilon\ge C\lambda^{-q}A/n ε ≥ C λ − q A / n for squared loss, and ε ≥ C λ − 1 ( A / n ) 2 / ( 1 + q ) \varepsilon\ge C\lambda^{-1}(A/n)^{2/(1+q)} ε ≥ C λ − 1 ( A / n ) 2/ ( 1 + q ) for logistic loss.
This distinction matters when the squared RKHS norm of an ambient-space Gaussian approximant is bounded by C γ − d C\gamma^{-d} C γ − d γ \gamma γ κ > 0 \kappa>0 κ > 0 n n n
λ n = n − κ , q n = 1 log n , \lambda_n=n^{-\kappa},\qquad q_n=\frac{1}{\log n}, λ n = n − κ , q n = log n 1 , λ n − q n = e κ , λ n − 1 = n κ . \lambda_n^{-q_n}=e^{\kappa},\qquad\lambda_n^{-1}=n^{\kappa}. λ n − q n = e κ , λ n − 1 = n κ . In the squared-loss bounds of [10 , 13 ] , the remaining dependence on q n q_n q n κ \kappa κ λ γ − d \lambda\gamma^{-d} λ γ − d d d d
bounds, balancing the squared-loss risk bias γ 2 α \gamma^{2\alpha} γ 2 α γ − ϱ / n \gamma^{-\varrho}/n γ − ϱ / n n − 2 α / ( 2 α + ϱ ) n^{-2\alpha/(2\alpha+\varrho)} n − 2 α / ( 2 α + ϱ ) [18 ] .
However, for logistic loss, Theorem 4.4 gives a risk bias of order γ β \gamma^\beta γ β λ − 1 γ − 2 ϱ / n 2 \lambda^{-1}\gamma^{-2\varrho}/n^2 λ − 1 γ − 2 ϱ / n 2 γ − d \gamma^{-d} γ − d Theorem 4.1 lead to the respective balances
inf λ > 0 { λ γ − d + λ − 1 γ − 2 ϱ n 2 } = 2 γ − ( d + 2 ϱ ) / 2 n , inf λ > 0 { λ γ − ϱ + λ − 1 γ − 2 ϱ n 2 } = 2 γ − 3 ϱ / 2 n . \inf_{\lambda>0}\left\{\lambda\gamma^{-d}+\lambda^{-1}\frac{\gamma^{-2\varrho}}{n^2}\right\}=\frac{2\gamma^{-(d+2\varrho)/2}}{n},
\qquad
\inf_{\lambda>0}\left\{\lambda\gamma^{-\varrho}+\lambda^{-1}\frac{\gamma^{-2\varrho}}{n^2}\right\}=\frac{2\gamma^{-3\varrho/2}}{n}. λ > 0 inf { λ γ − d + λ − 1 n 2 γ − 2 ϱ } = n 2 γ − ( d + 2 ϱ ) /2 , λ > 0 inf { λ γ − ϱ + λ − 1 n 2 γ − 2 ϱ } = n 2 γ − 3 ϱ /2 . Balancing each term with γ β \gamma^\beta γ β n − 2 β / ( 2 β + 2 ϱ + d ) n^{-2\beta/(2\beta+2\varrho+d)} n − 2 β / ( 2 β + 2 ϱ + d ) n − 2 β / ( 2 β + 3 ϱ ) n^{-2\beta/(2\beta+3\varrho)} n − 2 β / ( 2 β + 3 ϱ ) Theorem 4.7 . Thus the intrinsic norm bound removes the ambient dimension from the polynomial exponent. This comparison explains the role of the intrinsic RKHS norm bound within the present oracle analysis.
The resulting rate remains slower than the squared-loss regression rate n − 2 α / ( 2 α + ϱ ) n^{-2\alpha/(2\alpha+\varrho)} n − 2 α / ( 2 α + ϱ ) [10 ] , whose dependence on smoothness and dimension matches the minimax rate in [18 ] . Two differences in the analysis explain this gap. The first is, as discussed above, the norm-dependent variance bound in Lemma 3.1 . The second is the density-dependent risk bias in Theorem 4.4 , which is of order γ 2 α ( 1 − 1 / p ) \gamma^{2\alpha(1-1/p)} γ 2 α ( 1 − 1/ p ) g ∈ L p ( X ) g\in L_p(X) g ∈ L p ( X )
In view of Remark 4.2, we now seek to close the gap between the logistic learning rate and the squared-loss regression rate by clipping the predictions at a level that increases with the sample size. The idea of clipping is to control the supremum norm and the Bernstein constant through the clipping level M M M Theorem 4.8 , clipping only increases the logistic risk by at most e − M e^{-M} e − M n n n n − 2 α / ( 2 α + ϱ ) n^{-2\alpha/(2\alpha+\varrho)} n − 2 α / ( 2 α + ϱ )
Theorem 4.8 (Learning rates for clipped predictions). Under the assumptions of Theorem 4.4 , define the clipping operator
π M ( u ) = max { − M , min { u , M } } , M > 0. \pi_M(u)=\max\{-M,\min\{u,M\}\},\qquad M>0. π M ( u ) = max { − M , min { u , M }} , M > 0. Set β : = 2 α ( 1 − 1 / p ) \beta:=2\alpha(1-1/p) β := 2 α ( 1 − 1/ p )
γ n : = ( ( log n ) ϱ + 2 n ) 1 / ( β + ϱ ) , λ n : = ( log n ) ϱ + 2 n , M n : = 3 log n . \gamma_n:=\left(\frac{(\log n)^{\varrho+2}}{n}\right)^{1/(\beta+\varrho)},
\qquad
\lambda_n:=\frac{(\log n)^{\varrho+2}}{n},
\qquad
M_n:=3\log n. γ n := ( n ( log n ) ϱ + 2 ) 1/ ( β + ϱ ) , λ n := n ( log n ) ϱ + 2 , M n := 3 log n . For every fixed t ≥ 1 t\geq1 t ≥ 1 n n n 1 − e − t 1-e^{-t} 1 − e − t
R ( π M n f ^ n , λ n , γ n ) − R ∗ ≤ C ( ( log n ) ϱ + 2 n ) β / ( β + ϱ ) , (24) \mathcal{R}(\pi_{M_n}\widehat f_{n,\lambda_n,\gamma_n})-\mathcal{R}^*
\leq C\left(\frac{(\log n)^{\varrho+2}}{n}\right)^{\beta/(\beta+\varrho)}, \tag*{(24)} R ( π M n f n , λ n , γ n ) − R ∗ ≤ C ( n ( log n ) ϱ + 2 ) β / ( β + ϱ ) , (24) R 01 ( f ^ n , λ n , γ n ) − R 01 ∗ ≤ C ( ( log n ) ϱ + 2 n ) β / ( 2 ( β + ϱ ) ) . \mathcal{R}_{01}(\widehat f_{n,\lambda_n,\gamma_n})-\mathcal{R}_{01}^*
\leq C\left(\frac{(\log n)^{\varrho+2}}{n}\right)^{\beta/(2(\beta+\varrho))}. R 01 ( f n , λ n , γ n ) − R 01 ∗ ≤ C ( n ( log n ) ϱ + 2 ) β / ( 2 ( β + ϱ )) . Here C C C t , α , p , X , ∥ g ∥ L p ( X ) t,\alpha,p,X,\|g\|_{L_p(X)} t , α , p , X , ∥ g ∥ L p ( X ) ∥ f ∗ ∥ B 2 , ∞ α ( X ) \|f^*\|_{B^\alpha_{2,\infty}(X)} ∥ f ∗ ∥ B 2 , ∞ α ( X ) n n n
For p = ∞ p=\infty p = ∞ (24) has polynomial order n − α / ( 2 α + ϱ ) n^{-\alpha/(2\alpha+\varrho)} n − α / ( 2 α + ϱ ) α \alpha α d d d n − α / ( 2 α + d ) n^{-\alpha/(2\alpha+d)} n − α / ( 2 α + d ) [3 (1.5)] . Thus, up to logarithmic factors, our bound also matches the minimax optimal rate for binary classification, with the ambient dimension d d d ϱ \varrho ϱ
Conclusions
We have studied regularized Gaussian logistic classification on a compact smooth embedded manifold. The analysis combines a Bernstein-type bound with linear dependence on the prediction bound, an oracle inequality based on regularized-risk localization, and Gaussian approximation of intrinsic Besov functions. oracle analysis does not require class probabilities to be separated from zero and one. The signed multiscale Gaussian approximation construction cancels the geometric and differential contributions to the smoothing bias and achieves arbitrary positive approximation order while retaining the intrinsic-dimensional RKHS norm bound. A version of the oracle inequality based on covering estimates above a positive radius makes these approximation results compatible with the available manifold entropy bound. Under Besov regularity of the Bayes function f ∗ f^{*} f ∗ g ∈ L p ( X ) g \in L_{p}(X) g ∈ L p ( X ) 2 ≤ p ≤ ∞ 2 \le p \le\infty 2 ≤ p ≤ ∞ ( ( log n ) ϱ + 1 / n ) 4 α ( 1 − 1 / p ) / ( 4 α ( 1 − 1 / p ) + 3 ϱ ) ((\log n)^{\varrho+1}/n)^{4\alpha(1-1/p)/(4\alpha(1-1/p)+3\varrho)} (( log n ) ϱ + 1 / n ) 4 α ( 1 − 1/ p ) / ( 4 α ( 1 − 1/ p ) + 3 ϱ ) Theorem 4.7 . Its exponents depend on the intrinsic dimension ϱ \varrho ϱ α \alpha α p p p d d d Theorem 4.8 further improves the learning rate by clipping predictions. Under the same assumptions, the clipped logistic excess risk has rate ( ( log n ) ϱ + 2 / n ) 2 α ( 1 − 1 / p ) / ( 2 α ( 1 − 1 / p ) + ϱ ) ((\log n)^{\varrho+2}/n)^{2\alpha(1-1/p)/(2\alpha(1-1/p)+\varrho)} (( log n ) ϱ + 2 / n ) 2 α ( 1 − 1/ p ) / ( 2 α ( 1 − 1/ p ) + ϱ ) 2 α / ( 2 α + ϱ ) 2\alpha/(2\alpha+\varrho) 2 α / ( 2 α + ϱ ) n − α / ( 2 α + ϱ ) n^{-\alpha/(2\alpha+\varrho)} n − α / ( 2 α + ϱ )
Several questions remain open. First, the bandwidth and regularization choices depend on the smoothness, intrinsic dimension, and density integrability. A data-dependent selection rule that retains the same rate would connect the present analysis more closely with the adaptive procedures in [10 , 21 ] . Second, for 2 ≤ p < ∞ 2 \le p < \infty 2 ≤ p < ∞
Proofs
This appendix collects the proofs of the paper. Throughout the proofs, for a P P P g : X × Y → R g : X \times Y \to\mathbb{R} g : X × Y → R
E P g : = ∫ X × Y g ( x , y ) d P ( x , y ) , \mathbb{E}_{P}g := \int_{X \times Y} g(x,y)\,\mathrm{d}P(x,y), E P g := ∫ X × Y g ( x , y ) d P ( x , y ) , E D g : = 1 n ∑ i = 1 n g ( X i , Y i ) . \mathbb{E}_{D}g := \frac{1}{n}\sum_{i=1}^{n}g(X_i,Y_i). E D g := n 1 i = 1 ∑ n g ( X i , Y i ) . Thus E D \mathbb{E}_{D} E D E D ∼ P n \mathbb{E}_{D\sim P^{n}} E D ∼ P n
Proof of Proposition 2.1
If 0 < β < 1 0 < \beta< 1 0 < β < 1 [22 Theorem 1.2] , applied in a finite atlas after multiplication by a subordinate partition of unity whose supports are compactly contained in the corresponding charts, gives C k , β ( X ) = B ∞ , ∞ β ( X ) C^{k,\beta}(X)=B^{\beta}_{\infty,\infty}(X) C k , β ( X ) = B ∞ , ∞ β ( X ) β = 1 \beta=1 β = 1 C k , 1 ( X ) ↪ B ∞ , ∞ k ( X ) C^{k,1}(X)\hookrightarrow B^{k}_{\infty,\infty}(X) C k , 1 ( X ) ↪ B ∞ , ∞ k ( X )
It remains to pass from L ∞ L_{\infty} L ∞ L 2 L_{2} L 2 0 < r ≤ inj ( X ) 0<r\le\operatorname{inj}(X) 0 < r ≤ inj ( X ) ε > 0 \varepsilon>0 ε > 0 N ∈ N N\in\mathbb{N} N ∈ N N > max { α , ϱ + 6 } N>\max\{\alpha,\varrho+6\} N > max { α , ϱ + 6 } [22 Theorem 7.3.2] applies, with the same local means k 0 ( ε , f ) k_{0}(\varepsilon,f) k 0 ( ε , f ) k ( t , f ) k(t,f) k ( t , f ) ( p , q ) = ( ∞ , ∞ ) (p,q)=(\infty,\infty) ( p , q ) = ( ∞ , ∞ ) ( p , q ) = ( 2 , ∞ ) (p,q)=(2,\infty) ( p , q ) = ( 2 , ∞ )
∥ u ∥ L 2 ( X ) ≤ Vol ( X ) 1 / 2 ∥ u ∥ L ∞ ( X ) . \|u\|_{L_{2}(X)}\le\operatorname{Vol}(X)^{1/2}\|u\|_{L_{\infty}(X)}. ∥ u ∥ L 2 ( X ) ≤ Vol ( X ) 1/2 ∥ u ∥ L ∞ ( X ) . Applying this inequality to every local mean in the two equivalent quasi-norms yields
∥ f ∥ B 2 , ∞ α ( X ) ≤ C α , X ∥ f ∥ B ∞ , ∞ α ( X ) ≤ C ∥ f ∥ C k , β ( X ) , \|f\|_{B^{\alpha}_{2,\infty}(X)}\le C_{\alpha,X}\|f\|_{B^{\alpha}_{\infty,\infty}(X)}\le C\|f\|_{C^{k,\beta}(X)}, ∥ f ∥ B 2 , ∞ α ( X ) ≤ C α , X ∥ f ∥ B ∞ , ∞ α ( X ) ≤ C ∥ f ∥ C k , β ( X ) , which completes the proof.
Proof of Lemma 3.1 . At a point where η ∈ { 0 , 1 } \eta\in\{0,1\} η ∈ { 0 , 1 } 0 ≤ ϕ ( t ) ≤ ∣ t ∣ + log 2 ≤ ∣ t ∣ + 2 0\le\phi(t)\le|t|+\log2\le|t|+2 0 ≤ ϕ ( t ) ≤ ∣ t ∣ + log 2 ≤ ∣ t ∣ + 2 ϕ ( t ) 2 ≤ ( ∣ t ∣ + 2 ) ϕ ( t ) \phi(t)^2\le(|t|+2)\phi(t) ϕ ( t ) 2 ≤ ( ∣ t ∣ + 2 ) ϕ ( t ) η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) t ∈ R t\in\mathbb{R} t ∈ R
A : = ϕ ( t ) + log η , B : = ϕ ( − t ) + log ( 1 − η ) . A:=\phi(t)+\log\eta,\qquad B:=\phi(-t)+\log(1-\eta). A := ϕ ( t ) + log η , B := ϕ ( − t ) + log ( 1 − η ) . It is enough to prove
η A 2 + ( 1 − η ) B 2 ≤ ( ∣ t ∣ + 2 ) ( η A + ( 1 − η ) B ) . (25) \eta A^2 + (1-\eta)B^2 \le(|t|+2)(\eta A+(1-\eta)B). \tag*{(25)} η A 2 + ( 1 − η ) B 2 ≤ ( ∣ t ∣ + 2 ) ( η A + ( 1 − η ) B ) . (25) Let
F ( η , t ) : = ( ∣ t ∣ + 2 ) ( η A + ( 1 − η ) B ) − ( η A 2 + ( 1 − η ) B 2 ) . F(\eta,t):=(|t|+2)(\eta A+(1-\eta)B)-(\eta A^2+(1-\eta)B^2). F ( η , t ) := ( ∣ t ∣ + 2 ) ( η A + ( 1 − η ) B ) − ( η A 2 + ( 1 − η ) B 2 ) . Direct differentiation gives
∂ η F ( η , t ) = ( ∣ t ∣ − A − B ) ( A − B ) . \partial_{\eta}F(\eta,t)=(|t|-A-B)(A-B). ∂ η F ( η , t ) = ( ∣ t ∣ − A − B ) ( A − B ) . Note that
∣ t ∣ − ϕ ( t ) − ϕ ( − t ) = − 2 log ( 1 + e − ∣ t ∣ ) ≥ − 2 log 2 ≥ log η + log ( 1 − η ) . |t|-\phi(t)-\phi(-t)=-2\log(1+e^{-|t|})\ge-2\log2\ge\log\eta+\log(1-\eta). ∣ t ∣ − ϕ ( t ) − ϕ ( − t ) = − 2 log ( 1 + e − ∣ t ∣ ) ≥ − 2 log 2 ≥ log η + log ( 1 − η ) . Hence ∣ t ∣ − A − B ≥ 0 |t|-A-B\ge0 ∣ t ∣ − A − B ≥ 0 A − B A-B A − B η \eta η η ∗ = e t / ( 1 + e t ) \eta^*=e^t/(1+e^t) η ∗ = e t / ( 1 + e t ) A = B = 0 A=B=0 A = B = 0 F ( η ∗ , t ) = 0 F(\eta^*,t)=0 F ( η ∗ , t ) = 0 F ( η , t ) ≥ 0 F(\eta,t)\ge0 F ( η , t ) ≥ 0 t = f ( x ) t=f(x) t = f ( x ) P X P_X P X
Proof of Theorem 3.2 . By the definition of the infimum in (4) and comparison with the zero function, choose f λ ∈ F f_\lambda\in\mathcal{F} f λ ∈ F
a : = λ ∥ f λ ∥ F 2 + R ( f λ ) − R ∗ ≤ min { a F ( λ ) + λ , log 2 − R ∗ } . a:=\lambda\lVert f_\lambda\rVert_{\mathcal F}^2+\mathcal R(f_\lambda)-\mathcal R^*
\le\min\{a_{\mathcal F}(\lambda)+\lambda,\log2-\mathcal R^*\}. a := λ ∥ f λ ∥ F 2 + R ( f λ ) − R ∗ ≤ min { a F ( λ ) + λ , log 2 − R ∗ } . For f ∈ F f\in\mathcal F f ∈ F
g f ( z ) : = λ ∥ f ∥ F 2 + ϕ ( y f ( x ) ) − λ ∥ f λ ∥ F 2 − ϕ ( y f λ ( x ) ) , z = ( x , y ) . g_f(z):=\lambda\lVert f\rVert_{\mathcal F}^2+\phi(yf(x))-\lambda\lVert f_\lambda\rVert_{\mathcal F}^2-\phi(yf_\lambda(x)),\qquad z=(x,y). g f ( z ) := λ ∥ f ∥ F 2 + ϕ ( y f ( x )) − λ ∥ f λ ∥ F 2 − ϕ ( y f λ ( x )) , z = ( x , y ) . We see that
E P g f = λ ∥ f ∥ F 2 + R ( f ) − λ ∥ f λ ∥ F 2 − R ( f λ ) = λ ∥ f ∥ F 2 + R ( f ) − R ∗ − a . \mathbb E_Pg_f=\lambda\lVert f\rVert_{\mathcal F}^2+\mathcal R(f)-\lambda\lVert f_\lambda\rVert_{\mathcal F}^2-\mathcal R(f_\lambda)
=\lambda\lVert f\rVert_{\mathcal F}^2+\mathcal R(f)-\mathcal R^*-a. E P g f = λ ∥ f ∥ F 2 + R ( f ) − λ ∥ f λ ∥ F 2 − R ( f λ ) = λ ∥ f ∥ F 2 + R ( f ) − R ∗ − a . Comparison of the empirical objective with its value at zero gives λ ∥ f ^ D , λ ∥ F 2 ≤ log 2 \lambda\lVert\widehat f_{D,\lambda}\rVert_{\mathcal F}^2\le\log2 λ ∥ f D , λ ∥ F 2 ≤ log 2 f λ f_\lambda f λ λ ∥ f λ ∥ F 2 ≤ a ≤ log 2 \lambda\lVert f_\lambda\rVert_{\mathcal F}^2\le a\le\log2 λ ∥ f λ ∥ F 2 ≤ a ≤ log 2 f λ f_\lambda f λ f ^ D , λ \widehat f_{D,\lambda} f D , λ λ − 1 / 2 B F \lambda^{-1/2}B_{\mathcal F} λ − 1/2 B F
We only consider f ∈ λ − 1 / 2 B F f\in\lambda^{-1/2}B_{\mathcal F} f ∈ λ − 1/2 B F
F λ , ε : = { f ∈ λ − 1 / 2 B F : E P g f = ε } . \mathcal F_{\lambda,\varepsilon}:=\{f\in\lambda^{-1/2}B_{\mathcal F}:\mathbb E_Pg_f=\varepsilon\}. F λ , ε := { f ∈ λ − 1/2 B F : E P g f = ε } . The map f ↦ E P g f f\mapsto\mathbb E_Pg_f f ↦ E P g f ∥ ⋅ ∥ F \lVert\cdot\rVert_{\mathcal F} ∥ ⋅ ∥ F ∥ f ∥ ∞ ≤ ∥ f ∥ F \lVert f\rVert_\infty\le\lVert f\rVert_{\mathcal F} ∥ f ∥ ∞ ≤ ∥ f ∥ F F λ , ε \mathcal F_{\lambda,\varepsilon} F λ , ε F \mathcal F F
For each fixed sample set D D D f ↦ E D g f f\mapsto\mathbb E_Dg_f f ↦ E D g f f ↦ ∥ f ∥ F 2 f\mapsto\lVert f\rVert_{\mathcal F}^2 f ↦ ∥ f ∥ F 2 f ↦ ϕ ( Y i f ( X i ) ) f\mapsto\phi(Y_if(X_i)) f ↦ ϕ ( Y i f ( X i )) ϕ \phi ϕ
Let ε > 0 \varepsilon>0 ε > 0 f ∈ λ − 1 / 2 B F f\in\lambda^{-1/2}B_{\mathcal F} f ∈ λ − 1/2 B F E D g f ≤ 0 \mathbb E_Dg_f\le0 E D g f ≤ 0 E P g f ≥ ε \mathbb E_Pg_f\ge\varepsilon E P g f ≥ ε 0 ≤ θ ≤ 1 0\le\theta\le1 0 ≤ θ ≤ 1 f θ = ( 1 − θ ) f λ + θ f f_\theta=(1-\theta)f_\lambda+\theta f f θ = ( 1 − θ ) f λ + θ f λ − 1 / 2 B F \lambda^{-1/2}B_{\mathcal F} λ − 1/2 B F f θ f_\theta f θ f ↦ E D g f f\mapsto\mathbb E_Dg_f f ↦ E D g f g f λ = 0 g_{f_\lambda}=0 g f λ = 0
E D g f θ ≤ ( 1 − θ ) E D g f λ + θ E D g f = θ E D g f ≤ 0. \mathbb E_Dg_{f_\theta}\le(1-\theta)\mathbb E_Dg_{f_\lambda}+\theta\mathbb E_Dg_f=\theta\mathbb E_Dg_f\le0. E D g f θ ≤ ( 1 − θ ) E D g f λ + θ E D g f = θ E D g f ≤ 0. Moreover, the continuous map θ ↦ E P g f θ \theta\mapsto\mathbb E_Pg_{f_\theta} θ ↦ E P g f θ θ = 0 \theta=0 θ = 0 E P g f ≥ ε \mathbb E_Pg_f\ge\varepsilon E P g f ≥ ε θ = 1 \theta=1 θ = 1 θ ∈ [ 0 , 1 ] \theta\in[0,1] θ ∈ [ 0 , 1 ] f θ ∈ F λ , ε f_\theta\in\mathcal F_{\lambda,\varepsilon} f θ ∈ F λ , ε E D g f θ ≤ 0 \mathbb E_Dg_{f_\theta}\le0 E D g f θ ≤ 0 E D g f ^ D , λ ≤ 0 \mathbb E_Dg_{\widehat f_{D,\lambda}}\le0 E D g f D , λ ≤ 0 f ^ D , λ ∈ λ − 1 / 2 B F \widehat f_{D,\lambda}\in\lambda^{-1/2}B_{\mathcal F} f D , λ ∈ λ − 1/2 B F E P g f ^ D , λ ≥ ε \mathbb E_Pg_{\widehat f_{D,\lambda}}\ge\varepsilon E P g f D , λ ≥ ε f ∈ F λ , ε f\in\mathcal F_{\lambda,\varepsilon} f ∈ F λ , ε E D g f ≤ 0 \mathbb E_Dg_f\le0 E D g f ≤ 0
P D ∼ P n { E P g f ^ D , λ ≥ ε } ≤ P D ∼ P n { E D g f ≤ 0 for some f ∈ F λ , ε } . \mathbb P_{D\sim P^n}\{\mathbb E_Pg_{\widehat f_{D,\lambda}}\ge\varepsilon\}
\le\mathbb P_{D\sim P^n}\{\mathbb E_Dg_f\le0\text{ for some }f\in\mathcal F_{\lambda,\varepsilon}\}. P D ∼ P n { E P g f D , λ ≥ ε } ≤ P D ∼ P n { E D g f ≤ 0 for some f ∈ F λ , ε } . Moreover, the definitions of a a a g f g_f g f
R ( f ^ D , λ ) − R ∗ = a + E P g f ^ D , λ − λ ∥ f ^ D , λ ∥ F 2 ≤ a + E P g f ^ D , λ . \mathcal R(\widehat f_{D,\lambda})-\mathcal R^*
=a+\mathbb E_Pg_{\widehat f_{D,\lambda}}-\lambda\lVert\widehat f_{D,\lambda}\rVert_{\mathcal F}^2
\le a+\mathbb E_Pg_{\widehat f_{D,\lambda}}. R ( f D , λ ) − R ∗ = a + E P g f D , λ − λ ∥ f D , λ ∥ F 2 ≤ a + E P g f D , λ . Thus, bounding the probability on the right by e − t e^{-t} e − t a + ε a+\varepsilon a + ε 1 − e − t 1-e^{-t} 1 − e − t F λ , ε \mathcal F_{\lambda,\varepsilon} F λ , ε
Assume ε ≥ a + λ \varepsilon\ge a+\lambda ε ≥ a + λ f ∈ F λ , ε f\in\mathcal F_{\lambda,\varepsilon} f ∈ F λ , ε
∥ f ∥ F 2 ≤ a + ε λ ≤ 2 ε λ , ∥ f λ ∥ F 2 ≤ a λ ≤ ε λ . (26) \lVert f\rVert_{\mathcal F}^2\le\frac{a+\varepsilon}{\lambda}\le\frac{2\varepsilon}{\lambda},\qquad
\lVert f_\lambda\rVert_{\mathcal F}^2\le\frac{a}{\lambda}\le\frac{\varepsilon}{\lambda}. \tag*{(26)} ∥ f ∥ F 2 ≤ λ a + ε ≤ λ 2 ε , ∥ f λ ∥ F 2 ≤ λ a ≤ λ ε . (26) Define the loss difference
q f ( x , y ) : = ϕ ( y f ( x ) ) − ϕ ( y f λ ( x ) ) . q_f(x,y):=\phi(yf(x))-\phi(yf_\lambda(x)). q f ( x , y ) := ϕ ( y f ( x )) − ϕ ( y f λ ( x )) . and the auxiliary class
Q λ , ε : = { q f : f ∈ F λ , ε } . \mathcal{Q}_{\lambda,\varepsilon}:=\{q_f:f\in\mathcal{F}_{\lambda,\varepsilon}\}. Q λ , ε := { q f : f ∈ F λ , ε } . Since f , f λ ∈ λ − 1 / 2 B F f,f_\lambda\in\lambda^{-1/2}B_{\mathcal{F}} f , f λ ∈ λ − 1/2 B F 0 < λ ≤ 1 0<\lambda\le1 0 < λ ≤ 1
ε = E P g f ≤ λ ∥ f ∥ F 2 + R ( f ) ≤ 1 + ∥ f ∥ ∞ + log 2 ≤ 1 + λ − 1 / 2 + log 2 ≤ 3 / λ . \varepsilon=\mathbb{E}_{P}g_f\le\lambda\|f\|_{\mathcal{F}}^2+\mathcal{R}(f)\le1+\|f\|_\infty+\log2\le1+\lambda^{-1/2}+\log2\le3/\lambda. ε = E P g f ≤ λ ∥ f ∥ F 2 + R ( f ) ≤ 1 + ∥ f ∥ ∞ + log 2 ≤ 1 + λ − 1/2 + log 2 ≤ 3/ λ . We first establish boundedness in the supremum norm. The 1-Lipschitz property of ϕ \phi ϕ
∥ q f ∥ ∞ ≤ ∥ f − f λ ∥ ∞ ≤ ∥ f ∥ F + ∥ f λ ∥ F ≤ C ε 1 / 2 λ − 1 / 2 . (27) \|q_f\|_\infty\le\|f-f_\lambda\|_\infty\le\|f\|_{\mathcal{F}}+\|f_\lambda\|_{\mathcal{F}}\le C\varepsilon^{1/2}\lambda^{-1/2}. \tag*{(27)} ∥ q f ∥ ∞ ≤ ∥ f − f λ ∥ ∞ ≤ ∥ f ∥ F + ∥ f λ ∥ F ≤ C ε 1/2 λ − 1/2 . (27) Next, we use the Bernstein condition in Lemma 3.1 to bound the second moment. It gives
E P ( q f 2 ) ≤ 2 E P [ ( ϕ ( Y f ) − ψ ) 2 ] + 2 E P [ ( ϕ ( Y f λ ) − ψ ) 2 ] ≤ 2 ( ∥ f ∥ ∞ + 2 ) ( R ( f ) − R ∗ ) + 2 ( ∥ f λ ∥ ∞ + 2 ) ( R ( f λ ) − R ∗ ) ≤ C ε 3 / 2 λ − 1 / 2 . (28) \begin{aligned}
\mathbb{E}_{P}(q_f^2)&\le2\mathbb{E}_{P}\left[(\phi(Yf)-\psi)^2\right]+2\mathbb{E}_{P}\left[(\phi(Yf_\lambda)-\psi)^2\right]\\
&\le2(\|f\|_\infty+2)(\mathcal{R}(f)-\mathcal{R}^*)+2(\|f_\lambda\|_\infty+2)(\mathcal{R}(f_\lambda)-\mathcal{R}^*)\\
&\le C\varepsilon^{3/2}\lambda^{-1/2}. \tag*{(28)}
\end{aligned} E P ( q f 2 ) ≤ 2 E P [ ( ϕ ( Y f ) − ψ ) 2 ] + 2 E P [ ( ϕ ( Y f λ ) − ψ ) 2 ] ≤ 2 ( ∥ f ∥ ∞ + 2 ) ( R ( f ) − R ∗ ) + 2 ( ∥ f λ ∥ ∞ + 2 ) ( R ( f λ ) − R ∗ ) ≤ C ε 3/2 λ − 1/2 . (28) The last inequality uses (A.2) and the bounds R ( f ) − R ∗ ≤ a + ε ≤ 2 ε \mathcal{R}(f)-\mathcal{R}^*\le a+\varepsilon\le2\varepsilon R ( f ) − R ∗ ≤ a + ε ≤ 2 ε R ( f λ ) − R ∗ ≤ a ≤ ε \mathcal{R}(f_\lambda)-\mathcal{R}^*\le a\le\varepsilon R ( f λ ) − R ∗ ≤ a ≤ ε
The regularization terms are constants and cancel in ( E P − E D ) g f (\mathbb{E}_{P}-\mathbb{E}_{D})g_f ( E P − E D ) g f ( E P − E D ) g f = ( E P − E D ) q f (\mathbb{E}_{P}-\mathbb{E}_{D})g_f=(\mathbb{E}_{P}-\mathbb{E}_{D})q_f ( E P − E D ) g f = ( E P − E D ) q f Q λ , ε \mathcal{Q}_{\lambda,\varepsilon} Q λ , ε D D D Φ D : L 2 ( D X ) → L 2 ( D ) \Phi_D:L_2(D_X)\to L_2(D) Φ D : L 2 ( D X ) → L 2 ( D )
( Φ D u ) ( X j , Y j ) : = ϕ ( Y j u ( X j ) ) − ϕ ( Y j f λ ( X j ) ) , 1 ≤ j ≤ n . (\Phi_Du)(X_j,Y_j):=\phi(Y_ju(X_j))-\phi(Y_jf_\lambda(X_j)),\qquad1\le j\le n. ( Φ D u ) ( X j , Y j ) := ϕ ( Y j u ( X j )) − ϕ ( Y j f λ ( X j )) , 1 ≤ j ≤ n . The 1-Lipschitz property of ϕ \phi ϕ u , v ∈ L 2 ( D X ) u,v\in L_2(D_X) u , v ∈ L 2 ( D X )
∥ Φ D u − Φ D v ∥ L 2 ( D ) 2 = 1 n ∑ j = 1 n ∣ ϕ ( Y j u ( X j ) ) − ϕ ( Y j v ( X j ) ) ∣ 2 ≤ 1 n ∑ j = 1 n ∣ u ( X j ) − v ( X j ) ∣ 2 = ∥ u − v ∥ L 2 ( D X ) 2 . \begin{aligned}
\|\Phi_Du-\Phi_Dv\|_{L_2(D)}^2
&=\frac{1}{n}\sum_{j=1}^{n}\left|\phi(Y_ju(X_j))-\phi(Y_jv(X_j))\right|^2\\
&\le\frac{1}{n}\sum_{j=1}^{n}|u(X_j)-v(X_j)|^2\\
&=\|u-v\|_{L_2(D_X)}^2.
\end{aligned} ∥ Φ D u − Φ D v ∥ L 2 ( D ) 2 = n 1 j = 1 ∑ n ∣ ϕ ( Y j u ( X j )) − ϕ ( Y j v ( X j )) ∣ 2 ≤ n 1 j = 1 ∑ n ∣ u ( X j ) − v ( X j ) ∣ 2 = ∥ u − v ∥ L 2 ( D X ) 2 . In particular, Φ D \Phi_D Φ D (5) ,
e i ( Q λ , ε , L 2 ( D ) ) ≤ e i ( F λ , ε , L 2 ( D X ) ) ≤ ( 2 ε λ ) 1 / 2 e i ( id : F → L 2 ( D X ) ) . e_i(\mathcal{Q}_{\lambda,\varepsilon},L_2(D))\le e_i(\mathcal{F}_{\lambda,\varepsilon},L_2(D_X))\le\left(\frac{2\varepsilon}{\lambda}\right)^{1/2}e_i(\operatorname{id}:\mathcal{F}\to L_2(D_X)). e i ( Q λ , ε , L 2 ( D )) ≤ e i ( F λ , ε , L 2 ( D X )) ≤ ( λ 2 ε ) 1/2 e i ( id : F → L 2 ( D X )) . Consequently, (5) shows that
E D ∼ P n e i ( Q λ , ε , L 2 ( D ) ) ≤ C ( ε λ ) 1 / 2 A 1 / ( 2 p ) i − 1 / ( 2 p ) . (29) \mathbb{E}_{D\sim P^n}e_i(\mathcal{Q}_{\lambda,\varepsilon},L_2(D))\le C\left(\frac{\varepsilon}{\lambda}\right)^{1/2}A^{1/(2p)}i^{-1/(2p)}. \tag*{(29)} E D ∼ P n e i ( Q λ , ε , L 2 ( D )) ≤ C ( λ ε ) 1/2 A 1/ ( 2 p ) i − 1/ ( 2 p ) . (29) Since the map ( z , f ) ↦ q f ( z ) (z,f)\mapsto q_f(z) ( z , f ) ↦ q f ( z ) z z z f f f Q λ , ε \mathcal{Q}_{\lambda,\varepsilon} Q λ , ε [15 Theorem 7.16] with (A.3), (A.4) and (A.5) gives the local Rademacher bound
E D ∼ P n Rad D ( Q λ , ε ) ≤ C [ ε ( 3 − p ) / 4 λ − ( 1 + p ) / 4 ( A n ) 1 / 2 + ε 1 / 2 λ − 1 / 2 ( A n ) 1 / ( 1 + p ) ] . (30) \mathbb{E}_{D\sim P^n}\operatorname{Rad}_D(\mathcal{Q}_{\lambda,\varepsilon})\le C\left[\varepsilon^{(3-p)/4}\lambda^{-(1+p)/4}\left(\frac{A}{n}\right)^{1/2}+\varepsilon^{1/2}\lambda^{-1/2}\left(\frac{A}{n}\right)^{1/(1+p)}\right]. \tag*{(30)} E D ∼ P n Rad D ( Q λ , ε ) ≤ C [ ε ( 3 − p ) /4 λ − ( 1 + p ) /4 ( n A ) 1/2 + ε 1/2 λ − 1/2 ( n A ) 1/ ( 1 + p ) ] . (30) The constant C C C p ∈ ( 0 , 1 / 2 ] p\in(0,1/2] p ∈ ( 0 , 1/2 ]
Let h f : = E P q f − q f h_f:=\mathbb{E}_{P}q_f-q_f h f := E P q f − q f ( E P − E D ) g f = ( E P − E D ) q f (\mathbb{E}_{P}-\mathbb{E}_{D})g_f=(\mathbb{E}_{P}-\mathbb{E}_{D})q_f ( E P − E D ) g f = ( E P − E D ) q f
P D ∼ P n { E D g f ≤ 0 for some f ∈ F λ , ε } ≤ P D ∼ P n { sup f ∈ F λ , ε E D h f ≥ ε } . \mathbb{P}_{D\sim P^n}\{ \mathbb{E}_{D}g_f\le0\text{ for some }f\in\mathcal{F}_{\lambda,\varepsilon}\}
\le\mathbb{P}_{D\sim P^n}\left\{\sup_{f\in\mathcal{F}_{\lambda,\varepsilon}}\mathbb{E}_{D}h_f\ge\varepsilon\right\}. P D ∼ P n { E D g f ≤ 0 for some f ∈ F λ , ε } ≤ P D ∼ P n { f ∈ F λ , ε sup E D h f ≥ ε } . By symmetrization [15 Proposition 7.10] ,
E D ∼ P n sup f ∈ F λ , ε E D h f ≤ 2 E D ∼ P n Rad D ( Q λ , ε ) . \mathbb{E}_{D\sim P^n}\sup_{f\in\mathcal{F}_{\lambda,\varepsilon}}\mathbb{E}_{D}h_f
\le2\mathbb{E}_{D\sim P^n}\operatorname{Rad}_D(\mathcal{Q}_{\lambda,\varepsilon}). E D ∼ P n f ∈ F λ , ε sup E D h f ≤ 2 E D ∼ P n Rad D ( Q λ , ε ) . For every f ∈ F λ , ε f \in\mathcal{F}_{\lambda,\varepsilon} f ∈ F λ , ε E P h f = 0 \mathbb{E}_{P}h_f=0 E P h f = 0 ∥ h f ∥ ∞ ≤ 2 ∥ q f ∥ ∞ \|h_f\|_{\infty} \le2\|q_f\|_{\infty} ∥ h f ∥ ∞ ≤ 2∥ q f ∥ ∞ E P ( h f 2 ) ≤ E P ( q f 2 ) \mathbb{E}_{P}(h_f^2) \le\mathbb{E}_{P}(q_f^2) E P ( h f 2 ) ≤ E P ( q f 2 ) [15 Theorem 7.5] . Together with the preceding symmetrization bound, it gives, for every t ≥ 1 t \ge1 t ≥ 1 1 − e − t 1-e^{-t} 1 − e − t
sup f ∈ F λ , ε E D h f < C [ E D ∼ P n Rad D ( Q λ , ε ) + ε 3 / 4 λ − 1 / 4 ( t n ) 1 / 2 + ε 1 / 2 λ − 1 / 2 t n ] . \sup_{f\in\mathcal{F}_{\lambda,\varepsilon}} \mathbb{E}_{D}h_f<C\left[\mathbb{E}_{D\sim P^n}\operatorname{Rad}_{D}(\mathcal{Q}_{\lambda,\varepsilon})+\varepsilon^{3/4}\lambda^{-1/4}\left(\frac{t}{n}\right)^{1/2}+\varepsilon^{1/2}\lambda^{-1/2}\frac{t}{n}\right]. f ∈ F λ , ε sup E D h f < C [ E D ∼ P n Rad D ( Q λ , ε ) + ε 3/4 λ − 1/4 ( n t ) 1/2 + ε 1/2 λ − 1/2 n t ] . Substituting (A.6), we obtain
P D ∼ P n { sup f ∈ F λ , ε E D h f ≥ ε } ≤ e − t . \mathbb{P}_{D\sim P^n}\left\{\sup_{f\in\mathcal{F}_{\lambda,\varepsilon}}\mathbb{E}_{D}h_f\ge\varepsilon\right\}\le e^{-t}. P D ∼ P n { f ∈ F λ , ε sup E D h f ≥ ε } ≤ e − t . provided that ε ≥ a + λ \varepsilon\ge a+\lambda ε ≥ a + λ
ε ≥ C [ ε ( 3 − p ) / 4 λ − ( 1 + p ) / 4 ( A n ) 1 / 2 + ε 1 / 2 λ − 1 / 2 ( A n ) 1 / ( 1 + p ) + ε 3 / 4 λ − 1 / 4 ( t n ) 1 / 2 + ε 1 / 2 λ − 1 / 2 t n ] . \varepsilon\ge C\left[\varepsilon^{(3-p)/4}\lambda^{-(1+p)/4}\left(\frac{A}{n}\right)^{1/2}+\varepsilon^{1/2}\lambda^{-1/2}\left(\frac{A}{n}\right)^{1/(1+p)}+\varepsilon^{3/4}\lambda^{-1/4}\left(\frac{t}{n}\right)^{1/2}+\varepsilon^{1/2}\lambda^{-1/2}\frac{t}{n}\right]. ε ≥ C [ ε ( 3 − p ) /4 λ − ( 1 + p ) /4 ( n A ) 1/2 + ε 1/2 λ − 1/2 ( n A ) 1/ ( 1 + p ) + ε 3/4 λ − 1/4 ( n t ) 1/2 + ε 1/2 λ − 1/2 n t ] . Choose
ε : = C 0 [ a + λ + λ − 1 ( A n ) 2 / ( 1 + p ) + λ − 1 t 2 n 2 ] . \varepsilon:=C_0\left[a+\lambda+\lambda^{-1}\left(\frac{A}{n}\right)^{2/(1+p)}+\lambda^{-1}\frac{t^2}{n^2}\right]. ε := C 0 [ a + λ + λ − 1 ( n A ) 2/ ( 1 + p ) + λ − 1 n 2 t 2 ] . with C 0 C_0 C 0 F λ , ε \mathcal{F}_{\lambda,\varepsilon} F λ , ε E P g f ^ D , λ < ε \mathbb{E}_{P}g_{\widehat{f}_{D,\lambda}}<\varepsilon E P g f D , λ < ε D D D E P g f ^ D , λ < ε \mathbb{E}_{P}g_{\widehat{f}_{D,\lambda}}<\varepsilon E P g f D , λ < ε 1 − e − t 1-e^{-t} 1 − e − t
Finally, note that a ≤ a F ( λ ) + λ a\le a_{\mathcal{F}}(\lambda)+\lambda a ≤ a F ( λ ) + λ E P g f ^ D , λ < ε \mathbb{E}_{P}g_{\widehat{f}_{D,\lambda}}<\varepsilon E P g f D , λ < ε
R ( f ^ D , λ ) − R ∗ = a + E P g f ^ D , λ − λ ∥ f ^ D , λ ∥ F 2 ≤ a + ε ≤ C [ a F ( λ ) + λ + λ − 1 ( A n ) 2 / ( 1 + p ) + λ − 1 t 2 n 2 ] . \begin{aligned}
\mathcal{R}(\widehat{f}_{D,\lambda})-\mathcal{R}^{*}=a+\mathbb{E}_{P}g_{\widehat{f}_{D,\lambda}}-\lambda\|\widehat{f}_{D,\lambda}\|_{\mathcal{F}}^{2} \\
&\le a+\varepsilon\\
&\le C\left[a_{\mathcal{F}}(\lambda)+\lambda+\lambda^{-1}\left(\frac{A}{n}\right)^{2/(1+p)}+\lambda^{-1}\frac{t^2}{n^2}\right].
\end{aligned} R ( f D , λ ) − R ∗ = a + E P g f D , λ − λ ∥ f D , λ ∥ F 2 ≤ a + ε ≤ C [ a F ( λ ) + λ + λ − 1 ( n A ) 2/ ( 1 + p ) + λ − 1 n 2 t 2 ] . This completes the proof of (6) . □
Proof of Corollary 3.3. Use the function f λ f_\lambda f λ a a a F λ , ε \mathcal{F}_{\lambda,\varepsilon} F λ , ε Q λ , ε \mathcal{Q}_{\lambda,\varepsilon} Q λ , ε Theorem 3.2 . The localization argument and the bounds (A.2), (A.3), and (A.4) do not use the entropy assumption. Fix ε ≥ a + λ \varepsilon\ge a+\lambda ε ≥ a + λ F λ , ε \mathcal{F}_{\lambda,\varepsilon} F λ , ε ( 2 ε / λ ) 1 / 2 B F (2\varepsilon/\lambda)^{1/2}B_{\mathcal{F}} ( 2 ε / λ ) 1/2 B F f ↦ q f f\mapsto q_f f ↦ q f (7) gives
log N ( δ ( 2 ε λ ) 1 / 2 , Q λ , ε , ∥ ⋅ ∥ ∞ ) ≤ A δ − 2 p , b ≤ δ ≤ 1. \log N\left(\delta\left(\frac{2\varepsilon}{\lambda}\right)^{1/2},\mathcal{Q}_{\lambda,\varepsilon},\|\cdot\|_{\infty}\right)\le A\delta^{-2p},\qquad b\le\delta\le1. log N ( δ ( λ 2 ε ) 1/2 , Q λ , ε , ∥ ⋅ ∥ ∞ ) ≤ A δ − 2 p , b ≤ δ ≤ 1. Choose such a cover at radius b ( 2 ε / λ ) 1 / 2 b(2\varepsilon/\lambda)^{1/2} b ( 2 ε / λ ) 1/2 Q λ , ε \mathcal{Q}_{\lambda,\varepsilon} Q λ , ε N ⊂ Q λ , ε \mathcal{N}\subset\mathcal{Q}_{\lambda,\varepsilon} N ⊂ Q λ , ε
sup q ∈ Q λ , ε min v ∈ N ∥ q − v ∥ ∞ ≤ 2 b ( 2 ε λ ) 1 / 2 , log ∣ N ∣ ≤ A b − 2 p . (31) \sup_{q\in\mathcal{Q}_{\lambda,\varepsilon}}\min_{v\in\mathcal{N}}\|q-v\|_{\infty}\le2b\left(\frac{2\varepsilon}{\lambda}\right)^{1/2},\qquad\log|\mathcal{N}|\le Ab^{-2p}. \tag*{(31)} q ∈ Q λ , ε sup v ∈ N min ∥ q − v ∥ ∞ ≤ 2 b ( λ 2 ε ) 1/2 , log ∣ N ∣ ≤ A b − 2 p . (31) Set N 0 : = N ∪ { 0 } \mathcal{N}_0:=\mathcal{N}\cup\{0\} N 0 := N ∪ { 0 } δ ( 2 ε / λ ) 1 / 2 \delta(2\varepsilon/\lambda)^{1/2} δ ( 2 ε / λ ) 1/2 b ≤ δ ≤ 1 b\le\delta\le1 b ≤ δ ≤ 1 N \mathcal{N} N δ ( 2 ε / λ ) 1 / 2 \delta(2\varepsilon/\lambda)^{1/2} δ ( 2 ε / λ ) 1/2 Q λ , ε \mathcal{Q}_{\lambda,\varepsilon} Q λ , ε 0 < δ < b 0<\delta<b 0 < δ < b N 0 \mathcal{N}_0 N 0
log N ( δ ( 2 ε λ ) 1 / 2 , N 0 , ∥ ⋅ ∥ ∞ ) ≤ 2 A δ − 2 p , 0 < δ ≤ 1. \log N\left(\delta\left(\frac{2\varepsilon}{\lambda}\right)^{1/2},\mathcal{N}_0,\|\cdot\|_{\infty}\right)\le2A\delta^{-2p},\qquad0<\delta\le1. log N ( δ ( λ 2 ε ) 1/2 , N 0 , ∥ ⋅ ∥ ∞ ) ≤ 2 A δ − 2 p , 0 < δ ≤ 1. By (A.3), every member of N 0 \mathcal{N}_0 N 0 2 ( 2 ε / λ ) 1 / 2 2(2\varepsilon/\lambda)^{1/2} 2 ( 2 ε / λ ) 1/2 1 < δ ≤ 2 1 < \delta\le2 1 < δ ≤ 2 ( 2 ε / λ ) 1 / 2 (2\varepsilon/\lambda)^{1/2} ( 2 ε / λ ) 1/2 2 A 2A 2 A 4 A 4A 4 A ∥ ⋅ ∥ L 2 ( D ) ≤ ∥ ⋅ ∥ ∞ \|\cdot\|_{L_2(D)} \le\|\cdot\|_\infty ∥ ⋅ ∥ L 2 ( D ) ≤ ∥ ⋅ ∥ ∞ C 0 ≥ 1 C_0 \ge1 C 0 ≥ 1
e i ( N 0 , L 2 ( D ) ) ≤ ( 2 ε λ ) 1 / 2 ( C 0 A ) 1 / ( 2 p ) i − 1 / ( 2 p ) , i ≥ 1. e_i(\mathcal{N}_0,L_2(D)) \le\left(\frac{2\varepsilon}{\lambda}\right)^{1/2}(C_0A)^{1/(2p)}i^{-1/(2p)}, \qquad i \ge1. e i ( N 0 , L 2 ( D )) ≤ ( λ 2 ε ) 1/2 ( C 0 A ) 1/ ( 2 p ) i − 1/ ( 2 p ) , i ≥ 1. Apply [15 Theorem 7.16] to the finite class N 0 \mathcal{N}_0 N 0
E D ∼ P n Rad D ( N 0 ) ≤ C [ ε ( 3 − p ) / 4 λ − ( 1 + p ) / 4 ( A n ) 1 / 2 + ε 1 / 2 λ − 1 / 2 ( A n ) 1 / ( 1 + p ) ] . \mathbb{E}_{D\sim P^n}\operatorname{Rad}_D(\mathcal{N}_0) \le C\left[\varepsilon^{(3-p)/4}\lambda^{-(1+p)/4}\left(\frac{A}{n}\right)^{1/2}+\varepsilon^{1/2}\lambda^{-1/2}\left(\frac{A}{n}\right)^{1/(1+p)}\right]. E D ∼ P n Rad D ( N 0 ) ≤ C [ ε ( 3 − p ) /4 λ − ( 1 + p ) /4 ( n A ) 1/2 + ε 1/2 λ − 1/2 ( n A ) 1/ ( 1 + p ) ] . with C C C p ∈ ( 0 , 1 / 2 ] p \in(0,1/2] p ∈ ( 0 , 1/2 ] D D D
Rad D ( Q λ , ε ) ≤ Rad D ( N 0 ) + 2 b ( 2 ε λ ) 1 / 2 . \operatorname{Rad}_D(\mathcal{Q}_{\lambda,\varepsilon}) \le\operatorname{Rad}_D(\mathcal{N}_0)+2b\left(\frac{2\varepsilon}{\lambda}\right)^{1/2}. Rad D ( Q λ , ε ) ≤ Rad D ( N 0 ) + 2 b ( λ 2 ε ) 1/2 . Consequently, the estimate (A.6) remains valid with an additional term C b ( ε / λ ) 1 / 2 Cb(\varepsilon/\lambda)^{1/2} C b ( ε / λ ) 1/2 (8) , with the additional term contributing C b 2 / λ Cb^2/\lambda C b 2 / λ
Proof of Theorem 4.1 . The compact embedded manifold X X X [11 ]
sup y ∈ X V ( X ∩ B R d ( y , r ) ) ≤ C X r ϱ , 0 < r ≤ 1. \sup_{y\in X}V(X\cap B_{\mathbb{R}^d}(y,r))\le C_Xr^\varrho,\qquad0<r\le1. y ∈ X sup V ( X ∩ B R d ( y , r )) ≤ C X r ϱ , 0 < r ≤ 1. This gives the uniform integral bound
sup y ∈ X ∫ X exp ( − ∥ x − y ∥ R d 2 γ 2 ) d V ( x ) ≤ C X γ ϱ . \sup_{y\in X}\int_X\exp\left(-\frac{\|x-y\|_{\mathbb{R}^d}^2}{\gamma^2}\right)dV(x)\le C_X\gamma^\varrho. y ∈ X sup ∫ X exp ( − γ 2 ∥ x − y ∥ R d 2 ) d V ( x ) ≤ C X γ ϱ . By the reproducing property,
∥ T γ f ∥ H γ 2 ( X ) 2 = ( γ π ) − 2 ϱ ∫ X ∫ X f ( x ) f ( y ) ⟨ k γ ( ⋅ , x ) , k γ ( ⋅ , y ) ⟩ H γ ( X ) d V ( x ) d V ( y ) = ( γ π ) − 2 ϱ ∫ X ∫ X exp ( − ∥ x − y ∥ R d 2 γ 2 ) f ( x ) f ( y ) d V ( x ) d V ( y ) ≤ 1 2 ( γ π ) 2 ϱ ∫ X ∫ X ( ∣ f ( x ) ∣ 2 + ∣ f ( y ) ∣ 2 ) exp ( − ∥ x − y ∥ R d 2 γ 2 ) d V ( x ) d V ( y ) ≤ C X γ − ϱ ∥ f ∥ L 2 ( X ) 2 . \begin{aligned}
\|T_\gamma f\|_{\mathcal{H}_{\gamma^2}(X)}^2=(\gamma\sqrt{\pi})^{-2\varrho}\int_X\int_X f(x)f(y)\langle k_\gamma(\cdot,x),k_\gamma(\cdot,y)\rangle_{\mathcal{H}_\gamma(X)}dV(x)dV(y) \\
&=(\gamma\sqrt{\pi})^{-2\varrho}\int_X\int_X\exp\left(-\frac{\|x-y\|_{\mathbb{R}^d}^2}{\gamma^2}\right)f(x)f(y)dV(x)dV(y) \\
&\le\frac{1}{2(\gamma\sqrt{\pi})^{2\varrho}}\int_X\int_X\left(|f(x)|^2+|f(y)|^2\right)\exp\left(-\frac{\|x-y\|_{\mathbb{R}^d}^2}{\gamma^2}\right)dV(x)dV(y) \\
&\le C_X\gamma^{-\varrho}\|f\|_{L_2(X)}^2.
\end{aligned} ∥ T γ f ∥ H γ 2 ( X ) 2 = ( γ π ) − 2 ϱ ∫ X ∫ X f ( x ) f ( y ) ⟨ k γ ( ⋅ , x ) , k γ ( ⋅ , y ) ⟩ H γ ( X ) d V ( x ) d V ( y ) = ( γ π ) − 2 ϱ ∫ X ∫ X exp ( − γ 2 ∥ x − y ∥ R d 2 ) f ( x ) f ( y ) d V ( x ) d V ( y ) ≤ 2 ( γ π ) 2 ϱ 1 ∫ X ∫ X ( ∣ f ( x ) ∣ 2 + ∣ f ( y ) ∣ 2 ) exp ( − γ 2 ∥ x − y ∥ R d 2 ) d V ( x ) d V ( y ) ≤ C X γ − ϱ ∥ f ∥ L 2 ( X ) 2 . The Gaussian RKHS inclusion criterion [15 Proposition 4.46] gives
H j γ ( X ) ⊂ H γ ( X ) , ∥ u ∥ H γ ( X ) ≤ j d / 2 ∥ u ∥ H j γ ( X ) , j ≥ 1. \mathcal{H}_{j\gamma}(X)\subset\mathcal{H}_{\gamma}(X),\qquad\|u\|_{\mathcal{H}_{\gamma}(X)}\le j^{d/2}\|u\|_{\mathcal{H}_{j\gamma}(X)},\qquad j\ge1. H j γ ( X ) ⊂ H γ ( X ) , ∥ u ∥ H γ ( X ) ≤ j d /2 ∥ u ∥ H j γ ( X ) , j ≥ 1. Applying these two estimates to every term in (9) proves the result.
Proof of Lemma 4.2. We first prove the estimate for f ∈ C ∞ ( X ) f\in C^\infty(X) f ∈ C ∞ ( X ) L = 2 N + 2 L=2N+2 L = 2 N + 2 0 < δ < inj ( X ) / 4 0<\delta<\operatorname{inj}(X)/4 0 < δ < inj ( X ) /4 χ 0 ∈ C ∞ ( [ 0 , ∞ ) ) \chi_0\in C^\infty([0,\infty)) χ 0 ∈ C ∞ ([ 0 , ∞ )) 0 ≤ χ 0 ≤ 1 0\le\chi_0\le1 0 ≤ χ 0 ≤ 1 χ 0 = 1 \chi_0=1 χ 0 = 1 [ 0 , δ 2 ] [0,\delta^2] [ 0 , δ 2 ] χ 0 = 0 \chi_0=0 χ 0 = 0 [ 4 δ 2 , ∞ ) [4\delta^2,\infty) [ 4 δ 2 , ∞ )
χ ( x , y ) : = χ 0 ( d X ( x , y ) 2 ) , \chi(x,y):=\chi_0(d_X(x,y)^2), χ ( x , y ) := χ 0 ( d X ( x , y ) 2 ) , T γ = T γ l o c + T γ f a r . T_\gamma=T_\gamma^{\mathrm{loc}}+T_\gamma^{\mathrm{far}}. T γ = T γ loc + T γ far . T γ l o c f ( x ) : = ( γ π ) − ϱ ∫ X exp ( − ∥ x − y ∥ R d 2 γ 2 ) χ ( x , y ) f ( y ) d V ( y ) , T_\gamma^{\mathrm{loc}}f(x):=(\gamma\sqrt{\pi})^{-\varrho}\int_X\exp\left(-\frac{\|x-y\|_{\mathbb{R}^d}^2}{\gamma^2}\right)\chi(x,y)f(y)dV(y), T γ loc f ( x ) := ( γ π ) − ϱ ∫ X exp ( − γ 2 ∥ x − y ∥ R d 2 ) χ ( x , y ) f ( y ) d V ( y ) , T γ f a r f ( x ) : = ( γ π ) − ϱ ∫ X exp ( − ∥ x − y ∥ R d 2 γ 2 ) ( 1 − χ ( x , y ) ) f ( y ) d V ( y ) . T_\gamma^{\mathrm{far}}f(x):=(\gamma\sqrt{\pi})^{-\varrho}\int_X\exp\left(-\frac{\|x-y\|_{\mathbb{R}^d}^2}{\gamma^2}\right)(1-\chi(x,y))f(y)dV(y). T γ far f ( x ) := ( γ π ) − ϱ ∫ X exp ( − γ 2 ∥ x − y ∥ R d 2 ) ( 1 − χ ( x , y )) f ( y ) d V ( y ) . Since X X X R d \mathbb{R}^{d} R d c δ > 0 c_{\delta}>0 c δ > 0
d X ( x , y ) ≥ δ ⟹ ∥ x − y ∥ R d ≥ c δ . d_{X}(x,y)\ge\delta\Longrightarrow\lVert x-y\rVert_{\mathbb{R}^{d}}\ge c_{\delta}. d X ( x , y ) ≥ δ ⟹ ∥ x − y ∥ R d ≥ c δ . Let K γ f a r ( x , y ) K_{\gamma}^{\mathrm{far}}(x,y) K γ far ( x , y ) T γ f a r T_{\gamma}^{\mathrm{far}} T γ far 1 − χ ( x , y ) 1-\chi(x,y) 1 − χ ( x , y ) d X ( x , y ) ≤ δ d_{X}(x,y)\le\delta d X ( x , y ) ≤ δ 0 ≤ χ ≤ 1 0\le\chi\le1 0 ≤ χ ≤ 1
sup x ∈ X ∫ X ∣ K γ f a r ( x , y ) ∣ d V ( y ) ≤ ( γ π ) − ϱ V ( X ) exp ( − c δ 2 / γ 2 ) . \sup_{x\in X}\int_{X}\left|K_{\gamma}^{\mathrm{far}}(x,y)\right|dV(y)\le(\gamma\sqrt{\pi})^{-\varrho}V(X)\exp\left(-c_{\delta}^{2}/\gamma^{2}\right). x ∈ X sup ∫ X K γ far ( x , y ) d V ( y ) ≤ ( γ π ) − ϱ V ( X ) exp ( − c δ 2 / γ 2 ) . By symmetry, the same bound holds with x x x y y y
∥ T γ f a r ∥ L 2 → L 2 ≤ C X , δ γ − ϱ exp ( − c δ 2 / γ 2 ) . (32) \left\|T_{\gamma}^{\mathrm{far}}\right\|_{L^{2}\to L^{2}}\le C_{X,\delta}\gamma^{-\varrho}\exp\left(-c_{\delta}^{2}/\gamma^{2}\right). \tag*{(32)} T γ far L 2 → L 2 ≤ C X , δ γ − ϱ exp ( − c δ 2 / γ 2 ) . (32) For the local term, let E x : T x X → X \mathcal{E}_{x}:T_{x}X\to X E x : T x X → X x x x χ ( x , y ) \chi(x,y) χ ( x , y ) d X ( x , y ) ≥ 2 δ d_{X}(x,y)\ge2\delta d X ( x , y ) ≥ 2 δ δ < inj ( X ) / 4 \delta<\operatorname{inj}(X)/4 δ < inj ( X ) /4 y = E x ( u ) y=\mathcal{E}_{x}(u) y = E x ( u )
q x ( u ) : = ∥ x − E x ( u ) ∥ R d 2 , d V ( E x ( u ) ) = J x ( u ) d u x . q_{x}(u):=\left\|x-\mathcal{E}_{x}(u)\right\|_{\mathbb{R}^{d}}^{2},\qquad dV(\mathcal{E}_{x}(u))=J_{x}(u)\,du_{x}. q x ( u ) := ∥ x − E x ( u ) ∥ R d 2 , d V ( E x ( u )) = J x ( u ) d u x . By [21 Lemma D.12] , uniformly in x x x ∥ u ∥ < 2 δ \lVert u\rVert<2\delta ∥ u ∥ < 2 δ
q x ( u ) = ∥ u ∥ 2 + O ( ∥ u ∥ 4 ) , J x ( u ) = 1 + O ( ∥ u ∥ 2 ) , c ∥ u ∥ 2 ≤ q x ( u ) ≤ C ∥ u ∥ 2 . (33) \begin{aligned}
q_{x}(u)&=\lVert u\rVert^{2}+O(\lVert u\rVert^{4}),\\
J_{x}(u)&=1+O(\lVert u\rVert^{2}),\\
c\lVert u\rVert^{2}&\le q_{x}(u)\le C\lVert u\rVert^{2}. \tag*{(33)}
\end{aligned} q x ( u ) J x ( u ) c ∥ u ∥ 2 = ∥ u ∥ 2 + O (∥ u ∥ 4 ) , = 1 + O (∥ u ∥ 2 ) , ≤ q x ( u ) ≤ C ∥ u ∥ 2 . (33) Rescale the tangent coordinates by the bandwidth via u = γ z u=\gamma z u = γ z
Ψ x ( t , z ) : = { q x ( t z ) / t 2 , t ≠ 0 , ∥ t z ∥ < 3 δ , ∥ z ∥ 2 , t = 0 , \Psi_{x}(t,z):=
\begin{cases}
q_{x}(tz)/t^{2}, & t\ne0,\ \lVert tz\rVert<3\delta,\\
\lVert z\rVert^{2}, & t=0,
\end{cases} Ψ x ( t , z ) := { q x ( t z ) / t 2 , ∥ z ∥ 2 , t = 0 , ∥ t z ∥ < 3 δ , t = 0 , and extend the product
exp ( − Ψ x ( t , z ) ) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) \exp\left(-\Psi_{x}(t,z)\right)J_{x}(tz)\chi_{0}\left(t^{2}\lVert z\rVert^{2}\right) exp ( − Ψ x ( t , z ) ) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) by zero when ∥ t z ∥ ≥ 3 δ \lVert tz\rVert\ge3\delta ∥ t z ∥ ≥ 3 δ q x q_{x} q x u u u θ ↦ q x ( θ t z ) \theta\mapsto q_{x}(\theta tz) θ ↦ q x ( θ t z ) t 2 t^{2} t 2 t ≠ 0 t\ne0 t = 0
Ψ x ( t , z ) = ∫ 0 1 ( 1 − θ ) D 2 q x ( θ t z ) [ z , z ] d θ . (34) \Psi_{x}(t,z)=\int_{0}^{1}(1-\theta)D^{2}q_{x}(\theta tz)[z,z]\,d\theta. \tag*{(34)} Ψ x ( t , z ) = ∫ 0 1 ( 1 − θ ) D 2 q x ( θ t z ) [ z , z ] d θ . (34) For fixed x , z x,z x , z t t t ∥ z ∥ 2 \lVert z\rVert^{2} ∥ z ∥ 2 ∥ t z ∥ < 2 δ \lVert tz\rVert<2\delta ∥ t z ∥ < 2 δ Ψ x ( t , z ) ≥ c ∥ z ∥ 2 \Psi_{x}(t,z)\ge c\lVert z\rVert^{2} Ψ x ( t , z ) ≥ c ∥ z ∥ 2 t t t ∥ z ∥ \lVert z\rVert ∥ z ∥ J x ( t z ) J_{x}(tz) J x ( t z ) ∣ t ∣ ≤ 1 \lvert t\rvert\le1 ∣ t ∣ ≤ 1 0 ≤ ℓ ≤ L 0\le\ell\le L 0 ≤ ℓ ≤ L
∣ ∂ t ℓ [ exp ( − Ψ x ( t , z ) ) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) ] ∣ ≤ C ℓ ( 1 + ∥ z ∥ 2 ) M ℓ / 2 exp ( − c ∥ z ∥ 2 ) . (35) \left|\partial_{t}^{\ell}\left[\exp\left(-\Psi_{x}(t,z)\right)J_{x}(tz)\chi_{0}\left(t^{2}\lVert z\rVert^{2}\right)\right]\right|\le C_{\ell}(1+\lVert z\rVert^{2})^{M_{\ell}/2}\exp(-c\lVert z\rVert^{2}). \tag*{(35)} ∂ t ℓ [ exp ( − Ψ x ( t , z ) ) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) ] ≤ C ℓ ( 1 + ∥ z ∥ 2 ) M ℓ /2 exp ( − c ∥ z ∥ 2 ) . (35) Here, C ℓ > 0 C_{\ell}>0 C ℓ > 0 M ℓ ∈ N 0 M_{\ell}\in\mathbb{N}_{0} M ℓ ∈ N 0 c > 0 c>0 c > 0 x , t , z x,t,z x , t , z T x X T_{x}X T x X I t f ( x ) \mathcal{I}_{t}f(x) I t f ( x )
I t f ( x ) = π − ϱ / 2 ∫ T x X exp ( − Ψ x ( t , z ) ) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) f ( E x ( t z ) ) d z x . \mathcal{I}_{t}f(x)=\pi^{-\varrho/2}\int_{T_{x}X}\exp\left(-\Psi_{x}(t,z)\right)J_{x}(tz)\chi_{0}\left(t^{2}\lVert z\rVert^{2}\right)f(\mathcal{E}_{x}(tz))\,dz_{x}. I t f ( x ) = π − ϱ /2 ∫ T x X exp ( − Ψ x ( t , z ) ) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) f ( E x ( t z )) d z x . Then I t = T t l o c \mathcal{I}_{t}=T_{t}^{\mathrm{loc}} I t = T t loc t ≠ 0 t\ne0 t = 0 I 0 = I \mathcal{I}_{0}=I I 0 = I
We now apply Taylor’s formula at the origin to the integrand as a function of t t t L − 1 L-1 L − 1 x x x z z z
F x , z ( s ) = exp ( − Ψ x ( s , z ) ) J x ( s z ) χ 0 ( s 2 ∥ z ∥ 2 ) f ( E x ( s z ) ) . F_{x,z}(s)=\exp\left(-\Psi_{x}(s,z)\right)J_{x}(sz)\chi_{0}\left(s^{2}\lVert z\rVert^{2}\right)f(\mathcal{E}_{x}(sz)). F x , z ( s ) = exp ( − Ψ x ( s , z ) ) J x ( sz ) χ 0 ( s 2 ∥ z ∥ 2 ) f ( E x ( sz )) . Let F x , z ( j ) F_{x,z}^{(j)} F x , z ( j ) s s s f ( E x ( t z ) ) f(\mathcal{E}_{x}(tz)) f ( E x ( t z )) 1 ≤ ℓ ≤ L 1\le\ell\le L 1 ≤ ℓ ≤ L ∥ t z ∥ < 2 δ \lVert tz\rVert<2\delta ∥ t z ∥ < 2 δ
d ℓ d t ℓ f ( E x ( t z ) ) = ( ∇ ℓ f ) E x ( t z ) ( P x , E x ( t z ) z , … , P x , E x ( t z ) z ⏟ ℓ a r g u m e n t s ) . \frac{d^{\ell}}{dt^{\ell}}f(\mathcal{E}_{x}(tz))=(\nabla^{\ell}f)_{\mathcal{E}_{x}(tz)}\left(\underbrace{P_{x,\mathcal{E}_{x}(tz)}z,\ldots,P_{x,\mathcal{E}_{x}(tz)}z}_{\ell\ \mathrm{arguments}}\right). d t ℓ d ℓ f ( E x ( t z )) = ( ∇ ℓ f ) E x ( t z ) ℓ arguments P x , E x ( t z ) z , … , P x , E x ( t z ) z . Since parallel transport preserves lengths, this yields
∣ d ℓ d t ℓ f ( E x ( t z ) ) ∣ ≤ ∥ z ∥ ℓ ∣ ∇ ℓ f ∣ ( E x ( t z ) ) . (36) \left|\frac{d^\ell}{dt^\ell}f(\mathcal{E}_x(tz))\right| \leq\|z\|^\ell|\nabla^\ell f|(\mathcal{E}_x(tz)). \tag*{(36)} d t ℓ d ℓ f ( E x ( t z )) ≤ ∥ z ∥ ℓ ∣ ∇ ℓ f ∣ ( E x ( t z )) . (36) By Leibniz’s rule, each term in F x , z ( L ) ( s ) F_{x,z}^{(L)}(s) F x , z ( L ) ( s ) ℓ \ell ℓ f ( E x ( s z ) ) f(\mathcal{E}_x(sz)) f ( E x ( sz )) L − ℓ L-\ell L − ℓ ∥ z ∥ ℓ ≤ ( 1 + ∥ z ∥ 2 ) ℓ / 2 \|z\|^\ell\leq(1+\|z\|^2)^{\ell/2} ∥ z ∥ ℓ ≤ ( 1 + ∥ z ∥ 2 ) ℓ /2
∣ F x , z ( L ) ( s ) ∣ ≤ C ( 1 + ∥ z ∥ 2 ) M / 2 exp ( − c ∥ z ∥ 2 ) 1 { ∥ s z ∥ ≤ 2 δ } ∑ ℓ = 0 L ∣ ∇ ℓ f ∣ ( E x ( s z ) ) , (37) |F_{x,z}^{(L)}(s)| \leq C(1+\|z\|^2)^{M/2}\exp(-c\|z\|^2)\mathbf{1}_{\{\|sz\|\leq2\delta\}}\sum_{\ell=0}^{L}|\nabla^\ell f|(\mathcal{E}_x(sz)), \tag*{(37)} ∣ F x , z ( L ) ( s ) ∣ ≤ C ( 1 + ∥ z ∥ 2 ) M /2 exp ( − c ∥ z ∥ 2 ) 1 { ∥ sz ∥ ≤ 2 δ } ℓ = 0 ∑ L ∣ ∇ ℓ f ∣ ( E x ( sz )) , (37) M : = max 0 ≤ ℓ ≤ L ( M L − ℓ + ℓ ) . M:=\max_{0\leq\ell\leq L}(M_{L-\ell}+\ell). M := 0 ≤ ℓ ≤ L max ( M L − ℓ + ℓ ) . Applying Taylor’s formula to F x , z F_{x,z} F x , z z z z R L , t R_{L,t} R L , t
I t f ( x ) = π − ϱ / 2 ∑ j = 0 L − 1 t j j ! ∫ T x X F x , z ( j ) ( 0 ) d z x + R L , t f ( x ) , \mathcal{I}_t f(x)=\pi^{-\varrho/2}\sum_{j=0}^{L-1}\frac{t^j}{j!}\int_{T_xX}F_{x,z}^{(j)}(0)\,dz_x+R_{L,t}f(x), I t f ( x ) = π − ϱ /2 j = 0 ∑ L − 1 j ! t j ∫ T x X F x , z ( j ) ( 0 ) d z x + R L , t f ( x ) , R L , t f ( x ) : = π − ϱ / 2 t L ( L − 1 ) ! ∫ 0 1 ( 1 − θ ) L − 1 ∫ T x X F x , z ( L ) ( θ t ) d z x d θ . R_{L,t}f(x):=\frac{\pi^{-\varrho/2}t^L}{(L-1)!}\int_0^1(1-\theta)^{L-1}\int_{T_xX}F_{x,z}^{(L)}(\theta t)\,dz_x\,d\theta. R L , t f ( x ) := ( L − 1 )! π − ϱ /2 t L ∫ 0 1 ( 1 − θ ) L − 1 ∫ T x X F x , z ( L ) ( θ t ) d z x d θ . Applying (A.13), we obtain
∣ R L , t f ( x ) ∣ ≤ C ∣ t ∣ L ∑ ℓ = 0 L ∫ 0 1 ( 1 − θ ) L − 1 ∫ T x X ( 1 + ∥ z ∥ 2 ) M / 2 exp ( − c ∥ z ∥ 2 ) × 1 { ∥ θ t z ∥ ≤ 2 δ } ∣ ∇ ℓ f ∣ ( E x ( θ t z ) ) d z x d θ . (38) |R_{L,t}f(x)|\leq C|t|^L\sum_{\ell=0}^{L}\int_0^1(1-\theta)^{L-1}\int_{T_xX}(1+\|z\|^2)^{M/2}\exp(-c\|z\|^2)
\times\mathbf{1}_{\{\|\theta tz\|\leq2\delta\}}|\nabla^\ell f|(\mathcal{E}_x(\theta tz))\,dz_x\,d\theta. \tag*{(38)} ∣ R L , t f ( x ) ∣ ≤ C ∣ t ∣ L ℓ = 0 ∑ L ∫ 0 1 ( 1 − θ ) L − 1 ∫ T x X ( 1 + ∥ z ∥ 2 ) M /2 exp ( − c ∥ z ∥ 2 ) × 1 { ∥ θ t z ∥ ≤ 2 δ } ∣ ∇ ℓ f ∣ ( E x ( θ t z )) d z x d θ . (38) Choose finitely many pairs of coordinate neighborhoods U a ⋐ V a U_a\Subset V_a U a ⋐ V a U a U_a U a V a V_a V a φ a ( V a ) \varphi_a(V_a) φ a ( V a ) a a a e 1 , … , e ϱ e_1,\ldots,e_\varrho e 1 , … , e ϱ V a V_a V a θ ∈ [ 0 , 1 ] \theta\in[0,1] θ ∈ [ 0 , 1 ] ∣ t ∣ ≤ 1 |t|\leq1 ∣ t ∣ ≤ 1 z ∈ R ϱ z\in\mathbb{R}^{\varrho} z ∈ R ϱ ∥ θ t z ∥ ≤ 2 δ \|\theta tz\|\leq2\delta ∥ θ t z ∥ ≤ 2 δ
Θ θ , t , z ( x ) = E x ( θ t ∑ i = 1 ϱ z i e i ( x ) ) , x ∈ V a . \Theta_{\theta,t,z}(x)=\mathcal{E}_x\left(\theta t\sum_{i=1}^{\varrho}z_i e_i(x)\right),\qquad x\in V_a. Θ θ , t , z ( x ) = E x ( θ t i = 1 ∑ ϱ z i e i ( x ) ) , x ∈ V a . After decreasing δ \delta δ Θ θ , t , z ( U a ) ⊂ V a \Theta_{\theta,t,z}(U_a)\subset V_a Θ θ , t , z ( U a ) ⊂ V a φ a ∘ Θ θ , t , z ∘ φ a − 1 \varphi_a\circ\Theta_{\theta,t,z}\circ\varphi_a^{-1} φ a ∘ Θ θ , t , z ∘ φ a − 1 C 1 C^1 C 1 φ a ( U a ‾ ) \varphi_a(\overline{U_a}) φ a ( U a ) Θ θ , t , z \Theta_{\theta,t,z} Θ θ , t , z U a U_a U a
0 < c ≤ ∣ det D x Θ θ , t , z ∣ ≤ C , x ∈ U a . 0<c\leq|\det D_x\Theta_{\theta,t,z}|\leq C,\qquad x\in U_a. 0 < c ≤ ∣ det D x Θ θ , t , z ∣ ≤ C , x ∈ U a . Here ∣ det D x Θ θ , t , z ∣ |\det D_x\Theta_{\theta,t,z}| ∣ det D x Θ θ , t , z ∣ a , x , θ , t , z a,x,\theta,t,z a , x , θ , t , z 0 ≤ ℓ ≤ L 0\leq\ell\leq L 0 ≤ ℓ ≤ L Θ θ , t , z \Theta_{\theta,t,z} Θ θ , t , z
∫ U a ∣ ∇ ℓ f ∣ 2 ( Θ θ , t , z ( x ) ) d V ( x ) ≤ c − 1 ∫ U a ∣ ∇ ℓ f ∣ 2 ( Θ θ , t , z ( x ) ) ∣ det D x Θ θ , t , z ∣ d V ( x ) = c − 1 ∫ Θ θ , t , z ( U a ) ∣ ∇ ℓ f ∣ 2 ( y ) d V ( y ) ≤ c − 1 ∫ V a ∣ ∇ ℓ f ∣ 2 ( y ) d V ( y ) . \begin{aligned}
\int_{U_a}|\nabla^\ell f|^2(\Theta_{\theta,t,z}(x))\,dV(x)
\leq c^{-1}\int_{U_a}|\nabla^\ell f|^2(\Theta_{\theta,t,z}(x))|\det D_x\Theta_{\theta,t,z}|\,dV(x) \\
&=c^{-1}\int_{\Theta_{\theta,t,z}(U_a)}|\nabla^\ell f|^2(y)\,dV(y)
\leq c^{-1}\int_{V_a}|\nabla^\ell f|^2(y)\,dV(y).
\end{aligned} ∫ U a ∣ ∇ ℓ f ∣ 2 ( Θ θ , t , z ( x )) d V ( x ) ≤ c − 1 ∫ U a ∣ ∇ ℓ f ∣ 2 ( Θ θ , t , z ( x )) ∣ det D x Θ θ , t , z ∣ d V ( x ) = c − 1 ∫ Θ θ , t , z ( U a ) ∣ ∇ ℓ f ∣ 2 ( y ) d V ( y ) ≤ c − 1 ∫ V a ∣ ∇ ℓ f ∣ 2 ( y ) d V ( y ) . Taking square roots yields
∥ ∇ ℓ f ∘ Θ θ , t , z ∥ L 2 ( U a ) ≤ C ∥ ∇ ℓ f ∥ L 2 ( V a ) . (39) \|\nabla^\ell f\circ\Theta_{\theta,t,z}\|_{L^2(U_a)}\leq C\|\nabla^\ell f\|_{L^2(V_a)}. \tag*{(39)} ∥ ∇ ℓ f ∘ Θ θ , t , z ∥ L 2 ( U a ) ≤ C ∥ ∇ ℓ f ∥ L 2 ( V a ) . (39) On each U a U_a U a T x X T_xX T x X R ϱ \mathbb{R}^{\varrho} R ϱ ∥ θ t z ∥ ≤ 2 δ \|\theta tz\|\leq2\delta ∥ θ t z ∥ ≤ 2 δ x x x L 2 ( U a ) L_2(U_a) L 2 ( U a ) θ \theta θ z z z
∥ R L , t f ∥ L 2 ( U a ) ≤ C ∣ t ∣ L ∑ ℓ = 0 L ∫ 0 1 ( 1 − θ ) L − 1 ∫ { z ∈ R ϱ : ∥ θ t z ∥ ≤ 2 δ } ( 1 + ∥ z ∥ 2 ) M / 2 exp ( − c ∥ z ∥ 2 ) × ∥ ∇ ℓ f ∘ Θ θ , t , z ∥ L 2 ( U a ) d z d θ ≤ C ∣ t ∣ L ∑ ℓ = 0 L ∥ ∇ ℓ f ∥ L 2 ( V a ) ∫ 0 1 ( 1 − θ ) L − 1 ∫ R ϱ ( 1 + ∥ z ∥ 2 ) M / 2 exp ( − c ∥ z ∥ 2 ) d z d θ . \begin{aligned}
\lVert R_{L,t}f\rVert_{L_2(U_a)}
&\le C|t|^L\sum_{\ell=0}^{L}\int_0^1(1-\theta)^{L-1}\int_{\{z\in\mathbb{R}^{\varrho}:\lVert\theta tz\rVert\le2\delta\}}(1+\lVert z\rVert^2)^{M/2}\exp(-c\lVert z\rVert^2)\\
&\qquad\times\lVert\nabla^\ell f\circ\Theta_{\theta,t,z}\rVert_{L_2(U_a)}\,dz\,d\theta\\
&\le C|t|^L\sum_{\ell=0}^{L}\lVert\nabla^\ell f\rVert_{L_2(V_a)}\int_0^1(1-\theta)^{L-1}\int_{\mathbb{R}^{\varrho}}(1+\lVert z\rVert^2)^{M/2}\exp(-c\lVert z\rVert^2)\,dz\,d\theta.
\end{aligned} ∥ R L , t f ∥ L 2 ( U a ) ≤ C ∣ t ∣ L ℓ = 0 ∑ L ∫ 0 1 ( 1 − θ ) L − 1 ∫ { z ∈ R ϱ : ∥ θ t z ∥ ≤ 2 δ } ( 1 + ∥ z ∥ 2 ) M /2 exp ( − c ∥ z ∥ 2 ) × ∥ ∇ ℓ f ∘ Θ θ , t , z ∥ L 2 ( U a ) d z d θ ≤ C ∣ t ∣ L ℓ = 0 ∑ L ∥ ∇ ℓ f ∥ L 2 ( V a ) ∫ 0 1 ( 1 − θ ) L − 1 ∫ R ϱ ( 1 + ∥ z ∥ 2 ) M /2 exp ( − c ∥ z ∥ 2 ) d z d θ . Both scalar integrals are finite and independent of t t t C C C U a U_a U a X X X
∥ R L , t f ∥ L 2 ( X ) ≤ ∑ a ∥ R L , t f ∥ L 2 ( U a ) ≤ C ∣ t ∣ L ∑ ℓ = 0 L ∥ ∇ ℓ f ∥ L 2 ( X ) ≤ C ∣ t ∣ L ∥ f ∥ H L ( X ) . (40) \lVert R_{L,t}f\rVert_{L_2(X)}\le\sum_a\lVert R_{L,t}f\rVert_{L_2(U_a)}\le C|t|^L\sum_{\ell=0}^{L}\lVert\nabla^\ell f\rVert_{L_2(X)}\le C|t|^L\lVert f\rVert_{H^L(X)}. \tag*{(40)} ∥ R L , t f ∥ L 2 ( X ) ≤ a ∑ ∥ R L , t f ∥ L 2 ( U a ) ≤ C ∣ t ∣ L ℓ = 0 ∑ L ∥ ∇ ℓ f ∥ L 2 ( X ) ≤ C ∣ t ∣ L ∥ f ∥ H L ( X ) . (40) Note that T t = T ∣ t ∣ l o c \mathcal{T}_t=T^{\mathrm{loc}}_{|t|} T t = T ∣ t ∣ loc t t t
A r f : = 1 ( 2 r ) ! ∂ t 2 r T t f ∣ t = 0 . A_r f:=\frac{1}{(2r)!}\left.\partial_t^{2r}\mathcal{T}_t f\right|_{t=0}. A r f := ( 2 r )! 1 ∂ t 2 r T t f t = 0 . This definition is independent of the truncation order N N N χ 0 \chi_0 χ 0
To compute the term where all 2 r 2r 2 r f ( E x ( t z ) ) f(\mathcal{E}_x(tz)) f ( E x ( t z )) x x x u u u ( ∇ 2 r f ) x ( z , … , z ) (\nabla^{2r}f)_x(z,\ldots,z) ( ∇ 2 r f ) x ( z , … , z ) 2 r 2r 2 r f ∘ E x f\circ\mathcal{E}_x f ∘ E x z z z z i z_i z i
π − 1 / 2 ∫ R exp ( − s 2 ) s 2 k d s = ( 2 k ) ! 4 k k ! , k ≥ 0. \pi^{-1/2}\int_{\mathbb{R}}\exp(-s^2)s^{2k}\,ds=\frac{(2k)!}{4^k k!},\qquad k\ge0. π − 1/2 ∫ R exp ( − s 2 ) s 2 k d s = 4 k k ! ( 2 k )! , k ≥ 0. Thus, summing over nonnegative integers k 1 , … , k ϱ k_1,\ldots,k_\varrho k 1 , … , k ϱ r r r
π − ϱ / 2 ( 2 r ) ! ∫ R ϱ exp ( − ∥ z ∥ 2 ) ( ∇ 2 r f ) x ( z , … , z ) d z = 1 4 r ∑ k 1 + ⋯ + k ϱ = r ∂ u 1 2 k 1 ⋯ ∂ u ϱ 2 k ϱ ( f ∘ E x ) ( 0 ) k 1 ! ⋯ k ϱ ! = 1 4 r r ! ( ∑ i = 1 ϱ ∂ u i 2 ) r ( f ∘ E x ) ( 0 ) . \begin{aligned}
\frac{\pi^{-\varrho/2}}{(2r)!}\int_{\mathbb{R}^{\varrho}}\exp(-\lVert z\rVert^2)(\nabla^{2r}f)_x(z,\ldots,z)\,dz
&=\frac{1}{4^r}\sum_{k_1+\cdots+k_\varrho=r}\frac{\partial_{u_1}^{2k_1}\cdots\partial_{u_\varrho}^{2k_\varrho}(f\circ\mathcal{E}_x)(0)}{k_1!\cdots k_\varrho!}\\
&=\frac{1}{4^r r!}\left(\sum_{i=1}^{\varrho}\partial_{u_i}^2\right)^r(f\circ\mathcal{E}_x)(0).
\end{aligned} ( 2 r )! π − ϱ /2 ∫ R ϱ exp ( − ∥ z ∥ 2 ) ( ∇ 2 r f ) x ( z , … , z ) d z = 4 r 1 k 1 + ⋯ + k ϱ = r ∑ k 1 ! ⋯ k ϱ ! ∂ u 1 2 k 1 ⋯ ∂ u ϱ 2 k ϱ ( f ∘ E x ) ( 0 ) = 4 r r ! 1 ( i = 1 ∑ ϱ ∂ u i 2 ) r ( f ∘ E x ) ( 0 ) . By the coordinate formula for Δ X \Delta_X Δ X [12 Proposition 2.46 and Proposition 5.24] , its second-order coefficients agree with those of the Euclidean Laplacian to first order at the origin, while its first-order coefficients vanish there. Consequently, the terms of order 2 r 2r 2 r 2 r − 1 2r-1 2 r − 1 r r r r ≥ 1 r\ge1 r ≥ 1
1 4 r r ! ( ∑ i = 1 ϱ ∂ u i 2 ) r ( f ∘ E x ) ( 0 ) = 1 4 r r ! ( Δ X r f ) ( x ) + ( B ~ r f ) ( x ) , B ~ r ∈ Diff 2 r − 2 ( X ) . \frac{1}{4^r r!}\left(\sum_{i=1}^{\varrho}\partial_{u_i}^2\right)^r(f\circ\mathcal{E}_x)(0)=\frac{1}{4^r r!}(\Delta_X^r f)(x)+(\widetilde{B}_r f)(x),\qquad\widetilde{B}_r\in\operatorname{Diff}^{2r-2}(X). 4 r r ! 1 ( i = 1 ∑ ϱ ∂ u i 2 ) r ( f ∘ E x ) ( 0 ) = 4 r r ! 1 ( Δ X r f ) ( x ) + ( B r f ) ( x ) , B r ∈ Diff 2 r − 2 ( X ) . We now consider the remaining Leibniz terms, in which at least one derivative falls on
exp ( − Ψ x ( t , z ) ) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) . \exp(-\Psi_x(t,z))J_x(tz)\chi_0(t^2\lVert z\rVert^2). exp ( − Ψ x ( t , z )) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) . Since q x q_x q x J x J_x J x x ∈ X x\in X x ∈ X
D u J x ( 0 ) = 0 , D u 3 q x ( 0 ) = 0. D_uJ_x(0)=0,\qquad D_u^3q_x(0)=0. D u J x ( 0 ) = 0 , D u 3 q x ( 0 ) = 0. Differentiating (A.10) with respect to t t t x , z x,z x , z
∂ t Ψ x ( 0 , z ) = ∫ 0 1 θ ( 1 − θ ) D u 3 q x ( 0 ) [ z , z , z ] d θ = 0. \partial_t\Psi_x(0,z)=\int_0^1\theta(1-\theta)D_u^3q_x(0)[z,z,z]\,d\theta=0. ∂ t Ψ x ( 0 , z ) = ∫ 0 1 θ ( 1 − θ ) D u 3 q x ( 0 ) [ z , z , z ] d θ = 0. Together with the vanishing of D u J x ( 0 ) D_uJ_x(0) D u J x ( 0 )
∂ t [ exp ( − Ψ x ( t , z ) ) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) ] ∣ 0 = 0. \left.\partial_t\left[\exp(-\Psi_x(t,z))J_x(tz)\chi_0(t^2\lVert z\rVert^2)\right]\right|_0=0. ∂ t [ exp ( − Ψ x ( t , z )) J x ( t z ) χ 0 ( t 2 ∥ z ∥ 2 ) ] 0 = 0. Thus the terms with exactly one derivative on this factor vanish. Every nonzero remaining term has at least two derivatives on this factor and hence at most 2 r − 2 2r-2 2 r − 2 f f f A r A_r A r r ≥ 1 r\ge1 r ≥ 1
Now we are ready to prove the final estimate (11) . For f ∈ C ∞ ( X ) f\in C^\infty(X) f ∈ C ∞ ( X ) 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1
T γ f = T γ f a r f + T γ l o c f = T γ f a r f + I γ f . T_\gamma f=T_\gamma^{\mathrm{far}}f+T_\gamma^{\mathrm{loc}}f=T_\gamma^{\mathrm{far}}f+I_\gamma f. T γ f = T γ far f + T γ loc f = T γ far f + I γ f . The Taylor expansion of I t f I_t f I t f 2 N + 1 2N+1 2 N + 1 A r A_r A r
I γ f = ∑ r = 0 N γ 2 r A r f + R L , γ f . I_\gamma f=\sum_{r=0}^{N}\gamma^{2r}A_rf+R_{L,\gamma}f. I γ f = r = 0 ∑ N γ 2 r A r f + R L , γ f . Substituting this identity into the decomposition yields
T γ f − ∑ r = 0 N γ 2 r A r f = T γ f a r f + R L , γ f . T_\gamma f-\sum_{r=0}^{N}\gamma^{2r}A_rf=T_\gamma^{\mathrm{far}}f+R_{L,\gamma}f. T γ f − r = 0 ∑ N γ 2 r A r f = T γ far f + R L , γ f . By (A.8) and the fact that γ − ϱ − L exp ( − c δ 2 / γ 2 ) \gamma^{-\varrho-L}\exp(-c_\delta^2/\gamma^2) γ − ϱ − L exp ( − c δ 2 / γ 2 ) 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1
∥ T γ f a r f ∥ L 2 ( X ) ≤ C X , δ γ − ϱ exp ( − c δ 2 / γ 2 ) ∥ f ∥ L 2 ( X ) ≤ C γ L ∥ f ∥ L 2 ( X ) . \lVert T_\gamma^{\mathrm{far}}f\rVert_{L^2(X)}
\le C_{X,\delta}\gamma^{-\varrho}\exp(-c_\delta^2/\gamma^2)\lVert f\rVert_{L^2(X)}
\le C\gamma^L\lVert f\rVert_{L^2(X)}. ∥ T γ far f ∥ L 2 ( X ) ≤ C X , δ γ − ϱ exp ( − c δ 2 / γ 2 ) ∥ f ∥ L 2 ( X ) ≤ C γ L ∥ f ∥ L 2 ( X ) . The local remainder estimate (A.16), evaluated at γ \gamma γ
∥ R L , γ f ∥ L 2 ( X ) ≤ C γ L ∥ f ∥ H L ( X ) . \lVert R_{L,\gamma}f\rVert_{L^2(X)}\le C\gamma^L\lVert f\rVert_{H^L(X)}. ∥ R L , γ f ∥ L 2 ( X ) ≤ C γ L ∥ f ∥ H L ( X ) . Thus,
∥ T γ f − ∑ r = 0 N γ 2 r A r f ∥ L 2 ( X ) ≤ ∥ T γ f a r f ∥ L 2 ( X ) + ∥ R L , γ f ∥ L 2 ( X ) ≤ C γ L ( ∥ f ∥ L 2 ( X ) + ∥ f ∥ H L ( X ) ) ≤ C N , X , d γ 2 N + 2 ∥ f ∥ H 2 N + 2 ( X ) . \left\lVert T_\gamma f-\sum_{r=0}^{N}\gamma^{2r}A_rf\right\rVert_{L^2(X)}
\le\lVert T_\gamma^{\mathrm{far}}f\rVert_{L^2(X)}+\lVert R_{L,\gamma}f\rVert_{L^2(X)}
\le C\gamma^L\left(\lVert f\rVert_{L^2(X)}+\lVert f\rVert_{H^L(X)}\right)
\le C_{N,X,d}\gamma^{2N+2}\lVert f\rVert_{H^{2N+2}(X)}. T γ f − r = 0 ∑ N γ 2 r A r f L 2 ( X ) ≤ ∥ T γ far f ∥ L 2 ( X ) + ∥ R L , γ f ∥ L 2 ( X ) ≤ C γ L ( ∥ f ∥ L 2 ( X ) + ∥ f ∥ H L ( X ) ) ≤ C N , X , d γ 2 N + 2 ∥ f ∥ H 2 N + 2 ( X ) . This proves (11) for smooth f f f f ∈ H L ( X ) f\in H^L(X) f ∈ H L ( X ) f m ∈ C ∞ ( X ) f_m\in C^\infty(X) f m ∈ C ∞ ( X ) f m → f f_m\to f f m → f H L ( X ) H^L(X) H L ( X ) L 2 ( X ) L^2(X) L 2 ( X ) γ \gamma γ T γ : L 2 ( X ) → L 2 ( X ) T_\gamma:L^2(X)\to L^2(X) T γ : L 2 ( X ) → L 2 ( X ) T γ f m → T γ f T_\gamma f_m\to T_\gamma f T γ f m → T γ f L 2 ( X ) L^2(X) L 2 ( X ) A r A_r A r 2 r ≤ L 2r\le L 2 r ≤ L H L ( X ) H^L(X) H L ( X ) L 2 ( X ) L^2(X) L 2 ( X ) A r f m → A r f A_rf_m\to A_rf A r f m → A r f L 2 ( X ) L^2(X) L 2 ( X ) f m f_m f m (11) for every f ∈ H L ( X ) f\in H^L(X) f ∈ H L ( X ) □ \square □
Proof of Theorem 4.3. Set
N : = ⌈ α 2 ⌉ , R : = 2 N + 2. N:=\left\lceil\frac{\alpha}{2}\right\rceil,\qquad R:=2N+2. N := ⌈ 2 α ⌉ , R := 2 N + 2. Then
R > α , 2 N ≤ ⌊ α ⌋ = s − 1. R>\alpha,\qquad2N\le\lfloor\alpha\rfloor=s-1. R > α , 2 N ≤ ⌊ α ⌋ = s − 1. The definition (9) and the identities (10) give, for every γ > 0 \gamma>0 γ > 0
S γ , s − I = ∑ j = 1 s c j [ T j γ − ∑ r = 0 N ( j γ ) 2 r A r ] . S_{\gamma,s}-I=\sum_{j=1}^{s}c_j\left[T_{j\gamma}-\sum_{r=0}^{N}(j\gamma)^{2r}A_r\right]. S γ , s − I = j = 1 ∑ s c j [ T j γ − r = 0 ∑ N ( j γ ) 2 r A r ] . Suppose first that s γ ≤ 1 s\gamma\le1 s γ ≤ 1 j γ ≤ 1 j\gamma\le1 j γ ≤ 1 1 ≤ j ≤ s 1 \le j \le s 1 ≤ j ≤ s (11) to each term on the right and using the triangle inequality yields, for every f ∈ H R ( X ) f \in H^{R}(X) f ∈ H R ( X )
∥ ( S γ , s − I ) f ∥ L 2 ( X ) ≤ C α γ R ∥ f ∥ H R ( X ) . \left\|(S_{\gamma,s}-I)f\right\|_{L_2(X)} \le C_{\alpha}\gamma^{R}\|f\|_{H^{R}(X)}. ∥ ( S γ , s − I ) f ∥ L 2 ( X ) ≤ C α γ R ∥ f ∥ H R ( X ) . Since the operators T γ : L 2 ( X ) → L 2 ( X ) T_{\gamma}: L_2(X) \to L_2(X) T γ : L 2 ( X ) → L 2 ( X ) γ > 0 \gamma> 0 γ > 0 (9) and the triangle inequality give
∥ S γ , s − I ∥ L 2 ( X ) → L 2 ( X ) ≤ C α . (41) \left\|S_{\gamma,s}-I\right\|_{L_2(X)\to L_2(X)} \le C_{\alpha}. \tag*{(41)} ∥ S γ , s − I ∥ L 2 ( X ) → L 2 ( X ) ≤ C α . (41) Hence, for every decomposition f = f 0 + f 1 f=f_0+f_1 f = f 0 + f 1 f 0 ∈ L 2 ( X ) f_0\in L_2(X) f 0 ∈ L 2 ( X ) f 1 ∈ H R ( X ) f_1\in H^{R}(X) f 1 ∈ H R ( X )
∥ ( S γ , s − I ) f ∥ L 2 ( X ) ≤ C α ( ∥ f 0 ∥ L 2 ( X ) + γ R ∥ f 1 ∥ H R ( X ) ) . \left\|(S_{\gamma,s}-I)f\right\|_{L_2(X)}
\le C_{\alpha}\left(\|f_0\|_{L_2(X)}+\gamma^{R}\|f_1\|_{H^{R}(X)}\right). ∥ ( S γ , s − I ) f ∥ L 2 ( X ) ≤ C α ( ∥ f 0 ∥ L 2 ( X ) + γ R ∥ f 1 ∥ H R ( X ) ) . Taking the infimum over all decompositions yields
∥ ( S γ , s − I ) f ∥ L 2 ( X ) ≤ C α K ( γ R , f ; L 2 ( X ) , H R ( X ) ) . \left\|(S_{\gamma,s}-I)f\right\|_{L_2(X)}
\le C_{\alpha}K(\gamma^{R},f;L_2(X),H^{R}(X)). ∥ ( S γ , s − I ) f ∥ L 2 ( X ) ≤ C α K ( γ R , f ; L 2 ( X ) , H R ( X )) . Since R > α R>\alpha R > α (3) with m = R m=R m = R
K ( γ R , f ; L 2 ( X ) , H R ( X ) ) ≤ C α , X γ α ∥ f ∥ B 2 , ∞ α ( X ) . K(\gamma^{R},f;L_2(X),H^{R}(X))
\le C_{\alpha,X}\gamma^{\alpha}\|f\|_{B^{\alpha}_{2,\infty}(X)}. K ( γ R , f ; L 2 ( X ) , H R ( X )) ≤ C α , X γ α ∥ f ∥ B 2 , ∞ α ( X ) . This proves (12) for s γ ≤ 1 s\gamma\le1 s γ ≤ 1 1 / s < γ ≤ 1 1/s<\gamma\le1 1/ s < γ ≤ 1 B 2 , ∞ α ( X ) ↪ L 2 ( X ) B^{\alpha}_{2,\infty}(X)\hookrightarrow L_2(X) B 2 , ∞ α ( X ) ↪ L 2 ( X ) γ α \gamma^{\alpha} γ α s − α s^{-\alpha} s − α
Proof of Theorem 4.4. For P X P_X P X x x x
ℓ x ( t ) : = η ( x ) log ( 1 + e − t ) + ( 1 − η ( x ) ) log ( 1 + e t ) . \ell_x(t):=\eta(x)\log(1+e^{-t})+(1-\eta(x))\log(1+e^t). ℓ x ( t ) := η ( x ) log ( 1 + e − t ) + ( 1 − η ( x )) log ( 1 + e t ) . Since f ∗ ( x ) f^*(x) f ∗ ( x )
ℓ x ′ ( f ∗ ( x ) ) = 0 , ℓ x ′ ′ ( t ) = e t ( 1 + e t ) 2 ≤ 1 4 . \ell_x'(f^*(x))=0,\qquad\ell_x''(t)=\frac{e^t}{(1+e^t)^2}\le\frac{1}{4}. ℓ x ′ ( f ∗ ( x )) = 0 , ℓ x ′′ ( t ) = ( 1 + e t ) 2 e t ≤ 4 1 . Taylor’s formula therefore gives a quadratic bound on the conditional excess risk. Combining it with the 1-Lipschitz property of the logistic loss, for every t ∈ R t\in\mathbb{R} t ∈ R 1 ≤ r ≤ 2 1\le r\le2 1 ≤ r ≤ 2
0 ≤ ℓ x ( t ) − ℓ x ( f ∗ ( x ) ) ≤ min { ∣ t − f ∗ ( x ) ∣ , 1 8 ∣ t − f ∗ ( x ) ∣ 2 } ≤ 8 1 − r ∣ t − f ∗ ( x ) ∣ r . 0\le\ell_x(t)-\ell_x(f^*(x))
\le\min\left\{|t-f^*(x)|,\frac{1}{8}|t-f^*(x)|^2\right\}
\le8^{1-r}|t-f^*(x)|^r. 0 ≤ ℓ x ( t ) − ℓ x ( f ∗ ( x )) ≤ min { ∣ t − f ∗ ( x ) ∣ , 8 1 ∣ t − f ∗ ( x ) ∣ 2 } ≤ 8 1 − r ∣ t − f ∗ ( x ) ∣ r . Let p ′ p' p ′ p p p r : = 2 / p ′ = 2 ( 1 − 1 / p ) r:=2/p'=2(1-1/p) r := 2/ p ′ = 2 ( 1 − 1/ p ) 1 ≤ p ′ ≤ 2 1\le p'\le2 1 ≤ p ′ ≤ 2 1 ≤ r ≤ 2 1\le r\le2 1 ≤ r ≤ 2 r p ′ = 2 rp'=2 r p ′ = 2 f f f f − f ∗ ∈ L 2 ( X ) f-f^*\in L_2(X) f − f ∗ ∈ L 2 ( X )
R ( f ) − R ∗ ≤ 8 1 − r ∫ X ∣ f − f ∗ ∣ r g d V ≤ 8 1 − r ∥ g ∥ L p ( X ) ( ∫ X ∣ f − f ∗ ∣ r p ′ d V ) 1 / p ′ = 8 1 − r ∥ g ∥ L p ( X ) ∥ f − f ∗ ∥ L 2 ( X ) . (42) \begin{aligned}
\mathcal{R}(f)-\mathcal{R}^*
&\le8^{1-r}\int_X |f-f^*|^r g\,dV \\
&\le8^{1-r}\|g\|_{L_p(X)}
\left(\int_X |f-f^*|^{rp'}\,dV\right)^{1/p'} \\
&=8^{1-r}\|g\|_{L_p(X)}\|f-f^*\|_{L_2(X)}. \tag*{(42)}
\end{aligned} R ( f ) − R ∗ ≤ 8 1 − r ∫ X ∣ f − f ∗ ∣ r g d V ≤ 8 1 − r ∥ g ∥ L p ( X ) ( ∫ X ∣ f − f ∗ ∣ r p ′ d V ) 1/ p ′ = 8 1 − r ∥ g ∥ L p ( X ) ∥ f − f ∗ ∥ L 2 ( X ) . (42) Take S γ , s f ∗ ∈ H γ ( X ) S_{\gamma,s}f^*\in H_{\gamma}(X) S γ , s f ∗ ∈ H γ ( X ) s s s α \alpha α
R ( S γ , s f ∗ ) − R ∗ ≤ 8 1 − r ∥ g ∥ L p ( X ) ∥ S γ , s f ∗ − f ∗ ∥ L 2 ( X ) ≤ C α , p , X , d γ 2 α ( 1 − 1 / p ) ∥ g ∥ L p ( X ) ∥ f ∗ ∥ B 2 , ∞ 2 ( 1 − 1 / p ) ( X ) . \begin{aligned}
\mathcal{R}(S_{\gamma,s}f^*)-\mathcal{R}^*
&\le8^{1-r}\|g\|_{L_p(X)}\|S_{\gamma,s}f^*-f^*\|_{L_2(X)} \\
&\le C_{\alpha,p,X,d}\gamma^{2\alpha(1-1/p)}
\|g\|_{L_p(X)}\|f^*\|_{B^{2(1-1/p)}_{2,\infty}(X)}.
\end{aligned} R ( S γ , s f ∗ ) − R ∗ ≤ 8 1 − r ∥ g ∥ L p ( X ) ∥ S γ , s f ∗ − f ∗ ∥ L 2 ( X ) ≤ C α , p , X , d γ 2 α ( 1 − 1/ p ) ∥ g ∥ L p ( X ) ∥ f ∗ ∥ B 2 , ∞ 2 ( 1 − 1/ p ) ( X ) . Moreover, Theorem 4.1 gives
λ ∥ S γ , s f ∗ ∥ H γ ( X ) 2 ≤ C α , X , d λ γ − ϱ ∥ f ∗ ∥ L 2 ( X ) 2 . \lambda\|S_{\gamma,s}f^*\|_{H_{\gamma}(X)}^2
\le C_{\alpha,X,d}\lambda\gamma^{-\varrho}\|f^*\|_{L_2(X)}^2. λ ∥ S γ , s f ∗ ∥ H γ ( X ) 2 ≤ C α , X , d λ γ − ϱ ∥ f ∗ ∥ L 2 ( X ) 2 . Substitution into (13) proves (14) .
Proof of Proposition 4.5. (i) Set θ : = α / β ∈ ( 0 , 1 ] \theta:= \alpha/\beta\in(0,1] θ := α / β ∈ ( 0 , 1 ] a , b > 0 a,b>0 a , b > 0 log ( 1 + s ) ≤ C θ s θ \log(1+s) \le C_{\theta}s^{\theta} log ( 1 + s ) ≤ C θ s θ s ≥ 0 s \ge0 s ≥ 0
∣ log a − log b ∣ ≤ C θ ∣ a − b ∣ θ ( a − θ + b − θ ) . (43) |\log a-\log b| \le C_{\theta}|a-b|^{\theta}\left(a^{-\theta}+b^{-\theta}\right). \tag*{(43)} ∣ log a − log b ∣ ≤ C θ ∣ a − b ∣ θ ( a − θ + b − θ ) . (43) Condition (15) implies that η \eta η ( 0 , 1 ) (0,1) ( 0 , 1 ) x ∈ X x\in X x ∈ X 0 < η ( x ) < 1 0<\eta(x)<1 0 < η ( x ) < 1
∣ f ∗ ( x ) ∣ ≤ − log ( η ( x ) ( 1 − η ( x ) ) ) ≤ C θ [ η ( x ) ( 1 − η ( x ) ) ] − θ , |f^{*}(x)|\le-\log(\eta(x)(1-\eta(x)))\le C_{\theta}[\eta(x)(1-\eta(x))]^{-\theta}, ∣ f ∗ ( x ) ∣ ≤ − log ( η ( x ) ( 1 − η ( x ))) ≤ C θ [ η ( x ) ( 1 − η ( x )) ] − θ , so f ∗ ∈ L 2 ( X ) f^{*}\in L_{2}(X) f ∗ ∈ L 2 ( X ) η \eta η 1 − η 1-\eta 1 − η η \eta η
∣ f ∗ ( x ) − f ∗ ( y ) ∣ ≤ C ∥ η ∥ C 0 , β ( X ) d X ( x , y ) α ( [ η ( x ) ( 1 − η ( x ) ) ] − θ + [ η ( y ) ( 1 − η ( y ) ) ] − θ ) . (44) \begin{aligned}
|f^{*}(x)-f^{*}(y)|
&\le C\|\eta\|_{C^{0,\beta}(X)}d_{X}(x,y)^{\alpha}
\bigl([\eta(x)(1-\eta(x))]^{-\theta}\\
&\qquad+[\eta(y)(1-\eta(y))]^{-\theta}\bigr). \tag*{(44)}
\end{aligned} ∣ f ∗ ( x ) − f ∗ ( y ) ∣ ≤ C ∥ η ∥ C 0 , β ( X ) d X ( x , y ) α ( [ η ( x ) ( 1 − η ( x )) ] − θ + [ η ( y ) ( 1 − η ( y )) ] − θ ) . (44) Use the fixed finite atlas { ( U ν , ϕ ν ) } ν = 1 J \{(U_{\nu},\phi_{\nu})\}_{\nu=1}^{J} {( U ν , ϕ ν ) } ν = 1 J { χ ν } ν = 1 J \{\chi_{\nu}\}_{\nu=1}^{J} { χ ν } ν = 1 J
F ν : = ( χ ν f ∗ ) ∘ ϕ ν − 1 , F_{\nu}:=(\chi_{\nu}f^{*})\circ\phi_{\nu}^{-1}, F ν := ( χ ν f ∗ ) ∘ ϕ ν − 1 , extended by zero to R ϱ \mathbb{R}^{\varrho} R ϱ supp χ ν \operatorname{supp}\chi_{\nu} supp χ ν U ν U_{\nu} U ν ∥ h ∥ \|h\| ∥ h ∥ u u u u + h u+h u + h u u u x : = ϕ ν − 1 ( u ) x:=\phi_{\nu}^{-1}(u) x := ϕ ν − 1 ( u ) y : = ϕ ν − 1 ( u + h ) y:=\phi_{\nu}^{-1}(u+h) y := ϕ ν − 1 ( u + h )
F ν ( u + h ) − F ν ( u ) = χ ν ( y ) f ∗ ( y ) − χ ν ( x ) f ∗ ( x ) = χ ν ( y ) ( f ∗ ( y ) − f ∗ ( x ) ) + ( χ ν ( y ) − χ ν ( x ) ) f ∗ ( x ) . \begin{aligned}
F_{\nu}(u+h)-F_{\nu}(u)
&=\chi_{\nu}(y)f^{*}(y)-\chi_{\nu}(x)f^{*}(x)\\
&=\chi_{\nu}(y)(f^{*}(y)-f^{*}(x))+(\chi_{\nu}(y)-\chi_{\nu}(x))f^{*}(x).
\end{aligned} F ν ( u + h ) − F ν ( u ) = χ ν ( y ) f ∗ ( y ) − χ ν ( x ) f ∗ ( x ) = χ ν ( y ) ( f ∗ ( y ) − f ∗ ( x )) + ( χ ν ( y ) − χ ν ( x )) f ∗ ( x ) . We apply (A.20) to the first term and use ∣ χ ν ( y ) − χ ν ( x ) ∣ ≤ C ∥ h ∥ |\chi_{\nu}(y)-\chi_{\nu}(x)|\le C\|h\| ∣ χ ν ( y ) − χ ν ( x ) ∣ ≤ C ∥ h ∥ L 2 L_{2} L 2
∥ F ν ( ⋅ + h ) − F ν ∥ L 2 ( R ϱ ) ≤ C ∥ η ∥ C 0 , β ( X ) θ ∥ h ∥ α ( ∫ X [ η ( 1 − η ) ] − 2 θ d V ) 1 2 + C ∥ h ∥ ∥ f ∗ ∥ L 2 ( X ) . \|F_{\nu}(\cdot+h)-F_{\nu}\|_{L_{2}(\mathbb{R}^{\varrho})}
\le C\|\eta\|_{C^{0,\beta}(X)}^{\theta}\|h\|^{\alpha}
\left(\int_{X}[\eta(1-\eta)]^{-2\theta}\,dV\right)^{\frac{1}{2}}
+C\|h\|\|f^{*}\|_{L_{2}(X)}. ∥ F ν ( ⋅ + h ) − F ν ∥ L 2 ( R ϱ ) ≤ C ∥ η ∥ C 0 , β ( X ) θ ∥ h ∥ α ( ∫ X [ η ( 1 − η ) ] − 2 θ d V ) 2 1 + C ∥ h ∥∥ f ∗ ∥ L 2 ( X ) . Since 0 < α < 1 0<\alpha<1 0 < α < 1 ∥ h ∥ α ∥ f ∗ ∥ L 2 ( X ) \|h\|^{\alpha}\|f^{*}\|_{L_{2}(X)} ∥ h ∥ α ∥ f ∗ ∥ L 2 ( X ) ∥ h ∥ ≤ 1 \|h\|\le1 ∥ h ∥ ≤ 1 2 ∥ F ν ∥ L 2 ( R ϱ ) 2\|F_{\nu}\|_{L_{2}(\mathbb{R}^{\varrho})} 2∥ F ν ∥ L 2 ( R ϱ ) [22 ] , Theorem 2.6.1 applies to each F ν F_{\nu} F ν 0 < α < 1 0<\alpha<1 0 < α < 1 X X X (3) by interpolating the localization and reconstruction maps over a finite atlas, see [22 ] , proof of Theorem 7.2.3, Step 2, and Section 7.3.1. The preceding estimates therefore give (16) .
(ii) Under the assumptions of the second case, we first establish the gradient estimates
∣ ∇ η ( x ) ∣ 2 ≤ C η ( x ) , ∣ ∇ η ( x ) ∣ 2 ≤ C ( 1 − η ( x ) ) . (45) |\nabla\eta(x)|^{2}\le C\eta(x),\qquad|\nabla\eta(x)|^{2}\le C(1-\eta(x)). \tag*{(45)} ∣∇ η ( x ) ∣ 2 ≤ C η ( x ) , ∣∇ η ( x ) ∣ 2 ≤ C ( 1 − η ( x )) . (45) To prove these estimates, let M : = 1 + ∥ ∇ 2 η ∥ L ∞ ( X ) M:=1+\|\nabla^{2}\eta\|_{L_{\infty}(X)} M := 1 + ∥ ∇ 2 η ∥ L ∞ ( X ) ∇ η ( x ) ≠ 0 \nabla\eta(x)\ne0 ∇ η ( x ) = 0 v : = ∇ η ( x ) / ∣ ∇ η ( x ) ∣ v:=\nabla\eta(x)/|\nabla\eta(x)| v := ∇ η ( x ) /∣∇ η ( x ) ∣ X X X t ↦ E x ( − t v ) t\mapsto\mathcal{E}_{x}(-tv) t ↦ E x ( − t v ) t ≥ 0 t\ge0 t ≥ 0
0 ≤ η ( E x ( − t v ) ) ≤ η ( x ) − t ∣ ∇ η ( x ) ∣ + M 2 t 2 . 0\le\eta(\mathcal{E}_{x}(-tv))\le\eta(x)-t|\nabla\eta(x)|+\frac{M}{2}t^{2}. 0 ≤ η ( E x ( − t v )) ≤ η ( x ) − t ∣∇ η ( x ) ∣ + 2 M t 2 . Choosing t = ∣ ∇ η ( x ) ∣ / M t=|\nabla\eta(x)|/M t = ∣∇ η ( x ) ∣/ M ∣ ∇ η ( x ) ∣ 2 ≤ 2 M η ( x ) |\nabla\eta(x)|^{2}\le2M\eta(x) ∣∇ η ( x ) ∣ 2 ≤ 2 M η ( x ) 1 − η 1-\eta 1 − η
To justify differentiation despite possible endpoint values of η \eta η
f ε : = log ( η + ε ) − log ( 1 − η + ε ) , 0 < ε ≤ 1. f_{\varepsilon}:=\log(\eta+\varepsilon)-\log(1-\eta+\varepsilon),\qquad0<\varepsilon\le1. f ε := log ( η + ε ) − log ( 1 − η + ε ) , 0 < ε ≤ 1. These functions belong to C m ( X ) C^{m}(X) C m ( X ) { ( U ν , ϕ ν ) } ν = 1 J \{(U_{\nu},\phi_{\nu})\}_{\nu=1}^{J} {( U ν , ϕ ν ) } ν = 1 J { χ ν } ν = 1 J \{\chi_{\nu}\}_{\nu=1}^{J} { χ ν } ν = 1 J ν \nu ν V ν V_{\nu} V ν supp χ ν \operatorname{supp}\chi_{\nu} supp χ ν V ν ⋐ U ν V_{\nu}\Subset U_{\nu} V ν ⋐ U ν u = ( u 1 , … , u ϱ ) ∈ ϕ ν ( V ν ) u=(u_{1},\ldots,u_{\varrho})\in\phi_{\nu}(V_{\nu}) u = ( u 1 , … , u ϱ ) ∈ ϕ ν ( V ν ) a = ( a 1 , … , a ϱ ) ∈ N 0 ϱ a=(a_{1},\ldots,a_{\varrho})\in\mathbb{N}_{0}^{\varrho} a = ( a 1 , … , a ϱ ) ∈ N 0 ϱ 1 ≤ ∣ a ∣ ≤ m 1\le|a|\le m 1 ≤ ∣ a ∣ ≤ m
∂ u a [ log ( η ∘ ϕ ν − 1 + ε ) ] ( u ) \partial_{u}^{a}\left[\log(\eta\circ\phi_{\nu}^{-1}+\varepsilon)\right](u) ∂ u a [ log ( η ∘ ϕ ν − 1 + ε ) ] ( u ) as a finite linear combination of terms of the form
( η ( ϕ ν − 1 ( u ) ) + ε ) − k ∏ i = 1 k [ ∂ u b i ( η ∘ ϕ ν − 1 ) ] ( u ) , b 1 + ⋯ + b k = a , b i ∈ N 0 d , ∣ b i ∣ ≥ 1. \left(\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{-k}\prod_{i=1}^{k}\left[\partial_u^{b_i}\left(\eta\circ\phi_\nu^{-1}\right)\right](u),\qquad b_1+\cdots+b_k=a,\quad b_i\in\mathbb{N}_0^d,\quad|b_i|\geq1. ( η ( ϕ ν − 1 ( u )) + ε ) − k i = 1 ∏ k [ ∂ u b i ( η ∘ ϕ ν − 1 ) ] ( u ) , b 1 + ⋯ + b k = a , b i ∈ N 0 d , ∣ b i ∣ ≥ 1. If ℓ \ell ℓ k k k
∣ a ∣ = ∑ i = 1 k ∣ b i ∣ ≥ ℓ + 2 ( k − ℓ ) = 2 k − ℓ . |a|=\sum_{i=1}^{k}|b_i|\geq\ell+2(k-\ell)=2k-\ell. ∣ a ∣ = i = 1 ∑ k ∣ b i ∣ ≥ ℓ + 2 ( k − ℓ ) = 2 k − ℓ . By (A.21) and the boundedness of the coordinate vector fields on V ν V_\nu V ν C η ( ϕ ν − 1 ( u ) ) + ε C\sqrt{\eta(\phi_\nu^{-1}(u))+\varepsilon} C η ( ϕ ν − 1 ( u )) + ε C ∥ η ∥ C m C\|\eta\|_{C^m} C ∥ η ∥ C m ℓ \ell ℓ ℓ / 2 \ell/2 ℓ /2 C C C
∣ ( η ( ϕ ν − 1 ( u ) ) + ε ) − k ∏ i = 1 k [ ∂ u b i ( η ∘ ϕ ν − 1 ) ] ( u ) ∣ ≤ C ( η ( ϕ ν − 1 ( u ) ) + ε ) − k ( η ( ϕ ν − 1 ( u ) ) + ε ) ℓ / 2 = C ( η ( ϕ ν − 1 ( u ) ) + ε ) − k + ℓ / 2 = C ( η ( ϕ ν − 1 ( u ) ) + ε ) − ∣ a ∣ / 2 ( η ( ϕ ν − 1 ( u ) ) + ε ) ∣ a ∣ / 2 − k + ℓ / 2 . \begin{aligned}
\left|\left(\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{-k}\prod_{i=1}^{k}\left[\partial_u^{b_i}\left(\eta\circ\phi_\nu^{-1}\right)\right](u)\right|
\leq C\left(\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{-k}\left(\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{\ell/2} \\
&=C\left(\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{-k+\ell/2} \\
&=C\left(\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{-|a|/2}\left(\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{|a|/2-k+\ell/2}.
\end{aligned} ( η ( ϕ ν − 1 ( u )) + ε ) − k i = 1 ∏ k [ ∂ u b i ( η ∘ ϕ ν − 1 ) ] ( u ) ≤ C ( η ( ϕ ν − 1 ( u )) + ε ) − k ( η ( ϕ ν − 1 ( u )) + ε ) ℓ /2 = C ( η ( ϕ ν − 1 ( u )) + ε ) − k + ℓ /2 = C ( η ( ϕ ν − 1 ( u )) + ε ) − ∣ a ∣/2 ( η ( ϕ ν − 1 ( u )) + ε ) ∣ a ∣/2 − k + ℓ /2 . Since k − ℓ / 2 ≤ ∣ a ∣ / 2 k-\ell/2\leq|a|/2 k − ℓ /2 ≤ ∣ a ∣/2 0 ≤ ℓ ≤ k 0\leq\ell\leq k 0 ≤ ℓ ≤ k
0 ≤ ∣ a ∣ 2 − k + ℓ 2 ≤ ∣ a ∣ 2 ≤ m 2 . 0\leq\frac{|a|}{2}-k+\frac{\ell}{2}\leq\frac{|a|}{2}\leq\frac{m}{2}. 0 ≤ 2 ∣ a ∣ − k + 2 ℓ ≤ 2 ∣ a ∣ ≤ 2 m . Together with 0 < η ( ϕ ν − 1 ( u ) ) + ε ≤ 2 0<\eta(\phi_\nu^{-1}(u))+\varepsilon\leq2 0 < η ( ϕ ν − 1 ( u )) + ε ≤ 2
( η ( ϕ ν − 1 ( u ) ) + ε ) ∣ a ∣ / 2 − k + ℓ / 2 ≤ 2 m / 2 . \left(\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{|a|/2-k+\ell/2}\leq2^{m/2}. ( η ( ϕ ν − 1 ( u )) + ε ) ∣ a ∣/2 − k + ℓ /2 ≤ 2 m /2 . Absorbing 2 m / 2 2^{m/2} 2 m /2 C C C C ( η ( ϕ ν − 1 ( u ) ) + ε ) − ∣ a ∣ / 2 C(\eta(\phi_\nu^{-1}(u))+\varepsilon)^{-|a|/2} C ( η ( ϕ ν − 1 ( u )) + ε ) − ∣ a ∣/2 ε \varepsilon ε ( 1 − η ) ∘ ϕ ν − 1 (1-\eta)\circ\phi_\nu^{-1} ( 1 − η ) ∘ ϕ ν − 1
∣ ∂ u a ( f ε ∘ ϕ ν − 1 ) ( u ) ∣ ≤ C [ ( η ( ϕ ν − 1 ( u ) ) + ε ) − ∣ a ∣ / 2 + ( 1 − η ( ϕ ν − 1 ( u ) ) + ε ) − ∣ a ∣ / 2 ] ≤ C [ η ( ϕ ν − 1 ( u ) ) ( 1 − η ( ϕ ν − 1 ( u ) ) ) ] − ∣ a ∣ / 2 . \begin{aligned}
\left|\partial_u^a(f_\varepsilon\circ\phi_\nu^{-1})(u)\right|
\leq C\left[\left(\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{-|a|/2}+\left(1-\eta(\phi_\nu^{-1}(u))+\varepsilon\right)^{-|a|/2}\right] \\
&\leq C\left[\eta(\phi_\nu^{-1}(u))(1-\eta(\phi_\nu^{-1}(u)))\right]^{-|a|/2}.
\end{aligned} ∂ u a ( f ε ∘ ϕ ν − 1 ) ( u ) ≤ C [ ( η ( ϕ ν − 1 ( u )) + ε ) − ∣ a ∣/2 + ( 1 − η ( ϕ ν − 1 ( u )) + ε ) − ∣ a ∣/2 ] ≤ C [ η ( ϕ ν − 1 ( u )) ( 1 − η ( ϕ ν − 1 ( u ))) ] − ∣ a ∣/2 . The constants are independent of ε \varepsilon ε V ν V_\nu V ν X X X
∣ ∇ ∣ a ∣ f ε ∣ ≤ C [ η ( 1 − η ) ] − ∣ a ∣ / 2 , 1 ≤ ∣ a ∣ ≤ m . (46) |\nabla^{|a|}f_\varepsilon|\leq C[\eta(1-\eta)]^{-|a|/2},\qquad1\leq|a|\leq m. \tag*{(46)} ∣ ∇ ∣ a ∣ f ε ∣ ≤ C [ η ( 1 − η ) ] − ∣ a ∣/2 , 1 ≤ ∣ a ∣ ≤ m . (46) Also, adding the same positive number to η \eta η 1 − η 1-\eta 1 − η
∣ f ε ∣ ≤ ∣ f ∗ ∣ ≤ − log ( η ( 1 − η ) ) ≤ C m [ η ( 1 − η ) ] − m / 2 . |f_\varepsilon|\leq|f^*|\leq-\log(\eta(1-\eta))\leq C_m[\eta(1-\eta)]^{-m/2}. ∣ f ε ∣ ≤ ∣ f ∗ ∣ ≤ − log ( η ( 1 − η )) ≤ C m [ η ( 1 − η ) ] − m /2 . Since η ( 1 − η ) ≤ 1 / 4 < 1 \eta(1-\eta)\leq1/4<1 η ( 1 − η ) ≤ 1/4 < 1 (17) give the uniform bound
∥ f ε ∥ H m ( X ) ≤ C ( ∫ X [ η ( 1 − η ) ] − m d V ) 1 / 2 . \|f_\varepsilon\|_{H^m(X)}\leq C\left(\int_X[\eta(1-\eta)]^{-m}\,dV\right)^{1/2}. ∥ f ε ∥ H m ( X ) ≤ C ( ∫ X [ η ( 1 − η ) ] − m d V ) 1/2 . Note that the endpoint set has zero volume. As ε \varepsilon ε f ε f_\varepsilon f ε f ∗ f^* f ∗ f ε → f ∗ f_\varepsilon\to f^* f ε → f ∗ L 2 ( X ) L_2(X) L 2 ( X ) H m ( X ) H^m(X) H m ( X ) L 2 ( X ) L_2(X) L 2 ( X ) f ∗ ∈ H m ( X ) f^*\in H^m(X) f ∗ ∈ H m ( X ) H m ( X ) H^m(X) H m ( X ) (18) . By [22 Theorem 7.4.5 and Theorem 7.3.1] , we have the identity H m ( X ) = B 2 , 2 m ( X ) H^m(X)=B^m_{2,2}(X) H m ( X ) = B 2 , 2 m ( X )
B 2 , 2 m ( X ) ↪ B 2 , ∞ m ( X ) ↪ B 2 , ∞ α ( X ) , 0 < α ≤ m , B^m_{2,2}(X)\hookrightarrow B^m_{2,\infty}(X)\hookrightarrow B^\alpha_{2,\infty}(X),\qquad0<\alpha\leq m, B 2 , 2 m ( X ) ↪ B 2 , ∞ m ( X ) ↪ B 2 , ∞ α ( X ) , 0 < α ≤ m , by [22 Theorem 7.4.2] give the Besov conclusion. Finally, we verify the two claims concerning (19) . Put w ( x ) : = min { η ( x ) , 1 − η ( x ) } w(x) := \min\{\eta(x), 1-\eta(x)\} w ( x ) := min { η ( x ) , 1 − η ( x )} r > 0 r>0 r > 0 w > 0 w>0 w > 0 η ( 1 − η ) = w ( 1 − w ) ≥ w / 2 \eta(1-\eta)=w(1-w)\ge w/2 η ( 1 − η ) = w ( 1 − w ) ≥ w /2
∫ X [ η ( 1 − η ) ] − r d V ≤ 2 r ∫ X w − r d V = 2 r [ 2 r V ( X ) + r ∫ 0 1 / 2 u − r − 1 V { w < u } d u ] ≤ 2 r [ 2 r V ( X ) + r C 0 ∫ 0 1 / 2 u κ − r − 1 d u ] < ∞ . \int_X [\eta(1-\eta)]^{-r}\,\mathrm{d}V \le2^r\int_X w^{-r}\,\mathrm{d}V
=2^r\left[2^rV(X)+r\int_0^{1/2}u^{-r-1}V\{w<u\}\,\mathrm{d}u\right]
\le2^r\left[2^rV(X)+rC_0\int_0^{1/2}u^{\kappa-r-1}\,\mathrm{d}u\right]<\infty. ∫ X [ η ( 1 − η ) ] − r d V ≤ 2 r ∫ X w − r d V = 2 r [ 2 r V ( X ) + r ∫ 0 1/2 u − r − 1 V { w < u } d u ] ≤ 2 r [ 2 r V ( X ) + r C 0 ∫ 0 1/2 u κ − r − 1 d u ] < ∞. whenever κ > r \kappa>r κ > r r = 2 α / β r=2\alpha/\beta r = 2 α / β r = m r=m r = m
Proof of Proposition 4.6. Applying [28 Lemma 5.4] at the fixed smoothness order m m m (20) for sufficiently small γ > 0 \gamma>0 γ > 0 γ m − 1 < δ < 1 / 2 \gamma^{m-1}<\delta<1/2 γ m − 1 < δ < 1/2 γ m ∈ ( 0 , 1 ) \gamma_m\in(0,1) γ m ∈ ( 0 , 1 ) 0 < γ ≤ γ m 0<\gamma\le\gamma_m 0 < γ ≤ γ m γ m m − 1 < 1 / 4 \gamma_m^{m-1}<1/4 γ m m − 1 < 1/4 1 / 4 ≤ δ ≤ 1 1/4\le\delta\le1 1/4 ≤ δ ≤ 1 δ = 1 / 4 \delta=1/4 δ = 1/4 C m C_m C m
For the polynomial estimate, observe that, for 0 < q ≤ 1 / 2 0<q\le1/2 0 < q ≤ 1/2
δ 2 q ( log 2 δ ) ϱ + 1 = 2 2 q exp ( − 2 q log 2 δ ) ( log 2 δ ) ϱ + 1 ≤ 2 sup t > 0 exp ( − 2 q t ) t ϱ + 1 = 2 ( ϱ + 1 2 e q ) ϱ + 1 . \delta^{2q}\left(\log\frac{2}{\delta}\right)^{\varrho+1}
=2^{2q}\exp\left(-2q\log\frac{2}{\delta}\right)\left(\log\frac{2}{\delta}\right)^{\varrho+1}
\le2\sup_{t>0}\exp(-2qt)t^{\varrho+1}
=2\left(\frac{\varrho+1}{2eq}\right)^{\varrho+1}. δ 2 q ( log δ 2 ) ϱ + 1 = 2 2 q exp ( − 2 q log δ 2 ) ( log δ 2 ) ϱ + 1 ≤ 2 t > 0 sup exp ( − 2 q t ) t ϱ + 1 = 2 ( 2 e q ϱ + 1 ) ϱ + 1 . Substitution into (20) proves (21) with an enlarged constant C m C_m C m
Proof of Theorem 4.7. Fix an integer m ≥ 2 m\ge2 m ≥ 2
m − 1 > β + ϱ 2 . m-1>\beta+\frac{\varrho}{2}. m − 1 > β + 2 ϱ . Let C m C_m C m γ m \gamma_m γ m n n n 0 < γ n ≤ γ m 0<\gamma_n\le\gamma_m 0 < γ n ≤ γ m 0 < λ n ≤ 1 0<\lambda_n\le1 0 < λ n ≤ 1
q n : = log 2 2 log n ∈ ( 0 , 1 / 2 ] , b n : = 2 γ n m − 1 ≤ 1 4 , A n : = C m q n − ( ϱ + 1 ) γ n − ϱ ≥ 1. q_n:=\frac{\log2}{2\log n}\in(0,1/2],\qquad b_n:=2\gamma_n^{m-1}\le\frac14,\qquad A_n:=C_mq_n^{-(\varrho+1)}\gamma_n^{-\varrho}\ge1. q n := 2 log n log 2 ∈ ( 0 , 1/2 ] , b n := 2 γ n m − 1 ≤ 4 1 , A n := C m q n − ( ϱ + 1 ) γ n − ϱ ≥ 1. The estimate (21) verifies (7) for F = H γ n ( X ) \mathcal{F}=\mathcal{H}_{\gamma_n}(X) F = H γ n ( X ) q n q_n q n A = A n A=A_n A = A n b = b n b=b_n b = b n 1 − e − t 1-e^{-t} 1 − e − t n n n
γ n β + λ n γ n − ϱ + λ n − 1 ( A n n ) 2 / ( 1 + q n ) + λ n + λ n − 1 b n 2 + λ n − 1 t 2 n 2 . \gamma_n^\beta+\lambda_n\gamma_n^{-\varrho}+\lambda_n^{-1}\left(\frac{A_n}{n}\right)^{2/(1+q_n)}+\lambda_n+\lambda_n^{-1}b_n^2+\lambda_n^{-1}\frac{t^2}{n^2}. γ n β + λ n γ n − ϱ + λ n − 1 ( n A n ) 2/ ( 1 + q n ) + λ n + λ n − 1 b n 2 + λ n − 1 n 2 t 2 . The choice of q n q_n q n
A n n ≍ ( log n ) ϱ + 1 n γ n − ϱ = ( ( log n ) ϱ + 1 n ) ( 2 β + ϱ ) / ( 2 β + 3 ϱ ) , \frac{A_n}{n}\asymp\frac{(\log n)^{\varrho+1}}{n}\gamma_n^{-\varrho}
=\left(\frac{(\log n)^{\varrho+1}}{n}\right)^{(2\beta+\varrho)/(2\beta+3\varrho)}, n A n ≍ n ( log n ) ϱ + 1 γ n − ϱ = ( n ( log n ) ϱ + 1 ) ( 2 β + ϱ ) / ( 2 β + 3 ϱ ) , ( A n n ) 2 / ( 1 + q n ) = ( A n n ) 2 exp ( 2 q n 1 + q n log n A n ) ≍ ( A n n ) 2 . \left(\frac{A_n}{n}\right)^{2/(1+q_n)}
=\left(\frac{A_n}{n}\right)^2\exp\left(\frac{2q_n}{1+q_n}\log\frac{n}{A_n}\right)
\asymp\left(\frac{A_n}{n}\right)^2. ( n A n ) 2/ ( 1 + q n ) = ( n A n ) 2 exp ( 1 + q n 2 q n log A n n ) ≍ ( n A n ) 2 . It follows that the first three terms have the same order:
γ n β ≍ λ n γ n − ϱ ≍ λ n − 1 ( A n n ) 2 / ( 1 + q n ) ≍ ( ( log n ) ϱ + 1 n ) 2 β / ( 2 β + 3 ϱ ) . \gamma_n^\beta\asymp\lambda_n\gamma_n^{-\varrho}\asymp\lambda_n^{-1}\left(\frac{A_n}{n}\right)^{2/(1+q_n)}
\asymp\left(\frac{(\log n)^{\varrho+1}}{n}\right)^{2\beta/(2\beta+3\varrho)}. γ n β ≍ λ n γ n − ϱ ≍ λ n − 1 ( n A n ) 2/ ( 1 + q n ) ≍ ( n ( log n ) ϱ + 1 ) 2 β / ( 2 β + 3 ϱ ) . To control the error from the finite covering scale, note that λ n = γ n β + ϱ \lambda_n=\gamma_n^{\beta+\varrho} λ n = γ n β + ϱ
λ n − 1 b n 2 γ n β = 4 γ n 2 ( m − 1 ) − 2 β − ϱ → 0 , \frac{\lambda_n^{-1}b_n^2}{\gamma_n^\beta}=4\gamma_n^{2(m-1)-2\beta-\varrho}\to0, γ n β λ n − 1 b n 2 = 4 γ n 2 ( m − 1 ) − 2 β − ϱ → 0 , by the choice of m m m
λ n γ n β = γ n ϱ → 0 , \frac{\lambda_n}{\gamma_n^\beta}=\gamma_n^\varrho\to0, γ n β λ n = γ n ϱ → 0 , and
λ n − 1 t 2 n 2 ≤ t 2 ( ( log n ) ϱ + 1 n ) ( 2 β + 4 ϱ ) / ( 2 β + 3 ϱ ) = o ( ( ( log n ) ϱ + 1 n ) 2 β / ( 2 β + 3 ϱ ) ) \lambda_n^{-1}\frac{t^2}{n^2}\le t^2\left(\frac{(\log n)^{\varrho+1}}{n}\right)^{(2\beta+4\varrho)/(2\beta+3\varrho)}
=o\left(\left(\frac{(\log n)^{\varrho+1}}{n}\right)^{2\beta/(2\beta+3\varrho)}\right) λ n − 1 n 2 t 2 ≤ t 2 ( n ( log n ) ϱ + 1 ) ( 2 β + 4 ϱ ) / ( 2 β + 3 ϱ ) = o ( ( n ( log n ) ϱ + 1 ) 2 β / ( 2 β + 3 ϱ ) ) for fixed t t t 2 β = 4 α ( 1 − 1 / p ) 2\beta=4\alpha(1-1/p) 2 β = 4 α ( 1 − 1/ p ) (22) .
Proof of Theorem 4.8 . We first establish a comparison bound for clipped predictions. For every u ∈ R u\in\mathbb{R} u ∈ R y ∈ { − 1 , 1 } y\in\{-1,1\} y ∈ { − 1 , 1 } M > 0 M>0 M > 0
ϕ ( y π M ( u ) ) ≤ ϕ ( y u ) + e − M . (47) \phi(y\pi_M(u))\le\phi(yu)+e^{-M}. \tag*{(47)} ϕ ( y π M ( u )) ≤ ϕ ( y u ) + e − M . (47) Indeed, clipping decreases the loss when y u < − M yu<-M y u < − M ∣ u ∣ ≤ M |u|\le M ∣ u ∣ ≤ M y u > M yu>M y u > M ϕ ( M ) ≤ e − M \phi(M)\le e^{-M} ϕ ( M ) ≤ e − M
Fix 0 < λ ≤ 1 0<\lambda\le1 0 < λ ≤ 1 γ > 0 \gamma>0 γ > 0 M ≥ 1 M\ge1 M ≥ 1 f 0 ∈ H γ ( X ) f_0\in\mathcal{H}_\gamma(X) f 0 ∈ H γ ( X ) ϕ \phi ϕ
0 ≤ ( ϕ ( Y f 0 ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) + ≤ ∥ f 0 ∥ ∞ . 0\le\left(\phi(Yf_0(X))-\phi(Y\pi_Mf_0(X))\right)_+\le\|f_0\|_\infty. 0 ≤ ( ϕ ( Y f 0 ( X )) − ϕ ( Y π M f 0 ( X )) ) + ≤ ∥ f 0 ∥ ∞ . Moreover, (A.23) bounds the negative part of this loss difference by e − M e^{-M} e − M
E P ( ϕ ( Y f 0 ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) + ≤ R ( f 0 ) − R ∗ + e − M , \mathbb{E}_{P}\left(\phi(Yf_0(X))-\phi(Y\pi_Mf_0(X))\right)_+
\le\mathcal{R}(f_0)-\mathcal{R}^*+e^{-M}, E P ( ϕ ( Y f 0 ( X )) − ϕ ( Y π M f 0 ( X )) ) + ≤ R ( f 0 ) − R ∗ + e − M , E P ( ϕ ( Y f 0 ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) 2 ≤ ∥ f 0 ∥ ∞ ( R ( f 0 ) − R ∗ + e − M ) . \mathbb{E}_{P}\left(\phi(Yf_0(X))-\phi(Y\pi_Mf_0(X))\right)^2
\le\|f_0\|_\infty\left(\mathcal{R}(f_0)-\mathcal{R}^*+e^{-M}\right). E P ( ϕ ( Y f 0 ( X )) − ϕ ( Y π M f 0 ( X )) ) 2 ≤ ∥ f 0 ∥ ∞ ( R ( f 0 ) − R ∗ + e − M ) . Bernstein’s inequality shows that, with probability at least 1 − e − t / 2 1-e^{-t/2} 1 − e − t /2
E D ( ϕ ( Y f 0 ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) + ≤ 2 ( R ( f 0 ) − R ∗ + e − M ) + C ∥ f 0 ∥ ∞ ( t + log 2 ) n . (48) \mathbb{E}_{D}\left(\phi(Yf_0(X))-\phi(Y\pi_Mf_0(X))\right)_+
\le2\left(\mathcal{R}(f_0)-\mathcal{R}^*+e^{-M}\right)
+\frac{C\|f_0\|_\infty(t+\log2)}{n}. \tag*{(48)} E D ( ϕ ( Y f 0 ( X )) − ϕ ( Y π M f 0 ( X )) ) + ≤ 2 ( R ( f 0 ) − R ∗ + e − M ) + n C ∥ f 0 ∥ ∞ ( t + log 2 ) . (48) (A.23) implies
E D ( ϕ ( Y π M f ^ n , λ , γ ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) ≤ E D ( ϕ ( Y f ^ n , λ , γ ( X ) ) − ϕ ( Y f 0 ( X ) ) ) + E D ( ϕ ( Y f 0 ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) + e − M ≤ λ ∥ f 0 ∥ H γ 2 + E D ( ϕ ( Y f 0 ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) + + e − M . (49) \begin{aligned}
\mathbb{E}_{D}\left(\phi(Y\pi_M\widehat{f}_{n,\lambda,\gamma}(X))-\phi(Y\pi_Mf_0(X))\right)
&\le\mathbb{E}_{D}\left(\phi(Y\widehat{f}_{n,\lambda,\gamma}(X))-\phi(Yf_0(X))\right)\\
&\quad+\mathbb{E}_{D}\left(\phi(Yf_0(X))-\phi(Y\pi_Mf_0(X))\right)+e^{-M}\\
&\le\lambda\|f_0\|_{\mathcal{H}_\gamma}^2+\mathbb{E}_{D}\left(\phi(Yf_0(X))-\phi(Y\pi_Mf_0(X))\right)_++e^{-M}. \tag*{(49)}
\end{aligned} E D ( ϕ ( Y π M f n , λ , γ ( X )) − ϕ ( Y π M f 0 ( X )) ) ≤ E D ( ϕ ( Y f n , λ , γ ( X )) − ϕ ( Y f 0 ( X )) ) + E D ( ϕ ( Y f 0 ( X )) − ϕ ( Y π M f 0 ( X )) ) + e − M ≤ λ ∥ f 0 ∥ H γ 2 + E D ( ϕ ( Y f 0 ( X )) − ϕ ( Y π M f 0 ( X )) ) + + e − M . (49) Comparison of the empirical objective with zero gives ∥ f ^ n , λ , γ ∥ H γ ≤ λ − 1 / 2 \|\widehat{f}_{n,\lambda,\gamma}\|_{\mathcal{H}_\gamma}\le\lambda^{-1/2} ∥ f n , λ , γ ∥ H γ ≤ λ − 1/2
V = { π M f : f ∈ λ − 1 / 2 B H γ } . \mathcal{V}=\{\pi_Mf:f\in\lambda^{-1/2}B_{\mathcal{H}_\gamma}\}. V = { π M f : f ∈ λ − 1/2 B H γ } . Suppose that V \mathcal{V} V δ \delta δ { v 1 , … , v N } ⊂ V \{v_1,\ldots,v_N\}\subset\mathcal{V} { v 1 , … , v N } ⊂ V v j v_j v j π M f 0 \pi_Mf_0 π M f 0 M M M 2 M 2M 2 M
E P ( ϕ ( Y v j ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) 2 ≤ 2 E P ( ϕ ( Y v j ( X ) ) − ψ ( X , Y ) ) 2 + 2 E P ( ϕ ( Y π M f 0 ( X ) ) − ψ ( X , Y ) ) 2 \mathbb{E}_{P}\left(\phi(Yv_j(X))-\phi(Y\pi_Mf_0(X))\right)^2
\le2\mathbb{E}_{P}\left(\phi(Yv_j(X))-\psi(X,Y)\right)^2+2\mathbb{E}_{P}\left(\phi(Y\pi_Mf_0(X))-\psi(X,Y)\right)^2 E P ( ϕ ( Y v j ( X )) − ϕ ( Y π M f 0 ( X )) ) 2 ≤ 2 E P ( ϕ ( Y v j ( X )) − ψ ( X , Y ) ) 2 + 2 E P ( ϕ ( Y π M f 0 ( X )) − ψ ( X , Y ) ) 2 ≤ 2 ( M + 2 ) ( R ( v j ) − R ∗ + R ( π M f 0 ) − R ∗ ) . \le2(M+2)\left(\mathcal{R}(v_j)-\mathcal{R}^*+\mathcal{R}(\pi_Mf_0)-\mathcal{R}^*\right). ≤ 2 ( M + 2 ) ( R ( v j ) − R ∗ + R ( π M f 0 ) − R ∗ ) . Apply Bernstein’s inequality to these N N N log N + t + log 2 \log N+t+\log2 log N + t + log 2 1 − e − t / 2 1-e^{-t/2} 1 − e − t /2 j j j
R ( v j ) − R ( π M f 0 ) ≤ E D ( ϕ ( Y v j ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) + 1 2 ( R ( v j ) − R ∗ + R ( π M f 0 ) − R ∗ ) + C ( M + 2 ) ( log N + t + log 2 ) n . \begin{aligned}
\mathcal{R}(v_j)-\mathcal{R}(\pi_Mf_0)
&\le\mathbb{E}_{D}\left(\phi(Yv_j(X))-\phi(Y\pi_Mf_0(X))\right)\\
&\quad+\frac{1}{2}\left(\mathcal{R}(v_j)-\mathcal{R}^*+\mathcal{R}(\pi_Mf_0)-\mathcal{R}^*\right)
+\frac{C(M+2)(\log N+t+\log2)}{n}.
\end{aligned} R ( v j ) − R ( π M f 0 ) ≤ E D ( ϕ ( Y v j ( X )) − ϕ ( Y π M f 0 ( X )) ) + 2 1 ( R ( v j ) − R ∗ + R ( π M f 0 ) − R ∗ ) + n C ( M + 2 ) ( log N + t + log 2 ) . For each w ∈ V w \in\mathcal{V} w ∈ V ∥ w − v j ∥ ∞ ≤ δ \lVert w-v_j\rVert_\infty\le\delta ∥ w − v j ∥ ∞ ≤ δ δ \delta δ
R ( w ) − R ∗ ≤ 2 E D ( ϕ ( Y w ( X ) ) − ϕ ( Y π M f 0 ( X ) ) ) + 3 ( R ( π M f 0 ) − R ∗ ) + C ( M + 2 ) ( log N + t + log 2 ) n + 3 δ . \mathcal{R}(w)-\mathcal{R}^* \le2\mathbb{E}_D\bigl(\phi(Yw(X))-\phi(Y\pi_M f_0(X))\bigr)+3\bigl(\mathcal{R}(\pi_M f_0)-\mathcal{R}^*\bigr)
+\frac{C(M+2)(\log N+t+\log2)}{n}+3\delta. R ( w ) − R ∗ ≤ 2 E D ( ϕ ( Y w ( X )) − ϕ ( Y π M f 0 ( X )) ) + 3 ( R ( π M f 0 ) − R ∗ ) + n C ( M + 2 ) ( log N + t + log 2 ) + 3 δ . In particular, this holds for w = π M f ^ n , λ , γ w=\pi_M\widehat{f}_{n,\lambda,\gamma} w = π M f n , λ , γ R ( π M f 0 ) − R ∗ ≤ R ( f 0 ) − R ∗ + e − M \mathcal{R}(\pi_M f_0)-\mathcal{R}^* \le\mathcal{R}(f_0)-\mathcal{R}^*+e^{-M} R ( π M f 0 ) − R ∗ ≤ R ( f 0 ) − R ∗ + e − M 1 − e − t 1-e^{-t} 1 − e − t
R ( π M f ^ n , λ , γ ) − R ∗ ≤ C [ R ( f 0 ) − R ∗ + λ ∥ f 0 ∥ H γ 2 + ( M + 2 ) ( log N + t + log 2 ) n + ∥ f 0 ∥ ∞ ( t + log 2 ) n + e − M + δ ] . (50) \mathcal{R}(\pi_M\widehat{f}_{n,\lambda,\gamma})-\mathcal{R}^*
\le C\left[\mathcal{R}(f_0)-\mathcal{R}^*+\lambda\lVert f_0\rVert_{\mathcal{H}_\gamma}^2+\frac{(M+2)(\log N+t+\log2)}{n}
+\frac{\lVert f_0\rVert_\infty(t+\log2)}{n}+e^{-M}+\delta\right]. \tag*{(50)} R ( π M f n , λ , γ ) − R ∗ ≤ C [ R ( f 0 ) − R ∗ + λ ∥ f 0 ∥ H γ 2 + n ( M + 2 ) ( log N + t + log 2 ) + n ∥ f 0 ∥ ∞ ( t + log 2 ) + e − M + δ ] . (50) We now apply this bound with the parameters in the theorem and choose
f 0 = S γ n , s f ∗ , s = ⌊ α ⌋ + 1 , δ = γ n β . f_0=S_{\gamma_n,s}f^*,\qquad s=\lfloor\alpha\rfloor+1,\qquad\delta=\gamma_n^\beta. f 0 = S γ n , s f ∗ , s = ⌊ α ⌋ + 1 , δ = γ n β . Theorem 4.1 and the proof of Theorem 4.4 give
R ( f 0 ) − R ∗ ≤ C γ n β , ∥ f 0 ∥ H γ n 2 ≤ C γ n − ϱ , ∥ f 0 ∥ ∞ ≤ ∥ f 0 ∥ H γ n ≤ C γ n − ϱ / 2 . (51) \mathcal{R}(f_0)-\mathcal{R}^*\le C\gamma_n^\beta,\qquad\lVert f_0\rVert_{\mathcal{H}_{\gamma_n}}^2\le C\gamma_n^{-\varrho},\qquad\lVert f_0\rVert_\infty\le\lVert f_0\rVert_{\mathcal{H}_{\gamma_n}}\le C\gamma_n^{-\varrho/2}. \tag*{(51)} R ( f 0 ) − R ∗ ≤ C γ n β , ∥ f 0 ∥ H γ n 2 ≤ C γ n − ϱ , ∥ f 0 ∥ ∞ ≤ ∥ f 0 ∥ H γ n ≤ C γ n − ϱ /2 . (51) Fix an integer m ≥ 2 m\ge2 m ≥ 2
m − 1 > 3 β + ϱ 2 . m-1>\frac{3\beta+\varrho}{2}. m − 1 > 2 3 β + ϱ . Since λ n = γ n β + ϱ \lambda_n=\gamma_n^{\beta+\varrho} λ n = γ n β + ϱ
δ λ n 2 = 1 2 γ n ( 3 β + ϱ ) / 2 > γ n m − 1 \frac{\delta\sqrt{\lambda_n}}{2}=\frac{1}{2}\gamma_n^{(3\beta+\varrho)/2}>\gamma_n^{m-1} 2 δ λ n = 2 1 γ n ( 3 β + ϱ ) /2 > γ n m − 1 for all sufficiently large n n n γ n ≤ γ m \gamma_n\le\gamma_m γ n ≤ γ m λ n − 1 / 2 B H γ n \lambda_n^{-1/2}B_{\mathcal{H}_{\gamma_n}} λ n − 1/2 B H γ n δ / 2 \delta/2 δ /2 V \mathcal{V} V δ \delta δ V \mathcal{V} V
log N ≤ C m γ n − ϱ ( log 4 δ λ n ) ϱ + 1 ≤ C γ n − ϱ ( log n ) ϱ + 1 . \log N\le C_m\gamma_n^{-\varrho}\left(\log\frac{4}{\delta\sqrt{\lambda_n}}\right)^{\varrho+1}\le C\gamma_n^{-\varrho}(\log n)^{\varrho+1}. log N ≤ C m γ n − ϱ ( log δ λ n 4 ) ϱ + 1 ≤ C γ n − ϱ ( log n ) ϱ + 1 . The constants are independent of n n n
Substituting this estimate and (A.27) into (A.26), and using M n = 3 log n M_n=3\log n M n = 3 log n
R ( π M n f ^ n , λ n , γ n ) − R ∗ ≤ C [ γ n β + λ n γ n − ϱ + γ n − ϱ ( log n ) ϱ + 2 n + ( log n + γ n − ϱ / 2 ) ( 1 + t ) n + n − 3 ] . \mathcal{R}(\pi_{M_n}\widehat{f}_{n,\lambda_n,\gamma_n})-\mathcal{R}^*
\le C\left[\gamma_n^\beta+\lambda_n\gamma_n^{-\varrho}+\frac{\gamma_n^{-\varrho}(\log n)^{\varrho+2}}{n}+\frac{(\log n+\gamma_n^{-\varrho/2})(1+t)}{n}+n^{-3}\right]. R ( π M n f n , λ n , γ n ) − R ∗ ≤ C [ γ n β + λ n γ n − ϱ + n γ n − ϱ ( log n ) ϱ + 2 + n ( log n + γ n − ϱ /2 ) ( 1 + t ) + n − 3 ] . The parameter choices imply that the main terms are
γ n β = λ n γ n − ϱ = γ n − ϱ ( log n ) ϱ + 2 n = ( ( log n ) ϱ + 2 n ) β / ( β + ϱ ) . \gamma_n^\beta=\lambda_n\gamma_n^{-\varrho}=\frac{\gamma_n^{-\varrho}(\log n)^{\varrho+2}}{n}=\left(\frac{(\log n)^{\varrho+2}}{n}\right)^{\beta/(\beta+\varrho)}. γ n β = λ n γ n − ϱ = n γ n − ϱ ( log n ) ϱ + 2 = ( n ( log n ) ϱ + 2 ) β / ( β + ϱ ) . The remaining terms are of smaller order for fixed t t t 1 + t 1+t 1 + t C C C t t t (24) . For the misclassification bound, note that
sgn ( π M n f ^ n , λ n , γ n ) = sgn ( f ^ n , λ n , γ n ) . \operatorname{sgn}(\pi_{M_n}\widehat{f}_{n,\lambda_n,\gamma_n})=\operatorname{sgn}(\widehat{f}_{n,\lambda_n,\gamma_n}). sgn ( π M n f n , λ n , γ n ) = sgn ( f n , λ n , γ n ) . The calibration inequality (2) then gives the misclassification bound on the same event.
