# Regularized Ranking with Convex Losses andℓ1-Penalty

Authors: Heng Chen; Jitao Wu
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

In the ranking problem, one has to compare two different observations and decide the ordering between them. It has received increasing attention both in the statistical and machine learning literature. This paper considersℓ1-regularized ranking rules with convex loss. Under some mild conditions, a learning rate is established.


---

## Body

## 1. Introduction

In the ranking problem, one has to compare two different observations and decide the ordering between them. The problem of ranking has become an interesting field for researchers in machine learning community. It has received increasing attention both in the statistical and machine learning literature.The problem of ranking may be modeled in the framework of statistical learning (see [1, 2]). Let (X,Y) be a pair of random variables taking values in 𝒳×ℝ. The random observation X models some object and Y denotes its real-valued label. Let (X′,Y′) denote a pair of random variables identically distributed with (X,Y) (with respect to the probability ℙ) and independent of it. In the ranking problem one observes X and X′ but not their labels Y and Y′. X is “better” than X′ if Y>Y′. We are to construct a measurable function f:𝒳×𝒳→ℝ, called a ranking rule, which predicts the ordering between objects in the following way: if f(X,X′)≥0, we predict that X is better than X′. A ranking rule f has the property f(x,x′)f(x′,x)≤0. The performance of a ranking rule f is measured by the ranking error:
(1)L(f)=ℙ(sign(Y-Y′)f(X,X′)<0),
that is, the probability that f ranks two randomly drawn instances incorrectly. It is easily seen that L(f) attains its minimum L*, over the class of all measurable functions, at the ranking rule
(2)f*(x,x′):=sgn(2η(x,x′)-1)withη(x,x′)=ℙ(Y>Y′∣X=x,X′=x′).In practice, the best rulef* is unknown since the probability ℙ is unknown. A widely used approach for estimating L* is the empirical risk minimization with convex loss.Definition 1.
one says thatϕ:ℝ→[0,∞) is a ranking loss (function) if it is convex, differentiable at 0 with ϕ′(0)<0, and the smallest zero of ϕ is 1.Examples of ranking loss include the least square lossϕ(t)=(1-t)2 and q-norm SVM loss ϕq(t)=(1-t)+q, where q≥1 and t+=max{0,t} for t∈ℝ.The risk of a measurable functionf is defined as Q(f)=𝔼[ϕ(sign(Y-Y′)f(X,X′))]. Denote by fϕ a minimizer of Q(f) over the set of all measurable and antisymmetric functions. For example, as in the classification case (see [3, 4]), fϕ1=f*, and for q>1,(3)fϕq(x,x′)=(1+f*(x,x′))1/(q-1)-(1-f*(x,x′))1/(q-1)(1+f*(x,x′))1/(q-1)+(1-f*(x,x′))1/(q-1),fϕqfϕqfϕqfϕqfϕqfϕqfϕqfϕqfϕqfϕqfϕqfϕq11x,x′∈𝒳.The following inequality holds for anyf:
(4)L(f)-L*≤{Q(f)-Q*,ifϕ(t)=(1-t)+,cQ(f)-Q*,ifϕ′′(0)≥0,
where Q*=Q(fϕ) and c is some constant.Before proceeding further, we introduce the notion of Reproducing Kernel Hilbert Space (RKHS). Recall that a continuous functionK(σ,σ′) is a Mercer kernel on a set Σ, if K(σ,σ′)=K(σ′,σ),∀σ,σ′∈Σ, and given an arbitrary finite set {σ1,…,σn}⊂Σ, the matrix K=(K(σi,σj))i,j=1n is positive semidefinite. The RKHS ℋK associated with the Mercer kernel K is the completion of span{Kσ=K(σ,·)∣σ∈Σ}, with respect to the inner product given by 〈Kσ,Kσ′〉K=K(σ,σ′). See [5] and ([6, Ch. 4]) for details.For convenience, we assume hereafter that the Mercer kernelsK on 𝒳2×𝒳2 are symmetric in the sense that
(5)K((u,u′),(x,x′))=K((u′,u),(x′,x)),1111111111111111111111∀u,u′,x,x′∈𝒳.
Such examples are Mercer kernels K of either form K(s,t)=k(|s-t|2) or K(s,t)=k(〈s,t〉),s,t∈𝒳2, where |·|2 and 〈·,·〉 are the Euclidean norm and inner product, respectively.Since the best ranking rulef* is antisymmetric, it is reasonable that we restricted ourselves to the subspace ℋas of anti-symmetric functions in ℋK; that is,
(6)ℋKas={f∣f∈ℋK,f(x,x′)=-f(x′,x),∀x,x′∈𝒳}.
For any xi∈𝒳,i=1,…,n, and αij∈ℝ with αij=-αji,i,j=1,…,n, it is easily seen that
(7)f=∑i,j=1n‍αijK(xi,xj)∈ℋKas.
Conversely, any anti-symmetric function f∈span{K(xi,xj)}i,j=1n with above expression should satisfy αij=-αji,i,j=1,…,n, provided detK>0.For a set of samplesz={Z1,…,Zn}⊂𝒳2, let
(8)Ωz(f)=inf{∑i,j=1n‍|αij|∣f=∑i,j=1n‍αijK(xi,xj)};ℋK,z={∑i,j=1n‍αijK(xi,xj)},ℋK,zas={∑i,j=1n‍αijK(xi,xj)∣αij=-αji}.Forλ>0, the ℓ1-penalty regularized ranking rule fz,λ is the minimizer of the minimization problem
(9)fz,λ=argminf∈ℋK,zas{Qn(f)+λΩz(f)},
where Qn(f), known as empirical risk, is given by
(10)Qn(f)=1n(n-1)∑i≠j‍ϕ(sign(yi-yj)f(xi,xj)).Associated with any ranking rulef, we construct another ranking rule as follows:
(11)π(f)(x,x′)={sign(f(x,x′)),if|f(x,x′)|>1,f(x,x′),if|f(x,x′)|≤1.
Clearly, π(f) gives the same ranking rule as f and it satisfies
(12)Q(π(f))≤Q(f),Qn(π(f))≤Qn(f).Hereafter, we denotegn=π(fz,λ). The goal of this paper is to bound the excess error Q(gn)-Q*, which in turn together with (4) up bounds the excess ranking error L(gn)-L*. The main result of this paper is, under mild conditions, to establish a learning rate for ℓ1-penalty regularized ranking rules with convex loss.Classification with convex loss, in particular forq-norm SVMs, has been the subject of many theoretical considerations in recent years. The 1-norm SVMs with regularizer being RKHS norm for ranking was investigated in [2, 7]. The ℓ1-penalty has been used in [8, 9] for classification problems under the framework of SVMs. It is well known that ℓ1-regularization usually leads to solution with sparse representation (see, e.g., [10–13]). In this paper, we consider ranking with convex loss and ℓ1-penalty.In [2], the RKHS-norm SVMs for ranking was proposed. But it was implemented over a ball BR={f∈ℋ∣|∥f∥K≤R} of ℋK, not the whole RKHS ℋK; that is, it solves the minimization problem
(13)fn=argminf∈BRQn(f)+λ∥f∥K2.
A convergence rate for Q(fn)-inff∈BRQ(f) has been established for Gaussian kernel. The approximation error inff∈BRQ(f)-Q* was not considered there. The asymptotic behavior of the same algorithm implemented over the whole RKHS ℋK was investigated in [7]. Moreover, a fast learning rate O(1/n) is obtained under some conditions.We would like to mention a recent paper [14], where the error ℰ(f) of function f is defined by ℰ(f)=𝔼((Y-Y′-f(X)+f(X′))2). A convergence rate for the minimizer of the regularized empirical error was established. The author made use of the technique of estimation via integral operator developed in [15].The rest of the paper is organized as follows. In Section2, after making some assumptions, we state the main result, an upper bound for Q(gn)-Q*+λΩz(fz,λ). As usual, it is decomposed as a sum of three terms, sample error, hypothesis error, and approximation error. Sections 3 and 4 are devoted to the estimations of hypothesis error and sample error, respectively. A proof of the main result is given in Section 5.


## 2. Assumptions and Main Results

For the statement of the main results, we need to introduce some notions and make some assumptions.Denotegf=ϕ(sign(y-y′)f(x,x′))-ϕ(sign(y-y′)fϕ(x,x′)). The following assumption is a bound for variance of gf, which is adopted by many authors.Assumption 2.
There is a constantα∈[0,1] such that for any M,
(14)𝔼(gf2)≤c1(𝔼(gf))α,∀f:𝒳2⟶[-M,M],
where c1=c1(M) is a constant.Forϕq(t)=(1-t)+q, the assumption is satisfied [16] for
(15)α={1,if1<q≤2,2q,if2<q.It is known in [17] that if there is some positive constant C such that
(16)ℙ(|2η(X,X′)-1|≤ξ)≤Cξα/(1-α),∀ξ>0,
then the assumption is satisfied for ϕ1(t)=(1-t)+.Suppose hereafterκ:=sups∈𝒳2K(s,s)<∞. We note that, for any Mercer kernel K,
(17)sups∈𝒳2K(s,s)=sups,s′∈𝒳2K(s,s′).
We now construct a set of functions which contains ℋK,z and is independent of the samples.Definition 3.
The Banach spaceℋ is defined as the function set on 𝒳2 containing all functions of the form
(18)f=∑i=1∞‍aiKsi,{ai}i=1∞∈ℓ1,si∈𝒳2,
with the norm
(19)∥f∥:=inf{∑i=1∞‍|ai|f=∑i=1∞‍aiKsi}.Obviously,ℋK,z⊂ℋ,∀z∈Zn. By the definition of κ and (17), one has
(20)∥∑i=N1N2‍aiKsi∥K2=∑i,j=N1N2‍aiajK(si,sj)≤κ(∑i=N1N2‍|ai|)2,
which implies that the series ∑i=1∞‍aiKsi converges in ℋK. Consequently, f∈ℋK and ∥f∥K≤κ∥f∥. The following also holds: ∥f∥C≤κ∥f∥,∀f∈ℋ, where ∥f∥C=sups∈𝒳2|f(s)| for f∈C(𝒳2).Denoteℋas={f∈ℋ∣f(x,x′)=-f(x′,x)}. The approximation error of Q* by Q(f) with f∈ℋas is defined as
(21)D(λ):=inff∈ℋas{Q(f)-Q*+λ∥f∥}.Denote the minimizer(22)fλ:=argminf∈ℋas{Q(f)+λ∥f∥},λ>0.The next assumption is concerned with the approximation power ofℋas to fϕ.Assumption 4.
There are positive constantsc2 and β such that
(23)𝒟(λ)=Q(fλ)-Q*+λ∥fλ∥≤c2λβ,∀λ>0.Recallfϕ(x,x′)=-fϕ(x′,x). The above assumption is not too restrict.Assumption 5.
(i) The kernelK satisfies a Lipschitz condition of order γ with 0<γ<1; that is, there exists some c3>0 such that
(24)|K(s,t)-K(s,t′)|≤c3|t-t′|2γ.
(ii) The ranking loss has an increment exponent θ≥1; that is, there exist some constants θ≥1,c4 such that
(25)ϕ(t)≤c4(1+|t|)θ,ϕ±′(t)≤c4(1+|t|)θ-1,t∈ℝ,where ϕ±′ denotes the right- and left-sided derivatives of ϕ, respectively.Assumption 6.
The margin distributionρX satisfies condition Lτ with 0<τ<∞; that is, for some c5>0 and any ball B(x,δ):={u∈𝒳∣|u-x|2<δ}, one has
(26)ρX(B(x,δ))≥c5δτ,∀x∈𝒳,0<δ≤1.The last assumption concerns covering numbers. For a subset𝒮 of a space with pseudometric ρ and δ>0. The covering number 𝒩(δ,𝒮,ρ) is defined to be the minimal number l such that there exist l disks with radius δ covering 𝒮. When Σ is compact this number is finite.Assumption 7.
(i) There are someα>0 and cα>0 such that
(27)𝒩(δ,𝒳,|·|2)≤c6(1δ)α,∀δ>0.
(ii) For R>0, let BR={f∈ℋas∣∥f∥≤R}. There are some constant s∈(0,1),c7>0 such that
(28)log𝒩(δ,B1,∥·∥∞)≤c7δ-s,∀δ>0.It was shown in [18], under Assumptions 5(i), 6, and 7(i), that the following holds:
(29)log𝒩(δ,𝒳,|·|2)≤c6(4c3δ)α/γlog(2+4κδ),∀0<δ<1.
Therefor (ii) in Assumption 7 holds provided that α/γ<1.We are in a position to state the main result of this paper. The proof is given in Section5.Theorem 8.
For anyε∈(0,β), under the Assumptions 2–7, one has confidence at least 1-Cεe-t(30)Q(gn)-Q*+λΩz(fz,λ)≤C′(max{(logn+t)γ/τ,t})(2-α+s)/(2-α)n-(β-ε)μ,
where μ=min{γ/τ(β+(1-β)θ),1/(β+(1-β)θ),1/((2-α)β+s)} and Cε, C′ are constants independent of t or n.The first step of the proof is to decomposeQ(gn)-Q*+λΩz(fz,λ) into errors of different types as the following:
(31)Q(gn)-Q*+λΩz(fz,λ)=S(z,λ)+P(z,λ)+D(λ),
where
(32)S(z,λ)={Q(gn)-Qn(gn)}+{Qn(fλ)-Q(fλ)},
referred to as sample error and
(33)P(z,λ)={Qn(gn)+λΩz(fz,λ)}-{Qn(fλ)+λ∥fλ∥},
referred to as hypothesis error. We bound hypothesis error and sample error in the next two sections, respectively.In the estimation of sample error, Hoeffding's decomposition ofU-statistic, which breaks U-statistic into a sum of iid random variables and a degenerate U-statistic (see Section 4 for details), is a useful tool.


## 3. Hypothesis Error

In this section, we bound hypothesis errorP(z,λ). This error is caused as we switch from the minimizer fz,λ of Qn(f)+λΩz(f) in ℋK,zas to the minimizer fλ of Q(f)+λ||f|| in ℋas. Such errors are estimated in some papers, for example, [7, 18], and so forth. We note that, different from [18, 19], the underlying spaces ℋK,zas and ℋas are sets of antisymmetric functions. We begin with the representations of the functions.Lemma 9.
Letf∈ℋas. For any η>0, one has a representation:
(34)f=12∑i=1∞‍ai(K(xi,ui)-K(ui,xi)),xi,ui∈𝒳,∑i=1∞‍|ai|≤∥f∥+η.Proof.
For anyη>0, there are sequences {si}i=1∞∈𝒳2 and {ai}i=1∞∈ℓ1 such that f=∑i=1∞‍aiKsi,si∈𝒳2 and ∑i=1∞‍|ai|≤∥f∥+η.
Denotesi=(xi,ui),xi,ui∈𝒳,i=1,2,…. It follows from (5) that
(35)f(x′,x)=∑i=1∞‍aiK((ui,xi),(x,x′)).
The proof is complete by f(x,x′)=1/2(f(x,x′)-f(x′,x)).A set{xi}i=1n⊂𝒳 is said to be Δ-dense in 𝒳 if for any x∈𝒳 there exists some 1≤j≤n such that |x-xj|2<Δ.Proposition 10 ([19], Proposition 3.1).
Let{Xj}j=1n be drawn independently according to ρX. Then for any t>1, under Assumption 6 and (i) in Assumption 7, with confidence at least 1-e-t,{Xj}j=1n is cα,τ((logn+t)/n)γ/τ-dense in 𝒳, where cα,τ is a constant that depends only on α and τ.The hypothesis errorP(z,λ) is bounded by the following proposition.Proposition 11.
Assume Assumptions5 and 6. Then for any t>1, with confidence at least 1-e-t, there holds
(36)P(z,λ)≤C∥fλ∥∞(logn+tn)γ/τ×(1+∥fλ∥∞+∥fλ∥∞(logn+tn)γ/τ)θ-1,
where C′ is a constant independent of z,λ,m, and t. (hereafter, C and C′ are constants which are independent of R,t,n, or λ, and may changes from line to line.)Proof.
The proof follows the line of [19, 20]. For any η>0, let the representation fλ=∑i=1∞‍bi(K(xi,ui)-K(ui,xi)) with ∑i=1∞‍|bi|≤(∥fλ∥∞+η)/2 be given in Lemma 9.
By Proposition11, with confidence at least 1-e-t, for any i=1,2,…,n, there are some Xji,Xki∈{Xi}i=1n such that max{|xi-Xji|2,|ui-Xki|}≤cα,τ((logn+t)/n)1/τ. For an integer N, which will be determined later, denote f=∑i=1N‍bi(K(Xji,Xki)-K(Xki,Xji))∈ℋK,zas. So by Assumption 7,
(37)∥f-∑i=1N‍bi(K(xi,ui)-K(ui,xi))∥∞≤C(∥fλ∥+η)(logn+tn)γ/τ,
where C=c3cα,τγ.
ChooseN such that ∑j=N+1∞‍|bj|<η/2. Therefore
(38)∥∑i=1N‍bi(K(xi,ui)-K(ui,xi))-fλ∥∞≤2κ∑j=N+1∞‍|bj|≤κη.
Consequently, ∥f-fλ∥∞≤Dη:=C(∥fλ∥∞+η)((logn+t)/n)γ/τ+κη, which together with
(39)|Qn(f1)-Qn(f2)|≤c4(1+max{∥f1∥∞,∥f2∥∞})θ-1∥f1-f2∥∞
yields, with confidence at least 1-e-t,
(40)Qn(f)≤Qn(fλ)+c4(1+∥fλ∥∞+Dη)θ-1Dη.
On the other hand, since f∈ℋK,zas, the following holds by (12) and (9), with confidence at least 1-e-t:
(41)Qn(gn)+λΩz(fz,λ)≤Qn(fz,λ)+λΩz(fz,λ)≤Qn(f)+2λ∑j=1N‍|bj|≤Qn(f)+λ(∥fλ∥+η),
which together with (40) completes the proof by letting η→0.The above bound forP(z,λ) is the same as in [20], both using of the same density of {Xi}i=1n in 𝒳. However, the functions considered there are defined on 𝒳, instead of 𝒳2 as present.


## 4. Sample Error

As in [2, 7], Hoeffding's decomposition plays an important role in the estimation for sample error. For any f(x,x′),x,x′∈𝒳, denote
(42)φf(z,z′)=ϕ(sign(y-y′)f(x,x′)),z=(x,y),z′=(x′,y′).
By Hoeffding's decomposition of U-statistic, we have
(43)Q(f-fϕ)-Qn(f-fϕ)=2(Q(f-fϕ)-Pn(Pφf-Pφfϕ))-Un(hf-hfϕ),
where hf(z,z′)=φf(z,z′)-Pφf(z)-Pφf(z′)+Q(f) and, for any g(z,z′),
(44)Pg(z)=𝔼(g(Z,Z′)∣Z=z),Pn(g)=1n∑i=1n‍g(Zi),Un(g)=1n(n-1)∑i≠j‍g(Zi,Zj).Moreover, for any ranking rulef, we denote gf(z)=Pφf(z)-Pφfϕ(z). Then
(45)Q(f-fϕ)-Pn(Pφf-Pφfϕ)=𝔼(gf)-Pn(gf).
It is the deviation of sum of independent random variables from their mean.As seen, in Hoeffding's decomposition (43), the first term is a sum of iid variables and the second term Un(hf-hfϕ) is a degenerate U-statistic. The degeneration means 𝔼(Un(hf(Z,Z′)-hfϕ(Z,Z′))∣Z) = 0,∀Z.Denote(46)S1=Q(gn)-Q(fϕ)-(Qn(gn)-Qn(fϕ))=Q(gn-fϕ)-Qn(gn-fϕ),S2=Qn(fλ)-Qn(fϕ)-(Q(fλ)-Q(fϕ))=Qn(fλ-fϕ)-Q(fλ-fϕ),
so that the sample error Q(gn)-Qn(gn)+Qn(fλ)-Q(fλ)=S1+S2.We first estimateS1. Since gn depends on z, by (43) and (45), we need to consider the suprema of the sets
(47){𝔼(gπ(f))-Pn(gπ(f))∣F∈ℱ},{|Un(hπ(f)-hfϕ)|∣F∈ℱ},
where ℱ, containing gn, is (a subset of) a ball in ℋas.With the above decomposition and the methods in [21], the following proposition is established for the ball {f∈ℋKas∣∥f∥K≤R} and ϕ(t)=(1-t)+ in [7]. The Assumption 2 and the condition on the covering number of {f∈ℋKas∣∥f∥K≤R} play a crucial role. The arguments also work in the present setting; that is, for the ball BR={f∈ℋas∣∥f∥≤R}. For this we note that ϕ satisfies |ϕ(t)-ϕ(t′)| ≤ C|t-t′|,t,t′∈[-1,1]. Therefore, under (ii) of Assumption 5 and (ii) of Assumption 7, the covering number 𝒩(δ,𝒢,∥·∥∞) of 𝒢={gπ(f)∣f∈BR} satisfies log𝒩(δ,𝒢,∥·∥∞)≤C(R/δ)s. The interested reader may refer to [7, 21] for the details.Proposition 12.
LetR>0 and t>0. Under Assumption 2, (ii) of Assumption 5, and (ii) of Assumption 7, one has confidence at least 1-e-t,
(48)𝔼(gπ(f))-Pn(gπ(f))≤δ0+δ01-(α/2)(𝔼(gπ(f)))(α/2),123132132132132132132132132132132111∀f∈BR,
where δ0 is bounded by
(49)δ0≤C((tn)1/(2-α)+(Rsn)1/(2-α+s)),
with C being a constant independent of R,t, and n.The estimation for the supremumsupf∈ℱR|Un(hπ(f)-hfϕ)| of U-process is much involved. The supremum of U-processes has been studied in a few papers. The following lemma follows from the proof of ([22, Theorem 3.2, m=2]).Lemma 13.
Suppose that a function classℱ satisfies the following conditions. (i)
For anyf∈ℱ, f(z,z′)=f(z′,z) and 𝔼(f(Z,Z′)∣Z)=0.(ii)
ℱ is uniformly bounded by a universal constant C0.(iii)
Cℱ:=∫0∞‍log𝒩(δ,ℱ,∥·∥∞)dδ<∞.Then
(50)𝔼exp(λΓn)≤Cexp(C′λ2Cℱ),∀λ>0,
where C, C′ are some constants, independent of Cℱ, and
(51)Γn=supf∈ℱ|(n-1)Un(f)|.Proposition 14.
Suppose that (ii) in Assumption7 holds. Then one has with confidence at least 1-Ce-t(52)supf∈ℱR|Un(hπ(f)-hfϕ)|≤C′(Rs+1)tn,
where ℱR={hπ(f)∣f∈BR} and C,C′ are some positive constants.Proof.
We first claim thatℱR satisfies the conditions in Lemma 13. Indeed, condition (i) holds by definition of hπ(f) and f(x,x′)=-f(x′,x) for any f∈BR. Also, by definition of hf, for any f∈ℱR, ||hπ(f)||∞≤4ϕ(-1), implying (ii). Moreover, by (ii) of Assumption 5(53)∥hπ(f1)-hπ(f2)∥∞≤C∥π(f1)-π(f2)∥∞≤C∥f1-f2∥∞
we have
(54)log𝒩(ℱR,δ,∥·∥∞)≤log𝒩(BR,δC,∥·∥∞)≤c7(CR)sδ-s
provided (ii) in Assumption 7. This establishes (iii), as claimed.
Applying Markov's inequality toexp(λΓn), with λ=t/2C′Rs and appealing to Lemma 13, we have ℙ(Γn>t)≤Ce-t/(4C′Rs),∀t>0; that is,
(55)ℙ(Γn>4C′Rst)≤Ce-t,∀t>0.
For single function hfϕ, it is known in ([23, Proposition 2.3]) that
(56)ℙ(|Un(hfϕ)|≥C′tn-1)≤Ce-t,
which together with (55) completes the proof.The estimation forS2 is easy since fλ does not change with the set z of samples.Proposition 15.
Assume Assumption2. For any t>0, one has with confidence at least 1-Ce-t(57)S2≤C′t((1+κ∥fλ∥∞)θ3n+(1n)1/(2-α))+D(λ),
where C,C′ are some constants, independent of λ,t and n.Proof.
Clearly, the functiongfλ(Z) satisfies ∥gfλ∥∞≤C(1+∥fλ∥∞)θ. Then, by Assumption 2, we conclude, as in [20, 21], with confidence at least 1-e-t, that
(58)Pn(gfλ)-(Q(fλ)-Q*)≤C′t((1+∥fλ∥∞)θ3n+(1n)1/(2-α))+D(λ).
It remains to estimateUn(hfλ-hfϕ). For any single function g with g(z,z′)=g(z′,z) and 𝔼[g(Z,Z′)∣Z]=0,∀Z, we have by [23, Proposition 2.3]
(59)ℙ(|Un(g)|≥C′t∥g∥∞n-1)≤Ce-t,
which together with ∥hfλ-hfϕ∥∞≤C′(1+∥fλ∥∞)θ implies, with confidence at least 1-Ce-t, that
(60)|Un(hfλ-hfϕ)|≤C′(1+∥fλ∥∞)θtn,
where C and C′ are constants. The proof is complete.


## 5. Proof of Theorem8

Theorem 16.
ForR such that Ωz(fz,λ)≤R and any t>1, under Assumptions 2–7, one has with confidence at least 1-Ce-t(61)Q(gn)-Q*+λΩz(fz,λ)≤C′(+(Rsn)1/2-α+s+(Rs+1)tn+tλ(β-1)θn+λβ(logn+tn)γ/τλ(β-1)θ+(tn)1/(2-α)+(Rsn)12-α+s)(logn+tn)γ/τλ(β-1)θ+(tn)1/(2-α)+(Rsn)1/(2-α+s)+(Rs+1)tn+tλ(β-1)θn+λβ(logn+tn)γ/τλ(β-1)θ+(tn)1/(2-α)+(Rsn)12-α+s),
where C,C′ are constant independent of R,t, or n.Proof.
We note that(62)∥fλ∥∞≤κ∥fλ∥≤κD(λ)λ≤Cλβ-1.
By Ωz(fz,λ)≤R, a combination of Propositions 11, 12, 14, and 15 yields that, with confidence at least 1-Ce-t,
(63)Q(gn)-Q*+λΩz(fz,λ)≤C1(logn+tn)γ/τλ(β-1)θ+δ0+δ01-α/2{Q(f)-Q*}α/2+C2(Rs+1)tn+C3t(λ(β-1)θ3n+(1n)1/(2-α))+2λβ,
where Ci,i=1,2,3, are constants, and δ0 is bounded by (49).
Puttingx=Q(gn)-Q*+λΩz(fz,λ) and ν=α/2 into the implication relation
(64)x≤axν+b,a,b,x>0⟹x≤max{(2a)1/(1-ν),2b},
we obtain (61) from (63). Therefore, the conditional probability of the event that inequality (61) holds, given the event Ωz(fz,λ)≤R, is at least 1-Ce-t. The proof is complete.For anyR, denote the random event Ωz(fz,λ)≤R by ξR. Obviously, ℙ(ξR)=1 for R=ϕ(0)/λ. However, to prove Theorem 8, a smaller R with ℙ(ξR)=1 is desired. To this end, we apply the iteration technique for estimation of Ωz(fz,λ) introduced in [17].Recall thatμ is given in Theorem 8. It is easily seen that, for λ=n-μ,R≤n1/s,
(65)(1n)γ/τλ(β-1)θ≤λβ,1nλ(β-1)θ≤λβ,(1n)1/(2-α)≤(Rs+1)n≤(Rsn)1/(2-α+s)≤λβ(λ1-βR)s/(2-α+s).
Therefore, we have, by Theorem 16, with the conditional probability at least 1-Ce-t, given ξR,
(66)Q(gn)-Q*+λΩz(fz,λ)≤C′max{(logn+t)γ/τ,t}λβ((λ1-βR)s/(2-α+s)+2).
If λβ-1R-1=O(1), the above inequality becomes
(67)Q(gn)-Q*+λΩz(fz,λ)≤C′max{(logn+t)γ/τ,t}λβ(λ1-βR)s/(2-α+s).
Consequently, given event ξR with λβ-1R-1=O(1),R≤n1/s, we have with confidence at least 1-Ce-t,
(68)∥fz,λ∥≤Ωz(fz,λ)≤r(R)≔C′max{(logn+t)γ/τ,t}×λ(β-1)((1-s)/(2-α+s))Rs/(2-α+s).LetR(0)=ϕ(0)/λ,R(k)=r(R(k-1)),k=1,2,…. By induction, it is easy to prove λβ-1(R(k))-1 = O(1),R(k)≤n1/s. Since ℙ{ξR0}=1, we have with confidence at least 1-kCe-tΩz(fz,λ) ≤ R(k),k=1,2,…,. Clearly,
(69)R(k)≤(C′max{(logn+t)γ/τ,t})(1-νk+1)/(1-ν)×λβ-1λ-(1/(2-α+s))k+1,kkkkkkkkk=1,2,…,
where ν=s/(2-α+s)<1.For anyε>0, let k be the smallest integer such that (1/(2-α+s))k+1<ε. Substituting R=R(k) into (67), we bound the right hand side of (67) by (C′max{(logn+t)γ/τ,t})1/(1-ν)λβ-ε, with confidence at least 1-Cεe-t, where Cε=kC. This completes the proof.



---

*Source: 927827-2013-12-05.xml*