Nonparametric Risk and Stability Analysis for Multi-Task Learning Problems

1 Introduction

As machine learning is applied to a growing number of domains, many researchers have looked to exploit similarities in machine learning tasks in order to increase performance. For example, one may suspect that data for the classification of one commodity as profitable or not may help in classifying a different commodity. Similarly, it is likely that data for spam classification in one language can help spam classification in another language. A common technique for leveraging data from different domains for machine learning tasks is multitask learning. Multi-task learning pools multiple domains together and couples the learning of several tasks by regularizing separate estimators jointly and dependently. For instance, in transfer learning, a special case of multi-task learning, one uses data (or an estimator) from a well understood source domain with plentiful data to aid the learning of a target domain with scarce data. Although multi-task learning algorithms are becoming prevalent in machine learning, there are gaps in our understanding of their properties, especially in nonparametric settings. This paper looks to increase our understanding of fundamental questions such as: What can one say about the true risk of a multi-task estimator given its empirical risk? How do relative sample sizes affect learning among different domains? How does the similarity between two functions affect one's ability to transfer learning between them?

Although there are many regularization techniques proposed for multi-task learning (Figure 1 (left)), there are very few studies on how the learning bounds change under different parameter regularizations. In this paper, we analyze the stability bounds under a general framework of multitask learning using kernel ridge regression. Our formulation places a reweighting matrix ⇤ on task weights to capture the relationship among tasks. Our analysis shows that most existing work can be cast into this framework by changing the reweighting matrix ⇤. More importantly, we show that the stability bounds under this framework depend on the diagonal blocks of ⇤-1 , thus providing insights on how much we can gain from regularizing the relationship among tasks by using different reweighting matrices.

Moreover, recently a general framework on transfer learning under model shift has been proposed [Wang et al., 2014], where the conditional distribution between the source and target domains is allowed to differ, unlike in many previous methods, but the change is assumed to be smooth (Figure 1 (right)). However, it is not clear how performance varies with the type of smoothness assumption. Furthermore, it is unclear under what conditions transfer learning improves estimation over typical one data-set learning. In this paper, we provide analysis that connects the smoothness of the offset function to the learning bounds for this kind of transfer. We obtain tighter learning bounds for transfer learning when we assume a smooth change across domains, given that the data from the source domain is sufficiently large.

Contribution We provide a stability analysis for multi-task learning that allows one to understand the gap between the true risk and the empirical risk for many popular estimators. Also, we analyze the risk of multi-task learning under a nonparametric function transfer learning framework. In our analysis we derive an upperbound for the L2 risk that elucidates previously unknown question such as the relationship between sample sizes and loss, as well as conditions for outperforming one data-set estimation with transfer learning.

2 RelatedWork

