# Error Bounds forlp-Norm Multiple Kernel Learning with Least Square Loss

Authors: Shao-Gao Lv; Jin-De Zhu
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

The problem of learning the kernel function with linear combinations of multiple kernels has attracted considerable attention recently in machine learning. Specially, by imposing anlp-norm penalty on the kernel combination coefficient, multiple kernel learning (MKL) was proved useful and effective for theoretical analysis and practical applications (Kloft et al., 2009, 2011). In this paper, we present a theoretical analysis on the approximation error and learning ability of the lp-norm MKL. Our analysis shows explicit learning rates for lp-norm MKL and demonstrates some notable advantages compared with traditional kernel-based learning algorithms where the kernel is fixed.


---

## Body

## 1. Introduction

### 1.1. Overview of Multiple Kernel Learning

Kernel methods such as Support Vector Machines (SVMs) have been extensively applied to supervised learning tasks such as classification and regression. The performance of a kernel machine largely depends on the data representation via the choice of kernel function. Hence, one central issue in kernel methods is the problem of kernel selection; a great many approaches to selecting the right kernel have been studied in the literature [1–4] and other references therein.We begin with reviewing the classical supervised learning setup. Let(X,d) be a compact metric space and Y⊆ℝ, given a labeled sample z={(xi,yi)}i=1m⊆Z:=X×Y, sampled i.i.d. according to an unknown distribution ρ supported on Z, the goal is to estimate a real-valued function fz depending on the sample, that generalizes well on new and unseen data. A widely used approach to estimate a function from empirical data consists in minimizing a regularization functional in a Hilbert space ℋ of real-valued functions: X→ℝ. Typically, a regularization scheme estimates f as a minimizer of the functional
(1.1)Ez(f)+λΩ(f),
where ℰz(f)=(1/m)∑i=1m‍V(f(xi),yi) is the empirical risk of hypothesis f, measured by a nonnegative loss function V:ℝ×Y→ℝ+. In addition, Ω:ℋ→ℝ is a regularizer and λ>0 is a trade-off regularization parameter.In this paper, we assume thatℋ is a reproducing kernel Hilbert space (RKHS) ℋK with kernel K, see [5]. Every kernel K corresponds to a feature mapping ΨK:X→ℋK satisfying K(x,y)=〈ΨK(x),ΨK(y)〉K, and each element of ℋK has the following form:
(1.2)fw(x)=〈w,ΨK(x)〉K,∀w∈HK.By restricting the regularization to be the formΩ(f)=∥f∥K2, there is a lot of studies from different perspectives such as statistics, optimal recovery and machine learning [6–9], and other references therein. Regularization in an RKHS has a number of attractive features, including the availability of effective error bounds and stability analysis relative to perturbations of the data (see Cucker and Smale [7]; Wu et al. [10]; Bousquet and Elisseeff [6]). Moreover, the optimization problem (1.1) in an RKHS can be reduced to seek for solution in a finite-dimensional space. Although it is simple to prove, this result shows that the variational problem (1.1) can be computational easily.Because of their simplicity and generality, kernels and associated RKHS play an increasingly important role in Machine Learning, Pattern Recognition and Artificial Intelligence. When the kernel is fixed, an immediate concern is the choice of the regularization parameterλ. This is typically solved by means of cross validation or generalized cross validation [11]. However, the performance of kernel methods critically relies on the choice of the kernel function. A natural question is how to choose the optimal kernel in a collection of candidate kernels.Kernel learning can range from the width parameter selection of Gaussian kernels [9, 12] to obtaining an optimal linear combination from a set of finite candidate kernels. The latter is often referred to as multiple kernel learning in machine learning and nonparametric group Lasso in statistics [13]. Lanckriet et al. [3] pioneered work on MKL and proposed a semidefinite programming approach to automatically learn a linear combination of candidate kernels for the cases of SVMS. To improve computation efficiency, the multikernel class further is restricted to only convex combinations of kernels [2, 14, 15]. Most learning kernel algorithms are based on considering linear kernel mixtures Kθ=∑‍θkKk,(θk≥0) with a prescribed kernels K1,…,KM. For notational simplicity, we will frequently use Ψk instead of the standard feature ΨKk. Compared to (1.1), the primal model for learning with multiple kernels is extended to
(1.3)fw~,θ(x)=∑k=1M‍θk〈wk,Ψk(x)〉Kk,∀w~=(w1,…,wM),wherewk∈HKk.In this paper, we mainly focus on thelp-norm MKL, consisting in minimizing the regularized empirical risk with respect to the optimal kernel mixture ∑k=1M‍θkKk, in addition to lp-regularizer on θ to avoid overfitting. This leads to the following optimization problem:
(1.4)inf⁡w~,θ:θ≥01m∑i=1m‍V(∑k=1M‍θk〈wk,Ψk(xi)〉Kk,yi)+λ∑k=1M‍‖wk‖Kk2+μ∑k=1M‍|θk|p.
This scheme was introduced in [2] and the existence of its minimum has been discussed in [4].The optimization problem subsumes state-of-the-art approaches to multiple kernel learning, covering sparse and nonsparse MKL by arbitrarylp-norm regularization (1≤p≤∞) on the mixing coefficients as well as the incorporation of prior knowledge by allowing for nonisotropic regularizer. Kloft et al. [2] developed two efficient interleaved optimization strategies for the lp-norm multiple kernel learning, and this interleaved optimization is much faster than the commonly used wrapper approaches, as demonstrated on real-world problems from computational biology. An analysis of this model, based on Rademacher complexities, was first developed by Cortes et al. [1]. Later improved rates of convergence were derived based on the theory of local Rademacher complexities [15]. However, the estimate on local Rademacher complexities with 1≤p<2 strictly depends on no-correlation assumption of the M different features, which is too strong condition in theory and practice. In this paper, we employ the notion of empirical covering number to present a theoretical analysis of its generalization error. Besides no-correlation condition is not necessary, empirical covering number is one tight upper bound of local Rademacher complexities [16], also independent of the underlying distribution. We will see that some satisfying learning rates are established when the regularization parameter is appropriately chosen. The interaction between the sample error and the approximation error plays an important role in our analysis, and our new methodology mainly depends on the complexity of hypothesis class measured by empirical covering number and the regularity of a target function.It should be pointed out that the Tikhonov Regularization in (1.4) has two regularization parameter (λ, μ), which may be hard to deal with in practice. Fortunately, an alternative approach has been studied by Rakotomamonjy et al. [14] and Kloft et al. [2]. More precisely, this approach employs the regularizer ∥θ∥lp≤1 as an additional constraint into the optimization problem. By substituting wk for θwk, they arrive at the following problem:
(1.5)inf⁡w~,θ:θ≥01m∑i=1m‍V(∑k=1M‍〈wk,Ψk(xi)〉Kk,yi)+λ2∑k=1M‍‖wk‖Kk2θksubjectto‖θ‖lp≤1.


