# Density Problem and Approximation Error in Learning Theory

Authors: Ding-Xuan Zhou
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We study the density problem and approximation error of reproducing kernel Hilbert spaces for the purpose of learning theory. For a Mercer kernelK on a compact metric space (X, d), a characterization for the generated reproducing kernel Hilbert space (RKHS) ℋK to be dense in C(X)
is given. As a corollary, we show that the density is always true for convolution type kernels. Some estimates for the rate of convergence of interpolation schemes are presented for general Mercer kernels. These are then used to establish for convolution type kernels quantitative analysis for the approximation error in learning theory. Finally, we show by the example of Gaussian kernels with varying variances that the approximation error can be improved when we adaptively change the value of the parameter for the used kernel. This confirms the method of choosing varying parameters which is used often in many applications of learning theory.


---

## Body

## 1. Introduction

Learning theory investigates how to find function relations or data structures from random samples. For the regression problem, one usually has some experience and would expect that the (underlying) unknown function lies in some set of functionsℋ called the hypothesis space. Then one tries to find a good approximation in ℋ of the underlying functionf(under certain metric). The best approximation in ℋ is called the target functionfℋ. However,fis unknown. What we have in hand is a set of random samples{(xi,yi)}i=1ℓ. These samples are not given byfexactly (f(xi)≠yi). They are controlled by this underlying functionfwith noise or some other uncertainties (f(xi)≈yi). The most important model studied in learning theory [1] is to assume that the uncertainty is represented by a Borel probability measureρonX×Y, and the underlying functionf:X→Yis the regression function ofρgiven by
(1)fρ(x)=∫Y‍ydρ(y∣x),x∈X.
Here, ρ(y∣x)is the conditional probability measure atx. Then, the samples{(xi,yi)}i=1ℓare independent and identically distributed drawers according to the probability measureρ. For the classification problem,Y={1,-1}and sign (fρ)is the optimal classifier.Based on the samples, one can find a function from the hypothesis spaceℋ that best fits the dataz:={(xi,yi)}i=1ℓ(with respect to certain loss functional). This function is called the empirical target functionfz. When the number ℓ of samples is large enough, fz is a good approximation of the target function fℋ with certain confidence. This problem has been extensively investigated and well developed in the literature of statistical learning theory. See, for example, [1–4].What is less understood is the approximation of the underlying desired functionfby the target functionfℋ. For example, if one takes ℋ to be a polynomial space of some fixed degree, thenfcan be approximated by functions from ℋ only whenfis a polynomial in ℋ.In kernel machine learning such as support vector machines, one often uses reproducing kernel Hilbert spaces or their balls as hypothesis spaces. Here, we take(X,d(·,·)) to be a compact metric space and Y=ℝ.Definition 1.
LetK:X×X→ℝbe continuous, symmetric, and positive semidefinite; that is, for any finite set of distinct points{x1,…,xℓ}⊂X, the matrix(K(xi,xj))i,j=1ℓis positive semidefinite. Such a kernel is called a Mercer kernel. It is called positive definite if the matrix(K(xi,xj))i,j=1ℓis always positive definite.Thereproducing kernel Hilbert space (RKHS) ℋK associated with a Mercer kernelKis defined (see [5]) to be the completion of the linear span of the set of functions{Kx:=K(x,·):x∈X}with the inner product〈·,·〉ℋK=〈·,·〉Ksatisfying
(2)∥∑i=1ℓ‍ciKxi∥K2=〈∑i=1ℓ‍ciKxi,∑i=1ℓ‍ciKxi〉K=∑i,j=1ℓ‍ciK(xi,xj)cj.
The reproducing kernel property is given by
(3)〈Kx,g〉K=g(x),∀x∈X,g∈ℋK.
This space can be embedded intoC(X), the space of continuous functions onX.In kernel machine learning, one often takesℋKor its balls as the hypothesis space. Then, one needs to know whether the desired functionfcan be approximated by functions from the RKHS.The first purpose of this paper is to study the density of the reproducing kernel Hilbert spaces inC(X)(or inL2(X)whenXis a subset of the Euclidean spaceℝn). This will be done in Section 2 where some characterizations will be provided. Let us mention a simple example with detailed proof given in Section 6.Example 2.
LetX=[0,1]and let Kbe a Mercer kernel given by
(4)K(x,y)=∑j=0+∞‍aj(x·y)j,
whereaj≥0for eachj and∑j=0+∞‍aj<∞. SetJ:={j∈ℤ+:aj>0}. Then, ℋKis dense inC(X)if and only if
(5)a0>0,∑j∈J∖{0}‍1j=+∞.When the density holds, we want to study the convergence rate of the approximation by functions from balls of the RKHS as the radius tends to infinity. The quantity(6)I(f,R):=inf∥g∥K≤R∥f-g∥
is called the approximation error in learning theory. Some estimates have been presented by Smale and Zhou [6] for theL2norm and many kernels. The second purpose of this paper is to investigate the convergence rate of the approximation error with the uniform norm as well as theL2norm. Estimates will be given in Section 4, based on the analysis in Section 3 for interpolation schemes associated with general Mercer kernels. With this analysis, we can understand the approximation error with respect to marginal probability distribution induced byρ. Let us provide an example of Gaussian kernels to illustrate the idea. Notice that when the parameterσof the kernel is allowed to change withR, the rate of the approximation error may be improved. This confirms the method of adaptively choosing the parameter of the kernel, which is used in many applications (see e.g., [7]).Example 3.
Let(7)Kσ(x,y)=exp{-|x-y|2σ2},x,y∈X=[0,1]n.
There exist positive constantsAandBsuch that, for eachf∈Hs(ℝn)andR≥A∥f∥L2, there holds
(8)inf∥g∥Kσ≤R∥f-g∥L2(X)≤B(logR)-s/4
whenσis fixed; while whenσmay change withR, there holds
(9)inf∥g∥KσR≤R∥f-g∥L2(X)≤B(logR)-s.


## 2. Density and Positive Definiteness

