# Least Square Regularized Regression for Multitask Learning

Authors: Yong-Li Xu; Di-Rong Chen; Han-Xiong Li
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

The study of multitask learning algorithms is one of very important issues. This paper proposes a least-square regularized regression algorithm for multi-task learning with
hypothesis space being the union of a sequence of Hilbert spaces. The algorithm consists of two steps of selecting the optimal Hilbert space and searching for the optimal function. We assume that the distributions of different tasks are related to a set of transformations under which any Hilbert space in the hypothesis space is norm invariant. We prove that under the above assumption the optimal prediction function of every task is in the same Hilbert space. Based on this result, a pivotal error decomposition is founded, which can use samples of related tasks to bound excess error of the target task. We obtain an upper bound for the sample error of related tasks, and based on this bound, potential faster learning rates are obtained compared to single-task learning algorithms.


---

## Body

## 1. Introduction

Multitask learning [1] is a learning paradigm which seeks to improve the generalization performance of a learning task with the help of some other related tasks. This learning paradigm is inspired by human learning activities in that people often apply the knowledge gained from previous learning tasks to help learn a new task [2]. Different multitask learning algorithms have been designed, such as multitask support vector machine (SVM) [3], multitask feature learning [4, 5], multitask clustering approach [6], multitask structure learning [7], and multitask gradients learning [8].Multitask learning can be formulated under two different settings: symmetric and asymmetric [9]. The symmetric multitask learning tries to improve the performance of all tasks simultaneously, and the objective of asymmetric multitask learning tries to improve the performance of some target task using information from related tasks. The asymmetric multitask learning is related to transfer learning [10]. The major difference is that the source tasks are still learned simultaneously in asymmetric multitask learning while they are learned independently in transfer learning [2]. Much experimental work has achieved the target that is improving the prediction performance of a learning task with the help of other related tasks [1, 11–15]. However, there has been relatively little progress on theoretical analysis for these results.Baxter presented a general frame for model selection in multitask learning environment [16]. They showed that a hypothesis space that performs well on a sufficiently large number of training tasks will also perform well when learning novel tasks in the same environment. They proved that learning multiple tasks within an environment of related tasks can potentially give much better generalization than learning a single task. Ando and Zhang considered learning predictive structures on hypothesis spaces from multitask learning [17]. They presented a general framework in which the structural learning problem can be formulated and analyzed theoretically and related it to learning with unlabeled data. Ben-David and Borbely defined relatedness of tasks on the basis of similarity between the example generating distributions for classification [18], and then they gave precise conditions under which bounds guarantee generalization on the basis of smaller sample sizes than the standard single-task approach. Solnon et al. studied multitask regression, using penalization techniques [19]. They showed that the key element appearing for an optimal calibration is the covariance matrix of the noise between the different tasks. They presented a new algorithm to estimate this covariance matrix and proved that this estimator converges towards the covariance matrix.In this paper, we propose a least-square regularized regression algorithm for multitask learning with hypothesis space being the union of a sequence of Hilbert spaces. The relatedness of tasks is described by distributions that underlie these tasks and some property of the hypothesis space. We assume that the distributions are related by a set of transformations under which the norm of any Hilbert space in the hypothesis space is invariant. We design a multitask learning algorithm with two steps: firstly, samples of other related tasks are used to select an approximate optimal Hilbert space in the hypothesis space; secondly, in the optimal Hilbert space, we use standard least square regularized regression algorithm for the target task. It is proved that, under the above assumption, the optimal prediction function of every task is in the same Hilbert space. For error analysis, we decompose the excess error of prediction function in target task into regularization error and sample error in which the difference between error and empirical error of the prediction function in the target task is estimated by the average value of those in related tasks. This leads to a potential faster learning rate than that of standard regularized regression algorithm in single task.The rest of the paper is organized as follows. In Section2, we introduce some notions and definitions and then propose the least square regularized regression for multitask learning. In Section 3, we decompose excess error of target task into regularization error and sample error in which samples of other related tasks can be used to estimated difference between error and empirical error of the prediction function in target task. The main result is presented in Section 4. An upper bound for sample error of multiple tasks is given by Hoeffding’s inequality and an estimation for covering number in multitask learning, and then, based on the upper bound, potential faster learning rates compared to single-task learning algorithms are obtained.


## 2. Preliminaries

