# Indefinite Kernel Network withlq-Norm Regularization

Authors: Zhongfeng Qu; Hongwei Sun
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

We study the asymptotical properties of indefinite kernel network withlq-norm regularization. The framework under investigation is different from classical kernel learning. Positive semidefiniteness is not required by the kernel function. By a new step stone technique, without any interior cone condition for input space X and Lτ condition for the probability measure ρX, satisfied error bounds and learning rates are deduced.


---

## Body

## 1. Introduction

Regression learning has been widely applied in economic decision making, engineering, computer science, and especially statistics. To fix ideas, let the input data spaceX be a compact domain of Rn; the output data space Y is a subset of R, and ρ is a Borel probability distribution on Z=X×Y, which the random variable (X,Y) is drawn from. Let ρ(·∣x) be the conditional distribution for x∈X, and ρX is the marginal distribution. The goal of regression learning is to learn the regression function fρ:X→Y, which is given by (1)fρx=EY∣X=x=∫Yydρy∣x.As the distributionρ is unknown, fρ can not be calculated directly. In learning theory framework, one can get an approximation of fρ from a set of observations z={zi=(xi,yi)}i=1m∈Zm identically and independently drawn according to ρ. Least square scheme is the most popular method for regression problem. The generalization error for any measurable function f, (2)Ef=∫Zfx-y2dρ,is the mean error that suffered from the use of f as a model for the process producing y from x; see Cucker and Zhou [1]. A simple computation shows that [1](3)Efρ=min∫Zfx-y2dρ,f-fρLρX22=Ef-Efρ.Thus, E(f)-E(fρ) can be used to value the learning effect for f to approximate fρ.In order to minimize the expected risk functional, we employ the empirical risk functional(4)Ezf=1m∑i=1mfxi-yi2.The empirical risk minimization (ERM) principle is to approximate the function fρ which minimizes the risk E by the function f∗ which minimizes the empirical risk (4) in some hypothesis space H. Kernel based machines usually take reproducing kernel Hilbert spaces (RKHS) HK as the hypothesis space, which is associated with a Mercer kernel K. For definitions and properties, see [2]. The well-known regularized least square regression algorithm is(5)fz,γ=argminf∈HK1m∑i=1mfxi-yi2+γfK2.The penalty term γfK2 with regularization parameter γ>0 is to avoid ill-pose and overfitting. In the literature, a variety of consistence analysis have been done, for instance, the capacity dependent ones (e.g., [3, 4] and references therein) and the capacity independent ones (e.g., [5–8]).In recent years, coefficient based regularization kernel network (CRKN) attracts more attentions:(6)fz=argminfα∈HK,x1m∑i=1myi-fαxi2+λΩα,where α=(α1,…,αm)∈Rm and fα=∑i=1m‍αiK(x,xi). In this setting, the hypothesis space HK is replaced by a finite dimension function space: (7)HK,x=fαx=∑i=1mαiKx,xi:α=α1,…,αm∈Rm,m∈N,where K:X×X→R is only asked to be continuous and uniform bounded on X×X and is called a general kernel. The penalty Ω(α) is imposed on the coefficients of function f∈HK,x.Some researches have been done for the mathematical foundation of CRKN. In [9], the frame of error analysis for this coefficient based regularization is proposed. CRKN with l2-norm regularizer and indefinite kernel is studied; error bound and learning rate are derived thorough explicit expression of solution fz and integral operator techniques, not only for independently sampling, but also for weak dependent sampling; see [10, 11].CRKN withl1-norm regularizer attracts more attention, for it often leads to sparsity of the coefficient {αz,i}i=1m of fz with properly chosen regularization parameter λ. In [12], Xiao and Zhou analyzed the coefficient regularization using the l1 norm. Under a Lipschitz condition of the kernel K, the rate of order O(m-r/2(1+n)) is obtained. It is very slow since n is usually very large. In [13], under an interior cone condition for input space X and Lτ condition for the probability measure ρX, satisfied error bound and sharp convergence rate are obtained. The shortage for this analysis is that conditions are too strict, especially for Lτ condition, since it only includes the almost uniform distribution on X. To the best of our knowledge, the probability measure ρX has no direct relation with the consistency of algorithms. So we attempt to deduce satisfied error bound under more general conditions. To this end, we introduce a new step stone technique to the consistence analysis of CRKN with l1-norm regularization in [14].In this paper, we adopt the step stone technique to study thelq norm based CRKN with 1≤q≤2, which is defined as(8)fz=fαz,whereαz=argminα∈Rm1m∑i=1myi-fαxi2+ηαq,mq,where fα=∑i=1mαiKxi(·)=∑i=1mαiK(·,xi), and the norm (9)αq,m≔mq-1∑i=1mαiq1/q.