The density problem of reproducing kernel Hilbert spaces inC(X)was raised to the author by Poggio et al. See [8]. It can be stated as follows.Given a Mercer kernelKon a compact metric space(X,d(·,·)), when is the RKHSℋKdense inC(X)?By means of the dual space ofC(X), we can give a general characterization. This is only a simple observation, but it does provide us useful information. For example, we will show that the density is always true for convolution type kernels. Also, for dot product type kernel, we can give a complete nice characterization for the density, which will be given in Section 6.Recall the Riesz Representation Theorem asserting that the dual space ofC(X)can be represented by the set of Borel measures onX. For a Borel measureμonX, we define the integral operatorLK,μassociated with the kernel as
(10)LK,μ(f)(x):=∫X‍K(x,y)f(y)dμ(y),x∈X.
This is a compact operator on Lμ2(X) if μ is a positive measure.Theorem 4.
LetK be a Mercer kernel on a compact metric space (X,d). Then, the following statements are equivalent. (1)
ℋKis dense inC(X).(2)
For any nontrivial positive Borel measureμ,ℋKis dense inLμ2(X).(3)
For any nontrivial positive Borel measureμ,LK,μhas no eigenvalue zero inLμ2(X).(4)
For any nontrivial Borel measureμ, as a function inC(X),
(11)∫X‍K(·,y)dμ(y)≠0.Proof.
(1)⇒(2). This follows from the fact thatC(X)is dense inLμ2(X). See, for example, [9].
(2)⇒(3). Suppose that ℋKis dense inLμ2(X), butLK,μhas an eigenvalue zero inLμ2(X). Then, there exists a nontrivial functionf∈Lμ2(X)such thatLK,μ(f)=0; that is,
(12)LK,μ(f)(x)=∫X‍K(x,y)f(y)dμ(y)LK,μ(f)(x)=∫X‍Kx(y)f(y)dμ(y)=0.
The identity holds as functions inLμ2(X). If the support ofμisX, then this identity would imply thatfis orthogonal to eachKxwithx∈X. When the support ofμis notX, things are more complicated. Here, the support ofμ, denoted as suppμ, is defined to be the smallest closed subsetFofXsatisfyingμ(X∖F)=0.
The property of the RKHS enables us to prove the general case. As the functionLK,μ(f)is continuous, we know from (12) that, for eachxin suppμ,
(13)∫suppμ‍Kx(y)f(y)dμ(y)=∫X‍Kx(y)f(y)dμ(y)=0.
This means for eachxin suppμ,f⊥KxinLμ2(supp X), whereμhas been restricted onto suppμ. When we restrictKonto suppμ×suppμ, the new kernelK~is again a Mercer kernel. Moreover, by (1),ℋK~=ℋK|suppμ. It follows that span{Kx|suppμ:x∈suppμ} is dense inℋK~=ℋK|suppμ. The latter is dense inLμ2(suppμ). Therefore,fis orthogonal toLμ2(suppμ); hence, as a function inLμ2(X),fis zero. This is a contradiction.
(3)⇒(4). Every nontrivial Borel measureμcan be uniquely decomposed as the difference of two mutually singular positive Borel measures:μ=μ+-μ-; that is, there exists a Borel setA⊂Xsuch thatμ+(A)=μ+(X)andμ-(A)=0. With this decomposition,
(14)∫X‍K(x,y)dμ(y)=∫X‍K(x,y){χA(y)-χX∖A(y)}d|μ|∫X‍K(x,y)dμ(y)=LK,|μ|(χA-χX∖A)(x).
Here, χAis the characteristic function of the setA, and|μ|=μ++μ-is the absolute value ofμ. As|μ|is a nontrivial positive Borel measure andχA-χX∖Ais a nontrivial function inL|μ|2(X), statement (3) implies that, as a function inL|μ|2(X),∫X‍K(x,y)dμ(y)≠0. Since this function lies inC(X), it is nonzero as a function inC(X).
The last implication (4)⇒ (1) follows directly from the Riesz Representation Theorem.The proof of Theorem4 also yields a characterization for the density of the RKHS inLμ2(X).Corollary 5.
LetKbe a Mercer kernel on a compact metric space(X,d) andμ a positive Borel measure onX. Then, ℋKis dense inLμ2(X)if and only ifLK,μhas no eigenvalue zero inLμ2(X).The necessity has been verified in the proof of Theorem4, while the sufficiency follows from the observation that anLμ2(X)functionflying in the orthogonal complement of span{Kx:x∈X}gives an eigenfunction ofLK,μwith eigenvalue zero:
(15)〈Kx,f〉Lμ2(X)=∫X‍Kx(y)f(y)dμ(y)=LK,μ(f)(x)=0.Theorem4 enables us to conclude that the density always holds for convolution type kernelsK(x,y)=k(x-y)withk∈L2(ℝn). The density for some convolution type kernels has been verified by Steinwart [10]. The author observed the density as a corollary of Theorem 4 whenk^(ξ)is strictly positive. Charlie Micchelli pointed out to the author that, for a convolution type kernel, the RKHS is always dense inC(X). So, the density problem is solved for these kernels.Corollary 6.
LetK(x,y)=k(x-y)be a nontrivial convolution type Mercer kernel onℝnwithk∈L2(ℝn). Then, for any compact subsetXofℝn,ℋKonXis dense inC(X).Proof.
It is well known thatKis a Mercer kernel if and only ifkis continuous andk^(ξ)≥0almost everywhere. We apply the equivalent statement (4) of Theorem 4 to prove our statement.
Letμbe a Borel measure onXsuch that
(16)∫X‍K(x,y)dμ(y)=0,∀x∈X.
Then, the inverse Fourier transform yields
(17)∫X‍∫ℝn‍k^(ξ)eiξ·(x-y)dξdμ(y)=∫ℝn‍k^(ξ)μ^(ξ)eiξ·xdξ=0,∀x∈X.
Here, μ^(ξ)=∫‍e-iξ·ydμ(y)is the Fourier transform of the Borel measureμ, which is an entire function.
Taking the integral onXwith respect to the measureμ, we have
(18)∫ℝn‍k^(ξ)μ^(ξ)∫X‍eiξ·xdμ(x)dξ=∫ℝn‍k^(ξ)|μ^(ξ)|2dξ=0.
For a nontrivial Borel measureμsupported on X, μ^(ξ) vanishes only on a set of measure zero. Hence, k^(ξ)=0almost everywhere, which givesk=0. Therefore, we must haveμ=0. This proves the density by Theorem 4.After the first version of the paper was finished, I learned that Micchelli et al. [11] proved the density for a class of convolution type kernelsk(x-y)withkbeing the Fourier transform of a finite Borel measure. Note that a large family of convolution type reproducing kernels are given by radial basis functions; see, for example, [12].Now we can state a trivial fact that the positive definiteness is a necessary condition for the density.Corollary 7.
LetKbe a Mercer kernel on a compact metric space(X,d). IfℋKis dense inC(X), thenKis positive definite.Proof.
Suppose to the contrary thatℋKis dense inC(X), but there exists a finite set of distinct points{xi}i=1ℓ⊂Xsuch that the matrixAx:=(K(xi,xj))i,j=1ℓis not positive definite. By the Mercer kernel property,Axis positive semidefinite. So it is singular, and we can find a nonzero vectorc:=(c1,…,cℓ)T∈ℝℓsatisfyingAxc=0. It follows thatcTAxc=0; that is,
(19)∥∑i=1ℓ‍ciKxi∥K2=〈∑i=1ℓ‍ciKxi,∑j=1ℓ‍cjKxj〉K∥∑i=1ℓ‍ciKxi∥K2=∑i,j=1ℓ‍cicjK(xi,xj)=0.
Thus,
(20)∑i=1ℓ‍ciKxi=0.
Now, we define a nontrivial Borel measureμsupported on{x1,…,xℓ}as
(21)μ({xi})=ci,i=1,…,ℓ.
Then, forx∈X,
(22)∫X‍K(x,y)dμ(y)=∑i=1ℓ‍K(x,xi)ci=∑i=1ℓ‍ciKxi(x)=0.
This is a contradiction to the equivalent statement (4) in Theorem 4 of the density.Because of the necessity given in Corollary7, one would expect that the positive definiteness is also sufficient for the density. Steve Smale convinced the author that this is not the case in general. This motivates us to present a constructive example ofC∞kernel. Denote ∥g∥W∞m:=∑j=0m‍∥g(j)∥L∞ as the norm in the Sobolev spaceW∞m.Example 8.
LetX=[0,1]. For everym∈ℕand everyi∈{0,1,…,m}, choose a real-valuedC∞functionψi,m(x)on[0,1]such that
(23)ψi,m(x)=xi,∀x∈[0,1]∖(1m+1,1m),∫01‍ψi,m(x)dx=0.
DefineKon[0,1]×[0,1]by
(24)K(x,y)=∑m=1∞‍2-m∑i=0mψi,m(x)ψi,m(y)∑i=0m∥ψi,m∥W∞m2,x,y∈[0,1].
Then, Kis aC∞Mercer kernel on[0,1]. It is positive definite, but the constant function1is not in the closure ofℋKin C(X). Hence, ℋKis not dense inC(X).Proof.
The series in (24) converges inW∞mfor anym∈ℕ. Hence, KisC∞ and is a Mercer kernel on[0,1].
To prove the positive definiteness, we let{xi}i=1ℓ⊂[0,1]be a finite set of distinct points and(ci)i=1ℓ a nonzero vector. Choosem∈ℕsuch that
(25)m≥ℓ-1,1m<min{xj:xj>0,j∈{1,…,ℓ}}.
Then, for eachj∈{1,…,ℓ}, eitherxj=0orxj>1/m. Hence,
(26)xj∈[0,1]∖(1m+1,1m),∀j=1,…,ℓ.
By the construction ofψi,m, there holds
(27)ψi,m(xj)=xji,∀i=0,1,…,m,j=1,…,ℓ.
Then,
(28)∑i,j=1ℓ‍cicjK(xi,xj)≥2-m∑i=0m∥ψi,m∥W∞m2∑i=0m‍[∑j=1ℓ‍cjψi,m(xj)]2≥2-m∑i=0m∥ψi,m∥W∞m2∑i=0ℓ-1‍[∑j=1ℓ‍cjψi,m(xj)]2.
Now, the determinant of the matrix(xji)i=0,1,…,ℓ-1,j=1,…,ℓis a Vandermonde determinant and is nonzero. Since (cj)j=1ℓ is a nonzero vector, we know that ∑j=1ℓ‍cjxji≠0 for somei∈{0,1,…,ℓ-1}. It follows that ∑i,j=1ℓ‍cicjK(xi,xj)>0. Thus, K is positive definite.
We now prove that1, the constant function taking the value1everywhere, is not in the closure ofℋKinC(X). In fact, the uniformly convergent series (24) and the vanishing property ofψi,mimply that
(29)∫01‍K(x,y)dy=∫01‍Kx(y)dy=0,∀x∈X.
Since span{Kx:x∈X} is dense in ℋK and ℋK is embedded in C(X), we know that
(30)∫01‍f(y)dy=0,∀f∈ℋK.
If 1 could be uniformly approximated by a sequence {fm} in ℋK, then
(31)1=∫01‍1(y)dy=limm→∞∫01‍fm(y)dy=0,
which would be a contradiction. Therefore,ℋKis not dense inC(X).Combining the previous discussion, we know that the positive definiteness is a nice necessary condition for the density of the RKHS inC(X) but is not sufficient.