To propose regularized regression algorithm for multitask learning, we introduce some definitions and notations. Let(X,d) be a compact metric space and let Y=[-M,M]. Let ρ be a probability distribution on Z:=X×Y. The regression function is defined as
(1)fρ(x)=∫Y‍ydρ(y∣x),x∈X,
where ρ(y∣x) is the conditional probability measure at x induced by ρ. Knowing a set of samples from the probability distribution ρ, our goal is to find a good approximation of fρ.For multitask learning, we define the relatedness of probability distribution of multiple tasks.Definition 1.
For a functionf:X→X, let f[P] be the probability distribution over X×Y defined by f[ρ](T)=ρ({(f(x),b)∣(x,b)∈T}), for T⊆X×Y. Let ℱ be a set of transformations f:X→X and let ρ1andρ2 be probability distributions over X×Y. We say that ρ1 and ρ2 are ℱ-related if there exists some f∈ℱ such that ρ1=f[ρ2] or ρ2=f[ρ1].Then, we describe the relatedness of the transformation setℱ above and a hypothesis space.Definition 2.
Letℱ be a set of transformations f:X→X and let ℋ be a set of functions X→Y. We say that ℱ acts as a group over ℋ, if,(1)
for everyf∈ℱ and every h∈ℋ, there holds h∘f∈ℋ;(2)
for everyf,g∈ℱ, the inverse transformation f-1 and the composition f∘g are also members of ℱ.Definition 3.
Letℋσ be a Hilbert space with norm ∥·∥σ and let ℱ act as a group over ℋσ. We say ℋσ is norm invariant under ℱ, if, for any h∈ℋσ and any f∈ℱ, there holds
(2)∥h∥σ=∥h∘f∥σ.
To explain the above definitions, we give an example.Example 4.
LetX=ℝ2, Y=[-M,M], Γ=R, and Kσ(x,x′)=exp{-∥x-x′∥22/σ2}, for x,x′∈X, and ℋσ be the closure of linear span of the set {Kσ,x:=Kσ(x,·):x∈X} with inner product 〈Kσ,x,Kσ,x′〉σ=Kσ(x,x′), for any σ∈Γ. Let the norm ∥·∥σ of functions in ℋσ be induced by the inner product.
Assumeℱ is a set of translation and rotation transformations on {ℋσ,σ∈Γ}: for any f∈ℱ and h∈{ℋσ,σ∈Γ}, there holds (h∘f)(x):=h(x+xf), for some xf∈X, or (h∘f)(x):=h(Afx), for
(3)Af=[cosθf-sinθfsinθfcosθf],
where θf is an angle dependent on f. We can verify that ℱ acts as a group over ℋσ and ℋσ is norm invariant under ℱ, for any σ∈Γ.Now we introduce standard least-square regularized regression algorithm. We denote error and empirical error of a functionf:X→Y with squared loss as follows. For a distribution ρ on X×Y, the error of f is defined as
(4)Eρ(f)=∫Z‍(f(x)-y)2dρ.
It is well known that the regression function minimizes the error. Indeed,
(5)∥f-fρ∥ρX2=ℰ(f)-ℰ(fρ),
where ρX is the marginal distribution of ρ on X and ∥f∥ρX2=∫X‍|f(x)|2dρX. The above difference is called the excess error of f, and for a sample set S={(xi,yi),i=1,2,...,m}, independently drawn according to ρ, the empirical error of f is defined as
(6)E^S(f)=1m∑i=1m‍(f(xi)-yi)2.In this paper, we consider a sequence of related learning tasks. The goal is to use information of related tasks to improve learning performance of one special learning task. Letℱ be a transformation set and ℋσ be a Hilbert space with norm ∥·∥σ, for any σ∈Γ, where Γ is an index set. We assume that there is κ>0, such that
(7)∥f∥∞≤κ∥f∥σ.Letρi denote the probability distribution of the ith task, for i=1,…,n. We assume {ρi}i=1n is pair-wise ℱ-related, ℱ acts as a group over ℋσ, and ℋσ is norm invariant under ℱ, for any σ∈Γ. Let Si={(xij,yij)}j=1m be samples independently drawn according to ρi. Since the n tasks are related, we try to use samples z=∪i=1nSi of all the n tasks to improve the learning performance of the target task.Standard least-square regularized regression algorithm associated with{ℋσ:σ∈Γ} for the ith single task is defined as the minimizer
(8)fSi=argminf∈ℋσ,σ∈Γ{E^Si(f)+λ∥f∥σ2}.
In the above optimization, there are two steps; firstly, for any fixed σ∈Γ, find the optimal function fSi,σ; secondly, find the global optimal function fS, for σ∈Γ. Since the n tasks are related, we try to use samples z=∪i=1nSi of all the n tasks to improve the learning performance of the target task. Without loss of generality, we choose the first task as the target task.Now, we propose least square regularized regression algorithm for multitask learning.Step 1.
Use samples of othern-1 tasks to select the approximate optimal ℋσ^ as follows:
(9)σ^=argminσ∈Γ,h2,…,hn∈ℋσ∑i=2n‍{E^Si(hi)+λ∥hi∥σ2}.Step 2.
Inℋσ^, search for the approximation h^1 to fρ1 as follows:
(10)(h^1,…,h^n)=argminh1,…,hn∈ℋσ^∑i=1n‍{E^Si(hi)+λ∥hi∥σ^2}.