## 2. Assumptions and Main Results

Throughout the paper, we always assume thaty≤M almost surely with some constant M>0. By this assumption, we have that fρ(x)≤M for any x∈X. Also we require the kernel K∈Cs(X×X) with s>0, and the norm KCs(X) is denoted by κ.For the bounded indefinite kernelK(x,y), we consider the Mercer kernel(10)K~x,t=∫XKx,uKt,udρXu.The integral operator associated with a general kernel T(x,y) is defined by (11)LTfx=∫XTx,ufudρXu, which is a compact positive operator. For the approximation ability of kernel K based hypothesis space, we assume that LK~-β/2fρ∈LρX2(X), for some β>0.One of the main difficulties for the analysis of CRKN is that the hypothesis space is dependent on the sample.Definition 1.
Define a Banach space(12)H1=f:f=∑i=1∞αiKti,αi∈l1,ti⊂Xwith the norm (13)f=inf⁡∑i=1∞αi:f=∑i=1∞αiKti,αi∈l1,ti⊂X.The continuity and uniform boundedness ofK ensure that H1 consists of continuous functions. Denote the ball of radius R as BR={f:f∈H1,f≤R}.Our estimate of sample error is conducted through a concentration inequality, which is based on thel2 empirical covering number of BR. The normalized l2 metric d2 on Euclidean space Rk is defined by (14)d2α,β2=1k∑i=1kai-bi2,foranyα=aii=1k,β=bii=1k∈Rk. Under the above metric, the covering number of a subset E of Rk with ϵ>0 is denoted by N2(E,ϵ).LetF be a set of functions on X,x=(xi)i=1k∈Xk. The sampling operator Sx:F→Rk is defined by Sx(f)=(f(xi))i=1k, for any f∈F. The l2 empirical covering number of F is defined by(15)N2F,ϵ=supk∈Nsupx∈XkN2SxF,ϵ.A bound forl2 empirical covering number of B1 was derived in [13]. Suppose that K∈Cs(X×X); then,(16)log⁡N2B1,ϵ≤cp1ϵp,∀ϵ>0,where cp is a constant independent of ϵ, and 0<p<2 is defined by(17)p=2nn+2swhen0<s≤1,2nn+2when1<s≤1+n2,nswhens>1+n2.Our main conclusion is about the asymptotic convergence rate of kernel network (8).Theorem 2.
Letfz be the optimal solution of the algorithm (8) with 1≤q≤2. Suppose B1 satisfies the capacity condition (16) with 0<p<2, and LK~-β/2fρ∈LρX2(X) for some β>0. Taking η=m-t such that 0<t<q/p+2, we have for any 0<δ<1, with confidence 1-δ, that there holds(18)Efz-Efρ≤C~m-tmin⁡β,1,where C~ is a constant independent of m.Corollary 3.
Under assumptions of Theorem2. Suppose that q=1 and fρ∈HK~. Taking η=mϵ-1/2+p with 1/2+p>ϵ>0, for any 0<δ<1, then with confidence 1-δ, there holds (19)Efz-Efρ=Om-1/2+p+ϵ.The condition offρ∈HK~ is equal to β≥1. When the kernel K∈C∞(X×X), the parameter p can be arbitrarily close to 2; thus, our learning rate is almost the optimal rate 1/4 for CRKN with l1-norm regularization; see [13].


## 3. Rough Error Bounds oflq-Regularization