## 3. Interpolation Schemes for Reproducing Kernel Spaces

The study of approximation by reproducing kernel Hilbert spaces has a long history; see, for example, [13, 14]. Here, we want to investigate the rate of approximation as the RKHS norm of the approximant becomes large.In the following sections, we consider the approximation error for the purpose of learning theory. The basic tool for constructing approximants is a set of nodal functions used in [6, 15, 16].Definition 9.
We say that{ui(x):=ui,x(x)}i=1ℓis the set of nodal functions associated with the nodesx:={x1,…,xℓ}⊂Xifui∈span{Kxj}j=1ℓand
(32)ui(xj)=δij={1,ifj=i,0,otherwise.The nodal functions have some nice minimization properties; see [6, 16].In [15], we show that the nodal functions{ui}i=1ℓassociated withxexist if and only if the Gramian matrixAx:=(K(xi,xj))i,j=1ℓis nonsingular. In this case, the nodal functions are uniquely given by
(33)ui(x)=∑j=1ℓ‍(Ax-1)i,jKxj(x),i=1,…,ℓ.Remark 10.
When the RKHS has finite dimensionm, then, for any ℓ≤m we can find nodal functions {uj}j=1ℓ associated with some subset x={x1,…,xℓ}⊂X, while for ℓ>m, no such nodal functions exist. When dimℋK=∞, then, for any ℓ∈ℕ, we can find a subset x={x1,…,xℓ}⊂X which possesses a set of nodal functions.The nodal functions are used to construct an interpolation scheme:(34)Ix(f)(x)=∑i=1ℓ‍f(xi)ui,x(x),x∈X,f∈C(X).
It satisfies Ix(f)(xi)=f(xi) fori=1,…,ℓ. Interpolation schemes have been applied to the approximation by radial basis functions in the vast literature; see, for example, [17–20].The errorIx(f)-fforf∈ℋKwill be estimated by means of a power function.Definition 11.
LetKbe a Mercer kernel on a compact metric space(X,d)andx={x1,…,xℓ}⊂X. The power functionεKis defined onxas
(35)εK(x):=supx∈X{+∑i,j=1ℓ‍wiK(xi,xj)wj}1/2infw∈ℝℓ{∑i,j=1ℓ‍wiK(xi,xj)wjK(x,x)-2∑i=1ℓ‍wiK(x,xi)+∑i,j=1ℓ‍wiK(xi,xj)wj}1/2}.We know thatεK(x)→0whendx:=maxx∈Xmini=1,…,ℓd(x,xi)→0. IfKis LipschitzsonX:
(36)|K(x,y)-K(x,t)|≤C(d(y,t))s,
then
(37)εK(x)≤2Cdxs.
Moreover, higher order regularity ofKimplies faster convergence ofεK(x). For details, see [16].The error of the interpolation scheme for functions from RKHS can be estimated as follows.Theorem 12.
LetKbe a Mercer kernel andAx nonsingular for a finite setx={x1,…,xℓ}⊂X. Define the interpolation scheme associated withxas (34). Then, forf∈ℋK, there holds
(38)∥Ix(f)-f∥C(X)≤∥f∥KεK(x),(39)∥Ix(f)∥K≤∥f∥K.Proof.
Letx∈X. We apply the reproducing property (3) of the functionfin
(40)Ix(f)(x)-f(x)=∑i=1ℓ‍f(xi)ui(x)-f(x).
Then,
(41)Ix(f)(x)-f(x)=∑i=1ℓ‍ui(x)〈Kxi,f〉K-〈Kx,f〉KIx(f)(x)-f(x)=〈∑i=1ℓ‍ui(x)Kxi-Kx,f〉K.
By the Schwartz inequality inℋK,
(42)|Ix(f)(x)-f(x)|≤∥∑i=1ℓ‍ui(x)Kxi-Kx∥K∥f∥K.
As〈Ks,Kt〉K=K(s,t), we have
(43)∥∑i=1ℓ‍ui(x)Kxi-Kx∥K2=K(x,x)-2∑i=1ℓ‍ui(x)K(x,xi)+∑i,j=1ℓ‍ui(x)K(xi,xj)uj(x).
However, the quadratic function
(44)Q((wi)i=1ℓ):=K(x,x)-2∑i=1ℓ‍wiK(x,xi)Q((wi)i=1ℓ):=+∑i,j=1ℓ‍wiK(xi,xj)wj
overℝℓtakes its minimum value at(ui(x))i=1ℓ. Therefore,
(45)∥∑i=1ℓ‍ui(x)Kxi-Kx∥K≤εK(x).
It follows that
(46)|Ix(f)(x)-f(x)|≤∥f∥KεK(x).
This proves (38).
AsIx(f)∈ℋK andIx(f)(xi)=f(xi)fori=1,…,ℓ, we know that
(47)Ix(f)(xi)-f(xi)=〈Kxi,Ix(f)-f〉K=0,i=1,…,ℓ.
This means thatIx(f)-fis orthogonal to span{Kxi}i=1ℓ. Hence, Ix(f)is the orthogonal projection offonto span{Kxi}i=1ℓ. Thus, ∥Ix(f)∥K≤∥f∥K.The regularity of the kernel in connection with Theorem12 yields the rate of convergence of the interpolation scheme. As an example, from the estimate forεK(x)given in [16, Proposition 2], we have the following.Corollary 13.
LetX=[0,1], s≤N∈ℕ, andK(x,y)be aCsMercer kernel such thatAxis nonsingular forx={j/N}j=0N-1. Then, forf∈ℋK, there holds
(48)∥Ix(f)-f∥C(X)≤∥f∥K{(4s)s(1+s2s)(s-1)!∥∂s∂ysK∥∞}N-s.For convolution type kernels, the power function can be estimated in terms of the Fourier transform of the kernel function. This is of particular interest when the kernel function is analytic. Let us provide the details.Assume thatkis a symmetric function inL2(ℝn)andk^(ξ)>0almost everywhere onℝn. Consider the Mercer kernel
(49)K(x,y)=k(x-y),x,y∈[0,1]n.
ForN∈ℕ, we define the following function to measure the regularity:
(50)λk(N):=n(1+12N)n-1λk(N):=×max1≤j≤n{(2π)-n∫ξ∈[-N/2,N/2]n‍k^(ξ)(|ξj|N)Ndξ}λk(N):=+(1+(N2N)n)2(2π)-n∫ξ∉[-N/2,N/2]n‍k^(ξ)dξ.Remark 14.
This function involves two parts. The first part isξ∈[-N/2,N/2]n, where(|ξj|/N)N≤2-N; hence, it decays exponentially fast asNbecomes large. The second part isξ∉[-N/2,N/2]n, whereξis large. Then, the decay ofk^(which is equivalent to the regularity ofk) yields the fast decay of the second part.
The power functionεK(x)can be bounded byλk(N)on the regular points:
(51)x:=(αN)α∈{0,1,…,N-1}n.Proposition 15.
For the convolution type kernel (49) andxgiven by (51), one has(52)εK(x)≤λk(N).
In particular, if
(53)k^(ξ)≤C0e-λ|ξ|,∀ξ∈ℝn
for some constantsC0>0andλ>4+2nln4, then there holds
(54)εK(x)≤λk(N)≤4C0(max{1eλ,4neλ/2})N/2.Proof.
Choose{wα:=wα,x(x)}α∈xas the Lagrange interpolation polynomials onx. It is a vector inℝNnfor eachx∈X. Then, εK(x)≤supx∈XQN(x), where
(55)QN(x):=k(0)-2∑α∈x‍wα,x(x)k(x-α)QN(x):=+∑α,β∈x‍wα,x(x)k(α-β)wβ,x(x).
In the proof of Theorem  2 in [16], we showed thatQN(x)≤λk(N)for eachx∈[0,1]n. Therefore,εK(x)≤λk(N).
The estimate forλk(N)in the second part was verified in the proof of Theorem  3 in [16].For the Gaussian kernels(56)K(x,y)=exp{-|x-y|2σ2},x,y∈[0,1]n,
it was proved in [16, Example 4] that, forN≥80nlog2/σ2, there holds
(57)εK(x)≤λk(N)≤2e(116n)N/2+4σπ2-nN.


