Stability and Hypothesis Transfer Learning

Ilja Kuzborskij
Idiap Research Institute, SwitzerlandÉcole Polytechnique Fédérale de Lausanne (EPFL), Switzerland

ilja.kuzborskij@idiap.ch

Francesco Orabona
Toyota Technological Institute at Chicago, USA

francesco@orabona.com

Abstract
We consider the transfer learning scenario,
where the learner does not have access to thesource domain directly, but rather operates
on the basis of hypotheses induced from it– the Hypothesis Transfer Learning (HTL)
problem. Particularly, we conduct a theoretical analysis of HTL by considering the algorithmic stability of a class of HTL algorithms
based on Regularized Least Squares with biased regularization. We show that the relatedness of source and target domains accelerates the convergence of the Leave-OneOut error to the generalization error, thus enabling the use of the Leave-One-Out error tofind the optimal transfer parameters, even in
the presence of a small training set. In caseof unrelated domains we also suggest a theoretically principled way to prevent negativetransfer, so that in the limit we recover the
performance of the algorithm not using any
knowledge from the source domain.

1. Introduction
The standard assumption in supervised machine learning algorithms is to have models trained and tested on
samples drawn from the same probability distribution.
However, this assumption is often violated in practicalapplications.
A more general setting is the one in which the marginal
distributions over training and testing domains are different but related. This is the problem of Domain
Adaptation (DA), where a successful scheme typically
Proceedings of the 30 th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013. JMLR:
W&CP volume 28. Copyright 2013 by the author(s).

utilizes large unlabeled samples from both domains toadapt a source hypothesis to the target domain. Previous work has addressed in detail the theory of DA andproposed algorithms that critically depend on optimal
weighting parameters given by the theoretical analysis (Ben-David et al., 2010a;b; Mansour et al., 2009b;
Cortes et al., 2008). However, in practice, the learnerneeds access to sufficient unlabeled samples from both
domains to estimate these parameters. Even if unlabeled data are abundant, the estimation of these parameters can be computationally prohibitive in somescenarios. A hypothetical example is a large number ofdomains involved or, for instance, when one acquires
new domains incrementally. Here, keeping unlabeleddata from all the domains and reestimating parameters is a necessity.
To overcome this practical limitation, a new framework has been analyzed by a number of works (FeiFei et al., 2006; Yang et al., 2007; Orabona et al.,2009; Mansour et al., 2009a; Tommasi et al., 2010;
Kuzborskij et al., 2013). In this framework, that wewill call Hypothesis Transfer Learning (HTL), unlike
DA, only source hypotheses trained on a source domain
are utilized. The attractive quality of HTL is the fact,that it assumes no explicit access to the source domain, nor any knowledge about the relatedness of thesource and target distributions. Although, this setting
has been explored empirically with success, a formal
theory of HTL is mostly missing. Hence it is unclear
how to recover optimal transfer parameters and what
properties of the source hypothesis affect generalization.
In this paper, we take a step towards a theory of HTL.
In particular, we analyze the generalization ability ofa class of HTL algorithms stemming from Regularized Least Squares (RLS) with biased regularization.
We assume access to a given number of source hypotheses and a small set of training samples from tar-

Stability and Hypothesis Transfer Learning

get domain. Rather than relying on oracle inequalities for tuning the optimal parameters, we use the
Leave-One-Out (LOO) risk. The LOO risk is known
to have low bias compared to empirical risk or crossvalidation (Elisseeff & Pontil, 2003), thus making it
preferrable in a small sample regime.
In the following, we will show that the variance of the
LOO estimator for the considered algorithms decreases
with the increasing quality of the source hypothesis
over the target domain. We do so by employing thenotion of hypothesis stability (Bousquet & Elisseeff,2002), and upper bounding the second-order momentof the difference between the expected risk and the
LOO risk. In addition, we propose how a hypotheticalalgorithm could avoid negative transfer in the case of
unrelated domains, while in worst case scenario recovering the generalization guarantees of RLS. As a side
effect, we improve polynomial generalization bounds of
Bousquet & Elisseeff (2002) for RLS. Finally, from thestability theory point of view, this work also tries toaddress an open question by Elisseeff & Pontil (2003):“Is there a way to incorporate prior knowledge via stability?”, thus exposing a connection between stability
and the Hypothesis Transfer Learning.
The rest of the paper is organized as follows. We formally state the HTL problem in Section 2 and introduce analyzed algorithms in Section 4. The main result comes in Section 5, particularly in Theorem 2,
with implications discussed in Section 5.1. The proofof the main result can be found in Section 5.2, while
related work on DA and HTL is covered in Section 3.
Finally we draw some conclusions and discuss future
work in Section 6.