We propose the following new error decomposition by employing a stepping-stone approach.Consider the regularized kernel network withl2 norm:(20)fz,λ=fαz,λ,whereαz,λ=argminα∈Rm1m∑i=1myi-fαxi2+λα2,m2.Thus, we have that(21)Efz-Efρ≤Efz-Efρ+ηαzq,mq+ηαz,λq,mq=Efz-Ezfz+Ezfz,λ-Efz,λ+Ezfz+ηαzq,mq-Ezfz,λ-ηαz,λq,mq+2ηαz,λq,mq+Efz,λ-Efρ≤Efz-Ezfz+Ezfz,λ-Efz,λ+2ηαz,λ2,mq+Efz,λ-Efρ.The second inequality holds by the definition of fz and fz,λ∈HK,x.Letgf(z)=(f(x)-y)2-(fρ(x)-y)2 for f∈H1. For any f,f~∈H1, we have(22)Ef-Ezf+Ezf~-Ef~=Egf-1m∑i=1mgfzi+1m∑i=1mgf~zi-Egf~.The following concentration inequality is the special case of Lemma3 in [13]; here we take α=1.Lemma 4.
LetF be a class of measurable functions on Z. Suppose that there exist constants b,c>0, such that f∞≤b and Ef2≤cEf for every f∈F. Moreover, there are some a>0 and p∈(0,2), such that(23)log⁡N2F,ϵ≤a1ϵp,∀ϵ>0. Then, for any 0<δ<1, with confidence 1-δ/2, there holds, for any f∈F,(24)Ef-1m∑i=1mfzi≤12Ef+cp′max⁡c,b2-p/2+pam2/2+p+2c+18blog⁡4/δm,where cp′ is a constant only depending on p.For anyr>0, the function set Fr is defined by Fr={gf:f∈Br}. Now we verify that the conditions in Lemma 4 hold. Firstly, gf∞≤(3M+κr)2 for any gf∈Fr, and (25)Egf2≤3M+κr2Egf. Secondly, for any gf1,gf2∈Fr, (26)gf1-gf2∞≤κr+3Mf1-f2∞.Therefore, we have that, for ∀ϵ>0,(27)N2Fr,ϵ≤N2Br,ϵκr+3M≤N2B1,ϵrκr+3M≤cprκr+3Mϵp.For any vectorα=(a1,a2,…,am), there is(28)∑i=1mai=α1,m≤∑i=1maiq1/q×m1-1/q=αq,m.Denote(29)Wr=z∈Zm:αzq,m≤r,αz,λq,m≤r. For any z∈W(r), there is fz,fz,λ∈Br.Applying (22) and Lemma 4 with b=c=(3M+κr)2 and a=cp(r(κr+3M))p, it follows that there is a subset V~r of Zm with measure at most δ/2 such that(30)Efz-Ezfz+Ezfz,λ-Efz,λ≤12Efz-Efρ+Efz,λ-Efρ+21+1κcp′cp2/2+pκr+3M21m2/2+p+40κr+3M2log⁡4/δm,∀z∈Wr∖V~r.Plugging this estimate into (21) yields that(31)Efz-Efρ+ηαzq,mq+ηαz,λq,mq≤41+1κκ+32cp′cp2/2+pmax⁡r2,M21m2/2+p+3Efz,λ-Efρ+80κ+32max⁡r2,M2log⁡4/δm+3ηαz,λ2,mq.The following excess generalization error of fz,λ was proved in [15].Proposition 5.
Letfz,λ be given by (20) and K∈Cs(X×X) with some s>0. Suppose that LK~-β/2fρ∈LρX2(X) for some β>0 and 0<λ≤1. Then, for any δ∈(0,1), take λ=m-γ with 0<γ<2/(2+p), where p is defined by (17); then, with probability 1-δ/2 there holds (32)Efz,λ-Efρ=fz-fρLρX22≤C~K,p,γlog⁡20νγ,pδνγ,pm-min⁡β,1γ,αz,λ2,m≤Cγ~log⁡20νγ,pδνγ,p/2mmax⁡1-βγ/2,0,where ν(γ,p)=(4-γ(2+p))/(2-γ(2+p)) and C~K,p,γ,Cγ~ are constants independent of δ and m.Combining this estimate with (31) leads to Proposition 6.Proposition 6.
LetK∈Cs(X×X) with some s>0. Assume that LK~-β/2fρ∈LρX2(X), for some 2≥β>0. Taking λ=m-γ with 0<γ<2/(2+p) and 0<η,δ<1, then for any r>0 there is a subset Vr of Zm with measure at most δ such that, for any z∈W(r)∖Vr,(33)Efz-Efρ+ηαzq,mq+ηαz,λq,mq≤a~m-2/2+p+m-1log⁡4δmax⁡r2,M2+b~log⁡20νγ,pδνγ,pηmmax⁡1-βqγ/2,0+m-min⁡β,1γ, where a~ and b~ are constants independent on δ,m, and η.