A large part of multi-task learning work is formulated using kernel ridge regression (KRR) with various regularizations on task relations. The `2 penalty is used on a shared mean function and on the variations specific to each task [Evgeniou and Pontil, 2004; Evgeniou et al., 2005]. In [Solnon et al., 2013] a pairwise `2 penalty is placed between each pair of tasks. In [Zhou et al., 2011] an `2 penalty is proposed on each pair of consecutive tasks that controls the temporal smoothness. By regularizing the shared clustering structure among task parameters, task clusters are constructed for different features [Zhong and Kwok, 2012]. A multi-linear multi-task learning algorithm is proposed in [Romera-Paredes et al., 2013] by placing a trace norm penalty. However, there are very few literature dealing with the stability of multi-task KRR algorithms. The stability bounds for transductive regression algorithms are analyzed in [Cortes et al., 2008]. In [Audiffren and Kadri, 2013], the authors study the stability properties of multi-task KRR by considering each single task separately, thus failing to reveal the advantage of regularizing task relations. In [Maurer and Pontil, 2013], a regularized trace-norm multi-task learning algorithm is studied where the task relations are modeled implicitly, while we study a general family of multi-task learning algorithms where the task relations are modeled explicitly, reflected by a reweighting matrix ⇤ on task weights. More recently, the algorithmic stability for multi-task algorithms with linear models f(x) = w>x is studied in [Zhang, 2015]. While in this paper we consider the more challenging nonlinear models with feature map φ(x), where the new multi-task kernel between xi↪ xj is defined as φ(xi)⇤-1φ>(xj) by absorbing the reweighing matrix ⇤ on task weights. Our theory is also developed on the more general nonlinear models.

Most work on transfer learning assumes that specific parts of the model can be carried over between tasks. Recent work on covariate shift [Shimodaira, 2000; Huang et al., 2007; Gretton et al., 2007; Yu and Szepesvri, 2012; Wen et al., 2014; Reddi et al., 2015] considers the case where only P (X) differs across domains, while P(Y ♣X) stays the same (here X denotes the input feature space and Y denotes the output label space). In [Zhang et al., 2013], target and conditional shift are modeled by matching the marginal distributions on X. For transfer learning under model shift, there could be a difference in P(Y ♣X) that can not simply be captured by the differences in distribution P(X), hence neither covariate shift or target/conditional shift will work well under the model shift assumption. This problem is also demonstrated in [Wang et al., 2014]. In the same paper, the authors propose a transfer learning algorithm to handle the general case where P(Y ♣X) changes smoothly across domains.

We focus our analysis to the nonparametric setting. In particular, we consider orthogonal series regression, where one attempts to model functions using a finite collection of orthonormal basis functions [Tsybakov, 2009; Wasserman, 2006]. Moreover, we also consider kernel ridge regression, a natural generalization of ridge regression [Hoerl and Kennard, 1970] to the nonparametric setting [Gy¨orfi, 2002].

3 Stability Analysis onMulti-Task Kernel Ridge Regression

In this section, we analyze the stability bounds for multitask kernel ridge regression (MT-KRR). Our analysis shows that, MT-KRR achieves tighter stability bounds than independent task learning by regularizing task relations. In addition, different regularization techniques yield different stability bounds that are closely related to the diagonal blocks of the inversed reweighting matrix. Due to space constraints please refer to the appendix 1 for all the proofs.

3.1 Multi-task KRRAlgorithm: Formulation and Objective

Assume we have T tasks, each task t has data matrix Xt 2 Rnt⇥d ↪ Yt 2 Rnt , where xt↪i 2 X is the i-th row of Xt, and yt↪i 2 Y is the i-th scalar of Yt. nt is the number of data points for each task, and d is the dimension of features. Denote the total number of data points as m = PTt=1 nt.

Let φ be the feature mapping on x associated to kernel k with dimension q, and Φ(Xt) denote the matrix in Rnt⇥q whose rows are the vectors φ(xt↪i). Let Φ(X) 2 Rm⇥Tq represent the diagonalized data matrix Φ(X) = diag[Φ(X1) Φ(X2) · · · Φ(XT )] for all tasks, Y 2 Rm⇥1 be the stacked label vector Y = [Y1 Y2 ▷ ▷ ▷ YT ]>, and w 2 RTq⇥1 be the stacked weight vector w = [w1 w2 ▷ ▷ ▷ wT ]>. Throughout the paper we use `2 loss as the loss function for a hypothesis h, i.e., l(h(x)↪ y) = (h(x) - y)2 . Note that l(h(x)↪ y) is a σ-admissible loss function, i.e., 8x↪ y↪ 8h↪ h0 ↪ ♣l(h(x)↪ y) - l(h0 (x)↪ y)♣  σ♣h(x) - h0 (x)♣. For `2 loss σ = 4B, assuming ♣h(x)♣  B↪ ♣y♣  B for some B > 0. Define the MT-KRR objective as:

where ⇤ is a Tq ⇥ Tq reweighting matrix on task weights w. Let ˜ φ(xt↪j) = [0 · · · 0 φ(xt↪j) 0 · · · 0] be a row of Φ(X) for task t. Let H be a reproducing kernel Hilbert space with kernel k⇤-1(xs↪i↪ xt↪j) = ˜ φ(xs↪i)⇤-1 ˜ φ>(xt↪j) (s↪ t are indices for tasks), the objective becomes:

1 Available at http://www.autonlab.org/autonweb/24058.html

where g(x) = hg↪ k⇤-1(x↪ ▷)iH, and ♣♣▷♣♣K⇤-1 is the norm in H. This generalizes to the case where q = 1. The solution to MT-KRR is (assuming nonsingular ⇤): w = ⇤-1Φ>(X)[Φ(X)⇤-1Φ>(X) + mI]-1Y . Note in multitask learning setting, we have ⇤ = ⌦ ⌦ Iq (for some ⌦ 2 RT⇥T ), where Iq is the q ⇥ q identity matrix and ⌦ is the Kronecker product. By the property of the inverse of a Kronecker product, ⇤-1 = M ⌦ Iq where M = ⌦-1 , and it can be easily shown that k⇤-1 (xs↪i↪ xt↪j ) = Ms↪tk(xs↪i↪ xt↪j ). Most existing multi-task algorithms can be cast into the above framework, see Table 1 for a few examples.

Remark. Eq. 1 assumes same weight 1◁m on the loss for (xt↪j↪ yt↪j) for all tasks. Alternatively, we can put different weights on the loss for different tasks, i.e, minw PTt=1 1 nt Pnt j=1 (φ(xt↪j)wt - yt↪j)2 + w>⇤w. The solution becomes w = ⇤-1Φ>(X)(Φ(X)⇤-1Φ>(X) + C -1 I)-1Y , where C is the loss-reweighting matrix with 1◁nt's as the diagonal elements. As C is the same under different ⇤'s, it is not the focus of this paper. A study on the effect of C can be found in [Cortes et al., 2008].

3.2 Uniform Stability for MT-KRR

We study the uniform stability [Bousquet and Elisseeff, 2002], which is usually used to bound true risk in terms of empirical risk, for the MT-KRR algorithm.

Definition 3.1. ([Bousquet and Elisseeff, 2002]). The uniform stability β for an algorithm A w.r.t. the loss function l is defined as: 8S 2 Z m↪ 8i 2 ¶1↪ ▷▷▷↪m♦↪ ♣♣l(AS↪ ▷) - l(AS∩i↪ ▷)♣♣1  β, where Z = X ⇥ Y drawn i.i.d from an unknown distribution D, and S ∩ i is formed by removing the i-th element from S.

Definition 3.2. (Uniform stability w.r.t a task t). Let i be a data index for task t. The uniform stability βt of a learning algorithm A w.r.t a task t, w.r.t. loss l is: 8S 2 Z m↪ 8i 2 ¶1↪ ▷▷▷↪ nt♦↪ ♣♣l(AS↪ ▷) - l(AS∩i↪ ▷)♣♣1  βt▷

Let the risk or generalization error be defined as R(A↪ S) = Ez[l(AS↪ z)]↪ z 2 Z, and the empirical error be defined as Remp = 1m Pmi=1 l(AS↪ zi)↪ zi 2 Z m. Then we have the following generalization error bound (Theorem 12, [Bousquet and Elisseeff, 2002]) with probability at least 1 - δ: R  Remp + 2β + (4mβ + 4B2 )q ln 1◁δ 2m . This theorem gives tight bounds when the stability β scales as 1◁m. For the MT-KRR algorithm, we have the following theorem hold with respect to the uniform stability:

Theorem3.3. Denote ⇤-1 =M⌦Iq, andM1↪ ▷ ▷ ▷ ↪MT are the diagonal elements of M. Assuming the kernel values are bounded: 8x 2 X↪ k(x↪ x)  2 < 1. The learning algorithm defined by the minimizer of Eq. 1 has uniform stability β w.r.t. σ-admissible loss l with:

The proof is similar to the proof of Thm. 22 in [Bousquet and Elisseeff, 2002], except that in the multi-task learning setting, for the tth task ˜ φ(xt↪i) = [0 · · · 0 φ(xt↪i) 0 · · · 0], by the standard bounds for Rayleigh quotient, we have

Remark. The above theorem provides a more direct stability bound by taking the maximum over the diagonal elements of M, instead of computing the largest eigenvalue as in [Zhang, 2015]. Also, for a specific task t, if Mt < maxs¶Ms♦, then it is possible to obtain tighter stability βt using only Mt, which yields tighter bounds than the one in [Zhang, 2015] where they consider the worst case for all tasks.

Lemma 3.4. The learning algorithm defined by the minimizer of Eq. 1 has uniform stability βt w.r.t a task t, w.r.t. σ-admissible loss l with: βt  σ2 2 2nt Mt.

The proof is a straightforward adaptation of proof of Thm 3.3, with x constrained to be xt↪i. The reason we care about βt is that, it leads to a tighter generalization error bound for a task t, given βt < β. We have, with probability at least 1-δ, Rt  Rtemp +2βt+(4ntβt+4B2 )q ln 1◁δ 2nt , whereRt = Ez[l(AS(xt↪i)↪ yt↪i)], Rtemp = 1 nt Pnt i=1 l(AS(xt↪i)↪ yt↪i). In the following section, we study the stability bounds under a few special cases (Table 1), where it can be shown that we have tighter stability bounds for MT-KRR than learning each task independently.

3.3 Stability Bounds under Different Penalties

(a) Independent tasks. It is easy to derive that 8t↪Mt = 1◁λs, and βind  σ2 2 2λsm .

Remark. In [Audiffren and Kadri, 2013], the stability of multi-task KRR is analyzed by considering each task separately, which corresponds to the above analysis. In the following, we will show that different regularizations on task relations help tighten the stability bounds of MTL algorithms.

(b) Central function+offset. Applying blockwise matrix inversion we have 8t, Mt = λp◁T+λs λs(λp+λs) . We achieve tighter stability bounds than βind for T ≥ 2 and λp > 0 since:

(c) Pairwise penalty. Similarly to (b), we can derive that 8t, Mt = λp+λs λs(λpT+λs) . For T ≥ 2 and λp > 0, again we obtain tighter bounds than βind:

(d) Temporal penalty. We have the following lemma:

Lemma 3.5. Let ⇤ be defined as in Table 1 under temporal penalty and M be defined as in theorem 3.3. Let Mtmid be the middle element(s) of M1↪M2↪ ▷ ▷ ▷ ↪MT , i.e., tmid = T◁2↪ T◁2 + 1 if T is even, and tmid = (T + 1)◁2 if T is odd. Then the following hold: Mt < Mt-1↪ t = 2↪ ▷ ▷ ▷ ↪ tmid;Mt < Mt+1↪ t = tmid↪ ▷ ▷ ▷ ↪ T;maxtMt = M1 =MT < 1 λs ;mintMt =Mtmid ≥ λp+λs λs(λpT+λs) ▷

+λs PTt=1 ♣♣wt♣♣2

Table 1: Examples of multi-task learning algorithms with different ⇤'s as penalty

Combining Lemma 3.5 and Lemma 3.4 we can see that, with temporal penalty we have tightest stability bounds βt for t = tmid. Also, we achieve tighter stability bounds βt for the tth task than the t-1th task, if t < tmid; and tighter βt for the tth task than the t + 1th task, if t > tmid. However, since Mtmid ≥ (λp + λs)◁(λs(λpT + λs)), we achieve a looser bound with temporal penalty than Eq. 3 or Eq. 4. It indicates that we might lose some algorithmic stability due to the relatively restricted temporal smoothness assumption, compared to assuming pairwise smoothness. Nonetheless, the stability bound with temporal penalty is tighter than learning each task independently: maxt Mt < 1◁λs, for T ≥ 2.

4 Upper Bounds on Transfer Learning

A special case of multi-task learning, transfer learning, also assumes that one can benefit from task relations, but focuses mainly on two tasks. While general multi-task learning assumes a comparable number of samples for each task, transfer learning usually assumes a sufficiently labeled source task and a very limited labeled target task. In this section, we analyze the L2 risk for transfer learning with respect to the source and target sample size, and smoothness assumptions made between the tasks.

4.1 Model

We consider a densely sampled function f0, which one uses to aid in the regression of a sparsely sampled function f1. The relationship between functions is defined through a smoothness assumption on the difference of the two functions: g(x) ⌘ f1(x) - f0(x).

Our estimator works as follows: first, we use a sample of noisy f0 values to produce an estimate ˜ f0; second, we use ˜ f0 to generate noisy samples of g by subtracting ˜ f0 from noisy samples of f1, and we produce an estimate ˆ g; lastly, we define our estimator of f1 as ˆ f1(x) ⌘ ˜ f0(x) + ˆ g(x). Specifically we consider the following data:

Note, ⌅ is an error distribution with moment constraints. Furthermore, we shall take n1 = O(n0), although this is not necessary for the bounds derived below.

8<:

4.2 Basis Functions and Projections

We describe the estimation of functions using orthonormal basis functions. Let ¶'i♦i2Z be an orthonormal basis for L2([0↪ 1]), where L2(⌦) = ¶f : ⌦ 7! R : R⌦ f 2 < 1♦. Then, the tensor product of ¶'i♦i2Z serves as an orthonormal basis for L2([0↪ 1]d ); that is, the following is an orthonormal basis for L2([0↪ 1]d ): ¶'↵♦↵2Zd where '↵(x) = Qdi=1 '↵i (xi)↪ x 2 [0↪ 1]d . So we have that 8↵↪ ⇣ 2 Zd ↪ h'↵↪ '⇣i = I¶↵ = ⇣♦. Let f 2 L2([0↪ 1]d ), then f(x) = P↵2Zd a↵(f)'↵(x) where a↵(f) = h'↵↪ fi = R[0↪1]d '↵(z)f(z)dz 2 R.

Suppose function f has a corresponding set of evaluations Y = ¶yj = f(uj) + ✏j♦nj=1 where uj iid ⇠ Unif([0↪ 1]d ) and E [✏j] = 0, E ⇥✏2j ⇤ <1. Then, ˜ f, the estimate of f, will be:

and M is a finite set of indices for basis functions.

4.3 Theory

We bound the L2 risk of a transfer learning based estimate of f1: E hkf1 - ˆ f1k2 i. First, we state our assumptions on functions f0, and f1:

(a) Sobolev Ellipsoid Function Class Assumptions. We shall make a Sobolev ellipsoid assumption for f0↪ f1 2 F. Let a(f) ⌘ ¶a↵(f)♦↵2Zd. Suppose that: Fγ↪A = ¶f : a(f) 2 ⇥γ↪A↪ kfk1  fmax♦, where ⇥γ↪A = n¶✓↵♦↵2Zd : P↵2Zd ✓2↵2γ (↵) < A2o, and 2γ (↵) = Pdi=1 ♣↵i♣2γi for γ 2 Rd++, fmax↪A 2 R++, R++ = (0↪1). This assumption will control the tail-behavior of projection coefficients and allow one to effectively estimate f 2 F using a finite number of projection coefficients on the empirical functional observation.

(b) Smooth Difference Assumption. We shall make an additional assumption on the difference between f1 and f0, g(x) ⌘ f1(x) - f0(x): g = f1 - f0 2 F⇢↪B. Namely, we are imposing a smoothness constraint on the difference between our functions f0 and f1, which we will show controls the effectiveness of transfer learning.

Estimator: Before writing our estimator for f1, we define some terms. First, let ˜ f0 be the standard estimator for f0 based of Y0, let Mγ(t) ⌘ ¶↵ 2 Zd : γ(↵)  t♦:

We will take ˆ g to be the estimate of g based on Z, where

and g(x) = f1(x)-f0(x), r(x) = f0(x)- ˜ f0(x). Our estimator for f1 will then be: ˆ f1(x) = ˜ f0(x) + ˆ g(x), where ˆ g is the estimate of g based on Z, ˆ g(x) = P↵2M⇢(v) a↵(Z)'↵(x).

Risk Analysis: We analyze the L2 risk of our estimator below. Note that:

bound the risk for typical function estimation E hkf0 - ˜ f0k22 i then that for the smooth transfer E ⇥kg - ˆ gk22 ⇤. First we analyze the risk of standard functions regression one a single data-set for the estimation of the source function.

Next we analyze the risk of estimating g from Z (13). Note that Z is not a set of noisy observations from g as Y0 is to f0; we, instead have biased observations (from using ˜ f0), thus the rate will vary a bit.

One can see that we pay a penalty of (1 + n1◁n0)2◁(2+⇢-1 ) for using a biased sample to approximate g. As one would expect the penalty diminishes as n0 !1. Note furthermore that if n0 ≥ n1 then this penalty is no more than 2 2 2+⇢-1 = O(1). Hence, the risk of ˆ g is asymptotically upper-bounded with the same rate as that of the unbiased sample estimator ˜ g.

Transfer Estimator Risk: Below we state this section's main theorem and discuss some insights gained from it.

For simplification, consider the case where smoothness parameters are γ> = (⌧↪ ▷ ▷ ▷ ↪ ⌧)> and ⇢> = (⌫↪ ▷ ▷ ▷ ↪ ⌫)>, and

smoother than each function) and λ > 1 (the densely sampled function has strictly more samples than the sparsely sampled

have shown that transfer learning is asymptotically faster than single data-set regression on the target function for the typical case where the target function is similar to the source function and we have more samples from a source function. In fact, if

In other words, transfer learning has an asymptotic risk of regressing the smooth difference function g with the target sample of size n1: E hkf1 - ˆ f1k2 i = O (E [kg - ˜ gk2]), where ˜ g is defined analogously to (9) with a sample size of n1. Since functions f1 and f0 are similar the asymptotic reduction to the rate of estimation for g proves very beneficial.

Remark. We see that the upper bounds derived for MT-KRR and transfer learning are both affected by the smoothness assumptions we make between/among tasks (the γ↪ ⇢ parameter in the above analysis, and the λp↪ λs parameter in Sec. 3.3).

5 Experiments

5.1 Synthetic Data

Multi-Task Learning Stability. To show the stability bounds under different penalties, we simulate data with T tasks. Each task t has ¶Xt↪ Yt♦ : Yt = fc + fo + 0▷1✏, where fc = sin(20x) + sin(10x) is the central function, and fo = sin5(1 + ti)x is a smoother additive function, with ti ⇠ Unif(0↪ 1), plus ✏ 2 N(0↪ 1). Fig.2 (left) shows an example of the data with T = 3 and nt = 20 per task.

In Fig.2, we also plot the risk difference R -Remp (Sec. 3.2) w.r.t different number of tasks (fixed 10 points per task), and different number of points per task (with fixed 5 tasks), averaged over 50 experiments. We also plot the theoretical bounds (fitted to the actual curve using regression) for each case. We see that the results are consistent with our analysis. Using central+offset (Eq. 3), pairwise-penalty (Eq. 4), or temporal-penalty (Lemma 3.5) we achieve tighter bounds than learning each task independently (denoted as Separate). In addition, central+offset and pairwise-penalty result in the same curve (red and blue) when we set λp◁T in central+offset equal to λp in pairwise-penalty, which shows the equivalence of these two methods. Further we observe that temporalpenalty gives slightly larger R - Remp than central+offset and pairwise-penalty, which coincides with our analysis.

Transfer Learning Risk. We illustrate the risk of function transfer learning through an experiment with synthetic data. We randomly generate f0, g, and f1 and we draw data-sets Y0, Y1 with various configurations of n1 and n0. We consider the cosine basis: '0(x) = 1↪ 'k(x) = p2 cos(⇡kx)↪ 8 k ≥ 1.

We define f0(x) ⌘ PMk=0 ✓(0) k 'k(x), by generating the projection coefficients ✓(0) , M = 500. See Fig.3 (a) for example of functions. Specifically we consider n1 2 ¶15↪ 20↪ ▷ ▷ ▷ ↪ 50♦ and n0 = n21 . For each configuration, we draw 100 instances of Y0 and Y1 and we estimate the risk at (n0↪ n1) by crossvalidating the set of projection coefficients and calculating the loss of the estimate, and taking the mean over the 100 instances of Y0 and Y1. The risk estimation was performed for the values of γg 2 ¶1▷25↪ 1▷75↪ 2▷25♦ and γ0 = 1, keeping f0 constant throughout and changing g per value of γg (see Fig.3 (b-d)). As one would expect given our analysis, as the smoothness of g increases (i.e. γg increases) so too does the efficacy of transfer learning. It is interesting to note that transfer learning outperforms typical regression in all scenarios except for when one does not have a smooth offset and many source data samples; this too is consistent with our analysis. Lastly, it is worth noting that we can achieve a good fit of our upperbound on risks of transfer learning (Theorem 4.3).

5.2 Real Data

The real dataset is the Air Quality Index (AQI) dataset [Mei et al., 2014]. We extract bag-of-words vectors (feature X with dimension d = 100↪ 395) from social media posts to predict the AQI (label Y ) across cities. The results are averaged over 20 experiments. In Fig. 4 (left), we show the prediction error of MT-KRR using pairwise penalty (or equivalently the central+offset penalty) with 4 cities as 4 different tasks. We see that the MT-KRR algorithm (mtl) outperforms independenttask-learning (ind). In addition, we plot the leave-one-out error for each task (loo-1 through 4), and the prediction error by MT-KRR for the best task (mtl-min), which outperforms learning that task by itself (loo-3). Fig. 4 (right) shows the prediction error using the transfer method analyzed in this paper, compared with state-of-the-art baselines. The transfer method benefits from modeling a smoother offset across domains compared to optDA [Chattopadhyay et al., 2011] with single-source, and it also outperforms KMM [Huang et al., 2007] by allowing changes in P(Y ♣X).

6 Conclusion

In this paper we provide theory that connects the risk bounds for both transfer and multi-task learning to the relation of tasks. We show that, by imposing a smooth relationship between/among tasks, we obtain favorable learning rates for both algorithms, compared to learning tasks independently.

Acknowledgments

This work is funded in part by DARPA grants FA87501220324, FA87501420244, NSF IIS-1247658 and DOE DE-SC0011114 grants.