## 3. Error Decomposition

To estimate the bound of excess errorEρ1(h^1)-Eρ1(fρ1), we introduce some notations. Let σi* be the optimal σ∈Γ for the ith task,
(11)(σi*,h¯i*)=argminσ∈Γ,h∈ℋσ{EPi(h)+λ∥h∥σ2}.Lemma 5.
Letρi denote the probability distribution of the ith task for i=1,…,n, let ℋσ be a Hilbert space with norm ∥·∥σ for σ∈Γ, and let ℱ be a transformation set. Assume {ρi}i=1n is pair-wise ℱ-related, ℱ acts as a group over ℋσ, and ℋσ is norm invariant under ℱ, for any σ∈Γ. Then σi* defined in (11) satisfies
(12)σ1*=σ2*=⋯=σn*.Proof.
By the assumption thatρi and ρj are ℱ-related, it is easy to show that
(13)infh∈ℋσEρi(h)=infh∈ℋσEρj(h),
for any i,j∈{1,…,n} and σ∈Γ. Notice that ℋσ is norm-invariant under ℱ for any σ∈Γ. Then, there holds
(14)infh∈ℋσ{Eρi(h)+λ∥h∥σ2}=infh∈ℋσ{Eρj(h)+λ∥h∥σ2},
for any σ∈Γ. Then the lemma follows.To decompose the excess error, we give the following notations. Denote(15)(h¯1,…,h¯n)=argminh1,…,hn∈ℋσ^∑i=1n‍{Eρi(hi)+λ∥hi∥σ^2},(h^1*,…,h^n*)=argminh1,…,hn∈ℋσ*∑i=1n‍{E^Si(hi)+λ∥hi∥σ*2}.Proposition 6.
Leth^i be defined in (10). Then under the assumption of Lemma 5, Eρ1(h^1)-Eρ1(fρ1)≤Eρ1(h^1)-Eρ1(fρ1)+λ∥h^1∥σ^2 can be bounded by
(16){Eρ1(h¯1*)-Eρ1(fρ1)+λ∥h¯1*∥σ*2}+{Eρ1(h^1)-E^S1(h^1)}+{E^S1(h¯1)-Eρ1(h¯1)}+1n-1∑i=2n‍{Eρi(h¯i*)-E^Si(h¯i*)}+1n-1∑i=2n‍{Eρi(h^i)-E^Si(h^i)}.Proof.
Write the regularization error as(17)Eρ1(h^1)-Eρ1(fρ1)+λ∥h^1∥σ^2={Eρ1(h^1)-E^S1(h^1)}+{(E^S1(h^1)+λ∥h^1∥σ^2)-(E^S1(h¯1)+λ∥h¯1∥σ^2)}+{E^S1(h¯1)-Eρ1(h¯1)}+{(Eρ1(h¯1)+λ∥h¯1∥σ^2)-(Eρ1(h¯1*)+λ∥h¯1*∥σ*2)}+{Eρ1(h¯1*)-Eρ1(fρ1)+λ∥h¯1*∥σ*2}.
By Lemma 5, for any i,j∈{1,…,n}, there holds Eρi(h¯i)+λ∥h¯i∥σ^2=Eρj(h¯j)+λ∥h¯j∥σ^2. Then we obtain
(18)Eρ1(h¯1)+λ∥h¯1∥σ^2=1n-1∑i=2n‍{Eρi(h¯i)+λ∥h¯i∥σ^2}=1n-1∑i=2n‍{(Eρi(h¯i)+λ∥h¯i∥σ^2)-(Eρi(h^i)+λ∥h^i∥σ^2)}+1n-1∑i=2n‍{(Eρi(h^i)+λ∥h^i∥σ^2)-(E^Si(h^i)+λ∥h^i∥σ^2)}+1n-1∑i=2n‍{E^Si(h^i)+λ∥h^i∥σ^2},Eρ1(h¯1*)+λ∥h¯1*∥σ*2=1n-1∑i=2n‍{Eρi(h¯i*)+λ∥h¯i*∥σ*2}=1n-1∑i=2n‍{(Eρi(h¯i*)+λ∥h¯i*∥σ*2)cccccccccccc-(E^Si(h¯i*)+λ∥h¯i*∥σ*2)}+1n-1∑i=2n‍{(E^Si(h¯i*)+λ∥h¯i*∥σ*2)ccccccccccccccc-∥h¯i*∥σ*2(E^Si(h^i*)+λ∥h^i*∥σ*2)}+1n-1∑i=2n‍{E^Si(h^i*)+λ∥h^i*∥σ*2}.
By the definition, we have that
(19)1n-1∑i=2n‍{(Eρi(h¯i)+λ∥h¯i∥σ^2)-(Eρi(h^i)+λ∥h^i∥σ^2)}≤0,1n-1∑i=2n‍{(E^Si(h¯i*)+λ∥h¯i*∥σ*2)-(E^Si(h^i*)+λ∥h^i*∥σ*2)}≥0,1n-1∑i=2n‍{E^Si(h^i)+λ∥h^i∥σ^2}≤1n-1∑i=2n‍{E^Si(h^i*)+λ∥h^i*∥σ*2}.
Therefore, we have
(20)(Eρ1(h¯1)+λ∥h¯1∥σ^2)-(Eρ1(h¯1*)+λ∥h¯1*∥σ*2)≤1n-1∑i=2n‍{(Eρi(h^i)+λ∥h^i∥σ^2)-(E^Si(h^i)+λ∥h^i∥σ^2)}+1n-1∑i=2n‍{(Eρi(h¯i*)+λ∥h¯i*∥σ*2)ccccccccccccccc-(E^Si(h¯i*)+λ∥h¯i*∥σ*2)}.
Then, the proposition follows.In (16), there are 5 terms. The first term is called regularization error which depends on the approximation ability of hypothesis space to fρ1. The estimation of this term has been discussed in [20] for reproducing kernel Hilbert space with Gaussian kernel with flexible variances.The other four terms are called sample error. In the second and third terms,h^1 and h¯1 are selected from ℋσ^ which is dependent on Si, for i=2,…,n, and is independent of S1. Therefore, when we take expectation of S1, ℋσ^ can be seen as a fixed function space. Consequently, these two terms can be estimated with the same method in the proof of Propositions 2.1 and 3.1 in [21]. In the fourth term, h¯i* is a fixed function, for i=1,…,n. Therefore, this term can also be estimated as in the proof of Proposition 2.1 in [21]. The last term is more difficult to deal with because h^i, for i=2,…,n, can not be considered in ℋσ, for any fixed σ∈Γ. Consequently, when sample number m→∞, the convergence rate of the sample error depends on that of the last term. Therefore, in the following section, we focus on the estimation for the bound of the last term in (16).