### 1.2. Algorithm and Main Consequence

The following Lemma (see [4]) indicates that the above multikernel class can equivalently be represented as a block-norm regularized linear class in the product Hilbert space ℋ=ℋK1×⋯×ℋKM.Lemma 1.1.
Ifp>0, q=1+(1/p), and {aj,j∈ℕn}⊆ℝ, then
(1.6)min⁡{(∑j∈Nn‍aj2λj)1/2:λl≥0,l∈Nn,∑j∈Nn‍λjp≤1}=(∑j∈Nn‍|aj|2/q)q/2,
and the equality occurs for ∑j∈ℕn‍|aj|>0 at
(1.7)λ~j:=|aj|2/(p+1)(∑j∈Nn|aj|2p/(p+1))1/p.Hence, Lemma1.1 can be applied to define the feature mapping: Ψ:x∈X→(Ψ1(x),...,ΨM(x))∈ℋK~ associated with a kernel K~; the class of functions defined above coincides with
(1.8)Hp,D,M={fw:x⟶〈w,Ψ(x)〉HK~∣w=(w1,…,wM),‖w‖2,q≤D},
when p∈[1,∞], q∈[1,2] holds from q=2p/(p+1). The l2,q-norm is defined here as ∥w∥2,q=(∑j=1M‍∥wj∥Kjq)1/q. For simplicity, we write ∥fw∥2,q=∥w∥2,q. Clearly learning the complexity of (1.8) will be greater than one that is based on a single kernel only, further it provides greater learning ability while the computational complexity increases accordingly. The sample complexity of the above hypothesis space has been studied by Cortes et al. [1] and Kloft and Blanchard [15]. Thus the primal MKL optimization problem (1.5) is equivalent to the following regularization scheme, which is the primary object of investigation in this paper
(1.9)fz=〈wz,Ψ(x)〉HK~,wherewz=arg⁡min⁡w∈HK~1m∑i=1m‍V(〈w,Ψ(xi)〉HK~,yi)+λ‖w‖2,q2.
Here we use the symbol “min” instead of “inf,” since (1.4) is equivalent to (1.9) and the solution of (1.4) exists and is unique. Remark that the above algorithm is a standard regularized empirical risk minimization; this implies that lp-norm multiple kernel learning scheme can be free of over-fitting, a phenomenon which occurs when the empirical error is zero but the expected error in far from zero.In the following, we assume that{Kj}j=1,...,M is uniformly bounded, that is,
(1.10)κ=sup⁡j∈{1,...,M}sup⁡x∈XKj(x,x)<∞.
Also suppose that each Kj is continuous. In other words, each Kj is a Mercer kernel with bound κ; we refer to [17] for more properties and discussions on Mercer kernel.In this paper, we only focus on the least square loss:V(f(x),y)=(f(x)-y)2. Accordingly, the target function is given by
(1.11)fρ(x)=arg⁡min⁡{E(f(x)-y)2}=∫Y‍ydρ(⋅∣x),∀x∈X,
where we denote by ρ(·∣x) the conditional distribution of ρ. Through this paper we assume that ρ(·∣x) is supported on [-T,T], it follows that |fρ(x)|≤T for x∈X almost surely. Since the learner fz may be much larger than fρ, it is natural to apply a projection operator on fz, which was introduced into learning algorithms to improve learning rates.Definition 1.2.
The projection operatorπ is defined on the space of measurable functions f:X→ℝ as
(1.12)π(f)(x)={T,iff(x)>T,f(x),if|f(x)|≤T,-T,iff(x)<-T,
where T>0 is called the projection level.The target of error analysis is to understand howπ(fz) approximates the regression function fρ. More precisely, we aim to estimate the excess generalization error(1.13)E(π(fz))-E(fρ)
for the lp-norm MKL algorithm (1.4), where ℰ(f)=𝔼(f(x)-y)2 denotes the expect error of f.To show some ideas of our error analysis, we first state learning rates of (1.4) in a special case when fρ∈ℋK~ and K~ is C∞ on X⊂ℝn.Theorem 1.3.
Letfz be defined by (1.9). Assume K~ is C∞ on X⊂ℝn and fρ∈ℋK~. For any 0<δ<1 and ϵ>0, with confidence 1-δ, there holds
(1.14)E(π(fz))-E(fρ)=‖π(fz)-fρ‖ρ2≤C~log⁡(2δ)(1m)1-ϵ,withλ=(1m)1-2ϵ,
where C~ is some constant independent of m or δ.Theorem1.3 can be viewed as a corollary of our main result presented in Section 5. It can be arbitrary close to 𝒪(m-1) by choosing ϵ to be small enough, which is the best convergence rate in learning theory literature.


## 1.1. Overview of Multiple Kernel Learning

Kernel methods such as Support Vector Machines (SVMs) have been extensively applied to supervised learning tasks such as classification and regression. The performance of a kernel machine largely depends on the data representation via the choice of kernel function. Hence, one central issue in kernel methods is the problem of kernel selection; a great many approaches to selecting the right kernel have been studied in the literature [1–4] and other references therein.We begin with reviewing the classical supervised learning setup. Let(X,d) be a compact metric space and Y⊆ℝ, given a labeled sample z={(xi,yi)}i=1m⊆Z:=X×Y, sampled i.i.d. according to an unknown distribution ρ supported on Z, the goal is to estimate a real-valued function fz depending on the sample, that generalizes well on new and unseen data. A widely used approach to estimate a function from empirical data consists in minimizing a regularization functional in a Hilbert space ℋ of real-valued functions: X→ℝ. Typically, a regularization scheme estimates f as a minimizer of the functional
(1.1)Ez(f)+λΩ(f),
where ℰz(f)=(1/m)∑i=1m‍V(f(xi),yi) is the empirical risk of hypothesis f, measured by a nonnegative loss function V:ℝ×Y→ℝ+. In addition, Ω:ℋ→ℝ is a regularizer and λ>0 is a trade-off regularization parameter.In this paper, we assume thatℋ is a reproducing kernel Hilbert space (RKHS) ℋK with kernel K, see [5]. Every kernel K corresponds to a feature mapping ΨK:X→ℋK satisfying K(x,y)=〈ΨK(x),ΨK(y)〉K, and each element of ℋK has the following form:
(1.2)fw(x)=〈w,ΨK(x)〉K,∀w∈HK.By restricting the regularization to be the formΩ(f)=∥f∥K2, there is a lot of studies from different perspectives such as statistics, optimal recovery and machine learning [6–9], and other references therein. Regularization in an RKHS has a number of attractive features, including the availability of effective error bounds and stability analysis relative to perturbations of the data (see Cucker and Smale [7]; Wu et al. [10]; Bousquet and Elisseeff [6]). Moreover, the optimization problem (1.1) in an RKHS can be reduced to seek for solution in a finite-dimensional space. Although it is simple to prove, this result shows that the variational problem (1.1) can be computational easily.Because of their simplicity and generality, kernels and associated RKHS play an increasingly important role in Machine Learning, Pattern Recognition and Artificial Intelligence. When the kernel is fixed, an immediate concern is the choice of the regularization parameterλ. This is typically solved by means of cross validation or generalized cross validation [11]. However, the performance of kernel methods critically relies on the choice of the kernel function. A natural question is how to choose the optimal kernel in a collection of candidate kernels.Kernel learning can range from the width parameter selection of Gaussian kernels [9, 12] to obtaining an optimal linear combination from a set of finite candidate kernels. The latter is often referred to as multiple kernel learning in machine learning and nonparametric group Lasso in statistics [13]. Lanckriet et al. [3] pioneered work on MKL and proposed a semidefinite programming approach to automatically learn a linear combination of candidate kernels for the cases of SVMS. To improve computation efficiency, the multikernel class further is restricted to only convex combinations of kernels [2, 14, 15]. Most learning kernel algorithms are based on considering linear kernel mixtures Kθ=∑‍θkKk,(θk≥0) with a prescribed kernels K1,…,KM. For notational simplicity, we will frequently use Ψk instead of the standard feature ΨKk. Compared to (1.1), the primal model for learning with multiple kernels is extended to
(1.3)fw~,θ(x)=∑k=1M‍θk〈wk,Ψk(x)〉Kk,∀w~=(w1,…,wM),wherewk∈HKk.In this paper, we mainly focus on thelp-norm MKL, consisting in minimizing the regularized empirical risk with respect to the optimal kernel mixture ∑k=1M‍θkKk, in addition to lp-regularizer on θ to avoid overfitting. This leads to the following optimization problem:
(1.4)inf⁡w~,θ:θ≥01m∑i=1m‍V(∑k=1M‍θk〈wk,Ψk(xi)〉Kk,yi)+λ∑k=1M‍‖wk‖Kk2+μ∑k=1M‍|θk|p.
This scheme was introduced in [2] and the existence of its minimum has been discussed in [4].The optimization problem subsumes state-of-the-art approaches to multiple kernel learning, covering sparse and nonsparse MKL by arbitrarylp-norm regularization (1≤p≤∞) on the mixing coefficients as well as the incorporation of prior knowledge by allowing for nonisotropic regularizer. Kloft et al. [2] developed two efficient interleaved optimization strategies for the lp-norm multiple kernel learning, and this interleaved optimization is much faster than the commonly used wrapper approaches, as demonstrated on real-world problems from computational biology. An analysis of this model, based on Rademacher complexities, was first developed by Cortes et al. [1]. Later improved rates of convergence were derived based on the theory of local Rademacher complexities [15]. However, the estimate on local Rademacher complexities with 1≤p<2 strictly depends on no-correlation assumption of the M different features, which is too strong condition in theory and practice. In this paper, we employ the notion of empirical covering number to present a theoretical analysis of its generalization error. Besides no-correlation condition is not necessary, empirical covering number is one tight upper bound of local Rademacher complexities [16], also independent of the underlying distribution. We will see that some satisfying learning rates are established when the regularization parameter is appropriately chosen. The interaction between the sample error and the approximation error plays an important role in our analysis, and our new methodology mainly depends on the complexity of hypothesis class measured by empirical covering number and the regularity of a target function.It should be pointed out that the Tikhonov Regularization in (1.4) has two regularization parameter (λ, μ), which may be hard to deal with in practice. Fortunately, an alternative approach has been studied by Rakotomamonjy et al. [14] and Kloft et al. [2]. More precisely, this approach employs the regularizer ∥θ∥lp≤1 as an additional constraint into the optimization problem. By substituting wk for θwk, they arrive at the following problem:
(1.5)inf⁡w~,θ:θ≥01m∑i=1m‍V(∑k=1M‍〈wk,Ψk(xi)〉Kk,yi)+λ2∑k=1M‍‖wk‖Kk2θksubjectto‖θ‖lp≤1.


## 1.2. Algorithm and Main Consequence

The following Lemma (see [4]) indicates that the above multikernel class can equivalently be represented as a block-norm regularized linear class in the product Hilbert space ℋ=ℋK1×⋯×ℋKM.Lemma 1.1.
Ifp>0, q=1+(1/p), and {aj,j∈ℕn}⊆ℝ, then
(1.6)min⁡{(∑j∈Nn‍aj2λj)1/2:λl≥0,l∈Nn,∑j∈Nn‍λjp≤1}=(∑j∈Nn‍|aj|2/q)q/2,
and the equality occurs for ∑j∈ℕn‍|aj|>0 at
(1.7)λ~j:=|aj|2/(p+1)(∑j∈Nn|aj|2p/(p+1))1/p.Hence, Lemma1.1 can be applied to define the feature mapping: Ψ:x∈X→(Ψ1(x),...,ΨM(x))∈ℋK~ associated with a kernel K~; the class of functions defined above coincides with
(1.8)Hp,D,M={fw:x⟶〈w,Ψ(x)〉HK~∣w=(w1,…,wM),‖w‖2,q≤D},
when p∈[1,∞], q∈[1,2] holds from q=2p/(p+1). The l2,q-norm is defined here as ∥w∥2,q=(∑j=1M‍∥wj∥Kjq)1/q. For simplicity, we write ∥fw∥2,q=∥w∥2,q. Clearly learning the complexity of (1.8) will be greater than one that is based on a single kernel only, further it provides greater learning ability while the computational complexity increases accordingly. The sample complexity of the above hypothesis space has been studied by Cortes et al. [1] and Kloft and Blanchard [15]. Thus the primal MKL optimization problem (1.5) is equivalent to the following regularization scheme, which is the primary object of investigation in this paper
(1.9)fz=〈wz,Ψ(x)〉HK~,wherewz=arg⁡min⁡w∈HK~1m∑i=1m‍V(〈w,Ψ(xi)〉HK~,yi)+λ‖w‖2,q2.
Here we use the symbol “min” instead of “inf,” since (1.4) is equivalent to (1.9) and the solution of (1.4) exists and is unique. Remark that the above algorithm is a standard regularized empirical risk minimization; this implies that lp-norm multiple kernel learning scheme can be free of over-fitting, a phenomenon which occurs when the empirical error is zero but the expected error in far from zero.In the following, we assume that{Kj}j=1,...,M is uniformly bounded, that is,
(1.10)κ=sup⁡j∈{1,...,M}sup⁡x∈XKj(x,x)<∞.
Also suppose that each Kj is continuous. In other words, each Kj is a Mercer kernel with bound κ; we refer to [17] for more properties and discussions on Mercer kernel.In this paper, we only focus on the least square loss:V(f(x),y)=(f(x)-y)2. Accordingly, the target function is given by
(1.11)fρ(x)=arg⁡min⁡{E(f(x)-y)2}=∫Y‍ydρ(⋅∣x),∀x∈X,
where we denote by ρ(·∣x) the conditional distribution of ρ. Through this paper we assume that ρ(·∣x) is supported on [-T,T], it follows that |fρ(x)|≤T for x∈X almost surely. Since the learner fz may be much larger than fρ, it is natural to apply a projection operator on fz, which was introduced into learning algorithms to improve learning rates.Definition 1.2.
The projection operatorπ is defined on the space of measurable functions f:X→ℝ as
(1.12)π(f)(x)={T,iff(x)>T,f(x),if|f(x)|≤T,-T,iff(x)<-T,
where T>0 is called the projection level.The target of error analysis is to understand howπ(fz) approximates the regression function fρ. More precisely, we aim to estimate the excess generalization error(1.13)E(π(fz))-E(fρ)
for the lp-norm MKL algorithm (1.4), where ℰ(f)=𝔼(f(x)-y)2 denotes the expect error of f.To show some ideas of our error analysis, we first state learning rates of (1.4) in a special case when fρ∈ℋK~ and K~ is C∞ on X⊂ℝn.Theorem 1.3.
Letfz be defined by (1.9). Assume K~ is C∞ on X⊂ℝn and fρ∈ℋK~. For any 0<δ<1 and ϵ>0, with confidence 1-δ, there holds
(1.14)E(π(fz))-E(fρ)=‖π(fz)-fρ‖ρ2≤C~log⁡(2δ)(1m)1-ϵ,withλ=(1m)1-2ϵ,
where C~ is some constant independent of m or δ.Theorem1.3 can be viewed as a corollary of our main result presented in Section 5. It can be arbitrary close to 𝒪(m-1) by choosing ϵ to be small enough, which is the best convergence rate in learning theory literature.


## 2. Key Error Analysis

Our main result is about learning rates of (1.4) stated under conditions on the approximation ability of ℋK~ with respect to fρ and capacity of ℋK~.The approximation ability of the hypothesis spaceℋK~ with respect to fρ in the space LρX2 is reflected by regularization error.Definition 2.1.
The regularization error of the triple(ℋK~,fρ,ρX) is defined as
(2.1)Aq(λ)=min⁡f∈HK~{E(f)-E(fρ)+λ‖f‖2,q2},λ>0.
We will assume that for some 0<β≤1 and Cβ>0,
(2.2)Aq(λ)≤Cβλβ.Remark 2.2.
Our assumption implies that whenfρ is replaced by ℋK~, 𝒜q(λ) tends to zero by polynomial order decay as λ goes to zero. Note [7] that 𝒜q(λ)=o(λ) would imply fρ=0. So β=1 in (2.2) is the best we can expect. This case is equivalent to fρ∈ℋK~ when ℋK~ is dense in LρX2, see [18]. Assumption (2.2) with 0<β<1 can be characterized in terms of interpolation spaces [7].IfρX is the Lebesgue measure on X and the target function fρ∈Hs, a Sobolev space with power s. When Gaussian kernel (Gσ(x,y)=exp(-σ∥x-y∥2)) is taken with a fixed variance σ, a polynomial decay of 𝒜q(λ) is impossible. However, Example 1 of [19] successfully obtains a polynomial decay under the multikernel setting, allowing for varying variances of Gaussian kernels. This shows that multikernel learning can improve the approximation power and learning ability. More interestingly, we will take a special example to show the impact of the multikernel class on the regularization error in Section 5 below. In particular, a proper multikernel class can be applied to improve the regularization error if the regularity of fρ is rather high.Next we define the truncated sample error as(2.3)Sz(λ,f,T)={E(π(fz))-Ez(π(fz))}+{Ez(f)-E(f)},
and the sample error as
(2.4)Sz(λ,f)={E(fz)-Ez(fz)}+{Ez(f)-E(f)}.The functionf in the above equation can be arbitrarily chosen; however, only proper choices lead to good estimates of the regularization error. A good choice is f=fλ where
(2.5)fλ=arg⁡min⁡f∈HK~{E(f)+λ‖f‖2,q2}.A useful approach for regularization schemes with sample independent hypothesis spaces such as RKHS is an error decomposition, which decomposes the total errorℰ(π(fz))-ℰ(fρ) into the sum of the truncated sample error and the regularization error stated as follows.Proposition 2.3.
Letfλ be defined by (2.5); there holds
(2.6)E(π(fz))-E(fρ)≤Sz(λ,fλ,T)+Aq(λ).Proof.
We can decomposeℰ(π(fz))-ℰ(fρ) into
(2.7){E(π(fz))-Ez(π(fz))}+{Ez(π(fz))+λ‖fz‖2,q2-(Ez(fλ)+λ‖fλ‖2,q2)}+{Ez(fλ)-E(fλ)}+{E(fλ)-E(fρ)+λ‖fλ‖2,q2}-λ‖fz‖2,q2.
To bound the second term, by Definition of fz, ℰz(π(fz))+λ∥fz∥2,q2 can be bounded by
(2.8)Ez(fz)+λ‖fz‖2,q2≤Ez(fλ)+λ‖fλ‖2,q2,
since |π(f)(x)-y|≤|f(x)-y| holds for any function f on Z. The conclusion follows by combining these two inequalities.


## 3. Estimation on Sample Error

We are in a position to estimate the sample error𝒮z(λ,fλ,T). The sample error 𝒮z(λ,fλ,T) can be written as
(3.1){(E(π(fz))-E(fρ))-(Ez(π(fz))-Ez(fρ))}+{(Ez(fλ)-Ez(fρ))-(E(fλ)-E(fρ))}:=S1+S2.𝒮
2 can be easily bounded by applying the following one-side Bernstein-type probability inequality.Lemma 3.1.
Letξ be a random variable on a probability space Z with variance σ2 satisfying |ξ-𝔼(ξ)|≤Mξ for some constant Mξ. Then for any 0<δ<1, we have
(3.2)1m∑i=1m‍ξ(zi)-E(ξ)≤2Mξlog⁡(1/δ)3m+2σ2log⁡⁡(1/δ)m.Proposition 3.2.
Define the random variableξ2(z)=(fλ(x)-y)2-(fρ(x)-y)2. For every 0<δ<1, with confidence at least 1-δ/2, there holds
(3.3)S2=1m∑i=1m‍ξ2(zi)-E(ξ2)≤Aq(λ)(1+3κ2M2/q*log⁡(2/δ)mλ)+6T2+log⁡(2/δ)m.Proof.
From the definition of𝒜q(λ), we see that
(3.4)λ‖fλ‖2,q2≤E(fλ)-E(fρ)+λ‖fλ‖2,q2=Aq(λ).
Note that fλ(x)=〈wλ,Ψ(x)〉 for some wλ=(wλ(1),…,wλ(M))∈ℋK~, by the Cauchy-Schwarz inequality (C.-S.), we have for any x∈X:
(3.5)〈wλ,Ψ(x)〉=∑j=1M‍〈wλ(j),Ψj(x)〉≤C.-S.∑j=1M‍‖wλ(j)‖Kj‖Ψj(x)‖Kj≤Ho¨lder‖wλ‖2,q(∑j=1M‍‖Ψj(x)‖Kjq*)1/q*,
where (1/q)+(1/q*)=1. Using Assumption (1.10), it follows that
(3.6)‖fλ‖∞≤κM1/q*‖wλ‖2,q≤κM1/q*Aq(λ)λ.
Observe that(3.7)ξ2(z)=(fλ(x)-fρ(x))(fλ(x)+fρ(x)-2y).
Since that |fρ(x)|≤T almost surely, we have
(3.8)|ξ2|≤(‖fλ‖∞+T)(‖fλ‖∞+3T)≤c:=(κM1/q*Aq(λ)λ+3T)2.
Hence |ξ2-𝔼(ξ2)|≤Mξ2:=2c. Moreover, 𝔼(ξ2)2 equals
(3.9)E((fλ(x)-fρ(x))2(fλ(x)+fρ(x)-2y)2)≤(‖fλ‖∞+3T)2‖fλ-fρ‖ρ2,
which implies that σ2(ξ2)≤𝔼(ξ22)≤c𝒜q(λ). The desired result follows from Lemma 3.1.Next we estimate the first term𝒮1. It is more difficult to deal with because it involves a set of random variables fz varying with z, requiring to consider the functional complexity. For this purpose, we introduce the notion of empirical covering numbers, which often lead to sharp error estimates [16].Definition 3.3.
Let(𝒰,d) be a pseudometric space and S⊂𝒰. For every ϵ>0, the covering number 𝒩(S,ϵ,d) of S with respect to ϵ and d is defined as the minimal number of balls of radius ϵ whose union covers S, that is,
(3.10)N(S,ϵ,d)=min⁡{l∈N:S⊂⋃j=1l‍B(sj,ϵ)forsome{sj}j=1l⊂U},
where B(sj,ϵ)={s∈𝒰:d(s,sj)≤ϵ} is a ball in 𝒰.Thel2-empirical covering number of a function set is defined by means of the normalized l2-metric d2 on the Euclidian space ℝk given by
(3.11)d2(a,b)=(1k∑i=1k‍|ai-bi|2)1/2fora=(ai)i=1k,b=(bi)i=1k∈Rk.Definition 3.4.
Letℱ be a set of function on X, x=(xi)i=1k⊂Xk and ℱ|x={(f(xi))i=1k:f∈ℱ}⊂ℝk. Set 𝒩2,x(ℱ,ϵ)=𝒩(ℱ|x,ϵ,d2). The l2-empirical covering number of ℱ is defined by
(3.12)N2(F,ϵ)=sup⁡k∈Nsup⁡x∈XkN2,x(F,ϵ),ϵ>0.Denote byBR the ball of radius R with R>0, BR={f∈ℋK~:∥f∥K~≤R}. We need the following capacity assumption on ℋK~.Assumption 3.5.
There exists an exponentυ, with 0<υ<2 and a constant Cυ,K~>0 such that
(3.13)log⁡N2(B1,ϵ)≤Cυ,K~ϵ-υ,∀ϵ>0,
where B1 is the unit ball of ℋK~ defined as above.For any functionfw=〈w,Ψ(x)〉ℋK~, by the hölder inequality, we have
(3.14)‖fw‖K~=(∑j=1M‍‖wj‖Kj2)1/2≤M1/q*‖fw‖2,q,
and it follows from (3.13)
(3.15)log⁡⁡N2(B1q,ϵ)≤Cυ,KMυ/q*ϵ-υ,
where B1q is called the generalized unit ball of ℋK~ associated with q, defined by
(3.16)B1q={f∈HK~,‖f‖2,q≤1}.Note that for any function setℱ⊆C(X), the empirical covering number 𝒩2,x(ℱ,ϵ) is bounded by 𝒩(ℱ,ϵ), the (uniform) covering number of ℱ under the metric ∥·∥∞, since d2(f,g)≤∥f-g∥∞. It was shown in [20] that the quantity log(𝒩(B1,ϵ))≤C0(1/ϵ)s holds for some C0>0 if K is C2n/s on a subset of ℝn, hence log(𝒩2(B1,ϵ))≤C0(1/ϵ)s also holds. In particular, s is arbitrarily small for a C∞ kernel ( such as Gaussian kernel). Now we give a concrete example in ℝn to reveal relationship between the regularity of function class and its corresponding empirical covering number.Example 3.6.
LetX be a bounded domain in ℝn and Hs the Sobolev space of index s. When s>n, the classical Embedding Theorem tells us that Hs(X) is an RKHS and its unit ball B1 is embedded in a finite ball of the function space Cs-(n/2)-ζ(X) with inclusion bounded where 0<ζ<s-n. From the classical bounds for covering numbers of the unit ball of Cs-(n/2)-ζ(X), we see that
(3.17)log⁡(N2(B1,ϵ))≤Csϵ-n/(s-n/2-ζ),∀ϵ>0.
Hence Assumption (3.13) below holds with υ=n/(s-n/2-ζ)<2.Our concentration estimate for the sample error dealing with𝒮1 is based on the following concentration inequality, which can be found in [12].Lemma 3.7.
Letℱ be a class of measurable functions on Z. Assume that there are constants B,c>0 and η∈[0,1] such that ∥f∥∞≤B and 𝔼f2≤c(𝔼f)η for every f∈ℱ. If for some a>0 and υ∈(0,2),
(3.18)log⁡N2(F,ϵ)≤aϵ-υ,∀ϵ>0,
then there exists a constant cυ such that for any t>0, with confidence at least 1-e-t, there holds
(3.19)Ef-1m∑i=1m‍f(zi)≤12γ1-η(Ef)η+cυγ+2(ctm)1/(2-η)+18Btm,∀f∈F,
where
(3.20)γ:=max⁡{c(2-υ)/(4-2η+υη)(am)2/(4-2η+υη),B(2-υ)/(2+υ)(am)2/(2+υ)}.Denote the set of functionℱRq with R>0, where
(3.21)FRq={(π(f)(x)-y)2-(fρ(x)-y)2:f∈BRq}.Proposition 3.8.
IfB1q satisfies the capacity condition (3.13) with some 0<υ<2, then for any δ∈(0,1), with confidence 1-δ/2, there holds
(3.22)S1≤12‖π(fz)-fρ‖ρ2+80T2log⁡(2/δ)m+Cυ,T(1λ)υ/(2+υ)(1m)2/(2+υ)
with constant Cυ,T=4cυ(Cυ,K~T2)υ/(2+υ)M2υ/(2+υ)q*.Proof.
Consider the setℱRq. Each function g∈ℱRq can be expressed as g(z) = (y-π(f)(x))2-(y-fρ(x))2 with some f∈BRq. Then 𝔼g=ℰ(π(f))-ℰ(fρ)=∥π(f)-fρ∥ρ2 and (1/m)∑i=1m‍g(zi) = ℰz(π(f))-ℰz(fρ). Note that
(3.23)g(z)=(π(f)(x)-fρ(x))(π(f)(x)+fρ(x)-2y).
Since |π(f)(x)|≤T and |fρ(x)|≤T for any x∈X, we see that for any z∈Z,
(3.24)|g(z)|≤8T2,Eg2=∫Z‍(π(f)(x)-fρ(x))2(π(f)(x)+fρ(x)-2y)2≤4T2Eg.
On the other hand, for any g1,g2∈ℱRq at point z=(x,y), we have
(3.25)|g1(z)-g2(z)|≤4T|f1(x)-f2(x)|,
since the projector operator π is a contractive map. It follows that
(3.26)N2,z(FRq,ϵ)≤N2,x(BRq,ϵ4T)≤N2,x(B1q,ϵ4TR).
It follows from the capacity condition (3.15)
(3.27)log⁡N2(FRq,ϵ)≤Cυ,K~(4TRM1/q*)υϵ-υ.
Applying Lemma3.7 with B=c=4T2, η=1, and a=Cυ,K~(4TRM1/q*)υ, we see that for any δ∈(0,1), with confidence 1-δ/2, there holds
(3.28)Eg-1m∑i=1m‍g(zi)≤12Eg+80T2log⁡(2/δ)m+Cυ,TR2υ/(2+υ)(1m)2/(2+υ),∀f∈FRq.
Besides, following the definition of fz (1.9), we have
(3.29)λ‖fz‖2,q2=λ‖wz‖2,q2≤w=01m∑i=1m‍yi2≤T2,
that is, ∥fz∥2,q≤T/λ. Hence we can replace R with T/λ. Thus we derive our desired result.


## 4. Total Learning Rates

We are now in a position to obtain the learning rates of projected algorithm (1.9). Main results of this paper will be presented in Theorem 4.1.Following the error decomposition scheme in Proposition2.3 and combining Propositions 3.2 and 3.8, we derive the following bounds on the total error.Theorem 4.1.
Suppose thatB1q satisfies the capacity condition (3.13) with some 0<υ<2, and 𝒜q(λ)≤Cβλβ. For any δ∈(0,1), with confidence 1-δ, there holds
(4.1)‖π(fz)-fρ‖ρ2≤C′log⁡(2δ)(1m)min⁡⁡{2β/(2β+(1+β)υ),β},by takingλ=(1m)min⁡{2/(2β+(1+β)υ),1},
where C′=3κ2M2/q*+86T2+1+Cυ,T2υ/(2+υ)+Cβ and Cυ,T is defined as in Proposition 3.8.Proof.
Following Propositions3.2 and 3.8, with confidence at least 1-δ, (1/2)∥π(fz)-fρ∥ρ2 can be bounded by
(4.2)3κ2M2/q*Aq(λ)mλlog⁡(2δ)+(86T2+1)log⁡(2/δ)m+Cυ,T(2λ)υ/(2+υ)(1m)υ/(2+υ)+2Aq(λ).
Firstly, we set
(4.3)Aq(λ)mλ=Aq(λ),
which implies that λ=(1/m). On the other hand, from the assumption 𝒜q(λ)≤Cβλβ, we set
(4.4)(2λ)υ/(2+υ)(1m)2/(2+υ)=λβ,thatis,λ=m-(2/(2β+(1+β)υ)).
Hence our assertion follows by taking λ=(1/m)min{2/(2β+(1+β)υ),1}.Proof of Theorem1.3.
WhenK~∈C∞, it follows that condition (3.13) holds for arbitrary small υ>0. Moreover, fρ∈ℋK~ implies that β=1, the conclusion follows easily from Theorem 4.1.
Our learning rates below in Corollary4.2 will be achieved under the regularity assumption on the regression function that fρ lies in the range of LK~r for some r>0. Given any kernel K, LK is the integral operator on LρX2 defined by
(4.5)LK(f)(x)=∫X‍K(x,y)f(y)dρX(y),x∈X,f∈LρX2.
The operator LK is linear, compact, positive and can be also regarded as a self-adjoint operator on ℋK. Hence the fractional power operator LKr:LρX2→LρX2 is well defined and is given by
(4.6)LKr(f)=∑k‍λkr〈f,φk〉LρX2φk,f∈LρX2(X),
where {λk}k are eigenvalues of the operator LK arranged in a decreasing order and {φk}k are the corresponding eigenfunctions, which form an orthonormal basis of LρX2. In fact, the image of LKr is contained in ℋK if r≥1/2. So LK-rfρ∈LρX2 indicates that fρ lies in the range of LKr, measuring the regularity of the regression function.Corollary 4.2.
Suppose thatB1q satisfies the capacity condition (3.13) with some 0<υ<2, and LK~-rfρ∈LρX2 (0<r≤1). For any 0<δ<1, with confidence 1-δ, there holds
(4.7)‖π(fz)-fρ‖ρ2≤C~log⁡(2δ)(1m)min⁡⁡{2β/(2β+(1+β)υ),β},withβ=min⁡{2r,1},
where C~ is some constant independent of m or δ.Proof.
Recall a result from [18], if LK~-rfρ∈LρX2 (0<r≤1/2), there holds
(4.8)A2(λ)=‖fλ-fρ‖ρ2+λ‖fλ‖K~2≤λ2r‖LK~-rfρ‖LρX2.
If r≥1/2, this shows that fρ∈ℋK~ as mentioned above, then we have fλ=fρ and
(4.9)A2(λ)≤λ‖fρ‖K~2.
Hence for any r∈[0,1], we have
(4.10)A2(λ)≤λβ,withβ=min⁡{2r,1}.
On the other hand, observe Lemma5.1 below, and we have
(4.11)Aq(λ)≤C*λβ,withβ=min⁡{2r,1},
where C* is some constant and q∈[1,2]. The conclusion follows immediately from Theorem 4.1.Let us compare our learning rates with the existing results.In [10], a uniform covering number technique was used to derive the expected value of learning schemes (1.1) where Ω(fw)=∥w∥K2. If all the kernels {Ki} are the same with some specialized K and LK-rfρ∈LρX2 for some 0<r≤1/2. For any 0<ζ<1/(1+υ) and any 0<δ<1, with confidence 1-δ, then
(4.12)‖fz-fρ‖ρ2≤log⁡(2δ)O(m-2rζ).
Clearly the learning rates derived from Corollary 4.2 are better than that in [10] since 2rζ<2r/(1+υ)≤4r/(4r+(1+2r)υ).In [21], an operator monotonic technique was used to improve the kernel independent error bounds in comparison with the result in [17]. If LK-rfρ∈LρX2 for some 0<r≤1. For any 0<δ<1, with confidence 1-δ, there holds
(4.13)‖fz-fρ‖ρ2≤log⁡(2δ)O(m-3r/(2r+2)).Whenr≥1/2 and υ≤(2-r)/3r, the learning rate given by Corollary 4.2 is better than the above result.As for empirical risk minimization (ERM), classical results on analysis of ERM schemes give error bounds between the empirical target function and the regression function. In particular, learning rates of typem-ε with ε arbitrarily close to 1 can be achieved by ERM schemes (see [15]). However, the ERM setting is different from the one on Tikhonov regularization. How to choose the regularization parameter λ=λ(m), depending on the sample size m, is the essential difficulty for the regularization scheme, even when fρ lies in ℋK. On the other hand, it is obvious that our result is more general than that of [15] since the case for fρ∉ℋK (r<1/2) is also covered.


## 5. Discussion on Regularization Error

By our assumptions on M different kernels{Kj}j=1M, we see that ℋK~ is an RKHS generated by the Mercer kernel K~. There are several standard approximation results on regularization error 𝒜2(λ) in learning theory (see [17]). Next we establish a tight connection between 𝒜2(λ) and 𝒜q(λ) with 1≤q≤2.Lemma 5.1.
LetℋK~ be a separable RKHS over X associated with a bounded measurable kernel, ρ be a distribution on X×[-T,T], and 1≤q≤2. If there exist constants C>0 and β>0 such that 𝒜2(λ)≤Cλβ, then for all λ>0 we have
(5.1)Aq(λ)≤C(M(2-q)/2+1)λβ.Proof.
If there exists a functionf~λ satisfying
(5.2)λ‖f~λ‖2,22+‖f~λ-fρ‖ρ2≤Cλβ,
we see that λ∥f~λ∥2,22≤Cλβ. We write f~λ(x)=〈w~,Ψ(x)〉 with some w~=(w~(1),...,w~(M)), by the Ho¨lder inequality, we have
(5.3)‖f~λ‖2,qq=∑j=1M‍‖w~(j)‖Kjq≤Ho¨lderM(2-q)/2‖f~λ‖2,2q.
Then we obtain
(5.4)Aq(λ)≤λ‖f~λ‖2,q2+‖f~λ-fρ‖ρ2≤CM(2-q)/2λβ+Cλβ=C(M(2-q)/2+1)λβ.In other words, if𝒜2(λ) has a polynomial behavior in λ, then this behavior completely determines the behavior of all 𝒜q(λ). Thus it suffices to assume that the standard 2-approximation error function satisfies (2.2).From statistical effective dimension point of view, we will discuss the impact of the multikernel classℋK~ on the approximation error ∥fλ-fρ∥LρX2. To estimate this error, note that the regularizing function of 𝒜2(λ) exists, is unique, and given by [7]
(5.5)fλ=(λI+LK~)-1LK~fρ.
For simplicity, let M=2 and take a Mercer kernel Ko as the original one, by the classical Mercer theorem, Ko can be expressed as Ko(x,y)=∑k=1∞‍λkφk(x)φk(y). Another kernel we take is KoN=∑k=1∞‍λkNφk(x)φk(y) (2≤N∈ℕ+). In this case, K~=Ko+KoN=∑k=1∞‍(λk+λkN)φk(x)φk(y). By the fact that fλ-fρ=λ(λI+LK~)-1fρ and assumption LKo-rfρ∈LρX2, we have
(5.6)‖fλ-fρ‖LρX2=λ‖(λI+LK~)-1LKorLKo-rfρ‖LρX2=λ‖∑k=1∞‍αkλkrλk+λkN+λφk‖LρX2≤λmin⁡{r/N,1}‖LKo-rfρ‖LρX2for‖α‖l2=‖LKo-rfρ‖LρX2.Let us compare the multikernel class regularization with Tikhonov regularization inℋKo when the Mercer kernel Ko is employed. Denote the saturation index as the maximal r so that the approximation error achieves fastest decay rate under the condition LKo-rfρ∈LρX2. Then (5.6) shows the saturation index for multikernel class regularization is N while it is 1 for Tikhonov regularization in ℋKo, as shown in [17].In this case, our analysis implies that we should use an alternative kernel with faster eigenvalue decay when the spectral coefficients of the target function decay faster: for example, usingKoN instead of Ko. This has a dimension reduction effect. Essentially, we effectively project the data into the principal components of data. The intuition is also quite clear: if the dimension of the target function is small (spectral coefficient r decays fast), then we should project data to those dimensions by reducing the remaining noisy dimensions (corresponding to fast kernel eigenvalue decay N). In fact, the similar idea under the framework of semisupervised learning has been shown in spectral kernel design methods [22, 23].In general, for the sample error, there exist rates of convergence which hold independently of the underlying distributionρ. This is important, as it tells us that we can give convergence guarantees no matter what a kernel is used, even we do not know the underlying distribution. In fact, this is very common in statistical analysis of various machine learning algorithms (see [24]). This decay is usually fast enough for practical use where amounts of samples are available. For the approximation error, however, it is impossible to give rates of convergence which hold for all probability distributions ρ. Hence what determines the learning accuracy is the approximation error. In kernel regression setup, this is determined by the choice of the kernel and enhances the importance of learning kernels [4] and constructing refined kernels [25].


## 6. Further Study

In the last section, we exclusively discuss sparsity in the case of the square loss regularization functional in (1.1) with the regularizer Ω(f)=∥f∥K2 in RKHS. We can derive the explicit expression for this functional from [4], in turn which provides improvement and simplification of our algorithm (1.4).Lemma 6.1.
For any kernelK and positive constant λ, we have that
(6.1)Sλ(K):=min⁡{1m∑i=1m‍(f(xi)-yi)2+λ‖f‖K2}=λ〈y,(λI+K(x))-1y〉,
where the vector y=(yi,…,ym)T and K(x) denotes the m×m Gram matrix (K(xi,xj):i,j=1,…,m) and 〈·〉 denotes the standard inner product in Euclidean space.According to Lemma6.1, the least square algorithm of (1.4) can be rewritten as a one-layer minimization problem
(6.2)θz:=arg⁡min⁡θ≥0{〈y,(λI+Kθ(x))-1y〉+μλ∑k=1M‍|θk|p}.We assume thatfρ∈ℋθ0 for some θ0∈ℝM. Define Jθ:=supp(θ)={k:θk≠0}. We say that fρ is sparse relative to θ0 if the cardinally of Jθ0 is far smaller than M.Forp∈[1,pM] (but pM is close to 1), it would be interesting to show that the solution θz of (6.2) is approximately sparse following the path of θ0. In some sense, ∑k∉Jθ0‍(θz)k is very small with a very high probability. A refined analysis of lp-regularized methods was done by Koltchinskii [26] in the case of combination of M basis functions, mainly taking into account the soft sparsity pattern of the Bayes function and establishing several oracle inequalities in statistical sense. Extending the ideas into the kernels learning setting would be of a great significance, because it can provide theoretical support showing that the lp-norm MKL can automatically select good kernels, which coincide with the underlying right kernels.



---

*Source: 915920-2012-08-05.xml*