## 4. Approximation Error in Learning Theory

Now, we can estimate the approximation error in learning theory by means of the interpolation scheme (34).Consider the convolution type kernel (49) on X=[0,1]n. As in [6], we denote
(58)Λk(r)∶={infξ∈[-rπ,rπ]nk^(ξ)}-1/2,r>0.
The approximation error (6) can be realized as follows.Theorem 16.
Letk∈L2(ℝn) be a symmetric function with k^(ξ)>0, and let the kernel on X=[0,1]n be K(x,y)=k(x-y). For f∈L2(ℝn) and M≤N∈ℕ, we set fM∈L2(ℝn) by
(59)f^M(ξ)={f^(ξ),ifξ∈[-Mπ,Mπ]n,0,otherwise.
Then, with x={0,1/N,…,(N-1)/N}n, one has(i)
∥Ix(fM)∥K≤∥f∥L2Λk(N);(ii)
∥fM-Ix(fM)∥C(X)≤∥f∥L2Λk(M)εK(x)≤∥f∥L2Λk(M)λk(N);(iii)
∥f-fM∥L2(X)2≤(2π)-n∫ξ∉[-Mπ,Mπ]n‍|f^(ξ)|2dξ→0(asM→∞).Proof.
(i) Fori,j∈XN:={0,1,…,N-1}n and xi=i/N, expression (33) gives
(60)〈ui,uj〉K=∑s,t∈XN‍(Ax-1)is(Ax-1)jt〈Kxs,Kxt〉K=∑s,t∈XN‍(Ax-1)is(Ax-1)jt(Ax)ts=(Ax-1)ij.
Then for g∈C(X) we have
(61)∥Ix(g)∥K2=∥∑i∈XN‍g(xi)ui(x)∥K2=∑i,j∈XN‍g(xi)g(xj)〈ui,uj〉K=(g|x)TAx-1g|x,
where g|x is the vector (g(xi))i∈XN∈ℝNn. It follows that
(62)∥Ix(g)∥K2=〈g|x,Ax-1g|x〉ℓ2≤∥Ax-1∥2∥g|x∥ℓ22=∥Ax-1∥2∑i∈XN‍|g(xi)|2,
where ∥Ax-1∥2 denotes the (operator) norm of the matrix Ax-1 in (ℝNn,ℓ2).
We apply the previous analysis to the functionfM satisfying
(63)∑j∈XN‍|fM(xj)|2=∑j∈XN‍|(2π)-n∫ξ∈[-Nπ,Nπ]nf^M(ξ)ei·(j/N)·ξdξ|2‍=∑j∈XN‍|(2π)-n∫ξ∈[-π,π]n‍f^M(Nξ)eij·ξNndξ|2≤(2π)-n∫ξ∈[-π,π]n‍|f^M(Nξ)Nn|2dξ≤Nn∥f∥L22.
Then,
(64)∥Ix(fM)∥K2≤∥Ax-1∥2Nn∥f∥L22.
Now, we need to estimate the norm∥Ax-1∥2. For convolution type kernels, such an estimate was given in [15, Theorem 2] by means of methods from the radial basis function literature, for example, [17, 21–24]. We have
(65)∥Ax-1∥2≤N-n(Λk(N))2.
Therefore,
(66)∥Ix(fM)∥K≤∥f∥L2Λk(N).
This proves the statement in (i).
(ii) Letx∈X. Then
(67)fM(x)-Ix(fM)(x)=(2π)-n∫ξ∈[-Mπ,Mπ]nf^(ξ)‍×{eix·ξ-∑j∈XN‍uj,x(x)eixj·ξ}dξ.
By the Schwartz inequality,
(68)|fM(x)-Ix(fM)(x)|≤{(2π)-n∫ξ∈[-Mπ,Mπ]n|f^(ξ)|2k^(ξ)dξ}1/2×{(2π)-n∫ℝn‍k^(ξ)|eix·ξ-∑j∈XN‍uj,x(x)eixj·ξ|2dξ}1/2.
The first term is bounded by ∥f∥L2Λk(M). The second term is
(69){∑i,j∈XN‍k(0)-2∑j∈XN‍uj,x(x)k(x-xj)+∑i,j∈XN‍ui,x(x)k(xi-xj)uj,x(x)}1/2
which can be bounded by εK(x), as shown in the proof of Theorem 12. Therefore, by (52),
(70)∥fM-Ix(fM)∥C(X)≤∥f∥L2Λk(M)εK(x)≤∥f∥L2Λk(M)λk(N).
(iii) By the Plancherel formula,(71)∥f-fM∥L2(ℝn)2=(2π)-n∫ξ∉[-Mπ,Mπ]n‍|f^(ξ)|2dξ.
This proves all the statements in Theorem 16.Theorem16 provides quantitative estimates for the approximation error:
(72)∥f-Ix(fM)∥L2(X)≤{(2π)-n∫ξ∉[-Mπ,Mπ]n‍|f^(ξ)|2dξ}1/2+∥f∥L2Λk(M)λk(N)
with
(73)∥Ix(fM)∥K≤∥f∥L2Λk(N).
Choose N=N(M)≥M such that Λk(M)λk(N)→0 as M→+∞; we have ∥f-Ix(fM)∥L2(X)→0 and the RKHS norm of Ix(fM) is controlled by the asymptotic behavior of Λk(N).Denote byΛk-1 the inverse function of Λk:
(74)Λk-1(R):=max{r>0:Λk(r)≤R}=max{r>0:k^(ξ)≥R-2∀ξ∈[-rπ,rπ]n}.
Then, our estimate for the approximation error can be given as follows.Corollary 17.
LetX=[0,1]n and f∈Hs(ℝn). Then, for R>∥f∥L2,
(75)inf∥g∥K≤R∥f-g∥L2(X)≤inf0<M≤NR{∥f∥Hs(Mπ)-s+∥f∥L2Λk(M)λk(NR)},
where NR:=[Λk-1(R/∥f∥L2)]. If s>n/2, then
(76)inf∥g∥K≤R∥f-g∥C(X)≤inf0<M≤NR{∥f∥Hss-n/2Mn/2-s+∥f∥L2Λk(M)λk(NR){∥f∥Hss-n/2}}.
In particular, when
(77)C1exp{-λ1|ξ|d}≤k^(ξ)≤C0exp{-λ|ξ|},∀ξ∈ℝn
for some C0,C1,d,λ1>0 and λ>4+2nlog4, one has(78)I(f,R)=inf∥g∥K≤R∥f-g∥L2(X)≤(2d(d+1)nd/2πdλ1)s/d(d+1)×(π-s∥f∥Hs+2s+2C0C1∥f∥L2)×{logR+12logC1-log∥f∥L2}-s/d(d+1)
provided that with the function G(r):=(1/nπ)((2/λ1)log(rC1/∥f∥L2))1/d, R satisfies
(79)G(R)≥(16λ1nd/2πd-logmax{1/eλ,4n/eλ/2})d+1,logG(R)G(R)≤(-logmax{1/eλ,4n/eλ/2})(d+1)2d+4s.Proof.
The first part is a direct consequence of Theorem16 when we choose N to be NR, the integer part of Λk-1(R/∥f∥L2).
To see the second part, we note that (77) in connection with Proposition 15 implies with Λ:=max{1/eλ,4n/eλ/2},
(80)λk(N)≤4C0exp{NlogΛ2},Λk(r)≤{C1exp{-λ1(nrπ)d}}-1/2=1C1exp{λ12(nπ)drd}.
Then, Λk-1(R/∥f∥L2)≥G(R).
ForR≥(∥f∥L2/C1)exp{(λ1/2)(nπ)d}, we can choose M∈ℕ such that
(81)12{G(R)}1/(d+1)≤M≤{G(R)}1/(d+1).
Choose N∈ℕ such that
(82)Md+12≤N≤Md+1.
Then, M≤N, and by Theorem 16,
(83)∥Ix(fM)∥K≤∥f∥L2C1exp{λ12(nπ)dMd(d+1)}≤R,Λk(M)λk(N)≤4C0C1exp{N{(nπ)d}logΛ4+N{(nπ)d}logΛ4×(logΛ4+λ1(nπ)dN-1/(d+1))}.
When
(84)N1/(d+1)≥4λ1(nπ)d-logΛ,logNN≤(-logΛ)(d+1)4s,
there holds
(85)Λk(M)λk(N)≤4C0C1exp{NlogΛ4}≤4C0C1N-s/(d+1).
Hence,
(86)∥f-Ix(fM)∥L2(X)≤∥f∥Hs(Mπ)-s+∥f∥L24C0C1(2M)s≤(∥f∥Hsπ-s+2s∥f∥L24C0C1)×2s(G(R))-s/(d+1).
When R satisfies (79), we know that
(87)N1/(d+1)≥M2≥14{G(R)1/d}1/(d+1)≥4λ1(nπ)d-logΛ,logNN≤2logMd+1Md+1≤2d+2logG(R)G(R)≤-logΛ(d+1)4s.
Hence, (84) holds true. This proves our statements.For the Gaussian kernels, we have the following.Proposition 18.
Let(88)K(x,y)=exp{-|x-y|2σ2},x,y∈X=[0,1]n.
Denote Cσ,n:=σ2nπ2/4min{log(4n),nlog2} and Cσ,n,s:=(σnπ)s/2(Cσ,ns/2+(σπ)-n/2(2e+4/σπ)). If f∈Hs(ℝn), then one has(89)I(f,R)≤Cσ,n,s(∥f∥Hs+∥f∥L2)×{logR+n2log(σπ)-log∥f∥L2}-s/4
and when s>n/2,
(90)inf∥g∥K≤R∥f-g∥C(X)≤Cσ,n,s-n/2(∥f∥Hs+∥f∥L2)×{logR+n2log(σπ)-log∥f∥L2}n/8-s/4
for R satisfying
(91)R>∥f∥L2(σπ)-n/2×exp{σ2nπ2(max{Cσ,n,80nlog2/σ2}+1)28},(92)(132Cσ,nlog(σπ)n/2R∥f∥L2)1/2≥s2(log22σnπ+12log(σπ)n/2R∥f∥L2).Proof.
The Fourier transform ofk(x)=exp{-|x|2/σ2} is
(93)k^(ξ)=(σπ)nexp{-σ2|ξ|24}.
Then,
(94)Λk(r)=(σπ)-n/2exp{σ2nr2π28}.
For(95)R≥∥f∥L2Λk(max{Cσ,n,80nlog2σ2}+1),
we can take N∈ℕ with N≥max{Cσ,n,80nlog2/σ2} such that
(96)12Λk-1(R∥f∥L2)≤N≤Λk-1(R∥f∥L2).
Here, Λk-1 is the inverse function of Λk:
(97)Λk-1(r)=22σnπ(log{(σπ)n/2r})1/2.
Then, ∥f∥L2Λk(N)≤R. Let M≤N. By Theorem 16, ∥Ix(fM)∥K≤R.
By Corollary17 and (57),
(98)∥f-Ix(fM)∥L2(X)≤∥f∥Hs(Mπ)-s+∥f∥L2Λk(M)(2e+4σπ)exp{-NC0},
where C0:=min{log(4n),nlog2}. Choose M∈ℕ such that
(99)12NCσ,n≤M≤NCσ,n.
With this choice, σ2nM2π2/8≤C0N/2. Therefore,
(100)∥f-Ix(fM)∥L2(X)≤∥f∥Hs(4Cσ,nπ2N)s/2+∥f∥L2(σπ)-n/2×(2e+4σπ)exp{-C02N}≤Cσ,n,s′(∥f∥Hs+∥f∥L2)×max{(R∥f∥L2)-s/2,exp{-C04Λk-1(R∥f∥L2)}},
where
(101)Cσ,n,s′=Cσ,ns/2+(σπ)-n/2(2e+4σπ).
When(102)C04Λk-1(R∥f∥L2)≥s2logΛk-1(R∥f∥L2),
there holds
(103)∥f-Ix(fM)∥L2(X)≤Cσ,n,s′(∥f∥Hs+∥f∥L2)×{Λk-1(R∥f∥L2)}-s/2.
This yields the first estimate.
Whens>n/2, the same method gives the error with the uniform norm.


## 5. Learning with Varying Kernels

Proposition18 in the last section shows that, for a fixed Gaussian kernel, the approximation error I(f,R) behaves as
(104)I(f,R)≤C(logR)-s/4
for functions f in Hs.In this section, we consider the learning with varying kernels. Such a method is used in many applications where we have to choose suitable parameters for the reproducing kernel. For example, in [7] Gaussian kernels with different parameters in different directions are considered. Here, we study the case when the variance parameter keeps the same in all directions. Our analysis shows that the approximation error may be improved when the kernel changes with the RKHS norm R of the empirical target function.Proposition 19.
Let(105)Kσ(x,y)=exp{-|x-y|2σ2},x,y∈X=[0,1]n.
There exist positive constants An,s and Bn,s, depending only on n and s, such that for each f∈Hs(ℝn) and R≥An,s∥f∥L2, one can find some σ=σR satisfying
(106)inf∥g∥KσR≤R∥f-g∥L2(X)≤Bn,s(logR)-s.Proof.
Take(107)σ=(80nlog2N)1/2,N4nπ(15min{2+logn2log2,n})1/2≤M≤N2nπ(15min{2+logn2log2,n})1/2,
where N depends on R. Denote Cn:=nπ2/4min{log(4n),nlog2}. As in the proof of Proposition 18, we have
(108)∥f-Ix(fM)∥L2(X)≤(Nπ)-s∥f∥Hs(320nCnlog2)s/2+Nn/2∥f∥L2(80nlog2)n/4×(2e+4N80nπlog2)exp{-C02N}.
WhenN is large enough, with a constant Cn,s′ depending on n and s, this yields
(109)∥f-Ix(fM)∥L2(X)≤Cn,s′(∥f∥Hs+∥f∥L2)N-s.
Finally, we determineN by requiring
(110)∥f∥L2Λk(N)=∥f∥L2Nn/4(80nπlog2)-n/4exp{10n2π2Nlog2}≤R≤∥f∥L2Λk(N+1).
There is a constant An,s>0 depending only on n and s such that, for R≥An,s∥f∥L2, an integer N satisfying all the previous requirements and
(111)(N+1)n/4≤exp{10n2π2(N+1)log2}
exists. This makes all the estimates valid. It follows that
(112)R≤∥f∥L2Λk(N+1)≤∥f∥L2(80nπlog2)-n/4exp{20n2π2(N+1)log2}.
Hence,
(113)N+1≥120n2π2log2log{R∥f∥L2(80nπlog2)n/4}.
Therefore, there holds ∥Ix(fM)∥Kσ≤R and
(114)∥f-Ix(fM)∥L2(X)≤2sCn,s′(∥f∥Hs+∥f∥L2)(20n2π2log2)s×{logR+n4log(80nπlog2)-log∥f∥L2}-s.
This verifies our claim for the approximation error in L2(X).Let us mention the following problem concerning learning with Gaussian kernels with changing variances.Problem 20.
What is the optimal rate of convergence of(115)sup∥f∥Hs=1inf{∥f-g∥L2(X):∥g∥Kσ≤Rforsomeσ>0}
as R tends to infinity?


## 6. Dot Product Kernels

In this section, we illustrate our results by the family of dot product type kernels. These kernels take the form(116)K(x,y)=∑j=0+∞‍aj(x·y)j,x,y∈ℝn.
When ∑j=0+∞‍|aj|R2j<∞ for some R>0, the kernel K is a Mercer kernel on X:={x∈ℝn:|x|≤R} if and only if aj≥0 for each j≥0. See [25–28]. Here, we will characterize the density for this family as [29]. Denote xα:=Πi=1nxiαi and (|α|α):=(α1+⋯αn)!/(Πi=1nαj!) for x=(x1,…,xn)∈ℝn and α=(α1,…,αn)∈ℤ+n.Corollary 21.
LetR>0, X:=[0,R]n, and the kernel K be given by (116), where aj≥0 for each j∈ℤ+ and ∑j=0+∞‍ajR2j<∞. Set J:={α∈ℤ+n:a|α|>0}. Then, ℋK is dense in C(X) if and only if span{xα:α∈J} is dense in C(X). Thus, the density depends only on the location of positive coefficients in (116). In particular, when n=1, ℋK is dense in C[0,R] if and only if
(117)a0>0,∑j∈J∖{0}‍1j=+∞.Proof.
Note that(118)Kx(y)=K(x,y)=a0+∑j=1+∞‍aj∑|α|=j‍(|α|α)xαyα=∑α∈J‍a|α|(|α|α)xαyα.
Sufficiency. Suppose that span{xα:α∈J} is dense in C(X), but ℋK is not dense in C(X). Then, by Theorem 4 there exists a nontrivial Borel measure μ on X such that
(119)∫X‍K(x,y)dμ(y)=0,∀x∈X.
Taking the integral with respect to μ and using (118), we have
(120)0=∬XK(x,y)dμ(x)dμ(y)=∑α∈J‍a|ga|(|α|α)[∫X‍xαdμ(x)]2.
Since a|α|>0 for each α∈J, there holds
(121)∫X‍xαdμ(x)=0,∀α∈J.
That is, μ annihilates each xα for α∈J. But span{xα:α∈J} is dense in C(X); μ also annihilates all functions in C(X), which is a contradiction.
Necessity. If span{xα:α∈J} is not dense in C(X), then there exists a nontrivial Borel measure μ annihilating each xα; that is, ∫X‍xαdμ(x)=0 for each α∈J. Then, (118) tells us that, for each x∈X,
(122)∫X‍K(x,y)dμ(y)=∑α∈J‍a|ga|(|α|α)xα∫X‍yαdμ(y)=0.
This in connection with Theorem 4 implies that ℋK is not dense in C(X). This proves the first statement of Corollary 21.
The second statement follows from the classical Muntz Theorem in approximation theory (see [30]): for a strictly increasing sequence of nonnegative numbers λ0<λ1,…, span{xλj:j∈ℤ+} is dense in C[0,R] if and only if λ0=0 and ∑j=1+∞‍1/λj=+∞.The conclusion in Example2 follows directly from Corollary 21.By Corollary21, we can provide more examples of dot product positive definite kernels whose corresponding RKHS is not dense. The following is such an example. However, compared with Example 8, it is not constructive, in the sense that no function outside the closure of ℋK is explicitly given.Example 22.
LetX=[0,1] and define
(123)K(x,y)=1+∑k=1+∞‍2-k∑m=0k-1‍(x·y)2k+m.
Then, K is a positive definite Mercer kernel on X, but ℋK is not dense in C(X).Proof.
Observe that the assumption in Corollary21 holds for K, a0=1>0 and
(124)J∖{0}=⋃k=1+∞{2k,2k+1,…,2k+k-1}.
Since ∑j∈J∖{0}‍(1/j)=∑k=1+∞‍∑i=0k-1‍(1/(2k+i))≤∑k=1+∞‍(k/2k)<+∞, Corollary 21 tells us that ℋK is not dense in C(X).
What is left is to show that the Mercer kernelK is positive definite. Suppose to the contrary that there exist a finite set of distinct points I⊂X and a nonzero vector c=(cs)s∈I such that
(125)∑s,t∈I‍csctK(s,t)=0.
Denote
(126)K~(x,y)=∑k=1+∞‍2-k∑m=0k-1‍(x·y)2k+m.
Then,
(127)∑s,t∈I‍csctK(s,t)=(∑s∈I‍cs)2+∑s,t∈I∖{0}‍csctK~(s,t)=0.
Hence, ∑s∈I‍cs=0 which implies that I∖{0}≠∅ and (cs)s∈I∖{0} is a nonzero vector. Also,
(128)0=∑s,t∈I∖{0}‍csctK~(s,t)=∑k=0+∞‍2-k∑m=0k-1‍(∑s∈I∖{0}‍s2k+mcs)2.
It follows that
(129)∑s∈I∖{0}‍s2k+mcs=0,∀k∈ℕ,m=0,1,…,k-1.
Choose an integer k which is not less than #(I∖{0}), the number of elements in the set I∖{0}. Then, we know that the linear system
(130)∑s∈I∖{0}‍s2k+mxs=0,m=0,1,…,#(I∖{0})
has a nonzero solution (cs)s∈I∖{0}. Hence, the matrix (s2k+m)s∈I∖{0},m=0,1,…,#(I∖{0}) is singular. So, there exists a nonzero vector (dm)m=0#(I∖{0}) such that
(131)∑m=0#(I∖{0})‍s2k+mdm=0,∀s∈I∖{0}.
As each element s in I∖{0} is nonzero, we have
(132)∑m=0#(I∖{0})‍smdm=0,∀s∈I∖{0}.
However, the determinant of the matrix (sm)s∈I∖{0},m=0,1,…,#(I∖{0}) is a Vandermonde determinant and is nonzero. This is a contradiction, as the linear system having this matrix as the coefficient matrix has a nonzero solution. Therefore, the Mercer kernel K is positive definite.An alternative simpler proof for the positive definiteness of the kernel in Example22 can be given by means of the recent results in [25, 26].After characterizing the density, we can then apply our analysis in Section3 and provide some estimates for the convergence rate of the approximation error under the assumption that all the coefficients aj in (116) are strictly positive. We will not provide details here, but only show the application of the interpolation scheme (34) to polynomials.Iff(x)=∑|α|≤M‍cα(|α|α)xα, then
(133)Ix(f)(x)-f(x)=∑|α|≤M‍cα(|α|α){∑j=1ℓ‍uj(x)xjα-xα}.
It follows from the Schwartz inequality that
(134)|Ix(f)(x)-f(x)|2≤{∑|α|≤M‍|cα|2(|α|α)a|α|}×{∑|α|≤M‍a|α|(|α|α)|∑j=1ℓ‍uj(x)xjα-xα|2}.
The first term can be bounded by
(135){∑|α|≤M‍(|α|α)|cα|2}(minj=0,1,…,Maj)-1
while the second is bounded by
(136)∑α∈ℤ+n‍a|α|(|α|α){∑i,j=1ℓ‍ui(x)uj(x)xiαxjα-2∑j=1ℓ‍uj(x)xjαxα+xα·xα}=εK(x).
Thus, the approximation error can be given in terms of the regularity of the kernel K. The regularity of the approximated function yields the rate of approximation by polynomials f=fM while the asymptotic behavior of the coefficients aj in (116) provides the control of the RKHS norm of Ix(fM).



---

*Source: 715683-2013-10-07.xml*