2. Definitions and Problem Setting
In the following, we denote with small and capital bold
letters respectively column vectors and matrices, e.g.
α = [α1 , α2 , . . . , αd ]T ∈ Rd and A ∈ Rd1 ×d2 . The expected value of a random variable distributed according to p is denoted by Ez∼p [·], and multiple randomvariables as Ez∼p,z0 ∼p [·].
Denoting by X and Y respectively the input and output space of the learning problem, the training set S
is defined as {(xi , yi ) : 1 ≤ i ≤ m}, drawn i.i.d. fromX × Y according to the probability distribution µ. We
also define a supervised learning algorithm as follows.
Definition 1 (Supervised learning algorithm). A supervised learning algorithm is a map
A : (X × Y)m 7→ F ⊆ Y X
that maps the training set S onto a hypothesis fS ∈ F.

The LOO training set is defined as S \i ={(xj , yj ) : 1 ≤ j ≤ i − 1 and i + 1 ≤ j ≤ m} andhypothesis fS \i is produced by an algorithm A given
training set S \i .
To measure the accuracy of a learning algorithm, we
introduce the non-negative loss function `(f, (x, y)),which measures the cost incurred predicting f (x) instead of y. In the following we will focus on the squareloss, `(f, (x, y)) = (f (x) − y)2 , for its appealing computational properties.
The expected risk of a hypothesis fS , with respect tothe probability distribution p, is then defined as
Rp (A, S) = Rp (fS ) := E(x,y)∼p [`(fS , (x, y))],while the empirical risk ismR̂(A, S) :=1 X`(fS , (xi , yi )).
m i=1

We also define the LOO risk asm
1 X`(fS \i , (xi , yi )).
R̂ loo (A, S) :=m i=1
2.1. Hypothesis Transfer Learning Problem
In addition to the training set S for the target domain,drawn according to µ, we now introduce a source domain. Let X 0 and Y 0 be respectively the input andoutput space of a source domain. The source training
set S 0 = {(x0i , yi0 ) : 1 ≤ i ≤ m0 } is drawn i.i.d. fromX 0 × Y 0 according to the probability distribution µ0 .
Denote by f 0 the hypothesis generated by any learning algorithm over the source training set S 0 . The aimof an HTL algorithm is to use the source hypothesis
f 0 to improve the performance of a supervised learning algorithm over S. More formally, we define HTL
algorithm as follows
Definition 2 (HTL algorithm). An HTL algorithm isa map
Ahtl : (X × Y)m × F 0 7→ F ⊆ Y X(1)that maps S and the source hypothesis f 0 ∈ F 0 onto atarget hypothesis fShtl ∈ F.
The aim of the HTL algorithm is to satisfy the Improvement Condition (IC):Rµ (Ahtl , (S, f 0 )) ≤ Rµ (Ahtl , (S, 0)) .

(2)

We define a failure to satisfy IC as a negative transfer.
Note that we do not assume any relationship betweenµ and µ0 . We are only interested in the observable
improvement of the generalization error on the target
domain.

Stability and Hypothesis Transfer Learning

3. Related Work
We start by introducing related work from DA field,
closely related to the HTL problem. Most DA algorithms can de described by the general map
0

ADA : (X ×Y)m ×X mu ×(X 0 ×Y 0 )m 7→ F ⊆ Y X , (3)where in addition to previous notation, mu is the sizeof unlabeled set. Typically it is assumed that m  m0 ,m  mu and µ, µ0 are different.
A theoretical analysis of (3) has been proposed by BenDavid et al. (2010a), considering case m = 0, and alternatively m > 0, but m  m0 . The work provesa VC-bound on the expected risk of a target hypothesis, when the target hypothesis minimizes a convex
combination of the empirical source and target risks.
Hence the optimal DA algorithm critically depends
on weight parameters that control the importance ofsource and target distributions. However, these optimal parameters depend on a divergence term between
unlabeled training samples drawn from source and target marginal distributions, that appears additively intheir bound. The nature of this divergence term waslater explained by Ben-David et al. (2010b): the additive divergence term is inevitable unless an algorithm
has access to labeled training data from the target domain. A similar setting was also examined by Mansour
et al. (2009b), who instead derived Rademacher complexity bounds, but in practice proposed a very similar
sample reweighting scheme. Once again, an additive
divergence term appears in the bounds. Although related, problem (1) is not directly reducible to (3), since
it depends on the properties of the learning algorithm
that generates the source hypothesis. Apart from that,the source domain is inaccessible. These facts render
the mentioned DA bounds inapplicable for analysis of
the Hypothesis Transfer Learning.
As pointed out by Mansour et al. (2009a), the source
training set (or multiple sets) might not be available
due to the prohibitive size. With this motivation for
HTL they attack a multiple source type of problem (1).
They pose an assumption that the target distributionµmix is a mixture of n source distributions. With nsource hypotheses, it was shown, that if Rµ0i (fi0 ) ≤Pn ∀i ∈ {1, . . . , n}, then Rµmix ( i=1 βi fi0 (x)) ≤  +δ, δ ≥ 0. The result is insightful, since it relates therisk of target and source hypotheses. However, again,
the optimal weights depend on unknown quantities
that are estimated from unlabeled samples, partiallydefeating the original purpose of the algorithm.
HTL have been also considered from Bayesian perspective. Li & Bilmes (2007) have analyzed a Bayesian approch to solving (1) via PAC-Bayes bounds and arrived

at an additive KL-divergence term. It was shown thatfor logistic regression, the divergence term is upperbounded by kf − f 0 k, leading to biased regularizationin the learning algorithms. Indeed, Bayesian linear
regression with f 0 -mean Gaussian prior over f leads
to exact recovery of kf − f 0 k in optimization problem (Bishop, 2006). Another example of the Bayesian
HTL approach was proposed by Fei-Fei et al. (2006) for
visual object detection task. Results of Li & Bilmes(2007) hint that generative methods like the one in
Fei-Fei et al. (2006) could also be related to biased
regularization.
A number of empirical attempts have tried to justify
HTL. An SVM-like algorithm with regularizer kf −f 0 k
was proposed by Yang et al. (2007) for video concept detection task. Orabona et al. (2009) suggested
a parametrized variant kf − βf 0 k for Least-Squares
SVM, then extended to multiple sources by Tommasi
et al. (2010). Leveraging on this idea, a recent HTL
multiclass formulation explored a class-incremental
transfer setting (Kuzborskij et al., 2013). While someof these methods demonstrated impressive practicalpotential, their theoretical nature remains unclear.
We also briefly mention that variance bounds on the
LOO risk were derived by Zhang (2003). In our work
we are more interested in the generalization ability of
the algorithm, that is estimated through the conceptof algorithmic stability (Bousquet & Elisseeff, 2002)
and the LOO risk.

4. Hypothesis Transfer Learning
through Regularized Least Squares
Without loss of generality, in the following we willassume that Y, Y 0 = [−B; B], where B ∈ R andkxk ≤ 1, x ∈ X = Rd .
We will consider linear algorithms, extended to nonlinear ones through the use of kernels. Hence f (x)will be expressed as the inner product of a vector w,
learned from the training data, and the sample x.
We assume, that only the target training set S andsource hypothesis f 0 are given, so that the source training set S 0 is not required. The main objective of thisanalysis is to identify the effect of f 0 on the generalization properties of Ahtl . For this reason, we would
like to bound the expected risk of Ahtl with terms depending on the characteristics of f 0 . In particular,
we expect that a smaller risk Rµ (f 0 ) should improve
the generalization of Ahtl , compared to the case whenf 0 ≡ 0.
As said above, we proceed by specializing Ahtl to aStability and Hypothesis Transfer Learning

particular class of algorithms, the RLS with biased
regularization. This will allow us to arrive at a generalization bound where all the relevant quantities arecomputable in a closed form.
4.1. Biased Regularized Least Squares
The RLS algorithm consists in solving the following
optimization problem
m

min
u

1 X >
(u xi − yi )2 + λkuk2 .
m i=1

(4)

The interest of RLS lies in its strong theoretical guarantees and in the fact that solution can be expressedin a closed form (Rifkin et al., 2003). As a useful consequence, its LOO prediction function is expressed inclosed form as well, allowing a very efficient model selection (Cawley & Talbot, 2007). It is also possible toarrive at (4) from a Bayesian perspective by putting
a 0-mean Gaussian prior over the parameters of a linear regression model (Bishop, 2006). Note that thesame formulation can be used for both classification
and regression problems (Rifkin et al., 2003).
0Assuming that the source hypothesis f (x) is expressed as x> w0 , and w0 belongs to the same spaceof w, Orabona et al. (2009) proposed the use of a biased regularization to solve hypothesis transfer learning problems efficiently. More formally they defined
the following algorithm.
Algorithm 1. The Hypothesis Transfer Learning Algorithm based on Regularized Least Squares produces ahypothesis fShtl (x) = x> wS , wherem

1 X >(u xi − yi )2 + λku − w0 k2 . (5)wS = argmin
m i=1
uAnalogously, one can see the formulation of an Algorithm 1 as a Bayesian linear regression with w0 -mean
Gaussian prior distribution. The solution of an Algorithm 1 can be expressed in closed form, in fact fromthe first order optimality condition we get
wS = argminu

1kX > u − yk2 + λku − w0 k2
m⇒ X(X > wS − y) + mλ(wS − w0 ) = 0
>

>

(6)

0

⇒ X(X ŵS + X w − y) + mλŵS = 0⇒ (XX > + mλI)ŵS = Xy − XX > w0
⇒ ŵS = (XX > + mλI)−1 X(y − X > w0 )⇒ ŵS = X(X > X + mλI)−1 (y − X > w0 )where in (6) we used ŵS := wS − w0 and in thelast step we used the identity (XX > + mλI)−1 X =X(X > X + mλI)−1 to express the solution in dual
variables. So, the solution to the problem is given by
wS = X(X > X + mλI)−1 (y − X > w0 ) + w0 , due thedefinition of ŵS .
Using the fact that the LOO risk of Algorithm 1 canbe written in closed form, Orabona et al. (2009) proposed to weight the source hypothesis w0 by a scalarβ, optimized in order to minimize the LOO risk.
In the following we show how to generalize this approach to the generic source hypotheses f 0 and how to
obtain a generalization guarantee for it.

5. Analysis by Hypothesis Stability
We now propose a more general version of Algorithm 1.
Algorithm 2. RLS transfer algorithm by altering
training set as {(xi , yi − f 0 (xi )) : 1 ≤ i ≤ m} produces a hypothesis
0fShtl (x) = TC (x> ŵS ) + f 0 (x),
where
m

1 X >
(u xi − yi + f 0 (xi ))2 + λkuk2 ,ŵS := argmin
m i=1
uand the truncation function TC (ŷ) is defined as
TC (ŷ) = min(max(ŷ, −C), C).
If f 0 (x) is equal x> w0 , where w0 belongs to the same
space of wS , and C = ∞, Algorithms 1 and 2 arecompletely equivalent, because they have exactly thesame solution. However, Algorithm 2 is more generalbecause it allows w0 to belong to a different space.
Hence it captures the notion of biased regularization,and generalizes it to any type of source hypothesis f 0 .
This algorithm also captures and generalizes many of
the ideas present in the previous works on HTL (FeiFei et al., 2006; Yang et al., 2007; Orabona et al., 2009;
Mansour et al., 2009a; Tommasi et al., 2010). Still theuse of a specific loss, the square loss, will allow us
to have an efficient computation as well. Also, thisformulation allows to truncate the prediction within
the range [−C; C], that helps to greatly improve thetheoretical guarantees and the practical performance
too. In fact it is easy to see that if C ≥ B + kf 0 k∞ ,then (TC (x> ŵS ) + f 0 (x) − y)2 ≤ (x> ŵS + f 0 (x) − y)2 .
Our goal is to upper bound the expected risk of Algorithm 2, keeping in mind the effect of f 0 . To this end,
we propose to employ the stability framework of Bousquet & Elisseeff (2002). Our choice is motivated by thefact that bounds arising from the stability analysis arefree from complexity measures. Hence, the generalization bound of interest will be composed mostly fromStability and Hypothesis Transfer Learning

computable quantities, thus making it more practical,
e.g. for finding the optimal transfer parameters.
In particular, we can upper bound the moments of therandom variable Rµ (A, S)−R̂ loo (A, S) with a quantitythat captures the stability of the learning algorithm.
The second order moment can then be used to obtainpolynomial bounds, through the Chebyshev’s inequality (Bousquet & Elisseeff, 2002).
There exist various definitions of stability (Bousquet& Elisseeff, 2002), but the one we will use is the hypothesis stability.
Definition 3 (Hypothesis Stability (Bousquet & Elisseeff, 2002)). An algorithm A has a hypothesis stability
γ with respect to the loss function ` if ∀i ∈ {1, . . . , m}
the following holds

Note that our bound in the worst case loses only aconstant multiplicative factor with respect to the oneof Bousquet & Elisseeff (2002).
With this theorem we can prove the following result.
1
Theorem 2. Set λ ≥ m. If C ≥ B + kf 0 k∞ , then for
Algorithm 2 we have00

ES [(Rµ (fShtl ) − R̂ loo (fShtl ))2 ]Rµ (f 0 )+ Rµ (f 0 )
TC 2
λ
 .
= O C 2mλIf C = ∞, then for Algorithm 2 we have00

ES [(Rµ (fShtl ) − R̂ loo (fShtl ))2 ]Rµ (f 0 )(kf 0 k∞ + B)2
.
=O
mλ3

ES,(x,y) [|`(fS , (x, y)) − `(fS \i , (x, y))|] ≤ γ .
We will use a slight variation of the polynomial boundof Bousquet & Elisseeff (2002). The reason is, that
the Theorem 11 of Bousquet & Elisseeff (2002) has
2
the term M2 , that is not affected by Rµ (f 0 ). Instead,2
we exchange M2 for the term ES [`(fS \i , zi )].
Theorem 1. For a supervised learning algorithm
A with hypothesis stability γ, and M such that`(fS \i , (x, y)) ≤ M , for any i ∈ {1, . . . , m}, we have
ES [(Rµ (A, S) − R̂ loo (A, S))2 ]≤M ES [`(fS \i , (xi , yi ))]+ 3M γ .
m
2

Proof (Sketch). We trace the occurrence of M
2m to theproof of Lemma 9 (Bousquet & Elisseeff, 2002). At
the beginning of the proof they suggest the following
inequality
ES [(Rµ (f ) − R̂ loo (f ))2 ]1≤ ES [`(fS \i , zi )(M − `(fS \i , zj ))]m+ ES,z,z0 [`(fS \i , z)`(fS \i , z 0 ) − `(fS \i , z)`(fS \i , zi )]+ ES,z,z0 [`(fS \i , zi )`(fS \i , zj ) − `(fS \i , z)`(fS \i , zi )] .
Here we are only interested in first term, since it
2is the origin of the term M
2m . Using the fact that`(fS \i , zj ) ≥ 0, we have1
ES [`(fS \i , zi )(M − `(fS \i , zj ))]m1= ES [`(fS \i , zi )(M − `(fS \i , zj ))]m
M≤ES [`(fS \i , zi )] .
m

The proof can be found in Section 5.2, while in the next
Section we discuss the implications of this theorem.
5.1. ImplicationsFirst consider the case of f 0 ≡ 0. This case corresponds to learning without any source hypothesis,
without transfer learning. If we set C = ∞, wehave that the second-order moment is bounded byB4
O mλ, which is exactly the bound that can be ob3
tained using the results in Bousquet & Elisseeff (2002)
for RLS. We see this by combining Theorem 11 with
Lemma 23and obtaininga polynomial generalization

2
B√
1
bound O λ1.5 m . Considering the second moment,
the bound matches ours.
However, if we know the range [−B; B], we can set
C accordingly andthat the second moment is 2 obtainBbounded by O mλ. Thanks to the truncation, thebound is greatly improved over the polynomial boundwith square loss in Bousquet & Elisseeff (2002).
We now turn our attention to the case where f 0 6≡ 0.
In this case, the key quantity is Rµ (f 0 ), an indirect
measure of how the source and target domains are related. This term takes the role of the divergence between source and target distribution (Ben-David et al.,2010a;b; Mansour et al., 2009b), however, this is amore intuitive measure which is directly linked to theloss: how the source hypothesis is going to perform on
the target domain, the new task? In addition, it is multiplicative to all bound terms, while mentioned divergence terms are additive, even if the bounds are generally incomparable. Based on its value, we have various
1
The same bound also appears in (De Vito et al., 2005)(p17, footnote 2).

Stability and Hypothesis Transfer Learning
R (f 0 )regimes of interest. If µλ→ 0, we have the sur00
prising result that ES [(Rµ (fShtl ) − R̂ loo (fShtl ))2 ] → 0.
This implies that the expected risk approaches the
LOO risk, with probability 1. In other words, thetransfer learning decreases the variance of the LOO
in case when the source and target domains are related. This also implies that we can expect the tuningof any parameter of the algorithm (e.g. the type ofkernel) through the minimization of the LOO risk, tohave optimal performance, even with a small training
set. This is the first theoretical explanation of why thealgorithms of Orabona et al. (2009); Tommasi et al.
(2010) showed reliable performance despite a small
training set. Note that Rµ (f 0 ) has to be small withrespect to λ. In other words, the better the source hypothesis on the target domain, the more stable an HTL
algorithm must be according to Theorem 3. Looking
at Algorithm 1, this makes sense, since a very stablealgorithm will generate a hypothesis that does not deviate much from the source w0 .

(2010) already realized the empirical need to constrainβ, but here we demonstrate a principled form of theregularization. Note that the O(·) notation used in
the bound above hides the confidence variable δ, whichshould be tuned. Yet, here we are mainly interested
in the correct form of the objective function for finding the transfer parameters, as a way of using theory
to guide practice. Moreover, regardless of the specificprocedure used to estimate the optimal value of β, as
noted above we expect the algorithm to be robust to
negative transfer, at least in the asymptotic limit.

So far we have outlined the benefits of Rµ (f 0 ), but it
is reasonable to ask what happens when this quantity
is high, that is when the two domains are unrelated.
From the bound, we see that Algorithm 2 is also robust
against a mispecified source hypothesis f 0 . In fact, due
to truncation, the rate is exactly the same as obtainedin the non-transfer case. If we supply the algorithmwith a “bad” source hypothesis, in the limit it will havethe performance of an algorithm that learns just using
the training set. Again, this robustness is achieved
also thanks to the truncation, which avoids excessive
growth of the loss. In other words, Algorithm 2 isresistant to negative trasfer. We actually suspect thatthe truncation is necessary only for the proof, and infact, Tommasi et al. (2010) already noticed this robust
behaviour for Algorithm 1.

We first present two technical lemmas. The first one
is needed to bound the effect of the truncation, thesecond one is a closed-form formula for calculating thechange in truncated predictions of RLS when a new
sample point is added. This result is related to thewell-known closed-form formula for LOO risk for RLS,
e.g. see Cawley & Talbot (2007).
Lemma 1. Let α ≥ 1, and C ≥ |y|, thenWe now consider the case when the source hypothesis
f 0 is a weightedPcombination of n source hypothesesnfi0 , that is f 0 = i=1 βi fi0 . This weighting strategy isequivalent to the ones used in the works on DA, butwith the important difference that now these weights
can be efficiently estimated from the target training
set. In particular, one interpretation of the Theorem 2
yields


0
0
kβk2
.
min Rµ (fShtl ) ≤ min R̂ loo (fShtl ) + O √ββλmHence the bound suggests an efficient and principled
way to find β = [β1 , . . . , βn ]> . In other words, it
is enough to minimize the LOO risk with respect toβ, taking into account the regularization term, thus
turning β into a parameter of an optimization problem. Note that Orabona et al. (2009); Tommasi et al.

5.2. Proof of Theorem 2
To prove the bound of Theorem 2 we need to upperbound the quantities M , γ, and ES [`(fS \i , zi )] of Theorem 1. To do so, we proceed by stating and proving
additional lemmas. Particularly, M and ES [`(fS \i , zi )]are considered in Lemma 4, while γ is bounded in Theorem 3.

2(TC (∆) − y) ≤ (TC (y + α(∆ − y)) − y)22

≤ α2 (TC (∆) − y) .
Proof. We only prove the upper bound, noting thatthe proof of the lower bound is similar. The proof follows from an analysis of all the possible cases. The
lemma trivially holds when |y + α(∆ − y)| ≤ C. For∆ > C, the bound holds because y + α(∆ − y) >C; the same reasoning applies for ∆ < −C. The+ y < ∆ < C. We havelast case is when C−yα2(TC (y + α(∆ − y)) − y) = (C − y)2 . Note that C ≥ yimplies that C−y
α + y > y, so ∆ > y and this implies
the stated bound. The case is analogous −C < ∆ <− C+y
α + y: we have that TC (y + α(∆ − y)) = −C andC+y− α + y ≤ y because C + y ≥ 0, hence ∆ < y.
Lemma 2. Let wS be the hypothesis produced by the
RLS algorithm given training set S. For any i-th sample (x̂, ŷ) ∈ S, we have that the hypothesis wS \i produced by the same RLS algorithm on a training set S \isatisfies(TC (x̂> wS ) − ŷ)2 ≤ (TC (x̂> wS \i ) − ŷ)2

2
1
≤ 1+
(TC (x̂> wS ) − ŷ)2 .
mλStability and Hypothesis Transfer Learning

Proof. We define

Proof. The wS \i is given by
wS \i = argminum1
kX > u − yk22 + λkuk2 ,mQ(u) :=

where X is a matrix d×(m−1) and y an m−1 dimensional vector, respectively the matrix of the training
samples and vector of the training labels without the
sample i. Let M := X > X + mλI, then>>x̂ wS \i = x̂ XM−1Using the definition of ŵS in Algorithm 2, we havethat
Q(ŵS ) ≤ Q(0) = R̂(f 0 ) .
(9)0)
Hence we get kŵS k2 ≤ R̂(fλ . Nowy.

ES kŵS k2 ≤It is straightforward to see that x̂> wS is equal to


>

x̂ X

2

kx̂k





M
x̂> X

X > x̂
kx̂k2 + mλ

−1 

y
ŷ

.

−1 

M
X > x̂
M −1 0=0>
0x̂> X kx̂k2 + mλ
1 M −1 X > x̂  >+x̂ XM −1 −1 ,−1aLemma 4. Assume (x, y) drawn according to µ. For
Algorithm 2 the following bounds hold ∀i ∈ {1, . . . , m}


≤

>

−1

(8)

>

We proceed by bounding ES [`(wS \i , (xi , yi ))], and M
in Lemma 4.
Lemma 3. The following bounds hold for the hypothesis ŵS produced by the Algorithm 2
1
Rµ (f 0 ) ,λ

1kŵS k2 ≤ (B + kf 0 k∞ )2 .
λ
2  
2
B + kf 0 k∞
0√
+ B + kf k∞ ,TC
λES [(TC (x> ŵS ) − y + f 0 (xi ))2 ]Rµ (f 0 )0
+ Rµ (f ) .
≤ 2 TC 2λProof. We use Lemma 2, and the Cauchy-Schwarz inequality to derive

Observing that 0 ≤ x̂ XM X x̂ ≤ kx̂k2 , we have2athat 1 ≤ mλ
≤ 1 + kx̂kmλ , hence we use the upperbound in Lemma 1 to derive the stated upper bound.
Analogously, the lower bound follows from (8) and thelower bound in Lemma 1.

ES kŵS k2 ≤

1
1+
mλ

and

a − mλ >(x̂ wS \i − ŷ) .
a(TC (x̂> wS \i ) − ŷ)2

2
  a
(x̂> wS − ŷ) + ŷ − ŷ
.
= TC
mλ

1 X 0
1
(f (xi ) − yi )2 ≤ (B + kf 0 k∞ )2 .
mλ i=1
λx,ySo we haveandmkŵS k2 ≤sup (TC (x> ŵS \i ) − y + f 0 (x))2

where a := kx̂k2 + mλ − x̂> XM −1 X > x̂. Plugging
this result into (7) yields
x̂> wS = x̂> wS \i −1
1
ES R̂(f 0 ) = Rµ (f 0 ) .
λλFor the second upper bound, from (9) it also follows

(7)
Expanding the middle term and using the block-wisematrix inversion property (Petersen & Pedersen, 2008)
we get

1 X >(x u − yi + f 0 (xi ))2 + λkuk2 .
m i=1 isup (TC (x> ŵS \i ) − y + f 0 (x))2
x,y


2
1
1+
sup (TC (x> ŵS ) − y + f 0 (x))2
mλ
x,y
2

2
1
sup |TC (x> ŵS )| + B + kf 0 k∞ .
≤ 1+
mλ
x,y
≤

The term |TC (x> ŵS )| can be simultaneosly upperbounded using C and, using Cauchy-Schwarz inequality, by kŵS k. Hence using the second result ofLemma 3 we obtain the first result.
For the second upper bound, using the elementary inequality (a + b)2 ≤ 2(a2 + b2 ), in an analogous way wehave
ES [(TC (x> ŵS ) − y + f 0 (x))2 ]≤ 2ES [(TC (x> ŵS ))2 + (f 0 (x) − y)2 ]= 2 ES (TC (x> ŵS ))2 + Rµ (f 0 ) .

Stability and Hypothesis Transfer Learning

Again, the first term in the left hand side of the lastinequality can be simultaneosly upper bounded using
C 2 and, using Cauchy-Schwarz inequality, by kŵk2 .
Hence the first result of Lemma 3 concludes the proof.

Now, we are ready to upper-bound the hypothesis stability for Algorithm 2.
Theorem 3. The hypothesis stability of Algorithm 2
is upper bounded as





1
Rµ (f 0 )
4
0
2+
TC 2
+ Rµ (f ) .
γ≤
mλ
mλ
λ
Proof. We start by upper bounding the | · | termin the hypothesis stability from Definition 3. Using
Lemma 2, with ŷ = y − f 0 (x) and x̂ = x, we have002(fShtl (x) − y)2 − (fShtl\i (x) − y)
0

0

2
htl
= (fShtl(x) − y)2\i (x) − y) − (fS= (TC (x> ŵS \i ) − y + f 0 (x))2 −(TC (x> ŵS ) − y + f 0 (x))2!
2

1− 1 (TC (x> ŵS ) − y + f 0 (x))2 .
≤1+
mλTaking now the expectation with respect to S and using the second result of Lemma 4 we have the statedbound.
With the results above is now easy to prove Theorem 2.
Proof of Theorem 2. Using the upper bound inLemma 2 and the second result in Lemma 4, we have
ES [`(fS \i , (xi , yi ))]

2 



1
Rµ (f 0 )
≤2 1+
TC 2
+ Rµ (f 0 ) .
mλλ
It is now enough to introduce the upper bounds on M
(first result of Lemma 4), γ, and ES [`(fS \i , zi )] into
Theorem 1.

6. Conclusions and Future WorkIn this paper we have formally introduced the HTL
problem and analyzed a class of RLS algorithms withbiased regularization that can be used to solve thisproblem. Our main result is a generalization boundin terms of the Leave-One-Out (LOO) risk, obtained
through the notion of hypothesis stability. We pointout the key quantity Rµ (f 0 ) and expose its theoreticaland practical advantages over analogues in the theory
of DA. In particular, we showed that if source andtarget domains are related, hence Rµ (f 0 ) is small, theLOO risk converges faster to the expected risk andthe HTL decreases the variance of the LOO. In thecase of unrelated domains, we still match the theoretical guarantees of Regularized Least Squares trained
solely on the target domain. As a side effect of ouranalysis, thanks to the truncation we have improved
the polynomial generalization bounds of Bousquet &Elisseeff (2002) for RLS2 .
In future work, we will focus on the theoretical extension to a more general class of algorithms. Since it
is possible to express the LOO predictions in a closed
form for Algorithm 2, we intend to analyze its stability
with respect to any positive loss function, decoupling
the loss used in the algorithm from the one used in theanalysis, in a similar way as in, e.g., Orabona et al.
(2012). Accomplishing that suggests the possiblity for
analysis of intriguing HTL scenarios through different
loss functions, such as multiclass and hierarchical classification.
Another direction lies in improving the results by obtaining high probability bounds. We note that Bousquet & Elisseeff (2002) have also proved high probability bounds for another notion of stability, the uniform
stability, but the assumption is too strong in our case,since it relates stability to the infinity norm of thelosses which cannot be linked to the definition of thesource risk Rµ (f 0 ). The rigid assumption on uniform
stability was also noted by Kutin & Niyogi (2002), whoproved exponential PAC-style bounds for weaker notions of stability. However we forecast two problems
with applying their framework. First, the bound on
the loss is additive in the generalization bound andcannot be linked to the source risk. In our case wemanaged to avoid this by modifying the proof of Bousquet & Elisseeff (2002) in Theorem 1 and an analogous
and non-trivial change of Kutin & Niyogi (2002) results would be needed. Second, the alternative framework only bounds the discrepancy of expected andempirical risks. Instead we prefer to study the use
the LOO risk, since it is empirically more robust withsmall training set.

Acknowledgments
I.K. is supported by the Swiss National Science Foundation Sinergia project Ninapro.
2
The suboptimality of bounds in Bousquet & Elisseeff(2002) for RLS is also discussed by Zhang (2003).

Stability and Hypothesis Transfer Learning

References
Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A.,
Pereira, F., and Vaughan, J.W. A theory of learningfrom different domains. Machine Learning, 79(1):151–175, 2010a.
Ben-David, S., Lu, T., Luu, T., and Pál, D. Impossibility Theorems for Domain Adaptation. JMLR
W&CP, 9:129–136, 2010b.
Bishop, C.M. Pattern Recognition and Machine Learning. Springer-Verlang New York, 2006.
Bousquet, O. and Elisseeff, A. Stability and Generalization. Journal of Machine Learning Research, 2:499–526, 2002.
Cawley, G. C. and Talbot, N. L. C. Preventing OverFitting during Model Selection via Bayesian Regularisation of the Hyper-Parameters. Journal of Machine Learning Research, 8:841–861, 2007.

Mansour, Y., Mohri, M., and Rostamizadeh, A. Domain Adaptation with Multiple Sources. In Advances in neural information processing systems,
volume 21, pp. 1041–1048, 2009a.
Mansour, Y., Mohri, M., and Rostamizadeh, A. Domain adaptation: Learning bounds and algorithms.
In Computational Learning Theory, 2009b.
Orabona, F., Castellini, C., Caputo, B., Fiorilla, A.E.,
and Sandini, G. Model Adaptation with LeastSquares SVM for Adaptive Hand Prosthetics. In
Robotics and Automation, IEEE International Conference on, pp. 2897–2903. IEEE, 2009.
Orabona, F., Cesa-Bianchi, N., and Gentile, C. Beyond logarithmic bounds in online learning. In International Conference on Artificial Intelligence andStatistics (AISTATS), 2012.
Petersen, K.B. and Pedersen, M.S. The matrix cookbook. Technical University of Denmark, 2008.

Cortes, C., Mohri, M., Riley, M., and Rostamizadeh,
A. Sample Selection Bias Correction Theory. In
Algorithmic Learning Theory, pp. 38–53. Springer,
2008.

Rifkin, R., Yeo, G., and Poggio, T. Regularized
Least-Squares Classification. In Advances in Learning Theory: Methods, Models and Applications, pp.
131–154. VIOS Press, 2003.

De Vito, E., Caponnetto, A., and Rosasco, L. Model
Selection for Regularized Least-Squares Algorithm
in Learning Theory. Found. Comput. Math., 5(1):59–85, February 2005.

Tommasi, T., Orabona, F., and Caputo, B. Safety
in Numbers: Learning Categories from Few Examples with Multi Model Knowledge Transfer. In
Computer Vision and Pattern Recognition (CVPR),
IEEE Conference on, pp. 3081–3088. IEEE, 2010.

Elisseeff, A. and Pontil, M. Leave-one-out Error andStability of Learning Algorithms with Applications.
In Advances in Learning Theory: Methods, Models
and Applications, pp. 111–125. VIOS Press, 2003.
Fei-Fei, L., Fergus, R., and Perona, P. One-shotlearning of object categories. Pattern Analysis andMachine Intelligence, IEEE Transactions on, 28(4):594–611, 2006.
Kutin, S. and Niyogi, P. Almost-everywhere algorithmic stability and generalization error. In Eighteenth
conference on Uncertainty in artificial intelligence,
pp. 275–282, 2002.
Kuzborskij, I., Orabona, F., and Caputo, B. From N to
N+1: Multiclass Transfer Incremental Learning. In
Computer Vision and Pattern Recognition (CVPR),
IEEE Conference on. IEEE, 2013.
Li, X. and Bilmes, J. A bayesian divergence priorfor classifier adaptation. In Eleventh International
Conference on Artificial Intelligence and Statistics,
2007.

Yang, J., Yan, R., and Hauptmann, A.G. CrossDomain Video Concept Detection Using Adaptive
SVMs. In Proceedings of the 15th international conference on Multimedia, pp. 188–197. ACM, 2007.
Zhang, T. Leave-one-out Bounds for Kernel Methods.
Neural Computation, 15(6):1397–1437, 2003.