## 4. Refined Error Bound by Iteration

In this section, we apply an iteration technique to deduce an error bound. Proposition6 ensures that, for z∈W(r)∖Vr,(34)max⁡αzq,m,αz,λq,m≤a~1/qη-1/qm-2/2+pq+η-1/qm-1/qlog⁡4δ1/qmax⁡r2/q,M2/q+b~1/qlog⁡20νγ,pδνγ,p/qmmax⁡1-βγ/2,0+η-1/qm-min⁡β,1γ/q. We take η=m-t with 0<t≤qγ/2<q/(2+p), which yields that(35)max⁡αzq,m,αz,λq,m≤2a~log⁡4δ1/qmt/q-2/2+pqmax⁡r2/q,M2/q+max⁡2b~1/q,M2log⁡20νγ,pδνγ,p/qmγ/21-min⁡β,1≔12am,ηmax⁡r2/q,M2/q+12bm,η.It follows that, for anyr>0,(36)Wr⊂Wmax⁡am,ηmax⁡r2/q,M2/q,bm,η∪Vr. Let rj=max⁡{am,ηmax⁡{rj-12/q,M2/q},bm,η} and r0=max⁡{M,M2/q}mt/q. Hence,(37)Zm=Wr0⊂Wr1∪Vr0⊂⋯⊂WrJ∪⋃j=0J-1Vrj.For0<η≤1, we have that r0≥M, and rj≥bm,η≥M; thus, rj=max⁡{am,ηrj-12/q,bm,η}. A simple computation (see [13]) gives that(38)rJ≤max⁡a~m,η2/qJ-1r02/qJ,bm,ηa~m,ηbm,η2/qJ-1-1,bm,η≤μγ,p,δ2/qJmax⁡c~κ,p,M2/qJ,d~κ,p,M2/qJ,22+2/qb~1/qmθ~,where(39)a~m,η=am,ηq/2-q,μγ,p,δ=log⁡20νγ,pδνγ,p/qlog⁡4δ1/2-q,and c~κ,p,M and d~κ,p,M are both constants independent of m, η, δ, and by taking γ, t as 0<γ<2/(2+p) and 0<t≤qγ/2, we can deduce(40)θ~=γ21-min⁡β,1,by choosing J to be(41)J=ln⁡2/2+p-t-2-qr/21-min⁡β,1/2/2+p-t-2-qt/qln⁡2/q+1.Proof of Theorem2.
By takingγ=2t/q and replacing δ by δ/(J+1) in Proposition 6 and the above discussion, with confidence 1-Jδ/(J+1) for some 0<δ<1, the estimate (38) assures that (42)rJ=max⁡αzq1/q,αz,λq1/q≤c1~μγ,p,δJ+12/qJmθ~, where c1~ is a constant independent of m, and μ,θ~, and J are defined by (39), (40), and (41). Proposition 6 ensures that, with confidence 1-δ/(J+1), (43)Efz-Efρ≤a~m-2/2+p+m-1log⁡4J+1δmax⁡rJ2,M2+b~log⁡20J+1νγ,pδνγ,pηmmax⁡1-βqγ/2,0+m-min⁡β,1γ. Combing the above two inequalities completes the proof.



---

*Source: 6516258-2016-03-29.xml*