## 4. Error Analysis

In this section, we estimate the bound of the last term in (16). To bound this term, we have to estimate capacity of {ℋσ:σ∈Γ}. Here, the capacity is measured by the covering number.Definition 7.
For a subsetℱ of a metric space (X,d) and η>0, the covering number 𝒩(ℱ,η,d) is defined to be the minimal integer l∈ℕ such that there exist l disks with radius η covering ℱ.Forn∈ℕ and ℋσ,R={f∈ℋσ,∥f∥σ≤R}, define
(21)ℋσ,Rn={f=(f1,…,fn):fi∈ℋσ,R,i=1,…,n}.
For f∈ℋσ1,Rn and g∈ℋσ2,Rn, define
(22)l∞,n(f,g)=1n∑i=1n‍∥fi-gi∥∞,d∞(f,ℋσ2,Rn)=infg∈ℋσ2,Rnl∞,n(f,g).
Then, define the distance from ℋσ1,Rn to ℋσ2,Rn as
(23)d~∞(ℋσ1,Rn,ℋσ2,Rn)=supf∈ℋσ1,Rnd∞(f,ℋσ2,Rn).
Let 𝒩R(ε,Γ,d~∞) denote the minimal integer l∈ℕ such that there exist l parameters σ1,…,σl∈Γ, such that
(24)supσ∈Γmini∈{1,…,l}d~∞(ℋσ,Rn,ℋσi,Rn)≤ε.
Then, for ℋΓ,Rn={f=(f1,…,fn):fi∈ℋσ,R,i=1,…,n,σ∈Γ}, we have the following lemma.Lemma 8.
Consider the following:(25)𝒩(2ε,ℋΓ,Rn,l∞,n)≤𝒩R(ε,Γ,d~∞)·(supσ∈Γ𝒩(ε,ℋσ,R,l∞,1))n.Proof.
For anyf∈ℋΓ,Rn, there is σ∈Γ such that f∈ℋσ,Rn. By the definition of 𝒩R(ε,Γ,d~∞), there is σ¯∈{σ1,σ2,…,σ𝒩R(ε,Γ,d~∞)} such that d~∞(ℋσ,Rn,ℋσ¯,Rn)≤ε. Then, by the definition of d~∞, we have d∞(f,ℋσ¯,Rn)≤ε. And by the definition of d∞, there is f¯∈ℋσ¯,Rn satisfying l∞,n(f,f¯)≤ε.
By the definition of𝒩(ε,ℋσ¯,Rn,l∞,n), there is f~∈{fσ¯1,…,fσ¯𝒩(ε,ℋσ¯,Rn,l∞,n)}⊆ℋσ¯,Rn such that l∞,n(f¯,f~)≤ε. Therefore, we can obtain
(26)𝒩(2ε,ℋΓ,Rn,l∞,n)≤𝒩R(ε,Γ,d~∞)·supσ∈Γ𝒩(ε,ℋσ,Rn,l∞,n).
Note that, for any σ∈Γ, there holds 𝒩(ε,ℋσ,Rn,l∞,n)≤(𝒩(ε,ℋσ,R,l∞,1))n. Then the lemma follows.Proposition 9.
ForR=M/λ and h^i, for i=2,…,n, defined in (10), there holds
(27)P{1n-1∑i=2n‍{Eρi(h^i)-E^Si(h^i)}≥ε1}≤𝒩(ε116(κR+M),Γ,d∞)·(supσ∈Γ𝒩(ε116(κR+M),ℋσ,R,l∞,1))n-1·exp{-(n-1)mε128(κR+M)2}.Proof.
By the definition ofh^i, we have ∥h^i∥σ^≤R, for i=1,2,…,n. Then, there holds
(28)P{1n-1∑i=2n‍{Eρi(h^i)-E^Si(h^i)}≥ε1}≤P{sup[f2,…,fn]∈ℋΓ,Rn-11n-1∑i=2n‍{Eρi(fi)-E^Si(fi)}≥ε1}.
For f=[f2,…,fn]∈ℋΓ,Rn-1, denote Lz(f)=(1/(n-1))∑i=2n‍{Eρi(f)-E^Si(f)}. Note that, for f,g∈ℋΓ,Rn-1, there holds
(29)|Lz(f)-Lz(g)|=1n-1∑i=2n‍{Eρi(f)-E^Si(f)}-1n-1∑i=2n‍{Eρi(g)-E^Si(g)}=1n-1∑i=2n‍{∫Z‍(fi(x)-y)2dρi-∫Z‍(gi(x)-y)2dρi}-1n-1∑i=2n‍{1m∑j=1m‍(fi(xji)-yji)2cccccccccccccccc-1m∑j=1m‍(gi(xji)-yji)2}≤4(κR+M)·l∞,n-1(f,g).
Therefore, we can find that 𝒩=𝒩(ε1/8(κR+M),ℋΓ,Rn-1,l∞,n-1) balls {ℋk,Rn-1}k=1𝒩 such that the center f~k of each ball and point fk in this ball satisfies |Lz(f~k)-Lz(fk)|≤ε/2. Therefore, the probability in (28) can be bounded by following expression:
(30)P{sup[f2,…,fn]∈⋃k=1𝒩(ε1/8(κR+M),ℋΓ,Rn-1,l∞,n)‍ℋk,Rn-1Lz(f)≥ε1}≤𝒩(ε18(κR+M),ℋΓ,Rn-1,l∞,n)·maxk∈1,…,𝒩P{sup[f2,…,fn]∈ℋk,Rn-1Lz(f)≥ε1}≤𝒩(ε18(κR+M),ℋΓ,Rn-1,l∞,n)·maxk∈1,…,𝒩P{Lz(f~k)≥ε12}.
For the covering number 𝒩, by Lemma 8, we have the estimate
(31)𝒩(ε18(κR+M),ℋΓ,Rn-1,l∞,n)≤𝒩(ε116(κR+M),Γ,d~∞)·(supσ∈Γ𝒩(ε116(κR+M),ℋσ,R,l∞,1))n-1.
Using Hoeffding inequality, for any fixed f~k, we have
(32)P{Lz(f~k)≥ε12}=P{1(n-1)m×∑i=2n‍∑j=1m‍{∫Z‍(f~ik(x)-y)2dρi-(f~ik(xji)-yji)2∫Z‍}≥ε121(n-1)m}≤exp{-(n-1)mε128(κR+M)2}.
Then, the proposition follows.Finally, we can obtain a bound for the last term of (16) by Proposition 9.Proposition 10.
Leth^i, for i=2,…,n, be defined in (10). Assume, for all σ∈Γ and foralls>0, there holds
(33)ln𝒩(η,ℋσ,1,l∞,1)≤C0(1η)s.
Then with confidence at least 1-δ, there holds
(34)1n-1∑i=2n‍{Eρi(h^i)-E^Si(h^i)}≤ε0,
where ε0 is the solution of the following equation:
(35)ε02+s-8(ln(1/δ))(κR+M)2(n-1)mε0s-8(κR+M)2m×C0(16(κR2+MR))s-8(κR+M)2(n-1)mln𝒩R(ε016(κR+M),Γ,d∞)=0.Proof.
Let(36)δ=𝒩R(ε116(κR+M),Γ,d∞)·(supσ∈Γ𝒩(ε116(κR+M),ℋσ,R,l∞1))n-1·exp{-(n-1)mε128(κR+M)2}.
By condition on ln𝒩(η,ℋσ,1,l∞,1)≤C0(1/η)s, we have
(37)ln𝒩(ε116(κR+M),ℋσ,R,l∞,1)≤C0(16(κR2+MR)ε1)s.
Then, ε1 is not larger than ε0 in the following equation:
(38)lnδ=ln𝒩R(ε016(κR+M),Γ,d∞)+(n-1)C0(16(κR2+MR)ε0)s-(n-1)m8(κR+M)2ε02.
Then by Proposition 9, the proposition follows.Remark 11.
Compare multitask learning with multiple Hilbert spaces to single task learning with multiple Hilbert space.
Recall that the least square regularized regression in{ℋσ,σ∈Γ} for single task is defined as
(39)(σ^1,h^1)=argminh1∈ℋσ,σ∈Γ{E^S1(h1)+λ∥h1∥σ2}.Eρ1(h^1)-Eρ1(fρ1) can be bounded by the sum of regularization error and sample error with similar method in Proposition 6. In the sample error, the term most difficult to estimated will be ES^1(h^1)-Eρ1(h^1), because function h^1 changed with the S1 runs over function set {ℋσ,σ∈Γ}. By the same method in Proposition 10, with confidence 1-δ, this term can be bounded by the solution ε~0 of the following equation:
(40)ε~02+s-8(ln(1/δ))(κR+M)2mε~0s-8(κR+M)2m×C0(16(κR2+MR))s-8(κR+M)2mln𝒩R(ε~016(κR+M),Γ,d∞)=0.
Obviously, we have ε0<ε~0. Therefore, multitask learning algorithm has potential faster learning rate.Remark 12.
Comparing multitask learning with multiple Hilbert spaces to single task learning with single Hilbert space.
In this paper, we set the hypothesis space as a set of Hilbert spaces. It is well known that hypothesis space with more functions has stronger approximation ability and bigger complexity. Therefore, the regularization error may be smaller and sample error may be larger than that of algorithms with a single Hilbert space being the hypothesis space.
For least square regularized regression with a single Hilbert spaceℋσ for single task, with confidence 1-δ, the largest term in sample error can be bounded by the solution ε¯0 of the following equation:
(41)ε¯02+s-8(ln(1/δ))(κR+M)2mε¯0s-8(κR+M)2mC0(16(κR2+MR))s=0.
If we assumen=𝒪(mζ) with some ζ>0 large enough, (8(κR+M)2/(n-1)m)ln𝒩R(ε0/16(κR+M),Γ,d∞) in Proposition 10 can converge to 0 fast. Then, we can obtain ε0≈ε¯0, while the regularization error of multitask learning with multiple Hilbert spaces is smaller. Trading off the regularization error and sample error, we can obtain potential faster learning rate than that of single task learning.



---

*Source: 715275-2013-12-21.xml*